Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods

Abstract

We present an algorithm for minimizing a sum of functions that combines the computational efficiency of stochastic gradient descent (SGD) with the second order curvature information leveraged by quasi-Newton methods. We unify these disparate approaches by maintaining an independent Hessian approximation for each contributing function in the sum. We maintain computational tractability and limit memory requirements even for high dimensional optimization problems by storing and manipulating these quadratic approximations in a shared, time evolving, low dimensional subspace. Each update step requires only a single contributing function or minibatch evaluation (as in SGD), and each step is scaled using an approximate inverse Hessian and little to no adjustment of hyperparameters is required (as is typical for quasi-Newton methods). This algorithm contrasts with earlier stochastic second order techniques that treat the Hessian of each contributing function as a noisy approximation to the full Hessian, rather than as a target for direct estimation. We experimentally demonstrate improved convergence on seven diverse optimization problems. The algorithm is released as open source Python and MATLAB packages.

References in corpus (7)

• Improving neural networks by preventing co-adaptation of feature detectors
• On the difficulty of training Recurrent Neural Networks
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Pylearn2: a machine learning research library
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• The Natural Gradient by Analogy to Signal Whitening, and Recipes and Tricks for its Use

Cited by in corpus (26)

• Adam: A Method for Stochastic Optimization
• Deep Unsupervised Learning using Nonequilibrium Thermodynamics
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Discovering Hidden Factors of Variation in Deep Networks
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Strong error analysis for stochastic gradient descent optimization algorithms
• Efficient Second Order Online Learning by Sketching
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• A globally convergent incremental Newton method
• A Kronecker-factored approximate Fisher matrix for convolution layers
• Proximal Backpropagation
• Tensor machines for learning target-specific polynomial features
• Algorithms for solving optimization problems arising from deep neural net models: smooth problems
• A Proximal Stochastic Quasi-Newton Algorithm
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Error Bounds and Applications for Stochastic Approximation with Non-Decaying Gain
• Efficient Implementation of Second-Order Stochastic Approximation Algorithms in High-Dimensional Problems
• Low Dimensional Landscape Hypothesis is True: DNNs can be Trained in Tiny Subspaces
• Hessian Estimation via Stein's Identity in Black-Box Problems
• On SGD's Failure in Practice: Characterizing and Overcoming Stalling
• HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems
• Faster Stochastic Quasi-Newton Methods
• Optimization of neural networks via finite-value quantum fluctuations
• Proximal Stochastic Newton-type Gradient Descent Methods for Minimizing Regularized Finite Sums
• Empirical study of PROXTONE and PROXTONE${}^{+}$ for Fast Learning of Large Scale Sparse Models