Moments, Random Walks, and Limits for Spectrum Approximation
Date:
Presented our poster (joint work with Yujia Jin, Christopher Musco, and Aaron Sidford) at the Workshop on Modern Techniques in Graph Algorithms.
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 $\varepsilon$ in Wasserstein-1 distance even if we know all of their moments to multiplicative accuracy $(1\pm2^{-\Omega(1/\varepsilon)})$; 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/\varepsilon)}$ 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/\varepsilon$ in this result would require a new algorithmic approach. Specifically, no algorithm can compute an $\varepsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability, even when given the transcript of $2^{\Omega(1/\varepsilon)}$ random walks of length $2^{\Omega(1/\varepsilon)}$ started at random nodes.
This is joint work with Yujia Jin (Stanford), Christopher Musco (NYU), and Aaron Sidford (Stanford).