Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization

2013-09-10 · Shai Shalev-Shwartz, Tong Zhang

We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.

📄 PDF Abstract BibTeX arXiv:1309.2375

Code (0)

등록된 구현이 없습니다.

Tasks

BIG-bench Machine Learning regression

Methods 이 논문이 사용한 방법론

SVM A Support Vector Machine, or SVM, is a non-parametric supervised learning model. For non-linear classification and regression, they utilise the kernel trick to map inputs…

An Accelerated Proximal Coordinate Gradient Method

2014-12-01 · NeurIPS 2014 12 · Qihang Lin, Zhaosong Lu, Lin Xiao

We develop an accelerated randomized proximal coordinate gradient (APCG) method, for solving a broad class of composite convex optimization problems. In particular, our method achieves faster linear convergence rates for…

Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

2013-05-12 · NeurIPS 2013 12 · Shai Shalev-Shwartz, Tong Zhang

Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is of…

BIG-bench Machine Learning

Stochastic Optimization with Importance Sampling

2014-01-13 · Peilin Zhao, Tong Zhang

Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA…

Stochastic Optimization

Explicit Regularization of Stochastic Gradient Methods through Duality

2020-03-30 · Anant Raj, Francis Bach

We consider stochastic gradient methods under the interpolation regime where a perfect fit can be obtained (minimum loss at each observation). While previous work highlighted the implicit regularization of such algorithm…

SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization

2015-02-08 · Zheng Qu, Peter Richtárik, Martin Takáč, Olivier Fercoq

We propose a new algorithm for minimizing regularized empirical loss: Stochastic Dual Newton Ascent (SDNA). Our method is dual in nature: in each iteration we update a random subset of the dual variables. However, unlike…