# SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization

arXiv: https://arxiv.org/abs/1502.02268 · HTML: https://mlsanity.com/paper/1502.02268/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2015.

## Built on by (most cited first, 19 of 19)

- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Stability and Generalization for Randomized Coordinate Descent](https://mlsanity.com/paper/2108.07414/) (2021)
- [Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updates](https://mlsanity.com/paper/2305.13082/) (2023)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Efficient Global Optimization of Non-differentiable, Symmetric Objectives for Multi Camera Placement](https://mlsanity.com/paper/2103.11210/) (2021)
- [A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squares](https://mlsanity.com/paper/2211.05727/) (2022)
- [Polynomial Preconditioning for Gradient Methods](https://mlsanity.com/paper/2301.13194/) (2023)
- [Understanding Progressive Training Through the Framework of Randomized Coordinate Descent](https://mlsanity.com/paper/2306.03626/) (2023)
- [Subspace-based Approximate Hessian Method for Zeroth-Order Optimization](https://mlsanity.com/paper/2507.06125/) (2025)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [Joker: Joint Optimization Framework for Lightweight Kernel Machines](https://mlsanity.com/paper/2505.17765/) (2025)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)
- [Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees](https://mlsanity.com/paper/2508.19712/) (2025)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

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.