Communication-Efficient Federated AUC Maximization with Cyclic Client Participation

AI summary

Overview

Research area: Federated learning (FL), specifically federated optimization for non-decomposable objectives — Area Under the ROC Curve (AUC) maximization — under a cyclic client participation schedule.

Technical level: Advanced. The paper is a theory-heavy optimization paper: it builds on nonconvex–strongly-concave minimax optimization, the Polyak–Łojasiewicz (PL) condition, stagewise algorithms, and convergence-rate analysis in terms of ε-accuracy, alongside an empirical evaluation.

One-sentence scope: The paper develops and analyzes communication-efficient federated AUC maximization algorithms for two loss families (a squared surrogate loss and general pairwise AUC losses) when clients participate in a fixed, repeating order rather than being fully or randomly available.

What This Paper Is About

Federated AUC maximization is useful when data are class-imbalanced, because it directly optimizes the AUC metric instead of an aggregate surrogate loss that can bias models toward majority classes. Existing federated AUC methods assume all clients are available every round or that a random subset is sampled each round, which the authors argue is rarely practical. This paper studies the realistic case where clients join in a fixed, repeating schedule (cyclic client participation, CyCP) and asks whether communication-efficient convergence guarantees can still be achieved for the non-decomposable AUC objective.

Key Contributions

1. Federated nonconvex–strongly-concave minimax under cyclic participation. For the squared surrogate loss ψ(a,b) = (1 − a + b)², the authors reformulate AUC maximization as a minimax problem and design a stagewise algorithm in which each stage runs multiple full cycles of communication across all client groups in a predefined sequence. They introduce auxiliary "virtual sequences" that track model states at cycle boundaries, bounding the drift caused by biased updates within a cycle and decoupling error propagation across client groups. Under the PL condition this yields communication complexity Õ(1/ε^{1/2}) and iteration complexity Õ(1/ε), matching the best-known rate in the full-participation setting.

2. Federated pairwise optimization. For general pairwise AUC losses (e.g., sigmoid), where the gradient couples data across all clients, the authors design an active–passive algorithm that splits gradients into locally computed (active) and shared (passive) components. Their analysis traces model updates back to the start of the previous cycle, and unlike prior work must handle a delay of two full cycles. This yields communication complexity O(1/ε³) and iteration complexity O(1/ε⁴), improving under the PL condition to Õ(1/ε^{1/2}) and Õ(1/ε).

3. Empirical evaluation. The methods are validated on benchmark datasets spanning CIFAR-10 and CIFAR-100 (image classification), ChestMNIST (medical imaging), and a large-scale insurance fraud detection dataset.

4. A first-of-its-kind guarantee. The authors state that, to their knowledge, this is the first convergence guarantee for federated minimax optimization under cyclic client participation.

Main Findings

• Cyclic participation does not degrade the asymptotic rate (minimax case). For the squared surrogate loss under the PL condition, the method achieves communication complexity Õ(1/ε^{1/2}) and iteration complexity Õ(1/ε), matching the dependence on μ and ε achieved by Guo et al. (2020) and Yuan et al. (2021a) under the more idealized assumption of random client sampling.

• Linear speedup in the number of participating clients. The iteration complexity is Õ(L̂/(μ²Mε)), showing linear speedup with respect to the number of simultaneously participating clients M, i.e., Õ(1/(Mε)).

• Group count interacts with the local update budget. The communication complexity is Õ(K/(μ^{3/2} ε^{1/2})), and the authors set I_s = Θ(1/(K√(Mη_s))). They explain that a larger number of groups K introduces longer delays between consecutive client updates, increasing staleness and drift, so the local update count must be adapted to K to balance communication efficiency against error.

• General pairwise losses have weaker non-PL rates but recover the fast rate under PL. Communication complexity O(1/ε³) and iteration complexity O(1/ε⁴) without the PL condition; Õ(1/ε^{1/2}) and Õ(1/ε) with it. The O(1/ε³) communication complexity matches that of Guo et al. (2023a), which assumed random client sampling.

• Explicit stagewise parameter schedule. With L̂ = L + 2ℓ, c = (μ/L̂)/(5 + μ/L̂), γ = 2ℓ, η_s = η_0 exp(−(s−1)c), and T_s = 212/(η_0 min(ℓ, μ_2)) exp((s−1)c), the number of stages needed to reach 𝔼[φ(v_S) − φ(v*_φ)] ≤ ε is S ≥ O((5L̂ + μ)/μ · max{log(2Δ_0/ε), log S + log[(2η_0/ε)(12σ²/(5K))]}).

• Bias from deterministic scheduling breaks prior analysis. The authors note that under cyclic participation both primal (v) and dual (α) updates are complicated by deterministic client scheduling, which breaks the independent-sampling assumption and makes global gradient estimates biased, invalidating the convergence analyses of Guo et al. (2020) and Yuan et al. (2021a).

• Experimental numbers are not reported in the provided content. The abstract states that experiments on image classification, medical imaging, and fraud detection demonstrate superior efficiency and effectiveness, but the truncated content does not report specific accuracy, AUC, or speedup figures.

Methodology in Plain English

The setup: there are N clients split into K groups of N/K clients each. The server walks through the groups in a fixed repeating order (G¹, …, G^K). In each communication round, M clients are chosen uniformly at random without replacement from whichever group is currently active. Two special cases recover a fully deterministic schedule: K = N, or M = N/K.

For the squared-loss minimax problem, the algorithm is stagewise. Each stage solves a subproblem that penalizes deviation from the previous stage's output with a term (γ/2)‖v − v₀ˢ‖², where γ = 2ℓ is chosen so that the subproblem is ℓ-strongly convex in the primal variable. Inside a stage, the algorithm runs several epochs, each epoch visiting all K groups and having each participating client run I local gradient-descent steps on the primal variables (w, a, b) and gradient-ascent steps on the dual variable α. At the end of each group's turn, the server averages the returned primal and dual variables. Step sizes and epoch counts are then shrunk and grown across stages, which makes the duality gap decrease exponentially from stage to stage.

The technical trick is the introduction of conceptual "virtual sequences" — v̂^{e,0}, ṽ^{e,0}, α̂^{e,0}, α̃^{e,0} — that are never actually computed. They evaluate gradients at fixed reference points, letting the analysis separate the true gradient ("signal") from stochastic gradient error ("noise") and absorb the bias introduced by the cyclic order. This converts awkward cross-client coupling terms into a standard variance term plus a model-drift term.

For the general pairwise objective, the gradient of the loss couples every positive sample on one client with every negative sample on every other client. The authors split each gradient into an active part, computed from a client's own data with the current model, and a passive part, taken from scores that other clients shared in the previous epoch. Because passive components are delayed by a full epoch rather than a single round, the error dynamics involve a two-cycle delay, which the analysis handles by anchoring updates to the start of the previous cycle.

The analysis rests on standard assumptions: a bounded initial suboptimality gap Δ₀, the μ-PL condition on φ(v) = max_α f(v, α), ℓ-smoothness of f in v and α with L-smoothness of φ, bounded gradients (‖∇_v f‖² ≤ G²), and bounded gradient variance σ² for both the primal and dual updates.

Why This Matters

Impact on research. Prior federated AUC work assumed full or randomly sampled client participation. This paper shows that a structured, deterministic, repeating participation pattern — which is both more realistic and, per the cited literature, better for privacy because it strictly limits how often each client contributes — can retain the same asymptotic communication and iteration complexity. It supplies the first convergence guarantees for federated minimax optimization under cyclic participation and extends cyclic-participation theory (previously limited to empirical risk minimization) to non-decomposable objectives and general pairwise losses.

Real-world applications (drawn from the paper's motivating examples):

• Cross-device federated learning, where mobile devices operate in different time zones or charge at preferred times, producing naturally periodic availability windows.
• Medical imaging, where the paper evaluates on ChestMNIST and where data are class-imbalanced across hospitals.
• Fraud detection, where the paper uses a large-scale insurance fraud dataset and where positive cases are rare relative to negatives.
• Cross-silo federated learning, where institutions such as hospitals face planned constraints including large local datasets, internal network security policies, or scheduled IT maintenance windows.

Industry relevance. The paper's practical argument is that cyclic scheduling lets system designers group clients (for example by region or time zone) and sample within groups when a group is large, while preserving theoretical guarantees. Because the achievable rate does not degrade relative to idealistic sampling, and because iteration complexity scales as Õ(1/(Mε)) in the number of simultaneous participants, the approach is positioned as deployable on intermittently available fleets without paying a convergence penalty.

Future Directions

• Bridging theory and the reported experiments. The provided content does not report quantitative experimental results on CIFAR-10, CIFAR-100, ChestMNIST, or the fraud detection dataset; the empirical section and its numbers are not included in the truncated material.
• Extending the analysis beyond AUC. The authors point readers to Appendix G for compatibility with multiple specific AUC-consistent losses, and the pairwise formulation is noted to generalize to bipartite ranking and metric learning — natural targets for follow-up theory.
• Tightening the non-PL pairwise rates. The gap between the non-PL bounds (O(1/ε³) communication, O(1/ε⁴) iteration) and the PL bounds (Õ(1/ε^{1/2}), Õ(1/ε)) suggests room to investigate whether the PL condition can be relaxed or verified more broadly for pairwise objectives.
• Relaxing the standing assumptions. The analysis assumes bounded gradients and bounded variance, and empirically verifies the PL condition only via the cited prior work (Guo et al., 2023b); understanding behavior when these fail, or with heterogeneous and adversarial availability patterns beyond a fixed cycle, remains open.

Target Audience

Researchers and graduate students in federated learning and distributed optimization who work on non-ERM objectives, minimax or compositional optimization, and convergence analysis. It is also relevant to practitioners designing real-world FL deployments with intermittent client availability, and to readers interested in AUC maximization for imbalanced data in healthcare, finance, and mobile settings. A working knowledge of convex analysis, smoothness and PL conditions, and standard federated optimization notation is assumed.

Authors’ 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/ε^{1/2})$ and iteration complexity of $\widetilde{O}(1/ε)$. Second, we consider general pairwise AUC losses. We establish a communication complexity of $O(1/ε^3)$ and an iteration complexity of $O(1/ε^4)$. Further, under the PL condition, these bounds improve to communication complexity of $\widetilde{O}(1/ε^{1/2})$ and iteration complexity of $\widetilde{O}(1/ε)$. Extensive experiments on benchmark tasks in image classification, medical imaging, and fraud detection demonstrate the superior efficiency and effectiveness of our proposed methods.