Towards Weaker Variance Assumptions for Stochastic Optimization

arXiv:2504.09951 · math.OC, cs.LG, stat.ML · Submitted 2025-04-14 · Read on arXiv

math.OC, cs.LG, stat.ML

Submitted: 2025-04-14

Updated: 2026-09-26

Terminology

• Generalization — 4× in this paper · explained in 13 episodes
• Regret — 3× in this paper · explained in 3 episodes
• Regularization — 3× in this paper · explained in 3 episodes
• Convergence Guarantees — 2× in this paper · explained in 3 episodes
• Adaptation — 1× in this paper · explained in 1 episode
• Adaptivity — 1× in this paper · explained in 1 episode
• Hilbert Space — 1× in this paper · explained in 2 episodes
• Non-asymptotic Analysis — 1× in this paper · explained in 2 episodes
• Quantization — 1× in this paper · explained in 12 episodes

Sources

• Handbook of Convergence Theorems for (Stochastic) Gradient Methods
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
• Accelerated stochastic approximation with state-dependent noise
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications
• Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails
• Accelerated Minimax Algorithms Flock Together
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
• Petrov-Galerkin operator inference with application to stability-encouraging identification