Source-linked AI summary
Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures
Yiyun He
TL;DR
Private synthetic measures are intended to support reusable analyses, but worst-case Wasserstein accuracy faces a curse of dimensionality. The paper uses adaptive PrivTree partitions and private leaf-mass release; its guarantees relate error to ambient or finite-scale intrinsic dimension.
Problem
Worst-case Wasserstein error on [0,1]^d has an n^-1/d rate, whose slow convergence creates a high-dimensional accuracy barrier.
Source: §1 · p. 2Method
The paper applies PrivTree to build an adaptive partition, privately releases its leaf masses, and analyzes resolution and data-dependent privacy costs.
Source: §1.1 · p. 2Results
For arbitrary data, the exponent 1/d matches the minimax lower bound, while the intrinsic-dimension exponent 1/s matches it up to logarithms for fixed ε.
Source: §1.1 · p. 3Takeaways & Limitations
Adaptive partitions are the paper’s main contribution for capturing low-dimensional data structure in a worst-case setting without an i.i.d. population assumption.
Source: §1.1 · p. 3The tree-size lemma is an expectation bound, not a guarantee for every realized tree, because empty-cell false-positive subtrees lack deterministic size bounds.
Source: §5.3 · p. 22
Abstract
from arXiv · showhide
We study an $\varepsilon$-differentially private synthetic measure for $n$ points in $[0,1]^d$ by applying the existing PrivTree algorithm to construct an adaptive binary partition and then privately releasing its leaf masses. We consider the worst-case data model without any sampling or population-distribution assumption. The 1-Wasserstein error of the synthetic measure is $\widetilde O_d((\varepsilon n)^{-1/d})$ for $d\ge2$, which is optimal compared to the minimax lower bound up to a logarithmic factor. Moreover, for $d\ge3$ and $2<s\le d$, if the data set has covering number at most $Ar^{-s}$ over the relevant finite range of scales $r$, the expected error improves to $\widetilde O_{d,s}((\varepsilon n)^{-1/s})$. Thus the rate depends on a finite-scale intrinsic dimension rather than the ambient dimension, without requiring the recovery of a low-dimensional manifold. We also introduce a shifting technique to further avoid the exponential dependence of the constant on the ambient dimension $d$.
1 Introduction
The introduction motivates private synthetic measures as reusable outputs while identifying worst-case Wasserstein accuracy and high-dimensional rates as central challenges. It presents adaptive partitions and geometry-sensitive analysis as a way to capture low-dimensional data structure.
1 Introduction
- Private synthetic data can be released once and reused across analyses without further privacy loss from postprocessing.The introduction contrasts this with task-specific private algorithms, where multiple uses of real data usually require a larger privacy budget.Source: §1 · p. 1
- Wasserstein error controls differences in expectations of every 1-Lipschitz statistic, but its n^-1/d rate reflects a curse of dimensionality.The introduction motivates replacing ambient dimension with intrinsic dimension to improve rates without restricting the query class.Source: §1 · p. 2
1.1 Main results
- PrivTree refines cells with large biased noisy masses, and the construction then privately releases leaf masses and reconstructs a probability measure.The adaptive hierarchy uses a noise scale independent of depth; the error analysis separates leaf-aggregation resolution from leaf-mass perturbation.Source: §1.1 · p. 2, §1 · p. 2
- The analysis combines a terminal-cell resolution functional with a data-dependent Laplacian complexity bound that has order m^-1/s for intrinsic dimension s > 2.The resolution functional sums each terminal cell’s mass times its scale, bounding the cost of aggregating leaves to representative points, especially for unbalanced trees.Source: §1.1 · p. 2
- The covering-number bound need only hold down to r = (A/(εn))^(1/s), rather than at arbitrarily small scales.A natural cutoff is where the covering number reaches the effective private sample size, N(X, r*) ≍ εn.Source: §1.1 · p. 3
- For arbitrary data, the exponent 1/d matches the minimax lower bound, while the intrinsic-dimension exponent 1/s matches it up to logarithms for fixed ε.The authors identify capturing low-dimensional structure with adaptive partitions as the main contribution; [22] already achieves the ambient exponent without the logarithmic factor.Source: §1.1 · p. 3
2 Preliminaries
The preliminaries define Wasserstein error and differential privacy, then introduce the binary partition and finite-scale intrinsic-dimension framework used in the paper. The framework allows growth bounds only down to a specified resolution, while fixed-grid conversion can incur an exponential-in-d factor.
2.1 Wasserstein distance and empirical measures
- Wasserstein-1 is the minimum transport cost between measures and, by Kantorovich–Rubinstein duality, controls integration error over 1-Lipschitz functions.This connects the paper’s error measure to differences in Lipschitz statistics.Source: §2.1 · p. 4
2.2 Differential privacy
- Differential privacy requires output distributions to change little between data sets differing by one point; adaptive composition adds the privacy parameters of successive mechanisms.The paper uses this principle for a private tree release followed by private leaf-mass release.Source: §2.2 · pp. 4–5
2.3 Binary partition tree
- A partition tree’s resolution functional averages the geometric scale of each point’s terminal cell and bounds the cost of aggregating that cell to a representative.The tree is a finite subtree of the cyclic binary partition, whose coordinates are bisected in turn.Source: §2.3 · p. 5
2.4 Intrinsic dimensions
- The intrinsic-dimension assumption requires occupied-cell growth to hold only to a finite cutoff, but converting covering numbers to fixed-grid occupancy can lose a factor exponential in d.A public random shift is introduced later to reduce this covering-to-occupancy loss to a polynomial factor for fixed intrinsic dimension.Source: §2.4 · pp. 6–7
3 Aggregation algorithms and Laplacian complexity
Private aggregation releases noisy leaf masses over a partition tree, with Wasserstein error split into resolution and privacy-noise terms. A data-dependent Laplacian-complexity analysis replaces ambient-dimension dependence with intrinsic-dimension dependence when s>2.
3 Aggregation algorithms and Laplacian complexity
- The expected Wasserstein error separates into resolution error from leaf aggregation and privacy error from noisy leaf masses.The resolution term depends on the tree; the privacy term is analyzed through Laplacian complexity.Source: §3 · p. 8
3.1 Laplacian complexity
- For a fixed tree, the private leaf-mass mechanism is ε-differentially private, and its expected error is bounded using the Laplacian complexity of leaf representatives.The leaf-mass vector has ℓ1 sensitivity 1/n, and the projection step is post-processing.Source: §3.1 · p. 8
3.2 Dimension dependence in Laplacian complexity
- For data sets concentrated near a lower-dimensional set, a data-dependent bound on Laplacian complexity can exploit that structure and improve the O(m^-1/d) dependence of the previous bound.The last bound in Equation (12) uses worst-case complexity Lm(F) and does not use the geometry of the particular data set.Source: §3.2 · p. 9
- The intrinsic-dimension rate saturates at the parametric m^-1/2 scale below dimension 2, while approximately uniform full-dimensional grids recover the ambient rate.More concentrated or uneven data can have smaller effective occupancy and a better bound.Source: §3.2 · p. 12
4 Warm-up: Adaptive binary partition
The warm-up studies deterministic adaptive binary partitions, which refine cells according to their mass. It explains a termination condition for empirical data and derives intrinsic-dimensional resolution bounds from the distribution of stopping depths.
4.1 Naive adaptive binary partition
- A mass-threshold partition bisects cells whose mass exceeds θ, but smaller thresholds increase the number of pieces and can prevent termination.The warm-up considers this deterministic construction before the private partition algorithms.Source: §4.1 · pp. 12–13, §4 · p. 12
- For an empirical measure with no point appearing more than c times, the partition terminates at θ=c/n because sufficiently deep cells contain at most one distinct point and then have mass at most θ.The terminal-cell condition prevents further splitting.Source: §4.1 · pp. 12–13
4.2 Intrinsic-dimensional bounds
- The resolution analysis uses the stopping-depth distribution, retaining how mass is distributed across cells rather than only an occupied-cell bound.The exact distribution-based value is generally sharper than the occupied-cell bound.Source: §4.2 · p. 13
- The intrinsic-dimensional corollary requires the growth assumption only to the cutoff R=θ^-1 and states a bound under Aθ<1 and 0<s≤d.For empirical data, the example sets θ=c/n and applies the corollary when the finite-scale assumption holds.Source: §4.2 · pp. 14–15
5 Partition with soft thresholds
This section develops PrivTree’s depth-dependent soft-threshold partition and analyzes its termination and Wasserstein accuracy. It also states an intrinsic-dimensional accuracy result under finite-scale covering assumptions, combining resolution and leaf-mass error bounds.
5 Partition with soft thresholds
- A cell is split when its mass exceeds a threshold that increases with depth, yielding an adaptive partition that terminates even for measures with atoms.The deterministic partition is the skeleton for PrivTree’s later noisy split decisions.Source: §5 · p. 15, §5.1 · p. 15
5.1 Termination, size, and Wasserstein error
- The deterministic soft-threshold tree has bounded depth and finite size, with a Wasserstein resolution error whose cost is only a logarithmic factor multiplying δ.For empirical measures, the stated corollary also bounds the number of leaves by Cn log n.Source: §5.1 · pp. 15–16
5.2 Accuracy of the PrivTree partition
- PrivTree’s noisy split decisions terminate almost surely, and the resulting private synthetic measure is ε-differentially private with a Wasserstein error guarantee.The resolution analysis accounts for split-decision noise, and the final guarantee also includes the private leaf-mass release.Source: §5.2 · pp. 18–20
5.3 Intrinsic dimension dependence of PrivTree
- For d ≥ 3 and 2 < s ≤ d, the subsection combines intrinsic-dimensional partition and data-dependent Laplacian complexity bounds to deduce a 1-Wasserstein error of order (εn)−1/s up to logarithmic factors.The leaf-representative lemma is an expectation bound, not a bound for every realized tree; empty-cell false-positive splits can yield finite almost-sure trees with no deterministic size bound.Source: §5.3 · pp. 21–22
- Under Theorem 5.7’s assumptions, Theorem 5.9 adds d ≥ 3, 2 < s ≤ d, 1 ≤ A < εn, and Assumption 2.6 for µn with R = εn.The supplied passage identifies the result as PrivTree with intrinsic-dimensional accuracy but does not include its concluding bound.Source: §5.3 · p. 22
- The proof combines a resolution-error bound with leaf-mass error control and applies the triangle inequality to obtain Equation (39).The resolution analysis uses a scale split, while the leaf-mass analysis conditions on the tree and uses privacy budget ε/2.Source: §5.3 · p. 23
6 Randomly shifted partitions
A public random shift reduces the grid-alignment penalty in PrivTree’s covering-number analysis. The resulting intrinsic-dimensional guarantee applies under stated dimension and scale conditions, while the shift improves the fixed-grid comparison when intrinsic dimension is small relative to ambient dimension.
6 Randomly shifted partitions
- A sufficiently small central cluster can have intrinsic dimension s = 0 yet occupy 2^d cells in the fixed grid, motivating the public shift.For this example, the covering-number factor A is 2^d.Source: §6 · p. 24
- The algorithm translates data by a public uniform shift, discards cells disjoint from the translated window, privately processes active leaves, then translates the output back.Representatives are chosen inside the translated window so they return to the original domain after translation.Source: §6 · p. 24
- The shifted-grid occupancy lemma supplies the geometric basis for averaging the covering profile over shifts in the private intrinsic-dimensional bound.The proof covers the data set with balls and averages how many shifted cells each ball meets.Source: §6 · pp. 24–25
- Under Algorithm 6, for 0 < ε ≤ 1, εn > 2, d ≥ 3, 2 < s ≤ d, and 1 ≤ A < εn, expected support size is at most Cεn; the output is ε-differentially private.The expectation is over the public shift and noise used in split decisions and leaf-mass release.Source: §6 · p. 25
- The random shift replaces the fixed-grid factor 2^(d/s) in the Wasserstein bound with d, though the fixed grid can be sharper when s is comparable to d.The improvement is exponential-to-polynomial in d when s is small relative to d.Source: §6 · p. 26
A Capped adaptive binary partition
The capped adaptive partition stops after a prescribed number of leaves while retaining a Wasserstein-rate guarantee. Its breadth-first splitting rule prioritizes the shallowest leaves whose mass exceeds the threshold.
A Capped adaptive binary partition
- The breadth-first rule splits a minimum-depth leaf among those whose mass exceeds θ, and the queue enforces this ordering.The cap is reached after at most O(n) splits in the typical setting described.Source: A Capped adaptive binary partition · p. 26
- The capped partition preserves the Wasserstein rate, and with θ = c/n and M = ⌈Cn⌉ its stated specialization applies for constants independent of n.Each split adds one leaf, so the algorithm terminates after at most M − 1 splits.Source: A Capped adaptive binary partition · p. 26
- At the cap, all heavy leaves have depth h or h + 1, which bounds the tree depth and supports the error analysis.Here h is the minimum depth among heavy leaves; the argument uses nondecreasing split depths under the breadth-first rule.Source: A Capped adaptive binary partition · p. 27
B Linear-programming form of the PSMM projection
The PSMM projection can be written as a linear program over leaf values, constrained by pairwise representative distances and a bounded range. Linear-programming duality yields the equivalent form used in the paper.
B Linear-programming form of the PSMM projection
- The projection is equivalently a linear program in the leaf values, with pairwise Lipschitz constraints and bounds −D ≤ f_Qi ≤ D.The pairwise constraints use the Euclidean distances between leaf representatives.Source: B Linear-programming form of the PSMM… · p. 27
- Linear-programming duality gives the equivalent formulation, identified as the Euclidean-metric version of [22, Algorithm 2 and Proposition 6].The feasible set is symmetric, so taking the absolute value does not change the maximum.Source: B Linear-programming form of the PSMM… · p. 27