BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of California\, Berkeley//UCB Events Calendar//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
DTSTART:19701029T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:19700402T020000
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20171018T181042Z
DTSTART;TZID=America/Los_Angeles:20171101T151000
DTEND;TZID=America/Los_Angeles:20171101T160000
TRANSP:OPAQUE
SUMMARY:On Gaussian-width gradient complexity and mean-field behavior of interacting particle systems and random graphs
UID:112693-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:1011 Evans Hall
DESCRIPTION:Ronen Eldan\, Weizmann Institute of Science\n\nThe motivating question for this talk is: What does a sparse Erd\\"os-R\\'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 Chatterjee-Varadhan 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 log-normalizing constant $\\log \\sum_{x \\in \\{-1\,1\\}^n} e^{f(x)}$ by a corresponding mean-fieldfunctional.\n\nIn this talk\, we will introduce a new notion of complexity for measures on the discrete cube\, namely the mean-width of the gradient of the log-density. 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 log-densities 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 Chatterjee-Dembo\, which in particular simplifies the derivation of LDPs for subgraph counts\, and improves the attained bounds. \nWe will demonstrate how our framework can be used to study the behavior of low-complexity 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.
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=112693&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20171018T181042Z
LAST-MODIFIED:20171025T175950Z
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR