Hutch++: Optimal Stochastic Trace Estimation
We study the problem of estimating the trace of a matrix $A$ that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a $(1 \pm \epsilon)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$ using just $O(1/\epsilon)$ matrix-vector products. This improves on the ubiquitous Hutchinson's estimator, which requires $O(1/\epsilon^2)$ matrix-vector products. Our approach is based on a simple technique for reducing the variance of Hutchinson's estimator using a low-rank approximation step, and is easy to implement and analyze. Moreover, we prove that, up to a logarithmic factor, the complexity of Hutch++ is optimal amongst all matrix-vector query algorithms, even when queries can be chosen adaptively. We show that it significantly outperforms Hutchinson's method in experiments. While our theory mainly requires $A$ to be positive semidefinite, we provide generalized guarantees for general square matrices, and show empirical gains in such applications.
Code (1)
Similar Papers 제목 키워드 기반
Optimal Stochastic Trace Estimation in Generative Modeling
Hutchinson estimators are widely employed in training divergence-based likelihoods for diffusion models to ensure optimal transport (OT) properties. However, this estimator often suffers from high variance and scalabilit…
Image GenerationTime SeriesBOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions
Efficient matrix trace estimation is essential for scalable computation of log-determinants, matrix norms, and distributional divergences. In many large-scale applications, the matrices involved are too large to store or…
subspace methodsEstimation of matrix trace using machine learning
We present a new trace estimator of the matrix whose explicit form is not given but its matrix multiplication to a vector is available. The form of the estimator is similar to the Hutchison stochastic trace estimator, bu…
BIG-bench Machine LearningFormEfficient DP-SGD for LLMs with Randomized Clipping
Large language models (LLMs) are trained on vast datasets that may contain sensitive information. Differential privacy (DP), the de facto standard for formal privacy guarantees, provides a principled framework for traini…
Question AnsweringStochastic trace estimation with tensor train random vectors
Stochastic trace estimation is a standard tool for approximating the trace of a large-scale matrix available only through matrix-vector products. However, in tensor-structured settings, unstructured Gaussian or Rademache…