用于高效分布学习的稀疏先验

# Sparse Priors for Efficient Distribution Learning
Source: [https://arxiv.org/html/2609.20883](https://arxiv.org/html/2609.20883)
Barnabás PóczosAffiliation:Machine Learning Department, Carnegie Mellon University

###### Abstract

Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported indddimensions fromnnsamples degrade asO\(n−1/Θ\(d\)\)O\(n^\{\-1/\\Theta\(d\)\}\), though shown to be minimax optimal\. We hypothesize that present bounds are too pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications\. Consequently, we introduce the class of sparse priors and define the “Sparse Dimension” as a measure of sparsity of a prior over the space of all distributions\. We show that distribution learning under akk\-sparse prior achieves a Bayesian risk lower bound ofΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)under common distance metrics, and show a matching \(up to logarithmic terms asymptotically inn,kn,k\) upper bound for the TV distance under mild additional assumptions\. We show the statistical equivalence of distribution learning and learning to sample in the Bayesian setting so that our results apply to learning to sample as well\. Whilekkcan still depend on the dimensiondd, or a notion of intrinsic dimension, our results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence onnn\.

## 1Introduction

The theoretical minimax optimality, in terms of the sample complexity of samples required for learning to sample from a distribution, have been established for several popular machine learning techniques in recent work\.[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)and[Fu et al\. \(2024\)](https://arxiv.org/html/2609.20883#bib.bib10)establish the optimality for score\-based diffusion under Besov smoothness of the score function and score\-based conditional diffusion under Hölder smoothness of the score function respectively\. Similar results were established for Generative Adversarial Networks \(GANs\) by[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)\.[Singh et al\. \(2018\)](https://arxiv.org/html/2609.20883#bib.bib28)establish the minimax equivalence of distribution learning and learning to sample, which allows us to conclude the existence of minimax optimal distribution learners as well\. Theoretical guarantees however, still suffer from a major limitation: the established optimality bounds suffer from the curse of dimensionality\. Concretely, givennnsamples from a target distributionπ\\pisupported onℝd\\mathbb\{R\}^\{d\}, it is shown that both score\-based diffusion models and GANs can learn to sample from a distribution that is at the optimal distanceΘ⁡\(n−cd\+c′\)\\Theta\(n^\{\-\\frac\{c\}\{d\+c^\{\\prime\}\}\}\)\(upto poly\-log terms\) from the target distribution as measured by an appropriate Integral Probability Metric \(IPM\) like the total variation \(TV\) or Wasserstein distance, wherec,c′c,c^\{\\prime\}are constants that depend on the smoothness of the score function\.

A popular way to circumvent the curse of dimensionality is the manifold hypothesis, under which we assume that the data distribution lies on a lower dimensional submanifold\. While[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)and[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)extend their bounds to a version of the manifold hypothesis,[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2);[Tang and Yang \(2024\)](https://arxiv.org/html/2609.20883#bib.bib4)consider the most general submanifold structure comprising an atlas of homeomorphisms from a subset ofℝd′\\mathbb\{R\}^\{d^\{\\prime\}\}ford′<dd^\{\\prime\}<dto the support ofπ\\pi\.[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1);[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9);[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2);[Tang and Yang \(2024\)](https://arxiv.org/html/2609.20883#bib.bib4)all show a lower bound ofΩ⁡\(n−cd′\+c′\)\\Omega\(n^\{\-\\frac\{c\}\{d^\{\\prime\}\+c^\{\\prime\}\}\}\)on the minimax risk defined in Section[2](https://arxiv.org/html/2609.20883#S2)and show matching upper\-bounds \(upto poly\-log terms\)\. The manifold hypothesis offers significant improvements, and allows us to essentially replace the dimensionality of distributions with intrinsic dimensionality, which is indeed much lower than the true dimensionality for image distributions\. For example,[Gong et al\. \(2019\)](https://arxiv.org/html/2609.20883#bib.bib6);[Pope et al\. \(2021\)](https://arxiv.org/html/2609.20883#bib.bib7)estimate the intrinsic dimensionality of imagenet\([Deng et al\., 2009](https://arxiv.org/html/2609.20883#bib.bib16)\)to be at most1919and4343respectively, which is much smaller than the true dimensionality of\>150​k\>150k\. However it is still too large for image distributions to be learnable with the sample sizes we see in practice\. To see this, assume the optimisticd′=19d^\{\\prime\}=19and consider the rates of[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1), where for a distribution in a Sobolev class with smoothnessα\\alpha, leads to constantsc=αc=\\alphaandc′=2​αc^\{\\prime\}=2\\alphawhen the distance metric is the total variation \(TV\) distance\. Underα=2\\alpha=2, corresponding to the data\-generating distribution admitting smooth second derivatives, one obtains the asymptotic rate ofΘ\(n−2/23\)\\Theta\(n^\{\-2/23\}\), which means we need more than1011×10^\{11\}\\timessamples to observe a10×10\\timesimprovement in the total variation distance\. In order to obtain a modestΘ\(n−1/4\)\\Theta\(n^\{\-1/4\}\)bound on distribution learning, we need to assumeα=9\.5\\alpha=9\.5, requiring smoothness up to the ninth derivative of the data\-generating distribution\! On the other hand, we observe much faster rates in practice\.[Liang et al\. \(2026\)](https://arxiv.org/html/2609.20883#bib.bib34)study scaling behavior of the Fréchet Inception Distance \(FID\)\([Heusel et al\., 2017](https://arxiv.org/html/2609.20883#bib.bib11)\), a common pseudo\-metric for Generative AI, with compute \(which we denote ascomp\\mathrm\{comp\}in this discussion\) and data\. They observe that optimal training requires the number of samplesn=O⁡\(comp0\.4319\)n=O\(\\mathrm\{comp\}^\{0\.4319\}\), and FID decreases asO⁡\(comp−0\.234\)O\(\\mathrm\{comp\}^\{\-0\.234\}\), implying aO\(n−0\.234/0\.4319\)≈O\(n−0\.54\)O\(n^\{\-0\.234/0\.4319\}\)\\approx O\(n^\{\-0\.54\}\)rate of the FID with the number of samples under optimal training \(also an assumption made theoretically\), much well\-behaved than predicted by theory\. Similarly,[Henighan et al\. \(2020\)](https://arxiv.org/html/2609.20883#bib.bib35)observe aconst\.\+O⁡\(n−0\.3\)\\mathrm\{const\.\}\+O\(n^\{\-0\.3\}\)relationship of loss \(which does not equal to distance between distributions\) with the number of samples for images in ad=64d=64dimensional space, andconst\.\+O⁡\(n−0\.26\)\\mathrm\{const\.\}\+O\(n^\{\-0\.26\}\)relationship for images in ad=256d=256dimensional space\. Here the constant is treated as an un\-improvable loss, pertaining to modeling or compute limitations\.

In this work, we aim to disambiguate this gap between theory and practice by shifting focus from worst\-case minimax bounds to average\-case analysis of the Bayesian risk\. We hypothesize that smoothness assumptions such as Hölder or Sobolev smoothness on the target distribution are not enough to capture the structure of distributions that often appear in real applications\. We imagine a realistic prior over the space of distributions to create well\-separated, sparse clusters, such that smooth densities are not weighted equally to their smooth perturbations, as explained in Section[3](https://arxiv.org/html/2609.20883#S3)\. We introduce the notion of a “Sparse Dimension” in Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3), that measures the sparsity of a prior, and goes to∞\\inftyas the prior becomes less sparse\. Using the proposed notion of sparse priors, we study the Bayes’ risk of distribution learning and learning to sample from distributions\. We show in Section[4](https://arxiv.org/html/2609.20883#S4)that akk\-sparse prior admits a lower bound ofΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)on the Bayes’ risk defined in Section[2](https://arxiv.org/html/2609.20883#S2)under both the total variation and Wasserstein distances, which is a significant improvement over prior worst case bounds\. Whilekkcan still depend on and be of the order ofdd, our bounds do not suffer from the curse of dimensionality for any finitekkin terms of their dependence on the number of samples\. In Section[5](https://arxiv.org/html/2609.20883#S5), we show the existence of a distribution estimator that achieves a Bayes’ risk ofO⁡\(k​log⁡n/n\)O\(\\sqrt\{k\\log n\}/\\sqrt\{n\}\)for akk\-sparse prior under the total variation distance, thus matching our lower bounds up to logarithmic terms\. We show the statistical equivalence of distribution learning and learning to sample in Sections[4](https://arxiv.org/html/2609.20883#S4)and[5](https://arxiv.org/html/2609.20883#S5)\. We thus define a realistic class of priors that take a step towards explaining the gap between theory and practice of distribution learning and Generative AI\.

### 1\.1Summary of Key Contributions

We summarize our key contributions below:

1. 1\.Sparse Dimension:We introduce the formal problem statement and notation in Section[2](https://arxiv.org/html/2609.20883#S2)\. We introduce the notion of sparse priors and sparsity in Section[3](https://arxiv.org/html/2609.20883#S3)\. We present an intuitive notion for a realistic prior over the space of distributions that creates well\-separated clusters\. Within each cluster, most distributions have low density in the prior, with few distributions having high density\. We formalize this notion to define the Sparse Dimension in Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3), which measures how sparse a given distribution is\. We show in Section[3](https://arxiv.org/html/2609.20883#S3)that the constructions in popular theoretical minimax guarantees on distribution learning correspond to infinitely high sparse dimensions, and hence do not satisfy our bounds\. We show how the geometric notion of Assouad dimension of the support of a distribution can guarantee the sparsity of the distribution, even though that is not a necessary condition in Theorem[3\.1](https://arxiv.org/html/2609.20883#S3.Thmtheorem1)\. We further show thatkk\-sparsity implies the existence of a high\-measure subset of the support that satisfies similar constraints as the Assouad’s dimension in Theorem[3\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem2)\. We further show motivating examples of calculations of the sparsity of some distributions in Section[3\.1](https://arxiv.org/html/2609.20883#S3.SS1), which can be used for constructing sparse priors\.
2. 2\.Lower bounds using Sparse Dimension:We proceed to discuss Bayes’ optimality of distribution learning and learning to sample from distributions under a sparse prior\. We first show in Theorem[4\.1](https://arxiv.org/html/2609.20883#S4.Thmtheorem1)that sampling is at least as hard as learning a distribution under any distance \(pseudo\-\)metric, which allows us to focus on information theoretic lower bounds on distribution learning, which imply bounds on learning to sample\. This generalizes the minimax reduction shown in[Singh et al\. \(2018\)](https://arxiv.org/html/2609.20883#bib.bib28)to the Bayesian case\. Theorems[4\.2](https://arxiv.org/html/2609.20883#S4.Thmtheorem2)and[4\.3](https://arxiv.org/html/2609.20883#S4.Thmtheorem3)show that akk\-sparse prior defined using the total variation and Wasserstein \(W1\) distance respectively imply lower bound ofΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)on the Bayes’ risk, wherennis the number of samples\. This is interesting on several fronts\. First, it proves a bound on distribution learning that doesn’t suffer from the curse of dimensionality as in prior work, and discusses the Bayes’ risk instead of restricting to a pessimistic minimax risk\. Second, our proof techniques primarily reduce the analysis of the lower bound of the non\-parametric estimation problem to a uniform prior overkkparameters\. Thus similar bounds for other distance metrics not shown in this paper can be derived using techniques inspired from parametric lower bounds for the respective distance metrics\. Third, we see that our bounds are especially distinct from the submanifold analysis of[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2)that gives vacuous bounds for the TV distance, or the bounds of[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)that are worse for the TV distance than the W1 distance\.
3. 3\.Upper bounds using Sparse Dimension:We then shift our focus to upper bounds on Bayesian learning of distributions and learning to sample\. Theorem[5\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem1)shows that density estimation is at least as hard as learning to sample under any distance metric, so that our upper bounds on distribution learning, which by definition apply to density estimation, also apply to learning to sample\. Finally, we prove the existence of an estimator that achieves a Bayes risk ofO⁡\(k​log⁡n/n\)O\(\\sqrt\{k\\log n\}/\\sqrt\{n\}\)for akk\-sparse prior under the TV distance in Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)\. We utilize the framework of[Ghosal et al\. \(2000\)](https://arxiv.org/html/2609.20883#bib.bib30)that study posterior contraction around a single target distribution to show bounds on Bayesian learning assuming a true data\-generating prior\. Our upper bounds assume that the likelihood ratio between any two distributions is bounded by a constantbl​rb\_\{lr\}, which is not assumed for our lower bounds\. Note that the asymptotic bound does not depend on the value ofbl​rb\_\{lr\}, but only on its finiteness\. We exploit this in Corollary[5\.2\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem2.Thmcorollary1)to show the same upper bound as in Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)while assuming a relaxed bound on the likelihood ratio, which increases sub\-linearly in the number of samplesnnwith high probability\. We show a simple example of a Gaussian location family that satisfies the assumptions of the Corollary\. We also discuss that assuming boundedness of the support of distributions implies an upper bound on the W1 distance in terms of the TV distance, allowing us to extend our results to the W1 distance given akk\-sparse prior under the TV distance\. This is similar to the derivation of upper bounds followed by[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)\.
4. 4\.Asymptotic Comparison of Bounds:We have thus shown the existence of upper and lower bounds that match up to logarithmic terms\. We highlight that our upper and lower bounds are asymptotic in bothnnandkk\. This does not make our bounds vacuous for smallkkhowever, since by definition akk\-sparse prior is alwaysk′k^\{\\prime\}\-sparse fork′\>kk^\{\\prime\}\>k\. We thus make two separate asymptotic statements for clarity\. First, our upper and lower bounds match up to logarithmic terms when considering asymptotics innnandkk\. Second, our upper and lower bounds match up to logarithmic terms when considering asymptotics innnwhile keepingkkconstant for anykk\. In the latter, the constants hidden by the asymptotics may not depend similarly onkkfor the upper and lower bounds\.
5. 5\.Conclusion:We thus establish a non\-trivial class of realistic priors that do not suffer from the curse of dimensionality, which is a step towards explaining the gap between theory and practice in the field of distribution learning and generative AI\.

### 1\.2Related Work

Prior Results on Minimax Optimality\.Minimax optimality of diffusion models, or generative AI in general have been studied in many works before\.[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)discuss the minimax optimality of Generative Adversarial Networks \(GANs\), where they show that distribution learning for a Sobolev smooth target distribution suffers from a minimax lower bound of the typeΩ⁡\(n−cd\+c′\)\\Omega\(n^\{\-\\frac\{c\}\{d\+c^\{\\prime\}\}\}\)under an IPM corresponding to a Sobolev function class, wherec,c′c,c^\{\\prime\}depend on the Sobolev classes\. The authors then show that these rates are achievable by a non\-parametric Sobolev GAN, and show generalization guarantees for a leaky\-ReLU GAN using the pseudo\-dimension arguments of[Bartlett et al\. \(2019\)](https://arxiv.org/html/2609.20883#bib.bib18)\. The authors also show that the dependence onddin their bounds can be replaced withd′d^\{\\prime\}, the intrinsic dimensionality, where the intrinsic dimensionality specifcally determines the exponential rate of decay of the eigenvalues of the integral operator corresponding to an RKHS\.[Singh et al\. \(2018\)](https://arxiv.org/html/2609.20883#bib.bib28)generalize the analysis of[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)by considering general adversarial losses \(which are only guaranteed to be pseudo\-metrics\) and other spaces beyond Sobolev spaces\. They additionally show the minimax equivalence of density estimation and learning to sample, so that the results established for sampling in many works discussed herein apply directly to density esimation as well\.

[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)was one of the first papers to discuss the minimax optimality of score\-based diffusion models\. They derive similar lower bounds as[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)for Besov smooth target distributions and under the TV and W1 distances\. In addition, they show the existence of a neural network that can approximate the score function, and discuss generalization guarantees on learning the neural networks using the techniques of[Suzuki \(2019\)](https://arxiv.org/html/2609.20883#bib.bib19)\. They also show a matching upper bound, and extend their results to intrinsic dimensionality where they define a linear map between the intrinsic space of dimensiond′d^\{\\prime\}and the support of the true distribution inℝd\\mathbb\{R\}^\{d\}\.

[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2)consider a much more general setting of intrinsic dimensionality, where they define a submanifold inℝd′\\mathbb\{R\}^\{d^\{\\prime\}\}that can be mapped to the support of target distribution inℝd\\mathbb\{R\}^\{d\}using an atlas of homeomorphisms\. They assume Hölder smoothness of the target distribution and show a similar lower bound ofΩ⁡\(n−cd′\+c′\)\\Omega\(n^\{\-\\frac\{c\}\{d^\{\\prime\}\+c^\{\\prime\}\}\}\)for a Hölder class of IPMs that interpolate between the W1 and the TV distance\. Interestingly, as noted in the paper, the bounds in[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2)are vacuous for the TV distance, and match the bounds of[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1)if the submanifold reduces to the spaceℝd\\mathbb\{R\}^\{d\}\. The follow\-up work by[Tang and Yang \(2024\)](https://arxiv.org/html/2609.20883#bib.bib4)proves that score\-based diffusion models achieve this rate \(upto poly\-log factors\) using techniques similar to[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)\. Similar to[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2), the work by[Fu et al\. \(2024\)](https://arxiv.org/html/2609.20883#bib.bib10)assumes Hölder smoothness of the target function\. However,[Fu et al\. \(2024\)](https://arxiv.org/html/2609.20883#bib.bib10)consider a conditional diffusion model, where instead of learning a target distribution over some space𝒳\\mathcal\{X\}, the goal is to learn a conditional distribution over𝒳\\mathcal\{X\}with inputs from𝒴\\mathcal\{Y\}\. Similar to previous results, they also show minimax bounds of the typeΩ⁡\(n−cd\+c′\)\\Omega\(n^\{\-\\frac\{c\}\{d\+c^\{\\prime\}\}\}\)and show that score\-based diffusion models match these rates upto poly\-log terms using the techniques of[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)\.

Computational Efficiency of Learning\.An interesting observation from the above bounds is that both GANs and score\-based diffusion models have been shown to be minimax optimal, yet diffusion often performs better in practice\. We conjecture this gap arises from the assumption of perfect optimization of the underlying neural network, whether the neural network corresponds to a GAN\([Liang, 2021](https://arxiv.org/html/2609.20883#bib.bib1)\), or a score\-based diffusion model\([Oko et al\., 2023](https://arxiv.org/html/2609.20883#bib.bib9);[Tang and Yang, 2024](https://arxiv.org/html/2609.20883#bib.bib4);[Fu et al\., 2024](https://arxiv.org/html/2609.20883#bib.bib10)\)\. Computational efficiency and optimization error thus play a significant role in the applicability of bounds, and perfect optimization is not always a realistic assumption under computational constraints\. While we don’t study training dynamics of any generative or distribution learning algorithm, some work in this direction has been done by[Dupuis et al\. \(2025\)](https://arxiv.org/html/2609.20883#bib.bib20)that show algorithm and data\-dependent generalization bounds on learning the underlying neural networks for diffusion\. We note in general that we focus on statistical efficiency of algorithms in this work, and defer a discussion on computational efficiency to future work\.

Learning under a Non\-Parametric Prior\.In order to show our bounds, we assume that the true prior is perfectly known in this paper, which may not be true realistically\. We don’t discuss guarantees on learning the prior, or constructing optimization algorithms to account for priors\. The framework ofdata\-driven algorithm designdiscussed in[Balcan \(2020\)](https://arxiv.org/html/2609.20883#bib.bib21)suggests tuning hyperparameters for algorithms using previously observed tasks, which is an empirical route to approximating Bayes optimal learning algorithms for an unknown prior\. Guarantees on learning hyperparameters for linear regression using previously observed, similar tasks were discussed in[Balcan et al\. \(2022\)](https://arxiv.org/html/2609.20883#bib.bib22),[Balcan et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib23)and[Balcan et al\. \(2025\)](https://arxiv.org/html/2609.20883#bib.bib24)\.[Goyal et al\. \(2026\)](https://arxiv.org/html/2609.20883#bib.bib32)generalize this by giving guarantees on learning hyperparameters for general regression tasks with a convex loss\.

## 2Problem Statement and Notation

We consider the problem of learning an unknown distributionπ\\pidefined on the space𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}, givennnsamplesX1,…,Xn∼i\.i\.d\.πX\_\{1\},\\ldots,X\_\{n\}\\stackrel\{\{\\scriptstyle\\text\{i\.i\.d\.\}\}\}\{\{\\sim\}\}\\pisampled i\.i\.d\. fromπ\\pi\. We additionally assume thatπ∼𝒫\\pi\\sim\\mathcal\{P\}is sampled from a known prior𝒫\\mathcal\{P\}, over the set of distributions𝔻\\mathbb\{D\}\. Letπ^​\(X1,…,Xn\)\\hat\{\\pi\}\(X\_\{1\},\\ldots,X\_\{n\}\)be the estimated distribution fromnnsamples\. When obvious from context, we will denoteπ^​\(X1,…,Xn\)\\hat\{\\pi\}\(X\_\{1\},\\ldots,X\_\{n\}\)by the short\-handπ^n\\hat\{\\pi\}\_\{n\}\. For brevity, we will denote the set ofnnsamples by the singular𝐗∈𝒳n\\mathbf\{X\}\\in\\mathcal\{X\}^\{n\}\. We will also talk about sampling algorithms, that learn to sample from a distribution given samples\. We will analogously denote the learned sampling algorithm by𝒜^n\\hat\{\\mathcal\{A\}\}\_\{n\}and the distribution that the sampling algorithm actually samples from will be denoteddist⁡\(𝒜^n\)\\mathrm\{dist\}\(\\hat\{\\mathcal\{A\}\}\_\{n\}\)\. Unless specified explicitly, we assume a distance functionρ⁡\(⋅,⋅\)\\rho\(\\cdot,\\cdot\)between distributions to be a pseudo\-metric, which means that it is non\-negative, symmetric and follows the triangle inequality, butρ⁡\(π1,π2\)=0​⟹π1=π2\\rho\(\\pi\_\{1\},\\pi\_\{2\}\)=0\\;\\not\\\!\\\!\\\!\\implies\\pi\_\{1\}=\\pi\_\{2\}\. We are interested in the expected distance betweenπ^n\\hat\{\\pi\}\_\{n\}andπ\\pigiven by𝔼X1,…,Xn∼i\.i\.d\.π​\[ρ⁡\(π^n,π\)\]\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\stackrel\{\{\\scriptstyle\\text\{i\.i\.d\.\}\}\}\{\{\\sim\}\}\\pi\}\[\\rho\(\\hat\{\\pi\}\_\{n\},\\pi\)\]\. We will drop the subscript on the expectation when obvious from context\. Define the Bayes’ risk of estimators ofπ\\pias:

RB​a​y​e​s​\(π^n,𝒫\)=𝔼π∼𝒫​\[𝔼⁡\[ρ⁡\(π^n,π\)\]\]\.\\displaystyle R\_\{Bayes\}\(\\hat\{\\pi\}\_\{n\};\\mathcal\{P\}\)=\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\[\\rho\(\\hat\{\\pi\}\_\{n\},\\pi\)\]\]\.\(1\)We will also be investigating Bayes’ risk for the sampling algorithm, which will be given as follows using slight re\-use of notation:

RB​a​y​e​s​\(𝒜^n,𝒫\)=𝔼π∼𝒫​\[𝔼⁡\[ρ⁡\(dist⁡\(𝒜^n\),π\)\]\]\.\\displaystyle R\_\{Bayes\}\(\\hat\{\\mathcal\{A\}\}\_\{n\};\\mathcal\{P\}\)=\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\[\\rho\(\\mathrm\{dist\}\(\{\\hat\{\\mathcal\{A\}\}\_\{n\}\}\),\\pi\)\]\]\.\(2\)
Section[4](https://arxiv.org/html/2609.20883#S4)studies lower bounds on the Bayes’ risk of estimation over a class of priors𝔓\\mathfrak\{P\}given byinfπ^sup𝒫∈𝔓RB​a​y​e​s​\(π^n,𝒫\)\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}R\_\{Bayes\}\(\\hat\{\\pi\}\_\{n\};\\mathcal\{P\}\)\. Correspondingly, the Bayes’ risk of sampling will be lower bounded by the expression,inf𝒜^sup𝒫∈𝔓RB​a​y​e​s​\(𝒜^,𝒫\)\\inf\_\{\\hat\{\\mathcal\{A\}\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}R\_\{Bayes\}\(\\hat\{\\mathcal\{A\}\};\\mathcal\{P\}\)\. This is a notable departure from prior work that study the minimax risk defined byinfπ^supπ∈𝔻𝔼⁡\[ρ⁡\(π^n,π\)\]\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\pi\\in\\mathbb\{D\}\}\\mathbb\{E\}\[\\rho\(\\hat\{\\pi\}\_\{n\},\\pi\)\]andinf𝒜^supπ∈𝔻𝔼⁡\[ρ⁡\(dist⁡\(𝒜^n\),π\)\]\\inf\_\{\\hat\{\\mathcal\{A\}\}\}\\sup\_\{\\pi\\in\\mathbb\{D\}\}\\mathbb\{E\}\[\\rho\(\\mathrm\{dist\}\(\{\\hat\{\\mathcal\{A\}\}\_\{n\}\}\),\\pi\)\]for distribution learning and sampling respectively\.

We will denote byρℱ\\rho\_\{\\mathcal\{F\}\}the Integral Probability Metric \(IPM\) corresponding to the function classℱ\\mathcal\{F\}as defined below\. Note that by definition, any IPM is a pseudo\-metric\.

###### Definition 1\(Integral Probability Metric \(IPM\)\([Chewi et al\., 2024](https://arxiv.org/html/2609.20883#bib.bib3)\)\)\.

A \(pseudo\-\)metricρℱ\(\.,\.\)\\rho\_\{\\mathcal\{F\}\}\(\.,\.\)between two probability measuresμ,ν\\mu,\\nuis called an integral probability metric \(IPM\) if it can be written in the form

ρℱ​\(μ,ν\)=supf∈ℱ\|∫𝒳f⁡\(X\)​𝑑μ​\(X\)−∫𝒳f⁡\(X\)​𝑑ν​\(X\)\|\.\\displaystyle\\rho\_\{\\mathcal\{F\}\}\(\\mu,\\nu\)=\\sup\_\{f\\in\\mathcal\{F\}\}\\left\|\\int\_\{\\mathcal\{X\}\}f\(X\)\\mathrm\{d\}\\mu\(X\)\-\\int\_\{\\mathcal\{X\}\}f\(X\)\\mathrm\{d\}\\nu\(X\)\\right\|\.

Several popular distance metrics are IPMs over different classesℱ\\mathcal\{F\}\. For instance, the Wasserstein\-1 distance is the IPM overℱL​i​p​1\\mathcal\{F\}\_\{Lip1\}, the class of all 1\-Lipschitz functions, the TV distance is half of the IPM overℱ1\\mathcal\{F\}\_\{1\}, the class of all 1\-bounded functions\([Tang and Yang, 2023](https://arxiv.org/html/2609.20883#bib.bib2)\), and Maximum Mean Discrepancy \(MMD\)\([Gretton et al\., 2012](https://arxiv.org/html/2609.20883#bib.bib12)\)is the IPM over functions in an appropriate RKHSℋ\\mathcal\{H\}with function norm‖f‖ℋ≤1\\\|f\\\|\_\{\\mathcal\{H\}\}\\leq 1\([Chewi et al\., 2024](https://arxiv.org/html/2609.20883#bib.bib3)\)\. As a shorthand, we will writeρW​1\\rho\_\{W1\}andρT​V\\rho\_\{TV\}when referring to the Wasserstein\-1 and TV distance respectively\. We will also denote the KL\-divergence \(which is not a pseudo\-metric\) between distributionsμ,ν\\mu,\\nuasDK​L\(μ∥ν\)D\_\{KL\}\(\\mu\\\|\\nu\)\.

Lastly, we will define the ball of radiusrraround distributionν\\nufor a distance \(pseudo\-\)metricρ\\rhoasBρ​\(r,ν\)=\{μ∈𝔻:ρ⁡\(μ,ν\)≤r\}B\_\{\\rho\}\(r,\\nu\)=\\\{\\mu\\in\\mathbb\{D\}:\\rho\(\\mu,\\nu\)\\leq r\\\}\. For a distribution𝒫\\mathcal\{P\}over𝔻\\mathbb\{D\}, we will denote the total probability of the ball by𝒫​\(Bρ​\(r,ν\)\)\\mathcal\{P\}\(B\_\{\\rho\}\(r,\\nu\)\)\.

## 3Sparse Dimension

As we mention previously, we hypothesize that theoretical bounds on distribution learning tend to be pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications\. As an example, we show the pdfs of two distributions in Figure[1](https://arxiv.org/html/2609.20883#S3.F1)that are both heuristically “smooth” and “close” to each other\. These distributions would produce similar samples, and as such, we might not want to distinguish between them\. Such constructions are common in literature, such as the minimax construction of[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2)that consists of a uniform distribution over a ball, with small perturbations\.

![Refer to caption](https://arxiv.org/html/2609.20883v1/figs/gaussian_kink_3.png)Figure 1:The standard Gaussian illustrated with a small perturbation of it, of the type common information theoretic lower bounds often consider\. The perturbations are small enough that it would take an increasing number of samples to distinguish them as the dimensionality increases\. In our framework however, we argue that such small perturbations likely receive small prior mass in realistic scenarios, which relaxes the sample complexity requirement for identifying the more likely distribution\.We propose assuming a prior over the space of all distributions that captures the structure of realistic distributions\. Intuitively, such a prior should create well\-separated clusters in the space of all distributions\. Within each cluster, most distributions have low density in the prior, with few distributions having high density\. As an example, we consider the distributions over animal images, where we expect the clusters for different animal images like cats and dogs to be well\-separated\. A prior over the space of animal image distributions should give equal weight to the cat image and the dog image clusters\. Inside the dog image cluster, we expect to see a global distribution of all dog images with high density in the prior, but several distributions for different breeds of dogs, or dogs doing different actions, all with a lower density than the global distribution\. However a distribution corresponding to dog images with a particular pixel blacked out is probably not of interest to us, and would have very low/zero density\.

Thus we intuit that most of the probability mass in realistic distributions is concentrated on a small subset of all possible distributions, with the vast majority of the space being nearly empty\. This sparsity extends recursively so that only a few sub\-distributions within each cluster—e\.g\., cats, dogs, or specific dog breeds—capture the essential structure, while all other sub\-distributions have negligible mass\. The analysis of[Horwitz et al\. \(2025\)](https://arxiv.org/html/2609.20883#bib.bib25)for world models, where the authors suggest plotting an atlas of all world models, suggests a similar structure to the one described above if we plot the world models based on their similarity to each other\. Before we define the sparse dimension we note the following definition of the diameter of a set\.

###### Definition 2\(Diameter\)\.

The diameter of a setSSequipped with a distance \(pseudo\-\)metricρ\\rho, denoteddiam⁡\(S\)\\mathrm\{diam\}\(S\), is defined such thatdiam⁡\(S\)=supa1,a2∈Sρ⁡\(a1,a2\)\\mathrm\{diam\}\(S\)=\\sup\_\{a\_\{1\},a\_\{2\}\\in S\}\\rho\(a\_\{1\},a\_\{2\}\)\.

We now define the sparse dimension that formalizes our intuition that for a sparse distribution, a big fraction of the probability of a set should lie inside a relatively small subset\.

###### Definition 3\(Sparse Dimension\)\.

Given a distribution𝒫\\mathcal\{P\}on the space𝔻\\mathbb\{D\}and a distance \(pseudo\-\)metricρ\\rho, we say that𝒫\\mathcal\{P\}is sparse with sparse dimensionk\>0k\>0if there exists ac\>0c\>0such that for every set𝔸⊆𝔻\\mathbb\{A\}\\subseteq\\mathbb\{D\}andϵ∈\(0,1\]\\epsilon\\in\(0,1\], there exists a subset𝔹⊆𝔸\\mathbb\{B\}\\subseteq\\mathbb\{A\}that satisfies𝒫⁡\(𝔹\)≥ϵ​𝒫​\(𝔸\)\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{A\}\)anddiam⁡\(𝔹\)≤c​ϵ1/k​diam​\(𝔸\)\\mathrm\{diam\}\(\\mathbb\{B\}\)\\leq c\\epsilon^\{1/k\}\\mathrm\{diam\}\(\\mathbb\{A\}\)\.

Intuitively, we call a distribution sparse if every set in the support of the distribution contains a small, dense subset\. The sparse dimension is a measure of the sparsity, where a lower sparse dimension implies a sparser distribution\. Note that by definition, akk\-sparse distribution is immediatelyk′k^\{\\prime\}\-sparse for anyk′\>kk^\{\\prime\}\>k\. That is, the definition does not requirekkto be the smallest number that satisfies the sparsity condition\. We show below how certain properties of the support𝔻\\mathbb\{D\}of the distribution𝒫\\mathcal\{P\}can imply thekk\-sparsity of𝒫\\mathcal\{P\}, although these aren’t necessary conditions\. We first introduce the notion of covering number and Assouad dimension of a set\.

We define therr\-covering number of a space as the number of points in the smallest set required to ensure that all points in the space are at a distance at mostrrfrom some element on the set\.

###### Definition 4\(Covering number\([Shalev\-Shwartz and Ben\-David, 2014](https://arxiv.org/html/2609.20883#bib.bib29)\)\)\.

For a set𝔻\\mathbb\{D\}with a distance \(pseudo\-\)metricρ\\rho, consider a set of points𝔸\\mathbb\{A\}such that for any elementμ∈𝔻\\mu\\in\\mathbb\{D\},∃ν∈𝔸\\exists\\nu\\in\\mathbb\{A\}such thatρ⁡\(μ,ν\)≤r\\rho\(\\mu,\\nu\)\\leq r\. Then𝔸\\mathbb\{A\}is called anrr\-cover of𝔻\\mathbb\{D\}\. We defineN⁡\(r,𝔻\)N\(r,\\mathbb\{D\}\), therr\-covering number of𝔻\\mathbb\{D\}, as the cardinality of the smallestrr\-cover of𝔻\\mathbb\{D\}\. Thus, if therr\-cover𝔸\\mathbb\{A\}is the smallest possible,\|𝔸\|=N⁡\(r,𝔻\)\|\\mathbb\{A\}\|=N\(r,\\mathbb\{D\}\)\.

We then define the Assouad dimension, which bounds therr\-covering number for any subset of diameterRR\.

###### Definition 5\(Assouad dimension\([Fraser, 2020](https://arxiv.org/html/2609.20883#bib.bib33)\)\)\.

Consider a non\-empty set𝔻\\mathbb\{D\}with a distance \(pseudo\-\)metricρ\\rho\. The Assouad dimension of𝔻\\mathbb\{D\}, denoteddimA​\(𝔻\)\\mathrm\{dim\}\_\{A\}\(\\mathbb\{D\}\)is defined as:

dimA\(𝔻\)=inf\{k:there existsC\>0such that\\displaystyle\\mathrm\{dim\}\_\{A\}\(\\mathbb\{D\}\)=\\inf\\\{k:\\text\{there exists \}C\>0\\text\{ such that \}∀0<r<R​and​μ∈𝔻,\\displaystyle\\forall\\;0<r<R\\text\{ and \}\\mu\\in\\mathbb\{D\},N\(r,Bρ\(R,μ\)∩𝔻\)≤C\(R/r\)k\}\.\\displaystyle N\(r,B\_\{\\rho\}\(R,\\mu\)\\cap\\mathbb\{D\}\)\\leq C\(R/r\)^\{k\}\\\}\.

Thus, given a set with Assouad dimensionkkimplies therr\-covering of any subset of diameterRRis proportional to\(R/r\)k\(R/r\)^\{k\}\. This allows us to bound the sparse dimension of a distribution over the set as follows\.

###### Theorem 3\.1\.

Consider a set𝔻\\mathbb\{D\}equipped with the distance \(pseudo\-\)metricρ\\rhowith Assouad dimensionkk\. For anyδ\>0\\delta\>0, any distribution on𝔻\\mathbb\{D\}is always at most\(k\+δ\)\(k\+\\delta\)\-sparse\.

###### Proof\.

It follows from Definition[5](https://arxiv.org/html/2609.20883#Thmdefinition5)that for someν∈𝔻\\nu\\in\\mathbb\{D\},B⁡\(R,ν\)∩𝔻B\(R,\\nu\)\\cap\\mathbb\{D\}is covered by at mostC​\(R/r\)k\+δC\(R/r\)^\{k\+\\delta\}balls of radiusrrcentered at points in𝔻\\mathbb\{D\}, for some constantC\>0C\>0\. Now, for any set𝔸⊆𝔻\\mathbb\{A\}\\subseteq\\mathbb\{D\}of diameterdiam⁡\(𝔸\)=R\\mathrm\{diam\}\(\\mathbb\{A\}\)=R, construct anRRball that encompasses all points in𝔸\\mathbb\{A\}, centered at one of the points in𝔸\\mathbb\{A\}\. For anyϵ∈\(0,1\]\\epsilon\\in\(0,1\], we construct balls of radiusr=\(C​ϵ\)1/\(k\+δ\)​Rr=\(C\\epsilon\)^\{1/\(k\+\\delta\)\}Rsuch that we need at most⌊1/ϵ⌋\\lfloor 1/\\epsilon\\rfloorsuch balls to cover the set𝔸\\mathbb\{A\}, where⌊α⌋\\lfloor\\alpha\\rflooris the greatest integer≤α\\leq\\alpha\. Note that if\(C​ϵ\)1/\(k\+δ\)\>1\(C\\epsilon\)^\{1/\(k\+\\delta\)\}\>1, thenr\>Rr\>Rand we only need 1 such ball to cover the set𝔸\\mathbb\{A\}, which still falls inside our≤⌊1/ϵ⌋\\leq\\lfloor 1/\\epsilon\\rfloorbound\. By a pigeonhole argument, the intersection of at least one of these balls with𝔸\\mathbb\{A\}has a total probability≥ϵ​𝒫​\(𝔸\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{A\}\)with diameter≤2​\(C​ϵ\)1/\(k\+δ\)​R\\leq 2\(C\\epsilon\)^\{1/\(k\+\\delta\)\}R, such that the intersection of this ball with𝔸\\mathbb\{A\}satisfies the conditions of Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3)for a constantc=2​C1/\(k\+δ\)c=2C^\{1/\(k\+\\delta\)\}\. ∎

A few corollaries are immediate, which will be useful to us later\. We show that any distribution over akk\-Ahlfors regular set is always at mostkk\-sparse\.

###### Corollary 3\.1\.1\.

Consider akk\-Ahlfors regular set𝔻\\mathbb\{D\}equipped with the distance \(pseudo\-\)metricρ\\rhosuch that there exists a Borel measureℳ\\mathcal\{M\}with support𝔻\\mathbb\{D\}and a constantC≥1C\\geq 1such that for anyν∈𝔻\\nu\\in\\mathbb\{D\}and radius0<r≤diam⁡\(𝔻\)0<r\\leq\\mathrm\{diam\}\(\\mathbb\{D\}\),C−1​rk≤ℳ⁡\(Bρ​\(r,ν\)∩𝔻\)≤C​rkC^\{\-1\}r^\{k\}\\leq\\mathcal\{M\}\(B\_\{\\rho\}\(r,\\nu\)\\cap\\mathbb\{D\}\)\\leq Cr^\{k\}\. Any distribution on𝔻\\mathbb\{D\}is always at mostkk\-sparse\.

###### Proof\.

From Proposition[B\.3](https://arxiv.org/html/2609.20883#A2.Thmtheorem3), we note that for someν∈𝔻\\nu\\in\\mathbb\{D\},B⁡\(R,ν\)∩𝔻B\(R,\\nu\)\\cap\\mathbb\{D\}is covered by at mostC2​\(3​R/r\)kC^\{2\}\(3R/r\)^\{k\}balls of radiusrrcentered at points in𝔻\\mathbb\{D\}\. Thus𝔻\\mathbb\{D\}has Assouad dimensionkk, and similar arguments to Theorem[3\.1](https://arxiv.org/html/2609.20883#S3.Thmtheorem1), where we can now replace\(k\+δ\)\(k\+\\delta\)withkk\(for a different value ofCC\)\. ∎

Using a similar technique, we show that a distribution over a finite dimensional space is always sparse given an appropriate distance \(pseudo\-\)metric\. We will rely on this result for our construction of hard instances for showing lower bounds in Section[4](https://arxiv.org/html/2609.20883#S4)\.

###### Corollary 3\.1\.2\.

Any distribution over a subset ofℝd\\mathbb\{R\}^\{d\}, denoted𝔻⊆ℝd\\mathbb\{D\}\\subseteq\\mathbb\{R\}^\{d\}equipped with anlal\_\{a\}norm fora∈\[1,∞\]a\\in\[1,\\infty\]as the distance \(pseudo\-\)metric is always at mostdd\-sparse\.

###### Proof\.

Proceeds exactly the same as Corollary[3\.1\.1](https://arxiv.org/html/2609.20883#S3.Thmtheorem1.Thmcorollary1)withC=1C=1by invoking Proposition[B\.2](https://arxiv.org/html/2609.20883#A2.Thmtheorem2)instead of Proposition[B\.3](https://arxiv.org/html/2609.20883#A2.Thmtheorem3)\. ∎

We note thatkk\-sparsity of a distribution does not necessarily imply boundedness of the covering number of it’s support\. We show below thatkk\-sparsity implies that there exists a high\-measure subset of the support with a covering number with a similar expression as the Assouad dimension\.

###### Theorem 3\.2\.

Assume there exists akk\-sparse prior𝒫\\mathcal\{P\}that satisfies Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3)with constantccover the support𝔻\\mathbb\{D\}of diameterRRunder a distance \(pseudo\-\)metricρ\\rho\. Then for anyδ∈\(0,1\)\\delta\\in\(0,1\)and0<r<c​R0<r<cR, there exists a subset𝔹⊆𝔻\\mathbb\{B\}\\subseteq\\mathbb\{D\}such that𝒫⁡\(𝔹\)≥δ​𝒫​\(𝔻\)\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq\\delta\\mathcal\{P\}\(\\mathbb\{D\}\)and the covering number of𝔹\\mathbb\{B\}is bounded as:

N⁡\(r,𝔹\)≤⌈log⁡\(1−δ\)log⁡\(1−\(r/\(c​R\)\)k\)⌉≤⌈−log⁡\(1−δ\)​\(c​R\)krk⌉,\\displaystyle N\(r,\\mathbb\{B\}\)\\leq\\left\\lceil\\frac\{\\log\(1\-\\delta\)\}\{\\log\(1\-\(r/\(cR\)\)^\{k\}\)\}\\right\\rceil\\leq\\left\\lceil\-\\log\(1\-\\delta\)\\frac\{\(cR\)^\{k\}\}\{r^\{k\}\}\\right\\rceil,where⌈α⌉\\lceil\\alpha\\rceilis the least integer≥α\\geq\\alpha, and since−1/log\(1−x\)≤1/x\-1/\\log\(1\-x\)\\leq 1/xforx∈\(0,1\)x\\in\(0,1\)\.

###### Proof\.

Letϵ=\(r/\(c​R\)\)k\\epsilon=\(r/\(cR\)\)^\{k\}in Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3), such that there exists a set𝔸1⊆𝔻\\mathbb\{A\}\_\{1\}\\subseteq\\mathbb\{D\}of diameter≤r\\leq rsuch that𝒫⁡\(𝔸1\)≥ϵ​𝒫​\(𝔻\)\\mathcal\{P\}\(\\mathbb\{A\}\_\{1\}\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{D\}\)\. For anyNN, we can similarly find disjoint sets\{𝔸i\}i=1N\\\{\\mathbb\{A\}\_\{i\}\\\}\_\{i=1\}^\{N\}which satisfy𝔸i\+1⊆𝔻/\(⋃j=1i𝔸j\)\\mathbb\{A\}\_\{i\+1\}\\subseteq\\mathbb\{D\}/\(\\bigcup\_\{j=1\}^\{i\}\\mathbb\{A\}\_\{j\}\)such thatdiam⁡\(𝔸i\+1\)≤\(r/R\)​diam​\(𝔻/\(⋃j=1i𝔸j\)\)≤r\\mathrm\{diam\}\(\\mathbb\{A\}\_\{i\+1\}\)\\leq\(r/R\)\\mathrm\{diam\}\(\\mathbb\{D\}/\(\\bigcup\_\{j=1\}^\{i\}\\mathbb\{A\}\_\{j\}\)\)\\leq rand𝒫⁡\(𝔸i\+1\)≥ϵ​𝒫​\(𝔻/\(⋃j=1i𝔸j\)\)=ϵ⁡\(1−∑j=1i𝒫⁡\(𝔸j\)\)\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\+1\}\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{D\}/\(\\bigcup\_\{j=1\}^\{i\}\\mathbb\{A\}\_\{j\}\)\)=\\epsilon\(1\-\\sum\_\{j=1\}^\{i\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{j\}\)\)\. Note that the sets𝔸i\\mathbb\{A\}\_\{i\}are allowed to be null\. Since each of these sets has diameter≤r\\leq r, anrr\-ball centered at any point in the set covers the set\. \(Alternatively, if the set is null it is vacuously covered by anyrr\-ball\.\) Let𝔹=⋃i=1N𝔸i\\mathbb\{B\}=\\bigcup\_\{i=1\}^\{N\}\\mathbb\{A\}\_\{i\}forNNto be chosen later, such that𝔹\\mathbb\{B\}is covered byNNballs of radiusrr\.𝔹\\mathbb\{B\}has total measure𝒫⁡\(⋃i=1N𝔸i\)=∑i𝒫⁡\(𝔸i\)\\mathcal\{P\}\(\\bigcup\_\{i=1\}^\{N\}\\mathbb\{A\}\_\{i\}\)=\\sum\_\{i\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\. We simplify this as follows:

𝒫⁡\(⋃i=1N𝔸i\)\\displaystyle\\mathcal\{P\}\(\\bigcup\_\{i=1\}^\{N\}\\mathbb\{A\}\_\{i\}\)=∑i=1N𝒫⁡\(𝔸i\)≥∑i=1N−1𝒫⁡\(𝔸i\)\+ϵ⁡\(1−∑i=1N−1𝒫⁡\(𝔸i\)\)=ϵ\+\(1−ϵ\)​∑i=1N−1𝒫⁡\(𝔸i\)\\displaystyle=\\sum\_\{i=1\}^\{N\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\\geq\\sum\_\{i=1\}^\{N\-1\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\+\\epsilon\(1\-\\sum\_\{i=1\}^\{N\-1\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\)=\\epsilon\+\(1\-\\epsilon\)\\sum\_\{i=1\}^\{N\-1\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)≥ϵ\+ϵ⁡\(1−ϵ\)\+\(1−ϵ\)2​∑i=1N−2𝒫⁡\(𝔸i\)≥ϵ​∑i=1N−1\(1−ϵ\)i−1\+\(1−ϵ\)N−1​𝒫​\(𝔸1\)\\displaystyle\\geq\\epsilon\+\\epsilon\(1\-\\epsilon\)\+\(1\-\\epsilon\)^\{2\}\\sum\_\{i=1\}^\{N\-2\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\\geq\\epsilon\\sum\_\{i=1\}^\{N\-1\}\(1\-\\epsilon\)^\{i\-1\}\+\(1\-\\epsilon\)^\{N\-1\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{1\}\)≥ϵ​∑i=1N\(1−ϵ\)i−1=1−\(1−ϵ\)N\.\\displaystyle\\geq\\epsilon\\sum\_\{i=1\}^\{N\}\(1\-\\epsilon\)^\{i\-1\}=1\-\(1\-\\epsilon\)^\{N\}\.
LetN=⌈log⁡\(1−δ\)log⁡\(1−\(r/\(c​R\)\)k\)⌉N=\\left\\lceil\\frac\{\\log\(1\-\\delta\)\}\{\\log\(1\-\(r/\(cR\)\)^\{k\}\)\}\\right\\rceilso that𝒫⁡\(𝔹\)≥δ​𝒫​\(𝔻\)\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq\\delta\\mathcal\{P\}\(\\mathbb\{D\}\)as required\. ∎

We now discuss some examples on Sparse Priors\.

###### Example 3\.3\.

As an example of a sparse prior, we show an instantiation of the above result\. Consider the set of Gaussian distributions with unit covariance𝔻=\{𝒩\(θ,Id\):θ∈ℝd,∥θ∥≤1\}\\mathbb\{D\}=\\\{\\mathcal\{N\}\(\\theta,I\_\{d\}\):\\theta\\in\\mathbb\{R\}^\{d\},\\\|\\theta\\\|\\leq 1\\\}\. The Wasserstein\-1 metric between two Gaussians is directly equal to the Euclidean distance between means as given by,ρW​1​\(𝒩⁡\(θ1,Id\),𝒩⁡\(θ2,Id\)\)=‖θ1−θ2‖\\rho\_\{W1\}\(\\mathcal\{N\}\(\\theta\_\{1\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\},I\_\{d\}\)\)=\\\|\\theta\_\{1\}\-\\theta\_\{2\}\\\|\. Thus, any distribution over the meansθ\\thetaresults in an at mostdd\-sparse distribution over all Gaussian distributions with unit covariance indddimensions\. Bounds of the formΘ⁡\(d/n\)\\Theta\(\\sqrt\{d/n\}\)from Sections[4](https://arxiv.org/html/2609.20883#S4)and[5](https://arxiv.org/html/2609.20883#S5)are trivially known for a uniform distribution over the means, and satisfied by the maximum likelihood estimator\([Wasserman, 2010](https://arxiv.org/html/2609.20883#bib.bib26)\)\.

###### Example 3\.4\.

As an example of a prior that is not sparse, we consider the treatment of[Tang and Yang \(2023\)](https://arxiv.org/html/2609.20883#bib.bib2)\. We setγ→0\+\\gamma\\rightarrow 0^\{\+\}in Lemma 2 of the paper to see that for anyb\>0b\>0,n\>0n\>0andα\\alphathat depends on smoothness assumptions, there existH≥exp⁡\(bd​nd2​α\+d\)H\\geq\\exp\(b^\{d\}n^\{\\frac\{d\}\{2\\alpha\+d\}\}\)distributionsμ1,…,μH\\mu\_\{1\},\\ldots,\\mu\_\{H\}with a Hölder smooth pdf such that:

1. 1\.DK​L\(μh∥μl\)≤c1b−2​αn−2​α2​α\+dD\_\{KL\}\(\\mu\_\{h\}\\\|\\mu\_\{l\}\)\\leq c\_\{1\}b^\{\-2\\alpha\}n^\{\-\\frac\{2\\alpha\}\{2\\alpha\+d\}\}for anyh≠lh\\neq l\. That is,ρT​V​\(μh,μl\)≤c1​b−α​n−α2​α\+d\\rho\_\{TV\}\(\\mu\_\{h\},\\mu\_\{l\}\)\\leq\\sqrt\{c\_\{1\}\}b^\{\-\\alpha\}n^\{\-\\frac\{\\alpha\}\{2\\alpha\+d\}\}for anyh≠lh\\neq l, using the Pinsker’s inequalityρT​V​\(μ,ν\)≤DK​L\(μ∥ν\)/2\\rho\_\{TV\}\(\\mu,\\nu\)\\leq\\sqrt\{D\_\{KL\}\(\\mu\\\|\\nu\)/2\}\.
2. 2\.ρT​V​\(μh,μl\)≥c2​b−\(α\+d\)​n−α2​α\+d\\rho\_\{TV\}\(\\mu\_\{h\},\\mu\_\{l\}\)\\geq c\_\{2\}b^\{\-\(\\alpha\+d\)\}n^\{\-\\frac\{\\alpha\}\{2\\alpha\+d\}\}\.

Consider exactlyH=exp⁡\(bd​nd2​α\+d\)H=\\exp\(b^\{d\}n^\{\\frac\{d\}\{2\\alpha\+d\}\}\)of these distributions which form a set𝔸\\mathbb\{A\}of diameterR≤c1​b−α​n−α2​α\+dR\\leq\\sqrt\{c\_\{1\}\}b^\{\-\\alpha\}n^\{\-\\frac\{\\alpha\}\{2\\alpha\+d\}\}in the TV space from point 1\. Further, there can be only 1 of these distributions in any space of diameter<r=c2​b−\(α\+d\)​n−α2​α\+d<r=c\_\{2\}b^\{\-\(\\alpha\+d\)\}n^\{\-\\frac\{\\alpha\}\{2\\alpha\+d\}\}\. A uniform prior over theseHHdistributions thus allows the maximum measure over any space of diameter<r<rto be at most1/H1/H\. Letϵ=2/H\\epsilon=2/Hin Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3), such thatkk\-sparsity implies the existence of set𝔹\\mathbb\{B\}with measure𝒫⁡\(𝔹\)≥2/H\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq 2/Hwith diameterdiam⁡\(𝔹\)≤c​\(2/H\)1/k​R\\mathrm\{diam\}\(\\mathbb\{B\}\)\\leq c\(2/H\)^\{1/k\}R, for some constantcc\. Since any space of diameter<r<rhas measure≤1/H\\leq 1/H,diam⁡\(𝔹\)≥r⟹r≤c​\(2/H\)1/k​R⟹H≤2​ck​bd​k\\mathrm\{diam\}\(\\mathbb\{B\}\)\\geq r\\implies r\\leq c\(2/H\)^\{1/k\}R\\implies H\\leq 2c^\{k\}b^\{dk\}\. WhileHHcan increase arbitrarily withnn, the RHS2​ck​bd​k2c^\{k\}b^\{dk\}cannot, and thus no suchkkandccexist\. Hence this prior is not sparse\. We re\-direct the attention of the reader to Figure[1](https://arxiv.org/html/2609.20883#S3.F1)that shows a construction with small perturbations where we expect both distributions to not receive equal weight in realistic scenarios corresponding to sparse priors\. We expect a similar analysis for the treatment of other works such as[Liang \(2021\)](https://arxiv.org/html/2609.20883#bib.bib1);[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)would follow to show that the assumptions necessitate a non\-sparse prior\.

Note that our definition of sparse dimension controls the rate at which the total measure of any set increases with respect to its diameter\. This notion is similar to the notion of doubling dimension as defined in[Poczos et al\. \(2013\)](https://arxiv.org/html/2609.20883#bib.bib8)and previously in[Kpotufe \(2011\)](https://arxiv.org/html/2609.20883#bib.bib36), where the authors define a distribution𝒫\\mathcal\{P\}over𝔻\\mathbb\{D\}equipped with a distance metricρ\\rhoto have a doubling dimensionkkif there exists a constantCCif for every pointν∈𝔻\\nu\\in\\mathbb\{D\}and0<r<R0<r<R,

𝒫​\(Bρ​\(ν,R\)\)𝒫​\(Bρ​\(ν,r\)\)≤C​\(Rr\)k\.\\displaystyle\\frac\{\\mathcal\{P\}\(B\_\{\\rho\}\(\\nu,R\)\)\}\{\\mathcal\{P\}\(B\_\{\\rho\}\(\\nu,r\)\)\}\\leq C\\left\(\\frac\{R\}\{r\}\\right\)^\{k\}\.
While the definition of doubling dimension implies that everyRR\-ball has a “dense”rr\-ball core, our definition is more relaxed and allows the “dense”rr\-ball to be located anywhere within theRR\-ball instead of necessarily at the center\. This allows our definition to be a measure of sparsity as opposed to doubling dimension which is intuitively a measure of uniformity\. To see this, imagine a very sparse measure such that∃ν,r,R𝒫⁡\(Bρ​\(ν,r\)\)=0\\exists\\nu,r,R\\quad\\mathcal\{P\}\(B\_\{\\rho\}\(\\nu,r\)\)=0but𝒫⁡\(Bρ​\(ν,R\)\)≠0\\mathcal\{P\}\(B\_\{\\rho\}\(\\nu,R\)\)\\neq 0\. While the doubling dimension of such a space would be∞\\infty, the sparse dimension can still be finite\.

On the other hand however, our definition is also more restrictive as we control the growth in every set𝔸\\mathbb\{A\}whereas doubling dimension only controls the rate for perfect balls\. As we note later in Section[5](https://arxiv.org/html/2609.20883#S5), this restriction allows us to prove upper bounds that match theΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)lower bounds of Section[4](https://arxiv.org/html/2609.20883#S4)up to logarithmic terms\.

We denote the set of allkk\-sparse priors on a space𝔻\\mathbb\{D\}with distance \(pseudo\-\)metricρ\\rhoas𝔓⁡\(k,ρ,𝔻\)\\mathfrak\{P\}\(k,\\rho,\\mathbb\{D\}\), or as a shorthand𝔓\\mathfrak\{P\}when clear from context\.

### 3\.1Example Computations of Sparse Dimension

We show some more motivating examples showing sparsity of some distributions\. Our first example is motivated by the intuition for the structure of sparse dimension as presented in the beginning of this Section\. This intuitive structure is observed in the universe with clustering of objects with lighter objects orbiting larger ones\.

###### Example 3\.5\(Sparse Dimension of the Universe\)\.

We imagine the space of all distributions of interest as sparse and clustered, similar to the distribution of dark matter haloes in the Universe\. We hence calculate the sparse dimension of the Universe as a model for the sparse dimension of distributions of interest\. The distribution of dark matter haloes is usually modelled using a two\-point correlation functionξ\(\.\)\\xi\(\.\), that models the excess probability of a halo at a distancerrfrom a given halo\. That is, in a space of dimensiondd, the probability of a halo at distance atmostrrfrom a halo will be given by:

𝒫ξ​\(B⁡\(r,ν\)\)∝∫r′=0r\(ξ⁡\(r′\)\+1\)​r′\(d−1\)​d​r′\.\\displaystyle\\mathcal\{P\}\_\{\\xi\}\(B\(r,\\nu\)\)\\propto\\int\_\{r^\{\\prime\}=0\}^\{r\}\(\\xi\(r^\{\\prime\}\)\+1\)r^\{\\prime\(d\-1\)\}\\mathrm\{d\}r^\{\\prime\}\.For the 3D universe, over a range of distances0\.1​h−1​M​p​c≤r≤10​h−1​M​p​c0\.1h^\{\-1\}Mpc\\leq r\\leq 10h^\{\-1\}Mpcand forr0=5​h−1​M​p​cr\_\{0\}=5h^\{\-1\}Mpc, common surverys approximate the two\-point correlation function using a power law given byξ⁡\(r\)∝\(r/r0\)−α\\xi\(r\)\\propto\(r/r\_\{0\}\)^\{\-\\alpha\}forα≈1\.8\\alpha\\approx 1\.8\([Zehavi et al\., 2005](https://arxiv.org/html/2609.20883#bib.bib27);[Davis and Peebles, 1983](https://arxiv.org/html/2609.20883#bib.bib17)\)\. In this discussion we allow0​h−1​M​p​c≤r≤10​h−1​M​p​c0h^\{\-1\}Mpc\\leq r\\leq 10h^\{\-1\}Mpcto permit us to calculate the probability of anrr\-ball for allrrin the range as is required by Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3)\. Since the distribution of haloes is isotropic, denote the total probability of anyrr\-ball to beV⁡\(r\)V\(r\)which is given asV⁡\(r\)=𝒫ξ​\(B⁡\(r,ν\)\)∝rd​\(1\+dd−α​\(r/r0\)−α\)V\(r\)=\\mathcal\{P\}\_\{\\xi\}\(B\(r,\\nu\)\)\\propto r^\{d\}\(1\+\\frac\{d\}\{d\-\\alpha\}\(r/r\_\{0\}\)^\{\-\\alpha\}\)\. To calculate the sparse dimension, consider a set𝔸\\mathbb\{A\}of diameterRR\. Since𝔸\\mathbb\{A\}lies within a ball of radiusR≤10​h−1​M​p​cR\\leq 10h^\{\-1\}Mpc,𝒫⁡\(𝔸\)≤V⁡\(R\)\\mathcal\{P\}\(\\mathbb\{A\}\)\\leq V\(R\)\. Further,𝔸\\mathbb\{A\}can be covered by at mostV⁡\(R\+r/2\)/V⁡\(r/2\)V\(R\+r/2\)/V\(r/2\)balls of radiusr/2r/2\(similar to Proposition[B\.2](https://arxiv.org/html/2609.20883#A2.Thmtheorem2)\)\. By a simple pigeonhole argument, the intersection of at least 1 of theser/2r/2\-balls with𝔸\\mathbb\{A\}has weight≥V⁡\(r/2\)V⁡\(R\+r/2\)​𝒫​\(𝔸\)\\geq\\frac\{V\(r/2\)\}\{V\(R\+r/2\)\}\\mathcal\{P\}\(\\mathbb\{A\}\)\. Thus, if we pick anrrsuch that forϵ\>0\\epsilon\>0,ϵ≤V⁡\(r/2\)V⁡\(R\+r/2\)\\epsilon\\leq\\frac\{V\(r/2\)\}\{V\(R\+r/2\)\}, then we can show the existence of a set𝔹\\mathbb\{B\}which satsifies𝒫⁡\(𝔹\)≥ϵ​𝒫​\(𝔸\)\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{A\}\)with diameterrr\. Note the following bound,

V⁡\(r/2\)V⁡\(R\+r/2\)\\displaystyle\\frac\{V\(r/2\)\}\{V\(R\+r/2\)\}=rd\(2​R\+r\)d​\(1\+\(dd−α\)​\(r2​r0\)−α1\+\(dd−α\)​\(2​R\+r2​r0\)−α\)\\displaystyle=\\frac\{r^\{d\}\}\{\(2R\+r\)^\{d\}\}\\left\(\\frac\{1\+\\left\(\\frac\{d\}\{d\-\\alpha\}\\right\)\\left\(\\frac\{r\}\{2r\_\{0\}\}\\right\)^\{\-\\alpha\}\}\{1\+\\left\(\\frac\{d\}\{d\-\\alpha\}\\right\)\\left\(\\frac\{2R\+r\}\{2r\_\{0\}\}\\right\)^\{\-\\alpha\}\}\\right\)=rd−α\(2​R\+r\)d−α​\(\(r2​r0\)α\+\(dd−α\)\(2​R\+r2​r0\)α\+\(dd−α\)\)≥r1\.2\(3​R\)1\.2​\(2\.531\.8\+2\.5\)≥0\.068​r1\.2R1\.2\.\\displaystyle=\\frac\{r^\{d\-\\alpha\}\}\{\(2R\+r\)^\{d\-\\alpha\}\}\\left\(\\frac\{\\left\(\\frac\{r\}\{2r\_\{0\}\}\\right\)^\{\\alpha\}\+\\left\(\\frac\{d\}\{d\-\\alpha\}\\right\)\}\{\\left\(\\frac\{2R\+r\}\{2r\_\{0\}\}\\right\)^\{\\alpha\}\+\\left\(\\frac\{d\}\{d\-\\alpha\}\\right\)\}\\right\)\\geq\\frac\{r^\{1\.2\}\}\{\(3R\)^\{1\.2\}\}\\left\(\\frac\{2\.5\}\{3^\{1\.8\}\+2\.5\}\\right\)\\geq 0\.068\\frac\{r^\{1\.2\}\}\{R^\{1\.2\}\}\.Where we substituted=3,α=1\.8d=3,\\alpha=1\.8so thatd/\(d−α\)=2\.5d/\(d\-\\alpha\)=2\.5, lower boundr/\(2​r0\)≥0r/\(2r\_\{0\}\)\\geq 0and upper bound\(2​R\+r\)≤3​R\(2R\+r\)\\leq 3Rand\(2​R\+r\)/\(2​r0\)≤\(3​R/2​r0\)≤3\(2R\+r\)/\(2r\_\{0\}\)\\leq\(3R/2r\_\{0\}\)\\leq 3\. Thus forr=\(ϵ/0\.068\)1/1\.2​Rr=\(\\epsilon/0\.068\)^\{1/1\.2\}R, we show a set𝔹\\mathbb\{B\}with diameterrrand probability≥ϵ​𝒫​\(𝔸\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{A\}\)for anyϵ\>0\\epsilon\>0\. Thus the Universe follows a sparse prior of sparse dimension1\.21\.2in the ambient range of distances\.

We now show the sparse dimension of the Cantor distribution which can be used to construct distributions with non\-integer sparsity\.

###### Example 3\.6\(Sparse Dimension of the Cantor Distribution\)\.

To define the Cantor distribution, we need to define the Cantor set\. Leta∈\(0,1/2\)a\\in\(0,1/2\)be some constant,C0a=\[0,1\]C\_\{0\}^\{a\}=\[0,1\], and define setsCtaC\_\{t\}^\{a\}recursively as:Ct\+1a=⋃\[i1,i2\]∈Cta\(\[i1,\(i2−i1\)∗a\+i1\]∪\[i2−\(i2−i1\)∗a,i2\]\)C\_\{t\+1\}^\{a\}=\\bigcup\_\{\[i\_\{1\},i\_\{2\}\]\\in C\_\{t\}^\{a\}\}\(\[i\_\{1\},\(i\_\{2\}\-i\_\{1\}\)\*a\+i\_\{1\}\]\\cup\[i\_\{2\}\-\(i\_\{2\}\-i\_\{1\}\)\*a,i\_\{2\}\]\)\. Fora=1/3a=1/3, which is the common choice,C1a=\[0,1/3\]∪\[2/3,1\]C\_\{1\}^\{a\}=\[0,1/3\]\\cup\[2/3,1\],C2a=\[0,1/9\]∪\[2/9,1/3\]∪\[2/3,7/9\]∪\[8/9,1\]C\_\{2\}^\{a\}=\[0,1/9\]\\cup\[2/9,1/3\]\\cup\[2/3,7/9\]\\cup\[8/9,1\], and so on\. The Cantor set is the intersection of these sets such thatCa=∩t=0∞CtaC^\{a\}=\\cap\_\{t=0\}^\{\\infty\}C\_\{t\}^\{a\}\. The Cantor distribution, which we denoteπCa\\pi\_\{C^\{a\}\}is defined such that it assigns a total probability of2−t2^\{\-t\}to each of the2t2^\{t\}intervals ofCtaC\_\{t\}^\{a\}\. We claim that this distribution is\(−loga⁡2\)\(\-\\log\_\{a\}2\)\-sparse\.

To show this, consider a set𝔸\\mathbb\{A\}with diameterdiam⁡\(𝔸\)=R≤1\\mathrm\{diam\}\(\\mathbb\{A\}\)=R\\leq 1\. Consider the interval\[−R/2\+x,x\+R/2\]⊇𝔸\[\-R/2\+x,x\+R/2\]\\supseteq\\mathbb\{A\}for somex∈\[0,1\]x\\in\[0,1\]\. Lett1=⌊loga⁡R⌋t\_\{1\}=\\lfloor\\log\_\{a\}R\\rfloor, where⌊α⌋\\lfloor\\alpha\\rflooris the greatest integer≤α\\leq\\alpha\. Then, each interval ofCt1aC\_\{t\_\{1\}\}^\{a\}has length at leastRRand\[−R/2\+x,x\+R/2\]\[\-R/2\+x,x\+R/2\]intersects with at most22continuous intervals ofCt1aC\_\{t\_\{1\}\}^\{a\}\. Similarly, lett2=⌈loga⁡r⌉t\_\{2\}=\\lceil\\log\_\{a\}r\\rceilfor anyr<Rr<R, where⌈α⌉\\lceil\\alpha\\rceilis the least integer≥α\\geq\\alpha, such that each interval ofCt2aC\_\{t\_\{2\}\}^\{a\}has size at mostrr\. Thus, each interval ofCt2aC\_\{t\_\{2\}\}^\{a\}can be covered by an interval of diameterrr, and each interval ofCt1aC\_\{t\_\{1\}\}^\{a\}contains2t2−t12^\{t\_\{2\}\-t\_\{1\}\}intervals ofCt2aC\_\{t\_\{2\}\}^\{a\}\. Thus,2⋅2t2−t1≤23\+loga⁡\(r/R\)2\\cdot 2^\{t\_\{2\}\-t\_\{1\}\}\\leq 2^\{3\+\\log\_\{a\}\(r/R\)\}intervals of lengthrrare enough to cover an interval of lengthRR, and hence𝔸\\mathbb\{A\}\. By a pigeonhole argument, the intersection of at least one of these intervals with𝔸\\mathbb\{A\}must have probability≥2−3−loga⁡\(r/R\)​𝒫​\(𝔸\)\\geq 2^\{\-3\-\\log\_\{a\}\(r/R\)\}\\mathcal\{P\}\(\\mathbb\{A\}\)\. Now by Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3), we want to findc,kc,ksuch that for anyϵ∈\(0,1\]\\epsilon\\in\(0,1\]there is a subset𝔹\\mathbb\{B\}of𝔸\\mathbb\{A\}such that𝒫⁡\(𝔹\)≥ϵ​𝒫​\(𝔸\)\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq\\epsilon\\mathcal\{P\}\(\\mathbb\{A\}\)anddiam⁡\(𝔹\)≤c​ϵ1/k​diam​\(𝔸\)\\mathrm\{diam\}\(\\mathbb\{B\}\)\\leq c\\epsilon^\{1/k\}\\mathrm\{diam\}\(\\mathbb\{A\}\)\. We select the subset𝔹\\mathbb\{B\}as the highest density subset above so that𝒫⁡\(𝔹\)≥2−3−loga⁡\(r/R\)​𝒫​\(𝔸\)\\mathcal\{P\}\(\\mathbb\{B\}\)\\geq 2^\{\-3\-\\log\_\{a\}\(r/R\)\}\\mathcal\{P\}\(\\mathbb\{A\}\)anddiam⁡\(𝔹\)=r\\mathrm\{diam\}\(\\mathbb\{B\}\)=r\. Now,ϵ=2−3−loga⁡\(r/R\)⟹r/R=\(8​ϵ\)−log2⁡a\\epsilon=2^\{\-3\-\\log\_\{a\}\(r/R\)\}\\implies r/R=\(8\\epsilon\)^\{\-\\log\_\{2\}a\}\. Thus, the Cantor distribution isk=\(−loga⁡2\)k=\(\-\\log\_\{a\}2\)\-sparse with constantc=a−3c=a^\{\-3\}\.

## 4Lower Bounds using Sparse Dimension

The main technical results of this Section are presented in Theorems[4\.2](https://arxiv.org/html/2609.20883#S4.Thmtheorem2)and[4\.3](https://arxiv.org/html/2609.20883#S4.Thmtheorem3)that prove dimension\-independent lower bounds ofΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)on the Bayes’ risk of learning a distribution in add\-dimensional space under akk\-sparse prior\. It is, however, not obvious that sampling is reducible to learning a distribution\. That is, it is not obvious that the Bayes’ risk of sampling as defined in Equation[2](https://arxiv.org/html/2609.20883#S2.E2)should suffer the same lower bounds that learning a distribution does\. In the following Theorem, we show that a sampling algorithm can be used to devise a procedure to get low loss on any IPM, which allows the reduction of sampling to distribution learning\. While similar results have been shown in[Singh et al\. \(2018\)](https://arxiv.org/html/2609.20883#bib.bib28)for the minimax risk, we prove the result for the Bayes’ risk\.

###### Theorem 4\.1\.

For a target distributionπ\\pi, consider a sampling algorithm𝒜^n\\hat\{\\mathcal\{A\}\}\_\{n\}that samples from the distributiondist⁡\(𝒜^n\)\\mathrm\{dist\}\(\\hat\{\\mathcal\{A\}\}\_\{n\}\)\. The smallest Bayes’ risk of any sampling algorithm measured under any distance \(pseudo\-\)metricρ\\rhois lower bounded by the smallest Bayes’ risk of any estimator ofπ\\pi\. Formally,

inf𝒜^nsup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρ⁡\(dist⁡\(𝒜^n\),π\)\]\]≥infπ^sup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρ⁡\(π^​\(𝐗\),π\)\]\]\.\\displaystyle\\inf\_\{\\hat\{\\mathcal\{A\}\}\_\{n\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\(\\mathrm\{dist\}\(\\hat\{\\mathcal\{A\}\}\_\{n\}\),\\pi\)\]\]\\geq\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\]\.

###### Proof\.

Consider the distribution estimatorπ^n=dist⁡\(𝒜^n\)\\hat\{\\pi\}\_\{n\}=\\mathrm\{dist\}\(\\hat\{\\mathcal\{A\}\}\_\{n\}\)that achieves the same Bayes’ risk bound on distribution learning that𝒜^n\\hat\{\\mathcal\{A\}\}\_\{n\}achieves on sampling\. The inequality follows since there can be a more sample efficient distribution estimator that doesn’t require learning to sample\. ∎

The above theorem allows us to study lower bounds on sampling algorithms using standard information theory\. Below we state a dimension\-independentΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)lower bound for the total variation distance, which is proved in detail in Appendix[A\.2](https://arxiv.org/html/2609.20883#A1.SS2)\. We use a family of discrete distributions to demonstrate our hard instance, primarily because TV computation is easy for such a family\. Consider elementsz1,…,zk⊆𝒳z\_\{1\},\\ldots,z\_\{k\}\\subseteq\\mathcal\{X\}for some integerkkto be unequal elements of𝒳\\mathcal\{X\}, and a discrete distribution over these elements given by the probability vectorθ=\(θ1,…,θk\)\\theta=\(\\theta\_\{1\},\\ldots,\\theta\_\{k\}\)\. Then, the TV distance between any two such discrete distributions is simplified as follows:

ρT​V​\(πθ,πθ′\)\\displaystyle\\rho\_\{TV\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)=12​∑\|πθ​\(zi\)−πθ′​\(zi\)\|=12​∑i=1k\|θi−θi′\|,\\displaystyle=\\frac\{1\}\{2\}\\sum\|\\pi\_\{\\theta\}\(z\_\{i\}\)\-\\pi\_\{\\theta^\{\\prime\}\}\(z\_\{i\}\)\|=\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{k\}\|\\theta\_\{i\}\-\\theta\_\{i\}^\{\\prime\}\|,\(3\)which is proportional to thel​1l1norm betweenθ,θ′\\theta,\\theta^\{\\prime\}\. Any distribution over the family of discrete distributions is a distribution over thekk\-simplex ofθ\\theta, which is akk\-dimensional space equipped with thel​1l1norm\. By Corollary[3\.1\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem1.Thmcorollary2), it follows that a discrete distribution overkkelements is at mostkk\-sparse\. Consequently, in the following result, we assume\|𝒳\|≥k\|\\mathcal\{X\}\|\\geq k\.

###### Theorem 4\.2\.

Let𝔻\\mathbb\{D\}be the set of all distributions over𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}, and let𝔓\\mathfrak\{P\}be shorthand for𝔓⁡\(k,ρT​V,𝔻\)\\mathfrak\{P\}\(k,\\rho\_\{TV\},\\mathbb\{D\}\), be the set of allkk\-sparse priors over𝔻\\mathbb\{D\}using the total variation distance\. If\|𝒳\|≥k\|\\mathcal\{X\}\|\\geq k, the Bayes’ risk for any distribution estimatorπ^n\\hat\{\\pi\}\_\{n\}is lower bounded independent ofddas below:

infπ^sup𝒫∈𝔓RB​a​y​e​s​\(π^,𝒫\)=infπ^sup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρT​V​\(π^​\(𝐗\),π\)\]\]=Ω⁡\(k/n\)\.\\displaystyle\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}R\_\{Bayes\}\(\\hat\{\\pi\};\\mathcal\{P\}\)=\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{TV\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]=\\Omega\(\\sqrt\{k/n\}\)\.

###### Proof\.

In order to show Bayes risk lower bounds over allkk\-sparse priors, we construct akk\-sparse prior that achieves the desired lower bound\. As stated above, our construction is simply a family of discrete distributions over≥k\\geq kelements of𝒳\\mathcal\{X\}\. Such a distribution has at mostkkfree parameters, and hence any prior iskk\-sparse by Equation[3](https://arxiv.org/html/2609.20883#S4.E3)and Corollary[3\.1\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem1.Thmcorollary2)\. Constructing a hard prior over the set of discrete distributions matches popular constructions for showing parametric lower bounds for the TV distance\. We defer the reader to Theorem[A\.5](https://arxiv.org/html/2609.20883#A1.Thmtheorem5)in Appendix[A\.2](https://arxiv.org/html/2609.20883#A1.SS2)for a detailed proof\. ∎

We show a similar result as above for the Wasserstein\-1 \(W1\) distance\. We will use a similar construction of a family of discrete distributions, and will hence again require that\|𝒳\|≥k\|\\mathcal\{X\}\|\\geq k\.

###### Theorem 4\.3\.

Let𝔻\\mathbb\{D\}be the set of all distributions over add\-dimensional space, and let𝔓\\mathfrak\{P\}be shorthand for𝔓⁡\(k,ρW​1,𝔻\)\\mathfrak\{P\}\(k,\\rho\_\{W1\},\\mathbb\{D\}\), the set of allkk\-sparse priors over𝔻\\mathbb\{D\}using the Wasserstein\-1 distance\. For some constantrm​i​nr\_\{min\}independent ofkkanddd, assume∃z1,…,z⌊k⌋∈𝒳\\exists z\_\{1\},\\ldots,z\_\{\\lfloor k\\rfloor\}\\in\\mathcal\{X\}such thatmini≠j⁡‖zi−zj‖≥rm​i​n\\min\_\{i\\neq j\}\\\|z\_\{i\}\-z\_\{j\}\\\|\\geq r\_\{min\}\. Here⌊k⌋\\lfloor k\\rflooris the greatest integer≤k\\leq k\. Then, the Bayes risk for any distribution estimatorπ^n\\hat\{\\pi\}\_\{n\}is lower bounded independent ofddas below:

infπ^sup𝒫∈𝔓RB​a​y​e​s​\(π^,𝒫\)=infπ^sup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρW​1​\(π^​\(𝐗\),π\)\]\]=Ω⁡\(k/n\)\.\\displaystyle\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}R\_\{Bayes\}\(\\hat\{\\pi\};\\mathcal\{P\}\)=\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{W1\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]=\\Omega\(\\sqrt\{k/n\}\)\.

###### Proof\.

We will use the same construction of a uniform prior over a family of discrete distributions as the one for Theorem[4\.2](https://arxiv.org/html/2609.20883#S4.Thmtheorem2)\. We first show that the Wasserstein distance is bounded on both sides by the TV distance, which allows us to concludekk\-sparsity of the chosen prior\. We will then argue that since TV distance lower bounds W1 distance by a constant factor, the hard instance for TV estimation is also a hard instance for W1 estimation\.

Notably, for an appropriately chosenk′≤⌊k⌋k^\{\\prime\}\\leq\\lfloor k\\rfloor, letz1,…,zk′z\_\{1\},\\ldots,z\_\{k^\{\\prime\}\}be the support of the family of discrete distributions that are elements of𝒳\\mathcal\{X\}guaranteed by the Theorem statement\. Then,mini≠j⁡‖zi−zj‖≥rm​i​n\\min\_\{i\\neq j\}\\\|z\_\{i\}\-z\_\{j\}\\\|\\geq r\_\{min\}and letmaxi≠j⁡‖zi−zj‖=rm​a​x\\max\_\{i\\neq j\}\\\|z\_\{i\}\-z\_\{j\}\\\|=r\_\{max\}\. ForΠ⁡\(θ,θ′\)\\Pi\(\\theta,\\theta^\{\\prime\}\)the set of all couplings overπθ\\pi\_\{\\theta\}andπθ′\\pi\_\{\\theta^\{\\prime\}\}, the W1 distance is written as:

ρW​1​\(πθ,πθ′\)=infπ∈Π⁡\(θ,θ′\)𝔼X,Y∼π​\[‖X−Y‖\]=infπ∈Π⁡\(θ,θ′\)𝔼X,Y∼π​\[‖X−Y‖⋅𝕀⁡\(X≠Y\)\]\.\\displaystyle\\rho\_\{W1\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)=\\inf\_\{\\pi\\in\\Pi\(\\theta,\\theta^\{\\prime\}\)\}\\mathbb\{E\}\_\{X,Y\\sim\\pi\}\[\\\|X\-Y\\\|\]=\\inf\_\{\\pi\\in\\Pi\(\\theta,\\theta^\{\\prime\}\)\}\\mathbb\{E\}\_\{X,Y\\sim\\pi\}\[\\\|X\-Y\\\|\\cdot\\mathbb\{I\}\(X\\neq Y\)\]\.Note that the TV distance is simply,ρT​V​\(πθ,πθ′\)=infπ∈Π⁡\(θ,θ′\)P​rX,Y∼π​\(X≠Y\)\\rho\_\{TV\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)=\\inf\_\{\\pi\\in\\Pi\(\\theta,\\theta^\{\\prime\}\)\}Pr\_\{X,Y\\sim\\pi\}\(X\\neq Y\)\. Thus, we bound the W1 distance as follows:

rm​i​n​infπ∈Π⁡\(θ,θ′\)P​rX,Y∼π​\(X≠Y\)≤infπ∈Π⁡\(θ,θ′\)𝔼X,Y∼π\\displaystyle r\_\{min\}\\inf\_\{\\pi\\in\\Pi\(\\theta,\\theta^\{\\prime\}\)\}Pr\_\{X,Y\\sim\\pi\}\(X\\neq Y\)\\leq\\inf\_\{\\pi\\in\\Pi\(\\theta,\\theta^\{\\prime\}\)\}\\mathbb\{E\}\_\{X,Y\\sim\\pi\}\[‖X−Y‖⋅𝕀⁡\(X≠Y\)\]\\displaystyle\[\\\|X\-Y\\\|\\cdot\\mathbb\{I\}\(X\\neq Y\)\]≤rm​a​x​infπ∈Π⁡\(θ,θ′\)P​rX,Y∼π​\(X≠Y\),\\displaystyle\\leq r\_\{max\}\\inf\_\{\\pi\\in\\Pi\(\\theta,\\theta^\{\\prime\}\)\}Pr\_\{X,Y\\sim\\pi\}\(X\\neq Y\),which implies,

rm​i​n​ρT​V​\(πθ,πθ′\)≤ρW​1​\(πθ,πθ′\)≤rm​a​x​ρT​V​\(πθ,πθ′\)\.\\displaystyle r\_\{min\}\\rho\_\{TV\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)\\leq\\rho\_\{W1\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)\\leq r\_\{max\}\\rho\_\{TV\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)\.
Since the TV distance is proportional to thel​1l1distance by Equation[3](https://arxiv.org/html/2609.20883#S4.E3), the above equation implies⌊k⌋\\lfloor k\\rfloor\-Ahlfors regularity of our space by Lemma[B\.4](https://arxiv.org/html/2609.20883#A2.Thmtheorem4)\(considering the Lebesgue measure on the⌊k⌋\\lfloor k\\rfloor\-simplex, which is a⌊k⌋\\lfloor k\\rfloor\-dimensional space\), implying any prior over the space is⌊k⌋\\lfloor k\\rfloor\-sparse by Corollary[3\.1\.1](https://arxiv.org/html/2609.20883#S3.Thmtheorem1.Thmcorollary1), and hencekk\-sparse\.

Now that we have established that any prior over the set of discrete distributions as defined previously iskk\-sparse, we can select the same prior as in the construction of Theorem[4\.2](https://arxiv.org/html/2609.20883#S4.Thmtheorem2)\. Thus,

infπ^𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρW​1​\(π^​\(𝐗\),π\)\]\]\\displaystyle\\inf\_\{\\hat\{\\pi\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{W1\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]≥rm​i​n​infπ^𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρT​V​\(π^​\(𝐗\),π\)\]\]=Ω⁡\(k/n\)\.\\displaystyle\\geq r\_\{min\}\\inf\_\{\\hat\{\\pi\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{TV\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]=\\Omega\(\\sqrt\{k/n\}\)\.∎

## 5Upper Bounds using Sparse Dimension

The main technical results of this Section are presented in Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2), that shows the existence of an estimator that matches our lower bounds from Section[4](https://arxiv.org/html/2609.20883#S4)up to logarithmic terms, and Corollary[5\.2\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem2.Thmcorollary1)that shows a relaxation of the constraints of Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)\. We first show an analogous result to Theorem[4\.1](https://arxiv.org/html/2609.20883#S4.Thmtheorem1)that shows that density estimation, a special case of learning a distribution, is reducible to learning to sample from a distribution\. This guarantees that the Bayes’ risk of learning to sample as defined in Equation[2](https://arxiv.org/html/2609.20883#S2.E2)follow the same upper bounds that learning a distribution does\. The following theorem shows that any algorithm that learns a density can be used to sample from the distribution by rejection sampling\. Similar results have been shown in[Singh et al\. \(2018\)](https://arxiv.org/html/2609.20883#bib.bib28)for the minimax risk, we prove the result for the Bayes’ risk using similar techniques\.

###### Theorem 5\.1\.

For a target distributionπ\\pi, consider density estimators given byπ^n\\hat\{\\pi\}\_\{n\}\. The smallest Bayes’ risk of any density estimator is lower bounded by the smallest Bayes’ risk of any sampling algorithm measured under any distance \(pseudo\-\)metricρ\\rho\. Formally,

infπ^sup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρ⁡\(π^​\(𝐗\),π\)\]\]≥inf𝒜^nsup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρ⁡\(dist⁡\(𝒜^n\),π\)\]\]\.\\displaystyle\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\]\\geq\\inf\_\{\\hat\{\\mathcal\{A\}\}\_\{n\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\(\\mathrm\{dist\}\(\\hat\{\\mathcal\{A\}\}\_\{n\}\),\\pi\)\]\]\.

###### Proof\.

We define the sampling algorithm𝒜⁡\(π^n\)\\mathcal\{A\}\(\\hat\{\\pi\}\_\{n\}\)for everyπ^n\\hat\{\\pi\}\_\{n\}, that performs rejection sampling on the estimated density function\. While rejection sampling may be computationally inefficient for the distribution, we restrict our attention to sample complexity, such that𝒜⁡\(π^n\)\\mathcal\{A\}\(\\hat\{\\pi\}\_\{n\}\)samples fromπ^n\\hat\{\\pi\}\_\{n\}\. The inequality follows since there can be a more sample efficient sampling algorithm that doesn’t first require density estimation\. ∎

Our next theorem below shows the existence of an estimator that can learn a distribution with a Bayesian risk under the TV distance ofO⁡\(k​log⁡n/n\)O\(\\sqrt\{k\\log n\}/\\sqrt\{n\}\)for akk\-sparse prior, matching our lower bounds with a poly\-log term\. Since density estimation is a special case of this result, Theorem[5\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem1)allows us to conclude the existence of a sampling algorithm that achieves the same upper bound in TV distance\. Similar to our lower bounds, our upper bounds are asymptotic in bothnnandkk\. This does not make our bounds vacuous for smallkkhowever, since by definition akk\-sparse prior is alwaysk′k^\{\\prime\}\-sparse fork′\>kk^\{\\prime\}\>k\. Our upper bounds further assume that the likelihood ratio between any two distributions is bounded by a constantbl​rb\_\{lr\}\. Note that the asymptotic bound does not depend on the value ofbl​rb\_\{lr\}, but only on its finiteness\. We thus make two separate asymptotic statements for clarity\.

1. 1\.Under a bounded likelihood ratio for all distributions in the support of akk\-sparse prior, our upper and lower bounds match up to logarithmic terms when considering asymptotics innnandkk\.
2. 2\.Under a bounded likelihood ratio for all distributions in the support of akk\-sparse prior, our upper and lower bounds match up to logarithmic terms when considering asymptotics innnwhile keepingkkconstant for anykk\. Here the constants hidden by the asymptotics may not depend similarly onkkfor the upper and lower bounds\.

We prove the result in Appendix[B\.3](https://arxiv.org/html/2609.20883#A2.SS3),and provide a proof sketch below\. We show a relaxation of our bounded likelihood assumption in Corollary[5\.2\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem2.Thmcorollary1), proceeded by a simple example that satisfies the conditions of the Corollary\.

###### Theorem 5\.2\.

Consider akk\-sparse prior in the total variation distanceρT​V\\rho\_\{TV\}over a set of distributions𝔻\\mathbb\{D\}such that the likelihood ratio between any two distributions is bounded\. That is,‖π1/π2‖∞≤bl​r​∀π1,π2∈𝔻\\\|\\pi\_\{1\}/\\pi\_\{2\}\\\|\_\{\\infty\}\\leq b\_\{lr\}\\;\\forall\\pi\_\{1\},\\pi\_\{2\}\\in\\mathbb\{D\}, for some constantbl​r\>0b\_\{lr\}\>0\. Then, there exists an estimator such that the Bayes’ risk is upper bounded in the total variation distance forn=ω⁡\(bl​r\)n=\\omega\(b\_\{lr\}\)as follows:

𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]=O⁡\(k​log⁡nn\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\\right\)\.

###### Proof Sketch\.

LetE⁡\(n,ϵn,b1\)E\(n,\\epsilon\_\{n\},b\_\{1\}\)be the event𝒫\(\{π:ρT​V\(π,π0\)\>ϵn\|X1,…,Xn\}\)\>exp\(−b1nϵn2\)\\mathcal\{P\}\(\\\{\\pi:\\rho\_\{TV\}\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\>\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)for someϵn\\epsilon\_\{n\}chosen such thatn​ϵn2→∞n\\epsilon\_\{n\}^\{2\}\\rightarrow\\inftyasn→∞n\\rightarrow\\inftyand constantb1\>0b\_\{1\}\>0\. That is,E\(\.\)E\(\.\)represents the event that the posterior mass outside of anϵn\\epsilon\_\{n\}ball around the true distribution sampled from𝒫\\mathcal\{P\}is greater thanexp⁡\(−b1​n​ϵn2\)\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\. We will first argue that wheneverE\(\.\)E\(\.\)fails, there is a significant posterior probability around the true distribution, and hence we can identify a distribution close to the true distribution easily\. We will then argue that the probability ofE\(\.\)E\(\.\)goes to00fast asnnincreases\. Formally, we first decompose the required bound as follows, whereE\(\.\)cE\(\.\)^\{c\}is the complement of the eventE\(\.\)E\(\.\):

𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]≤P​r​\(E⁡\(n,ϵn,b1\)\)⋅𝔼⁡\[ρT​V​\(π0,π^n\)\|E⁡\(n,ϵn,b1\)\]\\displaystyle\\leq Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\)\\cdot\\mathbb\{E\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)\]\+Pr\(E\(n,ϵn,b1\)c\)⋅𝔼\[ρT​V\(π0,π^n\)\|E\(n,ϵn,b1\)c\]\.\\displaystyle\\quad\+Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\)\\cdot\\mathbb\{E\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\]\.\(4\)
We defineπ^n=arg​maxπ⁡𝒫​\(\{π′:ρ⁡\(π′,π\)≤ϵn\}\|X1,…,Xn\)\\hat\{\\pi\}\_\{n\}=\\argmax\_\{\\pi\}\\mathcal\{P\}\(\\\{\\pi^\{\\prime\}:\\rho\(\\pi^\{\\prime\},\\pi\)\\leq\\epsilon\_\{n\}\\\}\|X\_\{1\},\\ldots,X\_\{n\}\)as the center of theϵn\\epsilon\_\{n\}ball with highest posterior probability\. UnderE​\(n,ϵn,b1\)cE\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}, there is a significant posterior mass concentrated in anϵn\\epsilon\_\{n\}\-ball around the true distributionπ0\\pi\_\{0\}, as well as the estimated distributionπ^n\\hat\{\\pi\}\_\{n\}\. If these two distributions are more than2​ϵn2\\epsilon\_\{n\}apart, and since1−exp⁡\(−b1​n​ϵn2\)1\-\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)approaches11asn→∞n\\rightarrow\\infty, there is an asymptotically increasing total probability in the disjoint posterior balls around the two distributions which is eventually\>1\>1, which is not possible\. Thus, underE​\(n,ϵn,b1\)cE\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\},ρT​V​\(π0,π^n\)≤2​ϵn\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\\leq 2\\epsilon\_\{n\}asymptotically\. The second term of Equation[4](https://arxiv.org/html/2609.20883#S5.E4)is thus simplified as follows:

P​r​\(E​\(n,ϵn,b1\)c\)⋅𝔼⁡\[ρ⁡\(π0,π^n\)\|E​\(n,ϵn,b1\)c\]\\displaystyle Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\)\\cdot\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\]≤𝔼⁡\[ρ⁡\(π0,π^n\)\|E​\(n,ϵn,b1\)c\]=O⁡\(ϵn\)\.\\displaystyle\\leq\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\]=O\(\\epsilon\_\{n\}\)\.
It remains to bound the first term of Equation[4](https://arxiv.org/html/2609.20883#S5.E4)\. To do so, we first note that TV distance is bounded by 1 so thatρT​V\(\.,\.\)≤1\\rho\_\{TV\}\(\.,\.\)\\leq 1\. Further note from Markov’s inequality that for any non\-negative random variableVVand thresholdt\>0t\>0,P​r​\(V\>t\)≤𝔼⁡\[V\]/tPr\(V\>t\)\\leq\\mathbb\{E\}\[V\]/t\. Thus,

Pr\(E\(n,ϵn,b1\)\)⋅𝔼\[ρ\(π0,π^n\)\|E\(n,\\displaystyle Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\)\\cdot\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,ϵn,b1\)\]≤Prπ0∼𝒫,X1,…,Xn∼π0\(E\(n,ϵn,b1\)\)\\displaystyle\\epsilon\_\{n\},b\_\{1\}\)\]\\leq Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\},X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\)=𝔼π0∼𝒫​\[P​rX1,…,Xn∼π0​\(E⁡\(n,ϵn,b1\)\|π0\)\]\\displaystyle=\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\|\\pi\_\{0\}\)\]≤𝔼π0∼𝒫\[𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]exp⁡\(−b1​n​ϵn2\)\]\.\\displaystyle\\leq\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\\left\[\\frac\{\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\}\{\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\}\\right\]\.
We use nonparametric Bayesian convergence rates developed in[Ghosal et al\. \(2000\)](https://arxiv.org/html/2609.20883#bib.bib30)to argue that for someb2,b3\>b1b\_\{2\},b\_\{3\}\>b\_\{1\},Prπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]\>5exp\(−b2nϵn2\)\)≤exp\(−b3nϵn2\)Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\>5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\leq\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)such that for mostπ0\\pi\_\{0\}, the expected posterior probability in anϵn\\epsilon\_\{n\}ball aroundπ0\\pi\_\{0\}is significant\. Since the posterior probability of any region is at most 1, this allows us to decompose the above expression:

𝔼π0∼𝒫\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]exp⁡\(−b1​n​ϵn2\)\]\\displaystyle\\left\[\\frac\{\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\}\{\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\}\\right\]≤exp\(b1nϵn2\)\(Prπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]\>5exp\(−b2nϵn2\)\)⋅1\\displaystyle\\leq\\exp\(b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\(Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\>5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\cdot 1\+Prπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]≤5exp\(−b2nϵn2\)\)⋅5exp\(−b2nϵn2\)\)\\displaystyle\\;\+Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\\leq 5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\cdot 5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)≤exp⁡\(b1​n​ϵn2\)​\(exp⁡\(−b3​n​ϵn2\)\+5​exp⁡\(−b2​n​ϵn2\)\)\.\\displaystyle\\leq\\exp\(b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\(\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)\+5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\.
The above expression isO⁡\(ϵn\)O\(\\epsilon\_\{n\}\)ifexp⁡\(−b′​n​ϵn2\)=O⁡\(ϵn\)\\exp\(\-b^\{\\prime\}n\\epsilon\_\{n\}^\{2\}\)=O\(\\epsilon\_\{n\}\)for anyb′\>0b^\{\\prime\}\>0, which is satisfied for our choice ofϵn=k​log⁡n/n\\epsilon\_\{n\}=\\sqrt\{k\\log n/n\}\. We defer the reader to Appendix[B\.3](https://arxiv.org/html/2609.20883#A2.SS3)for a detailed proof\. ∎

We now present a Corollary of the above result that allows a relaxation of the bounded likelihood assumption\. In particular, since increasingbl​rb\_\{lr\}only affects the start of the asymptotic regime and not the bound itself, we allowbl​rb\_\{lr\}to increase sub\-linearly in the number of samples\. As long as we can ensure that such a bound on the likelihood ratio on the observed samples holds with high enough probability, we observe a similar relationship with much relaxed assumptions\.

###### Corollary 5\.2\.1\.

Consider akk\-sparse prior in the total variation distanceρT​V\\rho\_\{TV\}over a set of distributions𝔻\\mathbb\{D\}supported over𝒳\\mathcal\{X\}\. Assume that there exists a set𝒳n\\mathcal\{X\}\_\{n\}such that the likelihood ratio between any two distributions is bounded inside𝒳n\\mathcal\{X\}\_\{n\}\. That is,‖π1​\(x\)/π2​\(x\)‖∞≤bl​r​\(n\)​∀π1,π2∈𝔻,x∈𝒳n\\\|\\pi\_\{1\}\(x\)/\\pi\_\{2\}\(x\)\\\|\_\{\\infty\}\\leq b\_\{lr\}\(n\)\\;\\forall\\pi\_\{1\},\\pi\_\{2\}\\in\\mathbb\{D\},x\\in\\mathcal\{X\}\_\{n\}, for some functionbl​r\(\.\):ℕ→ℝ\+b\_\{lr\}\(\.\):\\mathbb\{N\}\\rightarrow\\mathbb\{R\}^\{\+\}andbl​r​\(n\)=o​\(n\)b\_\{lr\}\(n\)=o\(n\)\. Further assume that for anyπ∈𝔻\\pi\\in\\mathbb\{D\},P​rX∼π​\(X∉𝒳n\)=O⁡\(k​log⁡nn3/2\)Pr\_\{X\\sim\\pi\}\(X\\notin\\mathcal\{X\}\_\{n\}\)=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{n^\{3/2\}\}\\right\)\. Then, there exists an estimator such that the Bayes’ risk is upper bounded in the total variation distance as follows:

𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]=O⁡\(k​log⁡nn\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\\right\)\.

###### Proof\.

Denote the event thatX1,…,Xn∈𝒳nX\_\{1\},\\ldots,X\_\{n\}\\in\\mathcal\{X\}\_\{n\}byEnE\_\{n\}\. ThenP​r​\(Enc\)≤n​P​r​\(Xi∉𝒳n\)=O⁡\(k​log⁡nn\)Pr\(E\_\{n\}^\{c\}\)\\leq nPr\(X\_\{i\}\\notin\\mathcal\{X\}\_\{n\}\)=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\\right\)\. Thus,

𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]=𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\|En\]​P​r​\(En\)\+𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\|Enc\]​P​r​\(Enc\)\]\\displaystyle=\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\_\{n\}\]Pr\(E\_\{n\}\)\+\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\_\{n\}^\{c\}\]Pr\(E\_\{n\}^\{c\}\)\]≤𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\|En\]\+P​r​\(Enc\)\]=O⁡\(k​log⁡nn\),\\displaystyle\\leq\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\_\{n\}\]\+Pr\(E\_\{n\}^\{c\}\)\]=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\\right\),by Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)\. Note that the asymptotic rate of Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)requiresn=ω⁡\(bl​r\)n=\\omega\(b\_\{lr\}\), so that the same asymptotic rate is achieved even whenbl​rb\_\{lr\}is not a constant as long asbl​r​\(n\)=o​\(n\)b\_\{lr\}\(n\)=o\(n\)\. ∎

###### Example 5\.3\.

We show that the Gaussian location family withkkunknown elements of the mean satisfies the conditions of Corollary[5\.2\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem2.Thmcorollary1)\. Consider the family𝔻k=\{𝒩\(\(θ1,…,θk,0,…,0\),Id\):θ∈ℝk,∥θ∥≤1\}\\mathbb\{D\}\_\{k\}=\\\{\\mathcal\{N\}\(\(\\theta^\{1\},\\ldots,\\theta^\{k\},0,\\ldots,0\),I\_\{d\}\):\\theta\\in\\mathbb\{R\}^\{k\},\\\|\\theta\\\|\\leq 1\\\}, where only the firstkkelements of the mean are unknown\. We will denote the vector\(θ1,…,θk,0,…,0\)\(\\theta^\{1\},\\ldots,\\theta^\{k\},0,\\ldots,0\)byθ′\\theta^\{\\prime\}for brevity here\. Similar to our discussion in Section[3](https://arxiv.org/html/2609.20883#S3)the W1 distance between elements of this family is given asρW​1​\(𝒩⁡\(θ1′,Id\),𝒩⁡\(θ2′,Id\)\)=‖θ1′−θ2′‖=‖θ1−θ2‖\\rho\_\{W1\}\(\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)\)=\\\|\\theta\_\{1\}^\{\\prime\}\-\\theta\_\{2\}^\{\\prime\}\\\|=\\\|\\theta\_\{1\}\-\\theta\_\{2\}\\\|, which allows us to conclude that any prior over the family iskk\-sparse in the W1 distance\. Now, note that the TV distance is given asρT​V​\(𝒩⁡\(θ1′,Id\),𝒩⁡\(θ2′,Id\)\)=2​Φ​\(‖θ1′−θ2′‖/2\)−1\\rho\_\{TV\}\(\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)\)=2\\Phi\(\\\|\\theta\_\{1\}^\{\\prime\}\-\\theta\_\{2\}^\{\\prime\}\\\|/2\)\-1, whereΦ\\Phiis the cdf of the standard normal Gaussian\. Note that the ratioρT​V​\(𝒩⁡\(θ1′,Id\),𝒩⁡\(θ2′,Id\)\)/ρW​1​\(𝒩⁡\(θ1′,Id\),𝒩⁡\(θ2′,Id\)\)=2​Φ​\(r/2\)−1r\\rho\_\{TV\}\(\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)\)/\\rho\_\{W1\}\(\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)\)=\\frac\{2\\Phi\(r/2\)\-1\}\{r\}forr=‖θ1′−θ2′‖r=\\\|\\theta\_\{1\}^\{\\prime\}\-\\theta\_\{2\}^\{\\prime\}\\\|is decreasing inrr\. Thus forr∈\[0,2\]r\\in\[0,2\]given by‖θ‖≤1\\\|\\theta\\\|\\leq 1, we get that:

ρT​V​\(𝒩⁡\(θ1′,Id\),𝒩⁡\(θ2′,Id\)\)/ρW​1​\(𝒩⁡\(θ1′,Id\),𝒩⁡\(θ2′,Id\)\)∈\[2​Φ​\(1\)−12,1\]\.\\displaystyle\\rho\_\{TV\}\(\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)\)/\\rho\_\{W1\}\(\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\),\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)\)\\in\\left\[\\frac\{2\\Phi\(1\)\-1\}\{2\},1\\right\]\.Thus, the Gaussian family equipped with the TV distance iskk\-Ahlfors regular as defined in Corollary[3\.1\.1](https://arxiv.org/html/2609.20883#S3.Thmtheorem1.Thmcorollary1)using the Lebesgue measure over the parameter space, which allows us to conclude that any prior over the set iskk\-sparse in the TV distance as well\.

It remains to show the existence of a support set𝒳n\\mathcal\{X\}\_\{n\}over which the likelihood ratios are bounded byo⁡\(n\)o\(n\)\. The ratio of pdfs of𝒩⁡\(θ1′,Id\)\\mathcal\{N\}\(\\theta\_\{1\}^\{\\prime\},I\_\{d\}\)and𝒩⁡\(θ2′,Id\)\\mathcal\{N\}\(\\theta\_\{2\}^\{\\prime\},I\_\{d\}\)at a pointx∈ℝdx\\in\\mathbb\{R\}^\{d\}is bounded by the following:

exp⁡\(\|‖x−θ1′‖2−‖x−θ2′‖2\|2\)\\displaystyle\\exp\\left\(\\frac\{\|\\\|x\-\\theta\_\{1\}^\{\\prime\}\\\|^\{2\}\-\\\|x\-\\theta\_\{2\}^\{\\prime\}\\\|^\{2\}\|\}\{2\}\\right\)=exp⁡\(\|‖x−θ1′‖−‖x−θ2′‖\|​\(‖x−θ1′‖\+‖x−θ2′‖\)2\)\\displaystyle=\\exp\\left\(\\frac\{\|\\\|x\-\\theta\_\{1\}^\{\\prime\}\\\|\-\\\|x\-\\theta\_\{2\}^\{\\prime\}\\\|\|\(\\\|x\-\\theta\_\{1\}^\{\\prime\}\\\|\+\\\|x\-\\theta\_\{2\}^\{\\prime\}\\\|\)\}\{2\}\\right\)≤exp⁡\(‖θ1′−θ2′‖​\(2​‖x‖\+‖θ1′‖\+‖θ2′‖\)2\)\\displaystyle\\leq\\exp\\left\(\\frac\{\\\|\\theta\_\{1\}^\{\\prime\}\-\\theta\_\{2\}^\{\\prime\}\\\|\(2\\\|x\\\|\+\\\|\\theta\_\{1\}^\{\\prime\}\\\|\+\\\|\\theta\_\{2\}^\{\\prime\}\\\|\)\}\{2\}\\right\)≤exp⁡\(2​‖x‖\+2\),\\displaystyle\\leq\\exp\(2\\\|x\\\|\+2\),since‖θ1′‖,‖θ2′‖≤1\\\|\\theta\_\{1\}^\{\\prime\}\\\|,\\\|\\theta\_\{2\}^\{\\prime\}\\\|\\leq 1\. To obtainbl​r=o⁡\(n\)b\_\{lr\}=o\(n\), it suffices to select‖x‖<1/2​log⁡n\\\|x\\\|<1/2\\log n\. Consider𝒳n=\{x∈ℝd:‖x‖<1/2​log⁡n\}\\mathcal\{X\}\_\{n\}=\\\{x\\in\\mathbb\{R\}^\{d\}:\\\|x\\\|<1/2\\log n\\\}\. We recall the following Gaussian concentration inequality for anLL\-Lipschitz functionffandt\>0t\>0:

PrZ∼𝒩⁡\(0,Id\)\(f\(Z\)≥𝔼\[f\]\+t\)≤exp\(−t2/\(2L2\)\)\.\\displaystyle Pr\_\{Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\)\}\(f\(Z\)\\geq\\mathbb\{E\}\[f\]\+t\)\\leq\\exp\(\-t^\{2\}/\(2L^\{2\}\)\)\.Using the triangle inequality, we know that∥\.∥\\\|\.\\\|is11\-Lipschitz, which allows us to conclude the following for anyt≥0t\\geq 0:

PrZ∼𝒩⁡\(0,Id\)\(∥Z∥≥d\+t\)≤exp\(−t2/2\)\.\\displaystyle Pr\_\{Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\)\}\(\\\|Z\\\|\\geq\\sqrt\{d\}\+t\)\\leq\\exp\(\-t^\{2\}/2\)\.Thus for a large enoughn=ω⁡\(exp⁡\(d\)\)n=\\omega\(\\exp\(\\sqrt\{d\}\)\), and anyθ\\thetawith‖θ‖≤1\\\|\\theta\\\|\\leq 1, we obtain the bound:

P​rX∼𝒩⁡\(θ,Id\)​\(X∉𝒳n\)\\displaystyle Pr\_\{X\\sim\\mathcal\{N\}\(\\theta,I\_\{d\}\)\}\(X\\notin\\mathcal\{X\}\_\{n\}\)=P​rX∼𝒩⁡\(θ,Id\)​\(‖X‖≥1/2​log⁡n\)\\displaystyle=Pr\_\{X\\sim\\mathcal\{N\}\(\\theta,I\_\{d\}\)\}\(\\\|X\\\|\\geq 1/2\\log n\)≤P​rZ∼𝒩⁡\(0,Id\)​\(‖Z‖≥1/2​log⁡n−‖θ‖\)\\displaystyle\\leq Pr\_\{Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\)\}\(\\\|Z\\\|\\geq 1/2\\log n\-\\\|\\theta\\\|\)≤P​rZ∼𝒩⁡\(0,Id\)​\(‖Z‖≥1/2​log⁡n−1\)\\displaystyle\\leq Pr\_\{Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\)\}\(\\\|Z\\\|\\geq 1/2\\log n\-1\)≤exp⁡\(−\(1/2​log⁡n−1−d\)22\)\.\\displaystyle\\leq\\exp\\left\(\-\\frac\{\(1/2\\log n\-1\-\\sqrt\{d\}\)^\{2\}\}\{2\}\\right\)\.Nown=ω⁡\(exp⁡\(d\)\)n=\\omega\(\\exp\(\\sqrt\{d\}\)\)implies thatPrX∼𝒩⁡\(θ,Id\)\(X∉𝒳n\)=O\(n−logn/8\)=O\(k​log⁡n/n3/2\)Pr\_\{X\\sim\\mathcal\{N\}\(\\theta,I\_\{d\}\)\}\(X\\notin\\mathcal\{X\}\_\{n\}\)=O\(n^\{\-\\log n/8\}\)=O\(\\sqrt\{k\\log n\}/n^\{3/2\}\), which establishes the conditions required for Corollary[5\.2\.1](https://arxiv.org/html/2609.20883#S5.Thmtheorem2.Thmcorollary1), implying an upper bound ofO⁡\(k​log⁡n/n\)O\(\\sqrt\{k\\log n\}/\\sqrt\{n\}\)\. We note that this derivation hides constants that depend exponentially on the dimensiondd\. The upper boundO⁡\(k/n\)O\(\\sqrt\{k/n\}\), that has a constant dependence onddis trivially known for a uniform distribution over the means\([Wasserman, 2010](https://arxiv.org/html/2609.20883#bib.bib26)\)\.

If we assume that every distribution in𝔻\\mathbb\{D\}is supported on a set with bounded diameterdiam⁡\(𝒳\)\\mathrm\{diam\}\(\\mathcal\{X\}\), we obtain that for any two distributionsπ1,π2∈𝔻\\pi\_\{1\},\\pi\_\{2\}\\in\\mathbb\{D\},ρW​1​\(π1,π2\)≤diam⁡\(𝒳\)​ρT​V​\(π1,π2\)\\rho\_\{W1\}\(\\pi\_\{1\},\\pi\_\{2\}\)\\leq\\mathrm\{diam\}\(\\mathcal\{X\}\)\\rho\_\{TV\}\(\\pi\_\{1\},\\pi\_\{2\}\), which allows our bounds above to extend to the W1 distance as well\. This is similar to how[Oko et al\. \(2023\)](https://arxiv.org/html/2609.20883#bib.bib9)extend their TV bounds to W1 distance\. Note that the bounds on W1 derived in this way still depend on thekk\-sparsity of the prior to hold in terms of the TV distance\.

## 6Discussion and Future Work

We study the problem of learning a distribution given few samples from the target distribution\. We note that minimax optimality results common in literature suffer from the curse of dimensionality and are too pessimistic to match empirical success\. Consequently, we propose studying Bayes’ optimality of learning distributions and introduce the sparse dimension as a measure of sparsity of the prior\. We provide several examples of sparse distributions involving restricted support, and leave it as an open question to study sparse distributions without restricting the support\. We show that the Bayes’ risk of learning to sample suffers the same lower bounds that the Bayes’ risk of learning distributions does, and show bounds that overcome the curse of dimensionality\. We then show that the Bayes’ risk of learning to sample also satisfy the same upper bounds that the Bayes’ risk of learning distributions does, and show the existence of distribution estimators that match our lower bounds up to logarithmic terms\. We note that while the sparse dimension of a prior might increase with the dimensionality of the support of the distributions, we overcome the curse of dimensionality in terms of the dependence of our bounds on the number of samplesnn, which goes from the worst case bounds ofΘ\(n−c/\(d\+c′\)\)\\Theta\(n^\{\-c/\(d\+c^\{\\prime\}\)\}\)\(for constantsc,c′c,c^\{\\prime\}that depend on smoothness assumptions\) toΘ~​\(k/n\)\\tilde\{\\Theta\}\(\\sqrt\{k/n\}\), whereΘ~\\tilde\{\\Theta\}suppresses the dependence on logarithmic terms\. We restrict our attention to statistical efficiency in this work, and we leave a discussion on computational efficiency to future work\. Investigating meta\-learning methods to learn a feasible prior on learning distributions is an interesting direction for future work\. Along similar lines, it would be interesting to explore learning algorithms that learn using a given prior, and ways to incorporate priors into gradient descent\-based algorithms\.

## References

- Balcanet al\.\(2023\)M\. F\. Balcan, A\. Nguyen, and D\. SharmaNew bounds for hyperparameter tuning of regression problems across instances\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36,pp\. 80066–80078\.Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p5.1)\.
- Balcanet al\.\(2025\)M\. Balcan, S\. Goyal, and D\. SharmaDistribution\-dependent generalization bounds for tuning linear regression across tasks\.External Links:2507\.05084Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p5.1)\.
- Balcanet al\.\(2022\)M\. Balcan, M\. Khodak, D\. Sharma, and A\. TalwalkarProvably tuning the ElasticNet across instances\.InAdvances in Neural Information Processing Systems,S\. Koyejo, S\. Mohamed, A\. Agarwal, D\. Belgrave, K\. Cho, and A\. Oh \(Eds\.\),Vol\.35,pp\. 27769–27782\.Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p5.1)\.
- Balcan \(2020\)M\. BalcanData\-Driven Algorithm Design \(book chapter\)\.InBeyond Worst\-Case Analysis of Algorithms, Tim Roughgarden \(Ed\),Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p5.1)\.
- Bartlettet al\.\(2019\)P\. L\. Bartlett, N\. Harvey, C\. Liaw, and A\. MehrabianNearly\-tight vc\-dimension and pseudodimension bounds for piecewise linear neural networks\.Journal of Machine Learning Research20\(63\),pp\. 1–17\.Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p1.1)\.
- Chenet al\.\(2016\)X\. Chen, A\. Guntuboyina, and Y\. ZhangOn bayes risk lower bounds\.Journal of Machine Learning Research17\(218\),pp\. 1–58\.Cited by:[§A\.1](https://arxiv.org/html/2609.20883#A1.SS1.p4.1),[Theorem A\.3](https://arxiv.org/html/2609.20883#A1.Thmtheorem3)\.
- Chewiet al\.\(2024\)S\. Chewi, J\. Niles\-Weed, and P\. RigolletStatistical optimal transport\.External Links:2407\.18163Cited by:[§2](https://arxiv.org/html/2609.20883#S2.p4.1),[Definition 1](https://arxiv.org/html/2609.20883#Thmdefinition1)\.
- Csiszár \(1972\)I\. CsiszárA class of measures of informativity of observation channels\.Periodica Mathematica Hungarica2\(1\),pp\. 191–213\.External Links:[Document](https://dx.doi.org/10.1007/BF02018661)Cited by:[§A\.1](https://arxiv.org/html/2609.20883#A1.SS1.p1.1)\.
- Davis and Peebles \(1983\)M\. Davis and P\. J\. E\. PeeblesA survey of galaxy redshifts\. v\. the two\-point position and velocity correlations\.Astrophysical Journal267,pp\. 465–482\.Cited by:[Example 3\.5](https://arxiv.org/html/2609.20883#S3.Thmtheorem5.p1.2.1)\.
- Denget al\.\(2009\)J\. Deng, W\. Dong, R\. Socher, L\. Li, K\. Li, and L\. Fei\-FeiImagenet: a large\-scale hierarchical image database\.In2009 IEEE conference on computer vision and pattern recognition,pp\. 248–255\.Cited by:[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Duchi and Wainwright \(2013\)J\. C\. Duchi and M\. J\. WainwrightDistance\-based and continuum fano inequalities with applications to statistical estimation\.External Links:1311\.2669Cited by:[§A\.1](https://arxiv.org/html/2609.20883#A1.SS1.p2.1),[Theorem A\.2](https://arxiv.org/html/2609.20883#A1.Thmtheorem2)\.
- Dupuiset al\.\(2025\)B\. Dupuis, D\. Shariatian, M\. Haddouche, A\. O\. Durmus, and U\. SimsekliAlgorithm\- and data\-dependent generalization bounds for diffusion models\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p4.1)\.
- Fraser \(2020\)J\. M\. FraserAssouad dimension and fractal geometry\.Cambridge Tracts in Mathematics,Cambridge University Press\.Cited by:[Definition 5](https://arxiv.org/html/2609.20883#Thmdefinition5)\.
- Fuet al\.\(2024\)H\. Fu, Z\. Yang, M\. Wang, and M\. ChenUnveil conditional diffusion models with classifier\-free guidance: a sharp statistical theory\.External Links:2403\.11968Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p3.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p4.1),[§1](https://arxiv.org/html/2609.20883#S1.p1.1)\.
- Ghosalet al\.\(2000\)S\. Ghosal, J\. K\. Ghosh, and A\. W\. van der VaartConvergence rates of posterior distributions\.The Annals of Statistics28\(2\),pp\. 500 – 531\.External Links:[Document](https://dx.doi.org/10.1214/aos/1016218228)Cited by:[§B\.1](https://arxiv.org/html/2609.20883#A2.SS1.p1.1),[§B\.1](https://arxiv.org/html/2609.20883#A2.SS1.p11.1),[§B\.2](https://arxiv.org/html/2609.20883#A2.SS2.p1.1),[§B\.2](https://arxiv.org/html/2609.20883#A2.SS2.p2.1),[§B\.2](https://arxiv.org/html/2609.20883#A2.SS2.p3.1.1),[Lemma B\.1](https://arxiv.org/html/2609.20883#A2.Thmtheorem1),[Lemma B\.5](https://arxiv.org/html/2609.20883#A2.Thmtheorem5),[Lemma B\.7](https://arxiv.org/html/2609.20883#A2.Thmtheorem7),[Appendix B](https://arxiv.org/html/2609.20883#A2.p1.1),[item 3](https://arxiv.org/html/2609.20883#S1.I1.i3.p1.1),[§5](https://arxiv.org/html/2609.20883#S5.p8.1)\.
- Gonget al\.\(2019\)S\. Gong, V\. N\. Boddeti, and A\. K\. JainOn the intrinsic dimensionality of image representations\.In2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),Vol\.,pp\. 3982–3991\.External Links:[Document](https://dx.doi.org/10.1109/CVPR.2019.00411)Cited by:[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Goyalet al\.\(2026\)S\. Goyal, R\. Rongali, R\. Ray, and B\. PóczosGeneralization guarantees on data\-driven tuning of gradient descent with langevin updates\.External Links:2604\.13130,[Link](https://arxiv.org/abs/2604.13130)Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p5.1)\.
- Grettonet al\.\(2012\)A\. Gretton, K\. M\. Borgwardt, M\. J\. Rasch, B\. Schölkopf, and A\. SmolaA kernel two\-sample test\.Journal of Machine Learning Research13\(25\),pp\. 723–773\.Cited by:[§2](https://arxiv.org/html/2609.20883#S2.p4.1)\.
- Henighanet al\.\(2020\)T\. Henighan, J\. Kaplan, M\. Katz, M\. Chen, C\. Hesse, J\. Jackson, H\. Jun, T\. B\. Brown, P\. Dhariwal, S\. Gray, C\. Hallacy, B\. Mann, A\. Radford, A\. Ramesh, N\. Ryder, D\. M\. Ziegler, J\. Schulman, D\. Amodei, and S\. McCandlishScaling laws for autoregressive generative modeling\.External Links:2010\.14701,[Link](https://arxiv.org/abs/2010.14701)Cited by:[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Heuselet al\.\(2017\)M\. Heusel, H\. Ramsauer, T\. Unterthiner, B\. Nessler, and S\. HochreiterGANs trained by a two time\-scale update rule converge to a local nash equilibrium\.InAdvances in Neural Information Processing Systems,I\. Guyon, U\. V\. Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett \(Eds\.\),Vol\.30,pp\.\.Cited by:[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Horwitzet al\.\(2025\)E\. Horwitz, N\. Kurer, J\. Kahana, L\. Amar, and Y\. HoshenWe should chart an atlas of all the world’s models\.InThe Thirty\-Ninth Annual Conference on Neural Information Processing Systems Position Paper Track,Cited by:[§3](https://arxiv.org/html/2609.20883#S3.p3.1)\.
- Kpotufe \(2011\)S\. KpotufeK\-nn regression adapts to local intrinsic dimension\.InAdvances in Neural Information Processing Systems,J\. Shawe\-Taylor, R\. Zemel, P\. Bartlett, F\. Pereira, and K\. Weinberger \(Eds\.\),Vol\.24,pp\.\.Cited by:[§3](https://arxiv.org/html/2609.20883#S3.p18.1)\.
- Liang \(2021\)T\. LiangHow well generative adversarial networks learn distributions\.Journal of Machine Learning Research22\(228\),pp\. 1–41\.Cited by:[item 2](https://arxiv.org/html/2609.20883#S1.I1.i2.p1.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p1.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p2.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p3.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p4.1),[§1](https://arxiv.org/html/2609.20883#S1.p1.1),[§1](https://arxiv.org/html/2609.20883#S1.p2.1),[Example 3\.4](https://arxiv.org/html/2609.20883#S3.Thmtheorem4.p1.2.1)\.
- Lianget al\.\(2026\)Z\. Liang, H\. He, C\. Yang, and B\. DaiScaling laws for diffusion transformers\.External Links:2410\.08184,[Link](https://arxiv.org/abs/2410.08184)Cited by:[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Okoet al\.\(2023\)K\. Oko, S\. Akiyama, and T\. SuzukiDiffusion models are minimax optimal distribution estimators\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202,pp\. 26517–26582\.Cited by:[item 3](https://arxiv.org/html/2609.20883#S1.I1.i3.p1.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p2.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p3.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p4.1),[§1](https://arxiv.org/html/2609.20883#S1.p1.1),[§1](https://arxiv.org/html/2609.20883#S1.p2.1),[Example 3\.4](https://arxiv.org/html/2609.20883#S3.Thmtheorem4.p1.2.1),[§5](https://arxiv.org/html/2609.20883#S5.p12.1)\.
- Poczoset al\.\(2013\)B\. Poczos, A\. Singh, A\. Rinaldo, and L\. WassermanDistribution\-free distribution regression\.InProceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics,C\. M\. Carvalho and P\. Ravikumar \(Eds\.\),Proceedings of Machine Learning Research, Vol\.31,Scottsdale, Arizona, USA,pp\. 507–515\.Cited by:[§3](https://arxiv.org/html/2609.20883#S3.p18.1)\.
- Popeet al\.\(2021\)P\. Pope, C\. Zhu, A\. Abdelkader, M\. Goldblum, and T\. GoldsteinThe intrinsic dimension of images and its impact on learning\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Shalev\-Shwartz and Ben\-David \(2014\)S\. Shalev\-Shwartz and S\. Ben\-DavidUnderstanding machine learning: from theory to algorithms\.Cambridge University Press\.Cited by:[§B\.1](https://arxiv.org/html/2609.20883#A2.SS1.p1.1),[Definition 4](https://arxiv.org/html/2609.20883#Thmdefinition4)\.
- Singhet al\.\(2018\)S\. Singh, A\. Uppal, B\. Li, C\. Li, M\. Zaheer, and B\. PoczosNonparametric density estimation under adversarial losses\.InAdvances in Neural Information Processing Systems,S\. Bengio, H\. Wallach, H\. Larochelle, K\. Grauman, N\. Cesa\-Bianchi, and R\. Garnett \(Eds\.\),Vol\.31,pp\.\.Cited by:[item 2](https://arxiv.org/html/2609.20883#S1.I1.i2.p1.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p1.1),[§1](https://arxiv.org/html/2609.20883#S1.p1.1),[§4](https://arxiv.org/html/2609.20883#S4.p1.1),[§5](https://arxiv.org/html/2609.20883#S5.p1.1)\.
- Suzuki \(2019\)T\. SuzukiAdaptivity of deep reLU network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality\.InInternational Conference on Learning Representations,Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p2.1)\.
- Tang and Yang \(2023\)R\. Tang and Y\. YangMinimax rate of distribution estimation on unknown submanifolds under adversarial losses\.The Annals of Statistics51\(3\),pp\. 1282 – 1308\.External Links:[Document](https://dx.doi.org/10.1214/23-AOS2291)Cited by:[item 2](https://arxiv.org/html/2609.20883#S1.I1.i2.p1.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p3.1),[§1](https://arxiv.org/html/2609.20883#S1.p2.1),[§2](https://arxiv.org/html/2609.20883#S2.p4.1),[Example 3\.4](https://arxiv.org/html/2609.20883#S3.Thmtheorem4.p1.1.1),[§3](https://arxiv.org/html/2609.20883#S3.p1.1)\.
- Tang and Yang \(2024\)R\. Tang and Y\. YangAdaptivity of diffusion models to manifold structures\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,S\. Dasgupta, S\. Mandt, and Y\. Li \(Eds\.\),Proceedings of Machine Learning Research, Vol\.238,pp\. 1648–1656\.Cited by:[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p3.1),[§1\.2](https://arxiv.org/html/2609.20883#S1.SS2.p4.1),[§1](https://arxiv.org/html/2609.20883#S1.p2.1)\.
- Tsybakov \(2009\)A\. B\. TsybakovIntroduction to nonparametric estimation\.Springer Series in Statistics,Springer,New York\.External Links:ISBN 978\-0\-387\-79051\-0,[Document](https://dx.doi.org/10.1007/b13794)Cited by:[Lemma A\.4](https://arxiv.org/html/2609.20883#A1.Thmtheorem4)\.
- Wainwright \(2019\)M\. J\. WainwrightMinimax lower bounds\.InHigh\-Dimensional Statistics: A Non\-Asymptotic Viewpoint,Cambridge Series in Statistical and Probabilistic Mathematics,pp\. 485–523\.Cited by:[Theorem A\.1](https://arxiv.org/html/2609.20883#A1.Thmtheorem1),[§B\.2](https://arxiv.org/html/2609.20883#A2.SS2.p8.1)\.
- Wasserman \(2010\)L\. WassermanAll of statistics\.Springer,New York\.Cited by:[Example 3\.3](https://arxiv.org/html/2609.20883#S3.Thmtheorem3.p1.1.1),[Example 5\.3](https://arxiv.org/html/2609.20883#S5.Thmtheorem3.p2.5.1)\.
- Zehaviet al\.\(2005\)I\. Zehavi, Z\. Zheng, D\. H\. Weinberg, J\. A\. Frieman, A\. A\. Berlind, M\. R\. Blanton, R\. Scoccimarro, R\. K\. Sheth, M\. A\. Strauss, I\. Kayo, Y\. Suto, M\. Fukugita, O\. Nakamura, N\. A\. Bahcall, J\. Brinkmann, J\. E\. Gunn, G\. S\. Hennessy, Ž\. Ivezić, G\. R\. Knapp, J\. Loveday, A\. Meiksin, D\. J\. Schlegel, D\. P\. Schneider, I\. Szapudi, M\. Tegmark, M\. S\. Vogeley, D\. G\. York, and \(\. S\. Collaboration\)The luminosity and color dependence of the galaxy correlation function\.The Astrophysical Journal630\(1\),pp\. 1\.External Links:[Document](https://dx.doi.org/10.1086/431891)Cited by:[Example 3\.5](https://arxiv.org/html/2609.20883#S3.Thmtheorem5.p1.2.1)\.

## Appendix AInformation Theoretic Lower Bounds

We first cover some results on information theory and minimax bounds in this section that will be useful to show our bounds\.

### A\.1Background on Information Theory

For a parametrised family of distributions defined over the set𝒳\\mathcal\{X\}denoted by\{πθ\}\\\{\\pi\_\{\\theta\}\\\}forθ∈ℍ\\theta\\in\\mathbb\{H\}and a prior𝒫\\mathcal\{P\}onθ\\theta, we denote the mutual information\[[Csiszár, 1972](https://arxiv.org/html/2609.20883#bib.bib13)\]betweenθ∼𝒫\\theta\\sim\\mathcal\{P\}and a sampleX∼πθX\\sim\\pi\_\{\\theta\}asI⁡\(𝒫,ℍ\)I\(\\mathcal\{P\};\\mathbb\{H\}\)defined as follows:

I\(𝒫;ℍ\)=infQ∫ℍDK​L\(πθ∥Q\)𝒫\(dθ\),I\(\\mathcal\{P\};\\mathbb\{H\}\)=\\inf\_\{Q\}\\int\_\{\\mathbb\{H\}\}D\_\{KL\}\(\\pi\_\{\\theta\}\\\|Q\)\\mathcal\{P\}\(d\\theta\),where the infimum is over all possible distribution measuresQQover𝒳\\mathcal\{X\}\. The mutual information is a measure of the information we get from a sampleX∼πθX\\sim\\pi\_\{\\theta\}aboutπθ\\pi\_\{\\theta\}, given a prior over the possible values ofθ\\theta\. It is widely used in information theory to provide minimax estimation lower bounds using the Fano’s inequality stated below\.

###### Theorem A\.1\(Fano’s inequality\[[Wainwright, 2019](https://arxiv.org/html/2609.20883#bib.bib5)\]\)\.

Consider an M\-ary testing problem where we want to estimate an indexθ∈ℍ=\[M\]\\theta\\in\\mathbb\{H\}=\[M\]corresponding to the family of distributions\{πθ\}\\\{\\pi\_\{\\theta\}\\\}from a sampleX∼πθX\\sim\\pi\_\{\\theta\}\. Further assume a prior𝒫\\mathcal\{P\}to be uniform over the setℍ\\mathbb\{H\}, then the probability of error for any estimatorθ^\\hat\{\\theta\}is lower bounded as follows:

P​r​\(θ^​\(X\)≠θ\)≥1−I⁡\(𝒫,ℍ\)\+log⁡2log⁡M\.\\displaystyle Pr\(\\hat\{\\theta\}\(X\)\\neq\\theta\)\\geq 1\-\\frac\{I\(\\mathcal\{P\};\\mathbb\{H\}\)\+\\log 2\}\{\\log M\}\.

While we will use Fano’s inequality for our proof in Appendix[A\.2](https://arxiv.org/html/2609.20883#A1.SS2), we give other relevant results that can be useful for proving lower bounds in our setting\. In the technical note[Duchi and Wainwright \[2013\]](https://arxiv.org/html/2609.20883#bib.bib14)extend the Fano’s inequality to the continuous case where we are interested in estimating a continuous parameterθ\\thetaupto an accuracy ofϵ\\epsilon\. That is, they consider the Bayes’ risk of the 0\-1 loss function𝕀\[\|θ−θ^\|≥ϵ\]\\mathbb\{I\}\[\|\\theta\-\\hat\{\\theta\}\|\\geq\\epsilon\]\. This is given as the continuum Fano’s inequality below\.

###### Theorem A\.2\(Continuum Fano’s inequality\[[Duchi and Wainwright, 2013](https://arxiv.org/html/2609.20883#bib.bib14)\]\)\.

Consider an estimation problem where we want to estimateθ∈ℍ\\theta\\in\\mathbb\{H\}corresponding to the family of distributions\{πθ\}\\\{\\pi\_\{\\theta\}\\\}from a sampleX∼πθX\\sim\\pi\_\{\\theta\}\. Assume a 0\-1 loss function given by𝕀\[\|θ−θ^\|≥ϵ\]\\mathbb\{I\}\[\|\\theta\-\\hat\{\\theta\}\|\\geq\\epsilon\]\. Further assume a prior𝒫\\mathcal\{P\}to be uniform over the setℍ\\mathbb\{H\}, then the Bayes’ risk of estimation is lower bounded as follows:

RB​a​y​e​s\(θ^;𝒫\)=𝔼θ∼𝒫\[𝔼X∼πθ\[𝕀\[\|θ−θ^\|≥ϵ\]\]\]≥1\+I⁡\(𝒫,ℍ\)\+log⁡2log⁡\(supθ′∈ℍ𝒫⁡\{θ∈ℍ:‖θ−θ′‖≤ϵ\}\)\.\\displaystyle R\_\{Bayes\}\(\\hat\{\\theta\};\\mathcal\{P\}\)=\\mathbb\{E\}\_\{\\theta\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\\sim\\pi\_\{\\theta\}\}\[\\mathbb\{I\}\[\|\\theta\-\\hat\{\\theta\}\|\\geq\\epsilon\]\]\]\\geq 1\+\\frac\{I\(\\mathcal\{P\};\\mathbb\{H\}\)\+\\log 2\}\{\\log\(\\sup\_\{\\theta^\{\\prime\}\\in\\mathbb\{H\}\}\\mathcal\{P\}\\\{\\theta\\in\\mathbb\{H\}:\\\|\\theta\-\\theta^\{\\prime\}\\\|\\leq\\epsilon\\\}\)\}\.

Note that the denominator of the second term above is a log\-probability and is hence negative\. This generalizes the denominator of the Fano’s bound \(Theorem[A\.1](https://arxiv.org/html/2609.20883#A1.Thmtheorem1)\) which by a change of sign of the second term islog⁡\(1/M\)\\log\(1/M\), corresponding to a uniform prior over theMMhypotheses\.

In the current paper we discuss bounds over non\-uniform priors\. The following result from[Chen et al\. \[2016\]](https://arxiv.org/html/2609.20883#bib.bib15)which they call the Generalized Fano’s inequality is useful in such cases\.

###### Theorem A\.3\(Generalized Fano’s inequality\[[Chen et al\., 2016](https://arxiv.org/html/2609.20883#bib.bib15)\]\)\.

Consider an estimation problem where we want to estimateθ∈ℍ\\theta\\in\\mathbb\{H\}corresponding to the family of distributions\{πθ\}\\\{\\pi\_\{\\theta\}\\\}from a sampleX∼πθX\\sim\\pi\_\{\\theta\}\. Assume a 0\-1 loss function given byL⁡\(θ,θ^\)L\(\\theta,\\hat\{\\theta\}\)\. Further assume a prior𝒫\\mathcal\{P\}over the setℍ\\mathbb\{H\}, then the Bayes’ risk of estimation is lower bounded as follows:

RB​a​y​e​s\(θ^;𝒫\)=𝔼θ∼𝒫\[𝔼X∼πθ\[L\(θ,θ^\)\]\]≥1\+I⁡\(𝒫,ℍ\)\+log⁡2log⁡\(supθ′∈ℍ𝒫⁡\{θ∈ℍ:L⁡\(θ,θ′\)=0\}\)\.\\displaystyle R\_\{Bayes\}\(\\hat\{\\theta\};\\mathcal\{P\}\)=\\mathbb\{E\}\_\{\\theta\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\\sim\\pi\_\{\\theta\}\}\[L\(\\theta,\\hat\{\\theta\}\)\]\]\\geq 1\+\\frac\{I\(\\mathcal\{P\};\\mathbb\{H\}\)\+\\log 2\}\{\\log\(\\sup\_\{\\theta^\{\\prime\}\\in\\mathbb\{H\}\}\\mathcal\{P\}\\\{\\theta\\in\\mathbb\{H\}:L\(\\theta,\\theta^\{\\prime\}\)=0\\\}\)\}\.

It is easy to see how the statement of the Generalized Fano’s inequality \(Theorem[A\.3](https://arxiv.org/html/2609.20883#A1.Thmtheorem3)\) generalizes that of the Continuum Fano’s inequality \(Theorem[A\.2](https://arxiv.org/html/2609.20883#A1.Thmtheorem2)\) by allowing for a more general prior and loss function \(still binary\) keeping other terms the same\.

### A\.2Proofs of Main Lower Bounds

In this Section, we give detailed proofs of our main lower bounds\. We first show a dimension\-independentΩ⁡\(k/n\)\\Omega\(\\sqrt\{k/n\}\)lower bound on the Bayes risk for akk\-sparse prior for the total variation distance\. We will require the following result in our analysis\.

###### Lemma A\.4\(Varshamov\-Gilbert bound\[[Tsybakov, 2009](https://arxiv.org/html/2609.20883#bib.bib31)\]\)\.

Letm≥8m\\geq 8\. There exists a sequence of binary vectorsb0,…,bM∈\{0,1\}mb\_\{0\},\\ldots,b\_\{M\}\\in\\\{0,1\\\}^\{m\}such thatb0=\(0,…,0\)b\_\{0\}=\(0,\\ldots,0\),‖bi−bj‖1≥m/8\\\|b\_\{i\}\-b\_\{j\}\\\|\_\{1\}\\geq m/8for0≤i<j≤M0\\leq i<j\\leq MandM≥2m/8M\\geq 2^\{m/8\}\.

We are now ready to prove our result\.

###### Theorem A\.5\(Restated Theorem[4\.2](https://arxiv.org/html/2609.20883#S4.Thmtheorem2)\)\.

Let𝔻\\mathbb\{D\}be the set of all distributions over𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}, and let𝔓\\mathfrak\{P\}be shorthand for𝔓⁡\(k,ρT​V,𝔻\)\\mathfrak\{P\}\(k,\\rho\_\{TV\},\\mathbb\{D\}\),the set of allkk\-sparse priors over𝔻\\mathbb\{D\}using the total variation distance\. If\|𝒳\|≥k\|\\mathcal\{X\}\|\\geq k, the Bayes’ risk for any distribution estimatorπ^n\\hat\{\\pi\}\_\{n\}is lower bounded independent ofddas below:

infπ^sup𝒫∈𝔓RB​a​y​e​s​\(π^,𝒫\)=infπ^sup𝒫∈𝔓𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρT​V​\(π^​\(𝐗\),π\)\]\]=Ω⁡\(k/n\)\.\\displaystyle\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}R\_\{Bayes\}\(\\hat\{\\pi\};\\mathcal\{P\}\)=\\inf\_\{\\hat\{\\pi\}\}\\sup\_\{\\mathcal\{P\}\\in\\mathfrak\{P\}\}\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{TV\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]=\\Omega\(\\sqrt\{k/n\}\)\.

###### Proof\.

Letk≥2k\\geq 2and pickk′=⌊k⌋k^\{\\prime\}=\\lfloor k\\rfloorork′=⌊k⌋−1k^\{\\prime\}=\\lfloor k\\rfloor\-1to be an even number\. Letz1,…,zk′∈𝒳z\_\{1\},\\ldots,z\_\{k^\{\\prime\}\}\\in\\mathcal\{X\}be unequal elements in𝒳\\mathcal\{X\}\. Consider the set of binary vectors of lengthk′/2k^\{\\prime\}/2,S1=\{−1,1\}k′/2S\_\{1\}=\\\{\-1,1\\\}^\{k^\{\\prime\}/2\}, and for someδ∈\(0,1/2\)\\delta\\in\(0,1/2\), define the set of discrete probabilities\{θ∈\[0,1\]k′:θi=1\+bi​δk′,θk′\+1−i=1−bi​δk′,∀i≤k′/2,b∈S1\}\\\{\\theta\\in\[0,1\]^\{k^\{\\prime\}\}:\\theta\_\{i\}=\\frac\{1\+b\_\{i\}\\delta\}\{k^\{\\prime\}\},\\theta\_\{k^\{\\prime\}\+1\-i\}=\\frac\{1\-b\_\{i\}\\delta\}\{k^\{\\prime\}\},\\forall i\\leq k^\{\\prime\}/2,b\\in S\_\{1\}\\\}\. Note by construction that this set contains2k′/22^\{k^\{\\prime\}/2\}probability vectors, each of which sum to11and differ in at least22coordinates\. In fact, we can use Lemma[A\.4](https://arxiv.org/html/2609.20883#A1.Thmtheorem4)for large enoughk′k^\{\\prime\}to show that there exists a setS2⊆S1S\_\{2\}\\subseteq S\_\{1\}of size\|S2\|≥2k′/16\|S\_\{2\}\|\\geq 2^\{k^\{\\prime\}/16\}such that any two binary vectors insideS2S\_\{2\}differ in at leastk′/16k^\{\\prime\}/16coordinates\. Thus, defineℍ=\{θ∈\[0,1\]k′:θi=1\+bi​δk′,θk′\+1−i=1−bi​δk′,∀i≤k′/2,b∈S2\}\\mathbb\{H\}=\\\{\\theta\\in\[0,1\]^\{k^\{\\prime\}\}:\\theta\_\{i\}=\\frac\{1\+b\_\{i\}\\delta\}\{k^\{\\prime\}\},\\theta\_\{k^\{\\prime\}\+1\-i\}=\\frac\{1\-b\_\{i\}\\delta\}\{k^\{\\prime\}\},\\forall i\\leq k^\{\\prime\}/2,b\\in S\_\{2\}\\\}, as the set of≥2k′/16\\geq 2^\{k^\{\\prime\}/16\}probability vectors, each of which sum to11and differ in at leastk′/8k^\{\\prime\}/8coordinates\. Using Equation[3](https://arxiv.org/html/2609.20883#S4.E3), we obtain that forθ,θ′∈ℍ\\theta,\\theta^\{\\prime\}\\in\\mathbb\{H\},ρT​V​\(πθ,πθ′\)≥\(1/2\)⋅\(2​δ/k′\)⋅\(k′/8\)=δ/8\\rho\_\{TV\}\(\\pi\_\{\\theta\},\\pi\_\{\\theta^\{\\prime\}\}\)\\geq\(1/2\)\\cdot\(2\\delta/k^\{\\prime\}\)\\cdot\(k^\{\\prime\}/8\)=\\delta/8\.

Let𝔻\\mathbb\{D\}be the set of discrete distributions with probability vectors that belong toℍ\\mathbb\{H\}, and let𝒫\\mathcal\{P\}to be the uniform prior overℍ\\mathbb\{H\}, which iskk\-sparse by Corollary[3\.1\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem1.Thmcorollary2)\. We simplify the desired Bayes’ risk bound as follows:

𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρT​V​\(π^​\(𝐗\),π\)\]\]\\displaystyle\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{TV\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]=∑θ𝒫⁡\(θ\)​𝔼X1,…,Xn∼πθ​\[‖θ^−θ‖1/2\]≥∑θ𝒫⁡\(θ\)​P​r​\(θ^≠θ\)⋅δ/8\.\\displaystyle=\\sum\_\{\\theta\}\\mathcal\{P\}\(\\theta\)\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{\\theta\}\}\[\\\|\\hat\{\\theta\}\-\\theta\\\|\_\{1\}/2\]\\geq\\sum\_\{\\theta\}\\mathcal\{P\}\(\\theta\)Pr\(\\hat\{\\theta\}\\neq\\theta\)\\cdot\\delta/8\.
Using Fano’s inequality \(Theorem[A\.1](https://arxiv.org/html/2609.20883#A1.Thmtheorem1)\),

P​r​\(θ^≠θ\)≥1−I⁡\(𝒫,ℍ\)\+log⁡2log⁡\(2k′/16\)\.\\displaystyle Pr\(\\hat\{\\theta\}\\neq\\theta\)\\geq 1\-\\frac\{I\(\\mathcal\{P\};\\mathbb\{H\}\)\+\\log 2\}\{\\log\(2^\{k^\{\\prime\}/16\}\)\}\.
In order to bound the mutual information, we first bound the KL divergence between any two elements of𝔻\\mathbb\{D\}:

DK​L\(πθ∥πθ′\)\\displaystyle D\_\{KL\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\theta^\{\\prime\}\}\)=∑θi​log⁡\(θi/θi′\)=∑i,θi≠θi′θi​log⁡\(θi/θi′\)=∑i,θi=1\+δk′θi​log⁡\(θi/θi′\)\+∑i,θi=1−δk′θi​log⁡\(θi/θi′\)\\displaystyle=\\sum\\theta\_\{i\}\\log\(\\theta\_\{i\}/\\theta^\{\\prime\}\_\{i\}\)=\\sum\_\{i,\\theta\_\{i\}\\neq\\theta^\{\\prime\}\_\{i\}\}\\theta\_\{i\}\\log\(\\theta\_\{i\}/\\theta^\{\\prime\}\_\{i\}\)=\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\+\\delta\}\{k^\{\\prime\}\}\}\\theta\_\{i\}\\log\(\\theta\_\{i\}/\\theta^\{\\prime\}\_\{i\}\)\+\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\-\\delta\}\{k^\{\\prime\}\}\}\\theta\_\{i\}\\log\(\\theta\_\{i\}/\\theta^\{\\prime\}\_\{i\}\)=∑i,θi=1\+δk′θi​log⁡\(\(1\+δ\)/\(1−δ\)\)\+∑i,θi=1−δk′θi​log⁡\(\(1−δ\)/\(1\+δ\)\)\.\\displaystyle=\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\+\\delta\}\{k^\{\\prime\}\}\}\\theta\_\{i\}\\log\(\(1\+\\delta\)/\(1\-\\delta\)\)\+\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\-\\delta\}\{k^\{\\prime\}\}\}\\theta\_\{i\}\\log\(\(1\-\\delta\)/\(1\+\\delta\)\)\.Now, the number of timesθi\>θi′\\theta\_\{i\}\>\\theta^\{\\prime\}\_\{i\}is equal to the number of timesθi<θi′\\theta\_\{i\}<\\theta^\{\\prime\}\_\{i\}since the sum over allθi\\theta\_\{i\}andθi′\\theta\_\{i\}^\{\\prime\}is constant\. Further, forδ≤1/2\\delta\\leq 1/2,log⁡\(\(1\+δ\)/\(1−δ\)\)≤3​δ\\log\(\(1\+\\delta\)/\(1\-\\delta\)\)\\leq 3\\delta\. Thus,

DK​L\(πθ∥πθ′\)\\displaystyle D\_\{KL\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\theta^\{\\prime\}\}\)=∑i,θi=1\+δk′\(δ/k′\)log\(\(1\+δ\)/\(1−δ\)\)\+∑i,θi=1−δk′\(−δ/k′\)log\(\(1−δ\)/\(1\+δ\)\)\\displaystyle=\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\+\\delta\}\{k^\{\\prime\}\}\}\(\\delta/k^\{\\prime\}\)\\log\(\(1\+\\delta\)/\(1\-\\delta\)\)\+\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\-\\delta\}\{k^\{\\prime\}\}\}\(\-\\delta/k^\{\\prime\}\)\\log\(\(1\-\\delta\)/\(1\+\\delta\)\)≤1k′​\(∑i,θi=1\+δk′3​δ2\+∑i,θi=1−δk′3​δ2\)≤3​δ2\.\\displaystyle\\leq\\frac\{1\}\{k^\{\\prime\}\}\(\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\+\\delta\}\{k^\{\\prime\}\}\}3\\delta^\{2\}\+\\sum\_\{i,\\theta\_\{i\}=\\frac\{1\-\\delta\}\{k^\{\\prime\}\}\}3\\delta^\{2\}\)\\leq 3\\delta^\{2\}\.
This allows the following mutual information bound, for someθ0∈ℍ\\theta\_\{0\}\\in\\mathbb\{H\}:

I⁡\(𝒫,ℍ\)\\displaystyle I\(\\mathcal\{P\};\\mathbb\{H\}\)=infQ​over​𝒳⊗n∑DK​L\(πθ⊗n∥Q\)𝒫\(θ\)≤∑DK​L\(πθ⊗n∥πθ0⊗n\)𝒫\(θ\)\\displaystyle=\\inf\_\{Q\\text\{ over \}\\mathcal\{X\}^\{\\otimes n\}\}\\sum D\_\{KL\}\(\\pi\_\{\\theta\}^\{\\otimes n\}\\\|Q\)\\mathcal\{P\}\(\\theta\)\\leq\\sum D\_\{KL\}\(\\pi\_\{\\theta\}^\{\\otimes n\}\\\|\\pi\_\{\\theta\_\{0\}\}^\{\\otimes n\}\)\\mathcal\{P\}\(\\theta\)≤n∑DK​L\(πθ∥πθ0\)𝒫\(θ\)≤3nδ2\.\\displaystyle\\leq n\\sum D\_\{KL\}\(\\pi\_\{\\theta\}\\\|\\pi\_\{\\theta\_\{0\}\}\)\\mathcal\{P\}\(\\theta\)\\leq 3n\\delta^\{2\}\.
Substituting this into our desired bound gives:

𝔼π∼𝒫​\[𝔼𝐗∼π⊗n​\[ρT​V​\(π^​\(𝐗\),π\)\]\]\\displaystyle\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{P\}\}\\left\[\\mathbb\{E\}\_\{\\mathbf\{X\}\\sim\\pi^\{\\otimes n\}\}\[\\rho\_\{TV\}\(\\hat\{\\pi\}\(\\mathbf\{X\}\),\\pi\)\]\\right\]≥\(δ/8\)​∑θ𝒫⁡\(θ\)​P​r​\(θ^≠θ\)≥\(δ/8\)​∑θ𝒫⁡\(θ\)​\(1−3​n​δ2\+log⁡2\(k′/16\)​log⁡2\)\\displaystyle\\geq\(\\delta/8\)\\sum\_\{\\theta\}\\mathcal\{P\}\(\\theta\)Pr\(\\hat\{\\theta\}\\neq\\theta\)\\geq\(\\delta/8\)\\sum\_\{\\theta\}\\mathcal\{P\}\(\\theta\)\\left\(1\-\\frac\{3n\\delta^\{2\}\+\\log 2\}\{\(k^\{\\prime\}/16\)\\log 2\}\\right\)=\(δ/8\)​\(1−3​n​δ2\+log⁡2\(k′/16\)​log⁡2\)\.\\displaystyle=\(\\delta/8\)\\left\(1\-\\frac\{3n\\delta^\{2\}\+\\log 2\}\{\(k^\{\\prime\}/16\)\\log 2\}\\right\)\.
Now, since the choice ofδ\\deltais arbitrary, for large enoughk′k^\{\\prime\}andn=Ω⁡\(k\)n=\\Omega\(k\), we pickδ=\(\(k′/32\)−1\)​log⁡23​n\\delta=\\sqrt\{\\frac\{\(\(k^\{\\prime\}/32\)\-1\)\\log 2\}\{3n\}\}to obtain our desired bound ofΩ⁡\(k′/n\)=Ω⁡\(k/n\)\\Omega\(\\sqrt\{k^\{\\prime\}/n\}\)=\\Omega\(\\sqrt\{k/n\}\)\. ∎

## Appendix BNonparametric Bayesian Upper Bounds

We discuss Bayesian distribution estimation in this paper using nonparametric priors\. We derive our upper bounds using the theory of posterior convergence rates from[Ghosal et al\. \[2000\]](https://arxiv.org/html/2609.20883#bib.bib30)\. We state important results from nonparametric Bayesian convergence rates here, but first give a brief background on covering numbers\.

### B\.1Background on Covering Numbers

Covering numbers and packing numbers are important tools used in learning theoretic upper bounds\[[Shalev\-Shwartz and Ben\-David, 2014](https://arxiv.org/html/2609.20883#bib.bib29),[Ghosal et al\., 2000](https://arxiv.org/html/2609.20883#bib.bib30)\]\. We recall the definition of covering number from Section[3](https://arxiv.org/html/2609.20883#S3)\.

###### Definition 6\(Covering number\)\.

For a set𝔻\\mathbb\{D\}with a distance \(pseudo\-\)metricρ\\rho, consider a set of points𝔸\\mathbb\{A\}such that for any elementμ∈𝔻\\mu\\in\\mathbb\{D\},∃ν∈𝔸\\exists\\nu\\in\\mathbb\{A\}such thatρ⁡\(μ,ν\)≤r\\rho\(\\mu,\\nu\)\\leq r\. Then𝔸\\mathbb\{A\}is called anrr\-cover of𝔻\\mathbb\{D\}\. We defineN⁡\(r,𝔻\)N\(r,\\mathbb\{D\}\), therr\-covering number of𝔻\\mathbb\{D\}, as the cardinality of the smallestrr\-cover of𝔻\\mathbb\{D\}\. Thus, if therr\-cover𝔸\\mathbb\{A\}is the smallest possible,\|𝔸\|=N⁡\(r,𝔻\)\|\\mathbb\{A\}\|=N\(r,\\mathbb\{D\}\)\.

An analogous notion to the covering number is the packing number\.

###### Definition 7\(Packing number\)\.

For a set𝔻\\mathbb\{D\}with a distance \(pseudo\-\)metricρ\\rho, consider a set of points𝔸⊆𝔻\\mathbb\{A\}\\subseteq\\mathbb\{D\}such that∄ν1≠ν2∈𝔸\\nexists\\;\\nu\_\{1\}\\neq\\nu\_\{2\}\\in\\mathbb\{A\}for whichρ⁡\(ν1,ν2\)≤r\\rho\(\\nu\_\{1\},\\nu\_\{2\}\)\\leq r\. Then𝔸\\mathbb\{A\}is called anrr\-packing of𝔻\\mathbb\{D\}\. We defineD⁡\(r,𝔻\)D\(r,\\mathbb\{D\}\), therr\-packing number of𝔻\\mathbb\{D\}, as the cardinality of the biggestrr\-packing of𝔻\\mathbb\{D\}\. Thus, if the set𝔸\\mathbb\{A\}is the largest possible,\|𝔸\|=D⁡\(r,𝔻\)\|\\mathbb\{A\}\|=D\(r,\\mathbb\{D\}\)\.

We state the following Lemma, without proof which is commonly used to relate covering numbers with packing numbers\.

###### Lemma B\.1\(\[[Ghosal et al\., 2000](https://arxiv.org/html/2609.20883#bib.bib30)\]\)\.

For a set𝔻\\mathbb\{D\}with a distance \(pseudo\-\)metricρ\\rhoand for anyr\>0r\>0,

N⁡\(r,𝔻\)≤D⁡\(r,𝔻\)≤N⁡\(r/2,𝔻\)\.\\displaystyle N\(r,\\mathbb\{D\}\)\\leq D\(r,\\mathbb\{D\}\)\\leq N\(r/2,\\mathbb\{D\}\)\.

We use the above Lemma to show the Proposition below which is useful for our analysis in the paper\.

###### Proposition B\.2\.

Let𝔻⊆ℝd\\mathbb\{D\}\\subseteq\\mathbb\{R\}^\{d\}equipped with anlal\_\{a\}norm fora∈\[1,∞\]a\\in\[1,\\infty\]as the distance metric\. For any pointν∈𝔻\\nu\\in\\mathbb\{D\}and0<r<R0<r<R,N⁡\(r,B⁡\(R,ν\)∩𝔻\)≤\(3​R/r\)dN\(r,B\(R,\\nu\)\\cap\\mathbb\{D\}\)\\leq\(3R/r\)^\{d\}\.

###### Proof\.

We first note that in add\-dimensional space with anylal\_\{a\}norm, the volume of anyrr\-ball,V⁡\(r\)∝rdV\(r\)\\propto r^\{d\}\. Consider the largestrrpacking ofB⁡\(R,ν\)∩𝔻B\(R,\\nu\)\\cap\\mathbb\{D\}, such that every point in the packing is at a distance at leastrrfrom each other\. Thus, balls of radiusr/2r/2created around every element of the packing must be non\-overlapping\. If we haveNNsuch balls in the largest packing, then the total volume of the balls,N​V​\(r/2\)NV\(r/2\), is less than the volume of theR\+r/2R\+r/2ball,V⁡\(R\+r/2\)V\(R\+r/2\), because the balls don’t overlap\. Thus,D⁡\(r,B⁡\(R,ν\)∩𝔻\)=N≤\(R\+r/2\)d/\(r/2\)d=\(2​R/r\+1\)d≤\(3​R/r\)dD\(r,B\(R,\\nu\)\\cap\\mathbb\{D\}\)=N\\leq\(R\+r/2\)^\{d\}/\(r/2\)^\{d\}=\(2R/r\+1\)^\{d\}\\leq\(3R/r\)^\{d\}\. Now using Lemma[B\.1](https://arxiv.org/html/2609.20883#A2.Thmtheorem1)completes the proof\. ∎

We use a similar idea to bound the covering number of akk\-Ahlfors regular set\. We first define akk\-Ahlfors regular set formally\.

###### Definition 8\(kk\-Ahlfors regular sets\)\.

A set𝔻\\mathbb\{D\}equipped with the distance \(pseudo\-\)metricρ\\rhoiskk\-Ahlfors regular if there exists a Borel measureℳ\\mathcal\{M\}with support𝔻\\mathbb\{D\}and a constantC≥1C\\geq 1such that for anyν∈𝔻\\nu\\in\\mathbb\{D\}and radius0<r≤diam⁡\(𝔻\)0<r\\leq\\mathrm\{diam\}\(\\mathbb\{D\}\),C−1​rk≤ℳ⁡\(B⁡\(r,ν\)∩𝔻\)≤C​rkC^\{\-1\}r^\{k\}\\leq\\mathcal\{M\}\(B\(r,\\nu\)\\cap\\mathbb\{D\}\)\\leq Cr^\{k\}\.

The following Proposition bounds the covering number of a set given that it is Ahlfors regular\.

###### Proposition B\.3\.

Consider akk\-Ahlfors regular set𝔻\\mathbb\{D\}equipped with the distance \(pseudo\-\)metricρ\\rhosuch that the Borel measureℳ\\mathcal\{M\}satisfies the conditions of Definition[8](https://arxiv.org/html/2609.20883#Thmdefinition8)\. For any pointν∈𝔻\\nu\\in\\mathbb\{D\}and0<r<R≤diam⁡\(𝔻\)0<r<R\\leq\\mathrm\{diam\}\(\\mathbb\{D\}\),N⁡\(r,B⁡\(R,ν\)∩𝔻\)≤C2​\(3​R/r\)kN\(r,B\(R,\\nu\)\\cap\\mathbb\{D\}\)\\leq C^\{2\}\(3R/r\)^\{k\}\.

###### Proof\.

Consider the largestrrpacking ofB⁡\(R,ν\)∩𝔻B\(R,\\nu\)\\cap\\mathbb\{D\}, such that every point in the packing is at a distance at leastrrfrom each other\. Thus, balls of radiusr/2r/2created around every element of the packing \(each of which is in𝔻\\mathbb\{D\}\) must be non\-overlapping\. If we haveNNsuch balls in the largest packing, then the totalℳ\\mathcal\{M\}\-measure of the balls is always less than the totalℳ\\mathcal\{M\}\-measure of theR\+r/2R\+r/2ball centered atν\\nu, because the balls don’t overlap\. Thus,N​C−1​\(r/2\)k≤C​\(R\+r/2\)k⟹N≤C2​\(R\+r/2\)k/\(r/2\)k≤C2​\(3​R/r\)kNC^\{\-1\}\(r/2\)^\{k\}\\leq C\(R\+r/2\)^\{k\}\\implies N\\leq C^\{2\}\(R\+r/2\)^\{k\}/\(r/2\)^\{k\}\\leq C^\{2\}\(3R/r\)^\{k\}\. SinceD⁡\(r,B⁡\(R,ν\)∩𝔻\)=ND\(r,B\(R,\\nu\)\\cap\\mathbb\{D\}\)=N, using Lemma[B\.1](https://arxiv.org/html/2609.20883#A2.Thmtheorem1)completes the proof\. ∎

The following result will be useful for showing Ahlfors regularity of sets\.

###### Lemma B\.4\.

Consider \(pseudo\-\)metricsρ1,ρ2\\rho\_\{1\},\\rho\_\{2\}such that there exist constantsc1,c2\>0c\_\{1\},c\_\{2\}\>0for which for anyμ1,μ2∈𝔻\\mu\_\{1\},\\mu\_\{2\}\\in\\mathbb\{D\},c1​ρ2​\(μ1,μ2\)≤ρ1​\(μ1,μ2\)≤c2​ρ2​\(μ1,μ2\)c\_\{1\}\\rho\_\{2\}\(\\mu\_\{1\},\\mu\_\{2\}\)\\leq\\rho\_\{1\}\(\\mu\_\{1\},\\mu\_\{2\}\)\\leq c\_\{2\}\\rho\_\{2\}\(\\mu\_\{1\},\\mu\_\{2\}\)\. If the set𝔻\\mathbb\{D\}iskk\-Ahlfors regular when equipped with the \(pseudo\-\)metricρ1\\rho\_\{1\}, it is alsokk\-Ahlfors regular when equipped with the \(pseudo\-\)metricρ2\\rho\_\{2\}\.

###### Proof\.

Letℳ\\mathcal\{M\}be the Borel measure guaranteed by Definition[8](https://arxiv.org/html/2609.20883#Thmdefinition8), such that there exists a constantC≥1C\\geq 1such that for anyν∈𝔻\\nu\\in\\mathbb\{D\}and radius0<r≤diamρ1​\(𝔻\)0<r\\leq\\mathrm\{diam\}\_\{\\rho\_\{1\}\}\(\\mathbb\{D\}\),C−1​rk≤ℳ⁡\(Bρ1​\(r,ν\)∩𝔻\)≤C​rkC^\{\-1\}r^\{k\}\\leq\\mathcal\{M\}\(B\_\{\\rho\_\{1\}\}\(r,\\nu\)\\cap\\mathbb\{D\}\)\\leq Cr^\{k\}\. Now, for anyν∈𝔻\\nu\\in\\mathbb\{D\}and radius0<r≤diamρ2​\(𝔻\)0<r\\leq\\mathrm\{diam\}\_\{\\rho\_\{2\}\}\(\\mathbb\{D\}\), we have thatℳ⁡\(Bρ2​\(r,ν\)∩𝔻\)≤ℳ⁡\(Bρ1​\(c2​r,ν\)∩𝔻\)≤C​min⁡\(c2​r,diamρ1​\(𝔻\)\)k≤C​c2k​rk\\mathcal\{M\}\(B\_\{\\rho\_\{2\}\}\(r,\\nu\)\\cap\\mathbb\{D\}\)\\leq\\mathcal\{M\}\(B\_\{\\rho\_\{1\}\}\(c\_\{2\}r,\\nu\)\\cap\\mathbb\{D\}\)\\leq C\\min\(c\_\{2\}r,\\mathrm\{diam\}\_\{\\rho\_\{1\}\}\(\\mathbb\{D\}\)\)^\{k\}\\leq Cc\_\{2\}^\{k\}r^\{k\}\. Now note thatc1​diamρ2​\(𝔻\)≤diamρ1​\(𝔻\)c\_\{1\}\\mathrm\{diam\}\_\{\\rho\_\{2\}\}\(\\mathbb\{D\}\)\\leq\\mathrm\{diam\}\_\{\\rho\_\{1\}\}\(\\mathbb\{D\}\), since otherwise there exist pointsμ1,μ2∈𝔻\\mu\_\{1\},\\mu\_\{2\}\\in\\mathbb\{D\}for whichc1​ρ2​\(μ1,μ2\)\>ρ1​\(μ1,μ2\)c\_\{1\}\\rho\_\{2\}\(\\mu\_\{1\},\\mu\_\{2\}\)\>\\rho\_\{1\}\(\\mu\_\{1\},\\mu\_\{2\}\)\. Thus, for anyν∈𝔻\\nu\\in\\mathbb\{D\}and radius0<r≤diamρ2​\(𝔻\)0<r\\leq\\mathrm\{diam\}\_\{\\rho\_\{2\}\}\(\\mathbb\{D\}\), we have thatℳ⁡\(Bρ2​\(r,ν\)∩𝔻\)≥ℳ⁡\(Bρ1​\(c1​r,ν\)∩𝔻\)≥C−1​\(c1​r\)k\\mathcal\{M\}\(B\_\{\\rho\_\{2\}\}\(r,\\nu\)\\cap\\mathbb\{D\}\)\\geq\\mathcal\{M\}\(B\_\{\\rho\_\{1\}\}\(c\_\{1\}r,\\nu\)\\cap\\mathbb\{D\}\)\\geq C^\{\-1\}\(c\_\{1\}r\)^\{k\}\. We establish the required Ahlfors regularity forρ2\\rho\_\{2\}by picking a constantC′=max⁡\(C​c1−k,C​c2k\)C^\{\\prime\}=\\max\(Cc\_\{1\}^\{\-k\},Cc\_\{2\}^\{k\}\)\. ∎

The following result from[Ghosal et al\. \[2000\]](https://arxiv.org/html/2609.20883#bib.bib30)shows the existence of a test for a distributionν0\\nu\_\{0\}, given a bound on the packing number of a shrinking ball aroundν0\\nu\_\{0\}\. Here we denote a test as a measurable functionϕ:𝒳n→\[0,1\]\\phi:\\mathcal\{X\}^\{n\}\\rightarrow\[0,1\]\.

###### Lemma B\.5\(Theorem 7\.1,\[[Ghosal et al\., 2000](https://arxiv.org/html/2609.20883#bib.bib30)\]\)\.

Suppose that for a non\-increasing functionD⁡\(ϵ\)D\(\\epsilon\), someϵn≥0\\epsilon\_\{n\}\\geq 0and everyϵ\>ϵn\\epsilon\>\\epsilon\_\{n\},

D⁡\(ϵ/2,\{ν:ϵ≤ρ⁡\(ν,ν0\)≤2​ϵ\}\)≤D⁡\(ϵ\),\\displaystyle D\(\\epsilon/2,\\\{\\nu:\\epsilon\\leq\\rho\(\\nu,\\nu\_\{0\}\)\\leq 2\\epsilon\\\}\)\\leq D\(\\epsilon\),whereρ\\rhois the distance \(pseudo\-\)metric between distributions chosen to be either the Hellinger or the TV distance\. Then for everyϵ\>ϵn\\epsilon\>\\epsilon\_\{n\}, there exist testsϕn\\phi\_\{n\}\(depending onϵ\>0\\epsilon\>0\), such that, for a universal constantCtestC\_\{\\mathrm\{test\}\}and everyj∈ℕj\\in\\mathbb\{N\},

𝔼ν0⊗n​\[ϕn\]\\displaystyle\\mathbb\{E\}\_\{\\nu\_\{0\}^\{\\otimes n\}\}\[\\phi\_\{n\}\]≤D⁡\(ϵ\)​exp⁡\(−Ctest​n​ϵ2\)​11−exp⁡\(−Ctest​n​ϵ2\)\\displaystyle\\leq D\(\\epsilon\)\\exp\(\-C\_\{\\mathrm\{test\}\}n\\epsilon^\{2\}\)\\frac\{1\}\{1\-\\exp\(\-C\_\{\\mathrm\{test\}\}n\\epsilon^\{2\}\)\}supρ⁡\(ν,ν0\)\>j​ϵ𝔼ν⊗n​\[1−ϕn\]\\displaystyle\\sup\_\{\\rho\(\\nu,\\nu\_\{0\}\)\>j\\epsilon\}\\mathbb\{E\}\_\{\\nu^\{\\otimes n\}\}\[1\-\\phi\_\{n\}\]≤exp⁡\(−Ctest​n​ϵ2​j2\)\.\\displaystyle\\leq\\exp\(\-C\_\{\\mathrm\{test\}\}n\\epsilon^\{2\}j^\{2\}\)\.

### B\.2Posterior Contraction Rates

We begin this section by defining the posterior rate of contraction for a fixed prior\. This definition is a weaker form of the treatment of[Ghosal et al\. \[2000\]](https://arxiv.org/html/2609.20883#bib.bib30), where the authors allow the prior to depend on the number of samplesnn\.

###### Definition 9\(Posterior Rate of Contraction\)\.

Consider a set of distributions\{πθ\}\\\{\\pi\_\{\\theta\}\\\}parametrized byθ∈𝔻\\theta\\in\\mathbb\{D\}with a distance \(pseudo\-\)metricρ\\rhooverθ\\theta, and a prior distribution𝒫\\mathcal\{P\}over the set𝔻\\mathbb\{D\}\. Assume we obtain samplesX1,…,Xn∼πθ0X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{\\theta\_\{0\}\}forθ0∈𝔻\\theta\_\{0\}\\in\\mathbb\{D\}and denote by𝒫\(⋅\|X1,…,Xn\)\\mathcal\{P\}\(\\cdot\|X\_\{1\},\\ldots,X\_\{n\}\)the posterior probability of an event\. We say the posterior contracts at a rateϵn→0\\epsilon\_\{n\}\\rightarrow 0if𝒫\(θ:ρ\(θ,θ0\)\>Mnϵn\|X1,…,Xn\)→0\\mathcal\{P\}\(\\theta:\\rho\(\\theta,\\theta\_\{0\}\)\>M\_\{n\}\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\\rightarrow 0inπθ0⊗n\\pi\_\{\\theta\_\{0\}\}^\{\\otimes n\}\-probability, for everyMn→∞M\_\{n\}\\rightarrow\\inftyasn→∞n\\rightarrow\\infty\.

Intuitively, the above definition defines the posterior to contract at a rateϵn\\epsilon\_\{n\}if the posterior probability of anϵn\\epsilon\_\{n\}\-ball around the true parameter tends to 1\. Note that asymptotic rates for parametric Bayesian approaches do not depend on the priors since we expect any estimator to “forget” the prior in the asymptotic limit of samples\. This is however not true for nonparametric Bayesian approaches as considered in this paper, where the asymptotic rates depend heavily on the choice of prior as we observe in the following result\. We state the following Lemma, which is easily derivable from the proof of Theorem 2\.1 in[Ghosal et al\. \[2000\]](https://arxiv.org/html/2609.20883#bib.bib30), proved formally here for the reader’s convenience\.

###### Lemma B\.6\.

Consider a prior𝒫\\mathcal\{P\}defined over the set of distributions𝔻\\mathbb\{D\}with the distance metricρ\\rhochosen as either the Hellinger or the TV distance\. Suppose there exists sequencesδn\\delta\_\{n\}andϵn\\epsilon\_\{n\}withϵn→0\\epsilon\_\{n\}\\rightarrow 0andn​ϵn2→∞n\\epsilon\_\{n\}^\{2\}\\rightarrow\\inftyasn→∞n\\rightarrow\\infty, and a constantb\>0b\>0and sets𝔻n⊂𝔻\\mathbb\{D\}\_\{n\}\\subset\\mathbb\{D\}such that forπ0∈𝔻\\pi\_\{0\}\\in\\mathbb\{D\},

1. 1\.log⁡\(D⁡\(ϵn,𝔻n\)\)≤n​ϵn2\\displaystyle\\log\(D\(\\epsilon\_\{n\},\\mathbb\{D\}\_\{n\}\)\)\\leq n\\epsilon\_\{n\}^\{2\}
2. 2\.𝒫⁡\(𝔻/𝔻n\)≤exp⁡\(−n​ϵn2​\(b\+4\)\)\\displaystyle\\mathcal\{P\}\(\\mathbb\{D\}/\\mathbb\{D\}\_\{n\}\)\\leq\\exp\(\-n\\epsilon\_\{n\}^\{2\}\(b\+4\)\)
3. 3\.P​rX1,…,Xn∼π0​\(∫∏⁡\(π/π0\)​\(Xi\)​𝑑𝒫​\(π\)≥exp⁡\(−\(2\+b\)​n​ϵn2\)\)≥1−δn\.\\displaystyle Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\left\(\\int\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\geq\\exp\(\-\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\right\)\\geq 1\-\\delta\_\{n\}\.

Then, there exists a universal constantCtestC\_\{\\mathrm\{test\}\}for which we can bound the posterior probability far fromπ0\\pi\_\{0\}for a large enoughM\>0M\>0, asymptotically asn→∞n\\rightarrow\\infty, as follows:

𝔼π0⊗n\[𝒫\(π:ρ\(π,π0\)\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>Mϵn\|X1,…,Xn\)\]≤2exp\(−Ctestnϵn2\)\+δn\\displaystyle\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\]\\leq 2\\exp\(\-C\_\{\\mathrm\{test\}\}n\\epsilon\_\{n\}^\{2\}\)\+\\delta\_\{n\}\+exp⁡\(\(2\+b\)​n​ϵn2\)​\(exp⁡\(−\(b\+4\)​n​ϵn2\)\+exp⁡\(−Ctest​n​M2​ϵn2\)\)\.\\displaystyle\+\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\(\\exp\(\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\)\+\\exp\(\-C\_\{\\mathrm\{test\}\}nM^\{2\}\\epsilon\_\{n\}^\{2\}\)\)\.

###### Proof\.

The proof tracks the proof of Theorem 2\.1 in[Ghosal et al\. \[2000\]](https://arxiv.org/html/2609.20883#bib.bib30)closely, adding some more detail for clarity\. For everyϵ\>2​ϵn\\epsilon\>2\\epsilon\_\{n\}, Condition 1 implies:

log⁡\(D⁡\(ϵ/2,𝔻n\)\)≤log⁡\(D⁡\(ϵn,𝔻n\)\)≤n​ϵn2\.\\displaystyle\\log\(D\(\\epsilon/2,\\mathbb\{D\}\_\{n\}\)\)\\leq\\log\(D\(\\epsilon\_\{n\},\\mathbb\{D\}\_\{n\}\)\)\\leq n\\epsilon\_\{n\}^\{2\}\.Thus by Lemma[B\.5](https://arxiv.org/html/2609.20883#A2.Thmtheorem5)usingD⁡\(ϵ\)=exp⁡\(n​ϵn2\)D\(\\epsilon\)=\\exp\(n\\epsilon\_\{n\}^\{2\}\)\(constant inϵ\\epsilon\),ϵ=M​ϵn\\epsilon=M\\epsilon\_\{n\}for large enoughM≥2M\\geq 2, andj=1j=1, there exists testsϕn\\phi\_\{n\}such that

𝔼π0⊗n​\[ϕn\]\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\phi\_\{n\}\]≤exp⁡\(n​ϵn2\)​exp⁡\(−Ctest​n​M2​ϵn2\)​11−exp⁡\(−Ctest​n​M2​ϵn2\)\\displaystyle\\leq\\exp\(n\\epsilon\_\{n\}^\{2\}\)\\exp\(\-C\_\{\\mathrm\{test\}\}nM^\{2\}\\epsilon\_\{n\}^\{2\}\)\\frac\{1\}\{1\-\\exp\(\-C\_\{\\mathrm\{test\}\}nM^\{2\}\\epsilon\_\{n\}^\{2\}\)\}supπ∈𝔻n,ρ⁡\(π,π0\)\>M​ϵn𝔼π⊗n​\[1−ϕn\]\\displaystyle\\sup\_\{\\pi\\in\\mathbb\{D\}\_\{n\},\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\mathbb\{E\}\_\{\\pi^\{\\otimes n\}\}\[1\-\\phi\_\{n\}\]≤exp⁡\(−Ctest​n​M2​ϵn2\)\.\\displaystyle\\leq\\exp\(\-C\_\{\\mathrm\{test\}\}nM^\{2\}\\epsilon\_\{n\}^\{2\}\)\.\(5\)
Now ifCtest​M2−1\>CtestC\_\{\\mathrm\{test\}\}M^\{2\}\-1\>C\_\{\\mathrm\{test\}\}, the first condition implies the following asymptotically asn→∞n\\rightarrow\\infty,

𝔼π0⊗n\[𝒫\(π:ρ\(π,π0\)\>Mϵn\|X1,…,Xn\)ϕn\]≤𝔼π0⊗n\[ϕn\]≤2exp\(−Ctestnϵn2\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\\phi\_\{n\}\]\\leq\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\phi\_\{n\}\]\\leq 2\\exp\(\-C\_\{\\mathrm\{test\}\}n\\epsilon\_\{n\}^\{2\}\)\.
Given the above bound, we now only need to upper bound𝔼π0⊗n\[𝒫\(π:ρ\(π,π0\)\>Mϵn\|X1,…,Xn\)\(1−ϕn\)\]\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\(1\-\\phi\_\{n\}\)\]to finish the proof\. We expand the expression𝒫\(π:ρ\(π,π0\)\>Mϵn\|X1,…,Xn\)\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)below:

𝒫\(π:ρ\(π,π0\)\>Mϵn\|X1,…,Xn\)\\displaystyle\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)=∫π:ρ⁡\(π,π0\)\>M​ϵn∏i=1nπ\(Xi\)d𝒫\(π\)∫∏i=1nπ⁡\(Xi\)​𝑑𝒫​\(π\)\\displaystyle=\\frac\{\\int\_\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\\pi\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\}\{\\int\\prod\_\{i=1\}^\{n\}\\pi\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\}=∫π:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)∫∏i=1n\(π/π0\)​\(Xi\)​𝑑𝒫​\(π\)\.\\displaystyle=\\frac\{\\int\_\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\}\{\\int\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\}\.
LetEnE\_\{n\}be the event that∫∏i=1n\(π/π0\)​\(Xi\)​𝑑𝒫​\(π\)≥exp⁡\(−\(2\+b\)​n​ϵn2\)\\int\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\geq\\exp\(\-\(2\+b\)n\\epsilon\_\{n\}^\{2\}\), which occurs with probability≥1−δn\\geq 1\-\\delta\_\{n\}by condition 3\. Thus, givenEnE\_\{n\}happens we can say the following,

𝒫\(π:ρ\(π,π0\)\>Mϵn\\displaystyle\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X1,…,Xn\)\\displaystyle\|X\_\{1\},\\ldots,X\_\{n\}\)≤exp\(\(2\+b\)nϵn2\)∫π:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)\\displaystyle\\leq\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\int\_\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)=exp\(\(2\+b\)nϵn2\)\[∫π∉𝔻n:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)\\displaystyle=\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\bigg\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\+∫π∈𝔻n:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)\]\\displaystyle\\quad\+\\int\_\{\\pi\\in\\mathbb\{D\}\_\{n\}:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\bigg\]≤exp\(\(2\+b\)nϵn2\)\[∫π∉𝔻n∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)\\displaystyle\\leq\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\bigg\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\+∫π∈𝔻n:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)\]\.\\displaystyle\\quad\+\\int\_\{\\pi\\in\\mathbb\{D\}\_\{n\}:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\bigg\]\.Substituting into the desired expectation bound,

𝔼\[𝒫\(π:ρ\(π,π0\)\>Mϵn\\displaystyle\\mathbb\{E\}\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X1,…,Xn\)\(1−ϕn\)\|En\]\\displaystyle\|X\_\{1\},\\ldots,X\_\{n\}\)\(1\-\\phi\_\{n\}\)\|E\_\{n\}\]≤exp\(\(2\+b\)nϵn2\)\[𝔼π0⊗n\[∫π∉𝔻n∏i=1n\(π/π0\)\(Xi\)\(1−ϕn\)d𝒫\(π\)\]\\displaystyle\\leq\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\bigg\[\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\(1\-\\phi\_\{n\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\]\+𝔼π0⊗n\[∫π∉𝔻n:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)\(1−ϕn\)d𝒫\(π\)\]\]\\displaystyle\\quad\+\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\(1\-\\phi\_\{n\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\]\\bigg\]≤exp\(\(2\+b\)nϵn2\)\[𝔼π0⊗n\[∫π∉𝔻n∏i=1n\(π/π0\)\(Xi\)d𝒫\(π\)\]\\displaystyle\\leq\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\bigg\[\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\]\+𝔼π0⊗n\[∫π∉𝔻n:ρ⁡\(π,π0\)\>M​ϵn∏i=1n\(π/π0\)\(Xi\)\(1−ϕn\)d𝒫\(π\)\]\]\\displaystyle\\quad\+\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\\prod\_\{i=1\}^\{n\}\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\(1\-\\phi\_\{n\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\]\\bigg\]≤exp\(\(2\+b\)nϵn2\)\[∫π∉𝔻n1d𝒫\(π\)\\displaystyle\\leq\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\bigg\[\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}\}1\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\+∫π∉𝔻n:ρ⁡\(π,π0\)\>M​ϵn\(1−ϕn\)d𝒫\(π\)\]\.\\displaystyle\\quad\+\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\}\(1\-\\phi\_\{n\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\bigg\]\.
In the last step above we invoke Fubini’s theorem to swap the integrals and then note that𝔼π0⊗n​\[∏\(π/π0\)​\(Xi\)\]≤1\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\]\\leq 1\. Both the terms of the obtained inequality are now easy to bound using Equation[5](https://arxiv.org/html/2609.20883#A2.E5)for the second term, and condition 2 for the first term since∫π∉𝔻n1​𝑑𝒫​\(π\)=𝒫⁡\(𝔻/𝔻n\)\\int\_\{\\pi\\notin\\mathbb\{D\}\_\{n\}\}1\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)=\\mathcal\{P\}\(\\mathbb\{D\}/\\mathbb\{D\}\_\{n\}\)\. We finish the proof by noting that𝔼\[𝒫\(π:ρ\(π,π0\)\>Mϵn\|X1,…,Xn\)\(1−ϕn\)\|Enc\]Pr\(Enc\)≤Pr\(Enc\)≤δn\\mathbb\{E\}\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\(1\-\\phi\_\{n\}\)\|E\_\{n\}^\{c\}\]Pr\(E\_\{n\}^\{c\}\)\\leq Pr\(E\_\{n\}^\{c\}\)\\leq\\delta\_\{n\}\. ∎

Note that forδn→0\\delta\_\{n\}\\rightarrow 0and large enoughMM, the above bound directly implies that the posterior contracts at a rateϵn\\epsilon\_\{n\}\. The following Lemma allows us to showδn→0\\delta\_\{n\}\\rightarrow 0for a set of distributions that are close in Hellinger distance\. First, we remind the reader that the Hellinger distance between distributionsπ1,π2\\pi\_\{1\},\\pi\_\{2\}with pdfs written asπ1\(\.\),π2\(\.\)\\pi\_\{1\}\(\.\),\\pi\_\{2\}\(\.\)respectively is defined as\[[Wainwright, 2019](https://arxiv.org/html/2609.20883#bib.bib5)\]:

h2​\(π1,π2\)\\displaystyle h^\{2\}\(\\pi\_\{1\},\\pi\_\{2\}\)=∫\(π1​\(x\)−π2​\(x\)\)2​𝑑x\.\\displaystyle=\\int\\left\(\\sqrt\{\\pi\_\{1\}\(x\)\}\-\\sqrt\{\\pi\_\{2\}\(x\)\}\\right\)^\{2\}\\mathrm\{d\}x\.The Hellinger distance is closely related to the TV distance as follows:

12​h2​\(π1,π2\)≤ρT​V​\(π1,π2\)≤h⁡\(π1,π2\)​1−h2​\(π1,π2\)4\.\\displaystyle\\frac\{1\}\{2\}h^\{2\}\(\\pi\_\{1\},\\pi\_\{2\}\)\\leq\\rho\_\{TV\}\(\\pi\_\{1\},\\pi\_\{2\}\)\\leq h\(\\pi\_\{1\},\\pi\_\{2\}\)\\sqrt\{1\-\\frac\{h^\{2\}\(\\pi\_\{1\},\\pi\_\{2\}\)\}\{4\}\}\.\(6\)
###### Lemma B\.7\(Lemma 8\.4 in[Ghosal et al\. \[2000\]](https://arxiv.org/html/2609.20883#bib.bib30)\)\.

For everyϵ\>0\\epsilon\>0and distribution𝒫\\mathcal\{P\}on the set𝔻=\{π:h2​\(π,π0\)​‖π0/π‖∞≤ϵ2\}\\mathbb\{D\}=\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\\|\\pi\_\{0\}/\\pi\\\|\_\{\\infty\}\\leq\\epsilon^\{2\}\\\}, we have, for a universal constantChellinger\>0C\_\{\\mathrm\{hellinger\}\}\>0,

P​rX1,…,Xn∼π0​\(∫∏⁡\(π/π0\)​\(Xi\)​𝑑𝒫​\(π\)≤exp⁡\(−3​n​ϵ2\)\)≤exp⁡\(−Chellinger​n​ϵ2\)\.\\displaystyle Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\left\(\\int\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\leq\\exp\(\-3n\\epsilon^\{2\}\)\\right\)\\leq\\exp\(\-C\_\{\\mathrm\{hellinger\}\}n\\epsilon^\{2\}\)\.

### B\.3Proof of Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)

We now prove our main upper bound that assumes that the likelihood ratio between any two distributions is bounded by a constantbl​rb\_\{lr\}\. Note that our asymptotic bound does not depend on the value ofbl​rb\_\{lr\}and only on its finiteness\.

###### Theorem B\.8\(Restated Theorem[5\.2](https://arxiv.org/html/2609.20883#S5.Thmtheorem2)\)\.

Consider akk\-sparse prior in the total variation distanceρT​V\\rho\_\{TV\}over a set of distributions𝔻\\mathbb\{D\}such that the likelihood ratio between any two distributions is bounded\. That is,‖π1/π2‖∞≤bl​r​∀π1,π2∈𝔻\\\|\\pi\_\{1\}/\\pi\_\{2\}\\\|\_\{\\infty\}\\leq b\_\{lr\}\\;\\forall\\pi\_\{1\},\\pi\_\{2\}\\in\\mathbb\{D\}, for some constantbl​r\>0b\_\{lr\}\>0\. Then, there exists an estimator such that the Bayes’ risk is upper bounded in the total variation distance forn=ω⁡\(bl​r\)n=\\omega\(b\_\{lr\}\)as follows:

𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]=O⁡\(k​log⁡nn\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\\right\)\.

###### Proof\.

We will shorthandρT​V\\rho\_\{TV\}forρ\\rhoin this proof for notational convenience\. LetE⁡\(n,ϵn,b1\)E\(n,\\epsilon\_\{n\},b\_\{1\}\)be the event𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\>exp\(−b1nϵn2\)\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\>\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)for someϵn\\epsilon\_\{n\}chosen such thatn​ϵn2→∞n\\epsilon\_\{n\}^\{2\}\\rightarrow\\inftyasn→∞n\\rightarrow\\inftyand constantb1\>0b\_\{1\}\>0\. That is,E\(\.\)E\(\.\)represents the event that the posterior mass outside of anϵn\\epsilon\_\{n\}ball around the true distribution sampled from𝒫\\mathcal\{P\}is greater thanexp⁡\(−b1​n​ϵn2\)\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\. We will first argue that wheneverE\(\.\)E\(\.\)fails, there is a significant posterior probability around the true distribution, and hence we can identify a distribution close to the true distribution easily\. We will then argue that the probability ofE\(\.\)E\(\.\)goes to00fast asnnincreases\. Formally, we first decompose the required bound as follows, whereE\(\.\)cE\(\.\)^\{c\}is the complement of the eventE\(\.\)E\(\.\):

𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]≤P​r​\(E⁡\(n,ϵn,b1\)\)⋅𝔼⁡\[ρ⁡\(π0,π^n\)\|E⁡\(n,ϵn,b1\)\]\\displaystyle\\leq Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\)\\cdot\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)\]\+Pr\(E\(n,ϵn,b1\)c\)⋅𝔼\[ρ\(π0,π^n\)\|E\(n,ϵn,b1\)c\]\.\\displaystyle\\quad\+Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\)\\cdot\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\]\.\(7\)
We defineπ^n=arg​maxπ⁡𝒫​\(\{π′:ρ⁡\(π′,π\)≤ϵn\}\|X1,…,Xn\)\\hat\{\\pi\}\_\{n\}=\\argmax\_\{\\pi\}\\mathcal\{P\}\(\\\{\\pi^\{\\prime\}:\\rho\(\\pi^\{\\prime\},\\pi\)\\leq\\epsilon\_\{n\}\\\}\|X\_\{1\},\\ldots,X\_\{n\}\)as the center of theϵn\\epsilon\_\{n\}ball with highest posterior probability\. ConsiderE​\(n,ϵn,b1\)cE\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}so that𝒫\(\{π:ρ\(π,π0\)≤ϵn\|X1,…,Xn\}\)\>1−exp\(−b1nϵn2\)\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\>1\-\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\), and further assume thatρ⁡\(π0,π^n\)\>2​ϵn\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\>2\\epsilon\_\{n\}such that theϵn\\epsilon\_\{n\}\-posterior balls aroundπ0\\pi\_\{0\}andπ^n\\hat\{\\pi\}\_\{n\}are disjoint\. By definition ofπ^n\\hat\{\\pi\}\_\{n\},𝒫\(\{π:ρ\(π,π^n\)≤ϵn\|X1,…,Xn\}\)≥𝒫\(\{π:ρ\(π,π0\)≤ϵn\|X1,…,Xn\}\)\>1−exp\(−b1nϵn2\)\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\hat\{\\pi\}\_\{n\}\)\\leq\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\\geq\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\>1\-\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\. Now, sincen​ϵn2→∞n\\epsilon\_\{n\}^\{2\}\\rightarrow\\infty,∃n1\>0\\exists n\_\{1\}\>0such that for everyn\>n1n\>n\_\{1\},𝒫\(\{π:ρ\(π,π^n\)≤ϵn\|X1,…,Xn\}\)\+𝒫\(\{π:ρ\(π,π0\)≤ϵn\|X1,…,Xn\}\)\>1\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\hat\{\\pi\}\_\{n\}\)\\leq\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\+\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\>1, which is not possible if the balls are disjoint\. In other words, for everyn\>n1n\>n\_\{1\},E​\(n,ϵn,b1\)c⟹ρ⁡\(π0,π^n\)≤2​ϵnE\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\\implies\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\\leq 2\\epsilon\_\{n\}\. We thus simplify the second term of Equation[7](https://arxiv.org/html/2609.20883#A2.E7)as follows:

P​r​\(E​\(n,ϵn,b1\)c\)⋅𝔼⁡\[ρ⁡\(π0,π^n\)\|E​\(n,ϵn,b1\)c\]\\displaystyle Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\)\\cdot\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\]≤𝔼⁡\[ρ⁡\(π0,π^n\)\|E​\(n,ϵn,b1\)c\]=O⁡\(ϵn\)\.\\displaystyle\\leq\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,\\epsilon\_\{n\},b\_\{1\}\)^\{c\}\]=O\(\\epsilon\_\{n\}\)\.
It remains to bound the first term of Equation[7](https://arxiv.org/html/2609.20883#A2.E7)\. To do so, we first note that TV distance is bounded by 1 so thatρT​V\(\.,\.\)≤1\\rho\_\{TV\}\(\.,\.\)\\leq 1\. Further note from Markov’s inequality that for any non\-negative random variableVVand thresholdt\>0t\>0,P​r​\(V\>t\)≤𝔼⁡\[V\]/tPr\(V\>t\)\\leq\\mathbb\{E\}\[V\]/t\. Thus,

Pr\(E\(n,ϵn,b1\)\)⋅𝔼\[ρ\(π0,π^n\)\|E\(n,\\displaystyle Pr\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\)\\cdot\\mathbb\{E\}\[\\rho\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\|E\(n,ϵn,b1\)\]≤Prπ0∼𝒫,X1,…,Xn∼π0\(E\(n,ϵn,b1\)\)\\displaystyle\\epsilon\_\{n\},b\_\{1\}\)\]\\leq Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\},X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\)=𝔼π0∼𝒫​\[P​rX1,…,Xn∼π0​\(E⁡\(n,ϵn,b1\)\|π0\)\]\\displaystyle=\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\(E\(n,\\epsilon\_\{n\},b\_\{1\}\)\|\\pi\_\{0\}\)\]≤𝔼π0∼𝒫\[𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]exp⁡\(−b1​n​ϵn2\)\]\.\\displaystyle\\leq\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\\left\[\\frac\{\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\}\{\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\}\\right\]\.
Looking at the result of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6), we know we can get a bound of the sort𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]≤5exp\(−b2nϵn2\)\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\\leq 5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)for someb2\>0b\_\{2\}\>0forπ0\\pi\_\{0\}that satisfies the conditions of the Lemma\. LetPrπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]\>5exp\(−b2nϵn2\)\)≤exp\(−b3nϵn2\)Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\>5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\leq\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)for someb3\>0b\_\{3\}\>0so that mostπ0\\pi\_\{0\}satisfy the conditions of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)at any givennn\. Since the posterior probability of any region is at most 1, this allows us to decompose the above expression:

𝔼π0∼𝒫\[𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]exp⁡\(−b1​n​ϵn2\)\]\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\\left\[\\frac\{\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\}\{\\exp\(\-b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\}\\right\]≤exp\(b1nϵn2\)\(Prπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]\>5exp\(−b2nϵn2\)\)⋅1\\displaystyle\\leq\\exp\(b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\(Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\>5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\cdot 1\+Prπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]≤5exp\(−b2nϵn2\)\)⋅5exp\(−b2nϵn2\)\)\\displaystyle\\;\+Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\\leq 5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\cdot 5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)≤exp⁡\(b1​n​ϵn2\)​\(exp⁡\(−b3​n​ϵn2\)\+5​exp⁡\(−b2​n​ϵn2\)\)\.\\displaystyle\\leq\\exp\(b\_\{1\}n\\epsilon\_\{n\}^\{2\}\)\(\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)\+5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\.
The above expression isO⁡\(ϵn\)O\(\\epsilon\_\{n\}\)ifb2,b3\>b1b\_\{2\},b\_\{3\}\>b\_\{1\}andexp⁡\(−b′​n​ϵn2\)=O⁡\(ϵn\)\\exp\(\-b^\{\\prime\}n\\epsilon\_\{n\}^\{2\}\)=O\(\\epsilon\_\{n\}\)for anyb′\>0b^\{\\prime\}\>0\. This argument thus shows the required bound if the following conditions are satisfied:

1. 1\.The contraction rateϵn\\epsilon\_\{n\}satisfiesn​ϵn2→∞n\\epsilon\_\{n\}^\{2\}\\rightarrow\\inftyasn→∞n\\rightarrow\\inftyandexp⁡\(−b′​n​ϵn2\)=O⁡\(ϵn\)\\exp\(\-b^\{\\prime\}n\\epsilon\_\{n\}^\{2\}\)=O\(\\epsilon\_\{n\}\)for anyb′\>0b^\{\\prime\}\>0\.
2. 2\.For someb2,b3\>0b\_\{2\},b\_\{3\}\>0, Prπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]\>5exp\(−b2nϵn2\)\)≤exp\(−b3nϵn2\)\.\\displaystyle Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\>5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\leq\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)\.Further there is ab1∈\(0,min⁡\(b2,b3\)\)b\_\{1\}\\in\(0,\\min\(b\_\{2\},b\_\{3\}\)\)\.

Note that the condition onb1b\_\{1\}is trivially satisfied\. Further, note that there existn2,k2\>0n\_\{2\},k\_\{2\}\>0such that for alln\>n2,k\>k2n\>n\_\{2\},k\>k\_\{2\}and constantb4\>0b\_\{4\}\>0,n−b′​b42​k≤b4​k​log⁡nnn^\{\-b^\{\\prime\}b\_\{4\}^\{2\}k\}\\leq b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\. Thus the contraction rateϵn=b4​k​log⁡nn\\epsilon\_\{n\}=b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}for some constantb4\>0b\_\{4\}\>0as required in the Theorem statement satisfies the first condition\. It remains to show that there areb2,b3\>0b\_\{2\},b\_\{3\}\>0for whichPrπ0∼𝒫\(𝔼\[𝒫\(\{π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\}\)\|π0\]\>5exp\(−b2nϵn2\)\)≤exp\(−b3nϵn2\)Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\\\}\)\|\\pi\_\{0\}\]\>5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\leq\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)\. As noted before, we show this using Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)in the asymptotic limit, where we bound probability under the prior𝒫\\mathcal\{P\}that the sampled distribution doesn’t satisfy the conditions 1\-3 of the Lemma for big enoughnn\. Conditions 1\-2 in the Lemma do not depend on the prior or the sampledπ0\\pi\_\{0\}, and only require a bound on the packing number of a significant fraction of the support space\.

1. 1\.Proving conditions 1\-2 of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)for any constantb\>0b\>0andϵn=b4​k​log⁡nn\\epsilon\_\{n\}=b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}: We need to bound theϵn\\epsilon\_\{n\}packing number for some subset𝔻n\\mathbb\{D\}\_\{n\}\. First, note thatdiam⁡\(𝔻\)≤1\\mathrm\{diam\}\(\\mathbb\{D\}\)\\leq 1since the total variation distance between any two distributions is at most 1\. LetR=1R=1andr=ϵn/2r=\\epsilon\_\{n\}/2in Theorem[3\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem2)and for someb\>0b\>0, letδ=1−exp⁡\(−\(b\+4\)​n​ϵn2\)\\delta=1\-\\exp\(\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\)so thatlog⁡\(1−δ\)=−\(b\+4\)​n​ϵn2\\log\(1\-\\delta\)=\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\. Theorem[3\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem2)further requires thatr<c​Rr<cR, which is true without loss of generality, since otherwise we can replacerrwithc​RcRwithout changing our conclusions\. Thus, forN=⌈−\(b\+4\)​n​ϵn2log⁡\(1−c​\(ϵn/2\)k\)⌉N=\\left\\lceil\\frac\{\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\}\{\\log\(1\-c\(\\epsilon\_\{n\}/2\)^\{k\}\)\}\\right\\rceil, Theorem[3\.2](https://arxiv.org/html/2609.20883#S3.Thmtheorem2)implies that condition 1 is satisfied iflog⁡\(D⁡\(ϵn,𝔻n\)\)≤log⁡\(N⁡\(ϵn/2,𝔻n\)\)=log⁡N≤n​ϵn2\\log\(D\(\\epsilon\_\{n\},\\mathbb\{D\}\_\{n\}\)\)\\leq\\log\(N\(\\epsilon\_\{n\}/2,\\mathbb\{D\}\_\{n\}\)\)=\\log N\\leq n\\epsilon\_\{n\}^\{2\}\. This is trivially satisfied ifN=1N=1, so assumeN\>1N\>1such thatN≤2​−\(b\+4\)​n​ϵn2log⁡\(1−c​\(ϵn/2\)k\)N\\leq 2\\frac\{\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\}\{\\log\(1\-c\(\\epsilon\_\{n\}/2\)^\{k\}\)\}\. We haveϵn=b4​k​log⁡nn\\epsilon\_\{n\}=b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}and use the inequality\(−1/log\(1−x\)\)≤1/x\(\-1/\\log\(1\-x\)\)\\leq 1/xto derive sufficient conditions forlog⁡N≤n​ϵn2\\log N\\leq n\\epsilon\_\{n\}^\{2\}\. Below we show that that this satisfied asymptotically inn,kn,kfor anyb\>0b\>0andb4\>1/2b\_\{4\}\>1/\\sqrt\{2\}: n​ϵn2\\displaystyle n\\epsilon\_\{n\}^\{2\}≥log⁡N⟸n​ϵn2≥log⁡\(2​−\(b\+4\)​n​ϵn2log⁡\(1−c​\(ϵn/2\)k\)\)\\displaystyle\\geq\\log N\\impliedby n\\epsilon\_\{n\}^\{2\}\\geq\\log\\Biggl\(2\\frac\{\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\}\{\\log\(1\-c\(\\epsilon\_\{n\}/2\)^\{k\}\)\}\\Biggr\)⇔b42​k​log⁡n≥log⁡\(2​−b42​\(b\+4\)​k​log⁡nlog⁡\(1−c​\(ϵn/2\)k\)\)\\displaystyle\\iff b\_\{4\}^\{2\}k\\log n\\geq\\log\\Biggl\(2\\frac\{\-b\_\{4\}^\{2\}\(b\+4\)k\\log n\}\{\\log\(1\-c\(\\epsilon\_\{n\}/2\)^\{k\}\)\}\\Biggr\)⇔b42​k​log⁡n≥log⁡\(k​log⁡n\)\+log⁡\(2​b42​\(b\+4\)\)\+log⁡\(−1log⁡\(1−c​\(ϵn/2\)k\)\)\\displaystyle\\iff\\begin\{aligned\} b\_\{4\}^\{2\}k\\log n\\geq\\;&\\log\(k\\log n\)\+\\log\\\!\\bigl\(2b\_\{4\}^\{2\}\(b\+4\)\\bigr\)\+\\log\\\!\\left\(\-\\frac\{1\}\{\\log\(1\-c\(\\epsilon\_\{n\}/2\)^\{k\}\)\}\\right\)\\end\{aligned\}⟸b42​k​log⁡n≥log⁡\(k​log⁡n\)\+log⁡\(2​b42​\(b\+4\)\)\+log⁡\(1c​\(ϵn/2\)k\)\\displaystyle\\impliedby\\begin\{aligned\} b\_\{4\}^\{2\}k\\log n\\geq\\;&\\log\(k\\log n\)\+\\log\\\!\\bigl\(2b\_\{4\}^\{2\}\(b\+4\)\\bigr\)\+\\log\\\!\\left\(\\frac\{1\}\{c\(\\epsilon\_\{n\}/2\)^\{k\}\}\\right\)\\end\{aligned\}⇔b42​k​log⁡n≥log⁡\(k​log⁡n\)\+log⁡\(2​b42​\(b\+4\)c\)\+k​log⁡\(2ϵn\)\\displaystyle\\iff b\_\{4\}^\{2\}k\\log n\\geq\\log\(k\\log n\)\+\\log\\\!\\left\(\\frac\{2b\_\{4\}^\{2\}\(b\+4\)\}\{c\}\\right\)\+k\\log\\\!\\left\(\\frac\{2\}\{\\epsilon\_\{n\}\}\\right\)⇔b42​k​log⁡n≥log⁡\(k​log⁡n\)\+log⁡\(2​b42​\(b\+4\)c\)\+k2​log​n−k2​log⁡\(k​log​n\)\+k​log⁡\(2b4\)\\displaystyle\\iff\\begin\{aligned\} b\_\{4\}^\{2\}k\\log n\\geq\\;&\\log\(k\\log n\)\+\\log\\\!\\left\(\\frac\{2b\_\{4\}^\{2\}\(b\+4\)\}\{c\}\\right\)\+\\frac\{k\}\{2\}\\log n\-\\frac\{k\}\{2\}\\log\(k\\log n\)\\\\ &\\qquad\\qquad\\qquad\+k\\log\\\!\\left\(\\frac\{2\}\{b\_\{4\}\}\\right\)\\end\{aligned\}⇔log⁡\(2​b42​\(b\+4\)c\)≤k⁡\(b42−12\)​log⁡n\+\(k2−1\)​log⁡\(k​log⁡n\)−k​log⁡\(2b4\)\.\\displaystyle\\iff\\begin\{aligned\} \\log\\\!\\left\(\\frac\{2b\_\{4\}^\{2\}\(b\+4\)\}\{c\}\\right\)\\leq\\;&k\\left\(b\_\{4\}^\{2\}\-\\frac\{1\}\{2\}\\right\)\\log n\+\\left\(\\frac\{k\}\{2\}\-1\\right\)\\log\(k\\log n\)\\\\ &\\qquad\-k\\log\\\!\\left\(\\frac\{2\}\{b\_\{4\}\}\\right\)\.\\end\{aligned\} We obtain that the condition 1 is satisfied asymptotically inn,kn,kfor anyb\>0b\>0andb4\>1/2b\_\{4\}\>1/\\sqrt\{2\}\. Thus forb\>0,b4\>1/2b\>0,b\_\{4\}\>1/\\sqrt\{2\}andϵn=b4​k​log⁡nn\\epsilon\_\{n\}=b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\},∃n3,k3\>0\\exists n\_\{3\},k\_\{3\}\>0such that forn\>n3,k\>k3n\>n\_\{3\},k\>k\_\{3\},log⁡\(D⁡\(ϵn,𝔻n\)\)≤n​ϵn2\\log\(D\(\\epsilon\_\{n\},\\mathbb\{D\}\_\{n\}\)\)\\leq n\\epsilon\_\{n\}^\{2\}and𝒫⁡\(𝔻/𝔻n\)≤exp⁡\(−n​ϵn2​\(b\+4\)\)\\mathcal\{P\}\(\\mathbb\{D\}/\\mathbb\{D\}\_\{n\}\)\\leq\\exp\(\-n\\epsilon\_\{n\}^\{2\}\(b\+4\)\)\.
2. 2\.Establishing a sufficient condition for condition 3 of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)ifb<1b<1: The final condition of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)may not be satisfied uniformly for every choice ofπ0∈𝔻\\pi\_\{0\}\\in\\mathbb\{D\}from our assumptions\. Instead, we calculate the probability under the prior𝒫\\mathcal\{P\}that condition 3 is satisfied forπ0∼𝒫\\pi\_\{0\}\\sim\\mathcal\{P\}\. We re\-write condition 3 as follows: 1−δn\\displaystyle 1\-\\delta\_\{n\}≤P​rX1,…,Xn∼π0​\(∫∏⁡\(π/π0\)​\(Xi\)​𝑑𝒫​\(π\)≥exp⁡\(−\(2\+b\)​n​ϵn2\)\)\\displaystyle\\leq Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\left\(\\int\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\geq\\exp\(\-\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\right\)⟸1−δn\\displaystyle\\impliedby 1\-\\delta\_\{n\}≤PrX1,…,Xn∼π0\(∫\{π:h2​\(π,π0\)​‖π0/π‖∞≤ϵn2\}∏\(π/π0\)\(Xi\)​d​𝒫​\(π\)OPEN≥exp⁡\(−\(2\+b\)​n​ϵn2\)\)\\displaystyle\\leq\\begin\{aligned\} Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\Biggl\(\\int\_\{\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\\|\\pi\_\{0\}/\\pi\\\|\_\{\\infty\}\\leq\\epsilon\_\{n\}^\{2\}\\\}\}\\prod\(\\pi/\\pi\_\{0\}\)&\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\\\ &\\geq\\exp\(\-\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\Biggr\)\\end\{aligned\}⟸1−δn\\displaystyle\\impliedby 1\-\\delta\_\{n\}≤PrX1,…,Xn∼π0\(∫\{π:h2​\(π,π0\)≤ϵn2/bl​r\}∏\(π/π0\)\(Xi\)​d​𝒫​\(π\)OPEN≥exp⁡\(−\(2\+b\)​n​ϵn2\)\)\.\\displaystyle\\leq\\begin\{aligned\} Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\Biggl\(\\int\_\{\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\}\\prod\(\\pi/\\pi\_\{0\}\)&\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\\\ &\\geq\\exp\(\-\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\Biggr\)\.\\end\{aligned\} Note that Lemma[B\.7](https://arxiv.org/html/2609.20883#A2.Thmtheorem7)implies that: exp⁡\(−CLOSE\\displaystyle\\exp\(\-OPENChellinger​n​ϵn2\)\\displaystyle C\_\{\\mathrm\{hellinger\}\}n\\epsilon\_\{n\}^\{2\}\)≥PrX1,…,Xn∼π0\(𝒫\(\{π:h2\(π,π0\)≤ϵn2/bl​r\}\)−1∫\{π:h2​\(π,π0\)≤ϵn2/bl​r\}∏\(π/π0\)\(Xi\)d𝒫\(π\)≤exp\(−3nϵn2\)\)\\displaystyle\\geq\\begin\{aligned\} Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\Biggl\(\\mathcal\{P\}\(\\\{\\pi:&h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\)^\{\-1\}\\\\ &\\int\_\{\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\}\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\leq\\exp\(\-3n\\epsilon\_\{n\}^\{2\}\)\\Biggr\)\\end\{aligned\}=PrX1,…,Xn∼π0\(∫\{π:h2​\(π,π0\)≤ϵn2/bl​r\}∏\(π/π0\)​\(Xi\)​d​𝒫​\(π\)OPEN≤𝒫⁡\(\{π:h2​\(π,π0\)≤ϵn2/bl​r\}\)​exp⁡\(−3​n​ϵn2\)\),\\displaystyle=\\begin\{aligned\} Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\Biggl\(\\int\_\{\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\}&\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\\\ &\\leq\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\)\\exp\(\-3n\\epsilon\_\{n\}^\{2\}\)\\Biggr\),\\end\{aligned\}for the universal constantChellinger\>0C\_\{\\mathrm\{hellinger\}\}\>0\. Now, if 𝒫⁡\(\{π:h2​\(π,π0\)≤ϵn2/bl​r\}\)≥exp⁡\(−\(1−b\)​n​ϵn2\)\\displaystyle\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}\)andb<1b<1, then we have PrX1,…,Xn∼π0\(∫\{π:h2​\(π,π0\)≤ϵn2/bl​r\}∏\(π/π0\)\(Xi\)\\displaystyle Pr\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\\Biggl\(\\int\_\{\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\}\\prod\(\\pi/\\pi\_\{0\}\)\(X\_\{i\}\)OPENd​𝒫​\(π\)≤exp⁡\(−\(2\+b\)​n​ϵn2\)\)\\displaystyle\\mathrm\{d\}\\mathcal\{P\}\(\\pi\)\\leq\\exp\(\-\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\\Biggr\)≤exp⁡\(−Chellinger​n​ϵn2\),\\displaystyle\\leq\\exp\(\-C\_\{\\mathrm\{hellinger\}\}n\\epsilon\_\{n\}^\{2\}\),which satisfies condition 3 of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)forδn=exp⁡\(−Chellinger​n​ϵn2\)\\delta\_\{n\}=\\exp\(\-C\_\{\\mathrm\{hellinger\}\}n\\epsilon\_\{n\}^\{2\}\)\.
3. 3\.Sufficient conditions for invoking Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)occur with high probability: Combining the above sufficient condition for Condition 3 of Lemma[B\.6](https://arxiv.org/html/2609.20883#A2.Thmtheorem6)along with our proof for Conditions 1\-2, we get that for anyb∈\(0,1\)b\\in\(0,1\), there existn4,k4,M′\>0n\_\{4\},k\_\{4\},M^\{\\prime\}\>0such that forn\>n4,k\>k4,M\>M′n\>n\_\{4\},k\>k\_\{4\},M\>M^\{\\prime\}, 𝒫\(\{π:h2\(π,π0\)\\displaystyle\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)≤ϵn2/bl​r\}\)≥exp\(−\(1−b\)nϵn2\)⟹\\displaystyle\\leq\\epsilon\_\{n\}^\{2\}/b\_\{lr\}\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}\)\\implies𝔼π0⊗n\[𝒫\(π:ρ\(\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\[\\mathcal\{P\}\(\\pi:\\rho\(π,π0\)\>Mϵn\|X1,…,Xn\)\]≤2exp\(−Ctestnϵn2\)\+exp\(−Chellingernϵn2\)\\displaystyle\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\]\\leq 2\\exp\(\-C\_\{\\mathrm\{test\}\}n\\epsilon\_\{n\}^\{2\}\)\+\\exp\(\-C\_\{\\mathrm\{hellinger\}\}n\\epsilon\_\{n\}^\{2\}\)\+exp⁡\(\(2\+b\)​n​ϵn2\)​\(exp⁡\(−\(b\+4\)​n​ϵn2\)\+exp⁡\(−Ctest​n​M2​ϵn2\)\)\.\\displaystyle\+\\exp\(\(2\+b\)n\\epsilon\_\{n\}^\{2\}\)\(\\exp\(\-\(b\+4\)n\\epsilon\_\{n\}^\{2\}\)\+\\exp\(\-C\_\{\\mathrm\{test\}\}nM^\{2\}\\epsilon\_\{n\}^\{2\}\)\)\. Further, ifCtest​M2\>\(2\+b\)C\_\{\\mathrm\{test\}\}M^\{2\}\>\(2\+b\), then there is ab2′\>0b\_\{2\}^\{\\prime\}\>0such that asymptotically, 𝒫\(\{π:h2\(π,π0\)≤ϵn2\\displaystyle\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/bl​r\}\)≥exp\(−\(1−b\)nϵn2\)⟹\\displaystyle/b\_\{lr\}\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}\)\\implies𝔼π0⊗n\[𝒫\(π:ρ\(π,π0\)\>Mϵn\|X1,…,Xn\)\]≤5exp\(−b2′nϵn2\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\\left\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>M\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\\right\]\\leq 5\\exp\(\-b\_\{2\}^\{\\prime\}n\\epsilon\_\{n\}^\{2\}\)\.We recall that our proof for Conditions 1\-2 requires thatϵn=b4​k​log⁡nn\\epsilon\_\{n\}=b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}forb4\>1/2b\_\{4\}\>1/\\sqrt\{2\}\. For anyb∈\(0,1\)b\\in\(0,1\), as long asCtest​M2\>\(2\+b\)C\_\{\\mathrm\{test\}\}M^\{2\}\>\(2\+b\), we can chooseb4\>M/2b\_\{4\}\>M/\\sqrt\{2\}which allows us to replaceϵn\\epsilon\_\{n\}in the above equation withϵn/M\\epsilon\_\{n\}/Mto obtain that there is ab2\>0b\_\{2\}\>0such that asymptotically, 𝒫\(\{π:h2\(π,π0\)≤ϵn2\\displaystyle\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(M2bl​r\)\}\)≥exp\(−\(1−b\)nϵn2/M2\)⟹\\displaystyle/\(M^\{2\}b\_\{lr\}\)\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)\\implies𝔼π0⊗n\[𝒫\(π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\)\]≤5exp\(−b2nϵn2\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\\left\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\\right\]\\leq 5\\exp\(\-b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\.\(8\) We are interested in bounding the probability with which this happens, thus we want to findPrπ0∼𝒫\[𝒫\(\{π:h2\(π,π0\)≤ϵn2/\(M2bl​r\)\}\)≥exp\(−\(1−b\)nϵn2/M2\)\)\]Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(M^\{2\}b\_\{lr\}\)\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)\)\]for a large enoughMM\. Now sinceh2​\(π,π′\)≤2​ρT​V​\(π,π′\)h^\{2\}\(\\pi,\\pi^\{\\prime\}\)\\leq 2\\rho\_\{TV\}\(\\pi,\\pi^\{\\prime\}\)by Equation[6](https://arxiv.org/html/2609.20883#A2.E6),𝒫\(\{π:ρT​V\(π,π0\)≤ϵn2/\(2M2bl​r\)\}\)≥exp\(−\(1−b\)nϵn2/M2\)\\mathcal\{P\}\(\\\{\\pi:\\rho\_\{TV\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)implies𝒫\(\{π:h2\(π,π0\)≤ϵn2/\(M2bl​r\)\}\)≥exp\(−\(1−b\)nϵn2/M2\)\)\\mathcal\{P\}\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(M^\{2\}b\_\{lr\}\)\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)\)\. Thus, Prπ0∼𝒫\[𝒫\\displaystyle Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathcal\{P\}\(\{π:h2\(π,π0\)≤ϵn2/\(M2bl​r\)\}\)≥exp\(−\(1−b\)nϵn2/M2\)\)\]\\displaystyle\(\\\{\\pi:h^\{2\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(M^\{2\}b\_\{lr\}\)\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)\)\]≥Prπ0∼𝒫\[𝒫\(\{π:ρT​V\(π,π0\)≤ϵn2/\(2M2bl​r\)\}\)≥exp\(−\(1−b\)nϵn2/M2\)\)\],\\displaystyle\\geq Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathcal\{P\}\(\\\{\\pi:\\rho\_\{TV\}\(\\pi,\\pi\_\{0\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\\\}\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)\)\],and we can focus on the latter expression\. To bound the above expression, we use a similar argument as used in the proof of conditions 1\-2 and consider sets𝔸1,𝔸2,…\\mathbb\{A\}\_\{1\},\\mathbb\{A\}\_\{2\},\\ldotsdefined similarly\. Let𝔸0=𝔻\\mathbb\{A\}\_\{0\}=\\mathbb\{D\}and𝔸i\+1⊆𝔻/\(⋃j=1i𝔸j\)\\mathbb\{A\}\_\{i\+1\}\\subseteq\\mathbb\{D\}/\(\\bigcup\_\{j=1\}^\{i\}\\mathbb\{A\}\_\{j\}\)be the highest measure set that satisfies diam⁡\(𝔸i\+1\)≤ϵn2/\(2​M2​bl​r\)​diam​\(𝔸i\)≤ϵn2/\(2​M2​bl​r\)\.\\displaystyle\\mathrm\{diam\}\(\\mathbb\{A\}\_\{i\+1\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\\mathrm\{diam\}\(\\mathbb\{A\}\_\{i\}\)\\leq\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\.By definition,𝒫⁡\(𝔸1\)≥𝒫⁡\(𝔸2\)​…\\mathcal\{P\}\(\\mathbb\{A\}\_\{1\}\)\\geq\\mathcal\{P\}\(\\mathbb\{A\}\_\{2\}\)\\ldotsand let𝒫⁡\(𝔸Nδ\)≥δ​c​\(ϵn2/\(2​M2​bl​r\)\)k≥𝒫⁡\(𝔸Nδ\+1\)\\mathcal\{P\}\(\\mathbb\{A\}\_\{N^\{\\delta\}\}\)\\geq\\delta c\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}\\geq\\mathcal\{P\}\(\\mathbb\{A\}\_\{N^\{\\delta\}\+1\}\)for someδ∈\(0,1\)\\delta\\in\(0,1\)\. Note thatNδ≥1N^\{\\delta\}\\geq 1since𝒫⁡\(𝔸1\)≥c​\(ϵ2/\(2​M2​bl​r\)\)k\\mathcal\{P\}\(\\mathbb\{A\}\_\{1\}\)\\geq c\(\\epsilon^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}and further that such anNδN^\{\\delta\}exists due to the disjointness of the sets𝔸i\\mathbb\{A\}\_\{i\}and since the total probability is 1\. Now,𝒫⁡\(𝔸Nδ\+1\)≥c​\(ϵn2/\(2​M2​bl​r\)\)k​\(1−∑i=1Nδ𝒫⁡\(𝔸i\)\)\\mathcal\{P\}\(\\mathbb\{A\}\_\{N^\{\\delta\}\+1\}\)\\geq c\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}\(1\-\\sum\_\{i=1\}^\{N^\{\\delta\}\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\)by Definition[3](https://arxiv.org/html/2609.20883#Thmdefinition3)\. We can thus conclude: c​\(ϵn2/\(M2​bl​r\)\)k​\(1−∑i=1Nδ𝒫⁡\(𝔸i\)\)≤δ​c​\(ϵn2/\(2​M2​bl​r\)\)k⟹∑i=1Nδ𝒫⁡\(𝔸i\)\\displaystyle c\(\\epsilon\_\{n\}^\{2\}/\(M^\{2\}b\_\{lr\}\)\)^\{k\}\\left\(1\-\\sum\_\{i=1\}^\{N^\{\\delta\}\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\\right\)\\leq\\delta c\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}\\implies\\sum\_\{i=1\}^\{N^\{\\delta\}\}\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)≥1−δ\.\\displaystyle\\geq 1\-\\delta\. Now for everyπ∈𝔸i\\pi\\in\\mathbb\{A\}\_\{i\}fori≤Nδi\\leq N^\{\\delta\}, since the diameter of𝔸i\\mathbb\{A\}\_\{i\}is≤ϵn2/\(2​M2​bl​r\)\\leq\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\), 𝒫⁡\(B⁡\(ϵn2/\(2​M2​bl​r\),π\)\)≥𝒫⁡\(𝔸i\)≥δ​c​\(ϵn2/\(2​M2​bl​r\)\)k,\\displaystyle\\mathcal\{P\}\(B\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\),\\pi\)\)\\geq\\mathcal\{P\}\(\\mathbb\{A\}\_\{i\}\)\\geq\\delta c\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\},where we defineB⁡\(r,π\)=\{π′:ρ⁡\(π′,π\)≤r\}B\(r,\\pi\)=\\\{\\pi^\{\\prime\}:\\rho\(\\pi^\{\\prime\},\\pi\)\\leq r\\\}for ease of notation\. Thus define𝔻δ=⋃i=1Nδ𝔸i\\mathbb\{D\}\_\{\\delta\}=\\bigcup\_\{i=1\}^\{N^\{\\delta\}\}\\mathbb\{A\}\_\{i\}to obtain that for everyπ∈𝔻δ\\pi\\in\\mathbb\{D\}\_\{\\delta\}, 𝒫⁡\(B⁡\(ϵn2/\(2​M2​bl​r\),π\)\)≥δ​c​\(ϵ2/\(2​M2​bl​r\)\)k\.\\displaystyle\\mathcal\{P\}\(B\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\),\\pi\)\)\\geq\\delta c\(\\epsilon^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}\.Thus,P​rπ0∼𝒫​\(𝒫⁡\(B⁡\(ϵn2/\(2​M2​bl​r\),π0\)\)≥δ​c​\(ϵn2/\(2​M2​bl​r\)\)k\)≥𝒫⁡\(𝔻δ\)=1−δPr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathcal\{P\}\(B\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\),\\pi\_\{0\}\)\)\\geq\\delta c\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}\)\\geq\\mathcal\{P\}\(\\mathbb\{D\}\_\{\\delta\}\)=1\-\\delta\. We pick aδ\\deltasuch that: δ​c​\(ϵn2/\(2​M2​bl​r\)\)k\\displaystyle\\delta c\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\)\)^\{k\}=exp\(−\(1−b\)nϵn2/M2\)=exp\(−b42\(1−b\)klogn/M2\)\\displaystyle=\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)=\\exp\(\-b\_\{4\}^\{2\}\(1\-b\)k\\log n/M^\{2\}\)⟹log⁡δ\+log⁡\(c\)\\displaystyle\\implies\\log\\delta\+\\log\(c\)=−b42​\(1−b\)M2​k​log⁡n−k​log⁡ϵn2\+k​log⁡\(2​M2​bl​r\)\\displaystyle=\-\\frac\{b\_\{4\}^\{2\}\(1\-b\)\}\{M^\{2\}\}k\\log n\-k\\log\\epsilon\_\{n\}^\{2\}\+k\\log\(2M^\{2\}b\_\{lr\}\)=−k⁡\(b42​\(1−b\)M2​log​n−log⁡\(2​M2​bl​r\)\)−k​log⁡\(b42​k​log​n\)\+k​log​n\\displaystyle=\-k\\left\(\\frac\{b\_\{4\}^\{2\}\(1\-b\)\}\{M^\{2\}\}\\log n\-\\log\(2M^\{2\}b\_\{lr\}\)\\right\)\-k\\log\(b\_\{4\}^\{2\}k\\log n\)\+k\\log n≤−k⁡\(b42​\(1−b\)M2​log⁡n−log⁡n−log⁡\(2​M2​bl​r\)\)\.\\displaystyle\\leq\-k\\left\(\\frac\{b\_\{4\}^\{2\}\(1\-b\)\}\{M^\{2\}\}\\log n\-\\log n\-\\log\(2M^\{2\}b\_\{lr\}\)\\right\)\. For anyb∈\(0,1\)b\\in\(0,1\), we already have the constraints thatCtest​M2\>\(2\+b\)C\_\{\\mathrm\{test\}\}M^\{2\}\>\(2\+b\)andb4\>M/2b\_\{4\}\>M/\\sqrt\{2\}\. We additionally imposeb42​\(1−b\)M2\>1\\frac\{b\_\{4\}^\{2\}\(1\-b\)\}\{M^\{2\}\}\>1such thatδ\\deltaasymptotically decreases withnn\. Thus, for anybl​r\>0,b∈\(0,1\)b\_\{lr\}\>0,b\\in\(0,1\), there existn4=ω⁡\(bl​r\),k4\>0n\_\{4\}=\\omega\(b\_\{lr\}\),k\_\{4\}\>0and a constantb3\>0b\_\{3\}\>0such that for alln\>n4,k\>k4n\>n\_\{4\},k\>k\_\{4\},δ≤exp⁡\(−b3​b42​k​log⁡n\)=exp⁡\(−b3​n​ϵn2\)\\delta\\leq\\exp\(\-b\_\{3\}b\_\{4\}^\{2\}k\\log n\)=\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)\. Thus forn\>n4,k\>k4n\>n\_\{4\},k\>k\_\{4\}, using Equation[8](https://arxiv.org/html/2609.20883#A2.E8), Prπ0∼𝒫\(𝒫\(B\(ϵn2/\(2M2bl​r\),π0\)\)≥exp\(−\(1−b\)nϵn2/M2\)\)≥1−exp\(−b3nϵn2\)\\displaystyle Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathcal\{P\}\(B\(\\epsilon\_\{n\}^\{2\}/\(2M^\{2\}b\_\{lr\}\),\\pi\_\{0\}\)\)\\geq\\exp\(\-\(1\-b\)n\\epsilon\_\{n\}^\{2\}/M^\{2\}\)\)\\geq 1\-\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)⟹Prπ0∼𝒫\(𝔼π0⊗n\[𝒫\(π:ρ\(π,π0\)\>ϵn\|X1,…,Xn\)\]≤5exp\(−OPENOPENb2​n​ϵn2\)\)≥1−exp⁡\(−b3​n​ϵn2\)\.\\displaystyle\\implies\\begin\{aligned\} Pr\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\(\\mathbb\{E\}\_\{\\pi\_\{0\}^\{\\otimes n\}\}\\left\[\\mathcal\{P\}\(\\pi:\\rho\(\\pi,\\pi\_\{0\}\)\>\\epsilon\_\{n\}\|X\_\{1\},\\ldots,X\_\{n\}\)\\right\]\\leq 5\\exp\(\-&b\_\{2\}n\\epsilon\_\{n\}^\{2\}\)\)\\\\ &\\geq 1\-\\exp\(\-b\_\{3\}n\\epsilon\_\{n\}^\{2\}\)\.\\end\{aligned\} We now recall from Equation[7](https://arxiv.org/html/2609.20883#A2.E7)that we wanted to establish the above condition for constantsb2,b3,b4b\_\{2\},b\_\{3\},b\_\{4\}\(that do not depend onn,kn,k\) andϵn=b4​k​log⁡nn\\epsilon\_\{n\}=b\_\{4\}\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\. We have thus established all requirements to state our final bound, 𝔼π0∼𝒫​\[𝔼X1,…,Xn∼π0​\[ρT​V​\(π0,π^n\)\]\]=O⁡\(k​log⁡nn\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\_\{0\}\\sim\\mathcal\{P\}\}\[\\mathbb\{E\}\_\{X\_\{1\},\\ldots,X\_\{n\}\\sim\\pi\_\{0\}\}\[\\rho\_\{TV\}\(\\pi\_\{0\},\\hat\{\\pi\}\_\{n\}\)\]\]=O\\left\(\\frac\{\\sqrt\{k\\log n\}\}\{\\sqrt\{n\}\}\\right\)\.

∎