Differentially Private Synthetic Data from Sliced Chebyshev Moments

Differentially Private Synthetic Data from Sliced Chebyshev Moments

arXiv:2610.42081v1 [cs.LG] 30 Oct 2026

Lucas Rosenblatt Department of Computer Science Williams College lr21@williams.edu

R. Teal Witter Department of Mathematical Sciences Claremont McKenna College rtealwitter@cmc.edu

Christopher Musco Department of Computer Science and Engineering New York University cmusco@nyu.edu

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, 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 Õ(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 Õ(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.

1

Introduction

The generation of high-utility differentially private (DP) synthetic data has become a focal point of research into DP data release (Cummings et al., 2024). In the basic setup, we are given a dataset X = {x1 , . . . , xn } ⊂ Rd and wish to privately compute a distribution q that well-approximates the empirical distribution of X , which we denote by p (i.e., p is uniform over x1 , . . . , xn ). The hope is that q, or samples from q, can be used as a drop-in replacement for X in downstream machine learning and data analysis tasks, without the need for any further differential privacy mechanisms. To guarantee strong performance on downstream tasks, a natural goal is to develop algorithms that ensure q is close to p with respect to some meaningful statistical distance, like Wasserstein distance or some other integral probability metric. There has been significant theoretical work targeting such guarantees (He et al., 2023; Boedihardjo et al., 2024; Feldman et al., 2024; Musco et al., 2025; Ding et al., 2026). However, 1

downstream utility (mean rank)

6 AIM (3-way)

5

PrivBayes

4

AIM (2-way)

3

Our method

GEM (3-way) GEM (2-way) Private-GSD

2 1 1

2

3

4

5

6

distributional fidelity (mean rank)

7

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. all of this work obtains bounds that suffer exponentially in the data dimension, d, so it has yielded few practically competitive algorithms. Indeed, empirically oriented synthetic data methods give up on strong distribution guarantees, focusing on achieving practical utility on realistic downstream tasks (Zhang et al., 2017; Liu et al., 2021b; McKenna et al., 2022; Liu et al., 2023). Many of the best practical methods are based on noisily measuring only low-order marginals of p (involving at most 2 or 3 variables (McKenna et al., 2022)) and returning a synthetic distribution that matches these marginals (the “Select-Measure-Estimate” paradigm (Ponomareva et al., 2026)). While they sometimes come with workload-specific error guarantees, it is not surprising that higher-dimensional correlations and structure are missed.

1.1

Our Contributions

This work seeks to address this “curse of dimensionality” in synthetic data generation. In short, we introduce a new algorithm, SPLICE, that enjoys a strong distributional error guarantee, even in high dimensions, and moreover, offers state-of-the-art practical performance on downstream tasks. SPLICE is inspired by a recent approach for low-dimensional synthetic data generation based on matching polynomial moments (specifically, noisy Chebyshev polynomial moments) (Wang et al., 2016). This approach yields near-optimal bounds in terms of Wasserstein-1 (W1 ) distance: Musco et al. (2025) show that, for ap dataset with n 1-d points, moment matching yields an (ϵ, δ)-DP distribution q such that W1 (p, q) ≤ Õ( log(1/δ)/ϵn). At the same time, Chebyshev moment matching falls under the “SelectMeasure-Estimate” paradigm, so is easy to implement efficiently. Unfortunately, however, like other approaches listed above, Chebyshev moment matching does not readily scale to high dimensions. For d-dimensional data, the bound of Musco et al. (2025) degrades to Õ(1/n1/d ) for constant ϵ, δ. This is vacuous for d ≳ log n and weak even for small constant d. Moreover, the bound cannot be improved: Boedihardjo et al. (2024) show that no method can privately achieve Wasserstein-1 error below O(1/n1/d ).

2

Algorithmic Contribution. The key issue with prior work is that obtaining small Wasserstein-1 error requires matching multivariate products of Chebyshev polynomials, the number of which grows exponentially in the number of data variables. In SPLICE, we propose to instead measure sliced Chebyshev polynomial moments, which for any unit vector θ ∈ Rd , take the form:   Ex∼Unif(X ) Tj (θT x) , where Tj is a Chebyshev polynomial of degree j. The method computes moments of this form for L different random vectors θ1 , . . . , θL , where L scales polynomially in d. It then adds noise to those moments to ensure differential privacy, and finally fits a distribution q that matches the noisy moments. In other words, the method again fits into the popular “Select-Measure-Estimate” paradigm, but replaces low-degree marginal measurements with sliced moment measurements. Our main theoretical result is to prove that, while Wasserstein distance is out of reach, SPLICE yields a strong bound on the sliced Wasserstein-1 distance between our private distribution q and target p. Letting W1 denote the one-dimensional Wasserstein-1 distance and S d−1 denotes the unit sphere in d dimensional Euclidean space, sliced Wasserstein-1 distance is defined as: SW1 (p, q) := Eθ∼Unif(S d−1 ) [W1 (p̄θ , q̄θ )] ,

(1)

where p̄θ (analogously, q̄θ ) is the pushforward distribution obtained by projecting p onto θ ∈ S d−1 : p̄θ (A) = p({x : θ⊤ x ∈ A}) for any measurable set A ⊆ R.

(2)

In other words, SW1 (p, q) is the average Wasserstein-1 distance between one-dimensional projections of p and q. Originally introduced as a tractable approximation for the standard Wasserstein-1 distance (Rabin et al., 2011; Bonneel et al., 2015), sliced Wasserstein distance has been widely adopted across machine learning, especially in the generative model literature, as a valuable measure in its own right (Deshpande et al., 2018; 2019; Kolouri et al., 2018; 2019a; Liutkus et al., 2019; Nadjahi et al., 2020; Sebag et al., 2025; Gu et al., 2025). Concretely, we prove the following bound, which is stated more formally in Section 3 and proven in Section C: Theorem 5. Let B d denote the unit ball in Rd . There is an (ϵ, δ)-differentially private algorithm (SPLICE) that, given a dataset X = {x1 , . . . , xn } ⊂ Bd with p = Unif(X ), returns q such that   1 SW1 (p, q) ≤ Õ √ , with probability at least 99/100. (10) nϵ Critically, the bound in Theorem 5 is independent of the data dimension d: sliced Wasserstein error α requires only n = Õ(1/(ϵα2 )) data examples, though we allow the number of sampled directions to still depend on d. In contrast, as discussed above, obtaining even constant Wasserstein-1 error requires n = 2Ω(d) examples (Boedihardjo et al., 2024). The lack of dimension dependence in Theorem 5 mirrors existing dimension-free bounds on the convergence of an empirical measure to the true distribution under sliced Wasserstein distance (Nadjahi et al., 2020; Manole et al., 2022; Xi & Niles-Weed, 2022; Boedihardjo, 2024). Key to the proof of Theorem 5 is a moment matching result of potentially independent interest. We show that, if two high-dimensional distributions, p and q, match on their first 1/α moments along L = Õ(d/α2 ) random slices, then SW1 (p, q) ≤ O(α). This generalizes the well-known fact that, in one dimension, matching the first 1/α moments of two distributions guarantees W1 (p, q) ≤ α (Kong & Valiant, 2017; Braverman et al., 2022). The key technical challenge in establishing this result is to show that a polynomial bound on the required number of slices, L, suffices. A naive analysis suggests that L needs to scale exponentially in d to cover the d dimensional sphere. 3

Empirical Contribution. Theorem 5 tells us how many data examples, n suffice to build an accurate synthetic distribution, q, but does not say anything about the complexity of representing or learning that distribution from noisy moment measurements. To make our results practical, we choose to represent q as a mixture of K product distributions: in each component of the mixture, discrete random variables follow independent distributions, and continuous random variables are drawn from a single joint Gaussian distribution with low-rank-plus-diagonal covariance. Dependencies between discrete variables are introduced by mixing multiple such distributions. The class of distributions we consider thus involves O(d) parameters per component, so O(Kd) in total. We fit these parameters using gradient descent, relying on the key fact that the distribution’s sliced Chebyshev moments have an exact, differentiable closed form. Empirically, using datasets from the extensive TALENT tabular data benchmark (Liu et al., 2025), we evaluate SPLICE with this chosen representation for q. Our empirical results are quite striking. Concretely, we find that the mechanism gives the best regression utility of any method among a large set of state-of-the-art benchmarks, at every privacy budget. It also offers the best error on 2-way and 3-way marginal fidelity for ϵ ≥ 1, despite not targeting marginals directly, and achieves the best causal structure recovery by a significant margin. These results are summarized in Figure 1 at ϵ = 1, where SPLICE outperforms strong marginal-based baselines on both composite axes simultaneously, distributional fidelity and downstream utility, with detailed experiments contained in Section 5. Finally, we note that the runtime of SPLICE is competitive with the fastest baselines and dramatically faster than the slowest for typical dataset sizes. Roadmap. Section 2 provides our key technical result, that sliced moments along a small number of random directions suffice to control SW1 . Section 3 leverages this result to obtain the DP guarantee of Theorem 5. Section 4 instantiates the algorithm with a practical learned representation, and Section 5 empirically tests it. Section A surveys related work in additional depth.

2

Sliced Chebyshev Moment Matching

We begin with basic preliminaries on the Wasserstein distance and moment matching. Throughout, our goal will be to approximate a distribution p, which in the case of differentially private synthetic data, will be taken to be the uniform distribution over some dataset X = {x1 , . . . , xn } ⊂ Rd . Let q be some other distribution. The Wasserstein-1 distance between p and q is defined as follows:   W1 (p, q) := inf E(x,y)∼z ∥x − y∥2 , z∈Z(p,q)

where ∥ · ∥2 is the Euclidean distance and Z(p, q) is the set of all couplings between p and q. A powerful fact is that, if two 1-dimensional distributions p and q supported1 on [−1, 1] match on their first k polynomial moments (i.e., Ex∼p [xj ] = Ex∼q [xj ] for all j ∈ 1, . . . , k), then W1 (p, q) ≤ O(1/k) (Kong & Valiant, 2017; Braverman et al., 2022). This claim follows from combining Jackson’s theorem (Jackson, 1912), which says that any 1-Lipschitz function on [−1, 1] can be approximated to error O(1/k) by a degree k polynomial, with the Kantorovich-Rubinstein dual view of Wasserstein distance, which states that W1 (p, q) = max1 Lipschitz f Ex∼p [f (x)] − Ex∼q [f (x)]. Importantly, this moment matching claim can be made robust when using a basis of polynomial moments besides the standard basis (which is ill-conditioned). For example, let Tj denote the j th Chebyshev 1 The support assumption is to simplify notation, since we can always rescale the data to lie in [−1, 1]. Without scaling, the error would be O(1/k) times the diameter of the support. For high-dimensional distributions, we will likewise assume that p and q are supported on the unit ball Bd to reduce notational complexity.

4

polynomial of the first kind: T0 (x) = 1,

Tj+1 (x) = 2x · Tj (x) − Tj−1 (x) for j ≥ 1.

T1 (x) = x,

Let mj (p) = Ex∼p [Tj (x)] denote the j th Chebyshev moment. A recent result shows the following. Theorem 1 ((Musco et al., 2025, Theorem 1)). Let p, q be probability measures on [−1, 1]. For any positive integer k,  W1 (p, q) ≤

36 + Γk (p, q), k

Γk (p, q) = 

where

1/2

k X 1 j=1

j2

(mj (p) − mj (q))2 

.

(3)

Theorem 1 is useful when we wish to recover a distribution p from noisy approximations to its moments. In particular, suppose we know the first k Chebyshev moments up to cumulative error ∆k (in the sense of equation 3) and find q matching them to error ∆k (such a q always exists, since p is a valid choice). Because Γk is a norm satisfying triangle inequality, any such q satisfies W1 (p, q) ≤ 36/k + 2∆k . This argument was used by Musco et al. (2025) to obtain a near-optimal algorithm for 1-dimensional DP synthetic data based on noising Chebyshev moments with the Gaussian mechanism (Dwork & Roth, 2014). They show that, for a dataset with n 1-dimensional points, it is possible to return an (ϵ, δ)-differentially private distribution q p satisfying W1 (p, q) ≤ Õ( log(1/δ)/ϵn).

2.1

Sliced Moment Matching

As discussed, extending Theorem 1 to d dimensions requires matching a number of moments exponential in d, resulting in Wasserstein error scaling as O(1/n1/d ) (Musco et al., 2025). Our goal is to avoid this poor dependence on d by focusing on the relaxed sliced Wasserstein-1 distance defined in equation 1, noting that we always have SW1 (p, q) ≤ W1 (p, q) (Carlier et al., 2025). Towards this goal, we can immediately obtain the following corollary of Theorem 1 for high dimensional distributions. In particular, let p, q be probability measures on the unit ball B d = {x ∈ Rd : ∥x∥2 ≤ 1} and define mj (θ, p) = Ex∼p [Tj (x⊤ θ)] to be the j th Chebyshev moment of the one-dimensional projection of p as defined in equation 2. Define mj (θ, q) analogously. For any probability measure q on B d , define its weighted moment error in direction θ by  Γk (θ, p, q) := 

k X 1 j=1

j2

1/2 (mj (θ, p) − mj (θ, q))2 

.

(4)

Applying Theorem 1 to the one-dimensional projections and averaging over directions gives: Corollary 1. Let p, q be probability measures on B d . For any positive integer k, SW1 (p, q) ≤

36 + Γ̄k (p, q), k

Γ̄k (p, q) = Eθ∼Unif(S d−1 ) [Γk (θ, p, q)].

where

(5)

Corollary 1 is not immediately algorithmically useful, as it requires us to control (on average) how closely q matches the first k Chebyshev moments of p in every direction θ ∈ S d−1 . Our main technical tool is a proof that it suffices to instead only match moments for a small random sample of directions θ1 , . . . , θL drawn uniformly from S d−1 . In particular, we show:

5

Theorem 2. Let p be a probability measure on B d , let L be a positive integer, let β ∈ (0, 1), and let θ1 , . . . , θL be independent draws from Unif(S d−1 ). For any positive integer k, with probability at least 1 − β over the choice of θ1 , . . . , θL , simultaneously for all probability measures q on B d , 36 32 SW1 (p, q) ≤ + Γ̃k,L (p, q) + k β

r

L

1X d log(6Lk 2 ) , where Γ̃k,L (p, q) = Γk (θℓ , p, q). L L

(6)

ℓ=1

A consequence of this theorem is that, if we compute the first k moments of p along L = Õ(dk 2 ) random directions, the resulting information suffices to find a distribution that is O(1/k) close to p in sliced Wasserstein distance. In particular, we return any distribution that matches all of the resulting kL moments (so Γ̃k,L (p, q) = 0). Plugging into Theorem 2, we obtain SW1 (p, q) = O(1/k). However, the theorem is even more flexible in that, like Theorem 1, it allows us to return a q that only approximately matches p’s sliced moments. Approximation will be necessary in our application to differentially private data generation in Section 3, since we only have access to noised moments. Theorem 2 is proven by establishing that Γ̄k (p, q) = Eθ∼Unif(S d−1 ) [Γk (θ, p, q)] is well approximated by P Γ̃k,L (p, q) = L1 L ℓ=1 Γk (θℓ , p, q) for all q. In particular, we show: Lemma 3. Fix any positive integer k and any probability measure p on B d . Let L be a positive integer, let β ∈ (0, 1), and let θ1 , . . . , θL be independent draws from Unif(S d−1 ). With probability at least 1 − β over the choice of θ1 , . . . , θL , simultaneously for all probability measures q on Bd , L

1X 32 Γk (θℓ , p, q) − Eθ∼Unif(S d−1 ) [Γk (θ, p, q)] ≤ L β ℓ=1

r

d log(6Lk 2 ) . L

(7)

Proof q of Theorem 2. By Corollary 1, SW1 (p, q) ≤ 36/k + Γ̄k (p, q). By Lemma 3, Γ̄k (p, q) ≤ Γ̃k,L (p, q) + d log(6Lk2 ) 32 for all q, which immediately gives the theorem. β L Theorem 3 is proven in Section B. A natural proof approach would be to apply a concentration bound for each fixed distribution q, then extend to all distributions using an ϵ-net argument. However, directly discretizing the space of distributions introduces an exponential dependence on d, since representing a distribution on the d-dimensional ball requires roughly 2O(d) parameters. We avoid this issue by using symmetrization and Gaussian comparison arguments to reduce the problem to bounding a random linear combination of empirical moments. Since moments are linear in q, the resulting expression is maximized by a distribution that places all its mass at a single point. We can thus union bound over the d-dimensional ball, which has log-covering number just O(d), leading to a linear dependence in the required number of direction samples, L.

3

The SPLICE Algorithm for DP Synthetic Data

Theorem 2 suggests a route to differentially private synthetic data that mirrors the one-dimensional mechanism of Musco et al. (2025): compute sliced moments of the target dataset, intentionally add noise to those moments to ensure privacy, and construct a distribution q that matches the noised moments. We present this approach formally in Algorithm 1 below, showing how to calibrate the noise, and we then analyze the resulting accuracy of the method for any given privacy parameters. We remark that, as in Musco et al. (2025), more noise is added to higher-degree polynomial moments, since these moments play a diminishing role in capturing global structure in p. Additionally, we highlight that we intentionally do not specify the details of the final “Match” step of the algorithm. Our goal in this 6

Algorithm 1 Private Sliced Chebyshev Moment Matching Input: Dataset X = (x1 , . . . , xn ) ∈ (B d )n ; privacy parameters ϵ, δ ∈ (0, 1); integers k, L ≥ 1. Output: (ϵ, δ)-differentially private distribution q approximating p = Unif(x1 , . . . , xn ). i.i.d.

∼ Unif(S d−1 ). 2: Compute noisy moments. For all ℓ ∈ 1, . . . , L and j ∈ 1, . . . , k, compute m̃j,ℓ = Ex∼p [Tj (x⊤ θℓ )] + ηj,ℓ , where ηj,ℓ ∼ N (0, jσ 2 ) with σ 2 = 8L(1 + log k) log(1.25/δ)/(n2 ϵ2 ). 3: Match. Using the sampled directions and noisy moments, return a distribution 1: Sample directions. Sample θ1 , . . . , θL

L

k

1 X X (m̃j,ℓ − mj (θℓ , r))2 q∈ arg min . j2 r a probability measure on Bd L ℓ=1 j=1

section is to show that, if we solve the minimization problem shown, then q will be close to p in sliced Wasserstein distance with high probability. This is our main utility result. In the subsequent section, we describe an efficient heuristic for solving the problem in practice. We first establish the privacy of Algorithm 1. Doing so is straight-forward, as q only depends on p through the noisy moments, m̃j,ℓ . These moments, in turn, are obtained by adding N (0, σ 2 ) noise (i.e., applying the standard Gaussian mechanism) to the vector valued function: n 1 1X f (X )(ℓ,j) = √ · Tj (θℓ⊤ xi ) n j i=1

for ℓ ∈ 1, . . . , L and j ∈ 1, . . . , k.

(8)

√ Note the scaling by 1/ j: this ensures that the addition of N (0, jσ 2 ) noise in Algorithm 1 is equivalent to adding N (0, σ 2 ) noise to each coordinate of f (X ). Proving privacy thus amounts to bounding the ℓ2 sensitivity of f (X ). We do so under the standard replacement adjacency model, meaning that neighboring datasets differ in one record. Using that |Tj (z)| ≤ 1 for all z ∈ [−1, 1], we can bound the ℓ2 sensitivity of this function as: ∆22,f =

max

neighboring datasets X,X

∥f (X) − f (X ′ )∥22 ≤ ′

L X k X 4 4L ≤ 2 (1 + log k), jn2 n ℓ=1 j=1

Pk

where we used j=1 1/j ≤ 1 + log k. Dwork & Roth (2014, Theorem 3.22) show that (ϵ, δ)-differential privacy can be achieved by adding Gaussian noise with variance ∆22,f · 2 log(1.25/δ)/ϵ2 , which equals σ 2 . We thus conclude: Proposition 4 (Privacy). For ϵ, δ ∈ (0, 1), Algorithm 1 is (ϵ, δ)-differentially private. Next, we leverage the results of the previous section to show that Algorithm 1 also achieves a strong utility guarantee. I.e., that q is close to p in the sliced Wasserstein-1 distance. Formally we have: Theorem 5. Let q be the output of Algorithm 1. For any β ∈ (0, 1), with probability at least 1 − β over the directions and Gaussian noise, r  1/4 36 4 σ 2 (1 + log k) log(6Lk 2 ) 64 d log(6Lk 2 ) SW1 (p, q) ≤ +√ + . (9) k L β L β The proof is given in Section C. For nϵ ≥ 1 and d < nϵ, choose √ k = ⌈ nϵ⌉, L = ⌈dnϵ(1 + log(nϵ))⌉. 7

Then 1 + log k = O(1 + log(nϵ)) and, since d < nϵ, log(6Lk 2 ) = O(1 + log(nϵ)). Substituting these choices and σ 2 = 8L(1 + log k) log(1.25/δ)/(nϵ)2 in equation 9 gives ! (1 + log(nϵ))3/4 log1/4 (1.25/δ) √ , (10) SW1 (p, q) ≤ Oβ nϵ where the constant depends only on β. In particular, the bound does not depend on d. In √ the remaining √ regimes, equation 10 holds for any k, L ≥ 1: if d ≥ nϵ ≥ 1, Theorem 7 gives SW1 (p, q) ≤ 2/ d ≤ 2/ nϵ, √ and if nϵ < 1, then 2/ nϵ > 2 ≥ SW1 (p, q), so equation 10 holds with log(nϵ) read as max{0, log(nϵ)}. √ This proves the Õ(1/ nϵ) guarantee stated in Section 1.

4

A Tractable Representation

Our main result from the previous section, Theorem 5, says that it is information theoretically possible to re√ turn a private distribution q such that SW1 (p, q) ≤ Õ(1/ nϵ). Indeed, q can be obtained by postprocessing a set of sliced Chebyshev moments noised using the Gaussian mechanism. However, the theorem does not say anything about how to implement the postprocessing step efficiently, i.e. how to find q that minimizes or approximately minimizes the moment error in Algorithm 1. We address that gap in this section, providing an effective heuristic for fitting a distribution q. Mixture of product distributions. Importantly, our approach requires a more efficient representation for q than, for example, a naive d dimensional histogram, which would require 2O(d) parameters to even represent. We choose to instead optimize P over a parameter-efficient mixture of product distributions. I.e., we consider distributions of the form q̂ = K h=1 πh q̂h , where K is an integer parameter, π is a vector in the probability simplex, ∆K , and each q̂h is a product distribution. Concretely, for every index a corresponding to a categorical variable with ra levels, the distribution of q̂h at index a is represented by a probability vector ϕ(h,a) ∈ ∆ra . Each level is associated with a point on an equispaced grid of ra values on [−1, 1]. On the other hand, all continuous variables are modeled as a single joint Gaussian distribution with mean µh ∈ RdN and covariance Σh ∈ RdN ×dN , where dN (respectively, dC ) counts the continuous (respectively, categorical) variables. We assume that Σh is low-rank-plus-diagonal for N . The product of this single some rank R, i.e. Σh = Uh Uh⊤ + diag(Dh ) with Uh ∈ RdN ×R and Dh ∈ Rd>0 continuous distribution with the dC categorical distributions defines q̂h . Overall, we have: ! K X Y q̂(xC , xN ) = πh ϕ(h,a) (xa ) · N (xN ; µh , Σh ) . (11) h=1

a∈C

Any distribution of this form requires O(K(dC rmax + dN R)) parameters to represent, where rmax is an upper bound on the number of levels for any categorical variable.2 We note that, for each component distribution, q̂h , categorical and continous variables are independent, but by mixing K distributions, we can capture categorical-categorical and categorical-continuous dependence. √ It is worth noting that, in our implementation: (1) we rescale every column to [−1, 1] and measure moments of θℓ⊤ x/ d; √ as [−1, 1]d / d ⊂ Bd , the data lies in the unit ball as required by Algorithm 1, and the privacy analysis applies unchanged, and (2) the Gaussian block has unbounded support, so q̂ is not itself supported on Bd . We match moments using the unconstrained q̂ with standard regularization techniques and clip samples coordinate-wise to [−1, 1] at the end, so the final private distribution is supported on the rescaled ball. 2

8

Classification (AUC)

mean rank (lower = better)

6 4

4

2

2

" = 0:5

" = 1:0

PrivBayes

Regression (MSE)

6

" = 3:0

" = 10:0

AIM (2-way)

AIM (3-way)

" = 0:5

" = 1:0

GEM (2-way)

" = 3:0

GEM (3-way)

" = 10:0

SPLICE

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. Optimization. With the model above in place, our goal becomes to fit a distribution that minimizes the moment error in Algorithm 1, i.e., to minimize the following expression over parameters of q̂: L

k

1 X X (m̃j,ℓ − mj (θℓ , q̂))2 . L j2

(12)

ℓ=1 j=1

While we cannot ensure that doing so obtains near-minimal error over all possible distributions, as will be shown in the next section, empirically we find that our mixture model is rich enough to accurately match many practical datasets from noisy sliced moments, even with K = 5 and R = 2. We minimize equation 12 using gradient descent. We enforce simplex constraints on π and each ϕ(h,a) using a softmax reparameterization and we ensure the covariance diagonal is positive through a logarithmic reparameterization. To compute gradients, we take advantage of the fact that there is an efficient, differentiable procedure for computing mj (θℓ , q̂), which we describe in Section D.

5

Experiments

Data and Baselines. We evaluate on 209 datasets from the TALENT benchmark (Liu et al., 2025), spanning binary classification (75), multiclass classification (47), and regression (87), at privacy budgets ϵ ∈ {0.5, 1, 3, 10} with δ = 10−9 and five seeds per cell. Appendix H lists every dataset with its size, feature composition, and task. We consider a number of state-of-the-art baselines: AIM (McKenna et al., 2022) (with 2-way and 3-way marginal workloads), PrivBayes (Zhang et al., 2017), GEM (Liu et al., 2021b) (with 2-way and 3-way marginal workloads), and Private-GSD (Liu et al., 2023), all under the public-schema convention described in Section F for fairness. Our downstream utility for classification/regression measurements use the train-on-synthetic, test-on-real (TSTR) protocol, scoring each generated dataset by the best of four learners (logistic regression or ridge, random forest, XGBoost, TabPFN) and aggregating by rank. Despite checking 209 TALENT datasets, we only report aggregate comparisons on what we call “well-formed prediction tasks” i.e. tasks where the train-on-real ceiling of AUC at least 0.7 for classification and R2 at least 0.3 for regression. This means that “unlearnable” datasets do not contribute noisy wins; still, the vast majority of datasets are kept (184 of 209). Note that, unless otherwise specified, results for SPLICE use the mixture of categorical-Gaussian product distributions of Algorithm 2; a comparison among the SPLICE model variants is in Section F.1. Overall comparison. Figure 1 summarizes the benchmark at ϵ = 1 by two composite ranks: distributional fidelity (1-way, 2-way, and 3-way marginal TVD, kernel MMD2 , and sliced Wasserstein-1) and downstream 9

mean TVD (lower = better)

1-way marginals

2-way marginals

0.3

0.5

0.2

0.4

0.6 0.5

0.3

0.1 " = 0:5 " = 1:0 " = 3:0 " = 10:0

PrivBayes

0.7

AIM (2-way)

" = 0:5 " = 1:0 " = 3:0 " = 10:0

AIM (3-way)

3-way marginals

GEM (2-way)

" = 0:5 " = 1:0 " = 3:0 " = 10:0

GEM (3-way)

Private-GSD

SPLICE

mean edge Jaccard (higher = better)

mean SW 1 (lower = better)

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.

0.06 0.04 0.02 " = 0:5 PrivBayes AIM (2-way)

" = 1:0 AIM (3-way) GEM (2-way)

" = 3:0 GEM (3-way) Private-GSD

" = 10:0 SPLICE Thm. 5, scaled

0.6 0.4 0.2 0.0 " = 0:5

" = 1:0

PrivBayes AIM (2-way)

Figure 4: Sliced Wasserstein-1 distance (lower is better), 256 Monte Carlo directions on the unit ball, n = 36 datasets, with the bound of Theorem 5 parameterized at each dataset’s (n, d), minimized over k and L, and divided through by a constant; the overlay compares rates in ϵ, and baselines are faded.

" = 3:0

" = 10:0

GEM (2-way) Private-GSD

SPLICE

Figure 5: Jaccard similarity of undirected edge sets between the real-data and synthetic-data causal graphs (higher is better), n = 11 datasets. Error bars are ±1 SEM across datasets.

TSTR utility, macro-averaged over the classification and regression families with equal weight. SPLICE is ranked first on four of the five fidelity metrics, third on 1-way TVD behind only AIM (which measures those exact marginals directly), and outperforms every baseline on both composite axes simultaneously. On utility, SPLICE dominates regression and is competitive on classification tasks. Per-metric values appear in Section G. Downstream predictive utility. Figure 2 shows mean TSTR rank by privacy budget. On regression, SPLICE has the best mean rank at every budget (2.58, 2.19, 1.72, and 1.73 at ϵ = 0.5, 1, 3, 10 over 67 datasets). On classification, SPLICE is in the top 3 performers at each privacy budget. Classification is a more difficult setting for SPLICE, as the target is discrete and the datasets have more categorical features on average; the strength of sliced Chebyshev moment projections is in natively handling continuous or ordinal values, while categorical values without order are not faithfully represented by the projection into continuous space. See Figure 6 in the Appendix for the data type stratum breakdown.

10

Marginal fidelity. Despite never explicitly measuring a marginal, SPLICE is the best 3-way method at every budget, as well as the best 2-way method from ϵ = 1 (Figure 3); AIM, which matches noisy 1-way marginals directly, is best on that metric, but even there its margin shrinks as ϵ increases. SPLICE’s advantage grows with the interaction order, which is the main benefit of the method; matching higher-order Chebyshev moment measurements across random projections leads to distributional recovery containing higher-order interactions. Distributional distance and causal structure. SPLICE is theoretically motivated by the sliced Wasserstein1 metric (SW1 ), which is distributional and sensitive to higher order relationships in data. Perhaps unsurprisingly, our method is then best at every budget for SW1 (Figure 4), and the method using a mixture of categorical-Gaussian product distributions matches the theoretical rate almost exactly (the worst-case rate is scaled by a large constant factor, to match the practical SW1 error scale, but the decreasing rate across ϵ appears faithful). Additionally, the commonly used Kernel MMD distributional distance (Gretton et al., 2012) gives the same ordering (Figure 7 in the appendix). It has been noted that causal path analysis would be an impactful area for advances in DP synthetic data (Rosenblatt et al., 2024a; Ponomareva et al., 2026). Thus, we run GRaSP, a standard causal discovery method (Lam et al., 2022), on real and synthetic data and compare the recovered graphs (Figure 5). At tight and moderate budgets SPLICE roughly doubles edge recovery (measured F1) of the best marginal baseline (0.42 to 0.49 at ϵ ≤ 3 against 0.00 to 0.37). Compute and reliability. Thanks to its near-independence from sample size and dimensionality by construction, SPLICE runs in almost constant time and memory across three orders of magnitude of dataset size (30 to 120 seconds over a controlled grid from 12,500 to 400,000 rows and 6 to 24 columns, while e.g. Private-GSD times out beyond 25,000 rows, AIM struggles in higher dimensions and PrivBayes scales computationally with n (Section I)). Additionally, across the full generations of the benchmark, SPLICE completed all 16,800 of its generations with zero failures, while every other baseline failed somewhere due to each method’s structural constraints.

6

Conclusion

We introduced SPLICE, a differentially private synthetic data mechanism built on noisy sliced Chebyshev moments. Our analysis shows that matching moments along a number of random directions that is linear in the dimension controls the sliced Wasserstein-1 distance. Our mixture of categorical-Gaussian product distributions makes the mechanism practical, reliable and competitive: it outperforms strong marginal-based baselines on both composite axes simultaneously, distributional fidelity and downstream utility, across a 209-dataset benchmark, and in particular leads on regression, higher-order marginal fidelity and causal edge recovery.

Reproducibility Section E states the full practical algorithm (Algorithm 2) together with every default hyperparameter (Table 1), and Section F documents the experimental protocol, the public metadata convention, and the baseline implementations with their sources. Section H lists all benchmark datasets, and Section G reports the permetric values behind the figures. An implementation of SPLICE is available at https://github.com/lurosenb/splice. Please contact the authors for additional benchmark scripts and the complete results files.

11

Acknowledgements We thank Apoorv Vikram Singh for helpful discussions at the beginning of this project. This work was partially supported under the NSF AF program under award #2427363. The work was also partially supported by a Google TPU Builders Award.

References John Abowd, Robert Ashmead, Simson Garfinkel, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, Brett Moran, and William Sexton. Census TopDown: Differentially private data, incremental schemas, and consistency with public knowledge. Draft working paper, U.S. Census Bureau, July 2019. URL https://systems.cs.columbia.edu/private-systems-class/papers/ Abowd2019Census.pdf. John M. Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. The 2020 census disclosure avoidance system TopDown algorithm. Harvard Data Science Review, 2022. URL https://hdsr.mitpress.mit.edu/pub/ 7evz361i. Special Issue 2. Sergul Aydore, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit A. Siva. Differentially private query release through adaptive projection. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 457– 467, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/aydore21a.html. Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In Proceedings of the 26th Symposium on Principles of Database Systems (PODS), pp. 273–282, 2007. Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. J. ACM, 60(2):12:1–12:25, 2013. March Boedihardjo, Thomas Strohmer, and Roman Vershynin. Private measures, random walks, and synthetic data. Probability theory and related fields, 189(1–2):569–611, 2024. March T. Boedihardjo. Sharp bounds for max-sliced Wasserstein distances. arXiv:2403.00666, 2024.

arXiv preprint

Clément Bonet, Paul Berg, Nicolas Courty, François Septier, Lucas Drumetz, and Minh-Tan Pham. Spherical sliced-Wasserstein. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023. URL https://openreview.net/forum?id=jXQ0ipgMdU. Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22–45, 2015. Vladimir Braverman, Aditya Krishnan, and Christopher Musco. Sublinear time spectral density estimation. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pp. 1144–1157, 2022. Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. Data synthesis via differentially private Markov random fields. Proceedings of the VLDB Endowment, 14(11):2190–2202, 2021. 12

Guillaume Carlier, Alessio Figalli, Quentin Mérigot, and Yi Wang. Sharp comparisons between sliced and standard 1-Wasserstein distances. arXiv:2510.16465, 2025. URL https://arxiv.org/abs/ 2510.16465. Antoine Chatalic, Vincent Schellekens, Florimond Houssiau, Yves-Alexandre de Montjoye, Laurent Jacques, and Rémi Gribonval. Compressive learning with privacy guarantees. Information and Inference: A Journal of the IMA, 11(1):251–305, 2022. URL https://academic.oup.com/imaiai/ article/11/1/251/6276238. Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Yangsibo Huang, Matthew Jagielski, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, et al. Advancing differential privacy: Where we are now and future directions for real-world deployment. Harvard Data Science Review, 6(1), 2024. Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. In Proceedings of the 35th Annual Conference on Computational Learning Theory (COLT), pp. 625–661, 2022. URL https: //proceedings.mlr.press/v178/dagan22a.html. Ishan Deshpande, Ziyu Zhang, and Alexander G. Schwing. Generative modeling using the sliced Wasserstein distance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3483–3491, 2018. Ishan Deshpande, Yuan-Ting Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander G. Schwing. Max-sliced Wasserstein distance and its use for GANs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10648–10656, 2019. URL https://openaccess.thecvf.com/content_CVPR_2019/ html/Deshpande_Max-Sliced_Wasserstein_Distance_and_Its_Use_for_GANs_ CVPR_2019_paper.html. Rundong Ding, Yiyun He, and Yizhe Zhu. Minimax optimal differentially private synthetic data for smooth queries. In Proceedings of the 39th Annual Conference on Computational Learning Theory (COLT), pp. 1963–1964, 2026. URL https://proceedings.mlr.press/v336/ding26a.html. Full version: arXiv:2602.01607. Konstantin Donhauser, Johan Lokna, Amartya Sanyal, March Boedihardjo, Robert Hönig, and Fanny Yang. Certified private data release for sparse Lipschitz functions. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1396–1404, 2024. URL https: //proceedings.mlr.press/v238/donhauser24a.html. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 381–390, 2009. Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. In Proceedings of the 14th Conference on Innovations in Theoretical Computer Science (ITCS), pp. 48:1–48:24, 2023.

13

Vitaly Feldman, Audra McMillan, Satchit Sivakumar, and Kunal Talwar. Instance-optimal private density estimation in the Wasserstein distance. Advances in Neural Information Processing Systems (NeurIPS), 37:90061–90131, 2024. Miguel Fuentes, Brett C. Mullins, Ryan McKenna, Gerome Miklau, and Daniel Sheldon. Joint selection: Adaptively incorporating public information for private synthetic data. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2404–2412, 2024. URL https://proceedings.mlr.press/v238/fuentes24a.html. Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On avoiding the union bound when answering multiple differentially private queries. In Proceedings of the 34th Annual Conference on Computational Learning Theory (COLT), pp. 2133–2146, 2021. URL https://proceedings.mlr.press/v134/ ghazi21a.html. Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, and Nachiappan Valliappan. Differentially private heatmaps. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 37(6):7696–7704, Jun. 2023. URL https://ojs.aaai.org/index.php/ AAAI/article/view/25933. Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, and Sushant Sachdeva. PREM: Privately answering statistical queries with relative error. In Proceedings of the 38th Annual Conference on Computational Learning Theory (COLT), pp. 2460, 2025. URL https: //proceedings.mlr.press/v291/ghazi25a.html. Full version: arXiv:2502.14809. Kristjan Greenewald, Yuancheng Yu, Hao Wang, and Kai Xu. Privacy without noisy gradients: Slicing mechanism for generative model training. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2024. URL https://proceedings.neurips.cc/paper_files/ paper/2024/hash/e372bfe389adbf742a759396f0170356-Abstract-Conference. html. Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The journal of machine learning research, 13:723–773, 2012. URL https: //jmlr.org/papers/v13/gretton12a.html. Anming Gu, Edward Chien, and Kristjan Greenewald. Private continuous-time synthetic trajectory generation via mean-field Langevin dynamics. arXiv:2506.12203, 2025. URL https://arxiv.org/abs/ 2506.12203. Frederik Harder, Kamil Adamczewski, and Mijung Park. DP-MERF: Differentially private mean embeddings with random features for practical privacy-preserving data generation. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1819–1827, 2021. URL https://proceedings.mlr.press/v130/harder21a.html. Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 61–70, 2010. Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2348–2356, 2012. URL https://proceedings.neurips.cc/paper/2012/hash/ 208e43f0e45c4c78cafadb83d2888cb6-Abstract.html. 14

Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB Endowment, 3(1–2):1021–1032, 2010. Yiyun He, Roman Vershynin, and Yizhe Zhu. Algorithmically effective differentially private synthetic data. In Proceedings of the 36th Annual Conference on Computational Learning Theory (COLT), pp. 3941– 3968, 2023. URL https://proceedings.mlr.press/v195/he23a.html. Yiyun He, Roman Vershynin, and Yizhe Zhu. Online differentially private synthetic data generation. IEEE Transactions on Privacy, 1:19–30, 2024. ISSN 2836-208X. 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. Peter J. Huber. Robust estimation of a location parameter. In Breakthroughs in statistics: Methodology and distribution, pp. 492–518. Springer, 1992. Dunham Jackson. On approximation by trigonometric sums and polynomials. Transactions of the American Mathematical Society, 13(4):491–515, 1912. James Jordon, Jinsung Yoon, and Mihaela van der Schaar. PATE-GAN: Generating synthetic data with differential privacy guarantees. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019. URL https://openreview.net/forum?id=S1zk9iRqF7. Soheil Kolouri, Gustavo K. Rohde, and Heiko Hoffmann. Sliced Wasserstein distance for learning Gaussian mixture models. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3427–3436, 2018. Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized sliced Wasserstein distances. In Advances in Neural Information Processing Systems (NeurIPS), 2019a. URL https://proceedings.neurips.cc/paper/2019/hash/ f0935e4cd5920aa6c7c996a5ee53a70f-Abstract.html. Soheil Kolouri, Phillip E. Pope, Charles E. Martin, and Gustavo K. Rohde. Sliced Wasserstein autoencoders. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019b. Weihao Kong and Gregory Valiant. Spectrum estimation from samples. The Annals of Statistics, 45(5): 2218–2247, 2017. Wai-Yin Lam, Bryan Andrews, and Joseph Ramsey. Greedy relaxations of the sparsest permutation algorithm. In Proceedings of the 38th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1052–1062, 2022. URL https://proceedings.mlr.press/v180/lam22a.html. Jaewoo Lee, Yue Wang, and Daniel Kifer. Maximum likelihood postprocessing for differential privacy under consistency constraints. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 635–644, 2015. Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24:757–781, 2015. Si-Yang Liu, Hao-Run Cai, Qi-Le Zhou, Huai-Hong Yin, Tao Zhou, Jun-Peng Jiang, and Han-Jia Ye. Talent: A tabular analytics and learning toolbox. Journal of Machine Learning Research, 26(226):1–16, 2025. URL https://jmlr.org/papers/v26/25-0512.html. 15

Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu. Leveraging public data for practical private query release. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 6968–6977, 2021a. URL https://proceedings.mlr.press/v139/ liu21w.html. Terrance Liu, Giuseppe Vietri, and Steven Z. Wu. Iterative methods for private synthetic data: Unifying framework and new methods. Advances in Neural Information Processing Systems (NeurIPS), 34:690–702, 2021b. URL https://proceedings.neurips.cc/paper/2021/ hash/0678c572b0d5597d2d4a6b5bd135754c-Abstract.html. Terrance Liu, Jingwu Tang, Giuseppe Vietri, and Steven Z. Wu. Generating private synthetic data with genetic algorithms. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023. URL https://proceedings.mlr.press/v202/liu23ag.html. Antoine Liutkus, Umut Simsekli, Szymon Majewski, Alain Durmus, and Fabian-Robert Stöter. SlicedWasserstein flows: Nonparametric generative modeling via optimal transport and diffusions. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 4104–4113, 2019. URL https://proceedings.mlr.press/v97/liutkus19a.html. Tudor Manole, Sivaraman Balakrishnan, and Larry Wasserman. Minimax confidence intervals for the sliced Wasserstein distance. Electronic Journal of Statistics, 16(1), 2022. Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of highdimensional statistical queries under differential privacy. Proceedings of the VLDB Endowment, 11(10), 2018. Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphical-model based estimation and inference for differential privacy. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 4435–4444, 2019. URL https://proceedings.mlr.press/v97/mckenna19a.html. Ryan McKenna, Gerome Miklau, and Daniel Sheldon. Winning the NIST contest: A scalable and general approach to differentially private synthetic data. Journal of Privacy and Confidentiality, 11 (3), 2021a. URL https://journalprivacyconfidentiality.org/index.php/jpc/ article/view/778. Ryan McKenna, Siddhant Pradhan, Daniel R. Sheldon, and Gerome Miklau. Relaxed marginal consistency for differentially private query answering. Advances in Neural Information Processing Systems (NeurIPS), 34:20696–20707, 2021b. Ryan McKenna, Brett Mullins, Daniel Sheldon, and Gerome Miklau. AIM: an adaptive and iterative mechanism for differentially private synthetic data. Proceedings of the VLDB Endowment, 15(11):2599–2612, 2022. Dimitri Meunier, Massimiliano Pontil, and Carlo Ciliberto. Distribution regression with sliced Wasserstein kernels. In Proceedings of the 39th International Conference on Machine Learning (ICML), pp. 15501– 15523, 2022. URL https://proceedings.mlr.press/v162/meunier22b.html. Brett Mullins, Miguel Fuentes, Yingtai Xiao, Daniel Kifer, Cameron Musco, and Daniel R. Sheldon. Efficient and private marginal reconstruction with local non-negativity. Advances in Neural Information Processing Systems (NeurIPS), 37:141356–141389, 2024.

16

Cameron Musco, Christopher Musco, Lucas Rosenblatt, and Apoorv Vikram Singh. Sharper bounds for Chebyshev moment matching, with applications. In Proceedings of the 38th Annual Conference on Computational Learning Theory (COLT), pp. 4309–4358, 2025. URL https://proceedings.mlr. press/v291/musco25a.html. Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429–443, 1997. Kimia Nadjahi, Alain Durmus, Lénaı̈c Chizat, Soheil Kolouri, Shahin Shahrampour, and Umut Şimşekli. Statistical and topological properties of sliced probability divergences. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/hash/ eefc9e10ebdc4a2333b42b2dbb8f27b6-Abstract.html. Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 351–360, 2013. Jonathan Niles-Weed and Jacob Shkrob. Nearly sharp comparison results for sliced and max-sliced Wasserstein distances. arXiv:2608.13374, 2026. URL https://arxiv.org/abs/2608.13374. Boris T. Polyak and Anatoli B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992. Natalia Ponomareva, Zheng Xu, H. Brendan McMahan, Peter Kairouz, Lucas Rosenblatt, Vincent CohenAddad, Cristóbal Guzmán, Ryan McKenna, Galen Andrew, Alex Bie, Da Yu, Alex Kurakin, Morteza Zadimoghaddam, Sergei Vassilvitskii, and Andreas Terzis. How to DP-fy your data: A practical guide to generating synthetic data with differential privacy. Journal of Artificial Intelligence Research, 86:17:1– 17:102, 2026. URL https://www.jair.org/index.php/jair/article/view/21111. Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision (SSVM), pp. 435–446. Springer, 2011. Lucas Rosenblatt, Xiaoyan Liu, Samira Pouyanfar, Eduardo de Leon, Anuj Desai, and Joshua Allen. Differentially private synthetic data: Applied evaluations and enhancements. arXiv:2011.05537, 2020. URL https://arxiv.org/abs/2011.05537. Lucas Rosenblatt, Bernease Herman, Anastasia Holovenko, Wonkwon Lee, Joshua Loftus, Elizabeth McKinnie, Taras Rumezhak, Andrii Stadnik, Bill Howe, and Julia Stoyanovich. Epistemic parity: Reproducibility as an evaluation metric for differential privacy. ACM SIGMOD Record, 53(1):65–74, 2024a. Lucas Rosenblatt, Bill Howe, and Julia Stoyanovich. Are data experts buying into differentially private synthetic data? gathering community perspectives. arXiv:2412.13030, 2024b. URL https://arxiv. org/abs/2412.13030. Raif M. Rustamov and Subhabrata Majumdar. Intrinsic sliced Wasserstein distances for comparing collections of probability distributions on manifolds and graphs. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023. URL https://proceedings.mlr.press/v202/ rustamov23a.html.

17

Ilana Sebag, Muni Sreenivas Pydi, Jean-Yves Franceschi, Alain Rakotomamonjy, Mike Gartrell, Jamal Atif, and Alexandre Allauzen. Differentially private gradient flow based on the sliced Wasserstein distance. Transactions on Machine Learning Research, 2025. URL https://openreview.net/forum? id=aiOHc1LGpD. Thomas Steinke and Jonathan R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2017. URL https://journalprivacyconfidentiality.org/index. php/jpc/article/view/648. Lloyd N. Trefethen. Approximation Theory and Approximation Practice. SIAM, 2013. URL https: //ci.nii.ac.jp/ncid/BB11436031. Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1–2):1–230, 2015. Jonathan R. Ullman and Salil P. Vadhan. PCPs and the hardness of generating private synthetic data. In Theory of Cryptography Conference (TCC), pp. 400–416, 2011. Salil P. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pp. 347–450. Springer International Publishing, 2017. Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, 1996. URL https://ci.nii.ac.jp/ncid/BC04787328. Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. Cédric Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008. ISBN 9783540710509. URL https://books.google.cl/ books?id=hV8o5R7_5tkC. Margarita Vinaroz, Mohammad-Amin Charusaie, Frederik Harder, Kamil Adamczewski, and Mi Jung Park. Hermite polynomial features for private data generation. In Proceedings of the 39th International Conference on Machine Learning (ICML), pp. 22300–22324, 2022. URL https://proceedings.mlr. press/v162/vinaroz22a.html. Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang. Differentially private data releasing for smooth queries. Journal of Machine Learning Research, 17(51):1–42, 2016. URL https://www.jmlr.org/papers/v17/14-388.html. Andreas Winkelbauer. Moments and absolute moments of the normal distribution. arXiv:1209.4340, 2012. URL https://arxiv.org/abs/1209.4340. Jiaqi Xi and Jonathan Niles-Weed. Distributional convergence of the sliced Wasserstein process. In Advances in Neural Information Processing Systems, volume 35, 2022. Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. PrivBayes: Private data release via Bayesian networks. ACM Trans. Database Syst., 42(4), October 2017. ISSN 0362-5915. Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. PrivSyn: Differentially private data synthesis. In 30th USENIX Security Symposium, pp. 929–946, 2021. URL https://www.usenix.org/conference/usenixsecurity21/ presentation/zhang-zhikun. 18

A

Extended Related Work

Here we expand the discussions of Section 2 in the context of the surrounding literature. Practical DP synthetic data. Most practical mechanisms for private tabular synthesis follow the SelectMeasure-Estimate paradigm (Ponomareva et al., 2026): choose a workload of low-dimensional statistics, measure them with calibrated noise, and fit a distribution to the noisy answers. Model lineage is extensive, from early approaches like MWEM (Hardt & Rothblum, 2010; Hardt et al., 2012) to more recent graphical-model estimators (McKenna et al., 2019; 2021a; 2022), Bayesian networks (Zhang et al., 2017), relaxed projection and generative estimators (Aydore et al., 2021; Liu et al., 2021b; McKenna et al., 2021b), marginal-selection refinements (Zhang et al., 2021; Cai et al., 2021; Liu et al., 2021a; Fuentes et al., 2024; Mullins et al., 2024), and genetic search over discretized domains (Liu et al., 2023). These build on a long line of work on accurate query answering under DP, including consistency and matrix mechanism techniques (Barak et al., 2007; Hay et al., 2010; Li et al., 2015; McKenna et al., 2018; Lee et al., 2015; Nikolov et al., 2013), and they have led to real deployments (Abowd et al., 2019; 2022; Ghazi et al., 2023). Because these mechanisms measure discrete marginals, they must discretize numerical features, a step the survey of Ponomareva et al. (2026) identifies as a central difficulty for tabular data; SPLICE sidesteps it by measuring moments of continuous projections directly. A parallel line of work trains neural generative models under DP, from GANs (Jordon et al., 2019) to recent end-to-end approaches built on foundation models (Ponomareva et al., 2026), although marginal-based methods still dominate tabular benchmarks (Rosenblatt et al., 2024b; 2020). Closest to our release-once-then-fit structure within this line are private feature-sketch generators, which release a fixed noisy feature sketch and fit a generator to it: noisy sliced projections of records trained against smoothed-sliced f -divergences (Greenewald et al., 2024), random Fourier features for kernel MMD (Harder et al., 2021), Hermite polynomial features approximating a Gaussian kernel (Vinaroz et al., 2022), and compressive learning sketches (Chatalic et al., 2022). SPLICE shares the release-once-then-fit structure, but differs in two ways: its sliced Chebyshev sketch provably controls the distributional metric SW1 , whereas these methods match kernel or feature discrepancies without a guarantee on a standard distributional metric; and these feature-matching generators have not demonstrated utility competitive with the marginal-based state of the art on realistic tabular workloads, which is the comparison our experiments target. Hardness of private synthetic data. Answering all low-order statistics accurately is possible informationtheoretically (Blum et al., 2013), but generating synthetic data that does so is computationally hard in the worst case (Dwork et al., 2009; Ullman & Vadhan, 2011; Vadhan, 2017), with sharp sample complexity transitions between pure and approximate DP (Steinke & Ullman, 2017). This explains the field’s split between practical heuristics and guarantee-first mechanisms, which can ignore these real-world constraints. Distributional guarantees. A theoretical stream targets explicit statistical distance guarantees between the synthetic and true distributions. For Wasserstein distance, private measures and random walks achieve the optimal rate, which unfortunately degrades as n−1/d in dimension d (Boedihardjo et al., 2024; He et al., 2023), motivating work on low-dimensional structure (He et al., 2025; Donhauser et al., 2024), online generation (He et al., 2024), instance optimality (Feldman et al., 2024), and streaming moment estimation (Epasto et al., 2023). Weakening the metric helps: targeting smooth query classes improves the rates, although the sample complexity still depends exponentially on dimension (Wang et al., 2016; Ding et al., 2026). Relative error guarantees also refine worst-case bounds (Ghazi et al., 2025; 2021; Dagan & Kur, 2022). Our approach descends from moment matching, where matching k (Chebyshev) moments controls one-dimensional Wasserstein distance (Kong & Valiant, 2017; Braverman et al., 2022; Musco et al., 2025);

19

in this paper, we escape the dimension-exponential cost of the multivariate extension by matching moments only along random slices. Sliced Wasserstein distance. Sliced Wasserstein distance was introduced as a tractable surrogate for Wasserstein distance (Rabin et al., 2011; Bonneel et al., 2015) and is now a standard training objective and evaluation metric for generative models (Deshpande et al., 2018; 2019; Kolouri et al., 2018; 2019b;a; Liutkus et al., 2019). Its statistical and geometric properties are an active topic, including sharp comparisons to the unsliced distance (Carlier et al., 2025; Niles-Weed & Shkrob, 2026), kernel and intrinsic variants (Meunier et al., 2022; Rustamov & Majumdar, 2023; Bonet et al., 2023), and its role as an integral probability metric (Müller, 1997; Villani, 2008). In private learning, sliced Wasserstein distance drives gradient flow generators (Sebag et al., 2025) and trajectory synthesis (Gu et al., 2025). To our knowledge, SPLICE is the first to pair a sliced Wasserstein guarantee with a practical, state-of-the-art differentially private algorithm.

B

Proof of the Moment Error Approximation Lemma

Here we provide the deferred proof of Theorem 3, which we restate below: Lemma 3. Fix any positive integer k and any probability measure p on B d . Let L be a positive integer, let β ∈ (0, 1), and let θ1 , . . . , θL be independent draws from Unif(S d−1 ). With probability at least 1 − β over the choice of θ1 , . . . , θL , simultaneously for all probability measures q on Bd , L

1X 32 Γk (θℓ , p, q) − Eθ∼Unif(S d−1 ) [Γk (θ, p, q)] ≤ L β ℓ=1

r

d log(6Lk 2 ) . L

(7)

Proof of Theorem 3. Define L

Z := sup q

1X Γk (θℓ , p, q) − Eθ∼Unif(S d−1 ) [Γk (θ, p, q)] , L ℓ=1

where the supremum is over all probability measures on B d . We bound Eθ Z and apply Markov’s inequality. Expectation subscripts indicate the random family being averaged over; all other random variables are held fixed. Symmetrization and Gaussian Comparison. Let σ1 , . . . , σL be independent Rademacher random variables, independent of the directions. A standard symmetrization inequality (see e.g. (van der Vaart & Wellner, 1996, Lemma 2.3.1)) gives " # L X 2 Eθ [Z] ≤ Eθ,σ sup σℓ Γk (θℓ , p, q) . (13) L q ℓ=1

Fix the directions θ1 , . . . , θL and define   m1 (θℓ , p) − m1 (θℓ , q) mk (θℓ , p) − mk (θℓ , q) vℓ (q) := ,..., ∈ Rk , 1 k so Γk (θℓ , p, q) = ∥vℓ (q)∥2 .

20

(14)

Symmetry of the signs gives: " Eσ sup q

L X

"

# σℓ ∥vℓ (q)∥2

≤ 2Eσ sup q

ℓ=1

L X

# σℓ ∥vℓ (q)∥2 .

(15)

ℓ=1

For any realization of σ1 , . . . , σL , sup q

L X

σℓ ∥vℓ (q)∥2 ≤ sup q

ℓ=1

L X

σℓ ∥vℓ (q)∥2 + sup q

ℓ=1

L X

(−σℓ )∥vℓ (q)∥2 .

ℓ=1

Both suprema on the right are nonnegative, since we can always choose q = p, in which case vℓ (q) = 0. Taking expectations and using the symmetry of the random signs gives equation 15. Gaussian comparison removes the ℓ2 norms: Eσ sup q

L X

σℓ ∥vℓ (q)∥2 ≤

p

π/2Eg sup q

ℓ=1

L X ⟨gℓ , vℓ (q)⟩,

(16)

ℓ=1

Here gℓ = (gℓ1 , . . . , gℓk ) are independent standard Gaussian vectors. We apply the following lemma to each sign: Lemma 6. Fix ℓ ∈ {1, . . . , L} and let vℓ (q) be as in equation 14. Let a(q) be a function over probability measures with supq |a(q)| < ∞. Let σ be a Rademacher random variable and let g ∼ N (0, Ik ). Then p Eσ sup{a(q) + σ∥vℓ (q)∥2 } ≤ Eg sup{a(q) + π/2⟨g, vℓ (q)⟩}, q

q

where both suprema range over all probability measures q on B d . Proof. Fix any two probability measures q+ and q− on B d . We restrict the Gaussian supremum to these two |a−b| measures and use that, for two quantities a and b, max{a, b} = a+b 2 + 2 to obtain p Eg sup{a(q) + π/2⟨g, vℓ (q)⟩} q p ≥ Eg max {a(q) + π/2⟨g, vℓ (q)⟩} q∈{q+ ,q− }

p a(q+ ) + a(q− ) 1 = + Eg a(q+ ) − a(q− ) + π/2⟨g, vℓ (q+ ) − vℓ (q− )⟩ 2 2 a(q+ ) + a(q− ) 1 ≥ + ∥vℓ (q+ ) − vℓ (q− )∥2 2 2 a(q+ ) + a(q− ) ∥vℓ (q+ )∥2 − ∥vℓ (q− )∥2 ≥ + . 2 2 For p the second inequality we use that, if X is symmetric about zero, then E|b+X| ≥ E|X|. Also, E|⟨g, u⟩| = 2/π∥u∥2 for every u. The last inequality follows from triangle inequality. Taking the supremum over q+ and q− separately on the right-hand side yields 1 1 sup{a(q) + ∥vℓ (q)∥2 } + sup{a(q) − ∥vℓ (q)∥2 } = Eσ sup{a(q) + σ∥vℓ (q)∥2 }, 2 q 2 q q which proves the claim. equation 16 is obtained by applying Theorem 6 inductively to each σℓ , conditioning on all other random variables and treating their contributions as the offsets a(q). 21

Concentration and Net Argument.

Combining equation 15 and equation 16 gives:   " # L L X k X X √ mj (θℓ , p) − mj (θℓ , q)  Eσ sup , σℓ Γk (θℓ , p, q) ≤ 2πEg sup gℓj j q q

(17)

ℓ=1 j=1

ℓ=1

where the gℓj are independent standard normal random variables. For fixed directions and fixed gℓj , define L X k X gℓj

h(x) :=

ℓ=1 j=1

j

Tj (θℓ⊤ x),

x ∈ Bd .

(18)

By linearity of expectation, the expression inside the supremum on the right-hand side of equation 17 is Ex∼p [h(x)] − Ex∼q [h(x)]. Since q ranges over all probability measures on B d , we have: sup {Ex∼p [h(x)] − Ex∼q [h(x)]} = Ex∼p [h(x)] − inf h(x) ≤ sup h(x) − inf h(x). x∈Bd

q

x∈Bd

x∈Bd

(19)

It remains to bound the expected range of h on B d . A net of this ball has log-cardinality linear in d. Concretely, set ρ = 1/(Lk 2 ). By the standard volumetric covering bound for the Euclidean ball (see, e.g., Vershynin (2018)), there is a ρ-net Nρ ⊆ B d that satisfies |Nρ | ≤ (6Lk 2 )d

∃x′ ∈ Nρ such that ∥x − x′ ∥2 ≤ ρ.

∀x ∈ B d ,

and

(20)

For every fixed x′ ∈ Nρ , the random variable h(x′ ) is a centered Gaussian conditional on θ1 , . . . , θL . Since |Tj (t)| ≤ 1 for t ∈ [−1, 1], its variance satisfies ′

Varg (h(x )) =

L X k X Tj (θ⊤ x′ )2 ℓ=1 j=1

ℓ j2

≤L

k X 1 j=1

j

≤ 2

π2L . 6

A standard bound on the expected maximum of a collection of Gaussian variables (Vershynin, 2018) gives   π p ′ Eg max h(x ) ≤ √ (21) Ld log(6Lk 2 ). ′ x ∈Nρ 3 It remains to extend this bound to the entire ball. Let x ∈ B d be some point in the ball and let x′ ∈ Nρ be the nearest point in our ρ-net. For t ∈ [−1, 1], we have |Tj′ (t)| ≤ j 2 (Trefethen, 2013). It follows that: |h(x) − h(x′ )| =

L X k X gℓj  ℓ=1 j=1

j

Tj (θℓ⊤ x) − Tj (θℓ⊤ x′ )



≤

L X k X |gℓj | ℓ=1 j=1

≤

L X k X |gℓj | ℓ=1 j=1

≤ρ

L X k X ℓ=1 j=1

22

j

j

Tj (θℓ⊤ x) − Tj (θℓ⊤ x′ ) j 2 |θℓ⊤ (x − x′ )|

j|gℓj |.

In the last step, we used Cauchy-Schwarz and the fact that ∥θℓ ∥2 = 1 and ∥x − x′ ∥2 ≤ ρ. It follows that:   r L X k X 2 k(k + 1) ′ ′ Eg sup h(x) ≤ Eg max h(x ) + ρEg  j|gℓj | ≤ Eg max h(x ) + ρ L ′ ′ x ∈N x ∈N π 2 ρ ρ x∈Bd ℓ=1 j=1

≤ Eg max h(x′ ) + ρLk 2 . ′ x ∈Nρ

Recalling that ρ = 1/(Lk 2 ), combining with equation 21 yields " # π p Ld log(6Lk 2 ) + 1. Eg sup h(x) ≤ √ 3 x∈Bd

(22)

The distribution of the gℓj variables is unchanged when all signs are negated, so Eg [supx∈Bd h(x)] = −Eg [inf x∈Bd h(x)]. It follows that the right hand side of equation 19 can be bounded by twice the righthand side of equation 22. Combining equation 13, equation 17, equation 19, and equation 22, we obtain r p r r π d log(6Lk 2 ) 8 π/2 d log(6Lk 2 ) Eθ [Z] ≤ 8π + ≤ 32 . (23) 6 L L L p The last inequality uses d, k, L ≥ 1, so that 1/L ≤ d log(6Lk 2 )/L. Markov’s inequality completes the proof.

23

C

Proof of the Private Utility Theorem

Here we bound the sliced Wasserstein-1 distance between the output of Algorithm 1, q, and a target distribution p. We could, by a direct analysis, bound the moment error of the differentially private, synthetic distribution q by the norm of the added noise, which would grow with the number of directions L (since σ 2 scales linearly in L). This, however, would force a trade-off against the direction-sampling error of Theorem 2, which decreases with L, and balancing the two leaves a d1/4 factor in the rate. As an alternate strategy, we use the fact that q minimizes the fitting objective to analyze how the noise correlates with the moment error of the distribution we fit for q. This correlation is controlled by a noise-weighted sum of re-centered Chebyshev polynomials Tj (θℓ⊤ x) − Tj (0), where re-centering is free (the constant term cancels ⊤ in the correlation) and ensures each summand
is bounded by O(j|θℓ x|). Examining this sum, we see it 1 P ⊤ has variance proportional to λmax L ℓ θℓ θℓ ≈ 1/d, which cleanly cancels out the factor of d in the numerator from the net argument given in the proof of Theorem 3. We first record a bound that handles small L and the regime d ≥ nϵ. √ Lemma 7. For any probability measures p, q on B d , SW1 (p, q) ≤ 2/ d. Proof. Fix any coupling (x, y) of p and q. Its projected pushforward under z 7→ θ⊤ z is a coupling of p̄θ and q̄θ , so SW1 (p, q) ≤ Ex,y Eθ |θ⊤ (x − y)|. By rotational invariance of Unif(S d−1 ) and Jensen’s inequality, for p √ any u ∈ Rd , Eθ |θ⊤ u| = ∥u∥2 Eθ |θ1 | ≤ ∥u∥2 Eθ θ12 = ∥u∥2 / d. Since ∥x − y∥2 ≤ 2 for x, y ∈ B d , we recover the claim. We restate Theorem 5 before proving it. Theorem 5. Let q be the output of Algorithm 1. For any β ∈ (0, 1), with probability at least 1 − β over the directions and Gaussian noise, r  1/4 36 4 σ 2 (1 + log k) log(6Lk 2 ) 64 d log(6Lk 2 ) SW1 (p, q) ≤ +√ + . (9) k L β L β Proof. Fix the dataset and its empirical distribution p. We first deal with the case L < 4d log d, which requires d ≥ 2. In that case the last term of equation 9 alone satisfies s s r 2 64 d log(6Lk 2 ) d log 6 log 6 ≥ 64 = 32 ≥√ . β L 4d log d log d d √ By Theorem 7, SW1 (p, q) ≤ 2/ d, so equation 9 holds with probability one. For the rest of the proof, assume L ≥ 4d log d. Let Φ denote the least-squares objective in Algorithm 1; a minimizer exists since probability measures on Bd are weakly compact and Φ is weakly continuous. Since p is feasible and q minimizes this objective, Φ(q) ≤ Φ(p). Use the noise ηj,ℓ ∼ N (0, jσ 2 ) from Algorithm 1. Here and below P ℓ,j ranges over 1 ≤ ℓ ≤ L, 1 ≤ j ≤ k. Jensen’s inequality gives 1/2  X (mj (θℓ , q) − mj (θℓ , p))2 1  . Γ̃k,L (p, q) ≤  L j2 ℓ,j

Expanding Φ(q) ≤ Φ(p) gives: 2

1 X ηj,ℓ 1 X (mj (θℓ , q) − mj (θℓ , p) − ηj,ℓ )2 ≤ 2 L j L j2 ℓ,j

=⇒

ℓ,j

1 X (mj (θℓ , q) − mj (θℓ , p))2 L

ℓ,j

j2

24

≤

2 X ηj,ℓ (mj (θℓ , q) − mj (θℓ , p)) L

ℓ,j

j2

.

(24)

Define the noise weighted sum of re-centered Chebyshev polynomials, for x ∈ B d , as, G(x) :=

1 X ηj,ℓ [Tj (θℓ⊤ x) − Tj (0)] . L j2

(25)

ℓ,j

The right side of equation 24 equals 2(Eq G − Ep G). Bounding Eq G by supx G(x) and using Eη Ep G = 0 therefore gives, conditional on the directions,   X (mj (θℓ , q) − mj (θℓ , p))2 1  ≤ 2Eη sup G(x). (26) Eη  L j2 x∈Bd ℓ,j

This remains valid P even though q depends on the noise. ⊤ Let S = L−1 L ℓ=1 θℓ θℓ be the empirical second-moment matrix of the directions. Since cosine is 1-Lipschitz, the identity Tj (u) = cos(j arccos u) gives |Tj (u) − Tj (0)| ≤ j| arccos u − π/2| = j| arcsin u|, where we used arccos u − π/2 = − arcsin u. The elementary bound | arcsin u| ≤ (π/2)|u| then gives |Tj (u) − Tj (0)| ≤ (π/2)j|u| for u ∈ [−1, 1]. Fix x ∈ B d and condition on the directions, so that the coefficients of the noises in G(x) are deterministic. Using Var(ηj,ℓ ) = jσ 2 , we obtain, L

L

k

k

1 X X jσ 2 σ 2 X X [Tj (θℓ⊤ x) − Tj (0)]2 2 ⊤ x) − T (0)] = [T (θ j j ℓ L2 j4 L2 j3 ℓ=1 j=1 ℓ=1 j=1 ! L L k π 2 σ 2 X X (θℓ⊤ x)2 π 2 σ 2 (1 + log k) 1 X ⊤ 2 ≤ ≤ (θℓ x) 4L2 j 4L L

Varη G(x) =

=

ℓ=1 j=1 2 2 π σ (1 + log k)

4L

ℓ=1

x⊤ Sx .

P The first inequality uses the Chebyshev bound above; the last line uses kj=1 1/j ≤ 1 + log k and the definition of S. Since S is positive semidefinite and ∥x∥2 ≤ 1, x⊤ Sx ≤ λmax (S)∥x∥22 ≤ λmax (S). Thus the conditional variance is at most π 2 σ 2 (1 + log k)λmax (S)/(4L), uniformly over x ∈ B d . For d ≥ 2, apply the matrix Bernstein expectation bound (Tropp, 2015, Theorem 6.6.1, Eq. (6.6.2)) to the independent, centered matrices Xℓ = θℓ θℓ⊤ − Id /d. Isotropy gives Eθ Xℓ2 = (d − 1)Id /d2 , and λmax (Xℓ ) ≤ 1, so r 1 2 log d log d 2 Eθ λmax (S) ≤ + + ≤ . d dL 3L d The last inequality uses L ≥ 4d log d; for d = 1, S = 1 deterministically. This supplies the factor 1/d needed to cancel the dimension dependence in the logarithm of the net size below. Take a net Nρ as in equation 20, with mesh ρ = (Lk 2 )−1 and size at most (6Lk 2 )d . The Gaussian maximum bound, first conditional on the directions and then averaged using Jensen’s inequality, gives   X (mj (θℓ , q) − mj (θℓ , p))2 p p 1  ≤ √πσ Eθ,η  (1 + log k)d log(6Lk 2 )Eθ λmax (S) 2 L j 2L ℓ,j r (1 + log k) log(6Lk 2 ) ≤ πσ . L

25

To extend this bound from the net to the ball, use |Tj′ | ≤ j 2 and the argument leading to equation 22. The q P 2 . Thus equation 26 yields resulting error is at most ρL−1 ℓ,j E|ηj,ℓ | ≤ Lσ πk 

 r r 2) X (mj (θℓ , q) − mj (θℓ , p))2 1 (1 + log k) log(6Lk 2 2σ  ≤ 2πσ Eθ,η  + 2 L j L L πk ℓ,j r (1 + log k) log(6Lk 2 ) ≤ 8σ . L

(27)

Markov’s inequality therefore gives, with probability at least 1 − β/2, 1/2  2  2 ) 1/4 X (mj (θℓ , q) − mj (θℓ , p))2 σ (1 + log k) log(6Lk 1 4   ≤√ . L j2 L β 

ℓ,j

Combining this with Theorem 2, also at failure probability β/2, proves that with probability at least 1 − β, r 1/4  4 σ 2 (1 + log k) log(6Lk 2 ) 64 d log(6Lk 2 ) 36 +√ + . SW1 (p, q) ≤ k L β L β The simultaneous guarantee in Theorem 2 applies to the fitted q, even though it depends on the directions and noise. This proves equation 9.

26

D

Chebyshev Moments for a Mixture of Categorical-Gaussian Product Distributions

In this section we describe how to efficiently compute the sliced Chebyshev moment, mj (θ, q̂) = Ex∼q̂ [Tj (θT x)], for any direction θ ∈ S d−1 and any distribution q̂ that fits our mixture of categorical-Gaussian product distributions from Section 4. The computation is first simplified by passing to the standard moments. In particular, we can write the P Chebyshev polynomial in the monomial basis as Tj (y) = jt=0 cj,t y t and then use that: Ex∼q̂ [Tj (θT x)] =

j X

cj,t Ex∼q̂ [(θT x)t ].

t=0

We can further simplify the computation by splitting along the mixture components: Ex∼q̂ [Tj (θT x)] =

K X

πh

j X

cj,t Ex∼q̂h [(θT x)t ].

(28)

t=0

h=1

As in Section 4, let C ⊂ {1, . . . , d} contain the indices of all categorical variables in our data vectors. Let N = {1, . . . , d} \ C contain the indices of all continuous variables. Let θN and xN denote the vectors θ and x restricted to the continuous indices. We have that: X ⊤ θT x = θ a xa + θ N xN . a∈C

We can thus compute Ex∼q̂h [(θT x)t ] by iteratively applying the following standard expression, which holds for any independent random variables A and B: t     X t t E (A + B) = E[As ]E[B t−s ], s

(29)

s=0

In this case, the variables {xa }a∈C and xN are jointly independent. We have thus reduced our task to evaluating:    ⊤  Ex∼q̂h (θa xa )t (a ∈ C) and Ex∼q̂h (θN xN )t (30) for all t less than the maximum moment degree considered. Since xa is a finite categorical variable, the first expectation reduces to a simple sum over the possible  ⊤  ⊤ x is a univariate Gaussian random values of xa . For Ex∼q̂h (θN xN )t , we use that, when x ∼ q̂h , θN N variable with mean and variance: X 2 ⊤ Dh,i θi2 . νh = θN µh and σh2 = Uh⊤ θN + 2

i∈N

We can then just apply standard closed form expressions for the raw moments of a univariate Gaussian (see Winkelbauer (2012)). We implemented the procedure described above in Torch, then used Autograd to compute gradients when optimizing over the parameters of q̂.

27

E

The SPLICE Algorithm with a Mixture of Categorical-Gaussian Product Distributions

Algorithm 2 restates the mechanism of Section 4 as we actually run it. The private release is exactly that of Algorithm 1; the “Match” step is carried out by fitting the mixture of categorical-Gaussian product distributions Equation 11 using the exact, differentiable moment computation of Section D. Table 1 lists the implementation defaults used in every experiment. Algorithm 2 SPLICE: Sliced Moment Matching with a Mixture of Categorical-Gaussian Product Distributions Input: Dataset x1 , . . . , xn ; privacy parameters ϵ, δ > 0; components K; covariance rank R; column split into blocks C, N . Output: Synthetic distribution q̂ of the form Equation 11. 1: Encode. Normalize each continuous column to [−1, 1] and map each categorical column’s levels to equally spaced grid values in [−1, 1], giving a design matrix X ∈ [−1, 1]n×d . 2: Hyperparameters. Set the maximum degree k and number of directions L (Table 1). 3: Release. Sample public directions√θ1 , . . . , θL ∼ Unif(S d−1 ), compute the scaled sliced Chebyshev moments of the projections θℓ⊤ xi / d, and add Gaussian noise calibrated to the ℓ2 sensitivity of the scaled moment vector via the analytic Gaussian mechanism. 4: Fit. Minimize the weighted squared moment error between the noisy targets and the exact model moments by gradient descent, with the softmax and logarithmic parameterizations, warm start, restarts, averaging, and loss from main body. 5: Sample. Draw components h ∼ π, categorical levels from ϕ(h,a) , continuous blocks from N (µh , Σh ), and de-normalize each column to its original range.

symbol

default

role

K R L k optimizer robustness

5 2 min(theory, 300) min(theory, 30) Adam, cosine schedule Huber loss (δ = 0.5), EMA, restarts

mixture components rank of each continuous covariance factor number of directions Chebyshev degree per direction 2000 iterations, learning rate 0.02 stabilizes the non-convex fit

Table 1: Implementation defaults for Algorithm 2, as used in all experiments.

More implementation details q

Algorithm 2 inherits (ϵ, δ)-privacy by post-processing, with the scaledp 2/πTj ,

4L Pk 1 j=1 j of Section 3 (we use the equivalent normalized basis T̄j = n2

moment sensitivity ∆2 = q 8L Pk 1 with sensitivity πn 2 j=1 j ). Continuous columns are not rounded to a grid; a grid defines categorical values only. We calibrate σ with the analytic Gaussian mechanism (as do all baselines, where appropriate, for fairness). For our objective minimization we use gradient descent on the model parameters, enforcing the simplex constraints on π and on each ϕ(h,a) by a softmax reparameterization and keeping the covariance diagonal positive through a logarithmic parameterization. We warm start the continuous-block means from the degree-one moments by least squares, since m1 (θ, q̂) is linear in the means, and we stabilize the non-convex 28

fit with random restarts (our experiments use one), an exponential moving average of the parameters (Polyak & Juditsky, 1992), a Huber loss that caps the influence of the noisiest high-degree residuals (Huber, 1992), and light entropy and ridge regularization. Note that all of these are standard moves, and additionally are post-processing with respect to the release of the noisy sliced Chebyshev moments. Sampling. To draw a synthetic record we sample a component h ∼ π, draw each categorical column independently from ϕ(h,a) , draw the continuous block from N (µh , Σh ), clip it to the encoded range, and de-normalize. We note that clipping is also what squares the model with Theorem 5: the Gaussian block in Equation 11 has unbounded support, whereas the theorem is stated for distributions on Bd , so it is the clipped samples, rather than q̂ itself, that satisfy the support assumption. Since fitting q̂ and sampling from it are both post-processing of the noisy moments, privacy is unaffected either way. Finally, because the continuous block is Gaussian, samples are smooth and do not show the quantization artifacts of grid-based mechanisms.

29

F

Additional Setup, Experiments and Ablations

Public metadata convention. For a fair comparison, all methods are given the same kind of side information: column schema metadata is read off the training set and treated as public, so estimating it does not consume privacy budget. What each method reads differs. SPLICE uses only per-column bounds (minimum and maximum) and the level set of each categorical column. Private-GSD takes an explicit dictionary of bounds; AIM treats every column as categorical and reads the categories from the data; GEM uses quantile bin edges; and PrivBayes builds its support from the observed values. Treating this metadata as public is a small idealization, but it is the standard one in the literature. We note that two of the baselines are given strictly more than bounds: GEM’s quantile edges reveal the shape of each marginal, and AIM’s category lists reveal exactly which values occur. SPLICE has the smallest metadata footprint of the methods we compare. Computational limits of baseline methods. Our comprehensive evaluation attempts 210 × 4 × 5 = 4200 generation tasks per algorithm (incorporating the 209 benchmark datasets along with one synthetic smoketest dataset excluded from the final metrics). We enforce a strict two-hour timeout per task (all methods were GPU accelerated, except for PrivBayes which has a fast C implementation). PrivBayes fails on 34 tasks due to the most massive datasets (its runtime scales as ≈ n2 , and our estimated runtime for these larger datasets was multiple days for the method). AIM with 2-way workloads fails on 34 tasks due to timeouts and GPU memory exhaustion, primarily at ϵ = 10, where it allocates larger budgets across more measurement iterations; its 3-way variant drops 153 tasks across ten high-dimensional datasets, seven of which fail across all budgets regardless of row count. GEM utilizing 3-way workloads drops 50 tasks on wide datasets with high cardinality, whereas its 2-way version successfully completes all tasks. PrivateGSD runs out of host memory on larger tables and is thus evaluated solely on the subsets in general (this is despite being run on an NVIDIA RTX PRO 6000 Blackwell GPU with 96 GB of VRAM). Conversely, SPLICE successfully executed all 16,800 of its generations, with no timeouts or out-of-memory errors. This reliability is a result of the method architecture: the sliced release compresses the data into fixed-size moment sketches, scaling linearly with n and avoiding the combinatorial explosion associated with width, cardinality, or privacy budget. Baseline implementations and parameter settings. We use the maintained or author-released implementation of every baseline. AIM runs through the OpenDP Library (https://github.com/opendp/ opendp, version 0.14.2), whose implementation builds on the graphical-model inference of private-pgm (https://github.com/ryan112358/private-pgm, mbi 1.1.0). GEM uses the authors’ dp-query-release codebase (https://github.com/terranceliu/ dp-query-release), consolidated into our harness without algorithmic changes. PrivBayes runs the authors’ reference C++ implementation through a wrapper following SDGym (https://github.com/ sdv-dev/SDGym). Private-GSD uses the authors’ implementation (https://github.com/giusevtr/ private_gsd). Causal discovery uses the GRaSP implementation in causal-learn (https:// github.com/py-why/causal-learn). Every method runs with the settings recommended by its source implementation, and no method (including SPLICE, whose k and L follow the fixed formulas of Table 1) receives per-dataset hyperparameter tuning. The only per-baseline variation we report is the workload degree (2-way and 3-way marginals for AIM and GEM), shown as separate baselines, and all methods share the privacy accounting conventions and public metadata described above.

30

Classification mean rank

Regression mean rank

5

All numerical

5

4

4

3

3

2

Mixed

All categorical no qualifying datasets

2

" = 0:5 " = 1:0 " = 3:0 " = 10:0

" = 0:5 " = 1:0 " = 3:0 " = 10:0

4

4

2

2

2

" = 0:5 " = 1:0 " = 3:0 " = 10:0

" = 0:5 " = 1:0 " = 3:0 " = 10:0

" = 0:5 " = 1:0 " = 3:0 " = 10:0

PrivBayes

AIM (2-way)

4

AIM (3-way)

GEM (2-way)

GEM (3-way)

SPLICE

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.

F.1

SPLICE Model Variants

The mixture of categorical-Gaussian product distributions from Section 4 generalizes two simpler models: a CP-style mixture of categorical product distributions, and a low-rank Gaussian mixture. (Figure legends in this appendix abbreviate the full model as “mixed block”.) We also ran both of these special cases as SPLICE variants, fit to the exact same noisy moments. Figure 8 ranks the three on roughly 97 datasets, stratified by the fraction of discrete columns. The results are what the model classes suggest: the Gaussian mixture is best on continuous data, the CP model is best on discrete data (where the Gaussian mixture does poorly), and the full mixed model is best on mixed data. Figure 9 compares slicing to the multivariate Chebyshev mechanism of Musco et al. (2025) on 4dimensional datasets, the only regime where the latter is computationally feasible. A sliced SPLICE variant is ranked first for every task type and budget. The multivariate variants are behind on regression at every ϵ; multivariate CP reaches second on classification at the looser budgets but is never first. Against the full set of baselines, the multivariate variants rank at or near the bottom. In other words, slicing helps even when d is small enough that the curse of dimensionality is not binding.

31

mean MMD 2 (lower = better)

10 −1

10 −2 " = 0:5 PrivBayes AIM (2-way)

" = 1:0 " = 3:0 " = 10:0 AIM (3-way) GEM (3-way) SPLICE GEM (2-way) Private-GSD

mean rank (lower = better)

Figure 7: Unbiased RBF-kernel MMD2 between real and synthetic data (lower is better, log scale), medianheuristic bandwidth, n = 36 datasets. Error bars are ±1 SEM across datasets.

3

continuous data

3

2 1

mixed data

3

2

0:5

1:0

3:0

10:0

1

discrete data

2

0:5

1:0

"

3:0

10:0

1

0:5

1:0

3:0

"

SPLICE (CP)

SPLICE (GMM)

10:0

"

SPLICE (mixed block)

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.

Classification (AUC)

mean rank (lower = better)

5 4

4

3

3

2

2

1

" = 0:5

" = 1:0

SPLICE (CP)

" = 3:0

SPLICE (GMM)

Regression (MSE)

5

" = 10:0

1

" = 0:5

SPLICE (mixed block)

" = 1:0

" = 3:0

Multivar (CP)

" = 10:0

Multivar (GMM)

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. 32

G

Result Tables

This section gives the numbers behind the figures in the main text. Table 2 reports the five fidelity metrics at ϵ = 1, i.e., the components of the fidelity axis of Figure 1. Table 3 gives the mean fidelity rank at every budget. Table 4 gives mean TSTR rank by budget and task family on a fixed set of datasets, and Table 5 breaks the ϵ = 1 column down by downstream learner. Every table is computed from the same saved results and the same dataset filters as the figure it supports. Method PrivBayes AIM (2-way) AIM (3-way) GEM (2-way) GEM (3-way) Private-GSD Sliced (mixed block, ours)

1-way TVD (n = 58) 2-way TVD (n = 58) 3-way TVD (n = 58) MMD2 (n = 40) SW1 (n = 40) 0.214 ±0.027 0.143 ±0.028 0.143 ±0.028 0.189 ±0.026 0.243 ±0.025 0.270 ±0.027 0.187 ±0.013

0.442 ±0.037 0.412 ±0.038 0.420 ±0.038 0.438 ±0.036 0.462 ±0.036 0.486 ±0.035 0.388 ±0.023

0.642 ±0.041 0.638 ±0.042 0.650 ±0.040 0.658 ±0.039 0.662 ±0.039 0.668 ±0.038 0.586 ±0.030

0.057 ±0.016 0.058 ±0.012 0.061 ±0.012 0.065 ±0.016 0.088 ±0.018 0.077 ±0.013 0.043 ±0.006

0.032 ±0.002 0.036 ±0.004 0.039 ±0.004 0.036 ±0.002 0.045 ±0.003 0.047 ±0.004 0.026 ±0.003

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 AIM (2-way) AIM (3-way) GEM (2-way) GEM (3-way) Private-GSD Sliced (mixed block, ours)

5.00 1.40 2.60 2.80 5.40 7.00 3.80

3.40 2.40 3.60 4.20 6.20 6.80 1.40

3.00 3.00 4.60 5.60 7.00 3.40 1.40

3.20 3.40 5.00 5.60 6.80 2.40 1.60

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.

33

Classification (n = 91)

Regression (n = 67)

Method

ε = 0.5

ε = 1.0

ε = 3.0

ε = 10.0

ε = 0.5

ε = 1.0

ε = 3.0

ε = 10.0

PrivBayes AIM (2-way) AIM (3-way) GEM (2-way) GEM (3-way) Sliced (mixed block, ours)

3.13 ±0.16 4.52 ±0.15 4.98 ±0.12 2.64 ±0.16 2.79 ±0.17 2.95 ±0.16

2.95 ±0.17 4.22 ±0.17 5.11 ±0.11 2.71 ±0.15 3.12 ±0.16 2.89 ±0.16

2.32 ±0.15 3.68 ±0.16 5.14 ±0.12 3.35 ±0.16 3.44 ±0.17 3.07 ±0.17

1.71 ±0.11 3.27 ±0.17 4.93 ±0.13 3.90 ±0.15 3.98 ±0.15 3.20 ±0.17

4.07 ±0.19 3.37 ±0.16 3.54 ±0.19 3.64 ±0.21 3.79 ±0.20 2.58 ±0.25

3.36 ±0.19 3.45 ±0.17 3.91 ±0.18 3.73 ±0.20 4.36 ±0.19 2.19 ±0.22

3.06 ±0.21 3.49 ±0.18 4.21 ±0.15 4.12 ±0.19 4.40 ±0.18 1.72 ±0.13

2.27 ±0.18 3.78 ±0.18 4.30 ±0.15 4.27 ±0.18 4.66 ±0.16 1.73 ±0.10

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 Method PrivBayes AIM (2-way) AIM (3-way) GEM (2-way) GEM (3-way) Sliced (mixed block, ours)

Regression

LogReg/Ridge

RF

XGB TabPFN LogReg/Ridge

RF

XGB TabPFN

3.02 4.24 4.92 3.15 3.13 2.53

2.56 4.08 4.81 3.31 3.41 2.84

2.71 4.03 4.80 3.19 3.36 2.90

3.04 3.96 3.96 3.91 4.10 2.03

3.18 3.97 4.03 3.94 4.06 1.82

2.85 4.14 4.92 3.16 3.10 2.83

3.27 3.43 3.70 4.16 4.33 2.10

3.40 3.34 3.76 3.75 4.43 2.31

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.

34

H

Dataset details 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. ntrain

Dataset

Task

1000-Cameras-Dataset 2dplanes 3D Estimation using RSSI of WLAN dataset 3D Estimation using RSSI of WLAN dataset c... abalone Abalone reg accelerometer ada prior airfoil self noise airlines seed 0 nrows 2000 nclasses 10 nco... Amazon employee access analcatdata supreme Another-Dataset-on-used-Fiat-500-(1538-rows) archive2 artificial-characters auction verification autoUniv-au7-1100 avocado sales bank bank8FM Bank Customer Churn Dataset banknote authentication baseball Basketball c Bias correction r Bias correction r 2 BLE RSSI dataset for Indoor localization BNG(breast-w) BNG(cmc) BNG(echoMonths) BNG(lowbwt) BNG(mv) BNG(stock) BNG(tic-tac-toe) Brazilian houses reproduced California-Housing-Classification car-evaluation Cardiovascular-Disease-dataset CDC Diabetes Health Indicators churn Click prediction small cmc combined cycle power plant compass compass reg concrete compressive strength contraceptive method choice CookbookReviews CPMP-2015-runtime-regression

regression 830 regression 32,614 regression 4,608 regression 11,520 multiclass 3,341 regression 3,341 multiclass 122,403 binary 3,649 regression 1,202 binary 1,600 binary 26,215 regression 3,241 regression 1,230 regression 914 multiclass 8,174 regression 1,634 multiclass 880 regression 14,599 binary 36,168 regression 6,553 binary 8,000 binary 1,097 multiclass 1,072 binary 1,072 regression 6,180 regression 6,180 multiclass 7,987 binary 31,492 multiclass 44,236 regression 13,996 regression 24,883 regression 62,985 regression 47,239 binary 31,492 regression 8,553 binary 16,512 multiclass 1,382 binary 56,000 binary 202,944 binary 4,000 binary 31,958 multiclass 1,178 regression 7,654 binary 13,315 regression 13,315 regression 824 multiclass 1,178 regression 14,545 regression 1,686

35

ntest num. cat. WF 208 8,154 1,152 2,880 836 836 30,601 913 301 400 6,554 811 308 229 2,044 409 220 3,650 9,043 1,639 2,000 275 268 268 1,545 1,545 1,997 7,874 11,060 3,500 6,221 15,747 11,810 7,874 2,139 4,128 346 14,000 50,736 1,000 7,990 295 1,914 3,329 3,329 206 295 3,637 422

10 10 6 12 7 7 3 6 5 3 0 7 6 11 7 6 8 11 7 8 6 4 15 11 21 21 3 9 2 5 2 7 9 0 8 8 0 5 7 16 3 2 4 8 17 8 5 7 22

0 0 0 0 1 1 1 8 0 4 7 0 0 1 0 1 4 2 9 0 4 0 1 0 0 0 0 0 7 3 7 3 0 9 0 0 21 6 14 4 0 7 0 9 0 0 4 0 1

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Table 6 continued. ntrain

ntest num. cat. WF

Dataset

Task

CPS1988 cpu act cpu small credit Credit c credit reg Customer Personality Analysis customer satisfaction in airline dabetes 130-us hospitals Data Science for Good Kiva Crowdfunding Data Science Salaries dataset sales debutanizer default of credit card clients delta ailerons delta elevators Diabetic Retinopathy Debrecen Diamonds drug consumption dry bean dataset E-CommereShippingData eeg-eye-state electricity elevators Employee estimation of obesity levels eye movements bin FICO-HELOC-cleaned fifa Firm-Teacher Clave-Direction Classification Fitness Club c Food Delivery Time FOREX audcad-day-High FOREX audcad-hour-High FOREX audchf-day-High FOREX audjpy-day-High FOREX audjpy-hour-High FOREX audsgd-hour-High FOREX audusd-hour-High FOREX cadjpy-day-High FOREX cadjpy-hour-High fried GAMETES Epistasis 2-Way 20atts 0.1H EDM-1 1 GAMETES Heterogeneity 20atts 1600 Het 0.4 ... garments worker productivity gas turbine CO and NOx emission Gender Gap in Spanish WP golf play dataset extended Goodreads-Computer-Books healthcare insurance expenses Heart-Disease-Dataset-(Comprehensive) heloc house 16H house 16H reg house 8L house sales reduced

regression 22,524 5,631 regression 6,553 1,639 regression 6,553 1,639 binary 13,371 3,343 multiclass 80,000 20,000 regression 13,371 3,343 binary 1,792 448 binary 103,904 25,976 binary 81,412 20,354 multiclass 536,964 134,241 regression 3,004 751 regression 8,590 2,148 regression 1,915 479 binary 24,000 6,000 binary 5,703 1,426 regression 7,613 1,904 binary 920 231 regression 43,152 10,788 multiclass 1,507 377 multiclass 10,888 2,723 binary 8,799 2,200 binary 11,984 2,996 binary 36,249 9,063 regression 13,279 3,320 binary 3,722 931 multiclass 1,688 423 binary 6,086 1,522 binary 7,896 1,975 regression 14,450 3,613 multiclass 8,640 2,160 binary 1,200 300 regression 36,474 9,119 binary 1,467 367 binary 35,060 8,765 binary 1,466 367 binary 1,465 367 binary 35,060 8,765 binary 35,060 8,765 binary 35,060 8,765 binary 1,467 367 binary 35,060 8,765 regression 32,614 8,154 binary 1,280 320 binary 1,280 320 regression 957 240 regression 29,386 7,347 multiclass 3,796 950 binary 876 219 regression 987 247 regression 1,070 268 regression 952 238 binary 8,000 2,000 binary 10,790 2,698 regression 18,227 4,557 regression 18,227 4,557 regression 17,290 4,323

36

2 21 12 10 17 10 22 4 8 7 1 10 7 14 5 6 16 6 12 16 6 14 7 18 3 8 20 21 5 0 3 6 10 10 10 10 10 10 10 10 10 10 0 0 8 10 13 3 5 3 11 22 16 16 8 18

4 0 0 0 5 0 2 17 12 4 4 0 0 9 0 0 3 3 0 0 4 0 1 0 5 8 0 2 0 16 3 2 0 0 0 0 0 0 0 0 0 0 20 20 5 0 0 6 0 3 0 0 0 0 0 0

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Table 6 continued. ntrain

Dataset

Task

houses housing price prediction HR Analytics Job Change of Data Scientists htru in vehicle coupon recommendation INNHotelsGroup Insurance internet firewall Intersectional-Bias-Assessment Is-this-a-good-customer JapaneseVowels jm1 jungle chess 2pcs raw endgame complete Kaggle bike sharing demand challange kc1 kdd ipums la 97-small kin8nm kr-vs-k kropt Laptop Prices Dataset law-school-admission-bianry led24 led7 letter Long MagicTelescope mammography maternal health risk mauna-loa-atmospheric-co2 mfeat-morphological MiamiHousing2016 microaggregation2 mobile c36 oversampling Mobile Phone Market in Ghana Mobile Price Classification mozilla4 mv NASA PHM2008 national-longitudinal-survey-binary National Health and Nutrition Health Survey NHANES age prediction okcupid stem online shoppers page-blocks Parkinsons Telemonitoring pc1 pendigits Performance-Prediction phoneme Physicochemical r Pima Indians Diabetes Database puma8NH Pumpkin Seeds qsar aquatic toxicity qsar fish toxicity Rain in Australia

regression 16,512 regression 436 binary 15,326 binary 14,318 binary 10,147 binary 29,020 regression 18,838 multiclass 52,425 regression 8,800 regression 1,378 multiclass 7,968 binary 8,708 multiclass 35,855 regression 8,708 binary 1,687 binary 4,150 regression 6,553 multiclass 22,444 multiclass 22,444 regression 3,552 regression 16,640 multiclass 2,560 multiclass 2,560 multiclass 16,000 regression 3,581 binary 15,216 binary 8,946 multiclass 811 regression 1,780 multiclass 1,600 regression 11,145 multiclass 16,000 binary 41,408 regression 2,880 multiclass 1,600 binary 12,436 regression 32,614 regression 36,734 binary 3,926 binary 1,822 regression 1,821 multiclass 21,341 binary 9,864 multiclass 4,378 regression 4,700 binary 887 multiclass 8,793 regression 1,072 binary 4,323 regression 36,584 binary 614 regression 6,553 binary 2,000 regression 436 regression 726 multiclass 116,368

37

ntest num. cat. WF 4,128 109 3,832 3,580 2,537 7,255 4,710 13,107 2,200 345 1,993 2,177 8,964 2,178 422 1,038 1,639 5,612 5,612 889 4,160 640 640 4,000 896 3,804 2,237 203 445 400 2,787 4,000 10,352 720 400 3,109 8,154 9,184 982 456 456 5,336 2,466 1,095 1,175 222 2,199 268 1,081 9,146 154 1,639 500 110 182 29,092

8 5 3 8 0 11 3 7 14 9 14 21 6 3 21 20 8 3 0 8 7 0 0 15 19 9 6 6 5 6 16 20 6 4 14 4 7 21 9 7 4 2 5 10 18 21 16 19 5 9 8 8 12 8 4 12

0 7 10 0 21 6 7 0 5 4 0 0 0 6 0 0 0 3 6 0 4 24 7 0 0 0 0 0 1 0 0 0 0 10 6 0 3 0 7 0 3 11 9 0 1 0 0 0 0 0 0 0 0 0 2 6

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Table 6 continued. ntrain

ntest num. cat. WF

Dataset

Task

rice cammeo and osmancik ringnorm rl SDSS17 segment seismic+bumps sensory shill-bidding Shipping Shop Customer Data shrutime shuttle Smoking and Drinking Dataset with body signal socmob space ga statlog steel industry energy consumption stock stock fardamento02 sulfur svmguide3 sylvine telco-customer-churn Telecom Churn Dataset thyroid thyroid-ann treasury twonorm vehicle VulNoneVul walking-activity wall-robot-navigation water quality Water Quality and Potability Waterstress waveform database generator waveform database generator version 1 weather izmir website phishing Wilt wind wine wine+quality wine-quality-red wine-quality-white Wine Quality red Wine Quality white yeast

binary 3,048 762 binary 5,920 1,480 binary 3,976 994 multiclass 80,000 20,000 multiclass 1,848 462 binary 2,067 517 regression 460 116 regression 5,056 1,265 regression 8,799 2,200 regression 1,600 400 regression 8,000 2,000 multiclass 46,400 11,600 binary 793,076 198,270 regression 924 232 regression 2,485 622 binary 800 200 regression 28,032 7,008 regression 760 190 regression 5,021 1,256 regression 8,064 2,017 regression 994 249 binary 4,099 1,025 binary 5,634 1,409 binary 2,666 667 multiclass 5,760 1,440 multiclass 3,017 755 regression 839 210 binary 5,920 1,480 multiclass 676 170 regression 4,553 1,139 multiclass 119,465 29,867 multiclass 4,364 1,092 binary 6,396 1,600 binary 2,620 656 regression 950 238 multiclass 3,999 1,000 multiclass 4,000 1,000 regression 1,168 293 multiclass 1,082 271 binary 3,856 965 regression 5,259 1,315 binary 2,043 511 regression 5,197 1,300 multiclass 1,279 320 multiclass 3,918 980 regression 1,279 320 regression 3,918 980 multiclass 1,187 297

38

7 20 5 8 17 14 0 3 5 4 4 9 22 1 6 7 7 9 5 6 22 20 3 14 21 21 15 20 18 16 4 24 20 8 22 21 21 9 0 5 14 4 11 4 11 11 11 8

0 0 7 4 0 4 11 0 4 2 6 0 1 4 0 13 3 0 1 0 0 0 15 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0

✓ ✓ ✓ ✓ ✓

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

I

Resource Scaling and Compute

The real-world viability of a synthetic data algorithm hinges heavily on its resource consumption alongside its statistical utility, so we document the measured wall-clock time and memory usage for each method using a standardized protocol. All benchmarks process a single task per GPU at ϵ = 1, timing the fitting and sampling phases together, with peak resident memory recorded from the operating system and peak GPU memory tracked via NVML.

10 2 10 1 760 4.3k 5.6k 17k 63k

training rows SPLICE

PrivBayes

4

peak VRAM (GB)

10 3

peak RAM (GB)

wall time (s)

Cross-method comparison. On benchmark datasets ranging from 760 to 63,000 training rows, SPLICE’s cost is nearly flat: fit plus sampling takes 20 to 60 seconds, about 2 GB of resident memory, and under 1 GB of GPU memory. The reason is simple. The release is a single O(n) pass over the data, and the fit only ever touches the Lk released moments. On this range only PrivBayes (2 to 12 seconds, CPU only) and GEM are faster. Private-GSD goes from 52 seconds to a timeout at 63,000 rows, and 3-way AIM spikes on wide datasets. All numbers are averages over three seeds.

2 0

760 4.3k 5.6k 17k 63k

training rows

AIM (2-way)

AIM (3-way)

1.5 1.0 0.5 0.0

760 4.3k 5.6k 17k 63k

GEM (2-way)

training rows

Private-GSD

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.

Per-method scaling laws. We repeat the measurement on a controlled grid built from one large mixed dataset: a row sweep from 12,500 to 400,000 rows at d = 12, and a column sweep from 6 to 24 columns at n = 50, 000. Fitting t ∝ nα cd , where α is the row exponent and c the per-column multiplier, the SPLICE variants are essentially flat in both (α ≤ 0.09, c ≤ 1.05) and finish in 30 to 120 seconds everywhere on the grid. GEM is similarly flat because it runs a fixed number of epochs. 2-way AIM grows moderately with n (α ≈ 0.55); 3-way AIM does not depend on n but pays a factor of about 1.16 per column, going from 61 seconds at 6 columns to 960 seconds at 24. PrivBayes depends on both through its parent-set search, and scales as n2.2 on wide tables. Private-GSD is the most expensive by far: 659 to 1,470 seconds across seeds at only 12,500 rows, the 2,400-second limit on two of three seeds at 25,000 rows, and a timeout beyond that even at 6 columns. So, among the methods we test, only the SPLICE variants are both accurate on continuous features and insensitive to growth in either n or d. Compute. All experiments ran on a single server with two AMD EPYC 9354 processors (64 cores, 128 threads), 512 GB of RAM, and six NVIDIA RTX PRO 6000 Blackwell GPUs with 96 GB of memory each. Every generation task fits comfortably on one GPU; the resource measurements of Section I run one task 39

wall time (s)

10 3

10 3

10 2

10 2

10 1

10 1 10 5 training rows (d = 12)

SPLICE

PrivBayes

10 AIM (2-way)

AIM (3-way)

20 15 columns (n = 50; 000) GEM (2-way)

Private-GSD

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. at a time per GPU, while the sweeps schedule independent tasks across GPUs in parallel. SPLICE itself is light: a single fit-plus-sample cell takes 20 to 120 seconds and under 1 GB of GPU memory, so its full 16,800-cell sweep totals roughly 200 GPU-hours and would run on one consumer-grade GPU in about a week. The overall benchmark cost is dominated by the baselines.

40

Related documents

• Differentially Private Paired Table-Image Multimodal Synthesis#820723
• Optimal Cox regression under federated differential privacy: coefficients and cumulative hazards#1389099
• Convergence rates of randomly pivoted methods for low-rank approximation#973874
• Autoregressive latent diffusion for 3D molecule generation#1187484
• Reliable Hybrid Neural Surrogates for Multidimensional Grids: Application to Double Parton Distributions#1149467