acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Synthetic Data from Sliced Chebyshev Moments

32 views

Abstract

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, . In this work, we address this "curse of dimensionality" by presenting a new DP synthetic data algorithm, , 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 examples, returns a private distribution with Sliced Wasserstein-1 distance from the target, for constant privacy parameters. So, we only need to be polynomial in the data dimension for a high-quality approximation. Along the way, we prove a moment matching result of independent interest: for a distribution on the unit ball, matching the first Chebyshev moments along 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Synthetic Data, High-Dimension Statistics, Wasserstein Distance, Functional Approximation, Moment Matching

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ZCKgOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

Private synthetic data under the Wasserstein distance suffers from the curse of dimensionality. The authors bypass this by considering private sliced Wasserstein guarantees for the data. The technique to achieve these results provide connections between Chebyshev moments and sliced Wasserstein error. The authors also test their method on a variety of experiments.

Critical strengths
  1. The problem is well-motivated and novel, the paper is generally quite well written, and the proofs are easy to follow.

The strengths generally outweight the weaknesses of the paper.

Critical weaknesses
  1. In some of the experiments, it seems prior approaches are better at smaller values of ϵ\epsilon, e.g. ϵ≤1\epsilon \le 1. The authors should mention this as a limitation. Also the figures do not seem to scale the X axis in a reasonable manner.
  2. The authors do not provide any lower bounds, which would be useful to see if there are any gaps in their algorithms.

These concerns are minor and addressing them would strengthen the paper in my opinion.

Questions for authors
  1. Can the authors fix the figures so epsilon is scaled properly (e.g. either exact scale or log-scale), and try smaller values of \epsilon?
  2. It would be nice if the authors can also provide a lower bound.
2 comments

Thank you so much for taking the time to review our paper, and for your positive assessment of our work!

Changes made to address your concerns (and the concerns of other reviewers) appear in the updated PDF in blue. We'd also like to highlight that we were able to tighten the main utility theorem after submission, so Theorem 5 now has a dimension-independent rate SW1(p,q)≤O~(1/nϵ)SW_1(p,q) \leq \tilde{O}(1/\sqrt{n\epsilon}) (it was previously O~(d1/4/nϵ)\tilde{O}(d^{1/4}/\sqrt{n\epsilon})). The improvement is via a relatively minor modification of the original proof given in Appendix C.

W1 (first part): prior approaches are better at smaller values of ϵ\epsilon, e.g. ϵ≤1\epsilon \leq 1.

This is a fair point. We added a section in the experiments where we highlight a couple of those instances where prior methods are better (for instance, AIM leads on 1-way marginal fidelity at every budget, etc.) However, we note that it is generally true that the methods that lead in these cases are explicitly measuring the statistic being evaluated (e.g., AIM measures low-order marginals directly), while SPLICE spends its budget on sliced moments that target global structure.

W1 (second part) / Q1a: the figures do not scale the x axis reasonably.

Thank you for pointing this out, we appreciate that it was confusing! In the revised PDF, each line plot figure with an ϵ\epsilon-axis now has a log-scaled x axis where we put the x-axis ticks at the actual privacy budgets.

Q1b: try smaller values of ϵ\epsilon.

During the rebuttal period, we ran the full comparison at ϵ∈{0.1,0.25}\epsilon \in \{0.1, 0.25\} with the identical protocol. We note that such small values of ϵ\epsilon are less commonly used in practical DP synthetic data implementations (see e.g. Ponomareva et al. 2026 https://arxiv.org/pdf/2512.03238, section 7.1, where they note that the majority of practical DP synthetic data methods operate in the 1≤ϵ≤101 \leq \epsilon \leq 10 regime, while ϵ≪1\epsilon \ll 1 leads to too poor performance to be practical).

Nevertheless, it is an interesting regime to consider. Below we show SPLICE against the strongest and weakest baselines in this regime (AIM 2-way and Private-GSD), extended to moderate budgets so the trend is visible (means over all datasets covered by every shown method at every budget, 43 for TVD and 36 for SW1SW_1; lower is better):

3-way TVDϵ=0.1\epsilon{=}0.10.250.250.50.51133
AIM (2-way)0.6130.6040.5920.5870.561
Private-GSD0.7400.6920.6740.6370.573
SPLICE0.7730.6830.6230.5670.510
SW1SW_1ϵ=0.1\epsilon{=}0.10.250.250.50.51133
AIM (2-way)0.0410.0390.0370.0360.033
Private-GSD0.1060.0830.0650.0470.028
SPLICE0.1050.0620.0410.0260.015

At the tightest budgets SPLICE trails the marginal-based methods: as SPLICE spreads its budget over LkLk sliced moments, at very small ϵ\epsilon the per-moment noise swamps the available signal (though even at ϵ=0.1\epsilon = 0.1, every method still beats the trivial Dirac baseline discussed with Reviewer h6QY, whose mean SW1SW_1 error is 0.198 on this set). The table also shows how quickly this reverses: SPLICE improves roughly 7x on SW1SW_1 from ϵ=0.1\epsilon = 0.1 to 33 and overtakes every baseline on both metrics by ϵ=1\epsilon = 1. In our revision, we have added the small-ϵ\epsilon results for all seven methods to the appendix (Table 3, "The tight-budget regime" in Appendix G), and refer to it in the new Limitations paragraph in the main body.

W2 / Q2: no lower bounds.

This is a good question. We have added a remark on lower-bounds in the revision (see the remark in Appendix C, beside our trivial upper bound lemma). In summary, we note the following. For d=1d = 1, the SW1=W1SW_1 = W_1, and a known lower bound of Ω~(1/(ϵn))\tilde{\Omega}(1/(\epsilon n)) holds for DP synthetic data matching any distribution; this floor is tight, as there are a few known methods that match it (e.g. Musco et al. 2025). For general dd, this implies a lower bound of Ω(1/(ϵnd))\Omega(1/(\epsilon n\sqrt{d})), which follows from embedding a difficult one-dimensional distributional instance along a line that passes through the origin. The sliced Wasserstein distance shrinks by Θ(1/d)\Theta(1/\sqrt{d}) (the expected inner product of a random direction and the direction of that line). So, for constant dd, we cannot hope to obtain a bound better than O(1/(nϵ))O(1/(n\epsilon)), which is better than our current bound of O~(1/nϵ)\tilde{O}(1/\sqrt{n\epsilon}). Whether or not the square root can be removed, or the lower bound improved in d>1d>1 dimensions, is a nice open theoretical question.

We thank you again for your time and attention to our work, we believe we have addressed your questions/concerns but welcome a continued discussion.

Thanks for clarifying my concerns. I maintain my score.

Reviewer_yVPkOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper provides a new algorithm SPLICE. It gives a differentially private distribution from a private distribution that is closed in Sliced Wasserstein-1 distance to the original dataset. It achieves this by computing Chebyshev moments along random vectors and then from a known class of elementary mixture distributions, it finds the closest distribution via gradient descent. The moments are privatized so all postprocessing is private, ergo the output is private. They prove the approximation and privacy guarantees, and evaluate on known datasets where they claim it is now SOTA.

Critical strengths

Overall, I enjoyed this paper. To enumerate some strengths:

  1. This is a very easy read. A researched in the community but not working on precisely this problem I believe would likely be able to understand the main ideas very quickly.
  2. The ideas are straightforward and not convoluted. I appreciate using random vectors to comptue the moments as a way to reduce the complexity.
  3. The empirical results are very strong and their claim that this algorithm is SOTA is well supported.
Critical weaknesses

I do not large critical weaknesses. I overall support acceptance of the paper.

One weakness is the gap between their heuristic and their result. Namely, algorithm 1 returns the minimum over probability measures on the unit ball. Even though theorem 5 describes the sliced Wasserstein accuracy of the output, this output is (likely) intractable to compute. The authors are forced to find the minimum over a predetermined subspace of distributions, so the algorithm they can actually implement has no formal guarantees as far as I can tell.

Questions for authors
  1. On page 5, do we know if adding standard Gaussian noise independently is optimal for (eps, delta)-DP. I see that it is very simple from a privacy accounting perspective but perhaps there is tighter accounting that can give better output.

  2. Can we say something about the gap between the heuristic output and the theoretical output of Algorithm 1? That is, can you make any claim that is of the form in Theorem 5 but for the heuristic output?

  3. Why in the distributions to be mixed do you allow correlation between continuous distributions but not categorical distributions? It seems cleaner to have everything be independent and then using mixing for correlation for both. But if you need it for the space of continuous distributions to be rich enough, perhaps you should consider how to solve this for categorical features as well.

2 comments

Thank you for taking the time to review our paper, and for your positive assessment! We answer your questions below, and have updated the PDF as well (revisions are marked in blue).

Q1: do we know if adding standard Gaussian noise independently is optimal for (ϵ,δ)(\epsilon, \delta)-DP (or could we do tighter accounting)?

We do not know a formal way to say that adding Gaussian noise is optimal. Indeed, it is possible to add other forms of noise (Laplace is another common choice in the DP literature) and the amount added will need to depend on a different measure of sensitivity (Gaussian noise depends on an ℓ2\ell_2 measure). However, currently, we only know how to analyze our approach with Gaussian noise. As discussed in our response to Reviewer h6QY, after submitting the paper we were able to tighten our main result by removing a dimension factor. We show:

SW1(p,q)≤O~(1/nϵ) .SW_1(p, q) \leq \tilde{O}(1/\sqrt{n\epsilon})~.

This bound is getting close to optimal: we know we cannot improve beyond 1/(nϵ)1/(n\epsilon), even in one dimension. Nevertheless, it is an interesting question whether a different noise mechanism could tighten the gap between our result and this lower bound!

Q2: Can we say something about the gap between the heuristic output and the theoretical output of Algorithm 1?

Thank you for bringing this up, alongside Reviewer h6QY, who had raised a similar point.

We'd like to clarify something first: our distributional matching step is actually a precisely computable, convex problem as stated, because the moments are linear in the distribution. This means we could solve for the idealized output distribution in Algorithm 1, but only given enough compute. The problem that the mixture model solves is that this compute requirement has an exponential-in-dd cost.

As we were thinking about this question, we realized that we could actually check, with the tools we already had, whether Theorem 5 would apply to any given run. This is because the proof of Theorem 5 never actually uses that the solution returned by Algorithm 1 is globally optimal!

For our objective Φ(r)=1L∑ℓ=1L∑j=1k(m~j,ℓ−mj(θℓ,r))2/j2\Phi(r) = \frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{k}(\tilde m_{j,\ell} - m_j(\theta_\ell, r))^2/j^2, Theorem 5 instead only uses (a) Φ(q)≤Φ(p)\Phi(q) \leq \Phi(p), where pp is feasible, and (b) that Theorem 2 holds simultaneously for all distributions on the unit ball (which means it applies to whatever our optimizer ends up returning). We can directly compute the Φ\Phi values after we have fit any model, so with probability 1−β1-\beta over all the directions we sample,

SW1(p,r)≤36k+Φ(p)+Φ(r)+32βdlog⁡(6Lk2)Lfor every output r,\mathrm{SW}_1(p, r) \leq \frac{36}{k} + \sqrt{\Phi(p)} + \sqrt{\Phi(r)} + \frac{32}{\beta}\sqrt{\frac{d\log(6Lk^2)}{L}} \quad \text{for every output } r,

so any run whose output achieves Φ(r)≤Φ(p)\Phi(r) \leq \Phi(p) would inherit the Theorem 5 guarantee. We actually measured this directly on a large set of datasets/runs, please see our response to Reviewer h6QY for the table. In summary, we found the condition Φ(r)≤Φ(p)\Phi(r) \leq \Phi(p) held on 71-79% of the runs at the tight budgets (ϵ≤1\epsilon \leq 1), so Theorem 5 applied verbatim to most of the models we ended up actually fitting, plus we could directly account for the additional slack with the above bound and show it is not very big. So, though the mixture model has no a priori guarantee, in practice we can check that Theorem 5 is satisfied a posteriori, and we find that it typically is, or is with a small amount of slack.

Q3: Why allow correlation between continuous distributions but not categorical distributions? Would it not be cleaner to make everything independent and let mixing carry all correlation?

This is a great point for clarification, thank you for raising it! We deliberately imposed this asymmetry for a few reasons. First, to have a jointly dependent categorical block costs ∏ara\prod_a r_a parameters, versus the product form costing only ∑ara\sum_a r_a params. Secondly, for the moment expression to be differentiable on our mixture model (necessary for the optimization), we need the product structure (see Appendix C). If the categorical block was joint it would break the existing factorization. Finally, we ablated some variants of the mixture model, including something that is reminiscent of your suggested design (a model where everything is independent within a component, and we mix to mimic all the correlation), and went with the best one. See the model-variants ablation in Appendix E.1.

All that said, we agree that it is an interesting and promising direction to more directly model categorical dependence e.g., try low-rank couplings between categorical pairs. We view this as a promising direction for future work in improving SPLICE.

Thank you again for engaging with us during this review process, and for your encouraging outlook on our paper!

Reviewer_yVPkOpenReview ↗

Response

Dear Authors,

Thank you for your detailed responses. I maintain my score of 4. Best of luck.

Reviewer_h6QYOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper propose a new differential private synthetic data algorithm, SPLICE, by releasing noisy Chebyshev moments of random one-dimensional projections, then fitting a distribution to these perturbed moments. The key result controls sliced wasserstein-1 error uniformly over output distributions. The ideal algorithm achieves O~(d1/4/nϵ)\tilde O(d^{1/4}/\sqrt{n\epsilon}) error relative to the input distribution, thus addressing the "curse of dimensionality" in synthetic data generation.

Critical strengths
  • The theoretical contribution is meaningful. The utility guarantee holds over all candidate distributions, including outputs distribution fitted using the sampled directions. The symmetrization and Gaussian-comparison argument appears correct as well.
  • Exact differentiable moments avoid Monte Carlo noise during model-moment evaluation. Subsequent fitting preserves privacy through the post-processing property, conditional on fixed public metadata.
Critical weaknesses
  • The high-dimensional utility guarantee needs better calibration. On the unit ball, a data-independent Dirac distribution already achieves O(d−1/2)O(d^{-1/2}) sliced Wasserstein error. Thus, the advertised rate does not by itself justify the interpretation that n=O(d/ϵ)n=O(\sqrt d/\epsilon) gives meaningful distributional fidelity. A dimension-normalized comparison and trivial baseline are needed.
  • The proposed algorithm does not inherit the utility guarantee from Theorem 5. The analysis assumes unrestricted weighted least-squares fitting over bounded-support distributions, whereas the implementation fits an unbounded, restricted Gaussian mixture with a modified objective and then clips samples. Clipping supplies bounded support but changes the fitted moments.
Questions for authors
  • Can you report normalized sliced Wasserstein error and compare against the data-independent baseline?
  • The proof of Theorem 5 uses Φ(q)≤Φ(p)\Phi(q)\le\Phi(p). In the implementation, (14) is minimized over the Gaussian-mixture model q^\hat q, and samples are then clipped . Can you bound the moment error for the distribution of the clipped samples and bound its sliced Wasserstein-1 distance from pp?
2 comments

Thank you so much for your careful review! We respond to each of your points below (PDF changes in blue).

W1/Q1: consider the trivial O(d−1/2)O(d^{-1/2}) Dirac baseline w.r.t. the rate + report normalized SW error.

This is a good observation, and we agree that we should have given this trivial baseline in our original submission. As you noted, a Dirac chosen independently of the data already achieves SW1≤2/dSW_1 \leq 2/\sqrt{d} on the unit ball. Thus, our bound of O~(d1/4/nϵ)\tilde{O}(d^{1/4}/\sqrt{n\epsilon}) is only informative once nϵ≳d3/2n\epsilon \gtrsim d^{3/2} (up to log factors). We'd like to point out that this is still polynomial in dd, and that condition holds for the bulk of our benchmark datasets. Still, the correct reading of the original theorem is that we achieve non-trivial fidelity from n=O~(d3/2/ϵ)n = \tilde{O}(d^{3/2}/\epsilon) samples.

That said, after submission, we realized that our analysis could be tightened to provide a dimension-independent rate. In particular, with a relatively minor modification to the proof, we show:

SW1(p,q)≤O~(1/nϵ) .SW_1(p, q) \leq \tilde{O}(1/\sqrt{n\epsilon})~.

Note that this updated analysis has removed the d1/4d^{1/4} factor (we revised Theorem 5 and the proof in Appendix C). This has the nice side effect of cleaning up our comparison re: your comment, in particular our bound now beats the trivial rate exactly when nϵ≳dn\epsilon \gtrsim d, which holds for every benchmark dataset we considered!

In addition to reconsidering this bound, we ran the comparison you had asked for. We plotted the SW1SW_1 for a Dirac positioned at the origin w/ a Monte Carlo estimator, for 36 of our datasets. It had a mean SW1SW_1 error of 0.198. You can see the updated plot in Appendix G (Figure 6), but here we summarize the results for SPLICE and AIM (the strongest baseline from prior work) as a fraction of the trivial error achieved by the Dirac (lower is better; 1.0 would be no better than the trivial Dirac):

Normalized SW1SW_1ε=0.5ε=1ε=3ε=10
SPLICE0.230.140.070.06
AIM (2-way)0.190.190.170.17

Note: all the methods/baselines we considered beat the trivial baseline substantially.

W2/Q2: SPLICE algorithm does not directly inherit Theorem 5, bound the moment error of the clipped distribution?

This is correct. Our theory shows that distributions matched to the released (potentially noisy) moments are provably good under SW1SW_1. With enough compute, you can run the algorithm that achieves this bound exactly, so obtain a provably accurate DP algorithm. However, for practical applications, we are forced to consider a heuristic mixture model, to get around the difficulty inherent in modeling high-dimensional distributions (for which there is often NOT enough compute, by a huge margin). We cannot guarantee a good moment error in the worst case. We consider the problem of how to efficiently represent and fit high-dimensional distributions somewhat orthogonal to the main contribution of our paper, so we try to use relatively standard techniques (e.g. a mixture of simpler product distributions).

That said, in thinking about your question, we realized we can still check if our heuristic obtains a worst-case sliced Wasserstein bound. In particular, let Φ\Phi denote the objective from Algorithm 1: for a distribution rr, Φ(r)=1L∑ℓ=1L∑j=1k(m~j,ℓ−mj(θℓ,r))2/j2\Phi(r) = \frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{k}(\tilde m_{j,\ell} - m_j(\theta_\ell, r))^2/j^2.

In the proof of Theorem 5, we only use that Φ(q)≤Φ(p)\Phi(q) \leq \Phi(p), not that qq is a global optimum, and that Theorem 2 holds simultaneously for all distributions on the unit ball, which includes any output distribution qq. This lets us show that, w.p. 1−β1-\beta (over the slices) and for every output rr,

SW1(p,r)≤36k+Φ(p)+Φ(r)+32βdlog⁡(6Lk2)L.\mathrm{SW}_1(p, r) \leq \frac{36}{k} + \sqrt{\Phi(p)} + \sqrt{\Phi(r)} + \frac{32}{\beta}\sqrt{\frac{d \log(6Lk^2)}{L}}.

Note that we can measure each of these terms for a run of our mixture model! How to do so efficiently is discussed in Appendix D. So we can check Φ(q)≤Φ(p)\Phi(q) \leq \Phi(p) on a given run, and any run satisfying it will have exactly the guarantee Theorem 5 gives to an ideal minimizer.

We directly checked Φ(q)\Phi(q) on our benchmark datasets (36 datasets, 3 seeds), obtaining:

Φ(q)≤Φ(p)\Phi(q) \leq \Phi(p)med. Φ(q)/Φ(p)\Phi(q)/\Phi(p)
ϵ=0.5\epsilon=0.579%0.98
ϵ=1\epsilon=171%0.99

This shows that Theorem 5's guarantee applies verbatim to most of our runs, and then the other bound we give above covers the rest with a little slack (e.g. median 2% above the ideal bound on those other runs). We also note that Φ\Phi is measured on the clipped target distribution (as you had specified), so we account for the clipping directly (we added a little observation bounding the clipping displacement, which turns out to be quite small, in Appendix D).

Thank you again! We hope this addresses your concerns, and we would be grateful if you would consider raising your score.

Thank you for the rebuttal. The normalized SW1SW_1 comparison against the Dirac baseline addresses my concern about the interpretation of the high-dimensional guarantee. My concern about how the theorem applies to the clipped output has also been mostly addressed. Therefore I increased my score from 2 to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.