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 considers secure federated learning (FL) and aims to tackle the challenges of non-IID data distribution across clients and dropouts. The paper proposes that each client first secret shares their data to all other clients using Lagrange Coded Computing. This involves quantizing the data and appropriately mapping it to a finite field. Then, gradients are computed over the secret shared data. Since secret sharing operates over a finite field (as opposed to real numbers), the paper proposes to use *polynomial integer neural networks*, where quadratic function is used as a non-linearity (instead of ReLU or other typical functions) and a mean squared loss is used (instead of cross-entropy loss). The server first ‘decodes’ the gradients computed on secret shared data to obtain the gradient on the quantized data. Then, it sums the gradients and takes a step to update the global model. 
strengths_and_weaknesses: *Strengths:* The paper considers an important problem of tackling data heterogeneity and privacy in FL. These issues are intellectually challenging and practically important.

*Weaknesses:* 

1. The proposed solution requires each client to secret share their data to all other clients. Clearly, this is going to incur substantial burden in terms of computation and communication costs. The paper does not explicitly characterize the computation and communication costs for secret sharing client data. (It just mentions that the ‘sharing’ parameter $K$ impacts the costs, but explicit analysis seems to be missing.)

2. One of the main motivations of the paper is to tackle client dropouts. However, it looks like all clients need to be present during the phase of secret sharing data. This assumption needs to be clearly stated and it would be good to add a discussion around this. In particular, if the communication cost of transferring secret shared data to other clients is large, then this phase will take considerable time. In this case, not allowing any dropouts during secret sharing and requiring all clients to be present can be a major limitation. 

3. The paper does not give sufficient details in terms of gradient computation and securely transferring secret shared data to clients. (Specific comments in the Questions section.)

questions: 1. The key technical idea in the paper involves computing gradients on secret shared data. However, the paper does not give details on the gradient computation on secret shared data. It simply mentions that the gradient (when loss is MSE and non-linearity is square function) would be a multivariate polynomial in $(\bar{X}, \bar{Y})$ and parameters $\mathbf{w}$. Without any details, it is difficult to understand how the server decodes $\tilde{g}(\tilde{X}_j^{(I_t)}, \tilde{Y}_j^{(I_t)})$ in line 9 of Algorithm 1. During secret sharing, all the $K$ shards of each client are encoded together, while the server decodes gradients for each shard separately. It is important to add details and provide a proof of how the decoding happens. 
Currently, it is not even clear how the gradient $\tilde{g}(\tilde{X}_j^{(I_t)}, \tilde{Y}_j^{(I_t)})$ is defined. Is this an average of the gradients in  batch $I_t$? 

2. In Theorem 2, the security is mentioned in terms of  $\tilde{g}(\tilde{X}_j^{I_t}, \tilde{Y}_j^{I_t})$. However, the server decodes the gradients to obtain the gradient on uncoded data $\tilde{g}(\bar{X}_j^{(I_t)}, \bar{Y}_j^{(I_t)})$ for $j\in[K]$. Is it not that the privacy for server should be proved in terms of the decoded gradient? In other words, Theorem 2 should be stated in terms of $\tilde{g}(\bar{X}_j^{(I_t)}, \bar{Y}_j^{(I_t)})$? Overall, it is not clear how the server only obtains an *aggregation* of gradients. It is important to expand on this. 

3.  In FL all communication typically happens through the server. It is important to mention how a client will securely communicate the secret shared data to all other clients.

4. The proposed scheme involves several approximations as stated below:
* Quantization to convert real-field data into integers 
* Square function as a non-linearity instead of ReLU
* Mean squared loss instead of cross-entropy loss
* Stochastic quantization during update (eq. (6))
* Neural network weights are restricted to be integers

It seems like these approximations will negatively impact the accuracy. However, performance evaluation in Fig. 2 depicts that the proposed method consistently outperforms FedAvg for all datasets. It would be important to discuss why these factors mentioned above do not impact accuracy, and if they do, then are any optimizations performed to overcome them. Otherwise, the results appear to be a bit 'magical'.

In particular, it is known that the cross-entropy loss typically performs better than MSE. Furthermore, quadratic approximation for ReLU is known to severely degrade accuracy in some settings, see e.g., Mishra et al., “DELPHI: A Cryptographic Inference Service for Neural Networks,” Usenix 2020. Why these issues are not observed in the proposed method, and if they are observed how they are overcome?

5. Convergence analysis considers population loss instead of empirical loss. Convergence analysis often considers empirical risk. It would be helpful to comment on this.

6. To tackle non-iid nature, there are solutions such as FedProx, which change the local optimization problem at the client side, but still perform averaging at the server side. It is straightforward to use secure aggregation with FedProx as one solution of privacy + data heterogeneity. How would the proposed method compare against FedProx + secure aggregation (or similar solutions)?

7. It would be helpful to specify if the paper focuses on cross-silo setup or cross-device setup. Since cross-device setup consists of a large number of clients, performing secret sharing across all clients may be costly. On the other hand, the problem of dropouts is less severe in the cross-silo setup. It would be good to add a discussion on this.

8. Footnote on page 4 says that “The constant scalar c could be the absolute value of the minimum entry in dataset (X, Y).“ Since the dataset $(X,Y)$ is distributed across clients, how is it possible to find such a scalar $c$? Also, if the value of $c$ is data dependent it may not be appropriate to call it a ‘constant’.

9. What field size $p$ is used in the experiments?

10. Experiments use MLP with two hidden layers with $K=1$ and $T=1$. It is not clear why the degree of gradient as a polynomial would be 8. Can the authors give more details?

limitations: As mentioned in the Weaknesses, the proposed solution would incur heavy costs during the secret sharing phase. Also, dropouts cannot be tolerated during secret sharing. In addition, as mentioned in Questions, the proposed scheme relies on several ‘approximations’, and it would be important to discuss their impact on the accuracy and/or speed of convergence.
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: This paper proposes a Dropout-Resilient Secure Federated Learning framework based on Lagrange coded computing to
tackle two problems in FL: the non-IID data distribution and client dropout.

The clients share their datasets secretly using LCC to handle the non-IID problem and client dropouts. At the beginning of the training, the clients secretly share their private datasets with each other via Lagrange coding. This allows clients to access an encoded version of the global dataset. After collecting the computation results from a certain number of surviving clients, the server performs polynomial interpolation to decode the gradient.

The authors introduce the idea of polynomial integer neural networks (PINNs) for their proposed framework to work, since they need to correctly decode the gradient at the server, and that the gradient has to be a polynomial function in a finite field. 

The authors provide some theoretical analyses and numerical experiments to back their claims. 
strengths_and_weaknesses: Strengths:
- The paper is well written and it is very easy to read
- The paper is back by theoretical analyses and also backed by numerical experiments
- The idea of the paper is quite novel and interesting, even though it may not be extensible to big and practical neural networks and practical FL settings


Weaknesses:
- As correctly pointed out by the authors, the generality of the idea is questionable. Requiring neural networks to be polynomial integer neural networks (PINNs) is an assumption that probably cannot be hold in practice. 

questions: Have the authors also looked the LEAF datasets for the experiments? LEAF seems to be the standard dataset for FL papers, with natural client partitions and other FL constraints. 
limitations: As pointed out by the authors, 

- the generality of the idea is questionable. Requiring neural networks to be polynomial integer neural networks (PINNs) is an assumption that probably cannot be hold in practice. 
- Similarly, the degree of the gradientin a PINN increases exponentially with the number of layers of the neural network, limiting training larger models
- multiple local SGD steps is yet not supported, which is quite common in practical FL settings
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: This paper aims to address the non-iid and dropout problems in (privacy-preserving) FL using the Lagrange coded computing framework. Apply the LCC framework, it proposes a class of network called Polynomial Integer Neural Networks.

strengths_and_weaknesses: Strengths:
    (1) The paper is clearly written - problems, motivations, and intuition of the main methods are easy to understand.  
    (2) The method is novel and original (the paper shows how to use PINN to adopt LCC in the setting).  
    (3) Theoretical guarantees are given.  
    (4) The limitation is stated - the degree of the gradient grows fast so that the network can not be deep, which is reasonable.  

Weakness:
    (1) The experiment setup for baselines is not clearly stated - How is the FedAvg setup? Is it combined with secure aggregation methods?   
    (2) The experiment results are not clearly explained. Please see below for concrete questions.  

questions: (1) How are the baseline setups different than the main method (i.e., how do they tackle non-iid, dropout problems)?   
(2) The author claims "We observe that FedAvg is influenced by the dropout problem due to the biased gradients" (in lines 295-296). How is this inferred from Table 1 and figure 2?   

Overall, the paper is well written and shows enough technical strengths. Please address the questions in experiment setups and analysis. I am willing to raise my score if the experiments are good as well.

limitations: The author has stated the limitation in the main paper.
review_title: null

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: This paper proposes a new framework named Dropout-Resilient Secure Federated Learning (DReS-FL) to address the non-iid and client dropout issues in federated learning. By leveraging Lagrange coded computing (LCC) and secret sharing, DReS-FL enables clients to securely share their data to build a ‘public data set’ and participate in the learning task. To further guarantee the gradients are polynomial functions in a finite field, this paper introduces the polynomial integer neural networks (PINNs) to enable the framework. The experiment results show the DReS-FL proposed can achieve higher accuracy when facing clients dropping out.

strengths_and_weaknesses: Strengths:
1.	Addressing the FL dropout issue is a hot topic, and the proposed framework is very interesting. 
2.	This paper proposes the polynomial integer neural networks (PINNs) and proves PINNs can ensure the correct decode of the global gradient without privacy leakage.
3.	The DReS-FL has been formally analyzed to be resilient to a certain number N of client dropouts.

Weakness:
The secret sharing mechanism is not well presented.

questions: 1.	To perform Secret Sharing, the parameter K should be set before the learning task start, but whether K is constant?
2.	Line 156 said a large value of K can reduce the communication cost, can you explain the reason? (as I think more shards may bring more communication times between different clients)
3.	How can the clients establish communication?
4.	Are there any rules for sharing the data? How can a client determine whom he should share the shards with?

limitations: See the questions.
As the communication cost is often a bottleneck for FL, involving massive communication may further worsen this issue; please consider providing the discussion.
review_title: null

Meta-review: metareview: This paper discusses a novel secure aggregation method for dropout resilient federated learning. The proposed solution is interesting, with some reasonable theoretical and empirical analysis. The authors did a good job of engaging with the reviewers in the discussion phase. From my own reading, I found the paper quite lacking in motivation though. The primary motivating scenarios for secure aggregation are for FL from on-premise datasets, such as learning in healthcare settings across hospitals or insurance providers. In such cases, is there a significant dropout concern? On the other hand, I don't see the proposed schemes as practical in the learning from mobile devices scenario, where there is not even a fixed client pool to begin with. It seems that the authors need to think about the motivating scenarios for their work and add discussion about this to the paper.
confidence: Certain
Decision: Accept