Inexact Non-Convex Newton-Type Methods

Abstract

For solving large-scale non-convex problems, we propose inexact variants of trust region and adaptive cubic regularization methods, which, to increase efficiency, incorporate various approximations. In particular, in addition to approximate sub-problem solves, both the Hessian and the gradient are suitably approximated. Using rather mild conditions on such approximations, we show that our proposed inexact methods achieve similar optimal worst-case iteration complexities as the exact counterparts. Our proposed algorithms, and their respective theoretical analysis, do not require knowledge of any unknowable problem-related quantities, and hence are easily implementable in practice. In the context of finite-sum problems, we then explore randomized sub-sampling methods as ways to construct the gradient and Hessian approximations and examine the empirical performance of our algorithms on some real datasets.

arXiv comment36 pages, 2 figures

References in corpus (12)

• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• How to Escape Saddle Points Efficiently
• The Power of Normalization: Faster Evasion of Saddle Points
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
• Local minima in training of neural networks
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• Training Neural Networks with Stochastic Hessian-Free Optimization
• Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales
• Stochastic Optimization Using a Trust-Region Method and Random Models

Cited by in corpus (12)

• PyHessian: Neural Networks Through the Lens of the Hessian
• Convergence of Newton-MR under Inexact Hessian Information
• Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
• A Note on Inexact Condition for Cubic Regularized Newton's Method
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information
• An Adaptive Sample Size Trust-Region Method for Finite-Sum Minimization
• Precise expressions for random projections: Low-rank approximation and randomized Newton
• Adaptive norms for deep learning with regularized Newton methods
• Invexifying Regularization of Non-Linear Least-Squares Problems
• Non-PSD Matrix Sketching with Applications to Regression and Optimization