Krylov Subspace Descent for Deep Learning

Abstract

In this paper, we propose a second order optimization method to learn models where both the dimensionality of the parameter space and the number of training samples is high. In our method, we construct on each iteration a Krylov subspace formed by the gradient and an approximation to the Hessian matrix, and then use a subset of the training data samples to optimize over this subspace. As with the Hessian Free (HF) method of [7], the Hessian matrix is never explicitly constructed, and is computed using a subset of data. In practice, as in HF, we typically use a positive definite substitute for the Hessian matrix such as the Gauss-Newton matrix. We investigate the effectiveness of our proposed method on deep neural networks, and compare its performance to widely used methods such as stochastic gradient descent, conjugate gradient descent and L-BFGS, and also to HF. Our method leads to faster convergence than either L-BFGS or HF, and generally performs better than either of them in cross-validation accuracy. It is also simpler and more general than HF, as it does not require a positive semi-definite approximation of the Hessian matrix to work well nor the setting of a damping parameter. The chief drawback versus HF is the need for memory to store a basis for the Krylov subspace.

Cited by in corpus (24)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Real-Time COVID-19 Diagnosis from X-Ray Images Using Deep CNN and Extreme Learning Machines Stabilized by Chimp Optimization Algorithm
• Equilibrated adaptive learning rates for non-convex optimization
• Convergence rates of sub-sampled Newton methods
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• Imposing Hard Constraints on Deep Networks: Promises and Limitations
• Strong error analysis for stochastic gradient descent optimization algorithms
• Normalization Techniques in Training DNNs: Methodology, Analysis and Application
• Practical Quasi-Newton Methods for Training Deep Neural Networks
• A Kronecker-factored approximate Fisher matrix for convolution layers
• Optimization of Convolutional Neural Network using Microcanonical Annealing Algorithm
• Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networks
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• A Coordinate-Free Construction of Scalable Natural Gradient
• Accelerating Natural Gradient with Higher-Order Invariance
• Algorithms for solving optimization problems arising from deep neural net models: smooth problems
• Deep Curvature Suite
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Primal-Dual Sequential Subspace Optimization for Saddle-point Problems
• Improving Optimization for Models With Continuous Symmetry Breaking
• Second-order Information in First-order Optimization Methods
• Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
• Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization