mlsanityData to 7 Oct 2026

Fingerprinting Codes and the Price of Approximate Differential Privacy

arXiv 1311.3158 ↗First posted 13 Nov 2013cs.CRcited by 81

Not on the map. Why?

Abstract (arXiv)

We show new lower bounds on the sample complexity of (varepsilon, δ)-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ (0,1d)n has the form "What fraction of the individual records in the database satisfy the property q?" We show that in order to answer an arbitrary set Q of gg nd counting queries on D to within error ± α it is necessary that n ≥ tildeOmegaBigg(frac√d log |Q|α2 varepsilon Bigg). This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). In particular, our lower bound is the first to show that the sample complexity required for accuracy and (varepsilon, δ)-differential privacy is asymptotically larger than what is required merely for accuracy, which is O(log |Q| / α2). In addition, we show that our lower bound holds for the specific case of k-way marginal queries (where |Q| = 2k binomdk) when α is not too small compared to d (e.g. when α is any fixed constant). Our results rely on the existence of short fingerprinting codes (Boneh and Shaw, CRYPTO'95, Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Nov 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 16; 2023: 18; 2024: 14; 2025: 7; 2026: 8.

81 papers.

Sort:

By area:

  1. 2021Differentially Private Fine-tuning of Language Modelscited by 392
  2. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  3. 2023Harnessing large-language models to generate private synthetic textcited by 65
  4. 2021Iterative Methods for Private Synthetic Data: Unifying Framework and New Methodscited by 58
  5. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  6. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  7. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  8. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  9. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
  10. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  11. 2021Leveraging Public Data for Practical Private Query Releasecited by 39
  12. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
38 more
  1. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  2. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  3. 2022On the Impossible Safety of Large AI Modelscited by 27
  4. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  5. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  6. 2023Unleashing the Power of Randomization in Auditing Differentially Private MLcited by 19
  7. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
  8. 2021Privately Learning Subspacescited by 16
  9. 2021Differential Privacy Over Riemannian Manifoldscited by 16
  10. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  11. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  12. 2022Parameters or Privacy: A Provable Tradeoff Between Overparameterization and Membership Inferencecited by 14
  13. 2024Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuningcited by 14
  14. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  15. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  16. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  17. 2021Private learning implies quantum stabilitycited by 10
  18. 2021Differentially Private Coordinate Descent for Composite Empirical Risk Minimizationcited by 10
  19. 2022Privacy-Preserving Models for Legal Natural Language Processingcited by 10
  20. 2023Concentrated Differential Privacy for Banditscited by 10
  21. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  22. 2025Fed-SB: A Silver Bullet for Extreme Communication Efficiency and Performance in (Private) Federated LoRA Fine-Tuningcited by 10
  23. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  24. 2023On Differential Privacy and Adaptive Data Analysis with Bounded Spacecited by 9
  25. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  26. 2024DP-DyLoRA: Fine-Tuning Transformer-Based Models On-Device under Differentially Private Federated Learning using Dynamic Low-Rank Adaptationcited by 9
  27. 2022How to Combine Membership-Inference Attacks on Multiple Updated Modelscited by 8
  28. 2022Private Query Release via the Johnson-Lindenstrauss Transformcited by 8
  29. 2022Differentially Private Sampling from Distributionscited by 8
  30. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  31. 2021A Central Limit Theorem for Differentially Private Query Answeringcited by 7
  32. 2022Instance-Optimal Differentially Private Estimationcited by 7
  33. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  34. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 7
  35. 2024Dimension-free Private Mean Estimation for Anisotropic Distributionscited by 6
  36. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  37. 2023On the Benefits of Public Representations for Private Transfer Learning under Distribution Shiftcited by 5
  38. 2024Public-data Assisted Private Stochastic Optimization: Power and Limitationscited by 5

50 most cited of 81 All 81 (JSON)