Latent Variable models and Subset Smoothing

on YouTube ↗29m

" summary

Defines Subset Smoothed polytope K' as the convex hull of averages over k‑subsets of the n noisy samples and proves K' ≈ K when many latent points lie near each vertex (Dirichlet‑type condition) and noise is Gaussian. Shows averaging reduces variance by ~√k and K' admits a polynomial‑time optimization oracle (maximize a linear functional by picking top averages), so random linear probes recover vertex candidates with 1/poly(k) success given distance Ω(diameter). Provides a provable algorithm to find vertices under small k and standard noise.

AI-written summary · about

" chapters (7)

1. 0:00Latent polytopes introduction
2. 3:27Latent variable model examples
3. 8:17Defining subset smoothing
4. 16:53Convex hull and optimization
5. 17:13Separating hyperplanes in geometry
6. 21:10Random vectors and separation
7. 24:49Q&A

" related talks

• 01h 22mGeneralization IVPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 01h 02mTheory and Big DataRavi Kannan · Big Data Boot Camp 2013
• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical OptimizationBoaz Nadler · Statistics in the Big Data Era 2022
• 28mCertified Sub-Linear Lower Bounds for K-Means ClusteringSoledad Villar · Sublinear Algorithms and Nearest-Neighbor Search
• 09mPrimal--Dual Optimization and Application to SamplingAdil Salim · Meet the Fellows Welcome Event
• 53mSketching and ProjectingDeanna Needell · Sketching and Algorithm Design 2023
• 43mComputational and Statistical Tradeoffs via Convex RelaxationVenkat Chandrasekaran · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)