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

2018/03/06 by Tang, Junqi, Golbabaee, Mohammad, Bach, Francis +1
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1803.02246

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.

Related

• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Un-regularizing: approximate proximal point and faster stochastic\n algorithms for empirical risk minimization
• Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization
• Stochastic dual averaging methods using variance reduction techniques for regularized empirical risk minimization problems