On Gaussianwidth gradient complexity and meanfield behavior of interacting particle systems and random graphs.
Geometric functional analysis and applications November 13, 2017  November 17, 2017
Location: MSRI: Simons Auditorium
Boolean hypercube
meanfield
random graphs
large deviations
1Eldan
The motivating question for this talk is: What does a sparse Erd\"osR\'enyi random graph, conditioned to have twice the number of triangles than the expected number, typically look like? Motivated by this question, In 2014, Chatterjee and Dembo introduced a framework for obtaining Large Deviation Principles (LDP) for nonlinear functions of Bernoulli random variables (this followed an earlier work of ChatterjeeVaradhan which used limit graph theory to answer this question in the dense regime). The aforementioned framework relies on a notion of "low complexity" functions on the discrete cube, defined in terms of the covering numbers of their gradient. The central lemma used in their proof provides a method of estimating the lognormalizing constant $\log \sum_{x \in \{1,1\}^n} e^{f(x)}$ by a corresponding meanfield functional. In this talk, we will introduce a new notion of complexity for measures on the discrete cube, namely the meanwidth of the gradient of the logdensity. We prove a general structure theorem for such measures which goes beyond the discrete cube. In particular, we show that a measure $\nu$ attaining low complexity (with no extra smoothness assumptions needed) are close to a product measure in the following sense: there exists a measure $\tilde \nu$ a small "tilt" of $\nu$ in the sense that their logdensities differ by a linear function with small slope, such that $\tilde \nu$ is close to a product measure in transportation distance. An easy corollary of our result is a strengthening of the framework of ChatterjeeDembo, which in particular simplifies the derivation of LDPs for subgraph counts, and improves the attained bounds. We will demonstrate how our framework can be used to study the behavior of lowcomplexity measures beyond the approximation of the partition function. As an example application, we prove that exponential random graphs behave roughly like mixtures of stochastic block models.
Eldan Notes

Download 
1Eldan
H.264 Video 
1Eldan.mp4

Download 
Please report video problems to itsupport@msri.org.
See more of our Streaming videos on our main VMath Videos page.