Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations

DOI10.1007/S00039-018-0461-ZMaRDI QIDQ1632233zbMATH OpenOpenAlexWikidataFDO

Authors Ronen Eldan

Publication date 13 December 2018

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.04346

zbMATH Keywords

log-Sobolev inequalitiesGaussian-widthnonlinear large deviations

Mathematics Subject Classification ID

Large deviations (60F10) Gaussian processes (60G15)

Abstract: We prove structure theorems for measures on the discrete cube and on Gaussian space, which provide sufficient conditions for mean-field behavior. These conditions rely on a new notion of complexity for such measures, namely the Gaussian-width of the gradient of the log-density. On the cube ${-1,1}^n$, we show that a measure $u$ which exhibits low complexity can be written as a mixture of measures ${u_{h}eta}_{hetainmathcalI}$ such that: i. for each $heta$, the measure $u_{h}eta$ is a small perturbation of $u$ such that $logfracd{u}_{h}etadu$ is a linear function whose gradient is small and, ii. $u_{h}eta$ is close to some product measure, in Wasserstein distance, for most $heta$. Thus, our framework can be used to study the behavior of low-complexity measures beyond approximation of the partition function, showing that those measures are roughly mixtures of product measures whose entropy is close to that of the original measure. In particular, as a corollary of our theorems, we derive a bound for the na"ive mean-field approximation of the log-partition function which improves the nonlinear large deviation framework of Chatterjee and Dembo in several ways: 1. It does not require any bounds on second derivatives. 2. The covering number is replaced by the weaker notion of Gaussian-width 3. We obtain stronger asymptotics with respect to the dimension. Two other corollaries are decomposition theorems for exponential random graphs and large-degree Ising models. In the Gaussian case, we show that measures of low-complexity exhibit an almost-tight reverse Log-Sobolev inequality.

Recommendations

• The structure of low-complexity Gibbs measures on product spaces
• A Dimension-Free Reverse Logarithmic Sobolev Inequality for Low-Complexity Functions in Gaussian Space
• Decomposition of mean-field Gibbs distributions into product measures
• A transportation approach to the mean-field approximation
• Large deviations for empirical measures of mean-field Gibbs measures

Cites work

• scientific article; zbMATH DE number 3896050 (Why is no real title available?)
• Decomposition of mean-field Gibbs distributions into product measures
• Estimating and understanding exponential random graph models
• Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• Nonlinear large deviations
• On the variational problem for upper tails in sparse random graphs
• Probability in Banach spaces. Isoperimetry and processes
• Representation formula for the entropy and functional inequalities
• Transport-entropy inequalities and curvature in discrete-space Markov chains
• Transportation cost for Gaussian and other product measures
• Universality of the mean-field for the Potts model
• Upper tails and independence polynomials in random graphs

Cited in

(43)

• A Dimension-Free Reverse Logarithmic Sobolev Inequality for Low-Complexity Functions in Gaussian Space
• Upper tails for edge eigenvalues of random graphs
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Large deviation for uniform graphs with given degrees
• Upper tails via high moments and entropic stability
• Localization in random geometric graphs with too many edges
• Deviation probabilities for arithmetic progressions and irregular discrete structures
• Sub-critical exponential random graphs: concentration of measure and some applications
• On the upper tail problem for random hypergraphs
• A large deviation principle for the Erdős-Rényi uniform random graph
• Anti-concentration for subgraph counts in random graphs
• Typical large graphs with given edge and triangle densities
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
• Typical structure of sparse exponential random graph models
• Bernoulli random matrices
• Exponential random graphs behave like mixtures of stochastic block models
• Stability of the logarithmic Sobolev inequality via the Föllmer process
• Upper tail for homomorphism counts in constrained sparse random graphs
• A transportation approach to the mean-field approximation
• Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation
• Nonlinear large deviations: beyond the hypercube
• The structure of low-complexity Gibbs measures on product spaces
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Upper tails and independence polynomials in random graphs
• The CLT in high dimensions: quantitative bounds via martingale embedding
• Mean field approximations via log-concavity
• Decomposition of mean-field Gibbs distributions into product measures
• Upper tail of the spectral radius of sparse Erdös-Rényi graphs
• Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
• A counterexample to the DeMarco-Kahn upper tail conjecture
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes
• Replica symmetry in upper tails of mean-field hypergraphs
• Upper tail bounds for stars
• Multi-variate correlation and mixtures of product measures.
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Lower tails via relative entropy
• Preferential attachment when stable
• Analysis of high-dimensional distributions using pathwise methods
• Rare events in random matrix theory
• The upper tail problem for induced 4‐cycles in sparse random graphs
• Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs

This page was built for publication: Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1632233)