Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: ***Strong	

Personalization is a hardcore problem in FL. The authors target an important problem.

The theory analysis seems correct, but the bound seems not tight enough.

***Weakness

Recently, there are many personalized methods proposed for FL. In the I.I.D. setting, local SGD training (FedAvg) can obtain similar accuracy as centralized training with a theory guarantee.  But in the non-I.I.D. setting, I am curious to know what’s the ultimate goal of optimization. Can the proposed personalized methods obtain accuracy comparable to centralized training? If we do not compare with the centralized accuracy, how can we know the optimized personalized model can obtain sufficient accuracy for practical applications.

The experimental results are weak. The authors only provide results on the LR model for toy datasets (LibSVM). Without non-convex experiments, it is hard to believe the proposed method works in practice given that DNN-based models dominate nearly all ML tasks.

The code style and readability are poor, which discourages the popularity of the proposed method.

Although the authors mentioned some contributions of the proposed method, I still cannot get what’s the advantages of the new formulation over conventional Federated optimization? What is its limitation? What’s the cost to use this method? When should we choose this algorithm in practice? In which degree of non-IIDness? Playing with optimization analysis tricks won’t solve the personalized challenge of federated learning in practice.

review_title: Authors propose a model personalization method for federated learning with a new optimization formulation which provides an explicit trade-off between the global and local models. In addition, the authors develop several efficient variants of SGD for solving the new formulation and prove communication complexity guarantees.

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary of the paper: The paper proposes a new formulation for the federated learning problem, in which each agent has its local model, and a penalty term is added to the objective function to control the deviation of these local models from their average. Next, the authors develop a randomized algorithm to tackle this problem and characterize its convergence under several assumptions, such as smoothness and strong convexity. They also discuss variants of their algorithm, which uses variance reduction techniques or considers users' partial participation.


The paper is well-written, and the goals, problem formulation, and contributions are all explained in detail. However, the reviewer has a number of concerns, which are listed below:



The first concern is regarding the novelty of the formulation or analysis. The idea of this paper's formulation, giving a copy to each agent and adding a regularizer to keep the copies close, has been discussed in the distributed literature, for instance, in ADMM. Moreover, it is not clear which part of the analysis is novel or challenging. It seems that the authors use an unbiased estimator to solve an optimization problem with a smooth and strongly convex objective function. This setting has been studied extensively in the literature, including applying variance reduction techniques.



Second, the regularizer parameter $\lambda$ seems to be at the heart of this framework. With $\lambda=\infty$, the problem reduces to the classic federated learning setting, and when $\lambda=0$, the formulation boils down to the case that each agent solves its own problem. In particular, for the latter, the authors claim that "such purely local models are rarely useful." However, this claim's reasoning is not clear; for instance, from a theoretical point of view, results such as Theorem 3.1 suggest that having $\lambda=0$ will lead to the minimum loss $f$. In other words, it is not clear how we should compare the different trained models from setting different values for $\lambda$, and which range of $\lambda$ leads to a good model with respect to that measure.



Third, as stated in the introduction, several methods have been recently proposed to address the heterogeneous case or achieve personalization in the federated learning problem. I wonder why the authors have only compared their methods against each other in experiments and have not included those methods for comparison.

review_title: Well-written paper; Concerns regarding novelty of the formulation and analysis, the role of penalty parameter, and comparison with related works.

final_score: rating: 4: Ok but not good enough - rejection
review_content: ## Summary

This paper proposed a new formulation of federated learning, which balances between traditional global model and purely local models. The authors discuss the advantages of the new formulation and propose a new algorithm L2GD to solve the problem. They theoretically analyzed the communication complexity of L2GD under stronly-convex settings and propose several algorithmic variants.

## Pros
1. The authors developed a set of algorithms based on L2GD and provided theoretical analysis. The efforts are appreciated.


## Cons

Unfortunately, most contributions of this paper doesn't make sense to me. I have concerns regarding novelty and correctness of the statements made by this paper. Detailed comments are listed as follows.

**New formulation**
1. In section 2, the authors claim that "we prove that the optimal local models converge to the traditional global model characterized by (1) at the rate $O(1/\lambda)$". However, I didn't find any discussions or proof around this statement in following sections. From my understanding, there should be some equations showing how $x(\lambda)-x(\infty)$ or $f(x(\lambda))-f(x(\infty))$ changes over $\lambda$. But I didn't find any.
2. In experiments, the authors didn't compare the proposed formulation with the original formulation. How much benefits one can obtain from the new formulation is unclear, making this paper to be incomplete.
3. The formulation is not new. A nearly same formulation can be found in [1]. The authors didn't notice this paper. Since [1] also proposed an algorithm EASGD to solve the new formulation, the authors are supposed to compare L2GD with the algorithm in [1].

**New algorithm: Loopless LGD**
1. The algorithm is also not new. An extremely similar algorithm has appeared in [2]. By some re-parameterization, I believe they are equivalent to each other. The authors missed this reference. They should justify the differences and compare the results.
2. It is unclear why L2GD uses random local steps instead of a fixed one. Or what are the benefits of the randomized one?

**Convergence theory**
1. The conclusions of convergence analysis are questionable. In particular, when obtaining the convergence rate, it seems that the authors completely ignore the second term in (9). In general, people use $f(x)-f(x_*)<\epsilon$ or $\|x-x_* \| < \epsilon$ to define the $\epsilon$-neighborhood of the optimum. However, in this paper, the authors use $\|x-x_* \| < \epsilon \|x_0 - x_* \| + c$ to define the neighborhood and just ignore the second term when deriving the rate. Under this definition, they draw the conclusion that L2GD can improve the communication complexity of GD. This can be misleading and questionable. In GD, we don't have the second term in (9) at all.
2. Similarly, when obtaining the best value of $p$, the authors only optimize the first term. However, the second term in (9) also depend on $p$. The authors seem to ignore it again.

**New insights about the role of local steps**
1. The authors state that "the role of local steps in gradient type methods is not to reduce communication complexity, as is generally believed. Indeed, there is no theoretical result supporting this claim in the key heterogeneous data regime." This statement is not true. It has been shown in literature (eg, [3]) that local SGD can achieve the same rate $1/\sqrt{n K}$ as synchronous SGD but only uses $O(n^{3/4} T^{3/4})$ communication rounds, while synchronous SGD uses $T$ rounds.
2. "The more local steps are taken, the more we bias the method towards the purely local models." I feel we cannot draw this conclusion from this paper's analysis. In particular, in this paper, the choice of local steps is controlled by the parameter $\lambda$ (expected local steps = $1+L/\lambda$). When we set a small $\lambda$, we get two consequences: (1) the formulation will emphasize more on $f(x)$, and hence, the solution is biased towards purely local models. (2) the "optimal" local steps derived in this paper becomes larger. Obviously, these two consequences are parallel to each other. We cannot say the second point is the reason of the first point. Instead of setting the expected local steps to be $1+L/\lambda$, one can also use other values which won't influence the final solution.

**Experiments**
The experimental results can only show the importance of variance reduction, which seems to be a minor contribution of the paper. Most theoretical claims are not validated empirically.

## Post-rebuttal
Thanks the authors for the clarifications! I appreciate it. However, some of my concerns are not addressed. 
- The main concern I have is about the new insight on local update methods. Basically, the author obtain the insights based on a newly proposed algorithm (L2GD, let's call this algorithm B) and a new problem formulation (let's call this formulation B). However, they want to apply the insight from algorithm B and formulation B to algorithm A (original local update methods) and formulation A (original FL formulation). It is obvious that one cannot draw this conclusion because both the algorithm and the formulation are different.
- Second, as I stated in the original review, I don't think one can obtain the insights from the analyses in this paper. The author didn't directly answer my question and just said "they didn't expect people to interpret it in this way". But it is still unclear how to correctly understand their insights.

Based on the above two points, I strongly feel that their main insights about the effects of local updates should be further and carefully examined. The current version could be misleading. Besides, I also have the following minor concerns:

- The authors claim that [Yu et al. ICML 2019] didn't consider the heterogeneous setting. This is not true. Although [Yu et al. ICML2019] assumes that the gradient dissimilarity is uniformly bounded (which is widely used in literature), their setting is still non-iid setting. It's unfair to say that they only study the IID data setting. So the second motivation of this paper does not make sense to me. The authors oversell their contribution. More precisely, their contribution is not the first proof under data heterogeneous setting but should be the new proof without data similarity assumption.
- "non-local cousins" is unclear and hasn't been properly defined in the paper. For local SGD with mini-batch size ,  local steps and  clients, there are two non-local cousins: (a) SGD with mini-batch size ; and (b) SGD with mini-batch size . It seems that the authors misused these two algorithms. In the response, they agree that [Yu et al. ICML 2019] proves "with data dissimilarity assumption, local SGD can improve the communication complexity of classical SGD". Here, classical SGD refers to algorithm (a). In the updated paper, they cite two papers from Woodworth et al. to support their claim. However, the non-local methods in Woodworth et al. is algorithm (b). The authors should formally define which non-local algorithm they want to compare with.
- In the paper, the authors claim that they prove for the first time local methods can improve the communication complexity of the non-local cousins. However, this statement is overselling. The more precise version is that they prove that the variance-reduced version of local methods can improve the communication complexity of the vanilla non-local version algorithms.
- It seems that the authors want to claim a lot of contributions in this single paper and they didn't organize these contributions well. Hence, it causes difficulties for readers to understand their true novelty. I recommend the authors to rewrite the paper and carefully consider the paper structure. For example, if I understand correctly, the main contribution of this paper should be the insights on local updates. However, the authors didn't show any experiments on this insight in the main paper (they put them in the appendix). Instead, they just validate the effect of variance reduction in the main paper, which is just a minor point. Also, in the introduction, there is a long paragraph to introduce L2GD as one of the main contributions. However, as discussed in the responses, L2GD is not a new algorithm. The authors don't need to give it so much emphasize or should not claim it as one contribution.
- Also, in [1] EASGD does use multiple local steps. The authors should compare L2GD with EASGD, as they both are designed to minimize the new formulation.

## References

[1] Zhang et al. Deep learning with elastic averaging SGD. NeurIPS 2015.

[2] Wang et al. Overlap Local-SGD: An algorithmic approach to hide communication delay in distributed SGD. ICASSP 2020.

[3] Yu et al. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. ICML 2019.




review_title: Review #2

final_score: rating: 6: Marginally above acceptance threshold
review_content: Interesting insights into federated learning, possibly limited by the focus on strong convexity

This paper considers distributed training problems arising in the context of federated learning. It proposes a novel framing of the problem as a compromise between fitting a model locally to the data available at a device, and fitting a model globally to the data from all devices. This leads to the so-called loopless local gradient descent (L2GD) method, which is loosely related to the popular FedAvg/LocalSGD method, and also loosely related to a randomized version of the well-studied ADMM for consensus optimization problems. 

The paper provides theoretical convergence guarantees for L2GD and related variance-reduced versions L2GD+ and L2GD++. As is pointed out in footnote 1, the ideas underlying the L2GD and its analysis have been previously explored in the literature. It would be worth clarifying in the paper (in footnote 1 or elsewhere) what aspects of L2GD and its analysis which are novel and not completely subsumed by the previous works Liu et al. (2017) or Wang et al. (2018). The last sentence of footnote 1 is somewhat in this direction, but is not very precise.

I generally think the perspective proposed in this paper, along with the L2GD method, are novel and interesting, and I expect they will be useful to researchers working on federated learning. The main limitation of the work, in my view, is the limited fit and interest to the broader ICLR audience. For example, the CFP emphasizes the importance of non-convex optimization, and deep learning methods and architectures for representation learning. On the other hand, this paper focuses on convex models, both for the analysis (smooth and strongly convex) and in the experiments (l2-regularized logistic regression). The analysis techniques do not appear to make use of strong global structure (beyond the definition of strong convexity). Is there reason to believe it will not be possible to provide local convergence guarantees for L2GD under more relaxed assumptions (in particular, without assuming convexity)?

A few other minor points:
* Regarding the second motivating point, see also the recent work of Woodworth et al. (arxiv:2006.04735 and arxiv:2002.07839).
* Is there any intuition why, in Fig 1, when $\lambda$ approaches $10^{1}$, the blue curve begins to decrease and orange curve begins to increase? (I.e., why the non-monotonic behaviour?)
* Minor nit.: Alg 1 seems to violate the important notion in FL that devices never reveal their private information (e.g., their local decision variables or gradients) directly to the centralized master. Rather than saying that (8) is implemented at the master, would it make more sense for each device to receive $\bar{x}^k$ from the Master and implement (8) locally? (The averaged model can be computed in a secure way using DP and secure aggregation, much the same as it is in current FL implementations.)
review_title: Interesting insights into federated learning, possibly limited by the focus on strong convexity

Meta-review: The paper studies an elegant formulation of personalized federated learning, which balances between a global model and locally trained models. It then analyzes algorithm variants inspired by local update SGD in this setting. The problem formulation using the explicit trade-off between model differences and global objective was received positively, as mentioned by R1 and R2. After a productive discussion including the authors and reviewers, unfortunately consensus remained that the paper remains below the bar in the current form. The contributions are not presented clearly enough in context, the set of competing algorithms (including e.g. EA-SGD, ADMM, SVRG/Scaffold for the heterogeneous setting, and others) needs to be clarified in particular for the modified formulation compared to traditional FL, since objectives are different. Some smaller concerns also remained on the applicability to more general non-convex settings in practice. We hope the feedback helps to strengthen the paper for a future occasion.
Decision: Reject