How Does Selection Leak Privacy: Revisiting Private Selection and
  Improved Results for Hyper-parameter Tuning
Zihang Xiang Chenglong Wang Di Wang
We study the problem of guaranteeing Differential Privacy (DP) in
hyper-parameter tuning, a crucial process in machine learning involving the
selection of the best run from several. Unlike many private algorithms,
including the prevalent DP-SGD, the privacy implications of tuning remain
insufficiently understood. Recent works propose a generic private solution for
the tuning process, yet a fundamental question still persists: is the current
privacy bound for this solution tight?
  This paper contributes both positive and negative answers to this question.
Initially, we provide studies affirming the current privacy analysis is indeed
tight in a general sense. However, when we specifically study the
hyper-parameter tuning problem, such tightness no longer holds. This is first
demonstrated by applying privacy audit on the tuning process. Our findings
underscore a substantial gap between the current theoretical privacy bound and
the empirical bound derived even under the strongest audit setup.
  The gap found is not a fluke. Our subsequent study provides an improved
privacy result for private hyper-parameter tuning due to its distinct
properties. Our privacy results are also more generalizable compared to prior
analyses that are only easily applicable in specific setups.