Estimating the Spectral Density of Large Implicit Matrices

By Ryan P. Adams, Jeffrey Pennington, Matthew J. Johnson, Jamie Smith, Yaniv Ovadia, Brian Patton, James Saunderson. 2018

40 citations recorded by the source corpus.

Many important problems are characterized by the eigenvalues of a large matrix. For example, the difficulty of many optimization problems, such as those arising from the fitting of large models in statistics and machine learning, can be investigated via the spectrum of the Hessian of the empirical loss function. Network data can be understood via the eigenstructure of a graph Laplacian matrix using spectral graph theory. Quantum simulations and other many-body problems are often characterized via the eigenvalues of the solution space, as are various dynamic systems. However, naive eigenvalue estimation is computationally expensive even when the matrix can be represented; in many of these situations the matrix is so large as to only be available implicitly via products with vectors. Even worse, one may only have noisy estimates of such matrix vector products. In this work, we combine several different techniques for randomized estimation and show that it is possible to construct unbiased estimators to answer a broad class of questions about the spectra of such implicit matrices, even in the presence of noise. We validate these methods on large-scale problems in which graph theory and random matrix theory provide ground truth.

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

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

In Numerical Methods & Scientific Computing

Citations in the corpus

An Investigation into Neural Net Optimization via Hessian Eigenvalue Density (2019, methodology): “We perform a thorough comparison of our work to the recent proposal of [2] in Appendix D. Batch Normalization (BN) [14] is one of the most inﬂuential innovations in optimizing deep neural networks as it substantially reduces the training time and the dependence of the training on initialization.”
FFJORD: Free-form Continuous Dynamics for Scalable Reversible Generative Models (2018, methodology): “The Monte Carlo estimator derived from (7) is known as Hutchinson’s trace estimator (Hutchinson, 1989; Adams et al., 2018).”
The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “[72] Ryan P Adams, Jeffrey Pennington, Matthew J Johnson, Jamie Smith, Yaniv Ovadia, Brian Patton, and James Saunderson, “Estimating the spectral density of large implicit matrices,” arXiv preprint arXiv:1802.”
Invertible Residual Networks (2018, background): “Recently, unbiased estimates (Adams et al., 2018) and unbiased gradient estimators (Han et al.”
Residual Flows for Invertible Generative Modeling (2019, background): “Some recent works use Chebyshev polynomials to estimate the spectral functions of symmetric matrices (Han et al., 2018; Adams et al., 2018; Ramesh and LeCun, 2018; Boutsidis et al., 2008).”
Scalable Reversible Generative Models with Free-form Continuous Dynamics (2018, methodology): “The Monte Carlo estimator derived from (3) is known as the Hutchinson’s trace estimator (Hutchinson, 1989; Adams et al., 2018).”
Stochastic Chebyshev Gradient Descent for Spectral Optimization (2018, background): “[25] Ryan P Adams, Jeffrey Pennington, Matthew J Johnson Jamie Smith Yaniv Ovadia Brian Patton James Saunderson.”
Negative eigenvalues of the Hessian in deep neural networks (2018, background): “While there have been attempts at estimating Hessians in very high dimensions, for instance by Adams et al. (2018), they tend to suffer from either even higher computational costs or large variance.”