On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
We study Nesterov's accelerated gradient method with constant step-size and momentum parameters in the stochastic approximation setting (unbiased gradients with bounded variance) and the finite-sum setting (where randomness is due to sampling mini-batches). To build better insight into the behavior of Nesterov's method in stochastic settings, we focus throughout on objectives that are smooth, strongly-convex, and twice continuously differentiable. In the stochastic approximation setting, Nesterov's method converges to a neighborhood of the optimal point at the same accelerated rate as in the deterministic setting. Perhaps surprisingly, in the finite-sum setting, we prove that Nesterov's method may diverge with the usual choice of step-size and momentum, unless additional conditions on the problem related to conditioning and data coherence are satisfied. Our results shed light as to why Nesterov's method may fail to converge or achieve acceleration in the finite-sum setting.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
Recently, {\it stochastic momentum} methods have been widely adopted in training deep neural networks. However, their convergence analysis is still underexplored at the moment, in particular for non-convex optimization. …
Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization
We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Descent Ascent -- for separable convex-concave minimax optimization. The main idea of our algorithm is to carefully le…
Provable Accelerated Convergence of Nesterov's Momentum for Deep ReLU Neural Networks
Current state-of-the-art analyses on the convergence of gradient descent for training neural networks focus on characterizing properties of the loss landscape, such as the Polyak-Lojaciewicz (PL) condition and the restri…
Open-Ended Question AnsweringA Concise Lyapunov Analysis of Nesterov's Accelerated Gradient Method
Convergence analysis of Nesterov's accelerated gradient method has attracted significant attention over the past decades. While extensive work has explored its theoretical properties and elucidated the intuition behind i…
A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
Incorporating second order curvature information in gradient based methods have shown to improve convergence drastically despite its computational intensity. In this paper, we propose a stochastic (online) quasi-Newton m…
regression