CS Paper Radar

Variance Reduction with Delayed Feedback for Non-Convex Optimization

Wei Jiang, Dingzhi Yu, Zechao Li

cs.LG math.OC ·submitted 2026-10-20 16:48 UTC · v1

Abstract

We study variance reduction for non-convex optimization when gradient evaluations return with a delay. The server can update the parameter while earlier evaluations remain unfinished. We first analyze an ordered recursive momentum estimator for stochastic optimization. Under average smoothness and bounded variance, its oracle complexity is $O(1+σ^2ε^{-2}+LΔ_f(1+σ/ε+τ)ε^{-2})$, where the target is an expected squared gradient norm of at most $ε^2$ and $τ$ bounds the feedback delay. We next study finite sums with $n$ components and obtain $O(n+LΔ_f(\sqrt n+\min\{τ,n-1\})ε^{-2})$ evaluations. An asynchronous snapshot variant continues updating during full-gradient computations under an explicit bound on their completion time. For the stochastic method, we further replace a maximum-delay bound by a bound on the weighted amount of missing feedback.

Closest papers

Nearest neighbours by meaning across the whole index.

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

cs.LG math.OC ·2026-11-17 ·Zhaosong Lu, Yifeng Xiao
published similarity 0.69
Abstract · Accepted by SIAM Journal on Optimization

In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an $ε$-$surely\ feasible\ stochastic\ optimal$ ($ε$-SFSO) solution, in which the constraint violation is deterministically bounded by $ε$, and the expected optimality gap is at most $ε$. While a recently proposed stochastic variance-reduced first-order penalty method can compute an $ε$-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an $ε$-SFSO solution and that for computing an $ε$-$expected\ feasible\ stochastic\ optimal$ solution, where both the expected constraint violation and the expected optimality gap are bounded by $ε$. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an $ε$-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.

0.33

Adaptive Variance Reduction across Smoothness and Noise Conditions

cs.LG math.OC ·2026-10-09 ·Wei Jiang, Yibo Wang, Sifan Yang, Lijun Zhang, Zechao Li
theory similarity 0.66
Abstract

In this paper, we study adaptive stochastic non-convex optimization under unknown smoothness and noise conditions. Our algorithms require no smoothness constant, noise bound, initial function gap, or oracle-regime label. We first propose a fixed-budget method that combines normalized momentum, recursive variance reduction, and a fresh gradient stage, followed by fresh validation of the candidates. We prove that the same output has expected gradient norm $O(T^{-1/4})$ under objective smoothness and bounded noise variance, $O(T^{-1/3})$ under average smoothness, and $O(T^{-1/2})$ for noiseless gradients, where $T$ counts individual gradient evaluations. We then develop an anytime algorithm whose three optimization paths preserve their endpoints across reporting and budget-extension boundaries. The same three rates hold at every deterministic query budget, although the algorithm receives no information about the budget $T$. The analysis combines a scale potential, a uniform second-moment bound, and accounting for candidates retained through unfinished blocks. An optional sample-mean selector further reduces cumulative validation work from $O(T)$ to $O(T^{2/3})$ while preserving these rates.

0.26

Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction

eess.SY math.OC ·2026-10-30 ·Silan Zhang, Yujie Tang
similarity 0.65
Abstract

We study decentralized composite finite-sum optimization over a fixed connected undirected network, where agents access local component functions through function evaluations and share a possibly nonsmooth convex regularizer. In this setting, standard two-point gradient estimators can retain nonvanishing variance at a solution, complicating their integration with gradient tracking. We propose Distributed Zeroth-Order Incremental Variance Reduction (Distributed ZIVR), which combines incrementally updated component-gradient estimates with a proximal gradient-tracking scheme. The method admits an implementation using a constant number of function evaluations per agent at every iteration, without intermittent full-component or full-coordinate refreshes. For convex smooth component functions and strongly convex local averages, we establish linear convergence up to a controllable finite-difference error. With the finite-difference radius chosen for the target accuracy, Chebyshev-accelerated mixing yields a per-agent oracle complexity of $\widetilde{O}(d(m+κ)\log(1/ε))$ for expected squared solution error $ε$, where $d$ is the dimension, $m$ is the number of components per agent, and $κ$ is the condition number. This matches the centralized ZIVR oracle bound, while the communication bound has only an inverse square-root dependence on the network spectral gap. Experiments on logistic and robust regression demonstrate rapid reduction of solution and consensus errors.

0.13

Convergence Analysis of STORM Under Different Geometries

cs.LG math.OC ·2026-10-01 ·Wei Jiang, Yibo Wang, Wenhao Yang, Rui Yan, Lijun Zhang +1 more
theory similarity 0.65
Abstract

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.

0.17

Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

cs.LG math.OCstat.ML ·2026-10-14 ·Zijun Chen, Zihan Zhang
similarity 0.65
Abstract

Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex $L$-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order $1/L$. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components $n$. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying $0<η\lesssim 1/(L(1 + \log(nK)))$, where $K$ is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit $1/n$ factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.

0.38

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness

cs.LG math.OCstat.ML ·2026-09-11 ·Misbah Uz Zaman, Anirbit Mukherjee
hot direction similarity 0.64
Abstract · 46 pages, 2 figures

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ölder continuous gradients, $s\in(0,1]$, and gradient noise satisfying only a bounded $α$-th moment condition for $α\in(1,2]$. We establish three convergence results. Firstly, that standard SGD converges at rate $O(T^{-s/(1+s)})$ whenever $α\ge1+s$, extending the classical nonconvex SGD rate to heavy-tailed noise and Hölder smoothness simultaneously. Secondly, we analyze $δ$-regularized gradient clipping ($δ$-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of $O(T^{-2s(α-1)/[(1+s)(2α-1)]})$ under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for $α\ge1+s$ while in the very heavy-tailed regime $α<1+s$, it has a convergence rate $O(T^{-2s(α-1)/[(α-1)+s(2α-1)]})$ --- the first convergence guarantee in this regime for any stochastic gradient based method.

0.25

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

cs.LG math.OC ·2026-08-12 ·Chenhan Jin, Shengze Xu, Binghui Xie, Kaiwen Zhou, Fan Jia +2 more
theory similarity 0.64
Abstract

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.

0.04

Variance-Reduced Stochastic Hessian-Driven Nesterov Acceleration with Adam-Style Preconditioning

cs.LG math.OCmath.NA ·2026-11-08 ·Yaxin Yu, Long Chen, Minfu Feng
theory similarity 0.64
Abstract · 27 pages, 5 figures

Stochastic first-order methods use sampled gradients to reduce per-iteration costs, but estimation errors can slow convergence and, in some settings, cause divergence. To improve gradient accuracy while retaining acceleration, we develop scalar and diagonal versions of VR-Adam-SHANG for smooth stochastic convex optimization. The methods combine STORM-type recursive estimation, Adam-style preconditioning, and SHANG's accelerated interpolation and correction, using at most two stochastic gradient evaluations per iteration without full-gradient refreshes. Under unbiased sampling, bounded variance, and mean-square smoothness of gradient noise, polynomial steps with prescribed initialization yield $O(1/K)$ mean-square gradient-estimation error and expected objective-gap bounds combining $O(1/K^2)$ initial-energy decay with an $O(1/\sqrt K)$ stochastic term after $K$ iterations. These guarantees require neither monotonicity of the preconditioner nor a uniform positive lower bound on its eigenvalues. The analysis also establishes polynomial-step convergence of projected nonrecursive Adam-SHANG-s, filling a gap in its original theory. Experiments compare the methods at matched sample-gradient budgets. In every tested setting, at least one of the two versions achieves the lowest mean terminal objective gap among all compared methods.

0.29