Sketched Newton-Raphson

DOI10.1137/21M139788XMaRDI QIDQ5093644zbMATH OpenOpenAlexFDO

Authors Rui Yuan, Alessandro Lazaric, Robert M. Gower

Publication date 29 July 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.12120

zbMATH Keywords

iterative methodsnonlinear systemsrandomized Kaczmarzstochastic methodsstochastic Newton method

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Stochastic approximation (62L20) Complexity and performance of numerical algorithms (65Y20) Randomized algorithms (68W20) Analysis of algorithms (68W40) Stochastic and other probabilistic methods applied to problems in solid mechanics (74S60) Large-scale problems in mathematical programming (90C06) Methods of quasi-Newton type (90C53)

Abstract: We propose a new globally convergent stochastic second order method. Our starting point is the development of a new Sketched Newton-Raphson (SNR) method for solving large scale nonlinear equations of the form $F(x)=0$ with $F:mathbb{R}^{p}ightarrowmathbb{R}^m$. We then show how to design several stochastic second order optimization methods by re-writing the optimization problem of interest as a system of nonlinear equations and applying SNR. For instance, by applying SNR to find a stationary point of a generalized linear model (GLM), we derive completely new and scalable stochastic second order methods. We show that the resulting method is very competitive as compared to state-of-the-art variance reduced methods. Furthermore, using a variable splitting trick, we also show that the Stochastic Newton method (SNM) is a special case of SNR, and use this connection to establish the first global convergence theory of SNM. We establish the global convergence of SNR by showing that it is a variant of the stochastic gradient descent (SGD) method, and then leveraging proof techniques of SGD. As a special case, our theory also provides a new global convergence theory for the original Newton-Raphson method under strictly weaker assumptions as compared to the classic monotone convergence theory.

Recommendations

• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• Sub-sampled Newton methods
• Stochastic sub-sampled Newton method with variance reduction
• Stochastic regularized Newton methods for nonlinear equations
• An investigation of Newton-sketch and subsampled Newton methods

Cites work

• A globally convergent incremental Newton method
• A globally convergent Newton-GMRES method for large sparse systems of nonlinear equations
• A globally convergent Newton-GMRES subspace method for systems of nonlinear equations
• A randomized Kaczmarz algorithm with exponential convergence
• A trust region algorithm with adaptive cubic regularization methods for nonsmooth convex minimization
• Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
• Automatic Hessians by reverse accumulation
• Cubic regularization of Newton method and its global performance
• Exact and inexact subsampled Newton methods for optimization
• Global convergence of a new hybrid Gauss-Newton structured BFGS method for nonlinear least squares problems
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Iterative Solution of Nonlinear Equations in Several Variables
• Minimizing finite sums with the stochastic average gradient
• Newton methods for nonlinear problems. Affine invariance and adaptive algorithms.
• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• Numerical methods for nonlinear equations
• Numerical Optimization
• On projective Landweber-Kaczmarz methods for solving systems of nonlinear ill-posed equations
• On the convergence of the modified Levenberg-Marquardt method with a nonmonotone second order Armijo type line search
• Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
• Randomized iterative methods for linear systems
• Recent advances in numerical methods for nonlinear equations and nonlinear least squares
• Second-order stochastic optimization for machine learning in linear time
• Sketching as a tool for numerical linear algebra
• Stochastic dual coordinate ascent methods for regularized loss minimization
• Stochastic reformulations of linear systems: algorithms and convergence theory
• Sub-sampled Newton methods
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The method of successive approximations for functional equations
• Trust Region Methods

Cited in

(24)

• RidgeSketch: a fast sketching based solver for large scale ridge regression
• On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
• Stochastic regularized Newton methods for nonlinear equations
• On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
• A Bregman–Kaczmarz method for nonlinear systems of equations
• Greedy randomized sampling nonlinear Kaczmarz methods
• A residual-based weighted nonlinear Kaczmarz method for solving nonlinear systems of equations
• A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
• On averaging block Kaczmarz methods for solving nonlinear systems of equations
• Greedy capped nonlinear Kaczmarz methods
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• Greedy randomized Kaczmarz with momentum method for nonlinear equation
• Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
• On stochastic block methods for solving nonlinear equations
• Inexact Gauss-Newton methods with matrix approximation by sampling for nonlinear least-squares and systems
• Fine-grained analysis and faster algorithms for iteratively solving linear systems
• A fast block nonlinear Bregman-Kaczmarz method with averaging for nonlinear sparse signal recovery
• On a nonlinear fast deterministic block Kaczmarz method for solving nonlinear equations
• Convergence analysis of the nonlinear Kaczmarz method for systems of nonlinear equations with componentwise convex mappings and applications to image reconstruction in multispectral CT
• A variable dimension sketching strategy for nonlinear least-squares
• Incremental Gauss-Newton methods with superlinear convergence rates
• Several improved nonlinear deterministic block Kaczmarz methods for solving nonlinear equations
• On the adaptively inexact sketched Newton-Raphson methods for nonlinear systems of equations

This page was built for publication: Sketched Newton-Raphson

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093644)