# Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates

arXiv: https://arxiv.org/abs/2604.06525 · HTML: https://mlsanity.com/paper/2604.06525/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 41 references that are in the map.
- First posted on arXiv 7 Apr 2026.

## Builds on (most cited first, 25 of 25)

- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [A Unified Approach to Adaptive Regularization in Online and Stochastic Optimization](https://mlsanity.com/paper/1706.06569/) (2017)
- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Accelerated Parameter-Free Stochastic Optimization](https://mlsanity.com/paper/2404.00666/) (2024)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization](https://mlsanity.com/paper/2310.12139/) (2023)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [High Probability Complexity Bounds for Adaptive Step Search Based on Stochastic Oracles](https://mlsanity.com/paper/2106.06454/) (2021)
- [An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization](https://mlsanity.com/paper/2505.11670/) (2025)
- [High-order Accumulative Regularization for Gradient Minimization in Convex Programming](https://mlsanity.com/paper/2511.03723/) (2025)
- [A Parameter-Free Stochastic LineseArch Method (SLAM) for Minimizing Expectation Residuals](https://mlsanity.com/paper/2512.14979/) (2025)

## Abstract (arXiv)

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/√varepsilon) and the optimal sample complexity of O(1/varepsilon2).