Reading group: Sum-of-Squares Method for Statistics (Summer 2020)

Description

The goal of this reading group is to study the sum-of-squres (SoS) method and its application to statistical estimation problems.

General Information

Organizer:

Xiangyu Guo

Time:

Fri 9:00 pm EDT

Location:

via Zoom

Schedule

[Mon, Jun 12][handout][Ref: [Course0], section 1.1, 1.2] Introduction on SoS basics
[TBD][handout][Ref: [Course0], section 1.3] Round pseudo-distribution: Max-Cut
[TBD][handout][Ref: [Hop0] section 1] GMM (1): Identifiable proof
[TBD][handout][Ref: [Hop0] section 2, 3] GMM (2): SoS identifiable proof
[TBD][handout][Ref: [Hop0] section 4] GMM (3): Rounding
[TBD][handout][Ref: [Hop17]] Mean estimation in sub-Gaussian rates
[TBD][handout][Ref: [CHKRT20]] Covariance estimation for heavy-tailed distribution
[TBD][handout][Ref: [KKK19][BK20a]] Anti-concentration (1): List-decodable linear regression
[TBD][handout][Ref: [DHKK20][BK20b]] Anti-concentration (2): Robustly learning GMM

References

Related courses

  • [LiCourse] Robustness in Machine Learning (CSE 599-M), taught by Jerry Li

  • [SteCourse] Robust Statistics (STAT260), taught by Jacob Steinhardt

    • SoS basics

  • [Course0] SoS course by Boaz Barak and David Steurer

  • [Course1] SoS winter school in UCSD (2017)

  • [Course2] Aaron Potechin's SoS seminar (2020)

  • [Survey0] Semialgebraic Proofs and Efficient Algorithm Design, by N. Fleming, P. Kothari, and T. Pitassi

    • The "proof-to-algorithms" framework and the "low-degree liklihood ratio" approach

  • [Hop0] Samuel B. Hopkins' tutorial notes on SoS for clustering problem

  • [Hop1] Statistical Inference and the Sum of Squares Method. Samuel B. Hopkins' PhD Thesis. including the low-degree method and the pseudo-calibration technique.

  • [KWB19] Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio. introduction on the "low-degree likelihood ratio" framework

  • [HL18] Mixture Models, Robustness, and Sum of Squares Proofs. paper version of [Hop0]

  • [Hop17] Mean Estimation with Sub-Gaussian Rates in Polynomial Time

  • [CHKRT20] Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond

    • Certifying "anti-concentrated" distribution:
  • [KKK19] List-Decodable Linear Regression
  • [BK20a] List-Decodable Subspace Recovery via Sum-of-Squares
  • [BK20b] Outlier-Robust Clustering of Non-Spherical Mixtures
  • [DHKK20] Robustly Learning any Clusterable Mixture of Gaussians

    • Lower bounds

  • [Hop1]. proposes the "low-degree ratio hypothesis"

  • [HKPRSS17] The power of SoS for detecting hidden structures. SoS lowerbounds obtained via pseudo-calibration for a bunch of planted problems

  • [BHKKMP16] A nearly tight sum-of-squares lower bound for the planted clique problem . First application of the pseudo-calibration technique

  • [GJW20] Low-Degree Hardness of Random Optimization Problems . Lower bounds for low-degree methods via OGP

    • SoS for tensor problems

  • [Hop2] Notes on tensor decomposition using the SoS method