Kronecker Factored Curvature for Second Order Deep Learning

368 concepts231 papers1 proposal

First-order optimization algorithms like SGD and Adam navigate the loss landscape using only local slope information (the gradient). While computationally cheap, they can struggle in steep valleys or flat plateaus where the geometry is poorly conditioned. Second-order optimization methods, such as Natural Gradient Descent, resolve this by using curvature information—typically stored in the Fisher Information Matrix (FIM) or the Hessian—to adaptively rescale updates, allowing the optimizer to take a more direct path toward the minimum.

However, for a model with $P$ parameters, the FIM is a massive $P \times P$ matrix. Storing it requires $O(P^2)$ memory, and inverting it takes $O(P^3)$ time. For modern deep networks with millions or billions of parameters, calculating or inverting this matrix exactly is completely intractable. Kronecker-factored curvature approximation solves this bottleneck by breaking this massive matrix down into small, easily invertible pieces.

The Kronecker Factorization Trick

To make second-order optimization practical, James Martens et al. introduced Kronecker-factored Approximate Curvature (K-FAC). The core insight relies on two levels of structural simplification.

First, K-FAC ignores cross-layer parameter interactions, reducing the FIM to a block-diagonal matrix where each block corresponds to a single layer.

Second, it exploits the mathematical structure of how gradients are computed within a layer. For a standard fully-connected layer, the gradient of the loss with respect to the weight matrix $W$ is the outer product of the layer's input activations $a$ and the backpropagated loss gradients $g$:

$$\nabla_W L = g a^T$$

When we vectorize this gradient to compute the FIM block, the outer product of the vectorized gradient can be rewritten using the Kronecker product ($\otimes$) identity:

$$\text{vec}(\nabla_W L)\text{vec}(\nabla_W L)^T = \text{vec}(g a^T)\text{vec}(g a^T)^T = (a a^T) \otimes (g g^T)$$

The true FIM block is the expectation of this quantity over the data distribution: $E[(a a^T) \otimes (g g^T)]$. K-FAC introduces a crucial approximation: it factors the expectation of the Kronecker product into the Kronecker product of the expectations:

$$E[(a a^T) \otimes (g g^T)] \approx E[a a^T] \otimes E[g g^T]$$

This assumption—that the covariance of the activations and the covariance of the backpropagated gradients are statistically independent—drastically simplifies the dimensionality of the problem.

Why It Works: The Magic of Inversion

Why does this factorization solve the computational bottleneck? The power lies in a fundamental algebraic property of the Kronecker product: the inverse of a Kronecker product is the Kronecker product of the individual inverses:

$$(A \otimes B)^{-1} = A^{-1} \otimes B^{-1}$$

If a layer has $A$ inputs and $B$ outputs, its full FIM block is an $AB \times AB$ matrix, requiring $O(A^3 B^3)$ time to invert. By factorizing it into $E[a a^T]$ (size $A \times A$) and $E[g g^T]$ (size $B \times B$), we only need to invert two much smaller matrices independently.

The inversion cost plummets from $O(A^3 B^3)$ to $O(A^3 + B^3)$. This reduction transforms an intractable problem into a series of small, efficient matrix operations that are only slightly more expensive than standard first-order gradient updates.

Refining and Scaling the Approximation

While the basic K-FAC framework provides a massive speedup, researchers have continuously refined the approximation to balance accuracy and efficiency across different architectures:

  • Eigenbasis and Trace Corrections: Thomas George proposed EKFAC, showing that transforming gradient components into a Kronecker-factored eigenbasis decorrelates them, allowing a simple diagonal correction to capture complex curvature information more accurately. To further stabilize updates, Xiao-Lei Liu et al. introduced trace-restricted constraints (TEKFAC) to bound approximation errors.
  • Low-Rank and Diagonal Variants: For massive-scale architectures where even storing small matrices is challenging, methods like Eva (Lin Zhang et al.) and LNGD (Xiaolei Liu et al.) utilize rank-one or diagonal-Kronecker factorizations to reduce memory overhead to a sublinear scale relative to the total number of model parameters.
  • Beyond Fully Connected Layers: Roger B. Grosse et al. extended this structural modeling to convolutional layers (KFC) by treating backpropagated derivatives as structured probabilistic models, enabling efficient second-order optimization for computer vision tasks.

Expanding Beyond Optimization

The ability to efficiently estimate and invert curvature matrices has unlocked applications far beyond training acceleration:

Uncertainty Estimation

Turning deterministic networks into Bayesian ones requires computing the posterior distribution of the weights, often via a Laplace approximation. Erik A. Daxberger et al. and Hippolyt Ritter et al. demonstrated that Kronecker-factored representations capture essential intra-layer weight dependencies, providing robust uncertainty quantification and mitigating catastrophic forgetting without the quadratic memory explosion of full second-order methods.

Model Selection and Compression

Alexander Immer et al. leveraged these structured approximations to efficiently estimate marginal likelihood for deep learning model selection. Furthermore, the framework has been adapted to compress large models; Markus Nagel developed the LLM Surgeon, utilizing Kronecker-factored curvature to account for weight correlations during structured and unstructured pruning of large language models, making high-fidelity model compression computationally viable.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 239 papers
  2. Version 1 · 2026-10-04 · 345 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_kronecker_factored_curvature_approximati_a50872ce,
  title = {Kronecker-factored curvature approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/kronecker-factored-curvature-approximation/rdr_a50872cef632437aa307aaddf116988c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_kronecker_factored_curvature_approximati_a50872ce_v2,
  title = {Kronecker-factored curvature approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/kronecker-factored-curvature-approximation/rdr_a50872cef632437aa307aaddf116988c/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake