An investigation of Newton-sketch and subsampled Newton methods
From MaRDI portal
Publication:5135249
Abstract: Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.
Recommendations
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Sub-sampled Newton methods
- Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data
- Exact and inexact subsampled Newton methods for optimization
- Subsampled inexact Newton methods for minimizing large sums of convex functions
Cites work
- A Stochastic Approximation Method
- Coordinate descent algorithms
- Exact and inexact subsampled Newton methods for optimization
- Faster least squares approximation
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 3912096 (Why is no real title available?)
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Numerical Optimization
- Optimization methods for large-scale machine learning
- Second-order stochastic optimization for machine learning in linear time
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Sketching as a tool for numerical linear algebra
- Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data
- Sub-sampled Newton methods
Cited in
(43)- Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data
- Sub-sampled Newton methods
- Linesearch Newton-CG methods for convex optimization with noise
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- Sketch-based empirical natural gradient methods for deep learning
- Subsampled nonmonotone spectral gradient methods
- A sketched finite element method for elliptic models
- Inexact restoration with subsampled trust-region methods for finite-sum minimization
- Random projections of linear and semidefinite problems with linear inequalities
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- A robust multi-batch L-BFGS method for machine learning
- Randomized sketching algorithms for low-memory dynamic optimization
- Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic Hessian accuracy
- Stochastic proximal gradient method FOR _1 regularized optimization over a sphere
- Quasi-Newton methods for machine learning: forget the past, just sample
- Sketched Newton-Raphson
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- Convergence of Newton-MR under inexact Hessian information
- An inertial Newton algorithm for deep learning
- Stochastic proximal quasi-Newton methods for non-convex composite optimization
- A stochastic semismooth Newton method for nonsmooth nonconvex optimization
- Convergence analysis of inexact randomized iterative methods
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians
- 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
- Newton-MR: inexact Newton method with minimum residual sub-problem solver
- Global optimization using random embeddings
- Hessian averaging in stochastic Newton methods achieves superlinear convergence
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- Subsampled first-order optimization methods with applications in imaging
- 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
- Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
- Inexact Gauss-Newton methods with matrix approximation by sampling for nonlinear least-squares and systems
- Generalized subsampled Newton method for large-scale linear inequalities with Tikhonov regularization
- Quasi-Newton method with subspace gradients
- Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
- 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: An investigation of Newton-sketch and subsampled Newton methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5135249)
