SDNA: 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 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.

References in corpus (11)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• Stochastic Optimization with Importance Sampling
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• A Stochastic Quasi-Newton Method for Large-Scale Optimization
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization
• Robust Block Coordinate Descent

Cited by in corpus (31)

• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Stochastic Dual Ascent for Solving Linear Systems
• Testing and non-linear preconditioning of the proximal point method
• Block-proximal methods with spatially adapted acceleration
• Randomized Block Cubic Newton Method
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• Alternating Randomized Block Coordinate Descent
• Breaking Locality Accelerates Block Gauss-Seidel
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Primal-dual block-proximal splitting for a class of non-convex problems
• Stochastic Second-Order Optimization via von Neumann Series
• Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Parallel Stochastic Newton Method
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent
• Heavy Ball Momentum Induced Sampling Kaczmarz Motzkin Methods for Linear Feasibility Problems
• Bregman Monotone Operator Splitting
• Randomized block proximal damped Newton method for composite self-concordant minimization
• Randomized Extended Kaczmarz is a Limit Point of Sketch-and-Project
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration
• RSN: Randomized Subspace Newton
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
• Precise expressions for random projections: Low-rank approximation and randomized Newton
• A New Perspective on Randomized Gossip Algorithms
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Convergence analysis of two-level methods with general coarse solvers
• Stability and Generalization for Randomized Coordinate Descent
• Stochastic Primal Dual Coordinate Method with Non-Uniform Sampling Based on Optimality Violations