Research map / Optimization / Nonconvex and smooth optimization
Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
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.
Establishes sample-complexity lower bounds for second-order stochastic optimization under p-th-moment (p-BCM) heavy-tailed gradient and Hessian noise, proposes NSGD-Hess-style momentum methods with Hessian-vector clipping, and proves high-probability convergence nearly matching the bounds.
Problem
Second-order stochastic nonconvex optimization is fragile under heavy-tailed noise with only bounded p-th central moments (p in (1,2]) for gradients and Hessians, and lacks sample complexity limits and high-probability guarantees.
Approach
Combine normalized SGD with Hessian-corrected momentum (evaluating the Hessian-vector product at a random interpolation point with a fresh sample), and add clipping of both gradients and Hessian-vector products (Hessian clipping) to obtain high-probability guarantees under p-BCM noise; also derive zero-chain lower bounds for q-th order oracles under p-BCM.
Key results
- Lower bound Omega(Delta sigma_h/eps^2 (sigma/eps)^{1/(p-1)}) for second-order methods under p-BCM, improving the first-order bound by a factor of 1/eps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Hessian-corrected momentum with normalized updates under p-BCM noise | NSGDHess · Heavy-tailed p-BCM, in expectation | sample complexity: {\cal O}\left(\frac{\Delta (L +\sigma_h)}{\varepsilon^2} + \frac{\Delta (L + \sigma_h)}{\varepsilon^2} \left(\frac{\sigm | Helped |
| Add gradient and Hessian-vector-product clipping (ablation) | NSGDHess · Heavy-tailed p-BCM, high probability | sample complexity: {\cal O}\left(\left(\frac{\sqrt{\Delta_1(L+\sigma_h)}+ \sigma}{\varepsilon}\log \frac{1}{\delta\varepsilon}\right)^{\fra | Helped |
| Use Hessian-vector-product clipping rather than leaving the Hessian-vector product unclipped (ablation) | Clip NSGDHess · Heavy-tailed p-BCM, high-probability convergence | availability of high-probability guarantee | Helped |
| Remove the initial gradient-estimation batch (ablation) | NSGDHess · Heavy-tailed p-BCM, in expectation | sample complexity | Hurt |
Surprising findings
- Algorithms without clipping (NSGDM, NSGDHess) suffer significantly from heavy-tailed noise in the synthetic experiment.
- Clipping the full Hessian by operator norm breaks the unbiasedness property needed for analysis, motivating clipping of Hessian-vector products instead.
Limitations
- Requires tuning three extra clipping/step parameters, and high-probability bounds hold for a fixed delta rather than uniformly.
- Upper bound does not exactly match the lower bound in all parameters (Delta, L, sigma, sigma_h dependence).
- Experiments limited to a synthetic quadratic with Pareto noise; results are primarily theoretical.
Experimental setup
Metrics: sample complexity expected gradient norm high-probability gradient norm bound
Baselines: SGDHess SCN SGD with HVP-RVR NSGDM NIGT with clipping Clip-SGD
Builds on: NSGDHess NSGDM NIGT with clipping SHARP zero-chain lower bound framework
Closest papers by meaning
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.92)
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.91)
- Emergence of heavy tails in homogenized stochastic gradient descent (NeurIPS 2024 · similarity 0.89)
- Efficient Distributed Optimization under Heavy-Tailed Noise (ICML 2025 · similarity 0.89)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.89)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · similarity 0.89)
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.