mlsanityData to 7 Oct 2026

Hutch++: Optimal Stochastic Trace Estimation

arXiv 2010.09649 ↗First posted 19 Oct 2020cs.DS cs.LG cs.NAcited by 62

Not on the map. Why?

Abstract (arXiv)

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 ± ε) approximation to tr(A) for any positive semidefinite (PSD) A using just O(1/ε) matrix-vector products. This improves on the ubiquitous Hutchinson's estimator, which requires O(1/ε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.

Key facts. Cited by 62 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 5; 2023: 7; 2024: 8; 2025: 15; 2026: 22.

62 papers.

Sort:

By area:

  1. 2021Stabilizing Equilibrium Models by Jacobian Regularizationcited by 71
  2. 2021Optimizing Functionals on the Space of Probabilities with Input Convex Neural Networkscited by 53
  3. 2023Hutchinson Trace Estimation for High-Dimensional and High-Order Physics-Informed Neural Networkscited by 23
  4. 2021Preconditioning for Scalable Gaussian Process Hyperparameter Optimizationcited by 22
  5. 2023Query lower bounds for log-concave samplingcited by 12
  6. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  7. 2023Revisiting Energy Based Models as Policies: Ranking Noise Contrastive Estimation and Interpolating Energy Modelscited by 9
  8. 2025Position: Curvature Matrices Should Be Democratized via Linear Operatorscited by 9
  9. 2022Low-Rank Approximation with 1/ε1/3 Matrix-Vector Productscited by 7
  10. 2022Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problemscited by 7
  11. 2022Optimal Randomized Approximations for Matrix based Renyi's Entropycited by 7
  12. 2022Scale-invariant Bayesian Neural Networks with Connectivity Tangent Kernelcited by 7
38 more
  1. 2025Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimationcited by 6
  2. 2022Optimal Query Complexities for Dynamic Trace Estimationcited by 5
  3. 2024Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processescited by 5
  4. 2023When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimalitycited by 4
  5. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  6. 2026PRISM: Distribution-free Adaptive Computation of Matrix Functions for Accelerating Neural Network Trainingcited by 4
  7. 2026JPmHC Dynamical Isometry via Orthogonal Hyper-Connectionscited by 4
  8. 2024Sharper Bounds for Chebyshev Moment Matching, with Applicationscited by 3
  9. 2025Fast Generalized Neural Tangent Kernel Statistics via Trace Estimationcited by 3
  10. 2023Krylov Methods are (nearly) Optimal for Low-Rank Approximationcited by 2
  11. 2023Moments, Random Walks, and Limits for Spectrum Approximationcited by 2
  12. 2023Data-Driven Model Selections of Second-Order Particle Dynamics via Integrating Gaussian Processes with Low-Dimensional Interacting Structurescited by 2
  13. 2024Multivariate trace estimation using quantum state space linear algebracited by 2
  14. 2024Faster Spectral Density Estimation and Sparsification in the Nuclear Normcited by 2
  15. 2025Optimal Stochastic Trace Estimation in Generative Modelingcited by 2
  16. 2025Learning-Augmented Frequent Directionscited by 2
  17. 2025HiGP: A high-performance Python package for Gaussian Processcited by 2
  18. 2026Spectral Guardrails for Agents in the Wild: Detecting Tool Use Hallucinations via Attention Topologycited by 2
  19. 2026The Global Empirical NTK: Self-Referential Bias and Dimensionality of Gradient Descent Learningcited by 2
  20. 2026Mitigating the Contractivity Trap in Diffusion ODEs via Stein Stabilizationcited by 2
  21. 2024Warm Start Marginal Likelihood Optimisation for Iterative Gaussian Processescited by 1
  22. 2024RandALO: Out-of-sample risk estimation in no time flatcited by 1
  23. 2025BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functionscited by 1
  24. 2025On the Upper Bounds for the Matrix Spectral Normcited by 1
  25. 2025Matrix-Free Two-to-Infinity and One-to-Two Norms Estimationcited by 1
  26. 2026What Trace Powers Reveal About Log-Determinants: Closed-Form Estimators, Certificates, and Failure Modescited by 1
  27. 2026TASTE: Task-Aware Out-of-Distribution Detection via Stein Operatorscited by 1
  28. 2026Efficient DP-SGD for LLMs with Randomized Clippingcited by 1
  29. 2026Autoregressive Boltzmann Generatorscited by 1
  30. 2021XConv: Low-memory stochastic backpropagation for convolutional layerscited by 0
  31. 2021Variance Reduction for Matrix Computations with Applications to Gaussian Processescited by 0
  32. 2025Efficient Sparsification of Simplicial Complexes via Local Densities of Statescited by 0
  33. 2025Deterministic Bounds and Random Estimates of Metric Tensors on Neuromanifoldscited by 0
  34. 2025Lower bounds for trace estimation via Block Krylov and other methodscited by 0
  35. 2025Query Efficient Structured Matrix Learningcited by 0
  36. 2025Spectral Thresholds for Identifiability and Stability:Finite-Sample Phase Transitions in High-Dimensional Learningcited by 0
  37. 2025Matrix Phylogeny: Compact Spectral Fingerprints for Trap-Robust Preconditioner Selectioncited by 0
  38. 2026HESTIA: A Hessian-Guided Differentiable Quantization-Aware Training Framework for Extremely Low-Bit LLMscited by 0

50 most cited of 62 All 62 (JSON)