arXiv cs.CY· Lucas Rosenblatt, R. Teal Witter, Christopher Musco·· 11 小时前AI 评分31
SPLICE：基于切片 Chebyshev 矩的差分隐私合成数据算法
Differentially Private Synthetic Data from Sliced Chebyshev Moments
AI 导读
新差分隐私合成数据算法 SPLICE 通过测量带噪切片 Chebyshev 多项式矩并拟合分布，在常数隐私参数下返回与目标分布的 Sliced Wasserstein-1 距离为 Õ(1/√n) 的私有分布，且该界与数据维度 d 无关。
正文 · 原文
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 $\tilde{O}(1/\sqrt{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/\alpha)$ Chebyshev moments along $\tilde{O}(d/\alpha^2)$ random directions guarantees $\alpha$ 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.
| Subjects: | Machine Learning (cs.LG); Computers and Society (cs.CY); Data Structures and Algorithms (cs.DS) |
| MSC classes: | 68P27, 68T05 (Primary), 49Q22, 41A10, 60E15, 62G05 (Secondary) |
| ACM classes: | G.3; I.2.6; G.1.2; K.4.1 |
| Cite as: | arXiv:2610.42081 [cs.LG] |
| (or arXiv:2610.42081v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.42081 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Lucas Rosenblatt [view email]
[v1]
Fri, 30 Oct 2026 17:34:58 UTC (243 KB)
来源：arXiv cs.CY · arxiv.org