[edit]
Moments, Random Walks, and Limits for Spectrum Approximation
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5373-5394, 2023.
Abstract
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 \emph{all} of their moments to multiplicative accuracy (1±2−Ω(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 2Ω(1/ϵ) random walks of length 2Ω(1/ϵ) started at random nodes.