Acceleration of SVRG and Katyusha X by Inexact Preconditioning

Yanli Liu, Fei Feng, Wotao Yin

International Conference on Learning Representations (ICML)’19

Overview

Empirical risk minimization is an important class of optimization problems with many popular machine learning applications. To solve these problems, stochastic variance reduction methods are popular choices. In particular, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement.

In this paper, we propose to further accelerate SVRG and Katyusha X by inexact pre-conditioning. The proposed methods use fixed preconditioners to significantly reduce the total number of epochs. Although this leads to harder subproblems, we show it suffices to apply a fixed number of simple subroutines to solve the subproblems inexactly. We obtain overall better iteration complexity and gradient complexity than SVRG and Katyusha X.

In our numerical experiments, we observe, on average, a 8-fold speedup on iteration and a 7-fold speedup on time.

In the figures below, IP-SVRG (blue dash lines) and IP-Katyusha X (orange dash lines) are proposed methods. (By the way, despite having better complexities, Katyusha X did not have better performance than SVRG.)

LASSO on w1a.t dataset, using a diagonal preconditioner 
LASSO on w1a.t dataset, using a diagonal preconditioner
LASSO on cod-rna.t dataset, using a nondiagonal preconditioner 
LASSO on cod-rna.t dataset, using a nondiagonal preconditioner
Logistic regression on w1a.t dataset, using a diagonal preconditioner 
Logistic regression on w1a.t dataset, using a diagonal preconditioner
Logistic regression on cod-rna.t dataset, using a nondiagonal preconditioner 
Logistic regression on cod-rna.t dataset, using a nondiagonal preconditioner

Citation

Y. Liu, F. Feng, W. Yin, Acceleration of SVRG and Katyusha X by inexact preconditioning, international Conference on Machine Learning (ICML), Long Beach, CA, 2019.


« Back