cs.LGOct 30, 2026

Differentially Private Synthetic Data from Sliced Chebyshev Moments

Authors: Lucas Rosenblatt, R. Teal Witter, Christopher Musco

Organizations: Department of Computer Science, Williams College · Department of Mathematical Sciences, Claremont McKenna College · Department of Computer Science and Engineering, New York University

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, dd. 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 nn examples, SPLICE returns a private distribution with Sliced Wasserstein-1 distance O~(1/n)\tilde{O}(1/\sqrt{n}) from the target, for constant privacy parameters. Notably, this bound is independent of the data dimension, dd. Along the way, we prove a moment matching result of independent interest: for a distribution on the unit ball, matching the first O(1/α)O(1/α) Chebyshev moments along O~(d/α2)\tilde{O}(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.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Differentially Private Synthetic Data via Generalized Moment Matching

    Oct 21, 2026Rundong Ding, Yiyun He, Yizhe ZhuDifferentially Private Synthetic Data GenerationDifferential Privacy

  2. Differentially Private Synthetic Data via APIs 4: Tabular Data

    Jun 6, 2026Toan Tran, Arturs Backurs, Zinan Lin +3Synthetic Data GenerationSynthetic Tabular Data Generation