SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
This addresses the efficiency of empirical risk minimization for machine learning practitioners, offering a novel dual method with potential broad impact, though it appears incremental as it builds on existing stochastic dual coordinate ascent.
The paper tackles the problem of minimizing regularized empirical loss by proposing Stochastic Dual Newton Ascent (SDNA), which updates random subsets of dual variables and utilizes full curvature information, leading to significant improvements, sometimes by orders of magnitude, in theory and practice.
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 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. If, in addition, the loss functions are quadratic, our method can be interpreted as a novel variant of the recently introduced Iterative Hessian Sketch.