Non-Gaussian Component Analysis: Statistical Query Hardness and its Applications

on YouTube ↗29m

" summary

Proves an SQ hardness theorem for Non‑Gaussian Component Analysis: if a univariate A matches the first m moments with N(0,1) and has finite chi-square distance, then any SQ tester either needs d^m samples (via tiny query tolerance ~B^{-m}·sqrt(χ^2)) or exponentially many queries in d. Key tools are a projection/Noise‑operator lemma showing random projections hide non‑Gaussianity and a 1D construction: mixtures of k Gaussians matching 2k‑1 moments give high‑dimensional “parallel pancake” instances that encode hard GMM and other learning problems.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 1:21NON-GAUSSIAN COMPONENT ANALYSIS (NGCA): DEFINITION
3. 3:12EXAMPLE: NGCA ENCODES GMMS
4. 5:55STATISTICAL QUERY (SQ) MODEL [KEARNS'93]
5. 7:38INTERPRETATION OF SQ LOWER BOUNDS Suppose we have proved
6. 9:11POWER OF SQ ALGORITHMS • Restricted Model Can prove unconditional lower bounds
7. 9:34GENERAL METHODOLOGY FOR SQ LOWER BOUNDS
8. 11:11STATISTICAL QUERY HARDNESS OF NGCA
9. 12:27INTUITION: WHY IS NGCA HARD?
10. 13:26KEY LEMMA: RANDOM PROJECTIONS ARE ALMOST GAUSSIAN
11. 15:47SQ LOWER BOUND: PROOF OVERVIEW
12. 18:30EXAMPLE: SQ HARDNESS OF LEARNING GMMS
13. 19:45SQ HARD INSTANCES FOR GMMS: PARALLEL PANCAKES
14. 20:27SQ HARDNESS FOR WIDE RANGE OF PROBLEMS

" related talks

• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp
• 52mIndependent Component Analysis: From Theory to Practice and BackSantosh Vempala · Spectral Algorithms: From Theory to Practice 2014
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 35mLearning General Gaussian Mixtures With Efficient Score MatchingVasilis Kontonis · Joint IFML/MPG Symposium 2024
• 29mApproximating Spherical Gaussian MixturesAnanda Suresh · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian MixturesPravesh K. Kothari · Computational Phase Transitions (Simons Institute, 2020)