{"id":"d536153f-440a-48f9-80c4-255dc7110388","arxiv_id":"2509.22213","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"The paper defines alpha-ex-post Rényi DP with post-processing immunity and proves the Brownian mechanism satisfies it, but the validation-set stopping theorem underlying the experiments is not sound as stated.","lead":"This paper studies which accuracy-first (ex-post) differential privacy definitions survive post-processing, and introduces a Rényi-based ex-post definition with this property. It claims to provide practical tools for adaptive privacy budgeting, but the central validation-set stopping theorem has a flawed proof.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.6's validation-set stopping proof omits the stopping time from the likelihood ratio, so the claimed max(sum ε_i, ε_T) bound is unproven and contradicted by a geometric-stopping counterexample.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: Theorem 4.6's proof does not account for the privacy loss of the released stopping time t, and it incorrectly treats the epsilon-selection densities as validation-dependent. I re-read the proof of Theorem 4.6 in Section C.3 and confirmed that Eq. (59) writes a product over p_{E(X_ε)} terms even though Algorithm 1 defines E without X_ε, and that no factor for the stopping decisions c_i or the released t appears anywhere in the likelihood ratio. The final inequality in the X_y = X'_y case invokes T's RDP guarantee on an expression that contains no T output, so the argument cannot work. The geometric-stopping counterexample is decisive: with constant base mechanisms, the entire privacy loss is concentrated in t, and repeated invocation of a binary RDP stopping rule produces a geometric stopping time whose Rényi divergence exceeds the single-invocation budget. Because the experiments in Section 6 use Theorem 4.6 to justify the privacy accounting, the paper's central practical contribution is unsupported. I agree with the reader's REJECT verdict and see no reason to change it. The Brownian mechanism analysis and post-processing immunity theorems appear sound, and the paper is clearly written and openly credits parallel work by Ghazi et al. (2025); those strengths do not repair the failure of Theorem 4.6.","tokens_in":22570,"tokens_out":9731,"duration_ms":85277,"concrete_test":"Implement the counterexample exactly as specified in the reader's review. Let M_i be constant mechanisms (ε_i = 0, deterministic output), let T be a binary RDP stopping rule that on input (X_ε, y_i) returns Halt with probability p(X_ε), where p is chosen so that one invocation satisfies D_α(T(X_ε)||T(X'_ε)) ≤ ε_T. Run Algorithm 1 for K = 10, ε_T = ln 2, α = 2, and compute the Rényi divergence D_α between the distribution of the released t under X_ε and under X'_ε (with X_y = X'_y). If D_α(t) > ε_T, Theorem 4.6 is false as stated, since the claimed bound is max(0, ε_T) = ε_T. A simple choice is p(X_ε) = 1/3, p(X'_ε) = 2/3; one invocation has D_2 ≈ 0.405 ≤ 0.693, but the truncated geometric distribution of t over K = 10 steps has D_2 ≈ 3, clearly exceeding ln 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is in the proof of Theorem 4.6. Algorithm 1 releases the stopping time t, and the stopping decisions c_i = T(X_ε, y_i) depend on the validation set. The likelihood ratio in Eq. (59), however, contains no factor for c_i or t: it writes the joint density as ∏_i [p_{E(X_ε)}(ε_i | ...) p_{M_i(X_y)}(y_i | ...)] / [p_{E(X'_ε)}(ε_i | ...) p_{M_i(X'_y)}(y_i | ...)], where p_{E(X_ε)} is not the distribution used by Algorithm 1 — there ε_i = E(y_{1:i-1}, ε_{1:i-1}) has no validation-set argument. In the case X_y = X'_y the proof bounds the remaining product by e^{(1-α)ε_T} and invokes the (α, ε_T)-RDP guarantee of T, but T's output does not appear in the expression, so no such bound follows. In the case X_ε = X'_ε the stopping-time factor is also missing. Consequently the release of t is never privacy-accounted. This is not a technical gap in one inequality: a concrete counterexample with constant-cost base mechanisms (ε_i = 0) and a binary RDP stopping rule invoked K times yields a geometric distribution for t whose Rényi divergence from the neighbouring dataset grows with K and exceeds ε_T, violating the claimed bound max(Σε_i, ε_T). The experiments in Section 6 rely on Theorem 4.6 for their privacy accounting, so the central practical claim of validation-based adaptive privacy budgeting is unsupported. The Brownian mechanism analysis (Lemma 5.1, Corollary 5.3) and the post-processing immunity results are not affected by this flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22906,"tokens_out":14760,"duration_ms":126945,"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":[{"comment":"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":"Section 4, Theorem 4.6 and Eq. (59)-(60)"},{"comment":"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":"Section 5, Lemma 5.1 and Algorithm 2"},{"comment":"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.","section":"Section 6, privacy accounting"}],"minor_comments":[{"comment":"The first paragraph contains a duplicated word: 'necessitates necessitates' should be 'necessitates'.","section":"Section 1"},{"comment":"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}.","section":"Algorithm 1"},{"comment":"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.","section":"Theorem 4.4 proof, Eq. (49)"},{"comment":"The denominator in the final ratio should be p_{M_i(X')}(...), not a second occurrence of p_{M_i(X)}(...).","section":"Theorem 4.5 proof, Eqs. (54) and (57)"},{"comment":"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).","section":"Theorem 3.3 proof"}],"recommendation":"reject","confidential_remarks":"This manuscript contains two valuable components that could form the basis of a resubmission: the post-processing-immunity analysis and the Brownian mechanism's ex-post RDP proof. However, the validation-set stopping theorem is not sound, and it is the basis of the experimental privacy claims. I recommend rejection of the current version; a revised version that either fixes the stopping-time accounting or drops the validation-based stopping claim would deserve a fresh review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Load-bearing flaw in Theorem 4.6; the rest is mostly sound. The new notation for ex-post privacy (epsilon as part of the output) is actually helpful, and the post-processing immunity results—pure ex-post privacy has it, probabilistic ex-post privacy doesn't—are clean and correct as far as I can tell. The Brownian mechanism analysis via the precision-weighted Gaussian mechanism is also a genuine simplification. But the validation-set stopping theorem doesn't hold as stated. Equation (59) writes the epsilon-selection density as p_E(X_epsilon)(...), while Algorithm 1 defines epsilon_i = E(y_{1:i-1}, ...) with no validation set. More importantly, the stopping rule's outputs c_i and the released stopping time t never appear in the likelihood ratio, so the proof never accounts for the privacy cost of releasing t. The final inequality in the X_y = X'_y case tries to use the (alpha, epsilon_T)-RDP of T, but T's output isn't in the expression. A concrete counterexample with constant-cost base mechanisms and a binary RDP stopping rule invoked K times produces a geometric stopping time whose Rényi divergence grows with K and exceeds the claimed max(sum epsilon_i, epsilon_T). This isn't a minor gap; the experiments in Section 6 use Theorem 4.6 for their privacy accounting, so the central practical claim is unsupported. Minor issues: no code or data, and the Brownian proof implicitly assumes strictly increasing epsilon_i (the equality case is hand-waved). The paper is clearly written and honest about parallel work by Ghazi et al. Bottom line: the PPI classification and Brownian mechanism proof are worth keeping, but Theorem 4.6 needs a real fix. As submitted, I would not trust the validation-based privacy bound. I'd send it to a serious referee with a note to focus on Theorem 4.6; if that gets fixed, it becomes a solid paper.","headline":"The validation-stopping theorem is broken and the experiments lean on it, but the post-processing analysis and Brownian mechanism proof are genuinely useful.","tokens_in":23507,"tokens_out":3095,"would_cite":true,"duration_ms":26253,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Post-processing immunity comes to accuracy-first privacy","keywords":["differential privacy","ex-post privacy","Rényi differential privacy","post-processing immunity","accuracy-first privacy","Brownian mechanism","adaptive composition","private validation set"],"falsifier":"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.","tokens_in":1715,"feed_emoji":"🔒","tokens_out":1911,"duration_ms":60753,"temperature":0.7,"pith_summary":"The paper sets out to give the accuracy-first approach to differential privacy a privacy definition that behaves like ordinary differential privacy when outputs are post-processed: an analyst may adaptively raise or lower the privacy bound during a run, but no transformation of the released output can make the guarantee weaker. It shows that the existing pure ex-post privacy notion has post-processing immunity while the probabilistic relaxation does not, and it introduces $\\alpha$-ex-post R\\'enyi differential privacy, a definition that does have immunity. The paper proves that the Brownian mechanism, the accuracy-first counterpart of the Gaussian mechanism, satisfies the new definition, and that adaptive compositions of ex-post RDP mechanisms remain private, including a stopping rule that checks accuracy on a separate private validation set. If correct, this supplies the missing toolbox for accuracy-first privacy: data-dependent budgets, post-processing safety, and validation-based early stopping under one definition.","feed_headline":"Post-processing immunity comes to accuracy-first privacy","feed_subtitle":"A new Rényi differential privacy variant supports the Brownian mechanism and validation-based budget tuning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the approximate DP definition and the Gaussian mechanism that the Brownian mechanism is designed to generalise.","marker":"Dwork et al. (2006a)"},{"why":"Supplies R\\'enyi differential privacy and the Bayesian interpretation that the ex-post RDP definition extends.","marker":"Mironov (2017)"},{"why":"Introduces the accuracy-first perspective and the pure ex-post privacy definition whose post-processing immunity is established here.","marker":"Ligett et al. (2017)"},{"why":"Introduces the Brownian mechanism and the probabilistic ex-post relaxation that the paper shows lacks post-processing immunity.","marker":"Whitehouse et al. (2022)"},{"why":"Provides the R\\'enyi divergence data-processing inequality used in the post-processing immunity proof.","marker":"van Erven & Harremoës (2014)"},{"why":"Defines post-processing immunity, the property the paper argues any sensible privacy definition should satisfy.","marker":"Dwork & Roth (2014)"},{"why":"Provides the counterexample showing that probabilistic DP lacks post-processing immunity, which is transferred to $\\delta$-probabilistic ex-post privacy.","marker":"Meiser (2018)"},{"why":"Parallel work proposing ex-post RDP and giving the conversion to approximate ex-post privacy used in the paper.","marker":"Ghazi et al. (2025)"},{"why":"Supplies the minimum-variance unbiased linear weighting theorem underlying the sequential precision-weighted Gaussian mechanism.","marker":"Covington et al. (2025)"},{"why":"Provides the Private-PGM synthetic data generation method used in the experiments.","marker":"McKenna et al. (2019)"}],"fun_headline_variants":["Ex-post Rényi privacy gains post-processing immunity","Privacy that resists post-processing: ex-post Rényi","New Rényi privacy definition immune to post-processing","Ex-post Rényi: immunity and Brownian mechanism","Accuracy-first privacy: ex-post Rényi with validation tuning"],"cache_read_input_tokens":25472,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Ex-post Rényi privacy gains post-processing immunity","Privacy that resists post-processing: ex-post Rényi","New Rényi privacy definition immune to post-processing","Ex-post Rényi: immunity and Brownian mechanism","Accuracy-first privacy: ex-post Rényi with validation tuning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001751,"raw_usage":{"total_tokens":6929,"prompt_tokens":973,"completion_tokens":5956,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":5875}},"tokens_in":589,"tokens_out":5956,"duration_ms":35152,"temperature":1.0,"reasoning_tokens":5875,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:47:14.811787+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}