Moments, Random Walks, and Limits for Spectrum Approximation
This addresses a fundamental limitation in spectrum approximation for graph adjacency matrices, with implications for algorithmic design in machine learning and statistics, though it is incremental as it matches and strengthens existing bounds.
The paper tackles the problem of approximating a one-dimensional distribution from noisy moment measurements, showing that distributions on [-1,1] cannot be approximated to accuracy ε in Wasserstein-1 distance even with all moments known to high multiplicative accuracy, matching a prior upper bound. It strengthens this by proving that improving the exponential dependence on 1/ε in a recent spectral approximation method would require a new algorithmic approach, as no algorithm can compute an ε-accurate approximation with constant probability given 2^Ω(1/ε) random walks.
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\pm2^{-Ω(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 $2^{O(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.