PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Gauss-Newton Optimisation for Deep Learning

Aleksandar Botev, Hippolyt Ritter, David Barber

arXiv:1706.03662v2stat.ML

TL;DR

Neural-network second-order optimisation is hindered by infeasible curvature matrices and the tuning burden of first-order methods. The paper develops an efficient block-diagonal, Kronecker-factored Gauss-Newton approximation and finds that second-order methods can compete with well-tuned first-order approaches without hyperparameter tuning. It also shows that piecewise-linear networks have no differentiable local maxima under the stated conditions.

  • Problem

    First-order methods often require repeated hyperparameter tuning, while exact Hessian or Gauss-Newton computation is infeasible for modern neural networks.

  • Method

    The paper develops a recursive block-diagonal Gauss-Newton approximation with Kronecker-factored layer blocks that can be efficiently computed and inverted.

  • Results

    Second-order methods perform competitively against well-tuned state-of-the-art first-order methods without hyperparameter tuning, with faster CPU convergence and more marginal GPU improvement.

  • Takeaways & Limitations

    Practical Gauss-Newton optimisation can be competitive without tuning, while piecewise-linear networks lack differentiable local maxima under the paper’s stated conditions.

  • Takeaways & Limitations

    On GPU wall-clock time, the improvement over first-order methods was more marginal, and near-minimum behavior may be affected by mini-batch noise and numerical errors.

Abstract

from arXiv · show

We present an efficient block-diagonal ap- proximation to the Gauss-Newton matrix for feedforward neural networks. Our result- ing algorithm is competitive against state- of-the-art first order optimisation methods, with sometimes significant improvement in optimisation performance. Unlike first-order methods, for which hyperparameter tuning of the optimisation parameters is often a labo- rious process, our approach can provide good performance even when used with default set- tings. A side result of our work is that for piecewise linear transfer functions, the net- work objective function can have no differ- entiable local maxima, which may partially explain why such transfer functions facilitate effective optimisation.

1. Introduction

The paper develops a practical second-order approach to reduce the tuning burden and computational barriers that limit curvature-based neural-network optimisation. Its block-diagonal, Kronecker-factored method is reported as competitive without hyperparameter tuning, alongside a result about piecewise-linear networks.

  • Motivation: First-order methods require carefully selected learning rates and decay schedules, often necessitating many separate training runs.The paper contrasts this tuning burden with methods intended to work effectively using default settings.
  • Motivation: Explicit Hessian computation is infeasible for modern neural networks, while conjugate-gradient solutions using Hessian-vector products can be too slow.Curvature information can improve progress per step, but the required linear-system iterations may make the approach uncompetitive.
  • Contributions: The proposed method recursively approximates the Hessian with Kronecker-factored blocks, one for each feedforward layer, computed and inverted in a single backward pass.This is the paper’s core computational contribution.
  • Contributions: For piecewise-linear transfer functions, the error surface has no differentiable strict local maxima.The result is presented as a corollary of the recursive Hessian calculation.
  • Contributions: On three standard benchmarks, untuned second-order methods perform competitively against well-tuned state-of-the-art first-order methods.The paper also discusses how its approach relates to KFAC, whose applicability requires a probabilistic output model.

2. Properties of the Hessian

The paper derives recursive Hessian blocks for feedforward networks and uses their structure to characterize optimization surfaces with piecewise-linear transfer functions. Under stated differentiability and loss conditions, layer-wise curvature is positive semidefinite and differentiable local maxima are excluded.

  • Network and Hessian setup: A feedforward network maps input activations through layer weights and elementwise transfer functions to an output on which the loss is defined.Biases are absorbed into the weight matrices by appending a unit to the preceding activations.
  • Network and Hessian setup: The full Hessian is computationally intractable, so the analysis focuses on blocks containing second derivatives with respect to one layer’s weights.This focus is motivated by the Hessian being typically block-diagonal dominant in practice.
  • Block Hessian recursion: The pre-activation Hessian is recursively computed from the output Hessian, allowing each layer’s Hessian block to be obtained with a single backward pass.For multiple datapoints, the recursion is applied per datapoint and the sample Hessians are averaged.
  • Piecewise-linear networks: For piecewise-linear transfer functions, the second-derivative matrices vanish away from nondifferentiable points, simplifying the Hessian recursion.ReLU is given as an example of a piecewise-linear transfer function.
  • Piecewise-linear networks: If the output Hessian is positive semidefinite, pre-activation matrices remain positive semidefinite and the objective is locally convex with respect to each layer’s weights wherever twice differentiable.This excludes layer-wise local maxima and saddle points, except pathological zero-curvature regions.
  • No differentiable local maxima: For piecewise-linear networks, differentiable full-parameter local maxima cannot occur outside pathological constant regions; maxima must lie at sharp activation boundaries.The conclusion is illustrated with a two-layer ReLU and square-loss surface in Figure 1.

3. Approximate Gauss-Newton Method

The paper makes Gauss-Newton optimisation practical by replacing the infeasible full matrix with block-diagonal and Kronecker-factored approximations. Recursive and low-rank variants exploit layer structure, output dimensionality, and piecewise-linear curvature relationships to reduce computation and storage.

  • Gauss-Newton approximation: The Gauss-Newton matrix provides a positive semidefinite curvature approximation, but its exact form cannot feasibly be stored for neural networks.The method therefore applies block-diagonal and further factorised approximations.
  • Gauss-Newton approximation: Expected Gauss-Newton blocks can require O(D4) storage, reaching several terabytes when a layer dimension D is around 1000.The factorised approximation is introduced to make computation and storage feasible.
  • Factorised blocks: Each layer update is computed by solving a linear system in Kronecker-product form, using an activation covariance as one factor.The first factor is the uncentered covariance of the preceding layer’s activations.
  • Recursive structure: For piecewise-linear transfer functions, Hessian diagonal blocks equal Gauss-Newton diagonal blocks wherever derivatives exist.This establishes a direct structural link between the Hessian and the proposed Gauss-Newton recursion.
  • KFLR: With few outputs, Kronecker Factored Low Rank stores only K × D × N vectors, making exact expected pre-activation blocks computationally viable for small K.The low-rank representation is built from a square-root representation of the output-layer Gauss-Newton matrix.
  • KFRA: For high-dimensional outputs, Kronecker Factored Recursive Approximation passes the expected matrix through the network and initializes the recursion with the exact expected output-layer matrix.This is a nested-expectation approximation rather than per-datapoint sample recursion.

4. Related Work

Prior second-order neural-network methods used curvature products and iterative linear solves, but their computational cost limited competitiveness. The paper’s approach is closest to KFAC while differing in curvature matrix and applicability.

  • Second-order methods: Recent second-order methods seek practical curvature-based optimisation despite the predominance of first-order methods.The related-work discussion focuses on methods using Hessian, Gauss-Newton, or Fisher information.
  • Second-order methods: Full Gauss-Newton matrix-vector products can be computed efficiently, but conjugate-gradient optimisation at every iteration was too slow against well-tuned first-order methods.The method made good progress per iteration but incurred substantial iterative-solve cost.
  • KFAC: KFAC uses a block-diagonal approximation to the Fisher matrix under a probabilistic output-model interpretation.Its loss is defined through a KL-divergence between empirical and network output distributions.
  • KFAC: The Fisher and Gauss-Newton matrices generally differ, becoming equivalent only for exponential-family output models.Even in that special case, the subsequent factorised approximations differ.
  • KFAC: The proposed method does not require a probabilistic model interpretation and is therefore more widely applicable than KFAC.

5. Experiments

The experiments compare KFRA and KFAC with first-order optimisers on autoencoding and classification tasks, assessing optimisation progress, runtime, stability, and approximation quality. Second-order methods generally performed strongly without tuning, though hardware and near-minimum numerical effects affected some comparisons.

  • Experimental setup: The experiments used three grayscale image datasets for deep autoencoding and MNIST odd-even classification, reporting training error to evaluate optimisers.The autoencoder losses were binary cross-entropy on CURVES and MNIST and squared error on FACES.
  • Comparison protocol: ADAM was tuned over learning rate and decay period, whereas second-order methods used default settings and substantially fewer updates because they converged faster.First-order methods ran 40,000 or 160,000 updates; second-order methods ran 5,000 or 20,000.
  • Comparison to first-order methods: Even after tuning ADAM, second-order optimisers outperformed it out-of-the-box across CURVES, FACES, and MNIST.On FACES, second-order methods were faster and more stable, while ADAM diverged at its default learning rate of 10^-3.
  • Comparison of Gauss-Newton approximations: KFRA showed a noticeable optimisation speedup over KFAC per iteration and in wall-clock time, despite equivalent computational cost per update.The authors further compared update alignment with the exact Gauss-Newton update to assess whether update quality explained the advantage.
  • Hardware effects: On CPU, second-order methods were faster than ADAM per iteration and in wall-clock time; on GPU, ADAM was faster by wall-clock time.The final objective was higher for second-order methods in one setting, although all methods reached cross-entropy near 10^-8.
  • Non-Exponential Family Model: In the non-exponential-family mixture model, KFAC performed almost identically to KFLR, suggesting limited benefit from exact low-rank output curvature in this low-dimensional setting.The authors attribute the diminished benefit possibly to noise and the coarse factorised Kronecker approximation.

6. Rank of the Empirical Curvature

The empirical Gauss-Newton curvature is often severely rank-deficient because its rank is bounded by output-layer curvature and data or minibatch size. Damping is therefore important, while limited curvature information can still support relatively large updates.

  • Rank bounds: The Monte Carlo Gauss-Newton matrix rank is bounded by the last-layer Hessian rank multiplied by minibatch size, or by dataset size for the full dataset.Because modern networks have millions of parameters, the exact Gauss-Newton matrix is usually severely under-determined.
  • Curvature interpretation: Rank deficiency implies zero curvature in many parameter directions, paralleling under-determined maximum-likelihood problems with small datasets.
  • Binary classifier: For the binary classifier, the output-layer Hessian has rank one, making the low-rank curvature phenomenon especially pronounced.
  • Role of damping: Damping is important in rank-deficient settings beyond numerical stability, and the available curvature can still enable relatively large updates compared with gradient descent.

7. Conclusion

The paper develops practical block-diagonal Gauss-Newton approximations for feedforward networks and shows that second-order methods can compete with tuned first-order methods without hyperparameter tuning. It also derives structural properties of neural-network curvature and piecewise-linear objectives.

  • Structural result: For piecewise-linear transfer functions with convex loss, the objective has no differentiable local maxima and no differentiable saddle points with respect to one layer's parameters.The authors suggest this may provide partial insight into the practical success of such transfer functions.
  • Method: The method uses a block-diagonal approximation followed by a factorised Kronecker approximation because full Hessian, Fisher, and Gauss-Newton matrices are computationally infeasible.
  • Relation to KFAC: The Fisher and Gauss-Newton matrices are formally different except in the special case of exponential-family models, and KFRA can be marginally better aligned with exact Gauss-Newton updates than KFAC.
  • Empirical conclusion: Second-order methods performed admirably against well-tuned state-of-the-art first-order approaches without requiring hyperparameter tuning.
  • Practical performance: On CPU, second-order approaches converged significantly faster in wall-clock time, while GPU improvements were more marginal.The paper identifies parallel linear-system solving as a route to improving practical utility.

A. Derivation of the Block-Diagonal Hessian Recursion

The derivation relates diagonal blocks of the pre-activation Hessian across feedforward layers through a recursion. Matrix notation uses transfer-function derivatives and supports efficient layerwise computation.

  • Recursion: Diagonal blocks of the pre-activation Hessian are related across layers through the recursion in equation (8).
  • Matrix form: The pre-activation Hessian can be expressed in matrix notation using diagonal matrices defined from the recursive quantities.
  • Transfer-function derivatives: The symbols f′ and f′′ denote the first and second derivatives of the transfer function f.
  • Relation to prior work: The recursion is a special case of a more general Hessian-calculation recursion.

B. Implementation Details

The implementation uses positive semi-definite curvature approximations, damping, blockwise solves, and adaptive step-size controls to make Gauss-Newton updates practical. The method also uses Kronecker structure and recursive computations to reduce cost, while experiments and analysis characterize its effectiveness and scope.

  • Curvature approximation: Positive semi-definite curvature matrices avoid the indefinite Hessian problem; experiments use either the full Gauss-Newton matrix or a block-diagonal approximation.The full matrix is denoted ¯G, while the block-diagonal approximation is denoted eG.
  • Damping and regularisation: Damping introduces separate parameters for the full and approximate Gauss-Newton matrices, while L2 regularisation adds a diagonal term to both.The resulting curvature matrices are ¯C = ¯G + (τ + η)I and eC = eG + (γ + η)I.
  • Blockwise update: Because eC is block diagonal with one block per layer, the update decomposes into L independent linear systems.This structure enables layerwise inversion rather than solving one system over all network parameters.
  • Kronecker factorisation: Kronecker-factored blocks are approximated using two linear systems per layer instead of eigen decomposition and four matrix-matrix multiplications.The approximation is motivated by the Kronecker identity and can also be viewed as a form of damping for Kronecker-factored matrices.
  • Step-size control: The approximate update can differ substantially from the full Gauss-Newton update, so an appropriate step size is important, especially with mini-batch curvature estimates.The step size is selected using a quadratic approximation induced by the full Gauss-Newton matrix.
  • Step-size control: A Levenberg-Marquardt heuristic adapts τ from the reduction ratio ρ, decreasing τ when ρ > 0.75 and increasing it when ρ < 0.75.The ratio measures how well the quadratic approximation matches the true function.
  • Empirical scope: The method is competitive without tuning on three standard benchmarks, while fixed batch size 1000 leaves batch-size adaptation outside the study’s focus.The paper also notes that Monte Carlo curvature can be insufficient for some small-output, small-batch settings.

D. The Rank of the Monte Carlo Gauss-Newton

The rank analysis bounds Monte Carlo Gauss-Newton estimates through the output Hessian and sample count. For scalar-output binary classification, this limits curvature information and can reduce competitiveness against tuned first-order methods.

  • Rank bounds: The rank of a sample Gauss-Newton matrix is bounded by the rank of the output Hessian.The bound follows from the sample Gauss-Newton construction.
  • Rank bounds: The analysis does not bound the rank of the true Gauss-Newton matrix, which is an expectation of sample matrices.A bound applies instead to practical Monte Carlo estimates formed from N samples.
  • Monte Carlo estimate: Under the Fisher–Gauss-Newton equivalence condition, the resulting Monte Carlo estimate has rank at most rank(HL)N.The bound uses the sub-additivity of the rank operator.
  • Binary classification: For binary classification with scalar output, both Gauss-Newton and Fisher mini-batch curvature have rank bounded by the mini-batch size N.Here the final-layer output Hessian has rank 1.
  • Practical implication: In this setting, Monte Carlo curvature may be insufficient for competitiveness against well-tuned first-order methods, although approximate Gauss-Newton methods can still perform better initially.The paper identifies momentum and alternative rescaling as directions for further research.

E. Absence of Smooth Local Maxima for Piecewise Linear Transfer Functions

For feedforward networks with piecewise linear transfer functions and a positive-semidefinite output Hessian, the objective has no differentiable strict local maxima. Fixing all layers except one also makes the objective locally convex with respect to that layer wherever differentiable.

  • The lemma establishes that all diagonal Hessian blocks are positive semi-definite when transfer functions are piecewise linear and the output Hessian is positive semi-definite.The proof recursively propagates positive semidefiniteness from the output-layer Hessian to pre-activation matrices, then analyzes the parameter blocks.
  • Fixing all weights except one layer makes the error function locally convex with respect to that layer wherever the transfer functions are differentiable.Thus, within a layer, the objective has no differentiable local maxima or saddle points under the stated assumptions.
  • The overall objective has no differentiable strict local maxima with respect to the network parameters.A strict local maximum would require all Hessian eigenvalues to be negative, whereas the non-negative trace implied by positive-semidefinite diagonal blocks rules this out.
  • Any strict local maxima must therefore lie at non-differentiable boundary points of the nonlinear transfer functions.The result excludes smooth maxima but does not exclude maxima at activation boundaries.

F.2. Comparison of the Alignment of the Approximate Updates with the Gauss-Newton Update

The experiments compare KFAC and KFRA updates with regularised block-diagonal and full Gauss-Newton updates using cosine similarity across layers and training iterations. KFRA generally aligns better with the Gauss-Newton updates than KFAC, while block-diagonal and full Gauss-Newton alignment decays late on FACES but not on the other datasets.

  • Cosine similarity measures approximate per-layer updates against block-diagonal GN updates and full updates against the full GN matrix, with 1.0 optimal.The plots use iterations on the x-axis, place layers one to four in the top row and five to eight in the bottom row, and follow the KFRA* parameter trajectory.
  • KFRA updates have better alignment with the exact GN update than KFAC throughout optimisation across CURVES, FACES and MNIST.The comparison uses batch size 1000 because results for batch sizes 250, 500 and 1000 did not differ significantly.
  • Alignment between block-diagonal and full GN updates decays toward the end of training on FACES, but this pattern is not observed on CURVES or MNIST.The authors attribute the FACES decay most likely to badly conditioned conjugate-gradient solves.
  • KFRA updates are better aligned with both the block-diagonal and full GN matrices than KFAC updates.The paper relates this alignment advantage to KFRA generally outperforming KFAC, while noting that the methods differ in their approximations to the expected GN matrix for exponential-family models.
Loading 1706.03662v2…