Actually, All Learnable Distribution Classes Are Privately Learnable

# Actually, All Learnable Distribution Classes Are Privately Learnable
Source: [https://arxiv.org/html/2610.28878](https://arxiv.org/html/2610.28878)
## Actually, All Learnable Distribution Classes Are Privately LearnableThanks:Authors are listed in alphabetical order\.

Mohammad Afzali††thanks:University of British Columbia\.moafzali@cs\.ubc\.ca\. Supported in part by a Four Year Doctoral Fellowship \(4YF\) from the University of British Columbia\.Hassan Ashtiani††thanks:McMaster University and Vector Institute\.zokaeiam@mcmaster\.ca\. Supported by an NSERC Discovery Grant\.Gautam Kamath††thanks:New York University\.g@csail\.mit\.edu\. Supported by an NSERC Discovery Grant and an Ontario Early Researcher Award\.Peihan Liu††thanks:Columbia University\.peihanliu@cs\.columbia\.edu\. Supported in part by the Center for Smart Streetscapes, an NSF Engineering Research Center, under grant agreement EEC\-2133516Argyris Mouzakis††thanks:University of Texas at Austin\. Supported by the NSF AI Institute for Foundations of Machine Learning \(IFML\)\.Vikrant Singhal††thanks:University of Copenhagen\.vikrant\.singhal@di\.ku\.dk\. Supported by a Startup grant from Novo Nordisk Foundation \(NNF24OC0087820\)\.

###### Abstract

We show that every class of distributions that is learnable up to arbitrarily small target error in total variation distance with finitely many samples is also learnable under\(ε,δ\)\(\\varepsilon,\\delta\)\-differential privacy up to arbitrarily small target error with finitely many samples\. This proves a conjecture of Ashtiani\. Previous work by Bun, Kamath, Mouzakis, and Singhal\[[16](https://arxiv.org/html/2610.28878#bib.bib11)\]gave a*weak*refutation of this conjecture, showing that this implication is not true when learnability is defined with respect to a fixed target error\. In contrast, we show that, under the standard definition of learnability, the conjecture is true\.

## 1Introduction

Suppose a learner receives samples from an unknown probability distributionpp, which is known to belong to some class of probability distributions𝒬\\mathcal\{Q\}\. Can the learner identify a distributionp^\\hat\{p\}, such thatp^\\hat\{p\}is close to the distributionppin total variation distance? This fundamental question is known as*distribution learning*or*density estimation*, and has seen significant study across a variety of adjacent research communities including computer science, statistics, and information theory \(see, for example,\[[37](https://arxiv.org/html/2610.28878#bib.bib28),[23](https://arxiv.org/html/2610.28878#bib.bib17),[22](https://arxiv.org/html/2610.28878#bib.bib16),[25](https://arxiv.org/html/2610.28878#bib.bib18),[8](https://arxiv.org/html/2610.28878#bib.bib5),[40](https://arxiv.org/html/2610.28878#bib.bib43)\]\)\.

The problem of density estimation has also been studied extensively under the constraint of differential privacy \(DP\)\[[27](https://arxiv.org/html/2610.28878#bib.bib21)\]\. Indeed, there is a rich body of literature on private learning of various classes of distributions\. Some examples are private density estimation of structured univariate distributions\[[24](https://arxiv.org/html/2610.28878#bib.bib19),[35](https://arxiv.org/html/2610.28878#bib.bib27)\], high\-dimensional Gaussians\[[32](https://arxiv.org/html/2610.28878#bib.bib24),[17](https://arxiv.org/html/2610.28878#bib.bib12),[15](https://arxiv.org/html/2610.28878#bib.bib10),[1](https://arxiv.org/html/2610.28878#bib.bib2),[9](https://arxiv.org/html/2610.28878#bib.bib6),[38](https://arxiv.org/html/2610.28878#bib.bib30),[33](https://arxiv.org/html/2610.28878#bib.bib25),[5](https://arxiv.org/html/2610.28878#bib.bib4),[29](https://arxiv.org/html/2610.28878#bib.bib23)\], Gaussian Mixture Models\[[34](https://arxiv.org/html/2610.28878#bib.bib26),[2](https://arxiv.org/html/2610.28878#bib.bib3),[13](https://arxiv.org/html/2610.28878#bib.bib8),[3](https://arxiv.org/html/2610.28878#bib.bib37),[10](https://arxiv.org/html/2610.28878#bib.bib42),[4](https://arxiv.org/html/2610.28878#bib.bib38)\], and product distributions\[[32](https://arxiv.org/html/2610.28878#bib.bib24),[17](https://arxiv.org/html/2610.28878#bib.bib12),[45](https://arxiv.org/html/2610.28878#bib.bib35)\]\.

One vibrant program within this area has focused on designing increasingly general and generic frameworks for learning distribution classes \(see, for example,\[[17](https://arxiv.org/html/2610.28878#bib.bib12),[9](https://arxiv.org/html/2610.28878#bib.bib6),[29](https://arxiv.org/html/2610.28878#bib.bib23),[12](https://arxiv.org/html/2610.28878#bib.bib7),[3](https://arxiv.org/html/2610.28878#bib.bib37),[4](https://arxiv.org/html/2610.28878#bib.bib38)\]\)\. At their core, many of these methods rely upon non\-private learning algorithms as a black box, applying DP techniques on their outputs to design private algorithms\. At a July 2022 workshop at the Fields Institute, Ashtiani conjectured that*every*learnable distribution class could be privately learned\[[11](https://arxiv.org/html/2610.28878#bib.bib40)\]\.

###### Conjecture 1\.1\(Ashtiani’s Conjecture\)\.

Every distribution class𝒬\\mathcal\{Q\}that is learnable with respect to total variation distance is also learnable under the additional constraint of\(ε,δ\)\(\\varepsilon,\\delta\)\-differential privacy\.

Our main result \(Theorem[1\.3](https://arxiv.org/html/2610.28878#S1.Thmtheorem3)\) is a positive resolution to this conjecture: given a non\-private algorithm for learning a distribution class up to arbitrarily small target error in total variation distance, we provide a private algorithm for learning the same distribution class\.

A recent work by Bun, Kamath, Mouzakis, and Singhal\[[16](https://arxiv.org/html/2610.28878#bib.bib11)\]claimed to refute Ashtiani’s conjecture, which may seem to contradict our result\. In fact, their work can be viewed as a weak refutation of Ashtiani’s conjecture\. They constructed a distribution class which can be learned up to constant error in total variation distance, but cannot be learned privately to that same error\. The distribution class in their counter\-example, however, is not \(non\-privately\) learnable to all values of error\. In contrast, we use the traditional definition of learnability, wherein the distribution class must be learnable to*arbitrarily small*error\[[36](https://arxiv.org/html/2610.28878#bib.bib29)\]\. Indeed, our private algorithm relies crucially upon non\-private learning of the class to a higher accuracy than the target\.

Our positive resolution of the conjecture may come as a surprise as private and non\-private learnability are not necessarily equivalent for problems beyond density estimation\. Indeed, in the standard binary classification setting, non\-private learnability does not imply\(ε,δ\)\(\\varepsilon,\\delta\)\-DP learnability\[[19](https://arxiv.org/html/2610.28878#bib.bib14),[6](https://arxiv.org/html/2610.28878#bib.bib44)\]\. It is also remarkable that for \(non\-private\) density estimation, a nice characterization of learnability is not known \(and in some sense impossible\[[39](https://arxiv.org/html/2610.28878#bib.bib31),[40](https://arxiv.org/html/2610.28878#bib.bib43)\]\) while our private to non\-private reduction works anyway\.

### 1\.1Results

In what follows, let𝒳\\mathcal\{X\}be the domain of examples, which we assume is a standard Borel space, and denote byΔ⁡\(𝒳\)\\Delta\(\\mathcal\{X\}\)the set of all probability distributions on𝒳\\mathcal\{X\}\. Any𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)is referred to as a*distribution class*\. Denote by TV the total variation distance: forp,q∈Δ⁡\(𝒳\)p,q\\in\\Delta\(\\mathcal\{X\}\),TV⁡\(p,q\)≔supA∈ℬ\|p⁡\(A\)−q⁡\(A\)\|\\TV\(p,q\)\\coloneqq\\sup\_\{A\\in\\mathcal\{B\}\}\|p\(A\)\-q\(A\)\|whereℬ\\mathcal\{B\}are the measurable sets of𝒳\\mathcal\{X\}\.

###### Definition 1\.2\(Distribution learning\)\.

A distribution class𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)islearnableif there exist a learnerA:𝒳∗→Δ⁡\(𝒳\)A:\\mathcal\{X\}^\{\*\}\\to\\Delta\(\\mathcal\{X\}\)and a functionm:\(0,1\)2→ℕm:\(0,1\)^\{2\}\\to\\mathbb\{N\}such that, for everyα,β∈\(0,1\)\\alpha,\\beta\\in\(0,1\), everyn≥m⁡\(α,β\)n\\geq m\(\\alpha,\\beta\), and everyp∈𝒬p\\in\\mathcal\{Q\},

PrS∼pn\[TV\(A\(S\),p\)≥α\]≤β\.\\Pr\_\{S\\sim p^\{n\}\}\[\\TV\(A\(S\),p\)\\geq\\alpha\]\\leq\\beta\.
Thesample complexityof learning𝒬\\mathcal\{Q\}is the pointwise infimum of all functionsmmfor which there exists a learnerAAsatisfying the above guarantee\.

###### Theorem 1\.3\(Learnable classes are privately learnable; informal version of Theorem[6\.1](https://arxiv.org/html/2610.28878#S6.Thmtheorem1)\)\.

Suppose𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)is learnable with sample complexitym⁡\(α,β\)m\(\\alpha,\\beta\)forα,β∈\(0,1\)\\alpha,\\beta\\in\(0,1\)\. Then, for everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\),𝒬\\mathcal\{Q\}is also learnable under\(ε,δ\)\(\\varepsilon,\\delta\)\-differential privacy, with sample complexityn⁡\(α,β,ε,δ\)=O⁡\(m⁡\(1512​m​\(α/3,1/32\),116\)​1ε​log⁡\(4δ\)​log⁡\(4β\)\)n\(\\alpha,\\beta,\\varepsilon,\\delta\)=O\\left\(m\\left\(\\frac\{1\}\{512m\\left\(\\alpha/3,1/32\\right\)\},\\frac\{1\}\{16\}\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\delta\}\\right\)\\log\\left\(\\frac\{4\}\{\\beta\}\\right\)\\right\)\.

In particular, if a class𝒬\\mathcal\{Q\}is learnable with sample complexitym⁡\(α,β\)=poly​\(1α,log⁡1β\)m\(\\alpha,\\beta\)=\\text\{poly\}\(\\tfrac\{1\}\{\\alpha\},\\log\\tfrac\{1\}\{\\beta\}\), our bound implies that𝒬\\mathcal\{Q\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP learnable with sample complexitym⁡\(α,β,ε,δ\)=poly​\(1α,log⁡1β,1ε,log⁡1δ\)m\(\\alpha,\\beta,\\varepsilon,\\delta\)=\\text\{poly\}\(\\tfrac\{1\}\{\\alpha\},\\log\\tfrac\{1\}\{\\beta\},\\frac\{1\}\{\\varepsilon\},\\log\\tfrac\{1\}\{\\delta\}\)\.

As part of our approach, we develop private samplers\[[44](https://arxiv.org/html/2610.28878#bib.bib34),[20](https://arxiv.org/html/2610.28878#bib.bib15)\]for any learnable class, which can be of independent interest\. These samplers receive private data points and output a synthetic data set, generated from a distribution that is close to the underlying \(unknown\) distribution\.

###### Definition 1\.4\(Approximate multi\-sampler\)\.

Let𝒬⊆Δ⁡\(𝒳\)\\Q\\subseteq\\Delta\(\\mathcal\{X\}\),ℓ∈ℕ\\ell\\in\\mathbb\{N\},γ∈\(0,1\)\\gamma\\in\(0,1\)\. A randomized algorithmM:𝒳n→𝒳ℓM:\\mathcal\{X\}^\{n\}\\to\\mathcal\{X\}^\{\\ell\}is a\(ℓ,𝛄\)\\bm\{\(\\ell,\\gamma\)\}\-samplerfor𝒬\\Qwith sample complexitynnif for everyp∈𝒬p\\in\\Q,

TV⁡\(ℒ⁡\(Z\),ℒ⁡\(Z′\)\)≤γ,\\TV\(\\mathcal\{L\}\(Z\),\\mathcal\{L\}\(Z^\{\\prime\}\)\)\\leq\\gamma,whereZ∼pℓZ\\sim p^\{\\ell\},Z′=M⁡\(S\)Z^\{\\prime\}=M\(S\)withS∼pnS\\sim p^\{n\}, andℒ⁡\(⋅\)\\mathcal\{L\}\(\\cdot\)corresponds to the law of the random variable\.

###### Theorem 1\.5\(Differentially private synthetic data for learnable classes; informal version of Theorem[4\.3](https://arxiv.org/html/2610.28878#S4.Thmtheorem3)\)\.

Let𝒬⊆Δ⁡\(𝒳\)\\Q\\subseteq\\Delta\(\\mathcal\{X\}\)be learnable with sample complexitym⁡\(α,β\)m\(\\alpha,\\beta\)\. For everyℓ∈ℕ\\ell\\in\\mathbb\{N\}andγ\\gamma,ε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\), there exists a\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially private\(ℓ,γ\)\(\\ell,\\gamma\)\-sampler for𝒬\\Qwith sample complexity

n=O⁡\(m⁡\(γ64​ℓ,116\)​log⁡\(1γ​δ\)​1ε\)\.n=O\\left\(m\\left\(\\frac\{\\gamma\}\{64\\ell\},\\frac\{1\}\{16\}\\right\)\\log\\left\(\\frac\{1\}\{\\gamma\\delta\}\\right\)\\frac\{1\}\{\\varepsilon\}\\right\)\.

For the problem of \(non\-private\) density estimation, learnability in realizable setting is not equivalent to learnability in agnostic/robust setting\[[14](https://arxiv.org/html/2610.28878#bib.bib9)\]\. Our next result is a private to non\-private reduction for agnostic learning of distributions\. The formal version and more discussions appear in Section[C](https://arxiv.org/html/2610.28878#A3)\.

###### Theorem 1\.6\(Agnostic learnability implies private agnostic learnability, Informal version of[C\.2](https://arxiv.org/html/2610.28878#A3.Thmtheorem2)\)\.

Suppose𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)is “agnostic” learnable with sample complexitym⁡\(α,β\)m\(\\alpha,\\beta\)forα,β∈\(0,1\)\\alpha,\\beta\\in\(0,1\)\. Then, for everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\),𝒬\\mathcal\{Q\}is also agnostic learnable under\(ε,δ\)\(\\varepsilon,\\delta\)\-differential privacy, with sample complexityn⁡\(α,β,ε,δ\)=O⁡\(m⁡\(Θ⁡\(α\),116\)​m​\(Θ⁡\(α\),β\)​1ε​log⁡\(Θ⁡\(1α​δ\)\)𝐶𝐿𝑂𝑆𝐸n\(\\alpha,\\beta,\\varepsilon,\\delta\)=O\\left\(m\\left\(\\Theta\(\\alpha\),\\frac\{1\}\{16\}\\right\)m\\left\(\\Theta\(\\alpha\),\\beta\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\Theta\(\\frac\{1\}\{\\alpha\\delta\}\\right\)\\right\)\.

### 1\.2Techniques

At its core, our algorithm falls into the subsample\-and\-aggregate framework\[[43](https://arxiv.org/html/2610.28878#bib.bib33)\]\. Suppose we have a non\-private learning algorithmAA, which learns the distribution class𝒬\\mathcal\{Q\}in total variation distance\. Consider the following intuitive yet naive approach:

1. 1\.Partition the dataset intok=O⁡\(log⁡\(1/δ\)/ε\)k=O\(\\log\(1/\\delta\)/\\varepsilon\)parts;
2. 2\.Run the non\-private learning algorithmAAon each part;
3. 3\.Privately aggregate the outputs\.

Letqiq\_\{i\}fori∈\[k\]i\\in\[k\]be the output of the non\-private learning algorithm on theithi^\{\\text\{th\}\}part of the dataset\. If many ofqiq\_\{i\}’s are exactly the same \(i\.e\., the learner is*globally stable*\[[18](https://arxiv.org/html/2610.28878#bib.bib13)\]\), then they can be easily aggregated, for example, using DP stability\-based mode\[[47](https://arxiv.org/html/2610.28878#bib.bib36)\]\. However, the non\-private learnerAAonly guarantees that, with high probability, most ofqiq\_\{i\}’s are*close to*the ground truthppin TV, thus to one another\. In other words, non\-private density estimators may not be globally stable\.

Another idea for aggregatingqiq\_\{i\}’s is to first generate samples from eachqiq\_\{i\}, and then privately aggregate these samples\. AssumeZi∼qiℓZ\_\{i\}\\sim q\_\{i\}^\{\\ell\}is a sample of sizeℓ\\ellfromqiq\_\{i\}\. If we are lucky and many of theseZiZ\_\{i\}’s “collide” \(take the exact same value for different choices ofii\), then again we can privately aggregate them and will end up having a private sample set \(synthetic data\) from a distribution that is close to the ground truth distributionpp\. These public samples can then be fed to the non\-private learner to find an approximation topp\. In first glance, introducing the additional step of sampling fromqiq\_\{i\}’s appears counterproductive\. In fact, nowZiZ\_\{i\}’s may not collide not only becauseqiq\_\{i\}’s are not colliding, but also because of the randomness of generatingZiZ\_\{i\}’s\. Indeed, this would be the case ifZiZ\_\{i\}’s are generated independently for eachii\. However, as we discuss below, allowingZiZ\_\{i\}’s to be correlated \(across values ofii\) gives an extra flexibility that proves to be crucial for stablizing the outcomes of non\-private learners\.

To make the idea concrete we turn to*couplings*\. Couplings construct a joint distribution over a collection of random variables such that their marginal distributions are preserved\. The key observation is that a suitable TV coupling can convert closeness in total variation distance into a high probability guarantee of*exact equality*between sampled outcomes\. Specifically, after obtainingq1,…,qkq\_\{1\},\.\.\.,q\_\{k\}non privately, we jointly draw\(Z1,…,Zk\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)from a TV coupling of these distributions satisfying Definition[3\.1](https://arxiv.org/html/2610.28878#S3.Thmtheorem1)\. The coupling is designed to satisfy two key desiderata: \(1\) each marginal has the correct law, so thatZi∼qiℓZ\_\{i\}\\sim q\_\{i\}^\{\\ell\}is a valid synthetic dataset from the learner output on theit​hi^\{th\}block, and \(2\) assumingqiq\_\{i\}’s are all close in total variation distance, synthetic datasetsZiZ\_\{i\}’s would take the*exact same value*with high probability\. Thus, a TV coupling can convert total variation closeness of theqiq\_\{i\}’s into the sufficiently many exact repetitions of theZiZ\_\{i\}’s needed by the stability\-based mode\.

Indeed, the use of correlated sampling to convert closeness in TV into agreement of sampled outcomes already appears in the user\-level private learning algorithms of Ghazi, Kumar, and Manurangsi\[[28](https://arxiv.org/html/2610.28878#bib.bib22)\]\. Kalavasis, Karbasi, Moran, and Velegkas\[[30](https://arxiv.org/html/2610.28878#bib.bib1)\]subsequently use a related coupling approach to reduce TV\-indistinguishable PAC learning to approximate differentially private learning\. A similar concept has been used in\[[21](https://arxiv.org/html/2610.28878#bib.bib45)\]for private aggregation of teacher models\. In our setting, we apply this principle to synthetic datasets\.

Our constructions of a couplings are based on the Poisson coupling of Angel and Spinka\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\], which ensures that for alli,j∈\[k\]i,j\\in\[k\]simultaneously,Pr\[Zi≠Zj\]≤2TV\(qiℓ,qjℓ\)\.\\Pr\[Z\_\{i\}\\neq Z\_\{j\}\]\\leq 2\\TV\(q\_\{i\}^\{\\ell\},q\_\{j\}^\{\\ell\}\)\.When all relevant distributions admit densities with respect to a commonσ\\sigma\-finite reference measure, the Poisson coupling of Angel and Spinka\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]applies directly, as in\[[30](https://arxiv.org/html/2610.28878#bib.bib1)\]\. This already covers many familiar distribution classes\. For our main result, however, we must handle*arbitrary*learnable distribution classes, for which such a common dominating measure need not exist\. For instance,𝒫=\{δx:x∈ℝ\}\\mathcal\{P\}=\\\{\\delta\_\{x\}:x\\in\\mathbb\{R\}\\\}is trivially learnable with a single sample but there is noσ\\sigma\-finite measure dominating all point masses\. We, therefore, develop a more general version of the Poisson coupling that removes the common\-dominating\-measure assumption while retaining the same marginal and pairwise agreement guarantees on general standard Borel spaces\.

The coupling methods allow us to turn closeness of TV distances betweenqi′​sq\_\{i\}^\{\\prime\}sto agreement probability lower bounds betweenZiZ\_\{i\}’s\. Private aggregation ofZiZ\_\{i\}’s then gives the private multi\-sampler of Theorem[1\.5](https://arxiv.org/html/2610.28878#S1.Thmtheorem5)\. In order to have a private distribution learner, one can simply feed a privatized sample set to the non\-private learner\. However, this approach would result in a poor dependency onβ\\beta, the failure probability\. To overcome this issue, we use a boosting argument\.

This results in the logarithmic dependence of sample complexity on1/β1/\\betain Theorem[1\.3](https://arxiv.org/html/2610.28878#S1.Thmtheorem3)\.

### 1\.3AI Disclosure

The initial resolution for Ashtiani’s conjecture in the case of countable domains was independently obtained by two authors prompting GPT\-5\.6 Sol\. An internal Gemini model also produced a positive resolution of the conjecture by discovering a similar algorithm to the one presented\. All authors digested the result and verified it to be correct\.

Additional prompting, verification, and derivations from the authors resulted in the presented measure\-theoretic arguments that consititute a full resolution to the conjecture for general domains\. Care was taken to write the paper in a way that communicates the ideas most clearly to a human reader\. The authors also conducted a literature search to attribute the main algorithmic ideas to\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]and\[[30](https://arxiv.org/html/2610.28878#bib.bib1)\]\. All writing in this paper is done by the authors, who take full responsibility for the claims made herein\.

## 2Preliminaries

Let𝒴\\mathcal\{Y\}be a standard Borel space, and letℬ⁡\(𝒴\)\\mathcal\{B\}\(\\mathcal\{Y\}\)denote the Borel sets andΔ⁡\(𝒴\)\\Delta\(\\mathcal\{Y\}\)the probability measures on𝒴\\mathcal\{Y\}, with theσ\\sigma\-algebra generated by the mapP↦P⁡\(B\)P\\mapsto P\(B\)forB∈ℬ⁡\(𝒴\)B\\in\\mathcal\{B\}\(\\mathcal\{Y\}\)\. Subsets and finite products carry the induced and productσ\\sigma\-algebras, respectively\.

For a random variableZZ, we writeℒ⁡\(Z\)\\mathcal\{L\}\(Z\)for its law, i\.e\.,ℒ\(Z\)\(B\)=Pr\[Z∈B\]\\mathcal\{L\}\(Z\)\(B\)=\\Pr\[Z\\in B\]for every measurable setBB\. ForP,Q∈Δ⁡\(𝒴\)P,Q\\in\\Delta\(\\mathcal\{Y\}\), their total variation distance isTV⁡\(P,Q\)≔supB∈ℬ⁡\(𝒴\)\|P⁡\(B\)−Q⁡\(B\)\|\\mathrm\{TV\}\(P,Q\)\\coloneqq\\sup\_\{B\\in\\mathcal\{B\}\(\\mathcal\{Y\}\)\}\|P\(B\)\-Q\(B\)\|\.

Our coupling constructions use two standard measure\-theoretic objects\. First, we will use Markov kernels to formalize randomized mappings whose output distributions depend measurably on their inputs\. In particular, they allow us to view our coupling procedures as randomized maps from tuples of distributions to joint synthetic datasets\.

###### Definition 2\.1\(Markov kernel\)\.

Let\(𝒳,𝒜\)\(\\mathcal\{X\},\\mathcal\{A\}\)and\(𝒴,ℬ\)\(\\mathcal\{Y\},\\mathcal\{B\}\)be measurable spaces\. A*Markov kernel*K:𝒳↝𝒴K:\\mathcal\{X\}\\rightsquigarrow\\mathcal\{Y\}assigns to eachx∈𝒳x\\in\\mathcal\{X\}a probability measureK⁡\(x,⋅\)K\(x;\\cdot\)on𝒴\\mathcal\{Y\}, such that, for everyB∈ℬB\\in\\mathcal\{B\}, the mapx↦K⁡\(x,B\)x\\mapsto K\(x;B\)is𝒜\\mathcal\{A\}\-measurable\.

Second, our explicit coupling constructions are based on the Poisson coupling of Angel and Spinka\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\], which is built from Poisson point processes\. We recall their basic definition below\.

Informally, a Poisson point process with intensity measureμ\\muis a random cloud of points scattered over the space according toμ\\mu, where the expected number of points in a regionBBisμ⁡\(B\)\\mu\(B\), and the number of points falling in disjoint regions are independent\.

###### Definition 2\.2\(Poisson point process\)\.

Let\(𝒴,ℬ\)\(\\mathcal\{Y\},\\mathcal\{B\}\)be a measurable space and letμ\\mube aσ\\sigma\-finite measure on𝒴\\mathcal\{Y\}\. A*Poisson point process*𝒜\\mathcal\{A\}on𝒴\\mathcal\{Y\}with intensity measureμ\\muis a random counting measure such that:

1. 1\.for every measurableB⊆𝒴B\\subseteq\\mathcal\{Y\}withμ⁡\(B\)<∞\\mu\(B\)<\\infty,𝒜⁡\(B\)∼Poisson⁡\(μ⁡\(B\)\)\\mathcal\{A\}\(B\)\\sim\\operatorname\{Poisson\}\(\\mu\(B\)\)
2. 2\.for every collection of pairwise disjoint measurable setsB1,…,BmB\_\{1\},\\ldots,B\_\{m\}, the random variables𝒜⁡\(B1\),…,𝒜⁡\(Bm\)\\mathcal\{A\}\(B\_\{1\}\),\\ldots,\\mathcal\{A\}\(B\_\{m\}\)are independent\.

We recall the celebrated definition of differential privacy, as well as its useful post\-processing and parallel composition property\.

###### Definition 2\.3\(Differential privacy \(DP\)\[[27](https://arxiv.org/html/2610.28878#bib.bib21),[26](https://arxiv.org/html/2610.28878#bib.bib20)\]\)\.

Let\(𝒳,𝒜\)\(\\mathcal\{X\},\\mathcal\{A\}\)and\(𝒴,ℬ\)\(\\mathcal\{Y\},\\mathcal\{B\}\)be measurable spaces, and letε\>0\\varepsilon\>0andδ∈\(0,1\)\\delta\\in\(0,1\)\. A randomized algorithmA:𝒳∗→𝒴A:\\mathcal\{X\}^\{\*\}\\to\\mathcal\{Y\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially private if, for everyn∈ℕn\\in\\mathbb\{N\}, every pair of neighboring datasetsS,S′∈𝒳nS,S^\{\\prime\}\\in\\mathcal\{X\}^\{n\}differing in at most one element, and every measurable setB⊆𝒴B\\subseteq\\mathcal\{Y\}, we have

Pr\[A\(S\)∈B\]≤eεPr\[A\(S′\)∈B\]\+δ,\\Pr\[A\(S\)\\in B\]\\leq e^\{\\varepsilon\}\\Pr\[A\(S^\{\\prime\}\)\\in B\]\+\\delta,where the probabilities are over the internal randomness ofAA\.

###### Proposition 2\.4\(Post\-processing\)\.

Let\(𝒳,𝒜\)\(\\mathcal\{X\},\\mathcal\{A\}\),\(𝒴,ℬ\)\(\\mathcal\{Y\},\\mathcal\{B\}\), and\(𝒵,𝒞\)\(\\mathcal\{Z\},\\mathcal\{C\}\)be measurable spaces\. SupposeA:𝒳∗→𝒴A:\\mathcal\{X\}^\{\*\}\\to\\mathcal\{Y\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially private, and letK:𝒴↝𝒵K:\\mathcal\{Y\}\\rightsquigarrow\\mathcal\{Z\}be a data\-independent Markov kernel\. Then the randomized algorithmK∘A:S↦ZK\\circ A:S\\mapsto ZwithZ∼K⁡\(A⁡\(S\),⋅\)Z\\sim K\(A\(S\);\\cdot\)is also\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\.

###### Lemma 2\.5\(Parallel composition\[[41](https://arxiv.org/html/2610.28878#bib.bib32)\]\)\.

Letε≥0\\varepsilon\\geq 0,δ∈\[0,1\)\\delta\\in\[0,1\), and letI1,…,IkI\_\{1\},\\ldots,I\_\{k\}be a fixed partition of\[n\]\[n\]\. For eachi∈\[k\]i\\in\[k\], supposeAi:𝒳∗→𝒴A\_\{i\}:\\X^\{\*\}\\rightarrow\\Yis\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially private\. Then, for anyS∈𝒳nS\\in\\X^\{n\}, the algorithmA⁡\(S\)≔\(A1​\(SI1\),…,Ak​\(SIk\)\)A\(S\)\\coloneqq\\bigl\(A\_\{1\}\(S\_\{I\_\{1\}\}\),\\ldots,A\_\{k\}\(S\_\{I\_\{k\}\}\)\\bigr\), where the invocations use independent randomness, is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\.

## 3Couplings

As discussed in Section[1\.2](https://arxiv.org/html/2610.28878#S1.SS2), our private aggregation procedure requires a correlated sampling mechanism that converts TV closeness of the learner outputs into exact agreement of the sampled synthetic datasets\. We now formalize the properties of the coupling needed for the subsequent privacy and utility analyses\. In addition to having the correct marginals and a small pairwise disagreement probability discussed above, we further require the joint law of every finite collection of coupled samples to depend measurably on the input distributions\. This ensures that the coupling can be applied to random data\-dependent learner outputs and then supplied to subsequent randomized algorithms\.111This notion is closely related to correlated sampling\[[28](https://arxiv.org/html/2610.28878#bib.bib22), Definition 7\]: a strategy with multiplicative error22and a common random seed induces a family satisfying \(G1\) and \(G2\)\. We explicitly require \(G3\) to ensure measurable dependence of the joint laws on the input distributions, enabling composition with subsequent randomized algorithms on standard Borel spaces\.Throughout, we assume the domain𝒴\\Yto be standard Borel\.

###### Definition 3\.1\(Grand coupling scheme\)\.

Let𝒴\\mathcal\{Y\}be standard Borel and𝒫⊆Δ⁡\(𝒴\)\\mathcal\{P\}\\subseteq\\Delta\(\\mathcal\{Y\}\)\. A*grand coupling scheme*on𝒫\\mathcal\{P\}is a family of random variables\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}, on a common probability space, with joint lawΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}, such that:

1. \(G1\)*\(Marginals\.\)*ZP∼PZ\_\{P\}\\sim Pfor everyP∈𝒫P\\in\\mathcal\{P\}\.
2. \(G2\)*\(Agreement\.\)*Pr\[ZP≠ZQ\]≤2TV\(P,Q\)\\Pr\[Z\_\{P\}\\neq Z\_\{Q\}\]\\leq 2\\,\\mathrm\{TV\}\(P,Q\)for allP,Q∈𝒫P,Q\\in\\mathcal\{P\}\.
3. \(G3\)*\(Measurable marginal kernels\.\)*For everyk≥1k\\geq 1, the map𝐏↦ℒ⁡\(ZP1,…,ZPk\)\\mathbf\{P\}\\mapsto\\mathcal\{L\}\(Z\_\{P\_\{1\}\},\\dots,Z\_\{P\_\{k\}\}\)defines a Markov kernelΓk:𝒫k↝𝒴k\\Gamma\_\{k\}:\\mathcal\{P\}^\{k\}\\rightsquigarrow\\mathcal\{Y\}^\{k\}, where𝐏=\(P1,…,Pk\)∈𝒫k\\mathbf\{P\}=\(P\_\{1\},\\dots,P\_\{k\}\)\\in\\mathcal\{P\}^\{k\}\.

𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐏\)\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{P\}\)is then*defined*as a sample fromΓk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)\.

We present two constructions of this interface, based on the Poisson coupling of\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]\. Full details and complete proofs for both constructions are deferred to Appendix[A](https://arxiv.org/html/2610.28878#A1)\. The first, presented in Appendix[A\.1](https://arxiv.org/html/2610.28878#A1.SS1), is the original construction taken verbatim from\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\], which applies when the subset of relevant distributions𝒫\\mathcal\{P\}admits a commonσ\\sigma\-finite dominating measureν\\nu\.

We illustrate how Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)works with a simple example\. Consider a set of distributions𝒫\\mathcal\{P\}on domain\[0,1\]\[0,1\], where for each distributionP∈𝒫P\\in\\mathcal\{P\}, we have densityfPf\_\{P\}with respect to the Lebesgue measure bounded by a constantMM\. Draw an infinite sequence of i\.i\.d\. pairs\(Yi,Ui\)\(Y\_\{i\},U\_\{i\}\), distributed uniformly over\[0,1\]×\[0,M\]\[0,1\]\\times\[0,M\]\. This sequence of pairs is shared across allP∈𝒫P\\in\\mathcal\{P\}\. To draw a sample from a particularPP, we output theYiY\_\{i\}with the minimumiisuch thatUi≤fP​\(Yi\)U\_\{i\}\\leq f\_\{P\}\(Y\_\{i\}\)\. Intuitively, to sample from a distributionPP, this process outputs the first coordinate of the first point that lies underPP’s density\. By a standard rejection sampling argument, the resulting outputZPZ\_\{P\}has lawPP, giving the marginal property \(G1\)\. ForP,Q∈𝒫P,Q\\in\\P, the areas of the intersection and union of their acceptance regions are1−TV⁡\(P,Q\)1\-\\TV\(P,Q\)and1\+TV⁡\(P,Q\)1\+\\TV\(P,Q\), respectively\. Hence, the first proposal accepted by either distribution is accepted by both with probability1−TV⁡\(P,Q\)1\+TV⁡\(P,Q\)\\frac\{1\-\\TV\(P,Q\)\}\{1\+\\TV\(P,Q\)\}, and thus yields the disagreement property \(G2\),Pr\[ZP≠ZQ\]≤2​TV⁡\(P,Q\)1\+TV⁡\(P,Q\)≤2TV\(P,Q\)\\Pr\[Z\_\{P\}\\neq Z\_\{Q\}\]\\leq\\frac\{2\\TV\(P,Q\)\}\{1\+\\TV\(P,Q\)\}\\leq 2\\TV\(P,Q\)\.

More precisely, Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)yields a grand coupling scheme on𝒫\\mathcal\{P\}, using a single Poisson point process shared across allP∈𝒫P\\in\\mathcal\{P\}\. EachP∈𝒫P\\in\\Pdefines its own acceptance region through its densityd​P/d​νdP/d\\nu, and the coupled sampleZPZ\_\{P\}is theyy\-coordinate of the first point of the shared Poisson process that falls in that region, i\.e\., the point in the region with the smallesttt\-coordinate\.

###### Proposition 3\.2\(Informal version of Corollary[A\.3](https://arxiv.org/html/2610.28878#A1.Thmtheorem3)\)\.

Suppose𝒴\\Yis standard Borel and there exists aσ\\sigma\-finite measureν\\nusuch thatP≪νP\\ll\\nufor allP∈𝒫P\\in\\mathcal\{P\}\. Then the family of random variables\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}defined in Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)yields a grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}on𝒫\\mathcal\{P\}\.

Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)already captures a wide range of distribution classes\. For example, a family of distributions onℝd\\mathbb\{R\}^\{d\}that are all absolutely continuous with respect to Lebesgue measure admits a commonσ\\sigma\-finite dominating measure\. However, an arbitrary learnable distribution class need not admit such a measure\. For instance,𝒫=\{δx:x∈ℝ\}\\mathcal\{P\}=\\\{\\delta\_\{x\}:x\\in\\mathbb\{R\}\\\}is trivially learnable with a single sample but there is noσ\\sigma\-finite measure dominating all point masses\. Therefore, the first construction can not handle such classes\.

The key observation behind our second construction is that while a global measureν\\numay not exist over an arbitrary family, any finite tuple of distributions𝐏=\(P1,…,Pk\)∈Δ​\(𝒴\)k\\mathbf\{P\}=\(P\_\{1\},\\dots,P\_\{k\}\)\\in\\Delta\(\\Y\)^\{k\}always admits a canonical finite dominating measure,ν𝐏=∑i=1kPi\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i=1\}^\{k\}P\_\{i\}\. Returning to the simple example before, for any fixed set ofkkdistributions𝐏\\mathbf\{P\}, we can imagine sampling candidate pointsYiY\_\{i\}from a uniform mixture over𝐏\\mathbf\{P\}\. We can therefore apply the same Poisson coupling construction to each finite tuple respectively, using the tuple\-dependent dominating measureν𝐏\\nu\_\{\\mathbf\{P\}\}\. This yields a couplingΓk​\(𝐏,⋅\)​Δ​\(𝒴k\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)\\Delta\(\\Y^\{k\}\)ofP1,…,PkP\_\{1\},\.\.\.,P\_\{k\}\. We then show that these couplings vary measurably with𝐏\\mathbf\{P\}with the standard Borel machinery, so thatΓk:Δ​\(𝒴\)k↝𝒴k\\Gamma\_\{k\}:\\Delta\(\\mathcal\{Y\}\)^\{k\}\\rightsquigarrow\\mathcal\{Y\}^\{k\}is indeed a Markov kernel\.

The remaining issue is that, the reference measureν𝐏\\nu\_\{\\mathbf\{P\}\}, and thus the Poisson process used in the construction, depend on the tuple𝐏\\mathbf\{P\}– it essentially corresponds to a mixture over thesekkdistributions\. In our later privacy and utility analyses, however, we will need our coupling to handle when we enlarge a tuple ofkkdistributions into a tuple ofk\+1k\+1distributions without changing the joint distribution of the coordinates already present\. This will capture adjoining the ground truth distribution in the utility analysis, or jointly realizing two neighboring executions in the privacy analysis\. A priori, the coupling constructed for\(P1,P2\)\(P\_\{1\},P\_\{2\}\)need not coincide with the first two coordinates of the coupling constructed for\(P1,P2,P3\)\(P\_\{1\},P\_\{2\},P\_\{3\}\)\. Fortunately, the construction is insensitive to this choice\. More formally, the finite\-dimensional kernels are projectively consistent, namely, projecting the coupling of a larger tuple onto any subset of its coordinates gives exactly the coupling obtained by applying the construction directly to the corresponding subtuple\.222Although the kernelsΓk\\Gamma\_\{k\}are defined on ordered tuples, they are permutation equivariant \(Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)\)\. Namely, the finite\-dimensional law associated with a set of distributions is independent of the arbitrary ordering chosen for that set\.

Finally, Kolmogorov’s Extension Theorem \(Corollary[A\.6](https://arxiv.org/html/2610.28878#A1.Thmtheorem6)\) then guarantees the existence of a single, universal joint measureΓ∞∈Δ⁡\(𝒴Δ⁡\(𝒴\)\)\\Gamma\_\{\\infty\}\\in\\Delta\(\\Y^\{\\Delta\(\\Y\)\}\)\. In other words,Γ∞\\Gamma\_\{\\infty\}jointly realizes a random variableZPZ\_\{P\}for everyP∈Δ⁡\(𝒴\)P\\in\\Delta\(\\Y\), with finite\-dimensional marginals given by the kernelsΓk\\Gamma\_\{k\}, such thatZP∼PZ\_\{P\}\\sim Pfor everyP∈Δ⁡\(𝒴\)P\\in\\Delta\(\\Y\), and every pair satisfies the desired disagreement bound\. In particular, restricting this universal coupling to any𝒫⊆Δ⁡\(𝒴\)\\mathcal\{P\}\\subseteq\\Delta\(\\Y\)therefore yields a data\-independent grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}, without requiring a common dominating measure\.

###### Proposition 3\.3\(Informal version of Corollary[A\.7](https://arxiv.org/html/2610.28878#A1.Thmtheorem7)and[A\.6](https://arxiv.org/html/2610.28878#A1.Thmtheorem6)\)\.

Suppose𝒴\\Yis standard Borel\. The family of random variables\(ZP\)P∈Δ⁡\(𝒴\)∼Γ∞\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\mathcal\{Y\}\)\}\\sim\\Gamma\_\{\\infty\}induced by Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)x constitutes a universal grand coupling scheme onΔ⁡\(𝒴\)\\Delta\(\\Y\)\. Consequently, on any subset𝒫⊆Δ⁡\(𝒴\)\\P\\subseteq\\Delta\(\\Y\), its restriction\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}yields a valid grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}on𝒫\\P\.

We emphasize that this grand coupling scheme serves purely as an analytical tool\. Its purpose is to bring independent runs of the algorithms on two inputs into a shared probability space, for our privacy and utility analysis\. By the nature of the coupling, the marginals exactly match the true target distributions \(G1 in Definition[3\.1](https://arxiv.org/html/2610.28878#S3.Thmtheorem1)\)\. Consequently, all results derived within this joint probability space apply directly to the actual execution of the algorithms\.

## 4Private Synthetic Data Sampler

In this section, we apply the abstract grand coupling schemes developed in Section[3](https://arxiv.org/html/2610.28878#S3)to construct a differentially private synthetic data sampler\. Here, we set𝒴=𝒳ℓ\\Y=\\X^\{\\ell\}, where𝒳\\Xis the data universe andℓ\\ellis the size of the synthetic dataset\. Letℱ⊆Δ⁡\(𝒳\)\\mathcal\{F\}\\subseteq\\Delta\(\\mathcal\{X\}\)contain the ground\-truth distribution class𝒬\\mathcal\{Q\}and all possible outputs of the non\-private learner, and set𝒫=\{qℓ:q∈ℱ\}\\mathcal\{P\}=\\\{q^\{\\ell\}:q\\in\\mathcal\{F\}\\\}\. The goal is to privately output a synthetic datasetZ∈𝒳ℓZ\\in\\mathcal\{X\}^\{\\ell\}of arbitrary target sizeℓ\\ellsuch thatTV⁡\(ℒ⁡\(Z\),pℓ\)≤β\\mathrm\{TV\}\(\\mathcal\{L\}\(Z\),p^\{\\ell\}\)\\leq\\beta, given a datasetS∼pnS\\sim p^\{n\}from an unknown distributionp∈𝒬p\\in\\Q\.

#### Technical Intuition\.

At a high level, we partition the samples into disjoint blocks, run the non\-private learner on each block, and use our grand coupling to generate correlated synthetic datasets from the resulting learner outputs\.

For the utility analysis, we would like to show not only that the synthetic datasetsZ1,…,ZkZ\_\{1\},\.\.\.,Z\_\{k\}agree with one another frequently, but that their common values “behaves like an i\.i\.d\. sample” from the ground truth distributionpp\. To this end, we introduce an analysis\-only “ghost” sampleZ∗∼pℓZ^\{\*\}\\sim p^\{\\ell\}from the ground truth distribution and consider the augmented vector\(Z1,…,Zk,Z∗\)\(Z\_\{1\},\\dots,Z\_\{k\},Z^\{\*\}\)with joint lawΓk\+1​\(\(q1ℓ,…,qkℓ,pℓ\),⋅\)\\Gamma\_\{k\+1\}\\bigl\(\(q\_\{1\}^\{\\ell\},\\dots,q\_\{k\}^\{\\ell\},p^\{\\ell\}\);\\cdot\\bigr\), which is the corresponding finite\-dimensional marginal of our grand couplingΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}from Proposition[3\.3](https://arxiv.org/html/2610.28878#S3.Thmtheorem3)\. Note that the augmented vector is drawn from the same grand coupling, so adjoining this extra “ghost” coordinate does not change the joint law of the synthetic datasets produced by the algorithm, i\.e\., its marginal on the firstkkcoordinates is exactlyΓk​\(\(q1ℓ,…,qkℓ\),⋅\)\\Gamma\_\{k\}\(\(q\_\{1\}^\{\\ell\},\\dots,q\_\{k\}^\{\\ell\}\);\\cdot\)\.

Moreover, by the disagreement bound, for every learn outputqiq\_\{i\},Pr\[Zi≠Z∗\]≤2TV\(qiℓ,pℓ\)≤2ℓTV\(qi,p\)\\Pr\[Z\_\{i\}\\neq Z^\{\*\}\]\\leq 2\\,\\mathrm\{TV\}\(q\_\{i\}^\{\\ell\},p^\{\\ell\}\)\\leq 2\\ell\\,\\mathrm\{TV\}\(q\_\{i\},p\)\. Thus, when most blockwise learner outputs are accurate, many of the corresponding synthetic dataset agree withZ∗Z^\{\*\}exactly\. With appropriate accuracy parameters, we show that a large majority agree withZ∗Z^\{\*\}, providing the frequency gap required by𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}to outputZ∗Z^\{\*\}, with high probability\. The additional coordinateZ∗Z^\{\*\}is used only in the analysis and is not generated by the algorithm\.

For the privacy analysis, fix neighboring datasetsS,S′S,S^\{\\prime\}and use the same partition and base\-learner randomness in both executions\. Changing one record affects at most one block, so the resulting tuples𝐪=\(q1,…,qk\)\\q=\(q\_\{1\},\.\.\.,q\_\{k\}\)and𝐪′=\(q1′,…,qk′\)\\q^\{\\prime\}=\(q\_\{1\}^\{\\prime\},\.\.\.,q\_\{k\}^\{\\prime\}\)differ in at most one coordinatejj\. For the analysis only, we take a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\P\}\\sim\\Gamma\_\{\\P\}and defineZ~i=Zqiℓ\\widetilde\{Z\}\_\{i\}=Z\_\{q\_\{i\}^\{\\ell\}\}, andZ~i′=Z\(qi′\)ℓ\\widetilde\{Z\}^\{\\prime\}\_\{i\}=Z\_\{\(q^\{\\prime\}\_\{i\}\)^\{\\ell\}\}\. By \(G3\) and the definition of𝖢𝗈𝗎𝗉𝗅𝖾k\\mathsf\{Couple\}\_\{k\},\(Z~1,…,Z~k\)\(\\widetilde\{Z\}\_\{1\},\\dots,\\widetilde\{Z\}\_\{k\}\)has joint lawΓk​\(\(q1ℓ,…,qkℓ\),⋅\)\\Gamma\_\{k\}\(\(q\_\{1\}^\{\\ell\},\\dots,q\_\{k\}^\{\\ell\}\);\\cdot\), and\(Z~1′,…,Z~k′\)\(\\widetilde\{Z\}^\{\\prime\}\_\{1\},\\dots,\\widetilde\{Z\}^\{\\prime\}\_\{k\}\)has joint lawΓk​\(\(\(q1′\)ℓ,…,\(qk′\)ℓ\),⋅\)\\Gamma\_\{k\}\(\(\(q^\{\\prime\}\_\{1\}\)^\{\\ell\},\\dots,\(q^\{\\prime\}\_\{k\}\)^\{\\ell\}\);\\cdot\)\. These are exactly the joint laws used by the coupled sampling step in the two executions\. For every unchanged coordinatei≠ji\\neq j, we haveqi=qi′q\_\{i\}=q^\{\\prime\}\_\{i\}, and henceZ~i=Z~i′\\widetilde\{Z\}\_\{i\}=\\widetilde\{Z\}^\{\\prime\}\_\{i\}for every realization of the shared draw\.333For example, suppose𝐪=\(q1,q2\)\\q=\(q\_\{1\},q\_\{2\}\)and𝐪′=\(q1′,q2′\)\\q^\{\\prime\}=\(q\_\{1\}^\{\\prime\},q\_\{2\}^\{\\prime\}\)are obtained from the executions onSSandS′S^\{\\prime\}respectively, withq1≠q1′q\_\{1\}\\neq q\_\{1\}^\{\\prime\}andq2=q2′q\_\{2\}=q\_\{2\}^\{\\prime\}\. The unchanged coordinatei=2i=2is represented in both executions by the same coordinateZq2ℓ=Zq2′ℓZ\_\{q\_\{2\}^\{\\ell\}\}=Z\_\{q\_\{2\}^\{\\prime\\ell\}\}of the shared grand coupling\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\P\}\\sim\\Gamma\_\{\\P\}, and thus,Z~2′=Zq2′ℓ=Zq2ℓ=Z~2\\tilde\{Z\}\_\{2\}^\{\\prime\}=Z\_\{q\_\{2\}^\{\\prime\\ell\}\}=Z\_\{q\_\{2\}^\{\\ell\}\}=\\tilde\{Z\}\_\{2\}point wise\.

Thus, the two inputs to𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}are neighboring for every realization, so its privacy guarantee applies to each fixed coupling draw\.

#### Road Map\.

We present the formal construction in two stages to isolate the coupling randomness from the statistical randomness of the dataset partition and base learners\.

1. 1\.Aggregate\(Algorithm[1](https://arxiv.org/html/2610.28878#alg1)\): Operates on a fixed tuple𝐪=\(q1,…,qk\)∈ℱk\\mathbf\{q\}=\(q\_\{1\},\\dots,q\_\{k\}\)\\in\\mathcal\{F\}^\{k\}\. It draws\(Z1,…,Zk\)\(Z\_\{1\},\\dots,Z\_\{k\}\)via the grand coupling and aggregates them with the stability\-based mode\. Its privacy \(under tuple\-level change\-one adjacency\) follows directly from the construction of the grand coupling, while its utility follows from the disagreement bound and the accuracy of the stability\-based mode mechanism\.
2. 2\.Sampler\(Algorithm[2](https://arxiv.org/html/2610.28878#alg2)\): Operates on raw datasetsS∈𝒳nS\\in\\mathcal\{X\}^\{n\}, partitioningSSto form𝐪\\mathbf\{q\}before invokingAggregate\. It inherits the guarantees of Stage 1, and we can lift the privacy to standard change\-one adjacency on𝒳n\\mathcal\{X\}^\{n\}since changing one data point affects a single block in𝐪\\mathbf\{q\}, while utility follows by combining Hoeffding’s inequality over the block partition with the utility guarantees ofAggregate\.

We defer the detailed proofs and discussions in Appendix[B](https://arxiv.org/html/2610.28878#A2)\.

### 4\.1Tuple\-Level Primitive:Aggregate

We first presentAggregate\(Algorithm[1](https://arxiv.org/html/2610.28878#alg1)\), a mechanism operating on a fixed tuple of candidate distributions𝐪=\(q1,…,qk\)∈ℱk\\q=\(q\_\{1\},\\dots,q\_\{k\}\)\\in\\mathcal\{F\}^\{k\}to output a synthetic candidateZ∈𝒳ℓZ\\in\\X^\{\\ell\}\. Analysis in this subsection is purely with respect to tuple\-level adjacency, where neighboring inputs𝐪,𝐪′\\mathbf\{q\},\\mathbf\{q\}^\{\\prime\}differ in a single distribution coordinateqjq\_\{j\}\.

Algorithm 1Aggregate1:Distributions

q1,…,qk∈ℱq\_\{1\},\\ldots,q\_\{k\}\\in\\mathcal\{F\}\.

2:Synthetic dataset

Z∈𝒳ℓZ\\in\\X^\{\\ell\}
3:Jointly sample

\(Z1,…,Zk\)←𝖢𝗈𝗎𝗉𝗅𝖾k​\(q1ℓ,…,qkℓ\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)\\leftarrow\\mathsf\{Couple\}\_\{k\}\(q\_\{1\}^\{\\ell\},\\ldots,q\_\{k\}^\{\\ell\}\)//𝖢𝗈𝗎𝗉𝗅𝖾k\\mathsf\{Couple\}\_\{k\}is a finite\-dimensional marginal of a valid grand coupling scheme on𝒫=\{qℓ:q∈ℱ\}\\mathcal\{P\}=\\\{q^\{\\ell\}:q\\in\\mathcal\{F\}\\\}, which can be instantiated by either𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨\\mathsf\{Couple\\\_I\}in Algorithm[5](https://arxiv.org/html/2610.28878#alg5)or𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨𝖨\\mathsf\{Couple\\\_II\}in Algorithm[6](https://arxiv.org/html/2610.28878#alg6)

4:

Z=𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾⁡\(Z1,…,Zk\)Z=\\mathsf\{StabilityBasedMode\}\(Z\_\{1\},\.\.\.,Z\_\{k\}\)
5:return

ZZ\.

By instantiating𝖢𝗈𝗎𝗉𝗅𝖾k\\mathsf\{Couple\}\_\{k\}with a valid grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}444e\.g\., Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)if a common dominating measure exists, or Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)for general standard Borel spaces, it produces a joint measurable vector\(Z1,…,Zk\)\(Z\_\{1\},\\dots,Z\_\{k\}\), for any input tuple𝐪\\q, such thatZi∼qiℓZ\_\{i\}\\sim q\_\{i\}^\{\\ell\}andPr\[Zi≠Zj\]≤2TV\(qiℓ,qjℓ\)\\Pr\[Z\_\{i\}\\neq Z\_\{j\}\]\\leq 2\\TV\(q\_\{i\}^\{\\ell\},q\_\{j\}^\{\\ell\}\)for alli≠ji\\neq j\. We next show that: \(i\) the privacy guarantee of𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}transfers directly toAggregate, and \(ii\) if a large majority of the input distributionsqiq\_\{i\}are close to a target ground\-truth distributionppin TV, the output ofAggregatematches an ideal draw frompℓp^\{\\ell\}with high probability\.

###### Theorem 4\.1\(Informal version of Corollary[B\.4](https://arxiv.org/html/2610.28878#A2.Thmtheorem4)\)\.

For everyε\>0\\varepsilon\>0,δ,β∈\(0,1\)\\delta,\\beta\\in\(0,1\),ℓ∈ℕ\+\\ell\\in\\mathbb\{N\}^\{\+\}, andk=Ω⁡\(log⁡\(4/β\)\+log⁡\(1/δ\)ε\)k=\\Omega\\left\(\\frac\{\\log\(4/\\beta\)\+\\log\(1/\\delta\)\}\{\\varepsilon\}\\right\),Aggregateis\(ε,δ\)\(\\varepsilon,\\delta\)\-DP555With respect to tuple\-level adjacency, where neighboring inputs differ in a single distributionqiq\_\{i\}\.\. Moreover, for anyp∈𝒬p\\in\\Qand input tuple𝐪∈ℱk\\q\\in\\mathcal\{F\}^\{k\}, if at least7/87/8of the input distributions areO⁡\(β/ℓ\)O\(\\beta/\\ell\)\-close toppin TV, then the law of its output isβ/2\\beta/2\-close topℓp^\{\\ell\}in TV\.

###### Proof Sketch\.

Privacy:Since the joint law of𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\\mathsf\{Couple\}\_\{k\}\(\\q\)is a finite\-dimensional marginal of the global measureΓ𝒫\\Gamma\_\{\\P\}666For𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨\\mathsf\{Couple\\\_I\}\(Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)\), the joint law of\(Z1,…,Zk\)∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\(Z\_\{1\},\\dots,Z\_\{k\}\)\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\q\)\)is the\(q1ℓ,…,qkℓ\)\(q\_\{1\}^\{\\ell\},\\dots,q\_\{k\}^\{\\ell\}\)\-coordinate marginal of the explicit couplingΓ\\Gammaon𝒫=\{qℓ:q∈ℱ\}\\P=\\\{q^\{\\ell\}:q\\in\\mathcal\{F\}\\\}\. For𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨𝖨\\mathsf\{Couple\\\_II\}\(Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)\), it is the corresponding finite\-dimensional marginal of the grand couplingΓ∞\\Gamma\_\{\\infty\}on𝒴Δ⁡\(𝒴\)\\mathcal\{Y\}^\{\\Delta\(\\mathcal\{Y\}\)\}, where𝒴=𝒳ℓ\\mathcal\{Y\}=\\mathcal\{X\}^\{\\ell\}\., we evaluate executions on neighboring tuples𝐪\\qand𝐪′\\q^\{\\prime\}on a single shared probability space\. Specifically, we construct an analysis coupling from a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\P\}\\sim\\Gamma\_\{\\P\}, settingZ~i=Zqiℓ\\tilde\{Z\}\_\{i\}=Z\_\{q\_\{i\}^\{\\ell\}\}for input𝐪\\qandZ~i′=Z\(qi′\)ℓ\\tilde\{Z\}^\{\\prime\}\_\{i\}=Z\_\{\(q\_\{i\}^\{\\prime\}\)^\{\\ell\}\}for input𝐪′\\q^\{\\prime\}\. For every unchanged coordinatei≠ji\\neq j,qi=qi′q\_\{i\}=q\_\{i\}^\{\\prime\}impliesZqiℓ=Z\(qi′\)ℓZ\_\{q\_\{i\}^\{\\ell\}\}=Z\_\{\(q\_\{i\}^\{\\prime\}\)^\{\\ell\}\}pointwise\. Consequently, the realized input vectors\(Z~1,…,Z~k\)\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\)and\(Z~1′,…,Z~k′\)\(\\tilde\{Z\}^\{\\prime\}\_\{1\},\\dots,\\tilde\{Z\}^\{\\prime\}\_\{k\}\)differ in at most a single coordinatejjfor*every realization*ofΓ𝒫\\Gamma\_\{\\P\}\. Therefore, since neighboring input tuples yield pointwise neighboring vectors underΓ𝒫\\Gamma\_\{\\P\}, taking expectations overΓ𝒫\\Gamma\_\{\\P\}transfer the DP guarantee of𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}directly toAggregate\.

Utility:As in the privacy analysis, the utility guarantee relies on constructing an analysis coupling from the grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}\. Specifically, for input distributions𝐪=\(q1,…,qk\)∈ℱk\\q=\(q\_\{1\},\\dots,q\_\{k\}\)\\in\\mathcal\{F\}^\{k\}and a target distributionp∈ℱp\\in\\mathcal\{F\}, we take a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\P\}\\sim\\Gamma\_\{\\P\}and defineZ~i=Zqiℓ\\tilde\{Z\}\_\{i\}=Z\_\{q\_\{i\}^\{\\ell\}\}for eachi∈\[k\]i\\in\[k\], alongside an unobserved “ghost” sampleZ~∗=Zpℓ\\tilde\{Z\}\_\{\*\}=Z\_\{p^\{\\ell\}\}, indexed by the ground\-truth product distributionpℓ∈𝒫p^\{\\ell\}\\in\\P\. Sinceℒ​\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)\)andℒ​\(𝖢𝗈𝗎𝗉𝗅𝖾1​\(𝐩\)\)\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{1\}\(\\mathbf\{p\}\)\)are simply a finite\-dimensional marginal of the global measureΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}, our construction from the grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}satisfies\(Z~1,…,Z~k\)∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\(\\tilde\{Z\}\_\{1\},\.\.\.,\\tilde\{Z\}\_\{k\}\)\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)\)andZ~∗∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾1​\(p\)\)=pℓ\\tilde\{Z\}\_\{\*\}\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{1\}\(p\)\)=p^\{\\ell\}, by property G3 and G1 from Definition[3\.1](https://arxiv.org/html/2610.28878#S3.Thmtheorem1)\)\.

For every accurate input distribution whereTV⁡\(qi,p\)≤η\\TV\(q\_\{i\},p\)\\leq\\eta, property G2 bounds the disagreement byPr\[Z~i≠Z~∗\]≤2TV\(qiℓ,pℓ\)≤2ℓη\\Pr\[\\tilde\{Z\}\_\{i\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq 2\\TV\(q\_\{i\}^\{\\ell\},p^\{\\ell\}\)\\leq 2\\ell\\eta\. When7/87/8of theqiq\_\{i\}areη\\eta\-close topp, an overwhelming majority of the coupled samplesZ~i\\tilde\{Z\}\_\{i\}collapse onto the exact same realizationZ~∗∼pℓ\\tilde\{Z\}\_\{\*\}\\sim p^\{\\ell\}pointwise\. This manufactures the frequency gap required for𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}\[[46](https://arxiv.org/html/2610.28878#bib.bib47),[47](https://arxiv.org/html/2610.28878#bib.bib36)\]to outputZ~∗\\tilde\{Z\}\_\{\*\}with probability≥1−δ0\\geq 1\-\\delta\_\{0\}\.

We emphasize that neitherZ~∗\\tilde\{Z\}\_\{\*\}norZ~i′\\tilde\{Z\}^\{\\prime\}\_\{i\}is computed by the algorithm, and they are introduced purely for the analysis\. Full technical details appear in Proposition[B\.2](https://arxiv.org/html/2610.28878#A2.Thmtheorem2), Proposition[B\.1](https://arxiv.org/html/2610.28878#A2.Thmtheorem1), and Corollary[B\.4](https://arxiv.org/html/2610.28878#A2.Thmtheorem4)\. ∎

### 4\.2End\-to\-End Private Correlated Sampler:Sampler

In the preceding subsection, we established the privacy and utility guarantees ofAggregateconditioned on a fixed tuple of candidate distributions𝐪=\(q1,…,qk\)\\q=\(q\_\{1\},\\dots,q\_\{k\}\)\. We now lift these guarantees to the full end\-to\-end pipeline,Sampler\(Algorithm[2](https://arxiv.org/html/2610.28878#alg2)\), where input distributions are learned from disjoint blocks of a raw datasetS=\(X1,…,Xn\)∈𝒳nS=\(X\_\{1\},\\dots,X\_\{n\}\)\\in\\X^\{n\}\. The algorithm partitionsSSinto disjoint blocks, runs the base learner on each block to obtain the random tuple𝐪\\q, and then appliesAggregate\. Here, privacy is naturally defined at the dataset level, where two datasetsS,S′∈𝒳nS,S^\{\\prime\}\\in\\mathcal\{X\}^\{n\}are adjacent if they differ in a single record\.

Algorithm 2Sampler1:Dataset

S=\(X1,…,Xn\)S=\(X\_\{1\},\\ldots,X\_\{n\}\)with

n=b​kn=bk\. Number of blocks

kk\.

2:Synthetic samples

Z∈𝒳ℓZ\\in\\X^\{\\ell\}
3:Let a random seed \(a data\-independent permutation\) be

Π∼U⁡\(𝒮n\)\\Pi\\sim\\mathrm\{U\}\(\\mathcal\{S\}\_\{n\}\)
4:Partition

SSinto

kkdisjoint blocks

S1,…,Sk∈𝒳bS\_\{1\},\\ldots,S\_\{k\}\\in\\X^\{b\}, by setting

Si←\(XΠ⁡\(\(i−1\)​b\+1\),…,XΠ⁡\(i​b\)\)S\_\{i\}\\leftarrow\(X\_\{\\Pi\(\(i\-1\)b\+1\)\},\.\.\.,X\_\{\\Pi\(ib\)\}\)
5:Let learners’ random seeds \(data\- and permutation\-independent\) be

U1,…,Uk​∼i\.i\.d\.​U​\(\[0,1\]\)U\_\{1\},\.\.\.,U\_\{k\}\\overset\{\\text\{i\.i\.d\.\}\}\{\\sim\}\\mathrm\{U\}\(\[0,1\]\)\.

6:For each

i∈\[k\]i\\in\[k\], compute

qi←L⁡\(Si,Ui\)q\_\{i\}\\leftarrow L\(S\_\{i\};U\_\{i\}\)
7:

Z←Aggregate​\(q1,…,qk\)Z\\leftarrow\\textsc\{Aggregate\}\(q\_\{1\},\\ldots,q\_\{k\}\)
8:return

Z∈𝒳ℓZ\\in\\X^\{\\ell\}

While much of the analysis relies on standard techniques, the primary technical step lies in explicitly controlling the sources of randomness to bridgeAggregateandSampler, ensuring that the resulting random tuple satisfies the conditions required byAggregate\.

###### Theorem 4\.3\(Informal version of Corollary[B\.7](https://arxiv.org/html/2610.28878#A2.Thmtheorem7)\)\.

Fix a base learnerLLfor𝒬\\Q\. For everyε,δ,β∈\(0,1\)\\varepsilon,\\delta,\\beta\\in\(0,1\)andℓ∈ℕ\+\\ell\\in\\mathbb\{N\}^\{\+\}, letbbbe a sample size such that, for everyp∈𝒬p\\in\\Q,LLachievesTV⁡\(L⁡\(Si\),p\)≤O⁡\(β/ℓ\)\\TV\(L\(S\_\{i\}\),p\)\\leq O\(\\beta/\\ell\)with probability at least15/1615/16givenSi∼pbS\_\{i\}\\sim p^\{b\}\. Then,Samplersatisfies dataset\-level\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\. Moreover, for everyp∈𝒬p\\in\\Q, givenS∼pnS\\sim p^\{n\}withn=Ω⁡\(b​log⁡\(4/δ​β\)ε\)n=\\Omega\\left\(\\frac\{b\\log\(4/\\delta\\beta\)\}\{\\varepsilon\}\\right\), it outputs a synthetic datasetZ∈𝒳ℓZ\\in\\mathcal\{X\}^\{\\ell\}satisfyingTV⁡\(ℒ⁡\(Z\),pℓ\)≤3​β/4\\TV\(\\mathcal\{L\}\(Z\),p^\{\\ell\}\)\\leq 3\\beta/4\. Thus,Sampleris an\(ℓ,3​β/4\)\(\\ell,3\\beta/4\)\-approximate sampler for𝒬\\Qin the sense of Definition[1\.4](https://arxiv.org/html/2610.28878#S1.Thmtheorem4)\.

###### Proof Sketch\.

Privacy:Fix adjacent datasetsS,S′∈𝒳nS,S^\{\\prime\}\\in\\X^\{n\}differing at recordjj\. For any realization of the permutationΠ\\Pi, the record that differs in the two worlds falls into a unique block indexaa\. Since all other blocks,SiS\_\{i\}fori≠ai\\neq a, remain identical, and the base learner’s internal randomnessU1,…,UkU\_\{1\},\\dots,U\_\{k\}is drawn independently of input dataSS, the output tuples𝐪=L⁡\(S\)\\q=L\(S\)and𝐪′=L⁡\(S′\)\\q^\{\\prime\}=L\(S^\{\\prime\}\)differ in at most coordinateaa\. Taking an expectation over the data\-independent randomness, i\.e\., the random permutation for data partition and the learners’ random seeds, the tuple\-level DP guarantee ofAggregate, shown in Theorem[4\.1](https://arxiv.org/html/2610.28878#S4.Thmtheorem1), directly lifts to dataset\-level\(ε,δ\)\(\\varepsilon,\\delta\)\-DP forSampler\.

Utility:Define indicator variablesIi=1\{TV\(qi,p\)≤η\}I\_\{i\}=1\\\{\\TV\(q\_\{i\},p\)\\leq\\eta\\\}forη=O⁡\(β/ℓ\)\\eta=O\(\\beta/\\ell\)\. SinceS∼pnS\\sim p^\{n\}i\.i\.d\., the blocksSiS\_\{i\}are i\.i\.d\. draws frompbp^\{b\}, makingI1,…,IkI\_\{1\},\\dots,I\_\{k\}i\.i\.d\. Bernoulli variables with meanE​\[Ii\]≥15/16\\mbox\{\\bf E\}\[I\_\{i\}\]\\geq 15/16\. By Hoeffding’s inequality, settingk=O⁡\(log⁡\(1/β\)\)k=O\(\\log\(1/\\beta\)\)ensures that∑i=1kIi≥78​k\\sum\_\{i=1\}^\{k\}I\_\{i\}\\geq\\frac\{7\}\{8\}kholds with probability at least1−β/41\-\\beta/4\. Conditioning on thisgood event=\|\{TV\(qi,p\)≤η\}\|≥78k\\text\{good event\}=\|\\\{\\TV\(q\_\{i\},p\)\\leq\\eta\\\}\|\\geq\\frac\{7\}\{8\}k, Theorem[4\.1](https://arxiv.org/html/2610.28878#S4.Thmtheorem1)guarantees that the output distributionℒ⁡\(Z∣good event\)\\mathcal\{L\}\(Z\\mid\\text\{good event\}\)satisfiesTV⁡\(ℒ⁡\(Z∣good event\),pℓ\)≤β/2\\TV\(\\mathcal\{L\}\(Z\\mid\\text\{good event\}\),p^\{\\ell\}\)\\leq\\beta/2\. Combining the failure probability of the concentration with the conditional TV error yieldsTV⁡\(ℒ⁡\(Z\),pℓ\)≤β/2\+β/4=34​β\\TV\(\\mathcal\{L\}\(Z\),p^\{\\ell\}\)\\leq\\beta/2\+\\beta/4=\\frac\{3\}\{4\}\\beta\.

Full technical details appear in Proposition[B\.5](https://arxiv.org/html/2610.28878#A2.Thmtheorem5)and Proposition[B\.6](https://arxiv.org/html/2610.28878#A2.Thmtheorem6)\. ∎

## 5Main algorithm and reduction

We now present our main application, a black\-box reduction that transforms any non\-private base learnerLLinto a DP learner viaSampler\. Letm⁡\(α,β\)m\(\\alpha,\\beta\)denote the non\-private sample complexity ofLLfor outputting anα\\alpha\-accurate estimate in terms of TV, with probability at least1−β1\-\\beta\.

The algorithm is conceptually simple, where we first invokeSamplerto generate a private synthetic datasetZ∈𝒳ℓZ\\in\\mathcal\{X\}^\{\\ell\}, and then apply the non\-private learnerLLto the private synthetic datasetZZusing an independent random seedVV\.

The complete procedure is described in Algorithm[3](https://arxiv.org/html/2610.28878#alg3)\.

The results follows immediately from the guarantees ofSampler\. Privacy follows by post\-processing, and utility follows by coupling its output to an i\.i\.d\. sample frompℓp^\{\\ell\}and union\-bounding the coupling mismatch with the learner’s failure event\. The main privacy and utility guarantees ofPrivateLearnerare established in the following theorem\.

Algorithm 3BlackBoxPrivateLearner1:Dataset

S=\(X1,…,Xn\)S=\(X\_\{1\},\\ldots,X\_\{n\}\)
2:A distribution

q^∈Δ⁡\(X\)\\hat\{q\}\\in\\Delta\(X\)
3:

Z←Sampler​\(S\)Z\\leftarrow\\textsc\{Sampler\}\(S\)
4:Pick a learner’s random seed \(data\-independent\)

V∼U⁡\(\[0,1\]\)V\\sim\\mathrm\{U\}\(\[0,1\]\)and

q^←L⁡\(Z,V\)\\hat\{q\}\\leftarrow L\(Z;V\)
5:return

q^\\hat\{q\}

###### Theorem 5\.1\(Main Reduction\)\.

Letα,β,δ,ε∈\(0,1\)\\alpha,\\beta,\\delta,\\varepsilon\\in\(0,1\)be parameters, andLLbe a non\-private learner for𝒬\\Qwith sample complexitym⁡\(α,β\)m\(\\alpha,\\beta\)\. Then,BlackBoxPrivateLearner\(Algorithm[3](https://arxiv.org/html/2610.28878#alg3)\) is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\. Moreover, there is a sample size

n=O⁡\(m⁡\(β64​m​\(α,β4\),116\)​1ε​log⁡\(4β​δ\)\)n=O\\left\(m\\left\(\\frac\{\\beta\}\{64m\\left\(\\alpha,\\frac\{\\beta\}\{4\}\\right\)\},\\frac\{1\}\{16\}\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\beta\\delta\}\\right\)\\right\)such that, for everyp∈𝒬p\\in\\Q, givenS∼pnS\\sim p^\{n\}, the outputq^\\hat\{q\}satisfiesTV⁡\(q^,p\)<α\\TV\(\\hat\{q\},p\)<\\alphawith probability at least1−β1\-\\beta\.

###### Proof\.

Setℓ=m⁡\(α,β4\)\\ell=m\\left\(\\alpha,\\frac\{\\beta\}\{4\}\\right\),η=β64​ℓ\\eta=\\frac\{\\beta\}\{64\\ell\},b=m⁡\(η,116\)b=m\\left\(\\eta,\\frac\{1\}\{16\}\\right\), andδ0=min⁡\{δ,β4\}\\delta\_\{0\}=\\min\\left\\\{\\delta,\\frac\{\\beta\}\{4\}\\right\\\}\. By Proposition[B\.5](https://arxiv.org/html/2610.28878#A2.Thmtheorem5),Sampleris\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\. ApplyingLLto its output using independent randomness preserves privacy by post\-processing \(Proposition[2\.4](https://arxiv.org/html/2610.28878#S2.Thmtheorem4)\)\. Sinceδ0≤δ\\delta\_\{0\}\\leq\\delta, the resulting learner is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\.

For utility, takek=⌈max⁡\{8ε​log⁡\(4β​δ\),128​log⁡\(4β\)\}⌉k=\\left\\lceil\\max\\left\\\{\\frac\{8\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\beta\\delta\}\\right\),128\\log\\left\(\\frac\{4\}\{\\beta\}\\right\)\\right\\\}\\right\\rceilandn=b​kn=bk\. This choice satisfies both the stability requirement and the concentration bound in Corollary[B\.7](https://arxiv.org/html/2610.28878#A2.Thmtheorem7)\. Hence, for everyp∈𝒬p\\in\\QandS∼pnS\\sim p^\{n\}, the synthetic outputZZsatisfiesTV⁡\(ℒ⁡\(Z\),pℓ\)≤3​β4\\TV\\left\(\\mathcal\{L\}\(Z\),p^\{\\ell\}\\right\)\\leq\\frac\{3\\beta\}\{4\}\. By the choice ofℓ\\ell, the learner fails to achieve TV error strictly belowα\\alphaon an i\.i\.d\. sample frompℓp^\{\\ell\}with probability at mostβ4\\frac\{\\beta\}\{4\}\. Transferring this failure bound using union bound across the TV distance givesPr\[TV\(q^,p\)≥α\]≤β4\+3​β4=β\\Pr\\left\[\\TV\(\\hat\{q\},p\)\\geq\\alpha\\right\]\\leq\\frac\{\\beta\}\{4\}\+\\frac\{3\\beta\}\{4\}=\\beta\.

Finally, substituting the value ofbbandk=O⁡\(1ε​log⁡\(4β​δ\)\)k=O\\left\(\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\beta\\delta\}\\right\)\\right\)inton=b​kn=bkgives the claimed sample complexity\. ∎

## 6A Boosted Private Learner

In the previous section, thePrivateLearnerrequires the block\-level target TV error to satisfyη≲β/ℓ\\eta\\lesssim\\beta/\\ell\. When the non\-private sample complexity scales polynomially with accuracy, i\.e\.,m⁡\(α,β\)=poly⁡\(1/α,log⁡\(1/β\)\)m\(\\alpha,\\beta\)=\\mathrm\{poly\}\(1/\\alpha,\\log\(1/\\beta\)\), settingη∝β\\eta\\propto\\betaintroduces an undesirable polynomial dependence1/βΩ⁡\(1\)1/\\beta^\{\\Omega\(1\)\}into the overall sample complexitynn\. To get rid of this polynomial dependence and achieve a better logarithmic overheadO⁡\(log⁡\(1/β\)\)O\(\\log\(1/\\beta\)\), we introduce a boosted version,BoostedLearnerin Algorithm[4](https://arxiv.org/html/2610.28878#alg4)\.

The core idea is confidence boosting: amplifying a learner’s constant success probability to1−β1\-\\betathrough independent repetition and robust aggregation\. We runPrivateLearnerindependently onT=O⁡\(log⁡\(1/β\)\)T=O\(\\log\(1/\\beta\)\)disjoint blocksS1,…,STS\_\{1\},\\dots,S\_\{T\}with a fixed constant success probability1−β01\-\\beta\_\{0\}\(e\.g\.,β0=1/8\\beta\_\{0\}=1/8\), obtaining estimatesp^1,…,p^T\\hat\{p\}\_\{1\},\\dots,\\hat\{p\}\_\{T\}\. This requires a block accuracy of onlyη∼1/ℓ\\eta\\sim 1/\\ell, independent of the final target failure probabilityβ\\beta\. For eacht∈\[T\]t\\in\[T\],Nt=\|\{i∈\[T\]:TV⁡\(p^i,p^t\)≤2​α0\}\|N\_\{t\}=\|\\\{i\\in\[T\]:\\TV\(\\hat\{p\}\_\{i\},\\hat\{p\}\_\{t\}\)\\leq 2\\alpha\_\{0\}\\\}\|counts how many estimates are within TV distance2​α02\\alpha\_\{0\}ofp^t\\hat\{p\}\_\{t\}, whereα0=α/3\\alpha\_\{0\}=\\alpha/3\. We selectjjmaximizingNjN\_\{j\}and returnp^j\\hat\{p\}\_\{j\}\.

By doing so, if more than half of the estimates areα0\\alpha\_\{0\}\-close topp, they are all within2​α02\\alpha\_\{0\}of one another\. Thus, every such estimate hasNt\>T/2N\_\{t\}\>T/2, and the maximizing estimate also hasNj\>T/2N\_\{j\}\>T/2\. Among the estimates counted byNjN\_\{j\}, at least one must therefore beα0\\alpha\_\{0\}\-close topp, and thusTV⁡\(p^j,p\)≤2​α0\+α0=α\\TV\(\\hat\{p\}\_\{j\},p\)\\leq 2\\alpha\_\{0\}\+\\alpha\_\{0\}=\\alpha\. Each run fails with probability at mostβ0\\beta\_\{0\}, and by independence, the probability of failing to obtain a majority of accurate estimates decreases exponentially inTT\. See[D](https://arxiv.org/html/2610.28878#A4)for the formal proof\.

Algorithm 4BoostedLearner1:Dataset

S=\(X1,…,Xn\)S=\(X\_\{1\},\\ldots,X\_\{n\}\), a non\-private learner

LL, target accuracy

α\\alpha, target failure probability

β\\beta, and privacy parameters

\(ε,δ\)\(\\varepsilon,\\delta\)\.

2:A distribution

q^∈Δ⁡\(𝒳\)\\hat\{q\}\\in\\Delta\(\\X\)
3:Set target base parameter

α0←α/3\\alpha\_\{0\}\\leftarrow\\alpha/3, constant failure rate

β0←1/8\\beta\_\{0\}\\leftarrow 1/8, privacy target

δ0←min⁡\{δ,β0/4\}\\delta\_\{0\}\\leftarrow\\min\\\{\\delta,\\beta\_\{0\}/4\\\}\.

4:Set partition count

T←⌈128​ln⁡\(1/β\)⌉T\\leftarrow\\left\\lceil 128\\ln\(1/\\beta\)\\right\\rceil
5:Partition

SSinto

TTdisjoint subsets

S1,…,ST∈𝒳cS\_\{1\},\\dots,S\_\{T\}\\in\\mathcal\{X\}^\{c\}, each of size

c=O⁡\(log⁡\(1/\(β0​δ0\)\)ε⋅m⁡\(β064​m​\(α0,β0/4\),116\)\)c=O\\left\(\\frac\{\\log\(1/\(\\beta\_\{0\}\\delta\_\{0\}\)\)\}\{\\varepsilon\}\\cdot m\\left\(\\frac\{\\beta\_\{0\}\}\{64\\,m\(\\alpha\_\{0\},\\beta\_\{0\}/4\)\},\\frac\{1\}\{16\}\\right\)\\right\)
6:foreach

t∈\[T\]t\\in\[T\]in paralleldo

7:Obtain base estimate:

p^t←PrivateLearner​\(St,α0,β0,ε,δ0\)\\hat\{p\}\_\{t\}\\leftarrow\\textsc\{PrivateLearner\}\(S\_\{t\},\\alpha\_\{0\},\\beta\_\{0\},\\varepsilon,\\delta\_\{0\}\)\.

8:endfor

9:For each

t∈\[T\]t\\in\[T\], compute candidate ball size,

Nt←\|\{i∈\[T\]:TV⁡\(p^t,p^i\)≤23​α\}\|N\_\{t\}\\leftarrow\\left\|\{\}\\\{i\\in\[T\]:\\mathrm\{TV\}\(\\hat\{p\}\_\{t\},\\hat\{p\}\_\{i\}\)\\leq\\frac\{2\}\{3\}\\alpha\\\}\\right\|\{\}\.

10:Find

j=arg⁡maxi∈\[T\]⁡Nij=\\arg\\max\_\{i\\in\[T\]\}N\_\{i\}
11:return

p^j\\hat\{p\}\_\{j\}

###### Theorem 6\.1\(Boosted Private Learner\)\.

Letα,β,ε,δ∈\(0,1\)\\alpha,\\beta,\\varepsilon,\\delta\\in\(0,1\)be parameters, andLLbe a non\-private learner for𝒬\\Qwith sample complexitym⁡\(α,β\)m\(\\alpha,\\beta\)\. Then,BoostedLearner\(Algorithm[4](https://arxiv.org/html/2610.28878#alg4)\) is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\. Moreover, there is a sample size

n=O⁡\(m⁡\(1512​m​\(α/3,1/32\),116\)​1ε​log⁡\(4δ\)​log⁡\(4β\)\)n=O\\left\(m\\left\(\\frac\{1\}\{512m\\left\(\\alpha/3,1/32\\right\)\},\\frac\{1\}\{16\}\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\delta\}\\right\)\\log\\left\(\\frac\{4\}\{\\beta\}\\right\)\\right\)such that, for everyp∈𝒬p\\in\\Q, givenS∼pnS\\sim p^\{n\}, the outputq^\\hat\{q\}satisfiesTV⁡\(q^,p\)<α\\TV\(\\hat\{q\},p\)<\\alphawith probability at least1−β1\-\\beta\. In particular, ifm⁡\(α,β\)=poly⁡\(1α,log⁡\(1β\)\)m\(\\alpha,\\beta\)=\\operatorname\{poly\}\\left\(\\frac\{1\}\{\\alpha\},\\log\\left\(\\frac\{1\}\{\\beta\}\\right\)\\right\), thenn=poly⁡\(1α,log⁡\(1β\),1ε,log⁡\(1δ\)\)n=\\operatorname\{poly\}\\left\(\\frac\{1\}\{\\alpha\},\\log\\left\(\\frac\{1\}\{\\beta\}\\right\),\\frac\{1\}\{\\varepsilon\},\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\\right\)\.

Note that the DP guarantee is non\-trivial only whenδ=o⁡\(1/n\)\\delta=o\(1/n\), since allowingδ=Ω⁡\(1/n\)\\delta=\\Omega\(1/n\)permits the learner to randomly select a user’s data to output each run\[[42](https://arxiv.org/html/2610.28878#bib.bib41)\]\. Our sample complexity bound is meaningful in this regime because of its dependence onδ\\deltaonly through alog⁡\(1/δ\)\\log\(1/\\delta\)factor\. Specifically, rewriting the sample complexity in Theorem[6\.1](https://arxiv.org/html/2610.28878#S6.Thmtheorem1)asn⁡\(δ\)=C​log⁡\(4/δ\)n\(\\delta\)=C\\log\(4/\\delta\), whereCCcollects other factors independent ofδ\\delta, we haveδ⋅n⁡\(δ\)=C​δ​log⁡\(4/δ\)→0\\delta\\cdot n\(\\delta\)=C\\delta\\log\(4/\\delta\)\\to 0asδ→0\\delta\\to 0, that is,δ=o⁡\(1/n\)\\delta=o\(1/n\)\. In contrast, a dependence of the formn⁡\(δ\)=C/δn\(\\delta\)=C/\\deltawould giveδ⋅n⁡\(δ\)=C\\delta\\cdot n\(\\delta\)=C, soδ=Θ⁡\(1/n\)\\delta=\\Theta\(1/n\), which falls back to the trivial regime\.

## Acknowledgements

We thank David Woodruff for discussions and assistance with the internal version of Gemini used\. We also thank Matthew Joseph and Chris Liaw for their comments on a preliminary draft of this paper\.

## References

- \[AAK21a\]I\. Aden\-Ali, H\. Ashtiani, and G\. Kamath\(2021\)On the sample complexity of privately learning unbounded high\-dimensional gaussians\.InProceedings of the 32nd International Conference on Algorithmic Learning Theory,ALT ’21,pp\. 185–216\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[AAL21b\]I\. Aden\-Ali, H\. Ashtiani, and C\. Liaw\(2021\)Privately learning mixtures of axis\-aligned gaussians\.Advances in Neural Information Processing Systems34,pp\. 3925–3938\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[AAL24\]M\. Afzali, H\. Ashtiani, and C\. Liaw\(2024\)Mixtures of gaussians are privately learnable with a polynomial number of samples\.InProceedings of The 35th International Conference on Algorithmic Learning Theory,Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1),[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[AAL25\]M\. Afzali, H\. Ashtiani, and C\. Liaw\(2025\)Agnostic private density estimation for gmms via list global stability\.InProceedings of The 36th International Conference on Algorithmic Learning Theory,Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1),[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[AKT\+23\]D\. Alabi, P\. K\. Kothari, P\. Tankala, P\. Venkat, and F\. Zhang\(2023\)Privately estimating a Gaussian: efficient, robust and optimal\.InProceedings of the 55th Annual ACM Symposium on the Theory of Computing,STOC ’23\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[ALM\+19\]N\. Alon, R\. Livni, M\. Malliaris, and S\. Moran\(2019\)Private pac learning implies finite littlestone dimension\.InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,pp\. 852–860\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p6.1),[Remark 4\.4](https://arxiv.org/html/2610.28878#S4.Thmtheorem4.p1.1.1)\.
- \[AS19\]O\. Angel and Y\. Spinka\(2019\)Pairwise optimal coupling of multiple random variables\.External Links:1903\.00632Cited by:[§A\.1](https://arxiv.org/html/2610.28878#A1.SS1.p1.1),[Theorem A\.2](https://arxiv.org/html/2610.28878#A1.Thmtheorem2),[Appendix A](https://arxiv.org/html/2610.28878#A1.p1.1),[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p5.1),[§1\.3](https://arxiv.org/html/2610.28878#S1.SS3.p2.1),[§2](https://arxiv.org/html/2610.28878#S2.p4.1),[§3](https://arxiv.org/html/2610.28878#S3.p2.1),[Remark 4\.2](https://arxiv.org/html/2610.28878#S4.Thmtheorem2.p1.1.1),[footnote 7](https://arxiv.org/html/2610.28878#footnote7),[footnote 8](https://arxiv.org/html/2610.28878#footnote8)\.
- \[ABH\+20\]H\. Ashtiani, S\. Ben\-David, N\. J\. Harvey, C\. Liaw, A\. Mehrabian, and Y\. Plan\(2020\)Near\-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes\.Journal of the ACM67\(6\),pp\. 32:1–32:42\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p1.1)\.
- \[AL22\]H\. Ashtiani and C\. Liaw\(2022\)Private and polynomial time algorithms for learning Gaussians and beyond\.InProceedings of the 35th Annual Conference on Learning Theory,COLT ’22,pp\. 1075–1076\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1),[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[AMN24\]H\. Ashtiani, M\. Majid, and S\. Narayanan\(2024\)Sample\-efficient private learning of mixtures of gaussians\.Advances in Neural Information Processing Systems37,pp\. 98994–99039\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[ASH22\]H\. Ashtiani\(2022\)Private learning of gaussians and their mixtures\.Note:[https://www\.youtube\.com/watch?v=bmNjm0lx50I](https://www.youtube.com/watch?v=bmNjm0lx50I)Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[AUZ23\]H\. Asi, J\. Ullman, and L\. Zakynthinou\(2023\)From robustness to privacy and back\.InProceedings of the 40th International Conference on Machine Learning,ICML ’23,pp\. 1121–1146\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[BBC\+23a\]S\. Ben\-David, A\. Bie, C\. L\. Canonne, G\. Kamath, and V\. Singhal\(2023\)Private distribution learning with public data: the view from sample compression\.InAdvances in Neural Information Processing Systems 36,NeurIPS ’23,pp\. 7184–7215\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[BBK\+23b\]S\. Ben\-David, A\. Bie, G\. Kamath, and T\. Lechner\(2023\)Distribution learnability and robustness\.InAdvances in Neural Information Processing Systems 36,NeurIPS ’23,pp\. 52732–52758\.Cited by:[§1\.1](https://arxiv.org/html/2610.28878#S1.SS1.p4.1)\.
- \[BDK\+20\]S\. Biswas, Y\. Dong, G\. Kamath, and J\. Ullman\(2020\)CoinPress: practical private mean and covariance estimation\.InAdvances in Neural Information Processing Systems 33,NeurIPS ’20,pp\. 14475–14485\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[BKM\+24\]M\. Bun, G\. Kamath, A\. Mouzakis, and V\. Singhal\(2024\)Not all learnable distribution classes are privately learnable\.InProceedings of the 35th International Conference on Algorithmic Learning Theory,ALT ’24,pp\. 390–401\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p5.1),[Abstract](https://arxiv.org/html/2610.28878#abstract1.1)\.
- \[BKS\+19\]M\. Bun, G\. Kamath, T\. Steinke, and Z\. S\. Wu\(2019\)Private hypothesis selection\.InAdvances in Neural Information Processing Systems 32,NeurIPS ’19,pp\. 156–167\.Cited by:[Appendix C](https://arxiv.org/html/2610.28878#A3.p19.1),[§1](https://arxiv.org/html/2610.28878#S1.p2.1),[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[BLM20\]M\. Bun, R\. Livni, and S\. Moran\(2020\)An equivalence between private classification and online prediction\.InProceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science,FOCS ’20,pp\. 389–402\.Cited by:[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p1.2)\.
- \[BNS\+15\]M\. Bun, K\. Nissim, U\. Stemmer, and S\. Vadhan\(2015\)Differentially private release and learning of threshold functions\.InProceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science,FOCS ’15,pp\. 634–649\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p6.1),[Remark 4\.4](https://arxiv.org/html/2610.28878#S4.Thmtheorem4.p1.1.1)\.
- \[CN25\]A\. Cheu and D\. Nayak\(2025\)Differentially private multi\-sampling from distributions\.InProceedings of the 36th International Conference on Algorithmic Learning Theory,ALT ’25,pp\. 289–314\.Cited by:[§1\.1](https://arxiv.org/html/2610.28878#S1.SS1.p3.1)\.
- \[CCL\+26\]E\. Cohen, B\. Cohen\-Wang, X\. Lyu, J\. Nelson, T\. Sarlos, and U\. Stemmer\(2026\)Hot pate: private aggregation of distributions for diverse tasks\.InInternational Conference on Learning Representations,Vol\.2026,pp\. 29693–29719\.Cited by:[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p4.1)\.
- \[DDS12\]C\. Daskalakis, I\. Diakonikolas, and R\. A\. Servedio\(2012\)Learning Poisson binomial distributions\.InProceedings of the 44th Annual ACM Symposium on the Theory of Computing,STOC ’12,pp\. 709–728\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p1.1)\.
- \[DL01\]L\. Devroye and G\. Lugosi\(2001\)Combinatorial methods in density estimation\.Springer\.Cited by:[Theorem C\.4](https://arxiv.org/html/2610.28878#A3.Thmtheorem4),[Appendix C](https://arxiv.org/html/2610.28878#A3.p14.1),[§1](https://arxiv.org/html/2610.28878#S1.p1.1)\.
- \[DHS15\]I\. Diakonikolas, M\. Hardt, and L\. Schmidt\(2015\)Differentially private learning of structured discrete distributions\.InAdvances in Neural Information Processing Systems 28,NIPS ’15,pp\. 2566–2574\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[DIA16\]I\. Diakonikolas\(2016\)Learning structured distributions\.InHandbook of Big Data,P\. Bühlmann, P\. Drineas, M\. J\. Kane, and M\. J\. van der Laan \(Eds\.\),pp\. 267–283\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p1.1)\.
- \[DKM\+06a\]C\. Dwork, K\. Kenthapadi, F\. McSherry, I\. Mironov, and M\. Naor\(2006\)Our data, ourselves: privacy via distributed noise generation\.InProceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques,EUROCRYPT ’06,Berlin, Heidelberg,pp\. 486–503\.Cited by:[Definition 2\.3](https://arxiv.org/html/2610.28878#S2.Thmtheorem3)\.
- \[DMN\+06b\]C\. Dwork, F\. McSherry, K\. Nissim, and A\. Smith\(2006\)Calibrating noise to sensitivity in private data analysis\.InProceedings of the 3rd Conference on Theory of Cryptography,TCC ’06,Berlin, Heidelberg,pp\. 265–284\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1),[Definition 2\.3](https://arxiv.org/html/2610.28878#S2.Thmtheorem3)\.
- \[GKM21\]B\. Ghazi, R\. Kumar, and P\. Manurangsi\(2021\)User\-level differentially private learning via correlated sampling\.InAdvances in Neural Information Processing Systems 34,NeurIPS ’21,pp\. 20172–20184\.Cited by:[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p4.1),[footnote 1](https://arxiv.org/html/2610.28878#footnote1)\.
- \[HKM\+23\]S\. B\. Hopkins, G\. Kamath, M\. Majid, and S\. Narayanan\(2023\)Robustness implies privacy in statistical estimation\.InProceedings of the 55th Annual ACM Symposium on the Theory of Computing,STOC ’23,pp\. 497–506\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1),[§1](https://arxiv.org/html/2610.28878#S1.p3.1)\.
- \[KKM\+23\]A\. Kalavasis, A\. Karbasi, S\. Moran, and G\. Velegkas\(2023\)Statistical indistinguishability of learning algorithms\.InProceedings of the 40th International Conference on Machine Learning,ICML ’23,pp\. 15586–15622\.Cited by:[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p4.1),[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p5.1),[§1\.3](https://arxiv.org/html/2610.28878#S1.SS3.p2.1),[Remark 4\.2](https://arxiv.org/html/2610.28878#S4.Thmtheorem2),[Remark 4\.2](https://arxiv.org/html/2610.28878#S4.Thmtheorem2.p1.1.1),[Remark 4\.2](https://arxiv.org/html/2610.28878#S4.Thmtheorem2.p2.1.1),[Remark 4\.2](https://arxiv.org/html/2610.28878#S4.Thmtheorem2.p3.1.1),[Remark 4\.2](https://arxiv.org/html/2610.28878#S4.Thmtheorem2.p4.1.1)\.
- \[KAL02\]O\. Kallenberg\(2002\)Foundations of modern probability\.2 edition,Springer\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4757-4015-8)Cited by:[§A\.1](https://arxiv.org/html/2610.28878#A1.SS1.p4.1.1),[§A\.2](https://arxiv.org/html/2610.28878#A1.SS2.p16.1),[§A\.2](https://arxiv.org/html/2610.28878#A1.SS2.p18.1.1)\.
- \[KLS\+19a\]G\. Kamath, J\. Li, V\. Singhal, and J\. Ullman\(2019\)Privately learning high\-dimensional distributions\.InProceedings of the 32nd Annual Conference on Learning Theory,COLT ’19,pp\. 1853–1902\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[KMS\+22\]G\. Kamath, A\. Mouzakis, V\. Singhal, T\. Steinke, and J\. Ullman\(2022\)A private and computationally\-efficient estimator for unbounded gaussians\.InProceedings of the 35th Annual Conference on Learning Theory,COLT ’22,pp\. 544–572\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[KSS\+19b\]G\. Kamath, O\. Sheffet, V\. Singhal, and J\. Ullman\(2019\)Differentially private algorithms for learning mixtures of separated Gaussians\.InAdvances in Neural Information Processing Systems 32,NeurIPS ’19,pp\. 168–180\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[KV18\]V\. Karwa and S\. Vadhan\(2018\)Finite sample differentially private confidence intervals\.InProceedings of the 9th Conference on Innovations in Theoretical Computer Science,ITCS ’18,Dagstuhl, Germany,pp\. 44:1–44:9\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[KSS94a\]M\. J\. Kearns, R\. E\. Schapire, and L\. M\. Sellie\(1994\)Towards efficient agnostic learning\.Machine Learning17\(2–3\),pp\. 115–141\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p5.1)\.
- \[KMR\+94b\]M\. Kearns, Y\. Mansour, D\. Ron, R\. Rubinfeld, R\. E\. Schapire, and L\. Sellie\(1994\)On the learnability of discrete distributions\.InProceedings of the 26th Annual ACM Symposium on the Theory of Computing,STOC ’94,pp\. 273–282\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p1.1)\.
- \[KMV22\]P\. K\. Kothari, P\. Manurangsi, and A\. Velingker\(2022\)Private robust estimation by stabilizing convex relaxations\.InProceedings of the 35th Annual Conference on Learning Theory,COLT ’22,pp\. 723–777\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[LB23\]T\. Lechner and S\. Ben\-David\(2023\)Impossibility of characterizing distribution learning–a simple solution to a long\-standing problem\.arXiv preprint arXiv:2304\.08712\.Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p6.1)\.
- \[LB26\]T\. Lechner and S\. Ben\-David\(2026\)No scale sensitive dimension for distribution learning\.In37th International Conference on Algorithmic Learning Theory,Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p1.1),[§1](https://arxiv.org/html/2610.28878#S1.p6.1)\.
- \[MCS09\]F\. McSherry\(2009\)Privacy integrated queries: an extensible platform for privacy\-preserving data analysis\.InProceedings of the 2009 ACM SIGMOD International Conference on Management of Data,SIGMOD ’09,pp\. 19–30\.Cited by:[Lemma 2\.5](https://arxiv.org/html/2610.28878#S2.Thmtheorem5)\.
- \[MCS17\]F\. McSherry\(2017\)How many secrets do you have?\.Note:Blog postExternal Links:[Link](https://github.com/frankmcsherry/blog/blob/master/posts/2017-02-08.md)Cited by:[§6](https://arxiv.org/html/2610.28878#S6.p4.1)\.
- \[NRS07\]K\. Nissim, S\. Raskhodnikova, and A\. Smith\(2007\)Smooth sensitivity and sampling in private data analysis\.InProceedings of the 39th Annual ACM Symposium on the Theory of Computing,STOC ’07,pp\. 75–84\.Cited by:[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p1.1)\.
- \[RSS\+21\]S\. Raskhodnikova, S\. Sivakumar, A\. Smith, and M\. Swanberg\(2021\)Differentially private sampling from distributions\.InAdvances in Neural Information Processing Systems 34,NeurIPS ’21,pp\. 28983–28994\.Cited by:[§1\.1](https://arxiv.org/html/2610.28878#S1.SS1.p3.1)\.
- \[SIN24\]V\. Singhal\(2024\)A polynomial time, pure differentially private estimator for binary product distributions\.InProceedings of The 35th International Conference on Algorithmic Learning Theory,C\. Vernade and D\. Hsu \(Eds\.\),Proceedings of Machine Learning Research, Vol\.237,pp\. 1030–1054\.External Links:[Link](https://proceedings.mlr.press/v237/singhal24a.html)Cited by:[§1](https://arxiv.org/html/2610.28878#S1.p2.1)\.
- \[TS13\]A\. G\. Thakurta and A\. Smith\(2013\)Differentially private feature selection via stability arguments, and the robustness of the lasso\.InProceedings of the 26th Annual Conference on Learning Theory,Vol\.30,pp\. 819–850\.External Links:[Link](https://proceedings.mlr.press/v30/Guha13.html)Cited by:[§B\.1](https://arxiv.org/html/2610.28878#A2.SS1.SSS0.Px2.p9.1),[Fact B\.3](https://arxiv.org/html/2610.28878#A2.Thmtheorem3),[§4\.1](https://arxiv.org/html/2610.28878#S4.SS1.p5.1.1)\.
- \[VAD17\]S\. Vadhan\(2017\)The complexity of differential privacy\.InTutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich,Y\. Lindell \(Ed\.\),pp\. 347–450\.Cited by:[§B\.1](https://arxiv.org/html/2610.28878#A2.SS1.SSS0.Px2.p9.1),[Fact B\.3](https://arxiv.org/html/2610.28878#A2.Thmtheorem3),[§1\.2](https://arxiv.org/html/2610.28878#S1.SS2.p1.2),[§4\.1](https://arxiv.org/html/2610.28878#S4.SS1.p5.1.1)\.

## Appendix APoisson Coupling Details

We present two constructions of the grand coupling interface in Definition[3\.1](https://arxiv.org/html/2610.28878#S3.Thmtheorem1), both based on the Poisson coupling of\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]\. Subsection[A\.1](https://arxiv.org/html/2610.28878#A1.SS1)treats families𝒫⊆Δ⁡\(𝒴\)\\mathcal\{P\}\\subseteq\\Delta\(\\mathcal\{Y\}\)that admit a commonσ\\sigma\-finite dominating measure\. For such families, Corollary[A\.3](https://arxiv.org/html/2610.28878#A1.Thmtheorem3)establishes a grand coupling scheme on𝒫\\mathcal\{P\}\.

Subsection[A\.2](https://arxiv.org/html/2610.28878#A1.SS2)treats the general case, without assuming a common dominating measure\. For every standard Borel space𝒴\\mathcal\{Y\}, Corollary[A\.7](https://arxiv.org/html/2610.28878#A1.Thmtheorem7)establishes a universal grand coupling scheme onΔ⁡\(𝒴\)\\Delta\(\\mathcal\{Y\}\)\. Restricting this scheme to any family𝒫⊆Δ⁡\(𝒴\)\\mathcal\{P\}\\subseteq\\Delta\(\\mathcal\{Y\}\)gives a grand coupling scheme on𝒫\\mathcal\{P\}\.

### A\.1A Globally Dominated Poisson Coupling

We first formalize the setting where all distributions in the family are dominated by a single reference measure\. Let\(𝒴,ℬ\)\(\\Y,\\mathcal\{B\}\)be a standard Borel space and let𝒫⊆Δ⁡\(𝒴\)\\mathcal\{P\}\\subseteq\\Delta\(\\mathcal\{Y\}\)be a collection of probability measures of interest\. We use the original construction taken verbatim from\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]\.

###### Construction A\.1\.

Suppose there exists aσ\\sigma\-finite measureν\\nusuch thatP≪νP\\ll\\nufor everyP∈𝒫P\\in\\mathcal\{P\}\. We writefP=d​Pd​νf\_\{P\}=\\frac\{dP\}\{d\\nu\}for allP∈𝒫\.P\\in\\mathcal\{P\}\.

Let𝒜\\Abe a Poisson point process on𝒴×ℝ\+×ℝ\+\\Y\\times\\mathbb\{R\}\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}with intensityν⁡\(d​y\)​d​s​d​t\\nu\(dy\)dsdt\(Definition[2\.2](https://arxiv.org/html/2610.28878#S2.Thmtheorem2)\)\. For a realizationa\\mathrm\{a\}of the Poisson point process𝒜\\A, we letaP=\{\(y,s,t\)∈a:s≤fP​\(y\)\}\\mathrm\{a\}\_\{P\}=\\\{\(y,s,t\)\\in\\mathrm\{a\}:s\\leq f\_\{P\}\(y\)\\\}for allP∈𝒫P\\in\\mathcal\{P\}, and letΦ⁡\(P,a\)\\Phi\(P,\\mathrm\{a\}\)denote theyy\-coordinate of the point inaP\\mathrm\{a\}\_\{P\}having the smallesttt\-coordinate\. More formally, if\(y∗,s∗,t∗\)\(y^\{\*\},s^\{\*\},t^\{\*\}\)is the unique point satisfyingt∗=min\{t:\(y,s,t\)∈a,s≤fP\(y\)\}t^\{\*\}=\\min\\\{t:\(y,s,t\)\\in\\mathrm\{a\},s\\leq f\_\{P\}\(y\)\\\}, thenΦ⁡\(P,a\)=y∗\\Phi\(P,\\mathrm\{a\}\)=y^\{\*\}\. Note that on the null event that there is a tie we can defineΦ⁡\(P,a\)\\Phi\(P,\\mathrm\{a\}\)arbitrarily\.777Under the law of PPP, such events have probability zero, so it does not affect any of the distributions\. See proof of Prop 5 in\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]\.\. Using the same random process𝒜\\Afor everyP∈𝒫P\\in\\mathcal\{P\}, we define the random variableZP=Φ⁡\(P,𝒜\)Z\_\{P\}=\\Phi\(P,\\A\)and letΓ=ℒ⁡\(\(ZP\)P∈𝒫\)\\Gamma=\\mathcal\{L\}\(\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}\)be their joint law\.\.

Algorithm 5𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨\\mathsf\{Couple\\\_I\}from construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)1:Distributions

q1,…,qk∈ℱq\_\{1\},\\ldots,q\_\{k\}\\in\\mathcal\{F\}\.A fixedσ\\sigma\-finite measureν\\nuon𝒳ℓ\\X^\{\\ell\}dominating every relevantqℓ∈\{qℓ:q∈ℱ\}q^\{\\ell\}\\in\\\{q^\{\\ell\}:q\\in\\mathcal\{F\}\\\}\.

2:Synthetic samples

\(Z1,…,Zk\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)such that

Zi∼qiℓZ\_\{i\}\\sim q\_\{i\}^\{\\ell\}and

Pr\[Zi≠Zj\]≤2TV\(qiℓ,qjℓ\)\\Pr\[Z\_\{i\}\\neq Z\_\{j\}\]\\leq 2\\TV\(q\_\{i\}^\{\\ell\},q\_\{j\}^\{\\ell\}\)for all

i,j∈\[k\]i,j\\in\[k\]\.

3:Let a random seed be

𝒜\\A, a Poisson point process with intensity

ν⁡\(d​y\)​d​s​d​t\\nu\(dy\)dsdt
4:

Zi=Φ⁡\(qiℓ,𝒜\)Z\_\{i\}=\\Phi\(q\_\{i\}^\{\\ell\},\\A\)for all

i∈\[k\]i\\in\[k\]according to construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)⊳\\trianglerightConditional on a realization𝒜=a\\A=\\mathrm\{a\}, i\.e\. conditional on a realization of the PPP, the outputzi=Φ⁡\(qiℓ,a\)z\_\{i\}=\\Phi\(q\_\{i\}^\{\\ell\},\\mathrm\{a\}\)is deterministic\.

5:return

\(Z1,…,Zk\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)\.⊳\\trianglerightEquivalently,\(Z1,…,Zk\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)has the\(q1ℓ,…,qkℓ\)\(q\_\{1\}^\{\\ell\},\.\.\.,q\_\{k\}^\{\\ell\}\)\-coordinate marginal of the couplingΓ\\Gammafrom construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)

###### Theorem A\.2\(Proposition 5 and Theorem 2 in\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]\)\.

Suppose𝒴\\Yis standard Borel and there exists aσ\\sigma\-finite measureν\\nusuch thatP≪νP\\ll\\nufor allP∈𝒫P\\in\\mathcal\{P\}\. The lawΓ\\Gammadefined in Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1), is a coupling of\(P\)P∈𝒫\(P\)\_\{P\\in\\mathcal\{P\}\}, i\.e\.ZP∼PZ\_\{P\}\\sim Pfor everyP∈𝒫P\\in\\mathcal\{P\}\. Moreover, for everyP,Q∈𝒫P,Q\\in\\mathcal\{P\},

Pr\[ZP≠ZQ\]≤2​TV⁡\(P,Q\)1\+TV⁡\(P,Q\)≤2TV\(P,Q\)\\displaystyle\\Pr\[Z\_\{P\}\\neq Z\_\{Q\}\]\\leq\\frac\{2\\TV\(P,Q\)\}\{1\+\\TV\(P,Q\)\}\\leq 2\\TV\(P,Q\)

Theorem[A\.2](https://arxiv.org/html/2610.28878#A1.Thmtheorem2)establishes the core marginal and agreement guarantees for the coupling construction\. However, to formally show that it constitutes a grand coupling scheme on𝒫\\P, we must also verify the measurability requirement, as formalized below\.

###### Corollary A\.3\(Grand coupling schemeΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}from Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)\)\.

Suppose𝒴\\Yis standard Borel and there exists aσ\\sigma\-finite measureν\\nusuch thatP≪νP\\ll\\nufor allP∈𝒫P\\in\\mathcal\{P\}\. Then the family of random variables\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}defined in Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)constitutes a grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}on𝒫\\mathcal\{P\}\.

###### Proof\.

G1 and G2 follow immediately from Theorem[A\.2](https://arxiv.org/html/2610.28878#A1.Thmtheorem2)\. It suffices to show G3 that the map𝐏↦ℒ⁡\(ZP1,…,ZPk\)\\mathbf\{P\}\\mapsto\\mathcal\{L\}\(Z\_\{P\_\{1\}\},\.\.\.,Z\_\{P\_\{k\}\}\), where𝐏=\(P1,…,Pk\)\\mathbf\{P\}=\(P\_\{1\},\.\.\.,P\_\{k\}\)withPi∈𝒫P\_\{i\}\\in\\P, is a Markov kernel\.

Since𝒴\\Yis standard Borel andP≪νP\\ll\\nufor allP∈𝒫P\\in\\P, the Radon\-Nikodym derivatives may be chosen jointly measurably in\(P,y\)\(P,y\)\[[31](https://arxiv.org/html/2610.28878#bib.bib46)\], so writef⁡\(Pi,y\)=d​Pid​ν​\(y\)f\(P\_\{i\},y\)=\\frac\{dP\_\{i\}\}\{d\\nu\}\(y\)\. Let𝒜\\Abe a Poisson point process on𝒴×ℝ\+×ℝ\+\\Y\\times\\mathbb\{R\}\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}with intensityν⁡\(d​y\)​d​s​d​t\.\\nu\(dy\)dsdt\.For everyi∈\[k\]i\\in\[k\], define𝒜i=\{\(y,s,t\)∈𝒜:s≤f⁡\(Pi,y\)\}\\A\_\{i\}=\\\{\(y,s,t\)\\in\\A:s\\leq f\(P\_\{i\},y\)\\\}\. We define the random variableZiZ\_\{i\}byZi=yZ\_\{i\}=y, where\(y,s,t\)\(y,s,t\)is the point of𝒜i\\A\_\{i\}with the minimalttamong all points of𝒜i\\A\_\{i\}\. Equivalently, we writeZi=Φ⁡\(Pi,𝒜\),Z\_\{i\}=\\Phi\(P\_\{i\},\\A\),whereΦ\\Phidenotes this deterministic rule\.

Now defineΦ⁡\(𝐏,𝒜\)=\(Φ⁡\(P1,𝒜\),…,Φ⁡\(Pk,𝒜\)\)\\Phi\(\\mathbf\{P\},\\A\)=\(\\Phi\(P\_\{1\},\\A\),\\ldots,\\Phi\(P\_\{k\},\\A\)\)and for measurableB⊆𝒴kB\\subseteq\\Y^\{k\}, letΓk\(𝐏;B\)=Pr𝒜\[Φ\(𝐏,𝒜\)∈B\]\\Gamma\_\{k\}\(\\mathbf\{P\};B\)=\\Pr\_\{\\A\}\[\\Phi\(\\mathbf\{P\},\\A\)\\in B\], i\.e\.Γk​\(𝐏,⋅\)=ℒ⁡\(Φ⁡\(𝐏,𝒜\)\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=\\mathcal\{L\}\(\\Phi\(\\mathbf\{P\},\\A\)\)\. Sincef⁡\(Pi,y\)f\(P\_\{i\},y\)is jointly measurable, the indicator1\{s≤f\(Pi,y\)\}1\\\{s\\leq f\(P\_\{i\},y\)\\\}is also jointly measurable; applying a measurable filter to a point process yields another valid point process, and applying the argmin ontt\-coordinate is also measurable; and thus, the deterministic map\(𝐏,a\)↦Φ⁡\(𝐏,a\)\(\\mathbf\{P\},a\)\\mapsto\\Phi\(\\mathbf\{P\},a\)is measurable\. Therefore,𝐏↦Γk​\(𝐏,B\)\\mathbf\{P\}\\mapsto\\Gamma\_\{k\}\(\\mathbf\{P\};B\)is also measurable for every measurableB⊆𝒴kB\\subseteq\\Y^\{k\}, soΓk\\Gamma\_\{k\}is a Markov kernel\.

Thus, the joint law of\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}yields the desired grand couplingΓ𝒫\\Gamma\_\{\\P\}on𝒴𝒫\\mathcal\{Y\}^\{\\mathcal\{P\}\}\. ∎

### A\.2Projectively Consistent Poisson Couplings on Standard Borel Spaces

The preceding construction requires a singleσ\\sigma\-finite measure dominating every distribution in the family under consideration\. However, such a measure may not generally exist\. For example, the uncountable family of all point masses over the real line admits no commonσ\\sigma\-finite dominating measure\. In fact, on a standard Borel space, a family𝒫⊆Δ⁡\(𝒴\)\\P\\subseteq\\Delta\(\\Y\)admits a commonσ\\sigma\-finite dominating measure if and only if𝒫\\Pis TV separable\. Thus the core issue is not uncountability per se, but rather TV nonseparability\. For any*finite*tuple of probability measures𝐏=\(P1,…​Pk\)∈Δ​\(𝒴\)k\\mathbf\{P\}=\(P\_\{1\},\.\.\.P\_\{k\}\)\\in\\Delta\(\\Y\)^\{k\}, however, there is always a canonical finite dominating measure,ν𝐏=∑iPi\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i\}P\_\{i\}\. Thus, for each fixed finite tuple, the Poisson construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)can be applied with the tuple\-dependent reference measureν𝐏\\nu\_\{\\mathbf\{P\}\}\.

###### Construction A\.4\.

Fixk≥1k\\geq 1and a tuple𝐏=\(P1,…​Pk\)∈Δ​\(𝒴\)k\\mathbf\{P\}=\(P\_\{1\},\.\.\.P\_\{k\}\)\\in\\Delta\(\\Y\)^\{k\}\. Define the𝐏\\mathbf\{P\}\-dependent measureν𝐏=∑iPi\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i\}P\_\{i\}, which is finite, and letfiν𝐏=d​Pid​ν𝐏f\_\{i\}^\{\\nu\_\{\\mathbf\{P\}\}\}=\\frac\{dP\_\{i\}\}\{d\\nu\_\{\\mathbf\{P\}\}\}be the corresponding densities\. Let𝒜𝐏\\A\_\{\\mathbf\{P\}\}be a Poisson point process on𝒴×ℝ\+×ℝ\+\\Y\\times\\mathbb\{R\}\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}with intensityν𝐏​\(d​y\)​d​s​d​t\\nu\_\{\\mathbf\{P\}\}\(dy\)dsdt\(Definition[2\.2](https://arxiv.org/html/2610.28878#S2.Thmtheorem2)\)\. Unlike construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1), the law ofA𝐏A\_\{\\mathbf\{P\}\}depends on the entire tuple𝐏\\mathbf\{P\}\.

For a realizationa𝐏\\mathrm\{a\}\_\{\\mathbf\{P\}\}of the Poisson point process𝒜𝐏\\A\_\{\\mathbf\{P\}\}, we letΦi​\(𝐏,a𝐏\)\\Phi\_\{i\}\(\\mathbf\{P\},\\mathrm\{a\}\_\{\\mathbf\{P\}\}\)denote theyy\-coordinate of the point ina𝐏,i\\mathrm\{a\}\_\{\\mathbf\{P\},i\}having the smallesttt\-coordinate, where the acceptance regions area𝐏,i=\{\(y,s,t\)∈a𝐏:s≤fiν𝐏​\(y\)\}\\mathrm\{a\}\_\{\\mathbf\{P\},i\}=\\\{\(y,s,t\)\\in\\mathrm\{a\}\_\{\\mathbf\{P\}\}:s\\leq f\_\{i\}^\{\\nu\_\{\\mathbf\{P\}\}\}\(y\)\\\}for alli∈\[k\]i\\in\[k\]\.888Similar to[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1), if\(y∗,s∗,t∗\)\(y^\{\*\},s^\{\*\},t^\{\*\}\)is the unique point satisfyingt∗=min\{t:\(y,s,t\)∈a𝐏,s≤fiν𝐏\(y\)\}=min\{t:\(y,s,t\)∈a𝐏,i\}t^\{\*\}=\\min\\\{t:\(y,s,t\)\\in\\mathrm\{a\}\_\{\\mathbf\{P\}\},s\\leq f\_\{i\}^\{\\nu\_\{\\mathbf\{P\}\}\}\(y\)\\\}=\\min\\\{t:\(y,s,t\)\\in\\mathrm\{a\}\_\{\\mathbf\{P\},i\}\\\}, thenΦi​\(𝐏,a𝐏\)=y∗\\Phi\_\{i\}\(\\mathbf\{P\},\\mathrm\{a\}\_\{\\mathbf\{P\}\}\)=y^\{\*\}\. On the null event on which such a unique point does not exist, defineΦi​\(𝐏,a𝐏\)\\Phi\_\{i\}\(\\mathbf\{P\},\\mathrm\{a\}\_\{\\mathbf\{P\}\}\)arbitrarily\. Under the law of PPP, such events have probability zero, so it does not affect any of the distributions\. See proof of Prop 5 in\[[7](https://arxiv.org/html/2610.28878#bib.bib39)\]\.

Using the same random process𝒜𝐏\\A\_\{\\mathbf\{P\}\}for everyi∈\[k\]i\\in\[k\]999It is worth noting that the same Poisson process𝒜𝐏\\A\_\{\\mathbf\{P\}\}is shared by allkkcoordinates, and only the acceptance regions,𝒜𝐏,i=\{\(y,s,t\)∈𝒜𝐏:s≤fiν𝐏​\(y\)\}\\A\_\{\\mathbf\{P\},i\}=\\\{\(y,s,t\)\\in\\A\_\{\\mathbf\{P\}\}:s\\leq f\_\{i\}^\{\\nu\_\{\\mathbf\{P\}\}\}\(y\)\\\}differ acrossii, we define the random variableZ𝐏,i=Φi​\(𝐏,𝒜𝐏\)Z\_\{\\mathbf\{P\},i\}=\\Phi\_\{i\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\), and for every measurableB⊆𝒴kB\\subseteq\\Y^\{k\}, defineΓk\(𝐏;B\)=Pr\[\(Z𝐏,1,…,Z𝐏,k\)∈B\]\\Gamma\_\{k\}\(\\mathbf\{P\};B\)=\\Pr\[\(Z\_\{\\mathbf\{P\},1\},\.\.\.,Z\_\{\\mathbf\{P\},k\}\)\\in B\], i\.e\.,\(Z𝐏,1,…,Z𝐏,k\)∼Γk​\(𝐏,⋅\)\(Z\_\{\\mathbf\{P\},1\},\\dots,Z\_\{\\mathbf\{P\},k\}\)\\sim\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)\. Thus,Γk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)is the joint law induced by the𝐏\\mathbf\{P\}\-specific Poisson coupling\.

Algorithm 6𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨𝖨\\mathsf\{Couple\\\_II\}from construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)1:Distributions

q1,…,qk∈ℱq\_\{1\},\\ldots,q\_\{k\}\\in\\mathcal\{F\}\.

2:Synthetic samples

\(Z1,…,Zk\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)such that

Zi∼qiℓZ\_\{i\}\\sim q\_\{i\}^\{\\ell\}and

Pr\[Zi≠Zj\]≤2TV\(qiℓ,qjℓ\)\\Pr\[Z\_\{i\}\\neq Z\_\{j\}\]\\leq 2\\TV\(q\_\{i\}^\{\\ell\},q\_\{j\}^\{\\ell\}\)for all

i,j∈\[k\]i,j\\in\[k\]\.

3:Set

Pi=qiℓP\_\{i\}=q\_\{i\}^\{\\ell\}for all

i∈\[k\]i\\in\[k\],

ν𝐏=∑iPi\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i\}P\_\{i\}, and

fiν𝐏=d​Pid​ν𝐏f\_\{i\}^\{\\nu\_\{\\mathbf\{P\}\}\}=\\frac\{dP\_\{i\}\}\{d\\nu\_\{\\mathbf\{P\}\}\}
4:Let a random seed be

𝒜𝐏\\A\_\{\\mathbf\{P\}\}, a Poisson point process with intensity

ν𝐏​\(d​y\)​d​s​d​t\\nu\_\{\\mathbf\{P\}\}\(dy\)dsdt
5:

Zi=Φi​\(𝐏,𝒜𝐏\)Z\_\{i\}=\\Phi\_\{i\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)for all

i∈\[k\]i\\in\[k\]according to construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)⊳\\trianglerightConditional on a realization𝒜𝐏=a𝐏\\A\_\{\\mathbf\{P\}\}=\\mathrm\{a\}\_\{\\mathbf\{P\}\}, the outputzi=Φi​\(𝐏,a𝐏\)z\_\{i\}=\\Phi\_\{i\}\(\\mathbf\{P\},\\mathrm\{a\}\_\{\\mathbf\{P\}\}\)is deterministic\.

6:return

\(Z1,…,Zk\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)\.⊳\\trianglerightEquivalently,\(Z1,…,Zk\)∼Γk​\(𝐏,⋅\)\(Z\_\{1\},\.\.\.,Z\_\{k\}\)\\sim\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)from construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)

The key extra ingredients are to show that these tuple\-specific couplings vary measurably with𝐏\\mathbf\{P\}and are projective consistent across different tuples\. Measurability allows the construction to be applied to \(data\-dependent\) random distributions, while projective consistency allows finite couplings built from different tuples to be embedded into a common larger coupling\.

For a measurable mapT:𝒮→𝒯T:\\mathcal\{S\}\\to\\mathcal\{T\}and a measureμ\\muon𝒮\\mathcal\{S\}, we writeT\#​μT\_\{\\\#\}\\mufor the pushforward measure ofμ\\muunderTT, defined by\(T\#​μ\)​\(B\)=μ⁡\(T−1​\(B\)\)\(T\_\{\\\#\}\\mu\)\(B\)=\\mu\(T^\{\-1\}\(B\)\)for all measurableB⊆𝒯B\\subseteq\\mathcal\{T\}\. For finite products, writepri​\(y1,…,yk\)=yi\\mathrm\{pr\}\_\{i\}\(y\_\{1\},\\ldots,y\_\{k\}\)=y\_\{i\}for theii\-th coordinate projection\.

###### Proposition A\.5\(Projectively consistent Poisson coupling kernels\)\.

Let𝒴\\mathcal\{Y\}be standard Borel\. For everyk≥1k\\geq 1, Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)defines a mapΓk:Δ​\(𝒴\)k→Δ⁡\(𝒴k\)\\Gamma\_\{k\}:\\Delta\(\\mathcal\{Y\}\)^\{k\}\\to\\Delta\(\\mathcal\{Y\}^\{k\}\), with the following properties\. WriteΓk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)for the measureΓk​\(𝐏\)\\Gamma\_\{k\}\(\\mathbf\{P\}\), and letDi​j=\{\(y1,…,yk\)∈𝒴k:yi≠yj\}D\_\{ij\}=\\\{\(y\_\{1\},\\dots,y\_\{k\}\)\\in\\mathcal\{Y\}^\{k\}:y\_\{i\}\\neq y\_\{j\}\\\}\.

1. \(1\)*\(Measurability\.\)*For every measurableB⊆𝒴kB\\subseteq\\mathcal\{Y\}^\{k\}, the map𝐏↦Γk​\(𝐏,B\)\\mathbf\{P\}\\mapsto\\Gamma\_\{k\}\(\\mathbf\{P\};B\)is measurable with respect to the evaluationσ\\sigma\-algebra onΔ​\(𝒴\)k\\Delta\(\\mathcal\{Y\}\)^\{k\}; that is,Γk\\Gamma\_\{k\}is a Markov kernel fromΔ​\(𝒴\)k\\Delta\(\\mathcal\{Y\}\)^\{k\}to𝒴k\\mathcal\{Y\}^\{k\}\.
2. \(2\)*\(Marginals\.\)*For every𝐏=\(P1,…,Pk\)\\mathbf\{P\}=\(P\_\{1\},\\dots,P\_\{k\}\)andi∈\[k\]i\\in\[k\],\(pri\)\#​Γk​\(𝐏,⋅\)=Pi\(\\mathrm\{pr\}\_\{i\}\)\_\{\\\#\}\\,\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=P\_\{i\}\.
3. \(3\)*\(Disagreement bound\.\)*For every𝐏\\mathbf\{P\}andi,j∈\[k\]i,j\\in\[k\],Γk​\(𝐏,Di​j\)≤2​TV​\(Pi,Pj\)1\+TV⁡\(Pi,Pj\)≤2​TV​\(Pi,Pj\)\\Gamma\_\{k\}\(\\mathbf\{P\};D\_\{ij\}\)\\leq\\tfrac\{2\\,\\mathrm\{TV\}\(P\_\{i\},P\_\{j\}\)\}\{1\+\\mathrm\{TV\}\(P\_\{i\},P\_\{j\}\)\}\\leq 2\\,\\mathrm\{TV\}\(P\_\{i\},P\_\{j\}\)\.
4. \(4\)*\(Projective consistency\.\)*For every nonemptyE=\{i1,…,ik′\}⊆\[k\]E=\\\{i\_\{1\},\.\.\.,i\_\{k^\{\\prime\}\}\\\}\\subseteq\[k\]withi1<…<ik′i\_\{1\}<\.\.\.<i\_\{k^\{\\prime\}\}and𝐏′=\(Pi\)i∈E\\mathbf\{P\}^\{\\prime\}=\(P\_\{i\}\)\_\{i\\in E\}in the original order,\(prE\)\#​Γk​\(𝐏,⋅\)=Γk′​\(𝐏′,⋅\)\(\\mathrm\{pr\}\_\{E\}\)\_\{\\\#\}\\,\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=\\Gamma\_\{k^\{\\prime\}\}\(\\mathbf\{P\}^\{\\prime\};\\cdot\), whereprE​\(y1,…,yk\)=\(yi1,…,yik′\)\\mathrm\{pr\}\_\{E\}\(y\_\{1\},\.\.\.,y\_\{k\}\)=\(y\_\{i\_\{1\}\},\.\.\.,y\_\{i\_\{k^\{\\prime\}\}\}\)
5. \(5\)*\(Permutation equivariance\.\)*For every permutationσ\\sigmaof\[k\]\[k\]: if\(Z1,…,Zk\)∼Γk​\(\(P1,…,Pk\),⋅\)\(Z\_\{1\},\\dots,Z\_\{k\}\)\\sim\\Gamma\_\{k\}\\big\(\(P\_\{1\},\\dots,P\_\{k\}\);\\cdot\\big\), then\(Zσ⁡\(1\),…,Zσ⁡\(k\)\)∼Γk​\(\(Pσ⁡\(1\),…,Pσ⁡\(k\)\),⋅\)\\big\(Z\_\{\\sigma\(1\)\},\\dots,Z\_\{\\sigma\(k\)\}\\big\)\\sim\\Gamma\_\{k\}\\big\(\(P\_\{\\sigma\(1\)\},\\dots,P\_\{\\sigma\(k\)\}\);\\cdot\\big\)\.

###### Proof\.

Now, we prove these properties\.

1\. MeasurabilityFixk≥1k\\geq 1and let𝐏=\(P1,…,Pk\)∈Δ​\(𝒴\)k\\mathbf\{P\}=\(P\_\{1\},\\ldots,P\_\{k\}\)\\in\\Delta\(\\Y\)^\{k\}\. Defineν𝐏=∑iPi\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i\}P\_\{i\}, soPi≪ν𝐏P\_\{i\}\\ll\\nu\_\{\\mathbf\{P\}\}for alli∈\[k\]i\\in\[k\]\. Since𝒴\\Yis standard Borel, the Radon\-Nikodym derivatives may be chosen jointly measurably in\(𝐏,y\)\(\\mathbf\{P\},y\), so writefi​\(𝐏,y\)=d​Pid​ν𝐏​\(y\)\.f\_\{i\}\(\\mathbf\{P\},y\)=\\frac\{dP\_\{i\}\}\{d\\nu\_\{\\mathbf\{P\}\}\}\(y\)\.SincePi≪ν𝐏P\_\{i\}\\ll\\nu\_\{\\mathbf\{P\}\}, we may take0≤fi​\(𝐏,y\)≤10\\leq f\_\{i\}\(\\mathbf\{P\},y\)\\leq 1ν𝐏\\nu\_\{\\mathbf\{P\}\}\-a\.e\.

For each𝐏\\mathbf\{P\}, let𝒜𝐏\\A\_\{\\mathbf\{P\}\}be a Poisson point process on𝒴×ℝ\+×ℝ\+\\Y\\times\\mathbb\{R\}\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}with intensityν𝐏​\(d​y\)​d​s​d​t\.\\nu\_\{\\mathbf\{P\}\}\(dy\)dsdt\.For everyi∈\[k\]i\\in\[k\], define𝒜𝐏,i=\{\(y,s,t\)∈𝒜𝐏:s≤fi​\(𝐏,y\)\}\\A\_\{\\mathbf\{P\},i\}=\\\{\(y,s,t\)\\in\\A\_\{\\mathbf\{P\}\}:s\\leq f\_\{i\}\(\\mathbf\{P\},y\)\\\}\. We define the random variableZiZ\_\{i\}byZi=yZ\_\{i\}=y, where\(y,s,t\)\(y,s,t\)is the point of𝒜𝐏,i\\A\_\{\\mathbf\{P\},i\}with the minimalttamong all points of𝒜𝐏,i\\A\_\{\\mathbf\{P\},i\}\. Equivalently, we writeZi=Φi​\(𝐏,𝒜𝐏\),Z\_\{i\}=\\Phi\_\{i\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\),whereΦi\\Phi\_\{i\}denotes this deterministic rule\.

Now defineΦ⁡\(𝐏,𝒜𝐏\)=\(Φ1​\(𝐏,𝒜𝐏\),…,Φk​\(𝐏,𝒜𝐏\)\)\\Phi\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)=\(\\Phi\_\{1\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\),\\ldots,\\Phi\_\{k\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)\)and for measurableB⊆𝒴kB\\subseteq\\Y^\{k\}, letΓk\(𝐏;B\)=Pr𝒜𝐏\[Φ\(𝐏,𝒜𝐏\)∈B\]\\Gamma\_\{k\}\(\\mathbf\{P\};B\)=\\Pr\_\{\\A\_\{\\mathbf\{P\}\}\}\[\\Phi\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)\\in B\], i\.e\.Γk​\(𝐏,⋅\)=ℒ⁡\(Φ⁡\(𝐏,𝒜𝐏\)\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=\\mathcal\{L\}\(\\Phi\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)\)\. Since𝒴\\Yis standard Borel, the intensity measureν𝐏​\(d​y\)​d​s​d​t\\nu\_\{\\mathbf\{P\}\}\(dy\)dsdtdepends measurably on𝐏\\mathbf\{P\}, and since the law of any PPP is uniquely and completely determined by its intensity measure, it follows that the𝐏\\mathbf\{P\}\-dependent PPP law varies measurably with𝐏\\mathbf\{P\}\. Also,fi​\(𝐏,y\)f\_\{i\}\(\\mathbf\{P\},y\)is jointly measurable, so the indicator1\{\{g\(𝐏,y,s\)≥0\}\}1\\\{\\\{g\(\\mathbf\{P\},y,s\)\\geq 0\\\}\\\}is also jointly measurable; applying a measurable filter to a point process yields another valid point process, and applying the argmin ontt\-coordinate is also measurable; and thus, the deterministic map\(𝐏,a\)↦Φ⁡\(𝐏,a\)\(\\mathbf\{P\},a\)\\mapsto\\Phi\(\\mathbf\{P\},a\)is measurable\. Therefore,𝐏↦Γk​\(𝐏,B\)\\mathbf\{P\}\\mapsto\\Gamma\_\{k\}\(\\mathbf\{P\};B\)is also measurable for every measurableB⊆𝒴kB\\subseteq\\Y^\{k\}, soΓk\\Gamma\_\{k\}is a Markov kernel\.

2\. MarginalTo see thatZiZ\_\{i\}has the required law \(so that the above is indeed a coupling\), we note that𝒜𝐏,i\\A\_\{\\mathbf\{P\},i\}has intensityfi​\(𝐏,y\)​ν𝐏​\(d​y\)​d​t=Pi​\(d​y\)​d​tf\_\{i\}\(\\mathbf\{P\},y\)\\nu\_\{\\mathbf\{P\}\}\(dy\)dt=P\_\{i\}\(dy\)dt, so theyy\-coordinate of its first point, i\.e\.Φi​\(𝐏,𝒜𝐏\)\\Phi\_\{i\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\), has lawPiP\_\{i\}\. Hence,\(pri\)\#​Γk​\(𝐏,⋅\)=Pi\(\\mathrm\{pr\}\_\{i\}\)\_\{\\\#\}\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=P\_\{i\}

3\. Disagreement boundFixi,j∈\[k\]i,j\\in\[k\], and denoteg=fi​\(𝐏,y\)g=f\_\{i\}\(\\mathbf\{P\},y\),h=fj​\(𝐏,y\)h=f\_\{j\}\(\\mathbf\{P\},y\),α=TV⁡\(Pi,Pj\)\.\\alpha=\\TV\(P\_\{i\},P\_\{j\}\)\.Consider the first point\(y,s\)\(y,s\)to appear that hass≤g⁡\(y\)∨h⁡\(y\)s\\leq g\(y\)\\vee h\(y\)\. If it happens thats≤g⁡\(y\)∧h⁡\(y\)s\\leq g\(y\)\\wedge h\(y\), then we get the agreementZi=Zj=yZ\_\{i\}=Z\_\{j\}=y; otherwise, this point determines either the value ofZiZ\_\{i\}orZjZ\_\{j\}\. Hence, for any measurableAA, the intensity of the region accepted by both is∫A\(g∧h\)​d​ν𝐏\\int\_\{A\}\(g\\wedge h\)d\\nu\_\{\\mathbf\{P\}\}and the intensity of the region accepted by at least one is∫𝒴\(g∨h\)​d​ν𝐏\\int\_\{\\Y\}\(g\\vee h\)d\\nu\_\{\\mathbf\{P\}\}\. Therefore,Pr\[Zi=Zj\]≥Pr\[Zi=Zj∈Aand the same point determines bothZiandZj\]=∫A\(g∧h\)​d​ν𝐏∫𝒴\(g∨h\)​d​ν𝐏\\Pr\[Z\_\{i\}=Z\_\{j\}\]\\geq\\Pr\[Z\_\{i\}=Z\_\{j\}\\in A\\text\{ and the same point determines both $Z\_\{i\}$ and $Z\_\{j\}$\}\]=\\frac\{\\int\_\{A\}\(g\\wedge h\)d\\nu\_\{\\mathbf\{P\}\}\}\{\\int\_\{\\Y\}\(g\\vee h\)d\\nu\_\{\\mathbf\{P\}\}\}\. Note that∫𝒴\(g∨h\)​d​ν𝐏=1\+α\\int\_\{\\Y\}\(g\\vee h\)d\\nu\_\{\\mathbf\{P\}\}=1\+\\alphaand∫𝒴\(g∧h\)​d​ν𝐏=1−α\\int\_\{\\Y\}\(g\\wedge h\)d\\nu\_\{\\mathbf\{P\}\}=1\-\\alpha, so it follows thatPr\[Zi=Zj\]≥1−α1\+α\\Pr\[Z\_\{i\}=Z\_\{j\}\]\\geq\\frac\{1\-\\alpha\}\{1\+\\alpha\}, i\.e\.Pr\[Zi≠Zj\]≤1−1−α1\+α≤2α\.\\Pr\[Z\_\{i\}\\neq Z\_\{j\}\]\\leq 1\-\\frac\{1\-\\alpha\}\{1\+\\alpha\}\\leq 2\\alpha\.Thus,Γk​\(𝐏,Di​j\)≤2​TV⁡\(Pi,Pj\)1\+TV⁡\(Pi,Pj\)≤2​TV⁡\(Pi,Pj\)\\Gamma\_\{k\}\(\\mathbf\{P\};D\_\{ij\}\)\\leq\\frac\{2\\TV\(P\_\{i\},P\_\{j\}\)\}\{1\+\\TV\(P\_\{i\},P\_\{j\}\)\}\\leq 2\\TV\(P\_\{i\},P\_\{j\}\), forDi​j=\{\(y1,…,yk\)∈𝒴k:yi≠yj\}D\_\{ij\}=\\\{\(y\_\{1\},\.\.\.,y\_\{k\}\)\\in\\Y^\{k\}:y\_\{i\}\\neq y\_\{j\}\\\}\.

4\. Projective consistencyLetE⊆\[k\]E\\subseteq\[k\]be nonempty\. Let𝐏′=\(Pi\)i∈E\\mathbf\{P\}^\{\\prime\}=\(P\_\{i\}\)\_\{i\\in E\}and defineν𝐏′=∑i∈EPi\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}=\\sum\_\{i\\in E\}P\_\{i\}andfi​\(𝐏′,y\)=d​Pid​ν𝐏′​\(y\)f\_\{i\}\(\\mathbf\{P\}^\{\\prime\},y\)=\\frac\{dP\_\{i\}\}\{d\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}\}\(y\)fori∈Ei\\in E\. Thus, by the chain rule, we havefi​\(𝐏,y\)=r⁡\(y\)​fi​\(𝐏′,y\)f\_\{i\}\(\\mathbf\{P\},y\)=r\(y\)f\_\{i\}\(\\mathbf\{P\}^\{\\prime\},y\), wherer​\(y\)=d​ν𝐏′d​ν𝐏​\(y\)r\(y\)=\\frac\{d\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}\}\{d\\nu\_\{\\mathbf\{P\}\}\}\(y\)ν𝐏\\nu\_\{\\mathbf\{P\}\}\-a\.e, for alli∈Ei\\in E\. LetY\+=\{y:r⁡\(y\)\>0\}Y\_\{\+\}=\\\{y:r\(y\)\>0\\\}\. Sinceν𝐏′​\(𝒴∖Y\+\)=0\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}\(\\Y\\setminus Y\_\{\+\}\)=0andPi≪ν𝐏′P\_\{i\}\\ll\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}for everyi∈Ei\\in E, we also havePi​\(𝒴∖Y\+\)=0P\_\{i\}\(\\Y\\setminus Y\_\{\+\}\)=0\. Equivalently, the portion of the acceptance region for coordinateiilying over𝒴∖Y\+\\Y\\setminus Y\_\{\+\}has zero intensity\. Hence, almost surely, no point withr⁡\(y\)=0r\(y\)=0is accepted by any coordinatei∈Ei\\in E, and these points may be discarded\.

Note that under the change of variable\(y,s,t\)↦\(y,sr⁡\(y\),t\)\(y,s,t\)\\mapsto\(y,\\frac\{s\}\{r\(y\)\},t\), the restriction of𝒜𝐏\\A\_\{\\mathbf\{P\}\}onY\+×ℝ\+×ℝ\+Y\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}is transformed into a PPP with intensityν𝐏′​\(d​y\)​d​u​d​t\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}\(dy\)dudt, foru=s/r⁡\(y\)u=s/r\(y\), sinceν𝐏​\(d​y\)​d​s​d​t=ν𝐏​\(d​y\)​r​\(y\)​d​u​d​t=ν𝐏′​\(d​y\)​d​u​d​t\\nu\_\{\\mathbf\{P\}\}\(dy\)dsdt=\\nu\_\{\\mathbf\{P\}\}\(dy\)r\(y\)dudt=\\nu\_\{\\mathbf\{P\}^\{\\prime\}\}\(dy\)dudt\. Moreover, for alli∈Ei\\in E,s≤fi𝐏​\(y\)s\\leq f\_\{i\}^\{\\mathbf\{P\}\}\(y\)if and only ifsr⁡\(y\)≤fi​\(𝐏′,y\)⇔u≤fi​\(𝐏′,y\)\\frac\{s\}\{r\(y\)\}\\leq f\_\{i\}\(\\mathbf\{P\}^\{\\prime\},y\)\\iff u\\leq f\_\{i\}\(\\mathbf\{P\}^\{\\prime\},y\), so after rescaling thes−s\-coordinate, the transformation does not change they−y\-andt−t\-coordinate, i\.e\. it preserves the first accepted point for everyi∈Ei\\in E\. In other words, if some point\(y,s,t\)\(y,s,t\)was the first accepted point for coordinateiiin the full construction, its transformed version\(y,s/r⁡\(y\),t\)\(y,s/r\(y\),t\)has the sameyyandtt, and is accepted in the subtuple construction\. Therefore, the joint law of the coordinates indexed byEEobtained from the full construction is exactly the law obtained by applying the Poisson construction directly to𝐏′\\mathbf\{P\}^\{\\prime\}\. Hence,\(prE\)\#​Γk​\(𝐏,⋅\)=Γk′​\(𝐏′,⋅\)\(\\mathrm\{pr\}\_\{E\}\)\_\{\\\#\}\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=\\Gamma\_\{k^\{\\prime\}\}\(\\mathbf\{P\}^\{\\prime\};\\cdot\), fork′=\|E\|k^\{\\prime\}=\|E\|\.

5\. Permutation equivarianceLet𝐏=\(P1,…,Pk\)\\mathbf\{P\}=\(P\_\{1\},\.\.\.,P\_\{k\}\)and denote𝐏σ=\(Pσ⁡\(1\),…,Pσ⁡\(k\)\)\\mathbf\{P\}\_\{\\sigma\}=\(P\_\{\\sigma\(1\)\},\.\.\.,P\_\{\\sigma\(k\)\}\)for an arbitrary permutationσ\\sigmaof\[k\]\.\[k\]\.Note that the dominating measure is invariant under permutations, i\.e\.ν𝐏=∑iPi=∑iPσ⁡\(i\)=ν𝐏σ\.\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i\}P\_\{i\}=\\sum\_\{i\}P\_\{\\sigma\(i\)\}=\\nu\_\{\\mathbf\{P\}\_\{\\sigma\}\}\.Moreover, for everyi∈\[k\]i\\in\[k\],fi​\(𝐏σ,y\)=d​Pσ⁡\(i\)d​ν𝐏σ=d​Pσ⁡\(i\)d​ν𝐏=fσ⁡\(i\)​\(𝐏,⋅\)f\_\{i\}\(\\mathbf\{P\}\_\{\\sigma\},y\)=\\frac\{dP\_\{\\sigma\(i\)\}\}\{d\\nu\_\{\\mathbf\{P\}\_\{\\sigma\}\}\}=\\frac\{dP\_\{\\sigma\(i\)\}\}\{d\\nu\_\{\\mathbf\{P\}\}\}=f\_\{\\sigma\(i\)\}\(\\mathbf\{P\},\\cdot\)ν𝐏\\nu\_\{\\mathbf\{P\}\}\-a\.e\. Also note that a Poisson point process𝒜𝐏\\A\_\{\\mathbf\{P\}\}on𝒴×ℝ\+×ℝ\+\\Y\\times\\mathbb\{R\}\_\{\+\}\\times\\mathbb\{R\}\_\{\+\}with intensityν𝐏​\(d​y\)​d​s​d​t\\nu\_\{\\mathbf\{P\}\}\(dy\)dsdtis also the Poisson point process used in the construction for𝐏σ\\mathbf\{P\}\_\{\\sigma\}, sinceν𝐏=ν𝐏σ\.\\nu\_\{\\mathbf\{P\}\}=\\nu\_\{\\mathbf\{P\}\_\{\\sigma\}\}\.Thus, the acceptance regions are the same a\.s\. as well, i\.e\.𝒜𝐏σ,i=\{\(y,s,t\)∈𝒜𝐏:s≤fi​\(𝐏σ,y\)\}=\{\(y,s,t\)∈𝒜𝐏:s≤fσ⁡\(i\)​\(𝐏,y\)\}=𝒜𝐏,σ⁡\(i\)\\A\_\{\\mathbf\{P\}\_\{\\sigma\},i\}=\\\{\(y,s,t\)\\in\\A\_\{\\mathbf\{P\}\}:s\\leq f\_\{i\}\(\\mathbf\{P\}\_\{\\sigma\},y\)\\\}=\\\{\(y,s,t\)\\in\\A\_\{\\mathbf\{P\}\}:s\\leq f\_\{\\sigma\(i\)\}\(\\mathbf\{P\},y\)\\\}=\\A\_\{\\mathbf\{P\},\\sigma\(i\)\}\. Hence, if we similarly defineZσ,i=Φi​\(𝐏σ,𝒜𝐏\)Z\_\{\\sigma,i\}=\\Phi\_\{i\}\(\\mathbf\{P\}\_\{\\sigma\},\\A\_\{\\mathbf\{P\}\}\), then we haveZσ,i=Φi​\(𝐏σ,𝒜𝐏\)=Φσ⁡\(i\)​\(𝐏,𝒜𝐏\)=Zσ⁡\(i\)Z\_\{\\sigma,i\}=\\Phi\_\{i\}\(\\mathbf\{P\}\_\{\\sigma\},\\A\_\{\\mathbf\{P\}\}\)=\\Phi\_\{\\sigma\(i\)\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)=Z\_\{\\sigma\(i\)\}, whereZi=Φi​\(𝐏,𝒜𝐏\)Z\_\{i\}=\\Phi\_\{i\}\(\\mathbf\{P\},\\A\_\{\\mathbf\{P\}\}\)\. Thus,\(Zσ,1,…,Zσ,k\)∼Γk​\(𝐏σ,⋅\)\(Z\_\{\\sigma,1\},\.\.\.,Z\_\{\\sigma,k\}\)\\sim\\Gamma\_\{k\}\(\\mathbf\{P\}\_\{\\sigma\};\\cdot\)∎

There are two aspects of[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)worth remarking\. First, the standard Borel machinery is not needed to construct the coupling for a fixed tuple𝐏\\mathbf\{P\}\. In fact, for fixed𝐏\\mathbf\{P\}, the Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)is simply the globally\-dominated construction as in Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)using the𝐏\\mathbf\{P\}\-dependent dominating measureν𝐏=∑iPi\\nu\_\{\\mathbf\{P\}\}=\\sum\_\{i\}P\_\{i\}\. The standard\-Borel assumption is used to ensure that the relevant Radon\-Nikodym derivatives and Poisson law can be parameterized measurably in𝐏\\mathbf\{P\}so thatΓk\\Gamma\_\{k\}is indeed a Markov kernel\. This is what allows us later to sample fromΓk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)when𝐏\\mathbf\{P\}itself is a random data\-dependent tuple of learner outputs\.

Second, projective consistency allows couplings laws associated with different tuples to be realized as marginals of a single larger coupling\. For example, given𝐏=\(P1,…,Pk\)\\mathbf\{P\}=\(P\_\{1\},\.\.\.,P\_\{k\}\)and𝐐=\(Q1,…,Qk\)\\mathbf\{Q\}=\(Q\_\{1\},\.\.\.,Q\_\{k\}\), and considerOPENΓ2​k​\(\(,,,,,,,,,,,\)\);⋅\)\\Gamma\_\{2k\}\(\(P\_\{1\},\.\.\.,P\_\{k\},Q\_\{1\},\.\.\.,Q\_\{k\}\)\);\\cdot\)\. Projective consistency guarantees that its firstkkcoordinates have lawΓk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\), and its lastkkcoordinates have lawΓk​\(𝐐,⋅\)\\Gamma\_\{k\}\(\\mathbf\{Q\};\\cdot\)\. Thus, the larger coupling jointly realizes the two coupling laws without changing either of their original joint distributions\. This is the key property that we will need for privacy, where we couple two neighboring executions, and utility analyses, where we enlarge the current execution by adjoining the ground\-truth law\.

It is also worth noting the differences between the two constructions\. Under a commonσ\\sigma\-finite dominating measureν\\nu, construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)produces a single coupling\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}for arbitrary \(potentially uncountable\) family𝒫⊆Δ⁡\(𝒴\)\\mathcal\{P\}\\subseteq\\Delta\(\\Y\), using one single global Poisson point process\. On the other hand, construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)assumes*no global dominating measure*, and for each finite tuple𝐏\\mathbf\{P\}, constructs a tuple\-specific coupling using the canonical dominating measureν𝐏\\nu\_\{\\mathbf\{P\}\}that is also tuple\-dependent\. Although for a different finite tuple𝐐\\mathbf\{Q\}, the constructions generally uses a different reference measureν𝐐\\nu\_\{\\mathbf\{Q\}\}and hence a different PPP law and coupling, the projection consistency allows us to create a larger coupling of the concatenated tuple, such that the coordinates corresponding to𝐐\\mathbf\{Q\}have lawΓk​\(𝐐,⋅\)\\Gamma\_\{k\}\(\\mathbf\{Q\};\\cdot\), and the rest have lawΓk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)

Despite this bottom\-up approach, we can still establish a post\-hoc universal coupling over all ofΔ⁡\(𝒴\)\\Delta\(\\mathcal\{Y\}\)via the Kolmogorov Extension Theorem\[[31](https://arxiv.org/html/2610.28878#bib.bib46)\]\. Specifically, the projective consistency established in Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)allows us to stitch the entire family of finite\-dimensional couplings\(Γk\)k≥1\(\\Gamma\_\{k\}\)\_\{k\\geq 1\}together into a single, global probability measure over the uncountable product space𝒴Δ⁡\(𝒴\)\\mathcal\{Y\}^\{\\Delta\(\\mathcal\{Y\}\)\}, yielding a simultaneous coupling for every possible distribution inΔ⁡\(𝒴\)\\Delta\(\\mathcal\{Y\}\)\. Consequently, the conceptual takeaway for both constructions is identical\. In Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1), one conceptually draws the family\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}from the joint lawΓ\\Gamma\. In Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4), one conceptually draws the entire universe\(ZP\)P∈Δ⁡\(𝒴\)\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\mathcal\{Y\}\)\}fromΓ∞\\Gamma\_\{\\infty\}, and trivially restricts to the coordinates\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}for any subset𝒫\\mathcal\{P\}of interest\. The only caveat lies in how the \(conceptual\) couplings are constructed\. In Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1), we assume a dominating measureν\\nusuch thatP≪νP\\ll\\nufor allP∈𝒫P\\in\\mathcal\{P\}, and construct the coupling directly based on a single PPP𝒜\\mathcal\{A\}depending only onν\\nu\. In Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4), we instead build a𝐏\\mathbf\{P\}\-dependent measureν𝐏\\nu\_\{\\mathbf\{P\}\}and a corresponding PPP𝒜𝐏\\mathcal\{A\}\_\{\\mathbf\{P\}\}to define a couplingΓk​\(𝐏,⋅\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)for each finite tuple𝐏\\mathbf\{P\}, and then KET guarantees that this family of finite\-dimensional couplings\(Γk\)k≥1\(\\Gamma\_\{k\}\)\_\{k\\geq 1\}ultimately induces a global couplingΓ∞\\Gamma\_\{\\infty\}over the entire spaceΔ⁡\(𝒴\)\\Delta\(\\mathcal\{Y\}\)\.

###### Corollary A\.6\.

In the setup above, let\(Γk\)k≥1\(\\Gamma\_\{k\}\)\_\{k\\geq 1\}be the family of coupling kernels from Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)\. Then there exists a probability measureΓ∞\\Gamma\_\{\\infty\}on𝒴Δ⁡\(𝒴\)\\Y^\{\\Delta\(\\Y\)\}equipped with the productσ\\sigma\-algebra such that if\(ZP\)P∈Δ⁡\(𝒴\)∼Γ∞\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\Y\)\}\\sim\\Gamma\_\{\\infty\}, then for everyk≥1k\\geq 1and every finite collection of probability measures𝐏=\(P1,…,Pk\)\\mathbf\{P\}=\(P\_\{1\},\.\.\.,P\_\{k\}\),\(ZP1,…,ZPk\)∼Γk​\(𝐏,⋅\)\(Z\_\{P\_\{1\}\},\.\.\.,Z\_\{P\_\{k\}\}\)\\sim\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)\. In particular, for everyP∈Δ⁡\(𝒴\)P\\in\\Delta\(\\Y\),ZP∼PZ\_\{P\}\\sim Pand for everyP,Q∈Δ⁡\(𝒴\)P,Q\\in\\Delta\(\\Y\),Pr\[ZP≠ZQ\]≤2TV\(P,Q\)\\Pr\[Z\_\{P\}\\neq Z\_\{Q\}\]\\leq 2\\TV\(P,Q\)\. In other words,Γ∞\\Gamma\_\{\\infty\}is a grand coupling of all probability measure inΔ⁡\(𝒴\)\\Delta\(\\Y\), i\.e\.Γ∞\\Gamma\_\{\\infty\}is fixed by the family\(Γk\)k\(\\Gamma\_\{k\}\)\_\{k\}and does not depend on any particular finite tuple\.

###### Proof\.

Consider index setT=Δ⁡\(𝒴\)T=\\Delta\(\\Y\)and the coordinate spacesSP=𝒴S\_\{P\}=\\YforP∈TP\\in T\. For every finite subsetI=\{P1,…,Pk\}⊆TI=\\\{P\_\{1\},\.\.\.,P\_\{k\}\\\}\\subseteq T, we choose an arbitrary ordering\(P1,…,Pk\)\(P\_\{1\},\.\.\.,P\_\{k\}\)\. Under the natural isomorphism,\(yP\)P∈I→\(yPi\)i∈\[k\]\(y\_\{P\}\)\_\{P\\in I\}\\rightarrow\(y\_\{P\_\{i\}\}\)\_\{i\\in\[k\]\}, we defineμI\\mu\_\{I\}to be the probability measure onSI=∏Pi∈I𝒴=𝒴IS\_\{I\}=\\prod\_\{P\_\{i\}\\in I\}\\Y=\\Y^\{I\}, corresponding toΓk​\(\(P1,…,Pk\),⋅\)\\Gamma\_\{k\}\(\(P\_\{1\},\.\.\.,P\_\{k\}\);\\cdot\)\. Note that such definition is independent of the chosen ordering, since for any other ordering of the form\(Pσ⁡\(1\),…,Pσ⁡\(k\)\)\(P\_\{\\sigma\(1\)\},\.\.\.,P\_\{\\sigma\(k\)\}\)with arbitrary permutationσ\\sigmaof\[k\]\[k\], Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)shows that\(Zσ⁡\(1\),…,Zσ⁡\(k\)\)∼Γk​\(\(Pσ⁡\(1\),…,Pσ⁡\(k\)\),⋅\)\\big\(Z\_\{\\sigma\(1\)\},\\dots,Z\_\{\\sigma\(k\)\}\\big\)\\sim\\Gamma\_\{k\}\\big\(\(P\_\{\\sigma\(1\)\},\\dots,P\_\{\\sigma\(k\)\}\);\\cdot\\big\)if\(Z1,…,Zk\)∼Γk​\(\(P1,…,Pk\),⋅\)\(Z\_\{1\},\\dots,Z\_\{k\}\)\\sim\\Gamma\_\{k\}\\big\(\(P\_\{1\},\\dots,P\_\{k\}\);\\cdot\\big\)\. Hence, the two orderings induce the same law on the coordinate\-indexed space𝒴I\.\\Y^\{I\}\.

Now letJ⊆IJ\\subseteq I\. Using the same ordering, projective consistency in Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)implies\(prJ\)\#​μI=μJ\(\\mathrm\{pr\}\_\{J\}\)\_\{\\\#\}\\mu\_\{I\}=\\mu\_\{J\}, whereprJ:𝒴I↦𝒴J\\mathrm\{pr\}\_\{J\}:\\Y^\{I\}\\mapsto\\Y^\{J\}is the coordinate projection\. Hence,\(μI\)I\(\\mu\_\{I\}\)\_\{I\}is a projective family, and thus, the Kolmogorov Extension Theorem\[[31](https://arxiv.org/html/2610.28878#bib.bib46)\]yields random variables\(ZP\)P∈Δ⁡\(𝒴\)\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\Y\)\}withZP∈𝒴Z\_\{P\}\\in\\Ysuch that for every finite collection of distinct measuresI=\{P1,…,Pk\}I=\\\{P\_\{1\},\.\.\.,P\_\{k\}\\\},\(ZP1,…,ZPk\)∼Γk​\(\(P1,…,Pk\),⋅\)\(Z\_\{P\_\{1\}\},\.\.\.,Z\_\{P\_\{k\}\}\)\\sim\\Gamma\_\{k\}\(\(P\_\{1\},\.\.\.,P\_\{k\}\);\\cdot\)\. LetΓ∞=Law⁡\(\(ZP\)P∈Δ⁡\(𝒴\)\)\\Gamma\_\{\\infty\}=\\mathrm\{Law\}\(\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\Y\)\}\), which is a probability measure on𝒴Δ⁡\(𝒴\)\\Y^\{\\Delta\(\\Y\)\}equipped with its productσ\\sigma\-algebra\.

It remains to remove the distinctness assumption\. Fix an arbitrary tuple𝐏=\(P1,…,Pk\)∈Tk\\mathbf\{P\}=\(P\_\{1\},\.\.\.,P\_\{k\}\)\\in T^\{k\}and letQ1,…,QnQ\_\{1\},\.\.\.,Q\_\{n\}be the distinct measures \(in the same ordering\) in𝐏\\mathbf\{P\}, wherePi=Qπ⁡\(i\)P\_\{i\}=Q\_\{\\pi\(i\)\}for some mapπ:\[k\]↦\[n\]\\pi:\[k\]\\mapsto\[n\]\. Now define a duplication enlargement mapTπ:𝒴n↦𝒴kT\_\{\\pi\}:\\Y^\{n\}\\mapsto\\Y^\{k\}, whereTπ​\(y1,…,yn\)=\(yπ⁡\(1\),…,yπ⁡\(k\)\)T\_\{\\pi\}\(y\_\{1\},\.\.\.,y\_\{n\}\)=\(y\_\{\\pi\(1\)\},\.\.\.,y\_\{\\pi\(k\)\}\)\. SinceQQ’s are distinct, it follows that\(ZQ1,…,ZQn\)∼Γn​\(\(Q1,…,Qn\),⋅\)\(Z\_\{Q\_\{1\}\},\.\.\.,Z\_\{Q\_\{n\}\}\)\\sim\\Gamma\_\{n\}\(\(Q\_\{1\},\.\.\.,Q\_\{n\}\);\\cdot\)\. Moreover, since\(ZP\)P∈Δ⁡\(𝒴\)∼Γ∞\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\Y\)\}\\sim\\Gamma\_\{\\infty\}is indexed by the probability measures themselves,Pi=Qπ⁡\(i\)P\_\{i\}=Q\_\{\\pi\(i\)\}implies thatZPi=ZQπ⁡\(i\)Z\_\{P\_\{i\}\}=Z\_\{Q\_\{\\pi\(i\)\}\}is the same coordinate of the grand coupling, so it follows that\(ZP1,…,ZPk\)=Tπ​\(ZQ1,…,ZQn\)\(Z\_\{P\_\{1\}\},\\ldots,Z\_\{P\_\{k\}\}\)=T\_\{\\pi\}\(Z\_\{Q\_\{1\}\},\.\.\.,Z\_\{Q\_\{n\}\}\)pointwise\. Therefore,LawΓ∞​\(ZP1,…,ZPk\)=\(Tπ\)\#​Γn​\(\(Q1,…,Qn\),⋅\)\.\\mathrm\{Law\}\_\{\\Gamma\_\{\\infty\}\}\(Z\_\{P\_\{1\}\},\.\.\.,Z\_\{P\_\{k\}\}\)=\(T\_\{\\pi\}\)\_\{\\\#\}\\Gamma\_\{n\}\(\(Q\_\{1\},\.\.\.,Q\_\{n\}\);\\cdot\)\.

Next, it suffices to show that\(Tπ\)\#​Γn​\(\(Q1,…,Qn\),⋅\)=Γk​\(𝐏,⋅\)\(T\_\{\\pi\}\)\_\{\\\#\}\\Gamma\_\{n\}\(\(Q\_\{1\},\.\.\.,Q\_\{n\}\);\\cdot\)=\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)\. Now considerE=\{r1,…,rn\}E=\\\{r\_\{1\},\.\.\.,r\_\{n\}\\\}whererj=min⁡\{i∈\[k\]:Pi=Qj\}r\_\{j\}=\\min\\\{i\\in\[k\]:P\_\{i\}=Q\_\{j\}\\\}is the first representative coordinate forQjQ\_\{j\}in𝐏\\mathbf\{P\}\. By projection consistency, we have\(prE\)\#​Γk​\(𝐏,⋅\)=Γn​\(\(Q1,…,Qn\),⋅\)\(\\mathrm\{pr\}\_\{E\}\)\_\{\\\#\}\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=\\Gamma\_\{n\}\(\(Q\_\{1\},\.\.\.,Q\_\{n\}\);\\cdot\)sinceQQ’s are distinct\. Also note thatΓk​\(𝐏,Di​j\)≤2​TV⁡\(Pi,Pj\)=0\\Gamma\_\{k\}\(\\mathbf\{P\};D\_\{ij\}\)\\leq 2\\TV\(P\_\{i\},P\_\{j\}\)=0ifPi=PjP\_\{i\}=P\_\{j\}, so for\(Y1,…,Yk\)∼Γk​\(𝐏,⋅\)\(Y\_\{1\},\.\.\.,Y\_\{k\}\)\\sim\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\),Yi=Yrπ⁡\(i\)Y\_\{i\}=Y\_\{r\_\{\\pi\(i\)\}\}a\.s\., and thus\(Y1,…,Yk\)=Tπ​\(Yr1,…,Yrn\)\(Y\_\{1\},\.\.\.,Y\_\{k\}\)=T\_\{\\pi\}\(Y\_\{r\_\{1\}\},\.\.\.,Y\_\{r\_\{n\}\}\)a\.s\. Hence,Γk​\(𝐏,⋅\)=\(Tπ\)\#​Law​\(Yr1,…,Yrn\)=\(Tπ\)\#​Γn​\(\(Q1,…,Qn\),⋅\)=LawΓ∞​\(ZP1,…,ZPk\)\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)=\(T\_\{\\pi\}\)\_\{\\\#\}\\mathrm\{Law\}\(Y\_\{r\_\{1\}\},\.\.\.,Y\_\{r\_\{n\}\}\)=\(T\_\{\\pi\}\)\_\{\\\#\}\\Gamma\_\{n\}\(\(Q\_\{1\},\.\.\.,Q\_\{n\}\);\\cdot\)=\\mathrm\{Law\}\_\{\\Gamma\_\{\\infty\}\}\(Z\_\{P\_\{1\}\},\.\.\.,Z\_\{P\_\{k\}\}\)\. Thus, we have shown that for everyk≥1k\\geq 1and every tuple𝐏∈Δ​\(𝒴\)k\\mathbf\{P\}\\in\\Delta\(\\Y\)^\{k\}that could contain repeated measures,\(ZP1,…,ZPk\)∼Γk​\(𝐏,⋅\)\(Z\_\{P\_\{1\}\},\.\.\.,Z\_\{P\_\{k\}\}\)\\sim\\Gamma\_\{k\}\(\\mathbf\{P\};\\cdot\)\.

Finally, for allP∈Δ⁡\(𝒴\)P\\in\\Delta\(\\Y\), takingI=\{P\}I=\\\{P\\\}yieldsZP∼Γ1​\(P,⋅\)Z\_\{P\}\\sim\\Gamma\_\{1\}\(P;\\cdot\), and by Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5),Γ1​\(P,⋅\)=P\\Gamma\_\{1\}\(P;\\cdot\)=P, soZP∼PZ\_\{P\}\\sim P\. For allP,Q∈Δ⁡\(𝒴\)P,Q\\in\\Delta\(\\Y\), takingI=\{P,Q\}I=\\\{P,Q\\\}yields\(ZP,ZQ\)∼Γ2​\(\(P,Q\),⋅\)\(Z\_\{P\},Z\_\{Q\}\)\\sim\\Gamma\_\{2\}\(\(P,Q\);\\cdot\), soPr\[ZP≠ZQ\]=Γ2\(\(P,Q\);D12\)\\Pr\[Z\_\{P\}\\neq Z\_\{Q\}\]=\\Gamma\_\{2\}\(\(P,Q\);D\_\{12\}\)forD12=\{\(y1,y2\)∈𝒴2:y1≠y2\}D\_\{12\}=\\\{\(y\_\{1\},y\_\{2\}\)\\in\\Y^\{2\}:y\_\{1\}\\neq y\_\{2\}\\\}\. By the disagreement bound in Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5), it follows thatPr\[ZP≠ZQ\]=Γ2\(\(P,Q\);D12\)≤2TV\(P,Q\)\\Pr\[Z\_\{P\}\\neq Z\_\{Q\}\]=\\Gamma\_\{2\}\(\(P,Q\);D\_\{12\}\)\\leq 2\\TV\(P,Q\)\. ∎

Having established the existence of the global measureΓ∞\\Gamma\_\{\\infty\}, we now formally confirm that it constitutes a grand coupling scheme onΔ⁡\(𝒴\)\\Delta\(\\mathcal\{Y\}\), and trivially after restriction, on any subset𝒫\\mathcal\{P\}\.

###### Corollary A\.7\(Grand coupling schemeΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}from Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)\)\.

The family of random variables\(ZP\)P∈Δ⁡\(𝒴\)∼Γ∞\(Z\_\{P\}\)\_\{P\\in\\Delta\(\\mathcal\{Y\}\)\}\\sim\\Gamma\_\{\\infty\}constructed in Corollary[A\.6](https://arxiv.org/html/2610.28878#A1.Thmtheorem6)constitutes a universal grand coupling scheme on the entire spaceΔ⁡\(𝒴\)\\Delta\(\\Y\)\. Consequently, its trivial restriction\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}yields a valid grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}on any subset𝒫⊆Δ⁡\(𝒴\)\\P\\subseteq\\Delta\(\\Y\)\.

###### Proof\.

G1 and G2 directly follows from Corollary[A\.6](https://arxiv.org/html/2610.28878#A1.Thmtheorem6), and G3 follows from Proposition[A\.5](https://arxiv.org/html/2610.28878#A1.Thmtheorem5)\. The restriction to any subset𝒫\\mathcal\{P\}preserves all three properties trivially\.Thus, the joint law of\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}yields the desired grand coupling schemeΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}\. ∎

## Appendix BPrivate synthetic data sampler

In this section, we apply the grand coupling schemes developed in Section[3](https://arxiv.org/html/2610.28878#S3)to construct a differentially private synthetic data sampler\. In particular, we formally prove the privacy and utility guarantees ofAggregate\(Algorithm[1](https://arxiv.org/html/2610.28878#alg1)\) andSampler\(Algorithm[2](https://arxiv.org/html/2610.28878#alg2)\), presented in Section[4](https://arxiv.org/html/2610.28878#S4)\.

Throughout, let𝒴=𝒳ℓ\\Y=\\X^\{\\ell\}, where𝒳\\mathcal\{X\}is the data universe andℓ\\ellis the size of the synthetic dataset, and the space of probability measures of interest is𝒫=\{qℓ:q∈ℱ\}\\P=\\\{q^\{\\ell\}:q\\in\\mathcal\{F\}\\\}, whereℱ\\mathcal\{F\}contains the ground\-truth distribution class𝒬\\Qand all possible outputs of the base learner\.

### B\.1Aggregate: Tuple\-Level Privacy and Utility

We establish the privacy and utility guarantees ofAggregate\(Algorithm[1](https://arxiv.org/html/2610.28878#alg1)\), instantiated with any grand coupling scheme on𝒫\\Psatisfying Definition[3\.1](https://arxiv.org/html/2610.28878#S3.Thmtheorem1)\.

#### Tuple\-Level Privacy\.

Recall that we use a change\-by\-one adjacency notion for neighboring tuples, i\.e\.,𝐪=\(q1,…,qk\)\\mathbf\{q\}=\(q\_\{1\},\\dots,q\_\{k\}\)and𝐪′=\(q1′,…,qk′\)\\mathbf\{q\}^\{\\prime\}=\(q\_\{1\}^\{\\prime\},\\dots,q\_\{k\}^\{\\prime\}\)are neighboring if they differ in at most one coordinate\.

The privacy argument relies on using the grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}to jointly evaluate the algorithm on both𝐪\\qand𝐪′\\q^\{\\prime\}\. Since the joint law of𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\\mathsf\{Couple\}\_\{k\}\(\\q\), and likewise for𝐪′\\q^\{\\prime\}, inAggregate\(Algorithm[1](https://arxiv.org/html/2610.28878#alg1)\) is simply a finite\-dimensional marginal of the global measureΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}101010For𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨\\mathsf\{Couple\\\_I\}\(Construction[A\.1](https://arxiv.org/html/2610.28878#A1.Thmtheorem1)\), the joint law of\(Z1,…,Zk\)∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\(Z\_\{1\},\\dots,Z\_\{k\}\)\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\q\)\)is the\(q1ℓ,…,qkℓ\)\(q\_\{1\}^\{\\ell\},\\dots,q\_\{k\}^\{\\ell\}\)\-coordinate marginal of the explicit couplingΓ\\Gammaon𝒫=\{qℓ:q∈ℱ\}\\mathcal\{P\}=\\\{q^\{\\ell\}:q\\in\\mathcal\{F\}\\\}\. For𝖢𝗈𝗎𝗉𝗅𝖾​\_​𝖨𝖨\\mathsf\{Couple\\\_II\}\(Construction[A\.4](https://arxiv.org/html/2610.28878#A1.Thmtheorem4)\), it is the corresponding finite\-dimensional marginal of the grand couplingΓ∞\\Gamma\_\{\\infty\}on𝒴Δ⁡\(𝒴\)\\mathcal\{Y\}^\{\\Delta\(\\mathcal\{Y\}\)\}, where𝒴=𝒳ℓ\\mathcal\{Y\}=\\mathcal\{X\}^\{\\ell\}\., we can evaluate both executions on a single probability space\.

Specifically, rather than drawing independent samples fromℒ​\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\q\)\)andℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪′\)\)\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\q^\{\\prime\}\)\), respectively, we construct an analysis coupling from a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}\\sim\\Gamma\_\{\\P\}, settingZ~i=Zqiℓ\\tilde\{Z\}\_\{i\}=Z\_\{q\_\{i\}^\{\\ell\}\}for input𝐪\\qandZ~i′=Z\(qi′\)ℓ\\tilde\{Z\}^\{\\prime\}\_\{i\}=Z\_\{\(q\_\{i\}^\{\\prime\}\)^\{\\ell\}\}for input𝐪′\\q^\{\\prime\}\. For every unchanged coordinatei≠ji\\neq j,qi=qi′q\_\{i\}=q\_\{i\}^\{\\prime\}impliesZqiℓ=Z\(qi′\)ℓZ\_\{q\_\{i\}^\{\\ell\}\}=Z\_\{\(q\_\{i\}^\{\\prime\}\)^\{\\ell\}\}pointwise\. Consequently, the realized input vectors\(Z~1,…,Z~k\)\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\)and\(Z~1′,…,Z~k′\)\(\\tilde\{Z\}^\{\\prime\}\_\{1\},\\dots,\\tilde\{Z\}^\{\\prime\}\_\{k\}\)differ in at most a single coordinatejjfor*every realization*ofΓ𝒫\\Gamma\_\{\\P\}\. Therefore, since neighboring input tuples yield pointwise neighboring vectors underΓ𝒫\\Gamma\_\{\\P\}, the\(ε,δ\)\(\\varepsilon,\\delta\)\-DP guarantee of𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}transfers directly toAggregate\.

###### Proposition B\.1\(Privacy ofAggregate\)\.

If𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP, thenAggregatein Algorithm[1](https://arxiv.org/html/2610.28878#alg1)is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\.111111For𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}, adjacency is defined as replacing a single datasetZiZ\_\{i\}in\(Z1,…,Zk\)\(Z\_\{1\},\\dots,Z\_\{k\}\); forAggregate, adjacency is defined as replacing a single distributionqiq\_\{i\}in𝐪=\(q1,…,qk\)\\mathbf\{q\}=\(q\_\{1\},\\dots,q\_\{k\}\)\.

###### Proof\.

Fix a pair of neighboring tuples𝐪=\(q1,…,qk\)\\q=\(q\_\{1\},\.\.\.,q\_\{k\}\)and𝐪′=\(q1′,…,qk′\)\\q^\{\\prime\}=\(q\_\{1\}^\{\\prime\},\.\.\.,q\_\{k\}^\{\\prime\}\), whereqi=qi′q\_\{i\}=q\_\{i\}^\{\\prime\}for alli≠ji\\neq j\. LetPi=qiℓP\_\{i\}=q\_\{i\}^\{\\ell\}andPi′=qi′ℓP\_\{i\}^\{\\prime\}=q\_\{i\}^\{\\prime\\ell\}\. Hence,Pi=Pi′P\_\{i\}=P\_\{i\}^\{\\prime\}for alli≠ji\\neq j\. We denote𝐏=\(P1,…,Pk\)\\mathbf\{P\}=\(P\_\{1\},\.\.\.,P\_\{k\}\)and𝐏′=\(P1′,…,Pk′\)\\mathbf\{P\}^\{\\prime\}=\(P\_\{1\}^\{\\prime\},\.\.\.,P\_\{k\}^\{\\prime\}\)

By Definition[3\.1](https://arxiv.org/html/2610.28878#S3.Thmtheorem1), let\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\P\}be the grand coupling scheme on𝒫\\Pused in𝖢𝗈𝗎𝗉𝗅𝖾k\\mathsf\{Couple\}\_\{k\}, and, on the common probability space where\(ZP\)P∈𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}is defined, we construct the vectors𝐙~=\(ZP1,…,ZPk\)\\tilde\{\\mathbf\{Z\}\}=\(Z\_\{P\_\{1\}\},\\dots,Z\_\{P\_\{k\}\}\)and𝐙~′=\(ZP1′,…,ZPk′\)\\tilde\{\\mathbf\{Z\}\}^\{\\prime\}=\(Z\_\{P\_\{1\}^\{\\prime\}\},\\dots,Z\_\{P\_\{k\}^\{\\prime\}\}\)\. Note that the joint law of the output of𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)is exactly the marginal lawℒ⁡\(ZP1,…,ZPk\)\\mathcal\{L\}\(Z\_\{P\_\{1\}\},\\dots,Z\_\{P\_\{k\}\}\), and similarly for𝐪′\\q^\{\\prime\}, by property G3, so it follows that𝐙~​=d​𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\\tilde\{\\mathbf\{Z\}\}\\overset\{\\text\{d\}\}\{=\}\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)and𝐙~′​=d​𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪′\)\\tilde\{\\mathbf\{Z\}\}^\{\\prime\}\\overset\{\\text\{d\}\}\{=\}\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}^\{\\prime\}\)\.

Furthermore, sincePi=Pi′P\_\{i\}=P\_\{i\}^\{\\prime\}for alli≠ji\\neq j, we haveZ~i=Z~i′\\tilde\{Z\}\_\{i\}=\\tilde\{Z\}\_\{i\}^\{\\prime\}pointwise for alli≠ji\\neq j\. Thus, the vectors\(Z~1,…,Z~k\)\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\)and\(Z~1′,…,Z~k′\)\(\\tilde\{Z\}\_\{1\}^\{\\prime\},\\dots,\\tilde\{Z\}\_\{k\}^\{\\prime\}\)are neighboring\. LetM⁡\(𝐙,B\)M\(\\mathbf\{Z\};B\)denote the probability that𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}outputs an element of a measurable setBBon input𝐙\\mathbf\{Z\}\. SinceMMis\(ε,δ\)\(\\varepsilon,\\delta\)\-DP and our coupled input vectors are adjacent a\.s\.,M⁡\(\(Z~1,…,Z~k\),B\)≤eε​M​\(\(Z~1′,…,Z~k′\),B\)\+δM\(\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\);B\)\\leq e^\{\\varepsilon\}M\(\(\\tilde\{Z\}\_\{1\}^\{\\prime\},\\dots,\\tilde\{Z\}\_\{k\}^\{\\prime\}\);B\)\+\\delta\. Taking the expectation over the global measureΓ\\Gammayields:

Pr\[Aggregate\(𝐪\)∈B\]\\displaystyle\\Pr\[\\textsc\{Aggregate\}\(\\mathbf\{q\}\)\\in B\]=EΓ​\[M⁡\(\(Z~1,…,Z~k\),B\)\]\\displaystyle=\\mbox\{\\bf E\}\_\{\\Gamma\}\[M\(\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\);B\)\]≤eε​EΓ​\[M⁡\(\(Z~1′,…,Z~k′\),B\)\]\+δ\\displaystyle\\leq e^\{\\varepsilon\}\\mbox\{\\bf E\}\_\{\\Gamma\}\[M\(\(\\tilde\{Z\}\_\{1\}^\{\\prime\},\\dots,\\tilde\{Z\}\_\{k\}^\{\\prime\}\);B\)\]\+\\delta=eεPr\[Aggregate\(𝐪′\)∈B\]\+δ\.\\displaystyle=e^\{\\varepsilon\}\\Pr\[\\textsc\{Aggregate\}\(\\mathbf\{q\}^\{\\prime\}\)\\in B\]\+\\delta\.A symmetric argument holds for the reverse direction\. ∎

#### Tuple\-Level Utility

We next show that if a large majority of the input distributionsqiq\_\{i\}are close to a target ground\-truth distributionppin TV, then the output ofAggregatematches an ideal drawpℓ∼pℓp^\{\\ell\}\\sim p^\{\\ell\}with high probability, and is thus close topℓp^\{\\ell\}in TV\.

As in the privacy analysis, the utility guarantee relies on constructing an analysis coupling from the grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}\. Specifically, for input distributions𝐪=\(q1,…,qk\)∈ℱk\\q=\(q\_\{1\},\\dots,q\_\{k\}\)\\in\\mathcal\{F\}^\{k\}and a target distributionp∈ℱp\\in\\mathcal\{F\}, we take a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\P\}\\sim\\Gamma\_\{\\P\}and defineZ~i=Zqiℓ\\tilde\{Z\}\_\{i\}=Z\_\{q\_\{i\}^\{\\ell\}\}for eachi∈\[k\]i\\in\[k\], alongside an unobserved “ghost” sampleZ~∗=Zpℓ\\tilde\{Z\}\_\{\*\}=Z\_\{p^\{\\ell\}\}, indexed by the ground\-truth product distributionpℓ∈𝒫p^\{\\ell\}\\in\\P\. Sinceℒ​\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)\)andℒ​\(𝖢𝗈𝗎𝗉𝗅𝖾1​\(𝐩\)\)\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{1\}\(\\mathbf\{p\}\)\)are simply a finite\-dimensional marginal of the global measureΓ𝒫\\Gamma\_\{\\mathcal\{P\}\}, so our construction from the grand coupling schemeΓ𝒫\\Gamma\_\{\\P\}satisfies\(Z~1,…,Z~k\)∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\(\\tilde\{Z\}\_\{1\},\.\.\.,\\tilde\{Z\}\_\{k\}\)\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)\)andZ~∗∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾1​\(p\)\)=pℓ\\tilde\{Z\}\_\{\*\}\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{1\}\(p\)\)=p^\{\\ell\}, by property G3 and G1\.

We emphasize thatZ~∗\\tilde\{Z\}\_\{\*\}is never computed by the algorithm, as it is adjoined purely for the analysis\. For every accurate distributionqiq\_\{i\}whereTV⁡\(qi,p\)≤η\\mathrm\{TV\}\(q\_\{i\},p\)\\leq\\eta, property G2 guarantees thatZ~i=Z~∗\\tilde\{Z\}\_\{i\}=\\tilde\{Z\}\_\{\*\}except with probability at most2​ℓ​η2\\ell\\eta\. Consequently, when7/87/8of theqiq\_\{i\}areη\\eta\-close topp, an overwhelming majority of the coupled samplesZ~i\\tilde\{Z\}\_\{i\}collapse onto the exact same valueZ~∗∼pℓ\\tilde\{Z\}\_\{\*\}\\sim p^\{\\ell\}pointwise, creating a large frequency gap required for𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}to succeed\.

###### Proposition B\.2\(Utility ofAggregate\)\.

Fixp∈𝒬⊆ℱp\\in\\Q\\subseteq\\mathcal\{F\}and a tuple𝐪=\(q1,…,qk\)∈ℱk\\q=\(q\_\{1\},\.\.\.,q\_\{k\}\)\\in\\mathcal\{F\}^\{k\}\. DenoteJ=\{j∈\[k\]:TV⁡\(qj,p\)≤η\}J=\\\{j\\in\[k\]:\\TV\(q\_\{j\},p\)\\leq\\eta\\\}for some fixedη\\eta\. Suppose𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}outputs the mode with probability at least1−β𝖲𝖡𝖬1\-\\beta\_\{\\mathsf\{SBM\}\}, if the frequency gap \(between the mode and the second most frequently occurring element\) is at leastτ\\tau\. Then, for everyc∈\(0,1\)c\\in\(0,1\)such that2​\(1−c\)​\|J\|−k≥τ2\(1\-c\)\|J\|\-k\\geq\\tau,TV⁡\(ℒ⁡\(Aggregate​\(𝐪\)\),pℓ\)≤2​ℓ​ηc\+β𝖲𝖡𝖬\\TV\(\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\),p^\{\\ell\}\)\\leq\\frac\{2\\ell\\eta\}\{c\}\+\\beta\_\{\\mathsf\{SBM\}\}

###### Proof\.

Fix a tuple𝐪=\(q1,…,qk\)∈ℱk\\q=\(q\_\{1\},\.\.\.,q\_\{k\}\)\\in\\mathcal\{F\}^\{k\}and a ground truthp∈𝒬p\\in\\Q\. LetPi=qiℓP\_\{i\}=q\_\{i\}^\{\\ell\}andP∗=pℓP\_\{\*\}=p^\{\\ell\}\. We construct an analysis coupling using a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}\\sim\\Gamma\_\{\\mathcal\{P\}\}from our grand coupling scheme\. We evaluate the coordinates corresponding to the input distributions, settingZ~i=ZPi\\tilde\{Z\}\_\{i\}=Z\_\{P\_\{i\}\}fori∈\[k\]i\\in\[k\], alongside an unobserved “ghost” sampleZ~∗=ZP∗\\tilde\{Z\}\_\{\*\}=Z\_\{P\_\{\*\}\}\. By properties \(G1\) and \(G3\),\(Z~1,…,Z~k\)∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\)\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)\)andZ~∗∼pℓ\\tilde\{Z\}\_\{\*\}\\sim p^\{\\ell\}\. Similar to the proof of Proposition[B\.1](https://arxiv.org/html/2610.28878#A2.Thmtheorem1), we construct an analysis coupling using a single draw\(ZP\)P∈𝒫∼Γ𝒫\(Z\_\{P\}\)\_\{P\\in\\mathcal\{P\}\}\\sim\\Gamma\_\{\\mathcal\{P\}\}from our grand coupling scheme\. Specifically, we consider the coordinates corresponding to the input distributions, settingZ~i=ZPi\\tilde\{Z\}\_\{i\}=Z\_\{P\_\{i\}\}fori∈\[k\]i\\in\[k\], alongside an unobserved “ghost” sampleZ~∗=ZP∗\\tilde\{Z\}\_\{\*\}=Z\_\{P\_\{\*\}\}\. By properties G1 and G3,\(Z~1,…,Z~k\)∼ℒ⁡\(𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\)\(\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{k\}\)\\sim\\mathcal\{L\}\(\\mathsf\{Couple\}\_\{k\}\(\\mathbf\{q\}\)\)andZ~∗∼𝖢𝗈𝗎𝗉𝗅𝖾1​\(p\)=pℓ\\tilde\{Z\}\_\{\*\}\\sim\\mathsf\{Couple\}\_\{1\}\(p\)=p^\{\\ell\}\.

By the disagreement bound \(G2\), we havePr\[Z~i≠Z~∗\]≤2TV\(Pi,P∗\)=2TV\(qiℓ,pℓ\)\\Pr\[\\tilde\{Z\}\_\{i\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq 2\\TV\(P\_\{i\},P\_\{\*\}\)=2\\TV\(q\_\{i\}^\{\\ell\},p^\{\\ell\}\)for alli∈\[k\]i\\in\[k\]\. For indices in our accurate setJ=\{j∈\[k\]:TV⁡\(qj,p\)≤η\}J=\\\{j\\in\[k\]:\\TV\(q\_\{j\},p\)\\leq\\eta\\\}, this impliesPr\[Z~j≠Z~∗\]≤2ℓη\\Pr\[\\tilde\{Z\}\_\{j\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq 2\\ell\\eta\.

Consider the indicatorIj=1\{Z~j≠Z~∗\}I\_\{j\}=1\\\{\\tilde\{Z\}\_\{j\}\\neq\\tilde\{Z\}\_\{\*\}\\\}for allj∈Jj\\in J\. We have thatE​\[∑j∈JIj\]≤2​ℓ​η​\|J\|\\mbox\{\\bf E\}\[\\sum\_\{j\\in J\}I\_\{j\}\]\\leq 2\\ell\\eta\|J\|, and by Markov’s inequality, we havePr\[∑j∈JIj\>c\|J\|\]≤2​ℓ​ηc\\Pr\[\\sum\_\{j\\in J\}I\_\{j\}\>c\|J\|\]\\leq\\frac\{2\\ell\\eta\}\{c\}\. On the event∑j∈JIj≤c​\|J\|\\sum\_\{j\\in J\}I\_\{j\}\\leq c\|J\|, there are at least\|J\|−∑j∈JIj≥\(1−c\)​\|J\|\|J\|\-\\sum\_\{j\\in J\}I\_\{j\}\\geq\(1\-c\)\|J\|coordinates of\(Z~1,…,Z~k\)\(\\tilde\{Z\}\_\{1\},\.\.\.,\\tilde\{Z\}\_\{k\}\)equal toZ~∗\\tilde\{Z\}\_\{\*\}\. Since2​\(1−c\)​\|J\|−k≥τ\>02\(1\-c\)\|J\|\-k\\geq\\tau\>0, by our choice ofcc, it follows that\(1−c\)​\|J\|\>k/2\(1\-c\)\|J\|\>k/2, ensuringZ~∗\\tilde\{Z\}\_\{\*\}appears in a strict majority of thekkcoordinates\. Consequently,Z~∗\\tilde\{Z\}\_\{\*\}is the unique mode, any competing element appears at mostk−\(1−c\)​\|J\|k\-\(1\-c\)\|J\|times, and the frequency gap satisfies,2​\(1−c\)​\|J\|−k≥τ2\(1\-c\)\|J\|\-k\\geq\\tau\.

LetZ~\\tilde\{Z\}be the output obtained by applying𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}on the analysis\-coupled vector\(Z~1,…,Z~k\)\(\\tilde\{Z\}\_\{1\},\.\.\.,\\tilde\{Z\}\_\{k\}\), as in Algorithm[1](https://arxiv.org/html/2610.28878#alg1)\. Since\(Z~1,…,Z~k\)​=d​𝖢𝗈𝗎𝗉𝗅𝖾k​\(𝐪\)\(\\tilde\{Z\}\_\{1\},\.\.\.,\\tilde\{Z\}\_\{k\}\)\\overset\{\\text\{d\}\}\{=\}\\mathsf\{Couple\}\_\{k\}\(\\q\), it follows thatZ~​=d​Aggregate​\(𝐪\)\\tilde\{Z\}\\overset\{\\text\{d\}\}\{=\}\\textsc\{Aggregate\}\(\\q\)\. Hence,\(Z~,Z~∗\)\(\\tilde\{Z\},\\tilde\{Z\}\_\{\*\}\)is indeed a coupling ofℒ​\(Aggregate​\(𝐪\)\)\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\)andpℓp^\{\\ell\}\.

By the accuracy guarantee of𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}, we havePr⁡\[Z~≠Z~∗\|∑j∈JIj≤c​\|J\|\]≤β𝖲𝖡𝖬\\Pr\[\\tilde\{Z\}\\neq\\tilde\{Z\}\_\{\*\}\|\\sum\_\{j\\in J\}I\_\{j\}\\leq c\|J\|\]\\leq\\beta\_\{\\mathsf\{SBM\}\}\. Thus,Pr\[Z~≠Z~∗\]≤β𝖲𝖡𝖬\+2​ℓ​ηc\\Pr\[\\tilde\{Z\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq\\beta\_\{\\mathsf\{SBM\}\}\+\\frac\{2\\ell\\eta\}\{c\}\. Additionally,TV\(ℒ\(Aggregate\(𝐪\)\),pℓ\)=TV\(ℒ\(Z~\),ℒ\(Z~∗\)\)≤Pr\[Z~≠Z~∗\]≤β𝖲𝖡𝖬\+2​ℓ​ηc\\TV\(\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\),p^\{\\ell\}\)=\\TV\(\\mathcal\{L\}\(\\tilde\{Z\}\),\\mathcal\{L\}\(\\tilde\{Z\}\_\{\*\}\)\)\\leq\\Pr\[\\tilde\{Z\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq\\beta\_\{\\mathsf\{SBM\}\}\+\\frac\{2\\ell\\eta\}\{c\}\. ∎

To complete the utility guarantee, we instantiate the mode mechanism step with the stability\-based mode mechanism\[[46](https://arxiv.org/html/2610.28878#bib.bib47),[47](https://arxiv.org/html/2610.28878#bib.bib36)\], whose privacy and accuracy properties are recalled below\.

###### Fact B\.3\(Stability\-based mode, Proposition 3\.4 from\[[47](https://arxiv.org/html/2610.28878#bib.bib36)\];\[[46](https://arxiv.org/html/2610.28878#bib.bib47)\]\)\.

For everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\)andm∈ℕm\\in\\mathbb\{N\}, there exists an\(ε,δ\)\(\\varepsilon,\\delta\)\-DP mechanismM:𝒳m→𝒳M:\\mathcal\{X\}^\{m\}\\to\\mathcal\{X\}such that if the difference in counts between the mode of𝒳m\\mathcal\{X\}^\{m\}and the second most frequently occurring element is larger than4​log⁡\(1/δ\)/ε4\\log\(1/\\delta\)/\\varepsilon,M⁡\(x\)M\(x\)outputs the mode with probability at least1−δ1\-\\delta\.

We can now synthesize these components\. By combining our tuple\-level privacy guarantee \(in Proposition[B\.1](https://arxiv.org/html/2610.28878#A2.Thmtheorem1)\), the utility bound of our analysis coupling \(Proposition[B\.2](https://arxiv.org/html/2610.28878#A2.Thmtheorem2)\), and the accuracy of the mode mechanism \(Fact[B\.3](https://arxiv.org/html/2610.28878#A2.Thmtheorem3)\), we obtain the final privacy and utility guarantee for theAggregatesubroutine, stated below\.

###### Corollary B\.4\.

Letβ,ε,δ∈\(0,1\)\\beta,\\varepsilon,\\delta\\in\(0,1\),ℓ∈ℕ\+\\ell\\in\\mathbb\{N\}^\{\+\}be parameters\. Setη=β64​ℓ\\eta=\\frac\{\\beta\}\{64\\ell\},δ0=min⁡\{δ,β/4\}\\delta\_\{0\}=\\min\\\{\\delta,\\beta/4\\\}, and choosekksuch thatk≥8​log⁡\(4/β\)\+log⁡\(1/δ\)εk\\geq 8\\frac\{\\log\(4/\\beta\)\+\\log\(1/\\delta\)\}\{\\varepsilon\}\. ThenAggregate, with𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}instantiated using parameters\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)as in Fact[B\.3](https://arxiv.org/html/2610.28878#A2.Thmtheorem3), is\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\. Moreover, for anyp∈𝒬p\\in\\Qand input tuple𝐪∈ℱk\\mathbf\{q\}\\in\\mathcal\{F\}^\{k\}, if\|\{j∈\[k\]:TV⁡\(qj,p\)≤η\}\|≥7​k/8\|\\\{j\\in\[k\]:\\TV\(q\_\{j\},p\)\\leq\\eta\\\}\|\\geq 7k/8, thenTV⁡\(ℒ⁡\(Aggregate​\(𝐪\)\),pℓ\)≤β/2\\TV\(\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\),p^\{\\ell\}\)\\leq\\beta/2\.

###### Proof\.

By Proposition[B\.1](https://arxiv.org/html/2610.28878#A2.Thmtheorem1),Aggregateis\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP, since𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}is\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\. For utility, takeτ=4​log⁡\(1/δ0\)/ε\\tau=4\\log\(1/\\delta\_\{0\}\)/\\varepsilonandβ𝖲𝖡𝖬=δ0\\beta\_\{\\mathsf\{SBM\}\}=\\delta\_\{0\}from Fact[B\.3](https://arxiv.org/html/2610.28878#A2.Thmtheorem3), and choosec=1/8c=1/8\. It is not hard to verify that2​\(1−c\)​\|J\|−k≥k/2≥τ2\(1\-c\)\|J\|\-k\\geq k/2\\geq\\tau\. Proposition[B\.2](https://arxiv.org/html/2610.28878#A2.Thmtheorem2)therefore gives a coupling\(Z~,Z~∗\)\(\\tilde\{Z\},\\tilde\{Z\}\_\{\*\}\)such thatZ~​=d​Aggregate​\(𝐪\)\\tilde\{Z\}\\overset\{\\text\{d\}\}\{=\}\\textsc\{Aggregate\}\(\\q\),Z~∗​=d​pℓ\\tilde\{Z\}\_\{\*\}\\overset\{\\text\{d\}\}\{=\}p^\{\\ell\}, andPr\[Z~≠Z~∗\]≤β𝖲𝖡𝖬\+2​ℓ​ηc=δ0\+β/4≤β/2\\Pr\[\\tilde\{Z\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq\\beta\_\{\\mathsf\{SBM\}\}\+\\frac\{2\\ell\\eta\}\{c\}=\\delta\_\{0\}\+\\beta/4\\leq\\beta/2\. Consequently,TV⁡\(ℒ⁡\(Aggregate​\(𝐪\)\),pℓ\)≤β/2\\TV\(\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\),p^\{\\ell\}\)\\leq\\beta/2∎

### B\.2Sampler: End\-to\-End Private Correlated Sampling from Samples

We establish the privacy and utility guarantees ofSampler\(Algorithm[2](https://arxiv.org/html/2610.28878#alg2)\), which takes a datasetS∈𝒳nS\\in\\X^\{n\}as input\. Here, two datasetsS,S′∈𝒳nS,S^\{\\prime\}\\in\\X^\{n\}are adjacent if they differ in at most one record\.

###### Proposition B\.5\(Privacy ofSampler\)\.

If𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}inAggregateis\(ε,δ\)\(\\varepsilon,\\delta\)\-DP, thenSampleris\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\.121212For𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}, adjacency is defined as replacing a single datasetZiZ\_\{i\}in\(Z1,…,Zk\)\(Z\_\{1\},\\dots,Z\_\{k\}\); adjacency is defined as replacing a single recordXjX\_\{j\}in the raw datasetS=\(X1,…,Xn\)∈𝒳nS=\(X\_\{1\},\\dots,X\_\{n\}\)\\in\\mathcal\{X\}^\{n\}

###### Proof\.

Fix neighboring datasetsS=\(X1,…,Xn\)S=\(X\_\{1\},\.\.\.,X\_\{n\}\)andS′=\(X1′,…,Xn′\)S^\{\\prime\}=\(X\_\{1\}^\{\\prime\},\.\.\.,X\_\{n\}^\{\\prime\}\)such thatXi=Xi′X\_\{i\}=X\_\{i\}^\{\\prime\}for alli≠ji\\neq j\.

We first couple the data\-independent randomness used in the two executions onSSandS′S^\{\\prime\}\. Specifically, we draw a single permutationΠ∼U⁡\(𝒮n\)\\Pi\\sim\\mathrm\{U\}\(\\mathcal\{S\}\_\{n\}\)and a single collection of learner seedsU1,…,Uk​∼i\.i\.d\.​U​\(\[0,1\]\)U\_\{1\},\.\.\.,U\_\{k\}\\overset\{\\text\{i\.i\.d\.\}\}\{\\sim\}\\mathrm\{U\}\(\[0,1\]\)independently of data, and use the same realizations of them in both executions\.

Now fix a realization\(π,u1,…,uk\)\(\\pi,u\_\{1\},\.\.\.,u\_\{k\}\)\. Denote the partitions as\(si\)i\(s\_\{i\}\)\_\{i\}and\(si′\)i\(s\_\{i\}^\{\\prime\}\)\_\{i\}on the two executions\. Letaabe the block id containing the positionπ−1​\(j\)\\pi^\{\-1\}\(j\), i\.e\. the position occupied by the differing data coordinate under permutation\. SinceXi=Xi′X\_\{i\}=X\_\{i\}^\{\\prime\}for alli≠ji\\neq j, it follows thatsi=si′s\_\{i\}=s\_\{i\}^\{\\prime\}for alli≠ai\\neq a\. Therefore, with the same learner seeduiu\_\{i\}used onsis\_\{i\}andsi′s\_\{i\}^\{\\prime\}, it follows thatqi=L⁡\(si,ui\)=L⁡\(si′,ui\)=qi′q\_\{i\}=L\(s\_\{i\};u\_\{i\}\)=L\(s\_\{i\}^\{\\prime\};u\_\{i\}\)=q\_\{i\}^\{\\prime\}for alli≠ai\\neq a\. Hence, for every fixed realization of the data\-independent randomness, the induced tuples𝐪=\(q1,…,qk\)\\q=\(q\_\{1\},\.\.\.,q\_\{k\}\)and𝐪′=\(q1′,…,qk′\)\\q^\{\\prime\}=\(q\_\{1\}^\{\\prime\},\.\.\.,q\_\{k\}^\{\\prime\}\)differ in at most one coordinate\.

LetM⁡\(𝐪,B\)M\(\\q;B\)denote the probability thatAggregate\(𝐪\)\(\\q\)lies in a measurable setB⊆𝒳ℓB\\subseteq\\X^\{\\ell\}\. Since𝖲𝗍𝖺𝖻𝗂𝗅𝗂𝗍𝗒𝖡𝖺𝗌𝖾𝖽𝖬𝗈𝖽𝖾\\mathsf\{StabilityBasedMode\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP, by Proposition[B\.1](https://arxiv.org/html/2610.28878#A2.Thmtheorem1),Aggregateis\(ε,δ\)\(\\varepsilon,\\delta\)\-DP under change\-by\-one adjacency on input tuple\. Hence, for every realization\(π,u1,…,uk\)\(\\pi,u\_\{1\},\\ldots,u\_\{k\}\),M⁡\(𝐪,B\)≤eε​M​\(𝐪′,B\)\+δM\(\\q;B\)\\leq e^\{\\varepsilon\}M\(\\q^\{\\prime\};B\)\+\\delta\. Averaging over the shared data\-independent randomness yields

Pr\[Sampler\(S\)∈B\]\\displaystyle\\Pr\[\\textsc\{Sampler\}\(S\)\\in B\]=EΠ,\(Ui\)i∈\[k\]​\[M⁡\(𝐪,B\)\]\\displaystyle=\\mbox\{\\bf E\}\_\{\\Pi,\(U\_\{i\}\)\_\{i\\in\[k\]\}\}\[M\(\\q;B\)\]≤eε​EΠ,\(Ui\)i∈\[k\]​\[M⁡\(𝐪′,B\)\]\+δ\\displaystyle\\leq e^\{\\varepsilon\}\\mbox\{\\bf E\}\_\{\\Pi,\(U\_\{i\}\)\_\{i\\in\[k\]\}\}\[M\(\\q^\{\\prime\};B\)\]\+\\delta=eεPr\[Sampler\(S′\)∈B\]\+δ,\\displaystyle=e^\{\\varepsilon\}\\Pr\[\\textsc\{Sampler\}\(S^\{\\prime\}\)\\in B\]\+\\delta,and similarly for the reverse direction\. Therefore,Sampleris\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\. ∎

###### Proposition B\.6\(Utility ofSampler\)\.

Fix a base learnerLLfor𝒬\\Q\. Letε\>0\\varepsilon\>0,β,δ∈\(0,1\)\\beta,\\delta\\in\(0,1\),ℓ∈ℕ\+\\ell\\in\\mathbb\{N\}^\{\+\}be parameters\. Setη=β64​ℓ\\eta=\\frac\{\\beta\}\{64\\ell\},δ0=min⁡\{δ,β/4\}\\delta\_\{0\}=\\min\\\{\\delta,\\beta/4\\\}, and choosekksuch thatk≥max⁡\{8ε​log⁡\(4β​δ\),128​log⁡\(4β\)\}k\\geq\\max\\left\\\{\\frac\{8\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\beta\\delta\}\\right\),128\\log\\left\(\\frac\{4\}\{\\beta\}\\right\)\\right\\\}\. Letb∈ℕ\+b\\in\\mathbb\{N\}^\{\+\}be a sample size such that, for everyp∈𝒬p\\in\\Q, ifSi∼pbS\_\{i\}\\sim p^\{b\}andUi∼U⁡\(\[0,1\]\)U\_\{i\}\\sim\\mathrm\{U\}\(\[0,1\]\)independently,Pr\[TV\(L\(Si;Ui\),p\)≥η\]≤1/16\\Pr\[\\TV\(L\(S\_\{i\};U\_\{i\}\),p\)\\geq\\eta\]\\leq 1/16\.

Setn=k​bn=kb\. Then, for everyp∈𝒬⊆ℱp\\in\\Q\\subseteq\\mathcal\{F\}andS∼pnS\\sim p^\{n\},TV⁡\(ℒ⁡\(Sampler​\(S\)\),pℓ\)≤3​β/4\\TV\(\\mathcal\{L\}\(\\textsc\{Sampler\}\(S\)\),p^\{\\ell\}\)\\leq 3\\beta/4\. Thus,Sampleris an\(ℓ,3​β/4\)\(\\ell,3\\beta/4\)\-approximate sampler for𝒬\\Qin the sense of Definition[1\.4](https://arxiv.org/html/2610.28878#S1.Thmtheorem4)\.

###### Proof\.

Fixp∈𝒬p\\in\\Q\. We first show that, with high probability, at least7​k/87k/8of the learner outputs areη\\eta\-close topp\. Note that\(Xπ⁡\(1\),…,Xπ⁡\(n\)\)∼pn\(X\_\{\\pi\(1\)\},\\ldots,X\_\{\\pi\(n\)\}\)\\sim p^\{n\}, for any fixed permutationπ\\pi, sinceS∼pnS\\sim p^\{n\}\. Hence, conditional onΠ=π\\Pi=\\pi, the blocksS1,…,SkS\_\{1\},\.\.\.,S\_\{k\}, whereSi=\(Xπ⁡\(\(i−1\)​b\+1\),…,Xπ⁡\(i​b\)\)S\_\{i\}=\(X\_\{\\pi\(\(i\-1\)b\+1\)\},\.\.\.,X\_\{\\pi\(ib\)\}\), are independent andSi∼pbS\_\{i\}\\sim p^\{b\}for everyi\.i\.Moreover, the learner seedsU1,…,UkU\_\{1\},\.\.\.,U\_\{k\}remain independent conditional onΠ=π\\Pi=\\pi, and are independent of the dataSS\. Therefore, conditional onΠ=π\\Pi=\\pi,\(Si,Ui\),…,\(Sk,Uk\)\(S\_\{i\},U\_\{i\}\),\.\.\.,\(S\_\{k\},U\_\{k\}\)are independent, and thus, the learner outputsqi=L⁡\(Si,Ui\)q\_\{i\}=L\(S\_\{i\};U\_\{i\}\)are independent\.

Now define indicatorsIi=1\{TV\(qi,p\)\>η\}I\_\{i\}=1\\\{\\TV\(q\_\{i\},p\)\>\\eta\\\}for eachi∈\[k\]i\\in\[k\]\. By the accuracy guarantee of the learner,Pr⁡\[Ii=1\|Π=π\]≤1/16\\Pr\[I\_\{i\}=1\|\\Pi=\\pi\]\\leq 1/16for everyii, and thus,I1,…,IkI\_\{1\},\.\.\.,I\_\{k\}are independent Bernoulli with means at most1/161/16, conditional onΠ=π\\Pi=\\pi\. By Hoeffding’s inequality,Pr\[∑i=1kIi≥k/8\|Π=π\]≤exp\(−2k\(1/8−1/16\)2\)=e−k/128≤β/4\\Pr\[\\sum\_\{i=1\}^\{k\}I\_\{i\}\\geq k/8\|\\Pi=\\pi\]\\leq\\exp\(\-2k\(1/8\-1/16\)^\{2\}\)=e^\{\-k/128\}\\leq\\beta/4\. Since this holds uniformly for every realizationπ\\pi, so taking an expectation overΠ\\PiyieldsPr\[∑i=1kIi≥k/8\]≤β/4\\Pr\[\\sum\_\{i=1\}^\{k\}I\_\{i\}\\geq k/8\]\\leq\\beta/4, i\.e\.Pr⁡\[Ec\]≤β/4\\Pr\[E^\{c\}\]\\leq\\beta/4, whereE=\{\|\{i∈\[k\]:TV\(qi,p\)≤η\}\|≥7​k8\}E=\\\{\|\\\{i\\in\[k\]:\\TV\(q\_\{i\},p\)\\leq\\eta\\\}\|\\geq\\frac\{7k\}\{8\}\\\}\.

By Corollary[B\.4](https://arxiv.org/html/2610.28878#A2.Thmtheorem4), every realized𝐪\\qthat satisfiesEE, satisfiesTV⁡\(ℒ⁡\(Aggregate​\(𝐪\)\),pℓ\]≤β/2\\TV\(\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\),p^\{\\ell\}\]\\leq\\beta/2\. Note thatℒ\(Sampler\(S\)\|E\)=E\[ℒ\(Aggregate\(𝐪\)\|E\]\\mathcal\{L\}\(\\textsc\{Sampler\}\(S\)\|E\)=\\mbox\{\\bf E\}\[\\mathcal\{L\}\(\\textsc\{Aggregate\}\(\\q\)\|E\], soTV⁡\(ℒ⁡\(Sampler​\(S\)\|E\),pℓ\)≤β/2\\TV\(\\mathcal\{L\}\(\\textsc\{Sampler\}\(S\)\|E\),p^\{\\ell\}\)\\leq\\beta/2\. Thus,

TV⁡\(ℒ⁡\(Sampler​\(S\)\),pℓ\)\\displaystyle\\TV\(\\mathcal\{L\}\(\\textsc\{Sampler\}\(S\)\),p^\{\\ell\}\)≤Pr⁡\[E\]​TV⁡\(ℒ⁡\(Sampler​\(S\)\|E\),pℓ\)\\displaystyle\\leq\\Pr\[E\]\\TV\(\\mathcal\{L\}\(\\textsc\{Sampler\}\(S\)\|E\),p^\{\\ell\}\)\+Pr⁡\[Ec\]​TV⁡\(ℒ⁡\(Sampler​\(S\)\|Ec\),pℓ\)\\displaystyle\+\\Pr\[E^\{c\}\]\\TV\(\\mathcal\{L\}\(\\textsc\{Sampler\}\(S\)\|E^\{c\}\),p^\{\\ell\}\)≤β/2\+Pr⁡\[Ec\]≤β/2\+β/4=3​β/4\.\\displaystyle\\leq\\beta/2\+\\Pr\[E^\{c\}\]\\leq\\beta/2\+\\beta/4=3\\beta/4\.Finally, by the coupling characterization of total variation distance, there exists a coupling\(Z~,Z~∗\)\(\\tilde\{Z\},\\tilde\{Z\}\_\{\*\}\)such thatZ~​=d​Sampler​\(S\)\\tilde\{Z\}\\overset\{\\text\{d\}\}\{=\}\\textsc\{Sampler\}\(S\),Z~∗​=d​pℓ\\tilde\{Z\}\_\{\*\}\\overset\{\\text\{d\}\}\{=\}p^\{\\ell\}, andPr\[Z~≠Z~∗\]≤3β/4\\Pr\[\\tilde\{Z\}\\neq\\tilde\{Z\}\_\{\*\}\]\\leq 3\\beta/4\. Thus,Sampleris an\(ℓ,3​β/4\)\(\\ell,3\\beta/4\)\-correlated sampler for𝒬\\Q\. ∎

Combining the dataset\-level privacy guarantee of Proposition[B\.5](https://arxiv.org/html/2610.28878#A2.Thmtheorem5)with the utility guarantee of Proposition[B\.6](https://arxiv.org/html/2610.28878#A2.Thmtheorem6)yields the formal guarantee for the end\-to\-end pipelineSampler\.

###### Corollary B\.7\.

Under the same setting as[B\.6](https://arxiv.org/html/2610.28878#A2.Thmtheorem6),Sampleris\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\(ℓ,3​β/4\)\(\\ell,3\\beta/4\)\-approximate sampler for𝒬\\Qin the sense of Definition[1\.4](https://arxiv.org/html/2610.28878#S1.Thmtheorem4)\.

## Appendix CAgnostic private distribution learning

In this section, we extend our main result beyond the realizable setting\. We show that if a class of distributions is agnostic learnable, then it is also agnostic private learnable\. The following is the definition of agnostic learnability\.

###### Definition C\.1\(CC\-agnostic learnability\)\.

LetC≥1C\\geq 1and let𝒬⊆Δ⁡\(𝒳\)\\Q\\subseteq\\Delta\(\\mathcal\{X\}\)be nonempty\. We say that𝒬\\Qis*CC\-agnostically learnable with sample complexitym:\(0,1\)2→ℕ≥1m:\(0,1\)^\{2\}\\to\\mathbb\{N\}\_\{\\geq 1\}*if there exists a randomized learnerL:𝒳∗→Δ⁡\(𝒳\)L:\\mathcal\{X\}^\{\*\}\\to\\Delta\(\\mathcal\{X\}\)such that, for everyα,β∈\(0,1\)\\alpha,\\beta\\in\(0,1\)andp∈Δ⁡\(𝒳\)p\\in\\Delta\(\\mathcal\{X\}\), given a sample setS∼pm⁡\(α,β\)S\\sim p^\{m\(\\alpha,\\beta\)\}, the learner’s outputp^=L⁡\(S\)\\hat\{p\}=L\(S\)satisfiesTV⁡\(p^,p\)≤C​OPT⁡\(p\)\+α\\TV\(\\hat\{p\},p\)\\leq C\\operatorname\{OPT\}\(p\)\+\\alphawith probability at least≥1−β\\geq 1\-\\beta, where the probability is over the samples and the learner’s internal randomness, andOPT⁡\(p\)≔infq∈𝒬TV⁡\(p,q\)\\operatorname\{OPT\}\(p\)\\coloneqq\\inf\_\{q\\in\\Q\}\\TV\(p,q\),

###### Theorem C\.2\(General agnostic private reduction\)\.

Let𝒳\\mathcal\{X\}be standard Borel andC≥1C\\geq 1\. If𝒬⊆Δ⁡\(𝒳\)\\Q\\subseteq\\Delta\(\\mathcal\{X\}\)isCC\-agnostically learnable with sample complexitym⁡\(α,β\)m\(\\alpha,\\beta\), then, for everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\), it is also\(8​C2\+9​C\)\(8C^\{2\}\+9C\)\-agnostically learnable under\(ε,δ\)\(\\varepsilon,\\delta\)\-differential privacy, with sample complexityn0​\(α,β,ε,δ\)=O⁡\(m⁡\(α16​\(C\+3\),116\)​m​\(2​αC\+3,β\)​1ε​log⁡\(4​\(C\+3\)α​δ\)\)n\_\{0\}\(\\alpha,\\beta,\\varepsilon,\\delta\)=O\\left\(m\\left\(\\frac\{\\alpha\}\{16\(C\+3\)\},\\frac\{1\}\{16\}\\right\)m\\left\(\\frac\{2\\alpha\}\{C\+3\},\\beta\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\(C\+3\)\}\{\\alpha\\delta\}\\right\)\\right\)for everyα,β∈\(0,1\)\\alpha,\\beta\\in\(0,1\)\. The reduction preserves properness\.

###### Proof\.

LetLLbe aCC\-agnostic learner witnessing Definition[C\.1](https://arxiv.org/html/2610.28878#A3.Thmtheorem1)with sample complexitymm\. Seta=αC\+3a=\\frac\{\\alpha\}\{C\+3\},b=m⁡\(a16,116\)b=m\\left\(\\frac\{a\}\{16\},\\frac\{1\}\{16\}\\right\),T=m⁡\(2​a,β\)T=m\(2a,\\beta\),δ0=min⁡\{δ,a4\}\\delta\_\{0\}=\\min\\left\\\{\\delta,\\frac\{a\}\{4\}\\right\\\}, andk=⌈max⁡\{16ε​log⁡\(1δ0\),128​log⁡\(4a\)\}⌉k=\\left\\lceil\\max\\left\\\{\\frac\{16\}\{\\varepsilon\}\\log\\left\(\\frac\{1\}\{\\delta\_\{0\}\}\\right\),128\\log\\left\(\\frac\{4\}\{a\}\\right\)\\right\\\}\\right\\rceil\. Letn0=T​k​bn\_\{0\}=Tkb\.

We use Algorithm[7](https://arxiv.org/html/2610.28878#alg7)with the parameters chosen above\. Each call toSamplerinvokes Algorithm[2](https://arxiv.org/html/2610.28878#alg2)on a batchSj∈𝒳k​bS\_\{j\}\\in\\mathcal\{X\}^\{kb\}, usingkkblocks of sizebband base learnerLbaseL\_\{\\mathrm\{base\}\}, and returns one private sampleZj∈𝒳Z\_\{j\}\\in\\mathcal\{X\}\. We instantiateSamplerwith ambient familyℱ=Δ⁡\(𝒳\)\\mathcal\{F\}=\\Delta\(\\mathcal\{X\}\), the coupling implementation from Algorithm[6](https://arxiv.org/html/2610.28878#alg6), and privacy parameters\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\. All invocations use fresh randomness, independent of the outer permutation and of one another\. The final invocation ofLLreceives\(Z1,…,ZT\)\(Z\_\{1\},\\ldots,Z\_\{T\}\)and returnsq^\\widehat\{q\}using independent randomness\.

For inputs larger thann0n\_\{0\}, we use only the firstn0n\_\{0\}observations\. For inputs smaller thann0n\_\{0\}, we return a fixed element of𝒬\\Q\.

Privacy\.By Proposition[B\.5](https://arxiv.org/html/2610.28878#A2.Thmtheorem5), each invocation ofSampleris\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\. Conditioned on the data\-independent outer permutation, the invocations use disjoint sets of records\. Parallel composition \(Lemma[2\.5](https://arxiv.org/html/2610.28878#S2.Thmtheorem5)\) therefore implies that\(Z1,…,ZT\)\(Z\_\{1\},\\ldots,Z\_\{T\}\)is\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\. Averaging over the permutation preserves this guarantee\. The final estimate is post\-processing, so by Proposition[2\.4](https://arxiv.org/html/2610.28878#S2.Thmtheorem4)the learner is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP becauseδ0≤δ\\delta\_\{0\}\\leq\\delta\. The fixed output on insufficient data is also private\. If the assumed learnability is proper, chooseLLproper; the final estimate and the fixed output then both belong to𝒬\\Q\.

Utility\.Fixp∈Δ⁡\(𝒳\)p\\in\\Delta\(\\mathcal\{X\}\), writeOPT≔infq∈𝒬TV⁡\(p,q\)\\operatorname\{OPT\}\\coloneqq\\inf\_\{q\\in\\Q\}\\TV\(p,q\), and consider one invocation ofSampleronS0∼pk​bS\_\{0\}\\sim p^\{kb\}\. Letq1,…,qkq\_\{1\},\\ldots,q\_\{k\}be its base learner outputs and setη=C​OPT\+a16\\eta=C\\operatorname\{OPT\}\+\\frac\{a\}\{16\}\. By the agnostic guarantee ofLLand the choice ofbb,Pr\[TV\(qi,p\)≤η\]≥1516\\Pr\\left\[\\TV\(q\_\{i\},p\)\\leq\\eta\\right\]\\geq\\frac\{15\}\{16\}for everyi∈\[k\]i\\in\[k\]\.

LetJ=\{i∈\[k\]:TV⁡\(qi,p\)≤η\}J=\\left\\\{i\\in\[k\]:\\TV\(q\_\{i\},p\)\\leq\\eta\\right\\\}andE=\{\|J\|≥7​k8\}E=\\left\\\{\|J\|\\geq\\frac\{7k\}\{8\}\\right\\\}\. Independence of the blocks and learner randomness implies that the events\{TV\(qi,p\)\>η\}\\\{\\TV\(q\_\{i\},p\)\>\\eta\\\}are independent, each with probability at most116\\frac\{1\}\{16\}\. Thus, Hoeffding’s inequality givesPr\[Ec\]≤exp\(−2k\(18−116\)2\)=e−k/128≤a4\\Pr\[E^\{c\}\]\\leq\\exp\\left\(\-2k\\left\(\\frac\{1\}\{8\}\-\\frac\{1\}\{16\}\\right\)^\{2\}\\right\)=e^\{\-k/128\}\\leq\\frac\{a\}\{4\}\.

By Fact[B\.3](https://arxiv.org/html/2610.28878#A2.Thmtheorem3), the mode mechanism instantiated with\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)hasτ=4ε​log⁡\(1δ0\)\\tau=\\frac\{4\}\{\\varepsilon\}\\log\\left\(\\frac\{1\}\{\\delta\_\{0\}\}\\right\)andβ𝖲𝖡𝖬=δ0\\beta\_\{\\mathsf\{SBM\}\}=\\delta\_\{0\}\. OnEE, takingc=14c=\\frac\{1\}\{4\}, our choice ofkkensures2​\(1−c\)​\|J\|−k≥5​k16≥k4≥τ2\(1\-c\)\|J\|\-k\\geq\\frac\{5k\}\{16\}\\geq\\frac\{k\}\{4\}\\geq\\tau\.

For each tuple𝐪\\mathbf\{q\}, letμ𝐪≔ℒ⁡\(𝖠𝗀𝗀𝗋𝖾𝗀𝖺𝗍𝖾⁡\(𝐪\)\)\\mu\_\{\\mathbf\{q\}\}\\coloneqq\\mathcal\{L\}\(\\mathsf\{Aggregate\}\(\\mathbf\{q\}\)\)\. By Proposition[B\.2](https://arxiv.org/html/2610.28878#A2.Thmtheorem2)withℓ=1\\ell=1, onEEwe haveTV⁡\(μ𝐪,p\)≤8​η\+δ0\\TV\(\\mu\_\{\\mathbf\{q\}\},p\)\\leq 8\\eta\+\\delta\_\{0\}\. This holds with probability at least1−e−k/128≥1−a41\-e^\{\-k/128\}\\geq 1\-\\frac\{a\}\{4\}over the block data and base learner randomness\.

LetRp≔ℒ⁡\(𝖲𝖺𝗆𝗉𝗅𝖾𝗋⁡\(S0\)\)R\_\{p\}\\coloneqq\\mathcal\{L\}\(\\mathsf\{Sampler\}\(S\_\{0\}\)\), where the law includes both the randomness ofS0∼pk​bS\_\{0\}\\sim p^\{kb\}and the sampler’s internal randomness\. By Algorithm[2](https://arxiv.org/html/2610.28878#alg2)and the law of total probability, for every measurableB⊆𝒳B\\subseteq\\mathcal\{X\},Rp​\(B\)=𝔼𝐪​\[μ𝐪​\(B\)\]R\_\{p\}\(B\)=\\mathbb\{E\}\_\{\\mathbf\{q\}\}\[\\mu\_\{\\mathbf\{q\}\}\(B\)\]\. Consequently,

TV⁡\(Rp,p\)\\displaystyle\\TV\(R\_\{p\},p\)=supB\|𝔼𝐪​\[μ𝐪​\(B\)−p⁡\(B\)\]\|\\displaystyle=\\sup\_\{B\}\\left\|\\mathbb\{E\}\_\{\\mathbf\{q\}\}\[\\mu\_\{\\mathbf\{q\}\}\(B\)\-p\(B\)\]\\right\|≤𝔼𝐪​\[supB\|μ𝐪​\(B\)−p⁡\(B\)\|\]\\displaystyle\\leq\\mathbb\{E\}\_\{\\mathbf\{q\}\}\\left\[\\sup\_\{B\}\|\\mu\_\{\\mathbf\{q\}\}\(B\)\-p\(B\)\|\\right\]=𝔼𝐪​\[TV⁡\(μ𝐪,p\)\]\\displaystyle=\\mathbb\{E\}\_\{\\mathbf\{q\}\}\[\\TV\(\\mu\_\{\\mathbf\{q\}\},p\)\]≤\(8​η\+δ0\)​Pr⁡\[E\]\+Pr⁡\[Ec\]\\displaystyle\\leq\(8\\eta\+\\delta\_\{0\}\)\\Pr\[E\]\+\\Pr\[E^\{c\}\]≤8η\+δ0\+e−k/128\\displaystyle\\leq 8\\eta\+\\delta\_\{0\}\+e^\{\-k/128\}≤8​C​OPT\+a2\+a4\+a4\\displaystyle\\leq 8C\\operatorname\{OPT\}\+\\frac\{a\}\{2\}\+\\frac\{a\}\{4\}\+\\frac\{a\}\{4\}=8​C​OPT\+a\.\\displaystyle=8C\\operatorname\{OPT\}\+a\.
The data\-independent permutation preserves the joint distributionpT​k​bp^\{Tkb\}, so the batchesS1,…,STS\_\{1\},\\ldots,S\_\{T\}are independent, each with distributionpk​bp^\{kb\}\. Each invocation applies the sameSampler, with the same parameters and independent randomness\. Hence, for everyj∈\[T\]j\\in\[T\],ℒ⁡\(Zj\)=Rp\\mathcal\{L\}\(Z\_\{j\}\)=R\_\{p\}\. Since eachZjZ\_\{j\}depends only onSjS\_\{j\}and the randomness of its invocation, the outputs are independent\. Therefore,\(Z1,…,ZT\)∼RpT\(Z\_\{1\},\\ldots,Z\_\{T\}\)\\sim R\_\{p\}^\{T\}\.

Applying theCC\-agnostic guarantee ofLLwithT=m⁡\(2​a,β\)T=m\(2a,\\beta\)samples fromRpR\_\{p\}gives

TV⁡\(q^,Rp\)≤C​infq∈𝒬TV⁡\(q,Rp\)\+2​a\\TV\(\\widehat\{q\},R\_\{p\}\)\\leq C\\inf\_\{q\\in\\Q\}\\TV\(q,R\_\{p\}\)\+2awith probability at least1−β1\-\\beta\. By the triangle inequality,infq∈𝒬TV⁡\(q,Rp\)≤OPT\+TV⁡\(p,Rp\)\\inf\_\{q\\in\\Q\}\\TV\(q,R\_\{p\}\)\\leq\\operatorname\{OPT\}\+\\TV\(p,R\_\{p\}\)\. Thus, on the same event,

TV⁡\(q^,p\)\\displaystyle\\TV\(\\widehat\{q\},p\)≤TV⁡\(q^,Rp\)\+TV⁡\(Rp,p\)\\displaystyle\\leq\\TV\(\\widehat\{q\},R\_\{p\}\)\+\\TV\(R\_\{p\},p\)≤C​OPT\+\(C\+1\)​TV⁡\(Rp,p\)\+2​a\\displaystyle\\leq C\\operatorname\{OPT\}\+\(C\+1\)\\TV\(R\_\{p\},p\)\+2a≤C​OPT\+\(C\+1\)​\(8​C​OPT\+a\)\+2​a\\displaystyle\\leq C\\operatorname\{OPT\}\+\(C\+1\)\(8C\\operatorname\{OPT\}\+a\)\+2a=\(8​C2\+9​C\)​OPT\+\(C\+3\)​a\\displaystyle=\(8C^\{2\}\+9C\)\\operatorname\{OPT\}\+\(C\+3\)a=\(8​C2\+9​C\)​OPT\+α\.\\displaystyle=\(8C^\{2\}\+9C\)\\operatorname\{OPT\}\+\\alpha\.
Finally,log⁡\(1δ0\)=max⁡\{log⁡\(1δ\),log⁡\(4a\)\}≤log⁡\(4a​δ\)\\log\\left\(\\frac\{1\}\{\\delta\_\{0\}\}\\right\)=\\max\\left\\\{\\log\\left\(\\frac\{1\}\{\\delta\}\\right\),\\log\\left\(\\frac\{4\}\{a\}\\right\)\\right\\\}\\leq\\log\\left\(\\frac\{4\}\{a\\delta\}\\right\)\. Sinceε∈\(0,1\)\\varepsilon\\in\(0,1\),k=O⁡\(1ε​log⁡\(4a​δ\)\)k=O\\left\(\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{a\\delta\}\\right\)\\right\)\. Therefore,

n0=T​k​b\\displaystyle n\_\{0\}=Tkb=O⁡\(m⁡\(a16,116\)​m​\(2​a,β\)​1ε​log⁡\(4a​δ\)\)\\displaystyle=O\\left\(m\\left\(\\frac\{a\}\{16\},\\frac\{1\}\{16\}\\right\)m\(2a,\\beta\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{a\\delta\}\\right\)\\right\)=O⁡\(m⁡\(α16​\(C\+3\),116\)​m​\(2​αC\+3,β\)​1ε​log⁡\(4​\(C\+3\)α​δ\)\),\\displaystyle=O\\left\(m\\left\(\\frac\{\\alpha\}\{16\(C\+3\)\},\\frac\{1\}\{16\}\\right\)m\\left\(\\frac\{2\\alpha\}\{C\+3\},\\beta\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\(C\+3\)\}\{\\alpha\\delta\}\\right\)\\right\),which proves the stated sample bound\. ∎

Next, we present a generic agnostic private learner based on the non\-private Minimum distance estimator of\[[23](https://arxiv.org/html/2610.28878#bib.bib17)\]\. This automatically gives an agnostic private learner for every countable class whose Yatracos class has finite VC dimension\.

###### Definition C\.3\(Yatracos class\)\.

Let𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)be a non\-empty class of distributions\. For every ordered pair\(q,q′\)∈𝒬\(q,q^\{\\prime\}\)\\in\\mathcal\{Q\}, fix a measurable setAq,q′⊆𝒳A\_\{q,q^\{\\prime\}\}\\subseteq\\mathcal\{X\}satisfyingq⁡\(Aq,q′\)−q′​\(Aq,q′\)=TV⁡\(q,q′\)q\(A\_\{q,q^\{\\prime\}\}\)\-q^\{\\prime\}\(A\_\{q,q^\{\\prime\}\}\)=\\operatorname\{TV\}\(q,q^\{\\prime\}\)131313When the distributions in𝒬\\mathcal\{Q\}have densitiesfqf\_\{q\}with respect to a common dominating measure, we takeAq,q′=\{x∈𝒳:fq​\(x\)\>fq′​\(x\)\}A\_\{q,q^\{\\prime\}\}=\\\{x\\in\\mathcal\{X\}:f\_\{q\}\(x\)\>f\_\{q^\{\\prime\}\}\(x\)\\\}, recovering the usual definition\.\. The corresponding Yatracos class is defined as:

Yat\(𝒬\)≔\{Aq,q′:q,q′∈𝒬\}\.\\operatorname\{Yat\}\(\\mathcal\{Q\}\)\\coloneqq\\\{A\_\{q,q^\{\\prime\}\}:q,q^\{\\prime\}\\in\\mathcal\{Q\}\\\}\.

###### Theorem C\.4\(Minimum\-distance estimator,\[[23](https://arxiv.org/html/2610.28878#bib.bib17)\]\)\.

LetC\>0C\>0be a sufficiently large universal constant andα,β∈\(0,1\)\\alpha,\\beta\\in\(0,1\)\. Let𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)be a nonempty countable141414The countability assumption is used \(as a sufficient condition\) only to avoid measurability issues\. Indeed, if𝒬\\mathcal\{Q\}is countable, thenYat⁡\(𝒬\)\\operatorname\{Yat\}\(\\mathcal\{Q\}\)is also countable, so the minimum\-distance objectiveD⁡\(S,q\)≔supA∈Yat⁡\(𝒬\)\|PS​\(A\)−q⁡\(A\)\|D\(S,q\)\\coloneqq\\sup\_\{A\\in\\operatorname\{Yat\}\(\\mathcal\{Q\}\)\}\|P\_\{S\}\(A\)\-q\(A\)\|is measurable inSSfor everyq∈𝒬q\\in\\mathcal\{Q\}\., wherePSP\_\{S\}is the empirical measure\. Fixing an enumeration of𝒬\\mathcal\{Q\}, we may therefore return the firstqqsatisfyingD⁡\(S,q\)≤infq′∈𝒬D⁡\(S,q′\)\+α/2D\(S,q\)\\leq\\inf\_\{q^\{\\prime\}\\in\\mathcal\{Q\}\}D\(S,q^\{\\prime\}\)\+\\alpha/2\. This selection is measurable, and the usual MDE analysis gives the stated guarantee after adjusting the universal constant\.class of distributions withd=VC⁡\(Yat⁡\(𝒬\)\)<∞d=\\operatorname\{VC\}\(\\operatorname\{Yat\}\(\\mathcal\{Q\}\)\)<\\infty\. There exists an algorithm, calledMDE\\mathrm\{MDE\}, that, for everyp∈Δ⁡\(𝒳\)p\\in\\Delta\(\\mathcal\{X\}\), given a datasetS∼pnS\\sim p^\{n\}of sizen≥C⁡\(d\+log⁡\(2/β\)\)/α2n\\geq C\(d\+\\log\(2/\\beta\)\)/\\alpha^\{2\}, returnsq^∈𝒬\\widehat\{q\}\\in\\mathcal\{Q\}satisfying

Pr\[TV\(q^,p\)≤3OPT\+α\]≥1−β,\\Pr\\\!\\left\[\\operatorname\{TV\}\(\\widehat\{q\},p\)\\leq 3\\operatorname\{OPT\}\+\\alpha\\right\]\\geq 1\-\\beta,whereOPT≔infq∈𝒬TV⁡\(p,q\)\\operatorname\{OPT\}\\coloneqq\\inf\_\{q\\in\\mathcal\{Q\}\}\\operatorname\{TV\}\(p,q\)\.

Algorithm 7AgnosticPrivateLearner1:Dataset

S=\(X1,…,Xn\)S=\(X\_\{1\},\\ldots,X\_\{n\}\)with

n=T​k​bn=Tkb, a non\-private

CC\-agnostic learner

LL, and parameters

a,b,k,T,β,ε,δ0a,b,k,T,\\beta,\\varepsilon,\\delta\_\{0\}\.

2:An estimate

q^∈Δ⁡\(𝒳\)\\widehat\{q\}\\in\\Delta\(\\mathcal\{X\}\)\.

3:Define

Lbase​\(D\)≔L⁡\(D,a16,116\)L\_\{\\mathrm\{base\}\}\(D\)\\coloneqq L\\left\(D;\\frac\{a\}\{16\},\\frac\{1\}\{16\}\\right\)\.

4:Draw a data\-independent permutation

Π∼U⁡\(𝒮n\)\\Pi\\sim\\mathrm\{U\}\(\\mathcal\{S\}\_\{n\}\)\.

5:foreach

j∈\[T\]j\\in\[T\]do

6:

Sj←\(XΠ⁡\(\(j−1\)​k​b\+1\),…,XΠ⁡\(j​k​b\)\)S\_\{j\}\\leftarrow\(X\_\{\\Pi\(\(j\-1\)kb\+1\)\},\\ldots,X\_\{\\Pi\(jkb\)\}\)\.

7:

Zj←Sampler​\(Sj,ℓ=1,k,b,Lbase,ε,δ0\)Z\_\{j\}\\leftarrow\\textsc\{Sampler\}\(S\_\{j\};\\ell=1,k,b,L\_\{\\mathrm\{base\}\},\\varepsilon,\\delta\_\{0\}\)\.

8:endfor

9:

q^←L⁡\(\(Z1,…,ZT\),2​a,β\)\\widehat\{q\}\\leftarrow L\\left\(\(Z\_\{1\},\\ldots,Z\_\{T\}\);2a,\\beta\\right\)\.

10:return

q^\\widehat\{q\}\.

The following corollary gives a generic agnostic private learner for any countable class with finiteVC⁡\(Yat⁡\(𝒬\)\)\\operatorname\{VC\}\(\\operatorname\{Yat\}\(\\mathcal\{Q\}\)\)\.

###### Corollary C\.5\(Agnostic private learning Yatracos classes\)\.

LetC\>0C\>0be a sufficiently large universal constant andα,β,ε,δ∈\(0,1\)\\alpha,\\beta,\\varepsilon,\\delta\\in\(0,1\)\. Let𝒬⊆Δ⁡\(𝒳\)\\mathcal\{Q\}\\subseteq\\Delta\(\\mathcal\{X\}\)be a nonempty countable class of distributions withd=VC⁡\(Yat⁡\(𝒬\)\)<∞d=\\operatorname\{VC\}\(\\operatorname\{Yat\}\(\\mathcal\{Q\}\)\)<\\infty\. There exists an\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially private algorithm that, for everyp∈Δ⁡\(𝒳\)p\\in\\Delta\(\\mathcal\{X\}\), given a datasetS∼pnS\\sim p^\{n\}of sizen≥C​\(d\+1\)​\(d\+log⁡\(2/β\)\)ε​α4​log⁡\(2α​δ\)n\\geq C\\frac\{\(d\+1\)\(d\+\\log\(2/\\beta\)\)\}\{\\varepsilon\\alpha^\{4\}\}\\log\(\\frac\{2\}\{\\alpha\\delta\}\), returnsq^∈𝒬\\widehat\{q\}\\in\\mathcal\{Q\}satisfying

Pr\[TV\(q^,p\)≤99OPT\+α\]≥1−β,\\Pr\\\!\\left\[\\operatorname\{TV\}\(\\widehat\{q\},p\)\\leq 99\\operatorname\{OPT\}\+\\alpha\\right\]\\geq 1\-\\beta,whereOPT≔infq∈𝒬TV⁡\(p,q\)\\operatorname\{OPT\}\\coloneqq\\inf\_\{q\\in\\mathcal\{Q\}\}\\operatorname\{TV\}\(p,q\)\.

###### Proof\.

In Algorithm[7](https://arxiv.org/html/2610.28878#alg7), takeL⁡\(D,t,ρ\)≔MDE⁡\(D,t,ρ\)L\(D;t,\\rho\)\\coloneqq\\mathrm\{MDE\}\(D;t,\\rho\)\. By Theorem[C\.4](https://arxiv.org/html/2610.28878#A3.Thmtheorem4), this is a proper33\-agnostic learner for𝒬\\Qwith sample complexitym⁡\(t,ρ\)=⌈C0​d\+log⁡\(2/ρ\)t2⌉m\(t,\\rho\)=\\left\\lceil C\_\{0\}\\frac\{d\+\\log\\left\(2/\\rho\\right\)\}\{t^\{2\}\}\\right\\rceil, whereC0C\_\{0\}is a universal constant\.

Theorem[C\.2](https://arxiv.org/html/2610.28878#A3.Thmtheorem2)therefore makes Algorithm[7](https://arxiv.org/html/2610.28878#alg7)\(ε,δ\)\(\\varepsilon,\\delta\)\-DP and guaranteesq^∈𝒬\\widehat\{q\}\\in\\QwithTV⁡\(q^,p\)≤99​OPT\+α\\TV\(\\widehat\{q\},p\)\\leq 99\\operatorname\{OPT\}\+\\alphawith probability at least1−β1\-\\beta\.

Its sample bound isn0=O⁡\(m⁡\(α96,116\)​m​\(α3,β\)​1ε​log⁡\(24α​δ\)\)n\_\{0\}=O\\left\(m\\left\(\\frac\{\\alpha\}\{96\},\\frac\{1\}\{16\}\\right\)m\\left\(\\frac\{\\alpha\}\{3\},\\beta\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{24\}\{\\alpha\\delta\}\\right\)\\right\)\. Sincem⁡\(α96,116\)=O⁡\(d\+1α2\)m\\left\(\\frac\{\\alpha\}\{96\},\\frac\{1\}\{16\}\\right\)=O\\left\(\\frac\{d\+1\}\{\\alpha^\{2\}\}\\right\)andm⁡\(α3,β\)=O⁡\(d\+log⁡\(2/β\)α2\)m\\left\(\\frac\{\\alpha\}\{3\},\\beta\\right\)=O\\left\(\\frac\{d\+\\log\\left\(2/\\beta\\right\)\}\{\\alpha^\{2\}\}\\right\), this becomesn0=O⁡\(\(d\+1\)​\(d\+log⁡\(2/β\)\)ε​α4​log⁡\(2α​δ\)\)n\_\{0\}=O\\left\(\\frac\{\(d\+1\)\\left\(d\+\\log\\left\(2/\\beta\\right\)\\right\)\}\{\\varepsilon\\alpha^\{4\}\}\\log\\left\(\\frac\{2\}\{\\alpha\\delta\}\\right\)\\right\), which proves the claimed guarantee\. ∎

For potentially infinite classes, Bun et al\.\[[17](https://arxiv.org/html/2610.28878#bib.bib12), Theorem 4\]give a private hypothesis selection guarantee depending ond=VC⁡\(Yat⁡\(𝒬\)\)d=\\operatorname\{VC\}\(\\operatorname\{Yat\}\(\\mathcal\{Q\}\)\)and a locally small cover\. Anα\\alpha\-coverℋ⊆𝒬\\mathcal\{H\}\\subseteq\\mathcal\{Q\}contains an element within TV distanceα\\alphaof everyq∈𝒬q\\in\\mathcal\{Q\}, and is\(k,r\)\(k,r\)\-locally small ifsuph∈ℋ\|\{h′∈ℋ:TV⁡\(h,h′\)≤r\}\|≤k\\sup\_\{h\\in\\mathcal\{H\}\}\|\\\{h^\{\\prime\}\\in\\mathcal\{H\}:\\TV\(h,h^\{\\prime\}\)\\leq r\\\}\|\\leq k\. Applied to a\(k,8​α\)\(k,8\\alpha\)\-locally smallα\\alpha\-cover, their\(ε,δ\)\(\\varepsilon,\\delta\)\-private algorithm usesO⁡\(d\+log⁡\(1/β\)α2\+log⁡\(k/β\)\+log⁡\(1/δ\)α​ε\)O\\\!\\left\(\\frac\{d\+\\log\(1/\\beta\)\}\{\\alpha^\{2\}\}\+\\frac\{\\log\(k/\\beta\)\+\\log\(1/\\delta\)\}\{\\alpha\\varepsilon\}\\right\)samples and achieves the77\-agnostic guaranteeTV⁡\(q^,p\)≤7​α\\TV\(\\widehat\{q\},p\)\\leq 7\\alphawith probability at least1−β1\-\\beta, providedTV⁡\(p,h\)≤α\\TV\(p,h\)\\leq\\alphafor someh∈ℋh\\in\\mathcal\{H\}\. This guarantee requires a supplied approximation bound\. For countable classes, Corollary[C\.5](https://arxiv.org/html/2610.28878#A3.Thmtheorem5)removes both this requirement and the locally small cover assumption: finiteddalone suffices for a9999\-agnostic private learner, guaranteeingTV⁡\(q^,p\)≤99​OPT\+α\\TV\(\\widehat\{q\},p\)\\leq 99\\operatorname\{OPT\}\+\\alphawith probability at least1−β1\-\\betafor everypp\. This gives a qualitative improvement in the assumptions, at the cost of a larger sample complexity and approximation constant\.

## Appendix DOmitted proof from Section[6](https://arxiv.org/html/2610.28878#S6)

Here, we formally prove the guarantee for the boosted learner introduced in Section[6](https://arxiv.org/html/2610.28878#S6)\. Its core idea is confidence boosting: amplifying a learner’s constant success probability to1−β1\-\\betathrough independent repetition and robust aggregation\.

###### Proof of Theorem[6\.1](https://arxiv.org/html/2610.28878#S6.Thmtheorem1)\.

Setα0=α3\\alpha\_\{0\}=\\frac\{\\alpha\}\{3\},β0=18\\beta\_\{0\}=\\frac\{1\}\{8\},δ0=min⁡\{δ,β0/4\}\\delta\_\{0\}=\\min\\left\\\{\\delta,\\beta\_\{0\}/4\\right\\\}, andT=⌈128​ln⁡\(1/β\)⌉T=\\left\\lceil 128\\ln\\left\(1/\\beta\\right\)\\right\\rceil\. Fixingβ0\\beta\_\{0\}keeps the block sizeccindependent of the target failure probabilityβ\\beta\. We amplify confidence by increasing the number of independent runsTT\. By Theorem[5\.1](https://arxiv.org/html/2610.28878#S5.Thmtheorem1), each private learner is\(ε,δ0\)\(\\varepsilon,\\delta\_\{0\}\)\-DP\. Since the runs use disjoint blocks and independent randomness, parallel composition \(Lemma[2\.5](https://arxiv.org/html/2610.28878#S2.Thmtheorem5)\) gives the same privacy guarantee for the vector of estimates\. Selectingp^j\\hat\{p\}\_\{j\}uses only these estimates, so post\-processing preserves privacy \(Proposition[2\.4](https://arxiv.org/html/2610.28878#S2.Thmtheorem4)\)\. Sinceδ0≤δ\\delta\_\{0\}\\leq\\delta, the overall procedure is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\.

For utility, Theorem[5\.1](https://arxiv.org/html/2610.28878#S5.Thmtheorem1)provides a block sizec=O⁡\(m⁡\(β064​m​\(α0,β0/4\),116\)​1ε​log⁡\(4β0​δ0\)\)c=O\\left\(m\\left\(\\frac\{\\beta\_\{0\}\}\{64m\\left\(\\alpha\_\{0\},\\beta\_\{0\}/4\\right\)\},\\frac\{1\}\{16\}\\right\)\\frac\{1\}\{\\varepsilon\}\\log\\left\(\\frac\{4\}\{\\beta\_\{0\}\\delta\_\{0\}\}\\right\)\\right\)such that each estimate satisfiesTV⁡\(p^t,p\)<α0\\TV\(\\hat\{p\}\_\{t\},p\)<\\alpha\_\{0\}with probability at least1−β01\-\\beta\_\{0\}\. Fixp∈𝒬p\\in\\Qand let𝒯=\{t∈\[T\]:TV⁡\(p^t,p\)<α0\}\\mathcal\{T\}=\\left\\\{t\\in\[T\]:\\TV\(\\hat\{p\}\_\{t\},p\)<\\alpha\_\{0\}\\right\\\}\. The estimates are independent because the input is i\.i\.d\., the blocks are disjoint, and the runs use independent randomness\. Hoeffding’s inequality therefore givesPr\[\|𝒯\|≤T2\]≤exp\(−2T\(12−β0\)2\)≤β\\Pr\\left\[\|\\mathcal\{T\}\|\\leq\\frac\{T\}\{2\}\\right\]\\leq\\exp\\left\(\-2T\\left\(\\frac\{1\}\{2\}\-\\beta\_\{0\}\\right\)^\{2\}\\right\)\\leq\\beta\. On the event\|𝒯\|\>T/2\|\\mathcal\{T\}\|\>T/2, any two estimates indexed by𝒯\\mathcal\{T\}are within2​α02\\alpha\_\{0\}of one another\. Thus,Nt≥\|𝒯\|N\_\{t\}\\geq\|\\mathcal\{T\}\|for everyt∈𝒯t\\in\\mathcal\{T\}, and the maximizing indexjjsatisfiesNj≥\|𝒯\|\>T/2N\_\{j\}\\geq\|\\mathcal\{T\}\|\>T/2\. The estimates counted byNjN\_\{j\}must include somei∈𝒯i\\in\\mathcal\{T\}\. Consequently,TV⁡\(p^j,p\)≤TV⁡\(p^j,p^i\)\+TV⁡\(p^i,p\)<3​α0=α\\TV\(\\hat\{p\}\_\{j\},p\)\\leq\\TV\(\\hat\{p\}\_\{j\},\\hat\{p\}\_\{i\}\)\+\\TV\(\\hat\{p\}\_\{i\},p\)<3\\alpha\_\{0\}=\\alpha\. This proves the accuracy guarantee\. Finally,n=T​cn=Tc\. Sinceβ0=1/8\\beta\_\{0\}=1/8andδ0=min⁡\{δ,132\}\\delta\_\{0\}=\\min\\left\\\{\\delta,\\frac\{1\}\{32\}\\right\\\}, we havelog⁡\(4β0​δ0\)=O⁡\(log⁡\(4δ\)\)\\log\\left\(\\frac\{4\}\{\\beta\_\{0\}\\delta\_\{0\}\}\\right\)=O\\left\(\\log\\left\(\\frac\{4\}\{\\delta\}\\right\)\\right\)andT=O⁡\(log⁡\(4β\)\)T=O\\left\(\\log\\left\(\\frac\{4\}\{\\beta\}\\right\)\\right\)\. Substituting these choices gives the stated bound\.

Finally, ifm⁡\(α,β\)=poly⁡\(1α,log⁡\(1β\)\)m\(\\alpha,\\beta\)=\\operatorname\{poly\}\\left\(\\frac\{1\}\{\\alpha\},\\log\\left\(\\frac\{1\}\{\\beta\}\\right\)\\right\), this bound ispoly⁡\(1α,log⁡\(1β\),1ε,log⁡\(1δ\)\)\\operatorname\{poly\}\\left\(\\frac\{1\}\{\\alpha\},\\log\\left\(\\frac\{1\}\{\\beta\}\\right\),\\frac\{1\}\{\\varepsilon\},\\log\\left\(\\frac\{1\}\{\\delta\}\\right\)\\right\)\. ∎