  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.
