# Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes

arXiv: https://arxiv.org/abs/1803.02246 · HTML: https://mlsanity.com/paper/1803.02246/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Mar 2018.

## Built on by (most cited first, 3 of 3)

- [Stochastic Primal-Dual Deep Unrolling](https://mlsanity.com/paper/2110.10093/) (2021)
- [Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming](https://mlsanity.com/paper/2111.05530/) (2021)
- [Equivariance Regularization for Image Reconstruction](https://mlsanity.com/paper/2202.05062/) (2022)

## Abstract (arXiv)

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.