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

Oct 6, 2026stat.ML

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

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

\ell

-smooth games with an inner

μ

-PL inequality, we prove a complexity lower bound

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

, where

κ=\ell/μ

is the condition number,

σ^2

is the gradient variance, and

\varepsilon

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

o(κ^2)

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

Junsoo Ha

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

Oct 5, 2026math.OC

Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness

Normalized gradient descent is a widely studied adaptive optimization method. Most existing analyses focus on the best iterate or a weighted average of the iterates, whereas practical implementations typically return the last iterate. In this paper, we study the last-iterate convergence of normalized gradient descent for convex,

(ν,M_ν)

-Hölder-smooth objectives. For a constant stepsize, we establish an upper bound of

\mathcal{O}\bigl((\log^2(T)/T)^{(1+ν)/2}\bigr)

, which contains a logarithmic overhead relative to the known

\mathcal{O}\bigl(T^{-(1+ν)/2}\bigr)

guarantees for the best and weighted-average iterates. For

ν= 0

, this overhead is known to be unavoidable. We complement this analysis with numerical results based on the performance estimation problem (PEP), investigating the finite-horizon worst-case behavior in the smooth setting and whether the logarithmic overhead reflects an intrinsic limitation of constant-step normalized gradient descent. We then show that a linearly decreasing stepsize yields a last-iterate guarantee of

\mathcal{O}\bigl(T^{-(1+ν)/2}\bigr)

, matching the order of the best-iterate/weighted-average guarantees without requiring knowledge of

ν

and

M_ν

.

Yuki Takezawa, Eduard Gorbunov

Toyota Motor Corporation · MBZUAI

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

Oct 1, 2026math.OC

Convergence Analysis of STORM Under Different Geometries

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

O(T^{-1/3})

bound for nonconvex objectives and the

O(σ^2/(μT))

bound for last-iterate output under the

μ

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

O(T^{-1/4})

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

λ

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

O(σR/\sqrt T)

and

O(σ^2/(λT))

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

Wei Jiang, Yibo Wang, Wenhao Yang +3

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

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

Sep 30, 2026cs.LG

The Row Normalization Puzzle in Muon

This paper examines how row-wise renormalization affects Muon, focusing on the gap between NorMuon's worst-case guarantees and its practical performance (Li et al.). Despite its growing adoption and promising performance in large language model (LLM) pretraining, NorMuon's worst-case guarantees remain poorly understood. One fundamental question is: Does row normalization yield provable convergence gains, potentially through its interaction with approximate polar computation and exponential moving-average momentum? Our results show that row normalization introduces a dimension-dependent factor in the worst-case iteration complexity under the operator-norm geometry, which persists even with exact polar computation and any fixed momentum parameters. Indeed, we establish an algorithm-dependent lower bound and a matching upper bound in deterministic settings, and extend our upper bound analysis to stochastic settings. Both upper-bound analyses allow approximate polar computation. Experiments show that NorMuon is slower than Muon on synthetic problems inspired by our worst-case construction, yet outperforms Muon in LLM pretraining. These findings sharpen the puzzle of why row normalization helps in practice and complement the recent findings of Dewulf et al.

Jiayu Zhang, Tianyi Lin

Department of Industrial Engineering and Operations Research Columbia University

Stochastic Optimization Optimization Convergence Analysis Muon Optimizer

Sep 21, 2026math.OC

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

Dan Garber

Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

Oracle Complexity Optimization Convergence Analysis Nonsmooth Convex Optimization

Sep 14, 2026math.OC

The fixed-point bundle method over product-of-simplex domains arising from game equilibria

This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex domain and establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism. Exploiting this geometric equivalence, the predictor-corrector path-following algorithm for the VI on the product-of-simplex domain is shown to inherit the convergence guarantee of the simplex-domain framework, namely, global convergence with linear gap reduction near solutions. Numerical experiments on 5600 randomly generated instances with dimensions ranging from 2-player 128-action to 128-player 2-action demonstrate robust performance. The algorithm converges in every tested instance.

Hongbo Sun

Hongbo Sun∗

Optimization Convergence Analysis Nash Equilibrium Computation

Sep 3, 2026cs.LG

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate,

(1 - κ^{-3/2})

, where

κ

is the condition number of the ensemble, also polynomially improves on the best small-step guarantee (

κ^{3/2}

versus

κ^{5/2}

iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval

[α, β]

is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set

\{S : αI \leq S \leq βI\}

-- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

A. Afham

Centre for Quantum Technologies, National University of Singapore, Singapore

Riemannian Optimization Optimization Convergence Analysis Wasserstein Barycenters Optimal Transport

Aug 12, 2026math.OC

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.

Frank E. Curtis, Lingjun Guo, Daniel P. Robinson

Department of Industrial and Systems Engineering, Lehigh University

Optimization Convergence Analysis Nonconvex Optimization Augmented Lagrangian Method

Aug 12, 2026math.OC

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We show that under certain connectivity conditions, SK is a polynomial-time algorithm for doubly stochastic matrix scaling. With the developed tools, we showcase the local suboptimality of SK and provide accelerated variants. Finally, for dense matrices, we improve the complexity of existing first-order matrix scaling algorithms from

O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})

to

O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})

.

Wenzhi Gao, Zhaonan Qu, Yinyu Ye +1

ICME, Stanford University · Google · Department of Management Science and Engineering, Stanford University

Optimization Convergence Analysis

Aug 5, 2026stat.ML

Stable Density Ridges: Consistency and Convergence of Subspace Constrained Mean Shift

The Subspace Constrained Mean Shift (SCMS) algorithm is a popular nonparametric method for extracting density ridges, which serve as a low-dimensional representation of high-dimensional data. It is a widely held belief in the literature that SCMS trajectories converge to the classical density ridge, which we call the "static ridge", defined via the density gradient and the eigenvalues and eigenvectors of the density's Hessian. In this paper, we demonstrate that this assumption does not hold in general, as the static definition fails to account for the rotation of the trailing eigenspace along the continuous flow of the algorithm's underlying vector field. To resolve this, we propose a paradigm shift by introducing the "stable ridge", a novel geometric structure defined through the lens of dynamical systems and the Jacobian of the projected density gradient. We prove that this stable ridge is the true theoretical target of the SCMS algorithm. Building upon this foundation, we develop a generalized SCMS framework utilizing a constant step size, establishing its uniform R-linear convergence and topological surjectivity onto the stable ridge. We further derive the rates of convergence for estimating the stable ridge in terms of the Hausdorff distance. Finally, we expose that the original SCMS algorithm suffers from polynomial-time computational complexity, which is caused by implicitly coupling the step size to the smoothing bandwidth via the Mean Shift operator, and demonstrate how our generalized framework provides a statistically consistent and more efficient solution.

Wanli Qiao

Optimization Convergence Analysis

Aug 3, 2026math.OC

Non-KKT Accumulation in Entropic Mirror Descent

For mirror descent generated by a Legendre kernel, perhaps one of the most basic question in optimization is this: must every accumulation point of a bounded mirror descent sequence be Karush--Kuhn--Tucker (KKT) stationary under proper stepsizes? We show that the answer is no. A longstanding obstacle to resolving this question is the boundary blow-up of the Legendre gradient: it keeps every mirror step in the interior, while at a boundary limit, the inverse entropy metric vanishes on active coordinates and can erase the dual-feasibility in the KKT system. We construct

C^\infty

objectives and bounded sequences generated by the Shannon-entropic mirror descent on the nonnegative orthant

\R_+^n

, for every

n\geq 3

, and on the probability simplex

Δ_n

, for every

n\geq 4

, such that, in each case, the set of accumulation points is a smooth boundary circle containing a nonempty relatively open arc of non-KKT points. The steps satisfy

α_k\asymp k^{-β}

with

β\in(1/2,1)

, the objective values are nonincreasing, and the objectives are entropy-relatively smooth. Hence the pathology stems from the degeneracy of the Bregman geometry at the boundary, rather than from failure of descent, or improper stepsizes. To the best of our knowledge, these provide the first counterexamples to KKT accumulation for bounded mirror descent sequences with nonincreasing objective values.

Kuangyu Ding, Kim-Chuan Toh

School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA. · Department of Mathematics and Institute of Operations Research and Analytics, National University of Singapore, Singapore 119076.

Optimization Convergence Analysis Mirror Descent

Jul 27, 2026cs.LG

Global Convergence of DGM and PINN Algorithms for Solving Nonlinear PDEs

The Deep Galerkin Method (DGM) and Physics Informed Neural Networks (PINNs) have become widely-used methods for solving partial differential equations (PDEs) in the rapidly growing field of scientific machine learning. In these methods, a neural network is trained to approximate the PDE solution by using (stochastic) gradient descent to minimize the PDE residual of the neural network. Due to the non-convexity of the PDE residual objective function, the trained neural network may, in principle, only converge to a local minimizer of the objective function (which would not be a solution of the PDE). Therefore, there is a longstanding question regarding the mathematical foundations of these algorithms, and it is highly valuable to establish that the trained neural network will converge to the PDE solution. In this paper, we consider a class of semilinear PDEs with nonlinearities in the solution and its first derivative. For this class of PDEs, we prove that neural networks trained with gradient descent to minimize the PDE residual objective function will converge to the PDE solution as the network width and training time

\rightarrow \infty

.

Justin Sirignano, Konstantinos Spiliopoulos, Samuel Cohen

Mathematical Institute, University of Oxford · Department of Mathematics and Statistics, Boston University

Neural PDE Solvers Optimization Convergence Analysis PDE Solving Physics-Informed ML

Jul 26, 2026math.OC

When Rates Are Geometric: Rate-Certificate Transfer for Contact Splittings in Optimization

Discrete optimization algorithms are often analyzed through continuous-time limiting ODEs, but a convergence certificate for the ODE is not automatically one for the discrete algorithm. We develop contact Hamiltonian systems as a setting where the transfer can be made precise. A contact Hamiltonian

H

on

J^1(\mathbb{R}^n)

obeys the intrinsic decay identity

\dot H = -H\,\partial_s H

, so an augmented energy

\mathcal{E}

built from

H

, together with the conformal rate

\partial_s H

, is a continuous-time rate certificate whenever

\mathcal{E}

controls the objective gap. Our main theorem states, under three named and independently checkable hypotheses, that an order-

r

contact splitting with step

h

transfers this certificate over the finite horizon set by backward error analysis. The discrete decay envelope is governed by the modified conformal factor up to

O(h^r)

perturbations plus a backward-error shadowing defect, and the mechanism is inherited exactly because the modified Hamiltonian is itself a contact Hamiltonian. Quadratic heavy ball is a fully solvable example: its projected dissipative-leapfrog spectrum agrees with established conformal-symplectic optimization theory, while the augmented contact Hamiltonian yields a sharp objective-to-certificate comparison that verifies the transfer hypotheses. For strongly convex objectives with state-dependent damping, an explicit Bregman-type Lyapunov certificate instead transfers by an auxiliary-shadowing corollary. The decomposition

H=K+V+D

into kinetic, objective-encoding potential, and dissipation terms serves as a design template, with a catalogue of closed-form sub-flows including contact-specific damping families. Numerical experiments confirm the predicted conformal-factor tracking orders and show competitive performance on ill-conditioned benchmarks and deep-learning tasks.

George A Kevrekidis

Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218, USA

Optimization Convergence Analysis Hamiltonian Dynamics

Jul 24, 2026stat.ML

Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model

Zermelo's algorithm is a classical method for computing the maximum likelihood estimator in the Bradley--Terry (BT) model, but its convergence can be slow in practice. To accelerate computation, Newman introduced a family of Zermelo-type fixed-point iterations parameterized by

α

, with Zermelo's algorithm recovered at

α=1

. Empirical evidence suggests that the choice

α=0

often converges substantially faster, making it a promising alternative, yet the mechanism underlying this acceleration remains elusive. This paper provides theoretical insight into this phenomenon through a systematic local convergence analysis. We derive closed-form expressions for local convergence factors under synchronous and asynchronous updates and analyze their dependence on

α

via spectral analysis of the associated Jacobian matrices. For synchronous updates, we show that the algorithm may fail to converge when

α<1

, and its local convergence factor is quasi-convex in

α

under the population BT model. In contrast, asynchronous updates are always locally convergent, and their local convergence factor is provably monotonically increasing in

α

under the population BT model of consistently ordered bipartite comparison graphs, establishing the optimality of

α=0

in this setting. We further establish asymptotic approximation results for the population convergence factors under the BT model, justifying their practical relevance. Numerical experiments on synthetic and real-world datasets confirm the theory. Our analysis complements existing convergence results and shows that the acceleration of

α=0

arises not only from the parameter choice but, more importantly, from the use of asynchronous updates.

Ruijian Han, Ding Lu, Yiming Xu

Department of Data Science and Artificial Intelligence, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong SAR · Department of Mathematics, University of Kentucky, Lexington, KY, 40506, USA

Optimization Convergence Analysis Bradley–Terry Model

Jul 23, 2026math.OC

Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$

Barzilai--Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. In particular, a central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. We provide a negative answer to this question. Specifically, for every finite dimension

n\geq4

, we construct a nonempty open, hence positive-Lebesgue-measure, family of strictly convex quadratic problems and initial points for which the long Barzilai--Borwein method (BB1) converges but cannot converge root-superlinearly. More precisely, with the explicit constants

ρ_{\min}=10^{-6},ρ_{\max}=0.61

, every spectral component of the gradient is bounded above and below by the corresponding geometric sequence. Consequently, the gradient norm and the energy norm of the error satisfy two-sided geometric estimates with the same rates, while the objective gap satisfies the corresponding estimates with squared rates. In particular, all three quantities are bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial, based on a computer-assisted proof of a nonresonant, attracting seven-cycle of the projectivized BB dynamics in dimension four.

Dawei Li, Xiaotian Jiang, Mingyi Hong

University of Minnesota

Optimization Convergence Analysis

Jul 16, 2026cs.LG

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

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

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

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

Optimization Convergence Analysis Stochastic Optimization Convergence Federated Learning Stochastic Gradient Descent

Jul 11, 2026cs.LG

Sharper Analysis of Single-Loop Methods for Bilevel Optimization

Bilevel optimization underpins many machine learning applications, including hyperparameter optimization, meta-learning, neural architecture search, and reinforcement learning. While hypergradient-based methods have advanced significantly, a gap persists between theoretical guarantees and practical single-loop implementations required for efficiency. We bridge this gap by establishing sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods, leveraging our proposed analytical framework, decoupled norm analysis (DNA). For AID, we improve the convergence rate from

\mathcal{O}(κ^6/K)

to

\mathcal{O}(κ^5/K)

, where

κ

is the condition number of the inner-level problem. For ITD, we prove that the asymptotic error is

\mathcal{O}(κ^2)

, exactly matching the known lower bound and improving upon the previous

\mathcal{O}(κ^3)

guarantee. Numerical experiments on synthetic and real tasks corroborate our theoretical findings.

Yubo Zhou, Jun Shu, Luo Luo +4

School of Mathematics and Statistics, Xi’an Jiaotong University · School of Data Science, Fudan University · 3SGIT AI Lab, State Grid Corporation of China +1

Optimization Convergence Analysis Bilevel Optimization

Jul 10, 2026cs.LG

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

Schedule-Free methods have attracted growing interest for alleviating the burden of designing and tuning a learning rate scheduler, while matching and sometimes even outperforming optimizers with tuned schedulers. Despite their strong empirical results, their convergence theory in nonconvex optimization, where modern machine learning objectives typically arise, has remained largely unexplored. In this paper, we provide worst-case analyses of Schedule-Free gradient descent and Schedule-Free stochastic gradient descent, in their standard form and without auxiliary modifications or restrictive conditions, for smooth but possibly nonconvex objectives. Based on a Lyapunov analysis derived from the continuous-time limiting ordinary differential equation associated with these methods, we show that Schedule-Free gradient descent and Schedule-Free stochastic gradient descent achieve the optimal worst-case convergence rates attainable among first-order methods. We further formulate Schedule-Free gradient descent as a nonautonomous dynamical system and prove strict-saddle avoidance under an arbitrarily small one-time perturbation. These theoretical results provide a better understanding of the strong performance that Schedule-Free methods demonstrate.

Jiseok Chae, Donghwan Kim

Natural Science Research Institute KAIST Daejeon, Republic of Korea · Department of Mathematical Sciences KAIST Daejeon, Republic of Korea

Learning Rate Scheduling Optimization Convergence Analysis Nonconvex Optimization Gradient Descent Dynamics Stochastic Gradient Descent

Jun 30, 2026cs.LG

On the Convergence of Self-Improving Online LLM Alignment

The Self-Improving Alignment (SAIL) algorithm addresses distribution shift by reducing a bilevel formulation of the problem to an efficient, single-level method. Empirically, SAIL has demonstrated strong performance on this task. However, a formal analysis of its convergence properties has been lacking. We identify a key theoretical challenge: the standard SAIL objective function is not guaranteed to be strongly concave due to unfavorable properties of its Hessian. To address this limitation, we propose a regularized objective, SAIL-RevKL, which incorporates a reverse Kullback-Leibler (KL) divergence penalty to improve the optimization landscape. Our central theoretical contribution is to prove that this regularized objective satisfies the Polyak-Lojasiewicz (PL) condition within a bounded parameter space. We establish global convergence guarantees, achieving a near-linear sample complexity. We further validate the effectiveness and stability of SAIL-RevKL through empirical evaluations, demonstrating that it outperforms the vanilla SAIL on both MuJoCo benchmarks and LLM alignment tasks.

Xudong Wu, Pangpang Liu, Vaneet Aggarwal +1

The University of Hong Kong, Hong Kong SAR · Yale University, New Haven, CT, USA · Purdue University, West Lafayette, IN, USA

LLM Alignment Optimization Convergence Analysis KL-Regularized RL Language Model Self-Improvement

Jun 28, 2026cs.LG

How AI settled the complexity of the oldest SGD algorithm

In 1937, Stefan Kaczmarz proposed a simple algorithm for solving systems of linear equations. This algorithm turned out to be the earliest known example of stochastic gradient descent, a ubiquitous computing paradigm that drives the training of modern AI models such as ChatGPT and Gemini. Now, those AI models have joined forces to discover the worst-case complexity of the Kaczmarz algorithm. This paper tells the story of how it happened.

Michał Dereziński, Xiaoyu Dong

University of Michigan · National University of Singapore

Optimization Convergence Analysis Stochastic Gradient Descent

Jun 26, 2026cs.NE

Analysis of Parameter Settings for the Bat Algorithm Using Variance Evolution

Parameter settings in evolutionary algorithms and metaheuristics are important because such parameter values can influence the performance of algorithms under evaluation. For a given algorithm, there are many different numerical experiments to show that the algorithm can work well in practice; however, in most cases there is no theoretical analysis of parameter settings. In this work, we show that theoretical analysis using the theory of dynamical systems and evolution of population variance can give some good results in terms of parameter ranges for the bat algorithm. We also show that results from numerical experiments are consistent with theoretical bounds. Such analyses can provide good insights from different perspectives about the algorithmic characteristics such as variance evolution, transition between exploration and exploitation as well as convergence behaviour.

Xin-She Yang, Mehmet Karamanoglu

Faculty of Science and Technology, Middlesex University, The Burroughs, London NW4 4BT, United Kingdom.

Exploration-Exploitation Tradeoff Evolutionary Optimization Optimization Convergence Analysis Metaheuristic Optimization

Jun 26, 2026math.OC

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal--dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.

Shuang Li, Zhihui Zhu, Qiuwei Li

Department of Electrical and Computer Engineering, Iowa State University, Ames, Iowa 50014, USA · Department of Computer Science and Engineering, Ohio State University, Columbus, Ohio 43210, USA · DAMO Academy, Alibaba Group US, Bellevue, Washington 98004, USA

Optimization Convergence Analysis Distributed Optimization Alternating Direction Method of Multipliers Nonconvex Optimization

Jun 26, 2026cs.LG

Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator. While linear averaging preserves the monotonicity of gradient updates, this property is often violated when gradients are aggregated non-affinely, as in modern pipelines enforcing constraints like adaptivity, privacy, robustness or fairness. Whether it is possible to design non-affine aggregation rules that maintain monotonicity has remained an open question. We answer this question negatively: we prove that the monotonicity of aggregated gradients is preserved if and only if the aggregation rule is positively affine. Consequently, non-affine aggregation prevents steady convergence and substantially degrade algorithmic stability. We quantify these drawbacks and propose a path forward by identifying sufficient conditions under which monotonicity can be restored. Our results provide a unified theoretical framework explaining the disparate failure modes observed in modern learning systems.

Thomas Boudou, Batiste Le Bars, Nirupam Gupta +1

PreMeDICaL team, Inria, Idesp, Inserm, Universit´e de Montpellier, Montpellier, France · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France · Department of Computer Science, University of Copenhagen, Copenhagen, Danemark

Optimization Convergence Analysis Algorithmic Stability

Jun 24, 2026cs.LG

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

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

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

, leaving a gap with the

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

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

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

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

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

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

p

-moment condition,

p \in (1,2]

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

T

, this algorithm achieves a high-probability stochastic error of

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

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

Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

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

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

Jun 18, 2026cs.LG

Global Convergence of Gradient Descent for Score Matching in Gaussian Mixtures via Reverse Fisher Divergence

The score matching problem is a central training objective in modern generative modeling, diffusion models, fitting unnormalized statistical models, and inverse problems. A standard approach is to minimize the forward Fisher divergence, where the expectation is taken with respect to the teacher distribution. However, recent results show that even in simple Gaussian mixture model settings, this objective can lead to undesirable and initialization-dependent convergence behavior. In this paper, we study an alternative objective: the reverse Fisher divergence, where the expectation is taken with respect to the student distribution. We analyze gradient descent (GD) for fitting Gaussian mixture models and show that this change in the objective leads to significantly better optimization properties. First, when the teacher distribution is a single Gaussian and the student is a Gaussian mixture model with fixed weights and identity covariances, we prove the global convergence of GD from arbitrary initializations. Second, we extend the analysis to the case where the teacher is also a Gaussian mixture model and prove global convergence guarantees under a global random initialization scheme and a

\widetildeΩ(1)

-separation assumption on the target means. In particular, with high probability, each student component converges near its closest teacher component, and we provide conditions under which the student distribution converges in total variation distance. Our proofs rely on a new Lyapunov-based analysis of the gradient descent dynamics, showing that the reverse Fisher divergence has a much more favorable optimization landscape than the forward Fisher divergence.

Alexander Tyurin

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

Score Matching Optimization Convergence Analysis Gaussian Mixture Models Gradient Descent Dynamics

Jun 18, 2026math.OC

Semiglobal Input-Delay Tolerance Algorithm for Distributed Nonconvex Optimization of Networked Nonlinear Systems

This paper studies a class of distributed optimization problems in networked nonlinear systems (NNSs) subject to input delays and consensus constraints. It introduces input-delay tolerant semiglobal convergence (IDTSC), meaning that for any prescribed compact initial set there exists an admissible delay bound under which the optimal solution is computed within consensus constraints and all node states converge to the solution. Building on a hierarchical design and input-to-state stability analysis, a new semiglobal input-delay tolerant (SIDT) algorithm is developed that practically achieves IDTSC for distributed optimization under the coupling between input delays and nonlinear dynamics. Further, by relaxing strict convexity requirements through the Polyak-Łojasiewicz condition, the SIDT algorithm broadens its applicability to nonconvex optimization. Finally, numerical experiments corroborate the theory on NNSs with input delays.

Jing-Zhe Xu, Zhi-Wei Liu, Ming-Feng Ge +2

School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China · School of Mechanical Engineering and Electronic Information, China University of Geosciences, Wuhan 430074, China

Dynamical Systems Optimization Convergence Analysis Distributed Optimization Nonconvex Optimization

Jun 16, 2026math.OC

Beyond IGO-Flow: Toward Convergence Analysis of IGO in Continuous Spaces

Information-Geometric Optimization (IGO) provides a unified framework for black-box optimization by interpreting the adaptation of a search distribution as a natural gradient update. Despite its conceptual importance, the convergence theory of IGO remains limited: most existing results concern continuous-time idealizations such as the IGO flow, rather than discrete-time updates with non-infinitesimal learning rates. In this paper, we study discrete-time IGO in continuous spaces, formulated as natural gradient updates in the expectation-parameter coordinates of an exponential family. In particular, we analyze IGO over the multivariate Gaussian family on strongly convex quadratic objective functions. Our analysis covers a setting that simultaneously incorporates full covariance adaptation, a fixed positive learning rate, and quantile-based weights. In this setting, we prove that the covariance matrix converges to the zero matrix. We further show that the mean vector converges to the global optimum, provided that the condition number of the appropriately scaled covariance matrix is bounded at sufficiently frequent iterations. These results advance the convergence theory of IGO and help bridge the gap between the mathematical theory of IGO and practical covariance-adaptive search methods such as CMA-ES.

Ryosuke Kimura, Youhei Akimoto

University of Tsukuba, Tsukuba, Japan · RIKEN Center for Advanced Intelligence Project, Tokyo, Japan

Information Geometry Optimization Convergence Analysis Black-Box Optimization

Jun 13, 2026math.OC

Coercivity and Local Convergence of Physical Learning in Linear Circuits

Physical learning methods train physical networks to perform computational tasks using only local update rules, exploiting the physics of the system to handle the global transfer of information. We provide the first local convergence analysis of three such methods -- Equilibrium Propagation (EP), Coupled Learning (CL), and a new method we call Adjoint Coupled Learning (AL) -- for linear circuits, in the limit of small-nudging for both discrete and continuous time. EP and AL perform gradient descent on a natural loss function, while CL follows modified dynamics with an additional cubic correction. Assuming the existence of a solution, we identify a coercivity condition, expressed as a rank condition on a matrix built from the network's incidence structure, under which the training loss decays exponentially and the parameters converge to the solution manifold. We show that coercivity can fail by exhibiting a kite circuit in which a symmetry causes the coercivity constant to degenerate on the solution manifold, but prove using Sard's theorem that such degeneracies are non-generic: coercivity holds at every point of the solution manifold for almost every choice of desired output.

Joshua A. McGinnis, Xinbo Li, Yoichiro Mori

Department of Mathematics, University of Pennsylvania, Philadelphia.

Equilibrium Propagation Optimization Convergence Analysis Local Learning

Jun 12, 2026math.OC

Operator Calculus for Population-Based Optimization: Modular Convergence and Finite-Population Guarantees

Population-based optimizers combine update rules such as mutation, selection, and recombination. When one rule changes, it is often unclear which convergence guarantees survive or how the new combination should be assessed. We develop an operator calculus: an operator is a population-update rule, and the calculus specifies how separately checked effects can be combined. Under explicit regularity and small-step conditions, the leading changes caused by the updates add, yielding reusable building blocks for convergence analysis. The framework distinguishes finding and retaining a good solution, reducing the population's mean objective, and concentrating candidates near an optimizer, and identifies the extra approximation conditions needed for finite evaluation-budget guarantees. Applications include distribution adaptation, recombinative evolution, and consensus dynamics, with verified nonconvex cases. Controlled experiments on a common nonconvex problem collection show how component effects change with population geometry and the performance measure: a rule can worsen the mean objective yet produce better candidates.

Pekka Malo, Lauri Viitasaari, Patrik Nummi +3

Aalto University, Department of Information and Service Management, Finland. · Aalto University, Department of Information and Communications Engineering, Finland. · Indian Institute of Management Ahmedabad, Operations and Decision Sciences, India. +1

Evolutionary Optimization Optimization Convergence Analysis Metaheuristic Optimization Nonconvex Optimization Mean-Field Theory

Jun 10, 2026math.OC

Last-Iterate Convergence of Optimistic Multiplicative Weight Update

Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.

Francesco Orabona

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

Last-Iterate Convergence Optimization Convergence Analysis Min-Max Optimization Convergence Analysis