Practical Differentially Private Hyperparameter Tuning with Subsampling

Summary

The paper focuses on the problem of differentially private (DP) hyperparameter tuning for DP ML algorithms. The authors propose a method that subsamples the sensitive data for hyperparameter tuning, and extrapolates optimal values from the small dataset to the larger dataset. The authors provide a Renyi DP (RDP) analysis for their method, show that their method lowers the DP bound and computational complexity of hyperparameter tuning, and empirically show their method leads to better privacy-utility trade-offs than the existing SOTA method.

Strengths

1. The paper focuses on improving private hyperparameter tuning from all facets: using subsampled inputs to save on privacy cost, using the model output by the tuned choices for initializing the training over the larger dataset, as well as extrapolating optimal values for various hyperparameters from the smaller dataset to the larger dataset. 2. The paper is well written.

Weaknesses

Though the authors discuss this in Section 6, I feel one of the main shortcomings of the proposed method is the extrapolation heuristics designed specifically for DP-SGD. Having the method being applicable to commonly used adaptive optimizers (also discussed in Section 6) would make it more general.

Questions

I have listed the main limitation I felt in the weaknesses section. ------------ Post-rebuttal update: It is great to see the authors being able to provide guidance on DP-Adam using their tuning! I am raising my score since this addresses my main concern for the paper.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

This paper is about the efficient tuning of hyperparameters of machine learning models in a differentially private (DP) way. Previous works have shown that hyperparameter optimization can be computationally demanding and, more importantly, often uses sensitive data that might get leaked. However, this leakage can be reduced. Specifically in this paper, the authors aim for lowering not only the DP bounds but also the computational demand. The latter is achieved by only using a random subset of data for the hyperparameter optimization. As in previous work, a Rényi DP analysis is provided. Experiments under various settings and data sets demonstrate a better privacy-performance trade-off than baseline competitors while also being faster.

Strengths

- the problem of having efficient differentially private strategies for hyperparameter optimization is relevant and important - using subsampling to improve the computational efficiency and using its privacy amplifying effect is natural - the paper is mostly easy to read and follow (there are some issues, see below) - the theoretical analysis and experimental evaluation shows that either a better performance for the same privacy budget or a better privacy budget for the same performance can be achieved - the approach is computationally less demanding than previous works

Weaknesses

Overall, the paper appears to be solid, however, I think the paper lacks (a bit of) clarity. Some concepts (e.g., extrapolating hyperparameters) are insufficiently or too late introduced and other choices such as the training on all data but the previously used subset are insufficiently justified. Similar clarity issues appear for the mathematical notation. Moreover, the language should be revised/improved. However, I believe that those issues can be fixed. For almost all points, I provide a list of remarks, suggestions, and questions below. ### Remarks: - Section 1.1: Using subsets for hyperparameter tuning specifically for deep learning models (in a non-DP setting) was also recently considered, e.g., in: - Killamsetty, K., Durga, S., Ramakrishnan, G., De, A., & Iyer, R. (2021, July). Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning (pp. 5464-5474). PMLR. - Killamsetty, K., Abhishek, G. S., Lnu, A., Ramakrishnan, G., Evfimievski, A., Popa, L., & Iyer, R. (2022). Automata: Gradient based data subset selection for compute-efficient hyper-parameter tuning. Advances in Neural Information Processing Systems, 35, 28721-28733. - Definition 2: How is $\mathcal{M}$ an output distribution? - Theorem 4: Consider mentioning/introducing $\gamma$ for completeness. - line 106: I consider "number of candidate models $K$" is sub-optimally phrased. A hyperparameter can also be the learning rate, which does not change the model, but the optimization/learning of it. Perhaps something like "the number of runs $K$ within the hyperparemeter tuning" is clearer? This related to my first minor remark (lines 4-5). - Theorem 5: The notation $\mathcal{X}^N$ was used in Papernot and Steinke but the superscript $N$ was not introduced in this paper. Besides, $n$ instead of $N$ was used. Moreover, $\mathcal{Y}$ denotes the outputs in Papernot and Steinke whereas in this paper, $\mathcal{O}$ was used! - line 128: How is $\mathcal{M}_1$ different from $A$ in Theorem 5? Both are "hyperparameter tuning algorithms". - line 130: Aren't $\theta_1$ the model *parameters* instead of the model itself? In Equation (2.3), $f$ is the model with parameters $\theta$. - Equation (3.1): $\mathcal{M}_1(X_1)$ returns a tuple but in Equation (3.1) it is assumed that it only returns the second entry of that tuple. Besides, the output of $\mathcal{M}(X)$ would then be $((\theta_1, t_1), \theta_2)$. - Theorem 6: The notation $\mathcal{X}^n$ was never introduced. Besides, if a data set $X$ is an element of $\mathcal{X}$, then a single data point $x$ cannot be. Instead, it should be $x$ in curly brackets, no? - Lemma 9: First, $C$ was used as a scalar within the clipping strategy. Hence, the variable name cannot be used anymore for something else. Second, $\mathcal{M}$ never took $t$ as an argument before. Consider adapting the notation. ### Minor remarks and suggestions: - lines 4-5, 35-36: I think "where the number of random search samples is randomized itself" could be stated more clearly. - line 21, 96, 105, 107, 253, 280: however, - line 34: "provided a" instead of "gave" (there should be an a) - lines 53, 56, 225: w.r.t. the number - line 54: "than" instead of "then" - line 56: In a non-DP - line 74: curly brackets for sets - line 85: "As is common in practice," - line 87 (and others): Equation (2.2) - line 90: to have an $L_2$-norm of at most - Equation (2.3): Consider mentioning $f$ and $\theta$ for completeness. You could also connect $Z_j$ with the noise mentioned in line 90. - line 95, 106, 171: Wrong citation style (direct instead of indirect, i.e., by Zhu and Wang, (2019)). - line 97: If you want to gain space you can try adding `\looseness=-1` after "method." which tells $\LaTeX$ to try to fit "method." into the paragraph. Might also work for the caption of Figure 3. It is a neat trick worth knowing. - line 124: Inconsistent capitalization: Method should be capitalized - line 129: the method by - line 134: either use or consider - Consistency: "dataset" vs "data set" (e.g., lines 131 vs 134) - line 135: Math (Equation (3.2)) is always a part of a sentence. Hence, use rather a colon instead of a full-stop. - line 136: , respectively - line 137: with a standard [...] Theorem 4 - line 142: The number of iterations $T$ appear for the first time. Consider introducing them earlier, i.e., around lines 89-97. - line 165: Adam is an ICLR paper, not a preprint. - line 169: the learning rate - Consistency: "Thm." vs "Theorem" (e.g., lines 173 vs 212) - line 193-194: methods [...] as functions - line 194: mechanism DP-SGD is run - It is slightly confusing to mix "variants 1 and 2" and "(3.1) and (3.2)". - Figure 1: the three dashed lines between "our method" and "variant" might be confusing in black and white prints since they look like the blue curve. The crossing of lines around $q=0.1$ could be highlighted with an arrow. - Consistency: $E$ vs E in lines 202-204. - [Section 4.1 (but also before): It is slightly weird that some lines are missing line numbers.] - Section 5: Please name briefly at least the data sets and the learning task. Space can be gained be vertically shrinking Figures 2 and 3. - line 245: on the - line 247: 1150 and 1278, respectively. - line 251: Next, - line 254: typo in hyperparameter - Figure 2: What about "$6.06 \times$ slower"? Perhaps that is more clear/less confusing. - Figure 2 caption: Figure 4 (appendix) shows a more detailed version of this figure. - line 273: e.g. already means for example - line 276: "question is" or "questions are" - line 280: remove on - Tables: Captions go above tables and vertical lines should be avoided, see https://media.neurips.cc/Conferences/NeurIPS2023/Styles/neurips_2023.pdf ### After the Rebuttal: I have read all other reviews and all rebuttals. Furthermore, I thank the authors for their answers and the additional insights provided in the extra rabuttal pdf. I keep my original score.

Questions

- Q1: What is meant by "extrapolate the hyperparameter values to a larger dataset"? Can you provide an example? It is mentioned multiple times (lines 10, 43, 123, 131, ...) and I think it should be clarified (earlier). If the main example is in lines 140-146, I think it might help to tease it earlier as I was unsure what might be meant by extrapolating. Additionally, is there another example of extrapolation of hyperparameters? - Q2: Why is $X_1$ being excluded from $X$ in step 4 in line 132? I see the second variant as being meaningful but what is the motivation/intuition/reasoning behind variant 1? - Q3: Regarding the adjustment of the learning rate (lines 140-146): Didn't van der Veen et al. (2018) consider a change in batch size with a fix data set size? If the same batch size is used for the subsampled data set and the data set, it should not matter, or? - Q4: I am slightly confused by the difference of $\gamma$ and $q$, i.e., in Theorem 4 (and lines 193-197). My understanding is that $\gamma$ is for the batch and $q$ is for the subset $X_1$ (line 126). Can you clarify the difference between $\gamma$ and $q$? - Q5: Can you elaborate on how Figure 1 was created? As in, where do the numbers come from and how do the specific choices (title of the subfigures) go into that? - Q6: Can you elaborate on what is shown in Figures 2 and 3? Is the complete hyperparameter optimization cycle run ten times and the figures show the averaged test accuracies of the final models (i.e., the ten models with the best hyperparameters)? What are the individual dots per line? - Q7: The choice of $\mu$ is fixed for Figure 2 but quite differs in Figure 3. CIFAR-10 is harder than MNIST but has less "candidate models". How did you come up with those $\mu$ values? Does CIFAR-10 has the smallest $\mu$ because it uses a pre-trained model and all others are trained from scratch? - Q8: How is the choice of Adam (DP-SGD gradients) justified when the results only hold for DP-SGD? Did IMDB not work with DP-SGD? What was the reason for this choice? - Q9: Can you provide a table with data set sizes (and dimensionalities) as well as the used subset sizes? - Q10: Regarding the computational savings it is stated that the number in the plots next to baseline refers to the mean training time of the baseline scaled wrt the minimum of the variants. Can you provide more insight in those computational savings? Is it just the worst performing model on the smallest subset that yielded this saving once? Are your variants sometimes even slower than the baseline? Is there a substantial difference between the variants?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

Limitations and potential negative societal impact are discussed.

Summary

This work proposes a practical variant of tuning hyperparameters under differential privacy (DP) which has a better privacy-utility tradeoff and less computational time compared to the SOTA private hyperparameter tuning algorithm. Instead of using all datasets to tune hyperparameters as in previous works, this work proposes to use a subsampled dataset for hyperparameter tuning and provides a Renyi DP (RDP) analysis of the proposed approach. In addition, this work considers tuning hyperparameters that can affect the privacy loss. Both theory and experimental results demonstrate the superior performance of the proposed approach in terms of the utility-privacy tradeoff and computation time.

Strengths

Clear and well-structured presentation. Simple yet effective approach. Interesting results.

Weaknesses

There are a few confusing points. See questions below.

Questions

There is no description of the subsampling ratio $\gamma$. Is $\gamma$ the subsampling ratio for selecting minibatches in DP-SGD? Regarding figure 1: - Are the blue curves generated by taking max{Eq.(3.6), Eq.(3.7)} in Theorem 6? - What is the alpha used here? - Since the caption says “($\epsilon$, $\delta$)”-bounds, is it that the privacy loss of the proposed method is stated in RDP, and when generating the plots for comparison, the RDP bound is converted to a DP bound? - Is the $\delta$ part in the DP bound comparable? What is $\Delta W$ in Eq.(3.3)? Line 227: What is $\Lambda$ (the set containing all alpha values) used in the experiments? What are the major challenges of analyzing an extended version of this approach to tune the hyperparameters of other private optimizers, e.g., DP-Adam? Minor comments: when describing the approach (line 126 ~ 132) it might be clearer to use different letters for the base algorithm and the hyperparameter tuning algorithm. Minor issue: M subsample Poisson(q) should be M subsample Poisson ($\gamma$) in Theorem 4. Minor issue: it seems the right parentheses is missing in Eq.(3.1), Eq.(3.2).

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Limitations and broader impact are well discussed in the main paper.

Summary

The paper addresses private hyper-parameter tuning using privacy amplification by sampling. It introduces two versions of private fine-tuning on a sampled subset, which improves upon existing methods that fine-tune the entire private set. The problem involves deriving amplified privacy analysis and scaling the optimal hyper-parameters back to the original dataset. The authors employ linear scaling for hyper-parameter transfer and provide a Renyi differential privacy (RDP) analysis. Empirical results demonstrate that their approaches achieve better trade-offs between privacy and utility.

Strengths

1. The paper builds upon the existing results of "RDP of hyper-parameter fine-tuning" and "amplification by sampling of RDP" for their privacy analysis. They propose two algorithms for fine-tuning on a sampled set. The first algorithm directly applies the amplification by sampling rule of RDP to the fine-tuning algorithm with a known RDP. The second algorithm involves conducting a hyper-parameter tuning on a subset and then running the mechanism with the selected hyper-parameter on the dataset that does not include the subset. 2. While the contribution of the privacy analysis may appear limited, the authors successfully propose a comprehensive framework capable of tuning both DP and non-DP parameters on a subset. Their empirical results also support their findings regarding the transfer of optimal parameters from the subset to a larger set.

Weaknesses

The contribution of the paper may be considered incremental as it combines existing two techniques in a straightforward manner, specifically plugging one mechanism's RDP into another amplification by sampling rule that takes a RDP as an input. The privacy analysis of the second algorithm may be considered the only novel theoretical result in the paper.

Questions

The authors propose to use a linear scaling to transfer hyper-parameters. Is it generally hold for all hyper-parameters? For example, shall we also scale the optimal clipping threshold to the dataset size?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A