We propose a structure-adaptive variant of the state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for the regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity and low-rank, which is enforced by the non-smooth regularization, to achieve even faster convergence rate. This algorithmic improvement is done by restarting the Katyusha algorithm at a certain carefully-chosen frequency according to a modified version of restricted strong-convexity. Our analysis demonstrates that the proposed method is globally convergent and enjoys a local accelerated linear rate with respect to the low-dimensional structure of the solution represented by the restricted strong-convexity, even when the cost function itself is not strongly-convex. Since in practice the restricted strong-convexity is usually unknown and hard to be estimated accurately, we proposed two practical restart schemes. The first one is restarting the algorithm with a rough restricted strong-convexity estimate which is provably robust but have a compromise on the convergence rate. The second variant is based on the adaptive restart via convergence speed check. The numerical results on benchmark datasets demonstrate the effectiveness of our approach.