Pith. sign in

REVIEW 2 major objections 5 minor 55 references

Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping

T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read This paper proves that Batched NSGDM, a normalized SGD with momentum, achieves optimal heavy-tailed convergence without any gradient clipping.

desk verdict Genuinely new unknown-p result and a serious proof gap: the load-bearing martingale inequality in Appendix C does not work as printed. read the letter →

arxiv 2412.19529 v4 pith:XGEGMSCC submitted 2024-12-27 math.OC cs.LGstat.ML

Zijian Liu , Zhengyuan Zhou This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C1590C2662L2060G42
keywords heavy-tailednoisenonconvexoptimizationgradientnormalizationclippingstochasticdescentmartingaleinequalitygeneralizedsmoothness
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 claims that gradient clipping is not a necessary ingredient for optimal convergence under heavy-tailed noise in nonconvex stochastic optimization. It studies the existing Batched NSGDM algorithm, which normalizes the momentum update to unit length, and proves that it achieves the optimal rate O($T^{{-(p-1)/(3p-2)}}$) when the noise has a finite p-th moment, matching the known lower bound. It also provides the first convergence guarantee when the tail index p is unknown, with a rate O($T^{{-(p-1)/(2p)}}$). The central insight is that normalization changes the error term that must be controlled from a second moment to a first moment, which falls within the range of the heavy-tailed assumption.

What carries the argument

The central object is Lemma 4.3, a new vector-valued martingale inequality: for a martingale difference sequence (a sequence of random vectors whose conditional mean given the past is zero) v_t in R^d and any p in [1,2], E[||sum_{t=1}^T v_t||] <= 2 $\sqrt$(2) E[(sum_{t=1}^T ||v_t||^p)^{1/p}]. This inequality is proved in Appendix C via an AdaGrad-style regret bound, and it extends the scalar Burkholder-Davis-Gundy inequality to high dimensions with an explicit constant. It is what allows the accumulated noise in the momentum error to be controlled using only a p-th moment, which is the exact information available under heavy-tailed noise. The normalization step in Batched NSGDM makes the descent inequality depend on the first moment of the error rather than the second, so this inequality becomes the key substitute for clipping.

What would settle it

To decide whether the central claim holds, one can check Lemma 4.3 numerically: simulate a martingale difference sequence in $R^{2}$ with p close to 1 and heavy-tailed increments, and see whether E[||sum v_t||] is bounded by 2 $\sqrt$(2) E[(sum ||v_t||^p)^{1/p}]. A counterexample would invalidate the proof and the theorem.

Watch

Extended reading notes

Core claim

The paper proves that Batched NSGDM, a normalized SGD with momentum, achieves the optimal convergence rate O($T^{{-(p-1)/(3p-2)}}$) for nonconvex stochastic optimization under heavy-tailed noise, meaning the stochastic gradient noise only has a finite p-th moment with p in (1,2]. This rate matches the existing lower bound, and the result holds under the more general (L0,L1)-smoothness condition. The same algorithm, with parameters chosen independent of p, also achieves the first convergence rate O($T^{{-(p-1)/(2p)}}$) when the tail index is unknown. The proof relies on a new dimension-free vector-valued martingale inequality that bounds the expected norm of a martingale sum by a p-th moment of its increments.

Load-bearing premise

The proof hinges on the new martingale inequality in Lemma 4.3; if that inequality fails for some p in [1,2] or in some dimension, the claimed rates would not follow.

Editorial extensions

If this is right

  • If the paper is correct, gradient clipping is not necessary for optimal heavy-tailed nonconvex convergence; normalized SGD with momentum achieves the same O(T^{-(p-1)/(3p-2)}) rate.
  • When the tail index p is unknown, Batched NSGDM still converges at O(T^{-(p-1)/(2p)}) with parameters that depend only on the horizon and, in the worst case, on L1.
  • The analysis extends to generalized smoothness and affine noise, so the result covers settings beyond the classical Lipschitz-gradient and finite-variance assumptions.
  • The refined lower bound matches the upper bound in Delta_1, L0, and sigma_0, showing the dependence is tight.

Reading between the lines

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

  • The new martingale inequality may be of independent interest and could simplify analyses of other stochastic algorithms with heavy-tailed noise, such as sign-based or adaptive methods.
  • A natural next step, suggested by the paper, is to determine whether the optimal O(T^{-(p-1)/(3p-2)}) rate is achievable without knowing p, or to prove a lower bound for the unknown-p setting.
  • The paper's claim that normalization is a robust primitive suggests that gradient clipping might only be a proxy for a more fundamental first-moment control; similar arguments may apply to other normalized updates.
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 / 5 minor

Summary. The paper studies Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) for nonconvex optimization under heavy-tailed noise with only a finite p-th moment. It claims the first optimal convergence rate O(T^{-(p-1)/(3p-2)}) without gradient clipping, a first O(T^{-(p-1)/(2p)}) rate when the tail index p is unknown, extensions to generalized (L0,L1)-smoothness and generalized heavy-tailed noise, and a refined lower bound with sharp dependence on problem parameters. The main technical novelty is Lemma 4.3, a dimension-free vector-valued martingale inequality proved in Appendix C through an AdaGrad regret argument.

Significance. If correct, the paper would be a significant contribution: it would show that gradient clipping is not necessary for optimal heavy-tailed nonconvex convergence, provide a partially parameter-agnostic guarantee, extend the theory to relaxed smoothness, and give a lower bound with matching parameter dependence. The paper is generally well structured, the appendix is detailed, and the high-level proof strategy via normalization is natural and interesting. However, the central martingale inequality is proved through Appendix C, and the printed proof contains an algebraic inconsistency; since Lemma 4.3 is the single tool behind all noise-accumulation bounds, Theorems 3.2 and 3.6 are not established as printed.

major comments (2)
  1. [Appendix C, Lemma C.1 and Eq. (11)] The proof of Lemma C.1 is not valid as printed. With gamma_t defined as sqrt(2 * sum_{s<=t} ||v_s||^2), gamma_t is nondecreasing, and ||v_t||^2 = (gamma_t^2 - gamma_{t-1}^2)/2. The displayed identity gamma_t ||v_t||^2 / 2 = gamma_t (1/gamma_t^2 - 1/gamma_{t-1}^2) is then false: the right-hand side is nonpositive while the left-hand side is nonnegative. A one-step numeric check, T=1 and v_1=10e_1, gives 707.1 on the left and 0.141 on the right if the chain were true. Consequently the bound sum_t gamma_t ||v_t||^2/2 <= 2/gamma_T does not follow. If gamma_t is intended to be the inverse AdaGrad stepsize, the definition and every subsequent display must be corrected. Because Lemma 4.3 is invoked in Lemmas 4.5 and D.5, and those lemmas underlie Theorems 3.2 and 3.6, the central no-clipping rates rest on an unproved inequality as printed.
  2. [Appendix C, derivation of Lemma 4.3 from Lemma C.1] Even apart from the algebraic error in Eq. (11), the proof of Lemma 4.3 requires Lemma C.1 to produce random vectors w_t that are measurable with respect to F_{t-1}, so that E[<v_t,w_t>] = 0. The construction via AdaGrad can yield such a predictable sequence, but the proof as written does not clearly separate the predictable iterate w_t from the updated iterate w_{t+1}, and the flawed inequality in Eq. (11) is an essential step in the displayed bound. The lemma itself is plausible and likely true by known Hilbert-space martingale inequalities, but the manuscript's only proof needs to be repaired before the derived rates can be accepted.
minor comments (5)
  1. [Abstract and Section 1.1] The abstract and contribution list describe the result as 'the first convergence result under heavy-tailed noises without gradient clipping,' but footnote 1 acknowledges two independent and concurrent works with similar results. The wording should be adjusted to avoid an overclaim, e.g., by saying 'independently and concurrently.'
  2. [Theorem 3.2] The statement allows sigma_0 >= 0, but the choice of beta divides by sigma_0. The noiseless case sigma_0 = 0 should be stated separately or handled by a limiting argument, since the displayed formulas are undefined at sigma_0 = 0.
  3. [Appendix D, proof of Theorem D.1] There are small presentation issues in the appendix, including the notation 'Delta L_0 T' in Eq. (16) where 'Delta_1' is meant, and the indicator '1_{s>=2}' is used without a prior definition. These should be cleaned up.
  4. [Lemma 2.5] Lemma 2.5 is stated without proof and delegated to a cited work. Since it is used repeatedly in the main proof, a short proof or a precise pointer to the cited lemma would improve self-containedness.
  5. [Appendix C, proof of Lemma C.1] The proof says 'W.l.o.g.' and then handles the case ||v_1|| > 0, but the treatment of the first nonzero v_t is abbreviated; it would be clearer to spell out the indexing shift in the statement of Lemma C.1 so that the subsequent summation over t is unambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence rates are derived from explicit assumptions via new martingale/regret inequalities and external lower-bound machinery; the suspected Lemma C.1 defect is a proof-correctness concern, not circularity.

full rationale

The derivation chain is self-contained. The upper bounds in Theorems 3.2 and 3.6 follow from the one-step descent inequality (Lemma 4.1 / D.4), the martingale-difference decomposition (Lemma 4.2), and the vector-valued martingale inequality (Lemma 4.3), whose proof in Appendix C is a self-contained AdaGrad-style regret argument based on Rakhlin & Sridharan (2017). The stepsize and momentum choices are explicit formulas in problem constants, and no fitted parameter is relabeled as a prediction. The lower bound (Theorem 3.3) uses the standard zero-chain construction of Carmon, Arjevani, and Zhang with a modified stochastic oracle; this is independent external machinery, not an input to the upper bound. Self-citations to Liu et al. (2023a,b) appear only in related-work comparisons and in a remark on the noiseless rate; they are not load-bearing. The skeptical concern about Lemma C.1 is that inequality (11) may be dimensionally inconsistent with the printed definition of gamma_t; if true, that is a correctness flaw in proving Lemma 4.3, not an instance of a conclusion being assumed or defined into existence. Accordingly, no circularity is exhibited.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No data fitting occurs. The hyperparameters beta and eta are explicitly prescribed functions of problem constants, not free fitting constants. The central proof relies on standard martingale and online-learning inequalities, plus the paper's assumptions on smoothness, unbiasedness, and finite p-th moment noise. No invented entities are introduced. The main novel tool, Lemma 4.3, is proved inside the paper rather than imported.

assumptions (6)
  • domain assumption Assumption 2.1: F has a finite lower bound
    Standard in nonconvex optimization; used with E[F(x_{T+1})] >= F* to telescope the descent inequality in Lemma D.4.
  • domain assumption Assumption 2.2: generalized (L0,L1)-smoothness
    Main smoothness model; invoked through Lemma 2.5 and Lemma D.4, and imposes the constraint ||x-y|| <= 1/L1, hence stepsize eta <= 1/L1.
  • domain assumption Assumption 2.3: unbiased batched gradient estimator with independent samples
    Standard oracle model; needed so that noise terms form a martingale difference sequence.
  • domain assumption Assumption 2.4: finite p-th moment noise with E||xi||^p <= sigma0^p + sigma1^p ||grad F(x)||^p
    The heavy-tailed noise model; with sigma1=0 it is the classical finite p-th moment assumption, and with sigma1>0 it is the paper's generalized version.
  • standard math Lemma C.1: AdaGrad-style regret bound from Rakhlin and Sridharan 2017
    Reproved in Appendix C; it is the engine behind the vector-valued martingale inequality Lemma 4.3.
  • standard math Zero-chain lower bound machinery from Carmon 2020, Arjevani 2023, and Zhang 2020c
    Used essentially in the proof of the refined lower bound Theorem 3.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping." pith.science (2026). https://pith.science/paper/XGEGMSCC

@misc{pith2026241219529,
  author       = {Pith},
  title        = {Pith review of: Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XGEGMSCC}},
  note         = {Machine review of arXiv:2412.19529}
}
abstract

Recently, the study of heavy-tailed noises in first-order nonconvex stochastic optimization has gotten a lot of attention since it was recognized as a more realistic condition as suggested by many empirical observations. Specifically, the stochastic noise (the difference between the stochastic and true gradient) is considered to have only a finite $\mathfrak{p}$-th moment where $\mathfrak{p}\in\left(1,2\right]$ instead of assuming it always satisfies the classical finite variance assumption. To deal with this more challenging setting, people have proposed different algorithms and proved them to converge at an optimal $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$ rate for smooth objectives after $T$ iterations. Notably, all these new-designed algorithms are based on the same technique - gradient clipping. Naturally, one may want to know whether the clipping method is a necessary ingredient and the only way to guarantee convergence under heavy-tailed noises. In this work, by revisiting the existing Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) algorithm, we provide the first convergence result under heavy-tailed noises but without gradient clipping. Concretely, we prove that Batched NSGDM can achieve the optimal $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$ rate even under the relaxed smooth condition. More interestingly, we also establish the first $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{2\mathfrak{p}}})$ convergence rate in the case where the tail index $\mathfrak{p}$ is unknown in advance, which is arguably the common scenario in practice.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 30 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Lower bounds for non-convex stochastic optimization

    Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 0 (1-2): 0 165--214, 2023

    2023

  3. [3]

    Optimization methods for large-scale machine learning

    L \'e on Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60 0 (2): 0 223--311, 2018

    2018

  4. [4]

    Extrapolation and interpolation of quasi-linear operators on martingales

    Donald L Burkholder and Richard F Gundy. Extrapolation and interpolation of quasi-linear operators on martingales. 1970

    work page 1970

  5. [5]

    Martingale transforms

    Donald Lyman Burkholder. Martingale transforms. The Annals of Mathematical Statistics, 37 0 (6): 0 1494--1504, 1966

    work page 1966

  6. [6]

    Lower bounds for finding stationary points i

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184 0 (1): 0 71--120, 2020

    work page 2020

  7. [7]

    Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization

    Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of ...

    work page 2023

  8. [8]

    Robustness to unbounded smoothness of generalized signsgd

    Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35: 0 9955--9968, 2022

    work page 2022

Show all 55 references
  1. [9]

    Momentum improves normalized SGD

    Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD . In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp.\ 2260--2268. PMLR, 13--18 Jul 2020. URL...

    2020

  2. [10]

    High-probability bounds for non-convex stochastic optimization with heavy tails

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

    2021

  3. [11]

    On the intergrability of the martingale square function

    Burgess Davis. On the intergrability of the martingale square function. Israel Journal of Mathematics, 8: 0 187--190, 1970

    1970

  4. [12]

    Adaptive subgradient methods for online learning and stochastic optimization

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12 0 (7), 2011

    2011

  5. [13]

    Beyond uniform smoothness: A stopped analysis of adaptive sgd

    Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learn...

    2023

  6. [14]

    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 0 (4): 0 2341--2368, 2013

    2013

  7. [15]

    High-probability convergence for composite and distributed stochastic minimization and variational inequalities with heavy-tailed noise

    Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova, Samuel Horv\' a th, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richt\' a rik. High-probability convergence for composite and distributed stochastic minimization and variational inequalities with heavy...

    2024

  8. [16]

    Beyond convexity: Stochastic quasi-convex optimization

    Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015

    2015

  9. [17]

    Revisiting convergence of adagrad with relaxed assumptions

    Yusu Hong and Junhong Lin. Revisiting convergence of adagrad with relaxed assumptions. arXiv preprint arXiv:2402.13794, 2024

    2024 arXiv

  10. [18]

    From gradient clipping to normalization for heavy tailed sgd

    Florian H \"u bler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. arXiv preprint arXiv:2410.13849, 2024

    2024 arXiv

  11. [19]

    Parameter-agnostic optimization under relaxed smoothness

    Florian H\" u bler, Junchi Yang, Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 o...

    2024

  12. [20]

    Non-convex distributionally robust optimization: Non-asymptotic analysis

    Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 0 2771--2782, 2021

    2021

  13. [21]

    Adam: A method for stochastic optimization

    Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  14. [22]

    Convergence and efficiency of subgradient methods for quasiconvex minimization

    Krzysztof C Kiwiel. Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical programming, 90: 0 1--25, 2001

    2001

  15. [23]

    Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance

    Nikita Kornilov, Ohad Shamir, Aleksandr Lobanov, Darina Dvinskikh, Alexander Gasnikov, Innokentiy Shibaev, Eduard Gorbunov, and Samuel Horv\' a th. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance. In A. Oh, T. Nauman...

    2023

  16. [24]

    First-order and stochastic optimization methods for machine learning

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

    2020

  17. [25]

    The power of normalization: Faster evasion of saddle points

    Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv:1611.04831, 2016

    2016 arXiv

  18. [26]

    Convex and non-convex optimization under generalized smoothness

    Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, ...

    2023

  19. [27]

    Convergence of adam under relaxed assumptions

    Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp.\ 52166--52196. Curran Associates, ...

    2023

  20. [28]

    High-probability bound for non-smooth non-convex stochastic optimization with heavy tails

    Langqi Liu, Yibo Wang, and Lijun Zhang. High-probability bound for non-smooth non-convex stochastic optimization with heavy tails. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings o...

    2024

  21. [29]

    Stochastic nonsmooth convex optimization with heavy-tailed noises

    Zijian Liu and Zhengyuan Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises. arXiv preprint arXiv:2303.12277, 2023

    2023 arXiv

  22. [30]

    Near-optimal non-convex stochastic optimization under generalized smoothness

    Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near-optimal non-convex stochastic optimization under generalized smoothness. arXiv preprint arXiv:2302.06032, 2023 a

    2023 arXiv

  23. [31]

    Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise

    Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, vol...

    2023

  24. [32]

    Brendan McMahan and Matthew J

    H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In Conference on Learning Theory (COLT) , pp.\ 244--256. Omnipress, 2010

    2010

  25. [33]

    Convergence of gradient descent on separable data

    Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp.\ 3420--3428. PMLR, 2019

    2019

  26. [34]

    Lectures on convex optimization, volume 137

    Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018

    2018

  27. [35]

    Minimization methods for nonsmooth convex and quasiconvex functions

    Yurii E Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29 0 (3): 0 519--531, 1984

    1984

  28. [36]

    Improved convergence in high probability of clipped gradient methods with heavy tailed noise

    Ta Duy Nguyen, Thien H Nguyen, Alina Ene, and Huy Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Advances in Neural Information Processing Systems, 36: 0 24191--24222, 2023

    2023

  29. [37]

    Breaking the heavy-tailed noise barrier in stochastic optimization problems

    Nikita Puchkin, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. In International Conference on Artificial Intelligence and Statistics, pp.\ 856--864. PMLR, 2024

    2024

  30. [38]

    On equivalence of martingale tail bounds and deterministic regret inequalities

    Alexander Rakhlin and Karthik Sridharan. On equivalence of martingale tail bounds and deterministic regret inequalities. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp.\ 17...

    2017

  31. [39]

    A stochastic approximation method

    Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp.\ 400--407, 1951

    1951

  32. [40]

    High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance

    Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horv\' a th, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richt\' a rik. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In Andre...

    2023

  33. [41]

    u rb \"u zbalaban, Thanh Huy Nguyen, Ga \

    Umut S im s ekli, Mert G \"u rb \"u zbalaban, Thanh Huy Nguyen, Ga \"e l Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv:1912.00018, 2019

    1912 arXiv

  34. [42]

    A tail-index analysis of stochastic gradient noise in deep neural networks

    Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pp.\ 5827--5837. PMLR, 2019

    2019

  35. [43]

    Gradient normalization provably benefits nonconvex sgd under heavy-tailed noise

    Tao Sun, Xinwang Liu, and Kun Yuan. Gradient normalization provably benefits nonconvex sgd under heavy-tailed noise. arXiv preprint arXiv:2410.16561, 2024

    2024

  36. [44]

    Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude

    Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4 0 (2): 0 26--31, 2012

    2012

  37. [45]

    Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions

    Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Mac...

    2023

  38. [46]

    On the convergence of adam under non-uniform smoothness: Separability from sgdm and beyond

    Bohan Wang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, and Wei Chen. On the convergence of adam under non-uniform smoothness: Separability from sgdm and beyond. arXiv preprint arXiv:2403.15146, 2024

    2024 arXiv

  39. [47]

    Large batch training of convolutional networks

    Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arXiv:1708.03888, 2017

    2017 arXiv

  40. [48]

    Large batch optimization for deep learning: Training bert in 76 minutes

    Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv:1904.00962, 2019

    1904 arXiv

  41. [49]

    Improved analysis of clipping algorithms for non-convex optimization

    Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33: 0 15511--15521, 2020 a

    2020

  42. [50]

    Why gradient clipping accelerates training: A theoretical justification for adaptivity

    Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020 b . URL https://openreview.net/forum?id=BJgnXpVYwS

    2020

  43. [51]

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

    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: 0 15383--15393, 2020 c

    2020

  44. [52]

    Parameter-free regret in high probability with heavy tails

    Jiujia Zhang and Ashok Cutkosky. Parameter-free regret in high probability with heavy tails. Advances in Neural Information Processing Systems, 35: 0 8000--8012, 2022

    2022

  45. [53]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  46. [54]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  47. [55]

    denotes the set of natural numbers (excluding 0 )

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

Pith tools

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