Optimization Convergence Analysis

Follow this topic Ask about this topic

Momentum

4 papers in the last four weeks, up 33% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 58

Jun 9, 2026math.OC

Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry

We study distributed optimization with stochastic gradients and finite-bit communication modeled by random (unbiased) quantization. We propose q-PDGD, a quantized stochastic primal-dual method, and analyze it under relaxed global geometry. Under restricted secant inequality (RSI), a constant step-size yields linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity, while a diminishing step-size achieves O(1/k) convergence without shared-minimizer assumptions. Under Polyak-Lojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same stochastic quantized setting. Our results match the best-known centralized stochastic rates in oracle complexity, and are supported by experiments demonstrating the predicted tradeoffs between quantization level, step-size choice, and graph structure.

Susmit Sarkar, Abhinav Raghuvanshi, Kushal Chakrabarti +1

Indian Institute of Technology Bombay, Mumbai, Maharashtra, India · Tata Consultancy Services Research, Thane, Maharashtra, India

Stochastic Optimization Primal-Dual Optimization Optimization Convergence Analysis Distributed Optimization

Jun 9, 2026math.OC

Accelerating SAV-based optimization via randomized low-rank Hessian approximation

We propose a new optimization method, the Nyström-enhanced relaxed scalar auxiliary variable method (N-RSAV), which incorporates curvature information into the RSAV framework to accelerate convergence while preserving an unconditional modified energy dissipation law. Existing RSAV-based methods rely solely on first-order information and often suffer from slow convergence, particularly for ill-conditioned problems such as those arising in physics-informed neural networks (PINNs). To address this limitation, we design the linear operator in the RSAV scheme using approximate Hessian information obtained from a randomized low-rank Nyström approximation. To preserve the dissipation structure, we enforce positive semidefiniteness through eigenvalue truncation. Furthermore, we introduce an adaptive strategy that reuses the approximate Hessian based on the deviation between the original and modified energies, significantly reducing computational cost. We also provide a convergence analysis of the RSAV scheme with a general positive semidefinite operator under the Polyak-Lojasiewicz (PL) condition and establish corresponding convergence guarantees for N-RSAV under the PL condition and an additional convexity assumption. Numerical experiments on ill-conditioned problems with effectively low-rank structure, including convex quadratic problems and training of PINNs, demonstrate that the proposed methods achieve substantially faster convergence than conventional RSAV-based approaches.

Ryo Sagawa, Daisuke Furihata, Yuto Miyatake

Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, The University of Osaka · D3 Center, The University of Osaka

Optimization Convergence Analysis Second-Order Optimization

Jun 8, 2026cs.LG

Improved Convergence Analysis of Topology Dependence in Decentralized SGD

Decentralized SGD is a fundamental algorithm in decentralized learning, although the influence of an underlying network topology on its convergence behavior is not yet fully understood. Existing convergence analyses have shown that topologies with a small spectral gap significantly deteriorate the convergence rate of Decentralized SGD in both homogeneous and heterogeneous cases. However, many prior papers have reported that indeed the choice of the topology has a significant experimental impact in the heterogeneous case, but has little experimental impact on training behavior in the homogeneous case. In this paper, we present a tighter convergence analysis of Decentralized SGD, offering a more precise understanding of how topologies affect the convergence rate than the prior analysis. Specifically, unlike existing convergence analyses that used only the spectral gap as a property of the topology, our novel analysis shows that all eigenvalues of the mixing matrix affect the convergence rate. Throughout the experiments, we carefully evaluated the convergence behavior of Decentralized SGD and demonstrated that our novel convergence analysis can more accurately describe the effect of topology on the convergence rate.

Yuki Takezawa, Anastasia Koloskova, Sebastian U. Stich

Toyota Motor Corporation · University of Zurich · CISPA Helmholtz Center for Information Security

Optimization Convergence Analysis Decentralized Learning Decentralized Optimization

Jun 3, 2026cs.LG

Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

We study the deterministic first-order oracle complexity of finding

ε

-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical

ε^{-2}

rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the

ε^{-7/4}

rate under Lipschitz Hessians and the

ε^{-5/3}

rate under Lipschitz third derivatives. The matching lower bounds, however, have remained open. We resolve this gap by proving a new dimension-free first-order lower bound for higher-order smooth nonconvex functions, valid for every finite smoothness order. In particular, our construction gives a matching

Ω(ε^{-7/4})

lower bound in the Hessian-Lipschitz case and a matching

Ω(ε^{-5/3})

lower bound in the third-order-smooth regime. The hard instance is based on a \emph{block-chain} mechanism that enforces blockwise oracle revelation while preserving the smoothness structure needed for the scalar hard instance. The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors.

Dongruo Zhou

Department of Computer Science, Indiana University Bloomington, IN 47408, USA

Optimization Convergence Analysis Nonconvex Optimization

Jun 2, 2026stat.ML

Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCA

We study simultaneous alternating power iteration for fixed-order asymmetric rank-one spiked tensor models. Our main contribution is a finite-iteration local theory that is independent of any particular initialization. Once the iterates enter a sufficiently small neighborhood of the planted rank-one direction, their error decomposes into a geometrically decaying transient and an intrinsic noise floor caused by fixed orthogonal noise contractions at the planted point. The deterministic finite-sample conditions are stated explicitly, but under a coarse fixed-order multilinear noise event they reduce to a conservative high-signal regime for fixed or slowly expanding local radii. We then separate the warm-start mechanism from any specific spectral construction. A generic one-sweep principle shows that, if a sign-compatible initializer has correlation

γ_N

, first-sweep noise level

a_N

, and

a_N/(γ_N^{d-1}ω_{N,d})\to0

, then one can choose an expanding radius

r_N=o(ω_{N,d})

for which the first sweep enters the local basin. After entry, the local affine contraction yields convergence to the unique informative local fixed point in that basin. For centered-Gram initialization, we verify the required correlation and same-sample first-sweep noise bound under i.i.d. finite-fourth-moment noise by a signal-preserving noise-only leave-one comparison and an averaged leave-one slice-contraction estimate, which we call a pressed-back estimate. The leave-one comparison keeps the spike fixed and averages over the deleted coordinate, so planted coordinates enter through

\ell_2

-weighted sums rather than worst-case incoherence bounds.

Yanjin Xiang, Zhihua Zhang

Peking University

Optimization Convergence Analysis Tensor Decomposition

Jun 2, 2026cs.LG

Analytical Evaluation of DCA Convergence Properties for Minimizing Prediction Functions of Gaussian RBF Support Vector Regression

For nonconvex optimization problems whose objective is the prediction function of a trained Support Vector Regression (SVR) model with the Gaussian radial basis function (RBF) kernel (RBF-SVR), we present a framework that applies the difference of convex functions (DC) algorithm (DCA) by exploiting the analytical structure of the RBF kernel to construct an explicit DC decomposition. Specifically, we derive in closed form both the lower bound

μ

of the strong convexity parameter of the DC components and the upper bound

L

of the gradient Lipschitz constant of the subproblem. Both

μ

and

L

are determined solely by the post-training dual-coefficient sum

C_α

and the RBF kernel parameter

γ

, together with the DC decomposition parameter

ρ

, and they share a common leading term

C_αρ

. Through numerical experiments on six benchmark functions, we show that

C_αρ

is the primary single quantity characterizing both the convergence properties and the initial-point dependence of DCA, and further demonstrate that it decomposes into two independent pathways,

C \to C_α

and

γ\to ρ

, with its primary variation governed by the SVR hyperparameters

(C, γ)

. Together, these results allow the convergence properties of DCA on RBF-SVR to be assessed in advance through the single scalar quantity

C_αρ

: approximately from

(C, γ)

before training, and exactly in closed form after training.

Yohei Kakimoto, Yuto Omae, Hirotaka Takahashi

Nihon University · Tokyo City University

Optimization Convergence Analysis Support Vector Machines Kernel Methods

Jun 1, 2026cs.LG

FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo

Shampoo is attracting considerable attention for its superior performance on large-scale optimization benchmarks; yet it faces a significant practical bottleneck: the prohibitive computational overhead of matrix inversion. To mitigate this, practitioners typically rely on stale preconditioner updates, creating a fundamental trade-off between computational efficiency and optimization fidelity. In this work, we provide a theoretical study of staleness through the complementary lenses of convergence and stability. While staleness improves computational efficiency, it inherently degrades performance and introduces numerical instability. Crucially, we identify that damping, acting as a numerical stabilizer, can effectively suppress these negative effects. Guided by this analysis, we propose FOAM, an adaptive algorithm that stabilizes training by dynamically controlling both the damping factor and the eigendecomposition frequency based on an approximation of the staleness-oriented error. Experimental results demonstrate that FOAM reduces wall-clock time compared to standard Shampoo while maintaining robust convergence.

Kyunghun Nam, Sumyeong Ahn

KENTECH, Naju, Republic of Korea.

Deep Learning Optimization Optimization Convergence Analysis Algorithmic Stability Second-Order Optimization

Jun 1, 2026math.OC

Accelerating Min-Max Optimization via Power-Law Stepsizes

We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization. It is known that EG with a fixed stepsize achieves a

Θ(T^{-1/2})

last-iterate convergence rate, which is slower than the optimal

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

rate attainable by incorporating additional mechanisms such as anchoring. Motivated by recent advances showing that dynamic stepsizes alone can significantly accelerate gradient descent, we ask whether dynamic stepsizes can similarly accelerate the last-iterate convergence of EG. We present the first positive result in this direction. Specifically, we provide a deterministic dynamic stepsize schedule that accelerates the convergence rate of EG to

\mathcal{O}(T^{-2/3+\varepsilon})

for any

\varepsilon > 0

. We also show that this rate is tight when the extrapolation and update steps of EG use the same stepsize. We then show that allowing different stepsizes for the extrapolation and update steps further improves the convergence rate to the near-optimal

\mathcal{O}(T^{-1+\varepsilon})

. Our analysis reduces stepsize scheduling to an optimization problem, whose solution leads to a stepsize schedule that follows (a discretization of) a power-law distribution. Our proposed stepsize schedules and analysis extend to other methods, such as Optimistic Gradient (OG), and suggest broader applicability to general min-max optimization problems.

Yue Wu, Weiqiang Zheng, Yang Cai +1

University of Southern California · Yale University

Learning Rate Scheduling Last-Iterate Convergence Optimization Convergence Analysis Min-Max Optimization

May 31, 2026math.OC

Global Convergence of a Line-Search Filter Differential Dynamic Programming Method

In this article, we establish the global convergence properties of the FilterDDP algorithm, which extends the discrete-time differential dynamic programming (DDP) algorithm of Mayne and Jacobson [\emph{International Journal of Control}, 3, (1966), pp. 85-95] to handle nonlinear constraints over states and controls, in addition to the dynamics. FilterDDP adopts a line-search filter procedure for step acceptance. However, instead of a damped Newton step applied in the general nonlinear programming setting, the computation of a trial point involves applying a backward recursion and a forward simulation. We establish the global convergence of FilterDDP by showing that for a subset of constrained optimal control problems, the this backward-forward procedure satisfies the same properties as a Newton step for the purpose of establishing global convergence of a line-search filter method, following the analysis of Wächter and Biegler [\emph{SIAM Journal on Optimization}, 16 (2005), pp. 1-31].

Ming Xu, Iman Shames

School of Computer and Communication Sciences EPFL 1015 Lasanne, Switzerland · Department of Electrical and Electronic Engineering University of Melbourne Parkville, VIC, 3010, Australia

Optimization Convergence Analysis Constrained Optimization Optimal Control

May 29, 2026math.OC

A Unifying View of Anchoring via Operator-Side Tikhonov Regularization

Anchored fixed point and monotone equation methods, including Halpern iteration, extra anchored gradient, and their relatives, add a vanishing pull toward a reference point to obtain last-iterate guarantees. Existing anchored variants often achieve sharp last-iterate guarantees, but from the update-level perspective the placement of the anchor can be algorithm-specific and conceptually opaque. We show that anchoring admits a single operator-side construction: regularize the operator queried by the base method with a vanishing Tikhonov term, then run the unmodified base method. Applied to the Picard iteration, this recipe reproduces the Halpern iteration; applied to the forward step, extragradient (EG), and past extragradient (PEG, also known as Popov's method), it yields three variants whose anchor placements inherit the base method's query pattern. The forward-step instantiation gives a new residual convergence guarantee, while the EG and PEG instantiations give new regularized variants. The four analyses share a residual recurrence, recovering the

O(1/k)

Halpern residual-norm convergence rate, giving

O(1/\sqrt{k})

for the regularized forward step, and giving

O(1/k)

for the regularized EG and PEG variants in the unconstrained monotone Lipschitz setting.

Zihao Chen

UC Berkeley

Last-Iterate Convergence Optimization Convergence Analysis

May 28, 2026cs.LG

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

Recent work has analyzed the convergence of first-order methods under non-uniform smoothness assumptions that better model the loss landscape in machine learning tasks. We generalize this assumption to objectives whose curvature is an affine function of the objective value. This property is satisfied by a broad class of problems, including logistic regression, generalized linear models with a logistic link function, softmax policy gradient in reinforcement learning, and a class of neural networks. Under this assumption and gradient domination conditions, we establish a general convergence rate for the steepest descent method, and deterministic, diagonal variants of RMSProp and Adam. Our results imply that for logistic regression on separable data and the softmax policy gradient objective, sign GD converges linearly and is provably faster than GD. Furthermore, we show that for a class of two-layer neural networks on separable data, RMSProp and Adam can converge at a linear rate with a constant step-size and momentum parameter. Finally, we present a lower bound demonstrating that, under our assumption, RMSProp and Adam are provably faster than AdaGrad, AMSGrad, gradient descent, and heavy-ball momentum.

Sharan Vaswani, Yifan Sun, Reza Babanezhad

1Simon Fraser University · 2Stony Brook University · 3Samsung AI, Montreal.

Optimization Convergence Analysis Gradient Descent Nonconvex Optimization Adaptive Gradient Methods

May 28, 2026cs.LG

A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithm

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

Sakshi Kumari, Shyam Kumar M, Sushmitha P

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

Optimization Convergence Analysis Stochastic Optimization Convergence Adaptive Gradient Methods

May 26, 2026cs.LG

Deep-layer limit and stability analysis of the basic forward-backward-splitting induced network (II): learning problems

Deep unfolding neural networks derived from iterative optimization schemes and numerical ordinary/partial differential equations (ODEs/PDEs) have attracted much attention in data science over the last decade. Therein, numerous important network architectures were constructed from the basic forward-backward-splitting (FBS) algorithm. In this paper, we continue our research on the most basic FBS-induced network, an architecture unrolled from the original FBS algorithm by incorporating direct parameter relaxations. Following the difference/differential inclusion formulations in our previous forward system analyses, we here consider some theoretical aspects of corresponding learning problems. Under some mild assumptions, we establish a general convergence property of the training problem of the basic FBS-induced network to the learning problem of the deep-layer limit system, implying a

Γ

-convergence argument showing that any cluster point of the optimal learning parameters for the network is a solution to the learning problem of the deep-layer limit system. A qualitative analysis of perturbation stabilities of these learning problems is also presented. A simple numerical experiment is conducted to validate our main general convergence result.

Xuan Lin, Chunlin Wu

China Academy of Aerospace System and Innovation, 100088, Beijing, China · School of Mathematical Sciences, Nankai University, 94 Weijin Road, 300071, Tianjin, China

Optimization Convergence Analysis Neural Network Optimization

May 25, 2026cs.LG

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

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

Zhaoyu Zhu, Rui Gao, Shuang Li

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

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

May 15, 2026cs.LG

Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing

Sampling-based optimization (SBO), like cross-entropy method and evolutionary algorithms, has achieved many successes in solving non-convex problems without gradients, yet its convergence is poorly understood. In this paper, we establish a non-asymptotic convergence analysis for SBO through the lens of smoothing. Specifically, we recast SBO as gradient descent on a smoothed objective, mirroring noise-conditioned score ascent in diffusion models. Our first contribution is a landscape analysis of the smoothed objective, demonstrating how smoothing helps escape local minima and uncovering a fundamental coverage-optimality trade-off: smoothing renders the landscape more benign by enlarging the locally convex region around the global minimizer, but at the cost of introducing an optimality gap. Building on this insight, we establish non-asymptotic convergence guarantees for SBO algorithms to a neighborhood of the global minimizer. Furthermore, we propose an annealed SBO algorithm, Diffusion-Inspired Dual-Annealing (DIDA), which is provably convergent to the global optimum. We conduct extensive numerical experiments to verify our landscape results and also demonstrate the compelling performance of DIDA compared to other gradient-free optimization methods. Lastly, we discuss implications of our results for diffusion models.

Zeji Yi, Chaoyi Pan, Guanya Shi +1

Carnegie Mellon University

Optimization Convergence Analysis Black-Box Optimization Global Optimization Nonconvex Optimization Stochastic Optimization Convergence Derivative-Free Optimization

May 13, 2026cs.GT

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the

2\times 2

setting a new

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

best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.

John Lazarsfeld, Anas Barakat, Georgios Piliouras +2

SUTD · Google DeepMind · NUS CQT +2

Nash Equilibrium Last-Iterate Convergence Optimization Convergence Analysis Game Theory Zero-Sum Games Convergence Analysis+1

May 10, 2026stat.ML

Quantitative Local Convergence of Mean-Field Stein Variational Gradient Flow

Stein Variational Gradient Descent (SVGD) is a deterministic interacting-particle method for sampling from a target probability measure given access to its score function. In the mean-field and continuous-time limit, it is known that the flow converges weakly toward the target, but no quantitative rate is known for the last iterate. In this paper, we establish quantitative local convergence in strong norms for this dynamics, when the interaction kernel is of Riesz type on the

d

-dimensional torus. Specifically, assuming that the initial density and the target are smooth and close in

L^2

-norm, we obtain explicit polynomial convergence rates in

L^2

-norm that depend on the dimension and on the regularity parameters of the kernel, the initialization and the target. We further show that these rates are sharp in certain regimes, and support the theory with numerical experiments. In the edge case of kernels with a Coulomb singularity, we recover the global exponential convergence result established in prior work. Our analysis is inspired by recent results on Wasserstein gradient flows of kernel mean discrepancies.

Lénaïc Chizat, Maria Colombo, Roberto Colombo +1

Dynamical Systems Optimization Convergence Analysis Mean-Field Theory Variational Inference Stein Variational Gradient Descent

May 7, 2026cs.LG

When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$ -norm Lower Bounds

Sign-based optimization algorithms, such as SignSGD and Muon, have garnered significant attention for their remarkable performance in training large foundation models. Despite this empirical success, we still lack a theoretical understanding of when and why these sign-based methods outperform vanilla SGD. The core obstacle is that under standard smoothness and finite variance conditions, SGD is known to be minimax optimal for finding stationary points measured by

\ell_2

-norms, thereby fundamentally precluding any complexity gains for sign-based methods in standard settings. To overcome this barrier, we analyze sign-based optimizers leveraging

\ell_1

-norm stationarity,

\ell_\infty

-smoothness, and a separable noise model, which can better capture the coordinate-wise nature of signed updates. Under this distinct problem geometry, we derive matched upper and lower bounds for SignSGD and explicitly characterize the problem class in which SignSGD provably dominates SGD. Specifically, we compare the \emph{upper bound of SignSGD} with the \emph{lower bound of SGD}, illustrating that SignSGD effectively reduces the complexity by a factor of

d

under \emph{sparse noise}, where

d

is the problem dimension. Furthermore, we elevate this framework to the matrix domain, providing an equivalent optimal lower bound for the Muon optimizer, proving that extending the sign operator to matrices preserves this optimal scaling with dimensionality. Finally, we bridge our theoretical bounds to practice, demonstrating that the theoretical superiority of SignSGD accurately predicts its faster convergence during the pretraining of a 124M parameter GPT-2 model.

Hongyi Tao, Dingzhi Yu, Lijun Zhang

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China

Sign-Based Optimization Optimization Convergence Analysis Muon Optimizer Stochastic Optimization Convergence Stochastic Gradient Descent

May 4, 2026math.OC

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate

We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve

O(ε^{-5/3}\log(1/ε))

oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.

Sichao Xiong, Sadok Jerad, Coralia Cartis

Department of Computer Science University of Oxford Oxford, OX1 3QG · Mathematical Institue University of Oxford Oxford, OX2 6GG

Optimization Convergence Analysis Gradient Descent Nonconvex Optimization Accelerated Gradient Methods

May 1, 2026stat.ML

Gradient Regularized Newton Boosting Trees with Global Convergence

Gradient Boosting Decision Trees (GBDTs) dominate tabular machine learning, with modern implementations like XGBoost, LightGBM, and CatBoost being based on Newton boosting: a second-order descent step in the space of decision trees. Despite its empirical success, the global convergence of Newton boosting is poorly understood compared to first-order boosting. In this paper, we introduce Restricted Newton Descent, which studies convex optimization with Newton's method on Hilbert spaces with inexact iterates, based on the concepts of cosine angle and weak gradient edge. Within this framework, we recover Newton boosting with GBDTs and classical finite-dimensional theory as special cases. We first prove that vanilla Newton boosting achieves a linear rate of convergence for smooth, strongly convex losses that satisfy a Hessian-dominance condition. To handle general convex losses with Lipschitz Hessians, we extend a recent gradient regularized Newton scheme to the restricted weak learner setting. This scheme minimally modifies the classical algorithm by introducing an adaptive

\ell_2

-regularization term proportional to the square root of the gradient norm at each iteration. We establish a

\mathcal{O}(\frac{1}{k^2})

rate for this scheme, thereby obtaining a globally convergent second-order GBDT algorithm with a rate matching that of first-order boosting with Nesterov momentum. In numerical experiments, we show that our scheme converges while vanilla Newton boosting may diverge.

Nikita Zozoulenko, Daniel Falkowski, Thomas Cass +1

Department of Mathematics, Imperial College London, UK · Department of Mathematics, Stockholm University, Sweden · School of Computer Science, University of St. Gallen, Switzerland

Gradient-Boosted Decision Trees Optimization Convergence Analysis Second-Order Optimization

Apr 29, 2026math.OC

Man, Machine, and Mathematics

Nonlinear models and optimization methods have successfully tackled a rapidly growing set of problems in recent years. Indeed, a relatively small toolbox of such models and methods can provide sufficient performance across a large landscape of tasks: deep learning alone has made significant recent contributions in scientific modelling, natural language processing, visual analysis, etc. A similar relationship exists between physical theories and phenomena, where many applications and observations emerge neatly from remarkably minimal foundations. It is natural to wonder if sparse unified frameworks could be built to steer discussion and discovery in the fields concerned with learning, optimization, and modelling. In this work, we posit and examine a possible outline for such a unified theory, interpreting the notion of ''learning'' in a broad sense. In particular, we pursue our goals by viewing learning as an inter-connected process on multiple levels: problem setup, choosing methods, and the analysis of their interplay via imposed optimisation dynamics. We begin by proposing a precise yet versatile definition for ''solvable'' problems. We then define the ''parametrised methods'' by which their solution(s) may be ''learned''. Our goal is to sketch a ''universal convergence theorem'', specifying how and when solvable problems become amenable to the methods chosen for them. We find these constructions reduce the study of learning down to remarkably few ideas and tools - many of which are simply adapted from existing ones in dynamical systems theory, geometry, and fundamental physics.

Akshunna S. Dogra

The NSF AI Institute for Artificial Intelligence and Fundamental Interactions (IAIFI), USA · EPSRC Centre for Doctoral Training: Mathematics of Random Systems, UK · Center of Mathematical Sciences and Applications, Harvard University, USA +3

Optimization Convergence Analysis Statistical Learning Theory

Apr 18, 2026math.OC

Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence

Linear convergence of first-order methods is typically characterized by global optimization conditions whose constants reflect worst-case geometry of the ambient space. In high-dimensional or structured problems, these global constants can be arbitrarily conservative and fail to capture the geometry actually encountered by optimization trajectories. In this paper, we develop a trajectory-restricted framework for linear convergence based on localized geometric regularity. We introduce restricted variants of the Polyak--Łojasiewicz inequality, error bound, and quadratic growth conditions that are required to hold only on subsets of the domain. We show that classical convergence guarantees extend under these localized conditions, and in key cases, we develop new arguments that yield explicit relationships between the corresponding constants. The resulting rates are governed by geometric quantities associated with the regions traversed by the algorithm. For polyhedral composite problems, we prove that convergence is controlled by restricted Hoffman constants corresponding to the active polyhedral faces visited along the trajectory. Once the iterates enter a well-conditioned face, the effective condition number improves accordingly. Our work provides a geometric quantification for fast local convergence after active-set or manifold identification and more broadly suggests that linear convergence is fundamentally governed by the geometry of the subsets explored by the algorithm, rather than by worst-case global conditioning.

Faris Chaudhry, Anthea Monod, Keisuke Yano

Imperial College London, UK · Institute of Statistical Mathematics, Japan

Optimization Convergence Analysis Constrained Optimization

Jul 4, 2025cs.LG

On the Effectiveness of the z-Transform Method in Quadratic Optimization

The z-transform of a sequence is a classical tool used within signal processing, control theory, computer science, and electrical engineering. It allows for studying sequences from their generating functions, with many operations that can be equivalently defined on the original sequence and its

z

-transform. In particular, the z-transform method focuses on asymptotic behaviors and allows the use of Taylor expansions. We present a sequence of results of increasing significance and difficulty for linear models and optimization algorithms, demonstrating the effectiveness and versatility of the z-transform method in deriving new asymptotic results. Starting from the simplest gradient descent iterations in an infinite-dimensional Hilbert space, we show how the spectral dimension characterizes the convergence behavior. We then extend the analysis to Nesterov acceleration, averaging techniques, and stochastic gradient descent.

Francis Bach

SIERRA · Inria - Ecole Normale Sup´erieure · PSL Research University

Optimization Convergence Analysis Gradient Descent Dynamics Stochastic Gradient Descent

May 17, 2025cs.LG

On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm

As the default optimizer for training large language models, AdamW has achieved remarkable success in deep learning. However, its convergence behavior is not theoretically well-understood. This paper establishes the convergence rate

\frac{1}{K}\sum_{k=1}^KE\left[||\nabla f(x^k)||_1\right]\leq O(\frac{\sqrt{d}C}{K^{1/4}})

for AdamW measured by

\ell_1

norm, where

K

represents the iteration number,

d

denotes the model dimension, and

C

matches the constant in the optimal convergence rate of SGD. Theoretically, we have

||\nabla f(x)||_2\ll ||\nabla f(x)||_1\leq \sqrt{d}||\nabla f(x)||_2

for any high-dimensional vector

x

and

E\left[||\nabla f(x)||_1\right]\geq\sqrt{\frac{2d}π}E\left[||\nabla f(x)||_2\right]

when each element of

\nabla f(x)

is generated from Gaussian distribution

\mathcal N(0,1)

. Empirically, our experimental results on real-world deep learning tasks reveal

||\nabla f(x)||_1=\varTheta(\sqrt{d})||\nabla f(x)||_2

. Both support that our convergence rate can be considered to be analogous to the optimal

\frac{1}{K}\sum_{k=1}^KE\left[||\nabla f(x^k)||_2\right]\leq O(\frac{C}{K^{1/4}})

convergence rate of SGD in the ideal case. We also extend our result to NAdamW, an AdamW variant that employs a double-momentum mechanism, and demonstrate that it maintains the same convergence rate.

Huan Li, Yiming Dong, Zhouchen Lin

Institute of Robotics and Automatic Information Systems, College of Artificial Intelligence, Nankai University, Tianjin, China. · National Key Lab of General AI, School of Intelligence Science and Technology, Peking University, Beijing, China.

Optimization Convergence Analysis Stochastic Optimization Convergence Adaptive Gradient Methods

May 2, 2025math.OC

Negative Stepsizes Make Gradient-Descent-Ascent Converge

Efficient computation of min-max problems is a central question in optimization, learning, games, and control. Arguably the most natural algorithm is gradient-descent-ascent (GDA). However, since the 1970s, conventional wisdom has argued that GDA fails to converge even on simple problems. This failure spurred an extensive literature on modifying GDA with additional building blocks such as extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes. The key innovation is the proposal of unconventional stepsize schedules (dubbed slingshot stepsize schedules) that are time-varying, asymmetric, and periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). The core algorithmic intuition is that although negative stepsizes make backward progress, they de-synchronize the min and max variables (overcoming the cycling issue of GDA), and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. We interpret this as a second-order finite-differencing algorithm and show that, intriguingly, it approximately implements consensus optimization, an empirically popular algorithm for min-max problems involving deep neural networks (e.g., training GANs).

Henry Shugart, Jason M. Altschuler

UPenn

Learning Rate Scheduling Optimization Convergence Analysis Min-Max Optimization Gradient Descent Dynamics

Jun 7, 2024cs.LG

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size

2/λ

, where

λ

is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than

1/λ

suffices for global convergence. However, for all step sizes between

1/λ

and the critical step size

2/λ

, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than

1/λ

. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.

Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao +1

Department of Computer Science Cornell University Ithaca, NY, USA · ELLIS Institute Tübingen MPI for Intelligent Systems Tübingen AI Center, Germany

Dynamical Systems Logistic Regression Optimization Convergence Analysis Gradient Descent Gradient Descent Dynamics

Mar 28, 2024math.OC

Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients

Kakade's natural policy gradient method has been studied extensively in recent years, showing linear convergence with and without regularization. We study another natural gradient method based on the Fisher information matrix of the state-action distributions which has received little attention from the theoretical side. Here, the state-action distributions follow the Fisher-Rao gradient flow inside the state-action polytope with respect to a linear potential. Therefore, we study Fisher-Rao gradient flows of linear programs more generally and show linear convergence with a rate that depends on the geometry of the linear program. Equivalently, this yields an estimate on the error induced by entropic regularization of the linear program which improves existing results. We extend these results and show sublinear convergence for perturbed Fisher-Rao gradient flows and natural gradient flows up to an approximation error. In particular, these general results cover the case of state-action natural policy gradients.

Johannes Müller, Semih Çaycı, Guido Montúfar

Department of Mathematics, RWTH Aachen University, Aachen, 52062, Germany · Departments of Mathematics and Statistics & Data Science, University of California, Los Angeles, 90095, USA · Max Planck Institute for Mathematics in the Sciences, Leipzig, 04103, Germany

Policy Gradient Optimization Convergence Analysis Natural Gradient Methods Constrained Optimization Linear Programming

Date pendingmath.OC

Silver Rate Is (Almost) Optimal for Gradient Descent

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing

p_{\mathrm{sil}}=\log_2(1+\sqrt{2})

, we prove an

\Omega\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)

non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error

\Omega\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right)

. Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.

Yuhan Ye, Kaizhao Liu

MIT

Learning Rate Scheduling Optimization Convergence Analysis Gradient Descent Accelerated Gradient Methods