Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents an efficient federated learning method which leverages the empirical observation that the gradients used in model updates are usually in a low-rank subspace. Based on this observation, a "look-back gradient multiplier" (LBGM) method is proposed that only updates a scalar look-back coefficient (LBC) as long as the angular difference between the stored gradient and the latest gradient is within a given threshold. A theoretical analysis of this method is given in the paper and the performance is also verified in various experiments.
main_review: **Novelty:** The idea of model updates in a low-rank subspace is not new. In fact, it has been mentioned in one of the pioneering papers on federated learning:
- Konecny et al., Federated learning: Strategies for improving communication efficiency, 2016 (Section 2)

The core idea of low-rank updates in this paper is the same as the low-rank structured update in the above paper by Konecny et al. While the convergence analysis in this paper may be a new result, the proof technique is relatively standard and is similar to other works on delayed/compressed SGD. In general, it is not surprising to achieve a convergence result comparable to existing algorithms under the condition of $\Delta^2 \\leq \\eta$ where $\\eta$ is inversely proportional to $1/\\sqrt{T}$ in Corollary 1. Furthermore, I feel that the current Algorithm 1 may be too specific in the sense that it only allows sending a scalar LBC that is related to the angular difference. The algorithm would be more flexible if an arbitrary (but given) number of scalars is allowed to be transmitted, where the number of scalars depends on the dimension of the constrained subspace of updates.

It is also worth mentioning that similar observations of low-rank gradient subspaces have been made and leveraged in continual learning literature:
- Chaudhry et al., Continual Learning in Low-rank Orthogonal Subspaces, NeurIPS 2020.
- Saha et al., Gradient Projection Memory for Continual Learning, ICLR 2021.

**Practical feasibility:** It is difficult for the proposed algorithm to work in large-scale federated learning systems. The algorithm needs to store copies of look-back gradients (LBGs) for all the clients at the server, which would consume a huge amount of storage in realistic on-device federated learning systems with over millions of clients. Furthermore, in such large-scale systems, it is only feasible for only a small percentage of clients to participate in each federated learning round, i.e., random client sampling needs to be performed. This paper does not seem to consider client sampling/selection at all, not in the algorithm description, analysis, nor in the experiments.

**Experiments:** It is not clear how the hyperparameters were found in the experiments, such as the threshold for LBGM and the value of K for top-K. This is important since the performance of each method could largely depend on the choice of these critical hyperparameters, so the hyperparameters should be found methodologically (e.g., using grid search) instead of chosen arbitrarily. The comparison is only fair if the hyperparameters for each method has been optimized for the method itself. In addition, it is a bit difficult to align the communication savings with the accuracy curves. It would help if figures showing accuracy vs. number of bytes transmitted could be added.

**Minor:** 
- It seems that the spacing has been squeezed quite a lot to fit the paper into 9 pages. This should be avoided. For example, some detailed discussion on related work may be moved to the beginning of the appendix.
- In the related work section, Gradient Compression paragraph, there is a sentence saying "These works were originally proposed for inter-GPU communication speedups and not FL." This is incorrect. There has been many papers that discuss gradient compression in the context of federated learning. For example:
  - Haddadpour et al., Federated Learning with Compression: Unified Analysis and Sharp Guarantees, AISTATS 2021.
  - Albasyoni et al., Optimal Gradient Compression for Distributed and Federated Learning, 2020.

summary_of_the_review: While communication efficiency is an important aspect in federated learning, this paper appears to have limited novelty and also some issues regarding practical feasibility and experiments.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed two hypothesis: (1) the space spanned by gradients generated during training is low-rank; and (2) the principle components can be approximated by the gradients generated during training. The authors first validated these two hypotheses on several datasets. Then, based on these, they proposed a new algorithm called LBGM to reduce the communication costs in federated learning. In the algorithm, the clients local gradients will be treated as the principle components (if there are K clients, then we have K principle components). Then, during training, each clients only needs send a scalar, which represents the coefficient of the corresponding components, to the server. Hence, the communication costs in FL can be significantly reduced.
main_review: In general, I think the proposed algorithm is quite novel and interesting. It explores a new research direction to reduce the communication in FL. The theoretical analysis is also a nice addition to the paper. It provides many useful insights about the proposed algorithm.

In terms of weakness, I mainly have two concerns:
1. In experiments, it seems that in most cases, using LBGM will degrade the performance a lot. For example, in figure 5, on CIFAR-10, the accuracy nearly drops 5-10%. Although the communication is significantly reduced, the performance degradation may prevent people using this algorithm.
2. The algorithm is more suitable for classical distributed learning rather than federated learning. I encourage the authors to change the title and related parts in the paper. The reason is that in FL, at each round, only a few (maybe around 1-10%) clients will participate into training. That means, one client can be inactive for multiple rounds. As a result, the principle component on this client will likely be stale when it participate training again. So the client needs to transmit full gradient again. In this case, the benefits of using LGBM may diminish..  
summary_of_the_review: This paper proposed a novel idea to reduce communication in FL. However, it seems non-trivial to make this algorithm to work with partial client participation. Without this extension, I feel the current algorithm is more suitable for classical distributed training than FL.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper hypothesizes that,  
**(H1)** the subspace $S$ spanned by the stochastic gradients while training through SGD is low rank, and  
**(H2)** $S$ is well approximated by a subset of the actual stochastic gradients. 

It provides empirical evidence to support these claims by calculating,   
(i) the number of principal components that almost explain the entire variance of the stochastic gradients over time, and  
(ii) the alignment between the principal components of $S$ and the stochastic gradients, as well as the consecutive stochastic gradients, across different models and data sets. 

With these observations, the paper aims to reduce the complexity of the communicated bits between the devices in data-parallel distributed training. Specifically, it proceeds by first estimating the principal components of $S$ through consecutive stochastic gradients. These vectors are then stored at the server as well as each worker. At each communication round the device then only needs to share the projection coefficients for these principal vectors, until the set of the principal vectors needs to be updated and broadcasted to all the machines. 

This technique is empirically shown to reduce the communicated bits while almost retaining the performance on certain data sets. A convergence rate is also provided for this algorithm under assumptions that highlight the trade-off between the frequency of updating the principal vectors and the convergence rate to a first-order stationary point.   
main_review: ## Important existing work

I'd prelude everything by first mentioning **[this paper](https://arxiv.org/pdf/2103.11154.pdf)** from earlier this year, which is closely related to the paper but hasn't been cited. It approximates the subspace $S$ using only the (first-order) information from the optimization trajectory and then uses it to build a quasi-newton method. In light of this, it is not true that the paper is the first work that studies, 
>the effect of overparameterization on optimization of NN via the rank-characteristics of the first order optimization (gradient) landscape.
 
Furthermore, an **[older paper](https://arxiv.org/pdf/1812.04754.pdf)** (which is cited) has already made the case that the stochastic gradients lie in a tiny sub-space, which is **(H1)** in this paper. I don't understand why this is underplayed while discussing this paper in the related works section, where this paper is clubbed with other papers that study the hessian?

Having said that, I am a bit apprehensive about both **(H1)** and **(H2)** (more below). But if we believe these hypotheses, it is indeed novel to use them in the context of federated learning. I'd encourage the authors to revise their writing and their discussion of novelty in the light of these papers. 

## Results on other data-sets

It is commendable that the authors do experiments with many different data sets and architectures and include them in the appendix. However, I am not convinced that the two hypotheses **(H1)** and **(H2)** are well corroborated in all the experiments. For instance, it is not clear if **(H1)** holds true in figures 11 and 13. Why were these experiments not run long enough to actually let the PCA components stabilize and the curve flatten out? Similarly in figures 18, 19, 23, 26, 27, 31, i.e., experiments with bigger models it is not clear if either hypothesis is true, and the figures look uninformative when compared to figure 2 which is presented in the main paper. Similarly, the consecutive gradient alignment curves in figures 52, 53 look uninformative. 

I am not saying that this phenomenon can be refuted entirely, but it seems that it is at least not robust to the choice of the model and dataset. And this has not been discussed sufficiently in the paper. 

Finally, why were figures 5-8 not presented for instance for U-Net for Pascal-VOC? Were the improvements worse? If they were it is important to include those for a fair presentation of the work. In fact, for this technique to be relevant to federated learning, it is important to know how it scales to bigger models and datasets. I am specifically mentioning this instance, based on the gradient alignment curves and model size.  

### Learning rate scheduling
What is happening at the 25th iteration in figure 3 for CelebA? Is there a learning rate decay there? These kinds of shifts in principal components happen throughout all the curves in the appendix as well. Looking at the provided code it is not clear what learning rate schedules were used for respective figures, and it would be good to highlight this in the paper. More importantly, does the schedule impact the principal components? It seems to be the case looking at the curves. It would be good to investigate that.

## Convergence Rate

I am mostly happy with the convergence analysis and the following discussion. The analysis is not particularly novel, but it is good to see how $\Delta$ appears in the convergence guarantee.  

***

## Minor comments

>Can we observe the effect of overparameterization in gradient descent-based optimization of NNs    

1) This comes off as an ill-posed question, given the plethora of empirical and theoretical work that has come up in this area.
    
>We further reveal that LBGM can be extended to distributed training

2) The distinction that the authors make between FL and distributed training is slightly confusing (even later in the paper). Latter subsumes the former, and it seems that the authors want to demarcate between homogeneous v/s heterogeneous data-distribution settings or cross-silo v/s cross-device FL. This is especially confusing when the authors choose to demarcate between the baselines for **P2** and **P3**. I think the point there is that just communicating gradient signs can be detrimental for the heterogeneous setting?
  
3) I don't like the term *principal gradients* for principal components of $S$, as they are not really *gradients*. Moreover, I couldn't find anywhere a mathematical description of how these components are calculated, perhaps using SVD of the concatenation of all the gradients? The pseudocode in the appendix just uses a black-box function. It would be useful to include this in the appendix and specify how different levels of variance are specified.  

>SGD is resilient to noisy updates and often benefits from them in terms of generalization error

4) This is a vague statement, first of all, what does it mean for an optimization algorithm to be resilient to noisy updates? Do you mean that the analysis of SGD can be done for any unbiased stochastic gradients, with bounded variance? That is true, but it is unclear (at least apriori) if the noise introduced by the LBGM procedure is like that. This is a slippery slope argument to make. Or do you mean that while training with SGD, additive noise doesn't hurt the performance? If you mean the latter, I am not convinced that there is conclusive evidence to show this, across a range of models, data sets, and noise levels. So this is an underqualified statement as well. Please re-write this sentence or avoid it. 

5) Lemma 1 seems trivial to me. You are basically re-deriving what it means to project onto a vector. Is it really worth putting this into a lemma and writing a proof? or am I missing something here? 

> S2: FCN on FMNIST and FMNIST

6) Typo 
 
>The fact that rank deficiency of the gradient-space is not a consequence of model complexity or model performance suggests that the gradient-space of state-of-the-art large-scale ML models could be represented using a few principal gradient directions.

7) I was hoping that the authors will further investigate what causes this rank deficiency. That would have been a significant contribution by itself. **[This paper](https://arxiv.org/pdf/2103.11154.pdf)** conjectured that it had something to do with the number of classes in the data-set. Could the authors corroborate or refute that claim?

8) In many experiments (such as figure 2) the stochastic gradients were almost determined by a single PCA gradient. Did the authors investigate what caused this? How is the learning rate being decayed in these figures?

9) Did the authors experiment with layer-wise PCA gradients? Perhaps even a proof of concept experiment could be done by using actual principal components of $S$?     
summary_of_the_review: I think the claims of novelty in the first half of the paper are slightly inflated. The application to federated learning is definitely novel though and should become the focus of the paper. This can be done by improving the discussion of the related work, providing fair and well-rounded evidence for the low-rank hypotheses, and extending the experiments for federated learning to the biggest data-set and model possible. I am open to increasing my score if my concerns are addressed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the gradient subspace and finds it low-rank propery.
This observation motivates them to propose a new algorithm that reuses similar past gradients to save communication.
They provide a theoretical analysis (with some mistakes) and conduct experiments to validate their method.
main_review: From my perspective, the main novelty is two folds.
One is the investigation of the gradient subspace, while the other is the proposed method which reuses similar past gradients to save communication.
The proof technique for the theorem is standard. However, it seems to have some mistakes, which though can be fixed with additional efforts and some quantities redefined.
The paper provides abundant experiments which I appreciate a lot.
Experiments illustrate communication efficiency and the plug-and-play property of their method.
Most of the writing is clear but some parts are hard to understand.

I have the following concerns:
1. The readability for Figure 1-3 should be improved. Without the help of Algorithm 2, I can’t figure out the meaning of each coordinate axis. 
2. In the first paragraph of Section 3, it is better to add $\theta^{(t, 0)}_k$ is initialized as $\theta_k$ explicitly. 
3. The description of LBGM Algorithm is hard to understand at the first glance. Some undefined terms are used, like look-back coefficients. I have to look up their meanings and exact mathematical forms in Lemma 1 and Algorithm 1, which increases the reading burden. I suggest the author could give a specific definition of frequently used terminology at the beginning. Besides, to better deliver the main idea of Algorithm 1, certain properties could be provided. For example, each device uploads just one LBG to the server, and the server tracks and maintains all updated LBGs.
4. Lemma 1 seems to have a mistake. Since both $\rho_k^{(t), \ell}$ and $\cos(\alpha_k^{(t), \ell})$ are scalers, the equality (L1) implies that the vectors $g_k^{\ell}$ and $g_k^{(t)}$ have the same direction (and thus are parallel), which is contradictory to (a) in Figure 4, where $g_k^{\ell}$ and $g_k^{(t)}$ has an angle. 
5. The equality of the projections of a vector into two different vectors, though being wrong, is frequently used in the proof of Theorem 1. As a result, (14) and the first line of $Z_5$ are incorrect. However, these mistakes can be avoided. Letting $\tilde{d}_k^{(t)} = d_k^{(t)} \cos(\alpha_k^{(t), \ell})$ and abandon $\tilde{d}_k^{(t)} =  \rho_k^{(t), \ell}d_k^{\ell}$ solve the first problem. To bound $Z_5$, we can directly use the fact: $(1-\cos \theta)^2 \le |\sin \theta|$ for all $- \pi/2 \le \theta \le \pi/2$. In the way, though Theorem 1 can be rescued to be correct, the current proof is definitely not ready for publication.
6. It is unclear the frequency of LBC being transmitted. Note that communication is only saved when we communicate LBC rather than the whole vector. In the paper, related results include Figure 5 and 6 which investigates the variation of the total number of parameters shared. Besides, to compute the LBPs, we should first compute $\nabla F(\theta_k^{(t)})$ which incurs additional communication. I don’t know whether Figure 5 and 6 have taken this factor into account or not.

Some discussion:
1. I think there are more choices to set LBGs. In the paper, the LBG are just one of the history gradient. Why not define LBG as a moving average? This means we update the new LBG as the average of all LBGs. When the algorithm starts to converges, the average could be more stable.
2. The paper spends a lot of time studying the low-rank property of subsequent gradients. Why not let each device maintain more than one LBGs? In this way, each device has an LBG set, which is updated when the space it spans can’t explain the variance of the new coming LBG. Maybe we need PCA to determine whether the LBG set meets the requirement. With more LBGs, I guess the empirical performance would be improved further. After all, current experiments show with LBGM the test accuracy might slightly decay.
summary_of_the_review: I appreciate the empirical investigation of low-rank gradient space and the idea behind the proposed method.
However, the current version of this paper is not proper for publication due to the mentioned concerns.
review_title: null

Meta-review: The paper shows that most variance of gradients used in FL and distributed learning in general is in very low rank subspaces, an observation also made in Konecny et al 2016 and some other related works in deep learning, though sometimes for a different purpose.
The paper then proposes lightweight updates combining a fresh gradient with old updates. Experiments and a theoretical convergence guarantee complement the results, which are mostly convincing. 

The experiments compare against ATOMO but strangely not against the more common PowerSGD, which would also work with partial client participation.

Overall, reviewers all agreed that the paper is interesting, well-motivated and deserves acceptance.
We hope the authors will incorporate the open points as mentioned by the reviewers.
Decision: Accept (Poster)