Actually, All Learnable Distribution Classes Are Privately Learnable

1 Introduction

• Distribution learning asks whether samples from an unknown class member can yield a total-variation-close estimate, and Ashtiani conjectured that learnability implies private learnability.The paper gives a positive resolution using the standard definition, which requires learning to arbitrarily small error.Source: §1 · pp. 1–2

1.1 Results

• The main result privately learns any learnable distribution class, relying on non-private learning to higher accuracy than the target.The paper distinguishes this standard, arbitrarily-small-error guarantee from a fixed-error counterexample [BKMS24].Source: §1 · p. 2
• For polynomial non-private sample complexity, the stated bound yields polynomial private sample complexity; boosting gives logarithmic dependence on 1/β.The direct approach of feeding a privatized sample set to the learner would have a poor dependence on β.Source: §1.1 · p. 2, §1.2 · p. 4
• The paper also gives private synthetic-data samplers for learnable classes and a reduction from agnostic learnability to private agnostic learnability.The sampler outputs synthetic data from a distribution close to the unknown distribution; agnostic learnability is not equivalent to realizable learnability [BBKL23].Source: §1.1 · pp. 2–3

1.2 Techniques

• The technique partitions data, runs a non-private learner on each part, and privately aggregates outputs using synthetic samples drawn through a TV coupling.The coupling preserves the synthetic datasets’ marginals while making them agree with high probability when the learner outputs are TV-close.Source: §1.2 · pp. 3–4
• A generalized Poisson coupling removes the common σ-finite dominating-measure requirement while retaining marginal and pairwise agreement guarantees.This extension covers arbitrary learnable classes, including point masses that have no common σ-finite dominating measure.Source: §1.2 · p. 4

1.3 AI Disclosure

• The initial countable-domain resolution was obtained with AI assistance, while the authors developed measure-theoretic arguments for general domains and verified the claims.The authors state that all writing was theirs and that they take responsibility for the claims.Source: §1.3 · p. 4

2 Preliminaries

• The domain is a standard Borel space, and total variation is the supremum of probability differences over measurable sets.The law of a random variable is denoted by L(Z).Source: §2 · p. 5
• A Markov kernel maps each input to an output probability measure with measurable event probabilities, formalizing randomized mappings used in coupling procedures.The paper uses kernels to treat couplings as randomized maps from tuples of distributions to joint synthetic datasets.Source: §2 · p. 5
• A Poisson point process is a random counting measure whose counts on disjoint measurable sets are independent.The paper’s explicit coupling constructions build on the Poisson coupling of Angel and Spinka.Source: §2 · p. 5
• Differential privacy compares output probabilities on neighboring datasets, and data-independent post-processing preserves the same privacy parameters.Parallel composition also preserves (ε, δ)-DP when independent mechanisms run on a fixed partition of the data.Source: §2 · p. 5

3 Couplings

• A grand coupling scheme jointly samples from each distribution while preserving its marginals, bounding pairwise disagreement by twice the total variation distance, and requiring measurable finite-dimensional kernels.These properties let the coupling handle random learner outputs and support later privacy and utility analyses.Source: §3 · p. 6
• The Poisson-based construction works when the class has a common σ-finite dominating measure, using shared randomness to produce samples with the correct marginals and a TV-based disagreement bound.For bounded densities on [0, 1], the illustration uses shared uniform proposals and accepts the first point beneath each distribution’s density.Source: §3 · p. 6
• A common σ-finite dominating measure need not exist for an arbitrary learnable class, such as all point masses on R.That limitation prevents the first construction from covering every class considered by the paper.Source: §3 · p. 7
• For any finite tuple, a tuple-dependent finite dominating measure yields measurable, projectively consistent Poisson couplings that extend to a universal grand coupling on standard Borel spaces.Kolmogorov’s Extension Theorem supplies the universal joint measure, whose restriction gives a valid scheme on any distribution class without a common dominating measure.Source: §3 · p. 7

4 Private Synthetic Data Sampler

• The pipeline partitions records into disjoint blocks, runs the non-private learner on each block, then applies Aggregate to correlated synthetic datasets from the candidate distributions.The end-to-end sampler inherits Aggregate’s guarantees while lifting privacy from tuple-level to dataset-level adjacency.Source: §4 · pp. 8–9

4.1 Tuple-Level Primitive: Aggregate

• β/2: Aggregate is (ε, δ)-DP and its output law is within β/2 TV of p^ℓ when at least 7/8 of its inputs are O(β/ℓ)-close to p.This guarantee applies to a fixed tuple of candidate distributions.Source: §4.1 · p. 9
• An analysis-only ghost draw from p^ℓ lets the utility proof relate accurate candidate distributions to exact agreement with the target draw.The disagreement bound is at most 2ℓ TV(q_i, p), and the resulting consensus lets StabilityBasedMode output the ghost draw with high probability.Source: §4 · p. 8, §4.1 · p. 10
• Arbitrarily small TV error lets a large majority of candidate draws agree exactly with the target draw, replacing [KKMV23]’s stable-histogram and private-selection stages with one stability-based mode.Construction A.4 also establishes measurability and consistency for tuple-dependent Poisson couplings, enabling the analysis on arbitrary standard Borel spaces without a common dominating measure.Source: §4.1 · p. 10

4.2 End-to-End Private Correlated Sampler: Sampler

• 3β/4: Sampler is dataset-level (ε, δ)-DP and outputs Z with TV(L(Z), p^ℓ) ≤ 3β/4 when each block learner reaches O(β/ℓ) TV error with probability at least 15/16.The stated condition applies to blocks of size b, with the dataset size n set by the theorem’s sample-complexity bound.Source: §4.2 · p. 11
• Changing one record affects at most one block, so the tuple-level privacy guarantee of Aggregate lifts to dataset-level privacy for Sampler.The proof uses the same partition and learner randomness in neighboring executions.Source: §4 · p. 9, §4.1 · p. 10, §4.2 · p. 11

5 Main algorithm and reduction

• A private synthetic dataset is passed to the non-private learner with independent randomness, yielding the black-box reduction.Privacy follows by post-processing; utility is established by coupling the synthetic output to an i.i.d. sample and bounding the mismatch together with learner failure.Source: §5 · p. 12
• The utility proof transfers the learner’s failure bound from an i.i.d. sample to the synthetic-data procedure using a coupling mismatch bound and a union bound.The proof states that the resulting failure probability is at most β.Source: §5 · p. 12
• BlackBoxPrivateLearner is (ε, δ)-DP and, for every p ∈ Q, outputs an estimate with TV error < α with probability at least 1 − β.The theorem states that a sample size exists for this guarantee; the supplied passage does not include its expression.Source: §5 · p. 12
• Privacy is preserved because Sampler is (ε, δ0)-DP and applying the learner to its output is post-processing, with δ0 ≤ δ.The learner uses an independent random seed.Source: §5 · p. 12

6 A Boosted Private Learner

• Independent repetitions and robust aggregation amplify constant success probability to 1 − β while requiring block accuracy independent of the final failure probability β.The method uses T = O(log(1/β)) disjoint blocks and selects the estimate with the largest number of estimates within TV distance 2α0, where α0 = α/3.Source: §6 · p. 13
• If more than half the estimates are α0-close to p, the selected estimate has TV error at most α; independence makes the probability of lacking such a majority decrease exponentially in T.Each run fails with probability at most β0.Source: §6 · p. 13
• BoostedLearner is (ε, δ)-DP and achieves TV error < α with probability at least 1 − β for every p ∈ Q.The theorem states that a sample size exists for this guarantee; the supplied passage does not include its expression.Source: §6 · pp. 13–14
• A non-trivial DP guarantee requires δ = o(1/n); the stated sample-complexity dependence on δ is only logarithmic.The passage contrasts this with n(δ) = C/δ, which would give δ = Θ(1/n), the trivial regime.Source: §6 · p. 14

A Poisson Coupling Details

• The appendix gives two constructions of the grand coupling interface, both based on Poisson coupling.The first handles families with a common σ-finite dominating measure; the second does not require one.Source: A Poisson Coupling Details · p. 18
• For a family with a common σ-finite dominating measure, Corollary A.3 establishes a grand coupling scheme.The construction applies to families P whose distributions are all dominated by that measure.Source: A Poisson Coupling Details · p. 18
• Without a common dominating measure, Corollary A.7 establishes a universal grand coupling scheme on distributions over any standard Borel space.Restricting this scheme to any family gives a grand coupling scheme on that family.Source: A Poisson Coupling Details · p. 18

A.1 A Globally Dominated Poisson Coupling

• The construction assumes a σ-finite measure ν that dominates every distribution in the family.The family’s densities with respect to ν determine which Poisson points are accepted.Source: §A.1 · p. 18
• A shared Poisson point process defines each sample by filtering points according to the distribution’s density and selecting the accepted point with the smallest t-coordinate.The output is the selected point’s y-coordinate, and the same process is used for every distribution.Source: §A.1 · pp. 18–19
• Theorem A.2 gives the coupling’s marginal and agreement guarantees: ZP ∼ P and Pr[ZP ≠ ZQ] ≤ 2 TV(P, Q).The displayed bound in the passage is 2 TV(P, Q)/(1 + TV(P, Q)) ≤ 2 TV(P, Q).Source: §A.1 · p. 18
• The construction is a grand coupling scheme once its measurability requirement is verified.The proof establishes that the map from a tuple of distributions to the joint law is a Markov kernel.Source: §A.1 · p. 19

• On standard Borel spaces, a family has a common σ-finite dominating measure exactly when it is TV separable, so the obstruction is nonseparability rather than uncountability.Every finite tuple nevertheless has a canonical finite dominating measure: the sum of its distributions.Source: §A.2 · p. 19
• For each finite tuple, Construction A.4 uses its summed measure to define a Poisson process and selects each coordinate’s first accepted point.The acceptance rule uses the tuple-specific Radon–Nikodym densities.Source: §A.2 · pp. 19–20
• Measurability permits sampling the coupling for random data-dependent distributions, while projective consistency lets different tuples share a larger coupling.The latter supports jointly coupling neighboring executions and adjoining a ground-truth law for utility analysis.Source: §A.2 · pp. 20, 22
• The resulting kernels are measurable, have the specified marginals, and disagree between coordinates i and j with probability at most 2 TV(Pi, Pj).Projective consistency makes each subtuple marginal equal to the coupling constructed directly for that subtuple.Source: §A.2 · p. 20
• Kolmogorov’s Extension Theorem stitches the finite kernels into a universal grand coupling over all distributions, preserving each marginal and the pairwise disagreement bound.For every P and Q, ZP has law P and Pr[ZP ≠ ZQ] ≤ 2 TV(P, Q).Source: §A.2 · pp. 22–23

• The section applies grand coupling schemes to construct a differentially private synthetic data sampler.Source: B Private synthetic data sampler · p. 23
• It formally proves privacy and utility guarantees for Aggregate and Sampler.Source: B Private synthetic data sampler · p. 23
• The data universe is Y = X^ℓ, and the considered distributions are q^ℓ for q in F, where F contains the target class and all base-learner outputs.Source: B Private synthetic data sampler · p. 24

• A shared grand coupling makes neighboring input tuples yield pointwise neighboring sample vectors, transferring StabilityBasedMode’s (ε, δ)-DP guarantee to Aggregate.Source: §B.1 · p. 24
• When 7/8 of the inputs are η-close to p, most coupled samples match the ghost draw from p^ℓ, creating the frequency gap needed by StabilityBasedMode.The tuple-level utility proposition bounds the output’s TV distance by 2ℓη when the specified frequency-gap condition holds.Source: §B.1 · p. 25
• With at least 7k/8 inputs η-close to p, Aggregate is (ε, δ0)-DP and its output is within β/2 TV distance of p^ℓ.Source: §B.1 · p. 26

• For privacy, the same permutation and learner seeds are used in neighboring executions, so the changed record affects only one block’s learner output.Source: §B.2 · pp. 26–27
• Sampler partitions its input into k blocks and runs the base learner on each block with an independent seed before applying Aggregate.Source: §B.2 · p. 27
• Under the stated setting, Sampler is (ε, δ0)-DP and an (ℓ, 3β/4)-approximate sampler for Q.The sample size is n = kb, with b satisfying the base learner’s accuracy condition and k meeting the stated parameter bound.Source: §B.2 · pp. 27–28

Agnostic private distribution learning

• C-agnostic learnability bounds output error by C OPT(p) + α with probability at least 1 − β, where OPT(p) is the distance to the closest class member.The guarantee is over the sample and learner randomness.Source: C Agnostic private distribution learning · p. 28
• For standard Borel X and C ≥ 1, C-agnostic learnability of Q implies (8C^2 + 9C)-agnostic learnability under (ε, δ)-differential privacy for every ε, δ ∈ (0, 1); the reduction preserves properness.The guarantee holds for every α, β ∈ (0, 1).Source: C Agnostic private distribution learning · p. 28
• The reduction obtains privacy through disjoint batches and parallel composition, with the final estimate protected by post-processing.For insufficient data it returns a fixed class element; when the assumed learner is proper, the reduction's outputs remain in the class.Source: C Agnostic private distribution learning · p. 28
• Countable classes with finite VC(Yat(Q)) admit an (ε, δ)-private learner with TV(bq, p) ≤ 99 OPT + α, without a supplied approximation bound or locally small cover.Compared with the prior cover-based guarantee, this removes those assumptions at the cost of larger sample complexity and approximation constant.Source: C Agnostic private distribution learning · p. 31

Confidence boosting

• Independent repetition raises each estimate’s constant success probability to an overall success probability of at least 1 − β through robust aggregation.The selection chooses an estimate with the largest neighborhood of estimates within the prescribed distance.Source: D Omitted proof from Section 6 · p. 31
• The repeated procedure remains (ε, δ)-differentially private because its runs use disjoint blocks and selection is post-processing.Each run is (ε, δ0)-DP with δ0 ≤ δ.Source: D Omitted proof from Section 6 · p. 31
• On the event that more than half the estimates are accurate, robust selection returns an estimate within α of p; the proof sets T = ⌈128 ln(1/β)⌉.The estimates use disjoint blocks and independent randomness, and the sample count is n = Tc.Source: D Omitted proof from Section 6 · p. 31