Smoothed Analysis of Tensor Decompositions

on YouTube ↗01h 00m

" summary

Proves polynomial-time, noise-robust tensor decomposition under a smoothed-analysis model: add small Gaussian perturbations to component vectors, flatten high-order tensors to third-order, and run Jennrich’s eigenvector method. Shows minimum singular value bounds so decomposition works for rank up to roughly n^{p-1}/2 (e.g. ~n^2 when p=5), tolerates inverse-polynomial adversarial Frobenius noise, and achieves exponentially small failure probability. Corollary: learning mixtures and topic models with polynomially many components.

AI-written summary · about

" chapters (12)

1. 0:00Introduction to tensors
2. 2:27Uniqueness and prior results
3. 5:07Scope and goals of the talk
4. 6:56Motivation from machine learning
5. 10:31Method of moments and learning
6. 13:34The smooth analysis paradigm
7. 17:22Smooth analysis model for tensors
8. 23:29Summary of technical guarantees
9. 27:47Algorithm outline and flattening
10. 37:55Handling the overcomplete case
11. 43:31Technical proof components
12. 50:09Conclusion and future directions

" related talks

• 01h 11mTensor Decompositions: Uniqueness and Smoothed AnalysisMoses Charikar · Semidefinite Optimization, Approximation and Applications 2014
• 52mAverage-Case Overcomplete Tensor DecompositionDavid Steurer · Random Instances and Phase Transitions (Simons Institute, 2016)
• 39mFast Spectral Algorithms from Sum-of-Squares AnalysesTselil Schramm · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 53mTensor Decompositions for Learning Latent Variable Models IIDaniel Hsu · Foundations of Machine Learning Boot Camp 2017
• 01h 03mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 56mTensor Decompositions for Learning Latent Variable Models IDaniel Hsu · Foundations of Machine Learning Boot Camp 2017
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro FactorizationPraneeth Netrapalli · Randomized Numerical Linear Algebra and Applications 2018