SAGA and Restricted Strong Convexity
This extends SAGA's applicability to a broader class of convex and non-convex optimization problems in statistics, but it is incremental as it builds on existing methods with new theoretical analysis.
The paper tackles the problem of applying the SAGA incremental gradient method to non-strongly convex and non-convex statistical problems like Lasso and logistic regression with regularization, proving that SAGA achieves linear convergence up to statistical estimation accuracy under restricted strong convexity assumptions.
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.