Linear convergence of SDCA in statistical estimation

2017-01-26 · Chao Qu, Huan Xu

In this paper, we consider stochastic dual coordinate (SDCA) {\em without} strongly convex assumption or convex assumption. We show that SDCA converges linearly under mild conditions termed restricted strong convexity. This covers a wide array of popular statistical models including Lasso, group Lasso, and logistic regression with $\ell_1$ regularization, corrected Lasso and linear regression with SCAD regularizer. This significantly improves previous convergence results on SDCA for problems that are not strongly convex. As a by product, we derive a dual free form of SDCA that can handle general regularization term, which is of interest by itself.

📄 PDF Abstract BibTeX arXiv:1701.07808

Code (0)

등록된 구현이 없습니다.

Tasks

regression

SDCA without Duality

2015-02-22 · Shai Shalev-Shwartz

Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. In this paper we show how a variant of SDCA can be applied for non-convex losses. We prove li…

Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption

2015-06-08 · Chenxin Ma, Rachael Tappenden, Martin Takáč

In this paper we generalize the framework of the feasible descent method (FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent method (RC-FDM) framework. We show that the famous SDCA algorithm for o…

SDCA without Duality, Regularization, and Individual Convexity

2016-02-04 · Shai Shalev-Shwartz

Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on d…

Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields

2017-12-22 · Rémi Le Priol, Alexandre Piché, Simon Lacoste-Julien

This work investigates the training of conditional random fields (CRFs) via the stochastic dual coordinate ascent (SDCA) algorithm of Shalev-Shwartz and Zhang (2016). SDCA enjoys a linear convergence rate and a strong em…

Binary Classification General Classification

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

2014-07-01 · NeurIPS 2014 12 · Aaron Defazio, Francis Bach, Simon Lacoste-Julien

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on t…