Improved SVRG for quadratic functions
arXiv:2006.01017
Abstract
We analyse an iterative algorithm to minimize quadratic functions whose Hessian matrix is the expectation of a random symmetric matrix. The algorithm is a variant of the stochastic variance reduced gradient (SVRG). In several applications, including least-squares regressions, ridge regressions, linear discriminant analysis and regularized linear discriminant analysis, the running time of each iteration is proportional to . Under smoothness and convexity conditions, the algorithm has linear convergence. When applied to quadratic functions, our analysis improves the state-of-the-art performance of SVRG up to a logarithmic factor. Furthermore, for well-conditioned quadratic problems, our analysis improves the state-of-the-art running times of accelerated SVRG, and is better than the known matching lower bound, by a logarithmic factor. Our theoretical results are backed with numerical experiments.
arXiv comment14 pages
References in corpus (4)
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Towards closing the gap between the theory and practice of SVRG