PaperlayerView exact revision on arXiv

Source-linked AI summary

New insights and perspectives on the natural gradient method

James Martens

arXiv:1412.1193v11cs.LGstat.ML

TL;DR

The paper addresses how to understand and robustly implement natural gradient descent, whose Fisher matrix is costly for large models. It analyzes natural gradient as a second-order method, establishes links to the GGN, and derives convergence and practical optimization implications.

  • Problem

    Natural gradient descent can require impractical Fisher-matrix computation for models with very many parameters, motivating analysis of its curvature interpretation and approximations.

  • Method

    The paper analyzes stochastic second-order methods on convex quadratics, relates the Fisher to Hessian approximations including the GGN, and examines empirical Fisher and parameterization invariance.

  • Results

    The Fisher is often equivalent to the GGN, while the convergence analysis provides a more precise expression for stochastic second-order convergence speed than existing results.

  • Takeaways & Limitations

    Viewing natural gradient as a GGN-based second-order method motivates trust regions, damping, Tikhonov regularization, and Levenberg-Marquardt heuristics for robust performance.

  • Takeaways & Limitations

    Some asymptotic conclusions require mild hypotheses such as restricting parameters to a bounded region, especially for heavy-tailed parameter distributions.

Abstract

from arXiv · show

Natural gradient descent is an optimization method traditionally motivated from the perspective of information geometry, and works well for many applications as an alternative to stochastic gradient descent. In this paper we critically analyze this method and its properties, and show how it can be viewed as a type of 2nd-order optimization method, with the Fisher information matrix acting as a substitute for the Hessian. In many important cases, the Fisher information matrix is shown to be equivalent to the Generalized Gauss-Newton matrix, which both approximates the Hessian, but also has certain properties that favor its use over the Hessian. This perspective turns out to have significant implications for the design of a practical and robust natural gradient optimizer, as it motivates the use of techniques like trust regions and Tikhonov regularization. Additionally, we make a series of contributions to the understanding of natural gradient and 2nd-order methods, including: a thorough analysis of the convergence speed of stochastic natural gradient descent (and more general stochastic 2nd-order methods) as applied to convex quadratics, a critical examination of the oft-used "empirical" approximation of the Fisher matrix, and an analysis of the (approximate) parameterization invariance property possessed by natural gradient methods (which we show also holds for certain other curvature, but notably not the Hessian).

1. Introduction and Overview

The paper reframes natural gradient descent as a practical second-order method using the Fisher as a Hessian alternative, while analyzing its convergence, empirical approximations, and parameterization properties.

  • Motivation: Natural gradient descent replaces the standard gradient with the gradient multiplied by the inverse Fisher information matrix.It is applicable to probabilistic models and has been used in blind source separation, reinforcement learning, and neural network training.
  • Second-order perspective: The paper interprets natural gradient descent as a second-order method whose local quadratic model can be more detailed and less conservative than gradient descent’s implicit model.This perspective motivates trust regions, damping, and Tikhonov regularization for robust optimization.
  • Curvature matrices: The Fisher can approximate the Hessian as an expected model Hessian and is often equivalent to the Generalized Gauss-Newton matrix.The GGN is a Hessian approximation used in practical neural-network second-order methods.
  • Practical and theoretical caveats: The empirical Fisher is easier to compute but is less useful as a Fisher approximation or second-order curvature matrix and breaks some natural-gradient theory.It nevertheless preserves approximate parameterization invariance.
  • Convergence analysis: Stochastic second-order methods can have more favorable dependence on the starting point than averaged stochastic gradient descent, despite matching its asymptotic convergence speed on convex quadratics.The analysis provides a more precise convergence expression that accounts for the starting point.
  • Open questions: The convergence theory does not explain why GGN/Fisher optimization outperforms Hessian-based second-order schemes for neural-network training.The paper identifies this explanation as an open question for future work.

2. Neural Networks

Feed-forward neural networks consist of layers that transform inputs through affine maps followed by nonlinear activation functions, with parameters given by weights and biases.

  • Architecture: A feed-forward neural network is organized as a sequence of ℓ layers, each receiving inputs from the preceding layer.The input layer is not counted among the ℓ computational layers.
  • Layer computation: Each layer computes an affine transformation of the previous layer’s activities followed by a scalar nonlinear activation function.Activation functions are often applied coordinate-wise.
  • Notation: The network parameters comprise weight matrices W_1,...,W_ℓ and biases b_1,...,b_ℓ, while the input vector is denoted x.The network output is f(x, θ), determined by these parameters.
  • Scope: Most subsequent results apply to any differentiable function f(x, θ), not only feed-forward neural networks.The stated generality includes differentiability in both x and θ.

3. Supervised Learning Framework

Supervised learning seeks parameters that make network predictions match target outputs on training examples, as measured by a loss function.

  • Objective: The supervised-learning objective is to find parameters θ whose predictions match target outputs for each training input.Training data consist of input-target pairs (x, y).
  • Loss function: A loss function L(y, z) measures disagreement between a target y and a prediction z.The objective minimizes this disagreement over the training set.
  • Prediction forms: Predictions may be point estimates evaluated with losses such as squared error or parameters of predictive distributions evaluated by negative log probability.The framework therefore covers both regression-style and probabilistic predictions.

4. KL Divergence Objectives

The paper formulates supervised learning through conditional target and learned distributions, with KL-divergence objectives that reduce to empirical maximum-likelihood training when only observed output samples are available.

  • Connections to natural gradient: The paper notes that different formulations of these objectives correspond to subtly different formulations of the Fisher information matrix and natural gradient.These distinctions affect the associated theoretical properties.
  • KL objective: The idealized objective minimizes KL divergence from the target joint distribution to the learned joint distribution, equivalently the expected conditional KL divergence over Q_x.Only the conditional distribution of y given x is learned.
  • Empirical inputs: When the input distribution is unavailable or difficult to integrate, it can be replaced by an empirical distribution formed from samples.This yields an empirical objective over the observed inputs.
  • Maximum likelihood: When only one target sample y is available for each input x, replacing the conditional target distribution with empirical samples produces an objective proportional to standard maximum-likelihood training.The proportionality hides an additive constant independent of θ.
  • Conditional distributions: The learned conditional distribution is formed by composing the deterministic prediction f(x, θ) with an output conditional distribution R_y|z.The associated density is r(y|z).
  • Loss representation: A loss can often be represented by an output distribution when exp(−L(y, z)) has the same finite integral for every z.The corresponding density is defined proportionally to exp(−L(y, z)).

5. Various Definitions of the Natural Gradient and the Fisher Information Matrix

The paper defines the Fisher information matrix and natural gradient, then relates the Fisher to expected Hessians and the empirical data distribution. These relationships establish the Fisher as an approximation to the Hessian.

  • The Fisher information matrix is defined from gradients of the model log-likelihood and is used to form the natural gradient.The natural gradient is defined using the Fisher inverse and the objective gradient.
  • The Fisher can be expressed using the conditional model distribution and the input distribution, with the latter often replaced by its empirical version in practice.Analytic integration over the input distribution may be difficult for multilayer neural networks.
  • When the loss is negative log-likelihood, the Fisher is the expected Hessian of the loss under the model distribution over predicted outputs.
  • The Hessian uses a different distribution from the Fisher, so the two matrices can be viewed as approximations of each other.

6. Geometric Interpretation

The geometric interpretation treats the natural gradient as steepest descent under a distribution-based metric rather than the parameter space’s Euclidean geometry. Locally, the Fisher connects parameter changes to KL divergence and yields parameterization-invariant directions in distribution space.

  • The ordinary negative gradient is steepest descent under the Euclidean norm in parameter space.
  • The natural gradient adapts steepest descent to a metric intrinsic to the modeled distributions rather than tied to a parameterization.
  • The KL divergence is locally approximated by a quadratic form defined by the Fisher information matrix.
  • The negative natural gradient is the steepest descent direction in distribution space when local distance is measured by KL divergence.
  • The natural-gradient direction in distribution space is invariant to parameterization, unlike the ordinary gradient in general.

7. 2nd-order Optimization

Second-order methods optimize local quadratic models of the objective, with the curvature matrix controlling their updates. The section explains why Newton methods can be fast but unreliable or impractical for neural networks, motivating approximations and safeguards.

  • Second-order optimization updates parameters by minimizing a local quadratic model around the current iterate.
  • Gradient descent fits this framework by using a scaled identity curvature matrix, which is conservative but can move slowly in low-curvature directions.
  • Newton’s method uses the Hessian to obtain an accurate local curvature model and rapidly explore low-curvature directions.
  • Indefinite Hessians can make Newton quadratic models unbounded below and cause large updates that increase the objective.
  • High-dimensional neural-network parameter spaces make explicit calculation, storage, and inversion of the n^2-entry curvature matrix impractical.Approximate Newton methods address this with low-rank or diagonal approximations, or approximate minimization of the quadratic model.
  • A curvature model that takes a longer view of the objective could optimize faster than the locally optimal Hessian-based Taylor model.The paper presents this as a possible explanation for the Fisher’s observed superiority in neural-network optimization.

8. The Generalized Gauss-Newton Matrix

The Generalized Gauss-Newton matrix is a Hessian alternative obtained by retaining loss curvature while dropping network-function curvature. It is positive semidefinite, often aligns with the Hessian or Fisher, and supports more robust curvature estimation and optimization.

  • The GGN is introduced as an alternative to the Hessian whose connection to natural-gradient methods follows from its correspondence with the Fisher.
  • For convex losses, the GGN is positive semidefinite because it is constructed from the loss Hessian with respect to network outputs.
  • The GGN is obtained by dropping the network-function curvature term from the Hessian, equivalently by locally linearizing the network function.
  • The GGN equals the Hessian when predictions are optimal, and its optimizer behavior approaches Newton’s method near such an optimum.
  • GGN-based updates minimize a local quadratic model, but practical methods usually approximate this minimization and access the matrix through matrix-vector products.
  • Unlike the Hessian, the GGN avoids negative-curvature directions, though it does not capture all positive curvature and its omitted network curvature may be unstable.
  • Because individual GGN contributions are positive semidefinite, they cannot cancel, making the GGN more robustly estimable from data subsets than the Hessian.
  • For squared-error losses, the GGN has a nonnegative local quadratic approximation that vanishes on the loss-zero manifold, properties the Hessian need not share.

9. Computational Aspects of the Natural Gradient and Connections to the Generalized Gauss-Newton Matrix

The Fisher can be computed through Jacobian-based matrix-vector products and, under important conditions, is equivalent to the Generalized Gauss-Newton matrix. This equivalence extends curvature-based optimization to losses and parameterizations where the conventional GGN may be undefined.

  • Connections to curvature: For suitable objectives, the Fisher is an expected Hessian under the model’s predictive distribution, whereas the GGN uses the loss Hessian as its inner matrix.These provide two distinct ways to view the Fisher as a Hessian approximation.
  • Computational aspects: Fisher matrix-vector products can be computed by a linearized forward pass, multiplication by the predictive Fisher, and standard backpropagation.The predictive Fisher must be sufficiently simple for efficient multiplication.
  • Qualified equivalence: The Fisher and GGN are identical when the predictive Fisher equals the loss Hessian; this holds for exponential-family models using natural parameters.The equivalence also applies to common squared-error and cross-entropy constructions under suitable definitions of the loss and network output.
  • Model decomposition: The GGN’s definition depends on where the network computation is divided between f and L, while the Fisher is invariant to that choice.Including softmax in the loss can make the GGN equivalent to the Fisher for exponential-family models with natural parameters.
  • Qualified equivalence: The equivalence can generalize the GGN by defining the loss as a negative log density and taking the Fisher of the associated predictive distribution.This approach is useful when the original loss is not convex in its output variables and therefore does not define a valid GGN.

10. Constructing Practical Natural Gradient Methods, and the Critical Role of Damping

Finite natural-gradient steps can deviate from the intended distribution-space direction because updates occur in the original parameter space. Viewing the method as second-order optimization motivates damping and trust-region techniques for robust practical updates.

  • Step-size selection: Step-size schedules are difficult to choose: heuristic adaptive schemes exist, while α_k = ρ/k has stochastic convergence guarantees but may work poorly in practice.The paper therefore distinguishes theoretical convergence prescriptions from practical effectiveness.
  • Practical breakdown: Finite steps along a straight line in parameter space can veer far from the target direction in distribution space.The discrepancy arises because the natural gradient is locally meaningful, while the parameter-space path need not remain aligned over non-negligible distances.
  • Second-order interpretation: The natural gradient can be interpreted as the optimal update for a Fisher-based local quadratic approximation when the Fisher equals the GGN.With scaling factor α = 1, the update is −G(θ_k)^−1∇h(θ_k).
  • Damping: Damping and trust-region methods constrain or penalize updates when the local quadratic approximation becomes inaccurate over long distances.Tikhonov regularization is one example of the update-damping techniques motivated by the second-order view.
  • Damping: Tikhonov-damped GGN updates in Hessian-free optimization can use step-size 1 and make more progress than undamped updates.The undamped alternative requires a carefully chosen step-size to avoid poor behavior.

11. The Empirical Fisher

The empirical Fisher is computationally convenient and often lower-rank, but it is not generally the Fisher or GGN and can have inferior curvature and convergence behavior. The exact Fisher retains a closer second-order interpretation.

  • Definition and convenience: The empirical Fisher replaces the model-distribution expectation with an expectation over the target distribution or its empirical surrogate.This yields a simple matrix that is often used in practical natural-gradient methods.
  • Definition and convenience: Unlike the true Fisher, the empirical Fisher is not generally equivalent to either the Fisher or the Gauss-Newton matrix.It is therefore inaccurate to use those names interchangeably for the empirical approximation.
  • Practical advantages: The empirical Fisher is positive semidefinite, inexpensive when gradients are already available, and applicable even without an obvious probabilistic model.Its lower rank can also simplify diagonal or block computations.
  • Curvature quality: The exact Fisher can approximate the Hessian and equal the GGN in important cases, whereas the empirical Fisher lacks this property in general.This second-order interpretation is a principal reason to prefer the true Fisher when feasible.
  • Convergence behavior: For h(θ) = 1/2θ^2, the empirical Fisher is θ^2 while the true Fisher is 1, illustrating a scale mismatch in the empirical curvature.The example uses f(x, θ) = θ, a unit-variance normal predictive distribution, and a single training case.
  • Convergence behavior: Using the exact Fisher in the quadratic example yields linear convergence with rate |1 − α| for any fixed 0 < α < 2, unlike the empirical-Fisher iteration’s slower or conditional convergence.The linear-convergence example is noise-free, and such behavior is generally unavailable in realistic stochastic settings.
  • Diagonal methods: How the empirical Fisher is estimated affects convergence, with accumulated past gradients potentially avoiding the current-iterate failure mode.The paper identifies the relationship between such methods and classical stochastic second-order methods as an open research direction.

12. A Critical Analysis of Parameterization Invariance

Natural-gradient paths are invariant under smooth invertible reparameterizations only in the infinitesimal-step idealization. Finite-step methods are approximately invariant, with errors governed by step size and reparameterization curvature, and this property extends to some curvature matrices but not generally the Hessian.

  • Scope of invariance: The idealized infinitesimal-step natural-gradient path is invariant to smooth invertible reparameterizations of the model.The practical finite-step update need not preserve this invariance exactly.
  • Finite-step behavior: Finite-step natural-gradient methods are only approximately invariant, with the approximation depending on the reparameterization’s curvature and the step size α.The per-iteration error is small when the step is sufficiently small and the reparameterization is sufficiently smooth.
  • Error bounds: The update equivalence error is zero for affine reparameterizations and scales as α^2 for general smooth reparameterizations.As α approaches zero with proportionally more steps, the resulting sequences converge to equivalent smooth paths.
  • Other curvature matrices: Certain curvature matrices satisfying a parameterization-transformation condition include the GGN, Fisher, and empirical Fisher.This establishes that approximate path invariance is not unique to the natural gradient.
  • The Hessian: The Hessian generally fails the sufficient transformation condition, except in special cases such as affine reparameterizations or zero per-example gradients.Thus Hessian-based updates do not generally share the same parameterization-invariance property.

13. A New Interpretation of the Natural Gradient

The natural gradient can be interpreted as minimizing a local quadratic model whose curvature is the Fisher, with the model measuring Fisher-metric discrepancies between predicted and optimal output changes. This interpretation also yields an improvement bound and remains meaningful with singular Fisher matrices under suitable conditions.

  • The negative natural gradient minimizes a local quadratic approximation whose curvature matrix is the Fisher.
  • The quadratic model compares output changes induced by parameter updates with optimal output-space changes under the Fisher metric.
  • The model’s non-negative squared-error terms provide an efficiently computable bound on the largest improvement predicted by the quadratic approximation.
  • When F_R = H_L, the bound’s reference quantity is the optimal improvement from independently changing each output variable z.
  • The natural gradient remains definable when F^-1 does not exist by selecting the minimum-norm minimizer of the bounded-below quadratic model, potentially using F’s pseudoinverse.

14. Asymptotic Convergence Speed

The paper develops exact asymptotic convergence analyses for stochastic second-order methods on convex quadratics while identifying important conditions behind Fisher efficiency. The analysis separates noise- and initialization-dependent behavior, showing that curvature mainly improves finite-iteration effects rather than the dominant asymptotic noise term.

  • Fisher efficiency requires convergence to the global optimum, full-distribution Fisher computation, and realizability, with minibatch Fisher estimates likely invalidating the stated efficiency result.
  • The realizability condition can fail when the model cannot represent the training distribution or when a finite dataset yields a delta distribution with an undefined Fisher.
  • The paper derives exact asymptotic expressions for E[h(θ_k)] in the quadratic setting and analyzes Polyak averaging.
  • With Polyak averaging, nontrivial curvature does not improve the dominant noise-dependent term, while learning-rate decay can improve its constant but not the overall 1/k rate.
  • For convex quadratics, the mean iterate evolves independently of gradient-noise distribution, while noise affects only variance around that mean.
  • The expected objective gap decomposes into independent contributions from mean-iterate progress and iterate variance.

15. Conclusions and Open Questions

The paper frames natural gradient descent as a GGN-based second-order method and recommends standard regularization practices for robust optimization. It also identifies unresolved theoretical questions about GGN behavior, convergence, and comparisons with the Hessian and averaged SGD.

  • Conclusions: The paper advocates viewing natural gradient descent as a GGN-based 2nd-order method when the Fisher and GGN are equivalent.This interpretation supplies intuition for large-step behavior and connects natural gradient to established second-order optimization practice.
  • Conclusions: This perspective motivates damping, regularization, and trust-region techniques to improve practical robustness.The paper links these techniques to the limited accuracy of local quadratic approximations over long distances.
  • Open Questions: Global convergence for GGN-based second-order optimization remains insufficiently understood, even under convexity and squared loss.Existing local convergence bounds also do not fully characterize local behavior.
  • Open Questions: Current local convergence analyses cannot explain the empirical superiority of the GGN over the Hessian in neural-network training.The analyses assume constant curvature, a setting in which the Hessian is favored by the bounds.
  • Open Questions: The report leaves open whether the observed GGN advantage over the Hessian can be rigorously justified with appropriate damping or trust regions.It also asks when the Fisher and GGN differ materially and whether either is clearly preferable.
  • Open Questions: The practical importance of the pre-asymptotic advantage of stochastic second-order methods over SGD with Polyak averaging remains unresolved.The paper asks whether this advantage can be characterized using accessible properties of the target objective.

Appendix D. Some Self-contained Technical Results

The appendix develops technical results for stochastic second-order methods and parameterization-related update paths. It establishes operator properties used in convergence analysis and bounds the discrepancy between discrete updates under reparameterization.

  • Technical Results: The appendix derives trace and matrix-operator lemmas used to analyze stochastic second-order iterations on quadratic objectives.These results include invertibility, eigenvalue, and positive-semidefiniteness properties of operators built from the iteration matrices.
  • Operator Properties: For PSD inputs, the operator Φ(X)=X−DXD^⊤ is invertible and its inverse preserves positive semidefiniteness.The proof uses eigenvalue bounds for D and a convergent series of PSD matrices.
  • Convergence Bounds: The appendix bounds products and sums arising from annealed step sizes using harmonic-number inequalities and exponential estimates.These bounds support the non-asymptotic terms in the convergence analysis.
  • Parameterization: Under the stated update regularity conditions, reparameterized discrete optimizer paths converge to the same continuous path as α approaches zero.The analysis permits sequence lengths proportional to 1/α to obtain paths of finite non-zero length.
Loading 1412.1193v11…