Pith. sign in

REVIEW 3 major objections 4 minor 67 references

Differentially private synthetic data achieves the minimax-optimal error rate for k-smooth queries: (nε)^{-min{1,k/d}}.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 05:39 UTC pith:47N5UL2S

load-bearing objection The claimed minimax rate for k-smooth DP synthetic data is plausible and worth engaging, but the proof of the key coefficient-decay theorem uses a false inequality and the Gaussian noise is under-calibrated by a factor of 2; both are repairable and do not change the rate exponents. the 3 major comments →

arxiv 2602.01607 v3 pith:47N5UL2S submitted 2026-02-02 math.ST cs.ITcs.LGmath.ITstat.MLstat.TH

Minimax optimal differentially private synthetic data for smooth queries

Rundong Ding , Yiyun He , Yizhe Zhu This is my paper
classification math.ST cs.ITcs.LGmath.ITstat.MLstat.TH MSC 62C2068P27
keywords differential privacysynthetic datasmooth queriesChebyshev moment matchingminimax lower boundphase transitionWasserstein distance
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper claims that the minimax error for generating (ε,δ)-differentially private synthetic data on the hypercube, measured uniformly over all k-smooth queries, is (nε)^{-min{1,k/d}} up to log factors, and that this rate is achieved in polynomial time. That settles a gap left by earlier work, which only achieved n^{-2k/(3d+2k)} for smooth queries, and recovers the known Wasserstein rate n^{-1/d} at k=1. The result shows a phase transition at k=d: smoothness beyond the dimension gives no further improvement, so statistics like low-order moments and quadratic forms can be released at a dimension-independent n^{-1} rate. A reader should care because real summaries—moments, correlations, smooth losses—are not worst-case Lipschitz, so this theoretical rate is the relevant benchmark for practical synthetic-data pipelines.

Core claim

On its own terms, the paper establishes that k-smooth queries admit a minimax-optimal private synthetic data mechanism. Theorem 1 constructs a polynomial-time (ε,δ)-DP algorithm that, for any dataset X of size n in [-1,1]^d, outputs a synthetic dataset Y with expected error E d_k(p_X, p_Y) ≤ C_k d (√(log(1.25/δ)/(εn)))^{k/d} when k<d, with an extra log(εn) factor when k=d, and C_k √(log(1.25/δ)/(εn)) when k>d. Theorem 2 supplies the matching lower bound: every (ε,δ)-DP mechanism has worst-case expected error at least C_k (nε)^{-min{1,k/d}}. The two bounds agree up to a d-factor and logarithmic terms, so the minimax rate is Θ_{k,d}((nε)^{-min{1,k/d}}) with a phase transition at k=d. The algor

What carries the argument

The proof is carried by a coefficient-decay theorem for multivariate Chebyshev expansions: ∑_K ||K||_2^{2k} c_K² ≤ C_k (max_{|β|≤k}||∂^β f||_∞)², with C_k ≤ e^k k!. This turns smoothness into a weighted ℓ_2 bound on Chebyshev moment gaps; a companion multivariate Jackson estimate (Lemma 3) bounds truncation error by d C_k/m^k. Theorem 4 then controls the integral probability metric d_k by truncation plus √C_k times the weighted moment gap. The algorithm adds Gaussian noise to O(m^d) scaled Chebyshev moments of rounded data and matches them to a grid distribution, then rounds to an explicit synthetic multiset. The lower bound uses a DP-Assouad reduction with localized smooth bumps on m^d cell

Load-bearing premise

The upper-bound rate rests on the claim that Chebyshev coefficients of k-smooth functions decay as ∑_K ||K||_2^{2k} c_K² ≤ e^k k! · (max derivative)²; the proof of that claim as written relies on a termwise inequality that is false in d>1 (e.g., d=2, k=2, K=(1,1) gives 4≤1), so the advertised constants are not established by the text, though a weaker correctly-proved version would still give the same rate exponent.

What would settle it

Check Theorem 3 numerically in d=2 for f(x)=sin(πx_1)sin(πx_2): compute the ratio R = ∑_K ||K||_2^{4} c_K² / max_{|β|≤2}||∂^β f||_∞²; if R exceeds e²·2! for any such f, the stated constant fails. Independently, the proof's displayed inequality fails termwise at K=(1,1), so the derivation must be repaired; the rate claim would be settled by verifying whether a constant independent of d suffices after the multinomial repair.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If the rate is right, then for fixed k the sample size needed to reach error α at privacy (ε,δ) is n ≍ (αε)^{-1/max{1,d/k}} up to log factors—the first sharp sample-complexity benchmark for private smooth-query synthetic data.
  • When k>d, the error is Θ(1/(nε)) independent of dimension: low-order moments, correlations, and quadratic forms can be released with dimension-free accuracy.
  • At k=d there is a log(εn) penalty; the phase transition marks where extra smoothness stops helping, so algorithm design can stop increasing the moment order beyond d.
  • The k=1 case reproduces the known Wasserstein n^{-1/d} rate for (ε,δ)-DP, so the smooth-query framework is a genuine generalization of the Wasserstein benchmark.
  • The lower bound holds for constant ε>1 and δ up to O(ε), indicating the rate is not confined to a narrow high-privacy regime.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A direct test of the phase transition: fix εn and k>d, and run the algorithm at d=10 and d=1000; the theorem predicts nearly identical d_k error, showing the dimension-free regime in practice.
  • The coefficient-decay technique is not tied to DP: it gives a general finite-moment condition for approximating distributions under d_k, so it could sharpen non-private empirical-measure concentration or other IPM-based algorithms when the test class is smooth.
  • The pure ε-DP analogue is left open; if the Gaussian mechanism's ℓ_2 sensitivity analysis could be reworked for the Laplace mechanism, the known pattern from earlier smooth-query work suggests a rate n^{-k/(d+k)}—a conjecture the paper does not address.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies differentially private synthetic data generation for datasets supported on [-1,1]^d, with utility measured by the integral probability metric d_k induced by functions whose derivatives up to order k are bounded. It proposes a polynomial-time algorithm (Algorithm 1) based on grid rounding, Gaussian perturbation of normalized Chebyshev moments, weighted least-squares moment matching, and largest-remainder quantization to an explicit synthetic dataset. The main upper bound (Theorem 1) claims E d_k(p_X, p_Y) ≤ C_k d (sqrt(log(1.25/δ))/(εn))^{k/d} for k<d, with log(εn)/(εn) at k=d and 1/(εn) for k>d, where C_k ≤ (Ck)^k. The main lower bound (Theorem 2) claims that every (ε,δ)-DP mechanism has minimax error ≥ C_k (nε)^{-min{1,k/d}}, yielding a phase transition at k=d. If the claims hold, this strictly improves the smooth-query rates of Wang et al. (2016) and generalizes the Chebyshev moment-matching framework of Musco et al. (2025) and the Wasserstein lower bound of Boedihardjo et al. (2024).

Significance. The paper's central contribution is a clean characterization of the minimax rate for smooth queries in DP synthetic data, with a phase transition at k=d and a first minimax lower bound for (ε,δ)-DP in this setting. The proposed algorithm outputs an explicit synthetic dataset rather than a measure, which is practically relevant. The technical engine is a coefficient-decay theorem for multivariate Chebyshev expansions (Theorem 3) plus a multivariate Jackson inequality (Lemma 3), and the lower bound uses a DP-Assouad reduction with disjoint smooth bumps. The rate decomposition is transparent, the comparisons to [60], [48], and [11] are appropriate, and the claimed exponents are falsifiable. However, the proof as written contains a gap in Theorem 3 and a privacy-calibration error in Algorithm 1; these are load-bearing for the stated theorems, though they appear repairable without changing the minimax-rate exponents.

major comments (3)
  1. [Appendix C, Eq. (12), Theorem 3] The proof of Theorem 3 asserts the first inequality in (12): sum_K ||K||_2^{2k} c_K^2 ≤ sum_K K^{2α} c_K^2 for a fixed multi-index α with |α|=k. This is false for d>1: for d=2, k=2, α=(1,1), and K=(1,1), the left side has contribution ||K||_2^4 = 4, while K^{2α}=1. The subsequent multinomial expansion (sum a_i)^k ≤ k! sum_{|α|=k} a^α correctly gives sum_K ||K||^{2k} c_K^2 ≤ k! sum_{|α|=k} sum_K K^{2α} c_K^2, not control by a single α. Combining this with Proposition 1 and summing over the binom(d+k-1,k) choices of α introduces a further d- and k-dependent factor, so the advertised constant C_k ≤ e^k k! independent of d is not established. Since Theorem 3 is the engine of Theorem 4 and hence of Theorem 1, the constant-level statement C_k d in Theorem 1 is unsupported as written. The minimax-rate exponents likely survive with a d-dependent constant (which is compatible with the abstract's
  2. [Section 4.1 and Algorithm 1, Step 3] The privacy calibration of Algorithm 1 is off by a factor of 2. In Section 4.1 the sensitivity bound is Δ_{2,f}^2 ≤ (4·2^d/(π^d n^2)) S. For ε,δ∈(0,1), the Gaussian mechanism stated in Lemma 1 requires σ^2 ≥ Δ^2 · 2 log(1.25/δ)/ε^2 = 8·2^d/(π^d) · S log(1.25/δ)/(n^2 ε^2). Algorithm 1 instead sets σ^2 ≥ 4·2^d/(π^d) · S log(1.25/δ)/(n^2 ε^2), i.e. half the required variance. Thus the mechanism as printed is not (ε,δ)-DP. Doubling σ^2 restores privacy and does not affect the rate analysis, but the theorem statement and the algorithm must be corrected consistently.
  3. [Appendix A.4, Steps 1 and 3] The lower bound chooses β = 2c_1/(nε), so βn = 2c_1/ε. This is a valid fraction only if εn ≥ 2c_1, and the admissibility condition βn ≤ n/m^d with m≥2 forces m^d ≲ nε. The theorem allows ε ∈ (1/n, c_1) for arbitrary c_1, so when nε is smaller than a constant the constructed grid m cannot exist and the Hamming-distance bound d_Ham = ⌊βn⌋ may exceed n. The lower bound is trivially constant in that regime (d_k ≤ 2d), but the proof should split off a separate trivial case or state the lower bound under an nε ≥ C assumption. Without this, the full parameter range claimed in Theorem 2 is not proven as written.
minor comments (4)
  1. [Lemma 1] The lemma defines Δ_{2,2,f} as the squared ℓ2 sensitivity but the formulas use Δ_{2,f}; this is dimensionally inconsistent and is likely the source of the privacy-calibration slip. Please use one symbol for the ℓ2 norm and align all formulas.
  2. [Abstract and Theorem 1] The abstract states an error rate n^{-min{1,k/d}} 'up to a log factor', while Theorem 1 carries an extra d factor and a log(εn) factor at k=d. For precision, the abstract should state the d-dependence (e.g., O_{k,d}(...)) consistently.
  3. [Appendix G] The computational complexity statement says 'mkd variables and m d−1 moment-matching constraints'; this should be m^{kd} grid variables (since r=m^k per dimension) and roughly m^d moment constraints (or (m+1)^d-1 if indexing from {0,...,m}^d). Please correct the notation.
  4. [Lemma 12] The coefficient inequality is stated as '|\tilde c_i| ≤ |c_i|, ∀0≤i≤k' but the trigonometric polynomial has degree m; the correct range is 0≤i≤m.

Circularity Check

0 steps flagged

No circularity; the derivation chain is self-contained and externally benchmarked, with only a non-circular proof gap in Theorem 3.

full rationale

The paper's central claims do not reduce to their inputs by construction. The upper bound (Theorem 1) is derived from Chebyshev moment matching: Theorem 3 gives coefficient decay, Lemma 3 gives a multivariate Jackson estimate, Lemma 1 is the standard Gaussian mechanism, and Lemma 13 bounds the moment-normalization sum S. None of these ingredients is defined in terms of the target d_k rate, and no parameter is fitted to data: the grid resolution m is chosen analytically from n, epsilon, k, and d, and the constants are universal. The lower bound (Theorem 2) is a separate DP-Assouad reduction (Lemma 7 and Construction 1) that does not presuppose the upper bound. The only author self-citations ([36]-[38]) appear in the introduction and related-work recaps and are not load-bearing for any proof step; the paper's benchmarks are external ([48], [60], [11], [3], [40]). There is a genuine mathematical gap in Appendix C: the displayed inequality in Eq. (12) asserts a comparison to a single K^{2alpha}, whereas the multinomial argument the text gives ("(sum_i a_i)^k = sum_{|alpha|=k} k!/alpha! a^alpha <= k! sum_{|alpha|=k} a^alpha") yields a sum over all |alpha|=k. This is an erroneous proof step, not a circular reduction: it does not define a quantity in terms of a claimed output, nor does it rename a fit as a prediction. The rate exponents may survive with a larger d-dependent constant, but that is a correctness risk, not circularity. Therefore the paper exhibits no significant circularity.

Axiom & Free-Parameter Ledger

5 free parameters · 7 axioms · 0 invented entities

The paper introduces no fitted constants and no invented entities: the algorithm's design parameters (m, Δ, m′, σ²) and the lower bound's construction parameter β are all set explicitly in the text and optimized in the rate analysis. The load-bearing mathematical inputs are standard tools (Gaussian calibration, Parseval identities, Bernstein's inequality, Jackson kernels, Kantorovich-Rubinstein duality, Assouad's method), each either proved inside the paper or cited to external sources. The only paper-specific analytic premises are Theorem 3 (weighted Chebyshev coefficient decay) and Lemma 3 (multivariate Jackson bound), both proved in the appendices; Theorem 3's written proof contains the defective inequality (12).

free parameters (5)
  • m - moment-matching level (Chebyshev degree / grid resolution) = m ≈ (εn/√log(1.25/δ))^{1/max{d,k}}
    Tuning variable chosen to balance the Jackson approximation error d·m^{-k} against the Gaussian moment-noise term; optimized in the rate analysis, not fitted to any data.
  • β - fraction of moved points in lower-bound construction = β = 2c₁/(nε)
    Sets the Hamming distance ⌊βn⌋ between hard-instance pairs so that tanh(ε⌊βn⌋/2) ≤ tanh(c₁) < 1; constrained by βn ≤ n/m^d for feasibility.
  • Δ - grid width in Algorithm 1 = Δ = 2m^{-k}
    Sets the rounding error d·Δ/2 = d·m^{-k}, which is matched to the target rate in each of the three regimes.
  • m′ - synthetic output size = m′ = ⌈m^{kd}(εn)^{min{1,k/d}}⌉
    Controls the largest-remainder quantization error d·r^d/m′ = d(εn)^{-min{1,k/d}}.
  • σ² - Gaussian noise variance = (4·2^d/π^d)·S·log(1.25/δ)/(n²ε²)
    Derived from the ℓ₂-sensitivity of the scaled Chebyshev moments; as printed it is a factor 2 below the value required by Lemma 1, affecting only constants.
axioms (7)
  • standard math Gaussian mechanism calibration (Lemma 1)
    Standard (ε,δ)-DP result used for privacy of the moment perturbation (Section 4.1); cited to [26, 7, 58].
  • standard math Parseval identity with derivatives in cosine coordinates (Lemma 8)
    Relates weighted Fourier/Chebyshev coefficients to derivatives of g(θ)=f(cos θ); used in the proof of Theorem 3; cited to [54].
  • standard math Bernstein inequality for trigonometric polynomials (Lemma 10)
    Binds the coefficients in the chain-rule expansion (Lemma 9) in the proof of Theorem 3; cited to [43].
  • standard math Jackson kernel existence and moment bounds (Lemma 11)
    Provides the approximation kernel for the multivariate Jackson theorem (Lemma 3, Appendix D); attributed to [40].
  • standard math Kantorovich-Rubinstein duality (Eq. (1))
    Identifies W₁ with the Lipschitz IPM; used to connect the k=1 case to the Wasserstein literature.
  • domain assumption Assouad / DP-Assouad reduction framework
    Structural template for the lower bound (Appendix A), from [3] and the coupling-based Assouad inequality of [63].
  • domain assumption Density of C¹ gradient-bounded functions in the 1-Lipschitz class
    Used in Section 1.2 to relate d₁ to W₁; standard mollification fact, stated without proof.

pith-pipeline@v1.3.0-alltime-deepseek · 22779 in / 41229 out tokens · 371534 ms · 2026-08-03T05:39:47.041274+00:00 · methodology

0 comments
read the original abstract

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,\delta)$-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 $O_{k,d}(n^{-\min \{1, \frac{k}{d}\}})$, 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 \citep{wang2016differentially}. Moreover, we establish the first minimax lower bound for the utility of $(\varepsilon,\delta)$-differentially private synthetic data with respect to $k$-smooth queries, extending the Wasserstein lower bound for $\varepsilon$-differential privacy in (Boedihardjo et al., 2024).

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

67 extracted references · 6 linked inside Pith

  1. [1]

    Deep learning with differential privacy

    Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016. 11

    2016

  2. [2]

    Census topdown: Differentially private data, in- cremental schemas, and consistency with public knowledge.US Census Bureau, 2019

    John Abowd, Robert Ashmead, Garfinkel Simson, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, and William Sexton. Census topdown: Differentially private data, in- cremental schemas, and consistency with public knowledge.US Census Bureau, 2019

    2019

  3. [3]

    Differentially private assouad, fano, and le cam

    Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. InAlgorithmic Learning Theory, pages 48–78. PMLR, 2021

    2021

  4. [4]

    Differ- entially private covariance estimation.Advances in Neural Information Processing Systems, 32, 2019

    Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Differ- entially private covariance estimation.Advances in Neural Information Processing Systems, 32, 2019

    2019

  5. [5]

    Wasserstein concentration of empirical measures for dependent data via the method of moments.arXiv preprint arXiv:2601.07228, 2026

    Arash A Amini and Luciano Vinas. Wasserstein concentration of empirical measures for dependent data via the method of moments.arXiv preprint arXiv:2601.07228, 2026

    arXiv 2026

  6. [6]

    On the Gibbs exponential mechanism and private synthetic data generation

    Amir R Asadi and Po-Ling Loh. On the Gibbs exponential mechanism and private synthetic data generation. In2023 IEEE International Symposium on Information Theory (ISIT), pages 2213–2218. IEEE, 2023

    2023

  7. [7]

    Improving the gaussian mechanism for differential pri- vacy: Analytical calibration and optimal denoising

    Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential pri- vacy: Analytical calibration and optimal denoising. InInternational conference on machine learning, pages 394–403. PMLR, 2018

    2018

  8. [8]

    Privacy, accuracy, and consistency too: a holistic solution to contingency table release

    Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Ku- nal Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. InProceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 273–282, 2007

    2007

  9. [9]

    Privacy and synthetic datasets.Stan

    Steven M Bellovin, Preetam K Dutta, and Nathan Reitinger. Privacy and synthetic datasets.Stan. Tech. L. Rev., 22:1, 2019

    2019

  10. [10]

    A learning theory approach to noninterac- tive database privacy.Journal of the ACM (JACM), 60(2):1–25, 2013

    Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninterac- tive database privacy.Journal of the ACM (JACM), 60(2):1–25, 2013

    2013

  11. [11]

    Private measures, random walks, and synthetic data.Probability theory and related fields, 189(1):569–611, 2024

    March Boedihardjo, Thomas Strohmer, and Roman Vershynin. Private measures, random walks, and synthetic data.Probability theory and related fields, 189(1):569–611, 2024

    2024

  12. [12]

    Synthetic data generators–sequential and private.Advances in Neural Information Processing Systems, 33:7114–7124, 2020

    Olivier Bousquet, Roi Livni, and Shay Moran. Synthetic data generators–sequential and private.Advances in Neural Information Processing Systems, 33:7114–7124, 2020

    2020

  13. [13]

    A universal law of robustness via isoperimetry.Advances in Neural Information Processing Systems, 34:28811–28822, 2021

    S´ ebastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry.Advances in Neural Information Processing Systems, 34:28811–28822, 2021

    2021

  14. [14]

    Continual release of differentially private synthetic data from longitudinal data collections.Proceedings of the ACM on Management of Data, 2(2):1–26, 2024

    Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, and Wanrong Zhang. Continual release of differentially private synthetic data from longitudinal data collections.Proceedings of the ACM on Management of Data, 2(2):1–26, 2024

    2024

  15. [15]

    Make up your mind: The price of online queries in differential privacy

    Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. InProceedings of the twenty-eighth annual ACM- SIAM symposium on discrete algorithms, pages 1306–1325. SIAM, 2017

    2017

  16. [16]

    Fingerprinting codes and the price of approximate differential privacy

    Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. InProceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 1–10, 2014

    2014

  17. [17]

    The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.The Annals of Statistics, 49(5):2825–2850, 2021

    T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.The Annals of Statistics, 49(5):2825–2850, 2021. 12

    2021

  18. [18]

    Differentially private histogram with valid statistics.Statistics & Probability Letters, 219:110354, 2025

    Zilong Cao, Shisong Wu, Xuanang Li, and Hai Zhang. Differentially private histogram with valid statistics.Statistics & Probability Letters, 219:110354, 2025

    2025

  19. [19]

    A short course on approximation theory.Bowling Green State University, Bowling Green, OH, 38, 1998

    Neal L Carothers. A short course on approximation theory.Bowling Green State University, Bowling Green, OH, 38, 1998

    1998

  20. [20]

    Privacy-preserving logistic regression.Ad- vances in neural information processing systems, 21, 2008

    Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression.Ad- vances in neural information processing systems, 21, 2008

    2008

  21. [21]

    Differentially private empirical risk minimization.Journal of Machine Learning Research, 12(3), 2011

    Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization.Journal of Machine Learning Research, 12(3), 2011

    2011

  22. [22]

    Privacy at scale: Local differential privacy in practice

    Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tian- hao Wang. Privacy at scale: Local differential privacy in practice. InProceedings of the 2018 International Conference on Management of Data, pages 1655–1658, 2018

    2018

  23. [23]

    Certified private data release for sparse lipschitz functions

    Konstantin Donhauser, Johan Lokna, Amartya Sanyal, March Boedihardjo, Robert H¨ onig, and Fanny Yang. Certified private data release for sparse lipschitz functions. InInterna- tional Conference on Artificial Intelligence and Statistics, pages 1396–1404. PMLR, 2024

    2024

  24. [24]

    Minimax optimal proce- dures for locally private estimation.Journal of the American Statistical Association, 113(521):182–201, 2018

    John C Duchi, Michael I Jordan, and Martin J Wainwright. Minimax optimal proce- dures for locally private estimation.Journal of the American Statistical Association, 113(521):182–201, 2018

    2018

  25. [25]

    Differential privacy in practice: Expose your epsilons!Journal of Privacy and Confidentiality, 9(2), 2019

    Cynthia Dwork, Nitin Kohli, and Deirdre Mulligan. Differential privacy in practice: Expose your epsilons!Journal of Privacy and Confidentiality, 9(2), 2019

    2019

  26. [26]

    The algorithmic foundations of differential privacy.Foun- dations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Foun- dations and Trends®in Theoretical Computer Science, 9(3–4):211–407, 2014

    2014

  27. [27]

    Instance-optimal private density estimation in the wasserstein distance.Advances in Neural Information Processing Systems, 37:90061–90131, 2024

    Vitaly Feldman, Audra McMillan, Satchit Sivakumar, and Kunal Talwar. Instance-optimal private density estimation in the wasserstein distance.Advances in Neural Information Processing Systems, 37:90061–90131, 2024

    2024

  28. [28]

    JHU press, 2013

    Gene H Golub and Charles F Van Loan.Matrix computations. JHU press, 2013

    2013

  29. [29]

    Private evolution converges.arXiv preprint arXiv:2506.08312, 2025

    Tom´ as Gonz´ alez, Giulia Fanti, and Aaditya Ramdas. Private evolution converges.arXiv preprint arXiv:2506.08312, 2025

    arXiv 2025

  30. [30]

    Mirror descent algorithms with nearly dimension-independent rates for differentially-private stochastic saddle-point problems.arXiv preprint arXiv:2403.02912, 2024

    Tom´ as Gonz´ alez, Crist´ obal Guzm´ an, and Courtney Paquette. Mirror descent algorithms with nearly dimension-independent rates for differentially-private stochastic saddle-point problems.arXiv preprint arXiv:2403.02912, 2024

    arXiv 2024

  31. [31]

    Differentially private wasserstein barycenters.arXiv preprint arXiv:2510.03021, 2025

    Anming Gu, Sasidhar Kunapuli, Mark Bun, Edward Chien, and Kristjan Greenewald. Differentially private wasserstein barycenters.arXiv preprint arXiv:2510.03021, 2025

    arXiv 2025

  32. [32]

    A simple and practical algorithm for differentially private data release.Advances in neural information processing systems, 25, 2012

    Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release.Advances in neural information processing systems, 25, 2012

    2012

  33. [33]

    A multiplicative weights mechanism for privacy- preserving data analysis

    Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism for privacy- preserving data analysis. In2010 IEEE 51st annual symposium on foundations of computer science, pages 61–70. IEEE, 2010

    2010

  34. [34]

    Differential privacy in the 2020 census will distort covid-19 rates.Socius, 7:2378023121994014, 2021

    Mathew E Hauer and Alexis R Santos-Lozada. Differential privacy in the 2020 census will distort covid-19 rates.Socius, 7:2378023121994014, 2021. 13

    2020

  35. [35]

    Implementing differential privacy: Seven lessons from the 2020 United States Census.Harvard Data Science Review, 2(2), 2020

    Michael B Hawes. Implementing differential privacy: Seven lessons from the 2020 United States Census.Harvard Data Science Review, 2(2), 2020

    2020

  36. [36]

    Differentially private low- dimensional synthetic data from high-dimensional datasets.Information and Inference: A Journal of the IMA, 14(1):iaae034, 2025

    Yiyun He, Thomas Strohmer, Roman Vershynin, and Yizhe Zhu. Differentially private low- dimensional synthetic data from high-dimensional datasets.Information and Inference: A Journal of the IMA, 14(1):iaae034, 2025

    2025

  37. [37]

    Algorithmically effective differentially private synthetic data

    Yiyun He, Roman Vershynin, and Yizhe Zhu. Algorithmically effective differentially private synthetic data. InThe Thirty Sixth Annual Conference on Learning Theory, pages 3941–

  38. [38]

    Online differentially private synthetic data generation.IEEE Transactions on Privacy, (01):1–12, 2024

    Yiyun He, Roman Vershynin, and Yizhe Zhu. Online differentially private synthetic data generation.IEEE Transactions on Privacy, (01):1–12, 2024

    2024

  39. [39]

    Private synthetic data generation in bounded memory.Proceedings of the ACM on Management of Data, 3(2):1– 25, 2025

    Rayne Holland, Seyit Camtepe, Chandra Thapa, and Minhui Xue. Private synthetic data generation in bounded memory.Proceedings of the ACM on Management of Data, 3(2):1– 25, 2025

    2025

  40. [40]

    On approximation by trigonometric sums and polynomials.Transactions of the American Mathematical society, 13(4):491–515, 1912

    Dunham Jackson. On approximation by trigonometric sums and polynomials.Transactions of the American Mathematical society, 13(4):491–515, 1912

    1912

  41. [41]

    American Mathematical Soc., 1930

    Dunham Jackson.The theory of approximation, volume 11. American Mathematical Soc., 1930

    1930

  42. [42]

    New lower bounds for private estimation and a generalized fingerprinting lemma.Advances in neural information pro- cessing systems, 35:24405–24418, 2022

    Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and a generalized fingerprinting lemma.Advances in neural information pro- cessing systems, 35:24405–24418, 2022

    2022

  43. [43]

    Cambridge Mathematical Library

    Yitzhak Katznelson.An Introduction to Harmonic Analysis. Cambridge Mathematical Library. Cambridge University Press, 3 edition, 2004

    2004

  44. [44]

    Lipschitz clustering in metric spaces.The Journal of Geometric Anal- ysis, 32(7):188, 2022

    Leonid V Kovalev. Lipschitz clustering in metric spaces.The Journal of Geometric Anal- ysis, 32(7):188, 2022

    2022

  45. [45]

    Dif- ferentially private synthetic data via foundation model apis 1: Images.arXiv preprint arXiv:2305.15560, 2023

    Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin. Dif- ferentially private synthetic data via foundation model apis 1: Images.arXiv preprint arXiv:2305.15560, 2023

    Pith/arXiv arXiv 2023

  46. [46]

    Optimizing error of high-dimensional statistical queries under differential privacy.Proceedings of the VLDB Endowment, 11(10), 2018

    Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy.Proceedings of the VLDB Endowment, 11(10), 2018

    2018

  47. [47]

    A dy- namical system perspective for Lipschitz neural networks

    Laurent Meunier, Blaise J Delattre, Alexandre Araujo, and Alexandre Allauzen. A dy- namical system perspective for Lipschitz neural networks. InInternational Conference on Machine Learning, pages 15484–15500. PMLR, 2022

    2022

  48. [48]

    Sharper bounds for chebyshev moment matching, with applications

    Cameron Musco, Christopher Musco, Lucas Rosenblatt, and Apoorv Vikram Singh. Sharper bounds for chebyshev moment matching, with applications. InThe Thirty Eighth Annual Conference on Learning Theory, pages 4309–4358. PMLR, 2025

    2025

  49. [49]

    How to dp-fy your data: A practical guide to generating synthetic data with differential privacy.arXiv preprint arXiv:2512.03238, 2025

    Natalia Ponomareva, Zheng Xu, H Brendan McMahan, Peter Kairouz, Lucas Rosenblatt, Vincent Cohen-Addad, Crist´ obal Guzm´ an, Ryan McKenna, Galen Andrew, Alex Bie, et al. How to dp-fy your data: A practical guide to generating synthetic data with differential privacy.arXiv preprint arXiv:2512.03238, 2025

    Pith/arXiv arXiv 2025

  50. [50]

    Stochastic gradient descent with differentially private updates

    Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In2013 IEEE global conference on signal and informa- tion processing, pages 245–248. IEEE, 2013. 14

    2013

  51. [51]

    On integral probability metrics,ϕ-divergences and binary classification

    Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Sch¨ olkopf, and Gert RG Lanckriet. On integral probability metrics,ϕ-divergences and binary classification. arXiv preprint arXiv:0901.2698, 2009

    Pith/arXiv arXiv 2009

  52. [52]

    Between pure and approximate differential privacy

    Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. arXiv preprint arXiv:1501.06095, 2015

    Pith/arXiv arXiv 2015

  53. [53]

    Differentially private k-means clustering

    Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private k-means clustering. InProceedings of the sixth ACM conference on data and application security and privacy, pages 26–37, 2016

    2016

  54. [54]

    1, Basic theory

    Michael Eugene Taylor.Partial differential equations. 1, Basic theory. Springer, 1996

    1996

  55. [55]

    Private multiplicative weights beyond linear queries

    Jonathan Ullman. Private multiplicative weights beyond linear queries. InProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 303–312, 2015

    2015

  56. [56]

    Pcps and the hardness of generating synthetic data

    Jonathan Ullman and Salil Vadhan. Pcps and the hardness of generating synthetic data. Journal of Cryptology, 33(4):2078–2112, 2020

    2078

  57. [57]

    Springer, 2009

    C´ edric Villani.Optimal transport: old and new, volume 338. Springer, 2009

    2009

  58. [58]

    A closed form scale bound for the (ε, δ)-differentially private gaussian mechanism valid for all privacy regimes.arXiv preprint arXiv:2012.10523, 2020

    Staal A Vinterbo. A closed form scale bound for the (ε, δ)-differentially private gaussian mechanism valid for all privacy regimes.arXiv preprint arXiv:2012.10523, 2020

    Pith/arXiv arXiv 2012

  59. [59]

    Distance-based classification with Lipschitz functions.J

    Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with Lipschitz functions.J. Mach. Learn. Res., 5(Jun):669–695, 2004

    2004

  60. [60]

    Differentially private data releasing for smooth queries.The Journal of Machine Learning Research, 17(1):1779–1820, 2016

    Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang. Differentially private data releasing for smooth queries.The Journal of Machine Learning Research, 17(1):1779–1820, 2016

    2016

  61. [61]

    A statistical framework for differential privacy

    Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375–389, 2010

    2010

  62. [62]

    Private synthetic graph generation and fused gromov-wasserstein distance.arXiv preprint arXiv:2502.11778, 2025

    Leoni Carla Wirth, Gholamali Aminian, and Gesine Reinert. Private synthetic graph generation and fused gromov-wasserstein distance.arXiv preprint arXiv:2502.11778, 2025

    Pith/arXiv arXiv 2025

  63. [63]

    Assouad, fano, and le cam

    Bin Yu. Assouad, fano, and le cam. InFestschrift for Lucien Le Cam: research papers in probability and statistics, pages 423–435. Springer, 1997. A Minimax lower bound In this section, we prove Theorem 2 in the following steps. A.1 Total variation distance bound We will first introduce several auxiliary lemmas that connect the definition of differential p...

    1997

  64. [64]

    (Trigonometric polynomial)J 1(x) = Pm i=0 bJ1(i) cos(ix)

  65. [65]

    (Positivity)J 1(x)≥0

  66. [66]

    (Normalization) 1 π R π 0 J1(x)dx= 1

  67. [67]

    23 Lemma 12(Jackson’s Theorem for 1-dimensionalk-smooth functions, [40]).Letm, k≥1and a even periodic functiongwith period2πsatisfies∥g (k)∥L∞([0,π]d) ≤1

    (Bounded moments) 1 π R π 0 |x|ℓJ1(x)dx≤ C mℓ forℓ≤k. 23 Lemma 12(Jackson’s Theorem for 1-dimensionalk-smooth functions, [40]).Letm, k≥1and a even periodic functiongwith period2πsatisfies∥g (k)∥L∞([0,π]d) ≤1. Then for every integer m≥k, ˜gm(x) :=g∗J 1 = 1 π Z π 0 J1(y)g(x−y)dy, satisfies ∥g−˜gm∥L∞([0,π]d) ≤ Ck 1 mk . Moreover, if we write the Fourier expa...