Complexity Issues in Natural Gradient Descent Method for Training Multilayer Perceptrons

By Howard H. Yang, Shun-ichi Amari. 1998

The natural gradient descent method is applied to train an n-m-1 multilayer perceptron. Based on an efficient scheme to represent the Fisher information matrix for an n-m-1 stochastic multilayer perceptron, a new algorithm is proposed to calculate the natural gradient without inverting the Fisher information matrix explicitly. When the input dimension n is much larger than the number of hidden neurons m, the time complexity of computing the natural gradient is O(n).

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs) (2015, methodology): “The recently introduced Hessian-Free Optimization technique (Martens, 2010) and the Krylov Subspace Descent methods (Vinyals & Povey, 2012) use an extended Gauss-Newton approximation of the Hessian, therefore they can be interpreted as versions of natural gradient descent (Pascanu & Bengio, 2014).”
Parallel training of Deep Neural Networks with Natural Gradient and Parameter Averaging (2014, methodology): “[5] Howard Hua Yang and Shun-ichi Amari, “Complexity issues in natural gradient descent method for training multilayer perceptrons,” Neural Computation, vol.”
On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice (2020, background): “Gradient-based algorithms have a time complexity of O(n) for optimizing k hyper-parameters [86].”
Natural conjugate gradient training of multilayer perceptrons (2006, background): “There are ways in the on–line setting to alleviate this [3,14] and its impact is much smaller if batch natural gradient is considered.”
Fast Curvature Matrix-Vector Products for Second-Order Gradient Descent (2002, methodology): “This is exploited by Yang and Amari (1998) to compute efeciently the natural gradient for multilayer perceptrons with a single output and one hidden layer: assuming independently and identically distributed (i.i.d.) gaussian input, they explicitly derive the form of the Fisher information matrix a”
Topmoumoute Online Natural Gradient Algorithm (2007, unknown): “[10] offers two approaches to exploit this.”
Local minima and plateaus in hierarchical structures of multilayer perceptrons (2000, methodology): “If this is true, we can e ectively avoid them by the method of natural gradient ([6],[12],[13],[14]), because it enlarges the gradient of the repulsive direction from by multiplying the inverse of the almost singular Fisher information matrix.”
Adaptive Method of Realizing Natural Gradient Learning for Multilayer Perceptrons (2000, background): “Itwas alsosuggestedthatnaturalgradientlearningismucheasiertogetridof plateausthanordinarygradientlearning(Amari,1998;Yang&Amari,1998).”
Exact natural gradient in deep linear networks and its application to the nonlinear case (2018, background): “By deﬁnition, the natural gradient is the product of the inverse of the P × P Fisher information matrix F with the P -dimensional gradient vector, where P is the number of network parameters (often in the millions) [Yang and Amari, 1998; Amari et al., 2000; Park et al., 2000].”