Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives

Understand

Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings.

• In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly convex or sum-of-non-convex settings.
• More precisely, we provide new analysis to improve the state-of-the-art running times in both settings by either applying SVRG or its novel variant.
• Since non-strongly convex objectives include important examples such as Lasso or logistic regression, and sum-of-non-convex objectives include famous examples such as stochastic PCA and is even believed to be related to training deep neural nets, our results also imply better performances in these applications.