18.177. Topics in Stochastic Processes (fall 2018).
GENERAL INFORMATION.
In the study of large (often highdimensional) stochastic systems it is often important to be able to quantify the probabilities of rare events, or large deviations.
This course will cover the theory of large deviations, as well as recent applications and extensions in the field of probability and statistical physics.
The first part of the semester will cover general foundations. The second part will cover some recent research papers in probability theory.
The format will be similar to that of a class taught by David Aldous at Berkeley in 2008, although the topics of the second part will differ.
18.175 is a prerequisite. The lectures will also assume basic familiarity with pointset topology.
ADMINISTRATION.
Please include "18.177" in the subject line of all emails.
Instructor: Nike Sun (nsun at mit dot edu).
Office hours: Mondays 34 and Wednesdays 1112 in 2432.
REFERENCES. References marked * are available electronically through libraries.mit.edu.
Main references:
[DZ] *A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications (2010 corrected reprint).
[RS] *F. RassoulAgha and T. Seppäläinen, A Course on Large Deviations (2015).
[MM] M. Mézard and A. Montanari, Information, Physics, and Computation (2009).
[webpage]
Additional references:
*P. Billingsley, Convergence of Probability Measures (2nd edition 2008).
*S. Chatterjee, Large Deviations for Random Graphs (2015).
F. den Hollander, Large Deviations (2000).
J. R. Munkres, Topology (2nd edition 2015).
*D. Panchenko, The SherringtonKirkpatrick model (2013).
F. Rezakhanlou, lecture notes.
R. T. Rockafellar, Convex Analysis (1970).
SCHEDULE.
 Lecture 1 (09/05) Introductory examples: gaussian and binomial large deviations; review of binary entropy and relative entropy; an example with conditioning.
Week 1 office hours Thursday (09/06) 45:30.
 Lecture 2 (09/10) Formal definition of LDP; lower semicontinuity (lsc) for the rate function.
RS 2.12.2 / DZ Ch. 1.
 Lecture 3 (09/12) Cramér's theorem; weak LDP; exponential tightness; change of measure.
RS 2.32.4 / DZ 2.2.
Week 2 office hours Monday (09/10) 34 and Wednesday (09/12) 1112.
 Lecture 4 (09/17) More on change of measure; intuition and interpretations. Explicit calculations for discrete measures on R.
 Lecture 5 (09/18) A Cramértype weighting in the random kSAT problem. References:
 D. Achlioptas, C. Moore. "The asymptotic order of the random kSAT threshold." Proc. 43rd FOCS: 779788. IEEE, 2002.
 D. Achlioptas, Y. Peres. "The threshold for random kSAT is 2^k log 2  O(k)." J. Am. Math. Soc. 17:4 (2004): 947973.
 Lecture 6 (09/24) Contraction principle; Varadhan's lemma; CurieWeiss example; Legendre duality in general vector spaces; relative entropy and its dual.
RS 3.13.3, 4.1, 5.1.
 Lecture 7 (09/26) General weak LDP upper bound by convex conjugate; proof of Sanov's theorem.
RS 4.2, 5.2. Prohorov's theorem and Ulam's theorem in Billingsley (see above).
 Lectures 8 and 9 (10/01 and 10/03)
Guest lectures from Yufei Zhao on large deviations in random graphs. References:
 S. Chatterjee, S.R.S. Varadhan. "The large deviation principle for the ErdősRényi random graph." Eur. J. Combin. 32:7 (2011): 10001017.
 E. Lubetzky, Y. Zhao. "On replica symmetry of large deviations in random graphs." Random Struct. Algor. 47:1 (2015): 109146.
 Lecture 10 (10/10) Introduction to spin glasses: binary synchronization problem; SherringtonKirkpatrick (SK) model; random energy model (REM); condensation phenomenon and PoissonDirichlet statistics.
Reading: MM Ch. 5, Panchenko Ch. 2. Further references:
 B. Derrida. "Randomenergy model: Limit of a family of disordered models." Phys. Rev. Lett. 45.2 (1980): 79.
 B. Derrida. "Randomenergy model: An exactly solvable model of disordered systems." Phys. Rev. B 24.5 (1981): 2613.
 Lecture 11 (10/15) Introduction to variational methods for factor models: Gibbs variational principle; naive meanfield approximation (e.g. CurieWeiss); Bethe approximation; belief propagation (BP) equations.
Reading: MM Ch. 14. Further references:
 J. S. Yedidia, W. T. Freeman, Y. Weiss. "Constructing freeenergy approximations and generalized belief propagation algorithms." IEEE Trans. Inform. Theory 51.7 (2005): 22822312.
 A. Montanari. "Inference in graphical models" (lecture notes). Available online.
 M. J. Wainwright, M. I. Jordan. "Graphical models, exponential families, and variational inference." Foundations and Trends in Machine Learning 1.12 (2008): 1305. Available online.
 Lecture 12 (10/17) Bethe variational principle: constrained optimization on the local polytope; and an alternate view via random nlifts.
 Lecture 13 (10/22) Binary synchronization problem: Bethe formula (replica symmetric formula) for optimal MSE.
Some references for the optimal (Bayes) MSE:
 T. Lesieur, F. Krzakala, L. Zdeborová. "Phase transitions in sparse PCA."
arXiv:1503.00338,
ISIT 2015.
 Y. Deshpande, E. Abbe, A. Montanari. "Asymptotic mutual information for the binary stochastic block model."
arXiv:1507.08685,
ISIT 2016.
 J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur, L. Zdeborová.
"Mutual information for symmetric rankone matrix estimation: A proof of the replica formula."
NIPS 2016.
 M. Lelarge, L. Miolane. "Fundamental limits of symmetric lowrank matrix estimation."
PTRF (2016): 171.
 A. El Alaoui, F. Krzakala. "Estimation in the spiked Wigner model: a short proof of the replica formula."
arXiv:1801.01593 (2018).
 A. El Alaoui, F. Krzakala, M. I. Jordan. "Fundamental limits of detection in the spiked Wigner model."
arXiv:1806.09588 (2018).
Some references for the spectral threshold:
 J. Baik, G. Ben Arous, S. Péché. "Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices."
AOP 33.5 (2005): 16431697.
 D. Féral, S. Péché. "The largest eigenvalue of rank one deformation of large Wigner matrices."
CMP 272.1 (2007): 185228.
 F. BenaychGeorges, R. R. Nadakuditi. "The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices."
Adv. Math. 227.1 (2011): 494521.
 Lecture 14 (10/24) Binary synchronization problem: interpretation of Bayes inference as gaussian scalar channel.
Some proof ideas: the partition function encodes the MMSE ("Nishimori identity" & gaussian integration by parts);
an interpolation of the Hamiltonian can be used to bound the partition function.
Some references for the Guerra interpolation:
 F. Guerra, F. L. Toninelli. "The thermodynamic limit in mean field spin glass models."
CMP 230.1 (2002): 7179.
 F. Guerra. "Broken replica symmetry bounds in the mean field spin glass model."
CMP 233.1 (2003): 112.
 D. Panchenko, M. Talagrand. "Bounds for diluted meanfields spin glass models."
PTRF 130.3 (2004): 319336.
 M. Bayati, D. Gamarnik, P. Tetali. "Combinatorial approach to the interpolation method and scaling limits in sparse random graphs."
AOP 41.6 (2013): 40804115.
 D. Gamarnik. "Rightconvergence of sparse random graphs."
PTRF 160.12 (2014): 253278.
 Lecture 15 (10/29) SherringtonKirkpatrick (SK) model with external field: derivation of the TAP equations, and the "state evolution" scaling limit of the TAP (AMP) iteration. References:
 D. J. Thouless, P. W. Anderson, R. G. Palmer. "Solution of 'solvable model of a spin glass'."
Philos. Mag. 35.3 (1977): 593601.
 J. R. L. de Almeida, D. J. Thouless. "Stability of the SK solution of a spin glass model."
J. Phys. A, 11.5 (1978): 983.
 M. Bayati, A. Montanari. "The dynamics of message passing on dense graphs, with applications to compressed sensing."
IEEE Trans. Inform. Theory 57.2 (2011): 764785.
 E. Bolthausen. "An iterative construction of solutions of the TAP equations for the SK model."
CMP 325.1 (2014): 333366.
 Lecture 16 (10/31) TAP equations and replica symmetric prediction for the Ising perceptron. References:
 W. Krauth, M. Mézard. "Learning algorithms with optimal stability in neural networks."
J. Phys. A 20.11 (1987): L745.
 M. Mézard. "The space of interactions in neural networks: Gardner's computation with the cavity method."
J. Phys. A 22.12 (1989): 2181.
 J. Ding, N. Sun. "Capacity lower bound for the Ising perceptron."
arXiv:1809.07742 (2018).
 E. Bolthausen. "A Morita type proof of the replicasymmetric formula for SK."
arXiv:1809.07972 (2018).
 Lecture 17 (11/05) Uniqueness, extremality (nonreconstruction), replica symmetry. Decomposition into Bethe states (clusters) and the 1RSB equations. Reading: MM Chapter 21. References:
 A. Montanari, D. Shah. "Counting good truth assignments of random kSAT formulae."
SODA 2007.
 M. Mézard, A. Montanari. "Reconstruction on trees and spin glass transition."
J. Stat. Phys. 124.6 (2006): 13171350.
 F. Krzakala, A. Montanari, F. RicciTersenghi, G. Semerjian, L. Zdeborová.
"Gibbs states and the set of solutions of random constraint satisfaction problems."
PNAS 104.25 (2007): 1031810323.
 Lecture 18 (11/07) Random regular NAESAT for large k: combinatorial view of replica symmetry breaking. References:
 L. Zdeborová, F. Krzakala. "Phase transitions in the coloring of random graphs."
Phys. Rev. E 76.3 (2007): 031131.
 A. Montanari, F. RicciTersenghi, G. Semerjian. "Clusters of solutions and replica symmetry breaking in random ksatisfiability."
J. Stat. Mech. 2008.04 (2008): P04004.
 A. Sly, N. Sun, Y. Zhang. "The number of solutions for random regular NAESAT."
arXiv:1604.08546 (2016).
 Lecture 19 (11/14) Gaussian comparison inequalities (Slepian's inequality, Gordon's inequality); capacity of the spherical perceptron. References:
 Section 3.3 in M. Ledoux, M. Talagrand. Probability in Banach Spaces: isoperimetry and processes.
Springer, 2013.
 M. Stojnic. "Another look at the Gardner problem."
arXiv:1306.3979 (2013).
 Lecture 20 (11/19) lowcomplexity Gibbs measures. Main reference:
 T. Austin. "Measures of correlation and mixtures of product measures."
arXiv:1809.10272 (2018).
 T. Austin. "The structure of lowcomplexity Gibbs measures on product spaces."
arXiv:1810.07278 (2018).
Other references (some will be presented in December):
 S. Chatterjee, A. Dembo. "Nonlinear large deviations."
Adv. Math. 299 (2016): 396450.
 R. Eldan. "Gaussianwidth gradient complexity, reverse logSobolev inequalities and nonlinear large deviations."
arXiv:1612.04346 (2016).
 R. Eldan, R. Gross. "Decomposition of meanfield Gibbs distributions into product measures."
EJP 23 (2018).
 Lecture 21 (11/21) Generalized random energy model, Ruelle probability cascades, and the Parisi functional. Panchenko Ch.2.
 Lecture 22 (11/26) Some ingredients in the proof of the Parisi formula. Panchenko Ch. 3.
 Lecture 23 (11/28) Guest lecture from Andrej Risteski on variational methods and convex programming hierarchies. References:
A. Risteski. "How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods." COLT 2016.
A. Risteski, Y. Li. "Approximate maximum entropy principles via GoemansWilliamson with applications to provable variational methods." NIPS 2016.
V. Jain, F. Koehler, A. Risteski. "Meanfield approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective." arXiv:1808.07226 (2018).
 Presentations (12/03):
 Sergei: T. Seppäläinen. "Large deviations for increasing sequences on the plane." PTRF 112.2 (1998): 221244.
 Yuzhou: R. Basu, S. Ganguly, A. Sly. "Upper tail large deviations in first passage percolation." arXiv:1712.01255 (2017).
 Presentations (12/05):
 Roger: H. Cohn, R. Kenyon, J. Propp. "A variational principle for domino tilings." JAMS 14.2 (2001): 297346.
 Jie Jun: E. Bolthausen, J.D. Deuschel, G. Giacomin. "Entropic repulsion and the maximum of the twodimensional harmonic crystal." AOP 29.4 (2001): 16701692.
 Yixiang: E. Lubetzky, F. Martinelli, A. Sly. "Harmonic pinnacles in the discrete gaussian model." CMP 344.3 (2016): 673717.
 Presentations (12/10):
 Ashwin: G. Ben Arous, A. Guionnet. "Large deviations for Wigner's law and Voiculescu's noncommutative entropy." PTRF 108.4 (1997): 517542.
 Suhas: N. Gantert, S. Kim, K. Ramanan. "Large deviations for random projections of ell^p balls." arXiv:1512.04988 (2015).
 Presentations (12/12):
 Sinho: R. Eldan. "Gaussianwidth gradient complexity, reverse logSobolev inequalities and nonlinear large deviations." arXiv:1612.04346 (2016);
R. Eldan, R. Gross. "Decomposition of meanfield Gibbs distributions into product measures." EJP 23 (2018).
 Jonathan: F. Augeri. "Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in ErdősRényi graphs." arXiv:1810.01558 (2018).
