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

Oct 6, 2026stat.ML

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For

\ell

-smooth games with an inner

μ

-PL inequality, we prove a complexity lower bound

Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})

, where

κ=\ell/μ

is the condition number,

σ^2

is the gradient variance, and

\varepsilon

measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as

o(κ^2)

. Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.

Junsoo Ha

Optimization Convergence Analysis Min-Max Optimization Two-Timescale Stochastic Approximation Stochastic Optimization Convergence Stochastic Gradient Descent

Oct 5, 2026math.OC

A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization

Recent advances in penalty-based methods for stochastic bilevel optimization (SBO) have eliminated the need for second-order derivative oracles. However, for stochastic nonconvex-strongly convex bilevel problems, existing first-order methods typically rely on nested loops and/or large batch sizes for attaining

O(ε^{-6})

or

O(ε^{-4})

sample complexity under standard bounded-variance assumption or mean-square smoothness assumption. Achieving these rates with a single-loop penalty method and a constant batch size remains challenging due to a large penalty value needed for an accurate approximation. To address this challenge, we develop a stochastic SIngle-loop COnstant-Batch first-order penalty method (SICO) that combines two complementary ingredients. First, it performs one stochastic-gradient update per-iteration for both the original lower-level and penalized problems, with a projection that controls the separation between their iterates. Second, it applies an exponential moving average to stabilize the upper-level gradient estimator. We show that this combination achieves

O(ε^{-6})

sample complexity using only

O(1)

stochastic-gradient samples per iteration under unbiased, bounded-variance stochastic gradients. Under the additional mean-square smoothness assumption on the lower-level stochastic gradients, the same algorithm improves the complexity to

O(ε^{-4})

also with

O(1)

batch size. To the best of our knowledge, this is the first work to match the best-known convergence rate for fully first-order SBO methods using a single loop and a constant batch size. This result addresses an open problem posed in the literature.

Xingyu Chen, Ming Yang, Quanqi Hu +1

Department of Computer Science and Engineering Texas A&M University, College Station, USA

Bilevel Optimization Stochastic Optimization Convergence

Oct 4, 2026stat.ML

Gaussian Limits for SGD Without Stationary Moments

Temporal dependence can separate the Gaussian approximation of stochastic gradient descent from its stationary moments. For unmodified least-squares SGD, we construct a design with standard Gaussian marginals whose stationary error has every positive moment infinite. Independent observations with the same marginals instead give finite stationary variance. Both regimes retain a Gaussian small-step limit. Our general theory establishes pathwise contraction from a finite second design moment, then uses score cancellation and localization to obtain stationary Gaussian and Ornstein--Uhlenbeck limits. Independent Gaussian regression errors yield an exact conditional Gaussian law and total-variation convergence under the same design integrability. Stronger design conditions identify a positive first-order total-variation constant and a deterministic covariance correction with

o(a)

error. A scalar coverage expansion translates this correction into its inference consequence. Experiments examine distributional error, coverage, and calibration with dependent scores. Together, these results establish precise probability-law approximation beyond moment-based stationary analysis.

Xiaoli Li, Wei Biao Wu

University of Chicago

Stochastic Optimization Convergence Stochastic Gradient Descent

Oct 4, 2026cs.LG

Smoothed Gradient Method for Nonconvex Federated Stochastic Bilevel Optimization

In recent years, federated stochastic bilevel optimization has attracted increasing attention due to its wide range of applications in machine learning. To reduce the computational overhead associated with second-order Hessian and Jacobian matrices, several first-order methods have been proposed. However, existing methods typically impose restrictive assumptions on the lower-level function, suffer from a strong dependence on the condition number in their convergence rates, and require different learning-rate scales for variables across the upper- and lower-level problems, limiting their practical applicability and complicating hyperparameter tuning. To address these challenges, we propose a stochastic doubly smoothed gradient method for nonconvex federated stochastic bilevel optimization problems, which decouples the learning rates of upper- and lower-level variables and does not require a strongly-convex lower-level loss function. We establish rigorous theoretical guarantees for the proposed algorithm, demonstrating an improved convergence rate of

O(κ^{15/2}/ε^5)

and a communication complexity of

O(κ^{4}/ε^3)

, where

κ

denotes the condition number and

ε

represents the solution accuracy. Notably, these bounds exhibit significantly better dependence on the condition number

κ

than those of existing methods. Extensive experiments validate the effectiveness of our algorithm.

Xinwen Zhang, Peiran Yu, Zhaosong Lu +1

Temple University · University of Texas at Arlington · University of Minnesota

Gradient Descent Nonconvex Stochastic Optimization Bilevel Optimization Stochastic Optimization Convergence

Oct 1, 2026math.OC

Convergence Analysis of STORM Under Different Geometries

Stochastic recursive momentum (STORM) achieves fast convergence for nonconvex optimization via the variance reduction effect, but existing analyses rely on the strong average smoothness assumption. In this paper, we study the convergence of STORM for different objectives without average smoothness. We first revisit the results under average smoothness, obtaining the

O(T^{-1/3})

bound for nonconvex objectives and the

O(σ^2/(μT))

bound for last-iterate output under the

μ

-Polyak--Łojasiewicz~(PL) condition. Without average smoothness, we design an auxiliary sequence and compare the STORM update with it in the analysis. With the help of this sequence, we prove that STORM still attains an

O(T^{-1/4})

rate for nonconvex objectives, which is optimal under standard smoothness. For convex and

λ

-strongly convex objectives, we further prove averaged and last-iterate bounds with optimal rates of

O(σR/\sqrt T)

and

O(σ^2/(λT))

, respectively. All the obtained results use the same STORM recursion with different hyperparameter choices.

Wei Jiang, Yibo Wang, Wenhao Yang +3

School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

Stochastic Optimization Last-Iterate Convergence Optimization Convergence Analysis Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Oct 1, 2026math.OC

Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization

This paper investigates stochastic multi-level optimization where the objective is a nested composition of several smooth non-convex functions. We assume that only stochastic estimates of the gradient and function values for each level are accessible. Consequently, obtaining an accurate estimate of the overall gradient is challenging due to the nested structure. To address this, we employ a momentum-based estimator with mini-batches to track the function values of each level, which are subsequently used to construct momentum gradient estimators. We establish an optimal sample complexity of

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

for finding an

ε

-stationary point, avoiding the stronger average smoothness assumption commonly relied upon in prior literature. Furthermore, by employing a normalization technique, we attain the same rate without requiring problem-dependent constants to set hyperparameters. To achieve the optimal rate without mini-batches, we further develop a batch-free method that incorporates a first-order approximation and a clipping technique for function value estimation. Finally, we validate the effectiveness of our proposed methods through experiments on risk-averse portfolio optimization and hierarchical tilted empirical risk minimization.

Wei Jiang, Rui Yan, Sifan Yang +3

School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China

Stochastic Optimization Momentum Methods Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Sep 30, 2026cs.LG

Exact information accounting for SGD methods

As an alternative to the standard geometric analyses, we give an exact, information-theoretic analysis of stochastic gradient descent (SGD) and its variants. We show that a preconditioned SGD step is the posterior-mean update of a Gaussian Bayes model, and that its one-step regret splits into an intrinsic-time cost and a change in comparator information. The split extends to an identity for the objective itself. Convex convergence, strict-saddle-point escape, the link between flatness and generalization, the standard learning-rate schedules, adaptive optimizers, and the noisy, momentum, heavy-tailed, and gradient-free variants of SGD each correspond to a term or a special case of this identity. We measure its terms on synthetic and real training runs. On real networks it attributes the slack of classical convergence bounds to the terms their derivations drop and separates optimizers that reach the same training loss. That separation follows the number and consistency of their steps. Its relation to which of them generalizes better differs between networks. For gradient-free SGD the identity determines how a curvature preconditioner should enter the update. The sharpness-based generalization certificate it yields, with a data-independent isotropic prior, is vacuous at network scale unless the curvature spectrum is nearly flat across all parameters.

Akshay Balsubramani

Neural Network Generalization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Sep 30, 2026cs.LG

Convergence of Practical Muon with Finite Newton-Schulz Iterations and Nesterov Momentum

Practical Muon maintains momentum and performs a small, fixed number of Newton--Schulz iterations separately for each parameter matrix, often with a Nesterov correction. We analyze these layer-wise finite-step updates jointly on a coupled nonconvex objective, rather than replacing them by exact polar factors or one global orthogonalization. Under gradient-dependent

(\mathcal L_0,\mathcal L_1,q)

-smoothness and conditionally unbiased stochastic gradients with bounded layer-wise variance, we establish an

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

bound on the expected average Frobenius gradient norm. The analysis retains the Nesterov recursion and requires neither bounded stochastic gradients, symmetric noise, nor a uniform positive lower bound on the nonzero output singular values. Its constants contain no explicit matrix-dimension or rank factors when the number of blocks and problem constants are fixed. The proof follows a descent inequality and a decomposition of the momentum tracking error into initialization, noise, and drift. For the original five-step quintic, we verify the required scalar-map bounds analytically; the result also allows step-dependent coefficients satisfying the same bounds. A complementary nuclear-norm result quantifies rank dependence under a stronger spectral condition. The vanishing rate uses coupled learning-rate and momentum schedules, including the standard single-coefficient Nesterov rule.

Hanyng Peng, Hui Wang, Yue Yu

Pengcheng Laboratory, Shenzhen, China

Newton-Schulz Iteration Gradient Descent Nonconvex Stochastic Optimization Muon Optimizer Stochastic Optimization Convergence

Sep 29, 2026math.OC

Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-ES, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating subspace preconditioning with ellipsoidal randomized sampling. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-ES performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner

\hatΣ

that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where

λ_{\max}(\hatΣ) = 1

, we introduce the use of the empirical effective dimension

d^* = \operatorname{tr}(\hatΣ)

, which reflects the intrinsic dimensionality of the problem and guides both the sampling and randomized smoothing parameter schedules. In practice, such a preconditioner can be effectively obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge. We prove that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only

\tilde{\mathcal{O}}\left( \frac{\left( r^2 κ(\hatΣ) + d^* \right) L^2 D_{\mathcal{X}}^2}{\varepsilon^2} \right)

stochastic zeroth-order oracle queries. The method remains fully parameter-free and demonstrates significant improvements over the original POEM in problems with low-rank structure where

d^* \ll d

. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.

Alexander Sholokhov, Alexander Rogozin

Moscow Institute of Physics and Technology, Russia

Zeroth-Order Optimization Covariance Matrix Adaptation Evolution Strategy Stochastic Optimization Convergence

Sep 29, 2026cs.AI

Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients

Adam is widely observed to remain stable even when the objective deviates significantly from global smoothness. Under the generalized smoothness framework, however, existing analyses rely on strong tail assumptions on the stochastic gradients, such as almost-sure boundedness or sub-Gaussianity. Whether Adam converges on generalized smooth objectives under only second moment information on the stochastic gradients, without such concentration assumptions, was identified as an important open direction by Li et al. (2023). This paper gives an affirmative answer under fairly general conditions: such tail assumptions are not necessary. Building on the Adam self-normalization framework of Jin et al. (2026), developed for classical smoothness and bounded variance, we extend the stopping-time and de-preconditioning strategy to the

L_0

-

L_p

generalized smoothness condition and a generalized second moment ABC condition. Even when the stochastic-gradient condition provides only second moment information that may grow along the trajectory, the stochastic trajectory of Adam remains in a locally well-behaved smoothness region, with stretched-exponential tail decay under bounded variance and global smoothness. Consequently, we establish high-probability convergence rate guarantees over the full range

p<2

, with confidence dependence of order

δ^{-1/2}

, while the stepsize prefactor depends on

δ

only through a single logarithmic factor. We further construct a hard instance showing that, under only second-moment information, this

δ^{-1/2}

-type confidence dependence is sharp. Finally, in the regime

p<1

, we combine the trajectory control with polynomial-growth estimates on rare events to obtain convergence rate guarantees in expectation.

Ruinan Jin, Difei Cheng, Ling Chen +3

Mohamed bin Zayed University of Artificial Intelligence · Aerospace Information Technology University · The Ohio State University +2

Convergence Analysis Stochastic Optimization Convergence Adaptive Gradient Methods

Sep 29, 2026math.OC

Second-Moment Stochastic Approximation Methods

Classical stochastic approximation methods rely on estimators of the first moment (mean) of a random regression function. We study methods that employ estimators of both the first and the second moments, which include modern deep-learning optimizers such as Adam and Muon as special cases. We derive second-moment stochastic approximation methods through the lens of optimal preconditioning for solving matrix equations, and develop a two-stage framework for their convergence analysis. The first stage focuses on the analysis of conceptual (impractical) methods that rely on the exact first and second moments. In the second stage, we replace the exact moments with their respective estimators, and invoke Dvoretzky's theorem to show that the resulting practical methods converge almost surely to a neighborhood of the target solution. The size of the neighborhood depends on the biases and variances of the first- and second-moment estimators. We derive concrete bounds for Muon and a spectral variant of Adam that determine the radius of their neighborhood of convergence.

Tao Jiang, Lin Xiao

Fundamental AI Research (FAIR), Meta Superintelligence Labs

Stochastic Approximation Muon Optimizer Stochastic Optimization Convergence Adaptive Gradient Methods

Sep 24, 2026stat.ML

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

Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields

T^{-1/3}

expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the

Lb_2Δ^3\varepsilon^{-6}

and

LΔσ^2\varepsilon^{-4}

stochastic terms, where

Δ

is the initial objective gap and

σ^2+b_2\|x-x_1\|^2

bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For

p>2

, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-

T

stationarity, and stochastic

L^p

-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.

Wei Biao Wu

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

Sep 24, 2026cs.LG

A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning

Many iterative algorithms rely on bootstrapping. A variable is updated using a second, frozen copy as a target, which is periodically replaced with the updated variable. Majorize-minimize and inexact proximal-point methods share this structure, as does temporal-difference (TD) learning. However, existing convergence guarantees for scenarios that combine sampled updates with targets refreshed only every

K

steps rely on the specific structure of the update, such as linear approximation or gradient-based inner steps, and on uniformly bounded sampling error. We instead model the sampled update as a stochastic operator on the parameter space, which reduces the analysis to a contraction argument that needs no gradient structure and allows the sampling error to grow with the iterates. Within this framework, we derive a finite-time bound for i.i.d. samples and any target-update period

K

. We show that the iterates converge geometrically in root mean square to a ball around the fixed point, provided the sensitivity to the frozen target is smaller than the contraction slack of the inner map. Existing deterministic frozen-target contraction and stochastic-gradient-type bounds follow as special cases of our framework, and simulations of TD learning reproduce the predicted contraction rate and scaling of the error floor with the step size.

Ids van der Werf, Sergio Rozada, Antonio G. Marques

Delft University of Technology, Dep. Microelectronics, Delft, The Netherlands

Stochastic Approximation Temporal-Difference Learning Stochastic Optimization Convergence

Sep 24, 2026cs.LG

Precise Convergence Speed of Clipped SGD

We present a tightened convergence analysis of clipped gradient descent on

(L_0, L_1)

-smooth functions, with quantitative constants. Building on the ideas of Koloskova et al (2023), we refactor several case disjunctions to reveal the central role of a control of the bias derived from fundamental properties of

\ell_2

-projection, simplifying proofs. We also extend the domain of validity from

η\leq 1 / (9 β)

to

η< 1 /β

where

β= L_0 + c L_1

for clipping constant

c

, which matches the more traditional analysis of smooth functions. We strengthen the convergence criterion from

\left( \min_{t < T} \mathbb{E}[\lVert \nabla f(x_t) \rVert_2] \right)

to

\left( \frac{1}{T} \sum_{t < T} \mathbb{E}[\lVert \nabla f(x_t) \rVert_2] \right)

with matching speed, and lower the final achievable loss from

\mathcal{O}(\min(σ^2/c, σ))

to the more precise

6 \min(σ^2 /c, 3 σ)

.

David A. R. Robin

LAMSADE, Université Paris-Dauphine, PSL Research University

Gradient Clipping Nonconvex Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent

Sep 16, 2026math.OC

Gradient Descent with Stochastic Subspaces via Persistence of Memory

Stochastic subspace methods have gained popularity as gradient descent based techniques for large scale optimisation problems, especially in distributed settings. In this paper, we introduce the technique of "persistence of memory" to greatly extend and improve the random subspace methods. To this end, we leverage a vector that is only weakly correlated with the gradient in order to provide a guiding structure to the generative process of the random subspace along which the descent is going to take place. This guidance vector may be fixed for a large number of iterations, only to be refreshed at wide intervals (on whose size we can provide guarantees in terms of problem parameters). In important machine learning settings, such as optimisation problems embodying sparsity or a minibatch structure, we show that the guidance vector can be obtained in an effective and computationally inexpensive manner by leveraging the structured properties of the problem. En route, we establish to our knowledge the first theoretical analysis of classical SSD methods for sparse functions. In a local neighbourhood of the optimum, we demonstrate an alignment phenomenon of our gradient estimates with a low-lying eigenvector of the Hessian, allowing a once-for-all computation of the guidance vector which renders the method computationally favourable even in scenarios with unstructured objectives.

Subhroshekhar Ghosh, Clement Z. Q. Ng, Pierre-Louis Poirion +1

Department of Mathematics, National University of Singapore, Singapore · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan · Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan

Gradient Descent Stochastic Optimization Convergence

Sep 15, 2026math.OC

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.

Alexander Tyurin

AXXX, Moscow, Russia · Applied AI Institute, Moscow, Russia

Distributed Optimization Stochastic Optimization Convergence

Sep 15, 2026cs.LG

Same Flow, Different Paths: Variance Reduction in Flow Matching

In flow matching (FM), a velocity model

v_θ

is trained using a predefined path

g_t

that connects data and noise samples (e.g.,

g_t(x_0, x_1) = (1 - t) x_0 + t x_1

). In this work, we study the choice of this path from an optimization perspective by analyzing the variance of stochastic gradients. We consider the class

G(p_t,v^\star_t)

of paths that induce the same marginal distributions

p_t

and marginal velocity field

v^\star_t

, and therefore the same FM objective. Our main finding is that the choice of path

g_t

can fundamentally change the convergence rate of SGD, even when the FM objective remains exactly the same. (i) For a linear velocity model and one-dimensional Gaussian data, we derive a tight bound on the SGD iteration complexity up to logarithmic factors and find an analytically optimal path that minimizes this bound among linear paths inducing the same FM problem. (ii) We then extend the variance analysis to general FM problems and formulate path selection at a fixed

θ

as the variance-minimization problem PathOpt

_θ

, constrained to

g_t\in G(p_t,v^\star_t)

. We show that this constraint is essential: reducing variance without it can lead to slower convergence. (iii) Since the constraint

g_t \in G(p_t,v^\star_t)

cannot generally be verified directly, we derive an equivalent formulation with constraints that can be estimated from samples, allowing paths to be found numerically. Our theoretical results are supported by experiments with Gaussian data, Gaussian mixture models, and real datasets.

Alexander Tyurin

AXXX, Moscow, Russia · Applied AI Institute, Moscow, Russia

Flow Matching Stochastic Optimization Convergence Flow-Based Generative Modeling Variance Reduction Stochastic Gradient Descent

Sep 14, 2026cs.LG

How I learned to stop worrying and love StopGrads: Stationarity, Convergence, and a case study on Flow Map Learning

Stopgrads are widely used in training machine learning models, but stopgrads can alter the gradient, stationary points and convergence guarantees of the original objective, which can make stopgrad training theoretically ungrounded. We introduce a stopgrad regression principle, which identifies a general template for stopgrad objectives with a closed-form characterization of stationary points and their uniqueness, unifying stopgrad objectives for flow maps, reinforcement learning, and diffusion samplers. We provide theoretical grounding for optimizing stopgrad flow map objectives by showing their unique stationary point is the true flow map, and showing positive convergence results for Eulerian and Lagrangian objectives, including MeanFlow and improved MeanFlow. Remarkably, we show that under functional semi-gradient flow, the learned flow map has a closed-form expression composing the initial flow map and the true flow map. We additionally use our stopgrad regression principle to propose modified stopgrad placements for flow map objectives which reduce training memory by 2x.

Max W. Shen, Mark Goldstein, Zichu Wang +2

Flatiron Institute · NYU

Flow Map Learning Stochastic Optimization Convergence Gradient Descent Dynamics

Sep 14, 2026math.OC

High-Probability Convergence of SGD via Batched Updates

Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.

Feng Zhu, Robert W. Heath Jr., Aritra Mitra

Communication-Efficient Distributed Training Stochastic Optimization Convergence Federated Learning Heterogeneous Federated Learning Stochastic Gradient Descent

Sep 14, 2026cs.LG

Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent

We study loss-based filtering for finite-sum optimization with a subset of corrupted component functions whose gradients may be highly unreliable. Motivated by minimum-loss-based SGD (min-

k

-loss) and quantile-based methods for corrupted linear systems, we propose and analyze a general loss-filtering framework -- Quantile-

k

-Loss SGD (Q

k

L-SGD) -- that samples

k

component losses at each iteration and updates using an index chosen uniformly from the lower empirical

q

-quantile. We prove linear convergence of this family of methods under standard convexity assumptions, requiring the sample size to scale with the number of corruptions and a subset strong-convexity threshold. For the cases when large enough sampling is impossible or undesirable, we give a complementary small-sample probabilistic analysis that covers any sample size

k

and the convergence behavior depends on the probability of selecting an outlier and on the curvature of the selected good step. Experiments on polynomial regression, regularized logistic regression, and regularized hinge loss show that intermediate quantiles often outperform both standard SGD and min-

k

-loss SGD. In particular, min-

k

often stalls by repeatedly selecting nearly solved components, while intermediate quantiles retain robustness and produce more informative updates.

Jamie Haddock, Anna Ma, Elizaveta Rebrova

Department of Mathematics, Harvey Mudd College, Claremont, CA 91711-3116, USA. · Department of Mathematics, University of California, Irvine, CA 92617, USA. · Mathematical Institute, University of Oxford, Oxford, OX1 2JD, UK.

Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent

Sep 10, 2026cs.LG

Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise

Stochastic gradient descent (SGD) with gradient clipping and additive noise has become a standard technique for training machine learning models, particularly in applications requiring robustness or privacy guarantees. However, clipping introduces a bias in stochastic gradients, while additive noise introduces additional variance, making the long-run behaviour of individual optimization trajectories difficult to characterize. In this work, we prove that SGD with clipping and additive Gaussian noise (SGD-CN) converges almost surely (a.s.) under smoothness and uniformly bounded stochastic-gradient noise assumptions, provided the step sizes satisfy some standard decaying conditions. Our analysis extends to momentum variants such as the stochastic heavy ball and Nesterov's accelerated gradient, where we show that careful energy constructions yield similar guarantees. These results provide stronger theoretical foundations for understanding the pathwise behaviour of clipped stochastic gradient methods and suggest that, despite the bias and noise introduced by clipping and perturbation, the algorithm remains stable in both convex and nonconvex regimes.

Amartya Mukherjee, Jun Liu

Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Stochastic Optimization Gradient Clipping Stochastic Optimization Convergence Stochastic Gradient Descent

Sep 8, 2026math.OC

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to

\sqrt{\log n / n}

but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence

h

satisfying

h(n) = o(\sqrt{n})

, a bound of order

h(n)/\sqrt{n}

, holding simultaneously for all

n

with probability at least

1-α

and uniformly over the problem class, is achievable if and only if

\sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty.

The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.

Ruijie Li, Kang Chen, Tianyu Wang

School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University

Learning Rate Scheduling Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Stochastic Gradient Descent

Sep 8, 2026math.OC

How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than

\varepsilon

is

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

, compared to the near-optimal

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

that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to

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

. We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.

Ahmet Alacaoglu

Department of Mathematics, University of British Columbia

Stochastic Optimization Min-Max Optimization Stochastic Optimization Convergence

Aug 31, 2026cs.LG

Convergence rates for the RMSprop optimizer with full control of the hyperparameters

Popular adaptive stochastic gradient descent (SGD) methods to train artificial intelligence (AI) systems include the RMSprop, the Adam, and the AdamW optimizers, where the adaptivity parts in Adam and AdamW basically just coincide with RMSprop. Such adaptive methods involve several hyperparameters including the regularization parameter

ε

(which ensures that one does not divide by 0 and is often chosen to be very close to zero such as

10^{-8}

in PyTorch by default) and the second moment decay parameter

β

(which is often chosen to be very close to

1

such as 0.99 (RMSprop) and 0.999 (Adam and AdamW) in PyTorch by default). Despite the high relevance of such methods, it remains an open research problem to provide error estimates for such methods with the error constants being not exploding but uniformly bounded with the respect to the hyperparameters, even in the situation of convex stochastic optimization problems. It is the key contribution of this work to essentially solve this problem for RMSprop. Specifically, we bound the expectation of the stopped evaluation of the objective function at the RMSprop process from above by the sum of an initialization term that decays exponentially in the training time, a stochastic approximation remainder of order

γ_n

, and a memory error of order

( 1 - β)^2

with the error constants being uniformly controlled over all admissible choices of the step sizes, the second moment decay parameter

β

and the regularization parameter

ε\in[0,1]

(also covering

ε=0

). Our non-asymptotic error estimates hold not just for all sufficiently large n but hold for every gradient step

n=1,2,3,...

with all error constants being explicitly specified. The key innovative new feature in the proof of our analysis are suitable inverse moment bounds for the second moment process in RMSprop.

Steffen Dereich, Arnulf Jentzen

Stochastic Approximation Stochastic Optimization Convergence Adaptive Gradient Methods

Aug 10, 2026math.OC

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the

K=1

fresh-sample model, every randomized adaptive algorithm requires

Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)

queries to find a point with expected gradient norm at most

ε

. This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

Jikai Jin

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Aug 7, 2026stat.ML

Optimized Certainty Equivalent Risk Minimization Using Samples: Algorithms, Convergence Rates, and Applications

We consider the optimization of the Optimized Certainty Equivalent (OCE) risk, with applications including portfolio optimization in finance, and uncertainty quantification, classification, and regression in machine learning. Our contributions cover popular special cases of OCE, such as entropic risk, mean-variance risk, and smooth variants of Conditional Value-at-Risk. Our treatment sets out the conditions that facilitate the extension of OCE to unbounded r.v.s.. We provide a useful characterization of OCE that links OCE to utility-based shortfall risk (UBSR). Our characterization enables us to form an OCE estimator from the classic sample-average approximation (SAA) of UBSR. We derive mean-squared error (MSE) bounds for our proposed OCE estimator. For OCE optimization, we first derive an expression for the OCE gradient using the characterization linking OCE to UBSR. This expression serves as the basis for a gradient estimator for the OCE. We derive non-asymptotic bounds on the MSE for the proposed OCE gradient estimator. We incorporate the aforementioned gradient estimator into a stochastic gradient (SG) algorithm to optimize OCE and quantify its convergence rate using non-asymptotic bounds that we derive. Finally, we present three experiments that use our OCE optimization algorithm to solve portfolio optimization and uncertainty quantification problems.

Sumedh Gupte, Prashanth L. A., Sanjay P. Bhat

TCS Research, IIIT-H Research Park, Hyderabad, 500032, India · Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, 600036, India

Stochastic Optimization Convergence Portfolio Optimization Decision-Making under Uncertainty

Aug 6, 2026math.OC

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.

TaeHo Yoon, Nicolas Loizou

Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University.

Stochastic Optimization Last-Iterate Convergence Stochastic Optimization Convergence

Aug 5, 2026math.OC

A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition

This work introduces a proximal stochastic subgradient method for minimizing the sum of an expected cost, whose integrand is potentially nonsmooth and nonconvex, and a lower semicontinuous, prox-bounded function. We target a broad class of integrands obeying a nonsmooth, localized variant of the descent lemma in the decision variable, a structural assumption that simultaneously covers smooth losses with Lipschitz gradient and differences of such losses with convex functions. At each iteration the expected cost is replaced by a sample average that is progressively refined, and the proximal-subgradient stepsize is selected by an Armijo-type line search enforcing a sufficient-decrease property up to stochastic errors induced by the sample-based approximation. This framework accommodates substantially more general problem formulations than existing methods, in particular, it requires neither (weak) convexity of the regularizer nor a uniform bound on the variance of the stochastic oracle, and our analysis yields convergence guarantees that are new even in the smooth setting. Specifically, we establish almost sure convergence of the sequence of function values and stationarity of every accumulation point of the trajectories under the relaxed requirement that the sample-size sequence be merely nondecreasing and unbounded, with no prescribed growth rate. Leveraging the Kurdyka-Lojasiewicz (KL) property, we further upgrade this subsequential guarantee to convergence of the whole trajectory to a single stationary point. Finally, for exponential-type KL desingularizing functions and polynomially growing sample sizes, we derive explicit polynomial convergence rates, up to a logarithmic factor, for both the function values and the iterates.

Felipe Atenas, Alejandro Jofré, Pedro Pérez-Aros +1

Centro de Modelamiento Matem´atico (CNRS IRL2807), Universidad de Chile, Santiago, Chile · Departamento de Ingenier´ıa Matem´atica and Centro de Modelamiento Matem´atico (CNRS IRL2807), Universidad de Chile, Santiago, Chile · Department of Mathematics, University of Alicante, Alicante, Spain

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Aug 5, 2026math.OC

On MUON optimization: From non-convergence to an error analysis with Polar Express and the Newton-Schulz polynomial from implementations

Stochastic gradient descent (SGD) optimization methods are the standard instruments for the training of deep neural networks (DNNs). In many relevant artificial intelligence (AI) systems - such as popular large language models (LLMs)-not the standard SGD scheme is used as the optimization method but instead suitable accelerated variants of SGD are employed. One of the most popular methods of such accelerated SGD variants is the momentum orthogonalized by Newton-Schulz (MUON) optimizer proposed by Jordan et al. in 2024. The MUON optimizer exploits the special matrix structure of the weight parameters in the training of the DNNs and, in its original form, employs five Newton-Schultz (NS) matrix steps in each MUON iteration. In this work we propose and study a generalized variant of the MUON optimizer involving an arbitrary number of generalized NS steps with polynomials of possibly arbitrary high degree. The considered optimizer covers MUON with the original NS polynomial as well as MUON combined with the recently proposed Polar Express method as special cases. For a simple class of stochastic optimization problems (SOPs) we show for almost every mini-batch size that MUON fails to converge to the solution of the SOP as the number of gradient steps converges to infinity. We also establish an error analysis for MUON with the generalized NS steps that provides convergence rates in terms of the number of gradient steps and in terms of the size of the mini-batch. We illustrate our general error analysis for MUON in the case of several concrete examples including quadratic stochastic optimization problems (SOPs) as well as

\ell_2

regularized logistic regression for binary classification.

Thang Do, Steffen Dereich, Arnulf Jentzen

School of Data Science, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China · Department of Probability and Statistics, Institute of Mathematics, Vietnam Academy of Science and Technology, Vietnam · Institute for Mathematical Stochastics, Faculty of Mathematics and Computer Science, University of Münster, Germany +2

Stochastic Optimization Newton-Schulz Iteration Muon Optimizer Second-Order Optimization Stochastic Optimization Convergence Accelerated Gradient Methods

Aug 3, 2026stat.ML

Particle-based Generalised Stochastic Optimisation

We develop a class of diffusion-based stochastic particle optimisation methods for loss functions with intractable gradients. Specifically, we consider problems in which the loss gradient is an integral with respect to a parameter-dependent distribution, a structure that includes training generative models, fine-tuning, and learning latent-variable models. We introduce mean-field dynamics and its interacting-particle approximations, which contain several existing algorithms as special cases and provides a route to constructing new methods. Under well-posedness and joint contractivity assumptions, we prove exponential convergence and show that the continuous-time particle system admits a non-asymptotic error bound. We illustrate it by developing momentum and higher-order Langevin variants and evaluating them on maximum marginal-likelihood estimation and energy-based-model training.

Jiechen Jackie Zhang, O. Deniz Akyildiz

Department of Mathematics, Imperial College London

Stochastic Optimization Langevin Dynamics Stochastic Optimization Convergence