BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230717T120000Z
UID:adcad7bdc632e6b75e6b03fc6768e8a0-484
DTSTAMP:19700101T120014Z
DESCRIPTION:Moments, Random Walks, and Limits for Spectrum Approximation
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/484/moments-random-walks-and-limits-for-spectrum-approximation/
SUMMARY: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.

Based on joint work with Yujia Jin, Christopher Musco, and Aaron Sidford.


Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d



We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, Rachana Gusain, Rahul Madhavan, KVN Sreenivas
DTSTART:20230717T120000Z
END:VEVENT
END:VCALENDAR