CS Paper Radar

Understanding Private Evolution as Learning-Augmented Clustering

Audra McMillan, Kunal Talwar, Felix Zhou

cs.LG cs.CRstat.ML ·submitted 2026-09-29 04:17 UTC · v1
top venue

Abstract

Private Evolution (PE) is a differentially private algorithm for synthetic data generation. While it can be viewed as a Wasserstein learning algorithm, it performs much better in practice than worst-case Wasserstein analyses would predict. We recast PE as generative model-augmented Wasserstein learning. We show theoretically that when we take into account the use of a generative model that is able to capture something about the true distribution, then we can obtain much better performance bounds. For example, if the generator gives samples in the same low-dimensional space as the distribution, then sample complexity depends on intrinsic, not ambient, dimension. We also show that standard variants of PE can fail to converge on simple well-clustered instances, and propose a new geometry-aware version of PE with provable convergence on such instances. Experimentally, we show that our new algorithm is competitive with standard baselines and can improve recall.

Comment
to be published in NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy

cs.CR stat.MLcs.DScs.IT+1 ·2026-10-15 ·Mohammad Afzali, Hassan Ashtiani, Sivan Sabato
theory similarity 0.67
Abstract

We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].

0.16

Regularized Wasserstein Distance for Discrete Generative Modeling and Clustering Analysis

cs.CV cs.LG ·2026-10-31 ·Senmao Ye, Fei Liu, Dawei Zhang, Yuqian Zheng, Jun Zhang +1 more
code/data similarity 0.67
Abstract

In this paper, we formulate clustering analysis as discrete generative modeling. Specifically, when the generator is restricted to a finite candidate space, the generated samples naturally emerge as the most representative prototypes of the underlying data distribution. To model such a discrete candidate space, we employ a Discrete Distribution Network (DDN). However, DDN suffers from unstable training due to its hard nearest-neighbor selection. To stabilize training and encourage geometric consistency, we replace DDN's l2 loss between images with regularized Wasserstein distance between the empirical distributions of real and generated images. The resulting framework, termed Discrete Generative Clustering (DGC), offers four notable advantages: 1) the learned cluster centers are directly interpretable, as they are realistic synthetic samples; 2) the inference cost scales logarithmically with the number of clusters, i.e., O(log K), making the method scalable to extremely large K; 3) the regularized Wasserstein distance provides a smooth and well-behaved optimization objective that facilitates stable convergence, whereas DDN's l2 loss tends to converge to poor local optima; and 4) DGC replaces DDN's nearest-neighbor selection with random-neighbor selection, which avoids the density shift problem during multi-step forward. Extensive experiments on several benchmarks demonstrate the effectiveness and desirable properties of DGC. The code is publicly available at GitHub.

0.32

Geometry-Adaptive Mechanisms for Private Synthetic Data

cs.DS cs.CRcs.LG ·2026-09-27 ·Raoof Zare Moayedi, Amir R. Asadi, Mohammad Hossein Yassaee, Gholamali Aminian
theory similarity 0.67
Abstract · 43 pages, including appendices

Generating differentially private synthetic data with meaningful Wasserstein utility guarantees is challenging in high dimensions. For datasets of size \(n\) on $[0,1]^d$ with $d\ge2$, existing pure \(\varepsilon\)-differentially private mechanisms achieve expected $1$-Wasserstein error of order $(\varepsilon n)^{-1/d}$, reflecting the curse of dimensionality. While this rate is optimal in the worst case, it can be overly pessimistic when the data are supported on a lower-dimensional set. We formalize this through a multiscale packing-growth dimension $k$, which captures the geometric complexity of the support via the growth of packing numbers across scales. We propose \emph{Adaptive Pruned-PMM}, a pure $\varepsilon$-differentially private mechanism that combines private depth selection with our pruned variant of the Private Measure Mechanism (PMM) of He et al.\ (2023). The mechanism supports deeper, geometry-adapted hierarchies with expected running time $O\!\left(d(n+d)\log(\varepsilon n)\right)$, which is near-linear in $n$ for fixed dimension and privacy budget. Under an external multiscale packing-growth condition with dimension $k$, we show that, for fixed positive privacy budgets and fixed geometry, the expected $1$-Wasserstein error is of order $(\varepsilon n)^{-1/k}$ for $k>1$ as $n$ grows. We also prove a lower bound under a corresponding internal packing-growth condition, showing that the exponent $1/k$ is sharp within this framework.

0.08

Membership Inference Attack on Private Evolution

cs.CR ·2026-10-21 ·Daniil Filienko, Sikha Pentyala, Martine De Cock
published similarity 0.67
Abstract · Accepted at InfPriv Workshop at NeurIPS 2026

Synthetic Data Generation (SDG) is an actively studied way to enable safe sharing of private data more broadly. Inference-only SDG methods, such as Private Evolution (PE), are particularly appealing, as they can leverage black-box access to pre-trained foundation models to generate high quality data without the need for model fine-tuning on the private data. PE is explicitly designed to produce synthetic data under Differential Privacy (DP). Yet formal DP guarantees do not eliminate the need for empirical privacy auditing of the practical susceptibility of released synthetic data to adversarial attacks. In this work, we introduce the first white-box Membership Inference Attack (MIA) tailored to the voting-based algorithm underlying the PE framework. By exploiting how the iterative filtering process biases the survival and proximity of synthetic candidates toward private instances, our attack achieves empirical performance indicating private data leakage in the PE applications across image, text, and tabular modalities.

0.31

Differentially Private Synthetic Data from Sliced Chebyshev Moments

cs.LG cs.CYcs.DS ·2026-10-30 ·Lucas Rosenblatt, R. Teal Witter, Christopher Musco
benchmarktheory similarity 0.66
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/α)$ Chebyshev moments along $\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.

0.09

Differentially Private Synthetic Data via Generalized Moment Matching

cs.IT stat.MLcs.LGmath.PR+1 ·2026-10-21 ·Rundong Ding, Yiyun He, Yizhe Zhu
theory similarity 0.64
Abstract · 53 pages

We study $(\varepsilon,δ)$-differentially private synthetic data for arbitrary databases of $n$ records in $[-1,1]^d$ under a specified integral probability metric (IPM). We introduce generalized moment matching, which estimates moments privately, fits a probability measure, and samples synthetic records. A general error theorem applies when moment error controls the target IPM. This framework extends Chebyshev moment matching for $1$-Wasserstein distance and smooth queries. We apply the framework to maximum mean discrepancy with Matern and Laplace kernels and a two-layer ReLU neural tangent kernel. We also obtain guarantees for sliced Wasserstein-$1$ and the IPM induced by norm-bounded ReLU networks. With sufficiently many synthetic records,these rates are minimax optimal up to logarithmic factors for fixed dimension.

0.29

Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures

cs.DS cs.CRcs.ITmath.PR ·2026-09-15 ·Yiyun He
theory similarity 0.63
Abstract · 30 pages

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

0.23

Differentially Private Score Estimation with Applications to Score-Based Generative Models

cs.LG stat.MLmath.STstat.ME ·2026-11-19 ·Mengxiao Gao, Elly K. H. Hung, Yuchen Wu, Yi Yu
theory similarity 0.63
Abstract · 57 pages, 18 figures

Estimating the score function of a distribution plays a central role in statistics and machine learning, with applications in distribution estimation, sampling, and score-based generative modeling. However, learning scores from sensitive data raises privacy concerns. These concerns are particularly pronounced in score-based generative modeling, where trained models may memorize individual training examples and expose sensitive information through membership inference and data extraction attacks. Although non-private score estimation has been extensively studied, the statistical limits of its private counterpart remain less understood. In this work, we study score estimation under $(α,β)$-differential privacy for $d$-dimensional sub-Gaussian distributions with locally $γ$-Hölder-continuous scores. We develop a sampling-based private score estimator using quadratic B-splines and the exponential mechanism, and we implement our proposal through projected Langevin Monte Carlo with runtime polynomial in the sample size $n$. The proposed estimator satisfies $(α,β)$-differential privacy, and achieves expected density-weighted squared error $\mbox{polylog}(n) \max(n^{-2γ/(d+2γ+2)},\,(nα)^{-2γ/(d+γ+1)})$. We also establish a nearly matching private minimax lower bound, thereby characterizing the privacy-accuracy trade-off for score estimation. As an application, we construct a differentially private diffusion model whose privacy guarantee is independent of the number of denoising steps. We show that, with an appropriate discretization scheme, the resulting diffusion model attains nearly minimax optimal expected total variation error among all private distribution estimators. We validate our theoretical findings through experiments on both synthetic and real-world datasets.

0.08