Pith. sign in

REVIEW 2 major objections 4 minor 32 references

Private Hyperparameter Tuning with Ex-Post Guarantee

T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A generic selection mechanism makes differential-privacy hyperparameter tuning cost only about twice the privacy budget of the chosen candidate.

desk verdict 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. read the letter →

arxiv 2508.15183 v1 pith:HIEQZAE3 submitted 2025-08-21 cs.CR cs.DS

Badih Ghazi , Pritish Kamath , Alexander Knop , Ravi Kumar , Pasin Manurangsi , Chiyuan Zhang This is my paper · ORCID
classification cs.CRcs.DS MSC 68P27
keywords differentialprivacyex-postDPhyperparametertuningprivateselectionRényirandomdroppingfilterutility-first
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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+ε′.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [§6.2, Table 3] 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.
  2. 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.
minor comments (4)
  1. The proof says 'Let A,A′ be the output distributions of Algorithm 3', but Theorem 10 is about Algorithm 2.
  2. 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.
  3. 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.
  4. 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the tuning guarantee is derived from DP definitions by explicit coupling; the sole self-citation is background. A correctness gap in the RDP proof (Lemma 15) is not a circularity.

full rationale

I walked the paper's derivation chain. The main pure-DP results (Theorems 8, 10, 11) are proved by standard coupling arguments: for neighboring datasets, the geometric threshold noise is coupled as k vs. k+1, and the ε_i-DP of each base mechanism is used to bound the ratio of output probabilities. The final bound e^{2ε_i+ε'} is obtained by direct algebra from these inequalities, not by assuming the conclusion. The utility-boosting theorem (Theorem 12) is independent of the privacy proof and uses only a Markov-type failure-probability calculation. The ex-post RDP definition (Definition 6) is a definition; it is not secretly an input to the theorem. No fitted parameter is renamed as a prediction, no known result is merely renamed, and no uniqueness theorem is imported from prior work by the same authors. The only self-citation I found is [Ghazi et al., 2022], used in the introduction as an illustrative example of a utility requirement ('relative error of the estimated population is small'); it is background, not load-bearing. I did identify a serious correctness issue in Section 4.2: the proof of Lemma 15 claims that 'From 1 + x ≤ e^x for all x ∈ R, the LHS is at most exp((α − 1)e^{−ε(1+ℓ)}b − αa).' Since 1−α < 0, the factor (1−e^{−ε(1+ℓ)}b)^{1−α} is lower-bounded, not upper-bounded, by e^{(α−1)e^{−ε(1+ℓ)}b}; thus the displayed inequality has the wrong direction and the proof of Lemma 15 does not go through as written. This makes Theorem 13, which applies Lemma 15, unproven as written. That is a mathematical correctness gap, not circularity: the theorem is not being derived from its own conclusion, nor is any fitted quantity being relabeled as a prediction. Accordingly, the circularity score is low, reflecting only the presence of a non-load-bearing background self-citation.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central pure-DP claim relies only on standard DP definitions and the Geometric distribution property. The RDP extension additionally relies on Lemma 15, which is unproven as written. No new entities or mediators are introduced.

free parameters (3)
  • ε' = user-chosen (e.g., 0.01 in experiments)
    Additional privacy budget parameter in Algorithms 2-4; appears in the ex-post bounds as additive ε' and controls the geometric/exponential distribution of the correlated randomness.
  • ℓ_i = user-chosen; can be optimized per i
    Introduced in Theorem 13 to tune the RDP bound; appears in the coupling shift and the final ε̃ expression.
  • α = user-chosen Rényi order
    RDP order parameter in Theorems 13 and 16 and Lemma 7; the experiment must choose it for the conversion to (ε,δ)-DP.
assumptions (5)
  • standard math Standard definitions of pure, approximate, and Rényi DP, with the neighboring relation quantified over ordered pairs
    Used throughout Definitions 1-6; the symmetric reading of RDP is required for the application of Lemma 15 in Theorem 13.
  • domain assumption Mechanisms Mi are ex-ante εi-DP (pure) or (α,εi)-RDP
    Stated in Theorems 10-13; the algorithms take these mechanisms as black boxes.
  • domain assumption Output set O is totally ordered
    Algorithm 3 returns the maximum element; the proofs use the order to define the bad events U^j_{o,i}.
  • ad hoc to paper Lemma 15 (as used in Theorem 13)
    The proof of this lemma in Section 4.2 is invalid: the claimed inequality is false for α=2, ε=0.1, ℓ=1, a=0.01, b=0.1. Theorem 13 directly invokes this lemma, so the RDP result is not proven as written.
  • domain assumption Existence of a 'good' candidate with probability at least α (Theorem 12)
    Utility guarantee assumes some Mi* has Pr[Mi*(D) ≥ o*] ≥ α; this is a utility assumption, not a privacy assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Private Hyperparameter Tuning with Ex-Post Guarantee." pith.science (2026). https://pith.science/paper/HIEQZAE3

@misc{pith2026250815183,
  author       = {Pith},
  title        = {Pith review of: Private Hyperparameter Tuning with Ex-Post Guarantee},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HIEQZAE3}},
  note         = {Machine review of arXiv:2508.15183}
}
read the original abstract

The conventional approach in differential privacy (DP) literature formulates the privacy-utility trade-off with a "privacy-first" perspective: for a predetermined level of privacy, a certain utility is achievable. However, practitioners often operate under a "utility-first" paradigm, prioritizing a desired level of utility and then determining the corresponding privacy cost. Wu et al. [2019] initiated a formal study of this "utility-first" perspective by introducing ex-post DP. They demonstrated that by adding correlated Laplace noise and progressively reducing it on demand, a sequence of increasingly accurate estimates of a private parameter can be generated, with the privacy cost attributed only to the least noisy iterate released. This led to a Laplace mechanism variant that achieves a specified utility with minimal privacy loss. However, their work, and similar findings by Whitehouse et al. [2022], are primarily limited to simple mechanisms based on Laplace or Gaussian noise. In this paper, we significantly generalize these results. In particular, we extend the work of Wu et al. [2019] and Liu and Talwar [2019] to support any sequence of private estimators, incurring at most a doubling of the original privacy budget. Furthermore, we demonstrate that hyperparameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost. Finally, we extend our results to ex-post Renyi DP, further broadening the applicability of utility-first privacy mechanisms.

Figures

Figures reproduced from arXiv: 2508.15183 by the authors.

Figure 1
Figure 1. A plot of the standard deviation vs expectation of the number of invocations of a mechanism by the [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 29 canonical work pages

  1. [1]

    Abadi, A

    M. Abadi, A. Chu, I. J. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In CCS, pages 308--318, 2016

    work page 2016

  2. [2]

    URL https://github.com/pytorch/examples/tree/e9a4e7510c89613a2fe75312fba1fb8c14b3b376/mnist

    Basic MNIST Example. URL https://github.com/pytorch/examples/tree/e9a4e7510c89613a2fe75312fba1fb8c14b3b376/mnist. The example of MNIST written using PyTorch

    work page

  3. [3]

    Bun and T

    M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In TCC, pages 635--658, 2016

    work page 2016

  4. [4]

    Z. Ding, Y. Wang, Y. Xiao, G. Wang, D. Zhang, and D. Kifer. Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms. VLDB J. , 32 0 (1): 0 23--48, 2023. doi:10.1007/S00778-022-00728-2. URL https://doi.org/10.1007/s00778-022-00728-2

    work page doi:10.1007/s00778-022-00728-2 2023

  5. [5]

    Dwork, M

    C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381--390, 2009

    work page 2009

  6. [6]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. JPC, 7 0 (3): 0 17--51, 2016

    work page 2016

  7. [7]

    Feldman and T

    V. Feldman and T. Zrnic. Individual privacy accounting via a R \' e nyi filter. In NeurIPS, pages 28080--28091, 2021

    work page 2021

  8. [8]

    Ghazi, B

    B. Ghazi, B. Kreuter, R. Kumar, P. Manurangsi, J. Peng, E. Skvortsov, Y. Wang, and C. Wright. Multiparty reach and frequency histogram: Private, secure, and practical. PETS, 2022 0 (1): 0 373--395, 2022

    work page 2022

Show all 32 references
  1. [9]

    Guyon, S

    I. Guyon, S. Gunn, A. Ben-Hur, , and G. Dror. Gisette . UCI Machine Learning Repository, 2004. DOI : https://doi.org/10.24432/C5HP5B

    2004 doi

  2. [10]

    Hod and R

    S. Hod and R. Canetti. Differentially private release of Israel's national registry of live births. In S & P, pages 101--101, 2025

    2025

  3. [11]

    Koufogiannis, S

    F. Koufogiannis, S. Han, and G. J. Pappas. Gradual release of sensitive data under differential privacy. JPC, 7 0 (2), 2016

    2016

  4. [12]

    Lebensold, D

    J. Lebensold, D. Precup, and B. Balle. On the privacy of selection mechanisms with Gaussian noise. In AISTATS, pages 1495--1503, 2024

    2024

  5. [13]

    LeCun, C

    Y. LeCun, C. Cortes, and C. Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, 2, 2010

    2010

  6. [14]

    L \' e cuyer

    M. L \' e cuyer. Practical privacy filters and odometers with R \' e nyi differential privacy and applications to differentially private deep learning. arXiv:2103.01379, 2021

    2021 arXiv

  7. [15]

    Liu and K

    J. Liu and K. Talwar. Private selection from private candidates. In STOC, pages 298--309, 2019

    2019

  8. [16]

    McSherry and K

    F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94--103, 2007

    2007

  9. [17]

    Mehta, A

    H. Mehta, A. G. Thakurta, A. Kurakin, and A. Cutkosky. Towards large scale transfer learning for differentially private image classification. TMLR, 2023

    2023

  10. [18]

    I. Mironov. R \' e nyi differential privacy. In CSF, pages 263--275, 2017

    2017

  11. [19]

    Papernot and T

    N. Papernot and T. Steinke. Hyperparameter tuning with R\'enyi differential privacy. In ICLR, 2022

    2022

  12. [20]

    R. M. Rogers, S. P. Vadhan, A. Roth, and J. R. Ullman. Privacy odometers and filters: Pay-as-you-go composition. In NIPS, pages 1921--1929, 2016

    1921

  13. [21]

    R. M. Rogers, G. Samorodnitsky, Z. S. Wu, and A. Ramdas. Adaptive privacy composition for accuracy-first mechanisms. In NeurIPS, 2023

    2023

  14. [22]

    X. Tang, A. Panda, M. Nasr, S. Mahloujifar, and P. Mittal. Private fine-tuning of large language models with zeroth-order optimization. arXiv:2401.04343, 2024

    2024 arXiv

  15. [23]

    Buzz prediction in online social media

    The AMA Team at Laboratoire d'Informatique de Grenoble, 2017. Buzz prediction in online social media

    2017

  16. [24]

    Decennial census of population and housing disclosure avoidance, 2023

    US Census Bureau . Decennial census of population and housing disclosure avoidance, 2023. URL https://www.census.gov/programs-surveys/decennial-census/decade/2020/planning-management/process/disclosure-avoidance.html

    2023

  17. [25]

    V \"o lske, M

    M. V \"o lske, M. Potthast, S. Syed, and B. Stein. TL ; DR : Mining R eddit to learn automatic summarization. In Proc. Workshop on New Frontiers in Summarization, 2017

    2017

  18. [26]

    Vu and A

    D. Vu and A. B. Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In ICDM Workshops, pages 138--143, 2009

    2009

  19. [27]

    Whitehouse, A

    J. Whitehouse, A. Ramdas, Z. S. Wu, and R. M. Rogers. Brownian noise reduction: Maximizing privacy subject to accuracy constraints. In NeurIPS, 2022

    2022

  20. [28]

    R. J. Wilson, C. Y. Zhang, W. Lam, D. Desfontaines, D. Simmons - Marengo, and B. Gipson. Differentially private SQL with bounded user contribution. PETS, 2020 0 (2): 0 230--250, 2020

    2020

  21. [29]

    Z. S. Wu, A. Roth, K. Ligett, B. Waggoner, and S. Neel. Accuracy first: Selecting a differential privacy level for accuracy-constrained ERM . JPC, 9 0 (2), 2019

    2019

  22. [30]

    Yousefpour, I

    A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Mironov. Opacus: U ser-friendly differential privacy library in PyTorch . arXiv:2109.12298, 2021

    2021 arXiv

  23. [31]

    D. Yu, H. Zhang, W. Chen, J. Yin, and T. Liu. Gradient perturbation is underrated for differentially private convex optimization. In IJCAI, pages 3117--3123, 2020

    2020

  24. [32]

    D. Yu, S. Naik, A. Backurs, S. Gopi, H. A. Inan, G. Kamath, J. Kulkarni, Y. T. Lee, A. Manoel, L. Wutschitz, et al. Differentially private fine-tuning of language models. JPC, 14, 2024

    2024

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.