Heavy-Tailed Stochastic Optimization

Ask about this topic

Overview

The field studies how to optimize noisy objectives when gradient estimates can contain rare, very large shocks, often with finite moments but infinite variance. Common approaches include clipping or normalizing gradients, robust minibatch estimators, adaptive methods, and mirror descent; complementary analyses ask when ordinary SGD and momentum work without modifying their updates. Results cover convex and nonconvex problems as well as constrained, distributed, and Markovian settings, with guarantees for expected convergence, high-probability error, and last iterates. A central tension is that clipping can control outliers and improve guarantees but also introduce bias, while unclipped or adaptive methods may converge more slowly or require stronger assumptions.

Latest papers

CardsList

37 papers7 papers in the last four weeks, up 17% on the four weeks before. 0.0% of all new papers.

  1. The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

    Oct 24, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaLast-Iterate ConvergenceConvergence Analysis

    Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China

  2. Weak-LαL^α Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

    Oct 20, 2026Alyona Nekrasova, Makar Sidorov, Savelii Chezhegov +4Gradient ClippingHeavy-Tailed Stochastic Optimization

    Independent researcher · Yaroslavl State University · Moscow Independent Research Institute of Artificial Intelligence +2

  3. On the Last-Iterate Convergence of Clipped Gradient Methods

    Oct 14, 2026Zijian LiuLast-Iterate ConvergenceGradient Clipping

    New York University

  4. Last-Iterate Convergence of Clipped SGD with Linear Decay

    Oct 13, 2026Wei Jiang, Haomin Bai, Zechao LiLast-Iterate ConvergenceStochastic Gradient Descent

    School of Computer Science and Engineering, Nanjing University of Science and Technology · National Key Laboratory for Novel Software Technology, Nanjing University

  5. Strong Gaussian Approximation of Constant Learning Rate SGD: Bias and Trajectory Inference

    Oct 10, 2026Joseph Keslin, Wei Biao WuStochastic Gradient DescentHeavy-Tailed Stochastic Optimization

    Department of Statistics, University of Chicago

  6. Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping

    Oct 7, 2026Aleksandar Armacki, Haoyuan Cai, Ali H. SayedDecentralized OptimizationStochastic Gradient Descent

    Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

  7. Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

    Sep 30, 2026Vaneet AggarwalOnline Convex OptimizationDynamic Regret Minimization

    Purdue University, West Lafayette, IN, USA

  8. Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise

    Sep 26, 2026Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5Polyak-Ruppert AveragingStochastic Optimization

    Independent Researcher · HSE University · MBZUAI +3

  9. High-Probability Guarantees for SGD under ββ-Heavy-Tailed Gradient Noise

    Sep 26, 2026Qijun Tong, Masahiro Ikeda, Ryota KawasumiStochastic Gradient DescentStochastic Optimization Convergence

    The University of Electro-Communications · The University of Osaka · Gunma University

  10. TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

    Sep 25, 2026Haoxuan Wang, Yuchen Fang, Sen NaStochastic OptimizationStochastic Optimization Convergence

    School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Mathematics, University of California, Berkeley

  11. Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

    Sep 24, 2026Wei Biao WuNonconvex Stochastic OptimizationStochastic Optimization Convergence

  12. Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness

    Sep 11, 2026Misbah Uz Zaman, Anirbit MukherjeeGradient ClippingNonconvex Stochastic Optimization

    Department of Mathematics and Statistics Indian Institute of Science Education and Research Kolkata · Department of Computer Science The University of Manchester

  13. The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization

    Sep 5, 2026Tianxi Zhu, Yi Xu, Xiangyang JiMin-Max OptimizationStochastic Optimization Convergence

    School of Control Science and Engineering, Dalian University of Technology · Department of Automation, Tsinghua University

  14. Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness

    Aug 12, 2026Alokendu Mazumder, Ayaan Mohd, Harshit Rawat +3Stochastic Optimization ConvergenceAdaptive Gradient Methods

    Robert Bosch Center for Cyber Physical Systems, IISc Bengaluru · Undergraduate Program, IISc Bengaluru · Department of Computational Data Sciences, IISc Bengaluru +4

  15. The Convergence Behavior of Adam under Heavy-Tailed Noise

    Jul 29, 2026Yijiang PangNonconvex Stochastic OptimizationHeavy-Tailed Noise

    Michigan State University, East Lansing, USA

  16. Parameter-Free Dynamic Regret under Heavy-Tailed Noise

    Jul 29, 2026Vaneet AggarwalOnline Convex OptimizationDynamic Regret Minimization

    Purdue University

  17. Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

    Jul 28, 2026Bin Luo, Chengchang Liu, Jonathan Allcock +2Nonconvex Stochastic OptimizationHeavy-Tailed Noise

    The Chinese University of Hong Kong · Westlake University · Tencent Quantum Laboratory

  18. Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

    Jul 9, 2026Ryusei Yamada, Naoki Sato, Hideaki IidukaHeavy-Tailed NoiseStochastic Optimization Convergence

    Meiji University, Japan

  19. High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence

    Jun 24, 2026Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet AggarwalStochastic OptimizationOptimization Convergence Analysis

    Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University

  20. Is Variational Monte Carlo Robust? Sharp Moment Thresholds and Heavy-tailed Stochastic Optimization

    Jun 24, 2026Philipp Grohs, Davide NobileStochastic OptimizationVariational Monte Carlo

    Faculty of Mathematics, University of Vienna · RICAM, Austrian Academy of Sciences

  21. Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?

    Jun 22, 2026Dingzhi Yu, Hongyi Tao, Yuanyu Wan +2Stochastic OptimizationHeavy-Tailed Noise

    1Nanjing University · 2Zhejiang University · 3Fudan University

  22. Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

    Jun 21, 2026Shengchao Zhao, Yongchao LiuStochastic OptimizationNonconvex Stochastic Optimization

    School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China

  23. Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation

    Jun 21, 2026Zhiyu Li, Xi Xuan, Davide CarboneStochastic OptimizationStochastic Approximation

    University of Science and Technology of China Hefei, China · City University of Hong Kong Hong Kong SAR, China · Laboratoire de Physique de l’École Normale Supérieure, Université PSL, CNRS, Sorbonne Université, Université de Paris Paris, France

  24. Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success

    Jun 12, 2026Florian Hübler, Thomas Pethick, Suvrit SraStochastic OptimizationNonconvex Stochastic Optimization

    Department of Computer Science, ETH Zurich, Switzerland · Department of Mathematics, Technical University of Munich, Germany · Munich Center for Machine Learning (MCML)

  25. Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time

    Jun 2, 2026Pierre-Louis Cauvin, Panayotis MertikopoulosStochastic OptimizationStochastic Differential Equations

    Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

  26. In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

    May 30, 2026Zijian LiuStochastic OptimizationNonconvex Stochastic Optimization

    Stern School of Business, New York University

  27. Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

    May 23, 2026Zhuanghua Liu, Luo LuoStochastic OptimizationGradient Clipping

  28. Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

    May 18, 2026Zijian LiuStochastic OptimizationNonconvex Stochastic Optimization

    Stern School of Business, New York University

  29. Tight Complexity of Muon under Heavy-Tailed Noise

    May 18, 2026Jiayu Zhang, Tianyi LinStochastic OptimizationNeural Network Optimization

    Department of Industrial Engineering and Operations Research, Columbia University

  30. Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameters

    May 12, 2026Alexander Yukhimchuk, Mladen Kolar, Martin Takáč +1Stochastic OptimizationGradient Clipping

    MBZUAI · University of Southern California