Moments, Random Walks, and Limits for Spectrum Approximation
Yujia Jin Christopher Musco Aaron Sidford Apoorv Vikram Singh
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 $\epsilon$ in
Wasserstein-1 distance even if we know \emph{all} of their moments to
multiplicative accuracy $(1\pm2^{-\Omega(1/\epsilon)})$; 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/\epsilon)}$ 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/\epsilon$ in this result would require a new algorithmic approach.
Specifically, no algorithm can compute an $\epsilon$-accurate approximation to
the spectrum of a normalized graph adjacency matrix with constant probability,
even when given the transcript of $2^{\Omega(1/\epsilon)}$ random walks of
length $2^{\Omega(1/\epsilon)}$ started at random nodes.