Rest-Katyusha: Exploiting The Solution's Structure Via Scheduled Restart Schemes

Authors:
Junqi Tang University of Edinburgh
Mohammad Golbabaee University of Bath
Francis Bach INRIA - Ecole Normale Superieure
Mike E Davies University of Edinburgh

Introduction:

The authors propose a structure-adaptive variant of the state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for regularized empirical risk minimization.

Abstract:

We propose a structure-adaptive variant of the state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity or low rank which is enforced by a non-smooth regularization, to achieve even faster convergence rate. This provable algorithmic improvement is done by restarting the Katyusha algorithm according to restricted strong-convexity constants. We demonstrate the effectiveness of our approach via numerical experiments.

You may want to know: