Rest-Katyusha: Exploiting the solution's structure via scheduled restart schemes

Junqi Tang, Mohammad Golbabaee, Francis Bach, Mike Davies

Research output: Contribution to journalConference articlepeer-review

4 Citations (SciVal)


We propose a structure-adaptive variant of a 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 (RSC) constants. We also propose an adaptive-restart variant which is able to estimate the RSC on the fly and adjust the restart period automatically. We demonstrate the effectiveness of our approach via numerical experiments.

Original languageEnglish
Pages (from-to)429-440
Number of pages12
JournalAdvances in Neural Information Processing Systems
Publication statusPublished - 1 Jan 2018
Event32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada
Duration: 2 Dec 20188 Dec 2018

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Rest-Katyusha: Exploiting the solution's structure via scheduled restart schemes'. Together they form a unique fingerprint.

Cite this