# Moments, Random Walks, and Limits for Spectrum Approximation

arXiv: https://arxiv.org/abs/2307.00474 · HTML: https://mlsanity.com/paper/2307.00474/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 2 Jul 2023.

## Builds on (most cited first, 10 of 10)

- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [Traditional and Heavy-Tailed Self Regularization in Neural Network Models](https://mlsanity.com/paper/1901.08276/) (2019)
- [The Emergence of Spectral Universality in Deep Networks](https://mlsanity.com/paper/1802.09979/) (2018)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Network Density of States](https://mlsanity.com/paper/1905.09758/) (2019)
- [Spectrum Estimation from Samples](https://mlsanity.com/paper/1602.00061/) (2016)
- [Sublinear Time Spectral Density Estimation](https://mlsanity.com/paper/2104.03461/) (2021)
- [Approximating the Spectrum of a Graph](https://mlsanity.com/paper/1712.01725/) (2017)

## Built on by (most cited first, 2 of 2)

- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)
- [Fast Spectrum Estimation of Some Kernel Matrices](https://mlsanity.com/paper/2411.00657/) (2024)

## Abstract (arXiv)

We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on [-1,1] that cannot be approximated to accuracy ε in Wasserstein-1 distance even if we know all of their moments to multiplicative accuracy (1±2-Omega(1/ε)); this result matches an upper bound of Kong and Valiant [Annals of Statistics, 2017]. To obtain our result, we provide a hard instance involving distributions induced by the eigenvalue spectra of carefully constructed graph adjacency matrices. Efficiently approximating such spectra in Wasserstein-1 distance is a well-studied algorithmic problem, and a recent result of Cohen-Steiner et al. [KDD 2018] gives a method based on accurately approximating spectral moments using 2O(1/ε) random walks initiated at uniformly random nodes in the graph. As a strengthening of our main result, we show that improving the dependence on 1/ε in this result would require a new algorithmic approach. Specifically, no algorithm can compute an ε-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability, even when given the transcript of 2Omega(1/ε) random walks of length 2Omega(1/ε) started at random nodes.