Moments, Random Walks, and Limits for Spectrum Approximation

Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh

    Research output: Contribution to journalConference articlepeer-review


    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−Ω(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.

    Original languageEnglish (US)
    Pages (from-to)5373-5394
    Number of pages22
    JournalProceedings of Machine Learning Research
    StatePublished - 2023
    Event36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India
    Duration: Jul 12 2023Jul 15 2023


    • moment methods
    • random walks
    • spectral density estimation
    • sublinear algorithm

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Control and Systems Engineering
    • Statistics and Probability


    Dive into the research topics of 'Moments, Random Walks, and Limits for Spectrum Approximation'. Together they form a unique fingerprint.

    Cite this