Fast Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron

Abstract

We introduce a fast algorithm for entry-wise evaluation of the Gauss-Newton Hessian (GNH) matrix for the fully-connected feed-forward neural network. The algorithm has a precomputation step and a sampling step. While it generally requires $O(Nn)$ work to compute an entry (and the entire column) in the GNH matrix for a neural network with $N$ parameters and $n$ data points, our fast sampling algorithm reduces the cost to $O(n+d/{\epsilon }^2)$ work, where $d$ is the output dimension of the network and $\epsilon$ is a prescribed accuracy (independent of $N$). One application of our algorithm is constructing the hierarchical-matrix (H-matrix) approximation of the GNH matrix for solving linear systems and eigenvalue problems. It generally requires $O(N^2)$ memory and $O(N^3)$ work to store and factorize the GNH matrix, respectively. The H-matrix approximation requires only $O(N{r}_o)$ memory footprint and $O(N{r}_o^2)$ work to be factorized, where $r_o\ll N$ is the maximum rank of off-diagonal blocks in the GNH matrix. We demonstrate the performance of our fast algorithm and the H-matrix approximation on classification and autoencoder neural networks.

References in corpus (13)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• New insights and perspectives on the natural gradient method
• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• Sub-sampled Newton Methods with Non-uniform Sampling
• ImageNet Training in Minutes
• Large-Scale Distributed Second-Order Optimization Using Kronecker-Factored Approximate Curvature for Deep Convolutional Neural Networks
• Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• Parallelization of the inverse fast multipole method with an application to boundary element method
• Block-diagonal Hessian-free Optimization for Training Neural Networks
• Diagonal Rescaling For Neural Networks
• Tracking the gradients using the Hessian: A new look at variance reducing stochastic methods

Cited by in corpus (2)

• A literature survey of matrix methods for data science
• Deep Neural Network Learning with Second-Order Optimizers -- a Practical Study with a Stochastic Quasi-Gauss-Newton Method