Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a zeroth order Federated Learning method BAFFLE using forward only computations to replace back-propagation. The method intends to reduce memory storage and strengthen privacy against white-box vulnerability. The soundness of the finite difference method is justified by theory, experiments show that the method achieve comparable performance to conventional FL methods.    
strength_and_weaknesses: Strength: 
- clear presentation

Weakness: 
- Lack of novelty 
- Lack of convergence analysis 
- Lack of guidance on parameter choices and computational comparison 
- Limited experiments: shallow networks, iid environment 
clarity,_quality,_novelty_and_reproducibility: The paper is presented clearly and it is easy to follow.
summary_of_the_review: The paper proposes a zeroth order Federated Learning algorithm which is back propagation free. The main idea is to replace the gradient evaluation by zeroth order finite difference. This is very well known in zeroth order optimization literature. The more challenging part is to provide guidance on how to set the discretization stepsize and the number of samplings where the paper fail to provide any theoretical guidance. In particular, the more samples we draw, the more accurate the gradient estimation is, but the computational expenses will increase. The balance between the precision on the gradient estimation and the computational cost is a key for zeroth order method, which is a major omission of the paper. 

Besides the lack of convergence analysis, the experiment is also insufficient. Only shallow network are considered (two layers), it is expected that when the network goes deeper the gradient is more difficult to be estimated by zeroth order method (noise level increase), hence it will not be as competitive as gradient base method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a method to train federated learning using zero-order optimization. They use a gradient-free optimization approach and evaluate it on several benchmarks.
strength_and_weaknesses: Strengths:
- The problem the paper addresses is important. A common use case for FL is with clients with limited computing. As such, the reduction in memory by avoiding backdrop can be significant.
- The paper is clear and easy to follow

Weaknesses:
- Limited novelty: Mostly applies an existing zero-order optimization algorithm to FL
- Limited experimentation: Only uses LeNet, which has very bad performance on cifar10/100 even for the ground truth model and WRN only on MNIST. Not enough to be convincing.
- Inexact/misleading theoretical results: The authors ignore the dimension factor in both theorem 1&2 which is a critical factor especially as it is much larger than $\sqrt{k}$. Also, in theorem 2 what we care about is the operator 2 norm of $\hat{\Sigma}$, so just the fact that each element has $1/\sqrt{K}$ std around the desired value isn't enough (again will depend on the dimension). Ignoring the dimension is misleading, as there is no theoretical justification to use this approach with the given K values. The approach may empirically work well, but the theory doesn't support it.
- Exaggerated claims: 
   The authors in several cases raise claims that, in my opinion, are not supported by the empirical data. For example, they claim that 
   "BAFFLE achieves comparable performance to conventional FL using a relatively small value of K". In CIFAR10/100 we see about 7% 
   drop in accuracy even when using K=500, i.e. 1000 forward passes. Running 1000 forward passes on low resource compute is a 
   considerable amount and 7% drop is a considerable degradation in performance. 

   They also "assert that it is difficult to perform inference attack on BAFFLE". The support for that is very limited at best. They show the 
   distribution of $\Delta \mathcal{L}$ is the same between val data and random noise, but I do not agree this shows robustness to 
   inference attacks. The model is trained during many update steps and has to acquire information regarding the task to succeed. The 
   authors need to show that reasonable attacks fail to claim such robustness. 
- Unclear use of TEE. TEE from my understanding is part of the infrastructure to run FL and is agnostic to the exact algorithm. As such, it is not clear why is it important to include as part of the work. If the TEE details are relevant, it should be explained better.

clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear, although I would claim has misleading statements, and easy to follow. The quality of the experimental part is low and the novelty is small. The work is reproducible.
summary_of_the_review: The authors do now show empirical evidence to support their claims and as such I do not think this paper should be accepted.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose BAFFLE, backpropagation-free federated learning (FL) framework that uses multiple forward processes instead
of backpropagation. The main idea is to use Monte-Carlo approximation for stein's identity to approximate the analytical gradient. BAFFLE is mainly designed for two specific setups: low-resource edge devices, and FL systems with malicious clients. The authors prove convergence analysis for their estimator and show the effectiveness of their method in several FL setups (standard classification, robustness to attacks, and communication efficiency).
strength_and_weaknesses: Strength:
* First, it is written clearly and relatively easy to follow. 
* Second, the goal of the paper (addressing cases of low-resource end devices and robustness to malicious clients) is important and refreshing. 
* Third, the method, which is relatively simple, is constructed in a thoughtful way to adjust for FL setups. It seems to work in a descent way compared to the standard FedAvg. 
* Forth, although not mandatory in my opinion, Thm 1 & 2 are a nice addition. 

Weaknesses/Questions:
* As the authors stated, there is a noticeable drop in the model accuracy compared to FedAvg, but in my opinion it is fine for a first paper of this kind.
* Some information is missing, how did you perform the data split between the clients? There are multiple strategies for that. How did you optimized the hyper-parameters of the model? Was there a validation set? The authors should present the Top-1 results for CIFAR-100 for completeness (even though they are probably not so good). 
* Did you consider Softplus as a continuously differentiable alternative to Relu?
* Did you test how will the model perform in Personalized FL? It is especially interesting to show plots similar to those in Fig. 4 for real datasets that come from a different class distribution (as in PFL).
* How will the model perform under a more realistic FL setup such as having 100 or 500 clients?
* Can you quantify the computation gain (in terms of FLOPS or wall-clock time) compared to standard backpropagation?
* A comparison to more recent baselines other than FedAvg is missing in my opinion.
clarity,_quality,_novelty_and_reproducibility: The paper is clear, has novel contributions and the results are reproducible (code was provided).
summary_of_the_review: In my opinion this is a nice paper that deals with an interesting learning setup. The proposed solution is elegant and seems to be relatively efficient.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Paper studies Federated Learning (FL) and proposes using 0th-order estimators for approximating client gradients through only forward passes instead of exactly computing them through memory-wise costly auto-differentiation. Authors have refreshingly interesting motivations for doing this: (a) compute and memory constraints on edge client devices, (b) communication throughput constraints, (c) prevent data inversion attacks. The proposed 0th-order method for estimating the gradients from function value evaluations is pretty standard. It is notable that the author fail to properly discuss the vast literature on zeroth-order optimization, and in particular acknowledge similar algorithms in zeroth-order FL literature [1, 2]. Theorem 1 seems standard in the literature and it is not clear why they are not attributed properly to past work. 

Authors provide a lot of experiments and ablation studies which is commendable. Especially the memory comparison is very useful and promising. However, these results fail to fully justify the assumptions and motivations for this work. The local and global computational complexity (number of floating point operations per communication round) is not compared with the baselines. This is important since abstract claims "executing backpropagation on them incurs computational...overhead". The experiments to prove robustness to attacks is not quantitative and doesn't seem to be properly designed, specifically it doesn't compare the privacy leakage with standard FL algorithms. From the writing, it is really hard to know which experiments use FedSGD and which use FedAvg ("Ground Truth" is confusing). In practice FedAvg is almost always used, so it is not clear why FedSGD is chosen as a baseline. It is not clear how FedAvg+BAFFLE would work since they seems to require sending the pseduo-gradients (Tensors) from clients to servers instead of just function values like FedSGD+BAFFLE. In that case, the "#4 x K Bytes" annotation in the pseudocode is misleading. It would be great addition to the paper, if the authors can provide a graph plotting accuracy vs number of bytes of data communicated for different algorithms. Authors also do not compare their work with state-of-the-art algorithms eg: SCAFFOLD. Paper considers only cases with a small number of clients (up to C=100). Authors are highly encouraged to improve the experimental design and writing in above aspects.

[1] Li, Z., & Chen, L. (2021, October). Communication-efficient decentralized zeroth-order method on heterogeneous data. In 2021 13th International Conference on Wireless Communications and Signal Processing (WCSP) (pp. 1-6). IEEE.
[2] Fang, W., Yu, Z., Jiang, Y., Shi, Y., Jones, C. N., & Zhou, Y. (2022). Communication-efficient stochastic zeroth-order optimization for federated learning. arXiv preprint arXiv:2201.09531.
justification_for_why_not_higher_score: Failure to discuss vast related work literature. Inadequate or unclear experimental evalaution.
Decision: Reject