The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection
Authors: Shubhankar Mohapatra
Sajin Sasy
Xi He
Gautam Kamath
Om Thakkar
Venue: NeurIPS 2021 Submitted (2021)
Keywords: differential privacy
hyperparameter selection

Abstract: Hyperparameter optimization is a ubiquitous challenge in machine learning, and the performance of a trained model depends crucially upon their effective selection. 
While a rich set of tools exist for this purpose, there are currently no practical hyperparameter selection methods under the constraint of differential privacy (DP). 
We study honest hyperparameter selection for differentially private machine learning, in which the process of hyperparameter tuning is accounted for in the overall privacy budget. 
To this end, we i) show that standard composition tools outperform more advanced techniques in many settings, ii) empirically and theoretically demonstrate an intrinsic connection between the learning rate and clipping norm hyperparameters, iii) show that adaptive optimizers like DPAdam enjoy a significant advantage in the process of honest hyperparameter tuning, and iv) draw upon novel limiting behaviour of Adam in the DP setting to design a new and more efficient optimizer. 

24 In both the private and non-private settings, hyperparameter selection is instrumental to achieving high accuracy. The most common methods are grid search random search, both of which incur 26 a computational overhead scaling with the number of hyperparameters under consideration. In the private setting, this issue is often magnified most private training procedures introduce 28 hyperparameters. Regardless, and more importantly, hyperparameter tuning on sensitive dataset also costs in terms of privacy, naively incurring multiplicative cost which scales the square root The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection
Anonymous Author(s)
Affiliation
Address
email
Abstract
Hyperparameter optimization a ubiquitous challenge in machine learning, and the performance of trained model depends crucially upon their effective se- lection. While rich set of tools exist for this purpose, there are currently no practical hyperparameter selection methods under the constraint of differential privacy (DP). We study honest hyperparameter selection for differentially private machine learning, in which the process of hyperparameter tuning accounted for in the overall privacy budget. To this end, we i) show that standard composition tools outperform more advanced techniques in many settings, ii) empirically and theoretically demonstrate an intrinsic connection between the learning rate and clipping norm hyperparameters, iii) show that adaptive optimizers like DPAdam enjoy significant advantage in the process of honest hyperparameter tuning, and iv) draw upon novel limiting behaviour of Adam in the DP setting to design a new and more efficient optimizer.
10
11
12
Introduction
14
Over the last several decades, the field of machine learning has flourished. However, training machine learning models frequently involves personal data, which leaves data contributors susceptible to privacy attacks. This isn't tt purely hypothetical: recent results have shown that models are vulnerable to membership inference [SSSS17 CLE* 19 NSH19] and model inversion attacks [FJR15 SRS17.. The leading approaches for
16
18
machine learning are based on differential privacy (DP) [DNS066. Informally, DP rigorously limits and masks the contribution that an individual datapoint can have
20
21
algorithm's 's output. To address the aforementioned issues, DP training 22 procedures have been developed [WM10) BST14 SCS13 ACG+16), which generally resemble non- private gradient-based methods, but with the incorporation of gradient clipping and noise injection.
30 of the number of candidates (based on composition properties of differential privacy (OVV55).
31 Most prior works on private learning choose not account for this cost (ACG+16 16 YI.P+ 19 TB21 32 focusing instead on demonstrating the accuracy achievable by private learning under idealized condi- tions, that is, if the best hyperparameters were somehow known ahead of time. Some works assume
34 the presence of supplementary public data resembling the sensitive dataset (AGD+ 20 RTM 20), which may be freely used for hyperparameter tuning. Naturally, such public data may be scarce or nonexistent in settings where privacy is a concern, leaving practitioners with little guidance on how
36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 to choose hyperparameterss in practice. As explored in our paper, poor hyperparameter selection with standard private optimizers can have catastrophic effects on model accuracy.
38
39
Hope is afforded by the success of adaptive optimizers in the non-private setting. The canonical example is Adam [KB14], which exploits moments of the gradients adaptively and dynamically determine the learning rate. It works out of the box in many cases, providing accuracy comparable with tuned SGD. We navigate the different options available to a practitioner to solve the honest private hyperparameter tuning problem and ask, are there optimizers which provide strong privacy, require minimal hyperparameter tuning, and perform competitively with tuned counterparts?
40
41
42
43
44
45
Our Contributions
46
1. We investigate techniques for private tuning of hyperparameters. We perform the first empirical evaluation of the proposed theoretical method of Liu and Talwar [LT19], and demonstrate that it can be relatively expensive. That is, in certain cases, one can tune over sufficiently many hyperparameters using standard composition tools such as moments accountant (ACG*
47
48
49
2. We empirically and theoretically demonstrate that two hyperparameters, the learning rate and clipping threshold, are intrinsically coupled for non-adaptive optimizers. While other hyperparameters and the model architecture are restricted by the scope of the task, privacy and utility targets, and computational resources, the learning rate and clipping norm have no priori bounds. Since the 54 resulting hyperparameter grid adds up to the privacy cost while tuning to achieve the model with the best utility, explore leveraging adaptive optimizers to reduce the hyperparameter space.
50
51
52
59
3. We empirically demonstrate the DPAdam optimizer (with default values for most hyperparameters), can match the performance of tuned non-adaptive optimizers on a variety of datasets, thus enabling private learning with honest hyperparameter selection. This finding complements a prior claim 59 of Papernot et al. [PCS+20] 20]. which suggests that a well-tuned DPSGD can outperform DPAdam.
57
58
80 However, our findings show that this difference in performance is relatively insignificant. Furthermore,
61 in the realistic setting where hyperparameter tuning must be accounted for in the privacy loss, we show that DPAdam is much more likely to produce cancctasttoo results.
62
63 We show that the adaptive learning rate of DPAdam converges to a static value. To leverage this, 64 we introduce a new private optimizer, DPAdamWOSM that matches the performance of DPAdam without computing the second moments.
65
66
1.1
Related Work
67
Hyperparameter tuning plays a vital role in machine learning practice. In the non-private setting, ML practitioners use grid search, random search, Bayesian optimization techniques [SSA13] or AutoMI. [HZC21 techniques to tune their models. However, there hasn't been much research on private hyperparameter tuning procedures due to the significant associated privacy costs. Each set of hyperparameter configuration results in a privacy-utility tradeoff. This tradeoff for multiple configurations can be captured by Pareto frontiers using multivariate Bayesian optimization over parameter dimensions [AGD+20), 20). However, this method asks the model curator to query the dataset multiple times which requires non-private access to the dataset. There have been some end-to-end private tuning procedures [CMSTT CV13 KGGWI5) which work for a selected number of hyperparameter sets. These results work either in restricted settings for few combinations of candidates or under relaxations of differential privacy. The most relevant work to ours is an approach for private selection from private candidates [ Their work provides two methods, one which
68
69
70
71
73
74
75
76
77
79 outputs a candidate with accuracy greater than a given input threshold, and another which randomly
80 stops and outputs the best candidate seen far. The first approach is of limited utility in practice as
81 it requires a prior accuracy bound for the dataset. The second variant incurs a considerable overhead
82 in the privacy cost. We study this second approach and compare with naive approaches based on Moments Accountant (ACG+ 16) which would scale as the square root of the number of candidates.
83
2 Problem Setup and Overview
84
85 Consider a sensitive dataset D which lies beyond privacy firewall and has points of the form
86 (r1, y1), (122, (1),,y2),... ... (Nn, yn) where 2; E X is the feature vector of the ith point and y: E y its desired output. Though our experiments are carried out in the supervised setting, all results can be

---

88
translated to unsupervised setting as well. The dataset has been divided into two parts, the training set and the validation set. A trusted curator wants to train a machine learning model by making queries 90 on the dataset with a total end-to-end training privacy budget of (e,, of) such that the model can perform with high accuracy on the validation set. The curator wants to try multiple hyperparameter candidates for the model to figure out which candidate gives the maximum accuracy. However, as the model is private, each candidate requires multiple queries made on the dataset and all of them need to be accounted in the total privacy budget of (e ,y))
89
91
92
93
94
95
Note that any validation accuracy must also be measured privately. Since this accuracy a low- sensitivity query with a scalar output, and must only be computed once per choice of hyperparameters, the cost of this procedure is generally a lower order term versus the main training procedure. Thus for simplicity, we do not noise these validation accuracy queries. As we will see later, some optimizers require more candidates to tune and hence would also require more privacy budget than others.
96
97
98
99
100
To tackle private hyperparameter selection, we first compare the available private tuning procedures in Section 3 We show that the privacy cost for training a model depends on the hyperparameter grid size and standard composition theorems provide the best guarantees when the grid is small. In 4 we investigate different optimizers to see how many candidates are required to output a good solution. In Section 4.1 we provide theoretical and empirical evidence to demonstrate an intrinsic coupling between two hyperparameters the learning rate and clipping norm in DPSGD.
101
102
103
Section
104
105
106
We show that this coupling makes DPSGD sensitive to these parameter choices, which can drastically affect the validation accuracy. In Section [.2 we demonstrate that an adaptive optimizer, DPAdam, translates well from the non-private setting and obviates tuning of the learning rate. In Section [] we empirically compare DPAdam with DPSGD and DPMomentum to show that DPAdam performs at par we establish that DPAdam converges to static learning rate in restricted settings, and unveil a new optimizer OPAdamWOSM which can leverage
107
108
109
110
with less hyperparameter tuning. Finally, in Section [
111
112
this converged value without computing the second moments. In the interest of space, we defer standard preliminaries such as DP definitions, hyperparameters, and optimizers to the appendix.
113
3
The Cost of Privately Tuning DP Optimizers
114
115
Effective hyperparameter tuning is crucial in extracting good utility from an optimizer. Unlike the non non-private setting, DP optimizers typically i) have more hyperparameters tune; ii) require additional privacy budget for tuning. Existing work on DP optimizers acknowledge this problem (e.g..
116
117
118
ACG 16). but do not address the privacy cost incurred during hyperparameter tuning fACG* 16 approaches for private hyperparameter selection. The first performs composition via Moments Accountant [6) and the second is
119
19 19 TB21. There are two main prior general-purperr
120
121
the algorithm of Liu and Talwar (LT) [LT19] The latter is theoretical result, and to the best of our knowledge, has not been previously evaluated in practice. We investigate the privacy cost of these two techniques in practice and discuss situations in which each method is preferred.
122
124
3.1
Hyperparameter Selection via LT19
125
Liu and Talwar [LT19] propose a random stopping algorithm (LT) to output a 'good' hyperparameter candidate from a pool of K candidates, [.t...., FK) ). They assume sampling access a randomized mechanism Q(D) which samples ~ [K]. and returns the i-th candidate x,, and score q, for this candidate.
126
127
128
a random stopping algorithm, in which at every iteration, a candidate is picked from Q i..dd. with replacement and --basedd coin is flipped to randomly stop the algorithm. When the
129
130
algorithm stops, the candidate with the maximum score seen so far is outputted. In the approximate
DP version of this algorithm, an extra parameter T is set to limit the total of number of iterations. The pseudocode of this algorithm is deferred to the appendix.
132
Theorem 1 (LTT1), Theorem 3.4). Fix any 7 E [0, 82 > O and ler Y = 1 log 5े. IfQ is
133
134
(E1, DD) then the LT algorithm is 55) for E = 351 + 3/281 and 8y = /28,1 T + 82.
135
Theorem I expresses the privacy cost of the algorithm in terms of the privacy cost of individual learners, and parameters of the algorithm itself. The de parameter does not significantly affect the final epsilon ey of the algorithm and in practice, one can set it to very small value (10-20). Though small value of d2 has little effect on Qy, it increases the hard stopping time of the algorithm, T.
136
137
3

---

139
To understand the LT algorithm, we will compare the privacy costs of training a single hyperparameter candidate with a final y 6 budget via LT and compare with the privacy cost E ōn of the underlying individual learner. This setting might seem unnatural for LT as it was designed to select from a pool of candidates but we choose this setting to show the minimum privacy cost overhead associated with LT and later show how the privacy cost changes for multiple candidates (varying ?). To use LTT, one I [siin the final E 8y values and in this case, 7 = 1 (as we have just one candidate). The individual learner is then trained using ε d1 budget.
140
142
143
144
needs to figure out the EL, 51 via Theorem
Gamma
10
MA
Final Epalio
30'
0.01
0,001
150
0.1
200
100
231 5A0 2h 72z 722
100
50
10
100
1000
7500
850M
021K
1304
5500
150K
220k
9506
Uataset
Figure 1: Comparing the privacy cost of LT versus Moments Accountant. The minimal privacy overhead incurred by LT is at least -5x, and increases with the dataset size (left). However, as we allow LT to sample and test more candidate hyperparameters, the privacy cost barely increases (middle). Moments Accountant is able to test a significant number of candidates at the same cost as the minimal privacy overhead of LT (right).
148
Due to the delicate balance of oy in Theorem I one can see the 5₁ comes out to be much smaller than dy. This change in 61 results in a blowup of E and hence, the final privacy cost of the LT algorithm
147
148
(3s; + 3 20 is much larger than what it would have been for learning one candidate without LT.
149
We call this increase the blowup of privacy. We measure this blowup in Figure [left), for the setting
150
of a 4, L 250, T 10, 000 with varying dataset sizes (n). can be seen that for = 5, 000, the blowup is 4.8x whereas for for
151
950, 000, the blowup is almost 7.3x (note the log scale on y-axis). Qualitatively similar trends persist for other choices of noise multiplier, lot size and iterations. We add more experiments to compare LT vs MA with varying candidate sizes in the appendix.
152
153
154
Furthermore, we show that although LT entails a privacy blowup, decreasing y which corresponds to training more individual learners with 1 6,, doesn' It result in a significant difference in the final epsilon guaranteed by LT. In [egure[mmiddine
155
156
we show the final epsilon cost for different dataset size and varying values of y E [0.00T, 0.01, 0.1, 1]. It is interesting to note here that with smaller y values, one can train many candidates (in expectation, A) for negligible additional privacy cost. The blowup to train candidate (y = 1) versus 1, 000 candidates (? 0.001) increases from 33 to 39 for n = 5, 000 and increases from 0.49 to 0.69, for n 950, 000. This increase is minimal in comparison to advanced composition, which grows proportional to (vkk). However, another resource at play is the total training time, which is proportional 1// (i.e., the total number of candidates). In summary, the LT algorithm is effective if an analyst has the privacy budget to afford the initial blowup, as the privacy cost of testing additional hyperparameters is insignificant.
157
158
159
160
161
162
163
164
185
3.2
Hyperparameter Selection via Moments Accountant
186
We learnt from the previous section that, LT permits selection from large pool of hyperparameters (depending on the y value) but incurs a constant privacy blowup. We compare LT with tuning using Moments Accountant (MA). We notice using that with the same initial privacy blowup of the LT algorithm, MA is able to compose a considerable number of hyperparameter candidates. In FigureTrightt we show the number of candidates that can be composed using MA for the minimum
187
168
189
170
171
privacy cost for running the LT algorithm (y = 1). for the setting of a 4, L 250, T= = 10, 000 and varying dataset size (n) on the x-axis. As the T and L set constant, bigger n values in this graph correspond to fewer epochs of training and hence, worse utility. Depending on dataset size,
172
173
174
MA can compose candidates for n = 5000 and up to 175 candidates when n = 100000. It is perhaps surprising how well a standard composition technique performs versus LT. This information can be highly valuable to a practitioner who has limited privacy budget. Qualitatively similar trends persist for other choices of batch size, noise multiplier, and iterations.
176

---

178
From our experiments for both these tuning procedures, we conclude that while tuning with LT entails an initial privacy blowup, and the additional privacy cost for trying more candidates (smaller 7) is minimal. Even though this has an additional computation cost, it can be appealing when an analyst wants to try numerous hyperparameters. On the other hand, for the same overall privacy cost, MA can be used to compose a significant number of hyperparameter candidates. Additionally, MA allows access to all intermediate learners, whereas LT allows access to only the final output parameters. In the sequel, this conclusion will be useful in making the naive MA approach more appealing tool for some settings ge.g., tighter privacy budgets).
179
181
182
183
185
4 Tuning DP Optimizers
187
We detail aspects of tuning both non-adaptive and adaptive optimizers. We start with tuning non- adaptive optimizers (Section[4.I), We theoretically and empirically demonstrate a connection between the learning rate and clipping threshold. We also establish that non-adaptive optimizers inevitably require searching over a large LR-clip grid extract performant models. Adaptive optimizers forego this problem as they do not need to tune the hyperparameter dimension of learning rate. However, they introduce other hyperparameters that have known good choices in the non-private setting, and we empirically show that they are good candidates in the private setting (Section 4.2
188
189
190
192
194
4.1
Tuning DP non-adaptive optimizers
195
Wh While many hyperparameters are restricted due to computational and privacy/utility targets, the learning rate a and the clipping threshold C' have no a priori bounds. what follows, we show an interplay between these parameters by first theoretically analyzing the convergence of DPSGD. We then explore an illustrative experiment which demonstrates their entanglement. In the following theorem, we derive bound on the expected excess risk of DPSGD and while doing so, show that the optimal learning rate, Cept, is proportional to the inverse of C. The proof appears in Appendix D
196
198
200
201
Theorem 2. Let f be a convex and 3-smooth function, and let x² = arg minf(x). Let 2g be
#ES
an arbitrary point in S, and x1+1 = IIs( - a(ge + 21)), where g: min(1, C
202
and ze ~ NO0 o22) is the noise due to privacy. After T iterations, the optimal learning rate is 203
Gopt CTV1+02 where E[fG x. x.) f(x')] RCVI+o and R = E[I x= x=1]]-
n
VT
205
Though Theorem gives a closed-form expression for the optimum learning rate, it is a function of the parameter R. which is unknown a priori to the analyst. Given constant T and a, the optimal learning rate Copt is inversely propor-
206
Dorat 1600 1ea2 1e-05 1e-04
207
208
209
tional to the clipping norm C. This is crucial information practice because these parameters vary among datasets and
tesog Leaming Rate tal
20
211
are unbounded. This unboundedness property thus requires us search over very large ranges of C and a when we have no prior knowledge of the dataset. It is natural to ask whether one fix the clipping norm C' and search only
213
215
over a wide range for the learning rate a (or vice versa). We explore this relationship experimentally, showing that fixing one of these two hyperparameters may often but not always result in an optimal model.
16:04
4e 04
1e:03
40-00
se-0
25:88
46101
217
33
218
Cipping Threshole
219 In this experiment, we train a linear regression model on a 10-dimensional synthetic dataset of input-label pairs (ær, y) sampled from a distribution D as follows: æ1...., Fid ~
Figure 2: Log of training loss for sim- ulation experiment at o 4 on syn- thetic dataset. The black pixels corre- spond to lowest training loss. Note that most best loss values lie on diagonal expressing the inverse connection be- tween a and C.
221
U(( 1). y- z w", w* 10 We use the initialization We 0d and train for 100 iterations. the non-prive ooivvai setting, this model converges quickly with any reasonable
222
223
224
225
learning rate, but in the private setting, we notice that the training loss depends heavily on the choice of a and C.
Figure 2 shows heat map for the log training loss when trained on (a,C) pairs taken from a large grid consisting of [1, 2, 4, 5, 8] at scales of 1 10-3 10-2 10 10", 1. The best training is observed when the loss is 0 (black pixels).
227
5

---

3.0
0.66
0.5
3.00
Comen
(a) 0 =
2
(b) o =
(c)
Figure Ranking hyperparameter candidates across datasets. The black points correspond to the candidates with 0.001 (with all permutations of B1, B2 from our searchgrid); the gold corresponds to the candidate with 0.001, 31 = 0.9, B2 = 0.999
We observe fundamental phenomena from this figure. First, to achieve the best accuracy, a and C' need to be tuned on a large grid spanning several orders of magnitude for each of these parameters. Second, multiple (a,C) pairs achieve the best accuracy and all lie the same diagonal, validating
230
232
our theory for an inverse relation between learning rate and clipping norm. As mentioned earlier, one might hypothesize that by setting the clipping norm C constant and tuning a (corresponding
233
234
vertical line in Figure or vice versa, one could eliminate tuning hyperparameter, However, note
235
that not all C' and a values correspond the lowest loss. This phenomenon is evident by noticing that not all vertical or horizontal lines on this figure have black pixels. This happens, for example, the extremes (e.g., at the top-right corner), but also for several intermediate and standard choices (c.g., C' 0.1 or 0.2). Again, the analyst has no way of knowing this a priori. We conclude that to privately tune non-adaptive optimizers, we require a large grid of hyperparameter options.
236
237
238
239
240
4.2
Tuning DP adaptive optimizers
241
In the interest of reducing this space of tuning we turn to adaptive optimizers, where we can at least reduce one dimension of this search space. These approaches automatically adapt over the learning rate a, requiring us to tune only over the clipping norm C. But recall our key question: can we train models that perform competitively with the fine-tuned counterparts from DPSGD?
243
245
Adam [B14) the canonical adaptive optimizer introduces two new hyperparameters, which are the first and second moment exponential decay parameters (3, and (2)) In the non non-private setting, these parameters are relatively insensitive, and default values of a = 0.001, 31 = 0.9, and 32 = 0.999 are recommended based on empirical findings, requiring no additional tuning for this hyperparameter triple Hence before we compare DPAdam and DPSGD, we first find and establish such recommended values for this hyperparameter triple in the DP setting next, and then show that DPAdam with a small hyperparameter space performs competitively with DPSGD in Section 3
246
247
249
251
252
To establish default choices of a, 31, and B2 for DPAdam, we evaluate this private optimizer over four diverse datasets (details in Appendix B Table 2 and two learning models including logistic regression and a neural network with one 100 neurons hidden layer (TLNN). These selected datasets include both low-dimensional data (where the number of samples greatly outnumbers the dimensionality) and high-dimensional data (where the number of samples and dimensionality are at same scale). Since we still have a large hyperparameter space to tune over, for the rest of this work, we fix a constant lot size (L = 250), and consider tuning over three different noise levels, a E [2, 4, 8). so that we can study the effects tuning the other hyperparameters more thoroughly. All experiments are repeated three times and averaged before reporting. Additionally, in this particular experiment since we focus on a, 31, and 32. we also fix the clipping threshold C' 0.5, and T = 2500 iterations of training. For each dataset and model, we run DPAdam three times with hyperparameters (a, 31, 32) from the grids, a E [0.001, 0.05, 0.01, 0.2, 0.5], 31. 82 E [0.8, 0.85, 0.9, 0.95, 0.99.0.999].
253
254
255
257
259
261
263
264
We show that the default hyperparameter choice (a, B1, B2) of Adam in the non-private setting also works well for DPAdam. Figure [ shows the boxplots testing accuracies of DPAdam over different hyperparameter choices. When is 0.001 (same as in the non-private setting), all the datasets and models have final testing accuracies (marked in black) close to the best possible (and in most cases it is in fact the best) accuracy. Furthermore, we also highlight the accuracy of the
265
257

---

1.00
3.00
2.90
0.15
2097
0100)
-031
1003)
0.55
1000
1000
1000
0032
XX3)
0.05
1000
2000
MIDE
8530
2000
0231 KE0
*923
19393
0.60
1.00
3.00
0.15
2032
2000 E302
0009
10900
1000
7020 3000 4038 5003
9:00
1000
2000
1000
1000
5903
7000 1909 6200 3903 10302
DPSGD
DPAdam
DPMomentum
DPSGD(MA)
DPMomentum(MA)
Figure 4: Comparing the testing accuracy curves of DPAdam, DPSGD and DPMomentum models across their hyperparameter tuning grids with o = 4. The limits for y-axis are adjusted based on the dataset while maintaining 15% range for all.
269
suggested default choice (a = 0.001, 3 0.9, 32 0.999) using gold dots. Hence, for the ease of using DPAdam, we suggest the non-private default values for these parameters in the private setting as well and hence all our subsequent experiments.
271
5 Advantages of tuning using DPAdam
272
273
In the non-private setting, adaptive optimizers like Adam enjoy a smaller hyperparameter tuning space than SGD. We ask two questions in this section. First, can DPAdam (with little tuning) achieve accuracy comparable to a well-tuned DPSGD? Second, what is the incurs when using either of the two methods we detail in Section 3 for hyperparameter selection.
275
tradeoff one
277 To answer both questions, we compare DPAdam and DPSGD over the same set of datasets and models from the previous section. We report the accuracy of DPSGD with a range of learning rates and clipping values shown in Table 3 (Appendix[e) C). and the testing accuracy of DPAdam with default parameter choice from Section 4.2 (a = 0.001, 31 0.9, _32 0.999) and range of clipping values
278
279
281 C' in Table In total, DPSGD has 40 candidates to tune over, and DPAdam has 4. This is because have shown in Section 1 that DPSGD needs wide grid to obtain the best accuracy when data distributions are unknown. Additionally, we also consider the DPMomentum optimizer. Similar to how searched for default tuning choices for DPAdam in Section 4.2, we investigate if there cxists a qualitatively good choice for the momentum hyperparameter, and unfortunately our results show that there is no such choice. We detail this process in the supplement.
283
285
287 In order to show the comparison from both sides of the privacy-aceuree accuracy tradeoff, we compare the three optimizers through the privacy cost when extracting the best accuracy from these optimizers, and ii) the accuracy one would obtain from them under the tight privacy constraints.
289
290
5.1
Prioritizing Accuracy
For brevity, show experiments for in Figure 4 results for other values of displayed in the supplement. For each dataset and model, we train three times for each hyperparameter candidate and report the max every 100 iterations, corresponding the dark lines for each optimizer. We note that their maxima are extremely similar. However, Table shows the final privacy costs incurred by each of these accuracy lines, and reflects our claims from Section 3.1 that using fewer hyperparameter candidates and composing privacy via MA gives much tighter privacy guarantee.
292
283
294
296
297
5.2
Prioritizing Privacy
298
Additionally Figure 4. DPSGD and DPMomentum have pastel dotted lines corresponding their mean accuracy attained using the MA composition that provides the tightest privacy guarantees for
7

---

Dataset
DPSGD (LT)
DPMomentum (LT)
DPAdam (MA)
Table I: Final (at 8 10 10-6) for optimizers for the LR Mod- els (Figure 4. DPSGD and DP- Momentum use LT for privacy ac- counting; DPAdam uses MA.
Adult
5.01
5.23
1.91
ENRON
30.86
32.31
12.80
Gisette
26.40
27.64
10.76
MNIST
3.01
3.14
1.14
300
DPAdam. These pastel lines are the mean accuracies (with 95% CT) from 100 repetitions of this experiment. Since DPAdam has only 4 hyperparameter candidates, for this experiment, sample 4 of the candidates at random for DPSGD and DPMomentum so that they all incur the same privacy cost. Since the candidate pool is significantly larger for DPSGD and DPMomentum,
302
additionally scrutinize the parameter grid for them and prune the learning rates that perform poorly. Our pruning
304
305
process (detailed in the supplement) is quite generous, and favours minimizing the hyperparameter
space of DPSGD and DPMomentum as much possible. Despite the pruning advantage we see that these optimizers perform subpar than DPAdam when constrained with tight privacy requirements.
306
307
DPAdam without second moment: DPAdamWOSM
308
309
As illustrated in the previous section, adaptivity can indeed be a boon, enabling DPAdam to match the performance of tuned DPSGD while consuming roughly third of the privacy budget as seen in Table []] However, in addition to a decaying average of the past gradient updates, DPAdam also requires maintaining decaying average of their second moments. In this section, we design DPAdamWOSM, a new DP optimizer that operates only using decaying average of past gradients, as well as eliminates the need to tune the learning rate parameter. We achieve this by analyzing the convergence behavior of the second-moment decaying average in DPAdam in regimes where the scale of noise added is much higher than the scale of the clipped gradients. Setting the effective step size (ESS) of DPAdam to the converged constant, and removing all computations related to the second- moment updates, results in DPAdamWOSM. We empirically demonstrate that DPAdamWOSM matches the utility of DPAdam, while requiring less computation than DPAdam.
310
311
312
313
314
315
316
318
320
Observe that removing the second moment updates from DPAdam reduces it to DPMomentum with one additional feature: Dias-correction to the first-moment decaying average, which DPAdam does to account for its initialization at the origin. While the resultant optimizer still requires tuning the learning rate (in addition to other hyperparameters like the clipping threshold), DPAdamWOSM can be viewed as self-tuning the learning rate by fixing the converged effective step size DPAdam.
321
322
323
324
325
6.1
Effective step size (ESS) in DPAdam
326
DPAdam produces results with a smaller variance than DPSGD due to its adaptive learning rate. To understand this phenomenon better, we look closely into the update step of DPAdam [KB14). DPAdam being an adaptive optimizer picks per-parameter ESS as V which is the base learning
328
329
rate a scaled by the second moment of the individual parameter gradients. We notice that when
330
g + 0, the ESS for DPAdam converges for the first moment gradient, which innately accounts for the clip bound one is training with. This may happen at later iterations, when the model is close to its
331
332
minima and the gradients get close to zero.
333
Theorem 3. The effective step size (ESS) DPAdam with g - converges to ESS* ToC/L1+5
Proof. Recall that the average noisy gradient over a lot is g = g + +N (0,,02C))/L. We now look at the effect of this noisy gradient the effective step size (ESS) of DPAdam. As g - the second o²c²
334
335
336
moment of DPAdam converges to D This gives us the converging value for ESS:
E.SS
Vo2 +
V
02ca L + (oCIL)+E
'Note, pruning itself is of course unfair; the intent was to design DP optimizer that can be used on any data distributions that we have no prior knowledge of. To do so with DPSGD one would have to consider a significantly wide range of (a, C) pairs to cover 'good' candidates illustrated in Section
8

---

1.00
1.00
Gisttet
2.00
0.15
2097
0100)
-031
1003)
0.55
1000
7000
1000
6532
XX31
0.05
1000
2000
MIDE
8530
2000
0231
*92) 1939
0.40
1.00
2.50
0.15
2032
2000
E302
0009
10900
1000
7000 3000
4038
5903
9:00
1000
2000
TODC
1000
5903
2000
1909 6200
3993 10303
DPAdam
DPAdamWOSS
ADADP
OPAdarn-Media
DMKaamWOSMMMediin
Median
Figure 5: Comparing the testing accuracy curves of DPAdam, ADADP and DPAdamWOSM models across hyperparameter tuning grid from Table 3 with a = 4. The limits for the y-axes are adjusted based on the dataset while maintaining 15% range for all.
Theorem 3 gives closed form expression that ESS converges to. We can this value in place 338 of Vor+c in the update step from the inception of the learning process. Since the second-moment updates (e.g., 0ς) are not used anymore, removing them results in new optimizer DPAdamWOSM. We provide a pseudo-code for DPAdamWOSM in the appendix.
340
341
6.2
Comparing Adaptive Optimizers
We evaluate DPAdamWOSM by rumning it alongside DPAdam and ADADP with the same hyperpa- rameter grid in the appendix. For brevity, we show experiments on o = and others appear in the supplement. In Figure 5 we show the maximum and median accuracy curves for all the optimizers. We display the median accuracy curves (shown in dotted), as an indicator the quality of the entire pool of hyperparameter candidates for given optimizer; which in this case is strictly over the choices of clip. The max lines for ADADP lies beneath DPAdam and DPAdamWOSM for all dataset except Adult. Also, the max accuracy line for DPAdamWOSM runs alongside DPAdam which means that it can perform as good as DPAdam throughout training. The median line for DPAdamWOSM also
343
345
347
348
349
350
performs alongside DPAdam and in some cases is able to beat (e.g, the median for DPAdamWOSM
351
for MNIST-LR and MNIST-TLNN lies above the median line of DPAdam). This occurrence is seen because DPAdamWOSM uses the converged ESS from the first iteration of training.
352
7
Conclusion
353
354
In this paper, we performed a thorough investigation of honest hyperparameter selection for DP Optimizers. We compared two existing private methods, LT and MA to search for hyperparameter candidates and showed that, the former incurs significant privacy cost but can compose a great many candidates, while the latter is helpful when the number of candidates is small. Next, we explored connections between the clipping norm and the step size hyperparameter to show an inverse relation- ship between them. Additionally, we compared non-adaptive and adaptive optimizers, demonstrating that the latter typically achieves more consistent performance over a variety of hyperparameter settings. This can be vital for applications where public data is scarce, resulting in difficulties when tuning hyperparameters. Finally, we brought to light that DPAdam converges to static learning rate
355
356
357
358
359
360
361
362
365
when the noise starts dominating the gradients. This insight allowed us to derive novel optimizer DPAdamWOSM, a variant of DPAdam which avoids the accond-momed computation and enjoys better accuracy especially at earlier iterations. Future work remains to investigate further implications of these results to provide tuning-free free end-to-end private ML optimizers.
365

---

References
367
368
[6CG+16]
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS 16), 2016.
370
371
[AGD*20] Brendan Avent, Javier González, Tom Diethe, Andrei Paleyes, and Borja Balle. Auto- matic discovery of privacy-utility pareto fronts. Proceedings Privacy Enhancing Technologies, 2020(4): 23, 2020.
372
374
375
[BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems 31, NeurIPS '1, pages 6277-6287. Curran Associates, Inc., 2018.
376
377
378
[BST14] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk min- imization: Efficient algorithms and tight error bounds. In FOCS, pages 464-473, 2014.
379
380
[9] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pages 267-284, Santa Clara, CA, August 2019. USENIX Association.
381
383
385
[CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
387
[CV13] Kamalika Chaudhuri and Staal A Vinterbo. A stability validation procedure for differentially private machine learning. Advances in Neural Information Processing Systems, 26:2652 2-262222660, 2013.
388
389
390
[DHS11] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
392
06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, volume 4004, pages 486-503. Springer, 2006.
394
396
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 284, 2006.
397
398
389
[FJR15] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS'15), 2015.
400
401
[GAYB17] R. Gylberth, R. Adnan, S. Yazid, and T. Basaruddin. Differentially private optimization algorithms for deep neural networks. In 2017 International Conference on Advanced Computer Science and Information Systems (ICACSIS), pages 387-394, 2017.
403
405
[HSS12) Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8), 2012.
407
[HZC21] Xin He, Kaiyong Zhao, and Xiaowen Chu. Automl: survey of the state-of-the-art
408
Knowledge-Bass Based Systems, 212: 2021.
[KB14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: /4/ 22.9800 2014.
410
[KGGW15] Matt Kusner, Jacob Gardner, Roman Garnett, and Kilian Weinberger. Differentially private bayesian optimization. International conference on machine learning, pages 918-927. PMLR, 2015.
412
10

---

414
[KH20] Antti Koskela and Antti Honkela. Learning rate adaptation for differentially private learning. In International Conference on Artificial Intelligence and Statistics, pages 2465-2475 PMLR, 2020.
415
[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385. PMLR, 2015.
418
[LT19] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Pro- ceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, pages 298-309, 2019.
421
422
[MAE+18] H Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, Ilya Mironov, Nicolas Papernot, and Peter Kairouz. A general approach to adding differential privacy iterative training procedures. arXiv preprint
423
424
425
2018.
426
[NSH19] M. Nasr, R. Shokri, and A. Houmansadr. Comprehensive privacy analysis of deep learn- ing: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE Symposium on Security and Privacy (SP'19), 2019.
428
[PCS+20] Nicolas Papernot, Steve Chien, Shuang Song, Abhradeep Thakurta, and Ulfar Erlingsson. Making the shoe fit: Architectures, initializations, and tuning for learning with privacy, 2020.
429
431
432
[Qia99] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural Networks, 1999.
433
434
[RHW86] David Rumelhart, Geoffrey E Hinton, and Ronald J Williams, Learning representations by back-propagating errors. nature, 323(6688) 1986.
[RTM+20] Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H Brendan McMa- han, and Françoise Beaufays. Training production language models without memorizing user data. arXiv preprint wwXi::200911031 2020.
437
[SCS13] Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In GlobalSIP, pages 245-248, 2013.
440
[SRS17] Congzheng Song. Thomas Ristenpart, and Vitaly Shmatikov. Machine learning models that remember too much. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS' 17), 2017.
442
443
[SSA13] Kevin Swersky, Jasper Snoek, and Ryan P Adams. Multi-task bayesian optimization. Advances Neural Information Processing Systems, 26:2004-2012, 2013.
445
446
[SSSS17] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium Security and Privacy (SP), 2017.
448
449
[TB21] Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference Learning Representations, 2021.
450
[WM10] Oliver Williams and Frank McSherry. Probabilistic inference and differential privacy. In NIPS, pages 2451-449, 2010.
452
19LP+19] I.. Yu, I.. Liu, C. Pu, M. F. Gursoy,and and Truex. Differentially Private Model Publishing for Deep Learning. 2019 IEEE Symposium on Security and Privacy (SP'19), 19), 2019.
454
455
2FM+200 Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven HOI, et al. Towards theo- retically understanding why sgd generalizes better than adam in deep learning. arXiv preprint 2rXiv:2010005627,220000 2020.
457
11

---

Checklist
458
459
1. For all authors...
480
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
465
488
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
469
3. If you ran experiments...
470
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
473
474
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
477
478
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
479
(a) If your work uses existing assets, did you cite the creators? [Yes]
480
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're rr using/curating? [Yes]
483
484
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
486
5. If you used crowdsourcing or conducted research with human subjects...
487
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
488
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
490
491
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "aMdgWAsi6A8", "reviewer": "Reviewer_DFkp", "summary": "This paper looks to take a deeper dive into DP hyperparameter tuning, an often overlooked aspect of DP learning. It makes several practical claims about this problem, including comparisons of two well-known DP selection strategies and arguing for the promise of adaptive optimizers. For the latter, they provide evidence for why learning rate and clipping are difficult to tune for DP-SGD and how DPAdam can help mitigate this issue. Finally they also propose a new optimizer which matches DPAdam on performance but reduces the amount of necessary computations. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality:** To my knowledge, the investigations/results in this paper are indeed novel and important (even if they center around existing problems/methods). I do wonder though if work on adaptive setting of the clipping threshold should be listed as an orthogonal related direction (e.g., https://arxiv.org/pdf/1905.03871.pdf, https://arxiv.org/pdf/1812.02890.pdf) – one could see these papers as also aiming to reduce the amount of tuning needed in DP training procedures, but instead focusing on $C$ instead of $\\alpha$.\n\n**Quality:** I find the results solid for the most part but I have a few comments/questions here that I hope the authors can speak to.\n\n(1) Was the choice to fix $\\alpha$ in Sec 5 taken after inspecting the results in Sec 4.2? If so, is it actually fair to use the reduced search space for DPAdam in Sec 5 if the this reduction was based on inspecting additional runs on the same datasets earlier in Sec 4.2? It seems it would be stronger/more generalizable to see if these default choices carry over to do well on unseen tasks. \n\n(2) I think there are a few places where more extensive experiments might help better support the author's claims. These generally relate to getting a more precise sense of DPAdam's robustness over choices of $\\alpha$.\n\n* (a) A version of Figure 2 for DPAdam would be appreciated to compare with the existing one for DPSGD. Additionally, maybe similar analyses could also be repeated on more realistic datasets, especially if the aim is to conclude more generally that “to privately tune non-adaptive optimizers, we require a large grid.”\n\n* (b) While I buy that DPAdam is very likely easier to tune, I still question the generalizability of the stronger takeaway that one is recommended to fix the same default learning rate for DPAdam on new tasks. In practice, people do see non-trivial gains from tuning non-private Adam’s learning rate and indeed, it does seem like accuracy is hampered in the case of Adult by using the default. Perhaps experiments covering more graded reductions of the search space/privacy budgets could help clarify best practices for DPAdam.\n\n* (c) In Section 5, I’d be curious to see for completeness how DPAdam does when using the full search space (of DPSGD).\n\n(3) I wonder if the authors could speak more about the significance or practical benefit DPAdamWOSM offers. Is the claim is based on computational efficiency rather than accuracy/privacy (which look comparable to DPAdam)? Is so, what do the actual savings look like here? \n\n**Clarity:** As a whole, the paper reads well.  However, I did notice a few misc. things that I wanted to note\n\n* In Sec 1.1, it is said that [CMS11, CV13, KGGW15] “work either in restricted settings...or under relaxations of differential privacy.” Given that $(\\epsilon, \\delta)$-DP, which is studied in this paper, itself is considered a relaxation of “pure” $(\\epsilon)$-DP, the current wording might be confusing if it aims to communicate how these previous works differ.\n\n* Were the quantities $\\sigma, L, T$ defined prior to their usage in line 150? I feel that presentation would be helped if the full set of hyperparameters were explained in the main (currently left to appendix A) or at least mentioned with a pointer to the specific Appendix for more details. Similarly, ADADP is introduced without much context in Figure 5/Sec 6.2, \n\n* Why is it said that $\\delta_2$ has little effect on $\\delta_f$ in line 138? If we set it arbitrarily small (such as to the indicated 10^-20), doesn’t this end up blowing up $\\delta_f$ by a factor of 20 (via the dependence of $\\Upsilon$ on $\\delta_2$)? \n\n* It’s kind of difficult to actually see the “black” squares in Figure 2. Also wondering if these losses here were averaged over multiple runs?\n\n**Significance:** Overall, I think the contributions in this paper are interesting and tackle a very well-motivated problem. The privacy costs incurred by hyperparameter tuning are indeed an underemphasized aspect of “honest” DP model training. It seems natural then to study adaptive optimizers, which likely have an even larger role to play than in non-private settings. Here, one does not merely aim to conveniently save time/resources in the DP setting, but also the amount of necessary noise added to training procedures (assuming limited privacy budget). In this context, I find the major claims to all be of practical value towards bridging this gap to \"honest\" DP selection. However I do think some of them can be more extensively evaluated/supported (as discussed above).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing to add beyond what I have mentioned previously ", "review_text": "", "extra_scores": {"ethical_concerns": "None that I have observed. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "N7NZW7RUXPl", "reviewer": "Reviewer_cwxc", "summary": "This paper presents a combination of analytical and (mostly) empirical results evaluating the task of \"honest hyperparameter selection\" under differential privacy; that is, accounting for the full set of tuning experiments conducted when computing the resulting privacy guarantee. The authors provide some empirical comparison between two existing composition methods for hyperparameter selections -- Moments Accountant (MA) and Liu & Talwar (LT) and give a relation between privacy of individual learners and the final learner in Theorem 1; however, their focus is mostly on showing the competitiveness of DPAdam relative to DPSGD. They conclude with a proposed adaptation to DPAdam which discards the second moments term since they observe this to converge to a constant value in practice.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall: The paper is well-written and the experiments are generally clear. However, the ultimate intended contribution of the paper is not quite clear to me, or seems limited to providing evidence that DPAdam should be used in practice, with only the learning rate tuned, and without the second moments term. The findings are not surprising, as Adam is quite popular in practice already (although perhaps less so for DP learning, it is still available in widely available software packages like TF Privacy). Additionally, the \"new\" optimizer they propose mostly removes a component of Adam, and the motivation and gains from doing so are not entirely clear. I think that this could be a useful contribution to the applied DP literature, but currently it seems somewhat incremental, although there are several practical insights that are clearly expressed in the paper.\n\nMajor Comments:\n\n* Many of the empirical results in the paper are wholly unsurprising; I am most surprised that the authors place so much emphasis on them. For example, the fact that DPAdam performs competitively with tuned DPSGD is what I would expect (and have observed in practice, as have many others) -- indeed, this is why Adam achieved such wide adoption in (non-DP) scenarios. Unless there is a strong reason to doubt this would hold in a DP context, I do not see this as an independent contribution and it only provides motivation for tuning Adam instead of SGD (which, again, seems to be the existing practice, at least outside of DP but possibly also within the DP community).\n\n* I found the relationship between clipping bound and learning rate to be the most interesting insight from the paper, and was surprised to see less discussion and empricial investigation here. I would recommend to remove some of the other empirical results, and perhaps comment/experiment more to show what can be learned from this connection. Due to the impact that clipping is know to have on e.g. fairness and other geometric properties of DP learning, it seems that intelligently choosing the learning rate-clipping bound combination would be of great interest to many DP practitioners.\n\n* Figure 2 is interesting, but I think the authors place a great deal of emphasis on this emprical result when it is only a single experiment with DP linear regression on what appears to be a noise-free dataset with tightly bounded features. It would be useful to see this trend across more complex models and datasets.\n\n* The optimizer \"DPAdamWOSM\" is framed as a key contribution of the paper. However, it isn't clear what is gained from this new optimizer -- as the authors note, little is achieved by tuning the parameters associated with the decaying average of second moments in practice, and it is rare to tune these. So, what do we gain with respect to privacy, in practice, by simply eliminating it? The performance is effectively identical to DPAdam in Figure 5, as expected. (Of course, there are some gains in terms of computation, but the authors do not seem concerned with these.) Additionally, it seems that their method of choosing the fixed effective step size requires *running DPAdam on the data first* to set it to the converged constant. Please comment on the privacy loss of doing so.\n\nMinor Comments:\n\n* Please refer to the specific sections in supplementary materials when mentioning them (e.g. L132), and the specific algorithms or figures where relevant.\n\n* I found it difficult to intuitively understand the results of Fig. 1 (right). Almost no information is given about the MA approach (apparently since the authors' findings only apply to LT), which makes it difficult to understand why the curve is shaped as it is. Furthermore, it is strange that LT is not also included in that plot (for various levels of \\gamma); this would be a helpful comparison, as the authors devote little discussion to LT vs. MA in later stages and seem to choose them manually.\n\n* L146-147 suggests that \\delta_1 is much smaller than \\delta_f; however, \\delta_f is related to the square root of \\delta_1; is this only for delta << 1?\n\n* Please define parameters \\sigma, L, T in main text.\n\n* Fig. 2 needs more spacing from text; it is almost impossible to differentiate caption from main text.\n\nTypos etc.\n\n* L168: \"we notice using that with the\" -- please fix/clarify\n\nL179: \"blowup, and the\" --> \"blowup, the\"\n\n**Update**: I have read the author response. While it provides helpful clarifications and addresses some concerns, I will maintain my previous rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, although I believe there could be (positive/useful) implications for DP fairness research which are not discussed; see comments above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "DSnPHcGC0Ip", "reviewer": "Reviewer_akSs", "summary": "This paper investigate and compare private hyperparameter tuning using two different methods. Further, the authors demonstrates optimal learning rate is inver proportional to optimal clipping bound. Lastly, the authors showed advantage of DP adaptive optimizer over DPSGD from the perspective of hyperparameter tuning.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper presented several interesting findings, including comparing LT and MA for private hyperparameter tuning; showing relation between \\sigma and C, proposing new DP optimizer. There are several concerns after reading through the paper: 1. when the authors are talking about using MA to tune hyperparameter, it is not clear what that means. MA is a method to account for the privacy cost during some randomized process. Is it referring to using grid search to find hyper parameter settings and use MA to account for the privacy cost? This part needs to be clarified. 2. The upper bound in theorem 2 looks loose. Consider the case where \\sigma is 0 and C is sufficiently large such that no clipping happens at all, the bound on the right hand side becomes infinity and the convergence guarantee becomes vacant. However, in such scenario DPSGD should reduce to standard SGD with no privacy. 3. It is not clear what \\alpha_opt means. What is the learning rate optimal in terms of? Is it optimal in terms of convergence bound? privacy? something else? This part needs to be clarified.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and suggestions are listed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "D22m5jfLgu", "reviewer": "Reviewer_iVES", "summary": "This paper discusses the problem of private hyperparameter optimisation in machine learning. Although the discussion and results seem interesting, the privacy model is not very clear. \n\nThe response clarified this but it should be in the paper.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The settings seems to be this: We have a black-box optimisation algorithm $f$ that, given some hyperparamters $\\theta$, it generates a model $\\mu_i = f(\\theta_i, D)$. The model is then evaluated on some validation set $D'$ to obtain a score $q(\\mu_i, D')$, which may also be differentially privately generated. The model with the highest score is then selected. The question is, what is the overall privacy loss for $D$ if $\\mu_i$ is generated with a $(\\epsilon, \\delta)$-DP mechanism. In this setting, we do not care about the privacy loss with respect to $D'$. The paper never makes this model perfectly clear, however. \n\nOne issue that bothered me about this paper is the fact that, in order to obtain the score, we do not need to publish the model $\\mu_\\theta^D$. The confusion seems to arise  from [LT19], which states that their algorithm could be used in a setting where $K$ models are published and one of them is selected. Indeed, in Sec. 3.1, line 127, the randomised mechanism samples a model $i \\sim [K]$ and returns both a candidate and a score. However, the question is how much do we learn about the i-th model (and consequently D) if we only see the score on a validation dataset? \nTo answer this question, we must think about the DP properties of the scoring function itself on the i-th model. While it is easy to have $q$ be DP wrt D', the privacy loss wrt D is not clear. In the worst case, we can assume $\\mu_i$ is fully revealed, but I find this unsatisfactory.\n\nIn any case, assuming $\\mu_i$ is revealed and we do not care about privacy wrt $D'$, the results make sense and the discussion is interesting.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The privacy model is unclear.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of hyper-parameter selection in differential private learning, making a number of observations on the relation between learning rate and clipping parameters, and showing that adaptive optimizers like DP-Adam can outperform standard ones that are more commonly used in practice (eg, DP-SGD). One of the merits of the paper is to tackle an important but under-studied problem (hyper-parameter optimization under DP) from a practical standpoint, accounting for the privacy loss of tuning and showing that this leads to different trade-offs in the choice of optimizers.

The reviews were all somewhat positive but none of the reviewers expressed clear support for the paper acceptance. The author response helped to clarify a few aspects, but was not sufficient to get stronger support. Remaining concerns/doubts include:
- Insufficient evidence that DP-Adam is currently overlooked (the authors only cite one paper), which is crucial to assessing the significance of the DP-Adam findings
- The results seem to rely on the fact that default parameters for adaptive optimizers are good enough, which may not always be the case in practice.
- The new experiments replicating Figure 2 were found to be interesting but it is difficult to assess their completely without being able to see them in full.

Eventually, the decision was to reject the paper. However, the work is seen as promising so the authors are strongly encouraged to improve their work based on the feedback from the reviewers.
Decision: Reject