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

By Ronen Eldan. Geometric and Functional Analysis, 2016

96 citations recorded by the source corpus.

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 ν\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\nu}$$\end{document} which exhibits low complexity can be written as a mixtureof measures {νθ}θ∈I\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\{\nu_\theta\}_{\theta\in\mathcal{I}}}$$\end{document} such that: (i) for each θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta}$$\end{document}, the measure νθ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\nu_\theta}$$\end{document} is a small perturbation of ν\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\nu}$$\end{document} such that log dνθdν\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{{d \nu_\theta}}{{d \nu}}$$\end{document} is a linear function whose gradient is small and, (ii) νθ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\nu_\theta}$$\end{document} is close to some product measure, in Wasserstein distance, for most θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta}$$\end{document}. 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ïve mean-field approximation of the log-partition function which improves the nonlinear large deviation framework of Chatterjee and Dembo (Adv Math, 319:313–347, 2017. ISSN 0001-8708. https://dx.doi.org/10.1016/j.aim.2017.08.003) 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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/5bf5d44d15d9249e46c53fe94f9e2896f6ce1edf

How researchers see this paper

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

In Computational Theory and Mathematics

  1. Wojciech Samotij
  2. Frank Mousset
  3. Matan Harel
  4. Jacques Verstraëte

In Discrete Mathematics and Combinatorics

  1. Wojciech Samotij
  2. Frank Mousset
  3. Matan Harel
  4. Jacques Verstraëte

In Statistics and Probability

  1. Wojciech Samotij

Citations in the corpus