Introduction
In deep learning, standard Gradient Descent (GD) often struggles with "flat" regions of the loss surface or poorly scaled parameters, leading to slow convergence. Natural Gradient Descent (NGD), originally proposed by Shun-ichi Amari, solves this by treating the parameter space as a curved Riemannian manifold rather than a flat Euclidean one. It uses the Fisher Information Matrix (FIM) to adjust the gradient, effectively taking the "shortest path" in terms of probability distributions.
However, NGD has historically faced a massive computational bottleneck: it requires calculating and inverting the FIM. For a network with $n$ inputs, the FIM is a large matrix, and inverting it typically costs $O(n^3)$ or $O(n^2)$ at best. This makes NGD prohibitively expensive for high-dimensional data. This paper tackles the challenge of making NGD computationally efficient enough for practical use in multi-layer perceptrons (MLPs), reducing the complexity from $O(n^2)$ to $O(n)$.
Proposed Methodology
The authors propose a fast algorithm for computing the natural gradient by analyzing the mathematical structure of the FIM for a stochastic MLP.
- Stochastic Model: They define the MLP as a stochastic system where the output includes Gaussian noise. This allows them to define the FIM as a metric tensor of the parameter space.
- Matrix Partitioning: They prove that the FIM can be partitioned into specific blocks ($C_1, C_2, C_3$). They show that these blocks are linear combinations of a small set of vectors related to the input weights.
- Complexity Reduction: By exploiting this "low-rank-plus-diagonal" style structure, they demonstrate that the inverse of the FIM can be represented and applied in $O(n)$ time and space, rather than $O(n^2)$.
- Learning Rule: They implement an online learning version of NGD that updates weights using this efficiently computed inverse FIM.
Experimental Setup
To provide a controlled environment for theoretical verification, the paper relies on synthetic simulations rather than real-world benchmarks:
- Single-layer Perceptron: A teacher-student setup with 7-dimensional Gaussian inputs.
- Multi-layer Perceptron (Committee Machine): A network with 2-dimensional inputs and 2 hidden neurons.
- Noise Levels: They tested the algorithms under varying levels of additive Gaussian noise ($\sigma = 0.2, 0.4, 1.0$) to evaluate robustness.
Key Results and Insights
The Geometry of Learning
The core insight of the paper is that the FIM isn't just a random matrix; it encodes the geometry of how the network's output distribution changes. Because the hidden neurons share the same input vector, the FIM has a highly redundant structure that can be mathematically compressed.
Computational Speedup
The proposed algorithm successfully reduces the storage requirement from $O(n^2)$ to $O(n)$ and the computation of the natural gradient to $O(n)$, making it a viable alternative to standard GD for specific architectures.
Hitting the Cramer-Rao Lower Bound (CRLB)
In simulations, NGD consistently reached the Cramer-Rao Lower Bound (CRLB)—the theoretical maximum accuracy possible for any unbiased estimator—across all noise levels. Standard GD, on the other hand, only reached this bound under very low noise conditions and often plateaued at sub-optimal error rates.
Hyperparameter Robustness
Standard GD is highly sensitive to the "learning rate schedule." If hyperparameters are poorly chosen, GD fails to converge to the optimal solution. NGD is "Fisher efficient," meaning it naturally gravitates toward the best possible statistical estimate regardless of the noise level. NGD performed consistently across a wide range of learning rates, whereas GD's performance deteriorated rapidly if the learning rate was not perfectly tuned.
Limitations and Future Work
- Architectural Constraints: The $O(n)$ complexity trick relies on the input dimension $n$ being much larger than the number of hidden neurons $m$. If the number of hidden neurons is very large, the complexity benefits may diminish.
- Specific Activations: The analytic expressions for the FIM blocks were derived using specific activation functions (like the error function
erf). Extending this to modern activations like ReLU would require new mathematical derivations. - Scale: While $O(n)$ is a significant theoretical improvement, the paper demonstrates this on relatively small networks. Modern deep networks with millions of parameters require further approximations, paving the way for future methods like Kronecker-factored approximate curvature (K-FAC) which evolved from these foundational ideas.
Summary updated