On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimization

Yi Xu, Zhuoning Yuan, Sen Yang, Rong Jin, Tianbao Yang

Published 2019-01-30Version 1

Extrapolation is very popular in convex optimization, and even for non-convex optimizaion, several recent works have empirically shown its success in many machine learning tasks. However, it has not been analyzed for non-convex optimization and there still remains a gap between the theory and the practice. In this paper, we analyze gradient descent with extrapolation for non-convex optimization both in deterministic and stochastic settings. To the best of our knowledge, this is the first attempt to analyze GD with extrapolation both for non-convex deterministic and stochastic optimization.