CSE280: SUMOFSQUARES (SoS) & GAUSSIAN PROCESSES
This will be a onequarter (Winter2024) 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 widelybelieved to be optimal among polynomialtime 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 localiterative algorithms such as Hessian ascent (or provides strong evidence of doing so). Proving (or disproving) this conjecture would unravel interesting connections between highdimensional probability, sumofsquares, 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

Lecture1: Motivation/Introduction  Why certify Gaussian processes?

Lecture2: Sumofsquares: The proof system & SDP feasibility.

Lecture3: Subagâ€™s algorithm for spherical spinglasses.

Lecture4: Hermite polynomials & graph matrices: Harmonic analysis.

Lecture5: Lower bounds against the Lasserre hierarchy: Tracepower method & refutations.

Lecture6: Circumventing the problem: HighEntropySteps (HES) hierarchy.

Lecture7: HESbasedSoS certificates for Schatten norms of the Hessian.

Lecture8: HESbasedSoS certificates for the Nuclear norm of the higherorder derivatives.

Lecture9: Stepwise strong convexity & rounding: Sensitivity analysis & recursive quadratic sampling.

Lecture10: Rounding analysis: Bounding the lowdegree (pseudo) Wasserstein distance.

Lecture11: HESSoS advantage over localiterative algorithms: Free probability & universality.

Lecture12: Open problems.
NOTES & RESOURCES
As the lectures progress, I will upload PDFs of my (poorly) handwritten notes from my enotebook. I will also add relevant papers, SoS & spinglass resources soon.
Note: The second paper will be available on arXiv starting February15, 2024. Until then, I will share a (nearly) cameraready draft with enrolled students.