Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature

By Shashanka Ubaru, Jie Chen, Y. Saad. 2017

221 citations recorded by the source corpus.

Subfields: Applied Mathematics, Statistics and Probability, 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 Applied Mathematics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model (2019, positive): “This closely matches the estimated eigenspectrum of the Hessian of a convolutional network (see Figure 9 and Appendix E.4), and is also consistent with recent work finding heavy tailed eigenspectra of neural network Hessians [Ubaru et al., 2017, Ghorbani et al., 2019].”
An Investigation into Neural Net Optimization via Hessian Eigenvalue Density (2019, background): “There exists an extensive literature on bounding this error; [28] prove that under suitable conditions that where ρ > 1 .”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “We refer to Ubaru et al. (2017) for additional discussion.”
Stochastic Chebyshev Gradient Descent for Spectral Optimization (2018, methodology): “Another recently suggested powerful technique is stochastic Lanczos quadrature [30], however it is not suitable for our needs (our bias removal technique is not applicable for it).”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “For example, [3, 4] proposed fast algorithms for trace computation; and [17, 25] provided efficient randomized algorithms to estimate the ESD of a positive semi-definite matrix.”
Scalable Log Determinants for Gaussian Process Kernel Learning (2017, methodology): “In machine learning there has recently been renewed interest in MVM based approaches to approximating log determinants, such as the Chebyshev [19] and Lanczos [20] based methods, although these approaches go back at least two decades in quantum chemistry computations [21].”
Backpropagation for Implicit Spectral Densities (2018, unknown): “We make no attempt to conduct a comprehensive survey, but note that among the most promising recent approaches are those described by Han et al. [2017], Boutsidis et al. [2017], Ubaru et al. [2017], and Fitzsimons et al. [2017].”
GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration (2018, methodology): “K̂−1 XXy can be computed using conjugate gradients (CG) [9, 10, 43, 50], and the other two quantities can be computed using calls to the iterative Lanczos tridiagonalization algorithm [13, 46].”
OT-Flow: Fast and Accurate Continuous Normalizing Flows via Optimal Transport (2020, methodology): “[53] Shashanka Ubaru, Jie Chen, and Yousef Saad.”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, methodology): “…logarithm of the determinant log det( A ) , used in many machine learning tasks, such as Bayesian learning, kernel learning, Gaussian processes, tree mixture models, spatial statistics and Markov ﬁeld models (see e.g. ( Han et al., 2015; Ubaru et al., 2017; Ubaru and Saad, 2017; Han et al., 2017)).”