Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied the problem of solving federated compositional pairwise risk minimization. This problem has several applications in AUROC maximization with a pairwise loss, partial AUROC maximization with a compositional loss, etc. The main challenge of solving this problem stems from the non-decomposability of the objective function and the interdependence between different machines. To address these challenges, the authors proposed two federated learning (FL) algorithms called FedX (X=1 or 2) for handling linear and nonlinear objective function $f$. The authors provided theoretical convergence analysis for the proposed algorithms and conducted experiments to verify their efficacies.
strength_and_weaknesses: Strengths:
1. Solving compositional pairwise risk minimization problems in a federated setting is a new and interesting problem.
2. The analysis of the "lazy" components necessitated by the communication restrictions in the federated setting is non-trivial.

Weaknesses:
1. Although the compositional pairwise risk minimization problem in the federated learning setting is new, the proposed FedX method appears to be a relatively straightforward extension of FedAvg-type algorithms to this new setting, and the novelty only comes from the complications arising from compositional pairwise risk function stochastic evaluations. Hence, the convergence analysis framework in this paper remains standard.

2. The local update number $K$ scales as $O(T^{-1/3}$, which shrinks as $T$ gets large and is unlike the $O(T)$ in state-of-the-art FL algorithms (see, e.g., [Yang et al., ICLR'21]. Is this necessary or just an artifact due to the proof technicality?

3. The proposed algorithms require full client participation, which is often infeasible in real-world FL systems. Thus, the applications of the proposed algorithms could be limited.
clarity,_quality,_novelty_and_reproducibility: This paper is clearly written and easy to follow. The problem studied in this paper is novel, although the proposed algorithms and analysis techniques are somewhat standard. The reproducibility of this work seems good.
summary_of_the_review: This paper studied the problem of solving compositional pairwise risk minimization in the federated learning setting. The authors proposed two algorithms to handle linear and nonlinear objective functions. The theoretical convergence results are solid and provide interesting insights, although the algorithms and proof techniques are somewhat standard.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is about a Federated learning problem in which every input data point’s $z$ contribution to the objective is an arbitrary function $f$ or the sum of pairwise loss functions, each of which depends on $z$ and some other data point $z^\prime$. This is called compositional pairwise risk (CPR) optimization problem and is a generalization of the pairwise loss minimization problem, where $f$ is linear. Compared to the classical empirical risk minimization (ERM) problem, where the loss functions depend on a single data point, the challenge in the CPR setting is that the fact that data is distributed across different machines makes the computation hard to parallelize, which would not be the case with ERM. This makes the known centralized algorithms for CPR not directly adaptable in the federated learning setting by doing computation only with the data locally stored in each machine. As a result, in order to apply the proposed stochastic gradient descent algorithm, the terms of the gradient are split into “active” parts, which can be computed with local information within some machine, and “lazy” parts that depend on data stored across multiple machines. The latter terms are computed using “historical” data, which were communicated previously between the machines. As long as this “latency” error that is introduced along with the “gap” error from using local models versus the global model are comparable to the variance of the gradient estimator, similar convergence will be achieved with improved running time due to the parallelization. 
strength_and_weaknesses: Strengths:
- There are interesting ideas in the paper which could be useful for solving certain machine learning problems in distributed settings. 


Weaknesses:
- The author did not do a very good job in motivating the setting in the sense of the types of problems it can be applicable to. 
clarity,_quality,_novelty_and_reproducibility: The main ideas in the paper are mostly clear, although the algorithms are a bit complicated, and their analysis seems quite involved. The authors had to introduce novel ideas to overcome technical obstacles.
summary_of_the_review: Even though there are interesting and novel ideas in the paper, I believe there should be more discussion about the applicability of this particular setting, especially since it was introduced quite recently according to the related work section.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies distributed compositional pair risk optimization. The authors develop two algorithms to handle two different scenarios where the outer function $f$ is linear or nonlinear, and established their convergence rates. For linear $f$, they develop a FedX1 algorithm that achieves $O(1/N\epsilon^4)$ sample complexity on each machine. For nonlinear $f$, they design a FedX2 algorithm that achieves $O(M/\epsilon^4)$ sample complexity on each machine. The authors also conduct numerical experiments to test their algorithms. 
strength_and_weaknesses: Strength: 
1. This paper proposed two algorithms for federated CPR and established the best-known sample complexity results.

Weaknesses:
1.  The authors didn't clearly explain the distributed environment. In Page 2, the authors pointed out that a big challenge for CPR is that data are distributed on different machines and are prohibited to be moved to a central server. I don't think this would be a challenging point because most of the existing distributed algorithms do not ask the machines to share raw data, but instead they can share the sampled function value/gradient. It would be helpful if the authors could explain the challenges in distributed CPR more clearly.

2. In Page 4, the authors say that "It is not communication efficient that at each iteration all machines or a subset of machines sample data $z'$ and compute $h_w(z')$ and communicate them to all other machines in order to estimate/compute the blue terms above." However, as we can see from both FedX1 and FedX2 algorithms, these algorithms also require the machines share sampled stochastic information with other machines. For instance, FedX1 requires each machine to compute $H_{i,1}^r$ and $H_{i,2}^r$ and share them with the central machine in each round. This contradicts the above statement and makes me much confused. It would be helpful if the authors could explicitly explain what is allowed in this setting. 

3. Absence of benchmark results: For the case when the outer function $f$ is nonlinear, the authors did not present the benchmark sample complexities for nondistributed CPR. Please provide the best-known non-distributed result so that I can understand the contributions of the distributed algorithm better. 

4. The design of algorithms seems to be standard and techniques seem to be routine. FedX1 randomly samples the lazy parts from the previous round and FedX2 uses an additional weighted average technique, which has been well-understood in many ERM problems. These algorithms might be inefficient and lead to slow convergence.

5. In theorem 2, the authors set $K = O(M^{1/3} R^{1/3})$ where $M = \max_i |S_i|$ is the largest number of data on a single machine and $R$ is the total iteration. Following this strategy, because $| H_{i,2}^r | = K$,  in each round, the number of stochastic samples broadcasted to other machines may be huge if a high-level accuracy is required. This would cost huge memory and communications costs in practice and seems to be inefficient. What are the current best algorithms for handling nondistributed CPR? Is there any lower-bound result for the non-distributed case? 

6. FedX2 requires an $O(M/\epsilon^2)$ per machine sample complexity, which grows linearly in $M$. Further, it seems that this result cannot be applied to the online streaming scenario because this scenario often does not require knowledge of the number of samples. In contrast, it looks like this result fits the finite sum case better where there are only a finite number of data. But the mathematical expression for the finite sum case is often different from the proposed one. Could the authors explain more about this point? Is it possible to develop more efficient algorithms for the finite-sum case?

7. The sample complexities seem to be not satisfactory. Both FedX1 and FedX2 algorithms require $O(1/\epsilon^4)$ samples to find an $\epsilon$-stationary point, which is indeed expensive compared with various complicated problems in the ERM setting having $O(1/\epsilon^2)$ sample complexities. I think a good survey of the current results in both distributed and nondistributed CPR and ERM is helpful. 

8. In the numerical part, the authors use "iteration". Does it count as the product of round $r$ and communication interval $K$?

9. It would be helpful if the authors could provide some  applications of distributed CPR and write down their mathematical formulations to justify the importance and applicability of this problem.  
 
clarity,_quality,_novelty_and_reproducibility: The novelty of this paper seems to be limited in the case that the authors didn't clearly specify their setting and the analysis is standard. 
summary_of_the_review: This paper considers the distribution CPR problem. The main challenge is to design a communication-efficient algorithm in the distributed setting. However, the authors did not clearly explain their problem setting, especially which information can be communicated, making it hard to understand the challenges in algorithm design and evaluate the novelty of their algorithms. The FedX2 requires increasing per-iteration memory and communication costs if the algorithm targets obtaining a solution with high accuracy.  The technical analysis is standard The sample complexity results seem to be unsatisfactory compared with the existing vast works in ERM. 

In summary, it looks to me that the key is to explain the problem setting and why it is hard to design efficient algorithms for CPR. The current contributions seem to be limited.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary: this paper considers FL for the problem of minimizing empirical risk where each term in the sum depends on two datapoints (instead of the customary one datapoint). When datapoints are spread out over multiple clients, this results in a coupled problem where stochastic gradients (i.e. gradient of the loss on a single pair) may not be locally computable because one of the datapoints may not be local. The paper proposes a way to locally approximate (with delay) the aggregate effect of all datapoints, and use that.

Strengths: The paper seems rigorously written

Weaknesses: 
1. Lack of compelling motivation. For many of the problems mentioned (e.g. bipartite ranking or distance metric learning) there are problem-dependent approximate solutions available, or the ERM sum is not over all pairs in the data but rather each datapoint is paired with only a few others.
2. Lack of novelty: the algorithm is fairly obvious. the analysis is less obvious, but even there it follows known outlines in FL optimization
justification_for_why_not_higher_score: The motivation for the problem is somewhat lacking, and the algorithm and analysis - while new - are somewhat standard.
Decision: Reject