@inproceedings{f5df46b052514876ba4c08c3cb5864b8,

title = "SDN A: Stochastic dual Newton ascent for empirical risk minimization",

abstract = "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 existing methods such as stochastic dual coordinate ascent. SDNA is capable of utilizing all local curvature information contained in the examples, which leads to striking improvements in both theory and practice - sometimes by orders of magnitude. In the special case when an L2-regularizer is used in the primal, the dual problem is a concave quadratic maximization problem plus a separable term. In this regime, SDNA in each step solves a proximal subproblem involving a random principal submatrix of the Hessian of the quadratic function; whence the name of the method.",

author = "Zheng Qu and Peter Richtarik and Martin Tak{\'a}{\v c} and Olivier Fereoq",

year = "2016",

month = jan,

day = "1",

language = "English (US)",

series = "33rd International Conference on Machine Learning, ICML 2016",

publisher = "International Machine Learning Society (IMLS)",

pages = "2707--2725",

editor = "Weinberger, {Kilian Q.} and Balcan, {Maria Florina}",

booktitle = "33rd International Conference on Machine Learning, ICML 2016",

note = "33rd International Conference on Machine Learning, ICML 2016 ; Conference date: 19-06-2016 Through 24-06-2016",

}