Pith. sign in

REVIEW 3 major objections 3 minor 57 references

Stochastic Adaptive Gradient Descent Without Descent

T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper introduces an adaptive step-size rule for stochastic gradient descent that needs no hyper-parameter tuning, and proves convergence and explicit rates under strong convexity without knowing the smoothness or strong-convexity…

desk verdict Clever new stochastic AdaGD variant, but the square-summability proof for the non-strongly-convex cases only covers single-sample batches, so the convergence guarantee doesn't yet match the mini-batch experiments. read the letter →

arxiv 2509.14969 v2 pith:JYNPXCT7 submitted 2025-09-18 cs.LG math.OCstat.ML

Jean-François Aujol , Jérémie Bigot , Camille Castera This is my paper · ORCID
classification cs.LGmath.OCstat.ML MSC 90C2590C1562L20
keywords adaptivestepsizestochasticgradientdescentparameter-freeLyapunovanalysisconvexoptimizationstrongconvexityridgeregressionRobbins-Siegmund
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes an adaptive step-size scheme for stochastic gradient descent that requires no hyper-parameter tuning. The step size is formed from two stochastic gradient evaluations per iteration, using the difference of gradients of the same random component function evaluated at consecutive iterates to estimate local curvature. The paper proves almost-sure convergence of the iterates whenever the squared step sizes are summable, and shows summability holds in three settings: strongly convex objectives, linear regression, and sums of ridge functions. For strongly convex objectives, the third variant achieves $\mathbb{E}[\|x_{k+1}-x^\star\|^2] \le C/k^{1/2+\delta}$ without knowing the strong-convexity or smoothness constants. The practical claim is that this matches tuned baselines while removing the step-size search.

What carries the argument

The Lyapunov sequence $T_k = \|x_{k+1}-x^\star\|^2 + 2\lambda_k(1+\lambda_k/\lambda_{k-1})(f(x_k)-f^\star) + \|x_{k+1}-x_k\|^2/2$ is the central object. The argument decomposes the sampled-gradient difference into sampling noise and a curvature term, and the curvature term is controlled by the step-size condition $\lambda_k \le \|x_k-x_{k-1}\|/(2\sqrt{2}\|\nabla f_{\xi_{k-1}}(x_k)-\nabla f_{\xi_{k-1}}(x_{k-1})\|)$, while the recursion $\lambda_k \le \lambda_{k-1}\sqrt{1+\theta_{k-1}}$ maintains the Lyapunov inequality in expectation. Together these two conditions let the analysis reduce convergence to square-summability of the step sizes. The strong-convexity variant adds bounded-above and bounded-below estimates of $\lambda_k$ that produce the explicit rate.

What would settle it

Run Variants II and III on the finite-sum linear-regression problem with mini-batch size 32 and check empirically whether $\sum_k \lambda_k^2$ diverges or whether the bound $\|\Delta_k\|/\|\nabla f_\xi(x_k)-\nabla f_\xi(x_{k-1})\| \le 1/(\mu_\xi\|w_\xi\|^2)$ holds for the averaged gradient; either failure would show the summability guarantee does not cover the algorithm as run.

Watch

Extended reading notes

Core claim

The central discovery is that the deterministic 'adaptive gradient descent without descent' Lyapunov analysis can be transferred to stochastic gradients by one pivoting choice: evaluate the two gradients in the curvature estimate on the same previously drawn random component $f_{\xi_{k-1}}$. The step-size $\lambda_k$ is the minimum of an inverse-local-Lipschitz term and a multiplicative recursion, and the paper shows the resulting Lyapunov sequence has expected decrease up to a variance term. Under conditions that bound this term, the Lyapunov sequence converges almost surely whenever $\sum_k \lambda_k^2 < \infty$. For $\mu$-strongly convex $f_\xi$ with $L$-Lipschitz gradients, Variant III concentrates the step size between explicit constant-free bounds, giving a polynomial convergence rate in expectation without knowledge of $\mu$ or $L$.

Load-bearing premise

The load-bearing premise is that the squared step sizes sum to a finite value; in the linear- and ridge-regression cases this is proven for single-sample mini-batches, but the proof that it carries over to the mini-batches used in the experiments is not given.

Editorial extensions

If this is right

  • For strongly convex $f_\xi$, Variant III yields $\mathbb{E}[\|x_{k+1}-x^\star\|^2] \le C/k^{1/2+\delta}$ for all $k \ge k_0$, with $k_0$ independent of $\lambda_0$, and without knowing $\mu$ or $L$.
  • For finite-sum linear regression and sums of ridge functions, the squared step sizes are summable, so the iterates converge almost surely even though the component functions are not strongly convex.
  • The deterministic full-batch recursion is recovered up to a $\sqrt{2}$ factor, so the stochastic method inherits the no-descent property of the deterministic one.
  • The method uses one extra gradient evaluation per iteration but eliminates the tuning grid, so total oracle cost can be favorable when tuning is expensive.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proofs of square-summability in the linear- and ridge-regression cases assume single-element mini-batches and state this is without loss of generality; the step of extending the bound to averaged gradients is not shown. If that inequality degrades for mini-batch averages, the almost-sure guarantee does not cover the batch sizes used in the experiments (32 and 309).
  • The rate $O(1/k^{1/2+\delta})$ is slower than the $O(1/k)$ of well-tuned SGD on strongly convex problems; a natural test is whether the no-tuning robustness is worth the constant-factor slowdown at large $k$.
  • The analysis hinges on convexity for the key inequalities, but the variance term structure suggests a possible extension via the paper's convex-case results to objectives that are only locally Lipschitz smooth.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes AdaSGD, an adaptive step-size rule for stochastic convex optimization. The step size at iteration k is based on the ratio of the displacement to the difference of gradients of the previous mini-batch, combined with a recursive upper bound. Three variants are introduced; Variants II and III include a polynomial decay factor. The authors derive a Lyapunov inequality, then apply the Robbins-Siegmund theorem to obtain almost-sure convergence whenever the step sizes are square-summable, and provide polynomial convergence rates in the strongly convex case. They also claim square-summability for strongly convex objectives and for finite-sum least-squares and ridge regressions. Experiments compare sensitivity to the initial step size and performance against tuned SGD baselines.

Significance. The central construction is original and useful: the step-size derivation is self-contained, the Lyapunov analysis is coherent, and the parameter-free claim is credibly supported by the experiments. The main convergence theorem follows from a standard Robbins-Siegmund argument, and the paper is honest about which experimental settings lie outside the proven cases. However, the proof of square-summability for the non-strongly-convex cases does not cover the algorithm as implemented with mini-batches; this is a load-bearing gap that must be fixed before the central claim is fully established.

major comments (3)
  1. [Appendix A.2-A.3 and Corollary 3.3] The assertion that restricting to single-valued mini-batches is 'without loss of generality' is not justified and is false for the algorithm as stated. For a mini-batch S in linear regression, ∇f_S(x) = A_S x - b_S with A_S = (1/|S|)∑_{i∈S} w_i w_i^T, and the curvature ratio controlling λ_k is ∥r∥/∥A_S r∥ where r = ∇f_S(x_{k-1}). This ratio can be as large as 1/λ_min(A_S) and can be unbounded when A_S is nearly singular or r lies in its kernel. The rank-one identity used in the single-sample proof does not extend to mini-batch averages, so ∑λ_k² < ∞ is not established for mini-batches. Since Algorithm 1 and the experiments use batch sizes 32 and 309, Theorem 3.2 and Corollary 3.3 do not currently imply convergence of the method as run. A repair would need either a uniform lower bound on λ_min(A_S) over all possible batches, a different argument exploiting the random sampling, or a restriction to single-sample updates.
  2. [Appendix A.2] The proof defines μhat = max_ℓ ∥w_ℓ∥² and claims the bound ∥Δ∥ / ∥∇f_ξ(x_k)-∇f_ξ(x_{k-1})∥ ≤ 1/μhat. But the computation immediately before gives this ratio equal to 1/∥w_ℓ∥². To obtain the claimed upper bound one needs μhat ≤ ∥w_ℓ∥² for every ℓ, i.e., μhat = min_ℓ ∥w_ℓ∥². As written, the inequality has the wrong direction, so the single-sample Case-2 square-summability proof is also invalid as printed.
  3. [Section 3, Case-3 and Assumption 2] Corollary 3.3 is stated for Case-3 (ridge functions) under Assumption 2. However, Assumption 2(2-i) requires each ∇f_ℓ to be globally L-Lipschitz. For f_ℓ(x) = g_ℓ(⟨w_ℓ,x⟩) with g_ℓ merely μ-strongly convex, this need not hold; the paper's own ridge example g(t) = t^4/(1+t^2) + 0.01t² has a derivative that is not globally Lipschitz. Option (2-iii) requires boundedness of the iterates, which is not proved. Thus the convergence guarantee for Case-3 needs an additional smoothness or boundedness assumption, or a separate argument.
minor comments (3)
  1. [Section 2.3, displayed inequality after (13)] The displayed bound for E_{k-1}∥Δ_k∥² omits the factor 4 in front of λ_k² E_{k-1}[∥∇f_ξk(x_k)-∇f_ξ(k-1)(x_k)∥²]; Proposition 2.1 has the correct factor, so this appears to be a typographical slip.
  2. [Proof of Theorem 3.4] The term 32Lλ_k²∥x_k-x_*∥ should read 32L²λ_k²∥x_k-x_*∥² (or be absorbed into T_{k-1}), and the corresponding constant 32L/(8μ²) should be 32L²/(8μ²).
  3. [Appendix C, Eq. (28)] The inner expectation denoted E_k should be E_{k-1}, since the quantity is measurable with respect to the filtration at iteration k-1 once x_k is known.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the step-size derivation, Lyapunov analysis, and convergence rates are self-contained; the Appendix A.2-A.3 mini-batch reduction is a proof-completeness gap, not a circular step.

full rationale

The derivation chain is self-contained. The step-size (4) is defined so that conditions (12) and (14) hold, and Corollary 2.3 verifies this for the three variants; this is a design-and-verify argument, not a fit of a parameter to data that is later 'predicted'. The convergence claims do not assume their conclusions: Theorem 3.2 requires square-summability of lambda_k, which is proved in Appendix A rather than imposed; Corollary 3.3 then applies that theorem to Cases 1-3; and Theorem 3.4 derives the rate C/k^(1/2+delta) from the explicit k^(-1/2-delta) factor in Variant III together with the lower and upper bounds on lambda_k in Lemma B.3, not by feeding the target rate into the algorithm. The only self-citation at a load-bearing point is [5, Lemma A.3] in the proof of Theorem 3.4, but that lemma is a standard perturbation/summability tool whose assumptions do not include the theorem's conclusion, so it does not create circularity. The one notable defect is non-circular: in Appendix A.2 and A.3 the paper says 'without loss of generality, that the mini-batches are single valued' while Algorithm 1 and the experiments use mini-batches of size 32 and 309; the missing proof that the square-summability bound degrades gracefully under mini-batch averaging is a correctness/completeness gap, not a self-referential derivation.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard convex analysis assumptions and the square-summability of the adaptive step-size. The only non-standard assumption is the unproven WLOG reduction to single-valued mini-batches in Cases 2-3, which is flagged in red flags.

free parameters (2)
  • λ0 (initial step-size) = 10^-3 (fixed default in experiments)
    The algorithm starts at λ0=10^-3 and the paper argues performance is insensitive to it; it is an initialization, not fitted to the data, but it is still a user-set constant.
  • δ (decay exponent in Variants II and III) = 0.01 in experiments, any value in (0,1/2) allowed
    δ is not fitted to data, but it controls the step-size decay schedule and appears in the convergence rate; the paper's claim of being hyper-parameter-free relies on treating it as arbitrary, which is only partially justified.
assumptions (5)
  • domain assumption f and f_ξ are convex, differentiable, and lower-bounded for all ξ
    Section 1, problem (1). Central to the convexity inequalities used throughout the Lyapunov analysis.
  • domain assumption Assumption 1: λ_k is independent of ξ_k conditionally on F_{k-1}
    Section 2.2; satisfied by construction of Algorithm 1, but used in the proof to split conditional expectations.
  • domain assumption Assumption 2: either finite-sum with Lipschitz gradients, or global L-smoothness plus bounded variance at x*, or finite-sum with bounded iterates
    Section 3; needed for Lemma 3.1 to control the stochastic noise term in (15).
  • ad hoc to paper For Cases 2-3, one may reduce to single-valued mini-batches without loss of generality
    Appendix A.2 and A.3; the proof of square-summability is only carried out for ξ_k a single index, while experiments use batches of size 32 and 309. No justification is provided for the WLOG claim.
  • standard math Robbins-Siegmund almost-supermartingale theorem
    Theorem B.2 in Appendix B.2; used to prove almost-sure convergence of T_k.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic Adaptive Gradient Descent Without Descent." pith.science (2026). https://pith.science/paper/JYNPXCT7

@misc{pith2026250914969,
  author       = {Pith},
  title        = {Pith review of: Stochastic Adaptive Gradient Descent Without Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JYNPXCT7}},
  note         = {Machine review of arXiv:2509.14969}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2509.14969 by the authors.

Figure 1
Figure 1. Sensitivity to the choice of the initial step-size [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Last-three step-size sensitivity experiments, see Figure 1 for further details. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Evolution of the sub-optimality f(xk) − f ⋆ over the epochs. Comparison between the three variants of AdaSGD used without tuning and other methods that are tuned via a dense grid-search. Legend is the same as in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 43 canonical work pages

  1. [1]

    Parameter-free FISTA by adaptive restart and backtracking.SIAM Journal on Optimization, 34(4):3259–3285, 2024

    Jean-Franc ¸ois Aujol, Luca Calatroni, Charles Dossal, Hippolyte Labarri `ere, and Aude Rondepierre. Parameter-free FISTA by adaptive restart and backtracking.SIAM Journal on Optimization, 34(4):3259–3285, 2024

    work page 2024

  2. [2]

    FISTA restart using an automatic estimation of the growth parameter.Journal of Optimization Theory and Applications, 206(2):51, 2025

    Jean-Franc ¸ois Aujol, Charles Dossal, Hippolyte Labarri`ere, and Aude Rondepierre. FISTA restart using an automatic estimation of the growth parameter.Journal of Optimization Theory and Applications, 206(2):51, 2025

    work page 2025

  3. [3]

    Complexity guarantees for Polyak steps with momentum

    Mathieu Barr ´e, Adrien Taylor, and Alexandre d’Aspremont. Complexity guarantees for Polyak steps with momentum. InConference on learning theory, pages 452–478. PMLR, 2020

    work page 2020

  4. [4]

    Two-point step size gradient methods.IMA journal of numerical analysis, 8(1):141–148, 1988

    Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods.IMA journal of numerical analysis, 8(1):141–148, 1988

    1988

  5. [5]

    Bernard Bercu and J ´er´emie Bigot. Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures.The Annals of Statistics, 49(2):968 – 987, 2021

    work page 2021

  6. [6]

    Sample size selection in optimization methods for machine learning.Mathematical programming, 134(1):127–155, 2012

    Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning.Mathematical programming, 134(1):127–155, 2012

    2012

  7. [7]

    Making SGD parameter-free

    Yair Carmon and Oliver Hinder. Making SGD parameter-free. InConference on Learning Theory, pages 2360–2389. PMLR, 2022

    work page 2022

  8. [8]

    Second-order step-size tuning of SGD for non-convex optimization.Neural Processing Letters, 54(3):1727–1752, 2022

    Camille Castera, J ´erˆome Bolte, C ´edric F ´evotte, and Edouard Pauwels. Second-order step-size tuning of SGD for non-convex optimization.Neural Processing Letters, 54(3):1727–1752, 2022

    work page 2022

Show all 57 references
  1. [9]

    Fast bundle-level methods for unconstrained and ball-constrained convex optimization.Computational Optimization and Applications, 73(1):159–199, 2019

    Yunmei Chen, Guanghui Lan, Yuyuan Ouyang, and Wei Zhang. Fast bundle-level methods for unconstrained and ball-constrained convex optimization.Computational Optimization and Applications, 73(1):159–199, 2019

    2019

  2. [10]

    Convergence rates of gradient methods for convex optimization in the space of measures.Open J

    L ´ena¨ıc Chizat. Convergence rates of gradient methods for convex optimization in the space of measures.Open J. Math. Optim., 3:Art. No. 8, 19, 2022

    2022

  3. [11]

    New tight bounds for SGD without variance assumption: A computer-aided Lyapunov analysis.arXiv preprint arXiv:2505.17965, 2025

    Daniel Cortild, Lucas Ketels, Juan Peypouquet, and Guillaume Garrigos. New tight bounds for SGD without variance assumption: A computer-aided Lyapunov analysis.arXiv preprint arXiv:2505.17965, 2025

    2025

  4. [12]

    Artificial constraints and hints for unbounded online learning

    Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. InConference on Learning Theory, pages 874–894. PMLR, 2019

    2019

  5. [13]

    Learning-rate-free learning by d-adaptation

    Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by d-adaptation. InInternational Conference on Machine Learning, pages 7449–7479. PMLR, 2023

    2023

  6. [14]

    Grad-gradagrad? a non-monotone adaptive stochastic gradient method

    Aaron Defazio, Baoyu Zhou, and Lin Xiao. Grad-gradagrad? a non-monotone adaptive stochastic gradient method. arXiv preprint arXiv:2206.06900, 2022

    2022 arXiv

  7. [15]

    Adaptive subgradient methods for online learning and stochastic opti- mization.Journal of Machine Learning Research, 12(7), 2011

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic opti- mization.Journal of Machine Learning Research, 12(7), 2011

    2011

  8. [16]

    Duflo.Random iterative models, volume 34 ofApplications of Mathematics, New York

    M. Duflo.Random iterative models, volume 34 ofApplications of Mathematics, New York. Springer-Verlag, Berlin, 1997

    1997

  9. [17]

    The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance

    Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance. InConference on Learning Theory, pages 313–355. PMLR, 02–05 Jul 2022

    2022

  10. [18]

    Learning rate selection in stochastic gradient methods based on line search strategies.Applied Mathematics in Science and Engineering, 31(1):2164000, 2023

    Giorgia Franchini, Federica Porta, Valeria Ruggiero, Ilaria Trombini, and Luca Zanni. Learning rate selection in stochastic gradient methods based on line search strategies.Applied Mathematics in Science and Engineering, 31(1):2164000, 2023

    2023

  11. [19]

    Handbook of convergence theorems for (stochastic) gradient methods

    Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023

    2023 arXiv

  12. [20]

    A neural-network-based convex regularizer for inverse problems.IEEE Trans

    Alexis Goujon, Sebastian Neumayer, Pakshal Bohra, Stanislas Ducotterd, and Michael Unser. A neural-network-based convex regularizer for inverse problems.IEEE Trans. Comput. Imaging, 9:781–795, 2023. 10

    2023

  13. [21]

    On optimal universal first-order methods for minimizing heterogeneous sums.Optimization Letters, 18(2):427–445, 2024

    Benjamin Grimmer. On optimal universal first-order methods for minimizing heterogeneous sums.Optimization Letters, 18(2):427–445, 2024

    2024

  14. [22]

    Revisiting the Polyak step size.arXiv preprint arXiv:1905.00313, 2019

    Elad Hazan and Sham Kakade. Revisiting the Polyak step size.arXiv preprint arXiv:1905.00313, 2019

    1905 arXiv

  15. [23]

    Ismailov.Ridge functions and applications in neural networks, volume 263 ofMathematical Surveys and Monographs

    Vugar E. Ismailov.Ridge functions and applications in neural networks, volume 263 ofMathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2021

    2021

  16. [24]

    DoG is SGD’s best friend: A parameter-free dynamic step size schedule

    Maor Ivgi, Oliver Hinder, and Yair Carmon. DoG is SGD’s best friend: A parameter-free dynamic step size schedule. InInternational Conference on Machine Learning, pages 14465–14499. PMLR, 2023

    2023

  17. [25]

    Tuning-free stochastic optimization

    Ahmed Khaled and Chi Jin. Tuning-free stochastic optimization. InProceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024

    2024

  18. [26]

    DoWG Unleashed: An efficient universal parameter-free gradi- ent descent method.Advances in Neural Information Processing Systems, 36:6748–6769, 2023

    Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. DoWG Unleashed: An efficient universal parameter-free gradi- ent descent method.Advances in Neural Information Processing Systems, 36:6748–6769, 2023

    2023

  19. [27]

    ADAM: A method for stochastic optimization

    Diederik Kingma and Jimmy Ba. ADAM: A method for stochastic optimization. InInternational conference on learning representations (ICLR), volume 5, 2015

    2015

  20. [28]

    Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization.arXiv preprint arXiv:2310.12139, 2023

    Guanghui Lan, Yuyuan Ouyang, and Zhe Zhang. Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization.arXiv preprint arXiv:2310.12139, 2023

    2023 arXiv

  21. [29]

    Adaptive proximal algorithms for convex optimization under local lipschitz continuity of the gradient.Mathematical Programming, pages 1–39, 2024

    Puya Latafat, Andreas Themelis, Lorenzo Stella, and Panagiotis Patrinos. Adaptive proximal algorithms for convex optimization under local lipschitz continuity of the gradient.Mathematical Programming, pages 1–39, 2024

    2024

  22. [30]

    Online to offline conversions, universality and adaptive minibatch sizes.Advances in Neural Information Processing Systems, 30, 2017

    Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes.Advances in Neural Information Processing Systems, 30, 2017

    2017

  23. [31]

    A simple uniformly optimal method without line search for convex optimization.arXiv preprint arXiv:2310.10082, 2023

    Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex optimization.arXiv preprint arXiv:2310.10082, 2023

    2023 arXiv

  24. [32]

    On the convergence of stochastic gradient descent with adaptive stepsizes

    Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89, pages 983–992. PMLR, 16–18 Apr 2019

    2019

  25. [33]

    Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence

    Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence. InInternational Conference on Artificial Intelligence and Statistics, pages 1306–1314. PMLR, 2021

    2021

  26. [34]

    Near-optimal closed-loop method via lyapunov damping for convex optimization.arXiv preprint arXiv:2311.10053, 2023

    Severin Maier, Camille Castera, and Peter Ochs. Near-optimal closed-loop method via lyapunov damping for convex optimization.arXiv preprint arXiv:2311.10053, 2023

    2023 arXiv

  27. [35]

    Adaptive gradient descent without descent

    Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. InProceedings of the 37th International Conference on Machine Learning, volume 119, pages 6702–6712. PMLR, 13–18 Jul 2020

    2020

  28. [36]

    Adaptive proximal gradient method for convex optimization.Advances in Neural Information Processing Systems, 37:100670–100697, 2024

    Yura Malitsky and Konstantin Mishchenko. Adaptive proximal gradient method for convex optimization.Advances in Neural Information Processing Systems, 37:100670–100697, 2024

    2024

  29. [37]

    Adaptive bound optimization for online convex optimization

    H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. InConfer- ence on Learning Theory (COLT), volume 23, 2010

    2010

  30. [38]

    Prodigy: An expeditiously adaptive parameter-free learner

    Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner. InInterna- tional Conference on Machine Learning (ICML), 2024

    2024

  31. [39]

    Universal gradient methods for convex optimization problems.Mathematical Programming, 152(1):381– 404, 2015

    Yu Nesterov. Universal gradient methods for convex optimization problems.Mathematical Programming, 152(1):381– 404, 2015

    2015

  32. [40]

    A method of solving a convex programming problem with convergence rate O 1 k2

    Yurii Nesterov. A method of solving a convex programming problem with convergence rate O 1 k2 . InDoklady Akademii Nauk, volume 269(3), pages 543–547, 1983

    1983

  33. [41]

    Springer Science & Business Media, 2013

    Yurii Nesterov.Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013

    2013

  34. [42]

    Simultaneous model selection and optimization through parameter-free stochastic learning.Ad- vances in Neural Information Processing Systems, 27, 2014

    Francesco Orabona. Simultaneous model selection and optimization through parameter-free stochastic learning.Ad- vances in Neural Information Processing Systems, 27, 2014

    2014

  35. [43]

    Normalized gradients for all.arXiv preprint arXiv:2308.05621, 2023

    Francesco Orabona. Normalized gradients for all.arXiv preprint arXiv:2308.05621, 2023

    2023 arXiv

  36. [44]

    Icml 2020 tutorial on parameter-free online optimization, 2020

    Francesco Orabona and Ashok Cutkosky. Icml 2020 tutorial on parameter-free online optimization, 2020. 11

    2020

  37. [45]

    Coin betting and parameter-free online learning.Advances in Neural Information Processing Systems, 29, 2016

    Francesco Orabona and D ´avid P´al. Coin betting and parameter-free online learning.Advances in Neural Information Processing Systems, 29, 2016

    2016

  38. [46]

    Parameter-free stochastic optimization of variationally coherent functions.arXiv preprint arXiv:2102.00236, 2021

    Francesco Orabona and D ´avid P´al. Parameter-free stochastic optimization of variationally coherent functions.arXiv preprint arXiv:2102.00236, 2021

    2021 arXiv

  39. [47]

    Training deep networks without learning rates through coin betting.Ad- vances in neural information processing systems, 30, 2017

    Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting.Ad- vances in neural information processing systems, 30, 2017

    2017

  40. [48]

    Pedregosa, G

    F. Pedregosa, G. Varoquaux, A. Gramfort, V . Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V . Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python.Journal of Machine Learnin...

    2011

  41. [49]

    New York, Optimization Software,, 1987

    Boris T Polyak.Introduction to optimization. New York, Optimization Software,, 1987

    1987

  42. [50]

    Statistical complexity and optimal algorithms for nonlinear ridge bandits.The Annals of Statistics, 52(6):2557 – 2582, 2024

    Nived Rajaraman, Yanjun Han, Jiantao Jiao, and Kannan Ramchandran. Statistical complexity and optimal algorithms for nonlinear ridge bandits.The Annals of Statistics, 52(6):2557 – 2582, 2024

    2024

  43. [51]

    The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem

    Marcos Raydan. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM Journal on Optimization, 7(1):26–33, 1997

    1997

  44. [52]

    Robbins and D

    H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applica- tions. Optimizing Meth. Statist., Proc. Sympos. Ohio State Univ. 1971, 233-257 (1971)., 1971

    1971

  45. [53]

    Robles-Kelly and A

    A. Robles-Kelly and A. Nazari. Incorporating the Barzilai-Borwein adaptive step size into subgradient methods for deep network training. In2019 Digital Image Computing: Techniques and Applications (DICTA), pages 1–6, 2019

    2019

  46. [54]

    Optimizer benchmarking needs to account for hyperparameter tuning

    Prabhu Teja Sivaprasad, Florian Mai, Thijs V ogels, Martin Jaggi, and Franc ¸ois Fleuret. Optimizer benchmarking needs to account for hyperparameter tuning. InInternational Conference on Machine Learning (ICML), pages 9036–9045, 2020

    2020

  47. [55]

    Barzilai-borwein step size for stochastic gradient descent

    Conghui Tan, Shiqian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic gradient descent. Advances in neural information processing systems, 29, 2016

    2016

  48. [56]

    RMSprop: Divide the gradient by a running average of its recent magnitude

    Tijmen Tieleman and Geoffrey Hinton. RMSprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26–31, 2012. 12 A Ensuring Square-summability of the Step-sizes Theorem 3.2 holds true when the sequence of step...

    2012

  49. [57]

    Finally, for the right-hand side of (26), from (4), θkλk = λ2 k λk−1 ≤λ k−1 1 + 1− 1 k1/2+δ θk−1 =λ k−1 1 +θk−1− θk−1 k1/2+δ =λ k−1 (1 +θk−1) 1− 1 k1/2+δ θk−1 1 +θk−1

    By using Lemma B.3 once more in (25), it holds that, λkθk = λ2 k λk−1 ≥ 1 k1/2+δ 1 2 √ 2L 1 2δ√ 2 µ L = 1 k1/2+δ µ 2δ4L2, which is the left-hand side of (26). Finally, for the right-hand side of (26), from (4), θkλk = λ2 k λk−1 ≤λ k−1 1 + 1− 1 k1/2+δ θk−1 =λ k−1 1 +θk−1− θk−1 ...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.