Stochastic Optimization Convergence

Follow this topic Ask about this topic

The field asks when algorithms that use random samples, approximate gradients, or delayed updates reach a solution or a stationary point, and how their error depends on computation and noise. Researchers analyze stochastic gradient descent and its momentum and adaptive variants alongside variance reduction, clipping, proximal and mirror methods, and second-order updates. Results cover convex and nonconvex learning as well as distributed, federated, bilevel, and reinforcement-learning settings, with guarantees often expressed as convergence rates or sample and communication complexity. A central challenge is to obtain sharp guarantees under realistic heavy-tailed or dependent noise without assumptions that exclude practical optimizers or obscure their failures.

Latest papers

212 papers28 papers in the last four weeks, up 22% on the four weeks before. 0.2% of all new papers.

Apr 28, 2026

Enhancing SignSGD: Small-Batch Convergence Analysis and a Hybrid Switching Strategy

SignSGD compresses each stochastic gradient coordinate to a single bit, offering substantial memory and communication savings, but its 1-bit quantization removes magnitude information and is known to leave a generalization gap relative to well-tuned SGD. We revisit SignSGD from a 1-bit quantization and dithering perspective and contribute three improvements. First, we derive a small-batch convergence rate for SignSGD under unimodal symmetric gradient noise using a signal-to-noise weighted stationarity measure, removing the large-batch assumption of prior analyses. Second, we inject annealed Gaussian noise before the sign operator, which acts as a classical dithering mechanism and probabilistically restores magnitude information lost to hard thresholding. Third, we adapt the SWATS strategy to sign-based updates with a projection-based learning-rate calibration that smoothly transitions from SignSGD to SGD. Single-worker experiments on ResNet-18 isolate optimizer effects from communication aspects: pre-sign dithering surpasses Adam on CIFAR-100, and the calibrated switch reaches 92.18% test accuracy on CIFAR-10, outperforming both pure SGD 91.38% and pure SignSGD with momentum 90.82%.

Haoran Chen, Wentao Wang

´Ecole polytechnique Palaiseau, France

Sign-Based Optimization Stochastic Optimization Convergence Gradient Quantization Stochastic Gradient Descent

Apr 28, 2026

From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability

While it is generally understood that zeroth-order (ZO) algorithms have an extra dependency on their number of iterations for any choice of parameters, compared to their first-order (FO) counterparts, in this work, we show that under several conditions, in expectation, ZO methods do not suffer from extra dimension dependencies in their convergence rates with respect to their FO counterparts. We look at optimisation algorithms from the dynamical systems perspective and analyse the conditions under which one can formulate the average of a ZO algorithm as the average of its FO counterpart with bounded perturbations with values dependent on design parameters. Then, using input-to-state stability properties, we show ZO methods follow the same decay rate as their FO counterparts and converge to a neighbourhood of the fixed point of FO methods, where its radius depends on the bound of the norm of the perturbations, which can be made arbitrarily small. The theoretical findings are illustrated via numerical examples.

Amir Ali Farzin, Philipp Braun, Iman Shames

School of Engineering · Australian National University · Canberra, ACT 2601 +3

Zeroth-Order Optimization Stochastic Optimization Convergence Input-to-State Stability

Apr 24, 2026

Complex Stochastic Gradient Descent and Directional Bias in Reproducing Kernel Hilbert Spaces

Stochastic Gradient Descent (SGD) is a known stochastic iterative method popular for large-scale convex optimization problems due to its simple implementation and scalability. Some objectives, such as those found in complex-valued neural networks, benefit from updates like in SGD and Gradient Descent (GD) with a newly defined ``gradient'' that allows for complex parameters. This complex variant of the SGD/GD methods has already been proposed, but convergence guarantees without analyticity constraints have not yet been provided. We propose a variant of SGD (complex SGD) that allows for complex parameters, and we provide convergence guarantees under assumptions that parallel those from the real setting. Notably, these results extend to GD as well, and with the same set of assumptions, we confirm that some directional bias results extend from the real to the complex setting for kernel regression problems. We provide empirical results demonstrating the efficacy of the complex SGD in kernel regression problems utilizing complex reproducing kernel Hilbert spaces. In particular, we demonstrate we may recover superoscillation functions and Blaschke products from the Fock Space and Hardy Space, respectively, as the optimal functions for a particular choice of a loss function.

Natanael Alpay, Emeric Battaglia

Kernel Regression Reproducing Kernel Hilbert Spaces Kernel Methods Stochastic Optimization Convergence Stochastic Gradient Descent

Apr 19, 2026

A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muo

A unified framework for first-order optimization algorithms fornonconvex unconstrained optimization is proposed that uses adaptivelypreconditioned gradients and includes popular methods such as full anddiagonal AdaGrad, AdaNorm, as well as adpative variants of Shampoo andMuon. This framework also allows combining heterogeneous geometriesacross different groups of variables while preserving a unifiedconvergence analysis. A fully stochastic global rate-of-convergenceanalysis is conducted for all methods in the framework, with andwithout two types of momentum, using reasonable assumptions on thevariance of the gradient oracle and without assuming boundedstochastic gradients or small enough stepsize.

S. Gratton, Ph. L. Toint

Université de Toulouse, INP, IRIT, Toulouse, France. · Université de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium.

Momentum Methods Nonconvex Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

Apr 17, 2026

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Analysis of Stochastic Gradient Descent (SGD) and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, as well as in several elementary optimization settings. While several relaxations are explored in the literature, the Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an

ε

-stationary point requires

Ω(ε^{-6})

stochastic BG-0 oracle queries for smooth functions and

Ω(ε^{-4})

queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e.,

Ω(ε^{-4})

and

Ω(ε^{-3})

for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework that couples Halpern anchoring with Tikhonov regularization to dynamically mitigate the extra variance explosion term permitted by the BG-0 oracle. We prove that PASTA achieves minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.

Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1

School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

Stochastic Optimization Oracle Complexity Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Apr 16, 2026

StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models

Sign-based optimization algorithms, such as SignSGD, have garnered significant attention for their remarkable performance in distributed learning and training large foundation models. Despite their empirical superiority, SignSGD is known to diverge on non-smooth objectives, which are ubiquitous in modern machine learning due to ReLUs, max-pools, and mixture-of-experts. To overcome this fundamental limitation, we propose StoSignSGD, an algorithm that injects structural stochasticity into the sign operator while maintaining an unbiased update step. In the regime of (online) convex optimization, our theoretical analysis shows that StoSignSGD rigorously resolves the non-convergence issues of SignSGD, achieving a sharp convergence rate matching the lower bound. For the more challenging non-convex non-smooth optimization, we introduce generalized stationary measures that encompass prior definitions, proving that StoSignSGD improves upon the best-known complexity bounds by dimensional factors. Empirically, StoSignSGD exhibits robust stability and superior efficiency across diverse large language model (LLM) training regimes. Notably, in low-precision FP8 pretraining -- a setting where AdamW fails catastrophically -- StoSignSGD remains highly stable and yields a remarkable 1.44

\times

to 2.14

\times

speedup relative to established baselines. Furthermore, when fine-tuning 7B LLMs on mathematical reasoning tasks, StoSignSGD delivers substantial performance gains over both AdamW and SignSGD. Finally, to dissect the mechanisms driving its success, we develop a sign conversion framework capable of transforming any general optimizer into its unbiased, sign-based counterpart. Utilizing this framework, we deconstruct the core components of StoSignSGD and present a comprehensive ablation study to empirically validate our algorithmic design choices.

Dingzhi Yu, Rui Pan, Yuxing Liu +1

University of Illinois Urbana-Champaign

Stochastic Optimization Sign-Based Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence LLM Training

Apr 11, 2026

Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

From adversarial robustness to multi-agent learning, many machine learning tasks can be cast as finite-sum min-max optimization or, more generally, as variational inequality problems (VIPs). Owing to their simplicity and scalability, stochastic gradient methods with constant step size are widely used, despite the fact that they converge only up to a constant term. Among the many heuristics adopted in practice, two classical techniques have recently attracted attention to mitigate this issue: Random Reshuffling of data and Richardson--Romberg extrapolation across iterates. Random Reshuffling sharpens the mean-squared error (MSE) of the estimated solution, while Richardson-Romberg extrapolation acts orthogonally, providing a second-order reduction in its bias. In this work, we show that their composition is strictly better than both, not only maintaining the enhanced MSE guarantees but also yielding an even greater cubic refinement in the bias. To the best of our knowledge, our work provides the first theoretical guarantees for such a synergy in structured non-monotone VIPs. Our analysis proceeds in two steps: (i) we smooth the discrete noise induced by reshuffling and leverage tools from continuous-state Markov chain theory to establish a novel law of large numbers and a central limit theorem for its iterates; and (ii) we employ spectral tensor techniques to prove that extrapolation debiases and sharpens the asymptotic behavior even under the biased gradient oracle induced by reshuffling. Finally, extensive experiments validate our theory, consistently demonstrating substantial speedups in practice.

Konstantinos Emmanouilidis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Rene Vidal

Department of Computer Science, University of Pennsylvania · University of Wisconsin-Madison, Archimedes Research Unit

Random Reshuffling Richardson Extrapolation Stochastic Optimization Convergence Stochastic Gradient Descent

Apr 7, 2026

Optimal Rates for Pure $\varepsilon$ -Differentially Private Stochastic Convex Optimization with Heavy Tails

We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure

\varepsilon

-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded

k

-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. Prior work characterized the minimax optimal rate for

ρ

-zero-concentrated DP SCO up to logarithmic factors in this setting, but the pure

\varepsilon

-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure

\varepsilon

-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in deterministic polynomial time when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes -- including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes -- we achieve deterministic polynomial time even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our upper bound with a nearly matching high-probability lower bound.

Andrew Lowy

CISPA Helmholtz Center for Information Security

Heavy-Tailed Stochastic Optimization Differential Privacy Stochastic Optimization Convergence

Mar 31, 2026

Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization

Shuffling strategies for stochastic gradient descent (SGD), including incremental gradient, shuffle-once, and random reshuffling, are supported by rigorous convergence analyses for arbitrary within-epoch permutations. In particular, random reshuffling is known to improve optimization constants relative to cyclic and shuffle-once schemes. However, existing theory offers limited guidance on how to design new data-ordering schemes that further improve optimization constants or stability beyond random reshuffling. In this paper, we design a pipeline using a large language model (LLM)-guided program evolution framework to discover an effective shuffling rule for without-replacement SGD. Abstracting from this instance, we identify two fundamental structural components: block reshuffling and paired reversal. We analyze these components separately and show that block reshuffling strictly reduces prefix-gradient variance constants within the unified shuffling framework, yielding provable improvements over random reshuffling under mild conditions. Separately, we show that paired reversal symmetrizes the epoch map and cancels the leading order-dependent second-order term, reducing order sensitivity from quadratic to cubic in the step size. Numerical experiments with the discovered algorithm validate the theory and demonstrate consistent gains over standard shuffling schemes across convex and nonconvex benchmarks.

Lam M. Nguyen, Dzung T. Phan, Jayant Kalagnanam

IBM Research, Thomas J. Watson Research Center, Yorktown Heights, NY, USA

Stochastic Optimization Convergence Stochastic Gradient Descent Random Reshuffling

Mar 31, 2026

Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

We present a finite-time analysis of two smoothed functional stochastic approximation algorithms for simulation-based optimization. The first is a two time-scale gradient-based method, while the second is a three time-scale Newton-based algorithm that estimates both the gradient and the Hessian of the objective function

J

. Both algorithms involve zeroth order estimates for the gradient/Hessian. Although the asymptotic convergence of these algorithms has been established in prior work, finite-time guarantees of two-timescale stochastic optimization algorithms in zeroth order settings have not been provided previously. For our Newton algorithm, we derive mean-squared error bounds for the Hessian estimator and establish a finite-time bound on

\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2

, showing convergence to first-order stationary points. The analysis explicitly characterizes the interaction between multiple time-scales and the propagation of estimation errors. We further identify step-size choices that balance dominant error terms and achieve near-optimal convergence rates. We also provide corresponding finite-time guarantees for the gradient algorithm under the same framework. The theoretical results are further validated through experiments on the Continuous Mountain Car environment.

Kaustubh Kartikey, Shalabh Bhatnagar

Stochastic Optimization Stochastic Optimization Convergence Two-Timescale Stochastic Approximation Second-Order Optimization Zeroth-Order Optimization

Mar 30, 2026

Gradient Manipulation in Distributed Stochastic Gradient Descent with Strategic Agents: Truthful Incentives with Convergence Guarantees

Distributed learning has gained significant attention due to its advantages in scalability, privacy, and fault tolerance.In this paradigm, multiple agents collaboratively train a global model by exchanging parameters only with their neighbors. However, a key vulnerability of existing distributed learning approaches is their implicit assumption that all agents behave honestly during gradient updates. In real-world scenarios, this assumption often breaks down, as selfish or strategic agents may be incentivized to manipulate gradients for personal gain, ultimately compromising the final learning outcome. In this work, we propose a fully distributed payment mechanism that, for the first time, guarantees both truthful behaviors and accurate convergence in distributed stochastic gradient descent. This represents a significant advancement, as it overcomes two major limitations of existing truthfulness mechanisms for collaborative learning:(1) reliance on a centralized server for payment collection, and (2) sacrificing convergence accuracy to guarantee truthfulness. In addition to characterizing the convergence rate under general convex and strongly convex conditions, we also prove that our approach guarantees the cumulative gain that an agent can obtain through strategic behavior remains finite, even as the number of iterations approaches infinity--a property unattainable by most existing truthfulness mechanisms. Our experimental results on standard machine learning tasks, evaluated on benchmark datasets, confirm the effectiveness of the proposed approach.

Ziqin Chen, Yongqiang Wang

Department of Electrical and Computer Engineering, Clemson University, Clemson, SC 29634 USA

Distributed Training Decentralized Learning Distributed Optimization Stochastic Optimization Convergence

Mar 27, 2026

Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

Synchronous federated learning scales poorly due to the straggler effect. Asynchronous algorithms increase the update throughput by processing updates upon arrival, but they introduce two fundamental challenges: gradient staleness, which degrades convergence, and bias toward faster clients under heterogeneous data distributions. Although algorithms such as AsyncSGD and Generalized AsyncSGD mitigate this bias via client-side task queues, most existing analyses neglect the underlying queueing dynamics and lack closed-form characterizations of the update throughput and gradient staleness. To close this gap, we develop a stochastic queueing-network framework for Generalized AsyncSGD that jointly models random computation times at the clients and the central server, as well as random uplink and downlink communication delays. Leveraging product-form network theory, we derive a closed-form expression for the update throughput, alongside closed-form upper bounds for both the communication round complexity and the expected wall-clock time required to reach an

ε

-stationary point. These results formally characterize the trade-off between gradient staleness and wall-clock convergence speed. We further extend the framework to quantify energy consumption under stochastic timing, revealing an additional trade-off between convergence speed and energy efficiency. Building on these analytical results, we propose gradient-based optimization strategies to jointly optimize routing and concurrency. Experiments on EMNIST demonstrate reductions of 29%--46% in convergence time and 36%--49% in energy consumption compared to AsyncSGD.

Abdelkrim Alahyane, Céline Comte, Matthieu Jonckheere

LAAS-SARA · EMINES, Mohammed VI Polytechnic University, Ben Guerir, Morocco · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France +1

Asynchronous Federated Learning Federated Learning Stochastic Optimization Convergence

Mar 23, 2026

RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation

A celebrated method for Variational Inequalities (VIs) is Extragradient (EG), which can be viewed as a standard discrete-time integration scheme. With this view in mind, in this paper we show that EG may suffer from discretization bias when applied to non-linear vector fields, conservative or otherwise. To resolve this discretization shortcoming, we introduce RAndomized Mid-Point for debiAsed Gradient Extrapolation (RAMPAGE) and its variance-reduced counterpart, RAMPAGE+, which leverages antithetic sampling. In contrast with EG, both methods are unbiased. Furthermore, leveraging negative correlation, RAMPAGE+ acts as an unbiased, geometric path-integrator that completely removes internal first-order terms from the variance, provably improving upon RAMPAGE. We further demonstrate that both methods enjoy provable

\mathcal{O}(1/k)

convergence guarantees for a range of problems including root finding under co-coercive, co-hypomonotone, and generalized Lipschitzness regimes. Furthermore, we introduce symmetrically scaled variants to extend our results to constrained VIs. Finally, we provide convergence guarantees of both methods for stochastic and deterministic smooth convex-concave games. Somewhat interestingly, despite being a randomized method, RAMPAGE+ attains purely deterministic bounds for a number of the studied settings.

Zhankun Luo, M. Berk Sahin, Antesh Upadhyay +2

Authors are with the School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

Extragradient Methods Stochastic Optimization Convergence Variance Reduction

Mar 22, 2026

On the Role of Batch Size in Stochastic Conditional Gradient Methods

We study the role of batch size in stochastic conditional gradient methods under a

μ

-Kurdyka-Łojasiewicz (

μ

-KL) condition. Focusing on momentum-based stochastic conditional gradient algorithms (e.g., Scion), we derive a new analysis that explicitly captures the interaction between stepsize, batch size, and stochastic noise. Our study reveals a regime-dependent behavior: increasing the batch size initially improves optimization accuracy but, beyond a critical threshold, the benefits saturate and can eventually degrade performance under a fixed token budget. Notably, the theory predicts the magnitude of the optimal stepsize and aligns well with empirical practices observed in large-scale training. Leveraging these insights, we derive principled guidelines for selecting the batch size and stepsize, and propose an adaptive strategy that increases batch size and sequence length during training while preserving convergence guarantees. Experiments on NanoGPT are consistent with the theoretical predictions and illustrate the emergence of the predicted scaling regimes. Overall, our results provide a theoretical framework for understanding batch size scaling in stochastic conditional gradient methods and offer guidance for designing efficient training schedules in large-scale optimization.

Rustem Islamov, Roman Machacek, Aurelien Lucchi +3

University of Basel, Switzerland · MBZUAI, UAE · University of Bern, Switzerland +2

Stochastic Optimization Neural Network Optimization Stochastic Optimization Convergence

Mar 20, 2026

Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis

Stochastic approximation (SA) is a fundamental iterative framework with broad applications in reinforcement learning and optimization. Classical analyses typically rely on martingale difference or Markov noise with bounded second moments, but many practical settings, including finance and communications, frequently encounter heavy-tailed and long-range dependent (LRD) noise. In this work, we study SA for finding the root of a strongly monotone operator under these non-classical noise models. We establish the first finite-time moment bounds in both settings, providing explicit convergence rates that quantify the impact of heavy tails and temporal dependence. Our analysis employs a noise-averaging argument that regularizes the impact of noise without modifying the iteration. Finally, we apply our general framework to stochastic gradient descent (SGD) and gradient play, and corroborate our finite-time analysis through numerical experiments.

Siddharth Chandak, Anuj Yadav, Ayfer Ozgur +1

Department of Electrical Engineering, Stanford University, CA, USA. · School of Computer & Communication Sciences, EPFL, Lausanne, Switzerland.

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

Mar 19, 2026

Uniform a priori bounds and error analysis for the Adam stochastic gradient descent optimization method

The adaptive moment estimation (Adam) optimizer proposed by Kingma & Ba (2014) is presumably the most popular stochastic gradient descent (SGD) optimization method for the training of deep neural networks (DNNs) in artificial intelligence (AI) systems. Despite its groundbreaking success in the training of AI systems, it still remains an open research problem to provide a complete error analysis of Adam, not only for optimizing DNNs but even when applied to strongly convex stochastic optimization problems (SOPs). Previous error analysis results for strongly convex SOPs in the literature provide conditional convergence analyses that rely on the assumption that Adam does not diverge to infinity but remains uniformly bounded. It is the key contribution of this work to establish uniform a priori bounds for Adam and, thereby, to provide -- for the first time -- an unconditional error analysis for Adam for a large class of strongly convex SOPs.

Steffen Dereich, Thang Do, Arnulf Jentzen

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

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Mar 18, 2026

Mirror Descent on Riemannian Manifolds

Mirror Descent (MD) is a scalable first-order method widely used in large-scale optimization, with applications in image processing, policy optimization, and neural network training. This paper generalizes MD to optimization on Riemannian manifolds. In particular, we develop a Riemannian Mirror Descent (RMD) framework via reparameterization and further propose a stochastic variant of RMD. We also establish non-asymptotic convergence guarantees for both RMD and stochastic RMD. As an application to the Stiefel manifold, our RMD framework reduces to the Curvilinear Gradient Descent (CGD) method proposed in [26]. Moreover, when specializing the stochastic RMD framework to the Stiefel setting, we obtain a stochastic extension of CGD, which effectively addresses large-scale manifold optimization problems.

Jiaxin Jiang, Lei Shi, Jiyuan Tan

School of Mathematical Sciences, Fudan University, Shanghai 200433, China · Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China

Riemannian Optimization Stochastic Optimization Convergence

Mar 17, 2026

Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning

The global Lipschitz smoothness condition underlies most convergence and complexity analyses via two key consequences: the descent lemma and the gradient Lipschitz continuity. How to study the performance of optimization algorithms in the absence of Lipschitz smoothness remains an active area. The relative smoothness framework from Bauschke-Bolte-Teboulle (2017) and Lu-Freund-Nesterov (2018) provides an extended descent lemma, ensuring convergence of Bregman-based proximal gradient methods and their vanilla stochastic counterparts. However, many widely used techniques (e.g., momentum schemes, random reshuffling, and variance reduction) additionally require the Lipschitz-type bound for gradient deviations, leaving their analysis under relative smoothness an open area. To resolve this issue, we introduce the dual kernel conditioning (DKC) regularity condition to regulate the local relative curvature of the kernel functions. Combined with the relative smoothness, DKC provides a dual Lipschitz continuity for gradients: even though the gradient mapping is not Lipschitz in the primal space, it preserves Lipschitz continuity in the dual space induced by a mirror map. We verify that DKC is widely satisfied by popular kernels and is closed under affine composition and conic combination. With these novel tools, we establish the first complexity bounds as well as the iterate convergence of random reshuffling mirror descent for constrained nonconvex relative smooth problems.

Junwen Qiu, Leilei Mei, Junyu Zhang

Industrial Systems Engineering and Management, National University of Singapore

Random Reshuffling Stochastic Optimization Stochastic Optimization Convergence Nonconvex Optimization

Mar 16, 2026

Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions

This paper develops new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method to solve a class of possibly nonmonotone stochastic composite inclusions. Unlike unbiased estimators such as mini-batching, developing stochastic biased variants faces a fundamental technical challenge and has not been utilized before for inclusions and fixed-point problems. We fill this gap by designing a new framework that can handle both unbiased and biased estimators. Our main idea is to construct stochastic variance-reduced estimators for the forward-reflected direction and use them to perform iterate updates. First, we propose a class of unbiased variance-reduced estimators and show that increasing mini-batch SGD, loopless-SVRG, and SAGA estimators fall within this class. For these unbiased estimators, we establish a

\mathcal{O}(1/k)

best-iterate convergence rate for the expected squared residual norm, together with almost-sure convergence of the iterate sequence to a solution. Consequently, we prove that the best oracle complexities for the

n

-finite-sum and expectation settings are

\mathcal{O}(n^{2/3}ε^{-2})

and

\mathcal{O}(ε^{-10/3})

, respectively, when employing loopless-SVRG or SAGA, where

ε

is a desired accuracy. Second, we introduce a new class of biased variance-reduced estimators for the forward-reflected direction, which includes SARAH, Hybrid SGD, and Hybrid SVRG as special instances. While the convergence rates remain valid for these biased estimators, the resulting oracle complexities are

\mathcal{O}(n^{3/4}ε^{-2})

and

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

for the

n

-finite-sum and expectation settings, respectively. Finally, we conduct two numerical experiments on AUC optimization for imbalanced classification and policy evaluation in reinforcement learning.

Quoc Tran-Dinh, Nghia Nguyen-Trung

Department of Statistics and Operations Research The University of North Carolina at Chapel Hill 318 Hanes Hall, UNC-Chapel Hill, NC 27599-3260.

Stochastic Optimization Stochastic Optimization Convergence Variance Reduction

Mar 15, 2026

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and deep learning models while Markovian noise naturally arises in decentralized optimization and online system identification problems. We further allow the magnitude of noise to grow with the function value, enabling the analysis of many practical sampling strategies. In addition to the high-probability guarantee, we establish a matching

1/k

decay rate for the expected suboptimality. Our proof technique relies on the Poisson equation to handle the Markovian noise and a probabilistic induction argument to address the lack of almost-sure bounds on the objective. Finally, we demonstrate the applicability of our framework by analyzing three practical optimization problems: token-based decentralized linear regression, supervised learning with subsampling for privacy amplification, and online system identification.

Avik Kar, Siddharth Chandak, Rahul Singh +3

Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. · Department of Electrical Engineering, Stanford University, Stanford, CA, USA. · CMAP, CNRS, École polytechnique, Institut Polytechnique ´de Paris, Palaiseau, France.

Optimization Convergence Analysis Stochastic Optimization Convergence Stochastic Gradient Descent

Mar 13, 2026

Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization

We consider a stochastic optimization problem involving two random variables: a context variable

X

and a dependent variable

Y

. The objective is to minimize the expected value of a nonlinear loss functional applied to the conditional expectation

\mathbb{E}[f(X, Y,β) \mid X]

, where

f

is a nonlinear function and

β

represents the decision variables. We focus on the practically important setting in which direct sampling from the conditional distribution of

Y \mid X

is infeasible, and only a stream of i.i.d. observation pairs

\{(X^k, Y^k)\}_{k=0,1,2,\ldots}

is available. In our approach, the conditional expectation is approximated within a prespecified parametric function class. We analyze a simultaneous learning-and-optimization algorithm that jointly estimates the conditional expectation and optimizes the outer objective. Using a specially designed measure of non-optimality, combining the squared norm of the objective function's gradient and the mean square error of the auxiliary parametric model, we establish that the method achieves a convergence rate of order

\mathcal{O}\big(1/\sqrt{N}\big)

, where

N

denotes the number of observed pairs.

Noel Smith, Andrzej Ruszczynski

Department of Management Science and Information Systems, Rutgers University

Stochastic Optimization Stochastic Approximation Stochastic Optimization Convergence

Mar 11, 2026

Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

In this work, we study the convergence properties of the Dual Space Preconditioned Gradient Descent, encompassing optimizers such as Normalized Gradient Descent and Gradient Clipping. We consider preconditioners of the form

\nabla K

, where

K: \mathbb{R}^{d \times k} \to \mathbb{R}

is convex and apply

\nabla K(\cdot)

to train an over-parameterized linear model with a convex loss of the form

\ell(X W - Y)

, for weights

W \in \mathbb{R}^{d \times k}

, labels

Y \in \mathbb{R}^{n \times k}

and data

X \in \mathbb{R}^{n \times d}

. Under the aforementioned assumptions, we prove that the iterates of the full-batch preconditioned gradient descent converge at an exponential rate to a point

W_{\infty} \in \mathbb{R}^{d \times k}

satisfying

XW_{\infty} = Y

. We also study the implicit bias of Dual Space Preconditioned Gradient Descent. First, we demonstrate analytically and empirically that, for general

K(\cdot)

,

W_\infty

depends on the chosen constant step size, hindering a precise characterization of the implicit bias. We also provide an approximate implicit bias property for general preconditioners, namely,

\|W_0 - W_{\infty}\|_F \le c \|W_0 - W_{\text{GD}, \infty}\|_F

for a constant

c>0

and

W_{\text{GD}, \infty}

denoting the convergence point of GD initialized at

W_0

. Furthermore, for preconditioners of the form

K(G) = h(\|G\|_F)

, known as {\it isotropic preconditioners}, and for the stochastic variation of the algorithm with arbitrary batch-size, we prove linear convergence to

W_{\text{GD}, \infty}

. Finally, in the experiments, we demonstrate faster convergence on a nonlinear model obtained using the smoothed matrix elastic-net as a preconditioner.

Reza Ghane, Danil Akhtiamov, Babak Hassibi

Electrical Engineering Department, California Institute of Technology, Pasadena, CA 91125 USA · Computing + Mathematical Sciences Department, California Institute of Technology, Pasadena, CA 91125 USA

Gradient Descent Implicit Bias Stochastic Optimization Convergence

Mar 10, 2026

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

In this paper, we propose a trust-region interior-point stochastic sequential quadratic programming (TR-IP-SSQP) method for solving optimization problems with a stochastic objective and deterministic nonlinear equality and inequality constraints. In this setting, exact evaluations of the objective function and its gradient are unavailable, but their stochastic estimates can be constructed. In particular, at each iteration our method builds stochastic oracles, which estimate the objective value and gradient to satisfy proper adaptive accuracy conditions with a fixed probability. To handle inequality constraints, we adopt an interior-point method (IPM), in which the barrier parameter follows a prescribed decaying sequence. Under standard assumptions, we establish global almost-sure convergence of the proposed method to first-order stationary points. We implement the method on a subset of problems from the CUTEst test set, as well as on logistic regression problems, to demonstrate its practical performance.

Yuchen Fang, Jihun Kim, Sen Na +2

Department of Mathematics, University of California, Berkeley · Department of IEOR, University of California, Berkeley · School of Industrial and Systems Engineering, Georgia Tech +1

Constrained Optimization Stochastic Optimization Stochastic Optimization Convergence Trust-Region Optimization

Mar 10, 2026

SHANG++: Robust Stochastic Acceleration under Multiplicative Noise

Under the multiplicative noise scaling (MNS) condition, original Nesterov acceleration is provably sensitive to noise and may diverge when gradient noise overwhelms the signal. In this paper, we develop two accelerated stochastic gradient descent methods by discretizing the Hessian-driven Nesterov accelerated gradient flow. We first derive SHANG, a direct semi-implicit discretization that already improves stability under MNS. We then introduce SHANG++, which adds a damping correction and achieves faster convergence with greater noise robustness. We establish convergence guarantees for both convex and strongly convex objectives under MNS, together with explicit parameter choices. In our experiments, SHANG++ performs consistently well across convex problems and applications in deep learning. In a dedicated noise experiment on ResNet-34, a single hyperparameter configuration maintains accuracy within one percentage point of the noise-free setting. Across all experiments, SHANG++ outperforms existing accelerated methods in robustness and efficiency, with minimal parameter sensitivity.

Yaxin Yu, Long Chen, Minfu Feng

School of Mathematics, Sichuan University, Chengdu, Sichuan, 610065, China · Department of Mathematics, University of California, Irvine, Irvine, CA, 92697, USA

Accelerated Gradient Methods Stochastic Optimization Convergence Stochastic Gradient Descent

Mar 6, 2026

Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first adaptive projection-free framework for stochastic composite nonconvex minimization that requires neither global smoothness constants nor line search. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an

ε

-stationary point, ALFCG-FS attains

\mathcal{O}(N+\sqrt{N}ε^{-2})

iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve

\tilde{\mathcal{O}}(σ^2ε^{-4}+ε^{-2})

and

\tilde{\mathcal{O}}(σε^{-3}+ε^{-2})

, where

N

is the number of components and

σ

is the noise level. In contrast to typical

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

or

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

rates, our bounds reduce to the optimal rate up to logarithmic factors

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

as the noise level

σ\to 0

. Extensive experiments on multiclass classification over nuclear norm balls and

\ell_p

balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.

Ganzhao Yuan

Shenzhen University of Advanced Technology (SUAT), China

Nonconvex Stochastic Optimization Stochastic Optimization Stochastic Optimization Convergence

Mar 3, 2026

Why Adam Can Beat SGD: Second-Moment Normalization Yields Sharper Tails

Despite Adam demonstrating faster empirical convergence than SGD in many applications, much of the existing theory yields guarantees essentially comparable to those of SGD, leaving the empirical performance gap insufficiently explained. In this paper, we uncover a key second-moment normalization in Adam and develop a stopping-time/martingale analysis that provably distinguishes Adam from SGD under the classical bounded variance model (a second moment assumption). In particular, we establish the first theoretical separation between the high-probability convergence behaviors of the two methods: Adam achieves a

δ^{-1/2}

dependence on the confidence parameter

δ

, whereas corresponding high-probability guarantee for SGD necessarily incurs at least a

δ^{-1}

dependence.

Ruinan Jin, Yingbin Liang, Shaofeng Zou

Department of Electrical and Computer Engineering, The Ohio State University, USA · School of Electrical, Computer and Energy Engineering, Arizona State University, USA

Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Mar 3, 2026

HomeAdam: Adam and AdamW Algorithms Sometimes Go Home to Obtain Better Provable Generalization

Adam and AdamW are a class of default optimizers for training deep learning models in machine learning. These adaptive algorithms converge faster but generalize worse compared to SGD. In fact, their proved generalization error

O(\frac{1}{\sqrt{N}})

also is larger than

O(\frac{1}{N})

of SGD, where

N

denotes training sample size. Recently, although some variants of Adam have been proposed to improve its generalization, their improved generalizations are still unexplored in theory. To fill this gap, in the paper, we restudy generalization of Adam and AdamW via algorithmic stability, and first prove that Adam and AdamW without square-root (i.e., Adam(W)-srf) have a generalization error

O(\frac{\hatρ^{-2T}}{N})

, where

T

denotes iteration number and

\hatρ>0

denotes the smallest element of second-order momentum plus a small positive number. To improve generalization, we propose a class of efficient clever Adam (i.e., HomeAdam(W)) algorithms via sometimes returning momentum-based SGD. Moreover, we prove that our HomeAdam(W) have a smaller generalization error

O(\frac{1}{N})

than

O(\frac{\hatρ^{-2T}}{N})

of Adam(W)-srf, since

\hatρ

is generally very small. In particular, it is also smaller than the existing

O(\frac{1}{\sqrt{N}})

of Adam(W). Meanwhile, we prove our HomeAdam(W) have a faster convergence rate of

O(\frac{1}{T^{1/4}})

than

O(\frac{\breveρ^{-1}}{T^{1/4}})

of the Adam(W)-srf, where

\breveρ\leq\hatρ

also is very small. Extensive numerical experiments demonstrate efficiency of our HomeAdam(W) algorithms.

Feihu Huang, Guanyi Zhang, Songcan Chen

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China · MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, Nanjing, China

Adaptive Gradient Methods Neural Network Generalization Stochastic Optimization Convergence

Mar 3, 2026

Convex and Non-convex Federated Learning with Stale Stochastic Gradients: Diminishing Step Size is All You Need

We propose a general framework for distributed stochastic optimization under delayed gradient models. In this setting,

n

local agents leverage their own data and computation to assist a central server in minimizing a global objective composed of agents' local cost functions. Each agent is allowed to transmit stochastic-potentially biased and delayed-estimates of its local gradient. While a prior work has advocated delay-adaptive step sizes for stochastic gradient descent (SGD) in the presence of delays, we demonstrate that a pre-chosen diminishing step size is sufficient and matches the performance of the adaptive scheme. Moreover, our analysis establishes that diminishing step sizes recover the optimal SGD rates for nonconvex and strongly convex objectives.

Xinran Zheng, Tara Javidi, Behrouz Touri

University of Illinois Urbana-Champaign · University of California San Diego

Stochastic Optimization Convergence Stochastic Gradient Descent Nonconvex Stochastic Optimization Federated Learning Asynchronous Federated Learning

Mar 2, 2026

Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

Stochastic gradient descent (SGD) is central to simulation optimization, stochastic programming, and online M-estimation, where sampling effort is a decision variable. We study the mini-batch gradient noise as a sampling-design object. Under exchangeable fresh-sampling mini-batches, the conditional covariance given the de Finetti directing measure mu is b^{-1} G_mu(theta), and under identifiability the projected population object is b^{-1} G*(theta) -- projected Fisher information for correctly specified likelihoods, the sandwich partner of the Hessian otherwise. This identification fixes the noise matrix entering the diffusion analysis of constant-step SGD: the raw iterate path has a deterministic fluid limit, and the sqrt(b/eta)-scaled fluctuations satisfy a functional CLT with noise covariance G*; near a nondegenerate optimum the limit is Ornstein-Uhlenbeck, and its Lyapunov covariance scaled by eta/b matches the linearized discrete recursion at leading order. Under a curvature-noise compatibility condition mu_F > 0, we prove 1/N mean-square upper bounds and an i.i.d. parametric Fisher van Trees lower bound of the same rate order, with oracle-complexity guarantees depending on an effective dimension d_eff and condition number kappa_F. Numerical experiments verify the identification and confirm the Lyapunov predictions in direct SGD.

Daniel Zantedeschi, Kumar Muthuraman

Muma College of Business, University of South Florida, Tampa, FL, USA · McCombs School of Business, University of Texas at Austin, Austin, TX, USA

Stochastic Gradient Descent Stochastic Optimization Convergence Oracle Complexity

Feb 27, 2026

On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation

Stochastic Bilevel Optimization has emerged as a fundamental framework for meta-learning and hyperparameter optimization. Despite the practical prevalence of single-loop algorithms, their theoretical understanding in the stochastic regime remains less developed than that of multi-loop methods. In this paper, we provide a refined convergence analysis of the Single-loop Stochastic Approximate Implicit Differentiation (SSAID) algorithm. Under the squared-gradient stationarity criterion

\|\nablaΦ(x)\|^2\leε

, the corrected proof establishes an oracle complexity of

\mathcal{O}(κ^{14}ε^{-2})

, equivalently an averaged stationarity rate of

\mathcal{O}(κ^7K^{-1/2})

. The result preserves the canonical

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

dependence on the target accuracy while giving an explicit characterization of the condition-number dependence for stochastic AID-based single-loop methods.

Yubo Zhou, Luo Luo, Guang Dai +1

Xi’an Jiaotong University · Fudan University · SGIT AI Lab

Stochastic Bilevel Optimization Implicit Differentiation Bilevel Optimization Stochastic Optimization Convergence