Hoeffding-Style Concentration Bounds for Exchangeable Random Variables Thanks: The author NMG was supported by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory, managed by UT-Battelle, LLC, for the U. S. Department of Energy. + Remote Sensing Technology Institute, German Aerospace Center (DLR), Weßling, Germany Nina M. Gottschling Michele Caprio Abstract We establish Hoeffding-type concentration inequalities for the low and high tail bounds of sums of exchangeable random variables. Our results exhibit an anti-symmetry in such tail bounds due to the assumption of exchangeability, a generalization of the i.i.d. setting. In contrast to the existing literature on this problem, our result provides an upper tail bound with respect to the largest mean of a distribution in the support of the de Finetti mixing measure, and not the population mean. Equivalently, we establish a lower tail bound with respect to the smallest mean of a distribution in the support of the de Finetti mixing measure. This bridges the gap between finite sample and population means of exchangeable random variables, and distributional means. Keywords Concentration inequalities, uncertainty, exchangeable random variables 1 Introduction A common assumption in statistical modeling is that observations are independent and identically distributed, i.i.d. For identically distributed random variables, exchangeability provides a weaker symmetry assumption than independence, requiring only that the joint distribution be invariant under permutations of the indices. In some cases, such as for linear models, distinguishing between these assumptions using data alone may be impossible: “[…] there is no nontrivial, unbiased or invariant test of the null hypothesis that the errors are i.i.d. against the alternative hypothesis that they are merely exchangeably distributed, so that we would not be able to determine from the data whether or not the errors were i.i.d.” [ 2 ] This observation and existing tests for exchangeability [ 14 ] , motivate studying statistical guarantees that rely only on exchangeability. Here an open question, relevant to generalization bounds in machine learning and related data science settings, is whether one can obtain concentration bounds for sums of exchangeable random variables under an arbitrary marginal distribution . Addressing this question is particularly important in situations where the variance of the data-generating distribution is unknown or inaccessible. In such cases, concentration bounds provided by Hoeffding-type inequalities are useful because they provide variance-free concentration guarantees. For example, in statistical learning theory, the variance-free concentration guarantee from Hoeffding’s inequality for sums of i.i.d. random variables [ 13 ] , has been used to prove the generalization bound provided by Vapnik and Chervonenkjs [ 7 , Theorem 12.5] . In this paper, we answer this question in the affirmative. We show that the sample mean of bounded exchangeable random variables has a high-probability containment in a fixed interval and, in general, does not converge to the distribution mean. More specifically, the sample mean of bounded exchangeable random variables is contained with high probability in a fixed interval between the smallest and largest means among the distributions in the support of the de Finetti mixing measure. As a consequence, our results allows the construction of confidence intervals for the sample mean of bounded exchangeable random variables that are valid for any underlying distribution and depend only on the range bounds and the sample size. Our contributions can be formalized as follows. Let (\Omega,\mathcal{F},\mathbb{P}) be a probability space, where \mathcal{F} is the Borel \sigma -algebra on \Omega . Fix the sample number M\in\mathbb{N} and for each m\in\{1,\ldots,M\} , let X_{m}:\Omega\rightarrow[0,1] be bounded exchangeable identically distributed random variables; Exchangeability is recalled in Definition 2.2 . Let P[0,1] denote the space of probability measures on [0,1] , and let \rho be de Finetti’s measure, that is, the (random) mixing measure on P[0,1] from the measure theoretic formulation of de Finetti’s theorem, that we report in Theorem 2.3 . Denote by \displaystyle\bar{X}=\frac{1}{M}\sum_{m=1}^{M}X_{m},\quad\tilde{\mu}_{+}=\sup_{q\in\text{supp}(\rho)}\mathbb{E}_{q}(X_{1})\quad\text{ and }\quad\tilde{\mu}_{-}=\inf_{q\in\text{supp}(\rho)}\mathbb{E}_{q}(X_{1}), the sample mean \bar{X} and the supremum \tilde{\mu}_{+} , respectively infimum \tilde{\mu}_{-} , of the expectation of the random variable X_{1} with respect to the measures in the support of the de Finetti mixing measure \rho . In this work, we provide the following concentration bounds for the sample mean \bar{X} , \displaystyle\mathbb{P}\left(\bar{X}-\tilde{\mu}_{+}\geq t\right)\leq 2e^{-2Mt^{2}}, (1.1) and \displaystyle\mathbb{P}\left(\tilde{\mu}_{-}-\bar{X}\geq t\right)\leq 2e^{-2Mt^{2}}. (1.2) As in Hoeffding’s seminal work [ 13 ] , the bounds depend only on t,M and the endpoints of the ranges of the random variables X_{m} . In contrast to the concentration bound for i.i.d. random variables, instead of depending on the distribution mean, \mu=\mathbb{E}(X_{1})=\mathbb{E}_{\rho}(\mathbb{E}_{q}(X_{1})) , the bound depends on the largest and smallest means of the distributions in the support of the de Finetti mixing measure, \tilde{\mu}_{+} and \tilde{\mu}_{-} . As in [ 13 ] , we assume t>0 since for t<0 no nontrivial upper bound exists under our assumptions. 2 Related Work The literature on variance-free concentration bounds for the sample mean falls into three broad categories: (i) concentration for i.i.d. random variables, beginning with [ 13 ] , and for functions of i.i.d. variables, beginning with [ 19 ] ; (ii) concentration for functions of exchangeable random variables under structural assumptions on the function (see e.g. [ 5 ] ); and (iii) concentration for the weighted sample mean of exchangeable random variables around the finite population mean [ 9 ] . Ramdas and Manole [ 21 , Theorem 3.4] prove a Hoeffding-type inequality for the mean of exchangeable sub-Gaussian random variables with respect to the distribution mean. Foygel Barber [ 9 , Theorem 4] derives bounds to the weighted sample mean with respect to the population mean , where the expectation is taken over a population size N\in\mathbb{N} , rather than the distribution mean . This restriction is unavoidable: For exchangeable sequences, neither the sample mean, nor the population mean generally converge in probability to the distribution mean. In a related direction, we establish Hoeffding-type bounds for sums of exchangeable random variables. Additionally, the concentration bound provided by Foygel Barber [ 9 ] recovers the classical Hoeffding inequality for the i.i.d. setting, in the limit of an infinitely large population, N\to\infty , for fixed sample number M\in\mathbb{N} satisfying M\leq N . Similarly, we recover the classical Hoeffding inequality for all finite samples sizes M\in\mathbb{N} by assuming independence of the samples. In addition to the theoretical interest, our findings are applicable across a broad range of problems in Statistics, including conformal prediction [ 23 , 16 , 1 ] and inference in regression [ 4 , 17 ] . We note in passing that finite exchangeability—a stronger assumption than infinite exchangeability—appears in several modern statistical applications, such as permutation testing [ 11 , 20 ] . With a suitable adaptation based on a finite de Finetti-type representation [ 8 ] , our method of proof may be applicable in this setting as well. It is also worth pointing out that variance-free concentration bounds, such as Hoeffding’s inequality from [ 13 ] , have been used to prove generalization bounds in machine learning. For example, the proof of the generalization bound provided by Vapnik and Chervonenkjs [ 7 , Theorem 12.5] uses Hoeffding’s inequality. Notably, Hoeffding’s inequality from [ 13 ] has also been used to prove the Glivenko-Cantelli Theorem [ 7 , Theorem 12.4] for uniform almost sure convergence of the empirical distribution function to the true one. We now provide a summary of both Hoeffding’s inequality and de Finetti’s Theorem; This is because (i) our results can recover Hoeffding’s inequality under the assumption of independent samples, and (ii) our proof uses a measure-theoretic formulation of de Finetti’s representation Theorem. 2.1 Hoeffding’s Inequality Our result and proof are closely related to Hoeffding’s classical inequality in [ 13 ] , and recovers it in the i.i.d. case; We summarize it next. Let \{X_{m}\}_{m=1}^{M} be i.i.d. random variables. Denote \displaystyle\bar{X}=\frac{1}{M}\sum_{m=1}^{M}X_{m},\qquad\mu=\mathbb{E}(X_{1}). (2.1) Then, (a simplified) Hoeffding’s inequality from [ 13 ] states the following. Theorem 2.1 (Hoeffding’s Inequality) . Let \{X_{m}\}_{m=1}^{M} be i.i.d. random variables, such that for all m\in\{1,\ldots,M\} we have that 0\leq X_{m}\leq 1 with probability 1. Then, for 00 we have that \displaystyle e^{-\tilde{\mu}h-th}(1-\tilde{\mu}+\tilde{\mu}e^{h})\leq e^{-2t^{2}}. (4.3) Proof. After setting the partial derivative of the left-hand side of ( 4.3 ) with respect to h to zero, we find that the left-hand side of ( 4.3 ) attains its minimum at h=h_{0} , where \displaystyle h_{0}=\ln\left(\frac{(1-\tilde{\mu})(t+\tilde{\mu})}{(1-\tilde{\mu}-t)\tilde{\mu}}\right). (4.4) Since 00 if and only if \frac{t}{1-\tilde{\mu}}>\frac{t}{\tilde{\mu}+t} , that is, t>1-2\mu . Hence, if 1-2\mu>0 , the function G(t,\tilde{\mu}) attains its minimum at t=1-2\tilde{\mu} , and the value of the minimum is G(1-2\tilde{\mu},\tilde{\mu})=g(\tilde{\mu}) . If 1-2\tilde{\mu}<0 , then G(t,\tilde{\mu}) attains its minimum at t=0 , and the value of the minimum is \frac{1}{2\tilde{\mu}(1-\tilde{\mu})}=g(\tilde{\mu}) . Now it is easily seen that g(\tilde{\mu})\geq g(1/2)=2 . This implies the desired inequality in ( 4.3 ). ∎ We are now ready for the proof of our main result, Lemma 3.1 . Proof of Lemma 3.1 . We begin with proving part (i) . Equip [0,1] and [0,1]^{M} with the standard Borel sigma algebras denoted by \mathcal{B}\left([0,1]\right) and \mathcal{B}([0,1]^{M}) , respectively. The law for the random variable (X_{m})_{m=1}^{M}:\Omega\rightarrow[0,1]^{M} is defined as \displaystyle\begin{split}p=\mathbb{P}\circ(X_{1},X_{2},\ldots,X_{M})^{-1}:\mathcal{B}\left([0,1]^{M}\right)&\rightarrow[0,1]\\ A&\mapsto\mathbb{P}((X_{1},X_{2},...X_{M})^{-1}(A)).\end{split} (4.10) Following [ 10 ] , we denote the set of probability measures on \mathcal{B}([0,1]) by \displaystyle P[0,1]\equiv P_{\mathcal{B}([0,1])}=\{\rho:\mathcal{B}([0,1])\rightarrow[0,1],\text{ }\rho\text{ is a probability measure}\}. (4.11) As in [ 10 ] , we denote by PP[0,1] the space of measures on the space of measures P[0,1]\equiv P_{\mathcal{B}([0,1])} . Note that this measure space is also introduced in [ 12 , Section 2] . The set PP[0,1] can be equipped with a canonical \sigma -algebra, namely the one generated by the functions \displaystyle\epsilon_{f}:P[0,1] \displaystyle\rightarrow\mathbb{R} \displaystyle p \displaystyle\mapsto\epsilon_{f}(p)=\int_{[0,1]}f(x)p(\mathrm{d}x), (4.12) for all bounded measurable functions f:[0,1]\rightarrow\mathbb{R} . Now we can apply de Finetti’s Theorem 2.3 . The law of (X_{m})_{m=1}^{M}:\Omega\rightarrow[0,1]^{M} in ( 4.10 ) can be extended to [0,1]^{\mathbb{N}} by Kolmogorv’s Extension Theorem [ 15 , Theorem 14.36] . As the random variables are exchangeable identically distributed, the extended law p is exchangeable, and by de Finetti’s Theorem 2.3 , there exists a probability measure \rho\in PP[0,1] on P[0,1]\equiv P_{\mathcal{B}([0,1])} such that for every finite collection of measurable subsets S_{1},\ldots,S_{M}\in\mathcal{B}([0,1]) , we have \displaystyle p(S_{1}\times\cdots\times S_{M})=\int_{P[0,1]}q(S_{1})\times\cdots\times q(S_{M})\rho(\mathrm{d}q). (4.13) Following [ 13 , Inequality (1.7)] , we apply a common method to derive concentration inequalities. The probability \mathbb{P}\left(\left\{\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}>Mt\right\}\right) is the expected value of the function on \Omega which takes the values 0 and 1 , if \sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}-Mt is \leq 0 or >0 , respectively. This function does not exceed the exponential function, e^{h(\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}-Mt)} , where h is an arbitrary positive constant. The above can be summarized by the fact that the indicator function of a positive function is smaller or equal than the exponential function concatenated with the multiplication by a positive constant of a function. This yields \displaystyle\mathbbm{1}_{X>0}(\omega)\leq e^{hX}(\omega), (4.14) for all h>0 , all \omega\in\Omega and any X:\Omega\rightarrow[0,\infty) . Hence, \displaystyle\mathbb{P}\left(\left\{\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}>Mt\right\}\right)<\mathbb{E}\left(e^{h(\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}-Mt)}\right). (4.15) Now we use the above inequality, as applied in [ 13 , Inequality (1.7)] ; For h>0 , we obtain \displaystyle\begin{split}\mathbb{P}\left(\left\{\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}\geq Mt\right\}\right)&\leq\mathbb{E}\left(e^{h(\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}-Mt)}\right)\\ &=e^{-Mht-Mh\tilde{\mu}_{+}}\text{ }\mathbb{E}\left(\prod_{m=1}^{M}e^{hX_{m}}\right).\end{split} (4.16) As for m\in\{1,\ldots,M\} , each X_{m}:\Omega\rightarrow[0,1] is a bounded exchangeable identically distributed random variable, but not independent; Therefore, we cannot use [ 13 , Equality (1.8)] . Instead, we now consider the non-negative, continuous and, thus, Borel measurable function \displaystyle\begin{split}g:[0,1]^{M}&\rightarrow[0,\infty)\\ (x_{1},..x_{M})&\mapsto g(x_{1},..x_{M})=\prod_{m=1}^{M}e^{hx_{m}},\end{split} (4.17) and proceed to apply de Finetti’s theorem, the binomial theorem and a simple thresholding argument to prove an exponentially-in- M\in\mathbb{N} decreasing concentration bound for ( 4.16 ). The expectation over the function g defined in ( 4.16 ) can be rewritten using the pushforward of the probability measure \mathbb{P} with respect to (X_{1},\ldots,X_{M}) , yielding \displaystyle\mathbb{E}\left(\prod_{m=1}^{M}e^{hX_{m}}\right) \displaystyle=\mathbb{E}(g(X_{1},\ldots,X_{M}))=\int_{\Omega}g((X_{1},\ldots,X_{M})(\omega))\mathrm{d}\mathbb{P}(\omega) \displaystyle=\int_{(X_{1},\ldots,X_{M})(\Omega)}g(v_{1},\ldots,v_{M})\mathrm{d}\mathbb{P}((X_{1},\ldots,X_{M})^{-1}(v_{1},\ldots,v_{M})). (4.18) Now, inserting the law p=\mathbb{P}\circ(X_{1},...,X_{M})^{-1} in the above ( 4 ) yields \displaystyle\begin{split}\int_{(X_{1},\ldots,X_{M})(\Omega)}&g(v_{1},\ldots,v_{M})\mathrm{d}\mathbb{P}((X_{1},\ldots,X_{M})^{-1}(v_{1},\ldots,v_{M}))\\ &=\int_{(X_{1},\ldots,X_{M})(\Omega)}g(v_{1},\ldots,v_{M})\mathrm{d}p(v_{1},\ldots,v_{M}).\end{split} (4.19) Now, we apply de Finetti’s theorem, in particular equality ( 4.13 ), to the above ( 4.19 ) to obtain \displaystyle\begin{split}\int_{(X_{1},\ldots,X_{M})(\Omega)}&g(v_{1},\ldots,v_{M})\mathrm{d}p(v_{1},\ldots,v_{M})\\ &=\int_{(X_{1},\ldots,X_{M})(\Omega)}g(v_{1},\ldots,v_{M})\int_{P[0,1]}q(v_{1},\ldots,v_{M})\rho(\mathrm{d}q),\end{split} (4.20) for some fixed measure \rho\in PP[0,1] on the space of measures on \mathcal{B}([0,1]) . Using Fubini’s theorem in the above ( 4.20 ) yields \displaystyle\begin{split}\int_{(X_{1},\ldots,X_{M})(\Omega)}&g(v_{1},\ldots,v_{M})\int_{P[0,1]}q(v_{1},\ldots,v_{M})\rho(\mathrm{d}q)\\ &=\int_{P[0,1]}\int_{(X_{1},\ldots,X_{M})(\Omega)}g(v_{1},\ldots,v_{M})\mathrm{d}q(v_{1},\ldots,v_{M})\rho(\mathrm{d}q).\end{split} (4.21) Using that \{X_{m}\}_{m=1}^{M} are identically distributed, that g(v_{1},...,v_{M})=\prod_{m=1}^{M}e^{hv_{m}} and q(v_{1},...v_{M})=\prod_{m=1}^{M}q(v_{m}) in the above, ( 4.21 ) yields \displaystyle\int_{P[0,1]}\int_{\prod_{m=1}^{M}X_{m}(\Omega)}g(v_{1},..v_{M})\mathrm{d}q(v_{1},..v_{M})\rho(\mathrm{d}q) \displaystyle=\int_{P[0,1]}\int_{\prod_{m=1}^{M}X_{m}(\Omega)}\left(\prod_{m=1}^{M}e^{hv_{m}}\mathrm{d}q(v_{m})\right)\rho(\mathrm{d}q) \displaystyle=\int_{P[0,1]}\prod_{m=1}^{M}\left(\int_{X_{m}(\Omega)}e^{hv_{m}}\mathrm{d}q(v_{m})\right)\rho(\mathrm{d}q). (4.22) We now make explicit the expectation with respect to the measure q appearing in the integral in ( 4 ), obtaining \displaystyle\mathbb{E}\left(\prod_{m=1}^{M}e^{hX_{m}}\right) \displaystyle=\int_{P[0,1]}\prod_{m=1}^{M}\left(\int_{X_{m}(\Omega)}e^{hv_{m}}\mathrm{d}q(v_{m})\right)\rho(\mathrm{d}q) \displaystyle=\int_{P[0,1]}\left(\int_{X_{1}(\Omega)}e^{hv_{1}}\mathrm{d}q(v_{1})\right)^{M}\rho(\mathrm{d}q)=\int_{P[0,1]}\left(\mathbb{E}_{q}\left(e^{hX_{1}}\right)\right)^{M}\rho(\mathrm{d}q). (4.23) Using the above ( 4 ) in inequality ( 4.16 ) yields \displaystyle\mathbb{P}\left(\left\{\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}\geq Mt\right\}\right) \displaystyle\leq e^{-Mht}\text{ }\mathbb{E}\left(\prod_{m=1}^{M}e^{h(X_{m}-\tilde{\mu}_{+})}\right) \displaystyle=e^{-Mht-Mh\tilde{\mu}_{+}}\text{ }\mathbb{E}\left(\prod_{m=1}^{M}e^{hX_{m}}\right) \displaystyle=e^{-Mht-Mh\tilde{\mu}_{+}}\int_{P[0,1]}\left(\mathbb{E}_{q}\left(e^{hX_{1}}\right)\right)^{M}\rho(\mathrm{d}q). (4.24) Now we use Lemma 4.1 , which arises from the convexity of the exponential function, to start to polynomialise the integrand with respect to the expectation \mathbb{E}_{q}\left(X_{1}\right) . We apply Lemma 4.1 with the lower limit a=0 and the upper limit b=1 , to obtain \displaystyle\left(\mathbb{E}_{q}\left(e^{hX_{1}}\right)\right)^{M}\leq(1-\mathbb{E}_{q}(X_{1})+\mathbb{E}_{q}(X_{1})e^{h})^{M}=(1+(e^{h}-1)\mathbb{E}_{q}(X_{1}))^{M}. (4.25) Note that \mathbb{E}_{q}(X_{1})\leq\sup_{q\in\text{supp}(\rho)}\mathbb{E}_{q}(X_{1})=\tilde{\mu}_{+} for all q\in\text{supp}(\rho) , where \rho is the mixing measure on P[0,1] from de Finetti’s Theorem. As for h>0 , we have that (e^{h}-1)>0 , thus obtaining \displaystyle(1+(e^{h}-1)\mathbb{E}_{q}(X_{1}))^{M}\leq((e^{h}-1)\tilde{\mu}_{+}+1)^{M}=(1-\tilde{\mu}_{+}+\tilde{\mu}_{+}e^{h})^{M}. (4.26) Combining ( 4.25 ) and ( 4.26 ) yields the inequality \displaystyle\left(\mathbb{E}_{q}\left(e^{hX_{1}}\right)\right)^{M}\leq(1-\tilde{\mu}_{+}+\tilde{\mu}_{+}e^{h})^{M}, (4.27) which holds for all h>0 . Now we can insert inequality ( 4.27 ) into the concentration inequality ( 4 ), resulting in \displaystyle\mathbb{P}\left(\left\{\sum_{m=1}^{M}X_{m}-M\tilde{\mu}_{+}\geq Mt\right\}\right) \displaystyle\leq e^{-Mht-Mh\tilde{\mu}_{+}}\int_{P[0,1]}\left(\mathbb{E}_{q}\left(e^{hX_{1}}\right)\right)^{M}\rho(\mathrm{d}q) \displaystyle\leq e^{-Mht-Mh\tilde{\mu}_{+}}\int_{P[0,1]}(1-\tilde{\mu}_{+}+\tilde{\mu}_{+}e^{h})^{M}\rho(\mathrm{d}q) \displaystyle=e^{(-\tilde{\mu}_{+}-t)hM}(1-\tilde{\mu}_{+}+\tilde{\mu}_{+}e^{h})^{M}, (4.28) which holds for all h>0 , where convergence to zero as M\to\infty can be obtained for \displaystyle e^{(-\tilde{\mu}_{+}-t)h}(1-\tilde{\mu}_{+}+\tilde{\mu}_{+}e^{h})<1. (4.29) Note that bound in ( 4 ) is the same as in [ 13 , Equation (4.6)] . For 00 in ( 4 ) is indeed positive and is of the form given in [ 13 , Equation (4.7)] with \mu replaced by \tilde{\mu}_{+} . The rest of the proof follows by applying Proposition 4.2 . The latter follows the exact same analysis steps as in [ 13 ] with \mu replaced by \tilde{\mu}_{+} . Now for the proof of the lower tail bound, the proof of part (ii) , we use the result from part (i) . We have that \displaystyle\mathbb{P}\left(\tilde{\mu}_{-}-\bar{X}\geq t\right) \displaystyle=\mathbb{P}\left(-\bar{X}-(-\tilde{\mu}_{-})\geq t\right) \displaystyle=\mathbb{P}\left((1-\bar{X})-(1-\tilde{\mu}_{-})\geq t\right). (4.30) Note that the assumption 0\leq X_{m}\leq 1 has been made to give the bounds in part (i) a simple form. Note also that the supremum of the mean with respect to the distributions in the support of the mixing measure is given by \displaystyle\tilde{\mu}^{\prime}_{+}=\sup_{q\in\text{supp}(\rho)}\mathbb{E}_{q}(1-X_{1})=1-\inf_{q\in\text{supp}(\rho)}\mathbb{E}_{q}(X_{1})=1-\tilde{\mu}_{-}. (4.31) Now by applying part (i) to 1-X_{m} and using ( 4 ), for 0