Differentially Private Synthetic Data from Sliced Chebyshev Moments

Problem

Differential privacy (DP) synthetic data methods used in practice mostly match only low-order marginals over 2–3 variables, so they can only hope that high-dimensional global structure is preserved by chance. Conversely, theoretical methods that guarantee global distribution error get exponentially worse with the data dimension d. In fact, a lower bound is known showing that Wasserstein-1 error cannot be made smaller than n^(-1/d).

Method

The method samples L random directions on the unit sphere and computes the Chebyshev polynomial moments (up to degree k) of the data projected onto each direction. It adds Gaussian noise to these moments, with larger noise for higher degrees, to guarantee DP, and then finds a distribution q that fits the noisy moments. In the actual implementation, q is a mixture of K product distributions. Discrete variables are represented by independent distributions and continuous variables by Gaussians with low-rank plus diagonal covariance, and the model is trained by gradient descent using closed-form expressions for the moments.

Results

• Theory: for a constant privacy parameter, the method guarantees a Sliced Wasserstein-1 error of Õ(1/√(nε)), and this upper bound does not depend on the data dimension d.
• Supporting lemma: for distributions on the unit ball, matching the first O(1/α) Chebyshev moments along Õ(d/α²) random directions guarantees a Sliced Wasserstein error of α. A naive analysis would require a number of directions exponential in d.
• The authors report that, among the state-of-the-art DP synthetic data methods compared on the TALENT tabular data benchmark, it achieved the highest regression utility at every privacy budget.
• The authors state that for ε≥1 it had the best 2-way and 3-way marginal fidelity even though it does not target marginals directly, and that it also ranked first by a wide margin in causal structure recovery.

Limitations

The guaranteed distance is not the standard Wasserstein distance but the weaker Sliced Wasserstein distance. The data is assumed to lie within the unit ball. The theory assumes the moment-matching optimization problem can be solved, while the actual implementation uses an approximate representation (a mixture of product distributions) and a gradient descent heuristic. Experiments are limited to tabular data benchmarks.

Why it matters

When sharing or analyzing tabular data that contains personal information, the work provides theoretical and experimental evidence that it is possible to generate DP synthetic data that preserves global structure better than existing methods that match only low-order marginals.

Key terms

Differential privacy (DP)

A standard that mathematically limits the exposure of personal information by adding noise so that the output distribution is nearly the same whether or not any one person's data is in the dataset.

Sliced Wasserstein distance

A value obtained by projecting high-dimensional distributions onto one-dimensional distributions along random directions and then averaging the Wasserstein distance over those directions.

Chebyshev moments

The expected values of Chebyshev polynomials under a distribution. They are more numerically stable than ordinary power moments, which makes them well suited to recovering a distribution even when noise is added.

Select-Measure-Estimate

The common procedure for DP synthetic data: choose the statistics to measure, measure them with added noise, and then estimate a distribution that fits those measurements.

Original

• arXiv abstract
• PDF
• HTML full text
• Hugging Face

Authors: Lucas Rosenblatt, R. Teal Witter, Christopher Musco · Posted 2026-10-30 · License CC BY 4.0 · Based on the full text

This review is an AI-written summary of the paper. Please treat the original paper as the reference.