Differentially Private Synthetic Data from Sliced Chebyshev Moments
Authors: Lucas Rosenblatt, R. Teal Witter, Christopher Musco
Organizations: Department of Computer Science, Williams College · Department of Mathematical Sciences, Claremont McKenna College · Department of Computer Science and Engineering, New York University
Research on practical differentially private (DP) synthetic data has largely focused on methods that approximately preserve low-dimensional marginals of a target distribution, and can thus only hope to preserve higher-dimensional, global structure as a lucky by-product. At the same time, existing methods that target global accuracy guarantees pay a price exponential in the data dimension, d. In this work, we address this ``curse of dimensionality'' by presenting a new DP synthetic data algorithm, SPLICE, that comes with a compelling global distributional guarantee, even in high-dimensions, and moreover, is practically state-of-the-art. Our algorithm is based on measuring noisy sliced Chebyshev polynomial moments of the target distribution and fitting a distribution to match, a twist on recent polynomial methods for 1-D synthetic data. We prove that, given a dataset of n examples, SPLICE returns a private distribution with Sliced Wasserstein-1 distance O~(1/n) from the target, for constant privacy parameters. Notably, this bound is independent of the data dimension, d. Along the way, we prove a moment matching result of independent interest: for a distribution on the unit ball, matching the first O(1/α) Chebyshev moments along O~(d/α2) random directions guarantees α Sliced Wasserstein error. Finally, we provide a practical implementation of the algorithm that borrows tools from the tensor decomposition literature and achieves state-of-the-art performance compared to prior DP synthetic data methods on an extensive benchmark.
Figures & tables
Figure 1: This plot summarizes a comparison of state-of-the-art DP synthetic data algorithms. Each method is evaluated on the 48 downstream train-on-synthetic, test-on-real tasks and ranked according to accuracy. The distribution returned by each method was also ranked using five fidelity metrics (1-way, 2-way, and 3-way marginal TVD, kernel MMD, and sliced W1 ). The average rank determines the x and y coordinates. Lower is better on both axes.
q∈r a probability measure on BdargminL1ℓ=1∑Lj=1∑kj2(m~j,ℓ−mj(θℓ,r))2.
Algorithm 1 Private Sliced Chebyshev Moment Matching
Figure 2: Mean TSTR rank across datasets (lower is better) by privacy budget, best downstream learner per dataset. Classification (AUC), n=94 datasets, regression (MSE), n=67 .
Figure 3: Mean k -way marginal total variation distance (lower is better) on a fixed set of n=43 datasets where every method has a value at every budget. Left to right: 1-way, 2-way, 3-way marginals. SPLICE never targets marginals yet leads 2-way and 3-way fidelity from ϵ≥1 .
Figure 5
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
symbol
default
role
K
5
mixture components
R
2
rank of each continuous covariance factor
L
min(theory,300)
number of directions
k
min(theory,30)
Chebyshev degree per direction
optimizer
Adam, cosine schedule
2000 iterations, learning rate 0.02
robustness
Huber loss ( δ=0.5 ), EMA, restarts
stabilizes the non-convex fit
Appendix
Table 1: Implementation defaults for Algorithm 2 , as used in all experiments.
Figure 6: Mean TSTR rank (lower is better) by privacy budget, split by task family (top: regression, bottom: classification) and by feature type (columns: all numerical, mixed, all categorical). Each panel uses a fixed set of well-formed datasets on which every plotted method has a value at every budget: n=45 (numerical) and 22 (mixed) for regression; n=50 , 31 , and 10 for classification. Error bars are ±1 SEM across datasets. The benchmark has no well-formed all-categorical regression datasets.
Figure 7: Unbiased RBF-kernel MMD 2 between real and synthetic data (lower is better, log scale), median-heuristic bandwidth, n=36 datasets. Error bars are ±1 SEM across datasets.
Figure 8: Mean rank (lower is better) of the three SPLICE variants (CP, GMM, and the mixture of categorical-Gaussian product distributions, labeled “mixed block”), split by the fraction of discrete columns: continuous ( ≤0.3 ), mixed, and discrete ( ≥0.7 ). Left to right, the strata contain n=50 to 51 , 27 , and 20 datasets per budget.
Figure 9: Mean rank (lower is better) on 4-dimensional datasets (each restricted to its top 3 features), where the multivariate Chebyshev mechanism is still computationally feasible: the two multivariate variants against the sliced SPLICE variants. Left: classification, n=4 datasets. Right: regression, n=5 .
Method
1-way TVD ( n=58 )
2-way TVD ( n=58 )
3-way TVD ( n=58 )
MMD 2 ( n=40 )
SW 1 ( n=40 )
PrivBayes
0.214 ± 0.027
0.442 ± 0.037
0.642 ± 0.041
0.057 ± 0.016
0.032 ± 0.002
AIM (2-way)
0.143 ± 0.028
0.412 ± 0.038
0.638 ± 0.042
0.058 ± 0.012
0.036 ± 0.004
AIM (3-way)
0.143 ± 0.028
0.420 ± 0.038
0.650 ± 0.040
0.061 ± 0.012
0.039 ± 0.004
GEM (2-way)
0.189 ± 0.026
0.438 ± 0.036
0.658 ± 0.039
0.065 ± 0.016
0.036 ± 0.002
GEM (3-way)
0.243 ± 0.025
0.462 ± 0.036
0.662 ± 0.039
0.088 ± 0.018
0.045 ± 0.003
Private-GSD
0.270 ± 0.027
0.486 ± 0.035
0.668 ± 0.038
0.077 ± 0.013
0.047 ± 0.004
Appendix
Table 2: Distributional fidelity at ε=1 , the five components of the Figure 1 fidelity axis. Each entry is the mean ±1 SEM over the datasets ( n per column) where every method has a value; lower is better and the best value per column is bold.
Method
ε=0.5
ε=1.0
ε=3.0
ε=10.0
PrivBayes
5.00
3.40
3.00
3.20
AIM (2-way)
1.40
2.40
3.00
3.40
AIM (3-way)
2.60
3.60
4.60
5.00
GEM (2-way)
2.80
4.20
5.60
5.60
GEM (3-way)
5.40
6.20
7.00
6.80
Private-GSD
7.00
6.80
3.40
2.40
Appendix
Table 3: Mean fidelity rank (over the five distributional metrics of Table 2 ) at every privacy budget. Rank 1 is best out of 7; the best value per column is bold.
Classification ( n=91 )
Regression ( n=67 )
Method
ε=0.5
ε=1.0
ε=3.0
ε=10.0
ε=0.5
ε=1.0
ε=3.0
ε=10.0
PrivBayes
3.13 ± 0.16
2.95 ± 0.17
2.32 ± 0.15
1.71 ± 0.11
4.07 ± 0.19
3.36 ± 0.19
3.06 ± 0.21
2.27 ± 0.18
AIM (2-way)
4.52 ± 0.15
4.22 ± 0.17
3.68 ± 0.16
3.27 ± 0.17
3.37 ± 0.16
3.45 ± 0.17
3.49 ± 0.18
3.78 ± 0.18
AIM (3-way)
4.98 ± 0.12
5.11 ± 0.11
5.14 ± 0.12
4.93 ± 0.13
3.54 ± 0.19
3.91 ± 0.18
4.21 ± 0.15
4.30 ± 0.15
GEM (2-way)
2.64 ± 0.16
2.71 ± 0.15
3.35 ± 0.16
3.90 ± 0.15
3.64 ± 0.21
3.73 ± 0.20
4.12 ± 0.19
4.27 ± 0.18
GEM (3-way)
2.79 ± 0.17
3.12 ± 0.16
3.44 ± 0.17
3.98 ± 0.15
3.79 ± 0.20
4.36 ± 0.19
4.40 ± 0.18
4.66 ± 0.16
Appendix
Table 4: Downstream TSTR mean rank ( ±1 SEM across datasets) by privacy budget and task family, best downstream learner per dataset. Datasets are the fixed sets of well-formed tasks covered by every shown method at every budget, so the composition is identical across columns; rank 1 is best out of 6 and the best value per column is bold. Private-GSD is excluded because it covers only 10 of the 73 well-formed regression datasets.
Classification
Regression
Method
LogReg/Ridge
RF
XGB
TabPFN
LogReg/Ridge
RF
XGB
TabPFN
PrivBayes
3.02
2.56
2.71
2.85
3.27
3.04
3.18
3.40
AIM (2-way)
4.24
4.08
4.03
4.14
3.43
3.96
3.97
3.34
AIM (3-way)
4.92
4.81
4.80
4.92
3.70
3.96
4.03
3.76
GEM (2-way)
3.15
3.31
3.19
3.16
4.16
3.91
3.94
3.75
GEM (3-way)
3.13
3.41
3.36
3.10
4.33
4.10
4.06
4.43
Appendix
Table 5: Downstream TSTR mean rank at ε=1 broken out by downstream learner (the linear column is logistic regression on classification and ridge on regression). Same fixed dataset sets and rank convention as Table 4 ; the headline figures use the best learner per dataset.
Dataset
Task
ntrain
ntest
num.
cat.
WF
1000-Cameras-Dataset
regression
830
208
10
0
✓
2dplanes
regression
32,614
8,154
10
0
✓
3D_Estimation_using_RSSI_of_WLAN_dataset
regression
4,608
1,152
6
0
✓
3D_Estimation_using_RSSI_of_WLAN_dataset_c…
regression
11,520
2,880
12
0
✓
abalone
multiclass
3,341
836
7
1
✓
Abalone_reg
regression
3,341
836
7
1
✓
Appendix
Table 6: The 209 TALENT datasets in the benchmark: task type, training and test rows, numerical and categorical feature counts, and whether the dataset enters the well-formed aggregate set (WF; real-data ceiling AUC ≥0.7 or R2≥0.3 ). A few long dataset names are truncated.
Figure 10: Cost of generation at ϵ=1 : total wall time (log scale; open triangles are timeouts), peak resident memory, and peak GPU memory. Datasets, left to right: stock, phoneme, telco-customer-churn, California-Housing-Classification, BNG(mv). Markers are means over three seeds with ±1 SEM error bars; a timed-out cell is a single run stopped at the limit.
Figure 11: Controlled scaling at ϵ=1 : wall time against number of training rows at d=12 (left, log-log) and against number of columns at n=50,000 (right). Markers are means over three seeds with ±1 SEM error bars; open triangles are runs that hit the time limit.
We study (ε,δ)-differentially private synthetic data for arbitrary databases of n records in [−1,1]d under a specified integral probability metric (IPM). We introduce generalized moment matching, which estimates moments privately, fits a probability measure, and samples synthetic records. A general error theorem applies when moment error controls the target IPM. This framework extends Chebyshev moment matching for 1-Wasserstein distance and smooth queries. We apply the framework to maximum mean discrepancy with Matern and Laplace kernels and a two-layer ReLU neural tangent kernel. We also obtain guarantees for sliced Wasserstein-1 and the IPM induced by norm-bounded ReLU networks. With sufficiently many synthetic records,these rates are minimax optimal up to logarithmic factors for fixed dimension.
Rundong Ding, Yiyun He, Yizhe Zhu
Department of Mathematics, University of Southern California · Department of Mathematics, University of California San Diego
This paper investigates the problem of generating synthetic tabular data with differential privacy (DP) guarantees, enabling data sharing in sensitive domains. Despite extensive study, state-of-the-art methods often focus on minimizing low-order marginal query errors and overlook the challenges posed by high-order correlations. To address this gap, we extend the Private Evolution (PE) framework, originally developed for DP-compliant image and text synthesis, to tabular data. We introduce Tab-PE -- an algorithm for synthetic tabular data generation under DP constraints. Tab-PE iteratively improves a candidate dataset via an evolutionary process that leverages tabular-specialized operators to produce variations, privately scores them, and selects the highest-quality samples to retain and propagate. In contrast to the original PE, which relies on large foundation models, Tab-PE employs heuristic operators with significantly lower computational costs, making PE more practical and scalable for tabular data. Through extensive experiments on real-world and simulation datasets, we demonstrate that Tab-PE substantially outperforms prior baselines on datasets exhibiting high-order correlations. Compared to the best baseline -- AIM, Tab-PE improves classification accuracy by up to 10% while running 28 times faster.
Differentially private (DP) pipelines often combine heterogeneous mechanisms, yet their guarantees are best analyzed using different notions of privacy (e.g., bounded range, zCDP, ADP). When composing them, we have to analyze the guarantees through a reduced common representation that loses accounting precision. This issue is particularly relevant in DP synthetic data generation, where data preprocessing, generation algorithms, and DP-SGD could appear within the same pipeline. We develop novel tools for tight end-to-end accounting of such compositions using privacy loss distributions (PLD), f-DP, and Gaussian DP (GDP). In particular, we derive PLD and GDP analyses of bounded-range mechanisms such as the Exponential mechanism. Building on these theoretical results, we introduce AIM-GDP, a GDP-native variant of AIM (a state-of-the-art DP synthetic data mechanism) that enables easy composability with complex pipelines via PLD, attack-aware risk calibration, and tight end-to-end auditing while consistently achieving better utility; and MixCal, an algorithm for calibrating adaptive mixed compositions using PLD accounting. Overall, our tools enable tighter end-to-end accounting and thus less noise at the same privacy level in DP synthetic data pipelines.