Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
From MaRDI portal
Abstract: We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, with convergence and complexity guarantees that are independent of condition numbers and related problem-dependent quantities. Given a suitable initialization, similar guarantees also hold for strongly convex and smooth objectives without self-concordance. When implemented using randomized projections based on a sub-sampled Hadamard basis, the algorithm typically has substantially lower complexity than Newton's method. We also describe extensions of our methods to programs involving convex constraints that are equipped with self-concordant barriers. We discuss and illustrate applications to linear programs, quadratic programs with convex constraints, logistic regression and other generalized linear models, as well as semidefinite programs.
Recommendations
- An investigation of Newton-sketch and subsampled Newton methods
- A quadratically convergent Newton method for vector optimization
- A quadratically convergent scaling newton’s method for nonlinear programming problems
- An efficient improvement of the Newton method for solving nonconvex optimization problems
- Randomized sketch descent methods for non-separable linearly constrained optimization
- A quasi-Newton acceleration for high-dimensional optimization algorithms
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- scientific article; zbMATH DE number 4068627
- Newton Methods for Large-Scale Linear Equality-Constrained Minimization
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
Cites work
- A sparse Johnson-Lindenstrauss transform
- A stochastic quasi-Newton method for large-scale optimization
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Fast approximation of matrix coherence and statistical leverage
- Fast dimension reduction using Rademacher series on dual BCH codes
- Faster least squares approximation
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 1694914 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3980111 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 47310 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 6438182 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Inexact Newton Methods
- Introductory lectures on convex optimization. A basic course.
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Least angle regression. (With discussion)
- Local operator theory, random matrices and Banach spaces.
- Local Rademacher complexities
- Numerical Optimization
- On the use of stochastic Hessian information in optimization methods for machine learning
- Randomized Sketches of Convex Programs With Sharp Guarantees
- SGD-QN
- SGD-QN: careful quasi-Newton stochastic gradient descent
- Sparser Johnson-Lindenstrauss transforms
- Truncated-Newton algorithms for large-scale unconstrained optimization
Cited in
(71)- Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data
- Sub-sampled Newton methods
- On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization
- A hybrid stochastic optimization framework for composite nonconvex optimization
- Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
- Functional principal subspace sampling for large scale functional data analysis
- A Newton Frank-Wolfe method for constrained self-concordant minimization
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- Randomized Newton's method for solving differential equations based on the neural network discretization
- Sketch-based empirical natural gradient methods for deep learning
- Inexact restoration with subsampled trust-region methods for finite-sum minimization
- Random projections for quadratic programs
- Reduced rank regression with matrix projections for high-dimensional multivariate linear regression model
- A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
- Generalized self-concordant functions: a recipe for Newton-type methods
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Newton-Stein method: an optimization method for GLMs via Stein's lemma
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Scalable approximations for generalized linear problems
- A bootstrap method for error estimation in randomized matrix multiplication
- Utilizing second order information in minibatch stochastic variance reduced proximal iterations
- Robust frequent directions with application in online learning
- Optimization methods for large-scale machine learning
- Nesterov's acceleration for approximate Newton
- Randomized sketching algorithms for low-memory dynamic optimization
- Approximate Newton methods
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- Randomized sketch descent methods for non-separable linearly constrained optimization
- Sketched Newton-Raphson
- Stochastic reformulations of linear systems: algorithms and convergence theory
- An investigation of Newton-sketch and subsampled Newton methods
- Convergence of Newton-MR under inexact Hessian information
- A stochastic semismooth Newton method for nonsmooth nonconvex optimization
- Randomized block proximal damped Newton method for composite self-concordant minimization
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- Convergence analysis of a subsampled Levenberg-Marquardt algorithm
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- An overview of stochastic quasi-Newton methods for large-scale machine learning
- On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
- Generalized linear models for massive data via doubly-sketching
- Global optimization using random embeddings
- Hessian averaging in stochastic Newton methods achieves superlinear convergence
- Riemannian Natural Gradient Methods
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- Randomized estimation of functional covariance operator via subsampling
- Random projections for linear programming: an improved retrieval phase
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Subsampled first-order optimization methods with applications in imaging
- Optimal neural network approximation of Wasserstein gradient direction via convex optimization
- A multilevel method for self-concordant minimization
- A proximal stochastic quasi-Newton algorithm with dynamical sampling and stochastic line search
- SketchySGD: reliable stochastic optimization via randomized curvature estimates
- Trust region-type method under inexact gradient and inexact Hessian with convergence analysis
- Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
- Training multi-layer over-parametrized neural network in subquadratic time
- Practical operator sketching framework for accelerating iterative data-driven solutions in linear inverse problems
- FLECS: a federated learning second-order framework via compression and sketching
- Accelerated adaptive cubic regularized quasi-Newton methods
- A guide to stochastic optimisation for large-scale inverse problems
- Accelerated double-sketching subspace Newton
- Surrogate-based autotuning for randomized sketching algorithms in regression problems
- Efficient convex optimization requires superlinear memory
- Training (overparametrized) neural networks in near-linear time
- Quasi-Newton method with subspace gradients
- A variable dimension sketching strategy for nonlinear least-squares
- Incremental Gauss-Newton methods with superlinear convergence rates
- librla: Randomized Linear Algebra Library
- Equivariant test-time training with operator sketching for imaging inverse problems
- Second-order information promotes mini-batch robustness in variance-reduced gradients
- Covering number of real algebraic varieties and beyond: improved bounds and applications
This page was built for publication: Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2967608)
