Differentially Private Learning with Adaptive Clipping
Year: 2022

Abstract:
Existing approaches for training neural networks with user-level differential privacy (e.g., DP Federated Averaging) in federated learning (FL) settings involve bounding the contribution of each user’s model update by clipping it to some constant value. However there is no good a priori setting of the clipping norm across tasks and learning settings: the update norm distribution depends on the model architecture and loss, the amount of data on each device, the client learning rate, and possibly various other parameters. We propose a method wherein instead of a fixed clipping norm, one clips to a value at a specified quantile of the update norm distribution, where the value at the quantile is itself estimated online, with differential privacy. The method tracks the quantile closely, uses a negligible amount of privacy budget, is compatible with other federated learning technologies such as compression and secure aggregation, and has a straightforward joint DP analysis with DP-FedAvg. Experiments demonstrate that adaptive clipping to the median update norm works well across a range of realistic federated learning tasks, sometimes outperforming even the best fixed clip chosen in hindsight, and without the need to tune any clipping hyperparameter.

heading: 1 Introduction
text: Deep learning has become ubiquitous, with applications as diverse as image processing, natural language translation, and music generation [27, 13, 28, 7]. Deep models are able to perform well in part due to their ability to utilize vast amounts of data for training. However, recent work has shown that it is possible to extract information about individual training examples using only the parameters of a trained model [12, 30, 26, 8, 19]. When the training data potentially contains privacy-sensitive user information, it becomes imperative to use learning techniques that limit such memorization.
Differential privacy (DP) [10, 11] is widely considered a gold standard for bounding and quantifying the privacy leakage of sensitive data when performing learning tasks. Intuitively, DP prevents an adversary from confidently making any conclusions about whether some user’s data was used in training a model, even given access to arbitrary side information. The formal definition of DP depends on the notion of neighboring datasets: we will refer to a pair of datasets D,D′ ∈ D as neighbors if D′ can be obtained from D by adding or removing one element.
Definition 1.1 (Differential Privacy). A (randomized) algorithm M : D → R with input domain D and output rangeR is (ε, δ)-differentially private if for all pairs of neighboring datasets D,D′ ∈ D, and every measurable S ⊆ R, we have Pr (M(D) ∈ S) ≤ eε · Pr (M(D′) ∈ S) + δ, where probabilities are with respect to the coin flips of M .
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Following McMahan et al. [18], we define two common settings of privacy corresponding to two different definitions of neighboring datasets. In example-level DP, datasets are considered neighbors when they differ by the addition or removal of a single example [9, 4, 2, 22, 31, 23, 15]. In user-level DP, neighboring datasets differ by the addition or removal of all of the data of one user [18]. Userlevel DP is the stronger form, and is preferred when one user may contribute many training examples to the learning task, as privacy is protected even if the same privacy-sensitive information occurs in all the examples from one user. In this paper, we will describe the technique and perform experiments in terms of the stronger user-level form, but we note that example-level DP can be achieved by simply giving each user a single example.
To achieve user-level DP, we employ the Federated Averaging algorithm [17], introduced as a decentralized approach to model training in which the training data is left distributed on user devices, and each training round aggregates updates that are computed locally. On each round, a sample of devices are selected for training, and then each selected device performs potentially many steps of local SGD over minibatches of its own data, sending back the model delta as its update.
Bounding the influence of any user in Federated Averaging is both necessary for privacy and often desirable for stability. One popular way to do this to cap the L2 norm of its model update by projecting larger updates back to the ball of norm C. Since such clipping also effectively bounds the L2 sensitivity of the aggregate with respect to the addition or removal of any user’s data, adding Gaussian noise to the aggregate is sufficient to obtain a central differential privacy guarantee for the update [9, 4, 2]. Standard composition techniques can then be used to extend the per-update guarantee to the final model [20].
Setting an appropriate value for the clipping threshold C is crucial for the utility of the private training mechanism. Setting it too low can result in high bias since we discard information contained in the magnitude of the gradient. However setting it too high entails the addition of more noise, because the amount of Gaussian noise necessary for a given level of privacy must be proportional to the norm bound (the L2 sensitivity), and this will eventually destroy model utility. The clipping bias-variance trade-off was observed empirically by McMahan et al. [18], and was theoretically analyzed and shown to be an inherent property of differentially private learning by Amin et al. [3].
Learning large models using the Federated Averaging/SGD algorithm [17, 18] can take thousands of rounds of interaction between the central server and the clients. The norms of the updates can vary as the rounds progress. Prior work [18] has shown that decreasing the value of the clipping threshold after training a language model for some initial number of rounds can improve model accuracy. However, the behavior of the norms can be difficult to predict without prior knowledge about the system, and if it is difficult to choose a fixed clipping norm for a given learning task, it is even more difficult to choose a parameterized clipping norm schedule.
While there has been substantial work on DP techniques for learning, almost every technique has hyperparameters which need to be set appropriately for obtaining good utility. Besides the clipping norm, learning techniques have other hyperparameters which might interact with privacy hyperparameters. For example, the server learning rate in DP SGD might need to be set to a high value if the clipping threshold is very low, and vice-versa. Such tuning for large networks can have an exorbitant cost in computation and efficiency, which can be a bottleneck for real-world systems that involve communicating with millions of samples for training a single network. Tuning may also incur an additional cost for privacy, which needs to be accounted for when providing a privacy guarantee for the released model with tuned hyperparameters (though in some cases, hyperparameters can be tuned using the same model and algorithm on a sufficiently-similar public proxy dataset).
Related Work The heuristic of clipping to the median update norm was suggested by Abadi et al. [1], but no method for doing so privately was proposed, nor was the heuristic empirically tested. One possibility would be to estimate the median unclipped update norm at each round privately by adding noise calibrated to the smooth sensitivity as defined by Nissim et al. [21]. However this approach has several drawbacks compared to the algorithm we will present. It would require the clients to send their unclipped updates to the server at each round,1 which is incompatible with the foundational
1Alternatively, clients could first report their update norms, after which the server could reply with the clipping norm for the round, and finally the clients would send the clipped updates. However, this would still give the server strictly more information than our approach, and would require an extra round of communication, both of which are undesirable.
principle of federated learning to transmit only focused, minimal updates, and precluding the use of secure aggregation [5] and certain forms of compression [16, 6]. Also, by incorporating information across multiple rounds, our method is able to track the underlying quantile closely, with less jitter associated with sampling at each round, and using only a negligible fraction of the privacy budget.
Contributions In this paper, we describe a method for adaptively and privately tuning the clipping threshold to track a given quantile of the update norm distribution during training. The method uses a negligible amount of privacy budget, and is compatible with other FL technologies such as compression and secure aggregation [5, 6]. We perform a careful empirical comparison of our adaptive clipping method to a highly optimized fixed-clip baseline on a suite of realistic and publicly available FL tasks to demonstrate that high-utility and high-privacy models—sometimes exceeding any fixed clipping norm in utility—can be trained using our method without the need to tune any clipping hyperparameter.

heading: 2 Private adaptive quantile clipping
text: In this section, we will describe the adaptive strategy that can be used for adjusting the clipping threshold so that it comes to approximate the value at a specified quantile.
Let X ∈ R be a random variable, let γ ∈ [0, 1] be a quantile to be matched. For any C, define
`γ(C;X) = { (1− γ)(C −X) if X ≤ C, γ(X − C) otherwise,
so
`′γ(C;X) = { (1− γ) if X ≤ C, −γ otherwise.
Hence, E[`′γ(C;X)] = (1 − γ) Pr[X ≤ C] − γ Pr[X > C] = Pr[X ≤ C] − γ. For C∗ such that E[`′γ(C∗;X)] = 0, we have Pr(X ≤ C∗) = γ. Thus, C∗ is the γth quantile of X . Because the loss is convex and has gradients bounded by 1, we can get an online estimate of C that converges to the γth quantile of X using online gradient descent (see, e.g., Shalev-Shwartz [25]). See Figure 1 for a plot of the loss for a random variable that takes six values with equal probability.
Suppose at some round we have m samples of X , with values (x1, . . . , xm). The average derivative of the loss for that round is
¯̀′ γ(C;X) =
1
m m∑ i=1 { (1− γ) if xi ≤ C, −γ otherwise
= 1
m
( (1− γ) ∑ i∈[m] Ixi≤C − γ ∑ i∈[m] Ixi>C ) = b̄− γ,
where b̄ , 1m ∑ i∈[m] Ixi≤C is the empirical fraction of samples with value at most C. For a given learning rate ηC , we can perform the update: C ← C − ηC(b̄− γ).
Geometric updates. Since b̄ and γ take values in [0, 1], the linear update rule above changes C by a maximum of ηC at each step. This can be slow if C is on the wrong order of magnitude. At the other extreme, if the optimal value of C is orders of magnitude smaller than ηC , the update can be very coarse, and may overshoot to become negative. To remedy such issues, we propose the following geometric update rule: C ← C · exp(−ηC(b̄− γ)). This update rule converges quickly to the true quantile even if the initial estimate is off by orders of magnitude. It also has the attractive property that the variance of the estimate around the true quantile at convergence is proportional to the value at that quantile. In our experiments, we use the geometric update rule with ηC = 0.2.

heading: 2.1 DP-FedAvg with adaptive quantile clipping
text: Let m be the number of users in a round and let γ ∈ [0, 1] denote the target quantile of the norm distribution at which we want to clip. For iteration t ∈ [T ], let Ct be the clipping threshold, and ηC be the learning rate. Let Qt be set of users sampled in round t. Each user i ∈ Qt will send the bit bti along with the usual model delta update ∆ t i, where b t i = I||∆ti||2≤Ct . Defining b̄ t = 1m ∑ i∈Qt b t i, we would like to apply the update C ← C · exp(−ηC(b̄ − γ)). However, we can’t use b̄t directly, since it may reveal private information about the magnitude of users’ updates. To remedy this, we add Gaussian noise to the sum: b̃t = 1m (∑ i∈Qt b t i +N (O, σ2b ) ) . The DPFedAvg algorithm with adaptive clipping is shown in Algorithm 1. We augment basic federated averaging with server momentum, which improves convergence [14, 24].2
Algorithm 1 DPFedAvg-M with adaptive clipping
function Train(m, γ, ηc, ηs, ηC , z, σb, β) Initialize model θ0, clipping bound C0
z∆ ← ( z−2 − (2σb)−2 )−1/2 for each round t = 0, 1, 2, . . . do Qt ← (sample m users uniformly) for each user i ∈ Qt in parallel do
(∆ti, b t i)← FedAvg(i, θt, ηc, Ct)
σ∆ ← z∆Ct ∆̃t = 1m (∑ i∈Qt ∆ t i +N (0, Iσ2∆) ) ∆̄t = β∆̄t−1 + (1− β)∆̃t θt+1 ← θt + ηs∆̄t b̃t = 1m (∑ i∈Qt b t i +N (O, σ2b ) )
Ct+1 ← Ct · exp ( −ηC(b̃t − γ) ) function FedAvg(i, θ0, η, C) θ ← θ0 G ← (user i’s local data split into batches) for batch g ∈ G do θ ← θ − η∇`(θ; g)
∆← θ − θ0 b← I||∆||≤C ∆′ ← ∆ ·min ( 1, C||∆|| ) return (∆′, b)
2Note that since the momentum update is computed using privatized estimates of the average client delta, privacy properties are unchanged when momentum is added. We also experimented with adaptive learning rates, but found that they were less effective when noise is added for DP, perhaps because the noise causes the preconditioner vt to become large prematurely.
Theorem 1. One step of DP-FedAvg with adaptive clipping using σb noise standard deviation on the clipped counts ∑ bti and z∆ noise multiplier on the vector sums ∑ ∆ti is equivalent (so far as privacy accounting is concerned) to one step of non-adaptive DP-FedAvg with noise multiplier z if we set z∆ = ( z−2 − (2σb)−2 )−1/2 .
Proof. We make a conceptual change to the algorithm that does not change the behavior or privacy properties but allows us to analyze each step as if it were a single private Gaussian sum. Instead of sending (∆ti, b t i), each user sends (∆̂ t i, b̂ t i) , ( ∆ti/σ∆, (bti − 1/2)/σb ) . The server adds noise with
covariance I and averages, then reverses the transformation so ∆̃t = σ∆m (∑ i∈Qt ∆̂ t i +N (0, I) ) and
b̃t = σbm (∑ i∈Qt b̂ t i +N (0, 1) ) + 1/2. Noting that ||(∆̂ti, b̂ti)|| ≤ S , ( (Ct/σ∆)2 + (1/2σb) 2 )1/2
, it is clear that the two Gaussian sum queries of Algorithm 1 are equivalent to pre- and post-processing of a
single query with sensitivity S and covariance I , or noise multiplier z = 1/S = ( z−2∆ + (2σb) −2 )−1/2
. Rearranging yields the result.
In practice, we recommend using a value of σb = m/20. Since the noise is Gaussian, this implies that the error |b̃t − b̄t| will be less than 0.1 with 95.4% probability, and will be no more than 0.15 with 99.7% probability. Even in this unlikely case, assuming a geometric update and a learning rate of ηC = 0.2, the error on the update would be a factor of exp(0.2× 0.15) = 1.03, a small deviation. So this default gives high privacy for an acceptable amount of noise in the quantile estimation process. Using Thm. 1, we can compute that to achieve an effective combined noise multiplier of z = 1, with m = 100 clients per round, the noise multiplier z∆ is approximately 1.005. So we are paying only a factor of 0.5% more noise on the updates for adaptive clipping with the same privacy guarantee (a quantity which only gets smaller with increasing m). These constants (σb = m/20 and ηC = 0.2) are what we use in the experiments of Section 3.
The clipping norm can be initialized to any value C0 that is safely on the low end of the expected norm distribution. If it is too high and needs to adapt downward, a lot of noise may be added at the beginning of model training, which may swamp the model. However there is little danger in setting it quite low, since the geometric update will make it grow exponentially until it matches the true quantile. In our experiments we use an initial clip of 0.1 for all tasks. It is easy to compute that with a learning rate of ηC = 0.2 and a target quantile of γ = 0.5, if every update is clipped, the quantile estimate will increase by a factor of ten every 23 iterations. In order to show the effectiveness of the algorithm at tracking a known quantile, we ran it on simulated data for which we can compute the true quantile exactly. Figure 2 shows the result of this experiment.

heading: 3 Experiments
text: To empirically validate the approach, we examine the behavior of our algorithm on six of the public benchmark federated learning tasks defined by Reddi et al. [24], which are to our knowledge the most realistic and representative publicly available federated learning tasks that exist to date. All six tasks are non-i.i.d. with respect to user partitioning: indeed with the exception of CIFAR-100, the data is partitioned according to the actual human user who generated the data, for example the writer of the EMNIST characters or the Stack Overflow user who asked or answered a question. Table 1 (left) lists the characteristics of the datasets.
Two of the tasks derived from Stack Overflow data (SO-NWP and SO-LR) are ideal for DP research due to the very high number of users (342k) making it possible to train models with good user-level privacy without sacrificing accuracy. The other four tasks (CIFAR-100, EMNIST-AE, EMNISTCR, SHAKESPEARE) are representative learning tasks, but not representative population sizes for real world cross-device FL applications. Therefore we focus on establishing that adaptive clipping works well with 100 clients per round on these tasks in the regime where the noise is at a level such that utility is just beginning to degrade. Under the assumption that a larger population were available, one could increase m, σ∆, and σb proportionally to achieve comparable utility with high privacy. This should not significantly affect convergence (indeed, it might be beneficial) since the only effect is to increase the number of users in the average ∆̃t, reducing the variance. Table 1 (middle) shows the number of clients per round with which our experiments indicate we could achieve (5, n−1.1)-DP for each dataset with acceptable model performance loss (less than 5% relative to non-private training, as discussed later) if each dataset had n = 106 clients, using RDP composition with fixed-size subsampling [29].3

heading: 3.1 Baseline client and server learning rates
text: Reddi et al. [24] provide optimized client and server learning rates for federated averaging with momentum that serve as a starting point for our experimental setup. For almost all hyperparameters (model configuration, evaluation metrics, client batch size, total rounds, etc.) we replicate their experiments, but with two changes. First, we increase the number of clients per round to 100 for all tasks. This reduces the variance in the updates to a level where we can reasonably assume that adding more clients is unlikely to significantly change convergence properties [18]. Second, as shown in Algorithm 1 we use unweighted federated averaging, thus eliminating the need to set yet another difficult-to-fit hyperparameter: the expected total weight of clients in a round. Since these changes might require different settings, we reoptimize the client and server learning rates for our baseline with no clipping or noise. We ran a small grid of 25 configurations for each task jointly exploring client and server learning rates whose logarithm (base-10) differs from the values in Table 10 of Reddi et al. [24] by { -1⁄2, -1⁄4, 0, 1⁄4, 1⁄2 }. The optimal baseline client and server learning rates for our experimental setup are shown in Table 1 (right).
3The code used for all of our experiments is publicly available at https://github.com/googleresearch/federated/blob/master/differential_privacy/run_federated.py.
Because clipping (whether fixed or adaptive) reduces the average norm of the client updates, it may be necessary to use a higher server learning rate to compensate. Therefore, for all approaches with clipping—fixed or adaptive—we search over a small grid of five server learning rates, scaling the values in Table 1 by {1, 101/4, 101/2, 103/4, 10}. For all configurations, we report the best performing model whose server learning rate was chosen from this small grid on the validation set.4
We first examine the impact of adaptive clipping without noise to see how it affects model performance. Figure 3 compares baseline performance without clipping to adaptive clipping with five different quantiles. For each quantile, we show the best model after tuning over the five server learning rates mentioned above on the validation set. On three tasks (CIFAR-100, EMNIST-AE, SO-NWP), clipping improves performance relative to the unclipped baseline. On SHAKESPEARE and SO-LR performance is slightly worse, but we can conclude that adaptive clipping to the median generally fares well compared to not using clipping across tasks. Note that for our primary goal of training with DP, it is essential to limit the sensitivity one way or another, so the modest decrease in performance observed from clipping on some tasks may be part of the inevitable tension between privacy and utility.

heading: 3.2 Fixed-clip baselines
text: We would like to compare our adaptive clipping approach to a fixed clipping baseline, but comparing to just one fixed-clip baseline may not be enough to demonstrate that adaptive clipping consistently performs well. Instead, our strategy will be to show that quantile-based adaptive clipping performs as well or nearly as well as any fixed clip chosen in hindsight. If we can first identify clipping norms that span the range of normal values during training on each problem/configuration, we can compare adaptive clipping to fixed clipping with those norms.
To that end, we first use adaptive clipping without noise to discover the value of the update norm distribution at the following five quantiles: {0.1, 0.3, 0.5, 0.7, 0.9}. Then we choose as the minimum of our fixed clipping range the smallest value at the 0.1 quantile over the course of training, and as the maximum the largest value at the 0.9 quantile. Plots of the update norms during training on each of the tasks are shown in Figure 4.
On each task there is a ramp up period where the clipping norm, initialized to 0.1 for all tasks, catches up to the correct norm distribution. Thus we disregard norm values collected until the actual fraction of clipped counts b̄t on some round is within 0.05 of the target quantile γ. The chosen values for the
4Note that this modest retuning of the server learning rate is only necessary because we are starting from a configuration that was optimized without clipping. In practice, as we will discuss in Section 4, we recommend that all hyperparameter optimization should be done with adaptive clipping enabled from the start, eliminating the need for this extra tuning.
0.1 0.3 0.5 0.7 0.9
0.1 0.3 0.5 0.7 0.9
0.1 0.3 0.5 0.7 0.9
minimum and maximum fixed clips for each task are shown in Table 1 (right). Our fixed-clipping baseline uses five fixed clipping norms logarithmically spaced in that range. Here we are taking advantage of having already run adaptive clipping to minimize the number of fixed clip settings we need to explore for each task. If we had to explore over the entire range knowing only the endpoints across all tasks (0.22, 135.0) at the same resolution, we would need nearly four times as many clip values per task.
For each value of noise multiplier z ∈ {0, 0.01, 0.03, 0.1} we trained using the five fixed clipping norms and compare to adaptive clipping with the five quantiles (0.1, 0.3, 0.5, 0.7, 0.9). Note that for the fixed clipping runs z∆ = z; that is, for fixed clip C, the noise applied to the the updates has standard deviation zC. As discussed in section 2.1, on the adaptive clipping runs z∆ is slightly higher due to the need to account for privacy when estimating the clipped counts.

heading: 3.3 Comparison of fixed and adaptive clipping
text: Validation set results with adaptive clipping are shown in Figure 5 and with fixed clipping in Figure 6. These charts show that we have identified the noise regime in which performance is beginning to degrade. There is always a tension between privacy and utility: as the amount of noise increases, eventually performance will go down. For the purpose of this study we consider more than a 5% relative reduction in evaluation metric to be unacceptable. Therefore for each task, we look at the level of noise z∗ at which the evaluation metric on the validation set is still within 5% of the value with no noise, but adding more noise would degrade performance beyond 5%. Given z∗ for each task, we then choose C∗ to be the fixed clip value that gives best performance on the validation set. The values of z∗ and C∗ are shown in Figure 7 (left).
For our final test set evaluation, we compare adaptive clipping to the median to fixed clipping at C∗. The results are in Figure 7 (right). We show the average test set performance and bootstrapped 95% confidence interval over 20 runs varying the random seed used for client selection and DP noise. On three of the tasks (CIFAR-100, EMNIST-AE, SHAKESPEARE), clipping to the median actually outperforms fixed clipping to the best fixed clip chosen in hindsight, and on two more (EMNIST-CR, SO-NWP), the performance is comparable. Only on SO-LR the best fixed clip does perform somewhat better. This task seems to be unusual in that best performance comes from aggressive clipping, so a small fixed clip fares better than adaptive clipping to the median. However,
looking at Figure 6 (and noting the scale of the y axis), on this task more than the others, getting the exact right fixed clip is important. The development set recall@5 value of 55.1 corresponds to the optimal fixed clip of 16.0. The next larger fixed clip of 27.3 gave a recall of only 51.8, and larger clips fared even worse. So an expensive hyperparameter search may be necessary to even get close to this high-performing fixed clip value.

heading: 4 Conclusions and implications for practice
text: In our experiments, we started with a high-performing non-private baseline with optimized client and server learning rates. We then searched over a small grid of larger server learning rates for our experiments with clipping (adaptive or fixed). This is one way to proceed in practice, if such non-private baseline results are available. More often, such baseline learning rates are not available, which will necessitate a search over client learning rates as well. In that case, it would be beneficial to enable adaptive clipping to the median during that hyperparameter search. The advantage of clipping relative to the unclipped baseline observed on some tasks could only increase if the other hyperparameters such as client learning rate were also chosen conditioned on the presence of clipping.
Although the experiments indicate that adaptive clipping to the median yields generally good results, on some problems (like SO-LR in our study) there may be gains from tuning the target quantile. It
Task z∗ C∗ CIFAR-100 0.03 0.98 EMNIST-CR 0.10 0.37 EMNIST-AE 0.03 0.32 SHAKESPEARE 0.10 0.95 SO-NWP 0.01 0.30 SO-LR 0.01 16.0
ad ap
tiv e fix ed
54.3%
54.4%
54.5%
54.6%
54.7%
54.8%
54.9%
55.0%
55.1%
55.2%
55.3%
55.4%
CI FA
R10
0, a
cc ur
ac y
ad ap
tiv e fix ed
82.8%
83.0%
83.2%
83.4%
83.6%
83.8%
84.0%
EM N
IS T-
CR , a
cc ur
ac y
ad ap
tiv e fix ed
7.85e-4
7.90e-4
7.95e-4
8.00e-4
8.05e-4
8.10e-4
8.15e-4
8.20e-4
8.25e-4
EM N
IS T-
AE , m
ea n_
sq ua
re d_
er ro
r
ad ap
tiv e fix ed
56.22%
56.24%
56.26%
56.28%
56.30%
56.32%
56.34%
56.36%
56.38%
SH AK
ES PE
AR E,
a cc
ur ac
y
ad ap
tiv e fix ed
23.90%
23.95%
24.00%
24.05%
24.10%
24.15%
24.20%
24.25%
24.30%
24.35%
24.40%
SO -N
W P,
a cc
ur ac
y
ad ap
tiv e fix ed
51.5%
52.0%
52.5%
53.0%
53.5%
54.0%
54.5%
55.0%
55.5%
56.0%
56.5%
SO -L
R, r
ec al
l@ 5
adaptive fixed
clip
Figure 7: Left: for each task, the maximum noise possible before performance begins to significantly degrade (z∗), and the best fixed clip (C∗) chosen on the development set. Right: average test set performance and bootstrapped 95% confidence interval over 20 runs. In practice, finding the best fixed clipping norm would require substantial additional hyperparameter tuning.
would require adding another dimension to the hyperparameter grid, exponentially increasing the tuning effort, but even this would be preferable to tuning the fixed clipping norm from scratch, since the grid can be smaller: we obtained good results on all problems by exploring only five quantiles, but the update norms in the experiments range over four orders of magnitude, from 0.22 to 135.
Combining our results with the lessons taken from [18] and [24], the following strategy emerges for training a high-performing model with user-level differential privacy. We assume some non-private proxy data is available that may have comparatively few users n′, as well as that the true private data has enough users n that the desired level of privacy is achievable.
1. With adaptive clipping to the median enabled, using a relatively small number of clients per round (m ≈ 100), and a small amount of noise (z = 0.01), search over client and server learning rates on non-private proxy data.
2. Fix the client and server learning rates. Using the non-private data and low value of m, train several models increasing the level of noise z until model performance at convergence begins to degrade.
3. To train the final model on private data, if (m, z) is too small for the desired level of privacy even given n, set (m, z)← α · (m, z) for some α > 1 such that the privacy target ( , δ) is achieved.5 Finally, train the private model using that value of m and z.
By eliminating the need to tune the fixed clipping norm hyperparameter which interacts significantly with the client and server learning rates, the adaptive clipping method proposed in this work exponentially reduces the work necessary to perform the expensive first step of this procedure.
5Here we employ our assumption that n is sufficiently large, since m cannot exceed n.

Review summaries:
This paper studies the problem of how to choose a good clipping norm in differentially private federated learning. The authors propose a new method to select the clipping threshold by privately approximate the quantile of the update norm distribution. Experiments validate the effectiveness of the proposed method.

This paper tackles the problem of training accurate neural networks with user-level privacy in the federated learning settings. Classical implementations usually ensure user-level differential privacy of the learning scheme by applying the following procedure:    1) before sending their gradient update to the server, every user clip (or rescale) its gradient update so that its norm is smaller or equal to a constant clipping parameter $C$  2) after aggregating the clipped gradients, the server adds Gaussian noise proportional to $C$ before applying a gradient update rule.  In this paper, instead of applying step 1) with a fixed constant $C$, the authors present a method to adaptively select the clipping constant during the training. This method is based on a quantile regression problem under differential privacy constraints. The authors demonstrate through numerical experiments that this new adaptive clipping method obtain similar result as classical implementations while eliminating the need for hyper parameter search on $C$.

This works studies the problem of training neural networks with user-level differential privacy using federated learning. To bound user contribution, the authors propose to clip the gradient norms to the private estimate of the median of gradient norms, as opposed to some fixed clipping threshold. This method reduces the need to tune the clip threshold and achieves competitive performance across a range of tasks.