Convergence of SDP Hierarchies Using Kernel Based Methods: Moment Matrices

on YouTube ↗57m

" summary

Provides a general kernel-based rounding that converts an SDP pseudo-distribution P into a true probability Q by convolving with a squared kernel (Zeta^2) whose y-variable is a polynomial of degree ≤ L, and proves convergence bounds in terms of the kernel eigenvalue ratios (error ≤ (1 − λ_j/λ_0)·(max−min)). Construction uses reproducing kernels, orthogonal polynomials and linearization matrices to compute eigenvalues; results are exact for s=1,2, show asymptotic bounds when L/n is fixed as n→∞, and numerics (n up to 1000) show faster convergence on the sphere than the cube.

AI-written summary · about

" chapters (34)

1. 0:00Start
2. 3:01Example: the hypersphere
3. 3:35How difficult is this problem?
4. 4:14Approximation results (nonexhaustive)
5. 5:46Optimizing over measures
6. 6:44Moment matrix relaxations
7. 8:24SDP Relaxation (Lasserre/Parrilo)
8. 9:53What we'll be taking about...
9. 10:41Positive Kernels
10. 11:42Degenerate eigenvalues
11. 13:52Reproducing kernels
12. 15:11Kernels of interest
13. 18:08From a Kernel to an SDP
14. 19:56Rounding: Q-representation
15. 20:47How to form an approximation?
16. 22:08Is it normalized?
17. 24:30Is it positive?
18. 25:07Explicit representing measure
19. 25:58How are they related?
20. 28:45Role of the kernel
21. 30:51Summary of idea
22. 31:43A (too) general theorem
23. 35:43Proof (sketch)
24. 39:42Accuracy for polynomial optimization
25. 40:16How close is the SDP solution to the true optimum?
26. 41:56Existing SDPs and convergence as special cases
27. 43:33Zonal kernels
28. 44:53Zonal functions on the sphere
29. 45:13How can we find the optimal kernel?
30. 47:12Computing the eigenvalues
31. 49:44General case
32. 51:13Example: sphere
33. 52:10Example: hypercube
34. 53:54General recipe

" related talks

• 12mShort Proof of a Spectral Chernoff Bound for Local HamiltoniansNilin Abrahamsen · Meet the Fellows Welcome Event
• 31mShort Industry Talks pt. 1Gumaro Rendon, Anderson C A Nascimento · Eleventh Annual Industry Day
• 01h 06mNorm Minimization, Invariant Theory, And Quantum TomographyCole Franks · Optimization Under Symmetry 2021
• 59mOptimizing Noncommutative Polynomials: The SYK ModelRyan O'Donnell · Rigorous Evidence for Information-Computation Trade-offs
• 01h 15mDissipative State Preparation and the Dissipative Quantum EigensolverToby Cubitt · Quantum Summer Cluster Workshop 2023
• 55mFinding Eigenvalues in Exponential Size Space:...Zeph Landau · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 36mA Combinatorial Approach to Complexity Transitions in Quantum PhysicsRyan Mann · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 20mUnitary property testing lower bounds by polynomialsHenry Yuen, Adrian She · ITCS 2023