CSE-280: SUM-OF-SQUARES (SoS) & GAUSSIAN PROCESSES

This will be a one-quarter (Winter-2024) seminar course discussing a recent result (I,II) by Jonathan Shi and myself. The main contribution of this result is that it introduces a new SoS hierarchy to optimize certain Gaussian processes and efficiently certify the values of their expected supremum to some (constant) threshold of approximability. The threshold is widely-believed to be optimal among polynomial-time algorithms. The paper also makes a conjecture about the optimality of this hierarchy for a broad class of Gaussian processes, providing examples of modified Gaussian processes where the HES hierarchy provably outperforms local-iterative algorithms such as Hessian ascent (or provides strong evidence of doing so). Proving (or disproving) this conjecture would unravel interesting connections between high-dimensional probability, sum-of-squares, random matrices and free probability.

Meeting Time: Tuesdays, 11:40 AM - 1:40 PM PST.

Location: Social Sciences Building 2, Room 137. (Meetings will be zoomed; Contact me for the link and/or access to the recordings).

Lectures: Video recordings

SYLLABUS

• Lecture-1: Motivation/Introduction - Why certify Gaussian processes?

• Lecture-2: Sum-of-squares: The proof system & SDP feasibility.

• Lecture-3: Subag’s algorithm for spherical spin-glasses.

• Lecture-4: Hermite polynomials & graph matrices: Harmonic analysis.

• Lecture-5: Lower bounds against the Lasserre hierarchy: Trace-power method & refutations.

• Lecture-6: Circumventing the problem: High-Entropy-Steps (HES) hierarchy.

• Lecture-7: HES-based-SoS certificates for Schatten norms of the Hessian.

• Lecture-8: HES-based-SoS certificates for the Nuclear norm of the higher-order derivatives.

• Lecture-9: Step-wise strong convexity & rounding: Sensitivity analysis & recursive quadratic sampling.

• Lecture-10: Rounding analysis: Bounding the low-degree (pseudo) Wasserstein distance.

• Lecture-11: HES-SoS advantage over local-iterative algorithms: Free probability & universality.

• Lecture-12: Open problems.

NOTES & RESOURCES

As the lectures progress, I will upload PDFs of my (poorly) hand-written notes from my e-notebook. I will also add relevant papers, SoS & spin-glass resources soon.

Note: The second paper will be available on arXiv starting February-15, 2024. Until then, I will share a (nearly) camera-ready draft with enrolled students.