Source-linked AI summary
Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman
TL;DR
The paper studies learning discrete distributions from batches under person-level privacy, where batch structure can also help resist adversarial corruption. It develops a degree-6 sum-of-squares certificate for robust estimation and uses it to obtain private algorithms; its analysis also compares the efficient robust rate with the information-theoretic optimum and gives a statistical-query lower bound.
Problem
The paper seeks private learning from batches while addressing adversarially corrupted batches, a setting where exploiting batch structure permits error below the corruption fraction.
Source: §1 · pp. 3–4Method
A degree-6 sum-of-squares certificate captures discarded batches, mean feasibility, and mean-dependent covariance, yielding a robust estimator and the score used for privacy.
Source: §1 · p. 4, §1.1 · p. 4Results
The polynomial-time robust algorithm has error O(η log(1/η)/√m), compared with the information-theoretic optimum O(η/√m); a statistical-query lower bound rules out uniformly smaller error under fixed polynomial resource bounds.
Source: §1.1 · p. 6Takeaways & Limitations
The certificate supports robust estimation and, through the robustness-to-privacy reduction, the paper’s private algorithms for discrete batches.
Source: §1.1 · p. 4The polynomial-time robust error O(η log(1/η)/√m) is larger than the information-theoretic optimum O(η/√m).
Source: §1.1 · p. 6
Abstract
from arXiv · showhide
We study learning a discrete distribution under person-level differential privacy in the batched setting. Given $n$ users, each contributing $m$ i.i.d. samples from an unknown distribution $\mu$ over $[k]$, we seek an estimate of $\mu$ with total-variation error $\alpha$. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure $(\varepsilon,0)$-DP, we achieve $n = \widetilde O(k/(\alpha^2 m)+k/(\alpha\sqrt{m}\varepsilon)+k/\varepsilon)$, the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate $(\varepsilon,\delta)$-DP, we achieve $n = \widetilde O(k/(\alpha^2 m)+k/(\alpha\sqrt{m}\varepsilon)+k+\log(1/\delta)/\varepsilon)$. At $\delta=2^{-\Theta(k)}$, this is $\widetilde O(k)$ for fixed $\alpha,\varepsilon,m$ and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate $O(\eta\sqrt{\log(1/\eta)/m})$ and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.
1 Introduction
The paper studies person-level private learning of discrete distributions from batches, seeking pure privacy, optimal user complexity, and polynomial-time algorithms. Its central technique is a degree-6 sum-of-squares certificate that preserves multinomial batch variance, supporting robust estimation and a reduction from batch-level robustness to user-level private estimation.
1 Introduction
- Batch structure permits error O(η/√m) under an η-fraction of adversarially corrupted batches, whereas ignoring batches cannot beat η total-variation error.Qiao and Valiant showed the batched rate is information-theoretically optimal [QV18].Source: §1 · p. 3
- The problem treats each person’s batch as one privacy unit and seeks pure batch-level DP, information-theoretically optimal user complexity, and polynomial-time computation.Earlier private batch-learning work did not meet all three goals: one pure-DP construction was not polynomial-time, while strengthening an earlier efficient approximate-DP algorithm incurred a poly(k) sample factor.Source: §1 · p. 4
1.1 Results
- A degree-6 SoS certificate represents discarded batches, mean feasibility, and repaired-batch covariance, yielding both a robust estimator and the score for privacy reduction [HKMN23].The certificate is satisfied by clean data at the required scale, constrains feasible pseudo-means near the truth, remains stable under discarding batches, and admits polynomial-time optimization.Source: §1 · p. 4, §1.1 · p. 4
- The robust certificate also tolerates clean-batch distribution shifts of at most ω in total variation, with only an additive O(ω) increase in error.The private estimators tolerate corrupted user batches and such clean-user shifts when given ω; their accuracy floor includes an additive Cω term.Source: §1.1 · pp. 5, 7
- A polynomial-time (ε, 0)-DP algorithm achieves total-variation error at most α, and the pure-DP rate matches known lower bounds up to logarithmic factors.At δ = 2^-Θ(k), the bound is Õ(k) for fixed α, ε, m, and failure probability.Source: §1.1 · pp. 5–6
- On optimality under efficient computation, the polynomial-time robust algorithm achieves error O(η log(1/η)/m), while the information-theoretic optimum is O(η/√m) [QV18].Source: §1.1 · p. 6
1.2 Techniques
- A low-trace diagonal majorizer compresses exponentially many subset-variance constraints into one semidefinite condition, and sign-vector tests recover the needed subset bounds.Clean-data feasibility follows from semidefinite duality and the stronger symmetric Grothendieck inequality of Friedland and Lim [FL20].Source: §1.2 · p. 8
- O(η√(log(1/η)/m)) total-variation error follows by converting the covariance-aware directional certificate into a bound on the estimate.The certificate retains the covariance predicted by the candidate mean, allowing the variance difference to be controlled by directional mean error rather than a universal variance bound.Source: §1.2 · p. 10
- The certificate-based score has sensitivity one because changing one batch adds one discard; combining certificates gives quasi-convexity, and a polynomial-size semidefinite formulation enables efficient computation, while low-score-set volume must be controlled.The low-score-set ℓ1 diameter is bounded directly, without an ℓ2-to-ℓ1 conversion and its extra k loss. In the large α√m regime, the clean-data certificate still requires n = eΩ(k).Source: §1.2 · p. 11
1.3 Related Work
- Batch structure creates the algorithmic challenge: when m = 1, the information-theoretic optimum is achieved by the contaminated empirical distribution.Prior work introduced batch-robust learning and studied discrete distributions and related settings.Source: §1.3 · p. 12
- This is the first polynomial-time robustness-to-privacy application converting batch-level robustness into user-level privacy for learning discrete distributions.The framework was introduced by Hopkins, Kamath, Majid, and Narayanan [HKMN23] and independently by Asi, Ullman, and Zakynthinou [AUZ23].Source: §1.3 · p. 12
2 Preliminaries
The preliminaries formalize learning from batches that may be adversarially corrupted, then develop concentration, sum-of-squares, covariance-control, and privacy-reduction tools used by the later algorithms.
2 Preliminaries
- The model treats each clean user batch as m independent draws from an unknown distribution, with up to an η-fraction of batches adversarially corrupted.The goal is to output a distribution estimate with high-probability total-variation error at most α.Source: §2 · pp. 12–13
2.2 Probability Simplex
- For any subset direction, a clean batch average has a distribution-dependent mean and variance, while total variation between probability vectors uses the usual convention.The variance is the one later used to preserve the multinomial batch-average variance in robust estimation.Source: §2.2 · pp. 13–15
2.3 Concentration Bounds
- With probability 1−β, concentration bounds control means and second moments simultaneously over binary directions and sufficiently large subsets of clean batches.The supplied concentration statement covers subsets retaining at least a 1−η fraction of indices.Source: §2.3 · p. 15
2.4 Sum-of-Squares
- The sum-of-squares framework represents approximate feasibility of polynomial constraints through a linear functional whose positivity and constraint errors are controlled up to a chosen degree.The supplied definition includes positivity on squares and approximate satisfaction of inequality, equality, and counting constraints.Source: §2.4 · p. 17
2.5 Subset-Variance Control and the Diagonal-Majorizer SDP
- Subset-direction control of a covariance-gap matrix can be converted into feasibility of a diagonal majorizer through SDP duality and a symmetric Grothendieck inequality.The result concerns symmetric matrices and uses the real symmetric form because the covariance gap need not be positive semidefinite.Source: §2.5 · pp. 18–19
2.6 Robustness to Privacy
- The pure-DP reduction outputs a point with score at most 2ηn with probability 1−β when its stated hypotheses hold.The approximate-DP reduction has the analogous score guarantee, and the refined utility bound replaces log(1/(βη)) by log(2/β) under an inner-ball assumption.Source: §2.6 · pp. 19–20
3 Robust Estimation for Discrete Batches
The section gives a polynomial-time degree-6 sum-of-squares estimator for corrupted discrete batches. Its analysis uses clean-sample covariance control and a diagonal-majorizer certificate, with an extension to heterogeneous clean batches.
3 Robust Estimation for Discrete Batches
- A polynomial-time degree-6 SoS algorithm estimates the underlying distribution from η-corrupted batches, with total-variation error at most α and success probability at least 1−β.The theorem specifies α through a formula that is incomplete in the supplied passages.Source: §3 · p. 21
- Corollary 3.3 states that, for μ∈Δ_{k−1}, η∈(0,1/4), and β∈(0,1/2), if n≥Ω((k+log(1/β))/(η²log(1/η))), then samples y*₁,…,y*ₙ are η-good with probability 1−β.Source: §3 · p. 21
3.1 Sum-of-Squares Based Robust Algorithm
- The SoS constraints use a trace-bounded diagonal majorizer to control the empirical-versus-multinomial covariance gap simultaneously in every subset direction.The majorizer is presented as a succinct dual object to the covariance discrepancy constraints used in earlier SDP-based algorithms.Source: §3 · p. 21, §3.1 · p. 23
3.2 Proof of the Main SoS Lemma
- The main SoS proof bounds repaired and clean-kept second moments, then absorbs the remaining variance difference; its weighted Cauchy–Schwarz step sets the degree-6 bottleneck.The proof uses the batch-average variance formula V(μ,s)=⟨μ,s⟩(1−⟨μ,s⟩)/m.Source: §3.2 · pp. 27, 29, 30
3.3 Covariance Closeness Guarantees
- The covariance-closeness argument relates covariance differences to mean differences within SoS, and the heterogeneous-batch extension allows each clean batch to have its own nearby distribution.For heterogeneous batches, the supplied result assumes each μ_i is within total-variation distance ω of μ and modifies the covariance allowance.Source: §3.3 · pp. 30–31, §3.4 · p. 32
4 Private Estimation for Discrete Batches
The paper applies a robustness-to-privacy reduction to its batch estimator using a score based on certifiable means. It states polynomial-time pure- and approximate-DP estimation guarantees, though the supplied theorem passages omit their sample-size expressions.
4 Private Estimation for Discrete Batches
- The privacy construction instantiates the Hopkins–Kamath–Majid–Narayanan reduction on batch averages, using a quasi-convex score implemented through low-degree pseudoexpectations.For approximate DP, it also requires a worst-case intermediate volume-ratio bound obtained from an ℓ1-diameter bound.Source: §4 · p. 33
- The paper states polynomial-time pure-DP and approximate-DP algorithms that estimate μ to total-variation error at most α with probability at least 1−β.The supplied theorem excerpts do not include the sample-size conditions.Source: §4 · p. 33
- A candidate mean’s score is the smallest trimming budget for which a low-degree certificate consistent with that candidate exists.The score is defined using certifiable means and the diagonal-majorizer system.Source: §4 · pp. 33–35
4.1 Properties of the Score
The score is well-defined, has bounded sensitivity, is quasi-convex, and can be computed efficiently to additive accuracy.
4.1.1 Well-Definedness of the Score Function
- For every candidate in the stated domain, the score minimum is attained and the score is at most n.The proof establishes existence using a feasible point-mass functional and compactness of feasible pairs.Source: §4.1.1 · p. 36
4.1.2 Bounded Sensitivity
- Changing one batch average changes the score by at most 1.The sensitivity proof adjusts the certificate by removing the changed index from its selector.Source: §4.1.2 · p. 36
4.1.3 Quasi Convexity
- For a fixed dataset, the score of a convex combination of candidate means is at most the larger score of the two candidates.The proof combines their certificates linearly.Source: §4.1.3 · p. 37
4.1.4 Efficient Computability
- The score can be computed to additive accuracy γ in time polynomial in n, k, log(1/γ), log(1/τ), and the input bit length.The computation uses semidefinite constraints and binary search over nested feasible sets.Source: §4.1.4 · pp. 37–38
4.2 Problem-Specific Consequences
This section develops problem-specific tools and consequences for private estimators, establishing how efficiently found low-score points and their geometry support pure- and approximate-DP analyses. It also covers robustness under corrupted, heterogeneous batches, conditions for recovering an earlier approximate-DP sample bound, a sample-splitting improvement and limitation, and a clean-data alternative.
4.2.1 Efficiently Finding Low Scoring Points
- A polynomial-time algorithm returns an estimate such that every point within ℓ1 distance α/2 has score at most the minimum score over the stated domain.The guarantee follows by finding a low-scoring point without the certificate’s closeness constraint.Source: §4.2.1 · p. 38
4.2.2 Volume
- With probability 1 − β, an α-ball around μ0 has score at most ηn, and all points scoring at most η*n lie within radius α + O(1/√m) of μ0.The volume lemma assumes n ≥ Ω((k + log(1/β))/(η² log(1/η))).Source: §4.2.2 · p. 39
4.2.3 Proof of the Pure-DP Theorem
- The pure-DP proof bounds the utility requirement by ~O((k + log(2/β))/(α√mε)) below the split threshold and O((k + log(2/β))/ε) above it.These bounds are for the two regimes analyzed in the pure-DP theorem proof.Source: §4.2.3 · p. 43
4.2.4 Proof of the Approximate-DP Theorem
- The approximate-DP analysis obtains error at most α by applying soundness to a point of score at most 2ηprivn and projecting to the simplex.The construction uses internal accuracy α/2.Source: §4.2.4 · p. 45
- For clean data, splitting batches further refines the approximate-DP result when 0 < ε ≤ 1, β ≤ 1/3, and δ ≤ 1/2.For small α√m, the privacy term contains only a square-root logarithm.Source: §4.2.4 · p. 46
- For α√mε > 1, sample splitting replaces the fixed k term by k/(α√mε)^(2/3), up to an additional suppressed logarithmic factor.This argument does not preserve Corollary 4.18’s guarantee because splitting reduces the batch size that controls corruption error.Source: §4.2.4 · p. 47
- For clean data, choosing between this estimator and Esfandiari et al. [EMN22] using public parameters yields the smaller sample bound without privacy composition.For constant β and m ≥ Ck^2/α^2, their ball-localization algorithm uses n = O(log(1/δ)/ε) users.Source: §4.2.4 · p. 47
- The bound recovers Theorem 4.2 when ω = O(1/√m + αε), including when α√m ≤ 1 or ε is constant.The η-dependent term is defined to be zero when η = 0.Source: §4.2.4 · p. 48
5 Statistical Query Lower Bound for Discrete Batches
This section proves an SQ lower bound for robust learning from discrete batches by reducing estimation to testing and constructing moment-matched alternatives. It rules out uniformly smaller-than-η min{1, log(1/η)/m} error with fixed polynomial SQ resources.
5.4 Binomial Moment Construction
- The construction corrects a biased binomial count distribution to match low-order moments, with a discrete-grid construction covering every batch size.The count determines how many elements of a hidden balanced alphabet subset occur in a batch.Source: §5 · p. 50, §5.4 · p. 54
5.1 Testing Problem
- The testing setup allows an observed batch law within η total variation of the clean batch law and requires identifying the clean hypothesis against every valid oracle.Algorithms may be randomized and adaptive, with worst-case query bounds.Source: §5.1 · pp. 50–51
5.2 SQ Hardness
- Moment-matched count distributions cancel low-order Fourier terms, while correlation bounds for hidden subsets yield the SQ testing hardness.The construction keeps the conditional batch distribution fixed given the count and controls the remaining Fourier mass.Source: §5.2 · pp. 51–52
5 Statistical Query Lower Bound for Discrete Batches
- No SQ estimator with fixed polynomial resource bounds achieves uniformly o(η min{1, log(1/η)/m}) error.The lower bound concerns error uniformly over the parameters.Source: §5.3 · p. 54
5.3 From Estimation to Testing
- An estimator at the prohibited error scale would distinguish the testing hypotheses, so the testing lower bound also applies to robust estimation.The reduction thresholds the estimate's distance from the clean uniform distribution.Source: §5.3 · p. 54
A Details for the Approximate-DP Section
The appendix proves a sign-direction obstruction for low-variance certificates and extends its conclusion to approximate certificates. The resulting argument bounds certificate means using medians of observed projections.
A Details for the Approximate-DP Section
- A degree-6 certificate cannot place low variance around sign directions when a substantial fraction of observations lie far above a common level.The one-dimensional obstruction assumes at least n/4 observations are at least 20.Source: A Details for the Approximate-DP Section · pp. 63–64
- Approximate certificates retain the obstruction because the fixed degree-6 derivation has polynomially bounded coefficient norm, keeping accumulated constraint error negligible.The appendix normalizes projections by a factor no larger than √m.Source: A Details for the Approximate-DP Section · p. 66
- The obstruction bounds the median of observed sign projections within 20√(1/m + τ_cov) of the certificate mean.The bound is first established for exact certificates and extended to approximate ones.Source: A Details for the Approximate-DP Section · pp. 67–68
B Pure DP Lower Bounds
The pure-DP lower bound has three terms, each arising from a distinct argument: nonprivate estimation, centered code packing, and packing within the simplex.
B Pure DP Lower Bounds
- One lower-bound term comes from classical nonprivate estimation.The appendix identifies this as the source of one of the three terms in the pure-DP lower bound.Source: B Pure DP Lower Bounds · p. 68
- A centered code packing around the uniform distribution supplies another pure-DP lower-bound term.This is distinct from the nonprivate estimation argument.Source: B Pure DP Lower Bounds · p. 68
- A third term comes from packing inside the simplex in (k−1) coordinates.The appendix lists this as the third source of the lower bound's terms.Source: B Pure DP Lower Bounds · p. 68
B.1 Projection Notation for Lower Bounds
The appendix introduces restriction and extension operators for packing arguments, then develops pure-DP lower bounds using classical estimation and two packing constructions.
B.1 Projection Notation for Lower Bounds
- Restriction keeps the first k−1 coordinates, while extension appends the final simplex coordinate for lower-bound packing arguments.The appendix states that these operations preserve the relevant ℓ1-distance comparisons.Source: §B.1 · p. 68
- The appendix focuses on how the pure-DP lower bound depends on failure probability β; similar lower bounds already appear in [LSY+20].Source: §B.1 · p. 69
- Any ε-DP learner must estimate every distribution in the simplex within ℓ1 error α with probability at least 1−β, under the theorem’s stated parameter assumptions.Source: §B.1 · p. 69
- Ω((k + log(1/β))/α^2) individual samples are required nonprivately, yielding a batched lower-bound term after dividing by m.The proof attributes this term to classical distribution estimation.Source: §B.1 · p. 69
- Simplex packing gives at least (1/(6α))^(k−1) separated distributions, to which the packing lower-bound theorem applies.The construction reflects a large ℓ1-ball packing into the simplex while preserving separation.Source: §B.1 · p. 70
- A centered binary-code packing produces exponentially many distributions with disjoint α-radius balls and applies the packing theorem with γ=min{1, O(α√m)}.The code has pairwise Hamming distance greater than ⌊k/2⌋/4.Source: §B.1 · pp. 70–71