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

This will be a one-quarter (Winter-2024) seminar course discussing a recent result I by Jonathan Shi and myself. The main contribution of this result is that it introduces a new SoS hierarchy to certify the values of the expected supremum of Gaussian process, 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: Sensitivity analysis & recursive quadratic sampling.

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

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

NOTES & RESOURCES

I have some offline notes in my (poor) hand-writing that were shared with the students. For a list of relevant papers and monographs that are relevant, contact me.