SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization

By Zheng Qu, Peter Richtárik, Martin Takác, Olivier Fercoq. 2015

105 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “If hypothetically each of our quadratic subproblems Gσ k (∆α[k]) as defined in (10) were to be minimized exactly, the resulting steps could be interpreted as block-wise Newton-type steps on each coordinate block k, where the Newton-subproblem is modified to also contain the L1-regularizer (Mahajan e”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “It has been recently shown in SDNA [74] that incorporating curvature information contained in random low dimensional subspaces spanned by a few coordinates can sometimes lead to dramatic speedups.”
Distributed optimization with arbitrary local solvers (2015, methodology): “tanding and complicated implementation issues compared to those above may still limit their adoption in the wider community. A stochastic dual Newton ascent (SDNA) method was proposed and analyzed in [47]. However, the method needs to modied substantially before it can be implemented in a distribute”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “In the special case of B = A, mSDSA is directly equivalent to mSGD (this is due to the primal-dual relationship (20); see also Theorem5). Randomized coordinate Newton (RCN) method was rst proposed in [60]; mRCN is its momentum variant. Randomized Gaussian Kaczmarz (RGK) method was rst proposed in [2”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “An alternative approach is not to compute the gradient and subsequently compress it, but to update a subset of elements of the iterate x using coordinate descent type updates (Richt´arik & Tak´aˇc, 2016; Fercoq et al., 2014; Mishchenko et al., 2019).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A stochastic dual Newton ascent (SDNA) method was proposed and analyzed in [142].”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, background): “If hypothetically each of our quadratic subproblems Gσ′k (∆α[k]) as defined in (2) were to be minimized exactly, the resulting steps could be interpreted as block-wise Newton-type steps on each coordinate block k, where the Newton-subproblem is modified to also contain the L1-regularizer [18, 34, 23”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, unknown): “Alternative variance-reduced method include MISO (Mairal, 2015), FINITO (Defazio et al., 2014b), SDCA (Shalev-Shwartz, 2016), dfSDCA (Csiba & Richt´arik, 2015), AdaSDCA (Csiba et al., 2015), QUARTZ (Qu et al., 2015), SBFGS (Gower et al., 2016), SDNA (Qu et al., 2016), SARAH (Nguyen et al., 2017) and”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, background): “Its block variant can be also interpret as randomized coordinate Newton method (see [42]).”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “Stochastic Newton-type methods were recently developed and analyzed in the optimization and machine learning literature [51, 50, 53, 40].”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, methodology): “This combines and improves upon the results of [16, 17, 21, 33].”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “Recall that in Section 5 we show that both RBK and RNM converge to the solution of the primal and dual problems respectively with the same rate and that their iterates are related via a simple affine transform (51).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In particular, instead of iterating over values stored at the nodes, RNM uses these values to update “dual weights” yk ∈ Rm that correspond to the edges E of the network.”
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (2016, background): “(iv)] as in [21, 12, 7, 18] they result in faster convergence.”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, background): “…years, tremendous eﬀort was exerted to improve its performance, leading to various enhancements which use acceleration [1], momentum [14], minibatching [35], distributed implementation [16, 15], importance sampling [36, 6, 27, 4], higher-order information [26, 9], and a number of other techniques.”
Randomized Iterative Methods for Linear Systems (2015, methodology): “Such C is in [29] referred to by the name “non-vacuous” sampling.”