Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: 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.
main_review: The idea of the proposed method seems to be interesting, but the analysis of the current method needs to be further justified. Here are my main concerns of the current paper:
1. The motivation of using the quantile of the update distribution as the clipping threshold is not well justified.
2. The privacy guarantee of the current method is not very clear. For example, how the number of sampled clients will affect the privacy guarantee is not clear. In addition, it is not clear how the proposed method tracks the privacy loss in the experiments.
3. It is unclear how the proposed method will affect the utility guarantee of the algorithm. The contribution of the current paper will be stronger if the authors could add more analysis about the utility using the proposed clipping method.
4. One important metric to evaluate the performance of federated learning is the communication round. How the proposed method will affect the communication round is also unclear.
5. Experimental results show that the improvements of the proposed methods are not very significant compared with the fixed clipping method.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the problem of ERM under user-level differential privacy. They propose a method based on quantile clipping to bound the contribution of each user (L_2 sensitivity of the gradient estimation), eliminating the need to specify a clipping threshold in advance.
main_review: Strengths:
- The problem of ERM under user-level differential privacy is important and has real-world applications.
- To bound the contribution of each user, this paper chooses the clipping threshold by an adaptive method based on quantile, instead of requiring a pre-specified clipping threshold.

Weaknesses:
- The novelty and technical depth is low: the quantile computation method directly follows from a standard method based on gradient descent; there is no theoretical analysis for the accuracy guarantee (e.g. for the quantile computation), and the heuristic of clipping to median is proposed in DP-SGD.
- For quantile computation under differential privacy, the comparison with smooth sensitivity is not accurate and complete. At lines 72-73, the authors say that smooth sensitivity requires each client send unclipped updates to the server, however, only their norms are needed to estimate the median. In fact, since the privacy guarantee is in the centralized model, this paper also requires the server knowns the exact answers (i.e., the information of unclipped updates to estimate the median, and the aggregation of all client updates) to be perturbed by Gaussian noise.
- Lack of clear statements (e.g., theorems and proofs) for the privacy and accuracy guarantee. It is not easy to follow and understand the details of the proposed quantile computation method.

[1] Answering Range Queries Under Local Differential Privacy

limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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$.
main_review: Relevance: Federated Learning is currently a hot topic within the ML community. Furthermore, improving the convergence/accuracy of privacy preserving techniques is also very important and relevant to the NeurIPS community.

Clarity: The paper is overall well written and statements are clearly presented. 

Quality: Both the technical and experimental part of the paper look sound to me. I just have some minor comments/questions. 
- In the proof of Theorem 1, why are you building a query that sends $(\frac{\Delta_i^t}{\sigma_\Delta},\frac{(b_i^t -1/2)}{\sigma_b})$ instead of $(\frac{\Delta_i^t}{\sigma_\Delta},\frac{b_i^t }{\sigma_b})$ ? Also why is $\frac{1}{2\sigma_b}$ the sensitivity of $(b_i^t-1/2)/\sigma_b$ and not $1/\sigma_b$? 
- Figure 2 is interesting as it presents a sanity check of the quantile regression problem for a fixed gradient distribution. However it is unclear to me how informative it is in the context of the gradient descent, as the gradient distribution will be changing at every step.  
- I am not aware of the classical privacy level the literature on Private FL considers as acceptable, but, from my point of view, $\epsilon=5$ is not a very meaningful privacy budget. Maybe it would have been interesting to compare the privacy/accuracy tradeoff for several privacy budgets.

Originality and Significance: I think originality is not the main strength of this paper. The idea of using the median to adapt the gradient clipping during the learning was first presented in [1], even though it was not properly studied. Similarly, the problem of quantile regression is a plain old machine learning problem and adapting it with differential privacy only asked for Gaussian noise injection during SGD. Nevertheless, I think the idea of combining these techniques in a sound way to build efficient adaptive clipping is new. Overall, while the idea is not very surprising, I think this is an interesting paper that could benefit to the community by helping automatize the study of differentially private implementations of SGD. 

limitations_and_societal_impact: I don't see any negative social impact rising from this paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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.
main_review: This work proposes to clip to the median of the gradient norms to bound user contributions in federated learning under user-level DP. The authors run extensive experiments to show that clipping to the median yields desired performance comparable to clipping at the best threshold chosen in hindsight. The experiment setup is thorough, and the results support the claims of the work.

The algorithm to estimate the median (and arbitrary quantiles) is interesting. It does not require prior knowledge of the upper bound on the gradient norm. However, it is unclear the advantage of this method over existing private quantile estimators, for example, 

Dwork and Lei, Differential Privacy and Robust Statistics 

Tzamos et.al., Optimal Private Median Estimation under Minimal Distributional Assumptions. 

The authors may want briefly discuss why the current algorithm is preferred over existing algorithms for quantile estimation.

Another issue is the privacy guarantees. It seems that in the experiments the authors choose $\sigma_b, \sigma_\Delta$ that guarantees $(5, n^{-1.1})$-DP, which falls into the low privacy regime. The authors provided a procedure to tune the parameters to satisfy arbitrary privacy guarantees, but it is unclear to me when we should stop increasing the noise levels. The authors may wish to provide a more formal privacy guarantee in terms of the parameters (e.g., clip threshold, noise magnitudes). 

Overall the paper is well-organized.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper presents a method for adaptively setting the gradient clipping threshold for DP federated learning. The proposed method is mostly a combination of known techniques, but it provides a neat and well-presented solution to an important practical problem.

The reviews are mixed: some reviewers are more positive because of more emphasis on the practical relevance while others are more negative because of emphasis on limited technical novelty.

The AC is in favour of accepting the paper because of its practical usefulness and potential impact. In my opinion, the authors have been able to answer the criticisms of the negative reviews in their rebuttal. Unfortunately these reviewers have been unresponsive in the discussion and thus the reviews have not been updated in light of the author responses, potentially leaving the reviews unnecessarily negative.

While not reflected in the reviews, this paper was discussed extensively by the AC (who read it in full and championed the work) and the SAC, leading to the decision to accept.
Decision: Accept (Poster)