Foundations of Data Science II

on YouTube ↗55m

" summary

Claims that SVD identifies the k-dimensional subspace spanned by Gaussian means, yielding a polynomial-time algorithm to learn K spherical Gaussians with constant separation and unit variance; shows SVD subspace equals means subspace and that projecting there makes distance-based clustering reliable. Proves low-rank approximation with sample size independent of M,N using length-squared sampling yields dimension-independent sample complexity. Gives a practical sketch result A ≈ C U R from sampled rows and columns and a conductance-based O(1/phi^2) mixing bound for running-average Markov chains.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 3:24Application of SVD to Gaussian Mixtures
3. 5:19SVD subspace = space of means
4. 7:24Life without a Stochastic Model: An Example Theorem Hypothesis
5. 9:57Lile without a Stochastic Model An Example
6. 13:57Doing without a stochastic Model
7. 15:25Numerical Algorithms
8. 19:22Why Randomized Algorithms?
9. 21:33Simple Setting
10. 22:18Problems
11. 24:08A little Notation
12. 24:32Low Rank Approximation with Additive Error
13. 29:06Data Handling, Pass efficient Model
14. 31:47Length squared sample of rows and col's suffice
15. 40:05Different Topic: Markov Chains A Markov Chain (MC) is a directed graph with positive edge
16. 45:42Conductance, Rapid Mixing of Symmetric MC's
17. 49:56Brief Idea of Proof

" related talks

• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 44mSome Problems of Robust High-dimensional StatisticsGilad Lerman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 34mSubspace Clustering using Ensembles of K-SubspacesLaura Balzano · Randomized Numerical Linear Algebra and Applications 2018
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 49mRobust List Decoding of Spherical GaussiansDaniel Kane · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 36mUnbiased Estimates for Linear Regression via Volume SamplingMichal Derezinski · Randomized Numerical Linear Algebra and Applications 2018
• 26mMathematical Approaches to ClusteringJoseph Ross · MLconf Online 2020
• 02mTamara Kolda, Distinguished Member of Technical Staff, Sandia National Laboratories @ MLconf SF PartTamara Kolda · MLconf SF 2014