Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes
Junqi Tang · Mohammad Golbabaee · Francis Bach · Mike E davies

Wed Dec 5th 10:45 AM -- 12:45 PM @ Room 210 #14

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.

Author Information

Junqi Tang (University of Edinburgh)
Mohammad Golbabaee (University of Bath)
Francis Bach (INRIA - Ecole Normale Superieure)
Mike E davies (University of Edinburgh)

More from the Same Authors