Communication-Efficient Federated AUC Maximization with Cyclic Client Participation
Authors: Umesh-Vangapally
Wenhan Wu
Chen Chen
Zhishuai Guo
Venue: Accepted by TMLR ()

Abstract: Federated AUC maximization is a powerful approach for learning from imbalanced data in federated learning (FL). However, existing methods typically assume full client availability, which is rarely practical. In real-world FL systems, clients often participate in a cyclic manner: joining training according to a fixed, repeating schedule. This setting poses unique optimization challenges for the non-decomposable AUC objective. 
This paper addresses these challenges by developing and analyzing communication-efficient algorithms for federated AUC maximization under cyclic client participation. We investigate two key settings:
First, we study AUC maximization with a squared surrogate loss, which reformulates the problem as a nonconvex-strongly-concave minimax optimization. By leveraging the Polyak-Łojasiewicz (PL) condition, we establish a state-of-the-art communication complexity of $\widetilde{O}(1/\epsilon^{1/2})$ and iteration complexity of $\widetilde{O}(1/\epsilon)$. 
Second, we consider general pairwise AUC losses. We establish a communication complexity of $O(1/\epsilon^3)$ and an iteration complexity of $O(1/\epsilon^4)$. Further, under the PL condition, these bounds improve to communication complexity of $\widetilde{O}(1/\epsilon^{1/2})$ and iteration complexity of $\widetilde{O}(1/\epsilon)$.
Extensive experiments on benchmark tasks in image classification, medical imaging, and fraud detection demonstrate the superior efficiency and effectiveness of our proposed methods.

Published in Transactions on Machine Learning Research (01/2026)
Communication-Efficent Federated AUC Maximization with Cyclic Client Participation
Umesh Vangapally*
Z2008841 @students, wiu. edu wwnu25 www.20@unce edu chen. Sécreo. uef. edu 2guo Reiu.. edu
Wenhan Wu
Chen Chen
Zhishuai Guo"
Department of Computer Science, Northern Miinoi University
Depertment of Computer Science, University of North Carolina at Charlotte
Center for Research Computer Vision, University of Centrol Florida
Reviewed on OpenReview: https: www.//peee.neeeeeeeeee net/ forum?
id= formmm 18yPFLb VBy
Abstract
Federated AUC maximization is powerful approach for learning from imbalanced data in lederated learning (FL). However, existing methods typically assume full client availability, which is rarely practical. In real-world FL systems, clients often participate in cyclic manner: joining training according to a fixed, repeating schedule. This setting poses unique optimization challenges for the non-decomposable AUC objective. This paper addresses these challenges by developing and analyzing communication efficiefffi algorithms for feder- ated AUC maximization under cyelic client participation. We investigate two key settings: First, study AUC maximization with squared surrogate loss, which reformulates the minimax optimization. By leveraging the Polyak-
problem as sanconvex-strongly-oooo Lojasiewicz (PL) condition, we establish a state-of-the-an communication complexity of ((1/e/2) and iteration complexity of Ō(1/c). Second, consider general pairwise AUC losses. We establish communication complexity of O(1/c²) and an iteration complex- ity of O(1/e*). Further, under the PL condition, these bounds improve to communication complexity of ((1/e//3 and iteration complexity of Ö(1/e). Extensive experiments benchmark tasks in image classification, medical imaging, and fraud detection demonstrate the superior efficiency and effectiveness of our proposed methods.
1 Introduction
FL enables collaborative model training without centralizing raw data, making it invaluable for privacy- sensitive domains like healthcare, finance and mobile computing (Pati et al., 2022; McMahan et al., 2017: Konečný et al., 2016; Hard et al., 2018; Kairouz et al., 2021c). However, most FL research focuses on Empirical Risk Minimization (ERM) (Yu et al., 2019b; Stich, 2018; Mohri et al., 2019), which is ill-suited for imbalanced data, as it minimizes aggregate surrogate losses that do not directly address model bias toward majority classes (Elkan, 2001). In contrast, directly optimizing metrics such as the Area Under the ROC Curve (AUC) has been shown better capture performance under class imbalance (Ying et al., 2016; Cortes & Mohri, 2003; Rakotomamonjy, 2004; Yuan et al., 2021b).
Building on prior work (Gao et al., 2013; Ying et al., 2016; Zhao et al., 2011b; Kotlowski et al., 2011; Gao & Zhou, 2015; Calders & Jaroszewicz, 2007; Charoenphakdee et al., 2019a), deep AUC maximization problem can be formulated as:
min Egss, Exes. (h(w; ((w;::) weR
(1)
where S+ and S_ denote the sets of positive and negative samples, respectively. The function +(.-) is surrogate loss, and h( 2(w;2) represents the prediction score of input data z by deep neural network

---

Published in Transactions on Machine Learning Research (01/2026)
parameterized by w. Recent work has extended AUC maximization to the federated setting (Guo et al., 2020; Yuan et al., 2021a; Guo et al., 2023a). Guo et al. (2020); Yuan et al. (2021a) studied AUC maximization with a squared surrogate loss, reformulating the problem as a minimax optimization without explicit pairwise coupling. Guo et al. (2023a) cousidered a more general pairwise AUC formulation by allowing clients to share prediction scores. However, a major limitation of these methods is the assumption of full client availability in every communication round. They either require all clients to participate or randomly sample subset each round conditions rarely met in practice. Real-world FL systems often exhibit cyclic client participation, where clients join training in a fixed, repeating schedule (Cho et al., 2023). Cyclic Client Participation (CyCP) is a structured approach designed to transition FL from idealized models to practical, real-world deployments where client availability is inherently intermittent due to factors such as battery limitations and unstable network connectivity (Huba el al., 2022; Paulik et al., 2021). By enforcing a guarantee that all clients or client groups participate within a defined meta epoch, CyCP offers significant benefits over purely random sampling: it ensures comprehensive data coverage across the entire population an important property for mitigating non-IID data bias (Cho et al., 2023; Zhu et al., 2023)-and critically, this controlled, predictable participation frequency enhances privacy preservation by strictly limiting how often each client contributes with the global model (Kairouz et al., 2021a). While convergence guarantees have been established for ERM under such settings (Cho et al., 2023; Crawshaw & Liu, 2024; Wang & Ji, 2022), the non-decomposable nature of the AUC objective introduces unique challenges that remain unexplored.
To make federated AUC maximization practical under realistic deployment conditions, we study this problem under cyclic client participation for two key classes of surrogate losses. First, for the squared surrogale loss (a, 6) (1 + b)2, Problem (1) can be reformulated as minimax optimization problem (Ying et al., 2016). The minimar formulation does not require explicit construction of positive-negative pairs, making it naturally well-suited for online learning, where dala arrive sequentially, and for federaled sellings, where data reside across many devices- since it simplifies implementation and avoids cross-client pair management. Previous studies (Guo et al., 2020; Yuan et al., 2021a; Sharma et al., 2022; Deng & Mahdavi, 2021) developed commuicationn-ffiiiee algorithms for such minimax problems, but all assume full client participation.
Second, we consider general pairwise surrogate losses (e.g., sigmoid) for Problem (1). The minimar refor- mulation above does not cover all AUC' surrogate losses (Zhao et al., 2011a; Kotlowski et al., 2011; Gao & Zhou, 2015; Calders & Jaroszewicz, 2007; Charoenphakdee et al., 2019a). In particular, symmettrc pairwise losses have been shown to be more robust to label noise than the squared surrogate loss (Charvenphakdee et al., 2019b; Zhu et al,, 2022). It generalizes to tasks such as bipartite ranking and metric learning (Cohen et al., 1997; Clémençon et al., 2008; Kotlowski el al., 2011; Dembezynski et al., 2012; Radenović et al., 2016; Wu et al., 2017). While Guo et al. (2023a) provided a communccation-effiient federated algorithm for this objective, their analysis relies on random client sampling. In contrast, cyclic participation introduces deter- ministic delays, as only specific clients are active at each step. The specific formulations of these two types of problems are presented in Section 4 and 5, respectively. We discuss the compatibility of our proposed algorithms with multiple specific AUC-consistent losses in Appendix G.
Our contributions are as follows.
Minimax Problems. Under cyclic participation, both pri- mal (v) and dual (ax updates are complicated by deterministic client scheduling, which breaks the common independent sampling assumption. Consequently, global gradient estimates become biased, invalidating existing convergence analyses in (Guo et al., 2020; Yuan et al., 2021a). To this end, we use a stagewisc algorithm, where each stage comprises multiple full cycles of communication with all client groups in a pre- defined sequence. Our analysis constructs auxiliary sequences that track model states at cycle boundaries. These anchors enable us to bound the drift caused by biased updates within each cycle and disentangle the complex error propagation across client groups. By exploiting the strong concavity in a, we further control the dual dynamics. Under the cation complexity of O(1/2/)), matching the best-known rate in the full-participation setting (Guo et al., demonsttann that cyclic participation does not inherently degrade efficiency.
Federated Strroovee-SSrongy-oCoooooo
(PL.) condition, our method achieves communi-
Federated Pairwise Optimization. For general pairwise objectives, the key challenge is to handle the coupling between different clients to construct the loss function. We design an active-passive algorithm that decomposes gradients into components computed locally (active) and via shared information from others
2

---

Published in Transactions on Machine Learning Research (01/2026)
(passive). Our analysis traces model updates back to the start of the previous cycle, where all components are virtually evaluated at states independent of current updates, thus mitigating bias. Unlike (Guo et al., 2023a), our approach must handle a delay of two full cycles, making the error dynamics more complex. Nevertheless, our algorithm achieves the same Õ(1/E²) communication complexity (and improved rales under PL), confirming that efficient pairwise optimization remains feasible under cyclic participation.
Empirical Evaluation We validate our methods on benchmark datasets in diverse domains, including CIFAR-1O, CIFAR-100 (image classification), ChestMNIST (medical imaging), and a large-scale insurance fraud detection dataset. Results consistently demonstrate the effectiveness and efficiency of our proposed algorithms under cyelic client participation.
2 Related Work
Our work lies at the intersection of federated optimization for non-ERM objectives and the study of client participation schemes. We briefly review both areas.
2.1 Federated Non-ERM Optimization
While the FL. literature is dominated by Empiriaal Risk Minimization (ERM), there is growing interest. non-ERM objectives such as minimax and compositional optimization, motivated by applications like AUC maximization (Ying et al., 2016) and distribationally robust optimization (Namkoong & Duchi, 2016).
Federated Minimax Optimization. Several works have studied federated minimax problems (Guo et al., 2020; Yuan et al., 2021a; Deng & Mahdavi, 2021; Sharma et al., 2022). Closest to ours, Guo et al. (2020) and Yuan et al. (2021a) address AUC maximization by reformulating it as a nonconvex ponconvex-Strongly-oom strongly-concave minimax problem. They leverage the PL condition and employ stagewise algorithms that solve a sequence of subproblems. Guo et al. (2020) achieved an itcration complexity of O(1/(r²)) and communication complexity of 0(1/(1)/2(1/2)), where z the PL modulus. Yuan et al. (2021a) later incorporated variance reduction techniques to further reduce the communication complexity. A key limitation of these approaches is their assumption of full independently random client participation, which our work relaxes.
Federated Compositional Optimization. Compositional objectives introduce a nested structure that is especially challenging in FL. Gao et al. (2022) analyze a simpler setting where each client has entirely local inner (9k) and outer (fx) functions, avoiding inter-client coupling. In contrast, Guo et al. (2023a) consider more general pairwise objective, where data across clients are inherently coupled. Their algorithm employs an aclive passive gradient decomposition strategy and achieves linear speedup under random client sampling. Other heuristic approaches exist (Wu et al., 2022; Li & Huang, 2022), though they generally lack rigorous theorctical guarantecs.
2.2 Client Participation in Federated Learning
Various client participation schemes have been explored in FL to balance efficiency, scalability, and robust- ness. The simplest stratogy is full participation, where all clients perform local updates in every round (Stich, 2018; Yu et al., 2019a;b). Unbiased client sampling selects a random subset of clients each round (Karim- ireddy et al., 2020; Jhunjhunwala al., 2022: Yang al., 2021a), while biased sampling prioritizes clients based on predefined rules (Ruan et al., 2021) or data characteristics such as local loss values (Cho et al., 2020; Goetz et al., 2019). Asynchronous participation has also been proposed to accommodate heterogeneous client speeds and availability (Yu et al., 2019b; Wang & Ji, 2022). More recently, cyclic client participation, where clients join in a fixed, repeating order, has gained attention for its practical and privacy advantages (Kairouz et al., 2021b). This structured schoduling addresses diverse availability challenges. In cross-device FL, clients may operate in different time zones or charge their devices at preferred times (Cho et al., 2023; Yang et al., 2018). In cross-silo FL, clients such as hospitals face planned constraints, including managing large local datasets, internal network security, or scheduled IT maintenance windows. Convergence guaran- tees for cyclic participation in ERM have been established by Cho et al. (2023) and later strengthened with variance reduction by Crawshaw & Liu (2024). However, all of these methods focus exclusively ERM. Our
3

---

Published in Transactions on Machine Learning Research (01/2026)
work bridges this gap by developing communication-eficiion algorithms and providing rigorous convergence analyses for both federated AUC maximization under the realistic setting of eyclic client participation.
3 Preliminaries and Notations
We begin by establishing standard definitions and notations used throughout the paper. A function f is said to be C-Lipschitz continuous for all x, x' in its domain, 1f(x) - f(x') - C|x - -x'.. differentiable function f L-smooth its gradient Lipschitz continuous, meaning [V/(x) - V/(x') S L|x - x')
We consider federated learning environment with N clients, which are further divided into K groups. The global datasets D (positive set) and D (negative set) are partitioned into N non-overlapping subsets distributed across these clients, denoted as D1 Dj U DJ U... U DV and D2 = D2 u D2 U .DY. Here, Ez-D denotes the empirical expectation over dataset D.
We divide the clients into disjoint groups, each containing N/K clients, denoted by g for k E [K]. During training, the server cycles through these groups a fixed, pre-determined order (g',..., .k). implementing cyclic participation pattern. In cach communication round, M clients are selected uniformly at random without replacement from the active group.
This framework is especially relevant for real-world federated learning applications. For instance, in cross- device FI. mobile devices can be grouped by regions time zoncs, while random sampling within each group provides flexibility especially when the number of clients in a group is large. For simplicity, the framework can also be interpreted as a fully deterministic schedule in the special case of = N or M = N/K, where all clients the active group participate every round; in this case, the theoretical guarantees still hold.
The AUC for scoring function h X IR is defined
(h) Pr(h(x) 2 bxx')y 1, -1),
(2)
where 2 = (x,y) and z' =xx', y²) are drawn independently from the data distribution IP.
Notations. Let w E Rd denote the model parameters. In the minimax formulation, we define v == (w, b) as the primal variable, where a, b E R. For the stagewise algorithms, vo and ag denote the initialization at the beginning of stage 8.
Within each stage, vit denotes the variable epoch e, client group k, client m, and iteration t. The notation ve.k represents the final output of client m in group at epoch e. The group-level aggregation is given by
Σ
ve
G
mEga.
which is the average out put of all participating clients group & during epoch e.
The same notation convention applies wiik and am,t A complete list of symbols used in this paper is provided in Appendix A.
4 Minimax Optimization
To maximize AUC, we adopt the surrogate loss formulation in (1). Following Ying et al. (2016), we the squared surrogate loss (), (1 + 6)?, which reformulates the AUC maximization problem the following minimax optimization:
min max s(w, a, a,,,,,b,) E,[F(w,a,b, waa
(3)
where
=(1 ()((();)) - a) + p(h(w;z) y=-1]
+ 21 a)(ph(w 2)[[u==1]] (1 p)h( (w: (ww:2)]loo 2)I[(==1) - -p(1- p)a²

---

Published in Transactions on Machine Learning Research (01/2026)
Let v == (w,ab) a) denote the set of primal variables. This reformulation enables a natural decomposition across clients, leading to the following federated optimization problem:
min max aw,a. word oER (a.6)e82
1 K
Σ
(4)
mEge
where fk.m(w. a, b, a)) = Ea [F(w, a, b, oz )] and Pk,m denotes the local data distribution on client m of group k.
We now present our algorithm for federated AUC maximization under the practical constraint of cyclic client participation. At the s-th stage, construct strongly convex- sonvex-strongly concave subproblem centered the previous stage's output vū- The local objective for client in group k is defined as:
min max from (v, + -lv- vol?.
(5)
While our approach builds on the stagewise framework of Guo et al. (2020); Yuan et al. (2021a), the key novelty lics in the intra-stage optimization: we introduce multiple cycle epochs and provide a theoretical analysis that handles deterministic client ordering an aspect that poses significant technical challenges. The detailed procedure for a single stage is outlined in Algorithm 1, and the overarching multi-stage framework is presented in Algorithm 2. Each stage initializes the primal and dual variables using the outputs from the previous stage. Within stage, the algorithm runs for multiple epochs, during which all client groups are visited multiple times. Fach client group samples a subset of clients to participate, performs / local update steps, and then passes the updated primal and dual variables to the next client group. The primal variables are updated via stochastic gradient descent, while the dual variable is updated via stochastic gradient ascent. After completing a stage, the step sizes and number of epochs are adjusted before proceeding to the next stage.
We define the following key quantities for our analysis:
d(v) max f(v. d.(v) = o(v) +
2 iv-v.-1l1. f a) = f(, + -
vo-1 - vo, arg (v
(6)
7 211v VVy-v = arg mig 6(v),
Fi.m (V, az; mk (v, a: zk,m) +
Our convergence analysis based on the following standard assumptions:
Assumption 4.1. (i) Initialization: There erist Vo, Ao > 0 such that Φ(vo) v(v3) S Do.
(ii) PL condition: Φ(v) satisfies the p-PL. condition, i.e., m(δ(v) )(v.)) - Vo(v) 12; (iii) Smoothness:
For any 2, f(v,,r;)) z) is l-smooth in v and a. Φ(v) is L-smooth, í.e., [[V(()) - Vo(v2)] _ Ll|vi - v2ll: Bound gradients: [V (v, az 2) & G2; (v) Bounded variance:
E v.kk (v, VvFum(v,,a;2))1
(7)
E V Vafk. (v, V. (,
Remark. These assumptions consistent with prior literature (Guo et al., 2020; Yuan et al., 2021a). The PL condition for minimax AUC maximization has been theoretically and empirically verified (Guo et al., 2023b). Since f(v, a) is ε-smooth in v, it is also ê-weakly convex in v. Accordingly, in the subsequent analysis we choose 7 = 26, which guarantees that the subproblem (5) in each stage becomes f-strongly convex in v.
Our first step is to establish bound the suboptimality gap within stage (Lemma 4.2).
5

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm One Stage Federated Minimax (OSFM)
On Server:
Initialization: v1.0 vl.0,a'.. a...0
for e E [E] cycle-epochs do
for k E [K] do
Sample A clients from k-th client set uniformly at random w/o replacement to get client set g Send global model vek-1 to clients gat
Each client E G in parallel do:
vec
a
LocalUpdateey a
vek
Σ
m
mega
a
Σ a...
1g
mEga.
end for ve+1,0
ve,k a = (e.
end for Output:
Ee 1 k Es veik E 1 K
EB ask
E
LocalUpdateevo. an): for t E [T] do Sample mini-batch Zmn
e.k from local dataset
Update e.k
V m.t1 V vVv((v e.k m. Om m.,1) Update am,t = a m,t-1 + V (vek eik
k
esk o.k
mit am m.))
end for Return VI.aI
Algorithm Federated Minimax with Cyclic Client Participation (CyCp-Minimax)
Initialization: Primal variable x1.0 Client Groups 6(k), h E [K]
for 8 E [S] do
Va, a2 = MS,, Es) end for
Lemma 4.2. Suppose Assumption 4.1 holds and by running Algorithm 1 for one stage with output denoted by (v, )), we have
1 B-1
((v.a)-f(vv.o)
Σ
(v ,a) f2 av100)
E
E
-= a (v
rt v (0af (v a,0)) ) a 11100
E
38 + 382 |/2 / 22 + -100 - 0200 -
L -llv - -
di 3
(a - n)2
-o)]
+
As
The resulting bound contains terms like A and A that couple the randomness from different client groups. To decouple those dependencies, we introduce novel virtual sequences v=.0, ge,0, 6e.0 and 5o (Lemmas 4.3 and B.4). These sequences are purely conceptual and do not require any actual computation. Different from (Guo et al., 2020; Yuan al., 2021a), these virtual sequences further depend on virtual estimates of gradient e.g, evaluating gradient using current data and old model. These sequences are carefully designed to isolate the "signal" (the true gradient) from the "noise" (the stochastic gradient error) and to manage the bias introduced by the cyclic schedule.

---

Published in Transactions on Machine Learning Research (01/2026)
Lemma 4.3. Define v0+ =v
Σ
Σ V Vyfk.m V and
M
mefa.
ge+10 -.,0
Vvligve. a =mi)) VuJi(ve.,, (..0)) for 02 = vv- (8)
mega. t=1
then we have
B Be,
Gf KMI
Σ
ΣED mEge.
Σ
E[[|ve. von 112 12+ 1a ao amm..11))) L - v/l
MKI
- - l|vetto --etllleto--l v11 - 2nK1 (llv (1lv- -0.11---11 - 10+1.
vet10122
21K1
where Eg,0 denotes expectation with respect to all randomness realized prior to epoch e.
With the help of the two virtual sequences 8e.0 and ve.0, we have successfully disentangled the interdepen- dency between different clients and covert the bounds into standard variance bound plus model drift, i.c., the second term on the RHS.
Putting things together, we have the convergence analysis for one stage of the Algorithm Lemma 4.4. Suppose Assumption 4.1 holds. Running one stage of Algorithm 1 ensures that
- 4NEKI lIvo - vl12 + 4MEKI |la0 all? + (
362 + 36n G2 + 2p1 2
38
3no² M
Remark. Lemma above shows that the bound for the output of a stage (Algorithm 1) depends the quality of its imputs, Vo and co. which are the outputs of th previous stage. By employing stagewise algorithm (Algorithm 2) and setting parameters appropriately, we can ensure that the duality gap decreases exponentially across stages. Extending the one-stage result to the full double-loop (Algorithm 2) procedure yields the following theorem.
Thcorem 4.5. Define L- 2
Set γ 2e, n, no exp(-((s 1)c), T. 212 exp((s 1)c). To return Vs such that E[o(vs) - o(v') S e, it suffices to choose S 2 min(F.
P/L
stu/f.
GL+N max log (2 .llog S log 2no 12(0²)) 5K
1)) The iteration complerity is δ (Arhec) and the com-
O
P
munication complerity is δ
K 157
by setting 1, = O KVMm. where Ô suppresses logarithmic factors.
The iteration complexity exhibits lincar speedup with respect to the number of simultaneous participating clients M, i.e., ((1((Me)). This indicates that the proposed algorithm efficiently leverages parallelism even under eyclic participation. The need for a smaller communi- cation interval (scaled by K) as the number of groups increases arises naturally from the cyclic participation protocol. A larger K introduces longer delays between consecutive client updates, heightening staleness and drift. Adapting the local update count I, based on K effectively balances communication efficiency against the resulting error.
Remark. Lincar Speedup and Efficiency:
Comparison to Prior Work: Our communication complexity matches the dependency on and e achieved by Guo et al. (2020); Yuan et al. (2021a) under the more idealistic assumption of random client sampling. Thus, our analysis demonstrates that cyclic participation does not dograde the asymptotic convergence rate. To our knowledge, this is the first such guarantee for federated minimax optimization.
5 Pairwise Objective
In this section, we study a broader class federated pairwise optimization problems, which generalizes AUC maximization to arbitrary pairwise loss functions. We propose a novel algorithm and provide convergence

---

Published in Transactions on Machine Learning Research (01/2026)
analysis for this setting under eyclic client participation, both with and without assuming the PL condition. We consider the following Tederated pairwise objective:
N Σ
N
min F(w) wER*
Σ E (((w)) 1=1
(9)
EDD
A major challenge in optimizing equation is that its gradient inherently couples data across all clients. Let vi and .).((-.)) denote the partial derivatives of v with respect to its first and second arguments, rospectively. We decompose the global gradient
N
N
(F(w)
Σ
B B eDD Viv((((..a).
1=1
N
N B
B
ED
ed
j=1
A,2
Defining the local gradient component as VF,(w) = Aa + 4 the global gradient can be expressod compactly as FF(w)= v VF((w). The difficulty in computing Au and Ai lies in its dependence on global information specifically, the expectation over all clients' datasets Dÿ and Dj:
1 N
An ED
Σ
ED V Vin(((w;;)) h(w:2') Vh(w;
(10)
N
local
global
loral
which local components can be computed by each client using its own data but global components depend data from all clients.
To address this challenge while maintaining the cyclic participation constraint, we adopt an active passive strategy. To estimate A,,, each client computes the active parts using its own data while the passive parts are contributed by other clients through previously shared global information. Specifically, for the k-th group in the e-th epoch, we estimate the global term by sampling he. HS-! without replacement and compute estimator of An by
G 11..1
Vid(h(W edt ze m.n...
2. passive
Vh(wer e.k miti m...1)
(11)
active
active
and similarly Ai2 by
m.
Vid( Ni h(w 2 m...2))
Vh(w 2 miti m...2)
(12)
active
active
where local components in G are referred active parts, while global components referred as passive parts. The passive parts hg.e" and hf-11 are constructed by sampling scores from the previous epoch (e 1). And & = (k, m, e-1.ky represents random variable that captures the randomness in the sampled group K}, sampled client m (1...., g*), iteration index i [I....,I,, data sample e-1.k m,F,1 E Dj and n,,2 D/ for estimating the global component in (10). This delayed estimation bring two challenges: latency error of using old estimates and interdependence between randomness of different epochs and clients.
& [I,...,,K,,
e-1,k
Our algorithm design and analysis differ from Guo et al. (2023a) in two key aspects: (1) the passive compo- nents are from the previous epoch rather than the previous round, introducing greater latency but necessary
8

---

Published in Transactions on Machine Learning Research (01/2026)
for cyclic analysis; (2) the deterministic cyelic order creates more complex interdependeney between clients than random sampling. Unlike our minimax analysis where we could trace back to the start of the current cycle, here we must reference the previous cycle's initial state (we-1.) to establish independence, which increases the analytical complexity. A single loop algorithm is shown Algorithm 3, and a double loop al- gorithm for leveraging PL condition is shown in The One-Stage Federated Pairwise (Algorithm OSFP) algorithm executes single stage of federated optimization by iterating over multiple epochs. Within each epoch, it sequentially processes each client group. For every group, the server samples a subset of clients and broadcasts the current global model along with reference prediction sets. Each selected client then performs a LocalUpdate procedure, which maintains buffers of past predictions, samples new data points, computes pairwise losses and their gradients, and updates the local model using stochastic gradient steps. After completing local computations, clients return the updated models and prediction sets to the server, which aggregates them to update the global model. Once all epochs are completed, OSFP outputs the averaged global model. Furthermore, if the PL condition is satisfied, an outer loop (Algorithm 4) repeatedly calls OSFP over multiple stages, adjusting learning rates and epoch schedules to progressively refine the model.
Our analysis relies on the following standard assumptions for pairwise optimization in problem (9).
Assumption 5.1. (i) vb()) is differentiable, Ly-smooth and Cy-Lipschitz. is differentiable, Li-smooth and -h-Lipcchitz on w for any z E S S2. (iii)
(ii) h(::z)
Ezes; DeessBestt:NNBwee VV [V (): Ve))((((: b(w, (F((w)] S 0².
(iv) 3D such that [VF(()) VF(w))? I D2, Vi.
Theorem 5.2. Suppose Assumption 5.1 holds. Running Algorithm 3 ensures that
1
2t) (F (F(w*)) F((w)) + + +24 M nIKE
E VF
(*
1113
(13)
Remark. Since n nI. By sctting 17 1 C,, I Mie: E= E 23 the itcration complexity is O( Me). which demonstrates a sinear-speedup by M, and communication cost is EK = = These results matches the results in (Guo et al., 2023a) of full client participation setting. This demonstrates that our algorithm successfully handles the additional challenges of cyclic participation without sacrificing asymptotic efficiency. Ii important to note that the prediction scores (Hi, H()) incur no additional computation, as they simply reuse the scores generated during local updates. Since (H4, HS) stores only the prediction scores from the previous communication round, the required memory is O(IMK), where I is the communiattion interval, K is the number of client groups, and M is the number of simultaneously participating clients per group. This storage cost is negligible compared with the number of parameters in modern neural network and can be adjusted in practice by tuning M or 1. Each client's 's local buffers, Bi, and B,,,, are of size O(1), which stores sufficient historical predictions used to construct the loss function at every local update iteration. Shuffling these buffers is essential to ensure that, over time, each client has the opportunity to interact with every other client.
1
Under the additional assumption that F(w) satisfies the p-PL condition, which is commonly used in pairwise optimization (Yang et al., 2021c), we obtain significantly improved convergence rates as follows. Theorem 5.3. Suppose Assumption 5.1 holds and F(-) satisfies u-PL condition. To achieve an e-stationary point by running Algorithm 4, the iteration complerity is δ 1 (MMe)) and the communication complerity is 4
ō 11/ (1
K by setting I, = 0 (km)), where Ō suppresses logarithmic factors.
Remark. Linear Speedup: Both Theorem 5.2 and 5.3 confirm linear speedup with respect to the number of simultaneously participating clients M, demonstrating efficient use of parallel resources even under cyclic participation.
Impact of PL Condition: The PL condition dramatically reduce the iteration complexity from O(1/et) to Ö(1/e) and the communication complexity from ((1/e²) to 3/2/23/221/3
9

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm One Stage Federated Pairwise (OSFP)
1: On Server
2: Initialize H1, H2 by one initial epoch
for E [E] do
Hi H251 =
for k [K] do
Sample M clients from k-th client set uniformly at random w/o replacement to get client set ge.
7: Send global model w* to clients in S
8:
Clients S in parallel do:
9:
Sample without replacement R R122 from Hf, HE, respectively.
Send R R client for all i E [N]
10:
week Heik Hapk ILocnUppdate (wek)))
11:
12: Add Umegax m,1 to Hgt and megas mm m. to H2t1
13: Compute we,k
GeaN Emegex we.k
14: end for
15: end for
16: Return
R Ex a m.
17: On Client LocalUpdate
18: On Client i: Require parameters 1,,
19: Initialize model w and initialize Buffer B Bi,
20: Reccives wek-1 from the server and set 200 = weAk-
21: Receive Rug, R from the server
22: Shuffle R.ck R. and place the results into buffers B,,1,
23: Sample K points from Di, compute their predictions using model wº, denoted by H
24: Sample K points from Di, compute their prodictions using model w! denoted by H.P
25: for = K K-11 do
c.k 26: Sample m,, from D sample m,,,, from D
e.k
or sample two mini- bani-b of data
27: Take next he he-1 and he-1 from Bm, and Bm,,, resp.
Compute h(w.k : 1 2 and hwwhh 2m,t2) 2,,22)
28:
hiwek eik Add h(w mi (,,,,1) into Hm, and add h h(w e.k m,,i m,,, into H
29:
30: Compute Ge.k
mm,11 and Ge.
m,t2 according to (11) and (12)
a. w a.k m,1+1 m.t (G m.1.1 + Gm...))
31:
32: end for
33: Sends wha to the server
34: Sends H Hm to the server
Algorithm Federated Pairwise AUC Under PL Condition (CyCP-Pairwise)
Initialization: Wo for 8 E [S] do
W., a, OSFFPWW-1L.7 E.)
end for Return W ag
10

---

Published in Transactions on Machine Learning Research (01/2026)
General Impact:
The problem we consider is general enough to extend beyond AUC maximization to applications such as bipartite ranking, metric learning, and other client-coupled tasks. For instance, consider the contrastive loss commonly used in metric learning (Hadsell et al., 2006):
8(2), 22) ((][::z)),((w: = 2
22)
2 (1 (1-8(2), 22)) maxx(0, m m-11 22)ll))
(14)
where 8(21, if 2ι and 22 are similar, and otherwise, and h(w;z) denotes the embodding of data point z produced by model w. This loss naturally fits into the formulation in Problem when the data pairs are distributed across multiple clients.
Privacy Considerations. The two algorithmic frameworks proposed in this work require clients to share model parameters- -nd for pairwise objectives, to additionally share prediction scores- to enable collabora- tive optimization, consistent with prior literature (Guo et al., 2023a; McMahan et al., 2017). However, such information exchange can introduce privacy risks, as model updates and related signals may potentially leak information about individual data points (Zhu et al., 2019). These risks can be mitigated through several techniques, including: 1) adding noise to ensure differential privacy (Abadi et al., 2016; McMahan et al., 2018; Trucx et al., 2020; Wei et al., 2020); 2) quantization (Kang et al., 2024; Youn et al., 2023; Xu et al., 2025); 3) dropout (Jain el al., 2015); and 4) homomorphic encryption during aggregation (Jin el al., 2023; Fang & Qian, 2021).
6 Experiments
We evaluate our proposed method on four distinct datasets: CIFAR-10, CIFAR-100, ChestMNIST, and an Insurance fraud datasct to demonstrate the robustness of the proposed algorithms across domains (computer vision, medical imaging, and tabular data) under challenging non-IID and imbalanced conditions.
For CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2009), we reformulate the multi-class tasks as binary classification problems by designating one class as positive and the rest as negative. To induce class imbal- ance, 95% of positive samples in CIFAR-10 and 50% in CIFAR-100 are removed. ChestMNIST (Yang et al., 2021b) is framed as a binary task predicting the presence of a mass. Training data is distributed across 100 clients using a Dirichlet distribution with concentration parameter dir to simulate heterogencity. RosNet18 (He et al., 2016) is used for 1ifar-10/100 and DenseNet121 Huang et al. (2017) is used for ChestMNIST.
The Insurance fraud dataset is constructed from Medicare Part B claims (2017 2022) from the Centers for Medicare & Medicaid Services (CMS) (Centers for Medicare & Medicaid Services (CMS), 2016). Providers are labeled fraudulent based on the List of Excluded Individuals and Entities (LEIE) (Office of Inspector General, U.S Department of Health & Human Services, 2016). Fach U.S. state is treated as a separate client, resulting in 50 clients with naturally heterogeneous data. A chronological split is used: 2017 2020 for training. 2021 for validation, and 2022 for testing. The linear model is used for the insurance data.
We compare our methods with cyclic-participation basclines: CyCp-FodAVG (Cho et al., 2023), Amplified FedAVG (A-FedAVG) (Wang& & Ji, 2022), and Amplisied SCAFFOLD (A-SCAFFOLD) (Crawshaw & Liu, 2024). We also include Random Sampling Minimax (RS-Minimax) and Random Sampling PSM (RS-PSM). These two methods are adapted from Guo et al. (2020) and Guo et al. (2023a) and rely randomly sampling clients in each round. Step sizes are tuned in [1c-1, 1c-2, 1e-3). We use a surrogate loss (2) [+xx)((11-22)AA) where the scaling factor À is tuned in [1, le-1, 1e-2, 1e-3). Regularization factor p for minimax AUC is tuned in [1c-1, 1c-2, 1c-3]. All algorithms are trained for 100 epochs, with stagewisc algorithms tuned for initial stage length [1,10,50], decay factor [0.1,0.2,0.5], and stage scaling [2,5,10]. The reported results in all tables are mean and std of three runs of an algorithm
We first set dir- 0.5 for CIFAR-10/100 and evaluate two settings: (1) Original labels, using naturally imbalanced labels; (2) Flipped labels, where 20% of positive labels are randomly flipped to negative. Test AUC results are shown in Tables and 2. Our proposed methods (Minimax and PSM) consistently outperform all baselines across datasets and settings. For instance, on CIFAR-100, PSM improves AUC by 5 6% over the best bascline; on the Insurance dataset, PSM surpasses FedAVG by over 4%. Under label flips, Minimax and PSM also significantly outperform baselines. Our proposed methods, CyCP- Minimax and
11

---

Published in Transactions on Machine Learning Research (01/2026)
CyCP-PSM, achieve superior performance to these mandom-samplinn baselines in most cases since random sampling does not. ensure comprehensive population coverage, which is essential for mitigating non-ITD bias. We also emphasize that random sampling implicitly assumes that all sampled clients are available to participale, an assumption that often breaks down in real-world lederated environments. In contrast, cyclic client participation overcomes these limitations by utilizing predictable participation.
Sensitivity to Hoterogencity and Label Noise We further examine the impact of heterogencity (Dirich- let concentration dir) and label noise (flip ratio flip) on CIFAR-10, CIPAR-100, and CheST (Tables 3, 4 and 5). The trends are consistent: 1) As heterogeneity increases (smaller Dirichlet a), baseline methods exhibit significant drops in AUC, while Minimax and PSM remain stable. 2) Under high label-flip rates (flip=0.2), our methods maintain competitive performance, sometimes exceeding the clean-label baselines (e.g. PSM on CIFAR-10). 3) These observations confirm that the proposed algorithms better align client objectives despite data inconsistency and label corruption, validating their theoretical design for robust federated AUC optimization.
Ablation on Communication Efficiency Figure 1 presents an ablation study on the communication interval 1, which controls the number of local updates before synchronization. Both Minimax and PSM maintain stable lest AUC even as / increases, demonstrating that the proposed methods can tolerate in- frequent commmication without loss of convergence quality. This property makes them well-suited for banntrid foderatod environments, where communication cost dominates training time.
Overall, the experimental results demonstrate that: 1) Performance: Minimax and PSM achieve consistent and significant AUC improvements over state-offthhe-at baselines across diverse modalities. 2) Robustness: They remain resilient under severe class imbalance and label noisc. 3) Scalability: The methods scale effectively to large heterogeneous client populations and tolerate sparse communication. Together, these results substantiate the practical advantages of our proposed algorithms for real-world federated learning scenarios involving non-llD, imbalanced, and noisy data distributions.
Table 1: Experimental Results on Original Labels. (dir=0.5 for Cifar-10/100)
Cifar- 10
Cifar-100
ChestMNIST
Insurance
CyCp-FedAVG
0.7836 0.0020
0.8894 = 0.0012
0.6012 + 0.0016
0.7339 0.0035
A-FedAVG
0.7950 + 0.0014
0.9137 = 0.0028
0.5994 + 0.0025
0.7384 + 0.0030
A-SCAFFOLD
0.7993 0.0018
0.9105 = 0.0017
0.6015 = 0.0022
0.7412 + 0.0021
RS- -i-Mmxx
0.8153 0.0025
0.9392 0.0029
0.5697 = 0.0031
0.7419 + 0.0013
RS-Pairwise
0.8357 + 0.0012
0.9688 = 0.0010
0.6118 + 0.0020
0.7619 + 0.0011
CyCp- Minimax
0.8446 0.0015
0.9318
0.0014
0.6163 = 0.0026
0.7616 0.0017
CaCp-eairwise
0.8480 1 0.0008
0.9694 - 0.0013
0.6256 1 0.0015
0.7778 1 0.0002
Table Experimental Results on Flipped Labels (dir=0.5 for Cifar-10/100, flip=20%
Cifar-10
Cifar-100
ChestMNIST
Insurance
CyCp-FedAVG
0.7739 = 0.0031
0.8781 = 0.0019
0.5927 = 0.0008
0.7292 + 0.0029
A-FedAVG
0.7891 1 0.0020
0.8951
0.0023
0.5901 1 0.0013
0.7298 1 0.0035
A-SCAFFOLD
0.7950 + 0.0025
0.9066 - 0.0024
0.5987 1 0.0011
0.7307 1 0.0036
RS-Minimax
0.8170 + 0.0021
0.9185
0.0019
0.5587
0.0026
0.7517 + 0.0038
RS-Pairwise
0.8201 + 0.0017
0.9480
0.0020
0.6004 + 0.0009
0.7173 + 0.0043
Minimax
0.8316 + 0.0006
0.9275
0.0015
0.6150 + 0.0007
0.7505 + 0.0041
CyCp-Pairwise
0.8424 + 0.0038
0.9455
0.0020
0.6077 + 0.0012
0.7722 + 0.0018
We show ablation experiments over the communication interval in Figure 1. We can see that the algorithms can tolerate a large number of local update steps I without degrading the performance, which verifies the communication--ffciinnny of the proposed algorithms.
For more ablation experiments, please refer to Appendix F.
12

---

Published in Transactions on Machine Learning Research (01/2026)
Table Results with different Dirichlet parameter dir and flip ratio flip on Cifar-10
dir=0.1,flip-00 dir=0.1,flip=0
drr=10,flip-0
1ir=10,f1ip=0.2
CyCp-FedAVG
0.7581 0.0023
0.6800 = 0.0030
0.8227 = 0.0025
0.8199 + 0,0019
A-FedAVG
0.7732 0.0029
0.7015 0.0028
0.8354 + 0.0033
0.8254 + 0.0015
A-SCAFFOLD
0.7815 + 0.0016
0.7119 = 0.0021
0.8336 + 0.0019
0.8315 + 0.0011
RS-Minimax
0.7976 0.0021
0.8083 = 0.0025
0.8154 = 0.0031
0.8086 0.0016
RS-Pairwise
0.8059 + 0.0014
0.7712 0.0027
0.8304 = 0.0032
0.8217 + 0.0023
CyCp- Minimax
0.8184 0.0018
0.8095 = 0.0017
0.8702 = 0.0023
0.8511 - 0.0008
CyCp- Pairwise
0.8283 + 0.0012
0.7828 0.0020
0.8626 = 0.0027
0.8540 + 0.0014
Cifar-10, Minimax
Cifar-100, Minimax
Testing AUC
Testing AUC
3:3
1=16
8:0
1=16
1=32
1=32
64
1=64
1=128
1=128
031
I=122
1=512
035
Number of Iterations (*30k)
Number of Iterations (*30k)
Cifar-10, PSM
Cifar-100, PSM
Testing AUC
Testing AUC
1-16
1-16
1-32
1-
1-64
1=128
1=128
1=512
Number of Iterations (*30k)
Numbar of Iterations (*30k)
Figure 1: Ablation Study: The effect of communication interval J.
Table Results with different Dirichlet parameter dir and flip ratio flip on Cifar-100
dir=0.1,
dir-0.1,flip-0. 0.2
dir=10.flip-0
dir=10.f4ip-0.
FedA-G
0.9203 + 0.0009
0.8774 = 0.0018
0.9587 = 0.0025
0.9363 + 0.0024
A-FedAVG
0.9230 0.0014
0.8825 = 0.0026
0.9605 = 0.0030
0.9402 0.0023
A-SCAFFOLD
0.9199 1 0.0021
0.8906 + 0.0015
0.9627 1 0. 0.0027
0.9421 1: 0.0016
RS-Minimax
0.9216 0.0011
0.9123 = 0.0022
0.9520 1 0.0018
0.9266 0.0030
RS-Pairwise
0.9243 1 0.0015
0.9180 0.0024
0.9601 1 0.0017
0.9475 1: 0.0026
CyCp-Mininas
0.9299 0.0013
0.9148 = 0.0017
0.9610 = 0.0023
0.9564 0.0019
CyCp-Pairwise
0.9308 + 0.0016
0.9123 0.0028
0.9669 = 0.0015
0.9525 + 0.0021
Table Results with different Dirichlet parameter dir and flip ratio flip on ChestMNIST
dir=0.1,
dir-0.1,
dir=10.flip-0
1ir=10,f
CyCp-FedAVG
0.5584 0.0006
0.5329 + 0.0003
0.6561 1: 0.0013
0.6197 4 0.0017
A-FedAVG
0.5580 0.0004
0.5334 = 0.0006
0.6572 = 0.0015
0.6201 + 0.0013
A-SCAFFOLD
0.5573 + 0.0004
0.5341 = 0.0002
0.6568 = 0.0016
0.6233 + 0.0019
MS-Miniaax
0.5245 + 0.0011
0.5155 = 0.0004
0.6541 = 0.0008
0.6232 + 0.0017
RS-Pairwise
0.5502 + 0.0007
0.5338 = 0.0009
0.6545 = 0.0012
0.6293 + 0.0014
CyCp Minimax
0.5553 0.0010
0.5362
0.0005
0.6433 + 0.0012
0.6318 0.0018
CyCp- Pairwise
0.5598 0.0009
0.5498
0.0004
0.6595 = 0.0010
0.6356 + 0.0023
13

---

Published in Transactions on Machine Learning Research (01/2026)
7 Conclusion
This paper studies federated optimization of non-ERM objectives, with a focus on AUC maximization un- der the practical constraint of cyclic client participation. We propose communication-effiiene algorithms designed for this setting. For renomuae-eforrulatedd AUC, we introduce a stagewise method with auxiliary soquences to manage cyclic dependencies. For general pairwise losses, we develop an active-passive strategy that shares prediction scores across clients. We provide theoretical guarantees on both iteration and com- munication complexity, and validate the effectiveness of our algorithms on diverse tasks involving 50-100 clients.
8 Limitations and Future Work
Our work has several limitations. First, the fast communication rate of ((1/e2/2) depends the PL con- dition, which may limit the generalizability of the associated algorithms. Sccond, the convergence rates in both the PL and non-PL regimes have not yet reached known lower bounds, leaving room for improvement. Third, developing methods to formally ensure differential privacy remains an open question. Finally, ex- tending our approach beyond AUC maximization to a broader class of non-ERM objectives constitutes an important direction for future research.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Llya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications securily, pp. 308 318, 2016.
Toon Calders and Szymon Jaroszewicz. Efficient AUC optimization for classification. In Knowledge Discovery in Databases: PKDD 2007, 11th European Conference on Principles and Practice of Knowledge Discovery Databases, Warsaw, Poland, September 17-21, 2007, Proceedings, volume 4702 of Lecture. Notes in Computer Science, pp. 42-53. Springer, 2007.
Centers for Medicare & Medicaid Services (CMS). Medicare Provider Utilization and Payment Data: Physi- cian and Other Supplier. 2016. Accessed: 2024-03-25.
Nontawat Charoenphakdee, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for learning from corrupted labels. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research. pp. 961-970. PMLR, 2019a.
Nontawat Charocuphakdee, Jongycong Lee, and Masashi Sugiyama. On symmetric losses for learning from corrupted labels. In International Conference on Machine Learning, pp. 961 970. PMLR, 2019b.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and of selection strategies. arXiv preprint arXiv:2010.01243. 2020.
Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the convergence of federated averaging with cyclic client participation. In International Conference on Machine Learning, pp. 5677-5721. PMLR, 2023.
Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis. Ranking and empirical minimization of u-statistics. The Annals of Statislics, 36(2):844 874, 2008.
William W Cohen, Robert E Schapire, and Yoram Singer. Learning to order things. Advances in newral information processing systems, 10, 1997.
Corinna Cortes and Mehryar Mohri. Aue optimization vs. error rate minimization. Advances in neural information processing systems, 16, 2003.
14

---

Published in Transactions on Machine Learning Research (01/2026)
Michael Crawshaw and Mingrui Liu. Federated learning under periodic client participation and heterogeneous data: A new communicat ion-efficient algorithm and analysis. Advances in Neural Information Processing Systems, 02992000999, 2024.
Krzysztof Dembczynski, Wojciech Kotlowski, and Eyke Hillermeier. Consistent multilabel ranking through univariate losses. arXiv preprint arXiv:1206.644: 2012.
Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Stalisties, pp. 1387- 1395. PMLR, 2021.
Charles Elkan. The foundations of cost-sensitive learning. In International joint conference artificial intelligence, volume 17, pp. 973 978. Lawrence Erlbaum Associates Ltd, 2001.
Haokun Fang and Quan Qian. Privacy preserving machine learning with homomorphic encryption and federated learning. Future Internet, 13(4):94, 2021.
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-7055 PMLR, 2022.
Wei Gao and Zhi-Hua Zhou. On the consistency of AUC pairwisc optimization. In Qiang Yang and Michael J. Wooldridge (eds.), Proceedings of the Twenly- Fourth International Joinl Conference on Artificial Intelli- gence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pp. 939 945. AAAI Press, 2015.
Wei Gao, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou One-pass auc optimization. In ICML (3), pp. 906 914, 2013.
Jack Goetz, Kshitiz Malik, Due Bui, Seungwhan Moon, Honglei Liu, and Anuj Kumar. Active federated lcarning. arXiv preprint arXiv: 1909. 1909.12641,, 2019.
Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Commmication-elliiee distributed stochastic auc maximization with deep neural networks. In International Conference on Ma- chine Learning, pp. 3864-3874. PMLR, 2020.
Zhishuai Guo, Rong Jin, Jiebo Luo, and Tianbao Yang. Fedxl: Provable federated learning for deep x-risk optimization. In International Conference on Machine Learning, pp.
PMLR, 2023a.
Zhishuai Guo, Yan Yan, Zhuoning Yuan, and Tianbao Yang. Fast objective & duality gap convergence for non-convex strongly-concave min-max problems with pl condition. Journal of Machine Learning Research, 24(148):1-63, 2023b.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning invariant mapping. In 2006 IEEE Computer Society Conference Computer Vision and Pattern Recognition (CVPR 2006), 17-22 June 2006, New York, NY, USA, pp. 1735-1742. 1742. IEEE Computer Society, 2006. doi: 10.1109/ CVPR.2006.100. URL
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint vrXii:18111008 1.03604, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolu- tional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp.
2017.
15

---

Published in Transactions on Machine Learning Research (01/2026)
Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole- Jean Wu, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, Kaikai Wang, Anthony Shoumikhin, Jesik Min, and Mani Malck. PAPAYA: practical, private, and scalable federated learning. In Diana Marculescu, Yuejie Chi, and Carole-Jean Wu (eds.), Proceedinggs of the Fifth Conference on Machine Learning and Systems, MLSys 2022, Santa Clara, CA, USA, August 29 September paper_ saaper_flle____ salles/appe//22220
2022. mlsys.org, 2022. URL https: httpp://prooceddlgs.....
Pratock Jain, Vivek Kulkarni, Abhradeep Thakurta, and Oliver Williams. To drop or not to drop: Ro- bustness, consistency and differential privacy properties of dropout. CoRR, abs/ abs/1503.02031, 2015. URL
http:///arri..orr/bb//11....
Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkalti, and Gauri Joshi. Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence, pp. 906-916. PMLR, 2022.
Weizhao Jin, Yuhang Yao, Shanshan Han, Jiajun Gu, Carlee Joe- Wong, Srivatsan Ravi, Salman Avestimehr, and Chaoyang He. Fedml-ho: An efficient nomomopphiccancrppion basod learning system. Xrxiv preprint vrXie:2303.10877 2023.
federatod
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Prac- tical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, 1CML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 5213 5225. PMLR, 2021a. URL attp://procceddiggs mlr. www.mm.rrrrre1191111 http/////////aaai11111/ wkaakau22b.bbttmmm hmm.l
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Prac- tical and private (deep) learning without sampling or shuftling. In International Conference on Machine Learning, pp.
PMLR, 2021b.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundalions and Trendso in Muchine Learning, 14(1 21:1 210, 2021c.
Tianqu Kang, Lumin Liu, Hengtao He, Jun Zhang, Shenghui Song, and Khaled B. Letaief The ef- fect. of quantization in federated learning:a rényi differential privacy perspective. Tn IEEE Interna- tional Mediterranean Conference on Communications and Networking, MeditCom 2024, Madrid, Spain, July 8-11, 2024, pp. 233-238 IEEE, 2024. doi: 10.1109 /TtM///ITTTCM000122000000000 httts:://aiioor/10.11005 000 200.:m11000722222.0011177..
URL
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic coltrolled averaging for federated learning. In International Conference Machine Learning, pp. 5132 5143. PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Dis- tributed machine learning for on-device intelligence. arXic preprint orXiv:1610. 02527, 2016.
Wojeiech Kotlowski, Krzysztof Dembezynski, and Fyke Hüllermeier. Bipartite ranking through minimization of univariate loss. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28- July 2, 2011, pp. 1113-1120, Omnipress, 2011.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. (2009), 2009.
Junyi Li and Heng Huang. Fedgrec: Federated graph recommender system with lazy update of latent embeddings. arXiv preprint arxiv:2210. 13686, 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Commmnicttion-fflceent learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. PMLR, 2017.
16

---

Published in Transactions on Machine Learning Research (01/2026)
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in Neural Information Processing Systems (NeurIPS), pp. 2208 2216, 2016.
Yurii Nesterov. Introductory Lectures on Conver Oplimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004.
Office of Inspector General, U.S. Department of Health & Human Services. LEIE: Office of Inspector General LEIE Downloadable Databases. https://oig, httpes///o...hsssgo///cccsissss/ heoo///eccusionss/ttttrriiiaaaa 2016. Accessed: 2024-03-
25.
Sarthak Pati, Ujjwal Baid, Brandon Edwards, Micah Sheller, Shih-Han Wang, G Anthony Reina, Patrick Foley, Alexey Gruzdev, Deepthi Karkada, Christos Davatzikos, et al. Federated learning enables big data for rare cancer boundary detection. Nature communications, 13(1):7346, 2022.
Matthias Paulik, Matt Seigel, Henry Mason, Dominic Telaar, Joris Kluivers, Rogier C. van Dalen, Chi Wai Lau, Luke Carlson, Filip Granqvist, Chris Vandevelde, Sudeep Agarwal, Julien Freudiger, Andrew Byde, Abhishek Bhowmick, Gaurav Kapoor, Si Beaumont, Áine Cahill, Dominic Hughes, Omid Javidbakht, Fei Dong, Rehan Rishi, and Stanley Hung. Federated evaluation and tuning for on-device personalization: wttpg////aa//../////////
System design & applications. CoRR, bbss22102085003 2021. URL
Filip Radenović, Giorgos Tolias, and Ondicj Chum. Cnn image retrieval learns from bow: Unsupervisod fine-tuning with hard examples. In European conference on computer vision, pp. 3 20. Springer, 2016.
Alain Rakotomamonjy. Optimizing area under roc curve with svms. In ROCAI, pp. 71-80, 2004.
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe- Wong. Towards flexible device participation in federated learning. In International conference on artificial intelligence and statistics, pp. 3403 3411. PMLR, 2021.
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimization: Im- proved convergence analyses and algorithms. In International Conference on Machine Learning, pp. 19683 19730. PMLR, 2022.
Sebastian U Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2018.
Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the third ACM international workshop on edge systems, analytics and networking, pp. 61-66, 2020.
Shiqiang Wang and Mingyue Ji. unified analysis of federated learning with arbitrary client participation. Advances Neural Information Processing Systems, 35:19124-19137, 2022.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. JEEE transactions on information forensics and security, 15:3454-3469, 2020.
Chao- Yuan WI, Manmatha, Alexander J Smola, and Philipp Krahenbuhl Sampling matters in deep embedding learning. In Proceedings of the IEEE international conference on computer vision, pp. 2840- 2848, 2017.
17

---

Published in Transactions on Machine Learning Research (01/2026)
Yawen Wu, Zhepeng Wang, Dewen Zeng, Meng Li, Yiyu Shi, and Jingtong Hu. Federated contrastive repre- sentation learning with feature fusion and neighborhood matching, 2022. URL https::/openreviee..nt forum:71d-6LMPECJJAC..
Zhibo Xu, Jianhao Zhu, Jingwen Xu, Changze Lv, Zisu Huang, Xiaohua Wang, Muling Wu, Qi Qian, Xiaoqing Zheng, and Xuanjing Huang. Enhancing model privacy in federated learning with random masking and quantization. CoRR, 0bs/2508..1811 2025. doi: 10.48550/ARXIV 250.I....50..888 1891. //doi.org//i 11t111.../5.rr... 200.500/r11..228.18999999
URL https:
Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient descent ascent methods for min-max optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint 2rXiv:2101.1120s, 2021a.
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2: A large-scale light benchmark for 2d and 3d biomedical image classification. arXiv preprint (xXt::2110.147900 2021b.
Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied lederated learning: Improving google keyboard query suggestions. CoRR, abs/1811.02203,, 2018. URL attp://aarxtv.orggaa///BB11 wwt..rrgg//bb//1..29.....
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-201777 2021c.
Yiming Ying, Longyin Wen, and Siwci Lyu. Stochastic online auc maximization. In Advances in Neural Information Processing Systems, pp. 451-459, 459, 2016.
Yeojoon Youn, Zihao Hu, Juba Ziani, and Jacob D. Abernethy. Randomized quantization is all you need for differential privacy in federated learning. CoRR, abs/2306.11913 2023. doi: 10.48550/AAA 48850/ARXXIV ARXIV 2306.11913 URL https: http://do.oor///////// 40w.0.85////... httpa/rvvvvvv..11..11
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp. 7194-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 Arlificial Intelligence, pp. 5693 5700, 2019b.
Zhuoning Yuan, Zhishuai Guo, Yi Xu, Yiming Ying, and Tianbao Yang. Federated deep maximization 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 maximization: A new surrogate loss and empirical studies on medical image classification. In Proceedings of the IEEE/CVF International Conference on Compuler Vision, 2021b.
Peilin Zhao, Steven C. H. Hoi, Rong Jin, and Tianbao Yang. Online AUC maximization. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011, pp. 233 240, 2011a.
Peilin Zhao, Steven CH Hoi, Rong Jin, and Tianbo Yang, Online auc maxinization. 2011b.
Dixian Zhu, Xiaodong Wu, and Tianbao Yang. Benchmarking deep AUROC optimization: Loss functions and algorithmic choices. CoRR, abs/ 22071170. 2022. doi: 10.48550 018550/ARXIVV 220.2.2223777 URL https: / http://100855000/......2200
18

---

Published in Transactions on Machine Learning Research (01/2026)
Feng Zhu, Jingjing Zhang, and Xin Wang. Communictiion-eficeent local SGD with age-based worker se- lection. J. Supercomput. 1393316677 2023. doi: 10.107//11227-233551007 URL https: //000..00/0..0000/1117---------- 05190077
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché--Buc Emily B. Fox, and Roman Garnett (cds.), Advances in Neural Information Processing Systems 32: Arnuul Conference on Newral Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancoweer, BC, Canada, pp. 14747-14756, 2019. URL https: //
Abstract.html. hal..
19

---

Published in Transactions on Machine Learning Research (01/2026)
A
Notations
Table 6: Notations
Re
Model paramelers of the neural network, variables to be trained
mur Rdd
Model parmmelers of machine group & epoch iseration stage index is omiited when contest clear Introduced variables in minimux objective function
a, b.b E R2!
(W, Refr2
Prinal variable minimax objective function.
wiikk york ast
Outguts gronp/round round epoch Averages A data point.
particigating clients.
data point from machine
A data point sampled on machine m of group & at epoch e, iteration t
Two independent data points (positive and negative, respectively) sampled on machine m of group at epoch e, Iteration The prediction score data z by network w The of integers (1, 2....... X), where X integer. Local stochastic estimators of components of gradient
A[w:2)
[X]
G
Ry. MG
Global buffers of historical prediction scores for positive and negative data.
Collected historical prediction scores machine of group/round & at epoch
R REA
Tremittedd butfer from server to client
Predictions scores sampled from the collected scores of epoch e-1
B Analysis of CyCp Minimax
B.1 Auxiliary Lemmas
For the stagewise algorithm for minimax problem, we define the duality gap of s-th stage at point (v,
Gapa(v,dl = a'
("vvva') min f"(v', ax).
(15)
Before show the proofs, we first present the auxiliary lemmas from Yan et al. (2020).
Lemma B.1 (Lemma 1 of Yan et al. (2020)). Suppose function f(v,a) is X1-strongly conver in and d2 ss-strongyy concave in Consider the following problem
min max f(v, a), vEX aEY
where X and Y convex compact sets. Denote Va(a)) arg min f(v', and 6y(v) arg max f(v, v'EX
Suppose we have two solutions (Vo, 0n) and (V1, Then the following relation between variable distance and duality gap holds
A1
A2 14 - voll2+ (lay(vi) aoll < max a'EY f(vo, min f(v, au) veX
(16)
max
f(v1,
min f(v', a1). v'ex
a'ey
Lemma B.2 (Lemma of Yan et al. (2020)). We have the following lower bound for Gap,(vs; (v))
3
4 (0lv -v(v)))
Gap,(vs, a.) 2 Gap (v .,t1) +
50
where vo = and ag s+1 -a,, i.e. the initialization of (s + 1)-th stage is the output of the s-th stage.
B.2 Lemmas
Utilizing the strong convexity conncvity and smoothness of f(;,),, we have the following lemma.
20

---

Published in Transactions on Machine Learning Research (01/2026)
Lemma B.3. Suppose Assumption 4.1 holds and by running Algorithm with input (v For any (V, the oulpuls (V, (x) salisfies
B-1 Eir(vetio,a) u)) (vvv
(' ((),a)
E
K- E
( a vetlo v) + (O.s (vol(ve)) (v _a a t1,0
A1
38
36
122
| 1ett1,0 12 + 20(a -0000 g1lv v0.
M2
(a a)²
3
Proof. For any v and a, using Jensen's inequality and the fact that f"(v, a) is convex in v and concave in a;
f'( f(y,
(17)
E
By E-strongly convexity of (*) in v, we have
f'(ve.0 a (0, (ve:) a v ve.g + gllee -vl2 - f(v,
l
(18)
By 36-smoothness of (*(v,a) in v, we have
("(eetD .a) S ,0) S' a)) a) + (ve.l .a), veti.0 - -v.0) + 3
? vet1,00 100
30
= ff'vve a) +
)000), vet1. -veo0 + 2
//1 || - 02
(O, a) 0 8 (ve,0 0000) ve+1,0 - -vi,
(0)
3
2 1'(v00, a) + (0, S (v )00), 00100 0 vol0 + 2
||
1 1.0 - v0
(19)
+llas0 - alllve+tii +110 - 11
(
38
(vve ,a) (0.1 (vo.0 (vr:0 a00)) vo-1,0 - va.
122 (a - aa² + + 6
302
1 v
2
where (a) holds because that we know fv, a:) is E-Lipschitz in a since f(v, a.) is E-smooth, (b) holds by Young's inequality, and 12 = 2p(1 p) the strong concavity coefficient of f in a. Adding (18) and (19), rearranging terms, have
(' "(v"0,a"0) " + (y .a) a)
$ f(v,a'') f(v a) (O.l(v' ",a -v++ flvv0 v|
38 +
36 36//p12
//2 |v et100 - 000
(20)
2
#2 (a a)².
6
We know that -f(v, a) is u2-strong convexity of in a. Thus, we have
- aa 0. (a a00
( (a - a 20 + M2 (a 00 ~v .a)
(21)
21

---

Published in Transactions on Machine Learning Research (01/2026)
Since f(v, a) is E-mooohh in we get
-((v,a - - (vv (0.f (vaf )a-
- aa
+ l
-aattoo-a"0 -a
2
=-f"(v,a - - (v ,a ) ) cttle aa f(a a000
l
2
- -va l (v a ) a aa
(22)
S -f',va ( a ) - a a + l (att1.0 - -a
- a000)²²
+ f||v - vv -a
1 -- (0. a 11oo a a00 + 2 (a a 00 + L
l
5 g1l v112
3
//2 (a
(a =0
2
where (a) holds because that 0z a) is &Liiscchizz in v. Adding (21), (22) and arranging terms, we have
[" "(""0,""" (v, S -f((v .a) (v(vv" - (va/"(v + +ll(a -2 + e
)a a)
(23)
- -v1²- -
12 (a a..0)
2
Adding (20) and (23), we get
(v a) f"(v,
(vv s (0.[(vet) aa vet2,0
_ - v) [0al(v"0,aa ) ct100 -a)
32 + +6 36 M22
vo 20(a 01 -0-11002- p
3 g11vo
v112
42
- -a)²
(24)
2
3
Taking average over e, k. t, we get
(().a) (" S Eir(v - -
(v, (110
Out (v aa +1o v) + (0.f((v* a
)
) a Ct1D
E
c=0
Ag
38 + 36a 122 || +1,0
2 + 20
000 - 6 l|v v00
(a 00 a)²
2
Ag
In the following, we will bound the term A₁ by Lemma 4.3, Ag by Lemma B.4.
Proof of Lemma 4.3
Proof.
(V. (a ve+10- v)
Σ
Vuskum (v a00)) vet1,0 -v)
M
mega
K
MM
Σ
7
V
Vilkmm (v
Σ mega.
1
V
y F.e
k.m m.
(v ook
o 2.hk)) vet vet -v)
3
K
M
K
M
k=
m
k=
K
Σ
1
Σ
Σ
k.m m.t a mile)l, 1
K
M
I
K=1
t
(25)
22

---

Published in Transactions on Machine Learning Research (01/2026)
Using pet1.0
=v:0
Σ
1
Σ
(f then we have
M
mefa.
k
K
-
Σ
1
Σ
Σ
vm (v ,a
1
Σ
Σ
VvSk (V mm 2
M
M
mEgar t=1
k=1
mEg
t=1
(26)
Hence we get
K K
Σ
vifk (v.00,000
Σ meGe.
FyFR.m (v
ma O 2 vet10 get1.0)
i
M
k=1
mEgsk
k=1
Vvlkmm (v ,a
E
V
Fr (Y ak
m mot)), I], peti0- -v)
K
M
mege.
mega.
=nKT
Σ
D
Vr (ve.
(veo, a0.0 Fi kim (m Om m),)
mEga.
K
Σ
17
Vvskm((v a
Σ
17
V
Fi (ve. a00, ;20,1) 2.0,),, get10 -v)
K
M
M
mEgGN
km
mEg
K
Σ
E
Fi (v ;z
1
E
Σ
V VvFi Fi
mi
am,ti and },
ent
p0+1.0
K
M
mEGaN
mEga,
(27)
where
K
K
Σ
+
Vodkim (v-0 (v a
e.0 (.kk)
Σ
17
V
Vi (v am,t m,,,)], g0+100 -v)
K
M
M
k=1 mege.k
k=1
mEga.k
l 112 -1oottoo
< 38
Ilva,0
mell
K
m
(28)
Define another auxiliary sequence as
K
get1,0 ve.0
Σ
V (v=0 Voll k. (ve.) a,0 ,mth))
(v=00 ,.00)) for 1> 0; vo vvo (29)
M
k= megs.k t=
Denote
(v)
1
Σ
Verfém (ve,0 a=00) - VyFi h. (ve, (ve.U e,0, 20.,)) 2m1 )
v
1 vl- 32011.. (30)
M
2m
mE
Hence, for the auxiliary sequence ãi, can verify that.
+0+1.0 arg min θ (v).
(31)
23

---

Published in Transactions on Machine Learning Research (01/)026)
Since (v) is ") sstrongly convex, we have
1
|V - pet1.01p [v) 0.(
21
K
Σ
(V.Ji.m(v a0 a0 VvFiim(v") (2m))))))
_|v - 1
1
+
M
2n
k=1 mggei t=1
K
(vrJkm(V aa-0 - Vetti a =m)e))
peti.
1
| - 12
211
k=1 mCge.. t=1
K
Σ
(Vufe.(V -V ;2
(v - ve.0) + 1
1|v - v
2n
mgge.k t=1
K
(VofkmmV aa - VvFkim aa am)te)
-2a0) - 211
(pet1.0
|1
k= mega. t=1
1 K
Vv _0 FiFim( c., ,
(v - velo) + 1
1/v - p
M
2m
megaik
(VrSEm(VV ,000) - V.rkm a 00 :00
2
k= mEga. t=1
(32)
Multiplying 1/KT on both sides and adding this with (27), we get
|
2
3 SnKI
Σ
ΣΣM
Σ
Σ
(V
-V m, Om,ti am.)imm.))
(y
MKI
k= mege.k t=l
nKI
K
Σ
Vulā(v=io, a00) 000 -
aa
1
2
MKI
k= mEg t=1
(33)
|V- -0.002
2nKI |1
2nKI
K
Σ
Σ Σ
(VFf _a-5)- - V. Pi a=0,
a0000.0000000 ,000)21)))) pet1.0 ve.u
MKI
1m
mega t=1
where
K Σ
V ,0:00- - V.Ff 0.000 , ( geti.0 - 52,0) = 0. (34)
E
MKI
k=1 mEg fm
4 can be bounded as
1
KKI (ve+1.0- - vv.0 vet110 - v)
(1|ve0 v/12 - -1|ve,0 v2+1.012- - 1| - -112) (35)
kT
24

---

Published in Transactions on Machine Learning Research (01/2026)
Plugging (33) and (35) into (25) and noting nKIz S O(1,, we get E., ( (Vvf(ven a000), vet10 v)
s 31
1
Σ
VvFE(v
, a.0 2mm))) (m,,) (v.i(r00.
MKI
k= megei t=1
5l
+ KMI
Σ
E
Σ
B(Ilv=0
vm,.ll + 11a am,r113)
megai
1
B(I| B(llv -112-11vv 1| v001,0112
- -1|vet100 - -v1??)
2nK1
- ve- + p EElloctlo - v|?
+ 2nK1
(1lv - vv:0 1|v
Knj
KMT Σ
68
B(| [(1/vo0 21
-m + 11 - c
+ l [|vett100 + v/1
MKT
mEg
B(II B(llve.) - vI2 |/ve,0 1 - v + 2 (1|v - 0e.01p2 1|1 +)+110113))
2
where the last inequality uses
| - v/1² م -
v + -
(36)
and |/ 2 is addressed similarly before in 3.
Similarly, A2 can be bounded as
K Σ M
Lemma B.4. Define act1,0 a.0 +1
Σ
Σ
V P as..)
km
mEga.
t=1
20+1.0 -
VaPE(v 00 = + Vafk(v (000), for > 0; āo = ag. (37)
meg
E..0 ( (V.f(ve.) ,,sl),,
a actiu -a)
GījKa² Gl E Σ Σ
velll2 + 11a=:0 11) f -llaatt100 - oa1²
B([lve..
MKT KMT
megs.k
1 knKT B(Ila=0 - all - | a0
-1 all2) + 2n B(lla 0=.012 l|a 10)3))).)
a011.011--
With the above lemmas, we are ready to give the convergence one stage.
B.3 Convergence Analysis of a Single Stage in CyCp-Minimax
We have the following lemma to bound the convergence for the subproblem each s-th stage.
Lemma B.5. (One call of Algorithmm 1) Let (v,a) be the output of Algorithm 1. Suppose Assumption 4.1 hold. By running Algorithm with given input vo. on for T iterations, = 22, and S min( 344367 it we have for any and
1 llvo v122 + nT nT
362
3l
3no²
E[f((v,0) - (v, &
(oo -a)² +
+
36m²
21
2/12
2
K
A
25

---

Published in Transactions on Machine Learning Research (01/2026)
where = =2p[1 - p) is the strong concavity coefficient of a(v in a.
Proof. By the updates of w, we obtain
E E v0 E
Σ
Σ
a. [ivihhnn Skim (V a m (
MI
mEgai
E 2 - 1/2 S sfp
(38)
E c.k - 2 GP
E Am,t - a 1 $ 1/ K²G
Plugging Lemma 4.3 and Lemma B.4 into Lemma B.3, and taking expectation, get
([ a) (v)
E
36
36
p2
l/v0,0
+2
28
1
|1a+tiu- -a 1
E
2
2nK1
2nKT
61
U2
|10
all
u2
(a
aa)²
knKT
3
knKT
3
C2
v11
| v/1
kn
3
kn
3
Os
(la -00003
(a- (2)))
(1|v
1p - 1|v 1112
KT
KnKT
C4
36"
38
Σ
36
362
milll
am,)
2112
K
M
2
2/12
M
m
megai
3hKo²
MKI
(39)
Since 17 S min( / 1 thus in the RHS of (39), Ci can be canceled. C2, C3, C4 and Cp will be handled by telescoping sum. Ca can be bounded by (38).
Taking telescoping sum, it yields
(v) - (v(
38
38
3n0²
$ 4nEKI
1/vo - v + ETEKI
100
all2+
+
T6 +
2212
2
M
26

---

Published in Transactions on Machine Learning Research (01/2026)
B.4 Main Proof of Theorem 4.5
Proof. Since f(v, a) is E-smooth (thus Eweakly convex) in v for any a, Φ(v) = max f(v, also E-waklyy
a'
convex. Taking 7 = 26, we have
L 2 v1lva-1- -vll2
6(va-1) 2 (vv.) + (0o(v.), V--1 -va)
Va-1 - vv) + 3l
=vv,) + (0%(v.) + 22(v, - -V,-1),
|| - v.ll?
2
(4) o(v.) + (v.. (v.), Va-1 - -vo) + 3
|| - v.l12
(40)
2
( o(v.) 1 (06s (vb.(v.). (v.),v.00..v. (v.) 0b((v)) +
3
28
88
1
3
<vv.) 88
|10. (v3) 4e
(00, (v.),,((v.)) + [0d(vs))l?
8e
where (a) and (b) hold by the definition of (v)..
Rearranging the terms in (40) yields
1
3
Φ(v.) @(v. S
180 (v.) v2) + (80, (((v))
se [10cb(v=))
88
4e
(2)
1
3 +100(v+)))3)- ze 11d(v.))1
1r (v.))l
+ (1.0).
88
8P
(41)
1
10 (v.) (v.)(v.)
100((v))1
46
4e
(6)
1
|d (v.)
2e (o(v.) - -d(v.))
M
48
where (a) holds by using (a, b) S [[1aa]] + [[b and (b) holds by the p-PL, property of @(v).
Thus, we have
(48 + (p(vv d(v.)) -0( S [vo)(.
(42)
Since 7= 26, (v) is l-strongly convex in v and #22 2p(1 p) strong concave in a. Apply Lemma B.1 to f", we know that
[1a((a)) - vill + P2 ((a)(v)) - agl? s Gap, ag) + Gap,(Vv,
(43)
4
24 By the setting of 77 = 770 exp (-(s- 1) ct2 and T3 E,KI, = min( exp ((s -
212
11
c+2
we note
that n.T. S min(t,wa) Set I, such that
where the specific choice of I, will made later. Applying Lemma B.5 with (a,)) = arg min fv', aa) and â.(v.) = arg max ("v a'), we v
3r-
+
32
367 36 v n.o²
212
2uz
2
M
a'
have
4n.02
ll
[V)(as)) - voll2 + M2 (v,,(v)) - agl1?
+
M
53
4
4
(44)
4n.02
+
E
(GGap, an) + (v,
M
53
27

---

Published in Transactions on Machine Learning Research (01/2026)
Since Φ(v) is L-smooth and Y 26, then dv(v) is = (L + 20)-smooth. According to Theorem 2.1.5 of (Nesterov, 2004), we have
= 2LE(o.(ve) min o, (v)) - (VE sER
-2LE|4Gap, as) - 3Gap, av)
Am,.02
+
(Gap, (Vo. ai) + Gap, (v.,
(Vs, ax))
-3Gap, (vs,as)
(45)
M
53
1
4
155
2LE
+
Gap, ag)
Gap, (Ver
M
53
53
Applying Lemma B.2 (45), we have
16
Blllöo. || < 2ÎE
Gap, (vi. ag)
M
53
155
3
Gap (vot1 (att))
( + 4
( -v(v)))
(46)
53
50
5
16m
4
93
124
+
Gvp, ag))
Gap +1 (vo+)
s+1
.00
(d(v <(vi))
M
53
530
53
Combining this with (42), rearranging the terms, and defining constant 4l + 53
248
O(L + E), get
93
(c+ 2p) Blo(vo - x(v+)]
LE LE (vo* a0 [
265
248
7i
32m, Lo² M
<
4l
53
i BlØ(vv) - o(v+)] +
53
GlGap, azll +
(47)
((vi) <(v.)= + 8i
32n
s cE
Gap, (vo, an) ag)
+
53c
M
Using the fact that i 2 14
248 53
7L
16μ1
93
(c 2n))
48 +
+ 24x
L.
(48)
53c
53(4F +
248
T.
53
248
265
53
Then, we have
8i.
(c 2 Φ(vo+1) p(v.)) + Gap, Gap (vy .1
53c
(49)
si 53c
32
< cl o(vi) -(v.) + Gap, (vo. añ)
M
Defining A, = ((vi) <(v.)
st Gap, (vō, az), then 33c
B[A.] 321r L2
Lo
E[A c 2p
(50)
(c+ 2
Using this inequality recursively, it yields
32L0²
8-8
E|As+1l <
c 2/
E +
(c 2 M
Σ
7)
c+ 2/1
(51)
am1
28

---

Published in Transactions on Machine Learning Research (01/)026)
By definition,
8f.
A <(v)) =((v)) + Cap, (v aip)
53c
o(vo) - 6(v") + (f(vo, âi (vo)) + 2 3 f(vi(ao), - (10) -vol) (52)
53c
7L
< 53c
(S di (vo)) - s(V(an), S 260.
Using inequality
x S exp(-x), we have
-2u5
32tHoLo2
8
2
E E[As+1] S exp
BIA1] +
Σ exp
c 2/1
(c + 2n)
c + 2/1
a=1
-25
32moLo2
24.8
2cD exp
+
Sexp
c+ 2p
(c + 2p)
(c+ + 2μ))
To make this less than 6, it suffices to make
2ps
2eg exp
S 2'
c 241
(53)
32 Lo
(-
2
S Sexp
(c + 2
c 24
2
Let S be the smallest value such that exp
-205 c+2
min (c+2u)Me)
We can set S
4eg 6.5
max
c+22 2p
log
LSp den c+2 log [c+2p)Me 2p
Then, the total iteration complexity is
s
Σ
T. 50
424
Σ exp (s
2p
77 min(i,
u2)
C
+ 24
exp(S
S
2p
50
c+2p
70 min (,2
expl c+2H
2u
6n
(54)
7o/1 Mommmn (E, p2) max
(ct 24)
Tou H2 n² miminf u2 Me Me 1)
(L+ 1)00
(L+ 2)
max
5 max
where (a) uses the setting of S and exp(x: x. and Ô suppressos logarithmic factors.
T/. = no expeep((1 1) 2p T.
o42
212 exp - 1)
2p c+
7012
Next, we will analyze the communication cost.
To assure
3l 31 36n² 12 K2
which we used in above proof, need to take 1, =0 1 M
2pp
K /nn.
If K ToM
S 0(1), for < S2 = O 2
log (M())) we take then I, = and correspondingly E, = T KI, and correspondingly E, = TT/KK, = O/KM extp://xxppsssssss/ 1)
exp((== 1) p
T./K, For s > S2, I, = 0 K(10
29

---

Published in Transactions on Machine Learning Research (01/2026)
We have
S2
S2
212
c + 2p1 ) =0 M
2/r
T,
exp
(s (6-1)_
1)
(55)
7/u
Thus, the communication complexity be bounded by
S2
T. I
K
(s () c-2u
T
Σ
Ō
-
+
VMKKN exp
S=S++1
(56)
$ 0 M
exp
8 2p
2
c+2
-11
M
K
+ VK
S 0
+
12/221122
exp
c+2p
C Analysis of CyCp-FedX
In this section, we show the analysis of Theorem 5.2.
Proof. We denote
G.(w, w', V
V/1 (/((wzz)
Be(w;,,w';z)
7h(w:2)
(57)
Gme.1 = V Vib(h((w o. m,,,,) 12,5 Vhi
w m. 2,mee,1
G
m, (20h(hi, hiw m.t: 2,2 Vh( m. 2m..2
With 7j = 171,
L F(w F(w < VF(ww.))) TW w0.0 + wet11
we.
K Σ k=1
L Illwet20 w0
= =-iVF(wSoj MT
Gmm + Ge. Gmh
L Gmm)))
-V VF(w" -- 1.0) + VF(w
1| w
MT
2
k= m
<
1
|VF(w
VF 10 27 L
( m.t.1 + Gr,,,,)))
2T.
MT
km mega.A t=1
K
- -VVF(W=-.0)) 1.00T
MI Σ
Σ
Goah + Gm.t.2 + ||
w 1-100 m.
k= m 1=1
(58)
30

---

Published in Transactions on Machine Learning Research (01/2026)
Denoting k', ,, m', mm, t', ft as random variables corresponding to be the indexes that used passive parts at k m, 1
K
E
FVF(W= LOJT
1
Σ
Σ
Σ
GG m,,,1
+ mm.12)
MI
k=1
mega.
K
-
/VF(W 100
Gi(w
mitt m, We w
(m(()))) + G2(w, 1,0"
2 me" 10 11
2-1
W
mit Z m,
M1
mEge
G1(( 1,0 c,k
m, : W
1,0 2-IKk)
G2(we-1, 1,0 2-1,k"
,t W 1,0
2 zekk
2,,,,2)
Gi(wi (wee--1, c.ke
m,11 W 1,0
= G2(we-1,)
axm ,23 we 1,0 (mm,).2)
1-1,8"
1, 1
Σ
Σ
W/ - w0-101)2)- 1,7
Σ
E
w=
K
MI
MI
mega.
k' m'ESe 1.
ījК
FF - E
IKVF(W--L.))
1
Σ
(w 100)
K
KE[K]
< 1
- 167KL²
KMI Σ Σ
Σ
w0.0112
h mEGe.k
- SMKL2
Σ Σ
Σ
W
e--kk mi,e
w 1e-1.0
Bl/VF(W--L.))
KMI
2
m'eS- 1,K'
(59)
where the (a) holds because
)
G1(w--1.0 1,0 zokk
1m
w--10 2 + fe((w-11
2 m", w w=-10 1.0
z0-1,"
mm,t.2)
ze,
VF(W
(60)
By the updates of w, we obtain
K MI
E w 1.0 100
ip
Σ
Σ
Gee
m.a1 + Ge.k
1=1 meG
=
Σ
eik ((r
mi m,t,1 2 m
W-1KK e-1,k'
Gz(w
Gz
mmm W 2mm" , m.)))))
e-1,""
e-1k"
w we e.k
MI
1=1
megei
< E
MI Σ
Σ
(w milt Lmat
wo-l 2--1K) G
2--1"" w
m,t eiN 2m,),2)
mEgaik
Σ
(
1.0 eik 1m m +
G2(we-1.0
e-1,k"
1-10 2 m,,,t,))
MT
mm 1
k= mega.
3
E (GI
c,k
1-10 c-1,k 2
G2(w
e-1,k" 2mm
m,,)))) V
VV((w=11,))
V.
MI
mEg
+ F
(61)
31

---

Published in Transactions on Machine Learning Research (01/2026)
which leads to
E
w wyet
1,0
12
i k
k
2 6nj K2
E Ellw mit - w0.0 + 6ij K²
Σ
Σ
B Bllw
1- 1,k'
mi - -w--1012
KMI
KMI
$=1mege.
k=1 mega*
i?
+ 6if2 K2
we. we-1.0112
KMI
meg
K
Σ
Σ E
I(GI(W
10 a.k
( + G2(w" (0
1.0 2-11K" p2 wSo m.tt)) - (W
KMI
k=1 mEga
+ K2
(62)
Therefore,
E
E
W
1,0
w2:0112
E
K
L K
61 2
Σ
Σ
B w. noit - w2 + K2
Σ
W
1.1k
w
11
E
KMI
KMI
k= mege.k
k= mEg
L
K
Wortee - 1--1.0 + 67j² K2 0²
+
K2
Σ
Σ
Σ
Bll Bl|w
KMI + 3 T V
KMI
k=1 meg
(63)
w m,t
1 =1²²
me, + Gm,,,)
1=1v=l
1 k
=
=ii²B
Gi m. 2 W er e-1,5'
m' Imm' x22) + G2(w (w e-1,-" o-1,"" oT
30 2mm mas m,,,,
T
< E
7
G1 m. m Word ( G2 W wo-l.""
2
G1(w
2 1-0 2 2112) + Gy(we-1,0,
2mm 1 11 w e-11 1,0
2 mm..))))
+ E
7
G Gi(w
2m 1- 1.0 22-11 ) + G-(we-1.0
1,0, 20-1.""
, 11 w 1.0 (,.,))) V VF
+ 11
- -F + 4
V FF 1.0 11
s=lv=l
K
/ S - + 8 i K
<
wee 1=
I
==
=1172k2
47 k2 D2
FF 1
(64)
32

---

Published in Transactions on Machine Learning Research (01/)026)
ΣE
EE mEga.k
Σ
/w m.t
EKMI
E K
E K
I L2 K
ΣE
E
WI m.
KI
- w 8 12
ΣΣ E Σ
[K]llwe w=
T BKMI m
e
7=l
MES
+ -1j K 0²
T + K2 + 4n K2
Bl
E
(65)
1
ΣE E
weck mit
10
EKMI
mEGa.
-we-20012 + 8rj² K +88 V (66)
<161j i2K
|ww.D
Using iiK & 0(1),
EKMI EE
Σ
Σ
w m.e 10 s 1612 K xx- 161 160j2K2 K²a² +16722 K2 V
0²
VF 1.0
(67)
mEge.
and
1
E
w < 161 K o² r1
B w
+ KF 1 11
(68)
E
MI
Plugging these bounds into (58) and (59),
F(w*+1.0g - F(w S 1' - -w- 1-1001 + 22²2² (.2K]) [|| - 1-
161j 12 MI
Σ
Σ / we:012
E v F (we-100112
(69)
2
mego.k
1 E
Σ E VF - )12 =0
F((WrD)) F(W.)
+ +ipk σ² x2² + 24i o² KMI
(70)
iKK
Since nI. Set = M)) O MK.), E= })) itcration complexity is EKI 0 (MM)) and communication cost is EK 0 (3)
D Analysis of CyCD-FedX with PL condition
Below we show the proof of Theorem 5.3.
Proof. Using the property of PL condition, have
F(w++100-- - F(w.) < 2μ
V VF
(71)
33

---

Published in Transactions on Machine Learning Research (01/2026)
To ensure We need
I [VF(w*+l.0]) S pcs. Let co maxx(F(w0.)) -F(w.), /F((>90)) 112/H.
F(w*.0) F(w.))
Mee
iKK
3
if K2² a²
<
(72)
3
ijK d²
166.
KMI
3
where
(73)
Let T7. = O -( o² ) La = 0
MK MK.. ), E, (, ). The number of iterations in each stage is L,Es
o²
To ensure Eg S e, total number stage is log(ue). Thus, the total iteration complexity is MKptr,"
8 Σ
- 2
) = 0 MK
(74)
MKK2E
8=1
==1
Total communication complexity is
$ Σ
K
F,K 0
K) 0
(75)
2 1/2
1/3/2
E
Data Statistics
Dataset
Split
Positive Samples
Negative Samples
Positive %
Training
224
40,505
0.55%
Validation
505
4,495
10.10%
CIFAR-10
Test
1,000
9,000
10.00%
Training
227
44,546
0.51%
Validation
46
4,954
0.92%
CIFAR-100
Test
100
9,900
10.00%
Training
1,994
74,480
2.61%
Validation
625
10,594
5.57%
ChestMNIST
Test
1,133
21,300
5.05%
Training
2,863
4,028,888
0.07%
Validation
265
1,059,07 0,08
0.03%
Insurance
Test
132
1,085,055 ,053
0.01%
Table 7: Data statistics (without flipping).
F More Experimental Results
In this section, we show ablation studics to test the algorithm performance under differont scttings.
In Table we show experiments of varying number of clients. The advantages of our methods are preserved.
Table 9 reports the results over three independent rounds of random data removal and, for each round, three runs with different random seeds. Our methods consistently outperform the baselines across all repetitions.
34

---

Published in Transactions on Machine Learning Research (01/2026)
Table Ablation Number of Clients (dir=0.1, flip=0)
Cifar-10
Cifar-100
50 client
200 clients
50 client
200 clients
CyCp-FedAVG
0.7227 0.0015
0.7846 0.0011
0.8817 = 0.0020
0.8920 : 0.0018
A-FedAVG
0.7418 0.0026
0.7923 = 0.0016
0.8756 + 0.0025
0.8973 + 0.0012
A-SCAFFOLD
0.7450 0.0024
0.7940
0.0013
0.8866 - 0.0017
0.9012 1 0.0015
RS-Minimax
0.7372 + 0.0018
0.8012 = 0.0006
0.8994 = 0.0013
0.9183 + 0.0013
RS-Pairwise
0.7721 0.0014
0.8225
0.0010
0.9188 + 0.0012
0.9422 0.0021
CyCp-Minimas
0.8209 0.0012
0.8478
0.0016
0.9275 + 0.0022
0.9365 + 0.0016
CyCp-Pairwise
0.8367 0.0013
0.8448 = 0.0017
0.9647 + 0.0015
0.9653 0.0019
Table 9: Repeated Experiments on Randomly Removing Data. (dir=0.5 for Cifar-10/100)
Cifar-10
Cifar-100
CyCp-FedAVG
0.8083 0.0175
0.8815 = 0.0073
A-FedAVG
0.8123 = 0.0037
0.9006 = 0. 0.0052
A-SCAFFOLD
0.8208 0.0041
0.9016 = 0.0039
RS-Minimax
0.8225 = 0.0028
0.9342 + 0.0044
AS-PParrwise
0.8303 = 0.0019
0.9541 = 0. 0.0037
CyCp-Miuimax
0.8460 0.0060
0.9422 = 0.0029
CyCp-Paine Pairwise
0.8503 = 0.0048
0.9730 + 0.0055
In Figure 2, divide the data into 10 client groups with 10 clients per group. By varying M, which is the number of simultaneously participating clients, we observe that larger values of M lead to faster convergence, confirming the expected speed-up effect.
In Figure 3, we randomly partition the clients (N 100) into different numbers of groups. each round, a single client is sampled participate. We observe that larger values of K generally lead faster convergence, while the case K essentially reduces to the randon-sampling baseline. In real-world deployments, naturally formed groups (e.g., by geography, device type, availability pattern) may exhibit internally similar data distributions. Splitting such groups into smaller ones may cause the model to overfit to a narrow distribution before sufficiently exploring others. Therefore, the optimal choice of K depends on the underlying real-world heterogeneity and grouping structure. more systematic investigation of how interacts with real data distributions is an important direction for future work.
Cifar-10, Minimax
Cifar-10, PSM
Testing AUC
Testing AUC
M-1
M-1
M=2
M-8
Number of iterations (+30k)
Number iterations (*30k)
Figure 2: Ablation Study: Effect of the Number of Simultaneously Participating Clients M (dir 0.5, flip
0)
G Applicability to a Broad Class of AUC Maximization Formulations
Table 10 lists multiple AUC-consistent losses and their compatibility with algorithms.
35

---

Published in Transactions on Machine Learning Research 2016)0
Cifar-10, Minimax
Cifar-10, PSM
Testing AUC
Testing AUC
3.1
K=1
K=1
K=10
641
K=10
K=50
K=50
K-100
K-100
Communication Rounds (-1k)
Communication Rounds (-Ik)
Figure 3: Ablation Study: Effect of the Number of Client Groups (dir 0.5, flip 0)
Table 10: Applicability to Different Formulations of AUC Maximization (m denotes margin constant as hyper-parameter, and denotes scaling hyper-parameter).
Loss
Formulation
Applicable?
Minimax Loss (Ying et al., 2016)
(3)
Yes (Algorithm 1,2)
Pairwise Square (Gao et al., 2013)
(1) with (ba b) (m (a 1o--00 b))²
Yes (Algorithı 3,4)
Pairwise Squared Hinge (Zhao et al., 2011b)
(1) with ((a, = (m (a - bb)b
Yes (Algorithm 3,4)
Pairwise Logistic (Gao Zhou, 2015)
(1) with (a b) log(1 + exp(-a(a- b)))
Yes (Algorithm 3,4)
Pairwise Sigmoid (Calders & Jaroszewicz, 2007)
(1) with vi(a,
(1 + exp(s(a b)))
Yes (Algorithm 3,4)
(1) with v(a, b) = max(m - 7(m + t),
Pairwise Barrier Hinge (Charoenphakdee al., 2019b)
Yes/No'(Algen)
3,4)
max(r(t m),
t)), where 1=
q-norm hinge loss
(1) with (/a b) = (m (a-
Yes (Algorithm 3,4)
For the Pairwise Barrier Hinge loss, our algorithmu remain directly applicable. However, because this surrogate does not satisfy the smoothness assumption, it does not enjoy the linear speed-up guarantec in theory, which is a common limitation of nonsmooth FL objectives (Yuan et al., 2021a).
36


Reviews:
[{"review_id": "YXvWowT74d", "reviewer": "Reviewer_1VvX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles the problem of federated AUC maximization under the realistic constraint of cyclic client participation. Here, clients join training in a fixed schedule rather than being always available or randomly sampled. The main contributions are\n- Reformulating AUC maximization with squared surrogate loss as a nonconvex, strongly concave minimax problem. It proposes algorithm that accounts for deterministic client scheduling. \n- Demonstrating empirical evaluations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides rigorous theoretical analysis with lemmas and theorems establishing convergence rates and communication complexity bounds. It carefully addresses the bias introduced by cyclic scheduling using virtual sequences and delayed gradient decomposition.", "audience_yn": "Yes", "audience_explanation": "- TMLR’s audience includes researchers in federated learning, optimization, and machine learning theory.\n- The paper addresses a practical and underexplored problem, which is cyclic client participation. It common in real-world deployments.", "requested_changes": "There are some notational inconsistencies such as,\n- In equation 5 is $F(w, a, b, \\alpha, z)$ was supposed to be $F(w, a, b, \\alpha; z)$ which is also defiend later?\n- Sometime $h()$ is used as $h(w;z)$ and sometime it is $h(w,z)$. These are confusing.\n- Since the analysis uses multiple notations, all of them must be clearly defined in the preliminary, such as $v \\in \\mathbb{R}^{d+2}$ because $v = [w,a,b]$. In algorithm 1 what is $v^{e+1}\\_{m}$ and how does this relate with $v^{e,k}_{m}$. \n- Furthermore, add an overview of the algorithm to strengthen its readability.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JFrnK5zW5w", "reviewer": "Reviewer_1g59", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies federated AUC maximization under a practical client-participation scenario. Federated learning operates in privacy-sensitive settings with decentralized and often non-IID data, making classical ERM less suitable and motivating the use of AUC maximization for class-imbalanced tasks. While much prior work assumes full client availability, this paper instead focuses on a more realistic participation pattern: cyclic schedules.\n\nThe authors consider two surrogate loss families. Under the squared surrogate loss, which leads to a minimax formulation, they analyze the cyclic participation setting where independent client sampling does not hold. The proposed stage-wise algorithm achieves the same communication rate as full participation under a PL condition, suggesting that cyclic schedules do not degrade communication efficiency.\n\nThe second setting addresses more general pairwise surrogate losses. Here, the paper proposes an active–passive algorithm with gradient sharing, which attains competitive communication complexity and can accommodate delays of up to two full cycles.\n\nThe empirical evaluation spans multiple datasets representing common FL application domains, with class imbalance and heterogeneity appropriately simulated. The experiments vary heterogeneity levels and noise conditions, and include ablations on communication efficiency, collectively illustrating the scalability and robustness of the proposed approach.\n\n**Strengths**\n\nThe theoretical development is sound and well aligned with the algorithmic design, the methods are clearly presented, and the empirical evaluation spans multiple application domains. Importantly, the paper focuses on a practical and underexplored participation scenario, which is conceptually valuable and may inspire further work on realistic FL settings.\n\n**Weaknesses**\n\nThe motivation and introduction could be clearer, especially in explaining the practical meaning of the setups, and the experiment section would benefit from additional ablations to fully support some of the theoretical claims. In addition, the gradient-sharing mechanism raises potential privacy concerns that would benefit from brief discussion.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical analyses under both loss settings support the proposed algorithms, and the empirical evaluation covers diverse domains, suggesting reasonable coverage of practical FL scenarios. Overall, the main claims appear plausible, though improving clarity would strengthen the supporting evidence.", "audience_yn": "Yes", "audience_explanation": "This work encourages the community to move beyond idealized FL assumptions and consider more practical deployment factors, including realistic participation patterns and class imbalance in non-IID settings. By highlighting the underexplored cyclic participation scenario, it contributes to research on federated optimization, fairness, and communication efficiency. Combined with empirical evaluation across diverse application domains, the findings may stimulate broader discussion on practical FL settings and non-IID challenges in real-world deployments.", "requested_changes": "**Clarity and Motivation:**\n\n1. The authors may consider moving some formulas out of the introduction or placing them later in the paper. They interrupt the narrative and may hinder readers from understanding the high-level motivation (your storyline).\n2. Please provide a practical explanation or real-life example illustrating how these sets arise (beyond formulas). This would help readers grasp the relevance of the AUC setup.\n3. A concrete example from real deployments would strengthen the motivation and clarify why and how valuable the scenario cyclic schedule is in practice.\n4. The paper focuses on two surrogate loss families. Could the authors explain why these two are particularly appropriate, and whether other losses might also satisfy similar assumptions or can be generalized from here?\n5. Section 2.2 would benefit from a revised explanation from an application perspective. Clarifying the practical meaning of these schemes would make the presentation more aligned with the paper’s motivation.\n\n**Experimental Details:**\n\n1. Please clarify how data were removed to form the binary subsets and whether this procedure reliably simulates real class imbalance. How many times were these simulations repeated? Since Appendix E suggests that some datasets may contain very few positive samples, repeated runs may be important for obtaining stable results.\n2. Additional ablations examining how performance scales with an increasing number of clients would further strengthen the empirical section. It would also be good to confirm whether it is necessary to include experiments that directly support or validate the claims in Theorems 5.2 and 5.3.\n3. Since participation patterns may depend on the number of clients, could the authors provide experiments showing whether the proposed advantages persist as the client count changes?\n\n\n**Presentation & Formatting:**\n\n1. Table caption font size: decrease font size for readability in captions.\n2. Figure 1 image size, redesign: 2×2 layout or slightly larger font may make the figure clearer.\n3. Table formatting: The authors may consider using \\small fonts in tables for numbers.\n4. Table 2 caption has a missing parenthesis, and captions should include the evaluation metric for clarity.\n5. Section 5: “enough” is misspelled, and please check the manuscript for other minor typos.\n\n\n**Discussion and Limitations:**\n\n1. Broader applicability / general impact: The paper mentions potential broader impact in section 5 but does not concretely explain how the approach can extend to other application domains. A short discussion or example would help.\n2. Limitations and future work: A brief paragraph reflecting on limitations (e.g., assumptions on the PL condition, privacy implications of gradient sharing) would improve completeness.", "broader_impact_concerns": "One potential concern is gradient sharing in the active–passive method. Sharing gradients may leak sensitive information unless additional protections (e.g., differential privacy) are considered. And this is also a broad topic in FL. The paper would benefit from at least a short discussion of such risks and mitigation strategies. Beyond this, the work does not appear to pose major ethical or societal risks.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AQ3RaaeM7u", "reviewer": "Reviewer_M6NE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "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": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies federated AUC maximization under cyclic client participation, a realistic setting where clients join training in a fixed, repeating schedule rather than through random sampling or full participation. The authors make the following contributions:\n- Minimax Formulation: For AUC maximization with squared surrogate loss, the authors develop a stagewise algorithm with novel auxiliary sequences to handle biased gradient estimates under cyclic scheduling. Under the PL condition, they achieve $\\tilde{\\mathcal{O}}(K/(\\mu^{3/2} \\epsilon^{1/2}))$ communication complexity and $\\tilde{\\mathcal{O}}(\\hat{L}/(\\mu^2 M \\epsilon))$ iteration complexity, matching rates from full-participation settings.\n- Pairwise Formulation: For general pairwise AUC losses, they propose an active-passive gradient decomposition strategy that shares prediction scores across clients. Without PL: $\\mathcal{O}(K/\\epsilon^3)$ communication and $\\mathcal{O}(1/M \\epsilon^4)$ iteration complexity. With PL: $\\tilde{\\mathcal{O}}(K/(\\mu^{3/2} \\epsilon^{1/2}))$ communication and $\\mathcal{O}(1/(\\mu^2 M \\epsilon))$ iteration complexity.\n- Technical Innovation: Introduction of virtual sequences,  that decouple dependencies between client groups, enabling convergence analysis despite deterministic cyclic ordering, a key departure from random sampling analyses.\n\n# Strengths:\n\n- The paper addresses a practically important yet theoretically underexplored setting. Class imbalance is common in FL (e.g., medical, finance), making AUC maximization a more suitable objective than ERM. Addressing this under the realistic (but complex) cyclic participation setting is a valuable contribution.\n- The paper provides a comprehensive and rigorous theoretical analysis for both the minimax and general pairwise formulations. The development of auxiliary sequences and the analysis of the two-cycle delay are non-trivial and effectively address the challenges of the deterministic schedule.\n- A key finding is that the proposed cyclic-aware algorithms achieve convergence rates (both iteration and communication complexity) that match the best-known rates for the simpler random-participation setting. This strongly suggests that cyclic participation, when handled correctly, does not inherently degrade asymptotic efficiency.\n- The experiments are conducted on a diverse set of tasks, including vision, medical, and tabular fraud data. The inclusion of a large-scale, naturally heterogeneous fraud dataset (50 clients) is a good addition. The ablation study on local steps (Figure 1) also effectively supports the claim of communication efficiency.\n\n# Weaknesses:\n- A major weakness is the ambiguity in the definition of \"cyclic client participation.\" The introduction and abstract describe it as clients joining in a \"fixed, repeating schedule\". However, Algorithms 1 and 3 describe a process of cyclically iterating through $K$ groups (for $k \\in [K]$) and then randomly sampling $M$ clients from within that group (\"Sample M clients from k-th client set uniformly at random w/o replacement\"). This appears to be a hybrid \"cyclic-group-random-client\" model, not a standard \"cyclic-client\" model (like in Cho et al. 2023 ). This discrepancy between the paper's premise and its algorithms is confusing and needs to be clarified.\n- The experimental comparisons are not sufficient to validate the paper's core contribution. The proposed methods (CyCp-Minimax, CyCp-Pairwise) are compared almost exclusively against ERM baselines (CyCp-FedAVG, A-FedAVG, A-SCAFFOLD). It is already well-established that AUC maximization methods outperform ERM methods on imbalanced data. The current experiments (e.g., Tables 1 and 2) primarily re-demonstrate this known fact, rather than demonstrating the necessity of the proposed cyclic-aware AUC algorithms.\n- To properly situate the contribution, the experiments must include comparisons against SOTA Federated AUC Algorithms (Random Sampling): The performance of methods like Guo et al. (2020), Yuan et al. (2021a), Guo et al. (2023a),  using standard random client sampling. This would provide a direct comparison of the performance (e.g., final AUC, convergence speed) of the cyclic vs. random participation schemes.\n- The abstract states the communication complexity for the minimax problem is $\\tilde{O}(1/\\epsilon)$. However, the introduction and the formal result in Theorem 4.5 both state it is $\\tilde{O}(1/\\epsilon^{1/2})$ (under the PL condition). The $\\tilde{O}(1/\\epsilon)$ rate from the abstract appears to be the iteration complexity. This should be corrected for clarity.\n- The transition from biased gradient estimates to unbiased analysis via auxiliary sequences (Lemma 4.3) requires clearer exposition of which random variables are being conditioned on.\n- Algorithm 1 references client set $G^{e,k}$ in line 4 but uses $S^{e,k}$ in subsequent lines without clear definition. \n- The transition from single-stage (Algorithm 1) to multi-stage (Algorithm 2) framework lacks an intuitive explanation.\n- The choice of $\\gamma = 2l$ appears arbitrary and lacks justification.\n- The paper doesn't discuss computational overhead of maintaining auxiliary sequences or historical prediction scores ($H^e_1$, $H^e_2$).\n- In Algorithm 3, line 20 mentions \"Update buffer $B_{i,1}$, $B_{i,2}$ using $R^{e,k-1}{i,1}$, $R^{e,k-1}{i,2}$ with shuffling\". What is the shuffling procedure, and why is it important? Specify buffer size management for $H^e_1$, $H^e_2$.\n- How does the method perform when the number of groups $K$ varies? Is there a sweet spot for $K$ given $N$ clients?", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical claims are extensively supported by detailed proofs in the appendix. The empirical claims (i.e., that the proposed methods outperform ERM baselines) are supported by the provided tables. However, as noted in the weaknesses, the evidence is insufficient to support the more crucial implicit claim: that these new algorithms are superior to existing AUC algorithms in the cyclic setting.", "audience_yn": "Yes", "audience_explanation": "This paper is a strong fit for the TMLR audience. It addresses a core machine learning problem (AUC maximization), applies it to a major research area (federated learning), and provides a rigorous, in-depth theoretical optimization analysis.", "requested_changes": "See the above weakness section.", "broader_impact_concerns": "Not applicable. This work is theoretical and algorithmic, focused on improving optimization methods. It does not appear to have immediate, direct broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)