Pith. sign in

REVIEW 2 major objections 4 minor 48 references

Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a momentum variant of stochastic gradient descent achieves a high-probability stopping-time convergence rate of order log(τ)/√(τ) for smooth convex objectives with sub-Gaussian gradient noise, removing the extra…

desk verdict A real but incremental advance: the paper removes one logarithm from stopping-time high-probability bounds for a momentum SGD variant, with a reusable maximal inequality for almost supermartingales, but the proof of Lemma 1 has a localized gap that needs an extra event-restriction step before it is fully correct. read the letter →

arxiv 2506.23335 v2 pith:TIYD7XZP submitted 2025-06-29 math.OC math.STstat.TH

Yasong Feng , Yifan Jiang , Tianyu Wang , Zhiliang Ying This is my paper
classification math.OCmath.STstat.TH MSC 90C2590C1560G4062L20
keywords stoppingtimeconvergencestochasticgradientdescentwithmomentumhigh-probabilityboundsalmostsuper-martingaleslargedeviationssmoothconvexoptimizationsub-Gaussiannoise
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

Algorithms are terminated adaptively in practice, often by stopping rules such as "stop when progress is small," but most convergence theory only covers non-random iteration counts. This paper attacks the gap directly: it proves a high-probability bound that holds simultaneously for every iterate, which by an equivalence lemma is exactly the same as holding for any stopping time adapted to the algorithm. For smooth convex problems with sub-Gaussian gradient noise, the bound has the form $C\log(\tau+2)/\sqrt{\tau+1}$, improving the previously derived $\log^2(\tau)/\sqrt{\tau}$ stopping-time rate. The engine is a new large-deviation lemma for almost super-martingales, which the authors propose as a reusable tool. If the result is correct, adaptive early-stopping rules for stochastic momentum methods inherit the same near-optimal rate as fixed-horizon runs.

What carries the argument

The central object is the discrete Lyapunov function $E(k)$ defined above, together with Lemma 1, a large-deviation extension of the classical almost-super-martingale bound. An almost super-martingale is a nonnegative process whose conditional expected increment is controlled by a summable drift plus a negligible term; Lemma 1 shows that if the increments are conditionally sub-Gaussian, the whole process stays below a threshold with high probability. Lemma 2 proves the algorithm's Lyapunov drift has exactly that structure: $E(k)-E(k-1)\le a_k\|\theta_k\|^2+\sqrt{a_k}\langle\theta_k,\varphi_k\rangle$ with $a_k=16\eta_k/k$, noise $\theta_k=\nabla f(x_k)-g(x_k,\xi_k)$, and an $F_{k-1}$-measurable $\varphi_k$. The choice $\eta_k=1/(16L^2\log^2(k+2))$ makes $\sum_k a_k$ finite, which turns the drift bound into the $\log\tau/\sqrt{\tau}$ rate; the final tail argument uses a supermartingale maximal inequality.

What would settle it

Take $f(x)=\|x\|^2$, $L=2$, run SGDM (4) with $\eta_k=1/(16L^2\log^2(k+2))$ and i.i.d. Gaussian noise $\theta_k$ of variance $\sigma^2$, and estimate the empirical rate of the event that $\sup_{k\le 10^6}(f(x_k)-f^*)\sqrt{k+1}/\log(k+2)$ exceeds $C_1+C_2\log(1/\beta)$. If the frequency stays at or below $2\beta$ for constants fitted to the theorem, the claim survives; a sharper check is algebraic: at $k=1$, compute both sides of the conditional moment inequality $E[\exp(t\sqrt{a_1}\langle\theta_1,\varphi_1\rangle)\mid F_0]\le\exp(a_1\sigma^2tE(0))$ for $t=1$ under any sub-Gaussian law, since a violation would locate a gap in Lemma 1's application.

Watch

Extended reading notes

Core claim

Under Assumptions 1--3 ($f$ convex and $L$-smooth with finite minimum; stochastic gradients unbiased with bounded variance and conditionally sub-Gaussian noise), the SGDM variant defined by (4) with step-size $\eta_k=1/(16L^2\log^2(k+2))$ satisfies, for every $\beta\in(0,1/2)$ and every $\{x_k\}$-stopping time $\tau$, $P(f(x_\tau)-f^*\le (C_1+C_2\log(1/\beta))\log(\tau+2)/\sqrt{\tau+1})\ge 1-2\beta$, where $C_1,C_2$ depend only on problem parameters and the starting point. The proof works through a Lyapunov function $E(k)=\|x_{k+1}+(k+1)(x_{k+1}-x_k)-x^*\|^2+4\sqrt{(k+1)\eta_k}(f(x_k)-f^*)$, whose drift is shown to fit an almost-super-martingale inequality with sub-Gaussian increments; Lemma 1 converts that drift into a sharp tail bound. A companion proposition gives, for any $\varepsilon\in(0,1/2)$, a rate $\log^{(1+\varepsilon)/2}\tau/\sqrt{\tau}$ with constants involving $h_\sigma(\varepsilon)=\exp(\sigma^2\zeta(1+\varepsilon))(\zeta(1+\varepsilon))^2$. The authors state that this is the tightest stopping-time high-probability rate known for this setting.

Load-bearing premise

The load-bearing premise is Assumption 3, that the stochastic gradient noise is conditionally sub-Gaussian; if the noise is only bounded in variance or heavier-tailed, the moment-generating-function control of the Lyapunov drift no longer works and the high-probability stopping-time bound is not established.

Editorial extensions

If this is right

  • For every $\beta\in(0,1/2)$ and every stopping time $\tau$, the SGD-with-momentum iterate satisfies $f(x_\tau)-f^*\le O(\log(\tau+2)/\sqrt{\tau+1})$ with probability at least $1-2\beta$, under the theorem's assumptions.
  • The union-bound route that previously turned pointwise guarantees into stopping-time guarantees is no longer needed; the bound holds simultaneously for all $k$ from the start.
  • Early-stopping rules of the form $\tau=\min\{k:\|x_k-x_{k-1}\|\le\epsilon\}$ or based on objective decrease inherit the same rate, aligning theory with how stochastic algorithms are actually deployed.
  • Lemma 1 supplies a standalone high-probability almost-super-martingale tool that can be applied to other stochastic approximation schemes whose Lyapunov drift has the same shape.
  • Proposition 1 permits a trade-off between the logarithmic exponent and the constant, giving $\log^{(1+\varepsilon)/2}\tau/\sqrt{\tau}$ for any $\varepsilon\in(0,1/2)$.

Reading between the lines

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

  • Editorial inference: the large-deviation lemma is transferable; any stochastic approximation method that can write its Lyapunov drift as $a_k\|\theta_k\|^2+\sqrt{a_k}\langle\theta_k,\varphi_k\rangle$ with summable $a_k$ and sub-Gaussian $\theta_k$ will automatically get a stopping-time high-probability bound of the same shape.
  • Editorial inference: Proposition 1's $\varepsilon$-parameterized family suggests a finite-$\tau$ tuning problem: as $\varepsilon\to0$ the exponent approaches $1/2$ but $h_\sigma(\varepsilon)$ blows up through the zeta factor, so a practical choice of $\varepsilon$ should minimize the displayed bound at the horizon of interest.
  • Editorial inference: since Lemma 3 equates a uniform-in-$k$ high-probability bound with a stopping-time bound, future improvements in pointwise rates will carry over to stopping times automatically; the barrier broken here is therefore a proof-technique barrier rather than a fundamental computational one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies high-probability convergence of a stochastic gradient descent with momentum (SGDM) variant, with guarantees expressed in terms of stopping times. Under convex L-smooth objectives and sub-Gaussian gradient noise, it claims an O(log(τ)/√τ) high-probability error bound for any {x_k}-stopping time τ, improving the O(log^2(τ)/√τ) rate that the authors show follows from union-bounding existing per-iterate bounds. The proof introduces a Lyapunov function E(k), a one-step increment inequality (Lemma 2), and a new large-deviation lemma for almost supermartingales (Lemma 1). It also proves an equivalence between simultaneous all-iterate bounds and stopping-time bounds (Lemma 3). The central result is stated as Theorem 1, with a parameterized variant in Proposition 1.

Significance. If correct, the paper closes a logarithmic gap in stopping-time convergence rates for stochastic first-order methods, a topic of practical relevance because algorithms are often terminated by data-dependent rules. The comparison with prior work is quantitative and the claimed improvement is sharp and easily stated. The proof strategy is coherent: the Lyapunov function is natural, the decomposition into a supermartingale and a sub-Gaussian tail term is elegant, and the auxiliary large-deviation lemma for almost supermartingales could be of independent interest. No fitted parameters or circular reductions are involved, and the main theorem yields a concrete, falsifiable rate. However, the proof of Lemma 1 contains a missing event-restriction step at equation (18), and the auxiliary lemmas are stated under an i.i.d. assumption that does not formally cover their application. These are local, repairable issues rather than fundamental obstructions, but they must be fixed before the result can be accepted.

major comments (2)
  1. [Section 2.1, Eq. (18)] The derivation of the key inclusion after 'Since γ1S(k)≥...' is not valid as written. The difference between the right-hand and left-hand exponents in the displayed comparison equals B(∏_{l=k+1}∞(1+a_lσ^2)−1)M(k)/γ2 + Bσ^2(γ1S(k)−∑_{l=1}^k a_lS(l−1)). The second term is nonnegative, but the first term has the sign of M(k), and M(k)=E(k)−S(k) is not shown to be nonnegative. Consequently the pointwise inequality exp(BM(k)/γ2−Bσ^2γ1S(k)) ≤ N^{B/γ2}(k) is false on paths with M(k)<0. This step is the only bridge between the supermartingale N^{B/γ2} and the event controlling M(k)−σ^2γ1γ2S(k), so the final high-probability bound on E(k) is unsupported as the proof stands. The gap is repairable: on the event in the left-hand side of (18), the exponent is at least BE(0)+log(1/β)>0, and since S(k)≥0 this forces M(k)>0, so restricting the pointwise comparison to that event would restore the argument. This event-restriction step is absent from the manuscript and should be added explicitly.
  2. [Appendix A, Lemma 4 and Lemma 5] Both auxiliary lemmas are stated for a sequence of i.i.d. random variables θ_1,...,θ_k, but the sequence θ_k=∇f(x_k)−g(x_k,ξ_k) arising in the proof of Theorem 1 is not i.i.d. because x_k depends on the past noise. The proofs of the lemmas do not actually use independence; they use only the stated conditional properties (zero conditional mean, boundedness, and conditional sub-Gaussianity). The intended application is therefore valid after replacing 'i.i.d.' by an adapted sequence in the lemma statements, but as written the hypotheses do not formally cover the application. This should be corrected in the statements, since Theorem 1 relies on Lemma 4 for the verification of the almost supermartingale condition in Lemma 1.
minor comments (4)
  1. [Section 2, Lemma 2 proof] There are several typographical errors, including 'differncing' for 'differencing' and 'conditonal MGF' for 'conditional MGF'; these should be corrected in a revision.
  2. [Table 1 and Section 1.4] The phrase 'tightest high-probability convergence result rate' in Section 1.4 is an overclaim unless a matching lower bound is established; 'best known' would be more precise.
  3. [Section 1.2 and Section 3] The notation ≲ is used informally in equations (1)–(3) and (23)–(24); the authors may wish to state the precise polynomial-in-log(1/β) dependencies, since the comparison with Theorem 1 depends on the log factor.
  4. [Proposition 1] In the statement of Proposition 1, the constant C0 absorbs all problem-dependent factors such as L and σ, while hσ(ε) is exhibited explicitly; this is acceptable but the sentence defining C0 should state unambiguously that C0 is independent of k, β, and ε, and may depend on L and σ.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the stopping-time rate is derived from a new large-deviation supermartingale lemma applied to a Lyapunov function, with no fitted parameter renamed as a prediction and no load-bearing self-citation.

full rationale

The paper's central claim (Theorem 1) is a new high-probability stopping-time bound for a stochastic gradient descent with momentum variant. The derivation chain is self-contained: Lemma 1 develops a large-deviation inequality for almost supermartingales under a conditional sub-Gaussian condition, using only the stated assumptions, a supermartingale construction N^t(k), and Ville's inequality; Theorem 1 then verifies the conditions of Lemma 1 for the Lyapunov function E(k), with the constants C1 and C2 explicitly computed from problem parameters (L, sigma, gamma1, gamma2, E(0)) rather than fitted. No parameter is calibrated to the target quantity and then called a prediction; no equation in the proof reduces to the claimed bound by definition. The comparison with prior work is derived from external published bounds in [25,26,32,33] via a union bound and Lemma 3, so the claimed logarithmic improvement is not obtained by renaming a known result. The paper relies on standard assumptions (convexity, L-smoothness, unbiased and sub-Gaussian gradient noise) and does not import a contested premise from the authors' own prior work; no self-citation is load-bearing. The only notable concern is a possible gap in the proof of Lemma 1 around the sign of M(k) when comparing exponentials, but this is a correctness or rigor issue, not circularity: even if the proof requires a repaired event-restriction argument, the claimed theorem is not equivalent to its assumptions by construction. Accordingly, the circularity score is 0.

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

The theorem depends on the standard convex/smooth/optimization assumptions, a sub-Gaussian noise condition, and standard martingale inequalities. The step-size schedule is a hand-chosen design parameter. No new entities are introduced.

free parameters (1)
  • Step-size schedule eta_k = 1/(16 L^2 log^2(k+2))
    Chosen by hand so that a_k=16 eta_k/k is summable and eta_k <= k/(16 L^2), making the negative drift terms in Lemma 2 dominate; this exact schedule determines the log(k)/sqrt(k) rate.
assumptions (5)
  • domain assumption Assumption 1: f is convex, L-smooth, and attains a finite minimum.
    Used throughout Lemma 2 and Theorem 1 to derive the Lyapunov drift inequality and the function-value bound.
  • domain assumption Assumption 2: stochastic gradients are unbiased with bounded variance.
    Standard for stochastic first-order methods; invoked in the drift decomposition and in the sub-Gaussian verification.
  • domain assumption Assumption 3: gradient noise is conditionally sigma-sub-Gaussian.
    This is the load-bearing tail assumption that makes Lemma 1's moment-generating-function argument valid.
  • standard math Ville's maximal inequality for nonnegative supermartingales.
    Used in Lemma 1 to convert the supermartingale N^t(k) into a high-probability maximal bound.
  • standard math Conditional sub-Gaussian MGF bounds in Lemmas 4 and 5.
    These elementary concentration results are proved in the appendix and used to verify the almost super-martingale condition and to bound S(k).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods." pith.science (2026). https://pith.science/paper/TIYD7XZP

@misc{pith2026250623335,
  author       = {Pith},
  title        = {Pith review of: Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TIYD7XZP}},
  note         = {Machine review of arXiv:2506.23335}
}
read the original abstract

This work provides a novel convergence analysis for stochastic optimization in terms of stopping times, addressing the practical reality that algorithms are often terminated adaptively based on observed progress. Unlike prior approaches, our analysis: 1. Directly characterizes convergence in terms of stopping times adapted to the underlying stochastic process. 2. Breaks a logarithmic barrier in existing results. Key to our results is the development of a lemma to control the large deviation property of almost super-martingales. This lemma might be of broader interest.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

48 extracted references · 32 canonical work pages

  1. [1]

    Katyusha: The first direct acceleration of stochastic gradient methods

    Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1200–1205, 2017

    work page 2017

  2. [2]

    KatyushaX:Simplemomentummethodforstochasticsum-of-nonconvexoptimization

    ZeyuanAllen-Zhu. KatyushaX:Simplemomentummethodforstochasticsum-of-nonconvexoptimization. In International Conference on Machine Learning, pages 179–185. PMLR, 2018

    work page 2018

  3. [3]

    Variance reduction for faster non-convex optimization

    Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. InInterna- tional conference on machine learning, pages 699–707. PMLR, 2016

    work page 2016

  4. [4]

    On the convergence of nesterov’s accelerated gradient method in stochastic settings

    Mahmoud Assran and Mike Rabbat. On the convergence of nesterov’s accelerated gradient method in stochastic settings. InInternational Conference on Machine Learning, pages 410–420. PMLR, 2020

    work page 2020

  5. [5]

    Gradient convergence in gradient methods with errors

    Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10(3):627–642, 2000

    work page 2000

  6. [6]

    Oxford University Press, 02 2013

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013

    2013

  7. [7]

    High-probability bounds for non-convex stochastic optimization with heavy tails.Advances in Neural Information Processing Systems, 34:4883–4895, 2021

    Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails.Advances in Neural Information Processing Systems, 34:4883–4895, 2021

    2021

  8. [8]

    Stochastic first order methods in smooth convex optimization

    Olivier Devolder et al. Stochastic first order methods in smooth convex optimization. Technical report, CORE, 2011

    work page 2011

Show all 48 references
  1. [9]

    Fine-tuning pretrained language models: Weight initializations, data orders, and early stopping.arXiv preprint arXiv:2002.06305, 2020

    Jesse Dodge, Gabriel Ilharco, Roy Schwartz, Ali Farhadi, Hannaneh Hajishirzi, and Noah Smith. Fine-tuning pretrained language models: Weight initializations, data orders, and early stopping.arXiv preprint arXiv:2002.06305, 2020

    2002 arXiv

  2. [10]

    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, 2022

    2022

  3. [11]

    Stochastic heavy ball.Electronic Journal of Statistics, 12(1):461–529, 2018

    Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball.Electronic Journal of Statistics, 12(1):461–529, 2018

    2018

  4. [12]

    Stabilized SVRG: Simple variance reduction for nonconvex optimization

    Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang. Stabilized SVRG: Simple variance reduction for nonconvex optimization. InConference on learning theory, pages 1394–1448. PMLR, 2019

    2019

  5. [13]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming

    Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013

    2013

  6. [14]

    Understanding the role of momentum in stochastic gradient methods.Advances in Neural Information Processing Systems, 32, 2019

    Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods.Advances in Neural Information Processing Systems, 32, 2019

    2019

  7. [15]

    Goodfellow, Yoshua Bengio, and Aaron Courville.Deep Learning

    Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville.Deep Learning. MIT Press, Cambridge, MA, USA, 2016

    2016

  8. [16]

    Stochastic optimization with heavy- tailed noise via accelerated gradient clipping.Advances in Neural Information Processing Systems, 33:15042–15053, 2020

    Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping.Advances in Neural Information Processing Systems, 33:15042–15053, 2020. 14

    2020

  9. [17]

    Tight analyses for non-smooth stochastic gradient descent

    Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. InConference on Learning Theory, pages 1579–1613. PMLR, 2019

    2019

  10. [18]

    Making the last iterate of SGD information theoretically optimal

    Prateek Jain, Dheeraj M Nagaraj, and Praneeth Netrapalli. Making the last iterate of SGD information theoretically optimal. SIAM Journal on Optimization, 31(2):1108–1130, 2021

    2021

  11. [19]

    Accelerating stochastic gradient descent using predictive variance reduction

    Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013

    2013

  12. [20]

    Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition

    Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795–811. Springer, 2016

    2016

  13. [21]

    High probability bounds for a class of nonconvex algorithms with adagrad stepsize

    Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. InInternational Conference on Learning Representations, 2021

    2021

  14. [22]

    On the insufficiency of existing momentum schemes for stochastic optimization

    Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. In2018 Information Theory and Applications Workshop (ITA), pages 1–9. IEEE, 2018

    2018

  15. [23]

    Stochastic estimation of the maximum of a regression function.The Annals of Mathematical Statistics, pages 462–466, 1952

    Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function.The Annals of Mathematical Statistics, pages 462–466, 1952

    1952

  16. [24]

    Kushner and Hai Huang

    Harold J. Kushner and Hai Huang. Asymptotic properties of stochastic approximations with constant coefficients. SIAM Journal on Control and Optimization, 19(1):87–105, 1981

    1981

  17. [25]

    An optimal method for stochastic composite optimization.Mathematical Programming, 133(1-2):365–397, 2012

    Guanghui Lan. An optimal method for stochastic composite optimization.Mathematical Programming, 133(1-2):365–397, 2012

    2012

  18. [26]

    Springer, 2020

    Guanghui Lan.First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020

    2020

  19. [27]

    Validation analysis of mirror descent stochastic approximation method.Mathematical programming, 134(2):425–458, 2012

    Guanghui Lan, Arkadi Nemirovski, and Alexander Shapiro. Validation analysis of mirror descent stochastic approximation method.Mathematical programming, 134(2):425–458, 2012

    2012

  20. [28]

    High probability guarantees for nonconvex stochastic gradient descent with heavy tails

    Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. InInternational Conference on Machine Learning, pages 12931–12963. PMLR, 2022

    2022

  21. [29]

    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 The 22nd international conference on artificial intelligence and statistics, pages 983–992. PMLR, 2019

    2019

  22. [30]

    A high probability analysis of adaptive sgd with momentum

    Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. In Workshop on Beyond First Order Methods in ML Systems at ICML’20, 2020

    2020

  23. [31]

    An improved analysis of stochastic gradient descent with momentum

    Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261–18271, 2020

    2020

  24. [32]

    High probability convergence of stochastic gradient methods

    Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. InInternational Conference on Machine Learning, pages 21884–21914. PMLR, 2023

    2023

  25. [33]

    Revisiting the last-iterate convergence of stochastic gradient methods

    Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. arXiv preprint arXiv:2312.08531, 2023

    2023

  26. [34]

    High-probability convergence bounds for non-convex stochastic gradient descent.arXiv preprint arXiv:2006.05610, 2020

    Liam Madden, Emiliano Dall’Anese, and Stephen Becker. High-probability convergence bounds for non-convex stochastic gradient descent.arXiv preprint arXiv:2006.05610, 2020. 15

    2006

  27. [35]

    Algorithms of robust stochastic optimization based on mirror descent method.Automation and Remote Control, 80:1607–1627, 2019

    Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky. Algorithms of robust stochastic optimization based on mirror descent method.Automation and Remote Control, 80:1607–1627, 2019

    2019

  28. [36]

    Robust stochastic approximation approach to stochastic programming.SIAM Journal on optimization, 19(4):1574–1609, 2009

    Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming.SIAM Journal on optimization, 19(4):1574–1609, 2009

    2009

  29. [37]

    Early stopping-but when? InNeural Networks: Tricks of the trade, pages 55–69

    Lutz Prechelt. Early stopping-but when? InNeural Networks: Tricks of the trade, pages 55–69. Springer, 2002

    2002

  30. [38]

    Robbins and D

    H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications**research supported by nih grant 5-r01-gm-16895-03 and onr grant n00014-67-a-0108-

  31. [39]

    Rustagi, editor,Optimizing Methods in Statistics, pages 233–257

    In Jagdish S. Rustagi, editor,Optimizing Methods in Statistics, pages 233–257. Academic Press, 1971

    1971

  32. [40]

    A stochastic approximation method.The annals of mathematical statistics, pages 400–407, 1951

    Herbert Robbins and Sutton Monro. A stochastic approximation method.The annals of mathematical statistics, pages 400–407, 1951

    1951

  33. [41]

    Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball

    Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. InConference on Learning Theory, pages 3935–3971. PMLR, 2021

    2021

  34. [42]

    Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes

    Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. InInternational conference on machine learning, pages 71–79. PMLR, 2013

    2013

  35. [43]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  36. [44]

    Etude critique de la notion de collectif

    Jean Ville. Etude critique de la notion de collectif. Gauthier-Villars Paris, 1939

    1939

  37. [45]

    Cambridge University Press, 2019

    Martin J Wainwright.High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019

    2019

  38. [46]

    Adagrad stepsizes: Sharp convergence over nonconvex landscapes

    Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21(1):9047–9076, 2020

    2020

  39. [47]

    A unified analysis of stochastic momentum methods for deep learning.arXiv preprint arXiv:1808.10396, 2018

    Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning.arXiv preprint arXiv:1808.10396, 2018

    2018 arXiv

  40. [48]

    Why are adaptive methods good for attention models?Advances in Neural Information Processing Systems, 33:15383–15393, 2020

    Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models?Advances in Neural Information Processing Systems, 33:15383–15393, 2020. 16

    2020

Pith tools

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