FAST APPROXIMATION OF THE GAUSS NEWTON HESSIAN MATRIX FOR THE MULTILAYER PERCEPTRON.

We introduce a fast algorithm for entrywise 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(Nri) 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/e²) work, where d is the output dimension of the network and e 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²) memory and O(N³) work to store and factorize the GNH matrix, respectively. The 'H-matrix approximation requires only O(Nr_o) memory footprint and O(Nr°) work to be factorized, where ro O 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. [ABSTRACT FROM AUTHOR]