Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new federated learning algorithm which allows clients to perform their updates on the model using the gradient of the model obtained by other clients. This involves data samples stored on other clients memory in updating the model locally by a client. The paper provides convergence analysis for the proposed algorithm and examines its performance through experiments.
strength_and_weaknesses: Strength: The paper proposes a novel way to enable clients to share their gradients and use this information to update the model locally. The paper proves the convergence of the proposed algorithm and provide convincing experimental results to validate the theoretical analysis provided in the paper.

Weaknesses:

- Using the proposed algorithm, the server has to store a caching gradient matrix whose dimensions scales with the number of clients. When the number of clients is so large, to implement the proposed algorithm a server with a very large memory is required.

- It is beneficial for the paper if the convergence rate of the proposed FedAMD is compared to FedAvg to see what are the benefits of FedAMD compared to FedAvg in terms of convergence. FedAMD requires larger memory from the server side and it is interesting to see if FedAMD uses this memory successfully to obtain better convergence rate than that of FedAvg.

- From reading the Algorithm 1 on page 4, the role of cached gradients in updating models is not clear. It would be great if Algorithm 1 can be revised such that the role of cached gradient become obvious.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and provides a novel algorithm. I could not check proofs carefully.
summary_of_the_review: In summary, the paper proposes a new federated learning algorithm at the cost of the need for a server with a large memory capacity. The paper proves the convergence of the algorithm. However, the paper lacks a detailed comparison of the proposed algorithm's convergence with the convergence of FedAvg.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of improving convergence in Federated Learning especially under partial client participation settings. Differently from previous work, which either used large batch sizes or variance reduction techniques while resorting to full client participation, the authors propose a randomization of FedAvg and FedSGD. In that, the clients switch from being either anchor or minor groups. Convergence results are derived for non-convex losses under general conditions. Experimental results illustrate the efficacy of the approach. 
strength_and_weaknesses: Strengths
+ The paper is very well written and the algorithm is well motivated.
+ The convergence results show an $O\left(\frac{1}{\epsilon}\right)$ for general non-convex losses and linear convergence with the extra PL assumptions which is an improvement over the state of the art.
+ The proposed algorithm FedAMP also shows the efficacy of schemes which resort to heterogeneous batch sizes and updating schemes while resorting to variance reduction.
+ The experimental results are comprehensive in terms of comparison with other baselines and tends to outperform other baselines.


Weaknesses

- Though the algorithm claims to use partial client participation; it requires a full client participation at the first step which in turn requires each gradient from each client to be individually available to the server and that too persisted over time instead of being available in an aggregated manner. This severely undermines the privacy-preserving nature of FL as it makes each client susceptible to gradient inversion attacks. It is also not clear how can this be alleviated without resorting to additional storage in each device.
- The convergence results while improving in terms of $\epsilon$-accuracy of the error, is substantially worse as compared to other baselines in terms of dependence on the total number of clients. While other algorithms scale inversely with respect to the total number of clients, FedAMP scales linearly with the number of clients in the setup. Unless, the number of selected clients is always a function of the total number of clients, it seems the performance of FedAMP gets worse with increasing number of clients, if the number of clients selected per round is constant. It is also worth noting the performance benefit comes at the expense of additional assumption 3.
- An inherent assumption made by the authors is that the number of samples across clients is the same. The method by which a client is assigned to being an anchor or minor is solely decided by a coin toss and not based on the number of samples. In the general case, some clients may have fewer samples, in the case of which the number of local epochs and the batch size can't be uniform. It is also not clear how the choice $b$ and $b^{'}$ affects the algorithm performance.
- The authors miss comparing and contrasting with FedNova by Wang et.al., which especially takes care of the case where different clients undergo different number of rounds along with the flexibility of running different local solvers. It would be good to add comparisons with FedDyn and FedOPT which are highly performant baselines.
- While a theoretically optimal $p$ is derived, it can't be derived in practice as quantities such as the number of samples on each device and $\sigma^{2}$ is unknown to the server. 
- For the variance reduction phase, it requires additional storage of the past gradient which is the same size as that of the model. This can be particularly prohibitive with larger model and resource constrained devices.
clarity,_quality,_novelty_and_reproducibility: The paper is well written, easy to understand in terms of clarity and is of quality. The paper modifies well known techniques used in the context of FL and carefully tunes them so as to attain better rates. Hence, the originality is moderate.
summary_of_the_review: The paper has weaknesses in terms of the convergence proofs with the dependence on the total number of clients being significantly worse as compared to other schemes.  The applicability, usability and originality of the paper is undermined by some assumptions which either don't hold or are difficult to verify in practice. Moreover, the randomization of a client either doing a local-SGD style update or no update, can lead to stretches with very few clients contributing to the update. Having said that, I would be more than happy to increase my score if my concerns are addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a framework FedAMD, that disjoints the partial participants into anchor and miner groups. Clients in anchor group target to discover the bullseyes based on their local data distribution, while clients in the miner group perform multiple local updates and finally drive the update of the global model guided by the global bullseye. Under the partial-client scenario, this paper gives many theoretical proofs that FedAMD achieves sublinear speedup under non-convex objectives and linear speedup under the PL condition. Experimental results demonstrate that FedAMD is superior to SOTA works compared with BVR-L-SGD, FedAvg, FedPAGE, SCAFFOLD on Fashion MNIST.
strength_and_weaknesses: Strength:
1.The proposed FedAMD achieves sublinear speedup under non-convex objectives and linear speedup under the PL condition.
2.The proposed FedAMD is superior to SOTA works compared with BVR-L-SGD, FedAvg, FedPAGE, SCAFFOLD on Fashion MNIST.
3.The proofs of theories are detailed and correct, and they are consistent with the experimental results.

Weaknesses:
1.It seems that there is no analysis about the influence of initial model (line 1) on the experimental results in this paper. In fact, the influence of initial model exists (assuming that the best model is set at the beginning). It is suggested to add analysis about the influence of initial model.
2.The experiment is too simple. "We train a convolutional neural network LeNet-5 using Fashion MNIST". Such a specific experiment may affect the degree of confidence of the experiment results.
3.This paper proposes two strategies(constant and sequential) for selecting anchor and miner groups. But it would be better if there were a strategy based on the performance of each client.
4.The analysis of g(i)t,k (line 19)is reasonable, but it is worth discussing whether a factor α is needed for second and third items.
5.For the analysis of Figure 1, it seems that only Communication Rounds=400 is considered(why is 400?). Such analysis seems to be one-sided, and there are other considerations in fact, such as the change rate of the training loss.
clarity,_quality,_novelty_and_reproducibility: Quality: The proposed FedAMD is superior to state-of-the-art works, and there are many theories to support the experimental results in this paper.
Clarity: The algorithm 1 is detailed and reasonable, but some lines(line 1 and line 19)need additional analysis and discussion.
Originality: This work may be the first work to analyze the effectiveness of large batches under partial client participation.

summary_of_the_review: In general, it is a good paper. It has the SOTA results, many theoretical proofs and analysis. However, there are some weaknesses in the setting and analysis of the experiments section.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: After careful consideration of the paper, the reviews, and the discussion points on this paper, it has been decided that the paper is not yet ready for publication in ICLR. The main issue is that none of the reviewers were enthusiastic about the paper, relatively. This meas and there were just too many other papers that were much more highly considered (and rated) by reviewers than the give paper, and ICLR has a low acceptance rate. On my own reading of the paper, I think the writing can be improved as well --- for example, even reading through the abstract, there are things like the use of the word "disjoints", which is rarely used a a verb, a better word would just be to use "separates." There are a variety of such improvements that would help throughout the paper, but that wasn't a key reason for the final decision. Some of the key reasons for this decision are (and ways you can address this in the next version to a future conference):

* Requirement for full client participation
* Remaining questions about $\epsilon$-accuracy compared to baselines, this needs
to be very clear in the initial submission
* The issue of imbalance needs to be made much more clear in the initial paper submission, and the sensitivity should be tested and evaluated.
* Comparisons with methods such as FedNova needs to be more clearly stated and done in the original submission.
* Improvements in convergence proofs,
* Could some improved analysis about the influence of initial model

It is recommended to consider all of the reviewer comments in the next version of the paper and submit to the next conference to ensure that these questions do not arise again.


justification_for_why_not_higher_score: see above
justification_for_why_not_lower_score: see above
Decision: Reject