Does Momentum Help? A Sample Complexity Analysis
Stochastic Heavy Ball (SHB) and Nesterov's Accelerated Stochastic Gradient (ASG) are popular momentum methods in stochastic optimization. While benefits of such acceleration ideas in deterministic settings are well understood, their advantages in stochastic optimization is still unclear. In fact, in some specific instances, it is known that momentum does not help in the sample complexity sense. Our work shows that a similar outcome actually holds for the whole of quadratic optimization. Specifically, we obtain a lower bound on the sample complexity of SHB and ASG for this family and show that the same bound can be achieved by the vanilla SGD. We note that there exist results claiming the superiority of momentum based methods in quadratic optimization, but these are based on one-sided or flawed analyses.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Accelerated Stochastic Power Iteration
Principal component analysis (PCA) is one of the most powerful tools in machine learning. The simplest method for PCA, the power iteration, requires $\mathcal O(1/\Delta)$ full-data passes to recover the principal compon…
Dimensionality ReductionRiemannian stochastic recursive momentum method for non-convex optimization
We propose a stochastic recursive momentum method for Riemannian non-convex optimization that achieves a near-optimal complexity of $\tilde{\mathcal{O}}(\epsilon^{-3})$ to find $\epsilon$-approximate solution with one sa…
Riemannian optimizationMDPGT: Momentum-based Decentralized Policy Gradient Tracking
We propose a novel policy gradient method for multi-agent reinforcement learning, which leverages two different variance-reduction techniques and does not require large batches over iterations. Specifically, we propose a…
Multi-agent Reinforcement LearningPolicy Gradient Methodsreinforcement-learningReinforcement Learning+2Adai: Separating the Effects of Adaptive Learning Rate and Momentum Inertia
Adaptive Momentum Estimation (Adam), which combines Adaptive Learning Rate and Momentum, is the most popular stochastic optimizer for accelerating the training of deep neural networks. However, empirically Adam often gen…
Adaptive Inertia: Disentangling the Effects of Adaptive Learning Rate and Momentum
Adaptive Momentum Estimation (Adam), which combines Adaptive Learning Rate and Momentum, would be the most popular stochastic optimizer for accelerating the training of deep neural networks. However, empirically Adam oft…