NeurIPS 2018poster20 citations
Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes
Junqi Tang, Mohammad Golbabaee, Francis Bach, Mike E davies
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.
BibTeX
@inproceedings{NEURIPS2018_39059724,
author = {Tang, Junqi and Golbabaee, Mohammad and Bach, Francis and davies, Mike E},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Rest-Katyusha: Exploiting the Solution\textquotesingle s Structure via Scheduled Restart Schemes},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/39059724f73a9969845dfe4146c5660e-Paper.pdf},
volume = {31},
year = {2018}
}