Exact and inexact subsampled Newton methods for optimization
From MaRDI portal
Abstract: The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear rate of convergence in expectation. The second part of the paper analyzes an inexact Newton method that solves linear systems approximately using the conjugate gradient (CG) method, and that samples the Hessian and not the gradient (the gradient is assumed to be exact). We provide a complexity analysis for this method based on the properties of the CG iteration and the quality of the Hessian approximation, and compare it with a method that employs a stochastic gradient iteration instead of the CG method. We report preliminary numerical results that illustrate the performance of inexact subsampled Newton methods on machine learning applications based on logistic regression.
Recommendations
- Sub-sampled Newton methods
- Subsampled inexact Newton methods for minimizing large sums of convex functions
- On the use of stochastic Hessian information in optimization methods for machine learning
- Subsampled Hessian Newton Methods for Supervised Learning
- Linesearch Newton-CG methods for convex optimization with noise
Cited in
(63)- Sub-sampled Newton methods
- On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization
- Linesearch Newton-CG methods for convex optimization with noise
- A hybrid stochastic optimization framework for composite nonconvex optimization
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- Inexact restoration with subsampled trust-region methods for finite-sum minimization
- Generalized self-concordant functions: a recipe for Newton-type methods
- Statistically equivalent surrogate material models: impact of random imperfections on the elasto-plastic response
- Adversarial classification via distributional robustness with Wasserstein ambiguity
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- On the asymptotic rate of convergence of stochastic Newton algorithms and their weighted averaged versions
- On the use of stochastic Hessian information in optimization methods for machine learning
- Utilizing second order information in minibatch stochastic variance reduced proximal iterations
- Second-order stochastic optimization for machine learning in linear time
- Nesterov's acceleration for approximate Newton
- A robust multi-batch L-BFGS method for machine learning
- Approximate Newton methods
- Stochastic proximal gradient method FOR _1 regularized optimization over a sphere
- A fully stochastic second-order trust region method
- Quasi-Newton methods for machine learning: forget the past, just sample
- Sketched Newton-Raphson
- slimTrain---A Stochastic Approximation Method for Training Separable Deep Neural Networks
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- An investigation of Newton-sketch and subsampled Newton methods
- Convergence of Newton-MR under inexact Hessian information
- Train Like a (Var)Pro: Efficient Training of Neural Networks with Variable Projection
- Stochastic sub-sampled Newton method with variance reduction
- A stochastic semismooth Newton method for nonsmooth nonconvex optimization
- Subsampled Hessian Newton Methods for Supervised Learning
- Convergence analysis of inexact randomized iterative methods
- Subsampled inexact Newton methods for minimizing large sums of convex functions
- LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums
- An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians
- Convergence analysis of a subsampled Levenberg-Marquardt algorithm
- A trust region method for noisy unconstrained optimization
- An adaptive sampling augmented Lagrangian method for stochastic optimization with deterministic constraints
- SVRG meets AdaGrad: painless variance reduction
- 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
- Newton-MR: inexact Newton method with minimum residual sub-problem solver
- Generalized linear models for massive data via doubly-sketching
- Hessian averaging in stochastic Newton methods achieves superlinear convergence
- Inexact Newton-CG algorithms with complexity guarantees
- Adaptive sampling quasi-Newton methods for zeroth-order stochastic optimization
- On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations
- Convergence analysis of stochastic higher-order majorization–minimization algorithms
- Subsampled first-order optimization methods with applications in imaging
- A non-monotone trust-region method with noisy oracles and additional sampling
- On the inversion-free Newton's method and its applications
- 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
- A stochastic objective-function-free adaptive regularization method with optimal complexity
- Regularized methods via cubic model subspace minimization for nonconvex optimization
- A stochastic augmented Lagrangian method for stochastic convex programming
- A stochastic use of the Kurdyka-Łojasiewicz property: investigation of optimization algorithms behaviours in a non-convex differentiable framework
- Generalized subsampled Newton method for large-scale linear inequalities with Tikhonov regularization
- Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
- A survey of trust-region radius update mechanisms. Part I: First-order analysis
- New Globalized Newton-Type Methods for Nonconvex Optimization Problems
- Second-order information promotes mini-batch robustness in variance-reduced gradients
This page was built for publication: Exact and inexact subsampled Newton methods for optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854329)
