Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of hyper parameter tuning in the setting of differentially private training of machine learning models. The paper first shows that the hyper parameters used to train a model and the corresponding utility can leak information about training (through experimenting with outliers). They then go on to introduce and analyze ways that would help release DP models trained with the "best" set of hyper parameters, with small privacy leakage. If for hyper parameter tuning, $m$ models are trained with DP, then the leakage for releasing  the best model would be $m\epsilon$ with simple composition. The  method introduced by the paper, however, builds on prior work by Liu&Talwar and improves this to become $2\epsilon$, through randomly choosing and running hyper parameter settings. 
main_review: The problem studied here is a really important one, since it is directly related to actual deployment of DP models in real life settings. The proposed method seems solid and the experimental results look promising. I do have a few clarification questions:

1. How would this method be extended to be used with adaptive search methods? Grid search can be too time consuming/inefficient, especially when used with DP-SGD (as DP-SGD needs per-example gradients that are expensive to obtain) and there are some reinforcement learning based methods that can yield optimal hyper parameters much faster than grid search. Can this method be modified, maybe with a higher privacy expenditure, to be used in those cases?  
 
2. What kind of real-life attack scenario would you envision that could actually use the best models obtained by hyper parameter tuning to extract information. Basically, what type/how much information about a model do the set of optimal hyper parameters leak?


summary_of_the_review: I don't see any major issues with the paper and I find the problem addressed very relevant.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper has made the following contributions. Firstly, this paper illustrates how simply tuning hyperparameters based on non-private training runs can leak private information. Second, this paper provides privacy guarantees for hyperparameter search procedures within the framework of Renyi Differential Privacy. Their results improve and extend the work of Liu and Talwar (STOC 2019).
main_review: This paper considers an interesting and important problem: how hyperparameter tuning on private dataset can leak information, where it provides an intuitive SVM example. The paper then considers how to reduce the leakage. The problem is formalized in the following way: we pick a total number of runs $K$ from some distribution. Then, for each run  $k = 1, 2,\ldots, K$ , we pick an index $j_k \in [m]$ uniformly at random and run $M_{jk}$ . Then, at the end, we return the best of the $K$ outcomes. The paper proposes theoretical guarantees when $K$ comes from truncated negative binomial distribution, or Poission distribution, which strictly generalizes the previous results. Furthermore, it also proposes a new method of computing privacy leakage when $K$ comes from a general distribution, which should be of independent interest. Finally, the paper conducts empirical experiments to show the improvement if the new method.

My only concern for this paper is the problem formalization. First, for the current problem formulation, it is possible that the same parameter will be tried multiple times, which is definitely a waste of privacy. Not sure whether people will do it in practice. Second, the paper assumes the following scheme satisfies DP: randomly choose $j \in [m]$, and run $M_j$. Note that this is not equivalent with assuming each $M_j$ is DP, where the latter is more realistic. For example, in the hyperparameter tuning of DP-SGD, it easily holds that each run (with different clipping norm) satisfies DP. However, it is not clear to me whether randomly selecting one clipping norm, and then running DP-SGD is differentially private. The authors need to justify the relationship between these two assumptions. Naively speaking, the second can not lead to the first assumption. Please correct me if I miss something.
summary_of_the_review: Generally speaking, I recommend acceptance of this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides an considerable improvement to the DP analysis of hyperparameter tuning of DP algorithms (such as DP-SGD). The analysis is carried out using Rényi differential privacy (RDP), and the DP bounds are RDP bounds that contain the RDP parameters of the underlying mechanisms (that give the private candidates). Most importantly, the paper considerably improves the state-of-the-art of Liu and Talwar (2019). Also, a nice counterexample using SVMs is constructed, that shows the importance of this problem.

main_review: The paper is very well written and the analysis seems solid (though I did not check every line). The problem is important and the paper improves the state-of-the-art so its merits are clear.

My only critique:

As emhpasised in Sec. 3.2, the ‘strawman approach’ of fixing m does not work for pure eps-DP. However, I find this a bit misleading since you are not observing (eps,0)-DP of hyperparameter tuning but (eps,delta) (or RDP). So the delta might actually play a crucial role here. Allowing bit of delta in the DP bound, the randomness in choosing the number of repetition might perhaps be not that crucial. Or vice versa, in (eps,0), you would not get great gains from that randomness.

I suspect that this fact that you have to have the randomness in the number of repetitions actually is a requirement of the RDP analysis that you carry out. As far as I see, in Proposition 17 you claim it is not, but I do not fully see why that would be the case. The result of Proposition 17, i.e., that the RDP of k repetitions is not RDP for less than eps’(lambda), does not really give a ‘counter-example’ in the same  way as that result for pure epsilon. For example, suppose the underlying mechanism is eps=0.5 - DP. Then, you choose lambda = 1.9483. Then, eps - (log(1+exp(-eps))/(lambda-1)) ~ 1e-4 in which case the bound does not really say anything even for quite large numbers of k. And you can of course make that bound arbitrarily small by choosing lambda appropriately. I.e., if you let delta > 0, I think there is room for tighter analysis also for fixed k.

Could you comment on this tradeoff between lambda and eps in the bound of Proposition 17?

Could you give more intuition on why the randomness in number of repetitions k would be crucial or some other example that illustrates this?

Other:
- There is something strange at the bottom of p. 22: equation going over the line.

summary_of_the_review: All in all I think this is a very nice analysis and improves the state-of-the-art. Also, this is a very important problem. With small modifications I think this ought to be accepted. My only critique: I am just not entirely convinced that randomness in the number of repetitions is crucial for having tight bounds for DP hyperparameter tuning, I hope the authors can clarify my concerns.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The authors make the following contributions regarding differentially private hyperparameter tuning :
* As an example, the authors train an SVM with a weight penalty and show that, in presence of an outlier, a membership inference attack can be employed to infer from the hyperparameter whether or not the outlier was a part of the training set.
*The authors provide an algorithm for private hyperparameter tuning, which consists of running a learning algorithm that satisfies Rényi differential privacy (RDP) for a *random* number of times ($K$), each with a hyperparameter drawn uniformly at random from a finite candidate set. The authors first prove RDP guarantees of the algorithm when $K$ is sampled from a truncated negative binomial distribution and Poisson distribution. Then they proceed to prove RDP guarantees for any distribution of $K$ supported on $\mathbb{N}\cup \{0\}$ ¹.
The authors propose a way to measure the utility of the algorithms by looking at the expected quantile of the output. The results of their utility analysis, coupled with an experiment on MNIST, show that the algorithm with Poisson distribution performs better than those proposed by Liu and Talwar (2019) in an intermediate range of privacy budget ($\varepsilon$).

¹ From what I understand, we can obtain a tighter generic bound by going through the proof of Lemma 7. But the authors opt to use (7) since the postprocessing often leads to a bound that is independent of $q$ and $q'$ when plugging in a specific distribution.

main_review: DP-focused machine learning systems would benefit from this work, as most of them require hyperparameter tuning. The algorithms provided in this work help us avoid a large cost of composition and perform tuning at much smaller privacy loss. In addition, the generic bound allows us to be flexible on the distribution of the number of runs ($K$), though it requires some effort to translate the logarithmic term into something usable. I have checked all the proofs and there are no critical errors.

The authors have sufficiently compared their method with previous approaches. Specifically, using the main results, the authors show that their method extends and improves upon the work of Liu and Talwar (2019). The authors also compare their method with the exponential mechanism-based method (Gupta et al., 2010; Theorem 10.2) and show in Section D.4 that both methods have the same lower bounds of the utility guarantees up to constants.

Nonetheless, the authors might want to compare their method with the noise perturbation method proposed by Chaudhuri et al. (2013). This method requires the “stability” condition on the training procedure, which might not be tractable for neural networks. But for linear classifiers, the algorithm (Algorithm 1) only adds noises of size $O(1/n\varepsilon)$ to the scores, which is quite attractive for training on large datasets.

The paper is mostly written with DP-SGD in mind, but it does not consider when the model's evaluation on a hold-out validation set is incorporated in the base algorithm $Q$, which is a common practice in training an ML model. From an application point of view, the authors might want to discuss a bit how the model’s evaluation (in classification or regression) can be made DP or RDP as a part of $Q$. 

I see that distributions with finite support (e.g. the truncated binomial) are not considered in this study. But in practice, one might want to limit the number of hyperparameter searches (e.g. due to computational constraints), so such distributions might come into play. Have the authors performed some experiments on these against the truncated negative binomial and Poisson distribution? I wonder if the privacy-utility tradeoff is better when restricting to finite support.

Could the authors comment on how to determine an appropriate size of the candidate set ($m$)? A simple heuristic is $m=\mathbb{E}[K]$ but the authors might have something better in mind.

### **Specific comments**
* Page 2: In Eq (2), the special case where $\lambda=1$ should be mentioned here, as it is also in the range of $\hat\lambda$ in the main results.
* Page 6: When I tried to derive (6) from (5), I got an extra $-\rho\eta$ term from rewriting
$$\epsilon+\rho(\lambda-1)+(1+\eta)\left(1-\frac1{\hat\lambda}\right)\hat\epsilon=\rho\lambda+\rho(1+\eta)(\hat\lambda-1)=\rho(\lambda-1)+\rho\hat\lambda(1+\eta)-\rho\eta,$$
combining this with the rest of the terms, and then choosing $\lambda$ and $\lambda'$ so that the equality holds in the following inequality:
$$ \left(\rho(\lambda-1) + \frac{\log\mathbb{E}[K]}{\lambda-1} \right)+\left(\rho\hat\lambda(1+\eta) + \frac{(1+\eta)\log(1/\gamma)}{\hat\lambda}\right)- \rho\eta \\
  \geq  2\sqrt{\rho\log\mathbb{E}[K]} +2(1+\eta)\sqrt{\rho\log(1/\gamma)}-\rho\eta. $$
To clarify this, I think the authors should provide the proof of Corollary 4 somewhere in the Appendix, as I find the bound to be non-trivial.
* Page 7: In Lemma 7, “$q$ and $q'$ are arbitrary probabilities” is misleading. When I saw the statement for the first time, I read this as “$q$ and $q'$ can be anything in $[0,1]$”, but the proof indicates that they take specific forms in order for the Lemma to hold true. One way to resolve this issue is by directly stating the definition of $q$ and $q'$ after (7).
* Line 1-2 in Page 8:
> Vaguely, $f'$ being smooth corresponds to the distribution $K$ being spread out (i.e. far from being a point mass).    
>
This is not true; if $X$ is a point mass at $1$ i.e. $\Pr{[X=1]}=1$, then the PGF of $X$ is $f(x)=x$, and so $f'(x)=1$ which is smoother than any polynomial.  
Looking at the definition of PGF, the smoothness of $f'$ should depend on the right-tail heaviness of the distribution of $K$. Specifically, a heavier right tail corresponds to a faster growth rate of $f'$, which in turn leads to a larger RHS of Eq. (7) when $q > q'$. This observation is in line with the privacy-utility tradeoff: more probabilities of sampling a large $K$ (i.e. more utility) lead to a larger privacy loss.
* Page 18: when $p=r=\infty$, then the value of $r/p$ is unclear. What is the convention for this case?
* Page 23: It is mentioned below the definition of $Q,Q',A,A'$ that “the total ordering prefers the first option (corresponding to the first coordinate probability)” which should refer to the ones with the probabilities $1-b-c$ and $1-b'-c'$. In other words, we assume that $1-b-c>b$ and $1-b'-c'>b'$. However, the approximations below suggest that $b>c>1-b-c$ and $b'>c'>1-b'-c'$.
* Page 25: The proof of Lemma 20 is missing. Does it appear in Bun & Steinke (2016)?

### **Minor corrections**
* Page 6: In Remark 5: “$(\lambda_2,\varepsilon)$-RDP implies $(\lambda_2,\varepsilon)$-RDP” $\rightarrow$ “$(\lambda_2,\varepsilon)$-RDP implies $(\lambda_1,\varepsilon)$-RDP” and “ann” $\rightarrow$ “any”.
* Page 14: In the footnote, “experssion” $\rightarrow$ “expression”
* Page 16: In the definition of $g(y)$, $t$ should be $t^*$.
* Page 21: In the third display equation, the equal sign should be replaced with $>$.
* Page 23: First line in Section D.4: “hyperparamter” $\rightarrow$ “hyperparameter”

### **References**
Bun, M., & Steinke, T. (2016). Concentrated differential privacy: Simplifications, extensions, and lower bounds. TCC'16.  
Chaudhuri, K., & Vinterbo, S.A. (2013). A Stability-based Validation Procedure for Differentially Private Machine Learning. NIPS'13.  
Gupta, A., Ligett, K., McSherry, F., Roth, A., & Talwar, K. (2010). Differentially private combinatorial optimization. SODA '10.  
Liu, J., & Talwar, K. (2019). Private selection from private candidates. STOC'19.

summary_of_the_review: This work provides careful privacy and utility analysis of private algorithms for hyperparameter tuning. All of the analyses and the proofs are sound, and the experiments give good comparisons between various distributions.  To make the methods widely applicable, the authors might want to comment on how the model’s evaluation on a hold-out validation set can be integrated into the DP workflow. Overall, this is a strong paper and I recommend it for publication.
review_title: null

Meta-review: This paper tackles a problem at the intersection of AutoML and trustworthiness that has not been studied much before, and provides a first solution, leaving much space for a lot of interesting future research.
All reviewers agree that this is a strong paper and clearly recommend acceptance.
I recommend acceptance as an oral since the paper opens the door for a lot of interesting follow-ups.
Decision: Accept (Oral)