SAGA and Restricted Strong Convexity

Abstract

SAGA is a fast incremental gradient method on the finite sum problem and its effectiveness has been tested on a vast of applications. In this paper, we analyze SAGA on a class of non-strongly convex and non-convex statistical problem such as Lasso, group Lasso, Logistic regression with ${\ell }_1$ regularization, linear regression with SCAD regularization and Correct Lasso. We prove that SAGA enjoys the linear convergence rate up to the statistical estimation accuracy, under the assumption of restricted strong convexity (RSC). It significantly extends the applicability of SAGA in convex and non-convex optimization.

arXiv commentarXiv admin note: text overlap with arXiv:1701.07808

References in corpus (9)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Variance Reduction for Faster Non-Convex Optimization
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Linear convergence of SDCA in statistical estimation

Cited by in corpus (3)

• Linear convergence of SDCA in statistical estimation
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• Fast Global Convergence via Landscape of Empirical Loss