PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Quasi-Newton Methods for Training Deep Neural Networks

Donald Goldfarb, Yi Ren, Achraf Bahamou

arXiv:2006.08877v3cs.LGmath.OCstat.ML

TL;DR

DNNs can have tens of millions of variables, making full quasi-Newton approximations impractical. The paper proposes layer-wise Kronecker-factored BFGS and L-BFGS methods with damping; on the tested feed-forward models, they outperformed or performed comparably to state-of-the-art first- and second-order methods.

  • Problem

    DNNs can have tens of millions of variables, making full BFGS storage or even modest L-BFGS pair storage impractical.

    Source: §1 · p. 1

  • Method

    The proposed K-BFGS and K-BFGS(L) methods approximate layer-wise Hessian blocks with Kronecker factors and use a damping scheme for their quasi-Newton updates.

    Source: §1 · pp. 1–2

  • Results

    The methods outperform or perform comparably to state-of-the-art first- and second-order methods in experiments on multi-layer feed-forward neural network models.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The proposed methods use layer-wise second-order information with modest memory and computational resources, and the authors state they can extend to convolutional and recurrent networks.

    Source: §7 · p. 9

    The paper focuses on fully connected layers, although the authors state the approximation can extend to convolutional and recurrent layers.

    Source: §2 · p. 3

Abstract

from arXiv · show

We consider the development of practical stochastic quasi-Newton, and in particular Kronecker-factored block-diagonal BFGS and L-BFGS methods, for training deep neural networks (DNNs). In DNN training, the number of variables and components of the gradient $n$ is often of the order of tens of millions and the Hessian has $n^2$ elements. Consequently, computing and storing a full $n \times n$ BFGS approximation or storing a modest number of (step, change in gradient) vector pairs for use in an L-BFGS implementation is out of the question. In our proposed methods, we approximate the Hessian by a block-diagonal matrix and use the structure of the gradient and Hessian to further approximate these blocks, each of which corresponds to a layer, as the Kronecker product of two much smaller matrices. This is analogous to the approach in KFAC, which computes a Kronecker-factored block-diagonal approximation to the Fisher matrix in a stochastic natural gradient method. Because the indefinite and highly variable nature of the Hessian in a DNN, we also propose a new damping approach to keep the upper as well as the lower bounds of the BFGS and L-BFGS approximations bounded. In tests on autoencoder feed-forward neural network models with either nine or thirteen layers applied to three datasets, our methods outperformed or performed comparably to KFAC and state-of-the-art first-order stochastic methods.

1 Introduction

The paper develops stochastic Kronecker-factored BFGS and L-BFGS methods to make quasi-Newton training practical for deep neural networks. It situates these methods among prior stochastic second-order approaches and identifies their algorithmic and convergence contributions.

1 Introduction

  • With tens of millions of variables, full BFGS matrices and even modest L-BFGS pair storage are impractical, motivating layer-wise Kronecker-factored Hessian blocks.Each block corresponds to a layer and is approximated by the Kronecker product of two much smaller matrices.Source: §1 · p. 1
  • Common first-order methods scale stochastic gradients diagonally using estimates of individual components’ first and second moments.Examples include AdaGrad, RMSprop, and Adam [24].Source: §1 · p. 2
  • Prior stochastic second-order work spans quasi-Newton, generalized Gauss-Newton, and natural-gradient methods, including methods for strongly convex and nonconvex problems.The cited approaches include variance-reduced and online BFGS/L-BFGS methods, as well as Hessian-free and Krylov-subspace methods.Source: §1 · p. 2
  • The contributions include structured BFGS and L-BFGS variants, comparable per-iteration resource requirements to first-order methods, and damping that bounds both ends of the approximation’s eigenvalue range.The paper also reports a novel Hessian-action BFGS application and, to the authors’ knowledge, the first convergence proof for a stochastic Kronecker-factored quasi-Newton method.Source: §1 · p. 2

2 Kronecker-factored Quasi-Newton Method for DNN

The method exploits layer-wise Kronecker structure to build stochastic quasi-Newton updates for feed-forward networks. It updates separate factors using gradient information and Hessian-action BFGS, with damping for the relevant updates.

2 Kronecker-factored Quasi-Newton Method for DNN

  • For a single data point, each layer’s gradient and Hessian have Kronecker structure, which the method uses to construct layer-wise quasi-Newton approximations.For the gradient, the vectorized layer gradient is the Kronecker product of the preceding activation and the layer’s back-propagated quantity.Source: §2 · p. 3
  • The method focuses on fully connected layers, while the authors state that the Kronecker-factored block approximation can extend to convolutional and recurrent layers.The algorithm’s high-level iteration performs a forward-backward pass, updates layer weights, then uses another pass to obtain quantities for its factor updates.Source: §2 · pp. 3–4
  • Across data points, the method approximates the expectation of a Kronecker product by the Kronecker product of expectations, as in KFAC [30].The resulting layer-wise step uses the factors with an estimated layer gradient.Source: §2 · p. 3
  • The algorithm updates the gradient-side factor with damped BFGS or L-BFGS using changes in the layer quantities, and the activation-side factor with Hessian-action BFGS.The Hessian-action update uses a Levenberg-Marquardt damping term to address possible singularity of the positive-semidefinite matrix approximated by the inverse factor.Source: §2 · p. 3

3 BFGS and L-BFGS for Gl

Because nonconvexity and stochastic curvature changes can undermine BFGS updates, the paper proposes double damping of the update pair. It also uses a non-loop L-BFGS implementation to reduce the cost of applying the approximation.

3 BFGS and L-BFGS for Gl

  • Nonconvexity means the layer curvature matrix is often not positive definite, while stochastic updates make line-search enforcement impractical and large curvature changes require suppression.The proposed double-damping procedure modifies the update pair to address both positive-definiteness and large-change concerns.Source: §3 · p. 4
  • Double damping applies Powell’s damping first to the inverse approximation and then with B = I, imposing the stated curvature-ratio bounds at each step.The first step bounds yᵀHy/sᵀy by 1/µ1; the second bounds sᵀs/sᵀy by 1/µ2.Source: §3 · p. 4
  • The implementation uses non-loop L-BFGS because its two matrix-matrix multiplications are more efficient than the standard two-loop recursion when p and layer dimensions are large.The authors used p = 100 in their tests; the stated operation costs are O(pdido) for the non-loop multiplications versus 4p matrix-vector multiplications of O(dido) each for the standard approach.Source: §3 · p. 5

4 "Hessian action" BFGS for Al

The Hessian-action update constructs curvature pairs from a matrix action and has a rank-one inverse-update interpretation. Momentum complicates the scaled version, and Levenberg-Marquardt damping is used for stability.

4 "Hessian action" BFGS for Al

  • The Hessian-action method forms pairs with s = Hl a·Ei[al−1(i)] and y = Als, although Al does not represent an objective-function Hessian.The paper describes generating these pairs by Hessian action.Source: §4 · p. 5
  • For rank-one updates A+ = A + c·aaᵀ, every Broyden-family quasi-Newton update recovers (A+)^-1 when H = A^-1 and the pair is chosen by Hessian action.The theorem’s choice is s = Ha and y = A+s; BFGS and DFP are included in the stated family.Source: §4 · p. 5
  • With momentum, scaling H by 1/β to retain the rank-one result is unstable, so the implementation uses non-scaled Hessian-action BFGS.For this update, the paper adds Levenberg-Marquardt damping when Al may be singular or have very small positive eigenvalues.Source: §4 · p. 5

5 Convergence Analysis

The analysis establishes a convergence rate for a specified K-BFGS(L) variant under stated assumptions. Its proof also bounds the inverse-Hessian approximation above and below by positive-definite matrices.

5 Convergence Analysis

  • N = O(ϵ^-1/(1-β)) iterations suffice for E[∥∇f(θk)∥²] ≤ ϵ when β ∈ (0.5, 1), under the stated assumptions.The result concerns K-BFGS(L) with skipping DD and exact inversion on A_l.Source: §5 · p. 6
  • The convergence result assumes a continuously differentiable loss bounded below with a globally Lipschitz gradient, alongside the other stated assumptions.The prescribed step size is proportional to k^-β for β ∈ (0.5, 1).Source: §5 · p. 6
  • The inverse-Hessian approximation is bounded above and below by positive-definite matrices when the stated assumptions, including bounded activations, hold.The paper notes that sigmoid and tanh satisfy the bounded-activation assumption.Source: §5 · p. 6

6 Experiments

Across three autoencoder tasks, K-BFGS and K-BFGS(L) generally compare favorably with first-order methods and comparably with KFAC. The section also reports their resource requirements, robustness checks, and experimental setup.

Mini-batch and Moving Average

  • The methods use mini-batch estimates and exponentially decaying moving averages to incorporate past information and reduce variability.The section also notes that computing the updated activations uses the same mini-batch and doubles forward-backward passes per iteration.Source: §6 · pp. 6–7

Storage and Computational Complexity

  • K-BFGS and K-BFGS(L) have storage requirements comparable to first-order methods and require less computation per iteration than KFAC.The stated computational difference is that the K-BFGS methods use matrix multiplications, while KFAC uses matrix inversions whose cost depends cubically on input and output dimensions.Source: §6 · p. 7, Table 1 · p. 7, Table 2 · p. 7

Experimental Results

  • The experiments compare K-BFGS, K-BFGS(L), KFAC, Adam/RMSprop, and momentum SGD on MNIST, FACES, and CURVES autoencoders using ReLU activations.For Figure 1, the authors selected hyperparameters by grid search and plotted means and standard deviations from 20 runs with different random seeds.Source: §6 · pp. 7–9
  • K-BFGS methods outperform first-order methods on training loss except on CURVES, where RMSprop/Adam are exceptions, and perform comparably to KFAC in CPU time and epochs; K-BFGS(L) and KFAC similarly outperform first-order methods on test error.Figure 1 compares MNIST, FACES, and CURVES using training loss and testing mean-square error against epochs and CPU time.Source: Figure 1 · p. 8, §6 · p. 9
  • The authors report that their methods remain stable across a fairly wide range of hyperparameter settings.The claim refers to loss under varied hyperparameters.Source: §6 · p. 9
  • With mini-batches of 100, the methods retain advantageous training and testing performance, though these runs did not use 20 random seeds.The authors contrast these results with batch size 1000 and describe the approach as robust in the stochastic setting.Source: §6 · p. 9
  • K-BFGS and K-BFGS(L) can double the minibatch size for computing the stochastic gradient with almost no extra cost relative to the other methods discussed.The authors identify this as a potential advantage in highly stochastic settings.Source: §6 · p. 9

7 Conclusion

The paper concludes that its Kronecker-factored quasi-Newton methods train feed-forward networks with layer-wise second-order information and modest resources. It also discusses possible broader impacts and provides detailed pseudocode for K-BFGS/K-BFGS(L).

7 Conclusion

  • K-BFGS and K-BFGS(L) use layer-wise second-order information with modest memory and computation, and outperform or perform comparably to state-of-the-art first- and second-order methods in the reported experiments.The authors state that the methods can be extended to convolutional and recurrent neural networks.Source: §7 · p. 9

Broader Impact

  • The authors argue that greater training efficiency could help save energy, while noting that optimization algorithms may also be used for harmful purposes beyond the work's control.The broader-impact discussion names potential beneficial and harmful applications of DNNs.Source: Broader Impact · p. 10

A Pseudocode for K-BFGS/K-BFGS(L)

  • Algorithm 4 provides pseudocode for K-BFGS/K-BFGS(L), with inputs including batch size, learning rate, damping, and the stored-pair count for K-BFGS(L).The authors direct readers to Sections 3, 4, and Appendix C for details.Source: A Pseudocode for K-BFGS/K-BFGS(L) · p. 12

B Convergence: Proofs of Lemmas 1-3 and Theorem 2

The convergence argument establishes the bounded, positive-definite inverse approximations required by the stochastic quasi-Newton framework. The proposed double damping modifies curvature pairs in two steps to maintain update conditions without an inexact line search.

B Convergence: Proofs of Lemmas 1-3 and Theorem 2

C Powell’s Damped BFGS Updating

  • Because DNN line searches are expensive, the proposed Powell-based heuristic modifies curvature pairs to preserve positive definiteness of the BFGS approximation.The identity-based damping step ensures ỹᵀŝ ≥ µ₂ŝᵀŝ.Source: C Powell’s Damped BFGS Updating · p. 15

C.1 Double Damping (DD)

  • Powell damping on H bounds yᵀHy relative to sᵀy, while the identity-based second step bounds the modified curvature product relative to the step norm.These safeguards constrain the damped pair used in BFGS updates.Source: C Powell’s Damped BFGS Updating · p. 15
  • Double damping first interpolates current and past curvature through Powell damping on H, then applies identity-based damping interpretable as Levenberg–Marquardt damping.The method is designed to address stochastic curvature pairs and large curvature changes without line search.Source: §C.1 · p. 15
  • The authors report that at least 90% of iterations satisfy the stated curvature inequality even without skipping pairs, and skipping has only slight performance impact.The report concerns K-BFGS(L) tests on MNIST, FACES, and CURVES.Source: §C.1 · p. 15

D Implementation Details and More Experiments

The implementation section describes KFAC and first-order baselines, initialization and curvature estimation, and the autoencoder problems used in the experiments.

D.1.1 KFAC

  • KFAC uses layerwise curvature factors and periodically recomputes inverse factors; its G matrices are distinct from the G matrices used in K-BFGS.The described KFAC routine also updates its factors using mini-batch statistics.Source: §D.1.1 · p. 15, Algorithm 7 KFAC · p. 17

D.1.2 Adam/RMSprop

  • Adam and RMSprop differ in the implementation of moment estimates: Adam applies bias correction to the first and second moments, while RMSprop does not.Source: §D.1.2 · p. 16

D.1.3 Initialization of Algorithms

  • Second-order methods use a warm start that estimates applicable curvature information from the entire training set before parameter updates begin.The initialization procedure estimates A for K-BFGS variants and A and G for KFAC.Source: §D.1.3 · p. 16

Algorithm 7 KFAC

  • KFAC and the K-BFGS variants initialize their layerwise A inverse approximation to identity, while the L-BFGS curvature-pair information is applied to an identity initial matrix.The reported initialization and warm-start costs are roughly twice as large for KFAC as for K-BFGS and K-BFGS(L).Source: Algorithm 7 KFAC · p. 17

D.2 Autoencoder Problems

  • The experiments use MNIST, FACES, and CURVES autoencoder problems, with a regularization term η/2 ||θ||² where η = 10⁻⁵.Table 4 specifies the three problem architectures.Source: §D.2 · p. 17, Table 3 · p. 17, Table 4 · p. 17

D.3 Specification of Hyper-parameters

The authors tune learning rate and damping, set several other algorithm parameters, and evaluate sensitivity to learning-rate and damping choices. Both K-BFGS variants are reported robust across a fairly wide range of those hyperparameters.

D.3 Specification of Hyper-parameters

  • The tuning search varies learning rate α and damping λ, while the selected settings minimize deterministic loss at epoch ends; the reported minibatch size is 1000.The search includes multiple values for each parameter, and the best values are listed in Table 5.Source: §D.3 · pp. 17–18, Table 5 · p. 18
  • The authors set µ₁ = 0.2 for double damping and p = 100 stored curvature pairs for K-BFGS(L), but note smaller p might be more efficient on narrow layers.They did not investigate smaller p for simplicity and consistency.Source: §D.3 · p. 18
  • With β₂ = 0.999, Adam results were similar to those reported using β₂ = 0.9; the latter was chosen for a fair comparison.Source: §D.3 · p. 18

D.4 Sensitivity to Hyper-parameters

  • Both K-BFGS and K-BFGS(L) are robust within a fairly wide range of learning rates α and damping values λ.Figure 3 maps loss against these parameters for MNIST, FACES, and CURVES, with separate rows for the two methods.Source: §D.4 · p. 19, Figure 3 · p. 19

D.5 Experimental Results Using Mini-batches of Size 100

With minibatches of size 100, the proposed methods continued to perform advantageously in training and testing, and K-BFGS(L) clearly outperformed KFAC in CURVES training. The figures report training loss and testing error across epoch and CPU-time views.

D.5 Experimental Results Using Mini-batches of Size 100

  • The comparison figures show training loss in the upper row and testing mean-square error in the lower row, with progress plotted against epochs and CPU time.Source: §D.5 · p. 19, Figure 4 · p. 20, Figure 5 · p. 21
  • K-BFGS(L) clearly outperformed KFAC in training on CURVES with minibatches of size 100, while the proposed methods remained advantageous in training and testing.Source: §D.5 · p. 19

D.6 Doubling the Mini-batch for the Gradient at Almost No Cost

The method can nearly double the gradient minibatch at little extra cost by averaging the current stochastic gradient with one computed on the previous iteration. Preliminary tests found little benefit from this option, though K-BFGS remained stable across variants.

D.6 Doubling the Mini-batch for the Gradient at Almost No Cost

  • Averaging the current gradient with one computed on the previous iteration nearly doubles the gradient minibatch at almost no extra cost.With m = 1000, double-grad-minibatch uses gradients from 2000 data points per iteration, except the first.Source: §D.6 · p. 22
  • Preliminary experiments found that "double-grad" did not help much, while K-BFGS performed stably across variants; comparison tested an earlier K-BFGS version with minibatch size m=1000 against variants with m=500 and 1000.Source: §D.6 · p. 22
  • The authors note that a finer hyperparameter grid search might identify better-performing settings.Source: §D.6 · p. 22
Loading 2006.08877v3…