On Approximation Guarantees for Greedy Low Rank Optimization

on YouTube ↗30m

" summary

Greedy addition of rank‑one atoms achieves a provable multiplicative approximation: objective of the K‑rank greedy iterate is within a factor ~1 − exp(−C K/R) of the best rank‑R solution, with a more precise bound 1 − exp(−τ² γ K/R) when using OMP with power method (τ is the power‑method accuracy). Proof links low‑rank recovery to weak submodularity via restricted strong concavity/smoothness on rank‑restricted sets. Practically, K must grow like K ≈ R log n to reach usual statistical rates; SBM experiments show rank‑robust reconstruction.

AI-written summary · about

" chapters (10)

1. 0:00Introduction and objective
2. 2:33Motivation and applications
3. 3:53Atomic approximation framework
4. 7:24Submodular optimization basics
5. 8:47Weak submodularity theory
6. 11:55Generalizing to low rank
7. 14:05Restricted concavity bounds
8. 19:23Algorithm performance
9. 21:21Literature and experiments
10. 28:47Q&A and discussion

" related talks

• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 01h 04mSubmodularity: Theory and Applications IIAndreas Krause · Foundations of Machine Learning Boot Camp 2017
• 35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro FactorizationPraneeth Netrapalli · Randomized Numerical Linear Algebra and Applications 2018
• 40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical OptimizationBoaz Nadler · Statistics in the Big Data Era 2022
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 46mFast Attention Requires Bounded EntriesJosh Alman · Sketching and Algorithm Design 2023
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017