Trust-region algorithms for training responses: machine learning methods using indefinite Hessian approximations

DOI10.1080/10556788.2019.1624747zbMATH Open1440.90092arXiv1807.00251OpenAlexW2811026747WikidataQ127744831 ScholiaQ127744831MaRDI QIDQ5113710FDOQ5113710

Joshua D. Griffin, Jennifer B. Erway, Roummel F. Marcia, Riadh Omheni

Publication date: 16 June 2020

Published in: Optimization Methods \& Software (Search for Journal in Brave)

Abstract: Machine learning (ML) problems are often posed as highly nonlinear and nonconvex unconstrained optimization problems. Methods for solving ML problems based on stochastic gradient descent are easily scaled for very large problems but may involve fine-tuning many hyper-parameters. Quasi-Newton approaches based on the limited-memory Broyden-Fletcher-Goldfarb-Shanno (BFGS) update typically do not require manually tuning hyper-parameters but suffer from approximating a potentially indefinite Hessian with a positive-definite matrix. Hessian-free methods leverage the ability to perform Hessian-vector multiplication without needing the entire Hessian matrix, but each iteration's complexity is significantly greater than quasi-Newton methods. In this paper we propose an alternative approach for solving ML problems based on a quasi-Newton trust-region framework for solving large-scale optimization problems that allow for indefinite Hessian approximations. Numerical experiments on a standard testing data set show that with a fixed computational time budget, the proposed methods achieve better results than the traditional limited-memory BFGS and the Hessian-free methods.

Full work available at URL: https://arxiv.org/abs/1807.00251

zbMATH Keywords

machine learningtrust-region methodsnon-convexlarge-scale optimizationquasi-Newton methodslimited-memory symmetric rank-one update

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Large-scale problems in mathematical programming (90C06) Methods of quasi-Newton type (90C53) Linear equations (linear algebraic aspects) (15A06) Newton-type methods (49M15)

Cites Work

• Computing a Trust Region Step
• The elements of statistical learning. Data mining, inference, and prediction
• Title not available (Why is that?)
• Solving the Trust-Region Subproblem using the Lanczos Method
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the limited memory BFGS method for large scale optimization
• A stochastic quasi-Newton method for large-scale optimization
• Updating Quasi-Newton Matrices with Limited Storage
• A Stochastic Approximation Method
• Sample size selection in optimization methods for machine learning
• Representations of quasi-Newton matrices and their use in limited memory methods
• Trust Region Methods
• Convergence of quasi-Newton matrices generated by the symmetric rank one update
• On Efficiently Computing the Eigenvalues of Limited-Memory Quasi-Newton Matrices
• The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
• Testing a Class of Methods for Solving Minimization Problems with Simple Bounds on the Variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new matrix-free algorithm for the large-scale trust-region subproblem
• Iterative Methods for Finding a Trust-region Step
• A Subspace Minimization Method for the Trust-Region Step
• Computing Optimal Locally Constrained Steps
• Minimizing a quadratic over a sphere
• Algorithm 873
• Title not available (Why is that?)
• On solving L-SR1 trust-region subproblems
• Optimization Methods for Large-Scale Machine Learning
• A quasi-Newton algorithm for nonconvex, nonsmooth optimization with global convergence guarantees
• A robust multi-batch L-BFGS method for machine learning

Cited In (4)

• Second-order design sensitivity analysis using diagonal hyper-dual numbers
• A non-monotone trust-region method with noisy oracles and additional sampling
• Globally Convergent Multilevel Training of Deep Residual Networks
• A limited-memory trust-region method for nonlinear optimization with many equality constraints

Uses Software

• L-BFGS
• LSTRS
• GQTPAR
• MNIST
• TensorFlow
• Spearmint
• Hyperopt
• AdaGrad
• Adam
• HOGWILD
• EMNIST
• TuPAQ
• HSL-VF05
• ADADELTA

This page was built for publication: Trust-region algorithms for training responses: machine learning methods using indefinite Hessian approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113710)