Source-linked AI summary
Krylov Subspace Descent for Deep Learning
Oriol Vinyals, Daniel Povey
TL;DR
The paper addresses second-order optimization when both parameter dimensionality and training-set size are large. It proposes Krylov Subspace Descent, which optimizes over a gradient–Hessian Krylov subspace using data subsets and Hessian-vector products. KSD converges faster than HF and L-BFGS and generally achieves lower generalization error, while requiring more memory than HF.
Problem
The paper addresses efficient optimization for models with high-dimensional parameter spaces and many training samples, including deep neural networks.
Method
KSD builds a Krylov-subspace basis from gradient and Hessian or Gauss-Newton products, then optimizes the objective over that subspace using a subset of samples.
Results
KSD converges faster than HF and L-BFGS and tends to produce lower generalization error; HF can get stuck with the Hessian, whereas KSD remains faster.
Takeaways & Limitations
KSD provides a simpler and more general alternative to HF because it does not require positive-semidefinite Hessian approximations or damping-parameter heuristics.
Takeaways & Limitations
KSD requires storing K times the parameter dimension for its subspace, and subset-based optimization prevents convergence to an exact optimum.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets large-scale, non-convex optimization for deep networks by optimizing within Krylov subspaces built from gradient and Hessian information. Compared with Hessian Free optimization, it offers greater simplicity and generality, but requires additional memory and sacrifices exact convergence guarantees when using data subsets.
- Background: For high-dimensional problems, truncated Conjugate Gradients approximates Newton updates using Hessian-vector products without explicitly forming or inverting the Hessian.The Pearlmutter trick enables these products efficiently, including for neural networks.
- Method: KSD constructs a basis from gm, Hmgm, …, HK−1gm and optimizes the original nonlinear objective over that subspace using BFGS on a data subset.The Krylov construction can represent the approximate solution obtained by K iterations of CG for any damping value, while allowing more general solutions.
- Advantages over HF: Compared with HF, KSD avoids heuristics for initializing and updating damping, can operate with non-positive-semidefinite Hessian substitutes, and generally improves optimization speed and classification performance.These properties are presented as advantages over HF rather than as universal guarantees.
- Limitations: KSD requires storing K times the parameter dimension for the subspace, and subset-based optimization prevents convergence to an exact optimum.The authors regard the convergence issue as more theoretical than practical in typical deep-network training because overtraining noise is larger.
- Motivation: The method addresses optimization problems with large parameter spaces, many training samples, and potentially ill-conditioned Hessians, with particular interest in deep neural networks.The authors are motivated by applications including speech recognition.
2 The Hessian matrix and the Gauss-Newton matrix
The paper distinguishes the Hessian from positive-semidefinite substitutes such as the Fisher and Gauss–Newton matrices, then explains Hessian–vector and Gauss–Newton–vector products without explicitly constructing the matrices.
- For non-convex problems, the method can substitute a positive definite approximation for the Hessian, including the Fisher information matrix or Gauss–Newton matrix.
- The Gauss–Newton matrix is G = J^T HJ, representing the Hessian contribution that remains after ignoring neural-network parameter nonlinearity.
- Hessian–vector products can be computed efficiently with the Pearlmutter trick, avoiding explicit formation of the Hessian.
- For a parameter direction θ1, modified forward and reverse passes compute v1 = Jθ1 and then the product Gθ1.
- With softmax and negated cross-entropy, treating softmax as part of the error gives a closer Hessian approximation that remains positive semidefinite.
3 Krylov Subspace Descent: overview
KSD replaces HF’s truncated-CG step with optimization over a Krylov subspace built from gradient and Hessian-related directions, while avoiding HF’s damping heuristics and positive-semidefiniteness requirement.
- KSD can use an indefinite Hessian, whereas HF’s usual positive-semidefinite substitute requirement does not apply to KSD.
- Both methods approximate Hessian-related matrices from data subsets and use preconditioning based on the diagonal of the Fisher matrix.
- HF approximately computes a damped Hessian step with conjugate gradients, line search, and heuristics for updating the damping value λ.
- KSD constructs the subspace spanned by {g, Hg, . . . , H^(K−1)g, dprev} and optimizes the objective over it with BFGS on a sample subset.
4 Krylov Subspace Descent in detail
The detailed algorithm builds and preconditions an augmented Krylov basis, computes reduced Hessian information, and uses BFGS on a sample-based objective to choose the update.
- A diagonal Fisher preconditioner changes coordinates before Krylov construction, and a further within-subspace preconditioning step accelerates BFGS convergence.
- The basis is augmented with the previous search direction, which is included in the subspace optimized by BFGS.
- KSD constructs an orthogonal basis for the Krylov subspace and the Hessian or substitute represented in that reduced basis.
- Each iteration uses training-data subsets for the gradient, Hessian or substitute, and BFGS objective, with BFGS optimizing coefficients for approximately K iterations.
- The main parameter is the Krylov dimension K, with K = 20 as an example; the flooring constant ε was set to 10^-4 in experiments.
5 Experiments
Experiments compare KSD with SGD, L-BFGS, HF, and CG across several neural-network tasks, measuring errors and running time. KSD converges faster than HF and generally achieves lower generalization error, while pre-training is mainly useful for MNIST classification.
- Experimental setup: Experiments compare KSD with SGD and second-order methods across CURVES, MNIST, and Aurora tasks.The evaluation reports training and cross-validation errors together with running time.
- Results: KSD converges faster than HF and tends to achieve lower generalization error.The dominant objective, gradient, and Hessian or Gauss-Newton computations are shared between the implementations and performed on a GPU.
- Experimental setup: KSD was evaluated mainly with the Gauss-Newton matrix, using a Krylov subspace dimension of K = 80 for the reported Table 2 results.The standard subspace dimension was 20, but CURVES motivated reporting results with K = 80.
- Results: SGD performance was omitted from Figures 1 and 2 because it was worse than L-BFGS.L-BFGS used a moving window of size 10 for memory compatibility with KSD.
- Results: Pre-training significantly helped HF and KSD on MNIST classification but showed no significant difference on the other tasks.For the other experiments, random initialization and pre-training did not produce a significant difference.
- Evaluation metrics: The reported evaluation includes classification error on a 100K cross-validation set and word error rate on a 5M testing set with varying noise.
6 Conclusion and future work
The paper concludes that KSD is a second-order optimization method that avoids HF’s positive-semidefinite requirement and many heuristics, at the cost of additional memory. Future work examines when pre-training is necessary and applies KSD to recursive neural networks.
- Conclusion: KSD uses Hessian or PSD-approximation matrix-vector products without requiring the approximation itself to be positive semidefinite.
- Conclusion: KSD requires fewer heuristics than HF but uses more memory.
- Future work: Future work will investigate when pre-training is necessary, particularly whether sufficiently advanced optimization can remove that need when overfitting is not dominant.
- Future work: Current work indicates that KSD can efficiently train recursive neural networks without structural damping of the Gauss-Newton matrix.
HF LB HF KS KS
The supplied material contains partial convergence-plot labels and time-axis fragments for comparing optimization methods.
- Figure content: The fragments include log10(time(s)) labels and method names involving L-BFGS, HF, and KSD.
- Figure content: The supplied fragments do not report readable convergence values or a complete comparison outcome.
- Figure content: The labels distinguish HF and KSD variants using the Hessian and Gauss-Newton matrix.