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

2019/10/27 by Chao Chen, Chen, Chao, Severin Reiz +7
Computer Science · Engineering · #FOS: Mathematics #Neural Networks and Applications #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1910.12184

openalex publication_date 2019/10/27 · openalex created_date 2020/11/23 · openalex updated_date 2026/07/28

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/ε²) work, where d is the output dimension of the network and ε 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(N r_o) memory footprint and O(N r_o²) work to be factorized, where r_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.

Citations

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Sub-sampled Newton Methods with Non-uniform Sampling
• Diagonal Rescaling For Neural Networks
• Block-diagonal Hessian-free Optimization for Training Neural Networks
• Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic\n Problems
• Large-Scale Distributed Second-Order Optimization Using Kronecker-Factored Approximate Curvature for Deep Convolutional Neural Networks

Related

• Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks
• Efficient Computation of Hessian Matrices in TensorFlow
• Theoretical characterisation of the Gauss-Newton conditioning in Neural Networks
• Adaptive Error-Bounded Hierarchical Matrices for Efficient Neural Network Compression
• Block-diagonal Hessian-free Optimization for Training Neural Networks