Convergence Analysis of Nesterov's Accelerated Gradient Descent under Relaxed Assumptions
Abstract
We study convergence rates of Nesterov's Accelerated Gradient Descent (NAG) method for convex optimization in both deterministic and stochastic settings. We focus on a more general smoothness condition raised from several machine learning problems empirically and theoretically. We show the accelerated convergence rate of order 𝒪(1/T2) in terms of the function value gap, given access to exact gradients of objective functions, matching the optimal rate for standard smooth convex optimization in \citep{nesterov1983method}. Under the relaxed affine-variance noise assumption for stochastic optimization, we establish the high-probability convergence rate of order 𝒪̃(√(log(1/δ)/T)) and this rate could improve to 𝒪̃(log(1/δ)/T2) when the noise parameters are sufficiently small. Here, T denotes the total number of iterations and δ is the probability margin. Up to logarithm factors, our probabilistic convergence rate reaches the same order of the expected rate obtained in \citep{ghadimi2016accelerated} where the assumptions of bounded variance noise and Lipschitz smoothness are required. We additionally establish the convergence rates of the studied algorithms in the non-convex setting.
Related
- Improved Gradient Descent Lower Bounds Beyond Nesterov
- On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Accelerated Concatenation of Stepsize Schedules for Smooth Strongly Convex Gradient Descent
- PL conditions do not guarantee convergence of gradient descent-ascent dynamics
BibTeX
@misc{yu2026convergence,
title = {{Convergence Analysis of Nesterov's Accelerated Gradient Descent under Relaxed Assumptions}},
author = {Chenhao Yu and Junhong Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33761},
eprint = {2610.33761},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33761},
}
RIS
TY - UNPB
TI - Convergence Analysis of Nesterov's Accelerated Gradient Descent under Relaxed Assumptions
AU - Chenhao Yu
AU - Junhong Lin
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.33761
UR - https://arxiv.org/abs/2610.33761
AB - We study convergence rates of Nesterov's Accelerated Gradient Descent (NAG) method for convex optimization in both deterministic and stochastic settings. We focus on a more general smoothness condition raised from several machine learning problems empirically and theoretically. We show the accelerated convergence rate of order 𝒪(1/T^2) in terms of the function value gap, given access to exact gradients of objective functions, matching the optimal rate for standard smooth convex optimization in \citep{nesterov1983method}. Under the relaxed affine-variance noise assumption for stochastic optimization, we establish the high-probability convergence rate of order 𝒪̃(√(log(1/δ)/T)) and this rate could improve to 𝒪̃(log(1/δ)/T^2) when the noise parameters are sufficiently small. Here, T denotes the total number of iterations and δ is the probability margin. Up to logarithm factors, our probabilistic convergence rate reaches the same order of the expected rate obtained in \citep{ghadimi2016accelerated} where the assumptions of bounded variance noise and Lipschitz smoothness are required. We additionally establish the convergence rates of the studied algorithms in the non-convex setting.
ER -