Detecting Weak Signals via Hypothesis Testing

on YouTube ↗39m

" summary

Binary test between product noise P0 and a weak mixture signal (1−ε)P0+εP1 uses the chi‑square distance D = χ2(P1||P0) to set a sharp threshold: if ε√D → 0 no ideal test (both type I and II →0) exists, while if ε√D → ∞ an ideal test exists under mild regularity. Proof rewrites the likelihood ratio (mixture ≈ 1+ε sum of per‑coordinate ratios), then uses moment bounds and Paley‑Zygmund/anti‑concentration (up to fourth moments) to prove the phase transition.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:36Hypothesis Testing
3. 3:31Likelihood Ratios and Neyman-Pearson Lemma
4. 5:28Asymptotics
5. 7:56Weak Signals
6. 15:28Central Idea, in principle proof
7. 19:31Proper Lower Bound Theorem
8. 21:36(Some) High level proof ideas
9. 25:25High level proof ideas - 11
10. 28:30Open Questions
11. 30:35Related Work

" related talks

• 30mStatistical Property Testing and Estimation Beyond the i.i.d. SettingGregory Valiant · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) DataClément Canonne · Sublinear Algorithms Boot Camp 2024
• 27mDetection and Estimation through an Information Theory LensSergio Verdú · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 28mNear-Optimal Hypothesis Testing via Convex OptimizationArkadi Nemirovski · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 35mTesting Noise Assumptions of Learning AlgorithmsArsen Vasilyan · Joint IFML/MPG Symposium 2024
• 31mStrong Data Processing Inequalities and Estimation with ConstraintsJohn Duchi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 59mTesting Assumptions of Learning AlgorithmsArsen Vasilyan · Sublinear Algorithms Boot Camp 2024
• 37mEfficient Algorithms for Reliable Machine LearningAdam R. Klivans · The Role of TCS in Modern Machine Learning