math.OCApr 7, 2026

Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates

Authors: Yao Ji, Guanghui Lan

Organizations: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, 225 North Ave, Atlanta, GA 30332, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Achieving optimal rates for stochastic composite convex optimization without prior knowledge of problem parameters remains a central challenge. In the deterministic setting, the auto-conditioned fast gradient method has recently been proposed to attain optimal accelerated rates without line-search procedures or prior knowledge of the Lipschitz smoothness constant, providing a natural prototype for parameter-free acceleration. However, extending this approach to the stochastic setting has proven technically challenging and remains open. Existing parameter-free stochastic methods either fail to achieve accelerated rates or rely on restrictive assumptions, such as bounded domains, bounded gradients, prior knowledge of the iteration horizon, or strictly sub-Gaussian noise. To address these limitations, we propose a stochastic variant of the auto-conditioned fast gradient method, referred to as stochastic AC-FGM. The proposed method is fully adaptive to the Lipschitz constant, the iteration horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures. Under standard bounded conditional variance assumptions, we show that stochastic AC-FGM achieves the optimal iteration complexity of O(1/ε)O(1/\sqrt{\varepsilon}) and the optimal sample complexity of O(1/ε2)O(1/\varepsilon^2).

Figures & tables

 Gk=1mk∑i=1mkG(xk−1,ξk,i).\displaystyle G_{k}=\frac{1}{m_{k}}\sum_{i=1}^{m_{k}}G(x_{k-1},\xi_{k,i}). (2.1)
Algorithm 1 Stochastic AC-FGM
Figure 1: Illustration of the filtration {Fk}k∈N+\{\mathcal{F}_{k}\}_{k\in\mathbb{N}_{+}} and the intermediate σ\sigma -algebras Fk−13\mathcal{F}_{k-\frac{1}{3}} and Fk−23\mathcal{F}_{k-\frac{2}{3}} .
Figure 2: Illustration of the enlarged filtration {Fk}k∈N+\{\mathcal{F}_{k}\}_{k\in\mathbb{N}{+}} and the intermediate σ\sigma -algebra Fk−13\mathcal{F}_{k-\frac{1}{3}} and Fk−23\mathcal{F}_{k-\frac{2}{3}} .
More in this topic

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

Explore similar work

CardsList
Mar 6, 2026

Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first adaptive projection-free framework for stochastic composite nonconvex minimization that requires neither global smoothness constants nor line search. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an εε-stationary point, ALFCG-FS attains O(N+Nε−2)\mathcal{O}(N+\sqrt{N}ε^{-2}) iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve O~(σ2ε−4+ε−2)\tilde{\mathcal{O}}(σ^2ε^{-4}+ε^{-2}) and O~(σε−3+ε−2)\tilde{\mathcal{O}}(σε^{-3}+ε^{-2}), where NN is the number of components and σσ is the noise level. In contrast to typical O(ε−4)\mathcal{O}(ε^{-4}) or O(ε−3)\mathcal{O}(ε^{-3}) rates, our bounds reduce to the optimal rate up to logarithmic factors O~(ε−2)\tilde{\mathcal{O}}(ε^{-2}) as the noise level σ→0σ\to 0. Extensive experiments on multiclass classification over nuclear norm balls and ℓp\ell_p balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.

Ganzhao Yuan

Shenzhen University of Advanced Technology (SUAT), China

Nonconvex Stochastic OptimizationStochastic OptimizationStochastic Optimization Convergence
AskPDF
Jul 28, 2026

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(τmix/T)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↦2ΛGσ2σ^2\mapsto 2ΛG_σ^2 and L2↦2ΛL2L^2\mapsto 2ΛL^2, where Λ=O(τmixlog⁡T)Λ=O(τ_{\mathrm{mix}}\log T). For positive centered noise, the tuned method achieves expected sample complexity O~((τmix2Gσ+τmix5/2Gσ2)ε−3+τmix5ε−2)\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2}). The exactly noiseless specialization achieves O~(ε−2)\widetilde{O}(\varepsilon^{-2}) with mixing-time-free constants, while a mixing-time-oblivious variant achieves O~(τmix6ε−3+τmix3ε−2)\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

School of Computer Science Nanjing University of Information Science and Technology

Stochastic OptimizationNonconvex Stochastic OptimizationNonconvex OptimizationStochastic Optimization ConvergenceVariance Reduction
AskPDF
Sep 26, 2026

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal last-iterate rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Ω(log⁡T/T)Ω(\log T/\sqrt T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log⁡T\log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log⁡T\log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/T){O}(1/\sqrt{T}).

Weiming Ou, Xiao Wang

Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics

Convergence AnalysisAdaptive Gradient MethodsLast-Iterate Convergence
AskPDF