Stochastic Optimization Convergence

Follow this topic Ask about this topic

Momentum

21 papers in the last four weeks, against 2 the four weeks before. 0.2% of all new papers.

Jul 13Week of Sep 28

Latest papers 141

Jun 21, 2026math.OC

Adam Converges in Nonsmooth Nonconvex Optimization

Adam is one of the most widely implemented and influential modern optimizers. Why is it effective across different optimization problems in practice? This question arguably lies at the center of the optimization community over the last decade and has motivated a substantial body of work aimed at understanding its convergence behavior. However, existing studies have mainly focused on the convergence rate of Adam in smooth nonconvex optimization, which unfortunately does not adequately capture practical settings, since many real-world problems are nonsmooth, such as those arising in training neural networks. Thus, these studies cannot fully explain the popularity and empirical success of Adam. Recently, an insightful and powerful framework called Online-to-Nonconvex Conversion has opened a new way to analyze Adam for nonsmooth nonconvex optimization. Unfortunately, prior works along this line share two common limitations. First, all of them ignore the important bias-correction term in the original Adam algorithm. Second and more importantly, many of them require extra operations that are not used in Adam, such as a clipping step. Therefore, the convergence guarantee for the original Adam method still remains unclear. In this work, we present the first finite-time analysis for the classical form of Adam, i.e., with the bias-correction step and without further algorithmic modifications, and prove that a randomly scaled learning rate ensures a convergence rate of

1/T^{\frac{2}{13}}

for nonsmooth nonconvex optimization. Moreover, our result provably applies to the modern heavy-tailed noise regime, which is closer to practice. Interestingly, our theory is established under the parameter choice

β_1=β_2

, aligning with the recent empirical studies.

Zijian Liu

Department of Technology, Operations, and Statistics Leonard N. Stern School of Business New York University New York, NY 10012, USA

Heavy-Tailed Noise Nonconvex Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Nonsmooth Convex Optimization

Jun 19, 2026math.OC

Accelerated and Stable Convergence with Anchored Optimistic Method

We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate

O(1/k^2)

on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of

O(1/\sqrt{k})

on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz variational inequalities in the unconstrained setting without variance reduction or growing batches.

Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2

Universit´e de Montr´eal · Mila - Quebec AI Institute · CIFAR AI Chair +1

Last-Iterate Convergence Gradient Descent Min-Max Optimization Stochastic Optimization Convergence

Jun 19, 2026math.PR

Central limit theorem for the averaged Adam optimizer

In this article, we analyse convergence of the averaged Adam optimizer to an attracting zero of the Adam vector field. We provide a central limit theorem that, in particular, quantifies exactly the speed of convergence. The order of convergence is

n^{-1/2}

in the number of steps of the algorithm which coincides with the order observed for classical stochastic approximation algorithms. The covariance in the central limit theorem is given in terms of properties of the Adam algorithm in the state of the attractor.

Steffen Dereich, Arnulf Jentzen

Institute for Mathematical Stochastics, University of Münster, Germany · School of Data Science and School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China · Applied Mathematics: Institute for Analysis and Numerics, University of Münster, Germany

Stochastic Approximation Stochastic Optimization Convergence Adaptive Gradient Methods

Jun 17, 2026cs.LG

Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods

Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor

\sqrtκ

larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.

Depen Morwani, Alexandru Meterez, Pranav Nair +1

1Harvard University · 2Kempner Institute at Harvard University · †: Work done while at Harvard.

Stochastic Optimization Momentum Methods Stochastic Optimization Convergence Accelerated Gradient Methods Stochastic Gradient Descent

Jun 16, 2026cs.LG

MGUP: A Momentum-Gradient Alignment Update Policy for Stochastic Optimization

Efficient optimization is essential for training large language models. Although intra-layer selective updates have been explored, a general mechanism that enables fine-grained control while ensuring convergence guarantees is still lacking. To bridge this gap, we propose \textbf{MGUP}, a novel mechanism for selective updates. \textbf{MGUP} augments standard momentum-based optimizers by applying larger step-sizes to a selected fixed proportion of parameters in each iteration, while applying smaller, non-zero step-sizes to the rest. As a nearly {plug-and-play} module, \textbf{MGUP} seamlessly integrates with optimizers such as AdamW, Lion, and Muon. This yields powerful variants such as \textbf{MGUP-AdamW}, \textbf{MGUP-Lion}, and \textbf{MGUP-Muon}. Under standard assumptions, we provide theoretical convergence guarantees for \textbf{MGUP-AdamW} (without weight decay) in stochastic optimization. Extensive experiments across diverse tasks, including MAE pretraining, LLM pretraining, and downstream fine-tuning, demonstrate that our \textbf{MGUP}-enhanced optimizers achieve superior or more stable performance compared to their original base optimizers. We offer a principled, versatile, and theoretically grounded strategy for efficient intra-layer selective updates, accelerating and stabilizing the training of large-scale models. The code is publicly available at https://github.com/MaeChd/MGUP.

Da Chang, Ganzhao Yuan

Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences · Pengcheng Laboratory · University of Chinese Academy of Sciences +1

Neural Network Optimization Stochastic Optimization Convergence

Jun 14, 2026cs.LG

SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums

Empirical risk minimization on massive datasets naturally exhibits a nested double finite-sum structure, where

N=nm

total samples are logically or physically partitioned into

n

blocks of size

m

(e.g., in pooled data silos, out-of-core learning, or deliberate stratification). While variance-reduced methods achieve optimal oracle complexities for nonconvex objectives, they suffer from severe scaling bottlenecks in this centralized regime. Recursive estimators, such as PAGE, require periodic global full-gradient refreshes over all

nm

samples, which are computationally expensive. Conversely, single-loop methods, such as SILVER, avoid such refreshes but require an impractical

\mathcal{O}(nm)

memory footprint to store a control variate for every sample. In this paper, we propose SILAGE, a variance-reduced algorithm that addresses this trade-off. By actively exploiting the double-sum structure, SILAGE eliminates periodic global full-gradient refreshes over all

nm

components (evaluating at most one local group gradient per iteration) while requiring only

\mathcal{O}(n)

memory. Furthermore, we provide a tight convergence analysis that avoids pessimistic worst-case Lipschitz constants. Instead, SILAGE's complexity natively adapts to the underlying data geometry via nested functional similarities: across-group (

δ_1

) and within-group (

δ_2

) heterogeneity. Our results improve existing state-of-the-art bounds in several practically relevant regimes.

Igor Sokolov, Laurent Condat, Peter Richtárik

*Center of Excellence for Generative AI, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia. · KAUST

Memory-Efficient Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Variance Reduction

Jun 14, 2026math.OC

Schattor: Schatten-family methods for deep learning optimization

Modern deep learning optimization features heterogeneous parameter structures, noisy gradients, and highly nonconvex landscapes, posing significant challenges for both algorithm design and theoretical analysis. Motivated by the limitations of SGD and the success of adaptive optimizers, we propose {\it Schattor}, a family of adaptive first-order methods based on Schatten norms. Schattor unifies SGD and the recently proposed matrix-variate adaptive optimizer Muon within a single Schatten-norm-based framework. We establish dimension-free stationarity guarantees for methods in the Schattor family for stochastic matrix optimization problems via a novel matrix martingale moment bound. We also develop multi-block extensions that adaptively balance block-wise optimization progress and prove dimension-free stationarity guarantees in this more general setting.

Bohao Ma, Junyu Zhang, Chuan He

School of Data Science, The Chinese University of Hong Kong (Shenzhen), Shenzhen, Guangdong, China · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore · Department of Mathematics, Linköping University, Sweden

Deep Learning Optimization Stochastic Optimization Convergence Matrix Optimization Adaptive Gradient Methods

Jun 13, 2026cs.LG

When to use what Schatten- $p$ norm in deep learning?

Schatten-

\infty

based optimizers such as Muon have shown promising empirical performance, but there remains seemingly conflicting observations regarding whether they are beneficial. We resolve this conflict by showing that the conclusion is regime dependent. Even when the objective is smooth in the Schatten-

\infty

geometry, smaller Schatten-

p

geometries can be optimal, specifically in the low-dimensional regime, which we show includes Chinchilla scaling. This conclusion follows from a new noise-robust acceleration result for the SODA framework for

p>2

. The same analysis explains why Muon-like methods do not require warmup, why they naturally favor large batches, and yields a batch size scaling rule for arbitrary

p

.

Thomas Pethick

Deep Learning Optimization Muon Optimizer Nonconvex Optimization Stochastic Optimization Convergence Accelerated Gradient Methods

Jun 12, 2026math.OC

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

Non-Euclidean optimisation methods with matrix-valued updates, such as Muon and Scion, have recently shown strong empirical performance for training Transformer models, yet their theoretical advantages over Euclidean methods remain poorly understood. We address this gap in the heavy-tailed non-convex regime, where stochastic gradients have bounded

p

-th central moments,

p \in (1,2]

. We show that certain non-Euclidean methods achieve optimal sample complexity under stronger stationarity measures, while Euclidean methods incur additional dimension-dependent costs. As a consequence, for

m \times n

matrices, Muon finds an

\varepsilon

-stationary point in nuclear norm within

\mathcal{O}\left(\min\{m, n\} \frac{Δ_1 L}{\varepsilon^2} \left(\frac σ\varepsilon \right)^{\frac p {p-1}}\right)

samples, absorbing heavy-tailed noise without extra dimension dependence, unlike Euclidean methods. We further prove this sample complexity, including its dimension dependence, is optimal for all first-order methods under nuclear-norm stationarity. Experiments on large language models support our theory. Surprisingly, our results suggest that other Schatten geometries beyond the spectral geometry of Muon can perform competitively in certain settings.

Florian Hübler, Thomas Pethick, Suvrit Sra

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

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Muon Optimizer Stochastic Optimization Convergence Matrix Optimization+1

Jun 11, 2026cs.LG

Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers

In modern machine learning, parallelization of training is an important strategy for increasing scale. Asynchronous stochastic gradient descent (ASGD), which maximizes the utilization of available hardware by avoiding waiting for slow workers. However, with constant step sizes, the convergence of ASGD is nonetheless affected negatively by slow workers due to large delays in updates. At the same time, it has been empirically observed in asynchronous training of deep learning models that gradient clipping "stabilizes" training. In this work, we provide a theoretical justification for this behavior, as we show that clipping removes the dependence of the maximum delay in the oracle complexity. We employ a sub-Weibull model of gradient noise which generalizes sub-Gaussian and sub-exponential distributions to more heavy-tailed distributions, motivated by empirical observations in deep learning. We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.

Samuel Erickson, Mikael Johansson

School of EECS, KTH Royal Institute of Technology, Stockholm, Sweden.

Gradient Clipping Stochastic Optimization Convergence Distributed Training Federated Learning Stochastic Gradient Descent

Jun 7, 2026math.OC

OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimality

Orthogonalized momentum updates, as used in Muon-style optimizers, have recently shown strong empirical stability in large-scale deep learning. However, most current orthogonalized methods are still paired with fixed, externally scheduled, or otherwise open-loop magnitude rules, so their scale is not directly calibrated from the realized optimization trajectory. Motivated by the closed-loop perspective behind Lipschitz-free and noise-adaptive methods, we propose OptMuon, a family of adaptive momentum orthogonalization methods for stochastic nonconvex optimization. OptMuon combines Muon-style polar-factor directions with a trajectory-dependent AdaGrad-Norm-type coefficient schedule, so that the update magnitude is determined by the observed gradient and momentum history rather than by a prescribed Lipschitz-dependent rule. The schedule does not use the smoothness constant, the variance level, or the bounded-gradient constant in parameter selection, and its running-maximum correction prevents isolated gradient spikes from causing excessive coefficient collapse. Under lower-boundedness, unbiased stochastic gradients with bounded variance, smoothness, and an almost-sure bounded stochastic-gradient condition, we prove two complementary expected-stationarity guarantees. OptMuon-A achieves the noise-adaptive rate

\tilde{\mathcal O}(T^{-1/2}+σ^{1/2}T^{-1/4})

under average smoothness, while OptMuon-I achieves

\tilde{\mathcal O}(T^{-1/2}+σ^{1/3}T^{-1/3})

under individual smoothness. In the zero-noise regime, both bounds automatically reduce to a nearly optimal deterministic first-order rate

\tilde{\mathcal O}(T^{-1/2})

without manual hyperparameter retuning. These results show that closed-loop scalar adaptation can be combined with Muon-style momentum orthogonalization while retaining noise adaptivity and zero-noise optimality up to logarithmic factors.

Ganzhao Yuan

Faculty of Computer Science and Artificial Intelligence Shenzhen University of Advanced Technology (SUAT), China

Momentum Methods Nonconvex Stochastic Optimization Muon Optimizer Stochastic Optimization Convergence Adaptive Gradient Methods

Jun 3, 2026math.OC

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

We study decentralized stochastic smooth convex optimization, where

M

workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of

N

gradient samples while still preserving the centralized

O(1/\sqrt N)

statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to

\smash{M\lesssim \sqrtρ\,N^{3/4}}

workers, where

ρ

is the spectral gap of the gossip network, improving the best prior maximal scaling of

\smash{M\lesssim ρ\sqrt N}

. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.

Nitai Kluger, Amit Attia, Tomer Koren

Blavatnik School of Computer Science, Tel Aviv University · Google Research Tel Aviv

Stochastic Optimization Convergence Accelerated Gradient Methods Decentralized Optimization

Jun 3, 2026stat.ML

Deterministic Envelopes for Tamed SGLD: Decoupling Stochastic Gradient Noise and Localizing Taming

Stochastic gradient Langevin algorithms often use tamed denominators to stabilize superlinear drifts. This paper shows that when the denominator depends on the current stochastic gradient, the transformed update can have a biased conditional mean even if the original stochastic gradient is unbiased. This creates a stationary mean-shift channel that is absent for deterministic denominators.We propose a structure-preserving framework for designing tamed denominators. The construction keeps the denominator deterministic given the current state, and uses localized deterministic envelopes to avoid unnecessary taming in typical regions. These kernels retain the stabilizing effect of taming while avoiding the bias introduced by a gradient-dependent denominator. Our theory bounds the stationary bias through Euler, envelope, and stochastic-gradient residuals. The analysis also shows why purely local taming rules can lose control in the far tail and motivates a hybrid construction with additional tail protection. Experiments confirm the stationary distortions of random denominators, the bias reduction of deterministic-envelope designs, and the stabilizing effect of the hybrid construction.

Yiwei Zhou, Ziheng Chen

School of Mathematics and Statistics, Yunnan University, Kunming, Yunnan, 650500, China.

Stochastic Differential Equations Stochastic Gradient Langevin Dynamics Langevin Dynamics Stochastic Optimization Convergence

Jun 2, 2026math.OC

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

We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a stochastic differential equation (SDE) driven by a centered Lévy noise process with finite

p

-th order moments,

1 < p \leq 2

. This scheme -- which we call the Lévy mirror flow (LMF) -- arises naturally as the scaling limit of SMD in the presence of heavy-tailed noise. In particular, when

p < 2

-- the heavy noise regime -- the trajectories of LMF generically exhibit jump discontinuities of arbitrary magnitude which, if frequent enough, lead to infinite variance. Nonetheless, despite this highly singular behavior, we show that LMF attains

ε

-optimality within

\mathcal{O}(ε^{-p/(p-1)})

time in the convex case, and within

\mathcal{\tilde O}(ε^{-1/(p-1)})

time for (relatively) strongly convex objectives. These guarantees provide a transparent characterization of the impact of frequent long jumps on the convergence of the process, and percolate to a series of matching discrete-time guarantees for several variants of SMD under heavy-tailed noise.

Pierre-Louis Cauvin, Panayotis Mertikopoulos

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

Stochastic Optimization Stochastic Differential Equations Heavy-Tailed Noise Mirror Descent Stochastic Optimization Convergence Heavy-Tailed Distributions+1

Jun 1, 2026math.OC

Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Scheduler

Sharpness-Aware Minimization (SAM) has established itself as a powerful and widely adopted optimizer for training machine learning models. By explicitly minimizing the sharpness of the loss landscape, SAM often improves generalization while delivering strong empirical performance. However, SAM and its variants, like most training algorithms, are sensitive to the choice of learning rate, which is typically selected through extensive hyperparameter tuning or predefined schedulers. In this work, motivated by recent advances on the effectiveness of stochastic Polyak step sizes for Stochastic Gradient Descent (SGD), we derive Polyak schedulers tailored to SAM-style updates, yielding novel adaptive algorithms in both deterministic and stochastic settings. In the smooth setting, we prove linear convergence for strongly convex objectives and an

\mathcal{O}(1/T)

convergence rate for convex objectives in the deterministic case. In the stochastic setting, we establish analogous convergence guarantees up to a neighborhood of the optimum. Numerical experiments demonstrate that the proposed Polyak schedulers achieve performance comparable to or better than carefully tuned SAM baselines, while substantially reducing the need for learning-rate tuning.

Dimitris Oikonomou, Nicolas Loizou

Mathematical Institute for Data Science (MINDS), Johns Hopkins University, Baltimore, MD, USA · Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA · Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA

Sharpness-Aware Minimization Learning Rate Scheduling Stochastic Optimization Convergence

Jun 1, 2026cs.AI

Stochastic convergence of parallel asynchronous adaptive first-order methods

A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic factors) of order O(1/sqrt{t}) under reasonable assumptions. Numerical experiments suggest that such asynchronous adaptive algorithms are very relevant in heterogeneous large-scale machine learning systems.

Serge Gratton, Philippe L. Toint

Universit´e de Toulouse, INP, IRIT, Toulouse, France · Universit´e de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

May 30, 2026cs.IT

Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation

Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible. We study a B-bit quantized stochastic first-order oracle: an optimizer interacts for T rounds and receives, each round, a B-bit adaptive public-coin description of its stochastic gradient. Our main contribution is an exact reduction from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation -- under the B-bit oracle the query carries no information, so optimization collapses exactly onto a sequential distributed-estimation problem. This yields two unconditional lower bounds, a communication bound TB = Omega(d) and a statistical bound T = Omega(sigma^2 d / eps^2), and the sharp product-form bound T = Omega((sigma^2 d / eps^2) max{1, d/B}). The product form is also unconditional: a B-bit transcript carries at most O(TB / sigma^2) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information, and combined with the multivariate van Trees inequality this gives the bound directly, without bounded-likelihood-ratio truncation. We give a near-matching achievability result with exact per-round bit accounting under a bounded-dynamic-range oracle, tight up to a logarithmic factor; the lower bound is for truly Gaussian (unbounded) gradients, and closing this oracle gap is left open. A sequential rate-distortion perspective extends the reduction to correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by (1+rho)/(1-rho) rather than relaxing it. The bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems.

Munsik Kim

Stochastic Optimization Stochastic Optimization Convergence Communication Complexity Information-Theoretic Lower Bounds

May 30, 2026math.OC

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

Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite

p

-th moment for

p\in\left(1,2\right)

, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent (

\textsf{SGD}

), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent (

\textsf{SMD}

) and Accelerated Stochastic Mirror Descent (

\textsf{ASMD}

) in convex optimization, and for

\textsf{SGD}

and Stochastic Gradient Descent with Momentum (

\textsf{SGDM}

) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

May 29, 2026cs.LG

Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

Vagul Mahadevan, Claire Chen, Shuze Daniel Liu +1

Metron, Reston, VA, USA · Division Office Physics, Math and Astronomy, California Institute of Technology, Pasadena, CA, USA · Data Science Lab, MIT, Cambridge, MA, USA +2

Stochastic Approximation Temporal-Difference Learning Two-Timescale Stochastic Approximation Stochastic Optimization Convergence

May 28, 2026cs.LG

A Unified Framework for Gradient Aggregation in Multi-Objective Optimization

Many machine learning problems involve multiple inherent trade-offs that are best addressed by gradient-based multi-objective optimization (MOO) algorithms. Existing methods are often proposed with various motivations, analyzed case by case, and differ algorithmically in how the component gradients are aggregated at each step. In this work, we develop a unifying framework for gradient aggregation in MOO, establishing (optimal) rates of convergence to Pareto stationarity, the standard measure of performance in MOO. Central to our analysis is a sufficient alignment condition, from which we derive a theorem showing that non-conflicting directions, when chosen within the convex hull of gradients, form a fundamental sufficient condition for convergence. We further show that feasibility can be ensured through projection onto the dual cone, broadening the scope of methods that admit convergence guarantees. In parallel, we present a primal optimization perspective of gradient aggregation that encompasses established algorithms, clarifies their theoretical relationships, and enables the design of new variants. As an illustration, we introduce capped MGDA, derived from a CVaR-based formulation, and demonstrate its robustness in adversarial federated learning. Finally, we validate our theory through experiments on synthetic problems and practical benchmarks.

Zeou Hu, Kelvin Ho, Yaoliang Yu

1Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada · 3Vector Institute · 2Computer Science, The Chinese University of Hong Kong

Gradient Descent Stochastic Optimization Convergence Multi-Objective Optimization

May 28, 2026cs.LG

Singularity-aware Optimization via Randomized Geometric Probing: Towards Stable Non-smooth Optimization

Deep learning optimization relies heavily on the assumption of smooth loss landscapes, a condition systematically violated by modern architectures due to non-smooth components such as ReLU activations and quantization operators. In such non-smooth regimes, adaptive optimizers such as Adam suffer from gradient chattering, violent oscillations caused by conflicting signals within the Clarke subdifferential, leading to poor convergence and suboptimal generalization. To address this, we introduce Singularity-aware Adam (S-Adam), a novel optimizer that stabilizes training by dynamically modulating step sizes based on local geometric instability. Our key contribution is the Local Geometric Instability (LGI) metric, a computationally efficient estimator of the Clarke subdifferential diameter derived from the variance of randomized directional derivatives. S-Adam incorporates an adaptive damping mechanism exp(-

λ$$ρ

) that decelerates updates in high-instability regions while preserving fast convergence in smooth basins. We provide a rigorous convergence analysis using differential inclusions, proving that S-Adam converges almost surely to (

δ

,

ε

)-Clarke stationary points at the optimal O(1/

\sqrt(T)

) rate. Empirical evaluations on Quantization-Aware Training (QAT) and high-noise small-batch learning demonstrate that S-Adam consistently outperforms AdamW and Prox-SGD, achieving accuracy gains of up to 6 percent on CIFAR-100 and 3 percent on TinyImageNet while effectively mitigating gradient oscillations.

Ruoran Xu, Borong She, Xiaobo Jin +1

Xi’an Jiaotong-Liverpool University

Nonconvex Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

May 28, 2026cs.LG

A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithm

A crucial component of machine learning algorithms is minimizing loss functions with less computational cost and less oscillations. While adaptive learning rate-based optimizers have been widely used for real-world tasks, they do not guarantee convergence, which is why AMSGrad was later introduced to investigate the non-convergence behaviour of Adam. In this paper, popular adaptive optimization methods like Adam and AMSGrad are critically reviewed with an emphasis on their fundamental design concepts. To address limitations of the above mentioned optimizers, a new optimizer variant, C-Adam, is proposed based on the line of sight approach. A theoretical proof for convergence is also provided and the optimizer is validated through a number of real-life based numerical experiments.

Sakshi Kumari, Shyam Kumar M, Sushmitha P

#Department of Mathematics Indian Institute of Technology Patna Bihta 801 106 India · *Department of Mechanical Engineering Indian Institute of Technology Kharagpur2026 Kharagpur IndiaMay 28

Optimization Convergence Analysis Stochastic Optimization Convergence Adaptive Gradient Methods

May 27, 2026cs.LG

Stochastic Gradient Descent with Momentum is Algorithmically Stable

Stochastic gradient descent with momentum (SGDM) is one of the most widely used optimization algorithms in machine learning. While optimization properties of SGDM have been extensively studied in the literature, it remains insufficiently understood whether and when SGDM can generalize well to unseen data. In particular, it has been conjectured that while momentum accelerates training, it may degrade generalization. In this paper, we close this gap by developing a comprehensive generalization analysis of SGDM through the lens of algorithmic stability. More specifically, we introduce a generalized SGDM framework that encompasses both Polyak's and Nesterov's momentum schemes, and establish tight on-average model stability bounds for smooth and convex problems. Notably, the obtained bounds exploit small optimization error bounds along the trajectory, apply to any momentum parameter in the interval

[0, 1)

, and do not require the commonly assumed Lipschitzness of loss functions. We further derive optimization error bounds for the generalized SGDM, and combine them with our generalization analyses to obtain optimal excess population risk bounds for SGDM with both Polyak's and Nesterov's momentum.

Yunwen Lei, Zimeng Wang, Xiaoming Yuan

Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Umeå University, Sweden

Momentum Methods Algorithmic Stability Stochastic Optimization Convergence Accelerated Gradient Methods Stochastic Gradient Descent Generalization Bounds

May 27, 2026cs.LG

Learning Theory of the SVRG: Generalization and Convergence Analysis

Variance reduction (VR) methods employ stochastic gradients with decreasing variance, and they have been widely applied to solve large-scale optimization problems in machine learning because of their efficiency. Existing theoretical studies of VR methods are mainly focused on the convergence analysis, leaving the generalization behavior largely unexplored. In this paper, we bridge this gap by developing the first non-vacuous generalization analysis of the representative VR method: Stochastic Variance Reduced Gradient (SVRG), through the lens of algorithmic stability. In particular, we establish sharp stability bounds of the SVRG in both convex and strongly convex settings by exploiting its algorithmic structure. The obtained bounds are data-dependent, because the training errors are incorporated along the trajectory. Our analysis clarifies the interplay between optimization and generalization, leading to optimal excess population risk bounds in both settings. Our approach differs substantially from existing analyses of stochastic algorithms in the sense that we decompose the SVRG update as an SGD-like step plus a zero-mean correction term and then introduce novel Lyapunov functions to absorb the additional gradient terms induced by the reference points. Our analytical framework can be generalized to other VR methods, and we demonstrate the generalization by the well-known Stochastic Average Gradient Accelerated (SAGA) method.

Yunwen Lei, Zimeng Wang, Xiaoming Yuan

Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Ume˚a University, Sweden

Stochastic Optimization Convergence Variance Reduction Stochastic Gradient Descent Generalization Bounds

May 26, 2026cs.LG

Probabilistic Smoothing with Ratio-Monotone Transforms for Global Optimization

Probabilistic smoothing is a standard tool for global optimization, but existing methods rely on Gaussian kernels and specific transforms, often resulting in strong hyperparameter sensitivity and limited robustness. We propose a general smoothing framework that combines flexible symmetric unimodal kernels with monotonic ratio-based transformations. Under mild conditions, we show that the smoothed objective preserves the global maximizer and that all stationary points concentrate near the true optimum for sufficiently large amplification, without requiring a decreasing smoothing schedule. We further provide explicit complexity bounds for stochastic gradient ascent and show that a leave-one-out baseline provably reduces variance. Experiments on high-dimensional benchmarks and black-box adversarial attacks demonstrate improved robustness and competitive performance.

Kukyoung Jang, Taehyun Cho, Junrui Zhang +2

Department of Statistics, Seoul, Korea University · Department of Electrical and Computer Engineering, Seoul, Seoul National University · Shandong University at Weihai, Weihai, China.

Black-Box Optimization Global Optimization Stochastic Optimization Convergence

May 25, 2026cs.LG

Global Convergence of Wasserstein Policy Gradient for Entropy-Regularized Reinforcement Learning

Wasserstein policy gradient (WPG) is a policy optimization method for reinforcement learning (RL) that exploits the optimal-transport geometry of action distributions. For the entropy-regularized RL objective, WPG evolves each state-conditional policy by transporting it along the action gradient of the soft Q-function together with a Langevin-type diffusion. Despite its appeal for continuous-control problems, its global convergence properties remain poorly understood. Standard Langevin analyses do not directly apply, because the RL objective depends on the policy through the Bellman recursion rather than through a static convex functional, and the Langevin drift is determined by the soft Q-function, whose regularity must be controlled along the policy iterates. In this paper, we develop a global convergence theory for WPG by exploiting the Bellman structure of entropy-regularized RL. We show that the role usually played by convexity can be replaced by a Bellman-based argument: the soft Bellman residual admits a statewise KL representation with respect to a Gibbs policy; Bellman contraction relates this residual to the global optimality gap; and a Bellman resolvent identity connects value improvement to relative Fisher information. Combined with a uniform log-Sobolev inequality (LSI) for the evolving Gibbs family, these ingredients yield a distributional Polyak--Łojasiewicz condition. We further establish the regularity and uniform bounds needed to control the discretization error, thereby obtaining geometric contraction up to a discretization bias. Conceptually, our analysis shows that although entropy-regularized RL is not convex in the usual flat sense, the Bellman recursion induces a favorable Polyak--Lojasiewicz-type (PL) geometry that supports global convergence of WPG.

Zhaoyu Zhu, Rui Gao, Shuang Li

Shanghai Jiao Tong University · The University of Texas at Austin · The Chinese University of Hong Kong, Shenzhen

Optimization Convergence Analysis Wasserstein Gradient Flows Maximum Entropy RL Policy Gradient Methods Stochastic Optimization Convergence

May 21, 2026cs.LG

A note on convergence of Wasserstein policy optimization

Wasserstein Policy Optimization (WPO) is a recently proposed reinforcement learning algorithm that leverages Wasserstein gradient flows to optimize stochastic policies in continuous action spaces. Despite its empirical success, the theoretical convergence properties of WPO in environments with continuous state and action spaces have yet to be fully established. In this note, we argue that WPO within the framework of entropy-regularised Markov Decision Processes converges linearly. This is done by leveraging recent advances in mean-field analysis for convergence of gradient flows using log-Sobole inequalities. Assuming existence of sufficiently regular solution to the gradient flow equation we demonstrate monotonic energy dissipation along the flow and establish a local log-Sobolev inequality. Ultimately, these properties allow us to argue that the value function should converge linearly to the global optimum.

David Šiška, Yufei Zhang

School of Mathematics, University of Edinburgh, United Kingdom · Department of Mathematics, Imperial College London, United Kingdom

Wasserstein Gradient Flows Policy Optimization Maximum Entropy RL Stochastic Optimization Convergence

May 21, 2026cs.LG

An Improved Adaptive PID Optimizer with Enhanced Convergence and Stability for Deep Learning

Optimization is essential in deep learning. The foundational method upon which most optimizers are built is momentum-based stochastic gradient descent. However, it suffers from two key drawbacks. First, it has noisy and varying gradients, and second, it has an overshoot phenomenon. To address noisy gradients, Adam was proposed, which remains the most widely used adaptive optimizer. To address the overshoot phenomenon, a control-theory-based PID optimizer was proposed. To tackle both the limitations within a single framework, several variants of Adaptive PID (AdaPID) have recently been proposed. Although AdaPID performs well, it still inherits two critical drawbacks from Adam, namely convergence and stability issues. In this work, we address both these limitations. To fix the convergence issue, we uniquely integrate the idea of using a non-increasing effective learning rate into AdaPID (originally proposed in AMSGrad, an extension of Adam). To fix the stability issue, we innovatively integrate a gradient difference based modulation factor into AdaPID (originally proposed in DiffGrad, another extension of Adam). Combining both these ideas in AdaPID, results in our novel IAdaPID-ADG optimizer. We evaluate our proposed optimizer on multiple datasets, including benchmark datasets (MNIST and CIFAR10) and real-world datasets (IARC and AnnoCerv). The IAdaPID-ADG substantially outperforms all competing optimizers. Additionally, we perform an ablation study on the MNIST dataset to demonstrate the contribution of each added component.

Saurabh Saini, Kapil Ahuja, Thomas Wick +1

Department of Computer Science & Engineering, Indian Institute of Technology Indore, India. · Leibniz Universität Hannover, Institut für Angewandte Mathematik, Germany. · National Remote Sensing Centre, Indian Space Research Organisation, India.

Deep Learning Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

May 19, 2026cs.LG

LionMuon: Alternating Spectral and Sign Descent for Efficient Training

In large-scale optimization, the cheapness and effectiveness of update steps are the most crucial factors for a successful optimizer. Sign-based optimizers like Lion or Signum produce cheap per-step updates, whereas Muon's spectral matrix-sign update gives a much stronger direction at a substantially higher per-step cost. In this work, we propose LionMuon, which retains the effectiveness of Muon steps while considerably cutting the averaged iteration cost, similar to sign-based methods. It alternates between Lion's and Muon's updates on a fixed period P, sharing a single dual-EMA momentum buffer between them. The optimizer state memory therefore matches Lion and is exactly half of AdamW's. A simpler single-EMA variant, SignMuon, by itself already outperforms pure Muon. At P = 2, LionMuon Pareto-dominates Muon, Lion, Signum, and AdamW on every dataset and architecture we tested at 124M model size, reaching lower validation loss at lower compute, and the same advantage persists at 355M and 720M scale. On the theory side, we prove sharp complexity bounds under heavy-tailed noise which are governed by period-averaged smoothness and noise that interpolate between Muon's and Lion's constants. These bounds predict the compute-optimal period and the conditions under which LionMuon outruns Muon and Lion. Code: https://github.com/brain-lab-research/lion-muon

Arman Bolatov, Artem Riabinin, Nikita Kornilov +4

Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · Basic Research of Artificial Intelligence Laboratory (BRAIn Lab) · Applied Artificial Intelligence Institute +1

Stochastic Optimization Sign-Based Optimization Momentum Methods Neural Network Optimization Muon Optimizer Stochastic Optimization Convergence

May 19, 2026cs.NE

From Mean-Field Limits to Semiclassical Concentration: Global Convergence of the Canonical Evolutionary Strategy

We address the issue of global convergence in stochastic continuous optimization. For that purpose, we formulate the Canonical Evolutionary Strategy (CES) as a controlled mathematical framework to analyze global convergence in evolutionary algorithms via the semiclassical limit of a Schr{ö}dinger-type replicator-mutator equation. We provide a rigorous hierarchy from a discrete individual-based dynamics to a deterministic mean-field limit, demonstrating that global convergence is governed by the principal eigenfunction of the underlying operator. This property, defined as Geometric Selection, naturally prioritizes robust, flat optima over narrow local traps, offering a mathematical justification for the ''survival of the flattest'' phenomenon. Moreover, unlike consensus-driven methods that are prone to premature variance collapse when the global minimizer resides outside the initial support, the replicator-mutator dynamics of CES facilitate intrinsic mass transport. High-dimensional benchmarks (d = 30) confirm this advantage, showing that CES achieves lower residual errors in shifted initialization scenarios where standard consensus-driven and gradient-based methods fail to migrate effectively. By shifting the focus from point-wise consensus to spectral concentration, our framework provides a robust theoretical foundation for global convergence in Evolution Strategies (ES) without the need for additional numerical heuristics.

Matías Neto, Nicolás Garay, Luis Martí +1

Inria Chile Research Center, Av Apoquindo 2827, Las Condes, RM, Chile · Departamento de Ingeniería Matemática, Universidad de Chile, Santiago, Chile

Dynamical Systems Evolutionary Optimization Evolution Strategies Global Optimization Stochastic Optimization Convergence Flat Minima