Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers the federated learning problem, especially for the case that there are many classes and each client has a small set of classes. When there are many classes, the neural network has to have many parameters to define the last layer classifier, which makes a huge communication cost. To resolve this issue, the author proposes FedSS, by which each FL client samples a set of classes and defines the loss function only with the sampled classes.  Since unsampled classes are not involved in the client's training process, the client sends only the parameters corresponding to the sampled classes. The authors empirically show the proposed approach can reduce the communication cost without sacrificing performance. 

main_review: Pros,

This paper is well-written and easy to follow.

The idea is simple.

The proposed method can reduce the communication cost

Cons,

The most significant weak point is that the proposed algorithm is not free from the privacy issue. Since every sampled set of each client has to include the classes that the client has, the central server can infer the classes the client has. In many federated learning applications, it is strictly prohibited that the server can reveal any information of clients.

It would be much better to provide how much the algorithm can save the communication cost. Since the main contribution of this work is not improved performance but reduced communication cost, the authors should provide more discussions about the communication cost.

The authors should discuss with other communication efficient algorithms since the main contribution of this work is saving the communication cost. For instance, there are many works for efficient distributed learning, e.g., TernGrad. 

Experiments should include more results considering other data sets and neural net architectures. Since this is not a theory paper, the proposed algorithm can be justified only by experiments. Therefore, ICLR papers are expected to have comprehensive experimental results. 

summary_of_the_review: This paper should be very careful to define a class subsampling for federated learning applications since it can leak clients' private information. Also, this paper requires more comprehensive experiments with considering other communication-efficient algorithms.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors proposed federated sampled softmax (FedSS) for resource-efficient federated image representation learning. When the number of classes is large, the final classification layer could take up a large part of the communication cost during training. FedSS allows subsampling the weights of negative classes to reduce data transfer and leads to similar accuracy compared to the full softmax.
main_review: Pros:
1. The paper is generally well written and easy to follow.
2. FedSS provides a potential solution to reduce the communication cost of the classification layer in federated learning settings.

Cons:
1. Firstly, the proposed method only has a significant saving when the number of classes is huge (Figure 8, >>1000). However, the datasets used in this paper mostly have a limited number of classes (SOP and Landmarks). In this case, the saving is very small (smaller than 15%). On real tasks with many classes (ImageNet-21k), the proposed method failed to match the accuracy compared to the full Softmax (Table 3). And the increase of $|S_k|$ does not seem to close the gap. Therefore, it is questionable if the proposed algorithm has real-life benefits.
2. The proposed method seems to be a direct application of the sampled Softmax algorithm under a federated learning setting, which restricts the novelty.
3. The proposed method degrades the accuracy (even in Table 1, the results do not really match). How it behaves compared to just using a smaller model with the overall same model size? Since the communication savings on SOP and Landmarks are small, the smaller model baseline should also have roughly the same performance.
summary_of_the_review: The paper is generally well written. However, the experimental results and technical novelty are less convincing. I would lean towards objection for now.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper investigates the problem of training a good computer vision model in the cross-device federated setting, focusing on classification. For deep networks, when the number of classes gets large ($\geq 10^3$), the number of parameters is dominated by the classification layers, hence scaling proportionally to the number of classes in the network. The authors propose to alleviate the resulting computation and communication burden by using sub-networks for each client, with a shared feature extractor but with only a smaller number of classes, re-using the sampled softmax proposed by Bengio & Senécal 2008. The resulting algorithm, Federated Sampled Softmax (fedSS), is benchmarked on image classification and image retrieval tasks along with baselines and variants. Experimental results demonstrate the validity of the approach.
main_review: 
# Significance and impact
- The problem studied by the authors has not received a lot of attention, save for the previous work cited by the authors, which was restricted to a narrower problem (1 class per client).
- This paper brings a good practical solution for this problem, building on previous work, which makes it quite significant.

# Writing and clarity

- The paper is very well written and easy to follow, with helpful figures.
- It could be helpful to provide in appendix a short derivation of the validity of the sampled softmax approximation.

# Quality

The experiments are well conducted, with adapted baselines, and support well the claims of the paper. I have a few questions and suggestions:
- in table 2, the proposed method reaches a better performance than fullSoftmax. How do the authors explain this result?
- The paper mainly focuses on the choice of the classes to include in the sampled softmax, and bring a very good experimental support for the method. It would also have been interesting to study:
  - different NN architectures (only mobilenet v3 is used)
  - what is the effect of the proposed method when the number of local epochs increases? This number remains fixed to 1, leading to a very large number of rounds (2k or 5k);
  - What is the effect of label class heterogeneity on the method? e.g. for the SOP dataset one could study splits with varying heterogeneity.
summary_of_the_review: This paper introduces a novel and simple approach to a practical cross-device problem. The experiments are well conducted and support the claims of the paper. I think this paper should be accepted.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper works on "supervised" representation learning in a federated learning setting. The main goal is to save the communication cost: by preventing sending the entire fully-connected layer between the server and the clients if the clients only have data from parts of the classes. The authors proposed federated sampled softmax, which is to compute the softmax only over the "positive" classes of which a client has data and a small portion of the other negative classes. The authors empirically show that, by doing so, even with a very small set of the negative classes (so small communication cost), the resulting feature network can achieve comparable performance to learning with the conventional softmax. 
main_review: ===== Strength ======
1. The paper points out an interesting fact and problem: most of the parameters in a neural net are in the last fully connected (FC) layer, while in a large-number-of-class and non-IID setting, each client may only have data from a small portion of classes. The authors thus accordingly proposed the federated sampled softmax to save the communication cost by local training with only a small number of "negative" classes in addition to the "positive" classes.

2. The authors conduct experiments on three large-scale datasets. The authors conduct the ablation study on how many negative classes are needed. 

==== Weakness =====
1. The technical contribution is not sufficient. There have been many methods like (Bengio & Sen´ecal,2008) and [a-c] that subsample the negative classes in the softmax objective. Specifically, in [c], the proposed method did include the positive classes in a minibatch, together with a set of subsampled classes, to compute the softmax. While the authors compare different combinations of positive and negative classes in 3.4, to me, it seems pretty obvious that we should combine the clients' positive classes with subsampled negative classes. Besides, while the authors discussed several advanced methods in 3.3, they ended up choosing uniform sampling. I was wondering if any of these advanced approaches can be approximately implemented in a federated setting to further improve the performance.

[a] Joulin et al., Learning Visual Features from Large Weakly Supervised Data, ECCV 2016

[b] Mikolov et al., Distributed representations of words and phrases and their compositionality, NeurIPS 2013

[c] Hu et al., Learning answer embeddings for visual question answering, CVPR 2018

2. One potential direction to improve the novelty or technical contributions of the paper is to develop a series of methods for different kinds of representation learning in a federated setting, including learning a fully connected layer and metric learning. If we do not consider the computational cost at the client end, will metric learning (without learning the FC layer) outperform the proposed method? In [a], the authors proposed to learn multiple one-vs-all classifiers rather than a softmax classifier. Will it be effective in a federated setting?

3. The experimental setup can be improved. There is no clear description of how many classes, images, local epochs for each dataset. I also have concerns about using the pre-trained features for 4.2 and 4.3, which makes 4.2 and 4.3 like downstream tasks rather than representation learning. I would suggest that the authors include a fixed feature baseline in Table 1 and Table 2 to demonstrate that fine-tuning the feature extractor in a federated setting could outperform the pre-trained features. 

4. The authors only apply the proposed method to the FedAvg baseline. Will the proposed method be applicable/effective to more advanced federated learning algorithms like FedProx [d], Scaffold [e], and FedDyn [f]?

[d] Li et al., Federated optimization in heterogeneous networks. In MLSys, 2020

[e] Karimireddy et al., Scaffold: Stochastic controlled averaging for federated learning. In ICML, 2020

[f] Acar et al., Federated learning based on dynamic regularization. In ICLR, 2021

==== Other comments ====
1. I would suggest that the authors add "supervised" into their title, to contrast to many recent works on "unsupervised" representation learning.

2. I would suggest that the authors cite some more papers on federated learning.
summary_of_the_review: Overall, I enjoy reading the paper as it pointed out an interesting fact and problem. However, the proposed method seems to be too straightforward with insufficient novelty --- negative class subsampling has been widely used and including positive classes of the client seems to be quite intuitive. I have also listed several potential ways to strengthen the paper (please see the main review). I think the current version of the paper is below the acceptance bar, and thus I give a score of "3".
review_title: null

Meta-review: The paper revisits representation learning for extreme settings (large number of class categories) in a federated learning setup. The authors show how each client can sample a set of negative classes and optimize only the corresponding model parameters with respect to a sampled softmax objective that approximates the global full softmax objective. The authors investigate the interest of the approach for image classification and image retrieval. 

The reviewers appreciated the interest of the approach to reduce communication and the experimental evaluation on several datasets. The reviewers also expressed concerns about privacy, a central concern in federated learning. One reviewer noted for instance that ‘since every sampled set of each client has to include the classes that the client has, the central server can infer the classes the client has’. The reviewers would also have liked to see a more comprehensive evaluation, in the absence of the theoretical guarantees. Finally, the reviewers expressed regarding accuracy/efficiency trade-offs, one reviewer commenting that “the proposed method degrades the accuracy”. 

The authors submitted responses to the reviewers' comments. The authors discussed the challenges related to privacy. The authors also commented on other gradient sparsification communication-reducing competing approaches (FedAwS) and the choice of datasets. After reading the response, updating the reviews, and discussion, the reviewers found that ‘the current good results are only obtained on smaller-scale datasets with fewer classes [while] in machine learning, the phenomenon could be quite different at different scales’ and that ‘it is not clear if the proposed method can outperform TernGrad at the same amount of transferred data [and] TernGrad also has a better convergence proof compared to the proposed method’. 

We encourage the paper to pursue their approach further taking into account the reviewers' comments, encouragements, and suggestions. Recent progress in privacy protection theoretical frameworks in FL (secure multi party computation, etc.), see the recent survey by Kairouz et al. in FnT in ML, should help the authors develop guarantees for their approach. Moreover the reviewers suggested a clear path towards further improvements of the experimental evaluation. 

The revision of the paper will generate a stronger submission to a future venue.

Reject.
Decision: Reject