Near-optimal sample complexity achieved for private learning of discrete distributions
The claim
The authors assert they provide polynomial-time DP algorithms that match the information-theoretic optimum up to logarithmic factors
Published as: “Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy”
So what
Enables practical, efficient user-level private learning of categorical distributions with near-optimal sample requirements, filling a gap left by prior inefficient or suboptimal methods.
The five-minute version
The paper presents the first polynomial-time pure-DP algorithm for learning a discrete distribution from user-level batches that matches the information-theoretic optimum up to logarithmic factors, and also gives an approximate-DP version with similar guarantees. They achieve this via a new degree-6 sum-of-squares estimator that uses a trace-bounded diagonal majorizer certificate, and prove a statistical-query lower bound showing no polynomial-time algorithm can beat their error rate. The theoretical evidence consists of rigorous proofs of correctness, sample-complexity bounds, and matching lower bounds.
What they found 1
- Robust (non-private) estimator attains TV error O(η·p·log(1/η)/m)
“∥ˆ μ-μ∥TV ⩽O η p log(1/η)/m”
What undercuts it the paper’s own results
- The robust algorithm’s error O(η·p·log(1/η)/m) includes an extra p·log(1/η) factor compared to the information-theoretic optimum O(η/√m).
- Even without privacy or corruption, achieving error O(1/√m) requires Ω(k) users, so the user-complexity lower bound is inherent to the problem.
Stated limits 3
- Our polynomial-time robust algorithm achieves error O(η p log(1/η)/m), while the information-theoretic optimum is O(η/√m).
- For any fixed sufficiently small corruption fraction η, Theorem 1.1 guarantees error O(η p log(1/η)/m) = O(1/√m), which requires Ω(k) users even without corruptions or privacy.
- Consequently, no SQ estimator with fixed polynomial resource bounds in k, m, 1/η achieves uniformly smaller order of error.
What’s new here 4
- First polynomial-time pure (ε,0)-DP algorithm for batch-level discrete distribution learning that attains near-optimal user complexity.
- A degree-6 sum-of-squares estimator with a trace-bounded diagonal majorizer certificate for robust learning from untrusted batches.
- Application of the symmetric Grothendieck inequality to certify the majorizer, enabling efficient robustness-to-privacy reduction.
- A statistical-query lower bound ruling out uniformly better error under fixed polynomial SQ resources.
Artifacts & methods 5
- degree-6 sum-of-squares estimatorsystem
- trace-bounded diagonal majorizer certificateprimitive
- robustness-to-privacy reduction (HKMN23)evaluation
- statistical-query lower bound constructiontheory
- symmetric Grothendieck inequality (Friedland-Lim)primitive