Smoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro Factorization
summary
Paper analyzes Burer–Monteiro factorization on the penalized SDP and proves a smoothed‑analysis guarantee: after adding a Gaussian perturbation G to C, every ε-second‑order stationary point is an ε‑global optimum with high probability when the factor rank satisfies k ≥ O(√(m log(1/ε))). Tools: random matrix singular‑value bounds, ε‑net plus union bound, and descent‑direction arguments linking approximate low rank to convexity in X. Result holds for the penalized problem and yields polynomial‑time convergence to approximate global optima.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:31Semi-definite programs (SDPs)
- 3:38Burer-Monteiro factorization
- 6:10What can be done for nonconvex problems?
- 12:04Smoothed analysis
- 14:52Runtime guarantees
- 16:34Two key steps
- 19:34Smallest singular values of Gaussian matrices
- 24:36Technical issues
- 27:48Summary
- 31:02Open directions - random matrix theory
related talks
01h 00mSmoothed Analysis of Tensor Decompositions
01h 11mTensor Decompositions: Uniqueness and Smoothed Analysis
42mTight Semidefinite Programming Relaxations for Polynomial Optimization
30mOn Approximation Guarantees for Greedy Low Rank Optimization
47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
01h 01mRobustness, Stochastics, Uncertainty 2
32mLocal Statistics, Semidefinite Programming, and Community Detection