# A Sharp Transition in Data Reconstruction under Differential Privacy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 53 references that are in the map.
- First posted on arXiv 29 Sep 2026.

## Builds on (most cited first, 30 of 41)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [Reconstructing Training Data from Trained Neural Networks](https://mlsanity.com/paper/2206.07758/) (2022)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Bounding Training Data Reconstruction in Private (Deep) Learning](https://mlsanity.com/paper/2201.12383/) (2022)
- [Bounding Training Data Reconstruction in DP-SGD](https://mlsanity.com/paper/2302.07225/) (2023)
- [Evaluations of Machine Learning Privacy Defenses are Misleading](https://mlsanity.com/paper/2404.17399/) (2024)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Defending against Reconstruction Attacks with R'enyi Differential Privacy](https://mlsanity.com/paper/2202.07623/) (2022)
- [Extracting memorized pieces of (copyrighted) books from open-weight language models](https://mlsanity.com/paper/2505.12546/) (2025)
- [Deconstructing Data Reconstruction: Multiclass, Weight Decay and General Losses](https://mlsanity.com/paper/2307.01827/) (2023)
- [Scaling Laws for Differentially Private Language Models](https://mlsanity.com/paper/2501.18914/) (2025)
- [Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms](https://mlsanity.com/paper/2204.06106/) (2022)
- [Practical Differentially Private Hyperparameter Tuning with Subsampling](https://mlsanity.com/paper/2301.11989/) (2023)
- [Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano](https://mlsanity.com/paper/2210.13662/) (2022)
- [Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy](https://mlsanity.com/paper/2307.03928/) (2023)

## Abstract (arXiv)

Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single d-dimensional training sample from a ρ-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at ρ asymp d for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for ρ ll d; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for ρ gg d. Remarkably, the transition moves to ρ asymp s for data lying in an s-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet).