Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Voting-based approaches for DP

1/ Summary of the paper

This paper addresses the problem of learning a private model in an FL setting. It assumes that the server has an unlabelled dataset on which learning has to be performed. The paper proposes two extensions of known algorithms, PATE and Private-KNN in this setting. In both cases, up to variations, the approach is "one-shot" and amounts to getting consensus labels for the public dataset from the different FL agent, the consensus being obtained with DP guarantees. Then, a model is trained on the server using these consensus labels.
The paper provides Rényi DP guarantees for both algorithms. Experiments on real datasets in 2 settings (many agents and few ones) show an improved performance over baseline DP FL algorithms.

2/ Strong and weak points

- The paper makes a very good distinction of the number of agents and the DP guarantees it implies in both settings, with the notion of instance-level (i.e. at the individual sample level) vs agent-level (i.e. client) DP.
- The paper is well-motivated, and section 3 is very helpful in this regard (even if I have some remarks, see additional comments)
- The paper is well written and easy to follow

- A weakness of the paper is its limited algorithmic novelty: as far as I understand, PATE already considered N subsets of a large dataset, while here the subsets are already provided by the agents; Private-KNN-FL is more novel insofar as private-KNN only considered a single dataset, but here as well the jump from 1 to N is the only novelty.
- Another weakness of the paper is its experimental validation, see supporting arguments.

3/ Recommendation

Given the limited algorithmic novelty and the limitations of the experimental validation, I think this paper is marginally above acceptance threshold despite its interesting viewpoint and theoretical contributions.

4/ Supporting arguments

- All results in Table 1 and Table 2 rely on domain adaptation approach, with the final model being tested on a domain held by the server. While the proposed approaches really train a model on this domain (at least for the samples, not the labels), the baselines FedAvg, DP-FedAvg and DP-FedSGD are not designed for this setting by default, as they minimise the average losses of the clients and never see the server distribution. Out-of-domain generalisation is an issue of its own in FL, and the mix of both issues at the same time makes it impossible to really compare results with one another, rendering all these results less significant.
- Theorem 3 provides privacy guarantees of both approaches in the agent-level and instance-level DP cases, allowing to compare the proposed approaches with one another. However, in the experimental section, PATE-FL is compared to a baseline agent-level method, and Private-KNN-FL approach is compared with instance-level methods. Private-KNN-FL and PATE-FL are never compared with one another experimentally, which would have been helpful to understand when one is better than the other (especially for the ablation experiments of Fig 2).

5/ Questions and comments

- Could you detail the experimental methodology to get results from table 3? In particular, from which domain were the different agents extracted from? Does each column correspond to a different training?
- What Domain adaptation method is used for SVHn and MNIST in Table 1? What is the corresponding performance of FedAvg and DP-FedAvg when applying it to them as well?
- In Section 3.1, example 2 appears a bit artificial to me insofar as it is more the heterogeneity of the different clients (with positive and negative x_i) which yields a null gradient than the clipping. In particular, this is a low-dimensional example, whereas in high-dimensions it is well known that the magnitude of the gradients play less of a role, see e.g. the effectiveness of SignSGD, Adam or TernaryGrad compression methods in the FL setting.

review_title: Marginally above acceptance

final_score: rating: 4: Ok but not good enough - rejection
review_content: Federated learning enables distributed clients to train a model without sharing the data with each other. This is typically achieved by a gradient descent type algorithm such as federated averaging. The paper argues that federated learning via gradient updates has issues and proposes to use a voting based method for training machine learning models using unlabeled global data.

I have several concerns about the paper:

1. The novelty in the new algorithms is not clear.  PATE-FL and Private-kNN-FL are largely similar to the original PATE and Private-kNN algorithms.
2. The paper argues that the existing gradient descent type algorithms suffer from slow convergence. However, recent works such as SCAFFOLD (https://arxiv.org/pdf/1910.06378.pdf) provide fast convergence rates for gradient based federated learning. It would be good to add comparisons with these new algorithms.
3. In Example 2, the problem can be mitigated by setting the threshold to \tau + \alpha. Hence its not clear if this is an inherent issue in gradient based methods or if it is just an issue with hyperparameter tuning.
4. Unlike standard works, the proposed algorithms assume the existence of a global unlabeled dataset, which is not always feasible. Furthermore, the approach inherently requires that the global data is similar to the private datasets, which has not been quantified. For a fair comparison in experiments, one should consider variations of federated averaging with the global public data.

review_title: A new private federated learning algorithm

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
The paper proposes two approaches (i.e., PATE-FL and Private-kNN-FL) to train a differentially private global model in a federated setting based on [1] and [2]. In PATE-FL, each client first trains a teacher model using their local dataset. The teacher models are used to make noisy predictions on a public dataset. Then, the public dataset with predicted labels is used to train a final model. In Private-kNN-FL, instead of training a teacher model, the prediction depends on the labels of the nearest neighbors. The experiments show that PATE-FL and Private-kNN-FL can outperform DP-FedAvg in terms of agent-level DP and instance-level DP, respectively.

[1] Scalable Private Learning with Pate   ICLR 2018

[2] Private-kNN: Practical Differential Privacy for Computer Vision   CVPR 2020

Pros:

(1) The studied problem is interesting and important.

(2) The proposed approaches have quite good performance compared with DP-FedAvg.

Cons:

(1) The work does not have sufficient algorithmic contributions. PATE-FL simply applies PATE [1] in the federated setting without the data splitting since the data are naturally partitioned. Also, Private-kNN-FL uses Private-kNN [2] in local clients to label the public dataset. The algorithms are an extension of existing algorithms in the federated setting without proposing new techniques. The theoretical analysis seems can be easily derived from the existing theorems with a modified sensitivity.

(2) The proposed approach lacks some important details. In Private-kNN-FL, a data-independent feature extractor is used. However, the authors did not mention how to get the extractor. In federated learning scenarios, the training data are usually sensitive and thus it is challenging to get a good and public feature extractor for the data. If the quality of the feature extractor is bad, then the labeling may be quite bad especially when the data are non-i.i.d. distributed (which is a common case in federated learning). Also, it is not clear how to set $k$ for Private-kNN-FL. 

(3) The experiments are not clear and solid enough. Some experimental details are missing. Also, more experiments are needed. Please see the detailed comments. 

Detailed comments:

(1) The experimental details are missing: the number of communication rounds for FedAvg, the value of $k$, the feature extractor, the test dataset of Digit task.

(2) I’d like to see the experiments given different numbers of queries/$\varepsilon$. The authors may add a figure to show the accuracy versus $\varepsilon$ of all approaches.

(3) The experiments for agent-level DP evaluation can be further improved. It seems that each dataset is i.i.d. partitioned into different clients. The authors can try non-i.i.d. partition [3,4], which is a key feature in federated learning.

[3] Communication-Efficient Learning of Deep Networks from Decentralized Data 		AISTATS 2017

[4] Federated Learning with Matched Averaging  	ICLR 2020


=======Post-rebuttal comments=========

Thanks for the authors' response. However, my main concerns on the feature extractor and the contributions are still not well addressed. Moreover,

(1) The authors agree that a good feature extractor is usually hard to obtain in practice. The feature extractor will significantly limit the applicability of the proposed approach.

(2) I found that the authors use ImageNet pretrained models in the experiments. This setting is weird. In my knowledge, the pretrained models are seldom used in the existing federated learning studies. The model may already be good enough before training and thus cannot well show the effectiveness of the algorithms. 
review_title: Simple and effective ideas, some details are missing

final_score: rating: 6: Marginally above acceptance threshold
review_content: Objective of the paper:
The objective of the paper is to provide new federated learning algorithms based on aggregating labels from a voting scheme, instead of aggregating the gradients directly, to achieve more efficient differentially private algorithms.


Strong Points:
1)  It looks like the methods get strong results.
2)  Mix of theoretical results (in supplemental materials) and practical results.  

Weak Points:
1)   The paper is not written as well as I would like.  Terms like clipping threshold are never actually defined in the main text.  Expressions like "each data".  Example 2 isn't well explained (why will it be clipped to 0)?  Statements like "lower bounded by O(BG/√T)"  (if it's a lower bound, shouldn't that be Omega not O?).  Tables are confusing (what is epsilon followed by a down-arrow?).  
2)  The paper assumes a lot of background knowledge on the recent related work.  (I suppose that can't be helped, but it does make it a hard read.)  I don't understand how the "votes" work, in that I don't know what are the "labels" being voted on, or why the label with maximum vote is a reasonable approach.   (If I asked for a rating for a product and 10 people chose 1 but 9 people chose 8, 9, and 10, would I think the right rating is 1?)  

Overall Rating:   I am left with the paper being borderline;  I will tentatively place it above the threshold based on the results looking good, and see what other reviewers suggest.  

Questions for Authors:

Other Feedback:  I think in the end I was not the right reviewer for this paper, and I would defer to other reviewers (and raise my score as needed).  The paper suffers perhaps from being "too big" for the too-low page limit offered by ICLR.  The authors have tried to cram in a lot of experiments up front (and some theory in the supplemental materials), but the paper seems written essentially for people in the area.  Not enough up front explanation;  lots of assumed knowledge on the part of the reader in my mind.  
review_title: Review of Voting-based Approaches For Differentially Private Federated Learning

Meta-review: This paper adapts the semi-supervised DP learning methods based on voting to FL. Specifically, PATE and private-kNN. The adaptation is fairly straightforward as those methods rely on averaging of votes a primitive that is a standard part of FL. The framework assumes that unlabeled data from the same distribution is available to the server, a very strong assumption.
As pointed out in the reviews, the empirical evaluation has a number of major issues. For example, the comparison is with fully-supervised SGD based techniques instead of a gradient-based semi-supervised approach.

Decision: Reject