Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator

Wei Jiang; Sifan Yang; Yibo Wang; Lijun Zhang; Zechao Li

cs.LGSep 14, 2026

Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator

Authors: Wei Jiang, Sifan Yang, Yibo Wang, Lijun Zhang, Zechao Li

Abstract

Traditional variance reduction methods (e.g., SPIDER, SARAH, STORM) have been extensively investigated for improving the convergence rates of stochastic optimization. These techniques typically maintain a sequence of estimators for a single function (or gradient) across iterations. However, what if we need to track multiple functions, but can only access stochastic samples of $\mathcal{O}(1)$ functions at each iteration? This scenario arises in an important emerging family of finite-sum coupled compositional optimization (FCCO) problems of the form $\frac{1}{m}\sum_{i=1}^m f_i(g_i(\mathbf{w}))$ , where each $g_i$ is accessible only through a stochastic oracle. The key challenge is to track $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ over time, where $\mathbf g(\mathbf{w})$ has $m$ blocks but only $\mathcal{O}(1)$ blocks can be probed for their stochastic values at each step. To address this challenge, we propose a novel Multi-block-Single-probe Variance Reduction (MSVR) estimator to efficiently trace $\mathbf g(\mathbf{w})$ under partial block sampling. Building on the MSVR estimator, we develop several algorithms for FCCO problems, achieving improved sample complexities for non-convex, convex, strongly convex, and Polyak-Łojasiewicz (PL) objectives. We further obtain an improved dependence on $m$ when the outer function gradients $\nabla f_i$ are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.

Explore similar work

Sep 14, 2026math.OC

Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization

This paper studies projection-free algorithms for stochastic constrained multi-level compositional optimization. In this context, the objective function is a nested composition of several smooth functions, and the decision set is closed and convex. Since projection onto the constraint set can be computationally expensive, we develop projection-free methods that rely on linear minimization oracles. For non-convex objectives, we propose variance-reduced projection-free algorithms and establish complexity guarantees under both the Frank-Wolfe gap and the gradient mapping criteria. We also develop momentum-based methods that achieve convergence guarantees under weaker smoothness assumptions. Additionally, by using a stage-wise design, we derive a parameter-free variant that preserves the same complexities for the Frank-Wolfe gap. Such a design can be further used to develop algorithms for convex and strongly convex functions whose rates match those of single-level projection-free counterparts. Finally, we consider finite-sum problems and derive complexities for non-convex, convex, and strongly convex objectives. Numerical experiments across multiple tasks demonstrate the effectiveness of the proposed methods.

Wei Jiang, Sifan Yang, Wenhao Yang +4

Convex Optimization

Ask PDF

Jul 28, 2026math.OC

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias

O(τ_{\mathrm{mix}}/T)

uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under

σ^2\mapsto 2ΛG_σ^2

and

L^2\mapsto 2ΛL^2

, where

Λ=O(τ_{\mathrm{mix}}\log T)

. For positive centered noise, the tuned method achieves expected sample complexity

\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})

. The exactly noiseless specialization achieves

\widetilde{O}(\varepsilon^{-2})

with mixing-time-free constants, while a mixing-time-oblivious variant achieves

\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})

. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Zhaojun Peng

Convex Optimization Nonconvex Monte Carlo

Ask PDF

May 14, 2026math.OC

Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Stochastic compositional optimization minimizes objectives of the form

\min_{\bm{x} \in \mathcal{X}} F(\bm{f}(\bm{x}), \bm{x})

, where

\bm{f}

is accessible only through noisy stochastic queries. Existing methods for this problem assume that the outer function

F

is continuously differentiable, which excludes many practically important applications such as robust max-of-losses, Conditional Value-at-Risk, and norm regularizers. We propose the Hybrid Momentum Stochastic Frank--Wolfe algorithm, which drops the smoothness assumption on

F

. By combining a momentum-based Jacobian tracker with a Taylor-corrected function tracker, the algorithm feeds an entire stochastic linearization -- rather than a single gradient -- into a generalized linear minimization oracle. We establish an

\mathcal{O}(K^{-1/4})

convergence rate in the generalized Frank--Wolfe gap for non-convex objectives with

L_F

-Lipschitz outer functions, matching the optimal complexity for projection-free single-sample stochastic methods under expected smoothness. The analysis extends to heavy-tailed noise oracles with bounded

r

-th moments for

r \in (1, 2]

and recovers the deterministic rates of Vladarean et al (2023) as the noise vanishes.

El Mahdi Chayti

Zeroth-Order Optimization Stochastic Momentum

Ask PDF