Research map / Optimization / Nonconvex and smooth optimization
Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that normalized SGD with momentum (Batched NSGDM) converges at the optimal rate under heavy-tailed noise without gradient clipping, and also achieves O(T^{(1-p)/(2p)}) when the tail index p is unknown.
Problem
Nonconvex stochastic optimization when stochastic gradient noise has only a finite p-th moment (p in (1,2]), where prior methods rely on gradient clipping and require knowing the tail index p.
Approach
Revisits Batched normalized SGD with momentum and shows, via a new expected inequality for vector martingale difference sequences (derived from AdaGrad regret analysis), that gradient normalization alone attains the optimal heavy-tailed rate without clipping; setting parameters as if p=2 yields convergence without knowing p.
Key results
- Batched NSGDM achieves O(T^{(1-p)/(3p-2)}) expected gradient-norm rate under heavy-tailed noise without clipping, matching a newly refined lower bound in T, sigma0, Delta1, L0.
- Without knowing p, Batched NSGDM with parameters set as if p=2 attains O(T^{(1-p)/(2p)}), the first such rate.
- Under (L0,L1)-smoothness with known p, the rate reduces to O(Delta1 L1/T + sqrt(Delta1 L0/T)) in the noiseless case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use gradient normalization without gradient clipping | Batched NSGDM · Heavy-tailed noises with known tail index | average gradient norm convergence rate: \mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}}) | Helped |
| Set the stepsize and momentum as if the tail index were 2, without knowing its value | Batched NSGDM · Heavy-tailed noises with unknown tail index | average gradient norm convergence rate: \mathcal{O}(T^{\frac{1-\mathfrak{p}}{2\mathfrak{p}}}) | Helped |
Surprising findings
- A vector martingale inequality E||sum v_t|| <= 2sqrt2 E[(sum ||v_t||^p)^{1/p}] for any p in [1,2] is proved via AdaGrad regret analysis, and it is adaptive to p.
Limitations
- Unknown-p rate O(T^{(1-p)/(2p)}) is suboptimal compared with the known-p optimal rate.
- Dependence on L1 in step size unless T is large; with sigma1>0 batch size may need to depend on p.
- Batched NSGDM is not the commonly used adaptive methods like Adam.
Experimental setup
Metrics: expected gradient norm convergence rate
Baselines: Clipped SGD SGD Batched SGDM
Builds on: Clipped SGD NSGDM AdaGrad (L0,L1)-smoothness Batched NSGDM
Closest papers by meaning
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.91)
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.91)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · similarity 0.91)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.89)
- Efficient Distributed Optimization under Heavy-Tailed Noise (ICML 2025 · similarity 0.88)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.