Pith. sign in

REVIEW 3 major objections 4 minor 3 cited by

Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness

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

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

Pith's one-line read The paper proves the first high-probability convergence bounds for sign-based SGD under generalized $(L_0,L_1)$-smoothness and heavy-tailed noise, with sample complexity matching clipping and normalization without clipping-level tuning.

desk verdict The paper has the right idea and probably the right rates, but Lemma 1 has a genuine circularity in the high-probability argument, and until that is fixed the headline complexity bounds are not proven as written. read the letter →

arxiv 2502.07923 v2 pith:WSBWPGLT submitted 2025-02-11 math.OC cs.LG

Nikita Kornilov , Philip Zmushko , Andrei Semenov , Mark Ikonnikov , Alexander Gasnikov , Alexander Beznosikov This is my paper · ORCID
classification math.OCcs.LG MSC 90C2690C1562L20
keywords sign-basedoptimizationheavy-tailednoise(L0L1)-smoothnesshigh-probabilityboundsnon-convexSignSGDmajorityvotingstochasticapproximation
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

The paper asks whether the sign operator—discarding each gradient coordinate's magnitude and keeping only its sign—can replace clipping or normalization as a defense against heavy-tailed gradient noise in non-convex optimization. It answers yes: under $(L_0,L_1)$-smoothness, a generalized smoothness model in which the Hessian norm may grow linearly with the gradient norm, and under noise with a bounded $\kappa$-th moment, minibatch-SignSGD reaches average $\ell_1$ gradient accuracy $\varepsilon$ with probability at least $1-\delta$ using $N = O((\Delta L_0 d/\varepsilon^2 + \Delta L_1 d^{3/2}/\varepsilon)(1+(\|\sigma\|_1/\varepsilon)^{\kappa/(\kappa-1)})\log(1/\delta))$ samples, with $\kappa\in(1,2]$. The paper claims these are the first high-probability bounds in this combined setting, matching the optimal order for standard smoothness. A second variant, MajorityVote-SignSGD, replaces batching with majority voting over sign observations and, under unimodal symmetric noise, works for every $\kappa\in(0,2]$ with a $1/\kappa^2 + (\|\sigma\|_1/\varepsilon)^2$ dependence. Experiments on LLaMA-style language models up to 1.3B parameters and on a Switch-Transformer mixture-of-experts model show sign-based momentum methods beating clipped and normalized momentum baselines and matching or slightly beating AdamW.

What carries the argument

The load-bearing object is the coordinate-wise sign operator applied to gradient estimates. The proof's engine is a per-coordinate disagreement bound: with noise of $\kappa$-th moment $\sigma_i^\kappa$, the probability that $\mathrm{sign}(g_i)$ disagrees with $\mathrm{sign}(\nabla f_i)$ is at most $\sigma_i/|\nabla f_i|$, so the expected aligned length $\langle\nabla f, \mathrm{sign}(g)\rangle$ is at least $\|\nabla f\|_1 - 2\|\sigma\|_1$. A martingale measure-concentration lemma promotes this to a high-probability bound with only $\log(1/\delta)$. The $(L_0,L_1)$-smoothness descent lemma bounds the one-step function decrease by $L_0 d \gamma^2$ plus an $L_1$-dependent term, forcing the stepsize cap $\gamma \leq 1/(48 L_1 d^{3/2} \log(1/\delta))$. Batching reduces the effective noise by the factor $B^{-(\kappa-1)/\kappa}$, while majority voting uses Gauss's inequality for unimodal symmetric noise to make each coordinate's sign error probability less than $1/2$, so the majority of $M$ independent signs fails with probability $O(1/\sqrt{M})$ and the $\kappa$ exponent drops out.

What would settle it

Run minibatch-SignSGD on a synthetic $(L_0,L_1)$-smooth objective with known constants (for instance $f(x)=\exp(a^\top x)$ with a small $L_0$ regularizer) and independent Student-$t$ noise of tail index $\kappa\in(1,2]$, measuring the sample count to hit average $\ell_1$ gradient norm $\varepsilon$ with probability $1-\delta$. The theorem predicts $N = O((\Delta L_0 d/\varepsilon^2 + \Delta L_1 d^{3/2}/\varepsilon)(1+(\sigma/\varepsilon)^{\kappa/(\kappa-1)})\log(1/\delta))$; if the empirical exponent of $\sigma/\varepsilon$ departs from $\kappa/(\kappa-1)$ as $\kappa$ varies, the central bound is wrong. For majority voting, repeat with skewed heavy-tailed noise: if any coordinate's sign is wrong more than half the time, the $\sigma^2/\varepsilon^2$ rate should break, showing the symmetry assumption is indispensable.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that the sign operator is a complete substitute for clipping and normalization when the objective is $(L_0,L_1)$-smooth and the noise is heavy-tailed. Theorem 1 states that minibatch-SignSGD reaches average $\ell_1$ gradient accuracy $\varepsilon$ with probability $1-\delta$ using $N = O((\Delta L_0 d/\varepsilon^2 + \Delta L_1 d^{3/2}/\varepsilon)(1+(\|\sigma\|_1/\varepsilon)^{\kappa/(\kappa-1)})\log(1/\delta))$ samples for $\kappa\in(1,2]$. Theorem 2 states that under unimodal symmetric noise, MajorityVote-SignSGD achieves $N = O((\Delta L_0 d/\varepsilon^2 + \Delta L_1 d^{3/2}/\varepsilon)(1/\kappa^2 + (\|\sigma\|_1/\varepsilon)^2)\log(1/\delta))$ for all $\kappa\in(0,2]$. The paper claims these are the first high-probability bounds for sign-based methods under $(L_0,L_1)$-smoothness with heavy-tailed noise, and that they reduce to the optimal known rates when $L_1=0$.

Load-bearing premise

All high-probability results assume the gradient noise has a finite $\kappa$-th moment in every coordinate, and the majority-voting results further assume each coordinate's noise is symmetric and unimodal about the true gradient, so skewed or multimodal noise would void that second guarantee.

Editorial extensions

If this is right

  • SignSGD with batching is a parameter-free alternative to clipping: it attains the same sample-complexity order as ClipSGD and NSGD under heavy-tailed noise without selecting a clipping level.
  • Convergence is two-stage: for $\varepsilon \geq 8L_0/(L_1\sqrt{d})$ the bound is dominated by $(\Delta L_1 d^{3/2}/\varepsilon)(\|\sigma\|_1/\varepsilon)^{\kappa/(\kappa-1)}$, and below that threshold the $L_0$-term $(\Delta L_0 d/\varepsilon^2)(\|\sigma\|_1/\varepsilon)^{\kappa/(\kappa-1)}$ takes over.
  • Under unimodal symmetric noise, majority voting changes the noise dependence from $(\|\sigma\|_1/\varepsilon)^{\kappa/(\kappa-1)}$ to $(\|\sigma\|_1/\varepsilon)^2$, so the tail index $\kappa$ enters only through a $1/\kappa^2$ factor and the method works for every $\kappa>0$.
  • Momentum SignSGD keeps the same order of total sample complexity while using small constant batch sizes, the regime used in practical language-model pretraining.
  • For Polyak-Łojasiewicz objectives, restarted minibatch-SignSGD turns the average-gradient guarantee into high-probability function suboptimality with sample complexity $O((L_0 d/\mu + L_1 d^{3/2}\sqrt{\Delta}/\sqrt{\mu})(1+(\|\sigma\|_1^2/(\mu\varepsilon))^{\kappa/(2(\kappa-1))}))$ up to log factors.

Reading between the lines

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

  • Because the fast-phase stepsize cap scales as $1/(L_1 d^{3/2}\log(1/\delta))$, the practical advantage over normalized SGD may shrink in very high dimension; a clean ablation fixing $L_1$ and varying $d$ would show whether the fast phase survives.
  • The majority-voting guarantee rests on unimodal symmetric coordinate noise; a quick empirical check on real language-model gradients would show whether this holds, and skewed or multimodal coordinates would make minibatch-SignSGD the safer theoretical contract.
  • The momentum result is proved in expectation, so a high-probability version of M-SignSGD under $(L_0,L_1)$-smoothness remains open; the experiments suggest it is the practically relevant gap.
  • The perplexity win over AdamW is not derived from the theorems, which analyze sign updates on raw gradients; testing sign updates on Adam-style preconditioned directions would separate the sign effect from adaptive scaling.
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

3 major / 4 minor

Summary. The manuscript studies sign-based stochastic first-order methods for non-convex optimization under (L0,L1)-smoothness and heavy-tailed gradient noise. It claims high-probability sample complexity bounds for minibatch-SignSGD, a majority-vote variant under symmetric unimodal noise, momentum-based M-SignSGD (in expectation), and restarted variants for Polyak-Lojasiewicz functions, together with parameter-agnostic tuning schedules and large-scale LLM experiments. The central advertised result is the high-probability bound N = O(((ΔL0d/ε^2) + (ΔL1d^{3/2}/ε))[1 + (‖σ‖1/ε)^{κ/(κ-1)}] log(1/δ)) for κ ∈ (1,2], and an analogous bound for majority voting with milder noise dependence for κ ∈ (0,2].

Significance. If the proofs are repaired, the contribution is significant: it extends the high-probability analysis of sign-based methods to the combined setting of (L0,L1)-smoothness and heavy-tailed noise, with logarithmic dependence on 1/δ and mild parameter dependencies. The two-stage convergence discussion and the large-scale experiments on LLaMA and MoE models give the paper practical relevance. However, the central high-probability lemma contains a serious probabilistic gap, and at least one stepsize feasibility check is algebraically incorrect; as written, the main theorems are not established.

major comments (3)
  1. [Appendix A.3, proof of Lemma 1] Lemma 3 is stated and used as a fixed-λ concentration bound for martingale difference sequences, but the proof of Lemma 1 chooses λ as a function of the realized path, namely λ := 1/[6d(γmax‖∇f(x1)‖1 + Σ_{k=1}^T γk‖∇f(xk)‖1/(48d log(1/δ)) + 2CT L0)], and then substitutes this random λ into the bound. Lemma 3 does not provide a uniform bound over data-dependent λ, and no union bound over a λ-grid or self-normalized martingale inequality is supplied. This gap affects Lemma 1 directly and hence all downstream results that rely on it (Theorems 1, 2, 4–7, and 9–11). A uniform-in-λ concentration inequality or an appropriate peeling argument is needed.
  2. [Appendix A.4, proof of Theorem 4] After deriving the bound with the term 24d‖∇f(x1)‖1 log(1/δ)/T, the proof discards it with the sentence 'We can omit the last term since its dependency on T has the largest power.' This term is O(1/T), the same order as the main term Δ/(Tγ). For the chosen optimal T in the fast phase it is O(ε‖∇f(x1)‖1/(ΔL1√d)), and in the slow phase O(ε^2‖∇f(x1)‖1/(ΔL0)); neither is bounded by ε under the stated assumptions. Therefore the claimed sample complexity, which is independent of ‖∇f(x1)‖1, is not established as written.
  3. [Appendix A.4, proof of Theorem 4, slow-phase feasibility check] The verification that γ = sqrt(4Δ/(80T L0 log(1/δ)d)) satisfies γ ≤ 1/(48L1 d^{3/2} log(1/δ)) is algebraically incorrect. With the stated choice of T, the displayed chain yields γ ≤ 1/(40 L1√d log(1/δ)), and the final claimed inequality 1/(40 L1√d log(1/δ)) ≤ 1/(48 L1 d^{3/2} log(1/δ)) is false for d ≥ 1. The argument can likely be repaired by increasing the universal constant in T, but as written the slow-phase stepsize violates the condition of Lemma 1.
minor comments (4)
  1. [Appendix A.3, Eq. (19) vicinity] There is an inconsistency in the displayed constants: an intermediate line uses 6√d(γmax‖∇f(x1)‖1 + 2CT L0) log(1/δ), while the final bound in Eq. (19) uses 6d(γmax‖∇f(x1)‖1 + 2CT L0) log(1/δ). The constants should be reconciled.
  2. [Theorem 4 statement] In the two arbitrary-tuning cases, the statement begins with 'T, γk ≡ ...' without specifying the value or range of T. The intended finite-horizon schedule should be stated explicitly.
  3. [Appendix C, noise model] The experiments use α-stable noise with κ ∈ {2, 1.5, 1}, but Assumption 3 requires κ ∈ (1,2] and a finite κ-th moment. For κ = 1 the condition is outside the stated assumption; the text should explain how the experimental noise model is related to the theory, or restrict the reported κ values.
  4. [Section 3 and Appendix D] The main text compares M-SignSGD with M-ClippedSGD, while Appendix D introduces 'M-ClippedSignSGD'. The relationship between these baselines should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the high-probability bounds follow from the stated assumptions and independent concentration/batching lemmas.

full rationale

The paper's derivation chain is self-contained in the relevant sense. Lemma 1 starts from Assumptions 1–3 and the (L0,L1)-smoothness descent inequality (Lemma 2), applies martingale concentration (Lemma 3) to the martingale difference D_k, controls the sign-probability via Markov/Jensen, and arrives at bound (3); the later theorems choose stepsizes and batch sizes as explicit functions of the inputs L0, L1, σ, δ, ε, not as fitted values of the output. Theorem 2 adds a genuinely stronger unimodal-symmetric assumption and uses Gauss's inequality (Lemma 7); its milder κ-dependence comes from that external inequality rather than from assuming the conclusion. Lemma 4 is the only place a self-citation (Ref. [39]) appears, but the batching bound is credited there to the independent proof of [12, Lemma 4.2] and is also used by [30]; it is a standard MDS moment bound, so the self-citation is not load-bearing. The reviewer-flagged choice of λ after seeing Σ γ_k ||∇f(x_k)||_1 is a potential technical gap in the high-probability argument (Lemma 3 is stated for fixed λ), and the 'omitted' ||∇f(x1)||/T term in Theorem 4 is likewise a proof-completeness issue; but neither step equates a prediction to an input by construction, renames a fitted parameter as a prediction, or imports a uniqueness claim from the authors' prior work. Hence the circularity score is 0.

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

The central claim relies on standard domain assumptions (L0,L1-smoothness, heavy-tailed noise, PL condition for the restart results, and unimodal symmetric noise for the majority-vote result). No new entities or fitted constants are introduced; the step sizes and batch sizes in the theorems are derived from the problem parameters.

assumptions (8)
  • domain assumption Objective function is lower bounded (Assumption 1).
    Standard for non-convex optimization; needed for telescoping sums over function values.
  • domain assumption (L0,L1)-smoothness with sup over segment (Assumption 2).
    Central smoothness model motivated by LLM training; used in Lemma 2 and throughout the proofs.
  • domain assumption Heavy-tailed noise with bounded kappa-th moment coordinate-wise (Assumption 3).
    Defines the noise class; the main results are proven for kappa in (1,2].
  • domain assumption Polyak-Lojasiewicz condition (Assumption 4) for restart results.
    Used only in Theorems 9 and 10 for accelerated function-value convergence.
  • domain assumption Unimodal and symmetric noise for MajorityVote-SignSGD (stated in Theorem 2).
    Needed to apply Gauss's Inequality (Lemma 7) and to guarantee that majority voting improves the sign accuracy.
  • standard math Measure Concentration Lemma (Lemma 3, from [43]).
    Provides the log(1/delta) high-probability dependency for martingale difference sequences.
  • standard math HT Batching Lemma (Lemma 4, from [12,39,30]).
    Controls the reduction of heavy-tailed noise under minibatching; the paper applies it to coordinate-wise moments.
  • standard math Gauss's Inequality for unimodal symmetric distributions (Lemma 7, from [20]).
    Gives a sharp tail bound used to analyze the single-sample sign error probability in majority voting.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness." pith.science (2026). https://pith.science/paper/WSBWPGLT

@misc{pith2026250207923,
  author       = {Pith},
  title        = {Pith review of: Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WSBWPGLT}},
  note         = {Machine review of arXiv:2502.07923}
}
abstract

In recent years, non-convex optimization problems are more often described by generalized $(L_0, L_1)$-smoothness assumption rather than standard one. Meanwhile, severely corrupted data used in these problems has increased the demand for methods capable of handling heavy-tailed noises, i.e., noises with bounded $\kappa$-th moment. Motivated by these real-world trends and challenges, we explore sign-based methods in this setup and demonstrate their effectiveness in comparison with other popular solutions like clipping or normalization. In theory, we prove the first-known high probability convergence bounds under $(L_0, L_1)$-smoothness and heavy-tailed noises with mild parameter dependencies. In the case of standard smoothness, these bounds are novel for sign-based methods as well. In particular, SignSGD with batching achieves sample complexity $\tilde{O}\left(\left(\frac{\Delta L_0d}{\varepsilon^2} + \frac{\Delta L_1d^\frac{3}{2}}{\varepsilon}\right)\left[1 + \left(\frac{\sigma}{\varepsilon}\right)^\frac{\kappa}{\kappa-1}\right]\right), \kappa \in (1,2]$. Under the assumption of symmetric noises, SignSGD with Majority Voting can robustly work on the whole range of $\kappa \in (0,2]$ with complexity $\tilde{O}\left(\left(\frac{\Delta L_0d}{\varepsilon^2} + \frac{\Delta L_1d^\frac{3}{2}}{\varepsilon}\right)\left[\frac{1}{\kappa^2} + \frac{\sigma^2}{\varepsilon^2}\right]\right)$. We also obtain results for parameter-agnostic setups, Polyak-Lojasiewicz functions and momentum-based methods (in expectation). Our theoretical findings are supported by the superior performance of sign-based methods in training Large Language Models compared to clipping and normalization.

Figures

Figures reproduced from arXiv: 2502.07923 by the authors.

Figure 1
Figure 1. Experimental noise dependencies for (L0, L1)-smoooth problems. In practice, the achieved accuracy does not depend on κ, only linearly on σ. We also wish to highlight the small size of error bars especially in the end of training which corresponds to mild log 1 δ dependency. In addition, we check how well batching (Alg. 2) and majority voting (Alg. 3) reduce the noise, .i.e, whether reduction laws σ/B κ−1 κ and σ/√ M… view at source ↗
Figure 2
Figure 2. Experimental convergence speed transition for [PITH_FULL_IMAGE:figures/full_fig_p035_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization

    cs.LG 2026-02 reject novelty 6.0 of 10

    For non-convex smooth costs, the tail probability that SGD's best gradient remains above a fixed threshold decays at speed t/log(t) (bounded noise), and clipped SGD achieves t^{4(p-1)/(3p-2)}/log(t) under p-th moment ...

  2. DeMuon: A Decentralized Muon for Matrix Optimization over Graphs

    math.OC 2025-10 conditional novelty 6.0 of 10

    A decentralized Muon optimizer with gradient tracking reaches a stochastic stationary point at the same iteration complexity as centralized heavy-tailed algorithms.

  3. Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise

    math.OC 2025-06 reject novelty 6.0 of 10

    Lion and Muon with weight decay are shown to be instances of one stochastic Frank-Wolfe algorithm, and clipped and variance-reduced variants get the first high-probability convergence rates for nonconvex Frank-Wolfe u...

Reference graph

Works this paper leans on

81 extracted references · 50 canonical work pages · cited by 3 Pith papers

  1. [39]

    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áth. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  2. [1]

    Differentially private learning with adaptive clipping

    Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455–17466, 2021

    2021

  3. [2]

    Lower bounds for non-convex stochastic optimization

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

    2023

  4. [3]

    High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise

    Aleksandar Armacki, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, and Soummya Kar. High-probability convergence bounds for nonlinear stochastic gradient descent under heavy-tailed noise. arXiv preprint arXiv:2310.18784, 2023

    work page Pith review arXiv

  5. [4]

    Large deviations and improved mean-squared error rates of nonlinear sgd: Heavy-tailed noise and power of symmetry

    Aleksandar Armacki, Shuhua Yu, Dragana Bajovic, Dusan Jakovetic, and Soummya Kar. Large deviations and improved mean-squared error rates of nonlinear sgd: Heavy-tailed noise and power of symmetry. arXiv preprint arXiv:2410.15637, 2024

    arXiv

  6. [5]

    signsgd: Compressed optimisation for non-convex problems

    Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560–569. PMLR, 2018

    2018

  7. [6]

    signsgd with majority vote is communication efficient and fault tolerant

    Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint arXiv:1810.05291, 2018

    arXiv 2018

  8. [7]

    Stochastic gradient descent tricks

    Léon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade: Second Edition, pages 421–436. Springer, 2012

    work page 2012

Show all 81 references
  1. [8]

    Convex optimization

    Stephen Boyd. Convex optimization. Cambridge UP, 2004

    2004

  2. [9]

    Libsvm: a library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1–27, 2011

    2011

  3. [10]

    Understanding gradient clipping in private sgd: A geometric perspective

    Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 33:13773–13782, 2020. 10

    2020

  4. [11]

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

    Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex op- timization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pages 5396–5427. PMLR, 2023

    2023

  5. [12]

    Optimal mean estimation without a variance

    Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter Bartlett, and Michael Jordan. Optimal mean estimation without a variance. In Conference on Learning Theory, pages 356–357. PMLR, 2022

    2022

  6. [13]

    Unbiased and sign compression in distributed learning: Comparing noise resilience via sdes

    Enea Monzio Compagnoni, Rustem Islamov, Frank Norbert Proske, and Aurelien Lucchi. Unbiased and sign compression in distributed learning: Comparing noise resilience via sdes. arXiv preprint arXiv:2502.17009, 2025

    2025 arXiv

  7. [14]

    Adaptive methods through the lens of sdes: Theoretical insights on the role of noise

    Enea Monzio Compagnoni, Tianlin Liu, Rustem Islamov, Frank Norbert Proske, Antonio Orvieto, and Aurelien Lucchi. Adaptive methods through the lens of sdes: Theoretical insights on the role of noise. arXiv preprint arXiv:2411.15958, 2024

    2024 arXiv

  8. [15]

    Complexity lower bounds of adaptive gradient algorithms for non-convex stochastic optimization under relaxed smoothness, 2025

    Michael Crawshaw and Mingrui Liu. Complexity lower bounds of adaptive gradient algorithms for non-convex stochastic optimization under relaxed smoothness, 2025

    2025

  9. [16]

    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:9955–9968, 2022

    2022

  10. [17]

    Momentum improves normalized sgd

    Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International conference on machine learning, pages 2260–2268. PMLR, 2020

    2020

  11. [18]

    High-probability bounds for non-convex stochastic opti- mization with heavy tails

    Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic opti- mization with heavy tails. Advances in Neural Information Processing Systems, 34, 2021

    2021

  12. [19]

    From low probability to high confidence in stochastic convex optimization

    Damek Davis, Dmitriy Drusvyatskiy, Lin Xiao, and Junyu Zhang. From low probability to high confidence in stochastic convex optimization. Journal of Machine Learning Research, 22(49):1–38, 2021

    2021

  13. [20]

    The gauss–tchebyshev inequality for uni- modal distributions

    Sudhakar W Dharmadhikari and Kumar Joag-Dev. The gauss–tchebyshev inequality for uni- modal distributions. Theory of Probability & Its Applications, 30(4):867–871, 1986

    1986

  14. [21]

    Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity

    William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(120):1–39, 2022

    2022

  15. [22]

    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

  16. [23]

    A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness

    Xiaochuan Gong, Jie Hao, and Mingrui Liu. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness. In Forty-first International Conference on Machine Learning

  17. [24]

    Deep learning

    Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016

    2016

  18. [25]

    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

    2020

  19. [26]

    Methods for convex (l_0, l_1)-smooth optimization: Clipping, acceleration, and adaptivity

    Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Taká ˇc. Methods for convex (l_0, l_1)-smooth optimization: Clipping, acceleration, and adaptivity. arXiv preprint arXiv:2409.14989, 2024

    2024 arXiv

  20. [27]

    The heavy-tail phenomenon in sgd

    Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pages 3964–3975. PMLR, 2021

    2021

  21. [28]

    Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis

    Jie Hao, Xiaochuan Gong, and Mingrui Liu. Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis. InThe Twelfth International Conference on Learning Representations. 11

  22. [29]

    Beyond convexity: Stochastic quasi-convex optimization

    Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. In Advances in Neural Information Processing Systems, pages 1594–1602, 2015

    2015

  23. [30]

    From gradient clipping to normalization for heavy tailed sgd

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

    2024 arXiv

  24. [31]

    Parameter-agnostic optimization under relaxed smoothness

    Florian Hübler, Junchi Yang, Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness. In International Conference on Artificial Intelligence and Statistics, pages 4861–4869. PMLR, 2024

    2024

  25. [32]

    Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise

    Dusan Jakovetic, Dragana Bajovic, Anit Kumar Sahu, Soummya Kar, Nemanja Milosevich, and Dusan Stamenkovic. Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise. SIAM Journal on Optimization, 33(2):394–423, 2023

    2023

  26. [33]

    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:2771–2782, 2021

    2021

  27. [34]

    Stochastic-sign sgd for federated learning with theoretical guarantees

    Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign sgd for federated learning with theoretical guarantees. arXiv preprint arXiv:2002.10940, 2020

    2002 arXiv

  28. [35]

    Learning from history for byzantine robust optimization

    Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pages 5311–5319. PMLR, 2021

    2021

  29. [36]

    Error feedback fixes signsgd and other gradient compression schemes

    Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252–3261. PMLR, 2019

    2019

  30. [37]

    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

  31. [38]

    Revisiting gradient clipping: Stochastic bias and tight convergence guarantees

    Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pages 17343–17363. PMLR, 2023

    2023

  32. [40]

    Large-scale methods for distributionally robust optimization

    Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems , 33:8847–8860, 2020

    2020

  33. [41]

    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. Advances in Neural Information Processing Systems, 36:40238–40271, 2023

    2023

  34. [42]

    Convergence of adam under relaxed assumptions

    Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36:52166–52196, 2023

    2023

  35. [43]

    A high probability analysis of adaptive sgd with momentum

    Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint arXiv:2007.14294, 2020

    2007 arXiv

  36. [44]

    Relora: High- rank training through low-rank updates

    Vladislav Lialin, Sherin Muckatira, Namrata Shivagunde, and Anna Rumshisky. Relora: High- rank training through low-rank updates. In The Twelfth International Conference on Learning Representations, 2023

    2023

  37. [45]

    Loss landscapes and optimization in over- parameterized non-linear systems and neural networks

    Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85–116, 2022. 12

    2022

  38. [46]

    A communication-efficient distributed gradient clipping algorithm for training deep neural networks

    Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-efficient distributed gradient clipping algorithm for training deep neural networks. Advances in Neural Information Processing Systems, 35:26204–26217, 2022

    2022

  39. [47]

    Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing

    Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM computing surveys, 55(9):1–35, 2023

    2023

  40. [48]

    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 The Thirty Sixth Annual Conference on Learning Theory, pages 2266–2290. PMLR, 2023

    2023

  41. [49]

    Decoupled weight decay regularization

    I Loshchilov. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017

    2017 arXiv

  42. [50]

    Algorithms of robust stochastic optimization based on mirror descent method

    Aleksandr Viktorovich Nazin, AS Nemirovsky, Aleksandr Borisovich Tsybakov, and AB Judit- sky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80(9):1607–1627, 2019

    2019

  43. [51]

    Robust stochastic approximation approach to stochastic programming

    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

  44. [52]

    Improved convergence in high probability of clipped gradient methods with heavy tails

    Ta Duy Nguyen, Alina Ene, and Huy L Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv preprint arXiv:2304.01119, 2023

    2023 arXiv

  45. [53]

    On the difficulty of training recurrent neural networks

    Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310–1318, 2013

    2013

  46. [54]

    The fineweb datasets: Decanting the web for the finest text data at scale

    Guilherme Penedo, Hynek Kydlıcek, Loubna Ben Allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro von Werra, and Thomas Wolf. The fineweb datasets: Decanting the web for the finest text data at scale. corr, abs/2406.17557, 2024. doi: 10.48550. arXiv preprint ARXIV .2...

    2024 arXiv

  47. [55]

    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, pages 856–864. PMLR, 2024

    2024

  48. [56]

    High probability convergence of clipped distributed dual averaging with heavy-tailed noises

    Yanfu Qin, Kaihong Lu, Hang Xu, and Xiangyong Chen. High probability convergence of clipped distributed dual averaging with heavy-tailed noises. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2025

    2025

  49. [57]

    Exploring the limits of transfer learning with a unified text-to-text transformer

    Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1–67, 2020

    2020

  50. [58]

    Variance-reduced clipping for non-convex optimization

    Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1–5. IEEE, 2025

    2025

  51. [59]

    A stochastic approximation method

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

    1951

  52. [60]

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

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

    2023 arXiv

  53. [61]

    Stochastic sign descent methods: New algorithms and better theory

    Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, pages 9224–9234. PMLR, 2021

    2021

  54. [62]

    1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns

    Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Interspeech, volume 2014, pages 1058–1062. Singapore, 2014. 13

    2014

  55. [63]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014

    2014

  56. [64]

    Glu variants improve transformer

    Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202, 2020

    2002 arXiv

  57. [65]

    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, pages 5827–5837. PMLR, 2019

    2019

  58. [66]

    Momentum ensures convergence of signsgd under weaker assumptions

    Tao Sun, Qingsong Wang, Dongsheng Li, and Bao Wang. Momentum ensures convergence of signsgd under weaker assumptions. In International Conference on Machine Learning, pages 33077–33099. PMLR, 2023

    2023

  59. [67]

    Llama: Open and efficient foundation language models

    Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023

    2023 arXiv

  60. [68]

    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 The Thirty Sixth Annual Conference on Learning Theory, pages 161–190. PMLR, 2023

    2023

  61. [69]

    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

  62. [70]

    Provable adaptivity of adam under non-uniform smoothness

    Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, Tie-Yan Liu, Zhi-Quan Luo, and Wei Chen. Provable adaptivity of adam under non-uniform smoothness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2960–2969, 2024

    2024

  63. [71]

    Two sides of one coin: the limits of untuned sgd and the power of adaptive methods

    Junchi Yang, Xiang Li, Ilyas Fatkhullin, and Niao He. Two sides of one coin: the limits of untuned sgd and the power of adaptive methods. Advances in Neural Information Processing Systems, 36, 2024

    2024

  64. [72]

    Root mean square layer normalization

    Biao Zhang and Rico Sennrich. Root mean square layer normalization. Advances in Neural Information Processing Systems, 32, 2019

    2019

  65. [73]

    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:15511– 15521, 2020

    2020

  66. [74]

    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

    2020

  67. [75]

    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

    2020

  68. [76]

    Mgda converges under generalized smoothness, provably

    Qi Zhang, Peiyao Xiao, Shaofeng Zou, and Kaiyi Ji. Mgda converges under generalized smoothness, provably. arXiv preprint arXiv:2405.19440, 2024

    2024 arXiv

  69. [77]

    Convergence guarantees for rmsprop and adam in generalized-smooth non-convex optimization with affine noise variance

    Qi Zhang, Yi Zhou, and Shaofeng Zou. Convergence guarantees for rmsprop and adam in generalized-smooth non-convex optimization with affine noise variance. arXiv preprint arXiv:2404.01436, 2024

    2024 arXiv

  70. [78]

    Decon- structing what makes a good optimizer for language models

    Rosie Zhao, Depen Morwani, David Brandfonbrener, Nikhil Vyas, and Sham Kakade. Decon- structing what makes a good optimizer for language models. arXiv preprint arXiv:2407.07972, 2024

    2024 arXiv

  71. [79]

    On the convergence and improvement of stochastic normalized gradient descent

    Shen-Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64:1–13, 2021. 14 A Proofs A.1 (L0, L1)-smoothness Standard L-smoothness assumes that the gradient of a function is glob...

    2021

  72. [80]

    1 + ∥⃗ σ∥1 ε κ κ−1 #! , Optimal tuning for ε ≤ 8L0 L1 √ d : T = O ∆Lδ 0d ε2 , γk ≡ q ∆ 20Lδ 0dT , Bk ≡ 16∥⃗ σ∥1 ε κ κ−1 : N = O ∆Lδ 0d ε2

    (9) A.2 Technical lemmas and propositions We use the following facts from the linear algebra and convex analysis [8]: Proposition 1 (Norm Relation). For two normsℓp and ℓq with 1 ≤ p ≤ q ≤ 2, the following relation holds true: ∥x∥q ≤ ∥x∥p ≤ d 1 p − 1 q ∥x∥q, ∀x ∈ Rd. (10) Prop...

  73. [256]

    We trained the model for 100k steps

    We used a T5 tokenizer, since it was also trained on C4 with dictionary size equal to 32k. We trained the model for 100k steps. For all experiments, while the main model parameters use the respective optimization method, the LM head layer is optimized with AdamW [49]. This fol...

Pith tools

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