Stochastic Adaptive Gradient Descent Without Descent
Jean-Francois Aujol, Jérémie Bigot & Camille Castera · 2025
Read Stochastic Adaptive Gradient Descent Without Descent by Jean-Francois Aujol, Jérémie Bigot & Camille Castera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-14969.txt.
Introduction
Jean-François Aujol, Jérémie Bigot, and Camille Castera design step sizes for stochastic gradient descent that need no tuning and no line search, in a 2025 optimization paper. Gradient descent without descent is an adaptive method that reads local geometry from gradient information alone. Bringing that idea to noisy, stochastic gradients is the paper's goal, since most machine learning training uses noisy estimates.
Their strategy uses only a first-order stochastic oracle, the standard noisy gradient source, and adapts the step size from the local shape of the objective. Convergence proofs are given under several sets of assumptions for convex problems. In experiments, the untuned method competes with baselines whose step sizes were carefully tuned by hand. Removing the tuning burden matters because hyperparameter searches often cost more than the final training run.
Catalog record
| CREATOR | Jean-Francois Aujol, Jérémie Bigot & Camille Castera |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-14969
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Adaptive Gradient Descent Without Descent Jean-Francois Aujol, Jérémie Bigot & Camille Castera Abstract We introduce a new adaptive step-size strategy for convex optimization with stochastic gradient that exploits the local geometry of the objective function only by means of a first-order stochastic oracle and without any hyper-parameter tuning. The method comes from a theoretically-grounded adaptation of the Adaptive Gradient Descent Without Descent method to the stochastic setting. We prove the convergence of stochastic gradient descent with our step-size under various assumptions, and we show that it empirically competes against tuned baselines. 1 Introduction We consider the stochastic convex optimization problem \min_{x\in{\mathbb{R}}^{d}}f(x)=\min_{x\in{\mathbb{R}}^{d}}\mathbb{E}\left[f_{\xi}(x)\right], (1) where the expectation is taken with respect to some random variable \xi such that, f and f_{\xi}:{\mathbb{R}}^{d}\to{\mathbb{R}} are convex, differentiable and lower-bounded functions for all \xi . We furthermore assume that f has at least one minimizer x^{\star}\in\mathbb{R}^{d} , and we denote its smallest value by f^{\star}=f(x^{\star}) . When \xi follows a uniform distribution on subsets of \{1,\ldots,N\} (for some integer N>0 ), ( 1 ) reads \min_{x\in{\mathbb{R}}^{d}}f(x)=\min_{x\in{\mathbb{R}}^{d}}\frac{1}{N}\sum_{\ell=1}^{N}f_{\ell}(x), (2) where f_{1},\ldots,f_{N} is a set of convex, differentiable and lower-bounded functions. 1.1 Main contributions We introduce a new adaptive step-size strategy for stochastic gradient descent (SGD) to tackle ( 1 ). We build upon the adaptive strategy introduced by malitsky2019adaptive for deterministic (full batch) convex optimization. They propose a step-size that automatically adapts to the local geometry of f only by means of first-order oracle calls ( i.e., gradient evaluations). Their method has the notable advantages of not requiring any hyper-parameter tuning nor the global Lipschitz smoothness of the gradient of the objective function (Definition 1 ). While a stochastic version of the algorithm has been suggested in ( malitsky2019adaptive , Section 3) , it does not inherit the main advantages from the deterministic version: its implementation requires the careful tuning of a hyper-parameter, crucial to guarantee convergence. In contrast, we propose a different stochastic adaptation of their method that preserves the aforementioned advantages in the deterministic setting. As illustrated on Figure 1 , our algorithm converges without requiring the tuning of any hyper-parameter, under various standard assumptions and models for stochastic optimization. 1.2 Stochastic Adaptive Descent We consider a sequence (\xi_{k})_{k\in{\mathbb{N}}} of independent and identically distributed copies of \xi . For any random variable Z , \mathbb{E}_{{k-1}}\left[Z\right] denotes the conditional expectation \mathbb{E}\left[Z\mid\mathcal{F}_{k-1}\right] , where \mathcal{F}_{k-1} is the filtration up to iteration k-1 . In particular, for all k\in{\mathbb{N}} , we assume access to a stochastic gradient oracle \nabla f_{{\xi_{k}}} such that \forall x\in{\mathbb{R}}^{d} , \mathbb{E}_{{k-1}}\left[\nabla f_{{\xi_{k}}}(x)\right]=\nabla f(x) . We fix an initialization x_{0}\in{\mathbb{R}}^{d} and consider the stochastic recursion x_{k+1}=x_{k}-\lambda_{k}\nabla f_{{\xi_{k}}}(x_{k}), (3) where step-size \lambda_{k}>0 is a (possibly random) variable that is assumed to be independent of \xi_{k} conditionally on \mathcal{F}_{k-1} . The above notation has been chosen to be consistent with those in malitsky2019adaptive to ease the comparison. Our main contribution is to prove the benefits of the following adaptive step-sizes \lambda_{k} : \displaystyle\begin{split}&\hat{L}_{k-1}=\frac{\left\|\nabla f_{{\xi_{k-1}}}(x_{k})-\nabla f_{{\xi_{k-1}}}(x_{k-1})\right\|}{\left\|x_{k}-x_{k-1}\right\|},\\ &\lambda_{k}=\left\{\begin{array}[]{lclr}\min\left(\frac{1}{2\sqrt{2}\hat{L}_{k-1}}\phantom{\frac{|}{|}}\right.&,&\left.\lambda_{k-1}\sqrt{1+\frac{\lambda_{k-1}}{\lambda_{k-2}}}\right)&\text{(Variant {I})}\\ \min\left(\frac{1}{2\sqrt{2}\hat{L}_{k-1}}\frac{1}{k^{1/2+\delta}}\phantom{\frac{|}{|}}\right.&,&\left.\lambda_{k-1}\sqrt{1+\frac{\lambda_{k-1}}{\lambda_{k-2}}}\right)&\text{(Variant {II})}\\ \min\left(\frac{1}{2\sqrt{2}\hat{L}_{k-1}}\frac{1}{k^{1/2+\delta}}\phantom{\frac{|}{|}}\right.&,&\left.\lambda_{k-1}\sqrt{1+\left(1-\frac{1}{k^{1/2+\delta}}\right)\frac{\lambda_{k-1}}{\lambda_{k-2}}}\right)&\text{(Variant {III})}\end{array}\right.\end{split} (4) for all k\geq 2 , with \lambda_{0}>0 and 0<\delta<1/2 . The choice ( 4 ) adapts locally to the geometry of the functions f_{\xi} . We propose three variants of our method that have different convergence properties, and recommend using Variant- III which has the strongest theoretical guarantees. The parameter \delta>0 is not to be considered as a real hyper-parameter: it is needed for the theoretical convergence analysis, but can be taken arbitrarily small . input: x_{0}\in{\mathbb{R}}^{d} , \lambda_{0}=10^{-3} for k=0 to … : Draw mini-batch \xi_{k} Evaluate \nabla f_{{\xi_{k}}}(x_{k}) if k\geq 1 Evaluate \nabla f_{{\xi_{k-1}}}(x_{k}) if k=1 \lambda_{1}=\frac{\left\|x_{1}-x_{0}\right\|}{2\sqrt{2}\left\|\nabla f_{{\xi_{0}}}(x_{1})-\nabla f_{{\xi_{0}}}(x_{0})\right\|} else Compute \lambda_{k} according to ( 4 ) Store x_{k} , \lambda_{k},\lambda_{k-1} and \xi_{k} Update x_{k+1}=x_{k}-\lambda_{k}\nabla f_{{\xi_{k}}}(x_{k}) Algorithm 1 Adaptive SGD without descent Figure 1: Sensitivity to the choice of the initial step-size \lambda_{0} on three different problems (linear, logistic and Poisson regression, see Section 4 ). Our methods (AdaSGD, the blue curves) always perform well with small values of \lambda_{0} and thus do not require step-size tuning to compete with optimally-tuned SGD and “AdaSGD-MM” from malitsky2019adaptive . When the f_{\xi} are \mu -strongly convex with L -Lipschitz gradient, we prove that variant- III of ( 4 ) provides ( 3 ) with the convergence rate \mathbb{E}\left[\left\|x_{k+1}-x^{\star}\right\|^{2}\right]\leq\frac{C}{k^{1/2+\delta}},\quad\mbox{for all }k\geq k_{0}, with C>0 and k_{0}\geq 3 , without any knowledge of the constants \mu and L . We provide additional guarantees beyond the globally Lipschitz continuous and strongly convex settings later in Section 3 . We stress that ( 4 ) does not involve any scaling parameter to tune based on the curvature of the f_{\xi} ’s which most choices for SGD typically require, including the approach in malitsky2019adaptive in the stochastic case. This is possible at the price of one extra stochastic gradient evaluation at each iteration. The same drawback exists with the stochastic approach of malitsky2019adaptive , and it is inherent to the idea they propose. However, this additional cost has to be balanced with the cost of hyper-parameter tuning ( sivaprasad2020optimizer ) . 1.3 Related work Tuning the step-size in gradient descent (GD) has been the topic of a large body of literature. Without being exhaustive, we review the related work on adaptive step-sizes, with a focus on SGD. Further adaptation of malitsky2019adaptive In the deterministic setting, malitsky2019adaptive introduced an adaptive version of GD (here-after called AdaGD) that they later refined in ( malitsky2024adaptive ) to improve constant factors in the choice of the step-size. A proximal version has been developed ( latafat2024adaptive ) . As far as we know, there has been little work on adapting AdaGD to the stochastic setting (beyond the heuristics in malitsky2019adaptive ). One exception is the work of defazio2022grad , which takes inspiration from AdaGD, but which derives a rather different algorithm, that only allows for increasing step-sizes. In contrast, our method adapts to the local geometry at every iteration which generates non-monotone step-sizes. Adaptive methods. Adaptive methods are a very active topic due to their extensive use for training neural networks ( duchi2011adaptive ; mcmahan2010adaptive ; kingma2014adam ; tieleman2012lecture ) . However, they still feature a step-size parameter (and possibly others), whose choice significantly affects the performances ( sivaprasad2020optimizer ) . Beyond AdaGD, many other strategies exist in the deterministic setting ( li2023simple ; lan2023optimal ; khaled2023dowg ) . In particular, AdaGD can be seen as a more stable version of the Barzilai-Borwein step-sizes ( barzilai1988two ; raydan1997barzilai ) . Stochastic adaptations of these step-sizes have been proposed for convex ( tan2016barzilai ) and non-convex optimization ( 8945980 ; castera2022second ) , but they always mitigate the instability of the methods through additional hyper-parameters. Overall, we stress that the stochastic setting possesses additional difficulties that make it significantly more challenging ( orabona2020icml ) . Parameter free algorithms and normalized gradients Regarding the stochastic setting, the term parameter-free may have several meanings. It is often connected to online learning where one seeks adaptive strategies of methods that provably minimize f as well as the optimally-tuned instance of the method (up to a factor), see e.g. , ( orabona2014simultaneous ; Tuningfree24 ) . The definition of parameter free may vary depending on the assumptions on the function, the geometric constants of the problems that are assumed