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.