# Minimax optimal differentially private synthetic data for smooth queries

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 64 references that are in the map.
- First posted on arXiv 2 Feb 2026.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [A Dynamical System Perspective for Lipschitz Neural Networks](https://mlsanity.com/paper/2110.12690/) (2021)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Private Multiplicative Weights Beyond Linear Queries](https://mlsanity.com/paper/1407.1571/) (2014)
- [How to DP-fy Your Data: A Practical Guide to Generating Synthetic Data With Differential Privacy](https://mlsanity.com/paper/2512.03238/) (2025)
- [Algorithmically Effective Differentially Private Synthetic Data](https://mlsanity.com/paper/2302.05552/) (2023)
- [Instance-Optimal Private Density Estimation in the Wasserstein Distance](https://mlsanity.com/paper/2406.19566/) (2024)
- [Certified private data release for sparse Lipschitz functions](https://mlsanity.com/paper/2302.09680/) (2023)
- [Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections](https://mlsanity.com/paper/2306.07884/) (2023)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Private Evolution Converges](https://mlsanity.com/paper/2506.08312/) (2025)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Private Synthetic Data Generation in Bounded Memory](https://mlsanity.com/paper/2412.09756/) (2024)
- [Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance](https://mlsanity.com/paper/2502.11778/) (2025)

## Abstract (arXiv)

Differentially private synthetic data enables the sharing and analysis of sensitive datasets while providing rigorous privacy guarantees for individual contributors. A central challenge is to achieve strong utility guarantees for meaningful downstream analysis. Many existing methods ensure uniform accuracy over broad query classes, such as all Lipschitz functions, but this level of generality often leads to suboptimal rates for statistics of practical interest. Since many common data analysis queries exhibit smoothness beyond what worst-case Lipschitz bounds capture, we ask whether exploiting this additional structure can yield improved utility. We study the problem of generating (varepsilon,δ)-differentially private synthetic data from a dataset of size n supported on the hypercube [-1,1]d, with utility guarantees uniformly for all smooth queries having bounded derivatives up to order k. We propose a polynomial-time algorithm that achieves a minimax error rate of Ok,d(n^-min 1, frackd), up to a log(n) factor. This characterization uncovers a phase transition at k=d. Our results generalize the Chebyshev moment matching framework of (Musco et al., 2025; Wang et al., 2016) and strictly improve the error rates for k-smooth queries established in citepwang2016differentially. Moreover, we establish the first minimax lower bound for the utility of (varepsilon,δ)-differentially private synthetic data with respect to k-smooth queries, extending the Wasserstein lower bound for varepsilon-differential privacy in (Boedihardjo et al., 2024).