Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes a framework for sampling clients in each round of a Federated Learning training session. The proposed framework balances a notion of privacy (essentially a lower bound on number of sumands of any partial sum a server my reconstruct via linear combination of model updates retrieved throughout training), fairness gap (average gap in client participation across all rounds), and aggregation cardinality (average number of sumands in each round). The paper studies the relationship between these metrics, in relation to the convergence of the training. This is done by proposing new client sampling strategies, studying their properties, and comparing with naural baselines. The authors also provide experiments to support the analytical findings.
strengths_and_weaknesses: - I am unsure about the practical relevance of the assumptions regarding values of K and N.
- There does not seem to exist a lot of literature in client selection in FL with the purpose of improving privacy with respect to the server. The framework of differential privacy seeems important in that discussion, but the submission does not discuss that.
- The privacy guarantee is defined with respect to a particular time of reconstruction attack.
- The technical results give a good intuition on how the different metrics interact, even with baseline client selection strategies, which might be useful to practitioners. However, the assumption that dropout probability is the same across all clients seems unrealistic (although hard to avoid). 
questions: - I am unsure about the practical relevance of the assumptions regarding values of K and N. For example, See Table 1 in https://arxiv.org/pdf/1912.04977.pdf. This seems to suggest that in practice N is huge with respect to K (several orders of magnitude), and that the number of training rounds is also smaller than N. I am thinking: K in the 100s, N in the millions, and number of training rounds L in the thousands. With this in my opinion more relevant setting in mind, a given client will participate in no more than 2 sums. The results in appendix H, as refelected in the experiments section, seems to rely on N and L being of the same order. It be useful for the paper to state upfront some examples of values of N, K, L of relevance to the paper, and found in practice.
- The privacy guarantee is defined with respect to a particular time of reconstruction attack. In fact the sort of differentiation attacks that you describe motivates differential privacy. Using DP, one could ensure that a particular sumand does not alter the sum too much. Of course, if a user participates in many rounds this guarantee will degrade quickly, but that goes back to the choice of N, K.
- How does one implement your proposed mechanim at the scale of the above numbers (and the ones in the referenced paper)? Are there any challenges there? The experiments use small values of K and N.
limitations: -
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper explores the question of multi-round privacy leakage in federated learning with secure aggregation. To this end, the paper proposes a novel metric for multi-round privacy in FL. Existing FL secure aggregation protocols guarantee that the server can only learn the sum of N local models in any single round. The proposed multi-round privacy metric extends this guarantee to all training rounds. The paper motivates the need for multi-round privacy guarantees by demonstrating theoretically and experimentally that, under the assumption of partial user participation, existing secure aggregation protocols are vulnerable to attacks that aggregate models across multiple training rounds. To address this vulnerability, the paper proposes Multi-RoundSecAgg, a novel algorithm that provides a multi-round privacy guarantee. Theoretical analyses of the multi-round privacy, aggregation fairness gap and average aggregation cardinality guarantees of the proposed method are presented, as well as a convergence analysis. Finally, the proposed method is validated experimentally over range of FL settings and image datasets.
strengths_and_weaknesses: # Strengths

A. The writing and figures are very clear.

B. Strong motivation. The paper demonstrates that, under the assumption of partial user participation, existing secure aggregation protocols are vulnerable to attacks that aggregate models across multiple training rounds. This is an important limitation of existing methods, which merits attention from the community.

C. Strong novelty. The paper presents a novel multi-round attack on existing secure aggregation protocols. The paper proposes a novel metric for multi-round privacy in FL. The paper proposes a novel secure aggregation method that provides a multi-round privacy guarantee. The paper provides novel theoretical results for both existing secure aggregation methods and the proposed method. All of these are important contributions.

D. Strong theoretical results. The paper provides the theoretical guarantees of the proposed Multi-RoundSecAgg method in terms of multi-round privacy, aggregation fairness gap and average aggregation cardinality. The paper also provides a convergence analysis of the proposed Multi-RoundSecAgg method. These results provide important insights about the proposed method and its functioning.

E. Strong experimental results. Relevant baselines are compared against over a range of FL settings and datasets. Across all evaluations, the proposed method shows a better multi-round privacy guarantee, yet comparable test accuracy compared to the baselines.
 

 # Weaknesses

F. Experimental evaluations with real-world datasets and SOA model architectures would strengthen the paper. That said, this is not a major issue given the novelty of the work and breadth of theoretical results.

G. Given the focus on reconstruction attacks, the paper is missing a discussion of differentially private federated learning as a potential solution to the multi-round privacy vulnerability. 
questions: H. Given that T=4 is not a very strong privacy guarantee and that for T=6 the convergence rate already starts to take a significant hit, I wonder whether you're not better off adding noise to the gradients as in DP-FedAvg to protect the local data. Did you consider this option?

limitations: The authors adequately address the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Secure aggregation-based protocols can leak privacy over multiple training rounds in FL and do not provide long-term privacy guarantees. The partial user selection enables the reconstruction of the client's models. The authors propose a user-selection strategy that will provide long-term privacy guarantees and provide theoretical and convergence analysis. New metrics are proposed to capture the privacy guarantees.
strengths_and_weaknesses: Strengths:
- The paper is well-written and clear.
- Multi-RoundSecAgg is a novel scheme that provides privacy in FL in long term. It also ensures a fair selection of clients and shows tradeoffs between convergence and privacy.
- Proposed metrics are interesting, they allow for comparison between different user selection schemes in terms of privacy and that all clients participate in an equal number of rounds.
- Comparison with baseline experiments demonstrates the effectiveness of the metrics proposed.
- The remarks and assumptions provided are a plus.

Weaknesses:
- The privacy leakage of the aggregated models over multiple rounds is not addressed. This may be considered as future work.
- Applicability to cross-device only is missing.
questions: 1- Will multi-secagg work for cross-silo setup with partial user selection?
2- Will experiments with N=K show any deviation?

minor edits:
Line 113: "their."
Line 41-42: Refer/Cite the basis
Line 224: "number of selected at each"
limitations: Limitations are discussed in form of assumptions and remarks.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper concentrates on privacy-leakage in federated learning over multiple rounds. The authors note that secure aggregation protocols only have guarantees for a single aggregation round, whereas in federated learning the model is trained iteratively.  The paper proposes to measure and mitigate this privacy leakage over iterations. The main idea in the mitigation is to choose fixed groups of parties for model updates, so that an adversary can only ever see a contribution from the fixed group. This makes identifying any single individual party's contribution based on differences between iterations harder, since the individual contribution is always mixed in with the other group members. The proposed method essentially involves creating fixed subsets of users who are always chosen together for model updates. Another consideration is fairness in the sens of each party contributing an equal number of updates: the authors also propose a method by which all parties are chosen for updates an equal number of times on expectation. The paper then analyses convergence properties of the proposed method, and tests it empirically with several standard network structures and datasets.
strengths_and_weaknesses: ### Update after discussions

After the rebuttal and the discussions, I raise my score to recommend acceptance. I trust that the authors will improve the paper based on the discussions.

### Strengths

+ The idea of having some secure aggregation-type guarantees over several iterations seems like a fine one.
+ The theoretical results backing up the method are comforting, e.g., in the sense that the proposed method can be shown to converge under some fairly standard assumptions.


### Weaknesses

- The most glaring issue with the paper is that it completely omits discussing or even mentioning differential privacy (DP) and related definitions, which have been the standard privacy definition in machine learning for years, and that have also been widely used with federated learning (see e.g. Kairouz et al. 2019 for a quick overview of the basic idea in the context of federated learning, Dwork & Roth 2014 for a basic introduction to DP). Instead, the privacy discussed in the current paper is more related to secure computation, where the formal guarantees are on revealing only the end result of a computation. Calling such definitions privacy preserving is problematic for various reasons. One major issue is that the end result might well give out the input data in the clear without having any problems in satisfying this kind of definition of privacy-preserving (e.g. by choosing local loss functions s.t. the optimal value is an actual data point for a single client and 0 for everyone else would give out the single data point while still satisfying this kind of privacy guarantees). 
The guarantees are also brittle in the sense that any side information might lead to a catastrophic privacy breach, where one or more input data points are suddenly revealed (e.g. consider what happens to others if one of the fixed group members gives out it's updates, or an adversary gains information on such values from other sources).
As an immediate fix, I would suggest including some discussion on the privacy-definition that also considers DP, clarifying the claims that this is the first paper that considers privacy-leakage in federated learning over iterations (e.g. lines 51, 84-88), and changing the emphasis to be less on general privacy-preservation and more specifically on what this method tries to protect. More interesting, although also more work-intensive and hence probably out of the question for now, would be to try and combine the current papers' results with DP and show that the proposed method does indeed enable better privacy by limiting the amount of information an adversary can gain.
- Related to the previous point: I have a hard time understanding what are the consequences of providing privacy in the sense used in this paper.


### References

Dwork & Roth 2014: The algorithmic foundations of differential privacy.
Kairouz et al. 2019: Advances and open problems in federated learning.
questions: 1) In the experiments, is there some reason to stop training when you do? Would e.g. the partition baseline eventually reach ~ same performance, and the main issue is convergence speed, or is there some other reason why it would perform worse?

2) It seems that the proposed method assumes that the other parties in the same group are honest(?). Please mention the actual assumption as part of the the threat model.

3) I think Remark 7 on lines 290-295 would make more sense as a separate theorem: this seems like an important property that should be stated more formally.


#### Minor details:

Please add a table on the notation to Appendix: trying to follow the derivations can be frankly painful when one needs to hunt for the meaning of symbols all over the place. Fix typos on lines 113,224.
limitations: There is no discussion on the limitations of the proposed method, including in Section 7, which is pointed out as containing such discussion in the paper checklist.
review_title: null

Meta-review: metareview: The secure aggregation protocol is a basic building block in federated learning. It allows a central entity to learn the sum of vectors held by the clients, without being able to (noticeably) distinguish two different sets of vectors that lead to the same sum. This paper studies the question of how much privacy is leaked across multiple rounds of the secure aggregation protocol. It proposes a new “multi-round privacy” notion which aims to quantify the privacy leakage across multiple rounds of the secure aggregation protocol. The paper shows that the commonly used random subsampling protocol would violate this notion of privacy after a number of rounds that is linear in the number of users. The paper gives another algorithm, Multi-RoundSecAgg, which has better privacy properties, according to the proposed notion.

There are several drawbacks of this paper, several pointed out by the reviewers:

1) It is well-known that federated learning without differential privacy (DP) is vulnerable to the leakage of user’s sensitive information (e.g., inversion attacks), which this paper seeks to protect. E.g., from the aggregate vectors, one could directly read sensitive information pertaining to one user (e.g., if the individual vectors are sparse and have disjoint supports).
The argument provided by the authors in the rebuttal -- that they chose not to consider differential privacy since it hurts model accuracy -- is not satisfactory. In fact, the paper itself argues that even for the proposed multi round notion of privacy, for a more stringent privacy level to give the same utility, a larger number of rounds is needed until convergence. So even with the new notion, privacy does not come for free and has to be traded-off at least against efficiency (more precisely convergence speed).
It is also worth pointing out that in the case of DP, the multi-round leakage is already handled through composition theorems, and accounted for. See, e.g., the “Practical and Private (Deep) Learning Without Sampling or Shuffling” paper of Kairouz et al. (ICML 2019).

2) As pointed out by one of the reviewers, reconstructing an individual model after a number of rounds larger than the number of users is not realistic. Typical federated learning models are indeed trained for a number of rounds much smaller than the number of users. A detailed discussion of this limitation would be expected in the paper.

3) The claim that the worst-case is achieved when the local models do not change at all seems a bit hand-wavy to me. On a high level, it seems to ignore the correlation between the different models that would arise during the training process. Due to this correlation, it might be that all the users’ local models converge to the first user’s model. In this case, wouldn’t that be worse than having the models not change at all? Formalizing this claim, and its proof, would be helpful.

4) Given that the paper proposes a new privacy notion, discussing the qualitative properties and limitations of this notion is expected. E.g., does this notion compose across multiple applications? How does this notion behave in the presence of side information? 

Overall, in its present form, and for the reasons listed above, the paper falls short of the acceptance bar at NeurIPS.
confidence: Less certain
Decision: Reject