Completed
Optimality of Max-Cut
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Clustering a Mixture of Gaussians with Unknown Covariance - Lecture
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 The problem today
- 3 Challenges
- 4 How to measure separation?
- 5 Statistical metrics
- 6 Questions
- 7 Previous work: unknown covariance
- 8 Numerical illustration: FashionMNIST
- 9 Insight: Invariance
- 10 Canonical form
- 11 Maximum likelihood estimator
- 12 Optimality of Max-Cut
- 13 Two stage algorithm
- 14 Projected power iteration
- 15 Spectral algorithm
- 16 Global convergence guarantee
- 17 A statistical-computational gap?
- 18 A hard testing problem
- 19 Spectral methods lower bound
- 20 A reduction from testing
- 21 Max-Cut Semidefinite relaxation
- 22 Summary
