From Proofs to Algorithms for Machine Learning Problems
Talkat Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017) · 2017-11-06..11-09·
summary
Claims that many ML estimation gaps close when identifiability admits a concrete low-degree proof: sum-of-squares proofs capture the certificate, yield convex relaxations/SDPs and dual pseudo-distributions, and turn checking proofs into algorithms. Gives concrete results: matrix completion exact recovery at ~R·N samples via an SDP, tensor completion improved from R·N^2 to R·N^{1.5} samples using SOS-based pseudo-moments, dictionary learning via a degree‑4 SOS certificate, and community detection via low-degree posterior truncation (logarithmic SOS degree).
AI-written summary · about
chapters (10)
- 0:00Identifiability proofs and algorithms
- 1:05Parameter estimation problems
- 3:35Identifiability versus learning
- 9:21Matrix completion proofs
- 22:30Algorithms from identifiability
- 33:53Tensor completion with SOS
- 41:46Dictionary learning and sparsity
- 55:06Community detection in SBM
- 1:02:01Sum of squares approach
- 1:02:30Q&A
related talks
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
59mTesting Assumptions of Learning Algorithms