CSE 599S: Entropy optimality

Winter, 2016

Course overview

Instructor: James R. Lee

Office hours: After class and by appointment

TA: Jeffrey Hon (jhon@cs)

Office hours: TBD

Time and Location: Wed & Fri, 2:30-4pm in CSE 403

Class email list: cse599s_wi16 [click the link to sign up]

Homeworks: Homework policy will be discussed in class.

Homework Dropbox (turn homework in here)


[The lecture notes are evolving; some of the expositions may improve with time and reflection.
To keep track, the last modification date is written by the file link. ]
class topic notes related material
6-Jan Entropy and relative entropy. Optimality conditions in convex optimization. Matrix scaling. pdf
8-Jan Multiplicative-weights update. The Sinkhorn-Knopp scaling algorithm. pdf
13-Jan Mirror descent and density approximation. pdf
15-Jan Discrete Fourier analysis. Chang's Lemma and generalizations pdf
20-Jan Lifts of polytopes and non-negative rank pdf
22-Jan Junta degree and hardness amplification pdf
27-Jan From junta degree to non-negative rank pdf
29-Jan Spectrahedral lifts and positive semi-definite rank pdf
10-Feb Bregman divergences and mirror descent [again] see Lec. 3 for now;
these notes will be merged
12-Feb Quantum entropy maximization (and hyperbolic cones) pdf
17-Feb The Schrodinger problem and entropic interpolation
19-Feb Mixing times and convergence to equlibrium Chapter 1 of Montenegro-Tetali
  • Mathematical aspects of mixing times in Markov chains
  • Markov Chains and Mixing Times
  • 24-Feb Entropy-transport and discrete curvature
    [live stream @ 10:25am]
    powerpoint | pdf | video
    26-Feb Log-Sobolev inequalities, hypercontractivity, and locality-sensitive hashing pdf
    • If you didn't take CSE525, each problem here can be done for 1 point.
    2-Mar [continued]
    4-Mar Entropic interpolation over Brownian motion and Brascamp-Lieb inequalities notes
    9-Mar No class: Grad student visit days
    11-Mar Follmer-Borell interpolation notes

    Course overview

    Evaluation and grading

    • Homeworks (100%)

    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