FAACL: Federated Adaptive Asymmetric Clustered Learning

Thank you for the feedback. We have a clarification question. Above you indicated that our method lacks a comparison to SOTA techniques [1-4]. Can you clarify what are the SOTA techniques [1-4] that you are referring to.

Note that we are currently revising the paper to address each point raised and we will post the revisions once completed.

Thank you for the constructive feedback. Please find some answers to your questions below.

1. We added an introduction to federated learning and clustered federated learning in blue in Section 2.

2. FAACL can be implemented as it is for real world scenarios. In fact, this work was done in collaboration with an industry partner. To assess support, devices do not send their data to other devices. Instead, they receive the models of other clusters and evaluate them on their private validation set. Training is done in multiple rounds as in most federated learning techniques. FAACL and all the baselines used in the empirical comparison use FedAvg as the internal subroutine to train each cluster model. To ensure convergence, FedAvg requires multiple rounds of training. Perhaps the concern is that support evaluation will require additional rounds of training and testing. Note that in all clustered federated learning techniques additional rounds are needed to determine the cluster membership of each device and to continue the training when cluster membership changes. Here cluster support evaluation is equivalent to (though conceptually and procedurally different than) cluster membership evaluation in other CFL techniques. Table 9 compares the communication cost (i.e., combined size of all communication messages) of FAACL and the other CFL baselines. It is higher in the first 5 rounds since FAACL learns the number of clusters and then becomes similar to the other CFL baselines in subsequent rounds. Note that all algorithms ran for the same number of rounds (300) as listed in Tables 6, 7 (rounds correspond to epochs in Tables 6, 7).

3. We added some text in blue in Lines 249-252 to provide more details about Algorithm 5 and in Lines 257-260 for Algorithm 6.

4. Regarding the data splits, we are not sure whether you missed the text in Appendix B or you saw Appendix B but didn't find it clear enough. In any case, we added more details to Appendix B. Let us know if you still have questions about the data splits.

If the above answers address your concerns, please consider revising your score. Otherwise, let us know of any outstanding concern.

Thank you for the constructive feedback. Please find some answers to your questions below.

W1: Thank you for pointing those two very recent papers on CFL. We added a description of CFL-GP and SR-FCA in the related work section and included CFL-GP and SR-FCA in the empirical evaluation. The results for those techniques are highlighted in blue in each table of the revised paper. In short, FAACL outperforms CFL-GP and SR-FCA in all settings except for the MNIST dataset in Table 3 where the differences are negligible given that they both achieve an accuracy similar to the upper bound provided by FedAvg (optimal) when given the true underlying optimal cluster.

W2: FAACL can naturally handle newly added devices. We added the following text in blue in Lines 316-321: "In practice, devices may enter and leave the federation at any time. When a new device appears, it is simply initialized as a singleton cluster whose model is the local model of that device. Then this new cluster participates in subsequent iterations of cluster merging and cluster updating as usual. When a device leaves the federation, it is simply removed from the support and membership of each cluster it used to contribute to. If this device was part of a singleton cluster, that cluster is deleted. Subsequent iterations of cluster merging and cluster updating proceed as usual."

Q1: In previous work, when it is assumed that each device contributes to a single cluster, this limiting assumption prevents devices from contributing to the training of other clusters, which may lead to suboptimal results. As explained in Lines 66-76, there are asymmetric scenarios where the benefits of model sharing are not reciprocal between devices. For instance, consider a situation involving two devices, device $A$ and device $B$. Device $A$ has a large dataset characterized by the underlying conditional class distribution $p_A(y|x)$, whereas device $B$ has a smaller dataset with a similar conditional class distribution $p_B(y|x)$ that matches $p_A(y|x)$ for 90% of the inputs $x$. For device $A$, incorporating device $B$’s data could potentially introduce a bias that might degrade the accuracy of its own model because of the 10% divergence in their data distributions. Thus device $A$ would not wish to train on data from device $B$. Hence $A$ and $B$ should be in different clusters. On the other hand, having $A$ help $B$ train its model could significantly reduce variance owing to the greater volume of data $B$ would benefit from, thereby enhancing its overall performance (reduction in variance outweighs the bias introduced). In such a situation, it would be beneficial to let device $A$ contribute to the training of the models of both clusters that A and B belong to. In FAACL, this is achieved by introducing the notion of support cluster as described in Lines 132-146. Each cluster model will be trained by the devices of the cluster, but also the devices of supporting clusters (see Algorithm 6).

Q2: Regarding privacy, we added Section 4.6 in the revised paper to explain how to enhance the privacy of FAACL with differential privacy (DP). FAACL can be combined with a local DP mechanism (Shokri & Shmatikov, 2015) by adding noise to the weights of each model before sharing. In Algorithm 6, each device can add Gaussian noise as a function of sensitivity to achieve a desired degree of privacy at the end of each round of training. Models can then be shared with clusters and other devices while statistically preventing membership attacks at the cost of a reduction in accuracy. Note that secure aggregation as suggested by Sattler et al. (2020) is insufficient to ensure privacy. Secure aggregation keeps each local model private, but the aggregated model remains visible to everyone and can be attacked to infer the underlying data, especially when the aggregated model memorizes the data. In contrast, differential privacy (statistically) prevents membership attacks.

Q3: The computational complexity of Hierarchical FAACL is at least as good as any other CFL technique. In Lines 919-923, we added the following text in blue: "In comparison, all clustered federated learning techniques have a complexity of least $O(n|\mathcal{C}|)$ since each of the $n$ devices must repeatedly interact with each of the $|\mathcal{C}|$ clusters to determine which cluster to join. Since the number of clusters $|\mathcal{C}|$ may be as large as the number of devices $n$, then hierarchical FAACL has a computational complexity that is at least as good as any other clustered federated learning technique."