- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
Disclaimer. My expertise lies in generative modeling where I had experience in DP and IPM optimization, but I have no a priori knowledge of Private Evolution and the related literature. I therefore have low confidence for my assessment below. I will let the other reviewers and the AC judge the relevance of my review.
This paper studies an alternative to Private Evolution (a training-free method to derive a DP synthetic dataset from a real one) that the authors name direct evolution, consisting in optimizing an IPM with an evolutionary algorithm. The convergence of such an algorithm is proven to require exponentially many variations even for simple function classes in the IPM. The paper proposes an alternative based on mean matching for linear functions but finds that even data reconstruction is NP-hard for quadratic functions.
Critical strengths
- The paper derives a new paradigm for private evolution consisting in directly optimizing an IPM, together with theoretical results about the difficulty of following such a paradigm, which is a negative result that may be conceptually interesting.
Critical weaknesses
As an outsider of the research area of Private Evolution, but having studied the problem for the present review, I find that this paper suffers from two important weaknesses severely limiting the significance of its contributions.
Motivation and clarity
- The paper clarity could be improved. It explains its framework and Private Evolution in a more convoluted manner than prior work (Lin et al., 2023; González Lara et al., 2026). The motivation for direct evolution is seldom discussed. Furthermore, the derived insights are scattered throughout the paper, leaving their recollection up to the reader.
- Regarding direct evolution, it is especially unclear to me why, when optimizing the IPM via direct evolution, the authors choose to do so via an evolutionary process when the IPM could be optimized even more directly via, e.g., a gradient flow.
Impractical and unrealistic results
- While I appreciate negative results, the paper does not convey valuable insights that could be leveraged elsewhere in the literature -- at least to my knowledge. The significance of the presented results seem to be bounded to the present paper.
- Moreover, the presented results are presented in a very restricted setting with unrealistic assumptions of linear or quadratic queries. Their discriminative power being limited, bare mean matching can be used to solve the studied problem when realistic data require more elaborate care, and it is unclear whether the optimization and difficulty results can transfer to more complex queries.
Questions for authors
Given the above weaknesses, and in my current limited understanding of the tackled research problem, I recommend rejecting this paper. However, given my lack of expertise, I remain open for discussion with the authors, reviewers and AC.
In particular, answers to the following questions could make me reconsider my assessment.
- Could the authors explain why they choose not to optimize the IPM via gradient methods?
- Could the authors justify their assumptions and the relevance they carry w.r.t. a realistic setting and the relevant literature?
Post-rebuttal update
I would like to thank the authors for their response, and to apologize for not having had the time to acknowledge it sooner. Unfortunately, I am not convinced by the provided answers, and I tend to agree with Reviewer M1ek. Regarding my specific questions:
- The reason why direct optimization cannot be used in this context is still unclear: I do not understand how it is less relevant than changing paradigm from private evolution to direct evolution. However, this may be due to my lack of expertise on the topic.
- Negativity results are not shown to transfer to more complex queries. I understand the FID argument, but it is generally a bad idea to optimize for FID directly (unless for some fine-tuning) precisely for the reasons provided by the authors; MMD is a better choice but requires more complex queries (Deng et al., 2026).
To put it more broadly, I think the paper lacks a general insight about how the presented results on direct evolution transfers to the actual private evolution algorithms. Therefore, I am inclined to maintain my score while acknowledging my low confidence and waiting for the reviewer-AC discussion period.
Thanks for your feedback. We answer below.
We have now slightly repurposed how we introduce PE and added a flowchart for better intuition in Section 2, and we hope it is gentler to the uninitiated reader.
Lin et al., 2023 proposed PE and González Lara et al., 2026 proved that the algorithm is effectively minimizing a W1 distance. We therefore start directly from the interpretation of PE as an algorithm optimizing W1, which motivates studying other IPMs. Direct evolution is a natural candidate for this task: make as much progress on the target IPM as the variation set allows at each iteration.
We have rewritten a good amount of the main body to explain these insights better (in our opinion). As concrete examples, in Section 3 we now include some of the intuition behind why direct evolution gets stuck with high probability in the quadratic case and we have rewritten Theorem 3.1 in a more clear way.
We want to emphasize that our goal in this work was not to propose an algorithm for better solving a given class of IPMs, but to explore what is feasible (and not) using private evolution and related algorithms. Indeed, you are correct that one could optimize the IPM more directly with other methods, but our goal in this work is to deepen our understanding of evolution-based algorithms. We now discuss related methods for optimizing distances between datasets without evolution in the related work.
Understanding PE for IPM optimization is relevant in other places in the literature. We give two examples where this appears. First, there are already works adapting PE to query-based utility. For example, “Is API Access to LLMs Useful for Generating Private Synthetic Tabular Data?” by Swanberg et al. (2025) studies PE for tabular data using an IPM distance as accuracy measure. Second, Lin et al., (2023) develops PE for images, where preserving quadratic queries is important; we elaborate on this second example below. We have added these to the introduction.
We remark that the simplicity of the queries is actually a good thing for our lower bounds: even for simple IPMs, we show that evolution may fail to make progress. Our lower bounds also establish worst-case obstructions for broader problem classes that allow higher-degree queries, since these classes include our quadratic instances.
That said, although their discriminative power is limited, there are also practical motivations for understanding linear and quadratic IPMs. We give two examples. First, in image generation, a widely used metric for evaluating synthetic images is Fréchet Inception Distance (FID), which depends only on the first and second moments of image features. Thus, matching linear and quadratic queries in feature space is sufficient to preserve the quantities entering FID. We mention this example in the introduction. Second, recent work on evaluating LLM-based user simulators (Meshi et al., 2026) compares synthetic and real conversations using simple statistics, such as how often users accept recommendations. These are applications where the goal is to preserve simple statistics.