{"id":"bc212896-96a6-4af5-9db3-6f2a6c2886ca","arxiv_id":"2508.15183","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A random-dropping mechanism tunes hyperparameters under ex-post DP with about a 2x privacy blowup for the winning candidate, and extends to Rényi DP.","lead":"The paper gives a new algorithm for private hyperparameter tuning with ex-post guarantees: whatever candidate wins, the privacy cost is only about twice that candidate's budget, even if costlier candidates were tried. This matters because real deployments tune hyperparameters and the privacy budget itself, and existing methods either overpay via composition or only fit simple Laplace/Gaussian noise.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Ex-post RDP theorem (Thm 13) is unproven as written: Lemma 15's proof uses a false intermediate inequality; pure-DP main result appears sound.","rationale":"The reader's conditional verdict is appropriate. The pure-DP hyperparameter-tuning theorem (Theorem 11) has a clean, elementary proof and appears correct; the utility boosting argument (Theorem 12) also checks out. The weak point is the ex-post RDP extension (Theorem 13), and the reader correctly identified Lemma 15 as the load-bearing step. I double-checked the cited counterexample: it indeed refutes the proof's intermediate inequality, though not necessarily the lemma's final statement; in the same example the final RHS is exp(e^{−0.3}) ≈ 2.10, which is larger than the LHS. Thus the theorem may be salvageable, but as written its proof is invalid. Because the abstract's RDP generalization and the Table 3 experiments depend on this unproven theorem, the paper should remain conditional pending a corrected proof or a modified statement.","tokens_in":19953,"tokens_out":22364,"duration_ms":239109,"concrete_test":"Check whether Lemma 15's final inequality fails at its extremal feasible point. For α=2, ε=0.1, ℓ=1, the feasible set forces a ≥ e^{−ε} b^{α/(α−1)} = e^{−0.1} b^2; since the LHS decreases with a, compute M = max_{0<b<1} (1−e^{−0.1}b^2)^2 / (1−e^{−0.2}b). If M > exp(e^{−0.3}), the lemma is false and Theorem 13 collapses. If M ≤ exp(e^{−0.3}), the lemma's statement survives; the manuscript still needs a correct proof because the displayed inequality used in the proof is false and the referenced AM-GM step can have a negative factor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing concern is the proof of the ex-post RDP extension (Theorem 13), which the abstract advertises and the Gaussian/DP-SGD experiments rely on. The proof hinges on Lemma 15. As written, Lemma 15's proof claims\n(1−a)^α (1−e^{−ε(1+ℓ)}b)^{1−α} ≤ exp((α−1)e^{−ε(1+ℓ)}b − αa)\nfor all feasible a,b. This is false: with α=2, ε=0.1, ℓ=1, a=0.01, b=0.1, the hypothesis holds (b^2/a = 1 ≤ e^{0.1}), the LHS is about 1.0675, while the claimed RHS is about 1.0639. The subsequent weighted AM-GM step (⋆) is also invalid as stated because one of the AM-GM factors, (α−1)e^{−εℓ} − αb^{1/(α−1)}, is negative for large b. Consequently the proof of Lemma 15 does not go through, and Theorem 13, which applies Lemma 15 to every j≠i, is unproven as written. The final lemma statement may still be true—the counterexample targets an intermediate bound, not necessarily the lemma's conclusion—but no valid proof is provided. Since the RDP generalization and associated experiments depend on Theorem 13, this is a substantive correctness gap. The pure-DP result (Theorem 11) and the utility bound (Theorem 12) appear sound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies utility-first privacy: instead of fixing a privacy budget up front, the algorithm may try several differentially private estimators and then charge an ex-post privacy loss that depends on the selected output. The main algorithm (Algorithm 3) runs a sequence of mechanisms M_i, randomly drops candidates with probability depending on a shared geometric random variable, and returns the best surviving output. Theorem 11 claims that if M_i is ε_i-DP then the mechanism is ex-post ε̃-DP with ε̃(o,i)=2ε_i+ε' and ε̃(⊥)=0; Theorem 12 gives a utility/boosting guarantee under a weak success-probability assumption. The paper further defines ex-post Rényi DP (Definition 6), proves an ex-post RDP analogue (Theorem 13) using exponential rather than geometric randomness, gives an RDP privacy filter (Algorithm 4, Theorem 16), and reports experiments on analytic workloads and on DP-SGD hyperparameter tuning.","tokens_in":20300,"tokens_out":13445,"duration_ms":140938,"significance":"If all claims held, this would be a substantial generalization of earlier accuracy-first mechanisms of Wu et al. and Whitehouse et al., and of the private-selection results of Liu--Talwar and Papernot--Steinke, with a particularly attractive practical consequence: tuning DP-SGD over many hyperparameter configurations would incur only about twice the winner's budget. The pure-DP theorem (Theorem 11) is genuinely surprising and its proof is elementary and convincing; the utility theorem (Theorem 12) is also sound. The paper is self-contained and does not fit constants to data. The main weakness is that the advertised ex-post RDP extension, on which the Gaussian and DP-SGD experiments rely, is unproven as written because Lemma 15's proof contains a false inequality. Thus the current contribution is solid in the pure-DP setting but incomplete in the RDP setting advertised in the abstract.","major_comments":[{"comment":"The proof of Lemma 15 is invalid. The first displayed bound, (1−a)^α(1−e^{−ε(1+ℓ)}b)^{1−α} ≤ exp((α−1)e^{−ε(1+ℓ)}b − αa), is obtained by applying 1+x≤e^x to the second factor; but since 1−α<0, that application gives a lower bound, not an upper bound. Concretely, take α=2, ε=0.1, ℓ=1, a=0.01, b=0.1. The condition a^{1−α}b^α=1≤e^{0.1} holds, the left-hand side is approximately 1.0675, while the claimed upper bound is approximately 1.0639. The subsequent weighted AM–GM step (⋆) additionally requires (α−1)e^{−εℓ}−αb^{1/(α−1)}≥0, which can fail for large b. Because Theorem 13 applies this lemma to every j≠i, the ex-post RDP theorem is unproven as written. The lemma statement may still be true, but a correct proof or a different argument is needed.","section":"§6.2, Table 3"},{"comment":"The machine-learning experiments and the Gaussian-mechanism experiments in Section 6 use Algorithm 3 with DP-SGD or Gaussian mechanisms, whose privacy accounting goes through Theorem 13 and Lemma 7. Since Theorem 13 is currently unproven, the reported ex-post (ε,10^{-6})-DP guarantees in Table 3 and the comparisons based on them are not supported by the paper's theorems. If the RDP proof cannot be repaired, these experiments should be re-scoped to mechanisms covered by Theorem 11, or explicitly presented as heuristic, with the RDP contribution marked as a conjecture.","section":null}],"minor_comments":[{"comment":"The proof says 'Let A,A′ be the output distributions of Algorithm 3', but Theorem 10 is about Algorithm 2.","section":null},{"comment":"The theorem statement says each M_i has output set O×R, but Algorithm 3 outputs elements of O (together with the index i). This appears to be a typo and should be corrected or clarified.","section":null},{"comment":"In the display after applying Lemma 14, the factors in the product are written with ε_i in place of ε_j (e.g., e^{−ε_i·x}Q_j and e^{−ε_i(1+ℓ_i)}e^{−ε_i·x}Q′_j). The intended arguments should use ε_j, matching the subsequent application of Lemma 15.","section":null},{"comment":"The parameter list says 'Distribution E' but the algorithm samples k∼Geom(e^{−ε′}); the notation should be made consistent, as it is in Algorithm 3.","section":null}],"recommendation":"major_revision","confidential_remarks":"The pure-DP result (Theorem 11) appears correct and is a meaningful contribution on its own. The obstacle to acceptance is the ex-post RDP theorem: Lemma 15's proof is demonstrably wrong, and Theorem 13 and the DP-SGD/Gaussian experiments rest on it. I would request a corrected proof of Lemma 15/Theorem 13 before publication; if the lemma turns out to be false, the RDP claims and the experiments that depend on them should be removed or rescaled to pure-DP guarantees. There are no novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Shorthand: the pure-DP tuning result is the real deal. Algorithm 3 with geometric dropping gives ex-post ε̃-DP with ε̃(o,i)=2ε_i+ε' — you only pay for the winner, no matter how many other ε_j mechanisms you tried. That's a clean generalization of Liu-Talwar and Papernot-Steinke, and the proof is an elementary SVT-style coupling. I checked the algebra in Theorem 11 and it holds. The utility lower bound (Theorem 12) is fine too, and the privacy filter for ex-post RDP (Theorem 16) looks correct.\n\nNow the soft spot, and it's not minor: the ex-post RDP extension (Theorem 13) is unproven as written. The proof hinges on Lemma 15, whose proof uses the inequality (1-a)^α(1-c)^{1-α} ≤ exp((α-1)c - αa) with c = e^{-ε(1+ℓ)}b. That inequality is false. For α=2, ε=0.1, ℓ=1, a=0.01, b=0.1, the LHS is about 1.0675 and the RHS about 1.0639. The subsequent weighted AM-GM step also involves a factor that can be negative for large b. So the proof does not go through. The lemma statement itself might be salvageable — the counterexample targets an intermediate bound, not necessarily the conclusion — but as written there is no valid proof. Since the abstract advertises ex-post RDP and the Gaussian/DP-SGD experiments depend on Theorem 13, this is load-bearing.\n\nSmaller caveats: the application of Lemma 15 in Theorem 13 implicitly uses both directions of RDP; that's standard but should be stated. Table 3 reports averages over 100 trials without error bars or code, so the empirical comparison is suggestive rather than confirmatory. The pure-DP experiments in Table 1 are more informative.\n\nBottom line: this paper deserves a serious referee. The pure-DP result is solid and worth having, and the RDP gap looks fixable — but it needs to be fixed. A referee should ask for a correct proof of Lemma 15 or a clear marking of Theorem 13 as conditional. I'd bring it to reading group either way; the gap is instructive.","headline":"The pure-DP hyperparameter tuning result is correct and worth having; the ex-post RDP extension is unproven as written due to a false step in Lemma 15.","tokens_in":20820,"tokens_out":6241,"would_cite":true,"duration_ms":59378,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A generic selection mechanism makes differential-privacy hyperparameter tuning cost only about twice the privacy budget of the chosen candidate.","keywords":["differential privacy","ex-post DP","hyperparameter tuning","private selection","Rényi differential privacy","random dropping","privacy filter","utility-first privacy"],"falsifier":"Check Lemma 15 numerically: with α=2, ε=0.1, ℓ=1, a=0.01 and b=0.1 (so c=e^{-ε(1+ℓ)}b), the proof's claimed inequality (1-a)^α(1-c)^{1-α} ≤ exp((α-1)c - αa) gives a left-hand side of about 1.0675 and a right-hand side of about 1.0639, so the asserted bound fails. A corrected proof of Theorem 13 or a counterexample to its final bound would settle the paper's RDP claim.","tokens_in":19851,"feed_emoji":"🔒","tokens_out":8580,"duration_ms":92049,"temperature":0.7,"pith_summary":"This paper solves a practical mismatch in differential privacy: instead of fixing a privacy budget up front and hoping utility is enough, a practitioner can fix a utility bar and let the privacy cost be charged after the fact, based on which candidate actually wins. The authors give a generic selection algorithm that runs any sequence of private estimators, randomly drops candidates according to probabilities controlled by a single correlated random variable, and returns the best surviving output. The central guarantee is ex-post: if the winning output came from an estimator with budget ε_i, the realized privacy loss is at most about 2ε_i plus an arbitrarily small extra term, regardless of how many other estimators with larger budgets were run and discarded along the way. This turns hyperparameter tuning—including the choice of the privacy budget itself—into an operation with no additional privacy cost, and the paper demonstrates the benefit on DP-SGD-based machine learning tasks. The pure-DP proof is elementary, but the claimed Rényi-DP extension relies on an inequality (Lemma 15) that is false as stated, so that portion of the paper needs repair.","feed_headline":"Tuning hyperparameters privately costs about 2ε of the winner","feed_subtitle":"Try many private configurations, keep the best, and be charged only for the run that actually wins.","key_machinery":"The central mechanism is correlated random dropping: a single random value k (geometric in the pure-DP case, exponential in the Rényi case) is drawn once and sets the drop probability e^{-ε_i k} for every candidate, so all candidates share one privacy 'clock.' The proof's workhorse is the coupling of k with k+1 (or k+1+ℓ_i) across neighboring datasets, together with the ratio bound Geom_p(u) ≤ p^{u-v} Geom_p(v) for the geometric distribution, which converts the candidate-selection probabilities into the ex-post budget 2ε_i+ε′.","core_discovery":"Algorithm 3 draws one geometric random variable k, then for each candidate mechanism M_i (assumed ε_i-DP) keeps its output with probability e^{-ε_i k}; the final answer is the maximum score among kept outputs, or a special failure symbol if none survive. Theorem 11 states that this mechanism is ex-post ε̃-DP with ε̃(o,i)=2ε_i+ε′ and ε̃(⊥)=0. In words, selecting the best output among multiple differentially private estimators costs at most roughly twice the privacy budget of the estimator that actually produced the chosen output, and trying many configurations—including configurations with larger privacy budgets—does not add to the bill. The proof couples the shared random k to k+1 on neighbo","pith_inferences":["If Theorem 11 stands, the same random-dropping scheme should also select among candidate DP-SGD schedules with different subsampling rates or noise multipliers, as long as each schedule carries an ε_i-DP certificate; that is a direct testable extension the paper does not run.","The monotone AboveThreshold result (Theorem 9) hints that for monotone score functions the factor 2 may be shaved to 1, which would make tuning even cheaper in counting-style workloads; applying the same monotone analysis to Algorithm 3 is a natural next step.","The failure of Lemma 15 does not necessarily kill the RDP extension: the theorem's conclusion could still be true with a sharper bound or a different coupling, so a corrected proof is the concrete open step."],"forward_implications":["Machine-learning practitioners can try many hyperparameter configurations (learning rates, batch sizes, clipping norms, even the privacy budget ε) and keep the best model, paying only about 2ε of the winning configuration instead of a composed sum over all trials.","In analytics-style utility-first tasks, a fixed utility bar (e.g., 10% relative error) can be met by escalating through candidate budgets; the algorithm's ex-post voucher charges only the least noisy output actually released.","Because the selection itself is DP, the chosen model and its score can be published together; the realized budget ε̃(o,i) can be fed into a privacy filter, so the whole interactive session still satisfies an ex-ante DP guarantee.","Repeating each candidate a designed number of times boosts the probability that the final output is 'good' to 1-β (Theorem 12), giving a utility lower bound while keeping the privacy cost tied to the winner.","Empirically, on linear regression, MNIST, and Gisette under DP-SGD, the algorithm's realized ex-post DP cost was lower than the Brownian-motion and doubling baselines in the paper's comparisons."],"supporting_citations":[{"why":"Introduces ex-post DP and the accuracy-first problem; supplies the Laplace-only baseline this paper generalizes.","marker":"Wu et al. [2019]"},{"why":"Brownian-noise reduction for Gaussian mechanisms; another baseline that cannot handle generic estimators.","marker":"Whitehouse et al. [2022]"},{"why":"Private selection from private candidates; the 3ε hyperparameter-tuning result this algorithm improves and generalizes.","marker":"Liu and Talwar [2019]"},{"why":"Optimal 2ε ex-ante tuning and Rényi-DP tuning; the comparison point for Theorems 11 and 13.","marker":"Papernot and Steinke [2022]"},{"why":"Sparse Vector/AboveThreshold technique whose coupling analysis inspires the proofs of Theorems 8-11.","marker":"Dwork et al. [2009]"},{"why":"Defines Rényi DP, used for the proposed ex-post RDP variant and for DP-SGD accounting.","marker":"Mironov [2017]"},{"why":"Privacy filters/odometers; the composition framework extended to ex-post RDP in Theorem 16.","marker":"Rogers et al. [2016]"},{"why":"DP-SGD, the practical mechanism that motivates the general algorithm and appears in the ML experiments.","marker":"Abadi et al. [2016]"}],"fun_headline_variants":["Private tuning: pick best output, pay only ~2× its ε","Ex-post DP: hyperparameter search adds zero privacy cost","Utility-first: try many private models, pay 2ε for the best","Pay for the winner only: ex-post DP for any estimators"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The pure-DP guarantee presupposes that each candidate estimator really is ε_i-DP on its own; the Rényi-DP guarantee additionally presupposes Lemma 15's inequality, which is false as written—so the ex-post RDP claim is unproven until that step is fixed.","fun_headline_variants_meta":{"raw":{"variants":["Private tuning: pick best output, pay only ~2× its ε","Ex-post DP: hyperparameter search adds zero privacy cost","Utility-first: try many private models, pay 2ε for the best","Pay for the winner only: ex-post DP for any estimators"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000771,"raw_usage":{"total_tokens":3280,"prompt_tokens":799,"completion_tokens":2481,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":2406}},"tokens_in":543,"tokens_out":2481,"duration_ms":18653,"temperature":1.0,"reasoning_tokens":2406,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T18:08:15.880720+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check Lemma 15 numerically: with α=2, ε=0.1, ℓ=1, a=0.01 and b=0.1 (so c=e^{-ε(1+ℓ)}b), the proof's claimed inequality (1-a)^α(1-c)^{1-α} ≤ exp((α-1)c - αa) gives a left-hand side of about 1.0675 and a right-hand side of about 1.0639, so the asserted bound fails. A corrected proof of Theorem 13 or a counterexample to its final bound would settle the paper's RDP claim.","supporting_citations":[],"review_version":1}