Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures

A PrivTree-based ε-differentially private synthetic measure achieves minimax-optimal 1-Wasserstein error in ambient dimension, with improved rates governed by a finite-scale intrinsic dimension.

Yiyun He· 2026· DOI 10.48550/arXiv.2609.17624

The core problem

The paper studies the problem of releasing a synthetic measure that approximates an arbitrary dataset of n points in the unit cube [0, 1]^{d} while satisfying ε -differential privacy. The central object is a synthetic measure \overset{μ}{^} whose 1-Wasserstein distance to the empirical measure μ_{n} = \frac{1}{n} i = 1 \sum n δ_{x_{i}} is small in expectation. The author adopts a worst-case data model: no sampling assumption, no population distribution, and no low-dimensional manifold structure is presumed. This is a departure from much of the private synthetic data literature, which often assumes i.i.d. sampling from a distribution or a low-dimensional structure that must be recovered. The main question is whether one can obtain minimax-optimal Wasserstein rates in this fully adversarial setting, and whether the ambient dimension d can be replaced by a smaller, data-dependent intrinsic dimension. The paper answers both questions affirmatively. The construction is simple: apply the existing PrivTree algorithm to build an adaptive binary partition of the cube, then privately release the mass of each leaf. The analysis is the main contribution, establishing upper bound

Innovation

The paper establishes three main results. First, for any d \geq 2 and any dataset of n points in [0, 1]^{d}, the expected 1-Wasserstein error of the synthetic measure satisfies E [W_{1} (\overset{μ}{^}, μ_{n})] = O_{d} ((ε n)^{- 1/ d}), where the notation O_{d} hides polylogarithmic factors in n and ε and constants depending on d . This matches the known minimax lower bound Ω ((ε n)^{- 1/ d}) up to logarithmic factors, showing that the construction is optimal in the worst-case data model. Second, for d \geq 3 and 2 < s \leq d, if the dataset has covering number at most A r^{- s} over the relevant finite range of scales r, then the expected error improves to E [W_{1} (\overset{μ}{^}, μ_{n})] = O_{d, s} ((ε n)^{- 1/ s}) . Thus the rate depends on the finite-scale intrinsic dimension s rather than the ambient dimension d, without requiring the recovery of a low-dimensional manifold. The covering-number condition is a mild, data-dependent assumption that can hold even for sets that are not manifolds. Third, the author introduces a shi

The paper studies the problem of releasing a synthetic measure that approximates an arbitrary dataset of n points in the unit cube [0, 1]^{d} while satisfying ε -differential privacy. The central object is a synthetic measure \overset{μ}{^} whose 1-Wasserstein distance to the empirical measure μ_{n} = \frac{1}{n} i = 1 \sum n δ_{x_{i}} is small in expectation. The author adopts a worst-case data model: no sampling assumption, no population distribution, and no low-dimensional manifold structure is presumed. This is a departure from much of the private synthetic data literature, which often assumes i.i.d. sampling from a distribution or a low-dimensional structure that must be recovered. The main question is whether one can obtain minimax-optimal Wasserstein rates in this fully adversarial setting, and whether the ambient dimension d can be replaced by a smaller, data-dependent intrinsic dimension. The paper answers both questions affirmatively. The construction is simple: apply the existing PrivTree algorithm to build an adaptive binary partition of the cube, then privately release the mass of each leaf. The analysis is the main contribution, establishing upper bounds that match known lower bounds up to logarithmic factors and extending them to a finite-scale intrinsic dimension regime.

The mechanism is a two-stage procedure. First, PrivTree (a differentially private hierarchical partitioning algorithm) is run on the dataset to produce an adaptive binary partition P of [0, 1]^{d} . PrivTree recursively splits cells when the number of points in a cell exceeds a threshold that depends on the privacy parameter ε and the depth, thereby concentrating resolution where the data is dense. Second, the leaf masses are released privately. For each leaf L \in P, the count n_{L} = i = 1 \sum n 1 {x_{i} \in L} is computed and perturbed with Laplace noise to obtain \tilde{n}_{L}, and the synthetic measure is defined as

Why it matters

The results place the proposed mechanism at the frontier of private synthetic data generation. The minimax-optimal rate (ε n)^{- 1/ d} for d \geq 2 is a strong guarantee in the worst-case model, and the improvement to (ε n)^{- 1/ s} under a finite-scale intrinsic dimension condition is particularly appealing because it does not require estimating or recovering a manifold. The covering-number condition is weaker than assuming a manifold: it only requires that the data can be covered by a certain number of balls at each scale, which is a common notion in metric geometry and can be verified empirically. The shifting technique is a technical contribution that may be of independent interest for other partition-based private algorithms. One limitation is that the results are stated for the 1-Wasserstein distance; extensions to p -Wasserstein distances for p > 1 are not addressed. Another is that the constants in the O notation may depend on d and s in ways that are not fully explicit, although the shifting technique mitigates the exponential dependence on d . The paper does not provide an empirical evaluation, so the practical performance of the mechanism on real datasets remains to be studied. Nevertheless, the theoretical guarantees are a significant step toward understanding the fundamental limits of private synthetic data in high dimensions, and they suggest that intrinsic dimension can be exploited without explicit manifold recovery. The work also connects to the broader literature on private measures and optimal transport, and it may inspire further research on adaptive partitioning schemes that automatically adapt to the intrinsic dimension of the data.

Who should read this

CS practitioners and researchers

Opening member content…