Acceleration of SVRG and Katyusha X by Inexact Preconditioning
arXiv:1905.09734
Abstract
Empirical risk minimization is an important class of optimization problems with many popular machine learning applications, and stochastic variance reduction methods are popular choices for solving them. Among these methods, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement. In this paper, we propose to accelerate these two algorithms by \textit{inexact preconditioning}, the proposed methods employ \textit{fixed} preconditioners, although the subproblem in each epoch becomes harder, it suffices to apply \textit{fixed} number of simple subroutines to solve it inexactly, without losing the overall convergence. As a result, this inexact preconditioning strategy gives provably better iteration complexity and gradient complexity over SVRG and Katyusha X. We also allow each function in the finite sum to be nonconvex while the sum is strongly convex. In our numerical experiments, we observe an on average speedup on the number of iterations and speedup on runtime.
References in corpus (10)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- A Universal Catalyst for First-Order Optimization
- Optimization with First-Order Surrogate Functions
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- SDCA without Duality, Regularization, and Individual Convexity
- A2BCD: An Asynchronous Accelerated Block Coordinate Descent Algorithm With Optimal Complexity
- Breaking the Span Assumption Yields Fast Finite-Sum Minimization
- An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration