RES: Regularized Stochastic BFGS Algorithm

Abstract

RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments can be prohibitive in high dimensional problems. Application of second order methods, on the other hand, is impracticable because computation of objective function Hessian inverses incurs excessive computational cost. BFGS modifies gradient descent by introducing a Hessian approximation matrix computed from finite gradient differences. RES utilizes stochastic gradients in lieu of deterministic gradients for both, the determination of descent directions and the approximation of the objective function's curvature. Since stochastic gradients can be computed at manageable computational cost RES is realizable and retains the convergence rate advantages of its deterministic counterparts. Convergence results show that lower and upper bounds on the Hessian egeinvalues of the sample functions are sufficient to guarantee convergence to optimal arguments. Numerical experiments showcase reductions in convergence time relative to stochastic gradient descent algorithms and non-regularized stochastic versions of BFGS. An application of RES to the implementation of support vector machines is developed.

13 pages

Cited by in corpus (40)

• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Global Convergence of Online Limited Memory BFGS
• Decentralized Quasi-Newton Methods
• Stochastic Conjugate Gradient Algorithm with Variance Reduction
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• A Survey of Optimization Methods from a Machine Learning Perspective
• Practical Quasi-Newton Methods for Training Deep Neural Networks
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• A globally convergent incremental Newton method
• A Variance Reduced Stochastic Newton Method
• Hemingway: Modeling Distributed Optimization Algorithms
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• Estimation of discrete choice models with hybrid stochastic adaptive batch size algorithms
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Accelerated Gradient Temporal Difference Learning
• Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?
• A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• An efficient Averaged Stochastic Gauss-Newton algorithm for estimating parameters of non linear regressions models
• Stochastic Subspace Descent
• Stochastic quasi-Newton with line-search regularization
• Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• A Stochastic Quasi-Newton Method for Large-Scale Nonconvex Optimization with Applications
• Stochastic Trust Region Inexact Newton Method for Large-scale Machine Learning
• Stochastic quasi-Newton with adaptive step lengths for large-scale problems
• DynaNewton - Accelerating Newton's Method for Machine Learning
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
• Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
• Stochastic Damped L-BFGS with Controlled Norm of the Hessian Approximation
• A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning
• Low Dimensional Landscape Hypothesis is True: DNNs can be Trained in Tiny Subspaces
• Quasi-Newton Quasi-Monte Carlo for variational Bayes
• The Outer Product Structure of Neural Network Derivatives
• A Quasi-Newton Method for Large Scale Support Vector Machines
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
• Tensor Normal Training for Deep Learning Models
• Automatic and Simultaneous Adjustment of Learning Rate and Momentum for Stochastic Gradient Descent
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms