Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers the problem of Federated Learning (FL) with a random selection of clients in order to minimize $\sum_{i} p_i \mathcal{L}_i(\theta)$, where $\mathcal{L}_i$ is the loss function of client $i$ and $p_i$ is its weight, which is often proportional to the dataset size on client $i$. The authors study the impact of assigning weights $\omega_i(S_t)$ and probabilities $P(i\in S_t)$ to client $i$ when averaging the result of running SGD for $K$ steps locally on each sampled device. The authors first prove a decomposition bound (Theorem 1), which establishes a simple recursion for the distance to the solution. As far as I can see, this result is never used to establish a convergence rate. In addition to Theorem 1, under smoothness, bounded variance, and bounded dissimilarity assumptions, the authors study convergence rates of unbiased client sampling in the nonconvex regime (Theorem 2). As a side contribution, the authors also consider using different stepsizes $\eta_l, \eta_g$ locally and globally.
main_review: ## Main point:
I don't see a sufficient contribution in this work for its acceptance. First of all, most of the results are straightforward. The results from Appendix A require no more than computing expectations and simple summations. Theorem 1 is not even a convergence result but rather a simple one-step recursion that can be obtained by expanding norms and scalar products. Theorem 2 is proved using standard techniques from prior work. Taking all of this into account, I feel like the technical contribution is extremely limited.

In addition, I do not see any significant insight into the convergence of FedAvg. The impact of client sampling has been studied before and optimal sampling strategies were proposed by Chen et al. (2020), and other works, for instance (Fraboni et al., 2021), have studied more forms of unbiased sampling. This work gives a bit more detail into how it all affects training but it all seems trivial, but without new improved strategies for sampling, it is hard to see the value of this study.

### Minor concerns:
I think it's a bit confusing to denote the constant in Assumption 3 as $\kappa$ since $\kappa$ is often used to denote the problem conditioning.

### Typos:
"on a fix amount" -> "on a fixed amount"  
"dependence of FL convergence from the variance" -> "dependence of FL convergence on the variance"  
"through a fixed amount K of SGD initialized" -> "through a fixed amount K of SGD steps initialized"  
"needs to be collinear with the global direction" -> "needs to be correlated with the global direction"  
"Our work is structured as follow." -> "Our work is structured as follows."  
Assumption 3: "There exists constants" -> "There exist constants"  
The right-hand side of Equation (63) misses square brackets after "Cov".
summary_of_the_review: 1. I see very little novelty in this work. Most results follow by combining some simple identities for expectations of random variables with convergence results for Local SGD from prior literature (Wang et al., 2020a), (Li et al., 2020c). Adding a global stepsize also does not change almost anything in the proofs.  
2. The results do not have a clear significance. While Federated Learning is an important and challenging problem, and client sampling may play a big role in its efficient use in practice, the results in this paper provide us with little new insight.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies a framework for studying the impact of client selection strategies for unbiased aggregation at the server for federated learning. The framework separates the impact of client selection, client model drift, global model drift thereby providing new insights regarding the impact of client selection. In particular, the paper proposed a decomposition theorem which quantifies  the dependence on client sampling. Finally, experimental results on Shakespeare back the theory and demonstrate the effectiveness of one sampling choice over another based on the loss function setup in a FL framework.
main_review: Strengths:
- The paper is very well written and very easy to understand and follow.
- The paper studies a framework for studying the impact of client selection strategies for unbiased aggregation at the server. The framework separates the impact of client selection, client model drift, global model drift thereby providing new insights regarding the impact of client selection.
- Through the framework, the authors provide theoretical and empirical evidence as to in which scenarios weighted sampling is preferrable over weighted sampling. Previously multiple papers had observed stable  convergence performance  with weighted sampling for cases  data sample is weighed equally. This framework validates those claims.
- The experimental results back the theory.

Weaknesses:
- As showcased in Wang, et.al., "Tackling objective inconsistency in federated learning" (FedNova), the convergence rate in FL is affected by the objective inconsistency as well. It is not clear from the decomposition theorem, whether such an inconsistency is factored in.
- It is not clear from the experiments what sort of data distribution was considered for the clients. It is not clear if the claims made in the paper continue to hold for both iid and non-iid distributions.
- Moreover, the number of clients selected is roughly 50% of all clients present in the experiments. With unbiased aggregation, the variance is controlled with such a high selection rate. It is not clear if the number of clients are selected at a rate 5-10% clients per round or even lower, which is characterized by zero bias and high variance would have a different observation. With variance being the main deciding factor now, is there still a noticeable difference between sampling strategies? Also, how noticeable is the difference when each client undergoes just one step of SGD or likes of that as opposed to 50 steps of SGD. I would recommend the authors to add more experiments with only 5-10% clients being selected in each round.

Finally, as a suggestion to the authors: In most practical systems, the server doesn't have the privilege to sample clients based on MD or uniform sampling. But, instead the sampling in practical FL system is mostly event triggered. In such a case, how would one go about sampling clients and ensure unbiasedness of aggregation schemes?
summary_of_the_review: This paper proposes a new framework to study the effect of client sampling strategies based on weighting of clients/samples in a federating learning setup. While the framework is new and provides new insights, there are some clarifications required in terms of the theoretical convergence results. The experimental results are also incomplete and not up to the mark. Additional experiments are required. The paper is in a good shape, but without the improvements above it's not a strong paper yet.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The author(s) studied the impact of the client sampling for FL. In particular, the author(s) proposed a decomposition theorem and used it to obtain an improved convergence analysis of FedAvg. Numerical simulations are conducted to support the author(s) theoretical analysis. 
main_review: **Pros**:
- The paper is well-written
- The theory is well-developed and is correct to my knowledge

**Cons**:
My major concern is on the novelty of the theoretical analysis of clients' sampling.

- Clients sampling in FL and mini-batch sampling in SGD are closely related to each other. Related works on the sampling strategy for SGD are not well-address, for example [1, 2]. The major difference between FL and mini-batch SGD is that FL runs more steps during the local update, but SGD performs a single step. But this difference should not cause too much trouble. It seems that the analysis of the sampling scheme for SGD can be directly applied to the context of FL. Could the author(s) elaborate on the challenge of applying importance sampling to FL?

- Unbiased client sampling is closely related to unbiased gradient estimator, which is common knowledge in stochastic optimization. The discussion on unbiased sampling doesn't 
seem to be something new.

- The authors emphasized the importance and novelty of Theorem 1. I read the proof, and it seems to me that Theorem 1 is a detailed expansion of the variance term 
(instead of just bounding the variance by some constant in the literature). It is also straightforward that the variance can be decomposed as the summation of covariance. 
The Theorem feels somewhat incremental, and I am not sure if it is significant enough to be accepted in ICLR. 

- My comment on Theorem 2 is similar to the above comment for Theorem 1. The result is from a detailed expansion of the variance term, and I am not sure if it is significant enough. 

Some minor comments:
- In eq. (1), is it necessary to introduce "I"? Can we just write as \sum_{i=1}^n?
- In the second paragraph of page 7. The author(s) said that MD has an additional O(n) cost to construct the distribution and could be expensive. I think we only need to run this operation once before the FL start. I doubt if constructing the probability density for MD will introduce non-trivial overhead.


[1] Peilin Zhao, Tong Zhang. Stochastic Optimization with Importance Sampling for Regularized Loss Minimization. ICML 2015.

[2] Dominik Csiba, Peter Richt´arik. Importance Sampling for Minibatches. JMLR 2018.

summary_of_the_review: The paper is well-organized. But I am not convinced by the significance of the theoretical analysis of this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies the effect of client sampling in the convergence of Federated Learning. This work clearly formulates the setup of client sampling and studies the effect of client sampling to FL progress.
main_review: 1. The main theorem 1 (decomposition theorem) is somewhat too microscopic (as it only studies one round) and more like a direct corollary of the equation (3), and is independent with the other procedure in FL (e.g., local optimization steps). Hence, I would recommend calling theorem 1 "decomposition theorem/lemma for client sampling", rather than the "decomposition theorem for the convergence of FL" 

2. The decomposition in theorem 1 is somewhat incomplete as it involves $\theta_i^{t+1}$ outside $Q(\theta^t)$. This makes it hard to interpret the trade-off of the three terms in $Q(\theta^t)$. 

3. The paper argues that MD sampling should be used as default case, while uniform sampling is superior only in the special case when clients have the same amount of data. I cannot find a theoretical justification of the first part of this sentence. It is only shown in corollary 1 that Uniform is better than MD in certain cases, but not the reverse side. From Theorem 1, it is clear to me how to argue when MD can be better than Uniform Sampling, as the third term in $Q(\theta^t)$ is always larger in MD.
4. The convergence theorem 2 only studies the regime with sufficiently small local ste
p size $\eta_l$, which effectively reduces to the mini-batch regime. Is it possible to establish  the convergence without assuming sufficiently small local step size $\eta_l$?

Minor comment and suggestions:

1. "The decomposition theorem also provides a necessary condition for an optimization step to improve the current global model: the expected client contribution needs to be collinear with the global direction of the optimum". This claim does not sound accurate. Collinear is neither sufficient or necessary for making progress. The only necessary condition we can read from (7) is the negative inner product. Also, an optimization algorithm does not need to always make progress in distance to optimum every step to "improve" the model.
2. Table 1: the notation $\alpha$ appears much earlier than it was first referenced in the main text (before §3). For better reading experience, it would be great if the authors can hint the semantic of $\alpha$ in the caption of tale 1.
summary_of_the_review: Overall I appreciate author's effort in formulating and understanding the nuances in client sampling. My main concern of this work lies in the significance of the results as well as the interpretation. As this time I think the paper is marginally below the acceptance threshold, but I am happy to re-evaluate the paper if the authors can address my concerns.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper analyses two client sampling strategies for federated learning algorithms. This work compares Multinomial distribution and Uniform distribution. The authors provide a decomposition theorem, that gives some insights into the impact of client sampling. Moreover, they provide convergence guarantees for the general non-convex case under some additional assumptions such as Bounded Dissimilarity. An experimental comparison of two sampling schemes is done at the end of the paper. 
main_review: Structure.

This paper is well-written and it has a clear structure and narration. All assumptions are described and all variables are well defined. Proofs are also well-written and it is easy for a reader to follow. Proofs seem to be sound. 

However, in this paper pseudo-code of the considered algorithm is not provided. This might lead to confusion. It can be helpful for readers to have pseudo-code for better understanding. 

Authors use the phrase "after K SGD". Does it mean that K SGD steps? This phrase is confusing. 

Assumptions.

The first assumption in this paper is Unbiased Gradient and Bounded Variance. 

Assumption 1 (Unbiased Gradient and Bounded Variance). Every client stochastic gradient $g_{i}(\boldsymbol{x} \mid B)$ of a model $\boldsymbol{x}$ evaluated on batch $B$ is an unbiased estimator of the local gradient.

 We thus have $\mathbb{E}_{B}\left[{\xi}_{i}(B)\right]=0$ and $0 \leq \mathbb{E}_{B}\left[\left\|{\xi}_{i}(B)\right\|^{2}\right] \leq \sigma^{2}$, with ${\xi}_{i}(B)=g_{i}({x} \mid B)-\nabla \mathcal{L}_{i}({x})$

In https://arxiv.org/pdf/2002.03329.pdf it was shown that this assumption is limited and the simple 1-D counterexample is provided in proposition 1. Instead of using the Bounded Variance assumption, it is better to use the Expected Smoothness assumption:

Assumption (Expected smoothness). The second moment of the stochastic gradient satisfies
$$
\mathbb{E}\left[\|g(x)\|^{2}\right] \leq 2 A\left(f(x)-f^{\mathrm{inf}}\right)+B \cdot\|\nabla f(x)\|^{2}+C
$$
for some $A, B, C \geq 0$ and all $x \in \mathbb{R}^{d}$ and function $f$ is bounded from below by an infimum $ f^{\text {inf }} \in \mathbb{R}$. 

Another questionable assumption is Assumption 3 (Bounded Dissimilarity ).
There exists constants $\beta^{2} \geq 1$ and $\kappa^{2} \geq 0$ such that for every combination of positive weights $\left\{w_{i}\right\}$ such that $\sum_{i=1}^{n} w_{i}=1$, we have $\sum_{i=1}^{n} w_{i}\left\|\nabla \mathcal{L}_{i}(x)\right\|^{2} \leq$ $\beta^{2}\|\nabla \mathcal{L}(x)\|^{2}+\kappa^{2} .$ If all the local loss functions are identical, then we have $\beta^{2}=1$ and $\kappa^{2}=0$.

This means that analysis does not cover arbitrary heterogeneous cases. In https://arxiv.org/pdf/1910.14425.pdf it was shown that this assumption is also limited. It is described in Remark 3. 

Theory. 

In this paper, there are two theorems. The first one is the decomposition theorem. This theorem provides several insights and it is an interesting result, which can lead to further improvement. However, in the statement, we have the phrase "after K SGD", which is not clear. However, FedAvg can be modeled not only by the local SGD method. There are many other approaches such as Federated Random Reshuffling (https://arxiv.org/abs/2102.06704, https://arxiv.org/pdf/2110.10342.pdf). It might be interesting to formulate similar theorems for other methods. 

The second theorem provides convergence guarantees for local SGD. However, there is no epsilon complexity and comparison with other results. It might be useful for readers to have a table with different bounds. In http://proceedings.mlr.press/v130/gorbunov21a/gorbunov21a.pdf a lot of options and analyses are compared in Table 2.

Additionally, bounds for strongly convex and general convex cases are also desirable. 

Experiments. 

In this section the comparison between Multinomial and Uniform Distribution. These plots are illustrative. However, it is also interesting to have a comparison with other methods used in Federated Learning. It is not clear why n \in {10, 20, 40, 80}  are used and why only m = n/2 is considered. 

Additionally, it might be interesting to apply analysis of client sampling to other methods for Federated Learning such as SCAFFOLD (https://arxiv.org/pdf/1910.06378.pdf), Federated Random Reshuffling (https://arxiv.org/pdf/2102.06704.pdf), Variance Reduced methods (http://proceedings.mlr.press/v130/gorbunov21a/gorbunov21a.pdf), but not only localSGD. 



summary_of_the_review: Overall, this paper introduces interesting ideas, but it needs significant revision. The assumptions are limited and analysis can be significantly generalized. In this paper, there are no theoretical and experimental comparisons with other methods. Moreover, only two distributions are compared, additional comparison with other distributions is needed.
review_title: null

Meta-review: Dear authors,

I have carefully read the reviews, rebuttals, and the subsequent discussion. Most reviews provide high quality feedback, and the reviewers' combined opinion is strongly oriented towards recommending rejection. I have to concur with this recommendation. While essentially all reviewers agreed that the paper is well written, they also raised several key concerns. I will reiterate (and further elaborate) on some of them here:

1) I do not agree with the authors' claim that there is a significant difference between client sampling in FL and data sampling in SGD in terms of the underlying mathematics; at least not in the present form. The mathematical formulation of both problems is the same. While in SGD it is possible to access local information and construct more powerful sampling strategies using this information, it is also possible to forgo using this information and propose simpler data-agnostic strategies. Such strategies have been studies in the SGD literature before. I recommend the literature on *arbitrary sampling* pioneered by Richtarik and Takac ("Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function", Mathematical Programming, 2014) in the context of randomized coordinate descent. The same sampling approach was later adopted for SGD. The paper by Csiba and Richtarik (Importance sampling for minibatches, JMLR 2018) suggested by one of the reviewers is relevant here as it adopts the arbitrary sampling approach to (variance reduced) SGD. Such an arbitrary sampling paradigm is more general than the unbiased sampling strategy you study here (indeed, arbitrary sampling includes also biased samplings). The work of Chen et al mentioned by a reviewer is also more relevant than you appreciate. This work also mentions a couple decomposition statements. They work with the arbitrary sampling framework in the FL setting - and this seems more general than your framework since it includes biased samplings as well. Note that they then proceed to compute the optimal sampling out of all samplings, while you do not attempt to theoretically capture what samplings are best. This prior works thus addresses a similar problem, and goes deeper in this aspect. Also, the parameters $v_i$ in their Lemma 1 are simply just statistics of the sampling - and are unrelated to the data. Also, Lipschitz smoothness constant of the aggregate loss over all local data samples is not hard to estimate, and is needed anyway to set the stepsize correctly. So, your comments about the unavailability of these quantities in the FL setting seem incorrect.

2) Theorem 1 is indeed just a simple calculation / observation rather than a result. I agree with the reviewer who said that the value of this simple observation, without a deeper study of its consequences, and an explanation of how the consequences lead to new results that are in some sense interesting, is quite limited. As mentioned by one reviewer, sophisticated methods are often non-monotonic: they do *not* attempt to greedily reduce some simple potential (e.g., distance to the minimizer) as such a strategy may be suboptimal from a total convergence point of view. This observation by the reviewer seems to have been misunderstood by the authors. This limits the impact of Theorem 1 as Theorem 1 assumes that one is interested in a greedy method.

3) The bounded variance and bounded dissimilarity assumption *are* strong. The suggestion by one of the reviewers to consider a work on more accurate ways of modeling stochastic gradients (Khaled et al) was appropriate. I suggest the authors read the paper to see detailed reasoning explaining why the types of assumptions you make in this paper are problematic. The fact that some other papers use such problematic assumptions, even if they are well known, is not evidence that these assumptions are not problematic. It is merely evidence that many papers share the same issue. I also have to oppose the authors' view that non-peer-reviewed work should not be brought up. In my view, this is a deeply problematic and unscientific attitude to research that is available online. Peer review does not imply correctness, and vice versa. 

4) Experimental comparison with any other methods is missing. Why do you not compare with the optimal sampling strategy of Chen et al, for example? Does your framework suggest a better strategy in some sense? If yes, show it. If no, then in what sense are your sampling strategies interesting? In any case, all have been considered in the arbitrary sampling framework before as far as I can see.

5) There are more issues with have been identified by the reviewers. I strongly recommend the authors to take all of them seriously in their revision.

In summary, this is a solid paper. However, it has some serious issues and for this reason I cannot recommend it for acceptance. Having said that, I thank the authors for their submission and wish them best of luck in future research with this project.

Area Chair
Decision: Reject