Recycling Scraps: Improving Private Learning by Leveraging Intermediate Checkpoints
Authors: Virat Shejwalkar
Arun Ganesh
Rajiv Mathews
Om Thakkar
Abhradeep Guha Thakurta
Venue: Submitted to ICLR 2023 (2023)
Keywords: Differential privacy
training checkpoints
confidence intervals
uncertainty

Abstract: All state-of-the-art (SOTA) differentially private machine learning (DP ML) methods are iterative in nature, and their privacy analyses allow publicly releasing the intermediate training checkpoints. However, DP ML benchmarks, and even practical deployments, typically use only the final training checkpoint to make predictions. In this work, for the first time, we comprehensively explore various methods that aggregate intermediate checkpoints to improve the utility of DP training. Empirically, we demonstrate that checkpoint aggregations provide significant gains in the prediction accuracy over the existing SOTA for CIFAR10 and StackOverflow datasets, and that these gains get magnified in settings with periodically varying training data distributions.  For instance, we improve  SOTA StackOverflow accuracies to 22.7\% (+0.43\% absolute) for $\epsilon=8.2$, and 23.84\%  (+0.43\%) for $\epsilon=18.9$. Theoretically, we show that uniform tail averaging of checkpoints improves the empirical risk minimization bound compared to the last checkpoint of DP-SGD. Lastly, we initiate an exploration into estimating the uncertainty that DP noise adds in the predictions of DP ML models. We prove that, under standard assumptions on the loss function, the sample variance from last few checkpoints provides a good approximation of the variance of the final model of a DP run. Empirically, we show that the last few checkpoints can provide a reasonable lower bound for the variance of a converged DP model. 

Under review as a conference paper at ICLR 2023
RECYCLING SCRAPS: IMPROVING PRIVATE LEARNING BY LEVERAGING INTERMEDIATE CHECKPOINTS
Anonymous authors Paper under double-blind review
ABSTRACT
All state-of-the-art (SOTA) differentially private machine learning (DP ML) meth- ods iterative in nature, and their privacy analyses allow publicly releasing the intermediate training checkpoints. However, DP ML benchmarks, and even practical deployments, typically use only the final training checkpoint make predictions. In this work, for the first time, we comprehensively explore vari- ous methods that aggregate intermediate checkpoints improve the utility of DP training. Empirically, we demonstrate that checkpoint aggregations provide sig- nificant gains in the prediction accuracy over the existing SOTA for CIFAR10 and StackOverflow datasets, and that these gains get magnified in settings with periodically varying training data distributions. For instance, we improve SOTA StackOverflow accuracies to 22.7% (+0.43% absolute) for 8.2, and 23.84% (+0.43%) for e = 18.9. Theoretically, we show that uniform tail averaging checkpoints improves the empirical risk minimization bound compared the last checkpoint of DP-SGD. Lastly, we initiate an exploration into estimating the un- certainty that DP noise adds in the predictions of DP MI. models. We prove that, under standard assumptions on the loss function, the sample variance from last few checkpoints provides good approximation of the variance of the final model of DP run. Empirically, we show that the last few checkpoints can provide a reasonable lower bound for the variance of a converged DP model.
INTRODUCTION
Machine learning models can unintentionally memorize sensitive information about the data they were trained on, which has led to numerous attacks that extract private information about the training
data (Ateniese et al. 2013 Fredrikson et al. 2014 2015 Carlini et al. 2019 (hejwaalkr et al. 2021
Carlini et al. 2021 2022). For instance, membership inference attacks (Shokri et [0017] can infer
whether target sample was used to train given MI model, while property inference attacks (Melis) jet al. 2019] Mahloujifar et al.) 2022) can infer certain sensitive properties of the training data. To address such privacy risks, literature has introduced various approaches to privacy-preserving
ML (Nasr et al.] 2018 Shejwallkrr & Houmansadr 2021 Tang et al. 2022). In particular, iterative
techniques like differentially private stochastic gradient decent (DP-SGD) (Song al. 2013 Bassily
et al. 2014 Abadi et al. 2016b McMahan et al. 2017) and DP Follow The Regularized Leader
(DP-FTRL) Kairouzz et al. 2022 have become the state-of-the oh-the--rtttttt art for training DP neural networks.
For establishing benchmarks, prior works in DP ML (Abadi et al.) 2016b McMahan et al. 2017
2018
Thakkar et al., 2019) Erlingsson et al., 2019 Wang et al. [011]]] /hh & Wang 2019 Balle
et al.
2020 Erlingssnn et al. 2020)] Papernot et al. 2020 Tramer & Boneh, 2020, Andrew et al.)
Kairouz et al. 2021 Amid et al. 2022 De et al. 2022] Feldman et al. 2022) use only the final model output by the DP algorithm. This is also how DP models are deployed in practice (Ra-) maswamy et al., 2020; McMahan et al., 2022). However, the privacy analyses for the techniques used allow releasing/using all of the intermediate training checkpoints. In this work, comprehen- sively study various methods that leverage intermediate checkpoints to 1) improve the utility of DP training, and 2) quantify the uncertainty in DP MI. models that is due to the DP noise.
2021
Accuracy improvement using checkpoints: We propose two classes of aggregation methods based on aggregating the parameters of checkpoints, or their outputs. We provide both theoretical and em-

---

Under review as a conference paper at ICLR 2023
pirical analyses for aggregation methods. Theoretically, we show that excess empirical risk of the final checkpoint of DP-SGD is log(n) times more than that of the weighted average of the past k checkpoints. Here, is the size of dataset. Empirically, we demonstrate significant top-1 accu- racy gains due to our aggregations for image classification (CIFAR10) and a next word prediction (StackOverflow) tasks. Specifically, we show that our checkpoints aggregations achieve absolute (relative) prediction accuracy improvements of 3.79% (7.2 (7.2%) at 1 for CIFARIO (DP-SGD), and 0.43% (1.9%) at = 8.2 for the StackOverflow (DP-FTRLM) SOTA baselines, respectively. We also show that our aggregations significantly reduce the variance in the performance of DP models over training. Finally, we show that these benefits further magnify in more practical settings with periodically varying training data distributions. For instance, we note absolute (relative) accuracy gains of 17.4% (28.6%) at E = for CIFARIO over DP-SGD baseline such a setting.
Uncertainty quantification using checkpoints: There are various sources of randomness in a ML training pipeline (Abdar et al., (021). c.g., choice of initial parameters, dataset, batching, etc. This randomness induces uncertainty in the predictions made using such ML models. In critical do- mains, e.g., medical diagnosis, self-driving cars and financial market analysis, failing to capture the uncertainty in such predictions can have undesirable repercussions. DP learning adds an additional source of randomness by injecting noise at every training round. Hence, it is paramount to quantify reliability of the DP models, e.g., by quantifying the uncertainty in their predictions.
To this end, we take the first steps towards quantifying the uncertainty that DP noise adds to DP ML training. As prior work, Karwa& & Vadhan (2017) develop finite sample confidence intervals but for the simpler Gaussian mean estimation problem. Various methods exist for uncertainty quantifica- tion in ML-based systems (Mitchell, 1980, Roy et al. 2018 Begoli et al. 2019 Hubschneider al.,
McDermott & Wikle 2019 lagasovska & Lopez-Paz, 2019 Wang et al. 2019a]] Nair et al., Ferrando et al., 2022). However, these methods either use specialized (or simpler) model architectures to facilitate uncertainty quantification, or are not directly applicable to quantify the uncertainty in DP ML due to DP noise. For e.g., common way of uncertainty quantification (Bar- frientos et al. 2019, Nissim et al.) 2007; Brawner & Honaker, [018)] Evans et al. 2020) that we call the independent runs method, needs independent (bootstrap) runs of the ML algorithm. However, repeating a DP ML algorithm multiple times can incur significant privacy and computation costs.
2019
2020
To address the above issue, we propose to use the last & checkpoints of a single run of a DP ML algorithm as a proxy for the l final checkpoints from independent runs. This does not incur any ad- ditional privacy cost to the DP ML algorithm. Furthermore, it is useful in practice as it does not incur additional training compute, and can work with any algorithm having intermediate checkpoints.
Theoretically, we consider using the sample variance of a statistic f(0) at checkpoints Oty.-... Oz. as an estimator of the variance of [0 í.e., the statistic the final checkpoint, and give a bound on the bias of this estimator. As expected, our bound on the bias decreases as the "burn-in" time t as well as the time between checkpoints both increase. Intuitively, our proof shows that (i) as the burn- in time increases, the marginal distribution of each 0z,, approaches the distribution of 0,,, and (ii) as the time between checkpoints increases, any pair fr., 62, approaches pairwise independence. Both (i) and (ii) are proven via a mixing time bound, which shows that starting from any point distribution 0o the Markov chain given by DP-SGD approaches its stationary distribution at a certain rate. Empirically, we show our method provides reasonable lower bounds the uncertainty quantified using the more accurate (but privacy and computation intensive) method that uses independent runs.
Related work on Checkpoint aggregations: (Chen et al. 2017 Izmailov al. 2018) explore checkpoint aggregation methods to improve performance in (non-DP DP) ML settings, but observe neg- ligible performance gains. To our knowledge, (De al. (2022) is the only work in the DP MI. literature that uses intermediate checkpoints post training. They apply an exponential moving aver- age (EMA) over the checkpoints of DP-SGD, and note non-trivial gains in performance. However, we propose various aggregation methods that outperform EMA on standard benchmarks.
2 IMPROVING ACCURACY BY AGGREGATING DP TRAINING CHECKPOINTS
In this section, describe our checkpoint aggregation methods, followed by the experimental setup we use for evaluation. Next, we detail our experimental results that demonstrate the significant gains in accuracy of DP ML models due to checkpoints aggregations.
2

---

Under review as a conference paper at ICLR 2023
Differential Privacy (DP) (Dwork al. 2006) is notion to quantify the privacy leakage from the outputs of data analysis procedure. A randomized algorithm M D + y is (e, 6DDD if, for all neighbouring datasets D, D' D (i.e.. datasets that differ in one data sample) and all measurable sets of outputs 5 _ y. we have IP (M) E S] S e IP (M( E S) +6. We add Gaussian noise to functions of bounded sensitivity ensure DP. We also use DP's post-processing property, i.c., any analysis on the outputs of a DP algorithm does not worsen its DP guarantees.
DP Preliminaries:
We consider two state-of-the-ar DP ML algorithms: 1) DP-SGD for the central learning setting, i.e., when all data is pooled at a central location, e.g., a server, and 2) DP-FTRL for the federated learning (FL) setting, i.e. when all private data is distributed across remote collaborative devices. The privacy analyses for both of these techniques involves composition across training rounds, allowing the release of all intermediate checkpoints computed during training.
2.1 CHECKPOINTS AGGREGATION METHODS
We propose two types of aggregation methods: parameter aggregation, and output aggregation. Pa- rameter aggregations compute a function of the parameters of intermediate checkpoints from DP run, and then use the resulting aggregate parameters for inference. On the other hand, output ag- gregations compute function of the outputs of the intermediate checkpoints, and use it for making predictions. These classes can encompass vast majority of possible aggregation algorithms, but for brevity, we experiment with two algorithms in each of the classes: exponential moving average and uniform past average that aggregate parameters, and predictions average and labels majority vote that aggregate outputs. Note that all of our aggregation algorithms post-process the checkpoints, and hence, do not incur any additional privacy cost. Additionally, our aggregation methods are general, i... they are applicable to any training algorithm that computes intermediate checkpoints.
2.1.1 PARAMETER AGGREGATION METHODS
Exponential moving average (EMA): EMA has been previously used (Tan & Le 2019 Brock al.) 2021) to improve the performance of ML models inference time. Starting from the last checkpoint of the run, EMA assigns exponentially decaying weights to each of previous checkpoints; the weights are function of the EMA coefficient 3g at step I. During training, at each step 4, FMA
maintains moving average o &ema that is a weighted average of 05-1 and the 4hh checkpoint, 0²
This is formalized as follows: 0' &'ma (1 - 3c) Ot-l + 3 0¹. Following (Tan & Le 2019
De
1+t al. 2022), we use a warm-up schedule for the EMA coefficient as: Br = min [,
10+1
Uniform past k average (UPA): For step t of training, UPA computes the mean of the past k check- points, i.c., checkpoints from steps [t - (k - 1), t). We formalize this as: 0t Ei=(-(h-1) 0²
2.1.2 OUTPUT AGGREGATION METHODS
Output predictions averaging (OPA): For given test sample x, OPA first computes prediction vectors fo: (x) of the past & checkpoints, i.e., checkpoints from steps E [t - (k - 1), t). averages the prediction vectors, and computes argmax of the average vector the final output label. We
formalize OPA as Dopa(2> (x) argmax El for (x)).
Output labels majority vote (OMV): For given test sample x, OMV computes output predic- tion vectors for x and the corresponding labels. i.c., argmax (x). Finally, it uses the majority label among the labels (breaking ties arbitrarily) as its final output label. We formalize OPA as Jomv (x) = Majority (argmax (o (x)) (
2.2
EXPERIMENTS
2.2.1
EXPERIMENTAL SETUP
Datasets: We evaluate our checkpoints aggregation algorithms on three benchmark datasets in two different settings: CIFAR10 (Krizhevsky et al. 2009) and CIFAR 100 for image classification, and simulated federated learning over StackOverflow (Kaggle 2018) for next word prediction. Privacy guarantees sample-level for CIFAR tasks and user-level for StackOverflow (as it is keyed by
3

---

Under review as a conference paper at ICLR 2023
users). For experiments with DP, we fix the privacy parameter d to 10 on 100, and 10 on StackOverflw, ensuring that 8 < n where n is the number of examples in and the number of users in StackOverflow.
Model architectures, and training details: Following the setup of the state-of-the-art (SOTA) in [De et al. 2022). we train WideResNet- 16-4 with depth 16 and width 4 using DP-SGD (Abadi al.
2016b) in JAXline (Babuschkin et al. 2020 for = E {1, 8). For CIFAR100, we follow (De 2022) and fine-tune the last, classister layer of WideResNet-28. 10 pre-trained on ImageNet data. For StackOverflow, we follow SOTA in (Kairouz al. 2021 Denisov et al. 2022) and train a one-layer LSTM using DP-FTRI. in TFF (Abadi et al. 201 for 18.2, 18.9) J. For UPA, OPA and OMV, we treat k. the number of checkpoints to aggregate, as a hyperparameter and tune it using validation data. All our results are computed over 5 runs of each setting, We provide additional details of our experimental setup in Section B.I
et al.
2.2.2 EXPERIMENTAL RESULTS
First, we discuss the results for original datasets and then for more practical periodic distribution shifting datasets. Below, the tables present results for the final training round/step, i.e., for the aggregates computed until the last step/round, while plots show results over the last k rounds for some k much smaller than total number of training steps/rounds. For StackOverflow, due to large size of its test data, we provide plots for accuracy on validation data and tables with test accuracy.
CIFARIO results: Table and the left-most two plots Figure I present the accuracy gains in CIFARIO for {1,8), For 1, OPA provides the maximum accuracy gain of 3.79%, while for = 8, EMA provides maximum gain of 2.23% We note from Figure [ that all checkpoints aggregations improve accuracy for all the training steps of DP-SGD for both E's. Next, note from Figure that the accuracy of baseline DP-SGD has a high variance across training steps, i.e., based on the hyperparameters, DP-SGD can produce bad/good models which can be undesirable in prac- tice. However, checkpoints aggregations significantly reduce the variance in accuracy of models, and therefore, increase the confidence in the final DP-SGD model.
CIFAR10. Sample g
CIFAR1O, Sample level
StackOverllow, User level
StackCverflow, User level =0.9
79.5
56-
23.0
22.0
24.3
Accuracy (8g)
55
78.5
22.6
24.0
54
78.0
22.7
23.9
22.5
77.0
22.5
23.7
76,5
22.4
50
22.3
1395
2023 round
2038
2020 2035 2045 FL round
Train
Train
Outputs majority Figure 1: Accuracy improvements due to checkpoints aggregation methods for DP-SGD trained CIFARTO and DT-FTRI trained StackOverflow.
Baseline
Params EMA
Params average
Outputs average
StackOverflow results: Table I and the rightmost two plots in Figure present the accuracy gains in StackOverflow for E {18.9, 8.2): Figure plessent the results for 0o. The maximum accuracy gains are 0.57%, 0.43%, and 0.42% for of co. 18.9, and 8.2, respectively. We observe that UPA aggregation always provides the best accuracy. Note that these improvements are very significant, because there are 10,004 classes in StackOverflow data. Similarly for CIFARIO. 10, Figures | and 5 show that checkpoints aggregations improve accuracy for all training rounds by large margins and also significantly reduce the variance of model accuracy across training rounds. Note that these improvements are on top of the momentum optimizer used during training.
present
CIFAR100 results: Due to space constraints, we defer the results to Table 7 in Appendix B and discuss the major observations here. First, we improve the SOTA baseline De al. 2022 from
Note that EMA (with default EMA coefficients from non con-private settings) has also been used in De et al. coarse -oasine tuning of the EMA coeffi- cient provides significant accuracy gains. For instance, for CIFAR 10, our tuned EMA coefficients outperform those De et al. (2022) by ~ 0.6% and 0.35% for E of and 8, respectively.
(0022) to improve DP-SGD'S s performance. We observe that
2or CIFAR 100) Bu et al. 2022 achieve SOTA accuracy of 83% at using 303M parameters vision transformers pre-trained ImageNet21k. However, due computational constraints, we use the 36M pa-
4

---

Under review as a conference paper at ICLR 2023
Table 1: Test accuracy gains for original CIFARIO and StackOverflow.
Aggregation algorithms
Privacy level
None (Baseline)
Parameters aggregation
Outputs aggregation
EMA
UPA
OPA
OMV
CIFARIO I0; DP-SGD; sample-level privacy
77.18 + 1.46
79.41 + 0.51
79.39 1 0.52
79.4 + 0.59
79.34 1 0.54
=
52.83 + 2.17
56.61 + 0.91
56.62 + 0.89
56.68 + 0.89
56.4 = 0.69
StackOverflow DP-FTRL; user-level privacy
25.24 + 0.16
25.72 + 0.02
25.81 + 0.02
25.79 + 0.01
25.78 + 0.01
18.9
23.41 + 0.08
23.56 + 0.02
23.84 + 0.01
23.6 + 0.02
23.57
= 0.02
8 8.2
22.28 1 0.08
22.43 1 0.04
22.7 0.03
22.57 1 0.04
22.52 1 0.04
70.6% to 75.51% at e = 1, and from 77.6% to 80.8% at E To achieve these gains, we perform fine-tuning over the EMA checkpoint of ImageNet-truined WRN-28- 10 instead of the final checkpoint as in (De et al., 2022). Subsequently, we observe that for fine-tuning using CIFAR100 100, checkpoint aggregations provide small accuracy gains: for both E of I and 8, we observe maximum gains are 0.11% due to UPA and OPA, respectively.
2.2.3 ACCURACY IMPROVEMENTS IN PERIODIC DISTRIBUTION SHIFTING SETTINGS
In many real-world settings, for instance, in federated learning (FL) settings, training data distribu- tion may vary over time. /Zhu et al.] (2021) demonstrate the adverse impacts of distribution shifts in training data on the performances
resulting FL models. Considering the practical significance of such distribution shifts, we consider settings where the training data distribution has diurnal variations, i... it is a function of two oscillating distributions, D1 and D2; Figure 2 shows these distributions. Such scenario commonly occurs in FL training, c.g., when a model is trained using FL with client devices participating from two significantly different time zones.
Experimental setup: Following Zhu et al. (2021), we con- sider a setting where training data is a combination of clients/samples drawn from two disjoint data distributions, which oscillate over time as Figure shows. Here the prob- ability of sampling from, e.g., D1, at time t is p(Di, [2 mod T - 1/. where T is the period of oscillation of (1.2)-
Linear periodic distribution shifts
1.0
P(Sampling)
0.0
0.6
play
0.4
p(Ds)
To simulate such diurnal distribution, for CIFAR datasets, we design (12 such that Dj and D2 respectively contain the data from even and odd classes of the original data. For Stack- Overflow, we design (1)2)) such that Dj only has the ques- tions from each user, while D2 only has answers from them. Then, we draw clients from 111.2-- Apart from data distribution, the rest of experimental setup is the same as before. We use test and validation data same as for the original StackOverflow setting.
200
Time
Figure 2: Probability of sampling data from distributions D1 and Dz-
CIFAR1O results: Table 2 and Figure 3 (left two plots) show accuracy gains for diurnal CIFARIO. We note very large accuracy gains for both E E {1; the absolute accuracy gains are 7.45% and 17.37%, respectively, and are due OPA. Observe that, such diurnal settings have large variances in accuracy across training steps, but our aggregation methods almost completely eliminate the variances. We note that the improvements in diurnal settings are significantly more than that in original CIFARIO. 10. This is because in diurnal settings, the variances in model accuracy over training steps is very large, and hence, the benefits of checkpoints aggregations magnify in these settings.
StackOverflow results: Table and Figure 3 (rightmost two plots) present accuracy gains for di- urnal StackOverflow. The maximum accuracy gains are 0.09%. 0.44%, and 0.51% for of co, 18.9, and 8.2, respectively. In contrast to the diurnal CIFAR 10 case, improvements in diurnal Stack- Overflow and SterkOverflow are similar. This is because the two distributions in diurnal CIFAR10 (completely different images from even/odd classes) are significantly farther apart compared to the two distributions in diurnal StackOverflow (text from questions/answers).
rameter WRN pre-trained on downsampled ImageNetlk k from De et al. (2022). Moreover, similar De et al. 2022 observe that in small regimes, fine-tuning only the classifier layer provides better accuracy.
5

---

Under review as a conference paper at ICLR 2023
CIFARIO,
StackOverflow
PDS StackDverflow
20.6
12.00
50
Accurscy (30
20
23.50
K5
20.0
21.25
20.2
23.00
60
16.6
23.35
25
20.50
19.2
20.25
1194 1215
1269 Train stop
1254
5594
5554 5979 Train stop
5629
2504
2018
2028
1946.
2058
2018
2008
2338
2048
FL /u.undd
FL
mund
Baseline
average
Outputs average
Outputs majority
Figure 3: Accuracy gains due to checkpoints aggregations for DP-SGD trained periodic distribution shifting (PDS) CIFARIO (test data) and DP-FTRL trained PDS StackOverflow (validation data).
Table 2: Test accuracy gains for periodic distribution shifting (PDS) CIFARIO and StackOverflow.
Aggregation algorithms
Privacy level
None (Baseline)
Parameters aggregation
Outputs aggregation
EMA
UPA
OPA
OMV
PDS CIFARTO; DP-SGD; sample-level
privacy
E = 8
60.74 + 1.75
78.24 = 0.92
77.92 + 0.89
78.27 = 0.84
77.99 + 0.94
E = 1
47.13 1.76
54.04 = 0.81
54.35 + 0.9
54.58 0.82
54.03 1.08
PDS StackOverflow; DP-FTRL; user-level privacy
E 0
23.89 + 0.14
23.92 + 0.12
23.98 + 0.02
23.87 + 0.01
23.91 + 0.07
8 18.9
21.6 = 0.13
21.82 0.07
22.04
0.11
21.99 0.13
21.95 0.16
8.2
20.24 0.29
20.36 0.06 20.75
0.05
20.67 0.03
20.72 0.16
CIFAR100 results:
Due space constraints, defer full results in Table g in Appendix B For
CIFAR 100 also, we observe significant gains due to checkpoints aggregations in PDS setting: for of and 8, we note maximum gains of 4.96% (due to UPA) and 3.37% (due EMA), respectively. Similar to CIFAR1O, the gains due to checkpoints aggregation are significantly higher for PDS- CIFAR100 than for non-PDS CIFAR100.
Table 3: Accuracy gains on test data due to data-dependení checkpoints aggregations for Stack- Overflow (SO) and periodic distribution shifting StackOverflow (PDS-SO trained using DP-FTRL.
Privacy level
Dataset
Baseline
Best of data-independent
Best of data-dependent
SO
25.24 + 0.16
25.81 + 0.02 (UPA)
25.97 + 0.01 (UPA)
8 00
PDS-SO
23.89 + 0.14
23.98 + 0.02 (UPA)
24.18 + 0.02 (EMA)
SO
23.41 + 0.08
23.84 +.0.1 (UPA)
23.92 + 0.03 (UPA)
8 = 18.9
PDS-SO
21.60 0.13
22.04 0.111 (UPA)
22.18 + 0.07 (EMA)
SO
22.28 = 0.08
22.70 0.03 (UPA)
22.80 + 0.05 (UPA)
E = 8.2
PDS-SO
20.24 = 0.29
20.75 = 0.05 (UPA)
20.90 + 0.06 (UPA)
2.3
DATA-DEPENDENT CHECKPOINT SELECTION FOR AGGREGRATION
So far, our aggregated methods operated over fixed sequence of checkpoints, e.g., past k. However, when some public data similar the private training data is available, we propose a data-dependent checkpoint selection method for aggregation: aggregate the checkpoints that perform the best on the (held-out) public data. We expect this to improve over data-independent aggregation schemes. We validate this hypothesis for StackOverflow dataset. We use 10,000 random samples (less than 0.01 % of the training data) from the Stack Overflow validation data as the held-out public data. Note that this is disjoint from the validation data that we use for hyperparameter tuning. We omit the CIFAR datasets from this evaluation due to the lack of availability of additional similar data.
We compute accuracy of all training checkpoints the held-out data, find the best & checkpoints, and aggregate them as detailed above. We tune the hyperparameter & using disjoint validation data. Table 3 presents the gains due to data-dependent aggregations over the baseline and data- independent aggregations; Tables 5 and in Appendix B present full results 3 We see that data-
Note that only the data-dependent aggregations use public data, this comparison just for illustration.

---

Under review as a conference paper at ICLR 2023
dependent aggregations outperform cate-independent aggregations for all E's. For instance, at E of 8.2, accuracies of baseline, intaeiddeenndent and data-dependent aggregations are 22.28%, 22.7% and 22.8%, respectively. For c're's oo and 18.9, aggregating best past i checkpoints outperform aggre- gating past k: checkpoints (baseline) by 0.16% (0.73%) and 0.08% (0.51 %), respectively. We make the same observation for diurna PDS StackOverflow dataset-the maximum accuracy gains due to data-dependent aggregations are 0.29%, 0.58% and 0.66% for of co, 18.9, and 8.2, respectively.
2.4 IMPROVED EXCESS RISK VIA TAIL AVERAGING
In this section, we formally show that checkpoint aggregations like uniform tail averaging provably improves the privacy/utility trade-offss, compared to that of the last checkpoint of DP-SGD, To for- malize the problem, we define the following notation: Consider a data set D = {d1,-.. ........d,, dn and
loss function C(0; D) +/2 Σ 2(0;d:). d:). where each of the loss function is convex and L-Lipschitz
in the first parameter, and 0 E C with C S TR being convex constraint set. We analyze the following variant of DP-SGD, which is guaranteed to p-ZCDF
1. 8o + 0
2. For & E [T], Oz+1 + IIc (0,- - The (VL(0,; D) + b,)), where by ~ N (o, 2mp pxp) and
L'T
Ic (-) being the fz-projection onto the set C.
We will provide the utility guarantee for this algorithm by directly appealing to the result of Shamir & Zhang (2013). For given (0, 1), UPA (Section 2.1.1p corresponds the average of the
last of models, i.e., Opriv
Σ
O2. One can also consider polynomial-decay averaging
(=11-))++1
(PDA) with parameter 7 2 O, defined as follows: Oprix [t] (1
@pein [t 1] 3+1 0,.
For = 0, PDA matches UPA over all iterates. As increases, PDA places more weight on later iterates; in particular, y = cf', the averaging scheme is very similar EMA (Section I...I] since In that sense, PDA can viewed as as + T the decay parameter E-y approaches a constant I a method interpolating between UPA and EMA.
7+1
Theorem 2.1 (Adapted from Theorems and 4 Shamir & Zhang (013)). Consider the DP-SGD
algorithm above, and the associated parameters. Then there exists choice of learning rate T) and the number of time steps T s.t. the following are true for a (1)):
E. [C (AR D)] -min L(0; D) = O [Illllavv)) (4 ). and TE. [E(Or; D)] - min L((0; D) = =0 [1I011yPlog(m)
REC
BEC
Furthermore, for = (1), we have, E c (optiv (T]: D)]
min L(0;; D) O [.I1C up
BEC
Proof. If we choose T = [np]] and set nh appropriately. the proof of Theorem 2 Shamir & Zhang
2013) implies the following for Opriv : E [ (Opris D)]
min [(:; D) = O L|[C ove np
log (1)
BEc
Setting (1)) gives the theorem's 's first part, and aT 1, i.e., 1/a T [np] gives the second. The third follows from modifying Theorem 4 of Shamir & Zhang (2013) for the convex case (sce the end of Section 4 of Shamir & Zhang (0013) for details).
geriv The excess empirical risk for fy is higher by factor of log(n) in comparison to 6priv and pda [T]. For the step size selections typically used in practice (e.g., fixed or inverse polynomial step sizes), the last iterate will suffer from the extra log(n) factor, and we do not know how avoid it. Furthermore, Harvey et al. 2019) showed that this is unavoidable in the non-private, high probability regime
$ *Using Bun & Steinke (0166), easy convert the privacy guarantce (e, 6DP guarantee.
show that for carefully chosen step sizes, the logarithmic factor can be removed, and Feldman et al. 2020 extend this analysis to DP-SGD variant with varying batch sizes. Unlike those methods,
JJinn et al. 2202
averaging he done as post-processing of DGD outputs, rather than modification of the algorithm.
7

---

Under review as a conference paper at ICLR 2023
3 QUANTIFYING UNCERTAINTY IN PREDICTIONS DUE TO DP NOISE
In this section, we discuss our proposal of how to quantify the uncertainty that the differential privacy (DP) noise adds to the outputs of ML algorithms, without additional privacy cost or computation. First, we discuss the issues with the current established approach of uncertainty quantification in ML when used in DP setting, and then discuss our proposal and theoretical results. Finally, we provide experimental results that demonstrate the practical utility of our approach.
(Naive) uncertainty quantification, and its hurdles: As discussed in Section 1 although uncer- tainty quantification has long history of research, prior methods, including the most common independent runs method, are not applicable in DP settings. The two major issues with the indepen- dent runs method DP settings are: First, the additional runs of DP-ML algorithm can incur a significant increase in the privacy cost. Second, the additional computation required in independent runs method can be prohibitive, e.g., production FL. Hence, it is not feasible to use the naive method for uncertainty quantification in DP settings.
3.1 Two BIRDS, ONE STONE: OUR UNCERTAINTY QUANTIHICATION PROPOSAL
To address the two hurdles discussed above, we propose a simple yet efficient method that leverages intermediate checkpoints computed during DP run. Specifically, from the independent runs method with & checkpoints, c.g., the last & checkpoints, from a single DP run. The rest of the confidence interval computation is the same for both the methods. Specifically, we compute the most likely classification labels of the I models/checkpoints on a test input. Use the set of & output labels as a sample from the student's 's t-distribution and compute confidence interval of the mean of the distribution. Finally, we use the average of multiple such intervals over multiple test inputs as a proxy for uncertainty of outputs of the DP ML algorithm.
substitute the & output models
3.1.1 THEORY
In this section, we give a theoretical motivation for using checkpoints to estimate the variance of statistic. We show that under certain assumptions, if we take the sample variance of a statistic (() computed at the checkpoints .i...... O2g in expectation it is good approximation of the sample variance of the limiting distribution of DP-SGD. As expected, the quality of the approximation improves by increasing the length of the "burn-in" time as well as the time between checkpoints. To simplify the proof, we actually prove the theorem for DP-LD, a continuous-ting version of DP- SGD. DP-LD be defined as follows. We first reformulate (unconstrained) DP-SGD with step size 17 as: ((+1)) + Bi, C(Oon D) + b, (0, In00)pxp)
Notice that we have reparameterized so that its subscript refers to the sum of all step-sizes so far, Le. after t iterations we have te, and not 0.. Also notice that the variance of the noise we added is proportional to the step size 17. In turn, for any 1j that divides f, after t/1 iterations with step size n), the sum of variances of noises added is 2la2. Now, taking the limit as 1) goes of the sequence of random variables (tm) defined by DP-SGD, we get a continuous sequence (0, (e In particular, if we fix some t, then 0g is the limit as 17 goes to 0 of og defined by DP-SGD with step size 17. This sequence is exactly the sequence defined by DP-LD,, which is more formally given by the following stochastic differential equation:
d0,- C D)dt + 2dW,
(1)
Here, We is standard Brownian motion and o² is analogous to the variance of noise added in SP-SGD. In Appendix A we show the following:
Theorem 3.1 (Simplified version of Theorem[A.I]. Suppose L is I-strongly convex and M- Msmmotth, and a = in (T). Let 0 < < l2 < ... lu be such that li+1 4, + 7, Vi 0 and some E [K]} be the checkpoints, and f :: --1 [-1,1] be a statistic whose variance we wish estimate. Let S be the sample variance of f over the checkpoints, and V be the variance of (Orr), ), i.e. the statistic at the final checkpoint. Then, for some "burn-in" time B that is a function
y. Let [0.,
of M. p. we have: [[[ V| = exp(- (oo((mmmm((t) -B))
Intuitively, Theorem A. and its proof say the following: (i) As we increase fi, the time before the first checkpoint, each of the checkpoints' marginal distributions approaches the distribution of o
8

---

Under review as a conference paper at ICLR 2023
and (ii) As we increase y, the time between checkpoints, the checkpoints' distributions approach pairwise independence. So increasing both t and causes our checkpoints to approach & pairwise independent samples from the distribution of 0z,, i.., our variance estimator approaches the true variance in expectation. To show both (i) and (ii), we build upon past results from the sampling liter- ature to show mixing bound of the following form: running DP-LD from any point initialization Do. the Rényi divergence between 0g and the limit as t + oc of DP-LD, 8x. decays exponentially in t. This mixing bound shows (i) since if 1 is sufficiently large, then the distributions of all of 8,, Bez..... Big are close to fxc, and thus close to each other. This also shows (ii) since DP-LD is a Markov chain, i.e. the distribution of 8,, conditioned on 8t, is equivalent O,y-1. if we run DP-LD starting from Oz. instead of Oo. So our mixing bound shows that even after conditioning on o.., O2 has distribution close to 0x- Since 02 is close to 2x conditioned on any value of O2 then 02, is almost independent of Oz.-
the distribution of
Empirical analysis: We compare the uncertainty quantified using the independent runs method and us-
StackOverflow
CIFAR10
00:45
0.25
Confidence Interval width width
c=1. Indaparden rurs
0.040
0.20
C-1, Checkpoints
Indeperdent
ing our method; experimental setup is the same as in Section 1.2.1
0.025
cm Checkpoints
0.25
0.330
First, for both StackOverflow and CI- FARIO datasets, we do 100 indepen-
0.20
0.225
dent training runs. Then to com- pute uncertainty using the indepen- dent runs method, we take the final model from k of these runs (chosen randomly), compute prediction labels for given input, compute confidence interval widths for the input, and fi- nally, use the average of confidence interval widths of large number of inputs as the final uncertainty estimate. To compute uncertainty using checkpoints based method, we instead select our k models to be the last k checkpoints of a random training run, and obtain average confidence intervals as before.
0.220
30
40
50 60
70
90
300
20 30 60 Number of samples (N)
10
50 100
Number of samples (N)
Figure 4: Uncertainty due to DP noise measured using con- fidence interval widths. We compute the intervals using N bootstrap (independent) runs, and using the last N check- points of single run.
Figure 4 shows the results for StackOverflow and CIFAR10. Plots show intervals averaged over 5 runs, i.e., by sampling l final models 5 times or by using the last models of 5 random runs. We observe that uncertainty computed using the intermediate checkpoints consistently give a reasonable lower bound on the uncertainty computed using the independent runs.
4 CONCLUSIONS
In this work, explore methods for aggregating intermediate checkpoints to improve the utility of DP training. Using checkpoints aggregation methods, we show significant improvements in predic- tion accuracy over the SOTA for CIFAR and StackOverflow datasets. We also show that uniform tail averaging of checkpoints improves the ERM bound compared to the last checkpoint of DP-SGD. Lastly, we prove that for some standard loss functions, the sample variance from last few checkpoints provides a good approximation of the variance of the final model of DP run. We also conduct ex- periments demonstrating that the last few checkpoints can provide a reasonable lower bound for the variance of a converged DP model. For future work, using checkpoint aggregates during DP training could be an interesting direction to further improve its utility. Leveraging intermediate checkpoints to provide variance estimates for checkpoint aggregates could also be promising direction.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint 16XX3v6603.00 04467, 2016a.
'To our knowledge, all prior mixing results for DP-LD require that the a- R-Rényi divergence between d and 0x is finite for some >> 1 or some stronger assumption, which cannot be satisfied by point distribution for Pp. Thus, our mixing result for DP-LD starting from point distrihution may he of independent interest.

---

Under review as a conference paper at ICLR 2023
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proc. of the 2016 ACM SIGSAC Conf. Computer and Communications Security (6)S'16), pp. 308-318 2016b.
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, Rajendra Acharya, et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges.
Information Fusion, 76:243-297, 2021.
Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror de- scent for private model training. In International Conference on Machine Learning, pp. 517-535. PMLR, 2022.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially pri- vate learning with adaptive clipping. In Advances in Neural Information Processing Systems, volume 34, pp. 17455-17466, 2021.
Giuseppe Ateniese, Giovanni Felici, Luigi Mancini, Angelo Spognardi, Antonio Villani, and Domenico Vitali. Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers. arXiv preprint arXiv: 34330044447 2013.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, John Quan, George Papamakarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Luyu Wang. Wojciech Stokowiec, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL http:://githuu.ccmm wwtpssommmeeemmeeeeeeeeeee nd
Borja Balle, Peter Kairouz, Brendan McMahan, Om Thakkar, and Abhradeep Guha Thakurta. Pri- vacy amplification via random check-ins. Advances in Neural Information Processing Systems,
33:4623-6634 2020.
Andrés F. Barrientos, Jerome P. Reiter, Ashwin Machanavajhhala, and Yan Chen. Differentially private significance tests for regression coefficients. Journal of Computational and Graphi- cal Statistics, 2802)4400-53, 2019, doi: 10. 10.1000/10618600 860006611.0..0..... 1533881.
URL https:
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS). pp. 464 473, 2014.
Edmon Begoli, Tanmoy Bhattacharya, and Dimitri Kusnezov. The need for uncertainty quantifi- cation in machine-assisted medical decision making. Nature Machine Intelligence, 1(1):20-23, 2019.
Leonard Berrada, Soham De, Jamie Hayes, Samuel L Smith, and Borja Balle. JAX-Privacy: Algorithms for Privacy-Preserving Machine Learning in JAX. 2022. [Online; accessed 15 S--eeteember-2022.
deepminddjax.pprie
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman- JAX: composable transformations of Python+NumPP programs, 2018. BBL.htttp://githbb.o.
Thomas Brawner and James Honaker. Bootstrap inference and differential privacy: Standard errors for free. Unpublished Manuscript, 2018
Andy Brock, Soham De, Samuel L. Smith, and Karen Simonyan. High-performance large-scale image recognition without normalization. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 1059 1071. PMLR, 2021. URL htlp: http:://pprcceeee ngs.m w.pp.ss./.139/////eessp
10

---

Under review as a conference paper at ICLR 2023
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. arXiv preprint 2tt.:2200..0688.. 2022.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
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), pp. 267-284, 2019.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Frlingsson, et al. Extracting training data from large language models. 30th USENIX Security Symposium (USENIX Security 21), pp- 2633-2650, 2021.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Mem- bership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914, IEEE, 2022.
Hugh Chen, Scott Lundberg, and Su-In Lee. Checkpoint ensembles: Ensemble methods from single training process. arXiv preprint arXiv:/710.03222, 2017.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
Sergey Denisov, Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. arXiv preprint arXiv:2202.08312 2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pp. 265-284, 2006. URL
/olgg//1.11000 10.1007/1111 6818 18_144
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. Timothy M. Chan (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Sym- posium Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 2468-2479. SIAM, 2019. doi: 10. 11111399778611197552222811 10.1137/1.978111 /tt 1975482.151
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Tal- war, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. CoRR, abs/2001.03618, 2020. URI.
(200100318]
Georgina Evans, Gary King, Margaret Schwenzfeier, and Abhradeep Thakurta. Statistically valid inferences from privacy protected data. American Political Science Review, 2020.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Proc. of the Fifty-Second ACM Symp. on Theory of Computing (STOC'20), 2020.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954 964. IEEE, 2022.
Cecilia Ferrando, Shufan Wang, and Daniel Sheldon. Parametric bootstrap for differentially private confidence intervals. In International Conference on Artificial Intelligence and Statistics, pp- PMLR, 2022.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confer- on Computer and Communications Security. ACM, 2015.

---

Under review as a conference paper at ICLR 2023
Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing. In USENIX Security Symposium, 2014.
Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin MCMC. CoRR, abs/2010. 14658, 2020. URL abs/2010 201 0.1 4658
Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In COLT, 2019.
Christian Hubschneider, Robin Hutmacher, and J Marius Zöllner. Calibrating uncertainty models for steering angle estimation. In 2019 IEEE intelligent transportation systems conference (ITSC), pp. 1511-1518. IERE, 2019.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Averaging weights leads to wider optima and better generalization. In 34th Conference Un- certainty in Artificial Intelligence 2018, UAI 2018, pp. 876-885. Association For Uncertainty in Artificial Intelligence (AUAI), 2018.
Prateek Jain, Dheeraj M. Nagaraj, and Praneeth Netrapalli, Making the last iterate of sgd information theoretically optimal. SIAM Journal on Optimization, 1102):108-11133 2021. doi: 10.1137/
19M128908X. /tA.L/ppp////b...o/11111//////// 109
Kaggle. The StackOverflow data.
https::/www.kaggle.com wtt.s/attcccccttttet/seasoc.s
stackoverflow/sttcckoooo
2018. [Online; accessed 2--September-20222,
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pp. 5213-5225. PMLR, 2021.
Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03900 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Saeed Mahloujifar, Esha Ghosh, and Melissa Chase. Property inference from poisoning. In 2022 IEEE Symposium on Security and Privacy (SP). pp. 1569. IEEE Computer Society, 2022.
Patrick I. McDermott and Christopher K Wikle. Deep echo state networks with uncertainty quan- tification for spatio-temporal forecasting. Environmetrics, 30(3): 2019.
Brendan McMahan, Abhradeep Thakurta, Galen Andrew, Borja Balle, Peter Kairouz, Daniel Ra- mage, Shuang Song, Thomas Steinke, Andreas Terzis, Om Thakkar, and Zheng Xu. Federated learning with formal differential privacy guarantees, https: http:::://a..gooo /ttp//aa..iggoo.//////oo/// www.eelll...ccoo00000 02/federated- -eaondd-erannnnn with for.al.l.sssoo. 2022. [Online; accessed 15-September- 2022].
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06965 2017.
Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, Ilya Mironov, Nicolas Paper- not, and Peter Kairouz. A general approach to adding differential privacy iterative training procedures. arXiv preprint arXiv.1812.06210. 2018.
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. 2019 IEEE symposium on security and privacy (SP), pp. 691-706. IEFF, 2019.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Sym- posium (CSF), pp. 263-275. IEFF, 2017.
12

---

Under review as a conference paper at ICLR 2023
Tom M Mitchell. The need for biases in learning generalizations. Department of Computer Science, Laboratory for Computer Science Research ..., 1980.
Tanya Nair, Doina Precup, Douglas L Arnold, and Tal Arbel. Exploring uncertainty measures in deep networks for multiple sclerosis lesion detection and segmentation. Medical image analysis, 59:101557, 2020.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Machine learning with membership privacy using adversarial regularization. In Proceedings of the 2018 ACM SIGSAC conference computer and communications security, pp. 634 646, 2018.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pp. 84, 2007.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ülfar Frlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint arXiv:2007. 14191, 2020.
Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H Brendan McMahan, and Françoise Beaufays. Training production language models without memorizing user data. arXiv preprint arXiv:2009. 10031, 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
Abhijit Guha Roy, Sailesh Conjeti, Nassir Navab, and Christian Wachinger. Inherent brain segmen- tation quality control from fully convnet monte carlo sampling. In International Conference on Medical Image Computing and Computer-Asiisted Intervention, pp. 664-672. Springer, 2018.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In International Conference on Machine Learning, pp. 71-79, 2013.
Virat Shejwalkar and Amir Houmansadr. Membership privacy for machine learning models through knowledge transfer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9549-95597 9957,955777 2021.
Virat Shejwalkar, Huseyin A Inan, Amir Houmansadr, and Robert Sim. Membership inference at- tacks against nlp classification models. NeurlPS 202/ Workshop Privacy in Muchine Learning. 2021.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-1 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.
Natasa Tagasovska and David Lopez-Paz. Single-model uncertainties for deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Mingxing Tan and Quoc V. Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Cali- fornia, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6105-6114, PMLR, 2019.
9a.htm1
Xinyu Tang, Saeed Mahloujifar, Liwei Song, Virat Shejwalkar, Milad Nasr, Amir Houmansadr, and Prateek Mittal. Mitigating membership inference attacks by {Self- Seeff-Distillation) through novel ensemble architecture. In 31st USENIX Security Symposium (USENIX Security 22), pp. 1433- 1450, 2022.
13

---

Under review as a conference paper at ICLR 2023
Om Thakkar, Galen Andrew, and H Brendan McMahan. Differentially private learning with adaptive clipping. arXiv preprint arXiv:1905.0387)) 2019.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations, 2020.
Tim van Erven and Peter Harremos. Rényi divergence and kullback- divergence. IEEE Trans- actions on Information Theory, 6017):3777-3820, 2014. doi: 10. (0.1109/TT1:20142320050
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' AAlcéé-Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL 65a99bb7a31 wat.aa1155ffaa Tow.aaaTToaaa0aa000000000000---0
Guotai Wang, Wenqi Li, Michael Aertsen, Jan Deprest, Sébastien Ourselin, and Tom Vercauteren. Alcatoric uncertainty estimation with test-time augmentation for medical image segmentation with convolutional neural networks. Neurocomputingg 338:34 45, 2019a.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled renyi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pp. 1226 1235, 2019b.
Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konečný, Andrew Hard, and Tom Goldstein. Diurall or nocturnal? federated learning of multi- networks from periodically shifting distributions. In International Conference on Learning Representations, 2021.
Yuqing Zhu and Yu-Xiang Wang. Poission subsampled rényi differential privacy. In International Conference on Machine Learning, pp. 7634-7642. PMLR, 2019.
14

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM A.1
For conveniencefformality. we review the setup for the theorem we wish to prove. Recall that given loss function L. by taking the limit goes to 0 in DP-SGD, recover the stochastic differential equation (T). restated here for convenience:
d0, = VV D)dt + /2w
Note that the solutions 0, to this equation are random variables. A key property of ① that the stationary distribution (equivalently, the limiting distribution / + 2o) has pdf proportional to exp(=2(0; D)/a) under mild assumptions on (which are satisfied by strongly convex and smooth functions).
To simplify proof's and presentation in the section, we will assume that (a) Og is a point distribution, (b) we are looking unconstrained optimization over R2, i.e., there is no need for projection operator in DP-SGD and (I) (c) the loss L 1-strongly convex and M-smooth, and (d) o 1. We note that (a) can be replaced with 0g being sampled from random initialization without too much work, and (c) can be enforced for Lipschitz, smooth functions by adding quadratic regularizer. We let 0 refer the (unique) minimizer of L throughout the section.
Now, we consider the following setup: We obtain single sample of the trajectory {0= : E [o, J- We have some statistic θ 0- [-1,, 1], and we wish estimate the variance the statistic for the final value Or, i.e. the variance V == Var (f())). To do so, we use the sample variance of the checkpoints at times < t t2 < t3 ... tt T. That is, our estimator is defined as S - I - 2 where ğ = _ E f(0..).
Theorem A.1. Under the preceding assumptions/seuup. for some sufficiently large constant c, let 23d + +In(cM + (1/ + 1100 0 (12) + cln(1/A) (recall that is the dimensionality of the space). Then, 1 7 and 1i+1 4 7 for all 0, for S, V as defined above:
[ES] - V O(A).
Before proving this theorem, we need few helper lemmas about Rényi divergences:
Definition A.2. The Rényi divergence of order support RRd), (P Q), is defined as follows:
between two distributions P and Q (with
P(0)a
(.(PQQ) JOER Q00)a11 do
We refer the reader to e.g. van Erven Harremos (2014); Mironov (2017) for properties of the Rényi divergence. The following property shows that for any two random variables close in Rényi divergence, functions of them are close in expectation:
Lemma A.3. [Adapted from Lemma C.2 of Bun & Steinke 2016 Let and Q two distributions on Ω and g Ω [-1, Then,
Em-p [g(x)] - Ean [s(z)] S VeDa(Pl10)
Here, (2( corresponds Rényi divergence of order two between the distributions P and Q
The next lemma shows that the solution to approaches 0.x exponentially quickly in Rényi diver- gence.
Lemma A4. Fix some point gp. Assume 1-strongly convex, and M-smooth. Let P be the distribution 0f according to [ = and:
t: 1/2M + In(e(M ||0 - pln(M)))
( cln(1/A)).
Where is sufficiently large constant. Let Q be the stationary distribution of (1) Then:
D2(P, 2) O(A2).
15

---

Under review as a conference paper at ICLR 2023
The proof of this lemma builds upon techniques in Ganesh & Talwar 2020), , and we defer it to the end of the section. Our final helper lemma shows that 8xc is close to 8" with high probability:
Lemma A.S. Let 2x be the random variable given by the stationary distribution of (I for 1.
If L is I-strongly convex, then:
Or - 10 vp+ + exp(-222
Proof. We know the stationary distribution has pdf proportional to exp(-L(0r; D)); In particular, since C is 1-strongly convex, this means 00 is a sub-Gaussian random vector (i.e., its dot product with any unit vector is a Sab-Gaussinn random variable), and thus the above tail bound applies to it.
We now will show that under the assumptions in Theorem A. every checkpoint is close to the stationary distribution, and that every pair of checkpoints is nearly pairwise independent.
Lemma A.6. Under the assumptions/setup of Theorem A.1
have:
(EI) Vi: -
- E((f((,,))) = -(A),
(E2) Vi: [B((f((,,))) - (f, 0(A),
(E3) Vi j |Cov (f(O,,), f(0,,) O(A).
Proof. We assume without loss of generality A is most sufficiently small constant; otherwise, since f has range |-1, 1], all of the above quantities can easily be bounded by 2, so a bound of O(A)
holds for any distributions on }
For (EI), by triangle inequality, suffices to prove a bound of O()) on -0, We
abuse notation by letting O, denote both the random variable and its distribution. Then:
V Dall(M) - (x))
(f - E(
Dettee -
Lemma
/OO(3)) - (#2) 0(A).
In (x1) we use the data-processing inequality (Theorem of van Erven Harremos 2014 4), and in
(x2) the fact e" - 2z, [0, 1] and our assumption on A.
(E2) follows from (E1) by just using f² (which is still bounded in [-1, 1]) instead of f.
For (E3), note that since T is (continuous) Markov chain, the distribution of 9t, conditioned on 0, is the same as the distribution of 0,, -t, according to (T) if we start from 0,, instead of 9g. Let P be the joint distribution of 6,,, 0r,- Let Q be the joint distribution of o.., Az0 (since (I) has the same stationary distribution regardless of its initialization, this is a pair independent variables). Let
P', Q' be defined identically to P, Q, except when sampling O::- if [0,, 00 /2t//2nn11/////// (n/AA instead set Og 0r (and in the case of P', we instead sample 0z, from 0, 10 0* when this happens). Let R denote this distribution over 0,,- Then similarly to the proof of (EI) we have:
Lemma A.
Ep Ep(1(0))000) Eg (000)0)
D2((P',
(+a)
maxo, Comot (DR (Da(Or, 18,, (oo))
Lemma A.4
(CO(A2) - -
Here (+a) follows from the convexity of Rényi divergence, and in our application of A.4 we are using the fact that for all 6,, supp(R), ||0, 8*112 I vp / (nn/A))) Furthermore, by Lemma we know P and p' (resp. Q and Q¹) differ by at most A in total variation distance. So,
since f bounded in [-1, 1], we have:
(0.)) Ep (000)00000
16

---

Under review as a conference paper at ICLR 2023
[e]((0.) -f0 )ll s A.
Then by applying triangle inequality twice:
[EP](()))((ee)] Eel1(00.)111(00=0 0(4)
Now we can prove (E3) as follows:
|Cov (J(Oe), [B((((,,)) - (ELTOO))-BLTOO))))00)---EEE
S -
1ttp://0000000-100000000-10---1- -[1 S 0(4) + [B]] =[
Proof of Theorem A.7 We again assume without loss of generality A is at most sufficiently small constant. The proof strategy will to express [E[S] in terms of individual variances Var (f,,..) which can be bounded using Lemma A.6
We have the following:
1
B|S]
E [(f(0.))
E
f(Oe.)
f(0r,)
k
k:
1=1
From 2 we have the following:
E [1. - y;) = E[x3] 2T
2T[ (n + [[y??
= [E[2 (B[xx])²) + -Eli
- (Elu)))) + (B[x:))) + (E(lx))2 2E [x.usl]
Var (I:a) Var (1s) (B(x:))² + (B(ue))² 2E (m.eil)
In the following, we bound each of the terms A, B, and C individually. First, let us consider the term B. We have the following:
B Var (y:)
1
Σ
Var (f(0r,)) +2 Σ
Cov (f(0e)). (4)
(k: 1)2
jE(H),iat
ISiSESk 17L07
Plugging Lemma A.6 (E3) into 4 we bound the variance of as follows:
B Var (v:) = (Is 1)2
1
Σ jE(M),iza
Var (F(Be,) + +(AA).
(5)
We now focus on bounding the term C' in Lemma A.6
(E1) and (E3) implies the following:
(E(x:))² (EE,f(e, +
(B|y/))² (BI]F(00))))
E [r,yv]] (E)
(8)
17

---

Under review as a conference paper at ICLR 2023
Plugging ( and into (3) we have
E [2: yz)²
Var (J(OL.)) (le 1)2
Σ
Var (f(O1;)) O(A).
JElA)
Now, Lemma A.6 (E1) and (E2) implies vi: |aar (f(6..) Var (f(O), )) 0 So from 9 we have the following:
E [Tt vi)² = Var (f(Ot)))
k h- = (A))
(10)
Plugging this bound back in (2). we have the following:
k E[$] 1-1 (xx)
(x-1)
k (Var k- =0(4) Var (f(O..)) (11)
Which completes the proof.
A.1 OPTIMIZING THE NUMBER OF CHECKPOINTS
In Theorem A.I we fixed the number of checkpoints and gave lower bounds the burn-in time and separation between checkpoints needed for the sample variance bound to have bias at most A. We could instead consider the problem where T, the time of the final checkpoint, is fixed, and want to choose which minimizes the (upper bound on) mean squared error of the sample variance of (f(or)))) )EE()) Here, we sketch solution to this problem using the bound from this section.
The mean squared error of the sample variance is the sum of the bias and variance of this estimator. We will use the following reparameterizatioo of Theorem A.
Theorem A.7 (Reparameterized version Theorem
A.1 Let C1 = 2M + In(e2 +
110 0r 12))), where 02 is sufficiently large constant.
Then if S is the sample variance of
(D(X)T/ V is the true variance of XT, and //k 61:
[[S] - -12 2 S exp (- T/k T
C2
One can also show the variance of is close to the true sample variance:
Lemma A.8. If $ is the sample variance of k i.i.d. samples of 0r, then if cg is sufficiently
large constant, for ej as defined theorem A.7
1 Var (8) Var (8) 2exp
T/k
Var (S) S
62
Proof: Let .i...., 2x be i.i.d. samples of f(0)), then since each x; is in the interval [-1,1]:
Biaf] k
Var (x1) (k 3)
Var (5)
k(k 14-11
K
Giving the first part of the lemma. For the second part, let æ; be the sampled value of f(0rry)).
Then:
2
Bis = E
P
k
k
KETA
JElK
For some coefficients C. this be written Eisjete
C.j.A.m E(a,,, where the change in this expecta-
Eisiersm lo.je.m < 2. By similar argument to Theorem A.
tion if we instead use æ; that are i.i.d. is then at most exp T/k-o as long as co is sufficiently
18

---

Under review as a conference paper at ICLR 2023
large constant. In other words, [[[S -[S]]] E[S], giving the second part of the lemma.
S exp
T/k-o cg
A similar argument applies to
Putting it all together, we have upper bound the mean squared error of the sample variance of:
(- (- [T/h - c1
k + 3 exp
Assuming k > 1,T/k > c1. Minimizing this expression with respect to k gives
T
c1 + ln
which we can then round to the nearest integer larger than I to determine the number of checkpoints use that minimizes our upper bound on the mean squared error. Of course, if 'T' 2c, then Theorem A. cannot be applied to give meaningful bias bound for any number of checkpoints, so this choice of is not meaningful in that case.
A.2 PROOF OF LEMMA
We will bound the divergences P.) D. Pa) where Pt is the distribution
Og that is solution to LT. P3 is Gaussian centered the point V/ D). P3 is a Gaussian
centered at 8", and P1 is the stationary distribution of (T). Then, inequality for Rényi divergences to convert these pairwise bounds into the desired bound.
the approximate triangle
Lemma A.9. Fix some 9g- Let P1 be the distribution of 6, that is the solution to ①I, and let Pd be the distribution N00 - 1/ L(0n; D), 21). Then:
(P,, Pa) O (M² In(a) max{m"² 100 -0 n²1)
Proof. Let 0e be the solution trajectory of ( starting from Gg and let 6% be the solution trajectory if we replace C(e;; D) with VL(6o: D). Then 6,, is distributed according to P1 and 6 is distributed according to Pz.
By a tail bound on Brownian motion (see e.g. Fact 32 in Ganesh Talwar (020 ) we have that (0.n) [ dW, WW I wr + ll26)))) w.p. 1 - 8. Then following the proof of Lemma 13
in Ganesh & Talwar (020). w.p. 1--6 5,
00 doll2 - cM cMP+ V
M 100 -0"11
=E(0.n)
for some sufficiently large constant and the same is true w.p. 1 - 5 over 0.- Now, following the proof Theorem 15 in Ganesh & Talwar (2020), for some constant c', we have the divergence bound (P,,,, P2) < long as:
M In2 a (mn) 22
1100 0'112 <c.
In other words, for any fixed n,, get divergence bound of:
Da 0 (M²In(a)) (MM2))a))) max(pr? 11:101100000
- -001
as desired.
Lemma A.10. Let P2 be the distribution N(e. L D), and P3 be the distribution N 2n). Then for < 2/M:
a 1100
0"
D. (P, P3)
4n
19

---

Under review as a conference paper at ICLR 2023
Proof. By contractivity of gradient descent have:
|10 - 1) 1 (do,; D) 0* 11 S 1 1-
Now the lemma follows from Rényi divergence bounds between Gaussians (see e.g., Example 3 of van Erven & Harremos 22144).
Lemma A.11. Let P3 be the distribution N(0", 2m) and let P1 be the stationary distribution of Then for n S 1/2M we have:
Da Pa) S O In(1//) - In((T) In(a//4T))
Proof. We have Po( P3(0 ex(()) 4n 110 11) where Pa(0*) 4m
1
By M-
smoothness of the negative log density of Pa. we also have Pa(0) 2 Pa(0") exp( 2 | 12)
2/2 In addition, since P4 is 1-strongly log concave, Pa(0*) 2 ) (as the 1-strongly log concave density with mode 8 that minimizes Pi(0*) ) is the multivariate normal with mean 0* and identity covariance). Finally, for 2 11 and 17 1/2M, have a/4n > (a 1)M/2. Putting it all together:
Ps(O)
exp((a 1)Da(Ps,PP))
Pa(0)a-1u0 d0
.
P4(O' aa-
exp
- 41j
(a
1)
110 0-1 d0
ap/2
(2m)
(2
((p0)/211/22 11/2
exp
(-(2) 4n
(ax
1) M
2 110 1-
dB
4m
1
0/2
op/2
exp
-
a
(a 1) 2222/ 110 0/ do
M
2T
2m
4n1
(
1
a/2
1
op/2
(a
1) M
p/2
2T
21)
m
0/2
op/2
p/2
a
2T
2m
4mn
D. < a 1
a
!
In (1/1)
In((T))
+ P
In In(a/4TT)
In (x), we use the fact that a/ An > (a 1)M /2 to ensure the integral converges.
Lemma A.12. Fix some point 0g. Let P be the distribution 0, that is the solution to ① from Op for time 1) S 1/2M. Let Q the stationary distribution of (T). Then:
Qa(P = [² max(pn? .0lm,1100 110 0'112 1100 1-112
pln(a/n).)
Proof. By monotonicity of Rényi divergences (see e.g., Proposition 9 of Mironov (2017)), we can assume a 2 2. Then by applying twice the approximate triangle inequality for Rényi divergences (see e.g. Proposition 11 of Mironov (2017)), we get:
D. (P Dsa (P1, Pa)
D Ps) Dsa-2
The lemma now follows by Lemmas A.9
A.10
A.II
Lemma A.4 now now follows by plugging a = 2, = 1/2M into Lemma A.12 and then using Theorem
2 of Vempala & Wibisono 2019).
20

---

Under review as a conference paper at ICLR 2023
Table StackOverflow LSTM architecture details.
Layer
Output shape
Parameters
Input
20
0
Embedding
(20, 96)
960384
LSTM
(20, 670)
2055560
Dense
(20, 96)
64416
Dense
(20, 10004)
970388
Softmax
B MISSING DETAILS FROM SECTION 2.2
Below we provide the experimental setup and results that are missing from Section 2.2
B.I EXPERIMENTAL SETUP
Training hyperparameters:
CIFARIO training: We use Jaxline (Bradbury et al. 2018) to train on CIFARIO using DP- SGD (Berrada et al. 2022). For CIFARTO,
WidekesNet with depth 16 and width 4. We fix clip norm to 1, batch size to 4096 and augmentation multiplicity to 16 as in (De et al.) (022). and 4 and 3 for & = 8. For periodic distribution shifting (PDS) CIFAR1O 10, we set learning rate and noise multiplier, respectively, and 12 for = and to 4 and for 8. We stop the training when the intended privacy budget exhausts.
Then, set learning rate and noise multiplier, respectively, 2 and 10 for
For CIFARIO0 also, we use Jaxline (Bradbury et al., 2018) and use DP-SGD to fine tune the last, classifier layer of a WideResNet with depth 28 and width 10 that is praited on entire ImageNet data. We fix clip norm 1, batch size 16.384 and augmentation multiplicity to 16 as in (De et al., 2022). Then, we set learning rate and noise multiplier, respectively. to 3.5 and 21.1 for & = and to and 9.4 for = 8. For periodic distribution shifting (PDS) CIFAR 100, set learning rate and noise multiplier, respectively, E =. We stop the training when privacy budget exhausts.
CIFARIOO training:
and 21.1 for I and to 5 and 9.4 for
We would like to highlight that obtain significant improvement over the SOTA baseline of De et al. (2022): In particular, unlike in (De et al. 2022). we fine-tune the final EMA checkpoint, i.c., the computed using EMA during pre-training
ImageNet. This modification (without any additional checkpoints aggregations) gives a major accuracy boost of 5% (70.3% > 75.51% %) for for the normal CIFARTO0 baseline. We obtain
1 and of 3.2% (77.6% 80.81%) for e similarly high improvements by fine-tuning the EMA of pre-trained checkpoints (instead of just the final checkpoint) for the ROS-CIFARIOO case. We leave the further investigation of this phenomena to the future work.
SverkOverflow training: We follow the SOTA in (Kairouz et al., 202 1 Denisov use TFF to train a one-layer LSTM (detailed architecture in Table 4 Reddi et al. 2020) on Stack- Overflow using DP-MM full version from (Denisov et al.) (022). StackOverflow naturally user-partitioned data, and we process 100 clients in each FL round. We train for 2048 FL rounds and set clip norm, noise multiplier, server learning rate, client learning rate, and server momentum, respectively, to 1, 0.341, 0.5, 1.0, 0.95 for 18.9 and to 1, 0.682, 0.25, 1.0, 0.95 for E = 8.2. For NDS-StackOverrllo, the same set of hyperparameter performs the best based on our tuning of the aforementioned hyperparameters.
2022) and
Hyperparameters tuning of checkpoints aggregations: Here we provide the methodology we fol- low to obtain the best hyperparameters for our checkpoints aggregation methods (Section 2. For EMA, De et al. 2022) simply use the EMA coefficient that works the best in non-private baseline. However, for each of the settings consider, we tune EMA coefficient in {0.85, 0.9, 0.95, 0.99, 0.999, 0.9999} | and observe that the best EMA coefficients for private and non-private settings need not be the same (Table 99. For instance, for CIFAR10, for E of and 8. EMA coefficient of 0.95 and 0.99 perform the best and outperform 0.9999 by 0.6% and 0.3%, respectively. Hence, we advise future works to perform uning of EMA coefficient. Full results are given in Table
21

---

Under review as a conference paper at ICLR 2023
Table 5: Accuracy gains on test data due to data-dependent checkpoints aggregation algorithms for SterkOverflow trained using DPFTRLM to achieve user-level DP.
Aggregation algorithms
Privacy level
None (Baseline)
Parameters aggregation
Outputs aggregation
EMA
UPA
OPA
OMV
5 0C
25.24 + 0.16
25.97 + 0.01
25.97 = 0.01
25.94 + 0.03
25.97 = 0.02
18.9
23.41 + 0.08
23.88 + 0.04
23.92 + 0.03
23.81 + 0.06
23.76 + 0.07
C 8.2
22.28 + 0.08
22.66 + 0.05
22.80 + 0.05
22.7 + 0.01
22.69 = 0.01
Table 6: Accuracy gains on test data due to data-dependent checkpoints aggregation algorithms for periodic distribution shifting StackOverflow trained using DPFTRLM to achieve user-level DP.
Aggregation algorithms
Privacy level
None (Baseline)
Parameters aggregation
Outputs aggregation
EMA
UPA
OPA
OMV
8 XO
23.89
0.04
24.18
0.02
24.15
0.02
24.15
0.01
24.19 0.01
& 18.9
21.6 = 0.13
22.18
0.07
22.17 + 0.06
22.21 + 0.08
22.19 + 0.09
E = 8.2
20.24 0.29
20.84
0.13
20.85
0.12
20,90 0.06
20.82 0.08
StackOverflow, User level & 00
PDS StackOverflow (s s))
24.0
26.0
23.8
23.6
Accuracy 1%6)
25.8
23.4
23.2
Baseline
25.6
Params EMA
23.0
Params average
22.8
Outouts average
Outouts majority
22.6
1998
2008
2018
2028 2038 FL round
2048
1998
2008
2018 2028 2038 2048 round
Figure 5: Accuracy gains due checkpoints aggregations for StackOverflow (left) and periodic
distribution shifting StackOverflow (right) trained using DP-FTRLM without any DP, i.c., E = co.
For the past & checkpoints aggregation based methods, our tuning methodology is general and as follows: we use some validation data (which is disjoint from training data) and evaluate the efficacy of aggregating checkpoints where we vary & over large enough range, and select the that performs the best on average over runs. Finally, value. Our hyperparameters tuning method is easy to replicate hence for conciseness, here we only provide the ranges of ie that we use for tuning. For CIFAR10 and CIFAR100, {3.5. 10, 20, ..., 200] for both parameters and outputs aggregation. For StackOverflow, we tune k E f3, 5, 10, 20, ..., 200} } for parameters aggregations (i.e., UPA) and for outputs aggregation (i.e., OPA and OMV). However, as for outputs aggregations, one should store k checkpoints on device in the FL setting of StackOverflow, we reduce tuning range and tune à (3, 10, 20,..., 100).
present results on test data using the best
tune k
Details of data dependent checkpoints selection for StackOverflow: Here we provide precise method for selecting the best of all checkpoints and aggregate them. We perform these experiments for StackOverflow due to availability of additional data, and omit CIFAR datasets. Specifically, we use 10.000 samples from the validation partition of the original StackOverflow data and use as held-out data. Note that held-out data is disjoint from both training and validation data we use for other parts of experiments. We compute performance of all checkpoints on held-out data and order them from highest to lowest performing checkpoints. Then we tune k as detailed in the previous section. The aggregation function remains the same for all, but EMA, our aggregation methods from Section 211
Recall that traditional EMA computed over all the checkpoints computed during training. We compute EMA over best & checkpoints as of (1 - :3) 9i-1 + + 0¹, where i E {1, ...,k..,. k). We keep EMA coefficient, B, constant through out. For EMA, we further tune 3 using validation
data.
22

---

Under review as a conference paper at ICLR 2023
Table 7: Accuracy gains on test data for CITAR100 fine-tuned using DP-SGD and sample-level DP.
Aggregation algorithms
Privacy level
None (Baseline)
Parameters aggregation
Outputs aggregation
EMA
UPA
OPA
OMV
80.81 + 0.11
80.88 + 0.10
80.83 + 0.09
80.92 + 0.10
80.82 + 0.10
==1
75.51 + 0.15
75.42 + 0.13
75.62 + 0.12
75.51 + 0.16
75.57 = 0.18
Table 8: Accuracy gains on test data for periodic distribution shifting CIFARI00 fine-tuned using
DP-SGD and sample-level DP.
Aggregation algorithms
Privacy level
None (Baseline)
Parameters aggregation
Outputs aggregation
EMA
UPA
OPA
OMV
E
8
77.16
0.11
80.53 0.07
80.53
0.08
80.49 0.06
80.41 0.09
8
1
70.84 0.16
74.83
0.15
75.81
0.16
75.02 0.17
74.97 0.18
Table We observe that tuning the EMA coefficient can provide significant gains accuracy over the default value of 0.9999 that De et al. (022) use; with warm-up schedule and number of training steps that De et al. (2022) use, 0.9999 and 0.999 provide the same results. This implies that tuning EMA coefficients for each different privacy budget is required for the best performances.
EMA coefficient
Privacy level
0.9
0.95
0.99
0.999
(De
2002
8
79.41
79.35
79.41
79.16
56.59
56.61
56.06
56.05
23


Reviews:
[{"review_id": "WPZ0V0LTZZ", "reviewer": "Reviewer_J6hu", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper investigates whether aggregating intermediate checkpoints of DP-SGD algorithms enable better privacy-accuracy trade-off and uncertainty estimate (when compared to those of last-iterate model). They provide empirical evidence that a variety of check point aggregation methods enables improved test accuracy for centralized and federated learning tasks. They also show that for strongly convex smooth loss function, check-point aggregation enables accurate variance estimate for bounded statistics of last-iterate model. This estimation error decays exponentially with the burn-in time and the minimum interval between any two sampled checkpoints. ", "summary_of_the_review": "The paper shows interesting potential of using intermediate model aggregation to improve privacy-accuracy trade-off and uncertainty estimate of differentially private learning. However, at current state, the paper does not offer clear investigation of which aggregation method works best in different setting and why. And the paper's Theorem 3.1, motivation for aggregating checkpoints, and some of the claims need more support and explanations. Therefore, my assessment is borderline.\n\n\n======\nPost authors' response\n\nMy main concern is still that the paper still needs better (more consistent) explanations for the gain in privacy-utility trade-off or uncertainty estimate by utilising intermediate checkpoints.\n\n=====\nResponse to author's followup comments:\n> The increase in training process length is unavoidable for a worst-case analysis; even for a simple loss such as a one-dimensional quadratic loss, obtaining k near-independent samples from a distribution close to the distribution of DP-SGD’s outputs using o(k) times the number of gradient accesses as a run of DP-SGD (i.e., o(k) times the privacy budget) would violate privacy lower bounds.\n\nI appreciate the authors' lower bound argument. But at the current form, it needs more explanation, perhaps a formal statement and some references, to be interpretable and convincing. \n\nSecondly, \"obtaining k near-independent samples from a distribution\" is not a necessary condition for good uncertainty estimate. There are many uncertainty estimation methods, such as MC-dropout, that rely on correlated samples. The idea of using intermediate checkpoints intrinsically may involve analyzing how to use correlated samples and their benefits. Reducing the analysis to nearly-independent runs of MCMC (via large checkpoint interval) lack the perspective for explaining the advantage of performing checkpoint aggregation compared to independent runs of the training (fine-tuning) process. \n\n> We disagree with this performance analysis of UPA (i.e., uniform tail average). First note from Tables 1 to 3 and Figures 1 and 2 that UPA always performs better than the last checkpoint by large margins. Furthermore, note from Tables 1 and 2 that for the Stackoverflow dataset, UPA always performs better than all other aggregation methods.\n\nIn Table 1 and Figure 1 for the performance of UPA: For CIFAR10, under epsilon = 8, the performance improvement of UPA is 2.21%, which is only 0.33% larger than the standard deviation of the baseline (1.46%) plus the standard deviation of UPA (0.52%). Therefore, this test accuracy improvement almost falls in the range of standard deviation, which is marginal. For stackoverflow, in Table 1, the test accuracy improvement of UPA is below 0.5%, which is marginal. \n\nThe test accuracy gain of UPA in Table 2-3 and Figure 2 is indeed more significant. However, the experiments for Table 2 and 3 and Figure 2 are under periodic distribution shift or data-dependent checkpoints aggregations, which the current Theorem 2.1 does not apply to. To explain the benefits in Table 2 and 3 and Figure 2, the authors would need new analysis.", "strength_and_weaknesses": "Strengths:\n- Averaging intermediate models is a promising direction for improving privacy-accuracy trade-off for differentially private learning.\n- Utilizing checkpoints for uncertainty estimates is an attractive methodology that may enjoy lower computation cost.\n\nWeaknesses:\n- In terms of empirical result, it's not really clear what averaging method one should use and why. In the paper, the various aggregation methods (including one method from existing work De et al.) perform similarly for most tasks. For a few tasks where the differences between methods are more significant, the winning method is also not consistent. The authors may want to clarify why their methods are better than prior works for certain tasks but not others. How does this depend on the data distribution or learning tasks?\n- In terms of theoretical results, to my understanding, the paper's main contribution is Theorem 3.1. which shows improved uncertainty (variance) estimate as the burning time and intervals between checkpoints increase. However, I do not see the effect of the number of checkpoint models in this theorem. It's not clear whether we should use more checkpoints for variance estimation and why. \n- In terms of the motivation of using checkpoints for uncertainty estimate, the authors emphasize computation efficiency of re-using checkpoints when compared to training multiple independent last-iterate models. However, the total number of training epochs increase in order to produce good quality checkpoints (with reasonable interval between them). These computations are not parallelizable. I think the authors need to support this motivation with more evidence, e.g., how much is the additional computation cost for longer training? Is it negligible when compared to multiple independent runs of the training algorithm (which could be done in parallel)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RyR1XGAWoG", "reviewer": "Reviewer_374t", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper studies the problem of differential private machine learning (DP ML) and propose to aggreagate the checkpoint (intermediate parameters during training) for test time inference. On the experimental sides, the paper conduct experiments over standard dataset like CIFAR10 and stackoverflow and their methods improve the accuracy around 1% to 3%. It also provides some theory on convex optimization and demonstrate the advantage of averaging instead of using only the last iteration.\n\nMethod. The paper proposes to aggregate the checkpoint in a few ways: (1) average parameter (exponential averaging or uniform averaging) and (2) aggregate the output (majority vote or averaging). The DP guarantee follows directly as they are post-processing\n\nExperiments. The paper conduct experiments over CIFAR10 and stackoverflow, in both centralized setting and federated setting. I am not a specialist in experiments but the improvement seems solid/consistent, but marginal at the same time.\n\nTheory. The paper shows averaging is better than the last-iteration in the constrained convex optimization setting. It provides good insight. However, technically, their method just plug-in and play the bounds of [Shamir and Zhang'13], and they also fail to show a lower bound (this means it is not really a separation between averaging and plug-in and play, in contrast with [Shamir and Zhang'13]). Moreover, in the convex optimization setting, there are many DP gradient descent type algorithm that uses averaging, so it is not novel.\n\n", "summary_of_the_review": "This a solid paper, but the idea/improvement seems to be marginal for a ICLR paper.\n\n--------------------------------------------------------------------------------\n\nPost rebuttal\n\nI have read the rebuttal and my evaluation remains.", "strength_and_weaknesses": "Strength. Overall, I think this is a solid paper with consistent and extensive experiments. It also provides some theory explaining the insight of their method.\n\nWeakness. (1) The aggregation of checkpoint seems to be fairly straightforward idea of post-processing. (2) The experiment improvement seems marginal. (3) The theory only explains the insight at the convex optimization domain, as I mentioned, there are a tons of related literature and I believe they have better rate in convex optimization setting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ax0UM_bZaI", "reviewer": "Reviewer_PDAE", "summary": "", "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": "", "summary_of_the_paper": "This paper studies re-using the intermediate checkpoints during DP training for two purposes: 1. improve the accuracy; 2. construct reasonable uncertainty quantification. The contribution is on the methodology and empirical results.", "summary_of_the_review": "Overall I think this is a borderline paper and needs non-trivial revision on the related work discussion and experiments.", "strength_and_weaknesses": "Strength: This paper is clearly presented. The contribution is solid and the experiments are convincing and well-designed. The new method has no cost in terms of privacy guarantee, improves the accuracy, does no incur additional computation, and particularly the UPA trick is better than EMA in that no additional hyperparameter $\\beta_t$ needs extra privacy budget to tune honestly.\n\nWeaknesses: I have some concerns on the novelty (see details in next comment) and not comparing carefully to existing work. For example, although the work claims above Section 2.3.3 \"we improve the SOTA baseline of De et al. (2022) from 70.6% to 75.51% at ε = 1 and from 77.6% to 80.8% at ε = 8\". De et al. is not SOTA: CIFAR100 has achieved 83.0% at ε = 1 and 88.4% at ε = 8 without using any checkpointing like EMA, by \"Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacy\". Testing on this setting is important.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject