Research map / Optimization / Distributed and compressed
High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
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.
Proposes clipping of stochastic gradient differences (shifted clipping) for proximal and distributed methods under heavy-tailed noise, giving high-probability convergence rates (including accelerated and linear-speedup) for composite/distributed minimization and variational inequalities.
Problem
High-probability convergence of stochastic composite and distributed optimization and variational inequalities under heavy-tailed noise (bounded central alpha-th moment); naive clipping breaks the fixed-point property of proximal methods and prevents linear/accelerated rates.
Approach
Clip the difference between stochastic gradients and adaptively updated shifts (instead of clipping raw stochastic gradients), allowing decreasing clipping levels so the clipped bias vanishes; extend to distributed workers (clip locally, then average) and to acceleration (SSTM) and VIs (SGDA, SEG).
Key results
- DProx-clipped-SSTM-shift achieves accelerated high-probability complexity max{sqrt(LR^2/eps), (1/n)(sigma R/eps)^{alpha/(alpha-1)}} per worker, the first accelerated high-probability rate under bounded central alpha-th moment for composite/distributed problems.
- DProx-clipped-SGD-shift gives linear speed-up in the noise-dependent term (1/n factor) under heavy-tailed noise, which naive distributed clipping cannot achieve in the alpha<2 case.
- Theoretical results match known single-node rates for unconstrained clipped-SGD and recover Clipped-SMD rates up to log factors, without requiring grad f(x*)=0 for acceleration.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use shifts and clip stochastic gradient differences rather than clipping stochastic gradients directly | Composite minimization methods · Composite and distributed optimization with heavy-tailed noise | high-probability convergence | Helped |
| Add acceleration with Similar Triangles updates | DProx-clipped-SGD-shift · Composite distributed convex minimization | stochastic oracle calls per worker: \sqrt{\frac{LR^2}{\varepsilon}} versus \frac{LR^2}{\varepsilon} | Helped |
| Use distributed workers with local clipping and averaging | DProx-clipped-SGD-shift · Composite distributed minimization with heavy-tailed noise | noise-dependent stochastic oracle calls per worker: 1/n | Helped |
| Use distributed workers with local clipping and averaging | DProx-clipped-SEG-shift · Composite distributed variational inequalities | noise-dependent stochastic oracle calls per worker: 1/n | Helped |
| Increase the clipping level by a factor of n in the distributed method | Distributed clipped methods · Distributed heavy-tailed optimization | noise-dependent complexity: 1/n | Helped |
| Naively clip the full gradient in proximal gradient descent | Prox-GD · Composite minimization, even without stochastic noise | convergence to the exact solution | Hurt |
| Remove shifts from the strongly convex distributed method | DProx-clipped-SGD-shift · Distributed minimization | fixed-point convergence | Hurt |
Surprising findings
- Naive clipping of proximal gradient descent loses the fixed-point property when clipping level is below ||grad f(x*)||, forcing sublinear convergence even without noise.
- In the distributed alpha<2 case, applying existing aggregated-noise bounds introduces a dimension-dependent factor, making clipping after averaging inferior to clipping on workers.
Limitations
- Step size and clipping level depend on an upper bound R on ||x0-x*|| (not parameter-free).
- Logarithmic factors are not optimized and are worse than some prior single-node results.
- Results assume assumptions hold on a bounded ball around the solution, with high-probability induction.
Experimental setup
Metrics: oracle complexity for high-probability convergence (iteratio
Baselines: clipped-SGD clipped-SSTM Clipped-SMD Clipped-ASMD clipped-SEG clipped-SGDA
Builds on: clipped-SGD clipped-SSTM Clipped-SMD DIANA-style shifts Bernstein inequality for martingale differences
Closest papers by meaning
- Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping (NeurIPS 2020 · similarity 0.93)
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.91)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.89)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.89)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.89)
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · 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.