A Bayesian Proof and Interpretation
of Talagrand’s Majorizing Measure Theorem
May 28, 2026
Abstract
In this paper, we give a short Bayesian proof of Talagrand’s celebrated majorizing-measure theorem (MMT). While the upper-bound direction of MMT follows relatively directly from standard arguments, the lower-bound direction is widely regarded as the more difficult part and has received several distinct proofs. Unlike previous approaches, our proof does not rely on existing Gaussian processes lower bounds techniques, nor on combinatorial, geometric, or coding-theoretic constructions. Instead, we derive the lower bound from two area identities for Gaussian additive models. We show that the Gaussian width of a finite set is the integrated mean-squared error of the maximum-likelihood estimator (MLE), while the integrated minimum mean-squared error (MMSE) is larger than the Fernique–Talagrand functional, up to a universal constant. Simply then comparing the MLE with Bayes-optimal estimation gives a direct proof of the hard direction of MMT.
1 Introduction↩︎
Talagrand in [1] famously proved the majorizing measure theorem. The importance of this theorem is widely highlighted across the probability theory literature; see, for instance, the discussion surrounding Talagrand’s 2024 Abel Prize [2]. The theorem is as follows.
Theorem 1. [1]For any centered and separable Gaussian process \((G_t)_{t \in T}\) when \(T\) is endowed with the canonical pseudo-metric \[d(s,t)^2=\mathbb{E}(G_s-G_t)^2\] then it holds for universal constants \(0<c<C\) that \[c\mathcal{M}(T,d) \leq \mathbb{E}\sup_{t\in T}G_t \leq C\mathcal{M}(T,d),\]where \(\mathcal{M}(T,d)\) is the Fernique-Talagrand functional \[\begin{align} \label{eq:maj} \mathcal{M}(T,d)=\inf_{\mu\in\mathcal{P}(T)}\sup_{t\in T} \int_0^{\mathrm{diam}(T)}\sqrt{\log\frac{1}{\mu(B(t,r))}}\,dr \end{align}\tag{1}\]
The original proof of this celebrated theorem has often been viewed as opaque, and a substantial effort has gone into finding alternative proofs that offer further insight. As a result, several distinct and very interesting proofs of the majorizing-measure theorem are now available. Since the upper-bound direction follows from relatively direct arguments, these proofs focus mainly on the more challenging lower-bound direction. Talagrand himself gave multiple proofs based on greedy combinatorial constructions together with the Sudakov minoration theorem, leading to the important framework of generic chaining [1], [3], [4]. Later, van Handel gave a short interpolation proof of the lower bound using a contraction principle [5], while Borst et al. [6] developed a related approach based on convex optimization and primal-dual tree certificates. More recently, the theorem was recast in coding-theoretic terms, leading to a proof based on variable-length multiscale codes, Kraft’s inequality, and Sudakov-type lower bounds [7]. Most recently, Liu developed a rate-distortion equivalent of the functional \(\mathcal{M}(T,d)\) and proved the theorem using a lifting method together with Fernique’s sharpness of Dudley’s entropy integral for stationary processes [8], [9].
In this paper, we present a new proof of the lower bound based on a Bayesian statistical argument. Our proof does not rely on Gaussian-process lower-bound tools such as Sudakov minoration, nor does it involve a combinatorial, geometric, or coding-theoretic construction. Instead, it shows that the theorem follows cleanly by comparing the integrated mean-squared error of the maximum-likelihood estimator (MLE) with the integrated minimum mean-squared error (MMSE) in a simple Bayesian Gaussian additive model. The key technical tools we use are standard Bayesian identities, including the Nishimori identity and the I-MMSE formula [10], together with a new area identity connecting the mean-squared error of the MLE and the Gaussian width of a set (Proposition 2), which may be of independent interest. Figure 1 illustrates the main skeleton of the proof.
2 The proof↩︎
2.1 Getting started↩︎
2.1.1 Suffices to consider finite \(T\).↩︎
Our proof first notices that by separability of \(T\), we may assume \(T\) is finite which we assume from now on. This appears to be standard in the literature, but, for completeness, we include here the full reduction argument in Appendix 4. Moreover, we may assume without loss of generality there is no \(t,s \in T\) wth \(s \neq t\) such that \(G_t=G_s\) almost surely.
In particular, since \(T\) can be assumed to be finite, we employ the following lemma to realize the Gaussian process in a finite dimensional Euclidean space.
Lemma 1. Let \(T\) be finite and let \((G_t)_{t\in T}\) be a centered Gaussian process. For \(N=|T|,\) there exist \(N\) distinct vectors \((h_t)_{t\in T}\) in \(\mathbb{R}^N\) such that, for \(Z\sim N(0,I_N)\), \[(G_t)_{t\in T}\stackrel{d}= (\langle Z,h_t\rangle)_{t\in T},\] and \[d(s,t)=\|h_s-h_t\|_2.\]
Proof. Let \(K=(K(s,t))_{s,t\in T}\) be the covariance matrix of the Gaussian process, given by \(K(s,t)=\mathbb{E}G_sG_t\) for \(s,t \in T\). Since \(K\) is positive semidefinite, there exists a matrix \(A \in \mathbb{R}^{N \times N}\) such that \(K=AA^\top\). We then set \(h_t\) to be the row vector of \(A\) indexed by \(t\).
Note that by definition for all \(s,t \in T\) it holds \(\langle h_s,h_t\rangle=K(s,t)\). Therefore, the centered Gaussian processs \((\langle Z,h_t\rangle)_{t\in T}\) has the same covariance with the centered \((G_t)_{t\in T}\), and therefore the same law.
Finally, observe that for all \(s,t \in T,\) \[\|h_s-h_t\|_2^2=K(s,s)+K(t,t)-2K(s,t)=\mathbb{E}(G_s-G_t)^2=d(s,t)^2.\] ◻
Using the above lemma, for the rest of the proof we may assume \(G_t=\langle Z,h_t\rangle\) for some sequence of vectors \(h_t \in \mathbb{R}^N, t \in T.\) In particular, notice that in this setting the object of interest \(\mathbb{E}\sup_{t\in T}G_t=\mathbb{E}\sup_{t\in T} \langle Z,h_t\rangle\) simply corresponds to the Gaussian width of the convex hull of \(\{h_t: t\in T\},\) and for this reason we denote \[\mathcal{W}(T)=\mathbb{E}\sup_{t\in T}G_t=\mathbb{E}\sup_{t\in T} \langle Z,h_t\rangle.\]
2.1.2 Rate-distortion bound on \(\mathcal{M}(T,d)\)↩︎
Next, we leverage a convenient upper bound (up to constants) on the \(\mathcal{M}(T,d)\)-functional. The connection, while Liu mentions that might be known before [9] in the literature, to the best of our knowledge is first proved in [9]. Specifically, in [9] it is proven that for universal constants \(0<c',C'\) that \[\begin{align} \label{eq:liu} c'\mathcal{M}(T,d)-C'\mathrm{diam}(T) \leq \sup_{\pi \in \mathcal{P}(T)} \int_0^{\mathrm{diam}(T)} \sqrt{R_\pi(r)}\,dr, \end{align}\tag{2}\] where for \(0\le r\le \mathrm{diam}(T)\) and any \(\pi \in \mathcal{P}(T)\) we define (a self-coupling version of) the rate-distortion function \[R_\pi(r) =\inf\bigl\{ I(V;\widehat V): V \sim \pi, \widehat{V} \sim \pi, \mathbb{E}\|h_V-h_{\widehat V}\|^2\le r^2\bigr\},\] where the infimum is over all couplings of \((V,\widehat V)\)2. We remark that the proof follows from elementary (but elegant) calculus arguments and Sion’s minimax duality. For reader’s convenience, we include the proof in Appendix 5.
Now we turn to the following useful elementary observation, which is also stated in [9] without proof. We prove it here for completeness. Importantly, this observation allows one to ignore the \(\mathrm{diam}(T)\)-slack term in 2 .
Lemma 2. If \((T,d)\) is a finite metric space then \[\mathcal{W}(T)=\mathbb{E} \sup_{t\in T}G_t \ge \frac{1}{\sqrt{2\pi}}\,\operatorname{diam}(T).\]
Proof. Write \(D=\operatorname{diam}(T)\). If \(D=0\), the claim is trivial. Assume \(D>0\). Since \(T\) is finite, there exist \(a,b\in T\) such that \(d(a,b)=D\). Then \[\mathbb{E} \sup_{t\in T}G_t \ge \mathbb{E} \max\{G_a,G_b\}.\] Notice \[\mathbb{E} \max\{G_a,G_b\} =\frac{1}{2} \mathbb{E} (G_a+G_b)+ \frac{1}{2} \mathbb{E} |G_a-G_b|=\frac{1}{2} \mathbb{E} |G_a-G_b|.\] But \(G_a-G_b\) is a centered Gaussian random variable with variance \(\mathbb{E}(G_a-G_b)^2=d(a,b)^2=D^2.\) Therefore, \(\mathbb{E} |G_a-G_b| = D\,\mathbb{E} |g| = D\sqrt{\frac{2}{\pi}},\) where \(g\sim N(0,1)\). ◻
Hence, combining 2 and Lemma 2, to conclude the desired lower bound of Theorem 1, it suffices to prove for some universal constant \(c_0>0\) and for any \(\pi \in \mathcal{P}(T),\)
\[\begin{align} \label{eq:goal} c_0 \int_0^{\mathrm{diam}(T)} \sqrt{R_\pi(r)}\,dr \leq \mathcal{W}(T)=\mathbb{E}\sup_{t\in T}\langle Z,h_t\rangle. \end{align}\tag{3}\] We describe now a Bayesian proof of 3 for \(c_0=\frac{1}{2}.\)
2.2 The statistical model: MLE-width and MMSE-rate-distortion “area" theorems↩︎
2.2.1 The Bayesian statistical model↩︎
To prove 3 we fix any \(\pi \in \mathcal{P}(T)\) and construct a Bayesian Gaussian additive model that \(\pi\) plays the role of the prior. Specifically, for any signal-to-noise ratio (SNR) \(s\ge0\), we assume that the “signal" \(h_X\) is chosen from the prior \(X \sim \pi\) and a statistician observes \[\begin{align} \label{eq:GAM} Y_s=s h_X+Z, \end{align}\qquad{(1)}\] where \(Z \sim N(0,I_N)\). The goal of the statistician is to design an estimator that recovers \(h_X\) from the”noisy" \(Y_s.\)
It will be useful for us to focus on the mean-squared error performance of appropriately chosen estimators. For this reason, we define here for any estimator \(\hat{A}: \mathbb{R}^N \rightarrow \mathbb{R}^N\) its mean squared error by \[\mathrm{MSE}_s(\hat{A})=\mathbb{E}\| h_X-\hat{A}(Y_s)\|^2_2.\]
2.2.2 A MLE-width area theorem↩︎
We first focus is the so-called maximum likelihood estimator (MLE) \[\widehat X_s^{\rm MLE}\in \mathop{\mathrm{arg\,max}}_{u\in T} \log\mathbb{P}(Y_s|h_u) = \mathop{\mathrm{arg\,max}}_{u\in T} \left\{\langle Y_s,h_u\rangle-\frac{s}{2}\|h_u\|^2\right\},\]where ties are broken arbitrarily.
It is well-understood in the statistical literature that the performance of convex relaxations of the MLE relates to the Gaussian width of various convex sets, see e.g., the influential works [11], [12]. A key observation in this work is that for all Gaussian additive models (i.e., for any prior and any finite \(T\)) the Gaussian width \(\mathcal{W}(T)=\mathbb{E}\sup_{t\in T}\langle Z,h_t\rangle\) is in fact equal to the integrated mean-squared performance of the MLE across all SNR values. To the best of our knowledge, the following area formula is novel and potentially of independent interest.
Proposition 2 (Width-MLE area identity). For every prior \(\pi\) on \(T\), \[\mathcal{W}(T)=\frac{1}{2}\int_0^\infty \mathrm{MSE}_s(h_{\widehat X_s^{\rm MLE}})\,ds.\]
Proof. By expanding \(Y_s\) notice that almost surely \[\widehat X_s^{\rm MLE}\in \mathop{\mathrm{arg\,max}}_{u\in T} \left\{\langle Z,h_u-h_X\rangle -\frac{s}{2}\|h_u-h_X\|^2\right\}.\]
For this reason, fix any \(x\in T\) and \(z\in \mathbb{R}^N\) and define the function \[\Phi_{x,z}(s)= \max_{u\in T} \left\{ \langle z,h_u-h_x\rangle -\frac{s}{2}\|h_u-h_x\|^2 \right\}, s \geq 0.\]In particular, if for some \(s \geq 0,\) \[\begin{align} \label{eq:max}\hat{u}_s \in \mathop{\mathrm{arg\,max}}_{u\in T} \left\{ \langle z,h_u-h_x\rangle -\frac{s}{2}\|h_u-h_x\|^2 \right\}, \end{align}\tag{4}\] then it holds \(\Phi_{x,z}(s)=\langle z,h_{\hat{u}_s}-h_x\rangle -\frac{s}{2}\|h_{\hat{u}_s}-h_x\|^2.\)
Now, we explain some analytic properties of \(\Phi_{x,z}(s)\). Since we can always choose \(u=x\) it holds \(\Phi_{x,z}(s)\ge0\) for all \(s \geq 0\). Also, because \(T\) is finite, clearly \(\lim_{s \rightarrow +\infty}\Phi_{x,z}(s)= 0\). Moreover, the function \(\Phi_{x,z}(s), s \geq 0\) is the maximum of finitely many linear functions, therefore it is convex and piecewise linear. Finally, for every \(s \geq 0\) that the function \(\Phi_{x,z}(s)\) is differentiable, using Danskin’s theorem we have for \(\widehat u_s\) from 4 that the derivative satisfies \[(\Phi_{x,z})'(s)=-\frac{1}{2}\|h_{\widehat u_s}-h_x\|_2^2\]and also for every \(s \geq 0\) the right derivative satisfies \(|(\Phi_{x,z})'_{+}(s)| \leq \max_{u \in T} \frac{1}{2}\|h_{u}-h_x\|_2^2<\infty\). Combining the above, \[\Phi_{x,z}(0)=\Phi_{x,z}(0)-\lim_{s \rightarrow +\infty}\Phi_{x,z}(s)=\frac{1}{2}\int_0^\infty \|h_{\widehat u_s}-h_x\|_2^2\,ds.\] Now set \(x=X\) and \(z=Z\) and take expectations on the above equality. The left hand side becomes \[\mathbb{E}\max_{u\in T}\langle Z,h_u-h_X\rangle =\mathbb{E}\max_{u\in T}\langle Z,h_u\rangle-\mathbb{E}\langle Z,h_X\rangle =\mathbb{E}\max_{u\in T}\langle Z,h_u\rangle=\mathcal{W}(T),\] because \(Z\) is independent of \(X\) and centered. Moreover, under this choice of \(x,z\) the maximizer can be taken to satisfy for all \(s \geq 0,\) \(\widehat u_s= \widehat X_s^{\rm MLE}\) almost surely. Hence, the right hand side becomes equal to \(\frac{1}{2}\int_0^\infty \mathbb{E}\|h_X-h_{\widehat X_s^{\rm MLE}}\|_2^2\,ds=\frac{1}{2}\int_0^\infty \mathrm{MSE}_s(h_{\widehat X_s^{\rm MLE}})\,ds\), which completes the proof. ◻
2.2.3 An MMSE-rate distortion area theorem↩︎
Now, that we know the Gaussian width is equal to the integrated MSE of the MLE, we turn to the performance of the optimal Bayesian estimator that minimizes the MSE, which is the posterior mean. To analyse its optimal performance, we use the celebrated I-MMSE formula for our observation Gaussian additive model. Specifically, consider the mutual information between the signal and the observations, given by \[I_{\pi}(s)=I(h_X;Y_s),\] and the minimum mean squared error (MMSE), achieved by the posterior mean \(\mathbb{E}[h_X\mid Y_s],\) given by \[\mathrm{MMSE}_{\pi}(s)=\min_{A} \mathrm{MSE}_s(A)=\mathbb{E}\|h_X-\mathbb{E}[h_X\mid Y_s]\|^2.\] The I–MMSE identity3 of Guo–Shamai–Verdu [10] states that for all \(s\ge0,\) \[\label{eq:immse} I'_{\pi}(s)=s \mathrm{MMSE}_{\pi}(s).\tag{5}\]
Our first observation is that the MMSE serves as an upper bound to the inverse rate distortion function, defined by \[D_\pi(u)=\inf\bigl\{(\mathbb{E}\|h_V-h_{\widehat V}\|^2)^{1/2}: V \sim \pi, \hat{V} \sim \pi, I(V;\widehat V)\le u\bigr\}\]where the infimum is again over all couplings \((V,\hat{V})\). Notice \(D_\pi\) is non-increasing and \(D_\pi(u)=0\) if and only if \(u\ge H(V)\).
Lemma 3. For every \(s\ge0\), it holds \[2\mathrm{MMSE}_{\pi}(s)\ge D_\pi(I_{\pi}(s))^2.\]
Proof. For \(V \sim \pi\), let \(Y_s(V)=sh_V+Z, Z \sim N(0,I_N)\). The posterior mean \(\mathbb{E}[h_V\mid Y_s(V)]\) achieves by definition mean squared error \(\mathrm{MMSE}_{\pi}(s)\). Now, by Nishimori’s identity (see e.g., [13]), a sample \(\hat{V}\) from the posterior of \(V\) given \(Y_s(V)\) has mean squared error \(2\mathrm{MMSE}_{\pi}(s)\). Moreoever, marginally both \(V\) and \(\hat{V}\) follow \(\pi.\) Finally, by data processing, \[I(V;\hat{V})\le I(V;Y_s)=I_{\pi}(s).\] Therefore \((2\mathrm{MMSE}_{\pi}(s))^{1/2}\ge D_\pi(I_{\pi}(s))\). ◻
With this lemma at hand we move to the following important step, which relates the integrated MMSE to the integral of the inverse rate distortion function.
Lemma 4 (MMSE area lower bound). It holds \[\int_0^\infty \mathrm{MMSE}_{\pi}(s)\,ds \ge \frac{1}{2}\int_0^{H(V)}\frac{D_\pi(A)}{\sqrt A}\,dA.\]
Proof. Notice that for \(0 \leq s < S:=\sup\{ u \geq 0: \mathrm{MMSE}_{\pi}(u)>0\}\) the function \(I_{\pi}(s)\) is strictly increasing ranging from \(0\) to \(H(\pi).\) Hence, by the I-MMSE relation 5 and standard change of variables, \[\begin{align} \label{eq:step951} \int_0^\infty \mathrm{MMSE}_{\pi}(s)\,ds= \int_0^S \mathrm{MMSE}_{\pi}(s)\,ds =\int_0^S \frac{I'_{\pi}(s)}{s}\,ds=\int_0^{H(\pi)} \frac{1}{I_{\pi}^{-1}(A)}\,dA. \end{align}\tag{6}\]
By Lemma 3 and 5 , for all \(0 \leq s <S,\) \[2I'_{\pi}(s)\ge s D_\pi(I_{\pi}(s))^2.\] Equivalently, for all \(0 \leq u < H(\pi)\), \[(I_{\pi}^{-1})'(u)I_{\pi}^{-1}(u) D_{\pi}(u)^2\le 2.\]Since \(D_\pi\) is nonincreasing, for any \(H(V)>A \geq 0\), \(D_\pi(u)\ge D_\pi(A)>0\), hence for all \(u \leq A\) \[((I_{\pi}^{-1}(u))^2)'\le \frac{4}{D_\pi(A)^2}.\] By integrating \(u\) from \(0\) to \(A\), the above displayed equation gives for any \(H(V)>A> 0\), \[(I_{\pi}^{-1}(A))^2\le \frac{4A}{D_\pi(A)^2}.\] or \[\frac{1}{I_{\pi}^{-1}(A)}\ge \frac{D_\pi(A)}{2\sqrt{A}}.\] It follows then from 6 \[\int_0^\infty \mathrm{MMSE}_{\pi}(s)\,ds \ge \frac{1}{2}\int_0^{H(V)}\frac{D_\pi(A)}{\sqrt A}\,dA.\] ◻
We now need a final lemma that allows to relate the integral of the inverse rate density function to the integral of the rate density function itself. Satisfyingly, via simple double counting, the exact desired integral appears.
Lemma 5. It holds \[\int_0^{H(V)} \frac{D_{\pi}(A)}{\sqrt A}\,dA=2\int_0^{\mathrm{diam}(T)} \sqrt{R_{\pi}(r)}\,dr.\]
Proof. By standard change of variables and exhanging the order of integration,
\[\begin{align} \int_0^{H(V)} \frac{D_{\pi}(A)}{\sqrt A}\,dA&=2\int_0^{\sqrt{H(V)}} D_{\pi}(u^2)\,du\\ &=2\int_0^{\sqrt{H(V)}}\int_0^{\mathrm{diam}(T)} 1(D_{\pi}(u^2)>r) \,dr\,du\\ &=2\int_0^{\mathrm{diam}(T)}\int_0^{\sqrt{H(V)}}1(R_{\pi}(r)>u^2) \,du\,dr\\ &=2\int_0^{\mathrm{diam}(T)} \sqrt{R_{\pi}(r)}\,dr. \end{align}\] ◻
2.3 Putting it all together↩︎
By Proposition 2 and the definition of the MMSE as the minimum mean squared error among all estimators, \[\mathcal{W}(T)=\mathbb{E}\sup_{t\in T}\langle Z,h_t\rangle=\frac{1}{2}\int_0^\infty \mathrm{MSE}_s(h_{\widehat X_s^{\rm MLE}})\,ds \ge \frac{1}{2}\int_0^\infty \mathrm{MMSE}_{\pi}(s)\,ds.\]
Applying then Lemma 4 and Lemma 5 gives 3 .
3 Bayesian Intuition and Concluding Thoughts↩︎
In this final section, we highlight a few conceptual consequences of the Bayesian proof in terms of understanding Theorem 1.
As discussed above, the upper-bound direction of Theorem 1 is often viewed as the intuitive part of the theorem, see, for example, the generic chaining formulation in [14]. The lower-bound direction is much less transparent. One benefit of the present proof is that it gives this direction a clean statistical interpretation.
Let \(T\) be finite, and consider the Gaussian additive model ?? . Define the integrated Bayes-risk functional \[\begin{align} \label{eq:mmse} \mathcal{Z}(T,d):=\sup_{\pi \in\mathcal{P}(T)} \int_0^\infty \mathrm{MMSE}_{\pi}(s)\,ds . \end{align}\tag{7}\] By Lemma 4, inequality 2 , and an easy MMSE-diameter relation described in Lemma 7, we obtain for a universal constant \(c>0\) the relation \[c\mathcal{M}(T,d)\le \mathcal{Z}(T,d),\] where \(\mathcal{M}(T,d)\) denotes the Fernique–Talagrand functional. In words, the supremum over \(\pi\) of the integrated MMSE functional dominates, up to constants, the classical majorizing-measure functional. The hard direction of Theorem 1 then follows from a simple statistical observation: the Bayes estimator is optimal for squared error. Indeed, for every prior \(\pi\) and every \(s\), \[\mathrm{MMSE}_{\pi}(s) \le \mathrm{MSE}_s(h_{\widehat X_s^{\rm MLE}}).\] Moreover, Proposition 2 shows that the area under the MLE error curve is exactly the Gaussian width of \(T\). In short, the lower bound of the MMT follows from simply comparing the maximum-likelihood estimator with the Bayes-optimal estimator in a Gaussian additive model.
This also gives a canonical interpretation of the optimizing measure. The classical majorizing measure in \(\mathcal{M}(T,d)\) is an object that is often considered hard to understand probabilistically, see e.g., the discussion in [15] and how this difficulty has affected the literature of the problem. By contrast, the measure \(\pi\) appearing in the “dual" 7 is a very canonical statistical object; it is a least favorable prior for the Gaussian additive model, in the sense that it maximizes the integrated Bayes risk; see, for example, [16] for background on least favorable priors. Thus, while majorizing measures themselves can be difficult to interpret probabilistically, the dual optimal measure \(\pi\) has a clean statistical meaning.
It is perhaps striking that the Bayesian framework fits so naturally into this classical problem. A closely related Bayesian viewpoint was recently used by Mossel, Niles-Weed, Sun, and the author [17] to give a new proof of a seemingly quite different result: the fractional Kahn–Kalai conjecture [18] in probabilistic combinatorics, posed by Talagrand [19] as a refinement of earlier conjectures by Kahn and Kalai [20]. That conjecture gives a formula for thresholds of monotone properties of random subsets, whereas Theorem 1 gives a formula for the supremum of a Gaussian process. The success of a similar Bayesian proof strategy in both settings suggests a broader, though speculative, question: whether the majorizing-measure theorem and the theory of expectation thresholds are manifestations of a common mathematical theory.
Acknowledgments↩︎
The author is thankful to Jonathan Niles-Weed and Manolis Zampetakis for helpful feedback on an earlier draft of this work.
4 From finite to separable Gaussian processes↩︎
In the Bayesian proof in the main body we assumed \(T\) is finite. While it appears folklore in the literature that the finite-\(T\) statement of the hard direction of Talagrand’s Theorem 1 extends to any separable Gaussian process, we include here, for completeness, a full compactness proof establishing the reduction.
Let \((G_t)_{t\in T}\) be any centered separable Gaussian process with canonical metric \[d(s,t)=\bigl(\mathbb{E}(G_s-G_t)^2\bigr)^{1/2}.\] Now assume for any finite \(F\), we have
\[\mathbb{E}\max_{t\in F}G_t \ge c_0 \mathfrak R (F)\] where \(c_0>0\) is a universal constant and \[\mathfrak R (F) := \sup_{\pi\in\mathcal{P}(F)} \int_0^{\operatorname{diam}(F)} \sqrt{R_{\pi,F}(r)}\,dr.\] By monotone convergence we directly get \[\mathbb{E}\max_{t\in T}G_t \ge c_0 \mathfrak R_{\rm fin}(T)\]for \[\mathfrak R_{\rm fin}(T) := \sup_{\substack{F\subseteq T\\ F\;\mathrm{finite}}} \; \sup_{\pi\in\mathcal{P}(F)} \int_0^{\operatorname{diam}(F)} \sqrt{R_{\pi,F}(r)}\,dr.\] To continue, we turn to the partition version of \(\gamma_2\) Talagrand’s functional, given by \[\gamma_2^{\rm part}(T,d) = \inf_{\{\mathcal{A}_n\}} \sup_{t\in T} \sum_{n\ge0} 2^{n/2}\operatorname{diam}(\mathcal{A}_n(t)),\]where for each \(n\) \(\mathcal{A}_n\) ranges over partitions of \(T\) with number of cells satisfying \[|\mathcal{A}_n|\le N_n=2^{2^n},\] and \(\mathcal{A}_n(t)\) denotes the unique cell of \(\mathcal{A}_n\) containing \(t\). It is known in the literature that \(\mathfrak R (T)\) and \(\gamma_2^{\rm part}(T,d)\) (as well \(\mathcal{M}(T,d)\) from 1 ) are equal up to universal constants for any metric space \((T,d)\) [21]. Hence it suffices to prove the following lemma, which follows from an elementary compactness argument. We include the full proof here below.
Lemma 6. For every metric space \((T,d)\), \[\gamma_2^{\rm part}(T,d) = \sup_{\substack{F\subseteq T\\ F\;\mathrm{finite}}} \gamma_2^{\rm part}(F,d).\]
Proof. The inequality \[\sup_{F\subseteq T,\;|F|<\infty}\gamma_2^{\rm part}(F,d) \le \gamma_2^{\rm part}(T,d)\] is immediate. Indeed, if \((\mathcal{A}_n)\) is an admissible sequence of partitions of \(T\), then its restriction to \(F\), \[\mathcal{A}_n|_F := \{A\cap F:\;A\in\mathcal{A}_n,\;A\cap F\neq \varnothing\},\] is an admissible sequence of partitions of \(F\), and for every \(t\in F\), \[\operatorname{diam}\bigl((\mathcal{A}_n|_F)(t)\bigr) \le \operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr).\] Taking the infimum over admissible partition sequences on \(T\) gives the claim.
We now prove the reverse inequality. Let \[L:= \sup_{\substack{F\subseteq T\\ F\;\mathrm{finite}}} \gamma_2^{\rm part}(F,d).\] If \(L=+\infty\), there is nothing to prove so we assume \(L<\infty\). Now, fix \(\varepsilon>0\). We shall construct an admissible partition sequence \((\mathcal{A}_n)\) of \(T\) such that \[\sup_{t\in T} \sum_{n\ge0} 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr) \le L+\varepsilon.\] This will imply \[\gamma_2^{\rm part}(T,d)\le L+\varepsilon,\] and then the result follows by letting \(\varepsilon\) go to zero.
For each \(n\), let \([N_n]:=\{1,\dots,N_n\}\). Consider the compact product space \[\Omega := \prod_{n\ge0}[N_n]^T\] with the product topology, where each \([N_n]\) has the discrete topology. A point \[\omega=(\ell_n)_{n\ge0}\in\Omega\] assigns to each \(n\) a label map \[\ell_n:T\to [N_n].\] The inverse images of \(\ell_n\) define a partition of \(T\) with at most \(N_n\) cells.
For a finite set \(E\subseteq T\), a point \(t\in E\), an integer \(M\ge0\), and a labeling \(\omega=(\ell_n)\), define \[\Delta_n^E(t;\omega) := \operatorname{diam}\{x\in E:\ell_n(x)=\ell_n(t)\}.\] Equivalently, \[\Delta_n^E(t;\omega) = \max\{d(x,y):x,y\in E,\;\ell_n(x)=\ell_n(y)=\ell_n(t)\}.\] Since \(E\) is finite, this maximum is over a finite nonempty set.
Now define the closed subset \[C(E,t,M) := \left\{ \omega\in\Omega: \sum_{n=0}^M 2^{n/2}\,\Delta_n^E(t;\omega) \le L+\varepsilon \right\}.\] The set \(C(E,t,M)\) is closed because it depends only on finitely many labels \(\ell_0,\dots,\ell_M\) restricted to the finite set \(E\).
We claim that the family of closed sets \[\{C(E,t,M): E\subseteq T\text{ finite},\;t\in E,\;M\ge0\}\] has the finite intersection property.
Indeed, take finitely many constraints \[C(E_1,t_1,M_1),\dots,C(E_k,t_k,M_k).\] Let \[E_\ast:=E_1\cup\cdots\cup E_k.\] By the definition of \(L\), there is an admissible partition sequence \[(\mathcal{B}_n)_{n\ge0}\] of the finite metric space \(E_\ast\) such that \[\sup_{u\in E_\ast} \sum_{n\ge0} 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{B}_n(u)\bigr) \le L+\varepsilon.\] Label the cells of \(\mathcal{B}_n\) by elements of \([N_n]\). This gives maps \[\ell_n:E_\ast\to[N_n].\] Extend each \(\ell_n\) arbitrarily to all of \(T\), for instance by assigning all points of \(T\setminus E_\ast\) to label \(1\).
For every \(j=1,\dots,k\), every \(t_j\in E_j\), and every \(n\le M_j\), \[\Delta_n^{E_j}(t_j;\omega) \le \operatorname{diam}\bigl(\mathcal{B}_n(t_j)\bigr),\] because \(E_j\subseteq E_\ast\). Hence \[\sum_{n=0}^{M_j} 2^{n/2}\,\Delta_n^{E_j}(t_j;\omega) \le \sum_{n\ge0} 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{B}_n(t_j)\bigr) \le L+\varepsilon.\] Thus this labeling belongs to all of the finitely many closed sets. The finite intersection property is proved.
Since \(\Omega\) is compact, we conclude the intersection of all the sets \(C(E,t,M)\) is nonempty. Choose \[\omega=(\ell_n)_{n\ge0}\] in this intersection. Let \(\mathcal{A}_n\) be the partition of \(T\) into the fibers of \(\ell_n\). Then \[|\mathcal{A}_n|\le N_n.\]
Now, fix \(t\in T\) and \(M\ge0\). We claim \[\sum_{n=0}^M 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr) \le L+\varepsilon.\] For each \(0\le n\le M\), choose points \(x_n,y_n\in \mathcal{A}_n(t)\) such that \[d(x_n,y_n) \ge \operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr)-\delta_n,\] where \(\delta_n>0\) will be chosen later. If the diameter is not attained, choose \(x_n,y_n\) approximating the supremum; if the diameter is infinite, the argument below gives an immediate contradiction with \(L<\infty\) by choosing pairs with arbitrarily large distance.
Let \[E:=\{t\}\cup\{x_n,y_n:0\le n\le M\}.\] Since \(\omega\in C(E,t,M)\), we have \[\sum_{n=0}^M 2^{n/2}\,\Delta_n^E(t;\omega) \le L+\varepsilon.\] But \(x_n,y_n\in E\) and \[\ell_n(x_n)=\ell_n(y_n)=\ell_n(t),\] so \[\Delta_n^E(t;\omega)\ge d(x_n,y_n) \ge \operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr)-\delta_n.\] Therefore \[\sum_{n=0}^M 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr) \le L+\varepsilon+\sum_{n=0}^M a_n\delta_n.\] Letting all \(\delta_n\downarrow0\), we obtain \[\sum_{n=0}^M 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr) \le L+\varepsilon.\] Since this holds for every \(M\), monotone convergence of the partial sums yields \[\sum_{n\ge0} 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr) \le L+\varepsilon.\] Finally take the supremum over \(t\in T\). Thus \[\sup_{t\in T} \sum_{n\ge0} 2^{n/2}\,\operatorname{diam}\bigl(\mathcal{A}_n(t)\bigr) \le L+\varepsilon.\] Hence \[\gamma_2^{\rm part}(T,d)\le L+\varepsilon.\] Letting \(\varepsilon\downarrow0\) gives \[\gamma_2^{\rm part}(T,d)\le L.\] Together with the first inequality, this proves \[\gamma_2^{\rm part}(T,d) = \sup_{\substack{F\subseteq T\\ F\;\mathrm{finite}}} \gamma_2^{\rm part}(F,d).\] ◻
5 The rate-distortion integral upper bounds the \(\mathcal{M}(T,d)\) functional↩︎
In this section, we include for completeness the following result and a (very) slightly modified proof from [9]. The proof is based on elementary calculus and Sion’s minimax theorem.
Theorem 3 ([9]). There exist universal constants \(c,C>0\) such that, for every finite metric space \((T,d)\), \[\sup_{\pi \in \mathcal{P}(T)} \int_0^{\operatorname{diam}(T)} \sqrt{R_\pi(r)}\,dr \ge c \mathcal{M}(T,d)-C\operatorname{diam}(T).\]
Proof. Write \[\Delta:=\operatorname{diam}(T).\] We employ the following elementary calculus lemma from [9]. If \(y:[0,\Delta]\to[0,\infty]\) is non-increasing, right-continuous, and \(y(\Delta)=0\), then there exist universal constants \(0<c_0<C_0\) such that \[\label{eq:penalized-correct} c_0\int_0^\Delta y(r)\,dr \le \int_0^\infty \inf_{0\le r\le \Delta} \left\{\alpha^{-2}r^2+y(r)^2\right\} \,d\alpha \le C_0\int_0^\Delta y(r)\,dr.\tag{8}\]
For a fixed prior \(\pi\in\mathcal{P}(T)\), apply 8 to \[y(r)=\sqrt{R_\pi(r)},\qquad 0\le r\le \Delta.\] Since \(R_\pi(\Delta)=0\), this gives \[\label{eq:RD-to-penalty} \int_0^\Delta \sqrt{R_\pi(r)}\,dr \ge C_0^{-1} \int_0^\infty \inf_{0\le r\le \Delta} \left\{\alpha^{-2}r^2+R_\pi(r)\right\} \,d\alpha.\tag{9}\] By the definition of \(R_\pi\), for every \(\alpha>0\), \[\label{eq:penalty-coupling} \inf_{0\le r\le \Delta} \left\{\alpha^{-2}r^2+R_\pi(r)\right\} = \inf_{\substack{P_{X,X'}:\\ X\sim\pi,\;X'\sim\pi}} \left\{ \alpha^{-2}\mathbb{E} d(X,X')^2+I(X;X') \right\}.\tag{10}\] Indeed, if a coupling has \(\mathbb{E} d(X,X')^2\le r^2\), then the right-hand side is bounded above by \(\alpha^{-2}r^2+R_\pi(r)\); conversely, for any coupling one may choose \(r=(\mathbb{E} d(X,X')^2)^{1/2}\).
For \(\alpha>0\), \(\mu\in\mathcal{P}(T)\), and \(x\in T\), define \[\Psi_{\alpha,\mu}(x) := \inf_{\nu\in\mathcal{P}(T)} \left\{ \alpha^{-2}\mathbb{E}_{Y\sim\nu} d(x,Y)^2 + D_{\mathrm{KL}}(\nu\|\mu) \right\}.\] Now, by the Gibbs variational formula [22], it is easy to check that for fixed \(\alpha\) and \(x\), the map \(\mu\mapsto \Psi_{\alpha,\mu}(x)\) is convex. Let also \(K_x\) denote the conditional law of \(X'\) given \(X=x\). Then \[I(X;X') = \mathbb{E}_{X\sim\pi}D_{\mathrm{KL}}(K_X\|\pi),\]where \(D_{\mathrm{KL}}\) is the Kullback-Leibler (KL) divergence. Now, dropping the marginal constraint \(X'\sim\pi\) in 10 , we obtain \[\label{eq:drop-marginal} \begin{align} &\inf_{\substack{P_{X,X'}:\\ X\sim\pi,\;X'\sim\pi}} \left\{ \alpha^{-2}\mathbb{E} d(X,X')^2+I(X;X') \right\} \\ &\qquad\ge \mathbb{E}_{X\sim\pi} \inf_{\nu\in\mathcal{P}(T)} \left\{ \alpha^{-2}\mathbb{E}_{Y\sim\nu}d(X,Y)^2 + D_{\mathrm{KL}}(\nu\|\pi) \right\} \\ &\qquad= \mathbb{E}_{X\sim\pi}\Psi_{\alpha,\pi}(X). \end{align}\tag{11}\]
Therefore \[\begin{align} &\sup_{\pi\in\mathcal{P}(T)} \int_0^\infty \inf_{0\le r\le \Delta} \left\{ \alpha^{-2}r^2+R_\pi(r) \right\} d\alpha \\ &\qquad \geq \sup_{\pi\in\mathcal{P}(T)} \sum_{x\in T}\pi(x) \int_0^\infty \Psi_{\alpha,\pi}(x)\,d\alpha\\ &\qquad\ge \sup_{\pi\in\mathcal{P}(T)} \inf_{\mu\in\mathcal{P}(T)} \sum_{x\in T}\pi(x) \int_0^\infty \Psi_{\alpha,\mu}(x)\,d\alpha. \end{align}\] By Sion’s minimax theorem, using the convexity in \(\mu\) and linearity in \(\pi\), \[\label{eq:sion-correct} \begin{align} &\sup_{\pi\in\mathcal{P}(T)} \inf_{\mu\in\mathcal{P}(T)} \sum_{x\in T}\pi(x) \int_0^\infty \Psi_{\alpha,\mu}(x)\,d\alpha \\ &\qquad= \inf_{\mu\in\mathcal{P}(T)} \sup_{\pi\in\mathcal{P}(T)} \sum_{x\in T}\pi(x) \int_0^\infty \Psi_{\alpha,\mu}(x)\,d\alpha \\ &\qquad= \inf_{\mu\in\mathcal{P}(T)} \sup_{x\in T} \int_0^\infty \Psi_{\alpha,\mu}(x)\,d\alpha. \end{align}\tag{12}\]
It remains to lower bound the last display in terms of \(\mathcal{M}(T,d)\). Fix \(x\in T\), \(\mu\in\mathcal{P}(T)\), and \(\alpha>0\). For \(0\le r\le\Delta\), write \[L_x(r):=\log\frac{1}{\mu(B(x,r))}.\] We claim that there exist universal constants \(L_0,c_1>0\) such that \[\label{eq:psi-ball-lower} \Psi_{\alpha,\mu}(x) \ge c_1 \inf_{0\le r\le\Delta} \left\{ \alpha^{-2}r^2+\bigl(L_x(r)-L_0\bigr)_+ \right\}.\tag{13}\]
To prove this, fix \(\nu\in\mathcal{P}(T)\) and set \[m_2:=\mathbb{E}_{Y\sim\nu}d(x,Y)^2.\] Choose a fixed number \(a>1\), say \(a=2\), and put \[\rho:=\min\{a\sqrt{m_2},\Delta\}.\] Then \(m_2\ge \rho^2/a^2\). Markov’s inequality gives \[\nu(B(x,\rho))\ge 1-a^{-2}.\] Now it is easy to check the elementary bound for the binary relative entropy \(d_{\mathrm{bin}}(p\|q),\) that for some constants \(c_a,L_a>0\) if \(p\ge 1-a^{-2},\) \[d_{\mathrm{bin}}(p\|q) \ge c_a\left(\log\frac{1}{q}-L_a\right)_+.\]Hence, by data processing, \[D_{\mathrm{KL}}(\nu\|\mu) \ge c_a\bigl(L_x(\rho)-L_0\bigr)_+.\] Consequently, \[\begin{align} \alpha^{-2}m_2+D_{\mathrm{KL}}(\nu\|\mu) &\ge c_1 \left\{ \alpha^{-2}\rho^2+\bigl(L_x(\rho)-L_0\bigr)_+ \right\} \\ &\ge c_1 \inf_{0\le r\le\Delta} \left\{ \alpha^{-2}r^2+\bigl(L_x(r)-L_0\bigr)_+ \right\}. \end{align}\] Taking the infimum over \(\nu\) proves 13 .
Now apply the calculus lemma 8 to the non-increasing function \[y_x(r):=\sqrt{\bigl(L_x(r)-L_0\bigr)_+}, \qquad 0\le r\le\Delta.\] Since \(L_x(\Delta)=0\), we have \(y_x(\Delta)=0\). Combining 13 with the lower bound in 8 gives \[\begin{align} \int_0^\infty \Psi_{\alpha,\mu}(x)\,d\alpha &\ge c_2 \int_0^\Delta \sqrt{\bigl(L_x(r)-L_0\bigr)_+}\,dr \\ &\ge c_2 \int_0^\Delta \sqrt{L_x(r)}\,dr - C_2\Delta, \end{align}\] where we used \[\sqrt{(u-L_0)_+}\ge \sqrt{u}-\sqrt{L_0}, \qquad u\ge0.\] Therefore \[\begin{align} \inf_{\mu\in\mathcal{P}(T)} \sup_{x\in T} \int_0^\infty \Psi_{\alpha,\mu}(x)\,d\alpha &\ge c_2 \inf_{\mu\in\mathcal{P}(T)} \sup_{x\in T} \int_0^\Delta \sqrt{\log\frac{1}{\mu(B(x,r))}}\,dr - C_2\Delta \\ &= c_2 \mathcal{M}(T,d)-C_2\Delta. \end{align}\] Combining this estimate with 9 , 10 , 11 , and 12 , we obtain \[\sup_{\pi\in\mathcal{P}(T)} \int_0^\Delta \sqrt{R_\pi(r)}\,dr \ge c \mathcal{M}(T,d)-C\Delta\] for universal constants \(c,C>0\). This completes the proof. ◻
6 Diameter lower bound on the MMSE area↩︎
In this section, we include an auxiliary lemma relating for any Gaussian additive model the MMSE area and the diameter of the parameter space.
Lemma 7. Let \(T\) be a finite subset of a Euclidean space \(\mathbb{R}^N\). For a prior \(\pi\) on \(T\), let \[Y_s=sX+Z,\qquad X\sim \pi,\qquad Z\sim N(0,I_N).\]
Then for some universal constant \(c>0,\) \[\sup_{\pi} \int_0^\infty \operatorname{MMSE}_\pi(s)\,ds \ge c\operatorname{diam}(T).\]
Proof. Fix two points \(x_0,x_1\in T\), and put \[\delta:=\|x_1-x_0\|_2.\] We will show that for \(\pi\) the uniform prior on \(\{x_0,x_1\}\) we have for some universal constant \(c>0,\) \[\int_0^\infty \operatorname{MMSE}_\pi(s)\,ds \ge c\delta.\]
By translation and rotation, we can assume \[x_0=-\frac{\delta}{2}e_1, \qquad x_1=\frac{\delta}{2}e_1,\] where \(e_1\) is the first coordinate vector. Hence, we have \(X=\frac{\delta}{2}B e_1,\) for \(B\sim \mathrm{Unif}(\{-1,+1\}).\) Thus the problem reduces to the one-dimensional Gaussian channel \[Y=\alpha B+N, \qquad N\sim N(0,1), \qquad \alpha=\frac{s\delta}{2}.\] Consider the one-dimensional \[m_B(\alpha) := \mathbb{E}\bigl[(B-\mathbb{E}[B\mid Y])^2\bigr].\]and then we have \[\operatorname{MMSE}_\pi(s) = \frac{\delta^2}{4}\,m_B\!\left(\frac{s\delta}{2}\right).\]
But direct calculations give that \(\mathbb{E}[B\mid Y]=\tanh(\alpha Y),\) and therefore \[m_B(\alpha) = \mathbb{E}\bigl[1-\tanh^2(\alpha Y)\bigr] = \mathbb{E}\bigl[\operatorname{sech}^2(\alpha Y)\bigr] \geq \operatorname{sech}^2(1) \mathbb{P}(\alpha|Y| \leq 1).\] But for \(0\le\alpha\le1\), \[\mathbb{P}(|Y|\le1) = \mathbb{P}(|N+\alpha|\le1) \ge \mathbb{P}(-2\le N\le 0),\]so \(m_B(\alpha) \geq \operatorname{sech}^2(1) \mathbb{P}(-2\le N\le 0).\)
Therefore for some universal constant \(c>0\), for all \(0 \leq \alpha \leq 1\), \[\begin{align} \int_0^\infty \operatorname{MMSE}_\pi(s)\,ds &\ge \int_0^{2/\delta} \frac{\delta^2}{4} m_B\!\left(\frac{s\delta}{2}\right)\,ds \\ &\ge c\int_0^{2/\delta} \frac{\delta^2}{4}\,ds \\ &= c\frac{\delta}{2}. \end{align}\] ◻
References↩︎
\(^\circ\)Department of Statistics and Data Science, Yale University.
Email:ilias.zadik@yale.edu↩︎As customary, in the definition of \(R_\pi(r)\) and throughout the paper, we denote by \(H(V)\) the Shannon entropy of a discrete random variable \(V\), and by \(I(V;\widehat V)=H(V)-H(V|\widehat V)\) the mutual information between two discrete random variables \(V\) and \(\widehat V\).↩︎
Notice that in this work we introduce the I-MMSE formula in a reparametrized form compared to the original version in [10], solely because we define our Gaussian additive model with SNR equal to \(s\) while often in the literature the SNR of a Gaussian additive model is \(\sqrt{s}.\) The reason we make this choice is that this reparametrization of the SNR is more convenient in the analysis of the MLE.↩︎