REVIEW 3 major objections 5 minor 19 references
Accuracy-First R\'enyi Differential Privacy and Post-Processing Immunity
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Post-processing immunity comes to accuracy-first privacy
desk verdict The validation-stopping theorem is broken and the experiments lean on it, but the post-processing analysis and Brownian mechanism proof are genuinely useful. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the $\alpha$-ex-post RDP definition itself, equipped with the paper's new notation in which the mechanism returns both the useful output $y$ and the claimed privacy bound $\epsilon$ as part of its output. The definition is engineered so that the data-processing inequality for R\'enyi divergence applies directly: post-processing can only lower the $\alpha$-moment ratio, and this yields post-processing immunity. The argument for the Brownian mechanism runs through an equivalent sequential precision-weighted Gaussian mechanism, where each release is Gaussian with variance $\alpha\Delta^2/(2\epsilon_i)$ and outputs are combined by minimum-variance precision weighting, so the whole mechanism is a post-processing of a composition of Gaussian mechanisms and the composition theorem applies.
What would settle it
Run the validation-stopping algorithm with constant-cost base mechanisms and a binary RDP stopping rule that halts with fixed probability per round, then compute the privacy loss of the released stop time under neighbouring datasets; a geometric-stopping construction would violate the claimed bound $\max(\sum_j \epsilon_j, \epsilon_T)$ and show the stopping theorem is unsound.
Extended reading notes
Core claim
The central claim is that ex-post R\'enyi differential privacy, defined by moving the returned privacy bound $\epsilon$ inside the R\'enyi expectation, is the right accuracy-first definition: a mechanism $M:\mathcal{X}\to\mathcal{Y}\times\mathbb{R}_{\geq 0}$ is $\alpha$-ex-post RDP when for every neighbouring $X,X'$ the expectation $\mathbb{E}_{(y,\epsilon)\sim M(X')}[e^{(1-\alpha)\epsilon}(p_{M(X)}(y,\epsilon)/p_{M(X')}(y,\epsilon))^\alpha] \leq 1$. The paper proves that this definition has post-processing immunity, that a bounded ex-post RDP mechanism is also ordinary $(\alpha,\epsilon)$-RDP, and that adaptive composition holds with total bound equal to the sum of the returned $\epsilon_i$. It then proves that the Brownian mechanism satisfies the definition by exhibiting an equivalent sequential precision-weighted Gaussian mechanism whose privacy analysis is elementary. Finally, the paper extends composition to a stopping rule that inspects a separate private validation set, claiming a total bound $\epsilon = \max(\sum_{j\le t}\epsilon_j,\epsilon_T)$ for the resulting adaptive algorithm.
Load-bearing premise
The validation-stopping result assumes that a single $(\alpha,\epsilon_T)$-RDP guarantee for the stopping rule covers the whole procedure, even though the algorithm may call that rule up to $K$ times and the released stopping time itself may carry privacy loss.
Editorial extensions
If this is right
- Any transformation of the output of an $\alpha$-ex-post RDP mechanism, without further access to private data, leaves the privacy guarantee intact, so downstream processing no longer needs its own privacy accounting.
- The Brownian mechanism can now be used in accuracy-first workflows with a rigorous ex-post guarantee, so an analyst can increase the privacy budget over time until utility is sufficient.
- Adaptive composition of ex-post RDP mechanisms holds, including mixtures of ex-ante and ex-post RDP mechanisms, and releasing intermediate $\epsilon_i$ values does not break the guarantee.
- A bounded ex-post RDP mechanism is also ordinary RDP with the same bound, so standard RDP analysis and conversion tools apply.
- The validation-based stopping algorithm lets a practitioner check accuracy on a private validation set and stop as soon as a threshold is met, with total budget $\max(\sum_j \epsilon_j, \epsilon_T)$ under the paper's theorem.
Reading between the lines
- If the validation-stopping theorem turns out to require more than a single $\epsilon_T$ for repeated stopping-rule invocations, the total bound used in the algorithm would need to charge per check or use a different composition rule, and the experimental privacy accounting would need to be re-audited.
- The same definition could plausibly extend to the limiting cases $\alpha=1$ and $\alpha=\infty$, which would give ex-post versions of KL-based and pure differential privacy and connect the accuracy-first machinery to other privacy accounting frameworks.
- Because the definition exhibits post-processing immunity, it may provide a cleaner foundation for ex-post analogues of DP-SGD and of the exponential mechanism than the earlier probabilistic ex-post relaxation.
- The open question of whether $\delta$-approximate ex-post privacy has post-processing immunity matters for practitioners who prefer approximate-DP style bounds; a conversion from ex-post RDP that preserved immunity would give the best of both.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces alpha-ex-post Renyi differential privacy, a data-dependent privacy definition in which the reported privacy bound epsilon is part of the mechanism's output. The authors argue that this notation makes post-processing immunity expressible for ex-post privacy, and they prove that pure ex-post privacy and alpha-ex-post RDP have post-processing immunity while delta-probabilistic ex-post privacy does not. They develop adaptive composition theorems and show that the Brownian mechanism can be viewed as a sequential precision-weighted Gaussian mechanism, thereby proving that it satisfies alpha-ex-post RDP. They also propose a validation-set-based stopping algorithm (Algorithm 1) with a claimed privacy bound max(sum of epsilon_i, epsilon_T), and demonstrate the method on synthetic data generation from the UCI Adult dataset. The central theoretical claim of the paper is Theorem 4.6, which supports the validation-based stopping rule.
Significance. If the results were all sound, this would be a meaningful step: alpha-ex-post RDP would be the first accuracy-first definition combining post-processing immunity, an RDP-style composition calculus, an ex-post Gaussian/Brownian mechanism, and a practical validation-based stopping rule. The Brownian mechanism analysis (Lemma 5.1, Theorem 5.2, Corollary 5.3) and the post-processing immunity theorems appear correct and are valuable independent of the stopping-rule theorem. However, Theorem 4.6, which is the basis of the Section 6 experiments, is not sound as stated. The practical claim of validation-based adaptive privacy budgeting is therefore unsupported, and the contribution is not publishable in its current form.
major comments (3)
- [Section 4, Theorem 4.6 and Eq. (59)-(60)] The likelihood ratio omits the stopping mechanism. Algorithm 1 releases the stopping time t, and the event that T halts at iteration i depends on X_epsilon through T and on the previously released y_i. The proof in Eq. (59) writes the epsilon factor as p_{E(X_epsilon)}(epsilon_i | ...) and never includes a factor for the stopping decision c_i or for t. This is not a notational slip: in Algorithm 1, epsilon_i = E(y_{1:i-1}, epsilon_{1:i-1}) has no validation-set argument, so p_{E(X_epsilon)} and p_{E(X'_epsilon)} are identical and the ratio cancels. Consequently the bound in Eq. (60), which invokes the (alpha, epsilon_T)-RDP guarantee of T, is applied to an expression that contains no information about T's output. In the case X_epsilon = X'_epsilon the released stopping time is likewise absent from the expression. The claimed bound max(sum_{j<=t} epsilon_j, epsilon_T) is therefore unproven, and it is false in general: with constant-cost base mechanisms (epsilon_i = 0) and a binary RDP stopping rule invoked repeatedly, the stopping time has a geometric distribution whose Rényi divergence from the neighbouring dataset grows with the number of allowed invocations K and exceeds epsilon_T. Since the experiments in Section 6 rely on this theorem for their privacy accounting, the validation-based adaptive budgeting claim is unsupported.
- [Section 5, Lemma 5.1 and Algorithm 2] The mechanism is well-defined only for nondecreasing epsilon sequences. Algorithm 2 sets sigma_i^2 = alpha Delta^2 / (2 (epsilon_i - epsilon_{i-1})), which requires epsilon_i >= epsilon_{i-1}; if E can return a smaller epsilon, the mechanism calls for a Gaussian with negative variance. Similarly, Algorithm 3's Brownian bridge formula in Eq. (62) is stated for T_i < T_{i-1}, i.e., for epsilon_i > epsilon_{i-1}. The statements of Lemma 5.1, Theorem 5.2, and Corollary 5.3 do not state this monotonicity assumption on the epsilon selector E. The assumption should be added explicitly, or the algorithms should specify how decreases in epsilon are handled.
- [Section 6, privacy accounting] The sentence 'By Theorems 4.4 and 4.6 and the fact that epsilon >= epsilon_check, the total privacy bound is epsilon_total = epsilon_query + max(epsilon, epsilon_check)' is not justified, because Theorem 4.6 is not sound. The reported privacy guarantees of the experiment therefore do not follow from the theory in the manuscript.
minor comments (5)
- [Section 1] The first paragraph contains a duplicated word: 'necessitates necessitates' should be 'necessitates'.
- [Algorithm 1] In the pseudocode, the line 'epsilon_i <- E(y_{1:i-1}, epsilon_{i:1-1})' contains a typo in the subscript; it should be epsilon_{1:i-1}.
- [Theorem 4.4 proof, Eq. (49)] The conditional density p_{M2(X)}(y1, epsilon1 | y2, epsilon2) should read p_{M2(X)}(y2, epsilon2 | y1, epsilon1); as written the conditioning is inverted.
- [Theorem 4.5 proof, Eqs. (54) and (57)] The denominator in the final ratio should be p_{M_i(X')}(...), not a second occurrence of p_{M_i(X)}(...).
- [Theorem 3.3 proof] The density 'of f(y,epsilon)' is introduced without clear conditioning notation; it should be written as the conditional density of f(y,epsilon) given (y, epsilon).
Circularity Check
No significant circularity: the Brownian mechanism analysis and post-processing immunity results are derived from independent RDP and data-processing arguments, not from the proposed definition by construction.
full rationale
The paper's central derivations do not reduce to their inputs. Definition 4.1 introduces alpha-ex-post RDP as a general privacy notion, and Lemma 5.1 proves that the sequential precision-weighted Gaussian mechanism satisfies it by combining the standard RDP guarantee of the Gaussian mechanism with the adaptive composition theorem (Theorem 4.5); the guarantee is not assumed inside the definition. Theorem 5.2 establishes distributional equivalence to the Brownian mechanism by matching conditional distributions, so Corollary 5.3 transfers the privacy bound without using Whitehouse et al. (2022) as a circular privacy oracle. Post-processing immunity in Theorems 3.3 and 4.2 follows from the data-processing inequality for Rényi divergence applied to the post-processing channel, rather than from a definition that already contains the conclusion. Self-citations such as Koskela et al. (2023) appear only in the related-work discussion of odometers and are not load-bearing for any theorem. The possible gap in Theorem 4.6's proof regarding the released stopping time is a correctness concern about the validation stopping argument, not a circular derivation: no fitted parameter is renamed as a prediction, and no result is forced by a self-citation chain. The derivation chain is therefore self-contained with respect to circularity.
Assumptions & free parameters
free parameters (5)
- accuracy_threshold =
0.825
- alpha (RDP order) =
20
- epsilon_check =
0.01
- epsilon_query =
0.01
- epsilon release schedule =
7 values from 0.01 to 1.0, log-spaced
assumptions (4)
- standard math Data-processing inequality for Rényi divergence (van Erven and Harremoës, 2014)
- standard math Gaussian mechanism with sensitivity Delta and noise variance sigma^2 is (alpha, alpha Delta^2 / (2 sigma^2))-RDP
- domain assumption Mechanism outputs admit densities with respect to a common base measure
- ad hoc to paper A single-invocation RDP bound on the stopping rule T covers K sequential invocations
invented entities (2)
-
alpha-ex-post RDP privacy definition
-
Ex-post notation with epsilon as part of the output
Cite this review
Pith. "Pith review of Accuracy-First R\'enyi Differential Privacy and Post-Processing Immunity." pith.science (2026). https://pith.science/paper/LM7CXNX5
@misc{pith2026250922213,
author = {Pith},
title = {Pith review of: Accuracy-First R\'enyi Differential Privacy and Post-Processing Immunity},
year = {2026},
howpublished = {\url{https://pith.science/paper/LM7CXNX5}},
note = {Machine review of arXiv:2509.22213}
}
read the original abstract
The accuracy-first perspective of differential privacy addresses an important shortcoming by allowing a data analyst to adaptively adjust the quantitative privacy bound instead of sticking to a predetermined bound. Existing works on the accuracy-first perspective have neglected an important property of differential privacy known as post-processing immunity, which ensures that an adversary is not able to weaken the privacy guarantee by post-processing. We address this gap by determining which existing definitions in the accuracy-first perspective have post-processing immunity, and which do not. The only definition with post-processing immunity, pure ex-post privacy, lacks useful tools for practical problems, such as an ex-post analogue of the Gaussian mechanism, and an algorithm to check if accuracy on separate private validation set is high enough. To address this, we propose a new definition based on R\'enyi differential privacy that has post-processing immunity, and we develop basic theory and tools needed for practical applications. We demonstrate the practicality of our theory with applications to synthetic data generation and image classifier fine-tuning, where our algorithm successfully adjusts the privacy bound until an accuracy threshold is met on a private validation dataset.
Figures
Reference graph
Works this paper leans on
-
[1]
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep Learning with Differential Privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308–318. ACM,
work page 2016
-
[2]
for the interaction described in Algorithm 2
claims that their odometer provides (ϵ,δ) -DP “for the interaction described in Algorithm 2” (of their paper). Our arguments here show that this is false if it is indeed a claim of ex-ante (ϵ,δ) -DP. The paper of Lécuyer (2021) does not have any proof of this claim, only the other claim of their Theorem 2 that provides a conversion to a probabilistic DP o...
work page 2021
-
[3]
Private Hyperparameter Tuning with Ex-Post Guarantee
URL http://arxiv.org/ abs/2508.15183. Samuel Haney, Michael Shoemate, Grace Tian, Salil Vadhan, Andrew Vyrros, Vicki Xu, and Wanrong Zhang. Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters. InProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS ’23, pp. 1949–1963, New Y...
work page Pith review arXiv 2023
-
[8]
Tim van Erven and Peter Harremoës
URL https: //arxiv.org/abs/2112.09238. Tim van Erven and Peter Harremoës. Rényi Divergence and Kullback-Leibler Divergence.IEEE Transactions on Information Theory, 60(7):3797–3820,
-
[10]
that would be applicable, but found that they have too large overheads in privacy cost to be useful in our setting. 24 Table 3: Conversion of ex-post RDP ϵ values used for synthetic data generation to approximate ex-post privacyϵwithδ= 10 −5 using the formula of Ghazi et al. (2025, Lemma
work page 2025
-
[12]
Theorem A.1.Let COMPδg be a valid privacy odometer in the sense of Rogers et al
is probabilistically ex-post private. Theorem A.1.Let COMPδg be a valid privacy odometer in the sense of Rogers et al. (2023, Definition 3.1). Let M∗ be an ex-post mechanism whereM∗(X)y runs any fully adaptive com- position (Rogers et al., 2023, Algorithm 2), resulting in ADP parameters ϵ1,δ 1,...,ϵ K,δK, and M∗(X)ϵ = COMPδg(ϵ1,δ 1,...,ϵ K,δK). ThenM∗ isδ...
work page 2023
-
[13]
is not as clear. They are constructed by running multiple privacy filters with different upper bounds, and setting the accumulated privacy loss to be the smallest loss of the filters whose upper bound has not been exceeded. This construction results in some discretisation error in the odometers, since there is only a finite number of filters. Lécuyer (202...
work page 2021
-
[15]
(56) Plugging into(∗)gives (∗)≤E y1:K−1,ϵ1:K−1 "K−1Y i=1 βi pMi(X)(yi|ϵi) pMi(X)(yi|ϵi) α# .(57) Repeating these steps an additionalK−1times results in (∗)≤1,(58) which concludes the proof. Theorem 4.6.Let a dataset X be randomly divided into a training set Xy and validation setXϵ. LetMi(Xy,ϵi,y 1:i−1), 1≤i≤K be mechanisms that are (α,ϵi)-RDP , and letT(X...
work page 2011
Show all 19 references
-
[16]
Denote the ˆs1:K outputs from Algorithm 2 as ˆsseq 1:K and the outputs from Algorithm 3 as ˆsbro 1:K
Proof. Denote the ˆs1:K outputs from Algorithm 2 as ˆsseq 1:K and the outputs from Algorithm 3 as ˆsbro 1:K. In the Brownian mechanism (Whitehouse et al., 2022),ˆsbro 1 |X∼N(f(X),T 1). WhenT i <T i−1, ˆsbro i |ˆsbro 1 ,...,ˆs bro i−1,X∼N f(X) + Ti Ti−1 (ˆsbro i−1−f(X)), (Ti−1−...
2022
-
[19]
fnlwgt” and “educational-num
SVT permits an arbitrary number of accuracy checks, unlike the plain Gaussian check. However, SVT has a large overhead in the noise variance with a small number of checks, so in our setting, the plain Gaussian check requires less noise. Dataset and PreprocessingWe use the UCI ...
1996
-
[2016]
Since we know this mechanism is not ex-ante DP with a finiteϵ (unlessδ≥ 1 2), the value returned by the odometer cannot be an ex-ante DP guarantee
regardless of δ, and return an arbitrarily small ϵ for an RDP odometer (Feldman & Zrnic, 2021; Lécuyer, 2021). Since we know this mechanism is not ex-ante DP with a finiteϵ (unlessδ≥ 1 2), the value returned by the odometer cannot be an ex-ante DP guarantee. 3Note that Lécuyer...
2021
-
[2018]
Ilya Mironov
URL https://eprint.iacr.org/2018/277. Ilya Mironov. Rényi Differential Privacy. In30th IEEE Computer Security Foundations Symposium, pp. 263–275,
2018
-
[2019]
is able to generate high quality synthetic data based on only noisy values of marginal queries (Tao et al., 2021; Chen et al., 2025). To choose the marginal queries, we use the MST algorithm (McKenna et al., 2021), to obtain an initial set, and add the pairwise marginal querie...
2020
-
[2020]
13 Table 2: Common notations. MDP Mechanism γGeneric privacy parameter(s) (ϵ,δ)Privacy parameters for ADP-style definitions (ϵ,α)Privacy parameters for RDP-style definitions X∈XDataset, universe of datasets X∼X ′ Neighbouring datasets y∈YOutput of mechanism, universe of possib...
2016
-
[2021]
Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z
URL http://arxiv.org/abs/ 2103.01379. Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z. Wu. Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. InAdvances in Neural Information Processing Systems, volume
-
[2022]
Rpost(X,X′) Rprior(X,X′) α−1# ≤e (α−1)ϵ.(19) We can rearrange (19) to lnE y∼M(X)
odometer of Koskela et al. (2023) is even less clear. It is constructed in a similar way to the RDP odometers by running multiple GDP filters. The natural questions to ask is: does this odometer satisfy some sense of ex-post GDP? However, we are not aware of any work giving a ...
2023
-
[2023]
Rogers, Salil P
Ryan M. Rogers, Salil P. Vadhan, Aaron Roth, and Jonathan Ullman. Privacy Odometers and Filters: Pay-as-you-Go Composition. InAdvances in Neural Information Processing Systems, volume 29, pp. 1921–1929. Curran Associates, Inc.,
1921
-
[2024]
12 David M
URL http://arxiv.org/ abs/2412.13030. 12 David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy Loss Classes: The Central Limit Theorem in Differential Privacy.PoPETs, 2019(2):245–269,
2019 arXiv
-
[2025]
Christian Covington, Xi He, James Honaker, and Gautam Kamath
URLhttp://arxiv.org/abs/2504.14061. Christian Covington, Xi He, James Honaker, and Gautam Kamath. Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy.Statistica Sinica, 35:651–670,
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.