Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a submodel optimization technique in federated learning in the presence of diverse data feature distributions across clients. Heterogenity in features of local data leads to distinct update speed for individual feature-related parameters, degenerating convergence of the model. The paper claims that the global objective function of typical federated learning framework is ill-conditioned when each client updates and communicate only subset of the total model (submodel).
This paper handles the problem by compensating the amount of parameter updates based on the feature heat dispersion. It also provides formal analysis for the convergence of the proposed method. It demonstrates the effectiveness of the proposed method over baselines on three benchmarks; rating classification, text sentiment classification, click-through rate prediction.


strengths_and_weaknesses: 
### Strengths

- The submodel optimization setup where each client updates the subset parameters of the central server is realistic and would be the proper extension with clear motivation. In real-world applications edge devices are likely to have limited capacity in memory, computation, and communication bandwidth.

- Experimental results are quite compelling. Figure 3 presents that FedSubAvg converges fast and shows similar tendency with centralized training (CentralSGD)

### Weakness

- The assumption that server knows indexes for the feature-related parameters of all clients is unrealistic. 
Due to the assumption, the proposed algorithm is not compatible with deep models (e.g. DNN, MLP) with multiple non-linear layers.

- In the similar vein, The proposed method needs to calculate data feature dispersion, which can bring about privacy concerns.


questions: - Comparison with the typical FedAvg (participating clients update all parameters of server model then aggregate them) in terms of total communicated parameters would validate the efficiency of the proposed method. 


limitations: - As mentioned above, the proposed algorithm is incompatible with modern deep learning architectures (CNN, MLP), the more compatible approach should be proposed without using prior knowledge that the feature dispersion is known and feature-related parameters are predefined. 

- The writing is hard to follow, and some details (e.g. implementation details) were not explained well.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The manuscript considers a specific use case of federated learning in a recommender system or NLP scenario and proposes to scale the model update per coordinate through the ratio between the total number of clients and the number of clients who involve this model parameter coordinate. Some theoretical results are provided to motivate and justify the necessity of design choices.
strengths_and_weaknesses: # Strengths
* The considered scenario is interesting and important to the community. The proposed method is simple yet (intuitively) effective in alleviating the identified limitation.
* The entire manuscript is generally well-structured, and most claims are well-supported.
* Extensive numerical results are provided for some aspects.

# Weaknesses
1. The index set $S(i)$ determines the sub-model of $X S(i)r$. However, for the four considered datasets, the exact distribution of features (hot vs. cold features) is still unknown, and some specific treatments (line 211- line 212, line 226 - line 227) may require some justifications, such as "we label the samples with the ratings of 4 and 5 to be positive and label the rest to be negative". Will these treatments magnify the large imbalance phenomenon between hot and cold features?
2. Given the considered challenges and proposed coordinate-wise scaling solution, one strong competitor should be considered, i.e., using an adaptive optimizer on the server as in [1].
3. The client's index set must be sent to the server, and a clustering-based FL technique can utilize this information naturally. The reviewer is also interested in how cluster-based FL approaches perform, as these algorithms may have already addressed the issue of hot vs. cold features.

# Reference
1. Adaptive Federated Optimization

---

# Post rebuttal
The reviewer acknowledged the authors' feedback and checked other reviews. 

The response has addressed concerns #2 and (partially) #3. However, the reviewer still believes that the manuscript needs some revisions to polish its text (e.g., make it self-contained, well-structured, precise, etc).
questions: Check Weaknesses part.
limitations: Check Weaknesses part.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors consider a specific federated learning scenario where different data features ‘involve’ different clients. For some features, a large number of clients can be involved while other features might involve only limited clients. The authors show that in this case, the classical FedAvg can suffer from slow convergence. In the proposed new algorithm, the aggregations of parameter updates are weighted per parameter by the ratios of the local clients involved. The authors prove that by reweighting the parameter updates in this way, the condition numbers of the Hessian of the learning objectives become smaller than the original Hessian. In the experiments with four real-world datasets, the authors demonstrated that the proposed algorithm (FedSubAvg) offers faster convergence than existing alternatives.

strengths_and_weaknesses: Strengths:
Improving the convergence of federated learning is an important and active area of research. The authors contribute a new algorithm that can potentially improve the convergence of the federated averaging algorithm. The experiments were conducted on large-scale real-world datasets.

Limitations:
- The paper would need a thorough rewriting. For example, the example illustration of feature heat dispersion in recommender systems at L45-50 is difficult to comprehend. What does ‘less than 1% of the average’ mean? Please formally define ‘involvement‘. L122 ‘the number of clients who involve this model parameter’: How is this number determined in general?
- The proposed algorithm seems applicable only when ‘submodels‘ are well-defined, i.e., the individual clients do not have to update the full model parameters but instead, can download and update only the required small parts (submodel) of the complete model. On the other hand, typical local learning steps tend to require simultaneous updates of all model parameters, unless the model is linear. The authors should provide a detailed discussion as to when such submodels are well-defined and how the index set S(i) is determined in practice. Can this algorithm be applied to the standard MLPs?

Minor comments
- The proposed algorithm can be considered as diagonal preconditioning on stochastic gradient descent (SGD) (L167). The authors could discuss connections to existing SGD preconditioning methods, e.g., AdaGrad: AdaGrad preconditions the SGD update based on the magnitudes of individual parameter updates. Extending AdaGrad to the federated learning setting can be straightforward.
- Please enlarge the plots in figures 3 and 4.

questions: Please see Strengths And Weaknesses section.
limitations: The limitations and potential negative societal impact were not discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors point out the fact that (in the context of federated learning) client’s local data normally involve a small subspace of the full feature space. Especially in the case of models that contain large sparse embeddings, this would mean that each client downloads and updates only a small part of the full global model (I.e., a submodel). 

As some features are more popular than others (e.g., words in a vocabulary), some embedding will then be averaged by a larger fraction of clients than others. The authors then show that this discrepancy (called heat dispersion) might result in slower convergence of algorithms like FedAvg. 

They then propose a new method where each weight essentially has a different learning rate, based on how many clients participate in its update. They show both analytically and through an evaluation that this method improves the convergence speed. 



strengths_and_weaknesses: + The authors address an interesting problem on training FL models with sparse embeddings: the fact that not all of them are equally popular. 

+ The authors conducted a theoretical analysis of their model

+ They compared with 4 baselines, some of them designed to speed up convergence on non-iid data. 

+ The results show that their methodology is promising

- There are some assumptions in the evaluation (see below in questions for details)

- It is unclear how well this methodology would work with privacy-preserving mechanisms (e.g., local DP noise)


questions: Overall this is a great method to address sparse feature dispersion in FL. 

- Practically this algorithm works by providing a different averaging coefficient for each parameter, based on the "popularity" of each feature amongst the clients. As a result, the resulting overall (average) learning rate might be affected.  While this shows faster convergence on the empirical evaluation, it is unclear if this is due to using a default learning rate (and the same learning rate) across each method. A more fair experiment would be to make sure that a hyper-parameter search is conducted for each baseline and the proposed method. I am mentioning this because practically, by changing the averaging coefficient, FedAvg might be more tolerant to higher LR (thus improving convergence speed) than FedSubAvg before convergence is affected. It would be great if the authors revised their experiments and show that FedSubAvg is able to beat the other methods when each method is using hyperparams that are searched independently.

- The second question is wrt to the number of clients (K) vs other methods. The authors show that as the number of clients increase, FedSubAvg converges faster. As in many real-world FL deployed systems K = thousands of devices, it would be great to be able to also include the results from the baselines (or at least fedAvg) and possibly show for values > 100. Its unclear if the convergence of FedSubAvg is much better that the SOTA only for small K or if this algorithm would actually improve convergence in real-world scenarios. 

- The third question is about combining this method with privacy-preserving mechanisms. There were many approaches where secure embedding retrieval's were used, and local DP noise is added to the model to make sure that user privacy and regulations are respected. It would be great if the authors comment on the compatibility of their approach with such privacy-preserving approaches, especially as they have to be able to identify the exact features that the clients used to update the model. 
limitations: Please see above (questions)
review_title: null

Meta-review: metareview: This paper considers a particular FL scenario, where the model includes a large embedding layer as is typical in NLP and recommendation models. To make training feasible or more efficient, the FedSubAvg method is proposed. In particular, it deals with the setting where not all features are equally encountered in training data. This is leveraged to reduce communication and computation overhead, and also to improve optimization dynamics. The proposed approach comes with theoretical guarantees, and the paper also provides a thorough numerical evaluation demonstrating benefits over other approaches.

The reviewers raised concerns about the relevance and potential narrowness of the setup, assumptions, and whether the proposed FedSubAvg approach would be comparable with privacy-enhancing technologies like secure aggregation and differential privacy. It is clear that the setup considered is indeed relevant given the prevalence of models with large embedding layers in NLP and recommendation models, and the useful of such models in several applications. Given this, it isn't necessary for the authors to demonstrate any relevance to training standard MLPs since that isn't the focus and no claims are made in the paper about such architectures. The authors responses also were convincing that the approach can be made compatible with DP and secure aggregation in a reasonable way.

I'm happy to recommend that this paper be accepted. When preparing the camera ready, to make the paper accessible to a broader audience, it would be helpful to include (in the intro, or early in the paper) additional material and references to motivate the relevance of models with large embedding layers, in addition to the key revisions already made in response to the initial reviews.
confidence: Certain
Decision: Accept