Nonconvex Stochastic Optimization

Momentum

10 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 67

Oct 8, 2026cs.LG

Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with

O(δ^{-1}\varepsilon^{-3})

stochastic gradient queries or

O(dδ^{-1}\varepsilon^{-3})

function-value queries, where

δ

is the Goldstein radius,

\varepsilon

is the stationarity tolerance, and

d

is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.

Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

The University of Tokyo · The University of Tokyo, The University of Osaka, and RIKEN

Nonconvex Stochastic Optimization Nonconvex Optimization

Ask PDF

Oct 7, 2026math.OC

Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping

Heavy-tailed noise has been widely observed in modern machine learning, motivating the use of methods like gradient clipping and normalization. While these methods are well understood in centralized settings, much less is known in decentralized ones, where applying a nonlinearity to local gradients affects both optimization and consensus. Recent works on decentralized non-convex optimization have studied both clipping and normalization under heavy-tailed noise, with clipping yielding suboptimal rates and normalization needing local momentum or mini-batches to converge. This raises the question: can a baseline decentralized method using a nonlinearity achieve optimal convergence rates under heavy-tailed noise? We answer affirmatively with clipped decentralized SGD (

\mathtt{DSGD}

). For smooth non-convex costs under bounded

p

-th moment noise,

p \in (1,2]

, we show that clipped

\mathtt{DSGD}

achieves order-optimal rates both with high probability and in expectation. Moreover, we establish a linear speed-up in the number of agents, which, to our knowledge, has not been shown for decentralized methods with clipping. The key technical ingredient is a sharp analysis of the consensus gap that exploits the structure of clipping, relegating network effects to higher-order terms. Our results highlight an important distinction between clipping and normalization in decentralized settings: while normalized

\mathtt{DSGD}

can fail to converge, clipping retains magnitude information, enabling

\mathtt{DSGD}

to be convergent and order-optimal. Numerical experiments validate our theory.

Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Decentralized Optimization Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization Nonconvex Stochastic Optimization Gradient Clipping

Ask PDF

Oct 5, 2026math.OC

Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of

n

nodes, with the goal of finding an

(δ,ε)

-Goldstein stationary point. The best existing algorithm achieves

O(δ^{-1}(ε^{-3}+dε^{-1}))

sample complexity and

\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))

communication complexity, where

d

is the problem dimension and

γ

is the spectral gap of the communication matrix. However, the polynomial dependence on

d

can be a major bottleneck in high-dimensional regimes. In this paper, we propose a novel algorithm that achieves

O(δ^{-1}ε^{-3})

sample complexity and

\widetilde{O}(γ^{-1/2}δ^{-1}ε^{-3})

communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on

d

can be removed with only logarithmic additional communication.

Yuanyu Wan, Lan Xue, Haomin Bai +2

School of Software Technology, Zhejiang University · State Key Laboratory of Blockchain and Security, Zhejiang University · School of Artificial Intelligence, Nanjing University +1

Nonconvex Stochastic Optimization Decentralized Optimization

Ask PDF

Oct 4, 2026cs.LG

Smoothed Gradient Method for Nonconvex Federated Stochastic Bilevel Optimization

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

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

and a communication complexity of

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

, where

κ

denotes the condition number and

ε

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

κ

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

Xinwen Zhang, Peiran Yu, Zhaosong Lu +1

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

Gradient Descent Nonconvex Stochastic Optimization Bilevel Optimization Stochastic Optimization Convergence

Ask PDF

Oct 1, 2026math.OC

Optimal Stochastic Bilevel Optimization with First-Order Oracles

We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-

p

finite differences. For any fixed finite smoothness order

p\ge1

in the lower-level variable, MRT-FD finds an

\varepsilon

-stationary point using

\mathcal{O}(\varepsilon^{-4-2/p})

stochastic gradient queries. We also prove a matching

Ω(\varepsilon^{-4-2/p})

oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on

\varepsilon

is optimal for every fixed finite

p

, closing the upper--lower complexity gap in this stochastic first-order oracle setting.

Linxuan Pan, Junchi Yang

The Chinese University of Hong Kong, Shenzhen

Oracle Complexity Nonconvex Stochastic Optimization Bilevel Optimization

Ask PDF

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

Ask PDF

Oct 1, 2026math.OC

Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization

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

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

for finding an

ε

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

Wei Jiang, Rui Yan, Sifan Yang +3

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

Stochastic Optimization Momentum Methods Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Ask PDF

Sep 30, 2026cs.LG

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

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

(\mathcal L_0,\mathcal L_1,q)

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

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

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

Hanyng Peng, Hui Wang, Yue Yu

Pengcheng Laboratory, Shenzhen, China

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

Ask PDF

Sep 24, 2026stat.ML

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

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

T^{-1/3}

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

Lb_2Δ^3\varepsilon^{-6}

and

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

stochastic terms, where

Δ

is the initial objective gap and

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

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

p>2

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

T

stationarity, and stochastic

L^p

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

Wei Biao Wu

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

Ask PDF

Sep 24, 2026cs.LG

Precise Convergence Speed of Clipped SGD

We present a tightened convergence analysis of clipped gradient descent on

(L_0, L_1)

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

\ell_2

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

η\leq 1 / (9 β)

η< 1 /β

where

β= L_0 + c L_1

for clipping constant

c

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

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

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

with matching speed, and lower the final achievable loss from

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

to the more precise

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

David A. R. Robin

LAMSADE, Université Paris-Dauphine, PSL Research University

Gradient Clipping Nonconvex Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Sep 16, 2026cs.LG

Revisiting Distributed Sign-Based Variance Reduction

Sign-based methods reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction methods fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both nonconvex stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. As a result, we can obtain the convergence rates of

O(\sqrt{d/K}+\sqrt d (a/(nK))^{1/3})

for the

\ell_1

-norm and

O(\sqrt{a/K}+\sqrt a/(nK)^{1/3})

for the

\ell_2

-norm. Here,

K

is the iteration number,

n

is the number of workers,

d

is the dimension, and

a=1+ω

, with

ω

denoting the compressor's relative variance. For finite-sum problems with

M

components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are

O(M+d\sqrt{aM}ε^{-2})

and

O(M+a\sqrt M\ epsilon^{-2})

for

\ell_1

and

\ell_2

gradient norms at most

ε

, matching the corresponding bounds in centralized settings.

Wei Jiang, Zechao Li, Lijun Zhang

School of Computer Science and Engineering, Nanjing University of Science and Technology, China · National Key Laboratory for Novel Software Technology,Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Sign-Based Optimization Communication-Efficient Distributed Training Distributed Optimization Nonconvex Stochastic Optimization Variance Reduction

Ask PDF

Sep 14, 2026math.OC

Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization

This paper studies projection-free algorithms for stochastic constrained multi-level compositional optimization. In this context, the objective function is a nested composition of several smooth functions, and the decision set is closed and convex. Since projection onto the constraint set can be computationally expensive, we develop projection-free methods that rely on linear minimization oracles. For non-convex objectives, we propose variance-reduced projection-free algorithms and establish complexity guarantees under both the Frank-Wolfe gap and the gradient mapping criteria. We also develop momentum-based methods that achieve convergence guarantees under weaker smoothness assumptions. Additionally, by using a stage-wise design, we derive a parameter-free variant that preserves the same complexities for the Frank-Wolfe gap. Such a design can be further used to develop algorithms for convex and strongly convex functions whose rates match those of single-level projection-free counterparts. Finally, we consider finite-sum problems and derive complexities for non-convex, convex, and strongly convex objectives. Numerical experiments across multiple tasks demonstrate the effectiveness of the proposed methods.

Wei Jiang, Sifan Yang, Wenhao Yang +4

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

Stochastic Optimization Nonconvex Stochastic Optimization Constrained Optimization

Ask PDF

Sep 14, 2026cs.LG

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"{o}lder Smoothness

Classical convergence guarantees for stochastic gradient methods typically assume Lipschitz-smooth objectives and finite-variance gradient noise, both frequently violated in practice. In contrast, we study nonconvex stochastic optimization under the joint relaxation of these assumptions: objectives with

(L,s)

-H"older continuous gradients,

s\in(0,1]

, and gradient noise satisfying only a bounded

\alpha

-th moment condition for

\alpha\in(1,2]

. We establish three convergence results. Firstly, that standard SGD converges at rate

O(T^{-s/(1+s)})

whenever

\alpha\ge1+s

, extending the classical nonconvex SGD rate to heavy-tailed noise and H"older smoothness simultaneously. Secondly, we analyze

\delta

-regularized gradient clipping (

\delta

-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of

O(T^{-2s(\alpha-1)/[(1+s)(2\alpha-1)]})

under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for

\alpha\ge1+s

while in the very heavy-tailed regime

\alpha<1+s

, it has a convergence rate

O(T^{-2s(\alpha-1)/[(\alpha-1)+s(2\alpha-1)]})

--- the first convergence guarantee in this regime for any stochastic gradient based method.

Misbah Uz Zaman, Anirbit Mukherjee

Department of Mathematics and Statistics Indian Institute of Science Education and Research Kolkata · Department of Computer Science The University of Manchester

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

Ask PDF

Aug 12, 2026math.OC

Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size

Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness. Their performance, however, remains sensitive to the step size: raw stochastic curvature estimates can fluctuate sharply, whereas line searches add repeated proximal evaluations. We introduce Ada-BPSG, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate. A mediant aggregates incremental secant information so that nearly singular local ratios receive little weight, and an explicit safeguard translates the resulting curvature estimate into the bounded step-size sequence required for convergence. This design yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces. We prove an

O(n/K)

ergodic rate for convex objectives, a restarted linear rate under relative quadratic growth, and an

O(1/K)

bound for a Bregman proximal residual in the nonconvex setting. On logistic regression and sparse nonnegative matrix factorization, Ada-BPSG combines low objective values with substantially less sensitivity to the initial step size than standard variance-reduced baselines, while avoiding line search.

Chenhan Jin, Shengze Xu, Binghui Xie +4

1The Chinese University of Hong Kong · University of Utah · 3Beijing Normal-Hong Kong Baptist University +1

Nonconvex Stochastic Optimization Adaptive Gradient Methods Stochastic Gradient Descent

Ask PDF

Aug 10, 2026math.OC

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

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

K=1

fresh-sample model, every randomized adaptive algorithm requires

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

queries to find a point with expected gradient norm at most

ε

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

Jikai Jin

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Ask PDF

Aug 5, 2026math.OC

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

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

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

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

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Ask PDF

Aug 4, 2026math.OC

Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework

Unit excitation (UE) is a common assumption in stochastic saddle avoidance: the stochastic error must have a uniformly positive component along every direction, in expectation. This condition gives a direct way to rule out convergence to strict saddles, but it also oversimplifies the actual noise structure, and does not match many stochastic optimization regimes. In overparameterized or interpolation models, the noise may vanish near stationarity. In finite-sum problems, the stochastic gradient noise may lie in a low-dimensional, data-dependent subspace. In these (common) scenarios, UE is naturally not satisfied. In this paper, we prove an abstract almost sure avoidance theorem for stochastic recursions without UE. The theorem replaces UE-type requirements by verifiable pathwise conditions. In applications, these conditions follow, e.g., from local smoothness and finite-moment assumptions under standard i.i.d. sampling, or from the finite-sum structure under without-replacement sampling. Since the stochastically sampled maps generally do not share a fixed point, the celebrated center-stable manifold argument used in deterministic analyses is not directly applicable. Instead, we use a path-dependent change of variables together with a pathwise Lyapunov--Perron-based proof strategy. As applications, we obtain strict saddle avoidance for stochastic mirror descent (including SGD) and for random reshuffling. For nonsmooth composite objectives, we prove avoidance results for a proximal-type stochastic gradient method. Combining these insights with suitable iterate convergence guarantees, this allows establishing convergence to local minimizers of the original objective function.

Junwen Qiu, Bohao Ma, Andre Milzarek +1

Industrial Systems Engineering and Management, National University of Singapore, Singapore. · School of Data Science, The Chinese University of Hong Kong, Shenzhen, China.

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Gradient Descent

Ask PDF

Jul 29, 2026cs.LG

The Convergence Behavior of Adam under Heavy-Tailed Noise

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

p

-th central moment for some

p \in (1,2]

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

(ρ,ε)

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

p

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

p=2

). Specifically, the

ε

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

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

for

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

, which simplifies to

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

when

p=2

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

ε

-dominant iteration complexity is

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

for

p\in(1,2]

, which simplifies to

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

when

p=2

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

Yijiang Pang

Michigan State University, East Lansing, USA

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

Ask PDF

Jul 28, 2026math.OC

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

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

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

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

σ^2\mapsto 2ΛG_σ^2

and

L^2\mapsto 2ΛL^2

, where

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

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

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

. The exactly noiseless specialization achieves

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

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

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

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

Zhaojun Peng

School of Computer Science Nanjing University of Information Science and Technology

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

Ask PDF

Jul 28, 2026cs.LG

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension

d

of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index

p>4/3

, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (

\texttt{QNSGD}

), which finds an

ε

-stationary point using

\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)

queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (

\texttt{QPSGD}

), which computes a solution with

ε

-optimal solution using

\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)

queries in expectation. These sharper bounds improve upon the classical lower bounds

Ω\big(ε^{-\frac{3p-2}{p-1}}\big)

for nonconvex problems and

Ω\big(ε^{-\frac{p}{p-1}}\big)

for convex problems in the low-dimensional regimes

d\lesssimε^{-\frac{p}{p-1}}

and

d\lesssimε^{-\frac{2-p}{p-1}}

, respectively.

Bin Luo, Chengchang Liu, Jonathan Allcock +2

The Chinese University of Hong Kong · Westlake University · Tencent Quantum Laboratory

Nonconvex Stochastic Optimization Heavy-Tailed Noise Quantum Machine Learning Heavy-Tailed Stochastic Optimization

Ask PDF

Jul 24, 2026cs.LG

On the Convergence of Stochastic Low-Rank Adaptation

Low-rank adaptation (LoRA) optimizes

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

over two adapters

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

and

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

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

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

. The prior analysis shows LoRA-GD takes

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

oracle calls to find an

ε

-stationary point such that

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

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

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

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

ε

-stationary point with

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

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

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

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

The Chinese University of Hong Kong · Westlake University

Nonconvex Stochastic Optimization Low-Rank Adaptation Stochastic Optimization Convergence

Ask PDF

Jul 21, 2026stat.ML

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

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

λ

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

W_1

and

W_2

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

Yiwei Zhou, Ziheng Chen

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

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

Ask PDF

Jul 20, 2026cs.LG

Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles

Stochastic nonconvex optimization is central to training deep networks and LLMs in modern machine learning. We give a black-box reduction from stochastic nonconvex optimization to ordinary static regret minimization in online convex optimization (OCO), thereby resolving the open problem posed by Chen and Hazan (2024). Our reduction maintains a predictable gradient tracker, while a black-box online learner

\mathcal{A}

selects a preconditioner that transforms this tracker into the update direction. Given a

β

-smooth function with a range bounded by

M

and an unbiased gradient oracle with variance bounded by

σ^2

, we bound the expected average squared gradient norm by

O(σ\sqrt{Mβ/T}+\sqrt{Mβ}\mathrm{Reg}_T(\mathcal{A})/T+\frac{Mβ}{T})

, where

\mathrm{Reg}_T(\mathcal{A})

is the static regret of

\mathcal{A}

. Thus, any OCO oracle with

O(\sqrt{T})

regret recovers the classical

O(T^{-1/2})

convergence rate. We further extend the framework to nonsmooth nonconvex objectives, still relying only on ordinary static regret, and attain the optimal convergence rate for Goldstein-type stationarity. Finally, we conduct numerical experiments on nonconvex objectives to illustrate how the reduction exploits online-selected preconditioners while using the same stochastic-oracle budget as stochastic gradient descent.

Haichen Hu, David Simchi-Levi

Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT

Nonconvex Stochastic Optimization Adaptive Gradient Methods

Ask PDF

Jul 7, 2026cs.LG

K-ABENA: K-Adaptive Backpropagation with Error-based N-exclusion Algorithm : (Compensated Loss-Based Sample Exclusion with Unbiased Gradient Estimation)

We present K-ABENA (K-Adaptive Backpropagation with Error-based N-exclusion Algorithm), a selective gradient computation framework that reduces per-iteration training cost by excluding a fraction of low-loss ("minor") observations from the backward pass. Its canonical form (v3) combines a defensive-mixture sampling design over the minor set with Horvitz-Thompson inverse-probability reweighting, yielding a design-unbiased Horvitz-Thompson gradient estimator (Lemma 2) and whose self-normalized practical variant carries a bias of order O(1/m) with an explicit constant (Lemma 3). We prove an O(1/sqrt(T)) non-convex convergence guarantee for SGD under the estimator, with an additive term that quantifies the residual bias (Theorem 1). We further prove that uncompensated loss-based selection - a family that includes OHEM, SBP, and the two earlier K-ABENA variants - admits no stationary point at any minimizer where its selection bias is bounded away from zero (Proposition 2), and we quantify this failure empirically: at 0.17% class imbalance, uncompensated variants reach test AUC 0.53-0.62 versus 0.9998 for full-batch SGD, while the compensated estimator attains 0.9991 at identical 28.4% compute savings. On real datasets (Breast Cancer, Digits, Wine, Diabetes) the compensated estimator is statistically indistinguishable from full-batch SGD (paired permutation tests, p >= 0.5; Section 7) while saving 28-54% of per-epoch gradient computation. A biased "regularized mode" (the earlier half-domain variant) is retained as an option with a proven exact bias decomposition (Lemma 5) and quantified contraindications: it collapses to 0.386 accuracy under 40% label noise (baseline: 0.832) and to 0.53 AUC under extreme imbalance. Every advantage and every limitation reported in this paper is either proved or measured; all experiments are CPU-scale (NumPy/scikit-learn) and their scope is stated explicitly.

Jean-Francois Bonbhel

NeuroSoft IA, Qu´ebec City, Canada · YekoElite University, Brazzaville, Republic of Congo

Backpropagation Neural Network Optimization Importance Sampling Nonconvex Stochastic Optimization Adaptive Sampling Selection Bias+1

Ask PDF

Jul 6, 2026stat.ML

Non-asymptotic Convergence of Stochastic Gradient Descent in Score-based Generative Models

Score-based Generative Models (SGMs) have achieved impressive performance in data generation across a wide range of applications. While the statistical properties of their sampling procedures are increasingly well understood, the optimization dynamics underlying their training remain less explored. SGMs are typically trained by minimizing a weighted denoising score-matching objective, yet optimization guarantees with stochastic gradients remain limited. In this work, we study Stochastic Gradient Descent (SGD) for SGMs, contributing results in two complementary regimes. For general score parameterizations, we derive a non-convex analysis of SGD for the weighted denoising score-matching objective, making explicit how the resulting optimization bound depends on the loss weighting and time-sampling distribution. We then consider overparameterized two-layer ReLU networks and develop a Neural Tangent Kernel analysis tailored to diffusion training with stochastic gradients, yielding score-approximation error bounds along the SGD trajectory. Our analysis quantifies the role of the reweighting factor in these bounds, providing a theoretical characterization of weighting choices used in practice.

Stanislas Strasman, Sobihan Surendran, Sylvain Le Corff

SU, LPSM

Nonconvex Stochastic Optimization Score-Based Generative Modeling Stochastic Gradient Descent

Ask PDF

Jun 21, 2026cs.LG

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Federated learning (FL) is an emerging distributed machine learning paradigm that enables local devices to jointly train a global model while keeping data decentralized and private. We propose a variance-reduction based algorithm, VRA-FedSGD, for FL in the presence of heavy-tailed gradient noise and communication noise, where these noises are prevalent in large-scale machine learning over wireless networks and Internet of Things deployments. VRA-FedSGD employs a momentum variance reduction technique together with a nonlinear mapping to mitigate heavy-tailed gradient noise, and uses a variance-reduced aggregation mechanism to suppress heavy-tailed communication noise. In the mean sense, VRA-FedSGD achieves a convergence rate of {\small

\mathcal{O}\left(K^{-(p-1)/(2p-1)}\right)

} for nonconvex objective functions, where

p

is the tail index of heavy-tailed noise. In the almost sure sense, VRA-FedSGD achieves a convergence rate of

\tilde{\mathcal{O}}\left(K^{-(1-1/(p-ε))}\right)

for strongly convex objective functions, where

ε

is an arbitrarily small constant. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of VRA-FedSGD.

Shengchao Zhao, Yongchao Liu

School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Variance Reduction Heavy-Tailed Stochastic Optimization Federated Learning

Ask PDF

Jun 14, 2026cs.LG

SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums

Empirical risk minimization on massive datasets naturally exhibits a nested double finite-sum structure, where

N=nm

total samples are logically or physically partitioned into

n

blocks of size

m

(e.g., in pooled data silos, out-of-core learning, or deliberate stratification). While variance-reduced methods achieve optimal oracle complexities for nonconvex objectives, they suffer from severe scaling bottlenecks in this centralized regime. Recursive estimators, such as PAGE, require periodic global full-gradient refreshes over all

nm

samples, which are computationally expensive. Conversely, single-loop methods, such as SILVER, avoid such refreshes but require an impractical

\mathcal{O}(nm)

memory footprint to store a control variate for every sample. In this paper, we propose SILAGE, a variance-reduced algorithm that addresses this trade-off. By actively exploiting the double-sum structure, SILAGE eliminates periodic global full-gradient refreshes over all

nm

components (evaluating at most one local group gradient per iteration) while requiring only

\mathcal{O}(n)

memory. Furthermore, we provide a tight convergence analysis that avoids pessimistic worst-case Lipschitz constants. Instead, SILAGE's complexity natively adapts to the underlying data geometry via nested functional similarities: across-group (

δ_1

) and within-group (

δ_2

) heterogeneity. Our results improve existing state-of-the-art bounds in several practically relevant regimes.

Igor Sokolov, Laurent Condat, Peter Richtárik

*Center of Excellence for Generative AI, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia. · KAUST

Memory-Efficient Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Variance Reduction

Ask PDF

Jun 12, 2026math.OC

Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success

Non-Euclidean optimisation methods with matrix-valued updates, such as Muon and Scion, have recently shown strong empirical performance for training Transformer models, yet their theoretical advantages over Euclidean methods remain poorly understood. We address this gap in the heavy-tailed non-convex regime, where stochastic gradients have bounded

p

-th central moments,

p \in (1,2]

. We show that certain non-Euclidean methods achieve optimal sample complexity under stronger stationarity measures, while Euclidean methods incur additional dimension-dependent costs. As a consequence, for

m \times n

matrices, Muon finds an

\varepsilon

-stationary point in nuclear norm within

\mathcal{O}\left(\min\{m, n\} \frac{Δ_1 L}{\varepsilon^2} \left(\frac σ\varepsilon \right)^{\frac p {p-1}}\right)

samples, absorbing heavy-tailed noise without extra dimension dependence, unlike Euclidean methods. We further prove this sample complexity, including its dimension dependence, is optimal for all first-order methods under nuclear-norm stationarity. Experiments on large language models support our theory. Surprisingly, our results suggest that other Schatten geometries beyond the spectral geometry of Muon can perform competitively in certain settings.

Florian Hübler, Thomas Pethick, Suvrit Sra

Department of Computer Science, ETH Zurich, Switzerland · Department of Mathematics, Technical University of Munich, Germany · Munich Center for Machine Learning (MCML)

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Muon Optimizer Stochastic Optimization Convergence Matrix Optimization+1

Ask PDF

Jun 7, 2026math.OC

OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimality

Orthogonalized momentum updates, as used in Muon-style optimizers, have recently shown strong empirical stability in large-scale deep learning. However, most current orthogonalized methods are still paired with fixed, externally scheduled, or otherwise open-loop magnitude rules, so their scale is not directly calibrated from the realized optimization trajectory. Motivated by the closed-loop perspective behind Lipschitz-free and noise-adaptive methods, we propose OptMuon, a family of adaptive momentum orthogonalization methods for stochastic nonconvex optimization. OptMuon combines Muon-style polar-factor directions with a trajectory-dependent AdaGrad-Norm-type coefficient schedule, so that the update magnitude is determined by the observed gradient and momentum history rather than by a prescribed Lipschitz-dependent rule. The schedule does not use the smoothness constant, the variance level, or the bounded-gradient constant in parameter selection, and its running-maximum correction prevents isolated gradient spikes from causing excessive coefficient collapse. Under lower-boundedness, unbiased stochastic gradients with bounded variance, smoothness, and an almost-sure bounded stochastic-gradient condition, we prove two complementary expected-stationarity guarantees. OptMuon-A achieves the noise-adaptive rate

\tilde{\mathcal O}(T^{-1/2}+σ^{1/2}T^{-1/4})

under average smoothness, while OptMuon-I achieves

\tilde{\mathcal O}(T^{-1/2}+σ^{1/3}T^{-1/3})

under individual smoothness. In the zero-noise regime, both bounds automatically reduce to a nearly optimal deterministic first-order rate

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

without manual hyperparameter retuning. These results show that closed-loop scalar adaptation can be combined with Muon-style momentum orthogonalization while retaining noise adaptivity and zero-noise optimality up to logarithmic factors.

Ganzhao Yuan

Faculty of Computer Science and Artificial Intelligence Shenzhen University of Advanced Technology (SUAT), China

Momentum Methods Nonconvex Stochastic Optimization Muon Optimizer Stochastic Optimization Convergence Adaptive Gradient Methods

Ask PDF

Jun 3, 2026cs.LG

When Do Fewer Coordinates Suffice in DP-SGD?

Differentially private stochastic gradient descent (DP-SGD) injects noise into every updated coordinate, making the injected noise energy scale with the ambient parameter dimension

d

. We ask when private training can update fewer coordinates without losing the signal needed for optimization. We propose \textsc{TP-TopK} (Two-Phase TopK DP-SGD), a two-phase method for coordinate-sparse private training without public data, in which a private warm-up phase identifies a coordinate support used to guide the main training phase. We give a criterion characterizing when coordinate restriction can be beneficial, show via a nonconvex stationarity bound that under this condition the relevant noise term scales with the active dimension

k

rather than the full parameter dimension

d

, and provide a lower bound on the reliability of warm-up-based coordinate ranking. Experiments on MNIST, FMNIST, and CIFAR-10 show that learned coordinate supports can retain more gradient energy than size-matched random supports, with the largest gains when the active dimension is small and warm-up scores are informative.

Huiqi Zhang, Fang Xie

Guangdong Provincial Key Laboratory of IRADS, Beijing Normal-Hong Kong Baptist University Zhuhai, China

Differentially Private Stochastic Gradient Descent Nonconvex Stochastic Optimization Differential Privacy

Ask PDF

Momentum

Related topics

Latest papers 67