Organizations: School of Computer Science and Engineering, Nanjing University of Science and Technology, China · 2State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
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 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 m1∑i=1mfi(gi(w)), where each gi is accessible only through a stochastic oracle. The key challenge is to track g(w)=(g1(w),…,gm(w)) over time, where g(w) has m blocks but only 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 g(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 ∇fi are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.
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.
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(τ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↦2ΛGσ2 and L2↦2ΛL2, where Λ=O(τmixlogT). For positive centered noise, the tuned method achieves expected sample complexity O((τmix2Gσ+τmix5/2Gσ2)ε−3+τmix5ε−2). The exactly noiseless specialization achieves O(ε−2) with mixing-time-free constants, while a mixing-time-oblivious variant achieves O(τmix6ε−3+τmix3ε−2). All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.
Stochastic compositional optimization minimizes objectives of the form minx∈XF(f(x),x), where 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 O(K−1/4) convergence rate in the generalized Frank--Wolfe gap for non-convex objectives with LF-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∈(1,2] and recovers the deterministic rates of Vladarean et al (2023) as the noise vanishes.