*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
and Indo-US Virtual Center Seminar
Tselil Schramm (Stanford)
Monday, August 17, 2020
Virtual via Bluejeans - 11:30 am
Title: Reconciling Statistical Queries and the Low Degree Likelihood Ratio
Abstract: In many high-dimensional statistics problems, we observe information-computation tradeoffs: given access to more data, statistical estimation and inference tasks require fewer computational resources. Though this phenomenon is ubiquitous, we lack rigorous evidence that it is inherent. In the current day, to prove that a statistical estimation task is computationally intractable, researchers must prove lower bounds against each type of algorithm, one by one, resulting in a "proliferation of lower bounds". We scientists dream of a more general theory which unifies these lower bounds and explains computational intractability in an algorithm-independent way.
In this talk, I will make one small step towards realizing this dream. I will demonstrate general conditions under which two popular frameworks yield the same information-computation tradeoffs for high-dimensional hypothesis testing: the first being statistical queries in the "SDA" framework, and the second being hypothesis testing with low-degree hypothesis tests, also known as the low-degree-likelihood ratio. Our equivalence theorems capture numerous well-studied high-dimensional learning problems: sparse PCA, tensor PCA, community detection, planted clique, and more.
Based on joint work with Matthew Brennan, Guy Bresler, Samuel B. Hopkins and Jerry Li.
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
