FedX: Federated Learning for Compositional Pairwise Risk Optimization
Authors: Zhishuai Guo
Rong Jin
Jiebo Luo
Tianbao Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Pairwise Loss
Compositional Optimization

Abstract: In this paper, we tackle a novel federated learning (FL) problem for optimizing a family of compositional pairwise risks, to which no existing FL algorithms are applicable. In particular, the objective has the form of $\E_{\z\sim \mathcal S_1} f(\E_{\z'\sim\mathcal S_2} \ell(\w; \z, \z'))$, where two sets of data $\mathcal S_1, \mathcal S_2$ are distributed over multiple machines, $\ell(\cdot; \cdot,\cdot)$ is a pairwise loss that only depends on the prediction outputs of the input data pairs $(\z, \z')$, and $f(\cdot)$ is possibly a non-linear non-convex function. This problem has important applications in machine learning, e.g., AUROC maximization with a pairwise loss, and partial AUROC maximization with a compositional loss, etc. The challenges for designing a FL algorithm lie at the non-decomposability of the objective over multiple machines and the interdependency between different machines. We propose two provable FL algorithms (FedX) for handling linear and nolinear $f$, respectively. To tackle the challenges, we decouple the gradient's components with two types namely active parts and  lazy parts, where the {\it active} parts depend on local data that can be computed with the local model  and the {\it lazy} parts depend on other machines that are communicated/computed based on historical models. We develop a novel theoretical analysis to address the issue of latency of lazy parts and interdependency between the local gradient estimators and the involved data. We establish both iteration and communication complexities and exhibit that using the historical models for computing the lazy parts do not degrade the complexity results. We conduct empirical studies of FedX for AUROC and  partial AUROC maximization, and demonstrate their performance compared with multiple baselines.

Under review as a conference paper at ICLR 2023
FEDX: FEDERATED LEARNING FOR COMPOSITIONAL PAIRWISE RISK OPTIMIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
In this paper, we tackle a novel federated learning (FL) problem for optimizing a family of compositional pairwise risks, to which no existing FL algorithms are ap- plicable. In particular, the objective has the form of Ez~s, SS {(w; 2, z ). where two sets of data S are distributed over multiple machines, (():,)) is pairwise loss that only depends on the prediction outputs of the input data pairs (z, z'), and ʃ(-) is possibly non-linear non-convex function. This problem has important applications in machine learning, e.g., AUROC maximization with a pairwise loss, and partial AUROC maximization with compositional loss. The challenges for designing an FL algorithm lie in the non-decomposability of the objective over multiple machines and the interdependency between different ma- chines. We propose two provable FL algorithms (FedX) for handling linear and nonlinear f, respectively. To address the challenges, we decouple the gradient's s components with two types, namely active parts and lazy parts, where the active parts depend on local data that are computed with the local model and the lazy parts depend other machines that communicated/compp torical models and samples. We develop a novel theoretical analysis to combat the latency of the lazy parts and the interdependency between the local model param- eters and the involved data for computing local gradient estimators. We establish both iteration and communication complexities and show that using the historical samples and models for computing the lazy parts do not degrade the complexities. We conduct empirical studies of FedX for deep AUROC and partial AUROC max- imization, and demonstrate their performance compared with several baselines.
based his-
INTRODUCTION
This work is motivated by solving the following optimization problem arising in many MI. applica- tions in federated learning (FL. setting:
((w:2,2')
min WERd
S
S2
ZES,
E'ES,
s(w:R..5))
where S and S2 denote two sets of data points that distributed over many machines, denotes the model parameter of prediction function (.). E Rd,, f(-) is a deterministic function that could be linear or non-linear (possibly non-convex), and l(w;z,z') pairwise loss that only depends the prediction outputs of the input data z, z'. We refer to the above problem as compositional pairwise risk (CPR) minimization problem.
2(h hw (z)))) denotes
When f is a linear function, the above problem is the classic pairwise loss minimization problem, which has applications in AUROC (AUC) maximization (Gao et al. 2013 Zhao et al. 201 Gao &
Zhou 2015 Calders & Jaroszewic7 2007 [Charenppaadeee et al. 2019
Yang et al., 2021b). bipar- Dembezyskk et al.)
tite ranking (Cohen et al. [997] Clémençon al. 2008 Kotlowski et al.
2012). distance metric learning (Radenović et al. 2016 Wu et al. 2017
Yang et al.) 202 When f is a non-linear function, the above problem is a special case of finite-sum coupled compositional optimization problem (Wang & Yang 2022a). which has found applications in various performance measure optimization such as partial AUC maximization (Zhu et al. (2022), average precision max-
imization (Qi et al. 2021
Wang al. 2022 NDCG maximization (Qiu al. 2022), and p-norm

---

Under review as a conference paper at ICLR 2023
push optimization (Rudin 2009: Wang & Yang 2022a) and distance metric learning (Sohn 2016
We provide details of some examples of CPR minimization applications in Appendix
This is in sharp contrast with most existing studies on FL algorithms (ang 2013;
Konevený al. 2016 McMahan et al. 2017, Kairouz et al., 202T Smith et al. 2018 Stich 2018) Yu ct al.) 2019a b
Khaled et al. (2000) Woodworth al., 2020b a Karimireddy al., 2020b 2021 Haddadpour al., 2019), which focus on the following empirical risk minimization (ERM) problem with the data set S distributed over different machines: minwee" TST Exes (w; The major differences between
CPR and ERM are (1) the ERM's objective is decomposable over training data, while the CPR is not decomposable over training examples; and (2) the data-dependent losses in ERM are decoupled between different data points; in contrast the data-dependent loss in CPR couples different training data points. These differences pose big challenge for optimizing CPR in the FL setting, where the training data are distributed on different machines and are prohibited to be moved to a central server. In particular, the gradient of CPR cannot be written as the sum of local gradients at individual machines that only depend on the local data in those machines. Instead, the gradient of CPR at each machine not only depends local data but also data in other machines. As result, the design of communication-efficiee than that for ERM. In addition, the presence of non-linear function f makes the algorithm design and analysis even more challenging than that with linear f. There are two levels of coupling in CPR with nonlinear f with one level at the pairwise loss E(hw h (z')) and another level the non-linear risk of [g((; z, S2)), which makes estimation of stochastic gradient more tricky.
FL. algorithms for optimizing CPR is much more complicated
Although optimization of CPR can be solved by existing algorithms in a centralized learning set- ting (Wang et al. 2017 Ghadimi et al. 22200) Hu et al. 2020 Wang & Yang 2022aa] Qi et al.) 2021] Wang et al.) 2022 Zhu et al.) 2022 Chen et al. 2021 extension of the existing algorithms to the FL setting is non-taivial. This is different from the extension of centralized algorithms for ERM to the FL setting. In the design and analysis of FL algorithms for ERM, the individual machines compute local gradients and update local models and communicate periodically for averaging mod- els. The rationale of local FL algorithms for ERM is that as long as the gap error between local models and the averaged model is on par with the noise in the stochastic gradients by controlling the communication frequency. the convergence of local FL algorithms will not be sacrificed and is able to enjoy the parallel speed-up of using multiple machines. However, this rationale is not sufficient for developing FL algorithms for CPR optimization due to the challenges mentioned above.
To address the challenges, we propose two novel FL algorithms named FedX1 and FedX2 for optimizing CPR with linear and non-linear f, respectively. The main innovation in the algorithm design lies at that we decouple the gradient of the objective with two types, active parts and lazy parts. The active parts depend on data in local machines and the lazy parts depend on data in other machines. We estimate the active parts using the local data and the local model and estimate the lazy parts using the information with delayed communications from other machines that are computed at historical models the previous round. In terms of analysis, the challenge is that the model used in the computation of stochastic gradient estimator depends the (historical) samples for computing the lazy parts at the current iteration, which is only exacerbated in the presence of non-linear function f. We develop a novel analysis that allows us transfer the error of the gradient estimator into the latency error of the lazy parts and the gap error between local models and the global model. Hence, the rationale is that as long as the latency error of the lazy parts and the gap error between local models and the global model is on par with the noise in the stochastic gradient estimator we are able to achieve convergence and linear speed-up.
The main contributions of this work are summarized as follows:
We propose two novel communication-effice CPR with linear and nonlinear f. respectively. Besides communicating local models, the proposed algorithms need to communicate local prediction outputs only periodically.
algorithms. FedX1 and FedX2, for optimizing the
We perform novel technical analysis to prove the convergence of both algorithms. We show that both algorithms enjoy parallel speed-up in terms of the itcration complexity, and a lower-order communication complexity.
We conduct empirical studies two tasks for federated deep partial AUC optimization with compositional loss and federated deep AUC optimization with a pairwise loss, and demonstrate the advantages of the proposed algorithms over several baselines.
2

---

Under review as a conference paper at ICLR 2023
2 RELATED WORK
FL for ERM. The challenge of FL is how to utilize the distributed data to learn a ML model with light communication cost without harming the data privacy (Konevený et al. 2016 McMahan al.) 2017). To reduce the communication cost, many algorithms have been proposed to skip commu- nications (Stich 2018 8 Yu et al., 2019a b Yang 2013 Karimireddy et al., 2020b) or compress the communicated statistics (Stich et al. 2018 Basu et al. | Jiang & Agrawal 2018: Wangni et al.
2018
Bernstein et al.]
2018). Tight analysis has been performed in various studies (Kairouz al.
2021
Yu et al. 2019a bj Khaled et al. 2020; Woodworth et al. 2020b a Karimireddy et al. 2020b
Haddadpour al.
2019) However, most of these works target at ERM.
FL for Ron-ERM Problems. In (Guo et al.] 2020: Yuan et al. 202 Deng & Mahdavi 2021 Deng et al. 2020 Liu et al.] 2020; [Sharma et al., 2022), federated minimax optimization al-
gorithms are studied, which are not applicable to our problem when f is non-convex. Gao
al. [022) have considered much simpler federated compositional optimization in the form of Lx C-DD pf. (e (w; E); (), where l denotes the machine index. We can see that compared
with our CPR risk, their objective does not involve interdependence between different machines. Li ct al. 2022); Huang et al. (2022) have analyzed FL algorithms for bi-level problems where only the low-level objective involves distribution over many machines. TTazzanagh al. (2022) considered
another federated bilevel problem, where both upper and lower level objective are distributed many machines, but the lower level objective is not coupled with the data in the upper objective. [Xing it al. (2022) studied a federated bilevel optimization in a server-clients setting, where the central server solves an objective that depends on optimal solutions of local clients. Our problem cannot be mapped into these federated bilevel optimization problems.
Centralized Compositional Pairwise Risk Minimization. In the centralized setting CPR mini- mization has been considered in recent works (Qi et al.] [202T] Wang et al. 2022 Wang & Yang. 2022a Qiu et al. 2022; Jiang et al., (022). However,
non-trivial to extend these algorithms to the FL setting due to the challenges mentioned earlier. We provide a summary of state-of-the-art
sample complexities for solving ERM and CPR in both centralized and FL setting in Appendix
3 FEDX FOR OPTIMIZING CPR
We assume S S2 are split into N non-overlapping subsets that are distributed over N clients i.e.. S 8 U Sf ... U U. and S₂ S. U S S.Y. We denote by Eg - Exes Denote by Wi: | and W2j N |/ quantities W1 = (Wi1...... WIN) and We (w21....,w2N W2N) are available on all clients. If not, they can be easily computed and communicated once between the N clients. Denote by Vi((--) and V2l(;--) the partial gradients in terms of the first argument and the second argument, respectively. Without loss of generality, we assume the dimensionality of h((w;) z) is (i.e., d, = 1) in the following presentation. For our discussion of complexity, we will simply assume wis w2 R O(1).
N.j I. We assume that these
3.1 FEDXI FOR OPTIMIZING CPR WITH LINEAR f
With linear f. we rewrite the CPR risk into equivalent form that is tailored to the FL setting:
N
min F(w)= =
1 N
EEESi 1=1
E
Σ B Eesse& (h(W, 2). h(w,z'))
wERd
where big (lo (z), ((w, 2²)) = W1nw2, E(h(w, 2), h(w, 2²)). To highlight the challenge and motivate
FedX, we compute the gradient of the objective function and decompose it into two terms:
N
VF(w)
Ezes
Σ J=1
E
Ess
Est Vile h)
N
A
N
1
E EES
E
Beest
V
N
We use clients and machines interchangeably.
3

---

Under review as a conference paper at ICLR 2023
With the above decomposition, gradient terms As and A:2. Due to the symmetry between An and 422, below, we only use An as an illustration for explaining the proposed algorithm. The difficulty in computing An lies at it relies on data in other machines due to the presence of E. Ees! for all j. To overcome this difficulty, we decouple the data-dependent factors in An into two types marked by green and blue shown below:
see that the main task at the local client i is to estimate the
A
EREST
E j= R Byes
Vila
h(w,2) 2)
h((, z')
Vh(w,z)
locall
globall
local2
global2
locall
It is notable that the three green terms can be estimated computed based the local data. In par- ticular, locall can be estimated by sampling data from Si and local2 and local3 can be computed based on the sampled data z and the local model parameter. The difficulty springs from estimating and computing the two blue terms that depend on data on all machines. We would like to avoid com- municating h (w:z)) z') at every iteration for estimating the blue terms as each communication would incur additional communication overhead. To tackle this, we propose to leverage the historical information computed in the previous round To put this into context of optimization, we consider the update at the k-th iteration during the r-th round, where k = o,..., K 1. Let W denote the local model in i-th client the k-th iteration within r-th round. Let ,T,,, E S x,,x,2 E Si denote the data sampled at the k-th iteration from S and Sj, respectively. Each local machine will compute hw"",i x,,1)) and h h(w,, ((,,,)), which will be used for computing the active parts. Across all iterations ks = O, ...... K 1, will accumulate the computed prediction out- puts over sampled data and stored in two sets Hi, = : 1.,,,.). k = O...., K - 1} and Hi = [h(W", 2,,2) h = 0, ...... ...,,, K - 1}. At the end of round r, we will communicate w and MS,1 and Hi,2 to the central server, which will average the local models to get a global model w, and also aggregate Hi Hi,
... U HN., and Hz Hi.2 J H2.2.... U U''222 These aggregated information will be broadcast to each individual client. Then, at the k-th iteration in the E H.- without replacement and compute
1 U H2.1...
r-th round, we estimate the blue term by sampling hT an estimator Au by
G. = Vilia( h(W,, 1
hg.5
Vh(w" 1,6 1
(4)
active
lazy
active
where & = (j, 2,,,,.22 23,2.)) represents a random variable that captures the randomness in the sampled
iteration index & E {O...., K 1} and data sample 2 E St which is used for estimating the global1 in (3). We refer to the green factors in Gi.k.1 as the active parts and the blue factor in G. as the lazy part. Similarly, we can estimate A2 by G2,,,2
client j [L....,N.. N..
G = V26ps M
h( , x,,2)
Vh( T 2,,22)
(5)
lazy
active
active
where hi-51 E HT-1 is randomly sampled prediction output in the previous round with Ç = (i',t, (.) representing random variable including client sample j' and iteration sample t and the data sample r-1 2-,1 Then we will update the local model parameter w',,, by using gradient estimator GT, + G 1,A,2
We present the detailed steps of the proposed algorithm FedX1 in Algorithm Several remarks are following: (i) at every round, the algorithm needs to communicate both the model parameters w and the historical prediction outputs H and H,.51 where H is constructed by collecting all or sub- sub-sampled computed predictions in the (r 1)- round. The bottom line for constructing H'T"" is to ensure that H contains at least K independently sampled predictions that are from the previous round on all machines such that the corresponding data samples involved in 75-1 can be used to approximate N Σm EZES: K times. Hence, keep the communication costs minimal, each client at least needs sample ([[K/N] sampled predictions from all iterations k 0, 1, ..... K 1 and send them to the server for constructing H which is then broadcast to all clients for computing the lazy parts in the round As result, the minimal communication costs per-round per-client
?A round is defined as sequence of local updates between two consecutive communications,
4

---

Under review as a conference paper at ICLR 2023
Algorithm FedX1: Federated Learning for CPR with linear
On Client Require parameters 17, K
2: Initialize model w and initialize Buffer B,, = and B,,2 = 0
3: Sample K points from Si, compute their predictions using model wºo denoted by H
4: Sample K points from Siz compute their predictions using model w denoted by H
5: for r = 1..... do
6: Send H1,11 ,4,,2 to the server
7: Receive R4,11 R from the server
8: Update buffer B, Bi,2 using RT, R with shuffling see text for updating the buffer
9:
Set H - 0, H
10: for k 0, K
do
11:
Sample ,i,,,1 from S/ sample z,,,,2 from S o or sample two mini-batches of data Take next h--1 and hi- from BI, and B,,,, respectively
12:
13:
Compute hu( h(W[,,> 2.,x..) and h( 2(,22)
Add h(w Ri, into Hi,1 and add h(w k. z x.2 into Hi,2
15:
Compute G2,,,1 and 22,222 according (4) and 5
W = Wi. - (GT,,, (T,22)
17:
end for
18: Sends Wi,k to the server
19: Receives w" from the server and set wit Wr
20: end for
21:
On Server
22: for = 0, ..., R do
23: Collects Hi HT, U UH,,, and H2 Hi,2 U H2i22 ... UNN
24: Set R = H4, R H
25: Send R²,,, R client for all [N]
26: Receive w from client i, compute wi+1
DN
Wikk and broadcast it to all clients.
27:
end for
Kdo/N.. Nevertheless, for simplicity in Algorithm into H,T5
| we simply put all historical predictions
Similar to all other FL algorithms, FedXI does not require communicating the raw input data, hence protects the privacy of the data. However, compared with most FL algorithms for ERM, FedX1 for CPR has an additional communication overhead at least (/dKKNN) which depends on the dimen- sionality of prediction output d,, For learning high-dimensional model (e.g. deep neural network with d > 1) with score-based pairwise losses (d,, = 1), the additional communication cost O(K /N) could be marginal. For updating the buffer B,, and Bi,, we can simply flush the history and add the newly received R with random shuffling B,, and add R. with random shuffling to B1.2. However, we can keep the history up to a certain limit as long as the latency error can well controlled, which will be analyzed in Appendix [E]
Next, we present the theoretical results of FedX1 with more formal results given in appendix.
Theorem 1. (Informal) Under appropriate conditions, by setting 1 = O( Rers and K = O O- R1/3
Algorithm ensures that I Σ || [VF((")) - {0(
Remark. To get E1 D [W < 2,, we just need to set R 0 2 and K Ne- The number of communications much less than the total number of iterations i.e., O x())) long as N s O And the sample complexity on each machine Ne4. which is linearly reduced by the number of machines N.
Novelty of Analysis. As the lazy parts are computed in different machines in a previous round, the gradient estimators G and G will involve the dependency between the local model parameter w and the historical data contained in &, used for computing G., and G which makes the analysis more involved. We need to make sure that using the gradient estimator based on them can still result in "good" results. To this end, we borrow analysis technique in (Yang al. 202
5

---

Under review as a conference paper at ICLR 2023
to decouple the dependence between the current model parameter and the data used for computing the current gradient estimator, in which they used data in previous iteration to couple the data in the current iteration in order to compute gradient of the pairwise loss [(h(w,; Ze), h(w,; Zz-1)). Nevertheless, in federated CPR controlling the error brought by the lazy parts is more challenging since the delay is much longer and they were computed we replace W with w' to decouple the dependence between the model parameter w and the historical data Ç. then need to control the latency error ||w- w1 and the gap error between different machines E, Ee EE] Ell - such that the complexities are not compromised.
different machines. In our analysis,
3.2 FEDX2 FOR OPTIMIZING CPR WITH NONLINEAR f
Similarly, -erittte the objective into equivalent form that is tailored to the FL setting, i.e.,
N
F(w)
1
Σ BuEst
E Eesssf ( h(w::)))
(6)
N
where f((-) w.) and (j(::)) w2)e(;.)). We compute the gradient and decompose it into two terms:
(((w)=
1
Σ
E
EE Si N
E Exes; Vfilg(w;,,Sz)) Vi)) Σ
N
j=1
N N
E Ees N MES (f,(
Compared that in for CPR with linear f. the An term above involves another fac- tor Vilg((; (W; S2)), which cannot be computed locally as it depends on S2 distributed over all machines. Similarly, the A2 term above involves another non-locally computable factor (o z, S2)). To address the challenge of estimating g w: 2, S2), we leverage the similar tech- nique in the centralized setting [Wang & Yang 2022b) by tracking using a moving average es- timator based on random samples. In centralized setting, one can maintain and update u(z) for estimating g (w, z, S2) by u(z) + (1-7)u(2) + (h((W 2), h(w, ((,z')), z')). where z' a random sam- ple from Sz. However, this is not possible in an FL setting S2 is distributed over many machines. To tackle this, we leverage the same delay communication technique used in the last subsection. In particular, the k-th iteration in the r-th round, we update u(z),,,1) for sampled 2,,x,1 by
(Z,,.. (1 (1-71)ul 7) (z),,,) + ( 1. hE2"),
where h222 is random sample from H5- where { = (j', ('',(, (1,,2.222))) captures the randomness in client, iteration index and data sample in the last round. Then, we can use f (2,,,,)) in place of V fl 1) for estimating An- However, it is more nuanced for estimating [f 2, 52)) in A2: since z E S3 is not local random data. To address this, we propose to communicate 2 = {uf ( E [N], E [K]-}} Then at the k-iteration in the r- th round of the i-th client, can estimate (9 S2)) with random sample from 4r (u (u])).. Then we estimate A and
denoted by uf where (j',t' .t z 1. i.c., by using ff A2 by
G G
( Vzes( (W/uiz
Vh(WLuiz
lazy
active
(9)
G
Veli
h h( Ri z
Vh(w z(
lazy
active
active
where j.E.j', are random variables. Another difference from CPR with linear f is that even in the centralized setting directly using G²,,11 + will lead to non-linear make the stochastic gradient estimator biased (Wang et al. 2017). Hence, in order to improve the convergence, we follow existing state-of-the-an algorithms for stochastic compositional
complexity due to that
optimization (Ghadimi et al. 2020 Wang & Yang 2022b) compute moving average estimator

---

Under review as a conference paper at ICLR 2023
Algorithm 2 FedX2: Federated Learning for CPR with non-linear
1: On Client Require parameters 17, K
2: Initialize model w - 4 = {n" (z) = 0, Si}, C% = 0, and buffer B1, B,,,, C; = 0
3: Sample K points from Sj, compute their predictions using model wL, denoted by H/!
4: Sample K points from S2g, compute their predictions using model wL, denoted by H.,2 R do
5: for r = 1.... parr=1....
6: Send H1 H4 U to the server
7: Receive R4, R2,22 1---111 pr-- from the server
8: Update the buffer B1,, B, 2, C. using RTT RT22' p with shuffling, respectively
9:
Set H
= 0. H
0
10:
for k - 0, K - do
11:
Sample 2i,,,1 from S/ sample zi, from S a or sample two mini-batches of data from B, and 2 and C, respectively
12:
Take next h-- h and u²-!
13:
Compute h We 21,,,)) and h(w",,: 2(,,,2)
Compute h( 11,1)) and h(w", 2x,2,2) and add them to Hi,1, Hi,2. respectively Compute u (z,,1) according and add to uf
Compute G (i, and Gi,,,2 according 9
G (1 B)G + ((G k.2)
18:
Wi,++1 Wi,k- ",
19:
end for
20: Sends W., G to the server
21: Receives w", G" from the server and set w w,, G7,00 Gr
22:
end for
23:
On Server
24: for ..., R do
25: Collects Hi; = Hi, U HS, 2...... Hy,, and Us UUf
.UU JU,, where * == 1,2
26: Set R = H4, R₁ Hig P. = U and send them to Client for all i E [N]
27: Receive w G from client i, compute w*+1= = N E
w r1 Wik
G = 1 Em i
and broadcast them to all clients.
28:
end for
for the gradient at local machines, i.e., Step 17 in Algorithm 3 With these changes, we present the detailed steps FedX2 for solving CPR with non-linear f Algorithm 3 The buffers B,, and C, are updated similar to that for FedX1. Different from FedX1, there is an additional communi- cation cost for communicating 4 and an additional buffer C, at each local machine to store the received P.-1 from aggregated -/1-1, Nevertheless, these additional costs are marginal compared with communicating H and maintaining the buffer B....
We present the convergence result FedX2 below with more formal results given in appendix. Theorem 2. (Informal) Under appropriate conditions, denoting M max, |S| as the largest number of data on a single machine, by setting 7 = O M1 R373 ), B = O M17o ). 1= O (7775)37)
and K = 0/31/33 R1/3), Algorithm ensures that E D VV )12 < 0 ).
Remark. To get 1 En=
|VF(" [[2] e², we just set R = 0 M1/2 ). 0 7- O
2 and K 11 The number of communications R O M33 is less than the total /M
number of iterations i.c., O (f by factor of O2M /E). And the sample complexity each machine is 24 which is less than that in Wang & Yang (022b) which has a sample complexity of O (Ct) When the data are evenly distributed on different machines, we have achieved linear speedup property. And in an extreme case where all data are on one machine, we see that the sample complexity of FedX2 matches that established in (Wang& & Yang 2022b), which is expected. Compared with FedX1, the analysis of FedX2 has to deal with several extra difficulties. First, with non-linear f. the coupling between the inner function and outer function adds to the complexity of interdependence between different rounds and different machines. Second, we have to deal with the error for the lazy part related U1
7

---

Under review as a conference paper at ICLR 2023
It is notable that our analysis for FedX2 with moving average gradient estimator for solving CPR is different from previous studies for local momentum methods (Yu et al.) 2019a Karimireddy et al. 2020a), which used moving average with a fixed momentum parameter for computing gradient estimator in local steps for the ERM problem. In contrast, in FedX2 the momentum parameter /
is decreasing as R increases, which is similar to centralized algorithms for solving compositional problems (Ghadimi et al. 2020 Wang & Yang 2022b).
EXPERIMENTS
To verify our algorithms. we run experiments on two tasks: federated deep partial AUC maximiza- tion and federated deep AUC maximization with a pairwise surrogate loss, which corresponds to (I) with non- non-linear f and linear f. respectively.
Datasets and Neural Networks. We use four datasets: 1i Ci (Krizhevsky 2009),
CheXpert (Irvin et al. 2019), and ChestMNIST YYang et al. 2021a), where the latter two datasets are large-scale medical image data. The statistics of these datasets are reported in Appendix. For Cifar10 and Cifar100 we sample 20% of the training data as validation set, and construct imbalanced binary versions with positive:negative 1:5 in the training set similar to (Yuan al. 20216). For CheXpert, we consider the task of predicting Consolidation and use the last 1O00 images in the training set as the validation set and use the original validation set as the testing set. For ChestMNIST, we consider the task of Mass prediction and use the provided train/valid/tes split. We distribute training data to N 16 machines unless specified otherwise. To increase the heterogeneity of data on different machines, we add random Gaussian noise of (i,, 0.04) to all training images, where j E {-0.08 0.01 : ).08} that varies on different machines, i.e., for the i-th machine out of the N = 16 machines, its μ -0.0 + i * 0.01. We train ResNet18 from scratch for CIFAR-10 and CIFAR-100 data, and initialize DenseNet121 by an ImageNet pretrained model for CheXpert and ChestMNIST data. All experiments use the PyTorch framework (Paszke et al. 2019
Baselines. We compare our algorithms with three local baselines: 1) Local SGD which optimizes a Cross-Entropy loss using classical local SGD algorithm: 2) CODASCA state-of-the- the--rr-rt FL algorithm for optimizing a min-max formulated AUC loss (Yuan et al. 2021a); and 3) Local Pair which optimizes the CPR risk using only local pairs. As reference, we also compare with the Centralized methods, i.e., mini-batch SGD for CPR with linear f and SOX for CPR with non-linear f. For each algorithm, we tune the initial step size in [le-5, 1] using grid search and decay by factor of 0.1 after every 5K iterations. All algorithms are run for 20k iterations. The mini- batch sizes B1, B2 (as in Step 11 of FedX1 and FedX2) are set 32. The 3 parameter of FedX2 (and corresponding Local Pair and Centralized method) is set to 0.1. In the Centralized method, we tune the batch size Bi and Bg from (32, 64, 128, 256, 512] in an effort to benchmark the best performance of the centralized setting. For CODASCA and Local SGD which are not using pairwise losses, we set the batch size to 64 for the sake of fair comparison with FedX. For all the non- centralized algorithms, we set the communication interval K = 32 unless specified otherwise. In every run of any algorithm, we use the validation set to select the best performing model and finally use the selected model to evaluate on the testing set. For each algorithm, we repeat 3 times with different random seeds and report the averaged performance.
FedX2 for Federated Deep Partial AUC Maximization. First, we consider the task of one way partial AUC maximization, which refers to the area under the ROC curve with false positive rate (FPR) restricted to be less than a threshold. We consider the KL-OPAUC loss function proposed
in (Zuu et al. 2022). which is the formulation of (1) where S denotes the set of positive data, Sj denotes the set of negative data and b(a, = exp((b + a) /A) and f()) log(-) where A is parameter tuned in [1 : 5). The experimental results are reported in Table 1 We have the following observations: (i) FedX2 is better than all local methods (i.e., Local SGD, Pair and CODASCA). and achieves competitive performance as the Centralized method, which indicates the our algorithm can effectively utilize data on all machines. The better performance of FedX2 on CIFAR 100 and CheXpert than the Centralized method is probably due to that the Centralized method may overfit the training data; (ii) FedX2 is better than the Local Pair method, which implies that using data pairs from all machines are helpful for improving the performance in terms of partial AUC maximization; and (iii) FedX2 is better than CODASCA, which is not surprising since CODASCA is designed to optimize AUC loss, while FedX2 is used to optimize partial AUC loss.
FedX1 for Federated Deep AUC maximization with Corrupted Labels. Second, we consider the task of federated deep AUC maximization. Since deep AUC maximization for solving a min-max
8

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison for Federated Deep Partial AUC Maximization, All reported results partial
AUC scores on testing data.
K- 32, N 16
Centralized (OPAUC Loss)
Local SGD (CE Loss)
CODASCA (Min-Max AUC)
Local Pair
FedX2
(OPAUC) Loss)
(OPAUC Loss)
Gifar10
FPR g 0.3
0,7655 D.0039
0.6825
0.7288 D.0035
0.7487 0.0059
0.7580
0.00.44
FPR < 0.5
0.8032-00.039
0.727920.0050
0..702
0.7888 -0,052
Cifar100
IPR x 0.3
0.6287: 0.0037
1.87550000116
0.6131 0.0054
0.6281 0.0032
0.6332 0.0024
FPR 0.5
0.6487=0.0026
06124400002
0.6406=0.0041
0
0.6623- 0.022
CheXpert
FPR 0.3
0.7220=0.0035
0.6495
0.6903=0.0059
0.6002-0.0053
0.7344-0.0042
FPR 0.5
0.7060=0.0000
077017=0.004)
0.770==0.007
0.7483-0.0033
0.7918-0.0037
FPR 0.3
0.634420.0053
0.6071=0.0040 0.6072:000034
0.5904=20.002
0.5802=0.0039 0.6272=0.0038
0.6228=0.0048
ChesMNISS
FPR 0.5
0.6622=000029
0.6026=0.0025
0.6490=0.0039
Table 2: Comparison for Federated Deep AUC maximization under corrupted labels. All reported
results are AUC scores on testing data.
32, N
Centralized (PSM Loss)
Local SGD
CODASCA
Local Puir
FedX1 (PSM Loss)
(CE Loss)
(Min-Max AUC)
(PSM Loss)
Cifrrl
0.735210.0043
0.6501 E0.0024
16.0770000044
072072000027
0.7344.10.000
Cifar100
0.611410.0038
0.370
0.0050
0.6208: 0.6075=000045
1.0044
CheXpert
0.8149::000011
0.678210.0032
0.006210:0083
0.70241000043
ChestNNIST
0.722710.0026
0.564220000011
0.6509
0.67661000019
0.,023
Chric,
pMuG,
Weltaroe gilic
Ocetstort
Overaloot
ba)
Het
64.23
Sunder
Figure 1: Ablation study: Left two: Fix N and Vary K; Right two: Fix K and Vary N
loss (an equivalent form for the pairwise square loss) has been developed in previous works Yuaan et al. 2021a), we aim to justify the benefit of using the general pairwise loss formulation. According to "hhrrenphhaddee et al. 2019), a symmetric loss can be more robust to data with corrupted labels for AUC maximization, where a symmetric loss is one such that {(=)+((=2) is a constant. Since the square loss is not symmetrie,
conjecture that that min-max federated deep AUC maximization algorithm CODASCA is not robust to the noise in labels. In contrast, our algorithm FedXI can opti- mize a symmetric pairwise loss; hence we expect FedX1 is better than CODASCA in the presence of corrupted labels. To verify this hypothesis, we generate corrupted data by flipping the labels of 20% of both the positive and negative training data. We use FedXi/Local Pair to optimize the symmetric pairwise sigmoid (PSM) loss (Calders & Jaroszewicz 2007). which corresponds to (T) with linear [()) = 8 and É(a, b) = (1 + exp((a - b))) where a is a positive data score and b is a negative data score. The results are reported in Table 2 We observe that FedX1 is more robust to label noises compared to other local methods, including Local SGD, Local Pair, and CODASCA that optimizes min-max AUC loss. As before, FedXI has competitive performance with the Centralized method.
Ablation Study. Third, we show an ablation study to further verify our theory. In particular, we show the benefit of using multiple machines and the lower communication complexity by using K > 1 local updates between two communications. To verify the first effect, we fix K and vary N, and for the latter we fix N and vary K. We conduct experiments the CPR risk corresponding to partial AUC loss and the results are plotted in Figure T The left two figures demonstrate that our algorithm can tolerate certain value of K for skipping communications without harming the performance; and the right two figures demonstrate the advantage of FL by using FedX2, i.e., using data from more sources can dramatically improve the performance.
the CIFAR-10 data for optimizing
5 CONCLUSION
In this paper, we have considered federated learning (FL) for compositional pairwise risk minimiza- tion problems. We have developed communication-efiiienn FL algorithms to alleviate the inter- dependence between different machines. Novel convergence analysis is performed to address the technical challenges and to improve both iteration and communication complexities of proposed algorithms. We have conducted empirical studies of the proposed FL algorithms for solving deep partial AUC maximization and deep AUC maximization and achieved promising results compared with several baseline algorithms.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qspars--local-sgd: Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pp. 560-569. PMLR, 2018.
Kendrick Boyd, Kevin H Eng, and C David Page. Area under the precision-recall curve: point esti- mates and confidence intervals. In Joint European conference on machine learning and knowledge discovery in databases, pp. 451 1-66. Springer, 2013.
Toon Calders and Szymon Jaroszewicz. Efficient AUC optimization for classification. In Joost N. Kok, Jacek Koronacki, Ramón López de Mántaras, Stan Matwin, Dunja Mladenic, and Andrzej Skowron (eds.), Knowledge Discovery in Databases: PKDD 2007, 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, Warsaw, Poland, Septem- ber 17-21, 2007, Proceedings, volume 4702 of Lecture Notes in Computer Science, pp. 42-53. Springer, 2007. doi: 10. 0001007797--3-544-7477--99999999 978-3-540-74976-
URL httph:t//// /estss://ci... htt.//ii.oog/1.11111 1001//000077
Nontawat Charoenphakdee, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for learn- ing from corrupted labels. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 Proceedings of Machine Learning Research, pp. 961-970. PMLR, 2019. URL http:tt:ppoocceeeinngg www.mmrrp......... www.pp.ee......................e /v9 ht9p9///ccccrempphaeeeeee 9a.
html
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937- 4948, 2021. doi: 10.1 2911009922222213392222 2021 3092371
Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis. Ranking and empirical minimization of u-statistics. The Annals of Statistics, (6(2):844-874, 2008.
William W Cohen, Robert E Schapire, and Yoram Singer. Learning to order things. Advances in neural information processing systems, 10, 1997.
Krzysztof Dembezynski, Wojeiech Kotlowski, and Eyke Hüllermeier. Consistent multilabel ranking through univariate losses. arXiv preprint Xiv: 20016 2012.
Yuyang Deng and Mchrdad Mahdavi. Local stochastic gradient descent ascent: Convergence anal- ysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pp. 1387-1395. PMLR, 2021.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. Advances in Neural Information Processing Systems, 33:15111-15122.
2020. 2020.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integran integrateee differential estimator. Advances in Neural Information Processing Systems, 31, 2018
Hongchang Gao, Junyi Li, and Heng Huang. On the convergence of local stochastic compositional gradient descent with momentum. In International Conference on Machine Learning, pp. 7017- 7035. PMLR, 2022.
10

---

Under review as a conference paper at ICLR 2023
Wei Gao and Zhi-Hua Zhou. On the consistency of AUC pairwise optimization. In Qiang Yang and Michael J. Wooldridge (eds.), Proceedings of the Aventy-Fourrle International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina. July 25-31, 2015, pp. 939-945. AAAI Press, 2015. URL htttp://1jp http://aat...oetettattaatcttctce
Wei Gao, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou. One-pass AUC optimization. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pp. 906-914, JMLR.org, 2013.
mlr press /22ess/v2/// http:/v2////a// /atp//aal333/ 3.tml
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimizution, 23(4):2341-2366 2013.
Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approxi- mation method for nested stochastic optimization. SIAM J. Optim., 30(1);900-979, 2020. doi:
WRRLhttps://// //doi.:://///oo/ org. 1ttp//1...11//1112255533333 23C542
Margalit R Glasgow Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (lo- cal sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Communication- efficient distributed stochastic auc maximization with deep neural networks. In International Conference on Machine Learning, pp. 3864-3874. PMLR, 2020.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32, 2019.
James A Hanley and Barbara McNeil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1):29-36. 1982.
Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order meth- ods for conditional stochastic optimization and applications in meta learning. In Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neu- ral Information Processing Systemy 2020, NeurIPS 2020, December 6-12, 2020, vir- tual, 2020. URL bttps:: neurips. htc/paper/2220/haaae
Abstract html
Yankun Huang, Qihang Lin, Nick Street, and Stephen Baek. Federated learning on adaptively weighted nodes by bilevel optimization. arXiv preprint arXiv:2207. 10751, 2022.
Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-lleus, Chris Chute, Hen- rik Marklund, Behzad Haghgoo. Robyn L. Ball, Katie S. Shpanskaya, Jayne Seekins, David A. Mong, Safwan S. Halabi, Jesse K. Sandberg, Ricky Jones, David B. Larson, Curtis P. Langlotz, Bhavik N. Patel, Matthew P. Lungren, and Andrew Y. Ng. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelli- gence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pp. 590-597. AAAI Press, 2019.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. Advances in Neural Information Processing Systems, 31, 2018.
Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang, and Tianbao Yang. hulti-block-ssngle-ppe variance reduced estimator for coupled compositional optimization. arXiv preprini 0807002207.08540, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-200, 2021.
11

---

Under review as a conference paper at ICLR 2023
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebas- tian Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03606, 2020a.
Sai Praneeth Karimireddy, Satyen Kale. Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5144 5143. PMLR, 2020b.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross-device federated learning. Advances in Neural Information Processing Systems, 34:28663-2888 28676, 2021.
Ahmed Khaled and Chi Jin. Faster federated optimization under second-order similarity, arXiv preprint arXiv:2209.0222 2022.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Jakub Konevený, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: arXiv:6610.02277, 2016.
Wojeiech Kotlowski, Krzysztof Dembezynski, and Eyke Hüllermeier. Bipartite ranking through minimization of univariate loss. In Lise Getoor and Tobias Scheffer (eds.), Proceedings of the 28th International Conference on Machine Learning, ICMI, 2011, Bellevue, Washington, USA, June 28- July 2, 2011, pp. 1113-1120. Omnipress, 2011. URL https: :ttos:///cmmmm cc/2011/ papers/567 567 icmlpaper. pdf
Alex Krizhevsky. Learning multiple layers of features from tiny images. pp. 32-33, 2009.
Junyi Li, Jian Pei, and Heng Huang. Communication robust federated learning with noisy labels. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 914 924, 2022.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- tems, 2:429 2:429-450, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.021190 2019.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity, arXiv preprint 19Xiv:191..12600 2019.
Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jarret Ross, Tianbao Yang. and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 33:1 1056-11070, 2020.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcieent learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! arXiv preprint (.Xi::2202.09355,, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
12

---

Under review as a conference paper at ICLR 2023
Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang. Ji, and Tianbao Yang. Stochastie optimization of areas under precision-recall curves with provable convergence. In Mare' Aurelio Ran- zato, Alina Beygelzimer. Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp-
1752-1765, 2021, BRLptttt///prrreeiinngs neurips......................... 0dd1bc593a
Abstract. wttppppee/2////aaaaeeeeee
Zi-Hao Qiu, Quanqi Hu, Yongjian Zhong, Lijun Zhang, and Tianbao Yang. Large-scale stochas- tic optimization of NDCG surrogates for deep learning with provable convergence. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Mary- land, USA, volume 162 of Proceedings of Machine Leurming Research, pp. 18122-18152. PMLR, 2022. URL /ttpttttt:pp/prceeiiiioo www.eeeedinngsmm...... mlr wtt.:m.....p.s.se.e.e..e.e wwwp://pw/g/iiaao.aoaaa.a html
Filip Radenović, Giorgos Tolias, and Ondvrej Chum. Cnn image retrieval learns from bow: Unsu- pervised fine-tuning with hard examples. In European conference on computer vision, pp. 3-20. Springer, 2016.
Cynthia Rudin. The p-norm push: A simple convex ranking algorithm that concentrates at the top of the list. J. Mach. Learn. Res., 10:2233-2271 2009, doi: 10.5555/1577069.155566 URL https: / /dl. acm. org/ 10. 0tt.://0.5555/177691115353533339
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiiiene distributed optimization using an approximate newton-type method. In International conference machine learning, pp. 1000- 1008. PMLR, 2014.
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimiza- tion: Improved convergence analyses and algorithms. In International Conference on Machine Learming, pp. 19683-19730 PMLR, 2022.
Virginia Smith, Simone Forte, Ma Chenxin, Martin Takávc, Michael I Jordan, and Martin Jaggi. Cocoa: general framework for communicatonn-fficien distributed optimization. Journal of Machine Learning Research, 18:230, 2018.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. Advances in neural information processing systems, 29, 2016.
Sebastian U Stich. Local sgd converges fast and communicates little. International Conference on Learning Representutions, 2018.
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Ad- vances in Neural Information Processing Systems, 31, 2018.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. FedNest: Federated bilevel, minimax, and compositional optimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 21 146-21179. PMLR, 17-23 Jul 2022. URL https: : http:::///occeedeeeeee mmr. html
press/v1122ttarzaaapi/
Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: The- ory and applications. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 23292-23317, PMLR, 2022a. URL http::pss//pocceednige ml press/ v162 2162/wang22 wttp///n.22aaka..mmmmm html
Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. In International Conference on Machine Learning, pp. 23292-23317.. PMLR, 2022b.
13

---

Under review as a conference paper at ICLR 2023
Guanghui Wang, Ming Yang. Lijun Zhang, and Tianbao Yang. Momentum accelerates the conver- gence of stochastic AUPRC maximization. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Re- search, pp. 3753-3771. PMLR, 2022. URL httts:://proceeeeeeeeee ngs. mll.mmml... wtt.m......//s11/////// wang22b. html
Isabel Valera (eds.), International Conference
Mengdi Wang, Ethan Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Math. Program., 161(1-2): 419-449, 2017. doi: 10.1007/110107-016-10777 s10107-011 016 1017-3
URL http:::/ac..orr/11...1000
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication efficient distributed optimization. Advances in Neural Information Processing Systems, 31, 2018 8.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcma- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334- 10334-10343, PMLR, 2020a.
Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6292 2020b.
Chao-Yuan Wu, Manmatha, Alexander J Smola, and Philipp Krahenbuhl. Sampling matters in deep emhedding learning. In Proceedings of the IEFE international conference computer vision, pp. 2840-2848, 2017.
Pengwei Xing. Songtao Lu, Lingfei Wu, and Han Yu. Big-fed: Bilevel optimization enhanced graph-aided federated learning. IEEE Transactions on Big Data, pp. 1-12, 2022. doi: 10.1 100/ TBDATTA.002..3911449
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification. arXiv preprint arXiv:2110.14798. 2021a.
Tianbao Yang. Trading computation for communication: Distributed stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, 26, 2013.
Tianbao Yang. Algorithmic foundation of deep x-risk optimization.
arXiv preprint
arXiv:2206.0044 2022.
Zhenhuan Yang, Yunwen Lei, Puyu Wang, Tianbao Yang, and Yiming Ying. Simple stochastic and online gradient descent algorithms for pairwise learning. Advances in Neural Information Processing Systems, 14:20160-20177 2021b.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mo- mentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp. 7184-7193. PMLR, 2019a.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019b.
Zhuoning Yuan, Zhishuai Guo, Yi Xu, Yiming Ying, and Tianbao Yang. Federated deep auc max- imization for hetergeneous data with constant communication complexity. In International Conference on Machine Learning, pp. 12219 12229, PMLR, 2021a.
Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep AUC maxi- mization: A new surrogate loss and empirical studies on medical image classification. In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC. Canada, October 10- 2021, pp. 3020-3029 3029. IEEE, 2021b. doi: 10. 1ww1100//CC249222.0.02 100303. URL ht http://toooooog..... http://......oo///....oooo//o222 00303
14

---

Under review as a conference paper at ICLR 2023
Peilin Zhao, Steven C. H. Hoi, Rong Jin, and Tianbao Yang. Online AUC maximization. In Lise Getoor and Tobias Scheffer (eds.), Proceedings of the 28th International Conference on Machine Learning, ICML 2011. Bellevue, Washington, USA, June 28 July 2, 2011, pp. 233-2400 Omni- press, 2011. URL Utthttps:/ cml wttpc//////////et papprppppsssaaa 8 / 98 5 cm 1 paper.app.... p
Dongruo Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization. In International Conference on Machine Learning, pp. 7574-7583, PMLR, 2019.
Dixian Zhu, Gang Li, Bokun Wang. Xiaodong Wu, and Tianbao Yang. When AUC meets DRO: optimizing partial AUC for deep learning with non-convex convergence guarantee. CoRR. has/2203.00112 2022. doi: 10.48550arXX..2203.00777
URL
18550/arXi:0 2203.00176
15

---

Under review as a conference paper at ICLR 2023
A APPLICATIONS OF CPR PROBLEMS
We now present some concrete applications of the CPR minimization problems, including AUROC maximization, partial AUROC maximization and AUPRC maximization. A more comprehensive list of CPR minimization problems is discussed in the Intrduction section and can also be found in recent survey (Yang 2022).
AUROC Maximization The area under ROC curve (AUROC) is defined (Hanley & McNeil 1982 as
AUROC(W) = E[[(h(w w, z) 2 h(w, z })ly = +1, = -
(10)
where z, z' are a pair of data features and y, y are the corresponding labels. To maximize the
AUROC, there are number of surrogate losses {(),, e.g. [(w: z
(1 h(w, z) + h(w (w z 2
that have proposed in the literature (Gao et al. 2013 /Zhao et al. 201
Gao & Zhou 2015 Calders &
Jaroszewic7 2007
Charoenphakdee et al. 2019 Yang al. 2021b).
which formulates the problem
into
[(w, 2i, 25), 2, where S1 the set of data with positive labels and S2 the set of data with negative labels. This a CPR problem of (I) with f(z) = r.
min
S
(11)
2.
medical diagnosis, high false positive rates (FPR) and low true positive rates (TPR) may cause a large cost. To alleviate this, we will also consider optimizing partial AUC (pAUC). This task considers to maximize the area under ROC curve with the restriction that the false positive rate to be less than a certain level. In Zhu et al. (2022). it has been shown that the partial AUROC maximization problem can be solved by the
Partial AUROC Maximization
((w, ((,,2, 2, Zz)
min w
Alog X.ES,
exp 2,ES2
(12)
S
S2
where S is the set of positive data, S2 is the set of negative data, E(-) is surrogate loss, and À associated with the tolerance level of false positive rate. This is CPR problem of ( with
f(x) = >llo(()), and f(w, (w, 21) exp( f(w f(w.z.2,)))
AUPRC Maximization According to Boyd et al. 2013), the area under the precision-recal curve (AUPRC) can be approximated by
Σ
T(y; 1)T((((w, (w, h((,2z))
(x) (ESSE)ESS
T(y: =
(13)
S
Σ
I(h W 2,) 2 (,)
(R:
(ES
Then using surrogate loss, the AUPRC maximization problem becomes
Σ
I(U = 1) (((,, z; zz))
I( 1) (E..
min
(14)
S
Σ É(w, 2,Z,) (K),)))S
(ES))E)
which is CPR problem of
1 with ((w, 24,
((y,==))((w Zi, ((), and
f(11. x2)
Zi
Qi
al.
2021
B COMPLEXITY FOR SOLVING CPR AND ERM PROBLEMS
In Table 3 we summarize state-of-the-an results for ERM problems and CPR problems, in both centralized setting and federated setting. We cover the cases when the data comes with/without finite-sum structure. For the CPR problem, consider the finite-sum form for both the inner function and the outer function.
Here focuses non-convex problems. For federated learning in convex/strongly-comm cases, please refer to (Shamir et al.] 2014 Li et al. 2019 2020 Khaled et al.) 2020 Karimireddy et al. 2020b 2021 Mishchenko et 2022 Khaled & Jin 2022 and reference therein.
In Table 3 the * notion indicates that an algorithm matches a known lower bound complexity. The Spider algorithm (Fang et al. 2018) matches the lower bound result in (Zhou & Gu 2019) for the
16

---

Under review as a conference paper at ICLR 2023
Table 3: Comparison for sample complexity on each machine for solving ERM problem and CPR problem to e-stationary point, i... [[]] I e². N is the number of machines in federated setting. n is the number of finite-sum components outer finite-sum setting, which in ERM the number of all data and in CPR is the number of data on the outer function. Rin denotes the number of finite-sum components for the inner function 9 when it is of finite-sum structure. In federated learning setting with finite-sum structure, each machine i has n; data in the outer function. indicates the complexity matches a known lower bound.
Sample Complexity
Setting Expectation
SGD" O(1/2") (Ghadimi & Lan 2013
Centralized
SPIDER" O(ya/e
(Fang ot al, 2018
Finito-sum
PR-SGD": O(1/NA)) Yu
2019h
Expectation
ERM
Federated
VRL-SGD": O(1/Ne) Liang 2019
Expectation
SCAFFOLD': O(1/Ne")
(Karimireddy
20206
Expectation
FedProx: OL1/NT 2020
Finite-sum
Mime: O11 / Karimireddy al. 2021
Finite-sum
BSGD: ((1/2") (Hu 2020
Inner Expectation Outer Expection
BSpiderBoost": (1 (Hu 2020
Inner Expectation Outer Expectation
CPR
MSVR: (max(1 (e",, n/e")))))))) Ciang al. 2022
Inner Expectation Outer Finite-sum
Centralized
MSVR: D (e Tiang al. 2022
Inner Finite-sum Outer Finite-sum
SOX: O(n/e*) Wang & Yang 20226
Inner Expectation Outer Finite-sum
Federated
This Work: O(max, n,/e")
Inner Expoctation Outer Finitc-sum
finite-sum setting and the SGD algorithm (Ghadimi & Lan 2013) matches the lower bound in (Ar-
jevani et al. 2022) for the expectation setting. In finite-sum setting, the federated ERM algorithms,
i.e., PR-SGD, VRL-SGD, SCAFFOLD, matches the lower bound in (Woodworth et al. 2020b a
Glasgow et al., (022). BSpiderBoost matches the lower bound in (Hu et al.) 20200. For CPR
problems with a finite-sum structure on the outer function, the tight lower bounds are still unclear. After submitting to ICLR 2023, we noticed later work Jiang et al.] (2022) has propose MSVR algorithm (in Table 3 that further improves the sample complexities by utilizing variance reduce techniques SVRG and STORM. However, naively implementing MSVR in federated setting would have a much higher communication cost than our algorithm. Actually, even for those ERM algo- rithms which have used similar variance reduction techniques, it remains an open problem whether any communication-fffiiceit algorithm could be feasible.
C ANALYSIS OF FEDXI FOR OPTIMIZING CPR WITH LINEAR f
In this section, we present the analysis of the FedX1 algorithm. For z S and z' E S22, define Gi(w, z. w', z') = ()l,(h((:: h((''zz)) Vh(w;z)
(15)
G2( zz) = (hli)(((w, hiww Vh(w';z').
Therefore, the
G. Vilig 2 2. 1 V x.
defined in (3) is equivalent to Gi [W[,s 2 w - -) where h h(W57 ;257,)
scored of a randomly sampled data that in computed in the round r at machine j and iteration t. Technically, notations j and t are associated with and k. but we omit this dependence when the context is clear to simplify notations.
Similarly, the
G Velye(hi, h(w
2Z z.,22))) Vh(w
17

---

Under review as a conference paper at ICLR 2023
defined in 5 is equivalent to G2 (2
2. r-1 Whi 2(,2 Denote
(F((w) = BRES! N
LEs (W)
(16)
N
Exss N
E MES "(
(17)
1=1
We make the following assumptions regarding the CPR with linear f problem, i.e., problem 2
Assumption 1.
(-)() is differentiable, Le-smooth and Ci-Lipschitz.
hcs, 2) is difserentiable, La-smooth and Cn-Lipschitz on w for any z E Si US.
(ites//sss|////////////////vv/v + VF((w]] 0
/VV((w) -VF(W)] s D2.
Under Assumption it follows that F(.) is T--smooth, with L. == 2(TxCh + CeTTk). Simi- arly, G1, G2 also Lipschtz in with some constant L1 that depend on Ch, Ct, Le, Lp. Let max (T.p }.). Basically, we consider well-conditioned problems where Wi,1 = NiSi and 41,2 = .NSS
=
T
[Sa] are of O(1), therefore the above constants are appropriate. Nevertheless, we can also
directly consider the FL objective where W1,t = 1 and W2,1 = similar to existing FL studies for the ERM problem. We re-present Theorem as below.
N Theorem 3. Under Assumption by setting = O( (p//a) and K = 0 ), Algorithm ensures
that
R
1
E
V
|
<
0
(18)
R
R2/3
P=
18

---

Under review as a conference paper at ICLR 2023
Proof. Denote ÿ nK. Using the L-smoothness of F(w), we have
F( - F(w") - VF(W") (((("")[("++)) (w - w
w
w012
2
I
=-iVF(w') NK ΣΣ (G + G.Aa22
+
-
-wl
-
2
=-i(V((w") - VF(W" VI
1
G + GiAaa)
+ I w
-w]2
w'|3
NK
2
_ 27.
1
|VF(W) VF(W-11]|
LI
ΣΣ
(G. + GT222)
NK
b.
-NVF(w
NK Σ Σ ..... + Gimee
+ L |/ -w11
12iRi NK ΣΣ G + 22222)11++ /.l
-
- HVF(W" TT
1
ΣΣ GG + Giaz2)
NK
(19)
where
-E
(VF(WW
ΣΣ
(Gia Glaa))
NK
--R(1VF(W~1)
NK Σ
(w A. (.5i2) + G2 27 wh, (,22
Gw 2..1. .2j.,)) G2 a 2..2.2)
+ +WWWW "..... "....."" x3يū,) + G2(w 1- . (...
- -BIVE( |1 - 41 871. 1
Σ NK
Bllw" wi.ll?
-ENFF(W" NK ΣΣ (Gi(w") ",,,,, (. GZ(w"-1 "2 w"=' .2. ,22, VFl( (w""w
vF((
8 - 1 871.? 1
ΣΣ BllW - - (EW
NK
i E IVF - -
1
Blw w.
NK
(20)
where the second equality holds because that data samples 1 25 , 2f, are indepen- dent samples after w"-1, therefore
[[[G]( 11 2 w"-1, 22 + G2(w" L (2.,22) - -VF( =0 (21)
19

---

Under review as a conference paper at ICLR 2023
To bound the updates of w" after one round, we have 1/
E||w**
w"12
El NK IDOGa oa,
G2 Ba whes 2)l
NK
5n
C2
NK
NK
+ B
NK G1 A.
G1 (W", Z.A.I. (. G2(( u الaد)
NK
NK G1(W", A. + G2(w" [.
Gw A G2(w"
NK
+5
NK [iiww Z.a.. (55.22) + G2(w" 2 2. V Fi (P((w--1)
5ij 2.
/F(
$ $107² 1.2 NK
B W w'll 100 1?
ΣΣ
El Wi, w1= 107 L' - -1" Bll
NK
h
a² + +00 NK
+ 10
(22)
Thus,
1
E -
S R Σ
40
1
ΣΣ
E I
121++00 2012
NK +
o²
R
NK
(23)
Then we bound the updates in one round and one machine as
| w 1|2 = || (G] - - 1, w j.t 2,022) G2 G2 r-1 1-1
j 3,, Wi 1 2 21,= -- 1,2) - w/l2
$ 1| w- 1//G///"" 1 2,, + G2(w"- 1 , 1 x1,)=1,2))
+ [[GG((""
1,,,,,,,111-- 2,, G2(w"
J w--1, - 1.2 1-
-G'((W, zi k.i,k-1,11 -,,,,,,,,,, w- -3 + G2(w"" 2 1111 w", zz 1,2)
+ +n( Zz, k- 1,1 W w- , 2 + G2 (w" _ W - 1,2)
-G 2 1,1 2 G2(
2 W k- 2,))
+ [[C
2,, + G2 w _.j.e.11 k 11ح,
- -G
x + G2 w w b W 2,2)1 2
(24)
20

---

Under review as a conference paper at ICLR 2023
Using Young's 's inequality, continue this inequality
E w W[,
1
$ (1 + 4K ] B W -nG(G 22, 1,1 W : 33,112) + G2(W" 3.g0, w-1 -22x=12)1
+ (4K + E))" ,2, w- .21122 + G2(W" .z..e.11 w x112-12
-[GI(W' 1.11 w ,2,,1,1))
[2,1122 + G2(W" , 1 w ,,,K-122211
+ ([G] 1,1 W (3,22) + G2( (w" 5 w", x-22)
-[G1(W) k 2 1-1--111
j122 + G2((
e w Wi, 2, 212))
+ ([Gi(W],- 1-11-1111 1,1 23222 + G2( (w'"l , 1 W x122
- -[G -- 1, (522) + G2(w j 2 11 Wi, 4 -1
S + 4K
- w (G 24 - 1,1: w (,222 + G2 (w 2 x.-x=1,2))
+ (88K)"LEE w- w/ 12 + | W || | w |1
S + K |B||
w- V/ - 1)1 + 5n/² Ko²
+ 18K1 2' -- w + || - w w + 1| wJ. 13)
S11+ + 2
E
w/ + +4
+ 5K7202
K
+ 18K 2' -- w/ 11
|
W,,7 -1 112)
S 5(1+ +
E W T,K-- V
3 + 02)
K
+ 18K')² i.2E(1 [W w 1| + |
W w5 13))
2
+ 18 2 L3 (1=-=--------333333------------- -K +02)
(1 K
w/1 + 8K
+ 18K1 L' w 11 1
(25)
Thus, Eliw"
(SKN"E|VE(( + { +o²) + +18K,, i Fl[ w
+ +| - 15.
(1
2
+ +18K771m
K
m=
S "| +2)
0²) + 18K1,² L''((I - 1 || 1 1 (1))511)))5K
< 7 ||
0²) + 100K3 - D'E((IW'--W w1 | w3.5 11?),
(26)
where the second inequality is due to 18K7²² < +
Then,
1 R
N
K w/, <
Ellw
El
(D00((=++++)) +02), (27)
RNK
r=l
k=
and
20 + + 2017 0²
E 1 <
NK' (28)
Recalling 66
and 20
we obtain
(2(F(W))- F.)
+ (D2 + 0 + 407 0²
El F( so
(29)
R
ij
NK
21

---

Under review as a conference paper at ICLR 2023
R E 2, it takes
If we set O(Ne)), K = O(1/Ne), thus rj = O()), to ensure # Σ ((,,) )1 )|
communication rounds of R = O( and sample complexity on each machine 0 ((Nc))
D FEDX2 FOR OPTIMIZING CPR WITH NON-LINEAR f
In this section, we define the following notations:
G W1. Z1, u, Z2)
(30)
G1
W1. (1.
21, u. W2, Z2) = =))
Denote
[.((w) BrEst N
B (/d
(31)
N E
B Ex N V/w.///a/////////////aa////////)
(32)
j=1
We make the following assumptions regarding the CPR with non-linear f. i.e., problem Assumption 2.
6
(-(-) is differentiable, Le-smooth and Cr-Lipschitz. (6(-) Co-
f+(-) is differentiable, Ly-smooth and Cy-Lipschitz.
h(,z)) is differentiable, Lx-smooth and Cn-Lipschitz on w for any E Si U US2
[VF D
Based on this assumption, follows that G. Grg are Lipschitz with some constant modulus C₁ and are bounded by C2, F is mmoohh.. where C1, C2. LE are some proper constants depend on Assumption 2
We denote L = max(C1, C2, LF} to simplify notations.
D. ANALYSIS OF THE MOVING AVERAGE ESTIMATOR
For 2ι E 22 Sy define g(W1,21, Z2) (,(h(W1;21); h( z2)) and for z₁ E Sj, we define
g(Wl.2). W2. W2. Sz)
E Exesy
(33)
N
22

---

Under review as a conference paper at ICLR 2023
Lemma 1. Under Assumption the moving average estimator u satisfies
E Fl
o( ( 2, Wk: S2)
xE|Si|
7
Σ
Σ
4|
N ==1
|
zE|si|
3 2CCo
72
+
+2 |81|
(o² + CH)
Si
4|S1|
+ (1+ +
1 Wi-1 will 2/2
-w--11? + 2y²² 2// - -wi + 21/w" - ww
7
(34)
Proof. By update rules, we have
(z (Z) - (1 (2) - ((h(w",,u " 27 1), hewhhhwww)) 30 : ;2,,,)1)
2 ki1
(35)
Uk,k--1 (z)
2 * z 1,k11
Or equivalently,
(z) {{ { 11 - -r(u,, 1 s(
1, Whe 23,,,2)
= a
(36)
u 1-1-1 (z)
z _ I.,
N
Define Up = (u U2z u ..., u'y,k), W = N
Σ
w and
(( 2N
Σ
||u[ (z) g(W,, S
(37)
S,
zES
Then it follows that
((()) (Mā)
[l) g( 82)1?
2N
I | (z) o(w w.. S2)11 + (1/ o(Wk, x, S2), uf,(()) - 1
N
REIS!
1 (z) (
u (z) g (W we. So)1l
RES!
(u 1 (z),,,) o wL, wi, 82), (Z(,)))))) (2),,))
[
2|S
1
E
I (z) g (WT,. wI.
N
#ES!
1
B(u (. g(W],) 2. whi 25r0)) wh (2), (2T,
[S]
Big ( 2. whr 2(13b² g(We, zin wh, Sz), uf (z",,,,, 1
[8]
+
El uu (zf,..)) - ui 1
2|S
(38)
23

---

Under review as a conference paper at ICLR 2023
where
(ui (z.,,, - g( 2 2322) ui, - (z,,,,,))
-(ufj--1 (2,,,,) - g (
A. Wh, S2) k (2) k,,) g( (w/, R, W S2 Wh, S2) - - -1 1 (
+ (ul, (2) - g(
[ - g(W,
1
+ (uf, (uf (2),k,)
w/. S2))
7
S ( (Z) (.T,..)) - 2( WW
Wh, S2) - u k -- (ZT,x,))
+ 2 (2) - g( -. w,, ||u| (Z k.,,,) u 1 (z 1)12
- g k ki,k,, w/ S2)
(39)
If y S
1 9,
we have
1
7 +
1
| (z,,,)) - 2112
7
47
+
(o(w", i 2 W5
g( 2, wh, S2), u (2) - ui, (2,,
1 || (2) ui,x- + Z. WhJ 2[,(b2) g g(,,, x.,, Sc)
S
47
1
+ - I1 (2 1 -
47
S +.. 1,k, 2 Wie , (3,,32) 9( Wh 2 k,,11, Wh, S2)l
S 47 w-1 1.1,, w 23,0,2) g( (w" R S2)11 + 47 - ww
+ 44 w/1 + 4y W w-
$ 47 + 4 w w -11 11 + + w1 + 47 [| 1
(40)
Then, we have
N
1
Σ (z) -
-
1
Σ
E Ellui -(( 2, W S2)
2N
2N
Si
zE|Si|
zE|Sil
[ A (z g(wh 2 w/, 12
|| (z. - g( 2. wh, S2)11
N
|
27
27
+ 1
| (z) u A (z x 1112 + >llg(
(l -1 k,1, w- -2,.222) g(("-1 k wn 12)11
8y
+ A.il|w" - w-11 112 + 47 7. whix w/ 1.21 W/iT' 1-12
+ (uT (2%,..)) - g( 2. N5. -572) Wh 2....11 wh, Sz) - u -nf (25
(41)
Note
that Eatar || (z) 3(W Z, Wh S = Eater |1u|
g(Wh+11 1: Wh W S2)l1 which implics
2- | (2f - o(W,, W S2) 11 g(W], 2, wT, S2)112)
(42)
(11 g(W 2, w[, (z) g(W[, 2, wT, S2)
27 xES:
24

---

Under review as a conference paper at ICLR 2023
Besides, we have
(2, - 9 (W 1. 2.,,111 Wit 21,22 I MAA Wh: S2) - - 1
=B(uf (2,,,,1 - g(W" R, w 3322), (W). 2 who S2) - ur (2),x,))
+ +E(o( -/
2,,,, ,,,,,,,,,,,00
",,,,,,,,,1) - g( 2.,,
3..2 I (w) z,,,, 1: S2) - -i (2,,1.1)
x B( (z),,,1) g(W" ,,2,,,, k,1, w- - 2, u wh. S2) - g(w"=1 ,,,,,,11 w wo1,ww00 .S))
+ B(uf, - (2 - -9(w" g(w'',' , W '
2 A S2 - ui, - (2),,,1)
+ +//W-1 -- wx,x 12 + 4 [llo(w, 2 Wh, u h 111
S 10 + - || w/ - 111
1
+ B(uf (1) -((w' 1 w" 2. I( g(w"((W""' (w -.,,111 w. -f (x,,1(1,,,1))
|| w/,x11 = (ll I. Wh: S2) ui 111
(43)
where
B( (2,,x,) - g(w ,,,,,,1, w 2 I ( 11,,, W 101 SS)) u (2%
=B(uf (z),x,1) -4'00' (z k,1, + u/,0 (z g( (WW" ,,,,,,1 w'11 22)12).
g(w 1,,,,1 w" 1=11,8) (2)) - u/,0" (2( + u 1,0 (z) (z) - -.,x-11 -Z,,
1
<
-u,00 (2 k 9 ( k,1, w" .22 - -v,00 (2,,2,))
+ B(uf,x-1 (2(,a,))) - u/.0 (2 (.).)))) u/,0 (2 ( - (2),,,1)
+ B(ui, (zf,..) g( K,,,1 w 2,,22) 96 (w- , w--
: .2) - (2f,,)))))
+ E (zf - -(WW--1 A. w-1 (
(z),,.1) -
I 41ElIu. -- 11 uP.0" '1,'(2,,,0 (z 2
4 Blg I. -- S2) uu.o (z)
- -Egg( -1 2. w-1,, u0,0 (z", ||
+ 4 BlLo( -1 24,,1,1 w=11,,,) [,)) -n 1 (M || 4R| (4T. u1o0 (2,
(44)
Noting
Bllg(W" -1 k.1,1111 w- .82) 10 (z )11
Bllg(w"'1 1... 11-18) (L 1 +
- - (2
Ellg(w"'1 1, 2., wr (8)) 1 (Z uio 1)12
+ 2E(o(W"' 11 .. - - (. u. u. (z,,,,) - -7,0
(2,,,,1) -,,0'(25,,,1)
(45)
< 1
2 EBlo(W -! -1 k (r-1,8a) uh 1| + ( - -u,,0 (2)
S Blgs 2. w w0 18,) uL, (2 11 832
2
Then, we can obtain
7+1
1
(2 - -g( S[
2
N
S
1=1
zE|S
7(1
[s
+
E| Blluf(,-1(2) (z) 9(W,, w[, +
x2
(02 + +c)) (46)
2
N
|
zE|S
>332K2CB
1
72 w
12
+ 2
w"
w., 112 + || - w/1.
1811
N
25

---

Under review as a conference paper at ICLR 2023
Dividing 2+1
both sides gives
B Blluf - 2, S2)1
N
sE|si
7(1
+1
|s
B -
2, w.. S2)l
7 7+1
xE|S||
182K220
(o²
Cz)) 27 Iw" w--1112 2 w[ 21|w" -wlll
Sii
Si
(47)
Using Young's inequality,
E
El 9(W, So)1
N
RElSi
N
$
(11
7
Σ
[01 + 4|S
|E (2) - g(w S
S
N
zE|S||
4|Si|
+ (1 +
- +
27 2| - -w--112+22 ||/ - -wi,al? + 21|w" - wwll
7
<1
[ 2,
E
N xE|S!
yB2K2 K2
72
(o² +()
+ (1 + 4|Si| i.2 W will + 2-2l - 1| + //?/( - + 2/|w= - -w]l?
-w/,al?
(48)
D.2 ANALYSIS OF THE ESTIMATOR OF GRADIENT
With update G (1 - 3)) + ( + G. we define G% = 1 N
N Σ G and
Ag := | VF(WC)12 Then follows that G = - - + +
EG + GT,
Lemma 2. Under Assumption 2 Algorithm 3 ensures that
A (11 3))1 - VF(W 11 + 2 3200 N
+ +/5llwr -W 12
(49)
+ -1 5 - Dar (w")))?
26

---

Under review as a conference paper at ICLR 2023
Proof.
Ai ||0 FF
N =1(1188662 -11-- + + NN Σ (G - VF(W))]
(1 0 (1
VF(wD)
+
1 N
E I(Gi(WEN aT., (ZT.( WhT 255d)) + G (ig.t))))) (aaa))
I(G(( 2L +
(2 + GL(w"
N
1
3
(GI -
+ G2
I(Gi(W -1 Z.u. S2), w 2,,222
N
+ +G2(w"
w (s)), w/ .2.,k22)
1
B
(W 2...1.9WW S2), ..,,.,2))
N
G2((W " : w w- S2), -- x.)
(Gi(w" 2. I S2), w "_1 xz,..))
N
+ Gz(W"" :
S2), w/ =.,
= Σ (Wr 2. ( 2. ,,2), w- (
N
+ G2(W ", "3. "3 w (S,), w- (x,,,))) ,=,,)_,,,))) - VF( )r
(50)
27

---

Under review as a conference paper at ICLR 2023
Denoting 9z (w) g(w, 2. w, Using Young's inequality, we can then derive
Ai (1+ 8) (1- -1 vF(Wi-1))
+ N E(G((
S1),, wn 223112)
+G2(W" 1 1 " w- .2,,.,))) VF
+
St)),
1
1 E(G
+(1+
8
3
23722) G2( (2 (..
N
1
Σ
G2(w
N
(Gi(w") 2...
+ Ga(w"
N
Σ
I(G ". S2),, w- x
N
+ GGa("" 2 By S2), wi11 21,
3
1
Z.n T. w, S2), w- (
N
+Galw
9. 2 w- S2), S²), w (.,)))
N E(GI(W I.. 2 w S2), w-1 (351,2
+ G2(W 1. "6 , 33 "2 " S2), w
(51)
By the fact that
E
Σ (G)
-= S2), w- (2,(,12)
+ G2(w" 1 12 2 11 (S2), w- - VFF(">)) (52)
and
E|
Σ (GI(W ,2.1.,0WW F.E ,2)), w--1 (2,
0²
+ G22 , 2. 2. , w- S2), W w-11 - <
N
(53)
we obtain
-FFG:II-FF(W..... + 23² 0² C.7 9
A $ (1+
N
+ +5,ll w- -W/,l 12 + 5:8][ 12 + 558l af (2F.,.) - g(""" 2...I. M. S2))l12
< (1-3)11 VF(WL_))11 + 8202
+ +591 W wx 112 + -53l w/1p
N
(54)
1
+ 53
| g(w", 2 w,, S2)ll1
N
+ 5/
1
Σ
(35.t.)) - o( 227,, w- w-
N
28

---

Under review as a conference paper at ICLR 2023
D.3 THEOREM 2
We re-present Theorem as below.
Theorem 4. Suppose Assumption holds, denoting M = max; | as the largest number of data on a single machine, by setting = O ((M1/))
na/a ). 3 = 0 M ) = O( ass///pa))) and
K O0M0/3/R1 133), Algorithm 2 ensures that E
Σ r=1 VFF(W") 113 - 0 12//a))
Proof. By updating rules,
||w" - -w,,l1 S 12² k2.
(55)
and
|Wg - w 1
1
G < q 1
Σ
10 VF(w)) + VF(W)]]
(56)
NK
K
m=1
By updating rule, we also have
||"" w 1= 121
1 NK
ΣΣ
S 11
Σ
Gr-1
VF(W V//
K
k
(57)
Lemma
gives that
B - -
A
280²²
53
Σ
|
-W
12 +
5
Σ
| - w/
RK
3RK
N
RK
R
Σ
(z)
9(w:; ;2, S2)1
NK
Si
i,k
xES
+5 R
( g(w0-/ -2, , S2))1
NK
3/0
xES
(58)
which by setting of 1) and 3 leads to
24 3RK
480²
BIGG - VF(WDI <
N +
C10 + +27/ Σ
| (V 1)1
RK
T.k:
Bllu (Z) - 99(W"; ;2, 12) 12
22,
R
NK
i
ZES
1
+
| (5 g( 1 $2))1
NK
S
ZES
(59)
Using Lemma yields
(l) - g(W,, wi, S2)1
R
NK
i=1
ZES
4M 1
N NK
+ 18M²
Elluy (z) - g(w S2)1++
w/
R
S
72 RK
ZES
r.k
3/ 22x k² c + 8- 2 + +(A)
+ M
1
Σ
--- w- 1 + S
1
Σ
+8
Si 1
Σ
.ll
w|
RNK
7 RK
r,kkk
r.k
(60)
29

---

Under review as a conference paper at ICLR 2023
Combining this with previous five inequalities, obtain
1
Σ
El
W. S2)l
R
NK
0
M
+ +,32K² K2
+ 7 + 1
M
+ 8y 72
M i
+
N
1
E
yRK
BRK
R
(61)
and
BlIG% vF(WW)11
RK
YRK + + K2 + + + 1p M² +7+
M
7? +8/1i11 + M 1
1 BRK
+ B
+ Σ
N R
(62)
Then using the standard analysis of smooth function, we derive
F(w + ) - F(w")= S VF(w") (w
w
w²12
i.
=-NVF(w") NK ΣΣ G VF((w) + vF(W*)
2 11 w1
TH (IVF(W") )12
NK ΣΣ G - VVF(W) + I
| w
/
|VF ill NK ΣΣ
G VF(WD) + ill 1 E(VF(w)) VF(W"))11
K
L
| -
+ 2
$
17 IVF(W")1 + 7 K
Σ N
EO - VF(WD)) + " K
L
Σ k
w/
+
i
w r+ w=
2
2
(63)
Combining with Lemma I and Lemma
we derive
R Σ EE EIIVF((")) 11 0o M
M 7RK + +332K2 K2 + + + 1/ 72 + 8y + M n²²
3 3RK
N
(64)
By setting parameters as in the theorem, we can conclude the proof. Further, to get
R Σ, E||FF(W*)| & e, we just need to set = e, B K
MM
R
VM
M
E ANALYSIS OF FEDXI FOR OPTIMIZING CPR WITH LINEAR f WITH A LARGER BUFFER
In this section, we present the analysis of FedX1 with a larger buffer, i.e, B,, B keeps the history of previous rounds instead of only keep the history of the one previous round. For z E S, and z E Sj, we define
Gi 2, w/ x') Vlij(h
h(w';z')) Vh((;
(65)
G2(W, 2, w/ x²) = -Vii(h( w, 2) - h(w';zz)) Vh(w';z')
We use superscript (r- T, 1} to denote that historical statistics sampled from the buffer is computed at some round in (r - -,r-1)
1)) randomly. Therefore, the
G 1 = V (1(w.iiz,,... -r--r--1 /V((()
30

---

Under review as a conference paper at ICLR 2023
defined similarly 3 is equivalent to G1(W R, Wit ----- 2,,,,)) and the
G V hWw k.22 Vh 21,22))
defined in 5 is equivalent to G2 (2 - 2,001 W ((,,22))
We use same assumption and notations as in Appendix C Under Assumption 1 it follows that F()) Ls-smooth, with LF == 2(L,Ch + C.Lx). Similarly, G G2 are also Lipschtz in w with some constant modulus L that depend on C₁. Ce, Le: Ln.
We present the analysis in the theorem below.
Theorem 5. Under Assumption I by setting Ol Rays and K = O NRV7) and T O(1), Algorithm 2 with a larger buffer that keeps the history of last rounds ensures that
N
VF 2F(("-))1 0 R873
(66)
R
Proof.
Denote i K. Using the I-smoothness of F(w), we have
L
F(w - ((w")= & VF(W") ((w+) VF(W")((W*+1
w")
www
w012
+ i
- VF
Σ (G + GiA.2)
- -1
||
-w'l?
NK
2
< -
1 IVF(W") VP(W VP(
ΣΣ
(G + G.,,2)
2T.
NK
L w | w/12
-iVF(w
NK ΣΣ Gl + GI,22)
221 NK
ΣΣ Gi + Gf W
w/1p
- -VF(WWTT)
NK ΣΣ G. + + Gine)
(67)
where
EE iVF(w
1
ΣE. (o GlEa)
NK
-VR(VVF(W
NK Σ
(Gi (wia,, "
(2f.e)) + G2 2 wh, 2hma))
(Gi Aa
+ G2(w" (... (x([)))))
+ +W. T L... 22 + G2(w" T WT ((laaa)))))
( SA. wI + ShL?
NK ΣΣ
Ell ww,ell
- (
NN ΣΣ [CG(( (Gi(w L. 2 + Gz(w" 22 w" 2..a2)
-FF(W + VF(W
< "BIAF(('>> - SaL NK ΣΣ
El w -wi---
- 11.
(68)
31

---

Under review as a conference paper at ICLR 2023
By the updating rule,
B||w,+1
wrll
=
13
ΣΣ Gi G
NK
1
G2(W 338 wie, 2)
NK
3,122
5
2,.22 - G2
G2 aap w(aa
NK
(w 22.... WT 2jah) + G2(w B
NK
51)
NK GIIW ".
G2(w" ppee WTT, , -
+ 50/ E [FF(W->)) )?
$ 10 L'
NK ΣΣ
R BlIwE WI 1092
ΣΣ
F. w - 11 -w
NK
a²
100 NK
+ 10 B|F(W
(69)
Thus,
B|| W
r+ 12
R
(70)
4077"
1
ΣΣ
El T. - w/1 + 201 0²
+ 207
R
NK
NK
Since (.)(-) is Cr Lipschitz, we have
- 112k3
(71)
and
E w" w S
(72)
Thus,
W1 so 2( (((F(w)) (( - Fx) + 122112 (7(D2++07) + 722 +00
o²
(73)
R
NK
R Σ r=1
Set v) and as in theorem, we conclude the proof. Further, to ensure
B
S 2, we
R
just need to set = Ne2, K = 1/Ne, 7 πΙK = and - = 0(1, then number of communication rounds is R ) sample complexity on each machine is O (Ne))
F FEDX2 FOR OPTIMIZING CPR WITH NON-LINEAR f WITH MEMORY BANK
In this section, we present the analysis of FedX2 with a larger buffer, i.e.. B, B,, keeps the history of previous т > I rounds instead of only keep the history of the one previous round. We use the same notations and assumptions
in Appendix D The framework of the proof is similar as in Appendix Dexcept that we need to handle the extra error caused by the large buffer.
Theorem 6. Suppose Assumption holds, denoting M max; |S!|| as the largest number of data on a single machine, by setting = O M333
3 = O MiS0Ra75 ). 17 = Ol M )
R475
O(M7/4) and K (3 / Algorithm ensures that EE + |VF(W S 0 (R))))
Proof. First, need handle the estimator. Denote g(w1,P, W2. q) (( g))-
32

---

Under review as a conference paper at ICLR 2023
(z) = 11)) - 7( - E(h(W
i,ki
2 R. h(w
;2,,,,2
2 = K
z + z R, (74)
Or equivalently.
u (z)(()) {{ (z) 7( 7(,,,x11 (z) - ((W k, 2 1
W r.r-1 2/,022-1)
3.
,2,,022
z = z k.1
u A (2)
n. * x k,
(75)
Define 0/
(uf u2 x'y, and W wi. We have
1 (z) - 2WW,, wi,
2N
zeSi
1
E
1 (2) 9 ((W wh, Sa)ll (u]) 2, u.,x - -
N
S
RES1
2 || (z) n(/x-1(2)1
Σ
u (z) g( 2, wr.
N
S
x6
+ |8||
(u (2 g(w( wh, Sz), (ll.(() =
1
+ 2|5
| (2f,,.) 1
1
E
g 2 2.. (z)
N
Si
RES1
+
(u,, (2f, - g(w,, ZE...,, w/a 22,722 x-r--1) u. (Z),,,)) u. (2f,,,)))
[S
1
(g( (w k,, w W/r
2312 イ- g(wl, 2I,,, wh, Sa), uf, (2.,,,)) uf -1
[S
2|5
(76)
where
(u (2) - g(W Z. Wie
(
(2f,
j,,
(ui (2),).)) g(W Z ----
T-T
2. W/: S2) u i (z) 1,,,.111 (,,1))
j.t,
+ (u% (z. g(W),)
--
r.
(zf,..) g(W/, 2. wh, S2))
jtt
-uuf (2) w.1 g(W/, 4.
2. 82) 2
j.t
(ul (z
k. u.
R,
g
Wh 2 Sa))
< (u, k.11 g(W/ k
-- ) ( z w S2) ui (z)
j,,,2
(1|1l k- (1. (w 2. we, S2) 3 | (2.,,.) (2),
27
[ [(.]. 25, wL, S2)1
(77)
33

---

Under review as a conference paper at ICLR 2023
If y g, we have
2 1
1
2
2
/ - 1
47
+ (o(w : 2,,, 3,z
--r--1
20222 2)(00=1) - g 2, Wh, S2), ui (2,,,,)) 11
S
||u|a (2%,).) 11 - 1i1x-1 (2 11 + >llo N. R. W -i 3,,222 ) - و WW 2.A Wh, S2)1
4y
1
+ 47
|| (2 k. - 11)?
*119( Wh N. 2 We 11 2-- g Wh 2.K,11 S2)1
32,2122
I 47119(w"' -- ,2,,k,1; w" .2,,122 --trr11 - g(w ,.1,1:: """ ,2)) + 1
+ 47 W/ - w² + 47 W - -1-112
w1
w 11 470² + 47,4l wl 1| + (// w011 + 47
(78)
Then, we have
2 |lub - a
a(wi)]1
S 2
- -
1
1
1
+ N
Σ
| x- (2) - g( Z. wI.
_
|||u (2,, - g(W R wE, S
S
27
27
7 +1 1
||uT (2,,
ui (1),, + 711g( 2. w" (,,5112) -g(w" 22 w S2))1
8y
+ 1//L/w"-
11
112 + 4 W w + 41 4>1 w==111
+ (0f,--(25,..)) g( 2.,,,
0 (W/, Zf,,,, WI, S2) - -r, (
(79)
Note that Expar, (z) - S(WE+1 2, W W S2)1 = Enttree, 11
g(W 2, We 12 which implies
(Iluf s(W 2. we, S2)l - (2),,,)) - g (Wh 2i,. WK, 82)1?
2y
1 Σ
(80)
g(w6 z, wp, 12) (2
[ g( z, WT, S2)11))
27 zESi
Besides, we have
((0,)--((%,..)) - g( (w k1,1111 W5 W -- --
34,,,,2 ), g (W K S2) uf (2,,
(2), (2 - g(W g(w"-T 2 k,1,,,, W- -- g( k. wh, S2) - -
=
j,t
+ [Egg(W ",, 2. W"T
",,,0,2" ------ 1) g( :
Wi: 2.,4,1 w/: S2) - - (xf..a))
< B - 9( (W ". " w-' 23
9( "w--, "-',,,,,,11 ,2/,,,1 ,
+ ( - -9(W- , T 2,200
k w" 88) x-/x-1 (2
+ - -
4 |19(W", 2. wh, S2) u x - (Z% 1|
< 1/ s(W'1, 2., 4002 - 112 - || 1o5---r-pp w-
7
+ ( - -g(w-1, 1 2/12 --- g w - 2 w --r--- (2)) u. (2
w w(ull |lo(w, 2. wh, S2) -i--- (z% 1)1
(81)
34

---

Under review as a conference paper at ICLR 2023
where
B(ui, (2,,2,1) - -9( -0 TT0-- 1 w 22)22) -o--ww--- ---1 2 2 w" ",',,,)) - uf. (2,,,,)))
1 (2 + (2%,a.1) g(W" R.111 W 3,,422 1--1111
g(w" ,2,,6,1, " .S)) - u (z + 4/,00 (2),),1 1 (2),),)
< - (x (,),,,)): g( (w' 2 "² - _ (z(,):))
+ A (2,,,,1) -u/,0" "z, k. .) 4/,0" (z),,,)
u 1 (z,,,,1)
+ "( (2,,,,1 g(w"= M.1,1,1 w" 3,1,2
7,
).g( (WW"= ,2 w w- ( - (z),,))
+ BBul,o" (z,,,,)) - -S(W'T, N w-, -.
) _,000" (2],,,,) (2,,,12([,,1))
J1.2
S <4E||u, - 1 (2, -
+ Ellg(( -
(T= ,, "T=)) - - (2),
-llow 2 k,,,,,, ,²) - -u (z(,,,1 112
+ Bllo(w - 2,,1,11 ( -u,o " 11 + 4 - " (2
(82)
Noting
- "llg(W" - 2,,1111 W .S2) N0 (2,,,11)
=-Bllg(w" 2,1, w" (5)) (. + (Z],)) u (2,,,,)
.62)
= -Bllo( - 2,,,,11 "=TT,8)) " I1 - Bl - -p,o (xfx
+ 2B(g(W "W"T A,1,,111 W"T,,,) - 4/
(83)
S 2 Bllo(w'- ......1.. (80) u.
u x11,
S Bllg(w" "T 2., w S2) uf 11 8.3 K33
Then, we can obtain
7 + Bllug g(w S
7(1 1811
2202
E. 1
2
2
S1
(84)
+ + - w 1 + + ??| w1
Dividing 2
a+1 on both sides gives
Blluu - g(w [(WW)) =1
AP: E u g(
g(wp_1))1 +> w- 112 + 1
wfll2
7²0²
+ mm
+
Sii
(85)
Next, we deal with moving average of gradients, i.e. Ge With update G, = (1 - G) +
N
3(G 1,111 (T,,,)). we define G% ス Σ G and A |6 VF(WF)) [P. Then it follows
that G (1 (11-B)G%-11 + + Σ, (. + G C.
35

---

Under review as a conference paper at ICLR 2023
We get
4% 10% VF(W?))1
= =1(11-3)6 -B) - -O- D(G G + G.,.2)) VF(W212
11--8
(1 () - VF(WE-)) + (1 3)(VF( - VF(WE)
1
E (G2(W L (F, 1) W3/7 23,22)
+
N
1
N Σ
+ G2(W""T 2yye D. 21x2))
+ Σ [G](W 2.
w" 23,22)
+ GG2(W 2ff (2),7'1 w x1,2,2))
1 (G Z. I. wi, S2), w' .2,1122 25,22=1)) )
N
G2(W" 1ppeet1 g(w" 2...1 " w' 2.,k,22)
+B 1 [(GI(W' 1. W", S2), 2,,022
G2( gWW" .ل....1 "" w"= T =xf,22))
Gi L. 2 S2), _ 11
+ G2(W ". . -g(w" 3.. ( -"= (1,222))
+
EEG(( T, (w ,,,,,, ",,,, 1
N
+ +G2(W , gg(W 12,,0 WTTT,8)) w" w" xx,22)) VF
(86)
36

---

Under review as a conference paper at ICLR 2023
Using Young's 's inequality, can then derive
A S (1 8) (1- -B)(G- VF(Wi-1))
1 N E I(G "2.11, "....."",, w--r, (2,,22))
+ 3
+ +G2(W"
,yyyes :9wW""' .py S2),
(82), w- (.(,,2)) - v+(wi))
+(++ 3/10 NN EiGi(WER T. ( W v.r- 2iir2 1
Gi((""T 2 uf uyye
+Galw577
(2) ) wh 2.,)))
Σ
N
+Ga 2. (1775 " wh. 2(
(W 2h
"2 + Gz "a(w"-" ","""""p,," 22 " (((n)))
N
N [GI Z... w", S2),, w- _., )
+ GGl(W"T 2i "lw" aa ,w",, S2), w" 2(,,,2))
1
B
Gi Z.N dha St), (.,.5b2)
N
+Ga(w" 2... a " S2), w' 2(,,,2)
E (GIWW 22.. 2h.. W "" 22/02
+GaW" -p...9WW Lag ,2), wi 2,,,
(87)
By the fact that
BI
1 N
Σ (Gi(W"
2. " w S2)), w" (2,,a,))
(88)
+ G2(w" ( "oww ",, .S)), w"- (.=,,,)) [F( =0
and
E
(GI(W"
g. k W S.)) w- ",,,,,"" 2
N
+ G2(w"-1
-- ,9(w' " (2). wT (. VF(WD]12
(89)
0²
N
we obtain
4 (1 + B)(1 - -PF0---PP(WL-)I + 2,3203
N
5.8 w w/a1l - 5/8[ w/ + 5,8 |L (z), - g(w", 2. S2)))
(90)
I (1- 3)1 - VF(WE- 2 +2 8202
+ +59ll - wi + 5,81 -w
N
+ 5. (.,,,u., - 92i,,, (w ???
37

---

Under review as a conference paper at ICLR 2023
|
W 1 NK
(91)
G VF( + VF(W
K
Then,
E 4
K
k
$ (1
8
Σ
4 8802
+58
ΣΣ
w
W 1|
(92)
2
NK
+ 10 (2 g(w", , w", S2)11
Finally, we can analyze the convergence of the VF(w).
F(w F(w") S VF(W") [ (w w") + 2 ||
||""11_w'1?
1 ΣΣ G. 2 | r+ w012
= =-iVF(('T
NK
= -DVF(W")
NK Σ
G - vP(W") - VF(W7) + -1 - w/1l
= I
" 2
VVF W )12
+ "
NK ΣΣ
G VF(W")12 + ; 1| w/12
2
S 2
VF((")) 12
NK ΣΣ
G - I
k E(VF(w)) - -VF(W))
+
i NK
<
ΣΣ
GT - VE(WD))
ΣΣ |w w0ll
2
NK
+ / 2
(93)
Noting
Iw w/ S x2220000
(94)
With similar technique to Appendix D except that we have an extra error term caused by the larger buffer, we obtain
E
M 7RK
M² + 7 1²
M 22 MyMi + K 2
1
3 +
<
NN)
BRK
(95)
By setting parameters in the theorem,
conclude the proof. Further, to get
EE, M
? < 2 we just need to set 7 O(e2). 3 o vi
)
R = MM
K = =
38

---

Under review as a conference paper at ICLR 2023
G FEDX WITH PARTIAL CLIENT PARTICIPATION
Considering that not all client machines are available to work at each round, in this section, we provide an algorithm that allows partial client participation in every round. The algorithm given in Algorithm 3 We use the same assumption as in Appendix D The convergence results will be presented Theorem 7
Algorithm FedX2: Federated Learning for CPR with non-linear
1: On Client i: Require parameters 77, K
2: Initialize model w 44, (u²(z) (z) 0, Si}, Go 0, and buffer Bi, Br,,, C;
3: Send H4,1 H..,2 24 the server
4: Sample K points from Sj. compute their predictions using model wΩ. denoted by 7/00
5: Sample K points from S2 compute their predictions using model 1.0 denoted by H
6: for L...., do
7: i E Pr then skip this round, otherwise continue
8: Receive RT 2, pr-1 from the server
9:
R with shuffling, respectively Update the buffer Bi, 2,,,, C, using RiT R pr-1
10:
Set H 0, H4 0,24
11:
for k= 0..,,
do
12:
sample two mini-batches of data Take next h hi-1 and wp-1 from B₁, and Bi, and C, respectively
Sample 2,,,,1 from Si, sample 2. from S
13:
14:
Compute h [W 2,,,1) and h( ((w..:: 2),,,2)
15:
Compute h( w k. x...)) and h( w.,, (7,22) and add them to Hi Hi respectively Compute uf (z" (,,.1) according to (8 and add it to 4,""
16:
17:
Compute G and G,,,,2 according to
18:
GR = (1 - B)G
33G G ( W = W -
19:
20:
end for
21: Sends Wi, Gi,,A the server
22: Send H H4,g, to the server
23:
Receives w", G from the server and set wr+ Wr, 07,00 Gr
end for
25:
On Server
26:
Collects Hº = -1 UHL UH and = Ut uuf........ U2S, where = 1,2
27:
for for.=1,.... R do
28:
Sample set pr of clients to participant this round
29:
Broadcast w" and Gr to clients in pr
30:
Set R -H R HD, p 11 and send them to Client for all i pr r+1
31:
Receive r+1 G
(r+1 from client E P", compute w+1 | Eiepr W, Gr+1
EiEpr Cx++1 K
Pr
32:
Collects Hr+1 UHH Vi pr and u uuF Vi E P., where 1,2
33:
end for
39

---

Under review as a conference paper at ICLR 2023
G.1
ANALYSIS OF THE MOVING AVERAGE ESTIMATOR
Lemma 3. Under Assumption the moving average estimator u satisfies
N
1
E
(2)
s( w,, S2)1
N
xE|sil
7
IPP
(1
[BB| k- (z) 1WW 1
16
S
S
zE|Si
N
72
pr
36
+
2 - - w||l +
(o² +0) +
P|P
S1
N
S N
1P|
11 + & |M||
+ 8 N
[?|l
w
|| -wll?
N
+ 8(72
+
1.2 1
w| + 2()² +
1.2
N
8
NK
HEP
KEP
k=1
Proof. Denote P as the clients that are sampled to take participation in the r-th round. By update rules of we have
(z) u (z) - r(uf (z) e(h(w, x.,,,),, hw (122))) E Pr and xi,,, otherwise.
u (Z).
(96)
Or equivalently,
u (2) { u 1 (2) - -u (2) - g(w i
2 k,1, WiT". 22,,2)), i P and z K otherwise.
u ki (z),
(97)
Define up: (uf up U2, u'y,)), W/
1
Σ Te
Wi,
Then it follows that
2N
S
xE|S!|
E
I (z) g( z, we, Sz)l
N
zE|SH
+
(ui (z)
g( 2, We. Sz). (z) (x)) ş [ll[((()) - u(x=)(=))1?
Σ
E Ellui k- 2 S
2N
|S.]
Res
+ E N
Σ
[u, k- (z g(Wi, u. wi, Sz), (Z..a))).)) ((.x-(((.R.1))
SS
B ( 1
N
2|8
Σ
Elluu - (2) - g(w[, 2, wT. Sz)ll
2N
S.
#ES!
E
a- (2T...) - g(wi, 2f whit 2.r.)) (2T.k))) -.
S
(g( ( k, 2 wT. ) g gW we. S2), 1. -1
|
Pr
Σ
1
S|5.
ie
(98)
40

---

Under review as a conference paper at ICLR 2023
where for i P it has
(u g( (W R, Was (1,2) u (2),A,) - ui -25
(u],x-((z,,,,)) - W. K.
2, Wh. S2) u 1 (2,,,,1))
+ - - g( o(
g( 2 1 W S2))
(u[j ( 9( (WW.,
S2) u (1,
+ 1 (u/ 1 (2f,x,) u
S2))
(99)
?
= (u (Z) - =g( z
Wh. S2) - -i (z
+ 27
S2)11 - (2 -i k21, - -Iluf - g( W , W S
(1 A (2.,..) - g( Wh:
If y 8, we have for E Pr
1 - 1 7
E
-/, - (2
2
4y
+ W[g(( 1. 2 K, (3,.72
(h A. wh, S2), u (2),..) - - (2
$
El Bl (2)
1 (2 2| Ell 2i,,,, wfi7 23/(h2) - gl W/ 2i,,,11 W S2)1?
4y
+ L Bl
1 12)2
I Alllg( I. whe
r-1 : -2,022) - (. I WT. S2)11
S 4,:Bllg( (w' 2/ 1: w"11, , (25,72) - g( (w-- -1 2T,,,1 w--1 ,2)11 + 4 IT - 11
+ 4 Bll,'
w/| 1|2 + + W 112
$ 4400² + 47 1 w 112 + I T.,,. - -w'12 + 4y I V' - w- 1112
(100)
Then, we have
N
E U (z) -(( 2, w/. S2)1
2N
S
ZE Sil
<
E Bllu Eluu (2) - (( 2, S2)12
2N
xE|Si
27 E Bllu" (2) g(W] k, S2)12
|
iE
1 | El (2 g( Wh wh. 12) 7+1
|n 2. - uT (2 +4
2n
8y
+ 4 ? - -w--1 112 + 4n PE w w/ + 4- L w/a -=-
+ =E( (2),,.)) g( Whel (.r2)) 9( (W 2 S2) -
(101)
41

---

Under review as a conference paper at ICLR 2023
Note that for i E P", Exser 1 - g(Wg, Wg, S2]1 Exper [1(]x(z)
((W Z, w S2)l which implies for i E Pr
g( k Wh s2)1 - (2,,,,) g(W Zi,,,11 wh: S2)113)
2y
1 (1lu)x
(102)
(2) - 2W 2, W/: 82) || - | (z) o(W, 2, wh 12)
27 =ESt
Since ((-) - Co. we have that ||.())]1 v C.. (z))2 2 C9 and
|| (z) u/,0 (z) S K2
Besides, we have for E pr that
B 1 g(W,,,; 2i,,,,,, whe 23,22) 2 wis S2) -i, (z,,,,))) ))
nI, k- (z(,2 1)
B( (x),,.)) g(w"= K.
+ B(g(w" ,4,,111 w" 22,12) o(wlx a.1 2) ol (wi. 2.,11,1 w S2) u -- (2),
< 1 - 9(w"" 1 2 w 33 (wh, u. S2) g(w" , w , S2)
+ B
g(w"" -, w 3,,22)
2. w/ w ,.) 11,,-1(25,,..)
+ 2i'E|W" BBWWWW"-- - -w" 111 + 2/ - wl + B / w/,
1 BBllo(W 2.,,,,1, WK. - us (2
+ 4
$ $2/00 + 7 1 w" 112 212
1
+ B(uEA (2F,,,1) - g((w" -1 k. w-1 "1 (2),))) g(w))g(("" g(W 1 25 w (2)) -2,,-1(25,,,,
+ 2T. (W" - 111 + 2..2 2.. w whuull + 1.2To| w//0'11
+ FIlLOWW" 25.,,,1 S2) - uh (xf,,,))
(103)
where
E(u 1 11) g( ,z,,e,,, w-1 - g( (W" k, w- [82) ui -- (z.((z)..)))
= =B(Uuj (Z,,,,) - -u,,0' (2) 1) + -u,00 (2, - -g(W-- , w-1, , 2 -2,,72)
g(w" k11, --'1, u//0 (2f,,,1) + 4/,00 (2),,,) -f (2)
< B(ujj,n- (2),,,) - 17.0 (2 9( (w"
2 k,1, w 1- -2) - -u,00' (2,,,,1))
+ -(u (24,e.1) 11,0" 1)),, 00 (2) - (2),
+ B(u (z(,,.) - g(w"" -1 -.1.111 w (
), g (w" 11 ,,/,,,1, -- (.,) upoo ())
+ B(u 1 (z g(ww-- 1 w-1 1,,
4/o0 ( - 1
1
S 4E||u/ k 1 (2), - -u/00 "1,00(1,,,, 1) 1
Ellg(
( , w - -ui,o (2[, (z)
4
Elg((w k,1 1 u/,0= (21
1 Ello(w"
+ 4
(1)) -u,6'' (2 + 4B| a- (z(,,,1) u/o0 (z,,,, )|
1 S 4E 1 (2%,..1) 2 Ello(w- -1 2. w"-1,S,) -u/,0 (z],,,)) 1|
2
+ +882 K2
(104)
42

---

Under review as a conference paper at ICLR 2023
Noting for i E P
Ellg(W K. W .S) L0 ( k,1, 1|
--Bllg(w 3,, w/ (.))
u (2) + u - 4 (2 1|
--Elgg(w ,,,,,, ("11,,)
4 - - 4 (2)
+ 2E(g(W" -. w-1, (22)
- (2) 1 - (2
S Bl 2 k,11 w-
" (2))
8 | (M " R111
2
1 (W k,11 w- (2) u k- k. 1|1 8 K2
1 -
S ( a. wh, S2) - (4 R. )|
(105)
With the client sampling and data sampling, we observe that
E
Σ
lo(wk
R,,, Wh: S2) 1
N
IEP
(106)
P"
B M...
llo(( (Wk 2.,,,1 S2) -
N
N
es
[
Then by multiplying y to every term and rearranging terms using the setting of y S 0(1, we can
obtain
7 7+
E E (z) - ST S2)1
2
Si
i=1
SE|
(11
IPT
S|S
E BlJu x- (2) - g(W (2)
W/, S2)1
2
S
sE|si
4..1
8 3 K2 C
Pr
|PT
W - -- 112 + 4i2 |
(0" + +(8)
+
4
w"
w|ll"
|
S
N
N
K
+ +4(72
E W - w
12
(7
E
w
11.
|8
N
S
NK
Pr
tEP" k=1
(107)
Dividing
1+1 2
on both sides gives
E
(z) - g(W S2)1
N
S
XE S
7(1
|PT|
1 N
8 S
E U. x- (z)
g(W 2, W S2)112
Y +
N
S
zE|Si
2 pr
16,,3
K2C
CH pr
|r|
Pr
+ +8-
(a2 + C2)
+
+ 88.2
Iw" - w 1- +
88.
|
S
I
N
N
K
+ +8()2+ +
1
w|, + 2(72 +
i?
E
w
i,k 112
N
si
NK
Pr
PEP
k=1
(108)
43

---

Under review as a conference paper at ICLR 2023
Using Young's 's inequality,
E
E (z) g S S2)11
xE |S1
- (1 Y PM|
N
7 |T
Σ
Σ
(1+
E 1 - g(w 2, 12)
8|5|| N N
|i
|6 N
i=1
zE|si
+ +11 + 1 N
1.2 w will
P|
P"| |
16 Pr
PM
lw"" -w"-w"" 11 + 88² PM
+8
(o² +
+
18.2
"w"----11"
N Iw -wxl
|S
N
K
+ +8(72 2 +
Y
||
w 11 + 2(72
7
] 1
E
Bllw"
W.n'll 112
S
S
NK
iE
Pr1
N
<1
B A (z) - 9 (W 2, W S2)11
16 |
N
S
1=1
ZE|Si
N
N
72 IP"
(0² + -0)+ 16 x2 22 Pr
+
1 W
wi +8
7/p'
SH N
| N
|P'|
Pr
+8
[''l 11 + 8ï
|w"" -wil
N
N
Σ K
+ +8(72 +
7 12
Σ
| - - x| 2 + +(
+
7
12
E
w
W 11..
[8i
Si
NK
iE
G.2 ANALYSIS OF THE ESTIMATOR OF GRADIENT
With update G = (1 -1-98 -L-,, B(G + GT,,,),, we define G = [.
Σ G and
iEPn
A%. = |1G VF(W))1 Then it follows that T% (1 - (1-8))01111 3
Σ (GT, G.
sEP
Lemma 4. Under Assumption 2
Algorithm ensures that
8 o
A S (1 11-3) - VF(W
N
+
Σ
4i -. - w0 4i'E| w
W
1p1
+ N Σ
4i W
w111
N
+ 2 N
Σ
i.PBlIu (2 g( 2 W S2)1
13 ( (357 g( gWW5 2 W ,5)))
+
44

---

Under review as a conference paper at ICLR 2023
Proof.
Aj ||0| FV((W
-|(1-8)6% + |Pr
Σ
(G. + Gi,,,)) - VF(WE))
SEP"
[1 - 11-1(
(1- (VFF(WLL)))) - VF(wE))
+38
Σ (Gi
M... ul W + G2( 2y u u7 ( (..
[PT
(G1(W" "1 9. 2. (,),,,),, w--1, 22,,122)
+ Ga(w" "ww. 33 w " ,8)), ,S2), w/ z((2222
B
(Gi(w A.l,,, 2 S2), w--l ,
P
IEP
G2(W" ".....o y S2), w' x.,, - VF(W)) )|
(109)
Using Young's inequality and L-Lipschizness of G1, G2, we can then derive
A S (1+ 8) (1-
B [P
Σ (Gi(w "(un,, 2 (2)), wr (15,,2))
sEP
+ +G2(w" 2. M. S2), w ..(..))) VF(W
-11+ 1
8 8)08²
4L A 44%" 11 + N Σ
ai A W/ w11
Pr
+(1+ + 1
1
(
9 2,,,,, S2)1
SEP"
L'Ell - s(W 1 1.
wa s.]]l²)) w
(110)
By the fact that
Σ (GI(W"
25 2. 2 w- 182), w--1, 22,72
Pe
+ G2(W"11
22.. - -...1111 w- S2), S2), w-11 k,,, VF((-+)) = 0,
(111)
and
E
(GI(W-11
2. k -- S2), w -
Pr
iEP
VF VF(W-1)113 v σ²
+ G2(w"
.2 ---1 (wo-0(W-___
,25.0.1 w--1, SS2), w- -- 2(,,,
|r|
(112)
45

---

Under review as a conference paper at ICLR 2023
obtain
S (1 3)110111 - VF(W1-1)1 8o8
A
|
+ 2/3
Σ
AiZRI/WT w' 1/.2F//ww - -1= +
Af.2TE) w yo.t - w0
PM
P
sEP
sEP
+ 23
Σ ((
9 Z,,1,, S2)12
Pr
iEpn
+L (25,)))
We " ,s))1*
G.3 CONVERGENCE RESULT
Theorem 7. Suppose Assumption 2 holds, and assume there are least [P] machines take par-
ricipation in each round. Denoting M = max; S as the largest number of data on a sin- gle machine, by setting 7 O 2 (MPP1)375 ). O M PIya7s) γj O (apppes
N2/s
N2/3
and
K =0 (0000(/0000000 (M Algorithm 2 ensures that E D R N178
|VF(W')1 - 0 (
Proof. By updating rules, we have that for i E P",
|w" w 1|
I 12
(113)
and
K
[ w' 12 = 172 PrlK
Σ f=
Gr 12 < 1|
1 K
Gr - +
VF(W..I1
m=1
(114)
Similarly, we also have
K
w-11
1
G 112
pr
Pr k=1
(115)
K
Gr- VF +
K
Lemma
yields that
A
3a²
BIG - VPG
RK r.
3RK
Pr
+2 2
AL - w/| + + w 11
4i El' Ell - 11
|Pr|
p
Pr
2E
[ g(w", z, w", Sz)ll
R
Pr
Si
ie ,k
zest
+
[ - g(W6)) 2. w/ "
xES
(116)
46

---

Under review as a conference paper at ICLR 2023
which by setting of 77 and / leads to
2 3RK
480²
E
G
VF((D) v
+ 110 + +2i² R Σ
/FF (w ?]
RK
[P]
+
Bluu A (z) g(w";"'w"""" 12 S2)
NK
Si
i
ZESi
5
B Blluy (2)7..)) g( ; S2)11
R
NK
ZESi
+ 5
Bl|w"
W. 11?
R
K
P
Using Lemma yields
(l 3WW WW: S2)1
R
NK
xES;
16MN 1
El g(W. 2, W0. S2)1
r/p" RNK
S
ZESi
40
L w/l2 + 150 + C() + 22668
3/PPT RK
r,k
1281,2 18i1 ? (1|W"
w- 1| -w"-1133
K E
150(7/811 + +1i.
1
|w" wl + 32(715/1 + +1E
W 113.
N
NK
Combining this with previous five inequalities and noting the parameters settings, we obtain
N K
BlluC, - g(W 2, Wk,sS)))
R
NK
ZESi
S 0
MN PR
+ 1
M2N2
+ B K2 +
1/2
1
+
3
+
1 R
Σ
P/?
3RK
P
and
BIGHT VF(22)1
RK
r.k
00
MN
+ M
721P11 + + + 3K2
M
1
1
+
3
K2
+
1
Σ
PRK(P|
?
3RK
P
R
(117)
47

---

Under review as a conference paper at ICLR 2023
Then using the standard analysis of smooth function, we derive
マタ L
F(w+t!) - F(w") - VF(W")"(w" - - +
w r- -w-11
+ 2 - [|
= =-iVF(w"
Σ G. - VF(W")+ + VF(W9)
NK
= -=llVF(('')
1|2
" 2
V VVF(w")
ΣΣ Gx -VP(W(
NK
+ 2
|| w'12
(118)
VF((FF()))) 1| 7|1 NK ΣΣ OT - VF(W2))]
<
2
[(FF(w)) - VF( )|1 + I
+
rl
K
< "
VF((w)) 2
ল Σ IIN Σ (TTT VF(WE)112
1
La - w1 +
* K
Σ
w
w/12
Combining with 117
1133
114p. and 115 we derive
R Σ BIIFF(W")) 12
1
MN
+ +1
M
M 77 72 + 3²
1 7 3RK
+
( |P|
B
7M
TRK|PI
By setting parameters in the theorem, we can conclude the proof. Further, to get
# Σ, / e2, we just need to s 0 0
0 -
R = O N )
H STATISTICS OF DATASETS AND MORE EXPERIMENTS
The statistics of the datasets we use are listed in Table
Table 4: Statistics of the Datasets
# of Training Data
# of Validation Data
# of Testing Data
Ci
24000
10000
10000
Cifar100
24000
10000
10000
CheXpert
190027
1000
202
ChestMNIST 78468
11219
22433
Here we show some experiment results to verify the effectiveness of the larger buffers, the analysis of which given Appendix and F We focus on the task of one way partial AUC maximization optimized by FedX2 algorithm in the experiment section. Recall that with the larger buffers, just need to keep the last T rounds of communicated history in B, B, instead of the just keeping round's 's history. With large buffers, would provide each machines with larger
the previous pool to sample when computing local gradients. It would possibly help enhance the performance in local steps. In Figure 2 larger buffers. We can see that by keeping some larger 7 can improve the performance. And we have further verified that FedX2 can tolerate skip big number of communications.
denotes the Algorithm 3 while large refers to the algorithms with
48

---

Under review as a conference paper at ICLR 2023
Cifar10, PAUC. FPR 0.3
Cifar10, PAUC. FPR 0.5
Contrallae:
6-32
K-128
Cantrnlluedd
K-32
K-128
c.18
Y.44
K.1AA
PMC
PMC
0.20
6.70
0.74
0.70
0:70
0:77
6.79
0.00
Y12
1-4
7-139
0.00
Y1.
3-4
7-13K
Figure 2: Fix N, Vary K,T 7
49


Reviews:
[{"review_id": "q1Bld6Uy7EE", "reviewer": "Reviewer_gCnF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "Strengths:\n- There are interesting ideas in the paper which could be useful for solving certain machine learning problems in distributed settings. \n\n\nWeaknesses:\n- 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hJQW3fFEVD", "reviewer": "Reviewer_99hj", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. \n\nIn 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. ", "strength_and_weaknesses": "Strength: \n1. This paper proposed two algorithms for federated CPR and established the best-known sample complexity results.\n\nWeaknesses:\n1.  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.\n\n2. 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. \n\n3. 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. \n\n4. 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.\n\n5. 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? \n\n6. 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?\n\n7. 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. \n\n8. In the numerical part, the authors use \"iteration\". Does it count as the product of round $r$ and communication interval $K$?\n\n9. 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.  \n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_rc5SgK53mB", "reviewer": "Reviewer_iaiV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. ", "strength_and_weaknesses": "Strengths:\n1. Solving compositional pairwise risk minimization problems in a federated setting is a new and interesting problem.\n2. The analysis of the \"lazy\" components necessitated by the communication restrictions in the federated setting is non-trivial.\n\nWeaknesses:\n1. 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.\n\n2. 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?\n\n3. 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject