mlsanityData to 7 Oct 2026

On Differential Privacy and Adaptive Data Analysis with Bounded Space

arXiv 2302.05707 ↗First posted 11 Feb 2023cs.CR cs.DS cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically, (1) Under standard cryptographic assumptions, we show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy, compared to the space needed without privacy. To the best of our knowledge, this is the first separation between the space complexity of private and non-private algorithms. (2) The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries. We revisit previous lower bounds at a foundational level, and show that they are a consequence of a space bottleneck rather than a sampling bottleneck. To obtain our results, we define and construct an encryption scheme with multiple keys that is built to withstand a limited amount of key leakage in a very particular way.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 34 of its 98 references that are in the map. First posted on arXiv 11 Feb 2023.

Builds on

34 of 98 references.

References · 34

  1. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
  2. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  3. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 102
  4. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  5. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  6. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 76
  7. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  8. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  9. 2019A New Analysis of Differential Privacy's Generalization Guaranteescited by 36
  10. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  11. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  12. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
22 more
  1. 2021Fast and Memory Efficient Differentially Private-SGD via JL Projectionscited by 29
  2. 2017Practical Locally Private Heavy Hitterscited by 28
  3. 2017Calibrating Noise to Variance in Adaptive Data Analysiscited by 28
  4. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  5. 2016Max-Information, Differential Privacy, and Post-Selection Hypothesis Testingcited by 25
  6. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  7. 2017Heavy Hitters and the Structure of Local Privacycited by 20
  8. 2018Detecting Correlations with Little Memory and Communicationcited by 19
  9. 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 18
  10. 2018The Limits of Post-Selection Generalizationcited by 16
  11. 2016Adaptive Learning with Robust Generalization Guaranteescited by 15
  12. 2022Differentially Private Linear Sketches: Efficient Implementations and Applicationscited by 10
  13. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  14. 2019Communication and Memory Efficient Testing of Discrete Distributionscited by 8
  15. 2022Bounded Space Differentially Private Quantilescited by 8
  16. 2021Generalization in the Face of Adaptivity: A Bayesian Perspectivecited by 7
  17. 2017Sampling Without Compromising Accuracy in Adaptive Data Analysiscited by 6
  18. 2022Improved Utility Analysis of Private CountSketchcited by 6
  19. 2020Efficient Differentially Private F0 Linear Sketchingcited by 2
  20. 2021Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Spacecited by 2
  21. 2016Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPscited by 1
  22. 2021A Note on Sanitizing Streams with Differential Privacycited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 3; 2025: 1; 2026: 2.

9 papers.

  1. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  2. 2023Adaptive Data Analysis in a Balanced Adversarial Modelcited by 5
  3. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  4. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  5. 2023Differentially Private Clustering in Data Streamscited by 1
  6. 2024Adaptive Data Analysis for Growing Datacited by 1
  7. 2025Bayesian Perspective on Memorization and Reconstructioncited by 0
  8. 2026Efficient Adaptive Data Analysis over Dense Distributionscited by 0
  9. 2026Is Randomness Necessary for Adaptive Data Analysis?cited by 0