Accelerated Gradient Methods

Follow this topic Ask about this topic

Accelerated gradient methods seek faster optimization by improving on ordinary gradient descent, often using momentum or estimates of curvature. Classical approaches include Nesterov acceleration and heavy-ball momentum, while FISTA extends acceleration to problems with nonsmooth regularizers; newer variants combine these ideas with adaptive preconditioning, stochastic mini-batches, or distributed communication. They are used in machine learning and in structured tasks such as sparse optimization, matrix problems, and linear programming. A central challenge is that acceleration can be sensitive to noise, conditioning, and problem structure, so researchers study when fast convergence guarantees hold and when momentum or predetermined step sizes can fail.

Latest papers

44 papers7 papers in the last four weeks, up 40% on the four weeks before. 0.0% of all new papers.

Apr 9, 2026

Deterministic Adam-Inspired Methods with Accelerated Convergence Rate

Adam is widely used, but its convergence theory remains incomplete even in the deterministic full-batch setting because momentum and adaptive preconditioning are tightly coupled. For smooth convex objectives, we split the momentum variable through variable-and-operator splitting, which reveals the acceleration mechanism. We then combine a Hessian-driven correction with Adam-style feedback based on the gradient magnitude. The resulting Adam-HNAG (Hessian-driven Nesterov accelerated gradient with Adam-style adaptive preconditioning) flow admits a nonnegative energy that decays exponentially. Its discretization yields two methods, Adam-HNAG and the synchronous variant Adam-HNAG-s. Under the stated trajectory-bound and consistency conditions, both methods satisfy a discrete Lyapunov contraction. If the exact adaptive steps are accepted, this contraction gives an

O(k^{-2})

objective-value bound. Numerical experiments illustrate their behavior. These results apply to the proposed methods, not to the original Adam recursion.

Yaxin Yu, Long Chen, Zeyi Xu

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

Accelerated Gradient Methods Adaptive Gradient Methods

Ask PDF

Apr 7, 2026

Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates

Achieving optimal rates for stochastic composite convex optimization without prior knowledge of problem parameters remains a central challenge. In the deterministic setting, the auto-conditioned fast gradient method has recently been proposed to attain optimal accelerated rates without line-search procedures or prior knowledge of the Lipschitz smoothness constant, providing a natural prototype for parameter-free acceleration. However, extending this approach to the stochastic setting has proven technically challenging and remains open. Existing parameter-free stochastic methods either fail to achieve accelerated rates or rely on restrictive assumptions, such as bounded domains, bounded gradients, prior knowledge of the iteration horizon, or strictly sub-Gaussian noise. To address these limitations, we propose a stochastic variant of the auto-conditioned fast gradient method, referred to as stochastic AC-FGM. The proposed method is fully adaptive to the Lipschitz constant, the iteration horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures. Under standard bounded conditional variance assumptions, we show that stochastic AC-FGM achieves the optimal iteration complexity of

O(1/\sqrt{\varepsilon})

and the optimal sample complexity of

O(1/\varepsilon^2)

Yao Ji, Guanghui Lan

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, 225 North Ave, Atlanta, GA 30332, USA

Stochastic Optimization Accelerated Gradient Methods

Ask PDF

Apr 3, 2026

Scalable Mean-Variance Portfolio Optimization via Subspace Embeddings and GPU-Friendly Nesterov-Accelerated Projected Gradient

We develop a sketch-based factor reduction and a Nesterov-accelerated projected gradient algorithm (NPGA) with GPU acceleration, yielding a doubly accelerated solver for large-scale constrained mean-variance portfolio optimization. Starting from the sample covariance factor

L

, the method combines randomized subspace embedding, spectral truncation, and ridge stabilization to construct an effective factor

L_{eff}

. It then solves the resulting constrained problem with a structured projection computed by scalar dual search and GPU-friendly matrix-vector kernels, yielding one computational pipeline for the baseline, sketched, and Sketch-Truncate-Ridge (STR)-regularized models. We also establish approximation, conditioning, and stability guarantees for the sketching and STR models, including explicit

O(\varepsilon)

bounds for the covariance approximation, the optimal value error, and the solution perturbation under

(\varepsilon,δ)

-subspace embeddings. Experiments on synthetic and real equity-return data show that the method preserves objective accuracy while reducing runtime substantially. On a 5440-asset real-data benchmark with 48374 training periods, NPGA-GPU solves the unreduced full model in 2.80 seconds versus 64.84 seconds for Gurobi, while the optimized compressed GPU variants remain in the low-single-digit-second regime. These results show that the full dense model is already practical on modern GPUs and that, after compression, the remaining bottleneck is projection rather than matrix-vector multiplication.

Yi-Shuai Niu, Yajuan Wang

Beijing Institute of Mathematical Sciences and Applications (BIMSA)

Portfolio Optimization Randomized Sketching Accelerated Gradient Methods

Ask PDF

Apr 2, 2026

Optimal Projection-Free Adaptive SGD for Matrix Optimization

Recently, Jiang et al. [2026] developed Leon, a practical variant of One-sided Shampoo [Xie et al., 2025a, An et al., 2025] algorithm for online convex optimization, which does not require computing a costly quadratic projection at each iteration. Unfortunately, according to the existing analysis, Leon requires tuning an additional hyperparameter in its preconditioner and cannot achieve dimension-independent convergence guarantees for convex optimization problems beyond the bounded gradients assumption. In this paper, we resolve this issue by proving certain stability properties of Leon's preconditioner. Using our improved analysis, we show that tuning the extra hyperparameter can be avoided and, more importantly, develop the first practical variant of One-sided Shampoo with Nesterov acceleration, which does not require computing projections at each iteration. As a side contribution, we obtain improved dimension-independent rates in the non-smooth non-convex setting and develop a unified analysis of the proposed algorithm, which yields accelerated projection-free adaptive SGD with (block-)diagonal preconditioners.

Dmitry Kovalev

Yandex Research

Adaptive Gradient Methods Matrix Optimization Accelerated Gradient Methods Nonconvex Stochastic Optimization

Ask PDF

Mar 30, 2026

Critical Damping as a Momentum Schedule: Multi-Seed Validation, a Hybrid Recipe, and an Exhaustive Negative Result on Surgical Layer Selection

The critical damping condition of the damped harmonic oscillator model of SGD with momentum (Qian, 1999) yields a momentum schedule with no tuned hyperparameters: mu(t) = 1 - 2*sqrt(alpha(t)). Across five seeds on ResNet-18/CIFAR-10 (200-epoch cosine schedule) it reaches 90% test accuracy 2.34x faster than constant mu=0.9 (range 1.71-2.86x, 5/5 seeds, one-sided paired t-test p=4e-4), at the cost of a real final-accuracy deficit of 0.46 pp (5/5 seeds, p=0.009). A short-schedule control rules out a schedule-length artifact: compressed baselines either pay 0.5-0.9 pp of accuracy or stay slower to 90% at equal accuracy. A hybrid recipe -- critical-damping momentum until 90%, then constant mu=0.9 -- removes the deficit and keeps the speedup: 95.45 +/- 0.05% final accuracy at 2.4x faster progress to 90% (n=5). The speedup generalizes across architectures (VGG-16 without skip connections: 1.72x, n=3); on CIFAR-100 early gains persist (2-4x to mid-training thresholds) but the accuracy cost grows (-1.7 pp), compressing the accuracy-matched gain to 1.14x. We also report an exhaustive negative result on surgical layer selection. Version 2 of this paper claimed that gradient attribution on misclassified images selects which layers to retrain; running the identical correction protocol on all 35 combinations of 3-of-7 layer groups ranks the selected triple 11th of 35 (exact p=0.31) -- no better than random. What survives is weaker but real: combinations containing the top-ranked layer outperform the rest (+6.2 vs -1.4 mean net error reduction), and the bottom of the gradient-norm ranking reliably predicts the most harmful interventions (down to -20 net errors). Gradient attribution on errors is a harm-avoidance signal, not a selector of repair targets. We release the full 35-combination landscape as a baseline for layer-selection claims.

Ivan Pasichnyk

We Label Data Inc.

Gradient-Based Attribution Momentum Methods Neural Network Training Dynamics Accelerated Gradient Methods Stochastic Gradient Descent

Ask PDF

Mar 26, 2026

Improving Infinitely Deep Bayesian Neural Networks with Nesterov's Accelerated Gradient Method

As a representative continuous-depth neural network approach, stochastic differential equation (SDE)-based Bayesian neural networks (BNNs) have attracted considerable attention due to their solid theoretical foundations and strong potential for real-world applications. However, their reliance on numerical SDE solvers inevitably incurs a large number of function evaluations (NFEs), resulting in high computational cost and occasional convergence instability. To address these challenges, we propose a Nesterov-accelerated gradient (NAG) enhanced SDE-BNN model. By integrating NAG into the SDE-BNN framework along with an NFE-dependent residual skip connection, our method accelerates convergence and substantially reduces NFEs during both training and testing. Extensive empirical results show that our model consistently outperforms conventional SDE-BNNs across various tasks, including image classification and sequence modeling, achieving lower NFEs and improved predictive accuracy.

Chenxu Yu, Wenqi Fang

Shenzhen Institutes of Advanced Technology Chinese Academy of Sciences Shenzhen, P.R.China

Bayesian Neural Networks Neural Network Optimization Accelerated Gradient Methods

Ask PDF

Mar 10, 2026

SHANG++: Robust Stochastic Acceleration under Multiplicative Noise

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

Yaxin Yu, Long Chen, Minfu Feng

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

Accelerated Gradient Methods Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Mar 9, 2026

Momentum SVGD-EM for Accelerated Maximum Marginal Likelihood Estimation

Maximum marginal likelihood estimation (MMLE) can be formulated as the optimization of a free energy functional. From this viewpoint, the Expectation-Maximisation (EM) algorithm admits a natural interpretation as a coordinate descent method over the joint space of model parameters and probability measures. Recently, a significant body of work has adopted this perspective, leading to interacting particle algorithms for MMLE. In this paper, we propose an accelerated version of one such procedure, based on Stein variational gradient descent (SVGD), by introducing Nesterov acceleration in both the parameter updates and in the space of probability measures. The resulting method, termed Momentum SVGD-EM, consistently accelerates convergence in terms of required iterations across various tasks of increasing difficulty, demonstrating effectiveness in both low- and high-dimensional settings.

Adam Rozzio, Rafael Athanasiades, O. Deniz Akyildiz

Department of Mathematics, Ecole Normale Supérieure Paris-Saclay, France · Department of Mathematics, Imperial College London, UK

Maximum Marginal Likelihood Estimation Expectation-Maximization Stein Variational Gradient Descent Accelerated Gradient Methods

Ask PDF

Mar 5, 2026

FedBCD:Communication-Efficient Accelerated Block Coordinate Gradient Descent for Federated Learning

Although Federated Learning has been widely studied in recent years, there are still high overhead expenses in each communication round for large-scale models such as Vision Transformer. To lower the communication complexity, we propose a novel Federated Block Coordinate Gradient Descent (FedBCGD) method for communication efficiency. The proposed method splits model parameters into several blocks, including a shared block and enables uploading a specific parameter block by each client, which can significantly reduce communication overhead. Moreover, we also develop an accelerated FedBCGD algorithm (called FedBCGD+) with client drift control and stochastic variance reduction. To the best of our knowledge, this paper is the first work on parameter block communication for training large-scale deep models. We also provide the convergence analysis for the proposed algorithms. Our theoretical results show that the communication complexities of our algorithms are a factor

1/N

lower than those of existing methods, where

N

is the number of parameter blocks, and they enjoy much faster convergence than their counterparts. Empirical results indicate the superiority of the proposed algorithms compared to state-of-the-art algorithms. The code is available at https://github.com/junkangLiu0/FedBCGD.

Junkang Liu, Fanhua Shang, Yuanyuan Liu +3

School of Artificial Intelligence, Xi’an, Xidian University, China · College of Intelligence and Computing, Tianjin, Tianjin University, China · Medical College, Tianjin University; Peng Cheng Laboratory, Tianjin, China +1

Federated Learning Accelerated Gradient Methods

Ask PDF

Feb 26, 2026

Accelerating LLM Pre-Training through Flat-Direction Dynamics Enhancement

Pre-training Large Language Models requires immense computational resources, making optimizer efficiency essential. The optimization landscape is highly anisotropic, with loss reduction driven predominantly by progress along flat directions. While matrix-based optimizers such as Muon and SOAP leverage fine-grained curvature information to outperform AdamW, their updates tend toward isotropy -- relatively conservative along flat directions yet potentially aggressive along sharp ones. To address this limitation, we first establish a unified Riemannian Ordinary Differential Equation (ODE) framework that elucidates how common adaptive algorithms operate synergistically: the preconditioner induces a Riemannian geometry that mitigates ill-conditioning, while momentum serves as a Riemannian damping term that promotes convergence. Guided by these insights, we propose LITE, a generalized acceleration strategy that enhances training dynamics by applying larger Hessian damping coefficients and learning rates along flat trajectories. Extensive experiments demonstrate that LITE significantly accelerates both Muon and SOAP across diverse architectures (Dense, MoE), parameter scales (130M--1.3B), datasets (C4, Pile), and learning-rate schedules (cosine, warmup-stable-decay). Theoretical analysis confirms that LITE facilitates faster convergence along flat directions in anisotropic landscapes, providing a principled approach to efficient LLM pre-training. The code is available at https://github.com/SHUCHENZHU/LITE.

Shuchen Zhu, Rizhen Hu, Mingze Wang +4

Peking University · Zhejiang Lab, Zhejiang · Meituan, Beijing

Accelerated Gradient Methods Language Model Pretraining

Ask PDF

Feb 24, 2026

Complexity of Classical Acceleration for $\ell_1$ -Regularized PageRank

We study the degree-weighted work required to compute

\ell_1

-regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (ISTA), the best known worst-case work is

\widetilde{O}((αρ)^{-1})

, where

α

is the teleportation parameter and

ρ

is the

\ell_1

-regularization parameter. It is not known whether classical acceleration methods can improve

1/α

1/\sqrtα

while preserving the

1/ρ

locality scaling, or whether they can be asymptotically worse. For FISTA, we show a negative result by constructing a family of instances for which standard FISTA is asymptotically worse than ISTA. On the positive side, we analyze FISTA on a slightly over-regularized objective and show that, under a confinement condition, all spurious activations remain inside a boundary set

\mathcal{B}

. This yields a bound consisting of an accelerated

(ρ\sqrtα)^{-1}\log(α/\varepsilon)

term plus a boundary overhead

\sqrt{vol(\mathcal{B})}/(ρα^{3/2})

. We also provide graph-structural sufficient conditions that imply such confinement.

Kimon Fountoulakis, David Martínez-Rubio

University of Waterloo, Canada · IMDEA Software Institute, Madrid, Spain

Accelerated Gradient Methods

Ask PDF

Jul 13, 2023

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

This paper considers the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that have proposed effective algorithms, based on Polyak's heavy ball method and the Nesterov accelerated gradient method, to achieve convergence to a local minimum of nonconvex functions, this work proposes a broad class of Nesterov-type accelerated methods and puts forth a rigorous study of these methods encompassing the escape from saddle points and convergence to local minima through both an asymptotic and a non-asymptotic analysis. In the asymptotic regime, this paper answers an open question of whether Nesterov's accelerated gradient method (NAG) with variable momentum parameter avoids strict saddle points almost surely. This work also develops two metrics of asymptotic rates of convergence and divergence, and evaluates these two metrics for several popular standard accelerated methods such as the NAG and Nesterov's accelerated gradient with constant momentum (NCM) near strict saddle points. In the non-asymptotic regime, this work provides an analysis that leads to the "linear" exit time estimates from strict saddle neighborhoods for trajectories of these accelerated methods as well the necessary conditions for the existence of such trajectories. Finally, this work studies a sub-class of accelerated methods that can converge in convex neighborhoods of nonconvex functions with a near optimal rate to a local minimum and at the same time this sub-class offers superior saddle-escape behavior compared to that of NAG.

Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. Bajwa

Department of Electrical and Computer Engineering, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering, Management Science and Information Systems, and Statistics, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering and Statistics, Rutgers University–New Brunswick, NJ 08854 USA

Nonconvex Optimization Accelerated Gradient Methods Optimization Convergence Analysis

Ask PDF

Sep 29, 2022

NAG-GS: A Semi-Implicit Stochastic Optimizer with Large-Step Stability

Stochastic first-order methods are widely used for large-scale optimization and machine learning, where their performance often depends on the learning rate. We study NAG-GS, a stochastic momentum method based on a semi-implicit Gauss--Seidel discretization of a Nesterov-type flow. For strongly convex quadratics, we determine the exact range of stable step sizes for fixed damping and the step size that minimizes the worst-case spectral radius. When the damping equals the strong-convexity parameter, the method recovers the accelerated asymptotic factor

(\sqrtκ-1)/(\sqrtκ+1)

, where

κ

is the condition number. We also prove that the quadratic iteration converges linearly with dynamic damping when its limiting fixed-damping iteration is stable. For general strongly convex, possibly nonsmooth objectives, we establish an

O(1/k)

bound on the expected objective gap of the last iterate, using a conditionally unbiased stochastic first-order oracle with bounded second moment. The result holds with dynamic damping from any

γ_0>0

. We show that NAG-GS can also be written as a Heavy-Ball iteration with explicitly determined step sizes and momentum coefficients. We test the stochastic result on nonsmooth hinge-loss classification problems, and further evaluate NAG-GS on quadratic problems, logistic regression, convolutional neural networks, RoBERTa, and Vision Transformers. The experiments show that NAG-GS can remain effective at learning rates where standard optimizers become unstable or lose accuracy.

Valentin Leplat, Daniil Merkulov, Aleksandr Katrutsa +3

Skolkovo Institute of Science and Technology, Moscow, Russia · Moscow Institute of Physics and Technology, Moscow, Russia · AIRI, Moscow, Russia +1

Stochastic Optimization Accelerated Gradient Methods Stochastic Optimization Convergence Nonsmooth Convex Optimization

Ask PDF

Jan 26, 2022

Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant

Training logistic regression over encrypted data has emerged as a prominent approach to addressing security concerns in recent years. In this paper, we introduce an efficient gradient variant, termed the quadratic gradient, which is specifically designed for privacy-preserving logistic regression while remaining equally effective in plaintext optimization. By incorporating this quadratic gradient, we enhance Nesterov's Accelerated Gradient (NAG), Adaptive Gradient (AdaGrad), and Adam algorithms. We evaluate these enhanced algorithms across various datasets, with experimental results demonstrating state-of-the-art convergence rates that significantly outperform traditional first-order gradient methods. Furthermore, we apply the enhanced NAG method to implement homomorphic logistic regression training, achieving comparable performance within only four iterations. The proposed quadratic-gradient approach offers a unified framework that synergizes the advantages of first-order gradient methods and second-order Newton-type methods, suggesting broad applicability to diverse numerical optimization tasks.

John Chiang

Logistic Regression Gradient Descent Privacy-Preserving ML Adaptive Gradient Methods Accelerated Gradient Methods

Ask PDF