Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information

Abstract

We consider variants of trust-region and cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under mild conditions on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve $\epsilon$-approximate second-order optimality which have shown to be tight. Our Hessian approximation conditions constitute a major relaxation over the existing ones in the literature. Consequently, we are able to show that such mild conditions allow for the construction of the approximate Hessian through various random sampling methods. In this light, we consider the canonical problem of finite-sum minimization, provide appropriate uniform and non-uniform sub-sampling strategies to construct such Hessian approximations, and obtain optimal iteration complexity for the corresponding sub-sampled trust-region and cubic regularization methods.

32 pages

References in corpus (18)

• Deep Learning in Neural Networks: An Overview
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• The Loss Surfaces of Multilayer Networks
• Sketching as a Tool for Numerical Linear Algebra
• How to Escape Saddle Points Efficiently
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Proximal Stochastic Dual Coordinate Ascent
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Methods for Non-Convex Optimization
• Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
• Local minima in training of neural networks
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Second-Order Methods with Cubic Regularization Under Inexact Information
• Simultaneous Source for non-uniform data variance and missing data
• Black-Box Optimization in Machine Learning with Trust Region Based Derivative Free Algorithm
• Stochastic Second-Order Optimization via von Neumann Series
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Parallel Stochastic Newton Method

Cited by in corpus (29)

• Escaping Saddles with Stochastic Gradients
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• PyHessian: Neural Networks Through the Lens of the Hessian
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Inexact Non-Convex Newton-Type Methods
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Distributed Learning of Deep Neural Networks using Independent Subnet Training
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• Finding Local Minima via Stochastic Nested Variance Reduction
• Cubic Regularization with Momentum for Nonconvex Optimization
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
• A Stochastic Trust Region Method for Non-convex Minimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• GPU Accelerated Sub-Sampled Newton's Method
• Bernstein Concentration Inequalities for Tensors via Einstein Products
• Implicit Langevin Algorithms for Sampling From Log-concave Densities
• Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
• A note on solving nonlinear optimization problems in variable precision
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
• Precise expressions for random projections: Low-rank approximation and randomized Newton