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 $\mathcal{O}\left(1/T^2\right)$ 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 $\tilde{\mathcal{O}}\left(\sqrt{\log\left(1/δ\right)/T}\right)$ and this rate could improve to $\tilde{\mathcal{O}}\left(\log\left(1/δ\right)/T^2\right)$ 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.