# On the Query Complexity of Training Data Reconstruction in Private Learning

arXiv: https://arxiv.org/abs/2303.16372 · HTML: https://mlsanity.com/paper/2303.16372/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 29 Mar 2023.

## Builds on (most cited first, 19 of 19)

- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Generalised Differential Privacy for Text Document Processing](https://mlsanity.com/paper/1811.10256/) (2018)
- [Bounding Training Data Reconstruction in Private (Deep) Learning](https://mlsanity.com/paper/2201.12383/) (2022)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Defending against Reconstruction Attacks with R'enyi Differential Privacy](https://mlsanity.com/paper/2202.07623/) (2022)
- [Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms](https://mlsanity.com/paper/2204.06106/) (2022)
- [A Corrective View of Neural Networks: Representation, Memorization and Learning](https://mlsanity.com/paper/2002.00274/) (2020)
- [Gradual Release of Sensitive Data under Differential Privacy](https://mlsanity.com/paper/1504.00429/) (2015)
- [The Laplace Mechanism has optimal utility for differential privacy over continuous queries](https://mlsanity.com/paper/2105.07176/) (2021)

## Abstract (arXiv)

We analyze the number of queries that a whitebox adversary needs to make to a private learner in order to reconstruct its training data. For (ε, δ) DP learners with training data drawn from any arbitrary compact metric space, we provide the first known lower bounds on the adversary's query complexity as a function of the learner's privacy parameters. Our results are minimax optimal for every ε ≥ 0, δ ∈ [0, 1], covering both ε-DP and (0, δ) DP as corollaries. Beyond this, we obtain query complexity lower bounds for (α, ε) R'enyi DP learners that are valid for any α > 1, ε ≥ 0. Finally, we analyze data reconstruction attacks on locally compact metric spaces via the framework of Metric DP, a generalization of DP that accounts for the underlying metric structure of the data. In this setting, we provide the first known analysis of data reconstruction in unbounded, high dimensional spaces and obtain query complexity lower bounds that are nearly tight modulo logarithmic factors.