acceptodds
Under review as a conference paper at ICLR 2027

Zero-Cost Denoising for Optimizing Differentially Private Synthetic Data Generation

Abstract

Private Evolution (PE) is a leading API-only framework for differentially private (DP) synthetic text. Each PE iteration spends privacy budget on a noisy nearest-neighbor vote histogram used to select synthetic candidates. We show that this histogram is under-utilized and can be denoised without additional privacy loss under the public- PE framework: the denoiser is DP post-processing of the noisy histogram, the synthetic candidate graph, and the public vote sum constraints. Our estimator, GRE, solves one convex program that combines the sum-to- simplex constraint with Laplacian smoothness on the candidate kNN graph. The two terms are complementary: the simplex constraint preserves the known total but ignores geometry, while the graph penalty uses geometry but does not enforce the histogram constraints. Empirically, histogram error minimization, one-shot ranking accuracy maximization, and closed-loop PE generation quality are not strictly connected. We therefore tune by a degrees-of-freedom rule calibrated to closed-loop synthetic data generation behavior. Our experiments on domain-mismatched text corpora including AG News and DBpedia, graph-regularized histogram-constrained denoising improve top- PE quality at tight privacy budgets.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
privacy, synthetic data generation, differential privacy

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_UkdPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the selection step of Private Evolution (PE) for differentially private synthetic text. Each PE iteration releases a noisy nearest-neighbor vote histogram over synthetic candidates, which existing pipelines clip at zero and then rank. The authors propose GRE, a convex estimator that projects the noisy histogram onto the sum-to-N simplex while adding Laplacian smoothness over a kNN graph of candidate embeddings. Because GRE depends only on the released histogram, the candidate graph, and the public total N, it is presented as DP post-processing with no additional privacy cost. The smoothing strength is chosen by matching the smoother's effective degrees of freedom to the support size of the simplex projection. Experiments include a controlled histogram-recovery benchmark, end-to-end PE runs on AG News and DBpedia with Qwen3-32B generation evaluated by MAUVE, and an ablation over the smoothing rule.

Critical strengths
  1. The privacy closure conditions are clearly stated. GRE operates only on the released DP histogram, the synthetic candidates, and the public total N. The candidate graph is built from earlier DP outputs, and the choice of λ\lambda uses only σ\sigma, the graph, and the noisy histogram, so the method makes no additional query to the private data (Proposition 1, Appendix A). This is what makes GRE compatible with PE-family pipelines without changing their privacy accounting.
  2. The method is easy to plug in, and the ablations are meaningful. The comparison of clipping, simplex projection, graph-only smoothing, and the joint estimator keeps the generator, voting, noise, and budget split fixed, so the differences can be attributed to the selection step (Algorithm 1, Table 1). At ρ=0.010\rho=0.010, GRE reduces normalized MSE from 2.629 (clipping) and 0.975 (simplex projection) to 0.484, and on AG News it improves MAUVE in 17 of 20 budget-seed configurations (Figure 2).
  3. Negative results are reported explicitly. The paper shows that GRE degrades DBpedia and gives no additional final-iterate gain under a better initialization, and it relates these outcomes to smoothing bias (pages 8-9). This is scientifically more informative than reporting only favorable cases.
Critical weaknesses
  1. End-to-end applicability lacks an actionable criterion. GRE improves average MAUVE at all four budgets on AG News, but on DBpedia it is below AugPE at all four budgets. Reading Figure 2, the drop is about 0.13 at ρ=0.0467\rho=0.0467 and ρ=0.169\rho=0.169, which is comparable to the largest AG News gain of 0.084. The composition with a better initialization also shows no final gain (Section 6). The evidence therefore supports a specific high-noise, weak-initialization regime rather than a general upgrade to PE, and describing the DBpedia result as a slight decrease understates it. Reporting the negative case is valuable, but practitioners need a rule, computed only from DP outputs, for deciding whether to enable, weaken, or skip GRE. Without one, they cannot tell when the method will hurt.
  2. The diagnostic P is not a free online indicator. P in Eq. (3) uses the spectral coefficients cj=uj⊤hc_j=u_j^\top h of the clean, un-noised private histogram hh. It can explain results in a research evaluation, but it cannot be computed from the candidate graph and DP outputs alone. This contradicts the description of P as "a budget-free indicator" (Section 4.3) and the claim that Proposition 3 predicted the DBpedia failure. Using P in deployment would require extra privacy budget or an estimate from h~\tilde h, whose coefficients c~j2\tilde c_j^2 are biased upward by about σ2\sigma^2, precisely in the noise-dominated modes that P is meant to detect. This does not invalidate the post-processing guarantee of GRE, because the default λ\lambda rule does not use hh, but it limits the usability of the proposed diagnostic.
  3. The default degrees-of-freedom rule lacks independent support. Matching df(λ)\mathrm{df}(\lambda) to r^\hat r is intuitive, but no argument connects this choice to the closed-loop optimum. The rule was selected from four scalings by closed-loop MAUVE on AG News at ρ=0.0035\rho=0.0035 with three seeds (Table 2), the same setting that yields the headline gain, so the claim of "no tuned constants" is too strong. Theorem 1 only shows that an unconstrained linear smoother reduces MSE for sufficiently small λ\lambda; it does not cover the simplex-constrained estimator, ranking, or multi-round generation. The Lean development mainly checks this derivative identity and should not be read as verifying the full algorithm (Appendix B). Validating the rule on held-out datasets or budgets would make it more convincing.
  4. The added value of the joint constraint and its total cost are not fully established. In Table 1, graph-only denoising achieves slightly higher top-k Jaccard than GRE at every listed budget, and simplex projection achieves lower MSE at ρ≥0.2\rho\ge0.2, so the two structures are not uniformly complementary. Simplex projection alone, the closest prior method, is also absent from the end-to-end comparison in Figure 2, which leaves untested the statement that the gain comes from coupling the graph with the simplex constraint rather than from either alone. Building the kNN graph, estimating the degrees of freedom, and running FISTA add computation, but no wall-clock cost is reported. "Zero-cost" refers to the privacy budget, so this is not an error in the title, but a practical plug-in should report runtime and scalability to larger candidate pools.
Questions for authors

Questions that could affect my assessment:

  1. Could you add simplex projection alone to the end-to-end comparison in Figure 2, so that the contribution of coupling the two structures can be isolated?
  2. How would a practitioner decide whether to enable GRE without access to the clean histogram? Could you propose a rule computed only from DP outputs and report how it behaves on DBpedia?
  3. Does the default rule df(λ)=r^\mathrm{df}(\lambda)=\hat r remain close to the closed-loop optimum on DBpedia and at budgets other than ρ=0.0035\rho=0.0035?

Clarification:

  1. Which ρ\rho-to-ε\varepsilon conversion is used? With the stated formula ε=ρ+2ρlog⁡(1/δ)\varepsilon=\rho+2\sqrt{\rho\log(1/\delta)}, ρ=0.004\rho=0.004 gives ε≈0.41\varepsilon\approx0.41 rather than 0.36, and the "5x at ε=0.41\varepsilon=0.41" claim corresponds to a 10x ratio in Table 1.
1 comment

We thank the reviewer for the constructive feedback. Our responses are as follows:

  • The revision reports the DBpedia result quantitatively (−0.044-0.044, −0.085-0.085, −0.130-0.130, −0.132-0.132) and positions GRE as beneficial in a dataset-dependent manner rather than as a general upgrade to PE.

  • P is an oracle quantity for analysis. The revision describes it as such and removes Fig. 3. As the reviewer notes, the post-processing guarantee is unaffected, since the algorithm does not use P.

  • A rule computed solely from DP outputs is not currently available; we identify this as an interesting open problem for future research, potentially with larger scale of empirical benchmarking.

  • Thanks for catching this! Please note that The guarantee is stated in ρ\rho, and ε\varepsilon is given for reference only. The reported values were obtained with the conversion formula from [1] (https://arxiv.org/pdf/1605.02065). It turned out our plotting script code had bugs in the conversion implementation, we have updated the manuscript.

[1] Bun, Mark, and Thomas Steinke. "Concentrated differential privacy: Simplifications, extensions, and lower bounds." Theory of cryptography conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016.

Reviewer_QLxKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper looks at the selection step in Private Evolution (PE), specifically AugPE for text. The only place PE touches private data is the noisy nearest-neighbor vote histogram, and the authors argue it is used pretty wastefully: AugPE clips it at zero and takes the top-N. They propose GRE, which projects the noisy histogram onto the scaled simplex (nonnegative, sums to N) while adding a Laplacian smoothness penalty over a kNN graph of the synthetic candidates. Since N is public under replacement adjacency and the graph is built only from synthetic samples, this is post-processing and costs no extra budget. λ is picked by matching the effective degrees of freedom of the (unconstrained) smoother to the support size of the simplex projection.

Critical strengths

First, the paper is right that this is free in terms of privacy accounting. Everything GRE does happens after the single DP release, using N (public under replacement adjacency) and the synthetic candidates (also public), so Prop. 1 holds. The comparison is fair too, since all methods use the same σ and the same accounting. It also composes with other PE improvements like MAPLE or PE-means. This is the main reason I think the direction is worth pursuing.

Second, the observation that better histogram estimates don't automatically give better generations. GraphDenoise has the best Jaccard everywhere in Table 1 but is basically tied with AugPE end-to-end, and pushing the smoothing further drops closed-loop MAUVE from 0.24 to 0.05 in Table 2. That's a useful warning for anyone post-processing PE histograms, and the authors deserve credit for showing a dataset where their own method loses.

Critical weaknesses

(a) The end-to-end results don't support a general claim, and the explanation offered can't be used in practice.

GRE helps on one of the two datasets. On DBpedia it is below AugPE at every budget, and reading Fig. 2 by eye the gap is around 0.09 to 0.13 MAUVE at ρ=0.0127 and ρ=0.169, which isn't small. The paper says this was predicted by Prop. 3, but Prop. 3 is about per-mode linear shrinkage and says nothing about top-N selection or MAUVE; the appendix even admits P doesn't determine top-N recovery. With two datasets I don't think you can say P "tracks" anything. The bigger problem is that P is defined using c_j = u_jᵀh, i.e. the clean histogram. You can't compute that without looking at private data, so I don't see how it can be the "budget-free indicator" claimed in §4.3. If it's computed from h̃ instead, I'd expect it to be biased upward in exactly the high-noise regime, and that isn't discussed. So a practitioner has no private way to decide whether to turn GRE on. On top of that the evaluation is small: MAUVE is the only metric, 5 seeds with overlapping error bands at the middle budgets, one generator, T=5, and only top-N selection.

(b) The λ rule and the "coupling" claim aren't cleanly validated.

The df = r̂ rule is described as having no tuned constants, but the multiplier seems to have been chosen from Table 2, which was run on AG News at ρ=0.0035 with 3 seeds. That's one of the headline configurations, so this looks like tuning on the test setting. It's also non-private hyperparameter selection on the private dataset (cf. Papernot & Steinke, 2022), which should at least be acknowledged. SURE, the obvious alternative, wasn't run end-to-end at all, even though at ρ=0.010 it beats df = r̂ on both nMSE (0.467 vs 0.480) and Jaccard (0.495 vs 0.455).

The claim that the gain comes from coupling the graph penalty with the simplex constraint also doesn't hold up in the microbenchmark. GraphDenoise beats GRE on Jaccard at every budget in Table 1, and the simplex projection alone actually lowers Jaccard relative to clipping at small ρ. The sentence in §4.2 saying GRE "still leads on Jaccard" at ρ ≥ 0.2 contradicts the table (0.601 vs 0.606, and 0.675 vs 0.676). So the coupling argument rests on the single AG News comparison, where GRE beats GraphDenoise in 13 of 20 runs.

Questions for authors
  1. Is P in Fig. 3 computed from h or from h̃? If h, how would someone decide privately whether to use GRE? If h̃, how biased is it compared to the clean version?
  2. What is the end-to-end MAUVE with SURE-chosen λ? And was df = r̂ fixed before running Fig. 2, or picked based on Table 2?
  3. What fraction of kNN edges are between paraphrase siblings, and how does GRE compare with simply pooling votes over each parent's family?
  4. Which ε conversion did you use, and what is the correct ε for the "5× at ε=0.41" claim?
  5. Could you add downstream utility (e.g. classifier accuracy on the synthetic data, as AugPE reports) and significance tests across seeds? With AG News MAUVE in the 0.14–0.37 range it's hard to tell what the absolute gains mean.
  6. What happens with the df rule when r̂ is smaller than the number of connected components, so df(λ) can never reach it?

Suggestions, not required for my evaluation: try the resampling variant from Algorithm 1, a private corpus that's actually far from the generator's prior (the conclusion suggests this too), more datasets for the regime diagnostic, and some analysis of the constrained estimator rather than the unconstrained one.

1 comment

We thank the reviewer for the constructive feedback. Our responses are as follows:

  • The revision states the result precisely: GRE improves MAUVE over AugPE on AG News at all four budgets and reduces it on DBpedia (by 0.044, 0.085, 0.130, and 0.132). The benefit is dataset-dependent, and the paper reports both outcomes. Proposition 3 is about per-mode shrinkage; the revision no longer relates it to the DBpedia result.

  • P is computed from the clean histogram h and is therefore an oracle quantity for analysis, not a private decision rule. The revision states this, removes Fig. 3, and notes that a criterion computable from DP outputs remains open.

  • Simplex projection is a monotone transformation of h~\tilde h and thus cannot change the ranking except through ties, which accounts for its Jaccard in Table 1. The discussion of Table 1 in Sec. 4.2 has been revised to match the reported values, as the difference between GRE and GraphDenoise (13/20 runs, p=0.26p = 0.26) is not significant.

  • The reported ε\varepsilon values were obtained with a tighter conversion than the one stated. For consistency, all values now follow the stated formula: ρ=0.0035\rho = 0.0035 corresponds to ε=0.40\varepsilon = 0.40. The nMSE ratio at ρ=0.004\rho = 0.004 (ε=0.41\varepsilon = 0.41) is 10×10\times; the 5.4×5.4\times figure corresponds to ρ=0.010\rho = 0.010.

Reviewer_Y1vHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a Graph-Regularized Estimator (GRE) to denoise the differentially private nearest-neighbor vote histograms used in Private Evolution (PE). GRE combines nonnegativity and a known total-count constraint with Laplacian regularization on synthetic-candidate graphs. The paper distinguishes histogram estimation, one-shot selection, and iterative generation as different tuning objectives, proposing a degrees-of-freedom heuristic. Experiments show improved histogram recovery at tight privacy budgets and improved generation quality on AG News, but consistently worse performance on DBpedia.

Critical strengths

(1) The problem is practically relevant: improving already released private statistics could enhance synthetic-data utility without additional private queries or model training. (2) The privacy argument is convincing under public dataset size, replacement adjacency, and candidate construction based exclusively on previous DP outputs and public information. (3) The authors report negative results and identify a potentially useful distinction between estimation accuracy, selection accuracy, and closed-loop utility.

Critical weaknesses

(1) Theorem 1 correctly establishes local risk reduction for a fixed, unconstrained linear smoother. However, GRE uses simplex constraints and data-dependent regularization. The theorem does not establish improvement over simplex projection, better ranking, or improved generation. Appendix B acknowledges this limitation, but the main text sometimes overstates its implications. (2) Nearby candidates need not receive similar vote counts because their Voronoi cells can differ substantially. Moreover, the normalized Laplacian encourages similarity of degree-normalized counts, rather than raw counts. The authors should justify this choice and compare alternative Laplacians. The synthetic benchmark explicitly assumes graph-smooth histograms, limiting its ability to validate this assumption. (3) Figure 2 omits simplex-only post-processing, preventing isolation of the benefit from combining constraints and geometry. Graph-only denoising also outperforms GRE on Jaccard throughout Table 1. Evaluation uses only two datasets, one generator, one embedder, and one generation-quality metric. Independent representations and downstream utility would strengthen the significance.

Questions for authors

(1) Can the authors provide end-to-end simplex-only and SURE-tuned GRE results?

(2) Why use the normalized Laplacian, and how sensitive are results to graph construction?

(3) Is the diagnostic strictly offline, or can it guide deployment within the stated privacy budget?

(4) Does the tuning rule generalize across datasets and budgets, and what supports the under-exploration explanation?

(5) How does GRE differ from the omitted literature, and can the numerical and reproducibility issues be resolved?

1 comment

We thank the reviewer for the constructive feedback. Our responses are as follows:

  • Theorem 1 characterizes the unconstrained linear smoother with a fixed λ and serves as motivation for graph smoothing under DP noise. We have revised the manuscript following the theorem to state this scope explicitly and to separate it from the empirical behavior of the constrained estimator.

  • Graph smoothness is a modeling assumption, and Sec. 3.1 now presents it as such. The revision also gives the penalty in explicit form. We adopt the normalized Laplacian because its spectrum lies in [0, 2] for every candidate pool, which gives a fixed step size and a comparable scale of λ across iterations The benchmark in Sec. 4.2 is designed to isolate estimator behavior when the assumption holds.

  • The diagnostic P is an offline quantity: it depends on the clean histogram and is not intended for use within the privacy budget. The revision clarifies it accordingly.

  • Related work now covers maximum-likelihood post-processing under consistency constraints (Lee et al., 2015), graphical-model estimation (McKenna et al., 2019, 2022), and graph trend filtering (Wang et al., 2016).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.