Learning Overcomplete Latent Variable Models through Tensor Power Method
summary
Presents a polynomial-time algorithm that recovers overcomplete latent-variable models (mixtures and multiview) by constructing a third-order moment tensor and applying a form of the tensor power method. When component means are random and k is a constant factor larger than dimension d the algorithm outputs component estimates with sqrt(k/d) accuracy; with bounded variance it tolerates k up to about d^{1.5}. Sample complexity is roughly k/epsilon^2, initialization comes from random tensor slices or averaged samples, and the method is proved to work up to the stated bounds.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:40Learning
- 2:08Latent Variable Models
- 4:29Mixture of Gaussians
- 7:39Multi-view Model
- 19:06Method of moments [Pearson 1894]
- 26:55Tensor Power Method (orthogonal case)
- 31:03Overcomplete Tensor Decompositions
- 34:23Our Results (in tensor language)
- 37:45Alternating Least Squares
- 40:24Alternating Rank-1 Update
- 44:43Analyzing the Update
- 48:44Initialization
- 51:12Sample Complexity
- 52:41Not all vectors are the same
- 52:57Conclusion
- 53:11Open Problems
related talks
52mTensor Methods for Learning Latent Variable Models: Theory and Practice
53mTensor Decompositions for Learning Latent Variable Models II
56mTensor Decompositions for Estimating Latent Variable Models
49mSpectral Algorithms for Learning Latent Variable Models
52mAverage-Case Overcomplete Tensor Decomposition
52mLearning Mixture of Gaussians using Moment Tensor
56mTensor Decompositions for Learning Latent Variable Models I
01h 03mRecent Progress in High-Dimensional Learning