Syllabus (approximate)

Consider the set of all probability distributions on a finite set that satisfy a given collection of linear inequalities. For instance, we might specify various linear marginals or bounds on the probabilities of certain events. This set of distributions is a finite-dimensional polytope, and we can choose a distinguished element from that polytope by picking the one of maximum (Shannon) entropy. This course concerns the remarkable properties of such maximizers, along with a host of applications in computer science and mathematics. Every topic is teeming with fantastic open problems.

• Entropy, relative entropy, basic theorems of convex optimization The Sinkhorn-Knopp scaling algorithm, (regularized) gradient descent, and multiplicative weights update / boosting.
• Additive combinatorics: Chang's Lemma and its generalizations Roth's theorem on arithmetic progressions in dense subsets of the integers
• Lifts of polytopes, general models for linear programs Approximation of functions by juntas and lower bounds on extended formulations
• PSD lifts, general models for semi-definite programs Approximation of functions by low-degree sums-of-squares Maximization of von Neumann entropy over the PSD cone
• Negative dependence and concentration of measure Random spanning trees and the traveling salesman problem
• The Brascamp-Lieb inequality Forster's theorem, Robust subspace recovery
• The Schrodinger problem and entropy maximization over path space Brownian motion and Girsanov's change of measure formula Hypercontractivity and log-Sobolev inequalities
• Talagrand's convolution conjecture The Kumar-Courtade "most informative bit" conjecture
• Topics in online stochastic gradient descent