ARC and Indo-US Virtual Center Seminar: Tselil Schramm (Stanford)

Event Details
  • Date/Time:
    • Monday August 17, 2020
      11:30 am - 12:30 pm
  • Location: Virtual via Bluejeans
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Reconciling Statistical Queries and the Low Degree Likelihood Ratio - Virtual via Bluejeans at 11:30am

Full Summary: No summary paragraph submitted.

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.

----------------------------------

Speaker's Webpage

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

Additional Information

In Campus Calendar
No
Groups

ARC

Invited Audience
Faculty/Staff, Postdoc, Graduate students, Undergraduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Aug 10, 2020 - 9:09am
  • Last Updated: Aug 10, 2020 - 9:48am