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

Gaussian-widthlog-Sobolev inequalitiesnonlinear 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

• Decomposition of mean-field Gibbs distributions into product measures
• Estimating and understanding exponential random graph models
• scientific article; zbMATH DE number 3896050 (Why is no real title available?)
• 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

(53)

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

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)