On McDiarmid’s Inequality under Dependence
via Approximate Tensorization of Entropy
January 01, 1970
We argue that dependent versions of McDiarmid’s inequality are a useful but underutilized tool in mathematical statistics, learning theory and theoretical computer science. To make this point, we first highlight that approximate tensorization of entropy (ATE) implies McDiarmid’s via the Entropy Method. Second, we derive McDiarmid’s inequality for non-isotropic Gaussian random vectors \(X \sim \mathcal{N}(\mu, \Sigma)\) through ATE with a constant of the order of the condition number of \(\Sigma\). We both independently obtain this ATE through a simple application of stochastic localization and also discuss how a more general ATE for the Gibbs sampler due to [1] generalizes McDiarmid’s-like concentration to strongly log-concave and log-smooth probability measures. We then apply the resulting concentration inequalities to resolve a question on the concentration of \(\operatorname{sign}(X)\) posed by Simone Bombari, investigate Erdős-Rényi graphs under dependence and prove a Dvoretzky-Kiefer-Wolfowitz-type inequality for observations from a joint measure fulfilling ATE and continuous marginal CDFs. For the class of strongly log-concave and log-smooth measures, this result improves upon a prior Dvoretzky-Kiefer-Wolfowitz-type inequality for non-i.i.d.observations due to [2], by establishing the expected \(1/\sqrt{n}\)-rate of convergence under weak dependence instead of \(n^{-1/3}\).
Concentration of measure is at the heart of statistics, learning theory and theoretical computer science, most often used in form of Chernoff-type concentration inequalities for sub-Gaussian and sub-exponential random variables (See e.g., [3]–[6]). Such concentration inequalities are an integral part of the toolbox of modern theoretical statisticians and computer scientists and were popularized in the machine learning community through monographs by [7]–[9]. Their essence is summarized in the following quote due to [10]:
"A random variable that depends (in a ‘smooth’ way) on the influence of many
independent random variables (but not too much on any of them) is essentially constant".
In this work we highlight that the statement above also extends to dependent random variables, as long as dependence is not too strong. One well-known example of this is Gaussian and more generally log-Sobolev Lipschitz concentration ([11]). It allows us to concentrate Lipschitz functions of Gaussian random vectors \(X \sim \mathcal{N}(\mu, \Sigma)\) where \(\Sigma \in \mathbb{R}^{n\times n}\) does not have to be the identity. Hence, its entries can be non-i.i.d. Dependence between the entries of \(X\) is thereby captured in the covariance matrix \(\Sigma\) and enters the concentration inequality in form of its largest eigenvalue \(\|\Sigma\|_{op}\). This suffices to establish fundamental results such as the concentration of an empirical mean of the marginals \(\bar X_n := \frac{1}{n} \sum_{i=1}^n X_i\) around its true mean \(\mathbb{E}[\bar X_n]\) and thereby allows us to characterize the change of the rate of convergence depending on the strength of dependence.
However, Gaussian Lipschitz concentration fails to cover many simple tasks such as concentrating sums of indicators of dependent Gaussian random variables, due to the failing Lipschitzness wrt. Euclidean distance. In the independent setting, this can be easily achieved through an application of Hoeffding’s inequality that provides sub-Gaussian tails for sums of bounded random variables ([12]). McDiarmid’s inequality generalizes the behavior of Hoeffding’s inequality and provides sub-Gaussian tails for "smooth" functions of independent random variables in the sense of Talagrand’s quote ([13], [14]). The inequality is also known as the bounded difference inequality, which stems from the following "smoothness" assumption it imposes on the function \(f : \mathcal{X}^n \to \mathbb{R}\) to be concentrated.
Definition 1. Bounded Differences Property
A function \(f : \mathcal{X}^n \to \mathbb{R}\) fulfills the bounded differences property if for \(c_1,...,c_n \geq 0\) and all \(i \in [n]\): \[\begin{align} \sup_{y, x_1,...,x_n \in \mathcal{X}} |f(x_1,...,x_n) - f(x_1,...x_{i-1} y, x_{i+1},...,x_n)| \leq c_i. \end{align}\]
Concretely, this condition implies that \(f\) is Lipschitz wrt. the Hamming distance \(d_H(x,y) := \sum_{i=1}^n \mathbf{1}{\{x_i \neq y_i\}}\) with Lipschitz constant \(L := \max_{i\in[n]} c_i\). Likewise, if \(f\) is \(L\)-Hamming-Lipschitz, it fulfills bounded differences with constants \(L\). This type of Lipschitzness is more suitable to the functions of interest in many problems of combinatorial nature, a collection of which are outlined in [14]. The bounded difference property of \(f\) and independence between random variables is then enough to obtain the following sub-Gaussian tail bound for \(f\) around its mean.
Theorem 1. McDiarmid’s Inequality ([13])
Let \(X \in \mathcal{X}^n\) have independent entries. Assume \(f : \mathcal{X}^n \to \mathbb{R}\) fulfills the bounded differences property with constants \(c := (c_1,...,c_n)^{\top}\). Then, for all \(t > 0\) we have \[\begin{align} \mathbb{P}\left(|f(X) - \mathbb{E}[f(X)]| \geq t\right) &\leq 2\exp\left(-\frac{2t^2}{\|c\|_{2}^2}\right). \end{align}\]
Given that McDiarmid’s is applicable in cases where Gaussian Lipschitz concentration fails to apply, but suffers from the restriction to independent random variables, it is now natural to ask:
Is there a simple tool that let’s us apply
Hamming-Lipschitz concentration under dependence?
Surely, when the dependence structure is known and only a few of the entries depend on each other, we would expect a similar behavior as in Theorem 1 as we could treat dependent observations together and adjust the effective sample-size accordingly. This idea is formalized by a line of work that encodes information on the dependence structure between entries in dependency graphs, partitions entries into independent sets and then uses the (fractional) chromatic number to capture the strength of dependence. [15] was the first to derive a Hoeffding-type concentration inequality for sums of dependent random variables using this technique, followed by [16], [17] that extended it to functions with the bounded difference property.
Even earlier [18] proved the Azuma-Hoeffding inequality, a generalization of Hoeffding’s inequality, which holds for martingale differences instead of the special case of sums of independent random variables and is now termed the Martingale Method. This approach of capturing dependence through martingales and filtrations was later extended to bounded differences ([19]) and [20] exploit it to obtain a McDiarmid’s-like concentration inequality for Hamming-Lipschitz functions on discrete state spaces. When combined with Wasserstein matrices [21] show that the martingale method can unify some results obtained through other approaches to concentration with bounded differences, e.g., via the Dobrushin uniqueness condition ([22]–[26]) or couplings ([20]).
An alternative to dependency graphs and the martingale method is to capture dependence using information theoretic concepts. For example, [27] establish McDiarmid’s under dependence using Hellinger integrals. More widely used, however, is the entropy method, which derives McDiarmid’s-type inequalities relying on so called sub-additivity or tensorization of entropy (See e.g. [7]). This notion already appearing in [28] holds for product measures, hence i.i.d. random variables. The proof approach extends to dependent settings through approximate tensorization of entropy (ATE). Similar to log-Sobolev Lipschitz concentration where the log-Sobolev constant \(\rho \geq 1\) captures the strength of dependence, ATE captures dependence in a constant \(\kappa \geq 1\) that is 1 only for product measures. Katalin Marton pioneered this relaxation and established it first for Euclidean spaces ([29]). Thereafter, [30] and [31] derived ATE under versions of Dobrushin’s uniqueness condition on discrete product spaces and [32] provided concentration inequalities under higher-order bounded differences for discrete product spaces that exploit ATE. Since, ATE has become a central notion in the study of mixing times of the Glauber and heat-bath block dynamics also known as Gibbs samplers on discrete spin glasses as it has direct implications on their mixing time (See e.g., [33]–[35] for proofs of ATE through spectral and entropic independence). Further, [36] and [37] show Hamming-Lipschitz concentration and approximate variance tensorization for spin glasses through stochastic localization. These techniques are generalized and refined in [38] and [39]. While the study of dependence in spin glasses is interesting, it does not straightforwardly relate to the study of dependence in more classical problems in estimation and learning theory.
Only recently, works on ATE by [40] and [1] again focused on the Euclidean case first considered by [29]. Especially the results of [1] are remarkable as they imply ATE for Gaussian and strongly log-concave and log-smooth measures. Through McDiarmid’s inequality under ATE this provides a versatile analogue to Gaussian and log-Sobolev Lipschitz concentration for the Hamming-Lipschitz case:
Gaussian Hamming-Lipschitz concentration.
This manuscript aims to provide a comprehensive derivation of this tool that is mostly implicit and hidden between the parts of the literature on Markov chain mixing and concentration inequalities1.
In Section 2 we first derive McDiarmid’s inequality using ATE. In Section 3 we then provide an independent derivation of ATE for \(\mathcal{N}(\mu, \Sigma)\) with \(\kappa\) of the order of the condition number of \(\Sigma\) through stochastic localization. Moreover, we discuss how the results by [1] sharpen this ATE constant and establish ATE for a class of probability measures including all strongly log-concave and log-smooth ones. Section 4 contains three increasingly involved examples of applications of McDiarmid’s under ATE: a short proof that \(\operatorname{sign}(X)\) is dimension-free sub-Gaussian, a simple example of how McDiarmid’s reveals the effect of dependence in Erdős-Rényi graphs and a Dvoretzky-Kiefer-Wolfowitz-type inequality under ATE. We consider this inequality a main contribution of this work as it is the first to establish the expected \(1/\sqrt{n}\)-rate of convergence under ATE, in particular for weakly dependent Gaussians. Finally, Section 5 discusses our work.
Let \([n] := \{{1,2,...,n}\}\), \(\mathbf{1}{\{A\}}\) be the indicator function for a set \(A\) and \(A \sqcup B\) be the disjoint union between sets. Let \(\mathbf{1}_d \in \mathbb{R}^d\) be the all ones vector and \(I_d \in \mathbb{R}^{d \times d}\) the identity matrix. For matrices \(A,B \in \mathbb{R}^{d\times d}\) denote their positive definite and positive semi-definite order as \(A\prec B\) and \(A\preceq B\) and operator norm as \(\|A\|_{op}\). For \(x,y\in\mathcal{X}^n\), their Hamming distance is \(d_H(x,y) := \sum_{i=1}^n \mathbf{1}{\{x_i \neq y_i\}}\) and \(x_{-i} := (x_1,...,x_{i-1}, x_{i+1},...,x_n)^{\top}\) denotes all but the \(i\)-th entry of \(x \in \mathcal{X}^n\). For a probability measure \(\nu\) that has a density wrt. Lebesgue measure \(dx\) we abuse notation and write \(\nu(x)\) for its density. A measure on \(\mathbb{R}^d\) is \(\alpha\)-strongly log-concave and \(\beta\)-log-smooth if \(\nu(x) \propto \exp(-V(x))\) is s.t. \(\alpha I_d \preceq \nabla V(x) \preceq \beta I_d\) with \(0 < \alpha \leq \beta < \infty\) for all \(x \in \mathbb{R}^d\). Let \(\nu_i\) and \(\nu(\cdot|x_{-i})\) be its marginal and conditional measures. For two sequences \((a_n)_{n\in\mathbb{N}}\) and \((b_n)_{n\in\mathbb{N}}\) we write \(b_n = O(a_n)\) or \(a_n \lesssim b_n\) if \(\exists C > 0\) and \(n_0 \in \mathbb{N}\) s.t. \(\forall n \geq n_0, |\frac{b_n}{a_n}| \leq C\). We write \(a_n\asymp b_n\) if \(a_n\lesssim b_n\) and \(b_n\lesssim a_n\).
Concentration via the entropy method is discussed in detail in Chapter 6 of [7]. Alternatively, Chapter 3 in [42] also outlines the proof idea behind the Entropy Method from a more information theoretic viewpoint. The key inequality behind the Entropy Method for McDiarmid’s is tensorization of entropy, where entropy is defined as follows.
Definition 2. Entropy
Let \(\nu\) be a probability measure on \(\mathbb{R}^n\). For an integrable \(f : \mathbb{R}^n \to [0, \infty)\) s.t. \(\int_{\mathbb{R}^n} f|\log(f)|d\nu < \infty\), \[\begin{align} \operatorname{Ent}_{\nu}(f) := \int_{\mathbb{R}^n} f \log(f) d\nu - \left(\int_{\mathbb{R}^n} f d\nu\right)\log\left(\int_{\mathbb{R}^n} fd\nu\right). \end{align}\]
Whenever we use entropy the in the following, we assume that \(f\) is s.t. the relevant quantities exist. For random variables \(X \in \mathcal{X}^n\) with i.i.d. entries, entropy tensorization refers to the concept that the entropy is sub-additive in the sense that it is upper bounded by the sum of the expectations of the conditional entropies, i.e., the entropies wrt. the conditional measure \(\nu(\cdot|X_{i-1})\) on \(\mathcal{X}_i\).
Lemma 1. Entropy Tensorization (Lemma 4.1, [33])
Let \(\nu :=\nu_1 \otimes \dotsm \otimes \nu_n\) be a product probability measure on the product space \(\mathcal{X}^n := (\mathcal{X}_1 \times \dotsm \times \mathcal{X}_n)\). Suppose that \(X \sim \mathcal{\nu}\). Then, for all \(f : \mathcal{X}^n \to [0,\infty)\), \[\begin{align} \operatorname{Ent}_{\nu}(f) \leq \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu_i}(f)] = \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)]. \end{align}\]
Similarly, we formalize ATE in Definition 3 below, where now a constant \(\kappa \geq 1\) captures the deviation from the behavior of a product measure and thus bigger \(\kappa\) indicates more dependence. We refer to the case where \(\kappa \asymp 1\) as the case of weak dependence.
Definition 3. Approximate Tensorization of Entropy
A probability measure \(\nu\) on a space \(\mathcal{X}^n\) fulfills ATE with constant \(\kappa \geq 1\) if for all \(f : \mathcal{X}^n \to [0,\infty)\), \[\begin{align} \operatorname{Ent}_{\nu}(f) \leq \kappa \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)]. \end{align}\]
Section 3 discusses how this definition can be established, e.g., for multivariate Gaussians. For now, we keep working with this abstract definition and establish McDiarmid’s inequality for all measures fulfilling ATE. For the special case of \(1\)-ATE and product measures, these arguments recover Theorem 1. We want to reiterate that the proof hereafter is entirely known and based on the proof of [7].
Theorem 2. McDiarmid’s Inequality under ATE
Let \(X \sim \nu\) on \(\mathcal{X}^n\) that fulfills \(\kappa\)-ATE. Assume \(f : \mathcal{X}^n \to \mathbb{R}\) fulfills the bounded differences property with constants \(c = (c_1,...,c_n)^{\top}\). Then, for all \(t > 0\) we have \[\begin{align} \mathbb{P}\left(|f(X) - \mathbb{E}[f(X)]| \geq t\right) &\leq 2\exp\left(-\frac{2t^2}{\kappa \|c\|_{2}^2}\right). \end{align}\]
Remark 1. There are multiple extensions of Theorem 1, many of which should also extend to 2, e.g., when bounded differences only holds with high probability ([43], [44]) or the \(c_i\) are functions of all entries but \(x_i\), i.e., functions of \(x_{-i}\) ([7]).
Proof. This proof combines ATE with Hoeffding’s Lemma and the Herbst Argument outlined in Subsection 2.2. Concretely, by \(\kappa\)-ATE and using the test function \(\phi(x) := \exp(\lambda f(x))\) with \(\lambda > 0\) we have the following line of arguments where the second inequality \((\star)\) remains to be shown: \[\begin{align} \operatorname{Ent}_{\nu}(\exp(\lambda f)) &\leq \kappa \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(\exp(\lambda f))] \overset{(\star)}\leq \kappa \cdot \mathbb{E}\left[\sum_{i=1}^n \frac{c_i^2 \lambda^2}{8} \mathbb{E}\left[\exp(\lambda f(X)) |X_{-i}\right]\right] \\ &= \kappa \cdot \sum_{i=1}^n \frac{c_i^2 \lambda^2}{8} \mathbb{E}\left[\exp(\lambda f(X))\right] = \frac{\lambda^2 \kappa\|c\|_{2}^2}{8} \mathbb{E}\left[\exp(\lambda f(X))\right]. \end{align}\]
The bound \(\operatorname{Ent}_{\nu(\cdot | X_{-i})}(\exp(\lambda f)) \leq \frac{c_i^2\lambda^2}{8} \mathbb{E}[\exp(\lambda f(X))|X_{-i}]\) will hold by a specific form of Hoeffding’s Lemma that is suitable for applying the Herbst Argument (See Corollary 1 and Lemma 2).
As \(f\) does not have conditional mean zero, we work with the centered \(g_{X_{-i}}(x_i) := f(X_{-i}, x_i) - m_i\) where \(m_i = \mathbb{E}[f(X_{-i}, X_i)|X_{-i}]\). Then, by the bounded differences property of \(f\) it holds that \[\begin{align} \sup_{x_i \in \mathbb{R}} g_{X_{-i}}(x_i) - \inf_{x_i^\prime \in \mathbb{R}} g_{X_{-i}}(x_i^\prime) = \sup_{x_i, x_i^\prime \in \mathbb{R}} |g_{X_{-i}}(x_i) - g_{X_{-i}}(x_i^\prime)| \leq c_i. \end{align}\]
Above, \(g_{X_{-i}}(x_i) \in [a_i,b_i]\) where \(b_i-a_i = c_i\) and since \(g_{X_{-i}}(x_i)\) also has zero mean, by Corollary 1, \[\begin{align} \operatorname{Ent}_{\nu(\cdot|X_{-i})}(\exp(\lambda g_{X_{-i}})) &\leq \frac{c_i^2 \lambda^2}{8} \mathbb{E}[\exp(\lambda g_{X_{-i}}(X_i))| X_{-i}], \\ \Leftrightarrow e^{-\lambda m_i} \cdot \operatorname{Ent}_{\nu(\cdot|X_{-i})}(\exp(\lambda f)) &\leq \frac{c_i^2 \lambda^2}{8} \mathbb{E}[\exp(\lambda f(X))| X_{-i}] \cdot e^{-\lambda m_i}. \end{align}\]
Here, the second line holds by homogeneity of the entropy shown in Auxiliary Result 12. Dividing by \(e^{-\lambda m_i}\) thus justifies the main inequality \((\star)\). Now, the Herbst Argument of Lemma 2 is applicable and for all \(\lambda > 0\) the following bound on the moment generating function of \(f\) holds \[\begin{align} \mathbb{E}[\exp(\lambda (f(X)-\mathbb{E}[f(X)]))] \leq \exp\left(\frac{\lambda^2 \kappa \|c\|_{2}^2/4}{2}\right). \end{align}\]
Accordingly, a standard Chernoff bound and the choice \(\lambda = \frac{4t}{\kappa\|c\|_{2}^2}\) recover the one-sided statement: \[\begin{align} \mathbb{P}\left(f(X) - \mathbb{E}[f(X)] \geq t\right) &\leq \exp(-\lambda t) \cdot \mathbb{E}[\exp\left(\lambda(f(X) - \mathbb{E}[f(X)])\right)] \\ &\leq \exp(-\lambda t) \exp\left(\frac{\lambda^2 \kappa\|c\|_{2}^2/4}{2}\right) = \exp\left(-\frac{t^2}{\frac{\kappa}{2} \|c\|_{2}^2}\right). \end{align}\]
The two-sided bound follows by noting that \(-f\) also fulfills the bounded difference property. ◻
In this subsection we focus on the Herbst Argument at the core of the McDiarmid’s proof in the previous section and show how its main condition can be established using Hoeffding’s Lemma.
Lemma 2. Herbst Argument (Proposition 2.14, [45])
Let \(X \sim \nu\) where \(\nu\) is a probability measure on \(\mathbb{R}\). Suppose there exists \(v \in (0, \infty)\) s.t. for all \(\lambda > 0\) it holds that \(\operatorname{Ent}_{\nu}(\exp(\lambda X)) \leq \frac{\lambda^2v}{2} \mathbb{E}[\exp(\lambda X)]\). Then, for every \(\lambda > 0\) we have \[\begin{align} \mathbb{E}[\exp(\lambda (X-\mathbb{E}[X)])] \leq \exp\left(\frac{\lambda^2v}{2}\right). \end{align}\]
The Herbst Argument translates control of the entropy of test functions \(\phi(x) := \exp(\lambda x)\) for all \(\lambda > 0\) into sub-Gaussian control on a random variable’s moment generating function. For the proof of McDiarmid’s the argument’s condition can be established using Hoeffding’s Lemma.
Lemma 3. Hoeffding’s Lemma (Lemma 2.2, [7])
Let \(X \sim \nu\) have zero mean and \(X \in [a,b]\), \(\nu\)-almost surely. Then, \(X\) is \(\sigma^2\)-sub-Gaussian with \(\sigma^2 := \frac{(b-a)^2}{4}\) and for the cumulant generating function \(\psi(\lambda) := \log(\mathbb{E}[\exp(\lambda X)])\) we have \(\psi^{\prime\prime}(\lambda) \leq \sigma^2\).
Hoeffding’s Lemma has Hoeffding’s inequality as an immediate consequence (See [7]). The following corollary of Hoeffding’s Lemma reformulates it to be of the form needed to apply the Herbst Argument. While this route would be overly complicated to establish Hoeffding’s inequality, it is needed to exploit the conditional boundedness provided by the bounded difference property assumed by McDiarmid’s.
Corollary 1. Hoeffding’s Lemma for Herbst Argument (Page 166, [7])
Let \(X \sim \nu\) have zero mean and \(X \in [a,b]\), \(\nu\)-almost surely. Then, we have \[\begin{align} \operatorname{Ent}_{\nu}(\exp(\lambda X)) \leq \frac{(b-a)^2\lambda^2}{8} \mathbb{E}\left[\exp(\lambda X)\right]. \end{align}\]
Proof. In the argument to follow, we show the equality below, where the subsequent inequality is a direct application of Hoeffding’s Lemma 3 stating that \(\psi^{\prime\prime}(\lambda) \leq \frac{(b-a)^2}{4}\): \[\begin{align} \lambda \psi^\prime(\lambda) - \psi(\lambda) \overset{(\star)}= \int_0^\lambda \theta \psi^{\prime\prime}(\theta) d\theta \leq \frac{(b-a)^2\lambda^2}{8}. \end{align}\]
Using the definition of \(\psi^\prime(\lambda)\) expanding the left hand side above yields \[\begin{align} \lambda \psi^\prime(\lambda) - \psi(\lambda) &= \lambda \left(\log(\mathbb{E}[\exp(\lambda X))]\right)^\prime - \log(\mathbb{E}[\exp(\lambda X)]) = \frac{\mathbb{E}[\lambda X \exp(\lambda X)]}{\mathbb{E}[\exp(\lambda X)]} - \log(\mathbb{E}[\exp(\lambda X)]) \\ &= \frac{1}{\mathbb{E}[\exp(\lambda X)]} \underbrace{\left(\mathbb{E}[\log(\exp(\lambda X)) \exp(\lambda X)] - \mathbb{E}[\exp(\lambda X)] \log(\mathbb{E}[\exp(\lambda X)])\right)}_{\operatorname{Ent}_{\nu}(\exp(\lambda X))}. \end{align}\]
Using this form of the left hand side recovers the statement. Hence, it only remains to show that \((\star)\) is indeed valid. To do so, we define \(F(\lambda) := \lambda \psi^\prime (\lambda) - \psi(\lambda)\). Now, \[\begin{align} F^\prime(\lambda) = \frac{d}{d\lambda} (\lambda \psi^\prime(\lambda)) - \frac{d}{d\lambda} \psi(\lambda) = \psi^\prime(\lambda) + \lambda \psi^{\prime\prime}(\lambda) - \psi^\prime(\lambda) = \lambda \psi^{\prime\prime}(\lambda). \end{align}\]
The Fundamental Theorem of Calculus and the fact that \(F(0) = 0\) as \(\psi(0) = \log(\mathbb{E}[\exp(0 X)]) = 0\) now recover the missing equality \((\star)\): \[\begin{align} \int_0^\lambda \theta \psi^{\prime\prime}(\theta) d\theta = F(\lambda) - F(0) = \lambda \psi^\prime(\lambda) - \psi(\lambda). \end{align}\] ◻
In this section we first prove ATE for well-conditioned Gaussians and afterwards discuss a generalization and tightening of this result due to [1].
Besides its importance for McDiarmid’s, ATE is particularly central in the study of Gibbs samplers in Markov chain mixing (See e.g., [31], [33]–[35], [38], [39]), as it implies that \(O(\kappa n \log(1/\varepsilon))\) steps suffice to reduce the total variation distance and Kullback-Leibler divergence between the sample and stationary measure below \(\varepsilon > 0\) ([1]).
Stochastic localization is a recent tool in the study of high-dimensional probability measures that was first introduced by [46]. Thereafter, it led to multiple breakthroughs towards proving the KLS conjecture posed in [47] ([48]–[52]). Moreover, it proved to be a versatile tool in Markov chain mixing ([35], [38], [53], [54]). For detailed overviews on stochastic localization and connections to related works, see the recent surveys by [55], [56].
We use stochastic localization to establish ATE for Gaussians \(\mathcal{N}(\mu, \Sigma)\) on \(\mathbb{R}^n\) with constant proportional to the condition number \(\kappa(\Sigma)\). We present this proof both to provide an independent derivation of ATE for the relevant case of multivariate Gaussians and because it is the simplest application of stochastic localization known to the authors. It therefore yields insights into the technique in a simple setting where intuition can also be gained through more elementary perspectives.
The central object in stochastic localization is the following stochastic localization process.
Definition 4. Stochastic Localization Process
Let \(\nu\) be a probability measure on \(\mathbb{R}^n\) and \(B_t\) a standard Brownian motion in \(\mathbb{R}^n\) adapted to a filtration \((\mathcal{F}_t)_{t\geq0}\). Let \((C_t)_{t \geq 0}\) be an \(\mathcal{F}_t\)-measurable process where \(C_t \in \mathbb{R}^{n\times n}\) and \(C_t \succ 0\). Then, we call the following measure-valued stochastic process a stochastic localization process \[\begin{align} d\nu_t(x) \propto F_t(x)d\nu(x), \end{align}\]
where \(F_t\) solves the SDEs \(F_0(x) = 1\) and \(dF_t(x) = F_t(x)(x-\int_{\mathbb{R}^n} yd\nu_t(y))^{\top}C_t dB_t\) for all \(x \in \mathbb{R}^n\).
The behavior of the stochastic localization process is controlled by the process for the driving matrices \(C_t \in \mathbb{R}^{n \times n}\). When restricting the process to a constant driving matrix \(C_t = C \in \mathbb{R}^{n\times n}\), it’s density wrt. to the measure of interest \(\nu\) is given in the following result.
Theorem 3. Explicit Construction of \(\nu_t\) (Theorem 2, [57])
Let \(X_0 \sim \nu_0\), \(C \in \mathbb{R}^n, C \succ 0\), \(W_t\) be a standard Brownian motion and define \(y_t = tX_0 + C^{-1}W_t\). Then, there exists a standard Brownian motion \(B_t\) adapted to the Filtration generated by \(y_t\) s.t. the following Radon-Nikodym derivative is a solution \(F_t(x)\) for the SDE Definition 4: \[\begin{align} \frac{d\nu_t(x)}{d\nu} \propto \exp\left(-\frac{t}{2} x^{\top}C^2 x + y_t ^{\top}C^2 x\right). \end{align}\]
The idea behind entropic stability is that the change in entropy over the evolution of a stochastic localization process can be tracked if the entropy is roughly stable over time \(t \in [0, T]\). This will help us establish ATE for well-conditioned Gaussians, since with the right choice of the driving matrix \(C\) we will be able to transform them into isotropic Gaussians for which 1-ATE holds. The following lemma thereby formalizes how entropy is conserved along the stochastic localization process.
Lemma 4. Approximate Entropy Conservation (Proposition 39, [38])
Let \(\nu_t\) be a stochastic localization process as in Definition 4 with driving matrix \(C_t\). Fix \(T > 0\) and suppose that for all \(t \in [0,T]\) the \(\nu_t\) are \(\epsilon_t\)-entropically stable wrt. \(\psi(x,y) := \frac{1}{2} \|C_t(x-y)\|_{2}^2\). Then, \(\nu_t\) fulfills the following approximate entropy conservation \[\begin{align} \operatorname{Ent}_{\nu}(f) \leq \exp\left(\int_0^T \epsilon_t dt\right) \cdot \mathbb{E}[\operatorname{Ent}_{\nu_T}(f)], \quad \text{for all f : \mathbb{R}^n \to [0,\infty)}. \end{align}\]
Here, entropic stability is formalized in Definition 5 below.
Definition 5. Entropic Stability (Definition 29, [38])
Let \(\nu\) be a probability measure on \(\mathbb{R}^n\) and \(\epsilon > 0\). For all \(v \in \mathbb{R}^n\) let \(\mathcal{T}_v\nu\) be its exponential tilt defined through \(\frac{d\mathcal{T}_v \nu(x)}{d\nu} \propto \exp(v^{\top}x)\). The measure \(\nu\) fulfills \(\epsilon\)-entropic stability wrt. \(\psi : \mathbb{R}^n \times \mathbb{R}^n \to (0, \infty)\) if \[\begin{align} \psi\left(\int_{\mathbb{R}^n} x d\mathcal{T}_v\nu(x), \int_{\mathbb{R}^n} x d\nu(x)\right) \leq \epsilon \operatorname{D}_{KL}(\mathcal{T}_v \nu || \nu), \quad \text{for all} \quad v \in \mathbb{R}^n. \end{align}\]
The question now arises how entropic stability can be established. Luckily, for the entropic stability wrt. \(\psi(x,y) = \frac{1}{2} \|C_t(x-y)\|_{2}^2\) as required by Lemma 4 this can be done via covariance bounds.
Lemma 5. Entropic Stability from Covariance Bounds (Lemma 40, [38])
Let \(\nu\) be a measure on \(\mathbb{R}^n\) and \(C,A \in R^{n \times n}\) fulfill \(A,C \succ 0\). Suppose that \(\operatorname{Cov}_{\mathcal{T}_v \nu}(X) \preceq A\) for all \(v \in \mathbb{R}^n\). Then, \(\nu\) is \(\|CAC\|_{op}\)-entropically stable wrt. \(\psi(x,y) = \frac{1}{2} \|C(x-y)\|_{2}^2\).
It is now only an exercise to prove that the covariance of strongly log-concave measures is bounded.
Corollary 2. Covariance Bound for Tilts of Strongly Log-Concave Measures
Let \(\nu\) on \(\mathbb{R}^n\) be \(\alpha\)-strongly log-concave. Then, for all \(v \in \mathbb{R}^n\) the \(\mathcal{T}_v \nu(x) \propto \exp(v^{\top}x) d\nu(x)\) fulfill \[\begin{align} \operatorname{Cov}_{\mathcal{T}_v \nu}(X) \preceq 1/\alpha \cdot I_n. \end{align}\]
Proof. As we assume \(\nu\) has a density, by definition for all \(v \in \mathbb{R}^n\) the exponential tilt is of the form \[\begin{align} \mathcal{T}_v \nu(x) \propto \exp(v^{\top}x) \nu(x) \propto \exp(-V(x) + v^{\top}x). \end{align}\]
With \(Z\) the normalizing constant, taking a logarithm and derivatives yields \[\begin{align} \log(\mathcal{T}_v \nu(x)) &= - V(x) + v^{\top}x + Z \\ \nabla_x \log(\mathcal{T}_v \nu(x)) &= -\nabla_x V(x) + v \\ \nabla_x^2 \log(\mathcal{T}_v \nu(x)) &= -\nabla_x^2 V(x) \end{align}\]
Now, we have \(-\nabla_x^2 \log(\mathcal{T}_v \nu(x)) = \nabla_x^2 V(x) \succeq \alpha I_n\) and therefore the exponential tilt is also strongly log-concave. By the Bakry-Emery criterion in Theorem 10 we then have \[\begin{align} \operatorname{Ent}_{\mathcal{T}_v \nu}(f^2) \leq \frac{2}{\alpha} \cdot \mathbb{E}[\|\nabla f(X)\|_{2}^2], \quad \text{and} \quad \operatorname{Var}_{\mathcal{T}_v \nu}(f) \leq \frac{1}{\alpha} \cdot \mathbb{E}[\|\nabla f(X)\|_{2}^2]. \end{align}\]
Choosing \(f(x) = \theta^{\top}x\) for any \(\theta \in \mathbb{R}^n\) we obtain \(\operatorname{Cov}_{\mathcal{T}_v \nu}(X) \preceq 1/\alpha \cdot I_n\). ◻
It remains to connect ATE to entropy conservation. For this, we implement the idea that we take a measure of interest, transform it into a product measure where 1-ATE holds and conserve entropy along this evolution. Following the proof of [35] we obtain:
Corollary 3. ATE from Entropy Conservation
Let \(\nu_t\) be a stochastic localization process as in Definition 4. Suppose that \(\nu_t\) fulfills \(\gamma_T\)-approximate entropy conservation as in Lemma 4 over times \(t \in [0,T]\) and \(\nu_T\) is a product measure. Then, \[\begin{align} \operatorname{Ent}_{\nu}(f) \leq \gamma_T \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)]. \end{align}\]
Proof. The proof is by the following line of inequalities: \[\begin{align} \operatorname{Ent}_{\nu}(f) &\leq \gamma_T \cdot \mathbb{E}[\operatorname{Ent}_{\nu_T}(f)] \\ &\leq \gamma_T \cdot \mathbb{E}[\sum_{i=1}^n \mathbb{E}_{X_{-i} \sim \nu_T K}[\operatorname{Ent}_{\nu_T(\cdot | X_{-i})}(f)]] \\ &\leq \gamma_T \cdot \sum_{i=1}^n \mathbb{E}_{X_{-i} \sim \nu K}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)]. \end{align}\]
The first inequality holds by \(\gamma_T\)-approximate entropy conservation. The second by entropy tensorization of Lemma 1 that is applicable as \(\nu_T\) is a product measure. The third inequality holds by Lemma 6 where \(K(x,A) = \mathbf{1}{\{x_{-i} \in A\}}\) and hence \(\nu | K \triangleright x_{-i} = \nu(\cdot | x_{-i})\). ◻
Lemma 6. Supermartingality of Entropy (Lemma 39, [35])
Assume \(\nu_t\) is a stochastic localization process as in Definition 4. Let \(K\) be any Markov kernel. Then, the stochastic process \(t \mapsto \mathbb{E}_{y\sim \nu_t K}[\operatorname{Ent}_{\nu_t | K \triangleright y}(f)]\) is a supermartingale. Let \((\mathcal{F}_t)_{t\geq 0}\) be the filtration generated by the Brownian motion \(B_t\) of the process. Equivalently, for all \(0 \leq s < t\) \[\begin{align} \mathbb{E}[\mathbb{E}_{y\sim \nu_t K}[\operatorname{Ent}_{\nu_t | K \triangleright y}(f)] | \mathcal{F}_s] \leq \mathbb{E}_{y\sim \nu_s K}[\operatorname{Ent}_{\nu_s | K \triangleright y}(f)]. \end{align}\]
ATE for well-conditioned Gaussians now follows by collecting all of these results.
Theorem 4. ATE for Gaussians
Let \(\mathcal{N}\) be the multivariate Gaussian probability measure with mean \(\mu \in \mathbb{R}^n\) and covariance matrix \(\Sigma \in \mathbb{R}^{n\times n}\) s.t. \(\Sigma \succ 0\). Then, with \(X \sim \mathcal{N}\) the following ATE holds: \[\begin{align} \operatorname{Ent}_{\mathcal{N}}(f) \lesssim \kappa(\Sigma) \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\mathcal{N}(\cdot | X_{-i})}(f)]. \end{align}\]
Proof. This proof is inspired by the proof of [35] that derives ATE for SK-models with well-behaved interaction matrices in the high-temperature regime.
As entropy is invariant to shifts of the mean \(\mu\), we can show the statement for a zero-mean Gaussian. Let \(\nu\) be the \(n\)-dimensional Gaussian measure \(\mathcal{N}(0,\Sigma)\). Hence, its density is \[\begin{align} \nu(x) \propto \exp\left(-\frac{1}{2} x^{\top}\Sigma^{-1}x\right). \end{align}\]
Using the explicit construction of a stochastic localization process in Theorem 3 with \(\nu_0 := \nu\), positive definite driving matrix \(C\) and process \(y_t = t X_0 + C^{-1}B_t\) yields the following Radon-Nikodym derivatives wrt. \(\nu\) and Lebesgue measure \[\begin{align} \frac{d\nu_t(x)}{d\nu} \propto \exp\left(-\frac{t}{2} x^{\top}C^2 x + y_t ^{\top}C^2 x\right), \quad \nu_t(x) \propto \exp\left(-\frac{1}{2} x^{\top}(\Sigma^{-1}+ tC^2) x + y_t^{\top}C^2 x\right). \end{align}\]
We would like to choose \(C \succ 0\) s.t. \(\Sigma^{-1}+ TC^2 = c I_n\) for some \(c > 0\) as this would allow us to apply Corollary 3 because \(\nu_T\) would be a product measure. For any \(\varepsilon > 0\), we can obtain this with \[\begin{align} c := (1+\varepsilon) \lambda_{\max}{(\Sigma^{-1})} > \lambda_{\max}{(\Sigma^{-1})} \quad \text{and} \quad C := \sqrt{1/T} \cdot (cI_n - \Sigma^{-1})^{1/2} \succ 0. \end{align}\]
With these choices \(\nu_T\) then indeed is a product measure, since \[\begin{align} TC^2 = T/T \cdot (cI_n - \Sigma^{-1}) = (cI_n - \Sigma^{-1}). \end{align}\]
We further show that \(\nu_t\) are strongly log-concave for all \(t \in [0,T]\): \[\begin{align} -\nabla_x^2 \log(\nu_t(x)) = \Sigma^{-1}+ tC^2 &= \Sigma^{-1}+ t/T \cdot (cI_n - \Sigma^{-1}) \\ &= (1-t/T) \cdot \Sigma^{-1}+ t/T \cdot cI_n \\ &\succeq ((1-t/T) \cdot \lambda_{\min}{(\Sigma^{-1})} + t/T \cdot c) I_n \\ &= (\lambda_{\min}{(\Sigma^{-1})} + t/T \cdot (c - \lambda_{\min}{(\Sigma^{-1})})I_n =: \alpha_t I_n. \end{align}\]
Now, by Corollary 2 we have \(\operatorname{Cov}_{\mathcal{T}_v \nu}(X) \preceq 1/\alpha_t \cdot I_n\) and thus by Lemma 5 \(\nu_t\) is \(\epsilon_t\)-entropically stable wrt. the function \(\psi(x,y) = \frac{1}{2} \|C(x-y)\|_{2}^2\) where \[\begin{align} \epsilon_t := \frac{1}{T\alpha_t} \|cI_n - \Sigma^{-1}\|_{op} = \frac{c-\lambda_{\min}{(\Sigma^{-1})}}{T\lambda_{\min}{(\Sigma^{-1})} + t(c - \lambda_{\min}{(\Sigma^{-1})})} = \frac{c-d}{Td + t(c-d)}. \end{align}\]
Here, \(d: = \lambda_{\min}{(\Sigma^{-1})}\). Entropic stability lets us apply Lemma 4 by which we have \(\mathbb{E}[\operatorname{Ent}_{\nu_T}(f)] \geq \exp(-\int_0^T \epsilon_t dt) \cdot \operatorname{Ent}_{\nu_0}(f)\). By Corollary 3 we translate this into the following ATE: \[\begin{align} \operatorname{Ent}_{\nu}(f) &\leq \exp\left(\int_0^T \epsilon_t dt\right) \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)] \\ &\leq \exp\left(\left[\log(Td + t(c-d))\right]^T_0\right) \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)] \leq \frac{c}{d} \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)]. \end{align}\]
The statement follows as \(\lambda_{\min}{(\Sigma^{-1})} = 1/\lambda_{\max}{(\Sigma)}\) and \(\lambda_{\max}{(\Sigma^{-1})} = 1/\lambda_{\min}{(\Sigma)}\) and thus \[\begin{align} \frac{c}{d} = (1+\varepsilon) \cdot \frac{\lambda_{\max}{(\Sigma^{-1})}}{\lambda_{\min}{(\Sigma^{-1})}} = (1+\varepsilon) \cdot \frac{\lambda_{\max}{(\Sigma)}}{\lambda_{\min}{(\Sigma)}} = (1+\varepsilon) \cdot \kappa(\Sigma). \end{align}\] ◻
[1] approach ATE through a variational characterization of the kernel of the Gibbs sampler in terms of Kullback-Leibler divergences. They exploit that the kernel of the Gibbs sampler is invariant under coordinate-wise transformations, which allows them to lower bound the decay of Kullback-Leibler divergence using carefully chosen transport maps that preserve the block structure a Gibbs sampler operates on. With this approach, they derive an ATE for a class of measures with densities \(\nu(x) \propto \exp(-V(x))\) that is a superset of strongly log-concave and log-smooth measures and which is characterized by Assumption 1 placed on their potential \(V : \mathbb{R}^n \to \mathbb{R}\).
Assumption 1. Strong Condition
Let \(V_m : \mathbb{R}^{n_m} \to \mathbb{R}\) be convex for all \(m \in [M]\) and let \(V : \mathbb{R}^n \to \mathbb{R}\) with \(n = n_1 +\dotsm+ n_M\) be \[\begin{align} V(x) = V_0(x) + \sum_{m=1}^M V_m(x_m), \end{align}\]
where \(V_0 : \mathbb{R}^n \to \mathbb{R}\) is continuously differentiable and
\(x_m \mapsto V_0(x_m, y_{-m})\) is \(L_m\)-smooth for all \(y_{-m} \in \mathbb{R}^{n_m}\) and \(m \in [M]\),
\(x \mapsto V_0(x) - \frac{\lambda^\star}{2} \sum_{m=1}^M L_m \|x_m\|_{2}^2\) is convex.
Further, suppose that \(\lambda^\star > 0\) and call \(\kappa^\star = {\lambda^\star}^{-1}\) the coordinate-wise condition number of \(V\).
As this assumption on the potential \(V\) might be hard to verify, [1] provide the following weaker condition under which Assumption 1 holds.
Lemma 7. Weak Condition (Lemma 2.4, [1])
Let \(\nu\) on \(\mathbb{R}^n\) be an \(\alpha\)-strongly log-concave and \(\beta\)-log-smooth probability measure with density \(\nu(x) \propto \exp(-V(x))\). Then, \(V : \mathbb{R}^n \to \mathbb{R}\) satisfies the conditions in Assumption 1 with \(\kappa = \beta/\alpha \geq \kappa^\star \geq 1\).
Imposing Assumption 1 on the potential \(V\) of the measure of interest \(\nu\) on \(\mathbb{R}^n\), they prove:
Theorem 5. ATE for Well-Conditioned Measures (Theorem 3.1, [1])
Let the probability measure \(\nu\) on \(\mathbb{R}^n\) have density \(\nu(x) \propto \exp(-V(x))\) where \(V : \mathbb{R}^n \to \mathbb{R}\) fulfills Assumption 1. Then, with \(X \sim \nu\) we have \[\begin{align} \operatorname{Ent}_{\nu}(f) \leq \kappa^\star \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\nu(\cdot | X_{-i})}(f)]. \end{align}\]
For Gaussian measures \(\mathcal{N}(\mu, \Sigma)\) on \(\mathbb{R}^n\), this general ATE implies that our previously derived \(\kappa(\Sigma)\)-ATE is not tight. Instead, computing the tight constant \(\kappa^\star\) obtained through verifying Assumption 1 for such Gaussians yields the \(\kappa^\star(\Sigma)\)-ATE in Lemma 8 below where \(\kappa^\star(\Sigma) := \lambda_{\max}{(D^{1/2} \Sigma D^{1/2})}\) and \(D = \operatorname{diag}(\Sigma^{-1})\). This \(\kappa^\star(\Sigma)\) is the maximum eigenvalue of the precision standardized covariance matrix instead of the condition number and \(\kappa^\star(\Sigma) \leq \kappa(\Sigma)\).
Lemma 8. Tight ATE for Gaussians (Lemma 3.10, [1])
Let \(\mathcal{N}\) be the multivariate Gaussian probability measure with mean \(\mu \in \mathbb{R}^n\) and covariance matrix \(\Sigma \in \mathbb{R}^{n \times n}\) and let \(X \sim \mathcal{N}\). Then, with \(\kappa^\star(\Sigma) := \lambda_{\max}{(D^{1/2} \Sigma D^{1/2})}\) where \(D := \operatorname{diag}(\Sigma^{-1})\) we have \[\begin{align} \operatorname{Ent}_{\mathcal{N}}(f) \leq \kappa^\star(\Sigma) \cdot \sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\mathcal{N}(\cdot | X_{-i})}(f)]. \end{align}\]
While [1] discuss the implications of their work on mixing times of the Gibbs sampler and their relation to coordinate-wise algorithms in optimization, they do not highlight the consequences for Hamming-Lipschitz concentration. Corollary 4 below summarizes the important Gaussian case obtained by plugging the \(\kappa^\star(\Sigma)\)-ATE into Theorem 2. This is the inequality we refer to as Gaussian Hamming-Lipschitz concentration and which we believe to have many potential applications across mathematical statistics, learning theory and theoretical computer science.
Corollary 4. Gaussian Hamming-Lipschitz Concentration
Let \(X \sim \mathcal{N}(\mu, \Sigma)\) on \(\mathbb{R}^n\) with \(\Sigma \in \mathbb{R}^{n \times n}\). Assume \(f : \mathbb{R}^n \to \mathbb{R}\) fulfills the bounded differences property with constants \(c = (c_1,...,c_n)^{\top}\). Then, with \(\kappa^\star(\Sigma) := \lambda_{\max}{(D^{1/2} \Sigma D^{1/2})}\) where \(D := \operatorname{diag}(\Sigma^{-1})\), \[\begin{align} \mathbb{P}\left(|f(X) - \mathbb{E}[f(X)]| \geq t\right) \leq 2\exp\left(-\frac{2t^2}{\kappa^\star(\Sigma) \|c\|_{2}^2}\right) \quad \text{for all t > 0}. \end{align}\]
Remark 2. Note again that \(\kappa^\star(\Sigma) \leq \kappa(\Sigma)\) and equality holds only in the case when \(\Sigma = cI_n\) for \(c > 0\). Importantly, \(\kappa^\star(\Sigma)\) can indeed be infinitely smaller as can be seen in the following example: \[\begin{align} \Sigma := \begin{pmatrix} s & 0 \\ 0 & 1 \end{pmatrix} \quad \text{where s > 1}. \end{align}\]
Then, \(\kappa(\Sigma) = s\) but \(\kappa^\star(\Sigma) = 1\) and hence as \(s \to \infty\) the condition number diverges.
McDiarmid’s inequality has many applications in combinatorial problems as presented in [14], [7] or [9]. Examples of classical statistical problems where the inequality can be applied are the concentration of U-statistics or the \(L_1\)-norm error of kernel density estimators ([9]) as well as generalization bounds for cross-validation (See e.g., [58], [59]). In mathematical statistics and learning theory McDiarmid’s is used to establish uniform laws of large numbers via Rademacher complexities as in [9] or generalization bounds through algorithmic stability ([60], [61].
Here, we present three examples where McDiarmid’s under dependence (Theorem 2) can be applied for simple but very different problems. We thereby do not try to be exhaustive but want to provide examples that might spark the imagination of readers to come up with applications of Gaussian Hamming-Lipschitz concentration in their own fields of expertise.
The following question was pitched to us by Simone Bombari:
When does the random vector \(\operatorname{sign}(X) \in \{{\pm 1}\}^n\) where \(X \sim \mathcal{N}(\mu, \Sigma)\) with \(\mu \in \mathbb{R}^n\) and \(\Sigma \in \mathbb{R}^{n\times n}\) fulfill dimension-free sub-Gaussian concentration in the sense of Definition 6?
Definition 6. Sub-Gaussian Vector
\(X \in \mathbb{R}^n\) is a \(\sigma^2\)-sub-Gaussian vector if there exists \(\sigma^2 > 0\) s.t. \[\begin{align} \mathbb{E}\left[\exp\left(u^{\top}X - \mathbb{E}[u^{\top}X]\right)\right] \leq \exp\left(\frac{\sigma^2\|u\|_{2}^2}{2}\right) \quad \text{for all u \in \mathbb{R}^n}. \end{align}\]
Besides being an interesting exercise in high-dimensional probability, this question has applications in the analysis of deep neural networks via Neural Tangent Kernels (See e.g., [62]).
When \(\Sigma = I_n\) the question can easily be answered using McDiarmid’s inequality, but if \(\Sigma \not\asymp I_n\) the classical concentration inequalities including Gaussian Lipschitz concentration fail to apply directly. However, Theorem 2 immediately provides a strong answer for measures fulfilling ATE and thus well-conditioned multivariate Gaussians and strongly log-concave and log-smooth distributions.
Corollary 5. Sub-Gaussianity of Sign-Quantized Vectors under ATE
Let \(X \sim \nu\) and \(\nu\) on \(\mathbb{R}^n\) fulfill \(\kappa\)-ATE. Then, \(\operatorname{sign}(X) \in \{{\pm 1}\}^n\) is \(\kappa\)-sub-Gaussian.
Remark 3. Recall that if \(\nu\) is \(\alpha\)-strongly log-concave and \(\beta\)-log-smooth, Assumption 1 holds with \(\kappa^\star \leq \kappa := \beta/\alpha\) by Lemma 7 and hence \(\nu\) fulfills \(\kappa\)-ATE by Theorem 5. For a Gaussian \(X \sim \mathcal{N}(\mu,\Sigma)\) this suggests that \(\operatorname{sign}(X)\) is at least \(\kappa(\Sigma)\)-sub-Gaussian. Relying instead on Lemma 8 improves this to \(\kappa^\star(\Sigma)\)-sub-Gaussianity with \(\kappa^\star(\Sigma) := \lambda_{\max}{(D^{1/2} \Sigma D^{1/2})}\) where \(D := \operatorname{diag}(\Sigma^{-1})\).
Proof. We prove the statement by an application of McDiarmid’s inequality.
Define \(f(x) := u^{\top}\operatorname{sign}(x)\) for all \(u \in \mathbb{R}^n\). Then, for all \(x, y \in \mathbb{R}^n\) with Hamming distance \(d_H(x,y) \leq 1\) where the \(k\)-th entries differ, it holds that \[\begin{align} \left|f(x)-f(y)\right| &= \left|u^{\top}(\operatorname{sign}(x)-\operatorname{sign}(y))\right| = \left|\sum_{i=1}^n u_i (\operatorname{sign}(x_i) - \operatorname{sign}(y_i))\right| \\ &= |u_k (\operatorname{sign}(x_k) - \operatorname{sign}(y_k))| \leq |u_k| |\operatorname{sign}(x_k) - \operatorname{sign}(y_k)| \leq 2 |u_k| =: c_k. \end{align}\]
This means that \(f\) fulfills the bounded difference condition with \(\|c\|_{2}^2 = 4 \|u\|_{2}^2\). Theorem 2 yields \[\begin{align} \mathbb{E}[\exp(\lambda (u^{\top}\operatorname{sign}(X)-\mathbb{E}[u^{\top}\operatorname{sign}(X)])] &\leq \exp\left(\frac{\lambda^2 \kappa \|u\|_{2}^2}{2}\right) \quad \text{for all \lambda > 0}. \end{align}\]
Choosing \(\lambda = 1\) recovers the statement. ◻
During the preparation of this manuscript [63] provided an alternative proof for the sub-Gaussianity of \(\operatorname{sign}(X)\) where \(X \sim \mathcal{N}(0, \Sigma)\) with variance proxy of the order \(O(\kappa(\Sigma))\). Their elementary proof decomposes \(X\) into the sum of two Gaussians and exploits Gaussian Lipschitz concentration after smoothing the \(\operatorname{sign}\)-function with one of them. Hence, it is restricted to Gaussians and happens to be less tight in the constants that are involved.
Erdős-Rényi graphs (ERG) are a powerful model in graph theory and complex networks. An ERG is a graph with \(n\) nodes where two edges are connected with success probability \(p \in (0,1)\), independently. Many statistics of interest defined on such graphs fulfill variations of the bounded difference property and thus McDiarmid’s inequality and versions thereof are a handy tool for their analysis. In the following, we show how ERGs can be parametrized by Gaussian instead of Bernoulli random variables, which let’s us analyze them using Corollary 4.
Definition 7. Dependent Erdős-Rényi Graph
Let \(X \sim \mathcal{N}(\mu, \Sigma)\) with \(\mu \in \mathbb{R}^{N}\) and \(\Sigma \in \mathbb{R}^{N}\) where \(N = \binom{n}{2}\). Index the mean \(\mu\), covariance \(\Sigma\) and random vector \(X\) by tuples \((i, j) \in [n]^2\) where \(i < j\). We define a dependent Erdős-Rényi graph as a graph \(G_{\mu, \Sigma}(X) := (V, E(X))\) where \(V = [n]\) and \((i,j) \in E(X)\) if \(\mathbf{1}{\{X_{(i,j)} \geq 0\}}\) .
Corollary 6. Control on Marginal Edge Probabilities
For \(\mu^p := \Phi^{-1}(p) \cdot \operatorname{diag}(\Sigma)^{1/2}\) where \(p \in (0,1)\) and \(\Phi : \mathbb{R}\to [0,1]\) is the standard Gaussian CDF, \[\begin{align} \mathbb{P}((i,j) \in E(X)) = p \quad \text{for all (i,j) \in [n]^2 where i<j}. \end{align}\]
Proof. Since \(Z \overset{d}{=} -Z\) for \(Z \sim \mathcal{N}(0,1)\) and \(\mu^p_{(i,j)} = \Phi^{-1}(p) \sqrt{\Sigma_{(i,j), (i,j)}}\) it holds that \[\begin{align} \mathbb{P}((i,j) \in E(X)) &= \mathbb{P}(X_{(i,j)} \geq 0) = \mathbb{P}\left(\frac{X_{(i,j)} - \mu_{(i,j)}}{\sqrt{\Sigma_{(i,j), (i,j)}}} \geq - \frac{\mu_{(i,j)}}{\sqrt{\Sigma_{(i,j), (i,j)}}}\right) = \mathbb{P}\left(Z \geq - \frac{\mu_{(i,j)}}{\sqrt{\Sigma_{(i,j), (i,j)}}}\right) \\ &= \mathbb{P}\left(Z \leq \frac{\mu_{(i,j)}}{\sqrt{\Sigma_{(i,j), (i,j)}}}\right) = \Phi\left(\frac{\mu_{(i,j)}}{\sqrt{\Sigma_{(i,j), (i,j)}}}\right) = \Phi\left(\Phi^{-1}(p)\right) = p. \end{align}\] ◻
Remark 4. \(G_{\mu, \Sigma}(X)\) is a standard ERG with edge probability \(p\) if \(\mu = \mu^p\) and \(\Sigma = I_N\).
The statistic we are interested in in this expository treatment of ERGs is the maximum cut below.
Definition 8. Maximum Cut
For a graph \(G = (V,E)\) and with \(S \sqcup S^c = [n]\) we define the maximum cut as \[\begin{align} \operatorname{MaxCut}(G) := \max_{S \subseteq V} \operatorname{Cut}_S(G) = \max_{S \subseteq V} \sum_{i<j}^n \mathbf{1}{\{(i,j) \in E : |\{{i,j}\} \cap S| = 1\}}. \end{align}\]
Since the maximum cut fulfills the bounded difference property with \(c_i = 1\), we immediately obtain a concentration inequality for the statistic around its expectation.
Lemma 9. Concentration of the Maximum Cut
For a fraction \(\epsilon \in (0,1)\) the maximum cut of the dependent ERG \(G_{\mu^p, \Sigma}(X)\) fulfills \[\begin{align} \mathbb{P}\left(\left|\operatorname{MaxCut}(G_{\mu^p, \Sigma}(X))- \mathbb{E}[\operatorname{MaxCut}(G_{\mu^p, \Sigma}(X))]\right| \geq \epsilon \binom{n}{2}\right) \leq 2\exp\left(-\frac{2 \epsilon^2 \binom{n}{2}}{\kappa^\star(\Sigma)}\right), \end{align}\]
where \(\kappa^\star(\Sigma) := \lambda_{\max}{(D^{1/2} \Sigma D^{1/2})}\) with \(D := \operatorname{diag}(\Sigma^{-1})\) is the ATE constant for \(\Sigma\).
Remark 5. If \(\binom{n}{2}/\kappa^\star(\Sigma) \to \infty\) as \(n \to \infty\) the maximum cut concentrates around its expectation. For \(\kappa^\star(\Sigma) \asymp 1\) the rate of convergence is the same as for a standard ERG where \(\Sigma = I_N\).
Proof. For two graphs \(G, G^\prime\) with edge sets \(E, E^\prime \subseteq \{{(i,j) \in [n]^2 : i < j}\}\) differing in edge \((u,v)\), \[\begin{align} \operatorname{MaxCut}(G) &- \operatorname{MaxCut}(G^\prime) \\ &= \max_{S \subseteq V} \operatorname{Cut}_S(G) - \max_{S \subseteq V} \operatorname{Cut}_S(G^\prime) \leq \max_{S \subseteq V} \operatorname{Cut}_S(G) - \operatorname{Cut}_S(G^\prime) \\ &= \max_{S \subseteq V} \sum_{i<j}^n \mathbf{1}{\{(i,j) \in E : |\{{i,j}\} \cap S| = 1\}} - \mathbf{1}{\{(i,j) \in E^\prime : |\{{i,j}\} \cap S| = 1\}} \\ &= \mathbf{1}{\{(u,v) \in E : |\{{i,j}\} \cap S| = 1\}} - \mathbf{1}{\{(u,v) \in E^\prime : |\{{i,j}\} \cap S| = 1\}} \leq 1. \end{align}\]
By symmetry the same holds with \(G\) and \(G^\prime\) swapped and thus \(\operatorname{MaxCut}\) fulfills bounded differences with \(c_{(i,j)} = 1\). For two \(x, x^\prime \in \mathbb{R}^N\) with \(d_H(x, x^\prime) \leq 1\), their \(G_{\mu^p, \Sigma}(x)\) and \(G_{\mu^p, \Sigma}(x^\prime)\) only differ in one edge and thus the property transfers to \(x \mapsto \operatorname{MaxCut}(G_{\mu^p, \Sigma}(x))\). Hence, for all \(t > 0\), \[\begin{align} \mathbb{P}\left(\left|\operatorname{MaxCut}(G_{\mu^p, \Sigma}(X))- \mathbb{E}[\operatorname{MaxCut}(G_{\mu^p, \Sigma}(X))]\right| \geq t\right) \leq 2\exp\left(-\frac{2t^2}{\kappa^\star(\Sigma) \binom{n}{2}}\right). \end{align}\]
Here, the inequality holds by Corollary 4 and since \(\|c\|_{2}^2 = \binom{n}{2}\). ◻
A fundamental question in empirical process theory is the convergence of the empirical cumulative distribution function (CDF) to its population counterpart. The Dvoretzky-Kiefer-Wolfowitz (DKW) inequality provides an answer to this in the case of i.i.d. random variables where the rate of convergence is \(1/\sqrt{n}\) ([64], [65]). In this application we consider the dependent setting and study the convergence of the empirical CDF towards its population version, the average marginal CDF as defined below.
Definition 9. Cumulative Distribution Functions
Let \(\nu\) be a probability measure on \(\mathbb{R}^n\) and \(X \sim \nu\). Respectively, define the empirical and average marginal cumulative distribution functions at \(x \in \mathbb{R}\) as \[\begin{align} \hat{F}_n(x) := \frac{1}{n} \sum_{i=1}^n \mathbf{1}{\{X_i \leq x\}}, \quad \text{and} \quad \bar F(x) := \mathbb{E}[\hat{F}_n(x)] = \frac{1}{n} \sum_{i=1}^n \mathbb{P}(X_i \leq x). \end{align}\]
[2] derived the following DKW-type inequality when the underlying joint measure \(\nu\) fulfills a log-Sobolev inequality and the average marginal CDF is Lipschitz.
Theorem 6. DKW-type Inequality under LSI (Theorem 1.2, [2])
Let \(X \sim \nu\) on \(\mathbb{R}^n\) where \(\nu\) is a probability measure fulfilling \(\operatorname{LSI}(\rho)\). Assume that the average marginal cumulative distribution function \(\bar F\) is \(M\)-Lipschitz. Then, for any \(r > 0\), \[\begin{align} \mathbb{P}\left(\sup_{x\in\mathbb{R}} |\bar F(x) - \hat{F}_n(x)| \geq r\right) \leq \frac{4}{r} \exp\left(-\frac{2}{27}\frac{nr^3}{\rho M^2}\right). \end{align}\]
We complement this result for measures fulfilling ATE through an application of Theorem 2 combined with a standard bracketing argument.
Theorem 7. DKW-type Inequality under ATE
Let \(X \sim \nu\) on \(\mathbb{R}^n\) where \(\nu\) is a probability measure fulfilling \(\kappa\)-ATE. Assume that the average marginal cumulative distribution function \(\bar F\) is continuous. Then, for any \(r > 0\), \[\begin{align} \mathbb{P}\left(\sup_{x\in\mathbb{R}} |\bar F(x) - \hat{F}_n(x)| \geq r\right) \leq \frac{4}{r} \exp\left(-\frac{nr^2}{2\kappa}\right). \end{align}\]
Remark 6. Theorem 7 improves Theorem 6 in the dependence on \(r^2\) versus \(r^3\). Hence, it achieves the expected \(1/\sqrt n\)-rate of convergence up to logarithms as long as \(\kappa \asymp 1\). While it is unclear which measures exactly fulfill ATE, the class of \(\alpha\)-strongly log-concave and \(\beta\)-log-smooth measures is an intersection between the ones fulfilling ATE and a log-Sobolev inequality (See Theorem 10).
Proof. The proof combines our McDiarmid’s inequality with a standard bracketing argument as can be found in the proof of [2] or [66].
For all \(X, X^\prime \in \mathbb{R}^n\) s.t. \(d_H(X,X^\prime) \leq 1\), let \(k\) index the coordinate in which they differ. Define the corresponding empirical CDFs \(\hat{F}_n(x)\) and \(\hat{F}_n^\prime(x)\) for a fixed \(x \in \mathbb{R}\). Then, we have \[\begin{align} \left|\hat{F}_n(x) - \hat{F}_n^\prime(x)\right| &= \left|\frac{1}{n} \sum_{i=1}^n \mathbf{1}{\{X_i \leq x\}} - \frac{1}{n} \sum_{i=1}^n \mathbf{1}{\{X_i^\prime \leq x\}}\right| \\ &= \frac{1}{n} \left|\sum_{i=1}^n \mathbf{1}{\{X_i \leq x\}} - \mathbf{1}{\{X_i^\prime \leq x\}}\right| \\ &= \frac{1}{n} \left|\mathbf{1}{\{X_k \leq x\}} - \mathbf{1}{\{X_k^\prime \leq x\}}\right| \leq \frac{1}{n} =: c_k. \end{align}\]
Thus, as a function of \(X\), \(\hat{F}_n(x)\) fulfills the bounded difference property with \(\|c\|_{2} = 1/n \cdot \|\mathbf{1}\|_{2} = 1/\sqrt{n}\). Applying McDiarmid’s inequality then yields that for all \(t > 0\) we have \[\begin{align} \mathbb{P}\left(\left|\hat{F}_n(x) - \bar F(x)\right| \geq t\right) = \mathbb{P}\left(\left|\hat{F}_n(x) - \mathbb{E}[\hat{F}_n(x)]\right| \geq t\right) \leq 2\exp\left(-\frac{2t^2}{\kappa \|c\|_{2}^2}\right) = 2\exp\left(-\frac{2nt^2}{\kappa}\right). \end{align}\]
We translate this pointwise guarantee into a uniform one using bracketing. As \(\bar F\) is continuous and increasing, for all \(N \in \mathbb{N}\) we can choose \(N+1\) anchor points \[\begin{align} -\infty = a_0 < a_1 < ... < a_N = \infty \quad \text{s.t.\@{}} \quad \bar F(a_j) - \bar F(a_{j-1}) = \frac{1}{N} \quad \text{for all j \in [N]}. \end{align}\]
For all \(x \in (a_{j-1}, a_j]\) we have \((-\infty, a_{j-1}] \subset (-\infty, x] \subset (-\infty, a_j]\) and thus it holds that \[\begin{align} \mathbf{1}{\{X_i \leq a_{j-1}\}} \leq \mathbf{1}{\{X_i \leq x\}} \leq \mathbf{1}{\{X_i \leq a_j\}} \quad \text{for all i \in [n]}. \end{align}\]
Through summing these over \(i \in [n]\), for the empirical and average marginal CDF we have \[\begin{align} \hat{F}_n(a_{j-1}) \leq \hat{F}_n(x) \leq \hat{F}_n(a_j) \quad \text{and} \quad \bar F(a_{j-1}) \leq \bar F(x) \leq \bar F(a_j). \end{align}\]
Thus, the following upper and lower bounds hold \[\begin{align} \hat{F}_n(x) - \bar F(x) &\leq \hat{F}_n(a_j) - \bar F(x) \leq \hat{F}_n(a_j) - \bar F(a_{j-1}) = \hat{F}_n(a_j) - \bar F(a_j) + 1/N, \\ \hat{F}_n(x) - \bar F(x) &\geq \hat{F}_n(a_{j-1}) - \bar F(x) \geq \hat{F}_n(a_{j-1}) - \bar F(a_j) = \hat{F}_n(a_{j-1}) - \bar F(a_{j-1}) - 1/N. \end{align}\]
Taking absolute values and the maximum over \(j \in [N]\) this yields that for \(x \in R\), \[\begin{align} - \max_{j \in \{{0,...,N}\}} \left|\hat{F}_n(a_j) - \bar F(a_j)\right| - \frac{1}{N} \leq \hat{F}_n(x) - \bar F(x) \leq \max_{j \in \{{0,...,N}\}} \left|\hat{F}_n(a_j) - \bar F(a_j)\right| + \frac{1}{N}. \end{align}\]
Since \(-C \leq y \leq C \Leftrightarrow |y| \leq C\) and because the resulting right hand side is independent of \(x\), \[\begin{align} \sup_{x \in \mathbb{R}} \left|\hat{F}_n(x) - \bar F(x) \right| \leq \max_{j \in \{{0,...,N}\}} \left|\hat{F}_n(a_j) - \bar F(a_j)\right| + \frac{1}{N}. \end{align}\]
Note here, that \(\bar F(a_0) = \hat{F}_n(a_0) = 0\) and \(\bar F(a_N) = \hat{F}_n(a_N) = 1\) and thus we only have to control \(N-1\) terms in the maximum. It remains to do this using a union bound and the pointwise inequality: \[\begin{align} \mathbb{P}\left(\max_{j \in \{{0,...,N}\}} \left|\hat{F}_n(a_j) - \bar F(a_j)\right| \geq t\right) \leq 2 (N-1) \exp\left(-\frac{2nt^2}{\kappa}\right) \leq \frac{4}{r} \exp\left(-\frac{2nt^2}{\kappa}\right). \end{align}\]
Choosing \(N = \lceil \frac{2}{r} \rceil\) for which \(\frac{2}{r} \leq N \leq 1 + \frac{2}{r}\) and \(t = r/2\) then recovers the statement. ◻
Remark 7. For Gaussian measures the derivative of the average marginal CDF is \[\begin{align} \frac{d}{dx} \bar F(x) = \frac{1}{n} \sum_{i=1}^n \frac{d}{dx} \mathbb{P}(X_i \leq x) = \frac{1}{n} \sum_{i=1}^n \frac{1}{\sqrt{2\pi\Sigma_{ii}}} \exp\left(-\frac{(x-\mu_i)^2}{2\Sigma_{ii}}\right) \leq \frac{1}{\sqrt{2\pi}}\frac{1}{n} \sum_{i=1}^n \frac{1}{\sqrt{\Sigma_{ii}}} =: M. \end{align}\]
Both \(\kappa^\star(\Sigma)\) as in Lemma 8 and \(\rho M^2 = M^2\|\Sigma\|_{op}\) are upper bounded by \(\kappa(\Sigma)\). However, they are generally incomparable. If \(\Sigma\) is poorly conditioned due to high correlations \(\kappa^\star(\Sigma)\) blows up whereas \(\rho M^2\) is unaffected by this. In turn, if \(\Sigma\) is poorly conditioned due to scale imbalances across dimensions, \(\rho M^2\) will explode whereas \(\kappa^\star(\Sigma)\) remains bounded.
While the concentration of measure phenomena underlying the presented McDiarmid’s-type concentration inequalities under dependence play an important role in mixing time analyses for Gibbs samplers, they have not yet been exploited more broadly in mathematical statistics, learning theory and theoretical computer science. We believe that this is, because they have not yet been given sufficient attention in the form of McDiarmid’s and thus at a level of abstraction that is suitable for such problems as showcased by our applications. The applications we tackle are thereby only a first step in investigating the influence of dependence on concentration and convergence rates in a broad class of problems that exhibit Gaussian-like dependence and fulfill bounded differences. By analogy to Gaussian Lipschitz concentration, we expect the Gaussian version of McDiarmid’s – Gaussian Hamming-Lipschitz concentration – to be fruitful in many domains and therefore invite researchers to apply it to problems in their specific fields. We think that an iterative back and forth between tools and applications is the most effective approach to extending theory usually built on i.i.d. assumptions to (weakly) dependent cases. The DKW-type inequality derived in Theorem 7 serves as an example for this. On the one hand, it shows that McDiarmid’s under ATE is a useful tool, which combined with standard arguments can improve upon existing theory and establish the expected \(1/\sqrt{n}\)-convergence rate. On the other hand, the comparison to the DKW-type inequality under LSI in Theorem 6 due to [2] raises the question why the constants \(\kappa^\star\) and \(\rho M^2\) capturing the dependence in both cases may behave so differently. Future work should thus investigate whether this difference is merely a proof artifact or if there is an underlying more powerful characterization of dependence at work. One that ATE might not capture.
In this subsection we instantiate the foundational work by [29] to show that her results yield an ATE for Gaussian measures, albeit under more restrictive conditions on the covariance matrix \(\Sigma\) than the results in Section 3. Moreover, we outline when the McDiarmid’s-type inequality in [27] yields dimension-free Gaussian concentration.
Definition 10. Block-Interaction Matrix
Let \(\nu\) be a probability measure on \(\mathbb{R}^n\) with density \(\nu(x) \propto \exp(-V(x))\). Let \(x, y \in \mathbb{R}^n\) and \(z^{(k)}(x,y) := (x_{I_1},..., y_{I_k},..., x_{I_m})^{\top}\). Define the matrix A via its entries for \(k, \ell \in [m]\) and \(i \in I_k, j \in I_\ell\) \[\begin{align} A_{ij}^\rho(x,y) = \frac{1}{\sqrt{\rho_k-\rho} \cdot \sqrt{\rho_\ell-\rho}} \cdot \begin{cases} \nabla_x^2 V(z^{(k)})_{ij} & \text{if k \neq \ell}, \\ 0 & \text{if k = \ell}. \end{cases} \end{align}\]
Assumption 2. Marton’s Necessary Condition
A probability measure \(\mu\) with density \(p(x) \propto \exp(-V(x))\) fulfills this assumption if
The conditional measures \(\nu(\cdot| x_{-I_k})\) are \(\operatorname{LSI}(\rho_k)\) for all \(k \in [n]\),
The matrix \([\nabla_x^2 V(x)]_{I_k} \succeq \gamma I_{|I_k|}\) for \(\gamma \in \mathbb{R}\) for all \(k \in [n]\),
For \(0 < \rho < \min_{k \in [m]} \rho_k\) we have \(\sup_{x,y \in \mathbb{R}^n} \|A^0(x,y)\|_{op} < 1\) and \(\sup_{x,y \in \mathbb{R}^n} \|A^\rho(x,y)\|_{op} \leq 1\).
Theorem 8. Marton’s ATE (Theorem 1 [29])
Let \(\mu\) and \(\nu\) be probability measures on \(\Omega^n\). Suppose \(\mu\) fulfills the conditions in Assumption 2 with constants \(\rho_1,...,\rho_m, \rho > 0\). Then, the following ATE holds \[\begin{align} \operatorname{D_{KL}}(\nu||\mu) \leq \sum_{k=1}^n \frac{\rho_k}{\rho} \cdot \nu\left[\operatorname{D_{KL}}\left(\nu(\cdot | X_{-I_k}) || \mu(\cdot|X_{-I_k})\right)\right]. \end{align}\]
Corollary 7. Marton’s ATE for Gaussians
Let \(\mathcal{N}\) on \(\mathbb{R}^n\) be a multivariate Gaussian with mean \(\mu \in \mathbb{R}^n\) and \(\Sigma \in \mathbb{R}^{n \times n}\). Further, let \(\rho_k = (\Sigma^{-1})_{kk}\) and \(\rho \in (0, \min_{k \in [n]}\rho_k)\) be the biggest \(\rho\) s.t. \(\rho I_n \preceq \Sigma^{-1}\preceq 2\operatorname{diag}(\Sigma^{-1}) - \rho I_n\). Then, we have that \[\begin{align} \operatorname{Ent}_{\mathcal{N}}(f) \leq \sum_{i=1}^n \frac{\rho_i}{\rho} \cdot \mathbb{E}[\operatorname{Ent}_{\mathcal{N}(\cdot | X_{-i})}(f)]. \end{align}\]
Proof. We start by verifying Assumption 2:
For all \(k \in [n]\), the conditional density of \(\nu\) given \(x_{-I_k} = x_{-k}\) is \[\begin{align} \mathcal{N}(x_k| x_{-k}) \propto \exp\left(-\frac{1}{2} x^{\top}P x\right) \propto \exp\left(-\frac{1}{2} x_k P_{kk} x_k - x_k^{\top}[P]_{k,-k}x_{-k}\right). \end{align}\]
We have \(-\nabla_{x_k}^2 \log(\mathcal{N}(x_k|x_{-k})) \succeq P_{kk} =: \rho_k\). Therefore, by the Bakry-Emery criterion of Theorem 10 the measures \(\mathcal{N}(\cdot | x_{-k})\) are \(\operatorname{LSI}(\rho_k)\).
For \(\mu\) we have \(\nabla_x^2 V(x) = \Sigma^{-1}\) and therefore \([\nabla_x^2 V(x)]_k = P_{kk} \succeq \rho_k\).
Since \(\nabla_x^2 V(x) = \Sigma^{-1}\) is constant in \(x\), the block interaction matrix is defined via the entries \[\begin{align} A_{ij}^\rho(x,y) = \frac{1}{\sqrt{\rho_i-\rho} \cdot \sqrt{\rho_j-\rho}} \cdot \begin{cases} P_{ij} & \text{if i \neq j}, \\ 0 & \text{if i = j}. \end{cases} \end{align}\]
Note that \(\rho_k = P_{kk}\) and hence defining \(D := \operatorname{diag}(P)\) this simplifies to \[\begin{align} A^\rho = (D - \rho I_n)^{-1/2} (P-D)(D - \rho I_n)^{-1/2}. \end{align}\]
Now, the condition \(\|A^0\|_{op} < 1\) is equivalent to \(-I_n \prec A^0 \prec I_n\) which simplifies as \[\begin{align} -I_n \prec D^{-1/2} (P-D)D^{-1/2} \prec I_n \; \Leftrightarrow \; 0 \prec P \prec 2D. \end{align}\]
Further, the condition \(\|A^\rho\|_{op} \leq 1\) is equivalent to \(-I_n \preceq A^\rho \preceq I_n\) which simplifies as \[\begin{align} -I_n \preceq (D - \rho I_n)^{-1/2} (P-D)(D - \rho I_n)^{-1/2} \preceq I_n &\; \Leftrightarrow \; \rho I_n - D \preceq P-D \preceq D-\rho I_n \\ &\; \Leftrightarrow \; \rho I_n \preceq P \preceq 2D-\rho I_n. \end{align}\]
This latter condition holds by assumption and as \(\rho > 0\), we have \(0 \prec P \prec 2D \Leftrightarrow \|A^0\|_{op} < 1\).
An application of Theorem 8 and Auxiliary Result 13 yield the statement. ◻
Definition 11. Hellinger Integral of Order \(\alpha\)
Let \(\mu, \nu\) be two probability measures s.t. \(\mu \ll \nu\). We define the Hellinger integral of order \(\alpha\) as \[\begin{align} H_\alpha (\mu || \nu) := \int \left(\frac{d\mu}{d\nu}\right)^\alpha d\nu. \end{align}\]
Theorem 9. McDiarmid’s via Hellinger Integrals (Theorem 1, [27])
Let \(\nu\) on \(\Omega^n\) be a probability measure with marginals \(\nu_i\) on \(\Omega\). Let \(\nu \ll \otimes_{i=1}^n \nu_i\) and \(f : \Omega \to \mathbb{R}\) fulfill the bounded differences property with constants \(c := (c_1,...,c_n)^{\top}\). Then, for \(t > 0\) and \(\alpha > 1\), \[\begin{align} \mathbb{P}\left(\left|f(X) - \int_\Omega f(x) d\otimes_{i=1}^n \nu_i(x)\right| \geq t\right) \leq 2^{\frac{\alpha}{\alpha - 1}} \exp\left(- \frac{2t^2}{\frac{\alpha}{\alpha - 1} \|c\|_{2}^2}\right) H_\alpha(\nu|| \otimes_{i=1}^n \nu_i)^{\frac{1}{\alpha}}. \end{align}\]
Lemma 10. Hellinger Integrals for Zero-Mean Gaussians
Let \(\mathcal{N}_1\) and \(\mathcal{N}_2\) on \(\mathbb{R}^n\) be zero-mean Gaussians with covariances matrices \(\Sigma_1, \Sigma_2\). Assume that \(M := \alpha \Sigma_1^{-1}+ (1-\alpha) \Sigma_2^{-1}\succeq 0\). Then, the Hellinger integrals of order \(\alpha > 1\) have the form \[\begin{align} H_\alpha(\mathcal{N}_1 || \mathcal{N}_2) = \det(\Sigma_1)^{-\alpha/2} \det(\Sigma_2)^{-(1-\alpha)/2} \det(M)^{-1/2}. \end{align}\]
Proof. Let \(p\) and \(q\) be the densities of \(\mathcal{N}_1\) and \(\mathcal{N}_2\) with respect to Lebesgue measure. Then, \[\begin{align} H_\alpha(\mathcal{N}_1 || \mathcal{N}_2) &= \int_{\mathbb{R}^n} \left(\frac{d\mu}{d\nu}\right)^\alpha d\nu = \int_{\mathbb{R}^n} p(x)^\alpha q(x)^{1-\alpha} dx = \int_{\mathbb{R}^n} \mathcal{N}(x; 0, \Sigma_1)^\alpha \mathcal{N}(x; 0, \Sigma_2)^{1-\alpha} dx \\ &= (2\pi)^{-n/2} \det(\Sigma_1)^{-\alpha/2} \det(\Sigma_2)^{-(1-\alpha)/2} \int_{\mathbb{R}^n} \exp\left(-\frac{1}{2} x^{\top}\left(\alpha \Sigma_1^{-1}+ (1-\alpha) \Sigma_2^{-1}\right) x\right) dx \\ &= (2\pi)^{-n/2} \det(\Sigma_1)^{-\alpha/2} \det(\Sigma_2)^{-(1-\alpha)/2} \cdot Z_M \int_{\mathbb{R}^n} \frac{1}{Z_M}\exp\left(-\frac{1}{2} x^{\top}M x\right) dx \\ &= (2\pi)^{-n/2} \det(\Sigma_1)^{-\alpha/2} \det(\Sigma_2)^{-(1-\alpha)/2} \cdot (2\pi)^{n/2} \det(M^{-1})^{1/2} \\ &= \det(\Sigma_1)^{-\alpha/2} \det(\Sigma_2)^{-(1-\alpha)/2} \det(M^{-1})^{1/2}. \end{align}\]
The statement is recovered as \(\det(M^{-1}) = \det(M)^{-1}\). ◻
Corollary 8. Hellinger Integral between Joint Gaussian and Marginals
Let \(\mathcal{N}\) on \(\mathbb{R}^n\) be a multivariate Gaussian with zero-mean and covariance \(\Sigma \in \mathbb{R}^{n \times n}\) and let \(\mathcal{N}_i\) be its \(i\)-th marginal. Let \(X \sim \mathcal{N}\) and \(\operatorname{Cor}_{\mathcal{N}}(X) := D^{-1/2} \Sigma D^{-1/2}\) with \(D := \operatorname{diag}(\Sigma)\) and let \(\lambda_1,...,\lambda_n\) be the eigenvalues of \(\operatorname{Cor}_{\mathcal{N}}(X)\). For all \(\alpha > 1\), under the condition that \(\operatorname{Cor}_{\mathcal{N}}(X) \preceq \frac{\alpha}{\alpha-1} \cdot I_n\) we have \[\begin{align} H_\alpha(\mathcal{N} || \otimes_{i=1}^n \mathcal{N}_i) = \prod_{i=1}^n (\alpha \lambda_i^{\alpha-1} + (1-\alpha) \lambda_i^{\alpha})^{-1/2}. \end{align}\]
Remark 8. Taking a logarithm simplifies the analysis of the right hand side above: \[\begin{align} \log\left(H_\alpha(\mathcal{N} || \otimes_{i=1}^n \mathcal{N}_i)\right) = - \frac{1}{2} \sum_{i=1}^n \log(\alpha \lambda_i^{\alpha-1} + (1-\alpha) \lambda_i^{\alpha}). \end{align}\]
By Taylor expanding the summands around \(\lambda_i = 1\), the case of independence, we may see that under suitable conditions on the eigenvalues, the Hellinger integral can be controlled by \(\|\operatorname{Cor}_{\mathcal{N}}(X) - I_n\|_{F}\). Hence, Theorem 9 may also yield dimension-free concentration under weak dependence. However, the control of dependence is much less explicit than in Corollary 4 and the concentration is around the expectation of \(f(X)\) wrt. the product measure \(\otimes_{i=1}^n \mathcal{N}_i\).
Proof. Under the condition that \(M := \alpha \Sigma^{-1}+ (1-\alpha) I_n \succeq 0\) Lemma 10 yields \[\begin{align} H_\alpha(\mathcal{N} || \otimes_{i=1}^n \mathcal{N}_i) &= \det(\Sigma)^{-\alpha/2} \det(D)^{-(1-\alpha)/2} \det(\alpha \Sigma^{-1}+ (1-\alpha) D^{-1})^{-1/2} \\ &= \det(C)^{-\alpha/2} \det(D)^{-\alpha/2} \det(D)^{-(1-\alpha)/2} \det(D^{-1/2}(\alpha C^{-1}+ (1-\alpha) I_n)D^{-1/2})^{-1/2} \\ &= \det(C)^{-\alpha/2} \det(\alpha C^{-1}+ (1-\alpha) I_n)^{-1/2} \\ &= \det(\alpha C^{\alpha-1} + (1-\alpha) C^\alpha)^{-1/2}. \end{align}\]
Above, we use that \(\det(\Sigma) = \det(C)\det(D)\) and \(\det(ABA) = \det(A)^2\det(B)\) for \(A, B \in \mathbb{R}^{d \times d}\). By the Spectral Mapping Theorem, any matrix polynomial \(p(C)\) has eigenvalues \(p(\lambda_1),...,p(\lambda_2)\). Since the determinant is just the product of the eigenvalues of a matrix, we thus have \[\begin{align} H_\alpha(\mathcal{N} || \otimes_{i=1}^n \mathcal{N}_i) = \prod_{i=1}^n (\alpha \lambda_i^{\alpha-1} + (1-\alpha) \lambda_i^{\alpha})^{-1/2}. \end{align}\]
Using that \(A \preceq B \Leftrightarrow B^{-1}\preceq A^{-1}\) for \(A, B \in \mathbb{R}^{d \times d}\) and by left- and right-multiplication of \(D^{-1/2}\): \[\begin{align} M = \alpha \Sigma^{-1}+ (1-\alpha)D^{-1}\succeq 0 \; &\Leftrightarrow \; \alpha \Sigma^{-1}\succeq (\alpha-1)D^{-1}\\ \; \Leftrightarrow \; \Sigma \preceq \frac{\alpha}{\alpha-1} D \; &\Leftrightarrow \; D^{-1/2} \Sigma D^{-1/2} \preceq \frac{\alpha}{\alpha-1} I_n. \end{align}\]
The statement is then recovered as \(\operatorname{Cor}_{}(\mu) = D^{-1/2} \Sigma D^{-1/2}\). ◻
Remark 9. \(\operatorname{Cor}_{\mathcal{N}}(X) \preceq \frac{\alpha}{\alpha-1} \cdot I_n\) is equivalent to \(\Sigma \preceq \frac{\alpha}{\alpha-1} \cdot \operatorname{diag}(\Sigma)\).
Theorem 10. Bakry-Emery (Theorem 21.2, [67], Corollary 5.7.2, [68])
Let the probability measure \(\nu\) on \(\mathbb{R}^n\) have density \(\nu(x) \propto \exp(-V(x))\) for all \(x \in \mathbb{R}^n\). Suppose there is \(\alpha > 0\) s.t. \(\nabla^2 V(x) \succeq \alpha I_n\) for all \(x \in \mathbb{R}^n\). Then, the following holds: \[\begin{align} \operatorname{Ent}_{\nu}(f^2) \leq \frac{2}{\alpha} \cdot \mathbb{E}[\|\nabla f(X)\|_{2}^2] \quad \text{and} \quad \operatorname{Var}_{\nu}(f) \leq \frac{2}{\alpha} \cdot \mathbb{E}[\|\nabla f(X)\|_{2}^2]. \end{align}\]
Auxiliary Result 12. Homogeneity of Entropy
Let \(X \sim \nu\) where \(\nu\) is a probability measure on \(\mathbb{R}^n\). For \(f : \mathbb{R}^n \to [0, \infty)\) and \(\alpha > 0\) we have \[\begin{align} \operatorname{Ent}_{\nu}(\alpha f) = \alpha \operatorname{Ent}_{\nu}(f). \end{align}\]
Proof. By the definition of entropy we have \[\begin{align} \operatorname{Ent}_{\nu}(\alpha f) = \mathbb{E}\left[\alpha f(X) \log\left(\frac{\alpha f(X)}{\mathbb{E}[\alpha f(X)]}\right)\right] = \alpha \mathbb{E}\left[f(X) \log\left(\frac{f(X)}{\mathbb{E}[f(X)]}\right)\right] = \alpha \operatorname{Ent}_{\nu}(f). \end{align}\] ◻
Auxiliary Result 13. Equivalent Notions of ATE (Definition 30, [35])
Let \(\mu\) on \(\Omega^n\) be a probability measure fulfilling ATE. Then, the following two notions are equivalent: \[\begin{align} {\operatorname{D_{KL}}(\nu||\mu)} &\leq C \sum_{i=1}^n \mathbb{E}[{\operatorname{D_{KL}}(\nu(\cdot|X_{-i})||\mu(\cdot|X_{-i}))}] & \text{for all \nu on \Omega^n s.t.\@{} \nu \ll \mu}, \label{eq:ATEKL} \\ \operatorname{Ent}_{\mu}(f) &\leq C\sum_{i=1}^n \mathbb{E}[\operatorname{Ent}_{\mu(\cdot | X_{-i})}(f)] & \text{for all f : \Omega^n \to (0, \infty)}. \label{eqATEent} \end{align}\] {#eq: sublabel=eq:eq:ATEKL,eq:eqATEent}
Proof. In this proof we use the notation \(\nu[f] := \int f d\nu\) to make it more explicit wrt. which measure an expectation is taken. Recall that the Kullback-Leibler divergence is \({\operatorname{D_{KL}}(\nu||\mu)} := \operatorname{Ent}_{\nu}(\frac{d\nu}{d\mu})\).
?? \(\Rightarrow\) ?? : Let \(f : \Omega^n \to (0, \infty)\) be arbitrary. If \(f = 0\) the statement in ?? holds trivially. For \(f > 0\), define a measure \(\nu\) via the Radon-Nikodym derivative \(d\nu/d\mu = f/\mu[f]\). The measure \(\nu\) is a probability measure, because \(\mu[d\nu/d\mu] = \mu[f/\mu[f]] = 1\). By definition, it holds that \[\begin{align} {\operatorname{D_{KL}}(\nu||\mu)} = \operatorname{Ent}_{\mu}(\frac{d\nu}{d\mu}) = \mu\left[\frac{d\nu}{d\mu}\log\left(\frac{d\nu}{d\mu}\right)\right] = \mu\left[\frac{f}{\mu[f]} \log\left(\frac{f}{\mu[f]}\right)\right] = \frac{1}{\mu[f]} \operatorname{Ent}_{\mu}(f). \end{align}\]
By definition of the regular conditional probability, \[\begin{align} \frac{d\nu(x_i|x_{-i})}{d\mu(\cdot|x_{-i})} := \frac{\frac{d\nu(x)}{d\mu}}{\mu[\frac{d\nu}{d\mu}|x_{-i}]} = \frac{f(x)/\mu[f]}{\mu[f/\mu[f]|x_{-i}]} = \frac{f(x)}{\mu[f|x_{-i}]}. \end{align}\]
By the same reasoning as for \(d\nu/d\mu\) above, we have \[\begin{align} {\operatorname{D_{KL}}(\nu(\cdot|x_{-i})||\mu(\cdot|x_{-i}))} &= \mu\left[\frac{d\nu(x_i|x_{-i})}{d\mu(\cdot|x_{-i})} \log\left(\frac{f}{\mu[f|x_{-i}]}\right)\Big|x_{-i}\right] = \nu\left[\log\left(\frac{f}{\mu[f|x_{-i}]}\right)\Big|x_{-i}\right]. \end{align}\]
Integrating wrt. the measure \(\nu\) this becomes \[\begin{align} \nu[{\operatorname{D_{KL}}(\nu(\cdot|X_{-i})||\mu(\cdot|X_{-i}))}] &= \nu\left[\nu\left[\log\left(\frac{f}{\mu[f|x_{-i}]}\right)\Big|X_{-i}\right]\right] = \nu\left[\log\left(\frac{f}{\mu[f|x_{-i}]}\right)\right] \\ &= \mu\left[\frac{d\nu}{d\mu}\log\left(\frac{f}{\mu[f|x_{-i}]}\right)\right] = \frac{1}{\mu[f]} \mu\left[f\log\left(\frac{f}{\mu[f|x_{-i}]}\right)\right] \\ &= \frac{1}{\mu[f]} \mu\left[\mu\left[f\log\left(\frac{f}{\mu[f|x_{-i}]}\right)\Big| X_{-i}\right]\right] = \frac{1}{\mu[f]} \mu\left[\operatorname{Ent}_{\mu(\cdot|X_{-i})}(f)\right]. \end{align}\]
Substituting the expressions into ?? and multiplying the inequality by \(\mu[f]\) recovers ?? .
?? \(\Rightarrow\) ?? : Let \(\nu\) on \(\Omega^n\) be an arbitrary probability measure s.t. \(\nu \ll \mu\). Define \(f = d\nu/d\mu\) and note that since \(\nu\) is a probability measure, we have \(\mu[f] = \mu[d\nu/d\mu] = 1\). Hence, by the above \[\begin{align} \operatorname{Ent}_{\mu}(f) = \operatorname{Ent}_{\mu}(\frac{d\nu}{d\mu}) = {\operatorname{D_{KL}}(\nu||\mu)}, \quad \mu\left[\operatorname{Ent}_{\mu(\cdot|X_{-i})}(f)\right] = \nu[{\operatorname{D_{KL}}(\nu(\cdot|X_{-i})||\mu(\cdot|X_{-i}))}]. \end{align}\]
Substituting the expressions into ?? recovers ?? .
◻