Private selection mechanisms (e.g., Report Noisy Max, Sparse Vector) are
fundamental primitives of differentially private (DP) data analysis with wide
applications to private query release, voting, and hyperparameter tuning.
Recent work (Liu and Talwar, 2019; Papernot and Steinke, 2022) has made
significant progress in both generalizing private selection mechanisms and
tightening their privacy analysis using modern numerical privacy accounting
tools, e.g., R\'enyi DP. But R\'enyi DP is known to be lossy when
$(\epsilon,\delta)$-DP is ultimately needed, and there is a trend to close the
gap by directly handling privacy profiles, i.e., $\delta$ as a function of
$\epsilon$ or its equivalent dual form known as $f$-DPs. In this paper, we work
out an easy-to-use recipe that bounds the privacy profiles of ReportNoisyMax
and PrivateTuning using the privacy profiles of the base algorithms they
corral. Numerically, our approach improves over the RDP-based accounting in all
regimes of interest and leads to substantial benefits in end-to-end private
learning experiments. Our analysis also suggests new distributions, e.g.,
binomial distribution for randomizing the number of rounds that leads to more
substantial improvements in certain regimes.

本研究通过使用 Rényi DP 等现代数值隐私核算工具，提出了一种易于使用的方法来限制 ReportNoisyMax 和 PrivateTuning 的隐私特性，并在端到端的隐私学习实验中取得了显著的改进。同时，分析结果还指出了在特定领域中使用二项分布来随机化回合数可以获得更大的改进。