Distributed Personalized Empirical Risk Minimization

Summary

This paper proposes a new paradigm for learning from multiple heterogeneous data sources to achieve optimal statistical accuracy across all data distributions without imposing stringent constraints on computational resources shared by participating devices. The proposed Personalized Empirical Risk Minimization (PERM) schema provides an efficient solution to enable each client to learn a personalized model by learning who to learn with via personalizing the aggregation of data sources through an efficient empirical statistical discrepancy estimation module. The paper rigorously analyzes the convergence of the proposed algorithm and conducts experiments that corroborate the effectiveness of the proposed paradigm.

Strengths

The strengths of this paper include: 1: The proposed PERM schema is a novel and practical methodology that addresses the data heterogeneity issue in distributed learning. 2: The paper provides insightful theoretical analysis of the proposed algorithm and rigorously proves its convergence. 3: The paper is well written and organized.

Weaknesses

1: Inadequate evaluation and lack of verification on real data: Although the paper includes experiments showcasing the effectiveness of the proposed paradigm, it would greatly benefit from more comprehensive evaluation, particularly using real-world data. 2: The practical usefulness of Theorem 2 is limited due to its dependence on parameters related to the oracle models, which are typically unknown in real-world scenarios.

Questions

1: Could you please provide additional details regarding the implementation of the proposed algorithm, including the specific hyperparameters utilized in the experiments? 2: How does the performance of the proposed paradigm compare to existing approaches in scenarios with highly heterogeneous data distributions? 3: What is the scalability of the proposed paradigm with respect to the number of participating devices? Are there any potential computational or communication bottlenecks that could hinder its scalability? 4: Why were real data experiments not conducted in this study?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

See weaknesses.

Summary

This paper studies a distributed training strategy to obtained a personalized model that shares a bases for all clients while an adaptor for each clients.

Strengths

The overall derivation of the algorithm is theory-driven and reasonable. Good experiment result in the simulation dataset.

Weaknesses

This paper limits the mixing ops by a weighted summation, which great limits the scope and advantage of the proposed method. Does your algorithm work for a more general class of mixing ops? The experiment using the synthesis data looks great but as a paper aims at a very practical setting, could you show experiment on less-toyish benchmark？

Questions

See above

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

See above

Summary

This paper proposes an optimization strategy for federated learning (FL). A key challenge of FL is data heterogeneity, where each client device has different data distributions. Unlike a naive FL, which minimizes the empirical risk simply weighted over clients (called WERM), the proposed PERM first minimizes the empirical risk for each client individually. To mitigate the scalability problem in PERM, this paper proposes a practical algorithm using model shuffling. Experiments show better accuracy and loss compared to other personalized FL methods.

Strengths

+ PERM seems theoretically sound, achieving the optimal solution for each client. The performance seems to be better than representative personalized FL methods. + In addition to data heterogeneity, the proposed method can be easily extended to heterogeneous devices and models since PERM minimizes the loss of each client individually. + This paper explains the theoretical aspects very clearly. Especially Section 2, which describes the key theoretical part, is carefully written and quite easy to understand, even for readers a bit outside the field (like me).

Weaknesses

- The theoretical/practical merit compared to other personalized FL methods is not clearly mentioned (although experimental results show that the proposed method achieves better performance compared to representative methods of personalized FL.) Especially, I am curious about the scalability of the proposed method. In the introductions, I understand that existing personalized methods lack scalability. However, if my understanding is correct, the proposed method also suffers from increasing the number of training data and devices. Rather, PERM theoretically has O(#devices^2) loss functions, as mentioned in the paper, implying that scalability is a significant limitation of PERM. - The overall description was very clear and easy to read, but I sometimes struggled because of missing definitions and confusing notation. For example: * Weight parameter p vs. \alpha might be better for consistency. The definition of \alpha \in \Delta_N does not appear the first time it is used. * The procedure of PERM (L133-134 and Eq.(PERM)) was a bit unclear. In general, it was unclear to me how to determine \alpha_i before knowing the result of each client (i.e., h minimizing Eq.(PERM)) until I read the next section.

Questions

Training time compared to other personalized FL methods. This would be an important aspect and might be related to a limitation of the proposed method. Also, I'm curious about the discussion of scalability against the number of clients, compared with the existing methods.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

As described in the Weakness section, I suspect the proposed method may lack scalability.

Summary

The paper proposes a novel learning framework for personalizing empirical risk minimization in a given federated learning problem where the data is heterogeneous (non-IID). The core idea of the paper is to use optimization relaxations and data shuffling to achieve near-optimal solutions for the general NP-hard personalized federated learning formulation. The paper supports the framework's effectiveness by providing generalization bounds for strongly convex losses. Further, it evaluates the performance of the method on synthetic data where each client learns a logistic regression model.

Strengths

- The paper reviews the most important limitations of the current federated learning literature on heterogeneous data, including clustering and personalization ideas. Further, it demonstrates the main problems of the personalization frameworks (WERM and BERM). - The theoretical study of the problem when the loss of each client is strongly convex is rigorous, and it offers reliable convergence guarantees for large-scale problems (huge number of data points and limited number of devices) - The experiment results on the synthetic data are impressive, showing a significant improvement of the local losses compared to the baseline existing approaches.

Weaknesses

- While the paper claims the method can be used for cases where different models have different architectures, the reliance on the strong concavity and smoothness of $f$ is a serious limitation (neural networks with ReLU activation function are not convex nor smooth). - The experiments are only performed on the synthetic datasets where the underlying model in each client is logistic regression (convex). Therefore, it is not clear that the performance of the proposed algorithm is superior to other baselines if the data is real and the models are non-convex. - While one of the motivations for relaxing is scalability, there is no experiment on many data points and clients. One suggestion is to report the algorithm's runtime aside from the other approaches in the current experiments. Based on the above points, it is understandable that the theory might not be easily extendable to non-convex losses. However, it is crucial to add experiments on real data and with many data points on diverse neural network architectures for different clients.

Questions

- What is the current work's main computational and theoretical advantage to [1]? The theoretical assumptions seem the same in both papers. Is there any improvement in the generalization bounds? [1] Fallah, A., Mokhtari, A., & Ozdaglar, A. (2020). Personalized federated learning: A meta-learning approach. arXiv preprint arXiv:2002.07948.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

- The main limitation of the paper is the reliance on the strong concavity of the model in both theory and experiments. - There is no experiment on real datasets where each client can have its unique model or architecture. - There is no experiment on large-scale datasets where the underlying model is non-smooth and non-convex (neural networks with ReLU activation function).

Response to Authors

Thanks for the response. I found your explanations on comparing to Fallah's work fulfilling. I think it will be necessary to bring some of the experiments (EMNIST in particular) to the main body in the camera-ready version. Further, it would be nice if you mentioned the discussion you had on the scalability of the model in the limitations of the work.

Thanks

Thanks the author for the rebuttal. My concern is partially addressed and I increase my score accordingly.