Stochastic Dual Coordinate Ascent with Adaptive Probabilities

Dominik Csiba; Zheng Qu; Peter Richtárik

Stochastic Dual Coordinate Ascent with Adaptive Probabilities

Dominik Csiba, Zheng Qu, Peter Richtárik

School of Mathematics

Research output: Contribution to conference › Paper › peer-review

Abstract / Description of output

This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.

Original language	English
Publication status	Published - 27 Feb 2015
Event	32nd International Conference on Machine Learning - Lille, France Duration: 6 Jul 2015 → 11 Jul 2015 https://icml.cc/2015/

Conference

Conference	32nd International Conference on Machine Learning
Abbreviated title	ICML 2015
Country/Territory	France
City	Lille
Period	6/07/15 → 11/07/15
Internet address	https://icml.cc/2015/

Keywords / Materials (for Non-textual outputs)

math.OC
cs.LG
stat.ML

Access to Document

1502.08053v1Submitted manuscript, 746 KB

http://proceedings.mlr.press/v37/csiba15.html

Cite this

@conference{49c1127046414ee88da8adba1daf027c,

title = "Stochastic Dual Coordinate Ascent with Adaptive Probabilities",

abstract = "This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.",

keywords = "math.OC, cs.LG, stat.ML",

author = "Dominik Csiba and Zheng Qu and Peter Richt{\'a}rik",

year = "2015",

month = feb,

day = "27",

language = "English",

note = "32nd International Conference on Machine Learning, ICML 2015 ; Conference date: 06-07-2015 Through 11-07-2015",

url = "https://icml.cc/2015/",

}

TY - CONF

T1 - Stochastic Dual Coordinate Ascent with Adaptive Probabilities

AU - Csiba, Dominik

AU - Qu, Zheng

AU - Richtárik, Peter

PY - 2015/2/27

Y1 - 2015/2/27

N2 - This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.

AB - This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.

KW - math.OC

KW - cs.LG

KW - stat.ML

M3 - Paper

T2 - 32nd International Conference on Machine Learning

Y2 - 6 July 2015 through 11 July 2015

ER -

Stochastic Dual Coordinate Ascent with Adaptive Probabilities

Abstract / Description of output

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this