Linearly convergent stochastic heavy ball method for minimizing generalization error

2017/10/30 by Loizou, Nicolas, Richtárik, Peter
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1710.10737

Abstract

In this work we establish the first linear convergence result for the stochastic heavy ball method. The method performs SGD steps with a fixed stepsize, amended by a heavy ball momentum term. In the analysis, we focus on minimizing the expected loss and not on finite-sum minimization, which is typically a much harder problem. While in the analysis we constrain ourselves to quadratic loss, the overall objective is not necessarily strongly convex.

Related

• Stochastic Heavy Ball
• Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Convergence analysis of a stochastic heavy-ball method for linear ill-posed problems
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization