Krylov Subspace Descent for Deep Learning

By Oriol Vinyals, Daniel Povey. 2011

154 citations recorded by the source corpus.

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 Martens (2010), 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 semidefinite 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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, background): “In (Martens, 2010), (Byrd et al., 2011), and (Vinyals & Povey, 2011) stochastic versions of Hessian-free optimization are implemented and applied to optimization of deep networks.”
Revisiting Natural Gradient for Deep Networks (2013, methodology): “Vinyals and Povey (2012) make a similar empirical observation.”
Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs) (2015, methodology): “The recently introduced Hessian-Free Optimization technique (Martens, 2010) and the Krylov Subspace Descent methods (Vinyals & Povey, 2012) use an extended Gauss-Newton approximation of the Hessian, therefore they can be interpreted as versions of natural gradient descent (Pascanu & Bengio, 2014).”
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization (2014, methodology): “Instead we use an approach similar to Krylov subspace descent (Vinyals and Povey, 2012).”
Optimizing Neural Networks with Kronecker-factored Approximate Curvature (2015, background): “Due to their high difﬁculty, performance on these problems has become a standard benchmark for neural network optimization methods (e.g. Martens, 2010; Vinyals and Povey, 2012; Sutskever et al., 2013).”
Deep Learning: Methods and Applications (2014, methodology): “Other learning algorithms such as Hessian free [195, 238] or Krylov subspace methods [378] have shown a similar ability.”
New Insights and Perspectives on the Natural Gradient Method (2014, methodology): “, 2000; Nocedal and Wright, 2006), and other ones such as the “structural damping” approach of Martens and Sutskever (2011), or the approach present in Krylov Subspace Descent (Vinyals and Povey, 2012).”
A Kronecker-factored approximate Fisher matrix for convolution layers (2016, methodology): “F is an n × n matrix, where n is the number of parameters and can be in the tens of millions for modern deep architectures.”
Exact natural gradient in deep linear networks and its application to the nonlinear case (2018, methodology): “When it cannot be stored, one can approximate the natural gradient directly via conjugate gradients, exploiting fast methods for computing Fv products (as in Hessian-free and Gauss-Newton optimization [Martens, 2010; Pascanu and Bengio, 2013; Martens and Grosse, 2015; Vinyals and Povey, 2012]).”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, background): “Among them, algorithms that employ uniform sub-sampling constitute a popular line of work [4, 7, 16, 22].”
New perspectives on the natural gradient method (2014, methodology): “Since the exact minimumG−1∇h is often too difficult to compute, practical methods like the Hessian-free optimization of Marten s [2010], or Krylov Subspace Descent [Vinyals and Povey, 2012], will only approximately minimiz eM(δ). Since computing the whole matrix explicitly is usually too e xp nsive,”
Training Deep and Recurrent Networks with Hessian-Free Optimization (2012, methodology): “It is worth noting that Vinyals and Povey [34] have recently developed an alternative approach to Tikhonov damping, based on the idea of directly optimizing f over a K-dimensional Krylov basis generated by CG (or equivalently a Lanczos iteration).”
Normalization Techniques in Training DNNs: Methodology, Analysis and Application (2020, methodology): “Generally speaking, normalizing gradients is similar to second-order optimization [173], [174], [175], [176] or coordinate-wise adaptive learning rate based methods [7], [177], [178], but with the goal of exploiting the layer-wise structural information in DNNs. Yu et al .”
Implicit Regularization in Deep Learning (2017, methodology): “[95] also discuss the connections between Natural Gradients and some of the other proposed methods for training neural networks, namely Hessian-Free Optimization [96], Krylov Subspace Descent [97] and TONGA [98].”