Stochastic Optimization Convergence

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

Aug 3, 2026cs.LG

AOS: Adaptive Optimizer Switching via Training-State Signals for Faster Convergence and Better Generalization

Single-optimizer training is a poor fit for the distinct phases of deep network optimization: adaptive methods handle noisy early gradients well but overshoot flat minima, while SGD with momentum generalizes better in the late phase but converges slowly early on. We introduce AOS-R (Adaptive Optimizer Switching, Rule-Based), a lightweight controller that monitors six online gradient-space signals -- gradient noise scale (GNS), Hutchinson curvature trace, loss stagnation, update stability ratio, gradient stability index (GSI), and loss improvement ratio (LIR) -- and switches among AdamW, SGD-M, and Lion as the optimization landscape evolves. State-preserving momentum transfer and a 400-step learning-rate bridge prevent accuracy degradation at every transition point. On CIFAR-100/WRN-28x10, AOS-R reaches 78% top-1 in 81 epochs -- 26% fewer than AdamW (109), 43% fewer than SGD-M (143), and 16% fewer than Lion (96). Across eight model-dataset benchmarks, AOS-R achieves best accuracy on 6 of 8 combinations with a mean +0.4 pp gain and 0.80x convergence speedup over AdamW under a single shared hyperparameter configuration.

Alok Kumar Pandey, Umang Chaturvedi, Aatish Rana +1

Deep Learning Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Neural Network Training Dynamics

Ask PDF

Jul 31, 2026cs.LG

Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

We develop a parallel framework that assembles static gradient methods to achieve better adaptivity. A static gradient method, denoted by

\mathrm{GD}(x_0,T)

, takes as input an initial point

x_0\in\mathbb{R}^n

and

T\in \mathbb{R}^+

specifying the number

\floor{T}

of iterations. The step size is chosen as

s=S(T)

, where

S(\cdot)

is a predetermined function of

T

. The method then performs the iterations

x_{i+1}=x_i-\fracη{s}\cdot g_i,

where

g_i

is a stochastic gradient evaluated at

x_i

, and

η

is a scaling factor. For an integer

p\ge1

, the

p

processors in the proposed parallel framework search for an appropriate value of

T

according to a geometric sequence so that the resulting gradient descent satisfies the desired convergence conditions. Each processor executes an infinite sequence of stages indexed by

i=1,2,\ldots

. At stage

i

, processor

j

is assigned

T_{j,i}=h(j,i),

where

h:\mathbb{N}\times\mathbb{N} \rightarrow\mathbb{R}^{+}

is a prescribed function. Processor

j

(j=0,1,\ldots,p-1)

executes

\mathrm{GD}(x_0, T_{j,i})

at stage

i

Bin Fu

University of Texas Rio Grande Valley

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Ask PDF

Jul 29, 2026cs.LG

The Convergence Behavior of Adam under Heavy-Tailed Noise

We establish the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise. While several Adam variants are known to achieve optimal iteration complexity in bounded-variance nonsmooth nonconvex optimization, little is understood about their behavior when stochastic gradients admit only a bounded

p

-th central moment for some

p \in (1,2]

, a setting increasingly observed in modern deep learning. To address this gap, we generalize the recent online-to-nonconvex conversion framework to accommodate heavy-tailed martingale-difference noise. Building on this generalized framework, we develop a discounted regret analysis for Adam, without restrictive parameter coupling. Our results show that Adam converges to

(ρ,ε)

-stationary points under heavy-tailed noise. However, it exhibits a suboptimal iteration complexity and

p

-dependent convergence, a suboptimality that persists even in the bounded-variance case (

p=2

). Specifically, the

ε

-dominant term in the iteration complexity for reaching in-expectation stationarity is

T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{5p}{3p-4}}ε^{-\left(\frac{5p}{3p-4}+\frac{3}{2}\right)}\right)

for

p\in(\frac{4}{3},2]

, which simplifies to

T=\mathrm{O}(ε^{-13/2})

when

p=2

. When the domain radius is known and used to control the online-learner output, a standard setup in related literature, the convergence rate improves to match the optimal complexity. In this case, the

ε

-dominant iteration complexity is

T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{p}{p-1}}ε^{-\left(\frac{p}{p-1}+\frac{3}{2}\right)}\right)

for

p\in(1,2]

, which simplifies to

T=\mathrm{O}(ε^{-7/2})

when

p=2

. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.

Yijiang Pang

Michigan State University, East Lansing, USA

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

Ask PDF

Jul 29, 2026math.OC

Adaptive Gradient-Based Methods for a Broader Class of Optimization Problems under Performative Prediction

We study optimization under performative prediction, where deploying a model affects the future data distribution. For this setting, several gradient-based approaches have been proposed. However, they typically assume specific data distributions or loss functions, which limit their practical applicability. To overcome these limitations, we propose a gradient-based optimization method with convergence guarantees under substantially weaker assumptions. Our method explicitly estimates the induced distribution shift through finite differences. It enables higher-dimensional optimization across broader classes of loss functions and data distributions. We also propose a practical variant that reduces the number of samples required. Numerical experiments demonstrate that our proposed algorithms converge faster and more consistently than existing ones.

Hiroki Hamaguchi, Yuya Hikima, Hiroshi Sawada +1

Graduate School of Information Science and Technology, The University of Tokyo · Department of Industrial Engineering and Economics, Institute of Science Tokyo · Communication Science Laboratories, NTT, Inc. +1

Stochastic Optimization Convergence Adaptive Gradient Methods Performative Prediction

Ask PDF

Jul 28, 2026math.OC

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias

O(τ_{\mathrm{mix}}/T)

uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under

σ^2\mapsto 2ΛG_σ^2

and

L^2\mapsto 2ΛL^2

, where

Λ=O(τ_{\mathrm{mix}}\log T)

. For positive centered noise, the tuned method achieves expected sample complexity

\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})

. The exactly noiseless specialization achieves

\widetilde{O}(\varepsilon^{-2})

with mixing-time-free constants, while a mixing-time-oblivious variant achieves

\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})

. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Zhaojun Peng

School of Computer Science Nanjing University of Information Science and Technology

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Variance Reduction

Ask PDF

Jul 24, 2026cs.LG

On the Convergence of Stochastic Low-Rank Adaptation

Low-rank adaptation (LoRA) optimizes

J(B,A)=\mathcal L(W_\mathrm{base}+sBA)

over two adapters

B \in \mathbb{R}^{m \times r}

and

A \in \mathbb{R}^{r \times n}

that form a low-rank update to a frozen pretrained weight matrix

W_\mathrm{base} \in \mathbb{R}^{m \times n}

. The prior analysis shows LoRA-GD takes

\exp\{\mathcal{O}(ε^{-2})\}

oracle calls to find an

ε

-stationary point such that

\|\nabla J(B,A)\|\leq ε

in the deterministic setting. We sharpen the analysis and show that

\mathcal{O}(ε^{-4})

full-gradient evaluations suffice for the same first-order criterion. We further study stochastic LoRA under unbiased gradient estimates and finite variance. We propose LoRA-NSGDM, which finds an

ε

-stationary point with

\mathcal{O}(ε^{-8})

stochastic oracle complexity. Under the additional mean-square smoothness condition, we use variance reduction strategy and propose LoRA-STORM, which improves the stochastic oracle complexity to

\mathcal{O}(ε^{-6})

Ru Wang, Chengchang Liu, John C. S. Lui

The Chinese University of Hong Kong · Westlake University

Nonconvex Stochastic Optimization Low-Rank Adaptation Stochastic Optimization Convergence

Ask PDF

Jul 21, 2026stat.ML

RELTA-SGLD: Relative-Growth Localized Taming for Nonconvex Stochastic-Gradient Langevin Learning

We introduce RELTA-SGLD, a taming scheme that stabilizes superlinear stochastic-gradient updates while reducing unnecessary suppression of the original learning drift. A threshold determines where the taming turns on, while a relative-growth principle derived from the one-step Lyapunov stability condition determines the required taming strength. Together, they produce a lighter

λ

-scale denominator and preserve a nonvanishing far-tail return. As a consequence, we prove polynomial moment stability and first-order stationary accuracy in both

W_1

and

W_2

for nonconvex SGLD with superlinearly growing stochastic-gradient oracles, improving the corresponding half-order and quarter-order bounds for comparable stochastic-gradient tamed schemes. On Fashion-MNIST under active stabilization pressure, RELTA improves the mean learning metrics over both untamed SGLD and TUSLA and remains competitive with a tuned AdamW reference. In an ordinary-training regime, its lighter localized denominator reduces unnecessary perturbation of the original update and maintains nearly untamed learning dynamics.

Yiwei Zhou, Ziheng Chen

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

Stochastic Gradient Langevin Dynamics Langevin Dynamics Nonconvex Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Jul 17, 2026cs.LG

Scaling Limits of Constant-Stepsize SGD at Flat Minima

For stochastic gradient descent (SGD) with a constant stepsize

α

, the invariant law of the iterates, centered at a minimizer, describes the behavior of the algorithm over long time horizons. In the strongly convex case, this invariant law has the familiar

\sqrtα

scaling and a Gaussian limit as

α\downarrow 0

. We show that this behavior changes fundamentally for convex objectives

H

with flat minima and (sub)quadratic tails. More specifically, we study SGD with Markovian noise generated by a contractive driving chain. For every sufficiently small constant stepsize

α

, we prove existence, uniqueness, and geometric convergence to an augmented invariant law in a Wasserstein distance induced by an

α

-dependent metric. When the minimizer

x_\star

has local flatness exponent

m\ge2

, meaning that

\nabla^2 H(x)\asymp \lVert x-x_\star\rVert^{m-2} I_d

x\to x_\star

, we obtain a contraction bound with factor

1-cα^{m-1}

, where

c>0

is a constant. This recovers the factor

1-cα

in the quadratic case

m=2

. We then analyze the small-stepsize scaling limit. We show that the invariant law concentrates on the scale

α^{1/m}

and that the rescaled iterates converge weakly to the stationary distribution of the stochastic differential equation

dY_t=-h_0(Y_t)\,dt+Σ^{1/2}\,dB_t ,

where

h_0

is the limiting drift at the minimizer and

Σ

denotes the asymptotic covariance. This recovers the Gaussian limit when

m=2

and gives generally non-Gaussian stationary limits in the flat case

m>2

. Finally, we give corresponding results for coordinate-separable objectives with unequal flatness exponents.

Jingyi Zhang, Cheng Mao, Debankur Mukherjee

Georgia Institute of Technology

Stochastic Optimization Convergence Flat Minima Stochastic Gradient Descent

Ask PDF

Jul 16, 2026cs.LG

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explains when and why local updates help under realistic data heterogeneity. Recent work by [Patel et al., 2025] shows that a bounded second-order heterogeneity assumption captures the efficiency of Local SGD for strongly convex objectives, and conjectures that the same principle extends to the general convex setting. In this paper, we prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity. We also improve the best-known lower bounds for Local SGD in this setting, showing that our upper bounds are nearly tight. Together, these results provide a sharper, more fine-grained convergence theory for Local SGD. As a further application of our techniques, we provide a lower bound for serial SGD with replacement, showing how second-order heterogeneity captures the impact of rare high-curvature clients.

Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich +3

Department of Mathematics and Computer Science University of Basel Basel, Switzerland 4001 · Simons Institute for the Theory of Computing, Berkeley · Department of Data Science New Jersey Institute of Technology Newark, NJ, USA 07102

Optimization Convergence Analysis Stochastic Optimization Convergence Federated Learning Stochastic Gradient Descent

Ask PDF

Jul 15, 2026eess.SY

Information-Theoretic Adaptive Cooling for Deterministic MPPI via Entropy Feedback

This paper investigates deterministic optimal control using Model Predictive Path Integral (MPPI) control, a sampling-based and derivative-free framework well suited for systems with complex dynamics and nonsmooth objectives. In deterministic MPPI, the temperature must be driven to zero to recover the true optimum, yet the design of an effective cooling schedule remains a fundamental challenge. Existing methods typically rely on predefined open-loop schedules, which limit the efficiency and robustness of the algorithm. To overcome this limitation, we propose an Information-Theoretic Adaptive Cooling (ITAC) framework that uses the Shannon entropy of the importance weights as an online feedback signal to regulate the temperature. The proposed mechanism adapts the cooling rate to the current sampling state, enabling fast progress when the weights are diffuse and cautious cooling when they become concentrated. We prove asymptotic convergence of the resulting scheme to the deterministic optimum, and further derive a critical entropy threshold that leads to a smooth barrier against premature weight collapse. Experiments on nonsmooth signal temporal logic motion-planning tasks show that ITAC improves sampling efficiency and achieves substantially faster convergence than state-of-the-art baselines without sacrificing the derivative-free nature of MPPI.

Shuqi Wang, Wenrong Sun, Tao Han +2

School of Automation & Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China · Department of Physics, The Hong Kong University of Science and Technology, Hong Kong S.A.R., China

Stochastic Optimization Convergence MPPI Control Sampling-Based Motion Planning

Ask PDF

Jul 14, 2026cs.LG

Same Loss, Same Noise, Opposite Schedules: Noise Structure and Optimizer Normalization Jointly Determine Whether Learning-Rate Cooldown Helps

The cooldown phase of a warmup-stable-decay (WSD) learning-rate schedule, now a default in large-model pretraining, lowers the final training loss in some settings and does nothing in others. We give a provable account of which case obtains, and it turns on two properties together: the structure of the gradient noise and whether the optimizer normalizes its update. On a strongly convex objective with multiplicative (gradient-proportional) noise, stochastic gradient descent contracts geometrically at a constant learning rate, so cooldown has nothing to improve. Under the same objective and noise, sign-based and normalized methods, the standard surrogates for adaptive optimizers, settle on a noise floor of order

η^2

and reach the minimizer only as the learning rate is driven to zero; any additive noise then reinstates a floor for every method. The mechanism is elementary: an SGD step shrinks in proportion to the gradient and so anneals itself, whereas a normalized step keeps unit scale and cannot. We solve the signSGD stationary law on the quadratic exactly and obtain the floor constant in closed form, prove a local form of the dissociation under

(L_0,L_1)

-smoothness, extend the floor to normalized SGD in dimension d>1 by a scale-invariance argument, and establish robustness to momentum and heavy-tailed noise. Simulation confirms every prediction, and we demonstrate the resulting noise-regime diagnostic on a real classification task with directly measured gradient noise. The mechanism explains whether cooldown helps; the interior cooldown fraction used at scale lies outside stationary landscape-and-noise geometry.

Subham Singh, Ashutosh Mishra, Subha Raut

Department of Mathematics and Statistics, Mississippi State University · Independent Researcher

Learning Rate Scheduling Gradient Descent Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Jul 13, 2026cs.DC

Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity

Decentralized gradient descent (DGD) is widely used for solving distributed optimization problems over networks of agents. While its convergence properties are well understood, less is known about the communication and computation resources required to attain a prescribed accuracy. In this paper, we study DGD from a resource-aware perspective and characterize the communication-computation budget required to attain a target error level. We develop a bottleneck-centric framework in which different factors dominate the optimization dynamics at different error scales. Specifically, we identify operating regimes governed by initialization, objective heterogeneity and network connectivity, gradient noise, and communication noise. To capture these effects, we introduce two fundamental quantities: the gradient-Diversity-to-Network-connectivity Ratio (DNR) and the Gradient-to-Communication-noise Ratio (GCR). We show that these quantities determine the sequence of bottlenecks encountered during optimization and the corresponding budget-optimal operating strategy. Using a multi-stage analysis, we derive optimal stepsize selections and explicit budget-complexity bounds that quantify the budget resources required to attain a prescribed accuracy. The resulting expressions reveal how the overall budget decomposes into contributions associated with successive bottlenecks and provide insight into the fundamental tradeoffs among objective heterogeneity, network connectivity, gradient noise, and communication noise.

Nicolò Michelusi

School of Electrical, Computer and Energy Engineering, Arizona State University.

Distributed Optimization Stochastic Optimization Convergence Decentralized Optimization

Ask PDF

Jul 10, 2026math.OC

Solving Stochastic Fixed-Point Equations with High Probability

We study stochastic fixed-point equations

\mathbf{T}(\mathbf{x}) = \mathbf{x}

over normed spaces

(\mathcal{E}, \|\cdot\|)

, where the operator

\mathbf{T}

is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment. Given

ε> 0, δ\in (0, 1)

, the goal is to output

\mathbf{x} \in \mathcal{E}

such that

\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε

with probability at least

1-δ

. We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces. The key algorithmic ingredient is a recursive stochastic estimator based on clipped differences of oracle evaluations: instead of clipping

τ(\mathbf{x}; ξ)

itself, we clip stochastic differences at the Lipschitz scale

γ\|\mathbf{x} - \mathbf{y}\|

. This makes the estimator pathwise Lipschitz along the algorithmic trajectory while permitting martingale concentration under finite second moments in the native norm. Our main theorem gives an anytime high-probability residual bound: on a single event of probability at least

1 - δ

, the residual decreases nearly geometrically across epochs, up to lower-order logarithmic factors. Under only bounded variance, displaying only the dependence on the target error

ε

and Lipschitz constant

γ\in (0, 1]

\mathbf{T}

, the resulting oracle complexity is

\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}

. Under a Lipschitz-in-expectation oracle, the dependence improves to the corresponding

ε^{-3}

nonexpansive rate (i.e., for

γ= 1

), and under samplewise nonexpansiveness to

ε^{-2}

Jelena Diakonikolas

Department of Computer Sciences University of Wisconsin-Madison

Stochastic Approximation Stochastic Optimization Convergence Variance Reduction

Ask PDF

Jul 9, 2026cs.LG

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

Stochastic gradient descent (SGD) is a cornerstone of modern optimization. While its performance under heavy-tailed noise is often addressed through specialized modifications such as gradient clipping or normalization, we investigate a more fundamental question: how does vanilla SGD, particularly with momentum, perform in the presence of heavy-tailed noise? In this paper, we refine existing convergence results for vanilla SGD and, more importantly, provide the first comprehensive convergence analysis of vanilla SGD with momentum for strongly convex, convex, and nonconvex objectives, without employing any gradient control mechanisms. Our results demonstrate that the obtained convergence rates are inferior to the optimal rates achieved by clipped or normalized variants of SGD, thereby revealing inherent limitations of vanilla methods under heavy-tailed noise. The theoretical findings are supported by experiments on synthetic functions.

Ryusei Yamada, Naoki Sato, Hideaki Iiduka

Meiji University, Japan

Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

Jul 8, 2026cs.LG

Avoiding unsafe sets when training with Langevin Dynamics

Training a model with noisy gradient descent can be idealized as overdamped Langevin dynamics, and a natural safety question is to bound the probability

ν_t(\mathcal{A}_H) = \mathbb{P}(Q_t \in \mathcal{A}_H)

that the trajectory lies in a designated failure region

\mathcal{A}_H

. We study this for a smooth, strongly convex loss in

d

dimensions, with

\mathcal{A}_H

separated from the minimizer by an energy gap. At the end of training, the equilibrium mass

π(\mathcal{A}_H)

is exponentially small in

d

, with a complementary energy-barrier rate when the noise is small. Along the trajectory, a shape-free bound

ν_t(\mathcal{A}_H) \le π(\mathcal{A}_H)(1 + \sqrt{χ_0^2/π(\mathcal{A}_H)}\,e^{-mt})

shows the in-set probability relaxes to (twice) the static value after a burn-in of order

d

, using only the global spectral gap

m

. A worked Ornstein-Uhlenbeck example shows this burn-in is necessary: an angular slice of the equilibrium shell can transiently swell by a factor exponential in

d

, though its equilibrium mass is tiny. To rule this out we introduce a local relaxation rate, defined through the spectral measure of the region's centered indicator rather than a Dirichlet-form Rayleigh quotient. For geometrically isolated regions this rate exceeds the global one, shrinking the burn-in, and with a maximum-principle ceiling it caps the trajectory probability uniformly in time. Strong convexity sets how fast training relaxes, but the shape of the unsafe set decides whether the trajectory bulges through it on the way to equilibrium.

Adam M. Oberman

Department of Mathematics and Statistics, McGill University, Montreal, QC, Canada; Mila, Quebec AI Institute; and LawZero

Langevin Dynamics Stochastic Optimization Convergence

Ask PDF

Jul 8, 2026stat.ML

Finding a stationary point of a stochastic convex problem

We consider the problem of finding stationary points for stochastic convex optimization problems. Rather than surrogates to stationarity, such as a proximity-to-stationarity guarantee or small gradient of the Moreau envelope, we ask for a stronger notion: that the subdifferential of the objective actually contains a small element. This criterion is non-trivial, because subdifferentials of convex functions fail to converge uniformly, even in arbitrarily small neighborhoods of the optimum. Our convergence guarantees rely on dimension theory to decompose the graph of the subdifferential of a convex function, showing how stochastic sampling preserves "pieces" of these graphs, and allowing effective application of proximal-point-like methods.

Felipe Areces, John Duchi, Malo Sommers

Stanford University

Stochastic Optimization Convergence Nonsmooth Convex Optimization

Ask PDF

Jul 4, 2026cs.LG

A Gradient Flow Perspective on Minimum MMD Estimation

Minimum maximum mean discrepancy (MMD) estimation has emerged as a robust and likelihood-free alternative to maximum likelihood estimation for parameter estimation. Yet, despite its practical success, the associated optimization problem remains poorly understood, with theoretical guarantees for existing algorithms hinging on convexity assumptions that rarely hold in practice. We address this gap by proposing a preconditioned gradient descent (PGD) scheme, establishing its asymptotic \emph{global} convergence under explicit gradient-dominance and projection-residual conditions. Our approach is inspired by recent progress on MMD gradient flows, a nonparametric descent scheme on the space of probability measures. We provide extensive empirical evidence that our PGD scheme outperforms standard gradient descent across a range of challenging parameter estimation and composite hypothesis testing problems.

Sophia Seulkee Kang, Louis Sharrock, Xiaoyuan Cheng +2

Independent Researcher · University College London

Parameter Estimation Maximum Mean Discrepancy Gradient Descent Stochastic Optimization Convergence

Ask PDF

Jul 3, 2026cs.LG

On the Convergence of Adam, Revisited

We show that projected Adam for online optimization with arbitrary moment decay parameters

β_1,β_2\in[0,1)

can have average regret bounded away from zero. A similar result of Reddi-Kale-Kumar from 2018 required

β_1<\sqrt{β_2}

. Similar to their result, we use a three-periodic sequence of linear functions on

[-1,1]

with slopes

c,-1,-1

, though we use

c

slightly larger than

2

. This nonzero average regret result extends to Adam variants such as AdamW, RMSProp, NAdam, Adan, AdaMax, Muon, and to an i.i.d. variant of the three-periodic sequence of slopes for Adam.

Steven Heilman, Sampad Mohanty

Department of Mathematics, University of Southern California, Los Angeles, CA 90089.

Online Convex Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

Ask PDF

Jul 2, 2026math.OC

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization

In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.

Siyuan Zhang, Nachuan Xiao, Xin Liu

Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Nonsmooth Convex Optimization Decentralized Optimization

Ask PDF

Jun 30, 2026math.OC

Random Reshuffling Dominates Stochastic Gradient Descent

Stochastic Gradient Descent (

\textsf{SGD}

) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of

\textsf{SGD}

differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (

\textsf{Shuffling SGD}

). A particularly popular strategy in

\textsf{Shuffling SGD}

is Random Reshuffling (

\textsf{RR}

), which has achieved great empirical success across numerous experiments. Despite its strong performance,

\textsf{RR}

has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for

\textsf{RR}

, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of

\textsf{RR}

remain to this day. More precisely, according to the current theory,

\textsf{Shuffling SGD}

under

\textsf{RR}

converges only when the stepsize is smaller than a threshold proportional to

1/n

, where

n

is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of

\textsf{Shuffling SGD}

under

\textsf{RR}

is strictly worse than that of

\textsf{SGD}

when the number of epochs is smaller than another threshold proportional to

n

. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that

\textsf{RR}

dominates

\textsf{SGD}

in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Jun 29, 2026stat.ML

SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Rates

Modern deep learning has been shown to operate at the edge of stability, routinely using learning rates far larger than those justified by classical optimization theory. Most prior analyses of the edge of stability phenomenon focus on deterministic gradient descent, leaving the stochastic setting largely unexplored. In this work, we provide sharp convergence guarantees for Stochastic Gradient Descent (SGD) applied to the multiclass cross-entropy loss, for both linear classifiers and two-layer neural networks. We show that the stochasticity of SGD may cause the dynamics to alternate between an edge-of-stability regime that is dominated by curvature-driven oscillations, and a stable regime in which the expected loss decreases at a controlled rate. Despite that, we prove that SGD self-stabilizes the dynamics, ensuring that the iterates return to stability in a fixed number of iterations and allowing convergence in the best-iterate sense even with large learning rates. Experiments validate our theoretical findings and illustrate the benefits of SGD in the large-stepsize regime.

Konstantinos Emmanouilidis, Lachlan MacDonald, Salma Tarmoun +1

Department of CIS1 · IDEAS4 · University of Pennsylvania +2

Edge of Stability Stochastic Optimization Convergence Neural Network Training Dynamics Stochastic Gradient Descent

Ask PDF

Jun 29, 2026cs.LG

Curvature-Weighted Gradient Diversity: A Noise Measure for Geometry-Adaptive SGD Schedules

The standard convergence analysis of mini-batch stochastic gradient descent (SGD) models gradient noise using a single variance term that treats all parameter directions equally, ignoring the fact that noise in high-curvature directions has less impact because learning rates are already constrained there. We introduce Curvature-Weighted Gradient Diversity (CWGD), a geometry-aware measure that weights per-sample gradient diversity by the inverse square root of the Hessian, providing a tighter proxy for the effective optimization noise. For strongly convex quadratic objectives with diagonal Hessians and isotropic noise, we prove that a CWGD-modulated cosine learning-rate schedule can reduce the asymptotic optimization error floor by up to a factor of two compared with standard cosine annealing. We implement this idea as CWGD-Cosine using a Hutchinson-based diagonal Hessian estimator that is exact for quadratic objectives. Across a range of condition numbers, batch sizes, and noise structures, CWGD-Cosine consistently achieves approximately 20% lower final optimization error than standard cosine annealing while incurring negligible overhead in the quadratic setting. We also identify and correct a degenerate curvature estimator, analyze the robustness of the proposed estimator, and explicitly discuss the limitations of the method, including Hessian staleness in non-convex optimization. These results establish CWGD as a principled geometry-aware measure of optimization noise and motivate future extensions to more general learning problems.

Muhammad Hamza, Ayush Goel

Indian Institute of Technology Kharagpur · Indian Institute of Technology Kharagpur (IIT KGP)

Learning Rate Scheduling Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Jun 28, 2026math.OC

A samplewise backpropagation method for neural networks driven by fractional Brownian motion

In this paper, we develop a fractional stochastic neural network with residual dynamics driven by fractional Brownian motion. By introducing a discrete stochastic maximum principle for the network, we construct the corresponding adjoint recursion. For deterministic network parameters, we prove mean square convergence of projected samplewise stochastic gradient descent. Numerical experiments include a closed form convergence test, noisy regression with uncertainty quantification, long memory time series generation and image classification under structured perturbations. The results identify settings in which fractional drivers improve long memory recovery or robustness relative to Brownian and deterministic baselines.

Yuecai Han, Jianming Xu

School of Mathematics, Jilin University, Changchun 130012, Jilin, China

Stochastic Differential Equations Stochastic Optimization Convergence

Ask PDF

Jun 27, 2026cs.LG

Analysis of Adam Algorithms for Stochastic Dynamic Systems

The adaptive moment estimation algorithm, known as Adam, is widely used in modern machine learning, owing to its low per-iteration complexity and strong empirical performance. Despite its prevalent use, the theoretical foundation of Adam remains largely unexplored for time-varying and nonstationary systems. In fact, the existing theoretical analyses of Adam-type algorithms are primarily concerned with time-invariant model parameters and explicitly or implicitly rely on independent and identically distributed (i.i.d.) data assumptions, under which the learning taskcan be formulated as minimizing a fixed expected objective with a static minimizer. However, such assumptions are often violated in time-varying and nonstationary systems, thereby calling for a theoretical investigation beyond the conventional yet idealized i.i.d. setting. The main objective of this paper is to solve this challenging problem by establishing a general theory of Adam for time-varying and nonstationary stochastic systems. We will introduce some new techniques for analyzing the products of nonstationary and dependent random matrices induced by Adam's coupled first- and second-moment recursions, and will construct a new stochastic Lyapunov function that blends these two moment dynamics. Under a stochastic excitation condition that allows nonstationary and dependent data, we will derive both parameter tracking and output prediction error bounds explicitly, quantifying the effects of stepsize, first- and second-momentum parameters, gradient noise and parameter drift. These bounds not only provide guarantees for Adam performance, but also provide guidelines for hyperparameter selection. Experiments on both synthetic and real-world data validate our theory and design guidelines.

Xin Zheng, Yifei Jin, Lei Guo

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China · School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing 101408, China

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

Ask PDF

Jun 24, 2026cs.LG

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

We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time high-probability bounds for ordinary Stochastic Gradient Descent (SGD) under a standard growth envelope scale as

\widetilde{O}(t_{mix}^2/k)

, leaving a gap with the

\widetilde{O}(t_{mix}/k)

expectation bounds. We close this gap using a lag-blocking argument to establish a uniform high-probability guarantee with a leading stochastic term of

\widetilde{O}(t_{mix}/(k+K_0))

under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching

Ω(σ^2 t_{mix}/k)

lower bound on a quadratic objective driven by a persistent two-state chain. We then extend this framework to heavy-tailed Markovian gradients satisfying a stationary finite-

p

-moment condition,

p \in (1,2]

. We design an all-samples clipped block method that uses every Markov transition while mitigating Markovian bias. Under a transition budget

T

, this algorithm achieves a high-probability stochastic error of

\widetilde{O}(σ_p^2(t_{mix}/T)^{2(p-1)/p})

. We establish a matching lower bound by reducing PL optimization to heavy-tailed mean estimation for a sticky Markov chain. Ultimately, this work tightly characterizes the optimal polynomial dependence on mixing time for light-tailed PL-SGD, and the optimal heavy-tail exponent and effective-sample-size dependence in the robust regime.

Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

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

Stochastic Optimization Optimization Convergence Analysis Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization+1

Ask PDF

Jun 23, 2026math.OC

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon

n

, we consider the standard fixed stepsizes

η=Θ(1/\sqrt n)

. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order

1/\sqrt n

, thereby removing the extra

(\log n)

factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order

(\log n)/\sqrt n

. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1

Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Optimization Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Nonsmooth Convex Optimization

Ask PDF

Jun 23, 2026cs.LG

A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging

We study linear TD(0) under Markovian sampling, where data are generated along a single trajectory. We provide high-probability guarantees for a plain unprojected TD(0) algorithm with Polyak-Ruppert (PR) averaging, using a single stepsize schedule

η_t \propto \frac{1}{τ_{\mathrm{mix}}\log(t)\sqrt{t}}

that depends on the mixing time but requires no prior knowledge of the curvature parameter

ω

. Our first result shows that such a choice of the stepsize guarantees that the TD(0) iterates are automatically and uniformly bounded with high probability, without projections and without any stability argument based on

ω

. Building on this result, we establish a simultaneous high-probability convergence guarantee for the PR average: the same stepsize yields both a robust curvature-free

\widetilde{\mathcal{O}}\!\left(\frac{τ_{\mathrm{mix}}}{\sqrt{T}}\right)

rate and a fast curvature-dependent

\widetilde{\mathcal{O}}\!\left(\frac{τ_{\mathrm{mix}}^2}{ωT}\right)

rate, with the bound taking the minimum of the two. The core technical ingredient is a Poisson-equation toolkit for geometrically mixing Markov chains, which decomposes Markov noise into a martingale term plus a controlled remainder and enables a new self-bounding inductive argument for pathwise stability.

Wei-Cheng Lee, Francesco Orabona

King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia

Stochastic Approximation Temporal-Difference Learning Stochastic Optimization Convergence

Ask PDF

Jun 22, 2026cs.LG

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

AdamW is the de facto optimizer for training large language models (LLMs), yet the theory behind it still lives mostly in finite-variance regimes. This is increasingly unsatisfying, as empirical evidence indicates that stochastic gradient noise in LLM pretraining is typically heavy-tailed. Recent work shows that sign-based optimizers such as Lion and Muon achieve sharp heavy-tailed rates, and that AdaGrad can also converge under heavy-tailed noise. However, no rigorous convergence theory for AdamW has yet been established in this regime. Can AdamW converge under the same heavy-tailed assumptions, or does its second-moment accumulator create a genuine obstruction? We formulate this as an open problem, prove a positive weighted-metric benchmark, and give a corridor lower-bound mechanism showing how denominator memory can hide large gradients.

Dingzhi Yu, Hongyi Tao, Yuanyu Wan +2

1Nanjing University · 2Zhejiang University · 3Fudan University

Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Ask PDF

Jun 21, 2026cs.LG

Clipping the Price of Adaptivity at the Tail

Adaptive stochastic convex optimization (SCO) methods face a fundamental ``price of adaptivity'' barrier: under the standard set of assumptions, they cannot efficiently adapt to large uncertainty in both the initial distance to optimality and the Lipschitz constant. We circumvent this barrier by requiring a small amount of additional structure common to many learning problems. Specifically, we assume that the objective decomposes into a model and a loss function, enabling us to intervene by modifying the model's output before it passes to the loss function. Under this assumption, we design a method that clips the learned model output in tail events where it deviates too much from the output of a fixed reference model. Our method matches the optimal bounds for known-parameter SCO up to logarithmic factors in the uncertainty in the distance and Lipschitz parameters, thus efficiently adapting to large uncertainty in both.

Itai Kreisler, Yair Carmon, Oliver Hinder

Tel Aviv University · University of Pittsburgh

Stochastic Optimization Stochastic Optimization Convergence

Ask PDF

Jun 21, 2026cs.LG

Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization

Many central machine learning tasks, from entropy tuning in reinforcement learning to equilibrating generative adversarial networks, are fundamentally stochastic root-finding problems rather than loss minimization. Yet, they are frequently forced into a minimization framework via squared residuals, introducing a critical flaw we identify as the Variance Trap. Standard bilevel minimization algorithms require estimating hypergradients involving implicit Jacobians; in stochastic settings, these terms act as noise amplifiers, destabilizing convergence. We formalize Root-Finding Bilevel Optimization (RF-BO) as a distinct problem class that bypasses this pathology. We propose a Jacobian-free solution using Two-Time-Scale Stochastic Approximation (TTSA) that updates directly along the root error, structurally avoiding variance amplification. We provide the first non-asymptotic convergence guarantees for TTSA in this setting under Markovian noise. Extensive experiments demonstrate the decisive advantage of this paradigm: compared to squared-residual and implicit-gradient baselines, our framework achieves a 2.6% top-1 accuracy gain in SimCLR, 17

\times

faster convergence in non-linear ODE control where baselines fail, significantly improved entropy stability in reinforcement learning, and an 11.1% quality improvement in generative modeling.

Zhiyu Li, Xi Xuan, Davide Carbone

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

Stochastic Approximation Bilevel Optimization Two-Timescale Stochastic Approximation Stochastic Optimization Convergence

Ask PDF

Momentum

Related topics

Latest papers 141