Nonlinear large deviations

By Sourav Chatterjee, Amir Dembo. 2014

151 citations recorded by the source corpus.

We present a general technique for computing large deviations of nonlinear functions of independent Bernoulli random variables. The method is applied to compute the large deviation rate functions for subgraph counts in sparse random graphs. Previous technology, based on Szemeredi's regularity lemma, works only for dense graphs. Applications are also made to exponential random graphs and three-term arithmetic progressions in random sets of integers.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/c1bcde3434c84cbb36c66f858fc975bd592e1956

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order (2013, methodology): “, in the study of multiple stochastic integrals, in discrete harmonic analysis as elements of the Fourier expansions on the discrete cube or in numerous problems of random graph theory, to mention just the famous subgraph counting problem [22,23,26,27,35,36,49].”
Large deviations of subgraph counts for sparse Erdős–Rényi graphs (2018, methodology): “asures. When the Hamiltonian has the separable form f(x) = f1(x1)+···+fd(xd), so that µis itself a product measure, the naive mean ﬁeld approximation is an exact identity. The main idea introduced in [CD16] (see also the survey [Cha16]) is that the naive mean ﬁeld approximation can be rigorously jus”
Upper tails via high moments and entropic stability (2019, background): “The theory of nonlinear large deviations (discussed above) provides a variational description of the dependence of the upper tail probability P(X > (1 + δ)E[X]) on δ for a certain range of p → 0, as established in [2, 17, 22, 27]; the strongest of these results require p n−∆/(6∆−4) for general graph”
An introduction to large deviations for random graphs (2016, background): “…years ago, large deviations theory did not have the tools to answer such basic questions about nonlinear functions of independent random variables, although a number of powerful concentration inequalities were available for computing upper and lower bounds on tail probabilities [35, 37, 48, 50].”
Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations (2016, methodology): “We now turn to formulating our main theorem concerning nonlinear large deviations, which is parallel to [Chatterjee and Dembo, 2016, Theorem 1.1].”