Research map / Optimization / Distributed and compressed
Efficient Distributed Optimization under 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 TailOPT, a nested distributed-optimization framework with clipping (L2 or coordinate-wise BiClip) at inner and outer steps for heavy-tailed gradient noise, with convergence guarantees under infinite variance and an SGD-memory instantiation Bi^2Clip.
Problem
Distributed training with local updates (nested inner/outer optimization) suffers from heavy-tailed stochastic gradient noise, especially in attention-based models, where existing methods lack convergence guarantees or add heavy memory/communication overhead from preconditioners.
Approach
Coordinate-wise clipping from both above and below (BiClip) at both inner and outer optimizers mimics Adam-like per-coordinate amplification of small gradient coordinates without storing or transmitting any preconditioner, and comes with convergence proofs under bounded alpha-moment noise with local updates.
Key results
- Bi^2Clip achieves an average GLUE score of 84.52, above DiLoCo (83.08) and Adam^2 (82.93) in the reported table.
- On WMT TED en-de, Bi^2Clip reaches 29.41 BLEU / 59.18 METEOR versus 28.06 BLEU for Adam^2.
- Convergence theory covers RMSProp-TailClip and Bi^2Clip with rate O(T^{-(alpha-1)/(4alpha-2)}) under only a finite alpha-moment (alpha in (1,2)) with local updates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BiClip in both the inner and outer optimizers instead of DiLoCo | distributed RoBERTa training · GLUE | average: 83.08 -> 84.52 | Helped |
| Use BiClip in both the inner and outer optimizers instead of Adam in both | distributed RoBERTa training · GLUE | average: 82.93 -> 84.52 | Helped |
| Use BiClip in both the inner and outer optimizers instead of Avg-L₂Clip | T5 translation training · WMT translation (TED en-de and NewsComm en-fr) | average: 43.92 -> 44.51 | Helped |
| Use BiClip in both the inner and outer optimizers instead of Adam in both | T5 translation training · WMT translation (TED en-de and NewsComm en-fr) | average: 43.23 -> 44.51 | Helped |
| Replace Avg-SGD with Avg-L₂Clip | T5 translation training · WMT translation (TED en-de and NewsComm en-fr) | average: 42.68 -> 43.92 | Helped |
Surprising findings
- Plain averaged SGD and L2 clipping fail to learn CoLA (0.0 accuracy) on GLUE, showing SGD-based inner optimizers perform far worse than adaptive ones.
- Bi^2Clip, which keeps only SGD-level memory, outperforms Adam-based Adam^2 on several GLUE tasks and on translation.
Limitations
- Convergence bounds are loose; the authors note empirical performance exceeds what the theory suggests.
- Clipping thresholds u_t and d_t must be tuned by sweeping a hyperparameter grid, with no automatic selection rule.
- Theory requires increasing upper clipping and decreasing lower clipping schedules, and the experiments fix nu=zeta=gamma=0, departing from the analysis.
Experimental setup
Datasets: GLUE WMT (TED Talks, News Commentary) SQuAD CIFAR100 ImageNet (ViT pretraining) synthetic heavy-tailed linear regression data
Benchmarks: GLUE WMT TED/News Commentary (BLEU/METEOR) SQuAD CIFAR100 synthetic heavy-tailed regression
Metrics: accuracy F1 Matthews correlation Pearson/Spearman BLEU METEOR
Baselines: Avg-SGD Avg-L2Clip Adam^2 DiLoCo Adagrad-SGD RMSProp-SGD Adam-SGD
Builds on: DiLoCo Adam Adagrad RMSProp clipped SGD
Closest papers by meaning
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.89)
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.88)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · similarity 0.88)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.87)
- Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
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.