1
F EDE R AGE: Provably Convergent Agnostic Federated Learning under General Client Drift Herlock (SeyedAbolfazl) Rahimi and Dionysis Kalogerias, Senior Member, IEEE
arXiv:2609.21057v1 [cs.LG] 17 Sep 2026
Abstract—Federated learning (FL) enables collaborative model training without sharing raw data, but its performance degrades under non-IID data and stochastic client participation. Remedies built on classical Federated Averaging (FedAvg) typically presuppose that client participation probabilities are known to the server, which is rarely the case in deployed systems. We first discuss and then characterize the optimization problem that distributionally agnostic FedAvg actually solves when participation is entirely unknown, possibly highly skewed, and of variable size across rounds: uniform aggregation is shown to minimize a well-defined stochastic objective, weighted √ by the participation-induced marginal, at a standard O(1/ T ) rate for convex and possibly nonsmooth losses. Building on this characterization, we propose Federated Risk-Averse Averaging (F EDE R AGE), a risk-averse extension of FedAvg that embeds the Conditional Value-at-Risk (CVaR) into the local objective within a natural distributionally robust optimization (DRO) framework. F EDE R AGE implicitly upweights high-loss and infrequently participating clients √ while adding only a single scalar per-client, and admits an O(κ/ T ) rate in which the factor κ is the upper bound on the “price” of risk aversion. In contrast with aggregation-alignment schemes based on optimal transport, which require the availability distribution as an input, F EDE R AGE remains agnostic to it. Several experiments on three heterogeneous benchmarks indicate consistent improvements over state-of-the-art methods in accuracy, fairness, and convergence speed. Index Terms—Federated learning, distributionally robust optimization, conditional value-at-risk, risk-averse optimization, client heterogeneity, partial participation, convergence analysis.
I. I NTRODUCTION
F
EDERATED learning (FL) allows a population of distributed clients to collaboratively train a shared model without exchanging raw data, thereby preserving privacy and reducing communication overhead [2]–[8]. In synchronous FL, each communication round proceeds as follows: a central server broadcasts the current global model to all clients; each client updates the received model locally on its private dataset (the local rounds); and a subset of active clients then transmit their updated parameters back to the server. The server aggregates the received parameters—most commonly through Federated Averaging (FedAvg) [3], [9]—and the process repeats until convergence (see Algorithm 1). The efficiency, stability, and fairness of this decentralized procedure depend not only on the local data distributions but also on the stochastic availability of the clients. Performance degradation in FL systems can be traced to two principal sources of heterogeneity. The first is statistical (data) heterogeneity: clients often possess non-IID data due to personalized usage patterns, device contexts, or geographical factors [10]–[12]. This induces client drift, the divergence of local optimization trajectories, which slows or destabilizes aggregation and degrades generalization; this has been studied extensively in This work has been supported by the US National Science Foundation under Grants 2242215 and 2431860. Preliminary results leading to this paper were presented in part at the 2025 IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) [1].
Fig. 1: Motivating example: Interaction of statistical heterogeneity and skewed availability. Five clients possess highly nonIID data (clustered by user). Client availability is skewed: three clients participate with probability 0.3, two with 0.05. Top: learned decision regions after training. Bottom: test accuracy versus communication rounds. FedAvg overfits to frequently available clients, degrading accuracy for infrequent ones and slowing convergence. FedeRage (proposed) mitigates this bias, converging faster and attaining higher final accuracy under the same non-IID and availability regime. the FL literature [13]–[18]. The second source is system and participation heterogeneity: clients differ in computational capacity, communication bandwidth, and, most critically, availability. Unlike classical distributed optimization with deterministic scheduling, client participation in FL is inherently stochastic, constrained by factors such as network connectivity, battery state, and user activity [19]–[26]. Such restricted availability systematically biases aggregation toward frequently active clients while underrepresenting sporadic participants, resulting in slower convergence and degraded fairness [27]. A key observation underlying this work is that, beyond being non-uniform and potentially highly skewed, client availability is in practice also unknown to the server, who nonetheless must coordinate aggregation in standard FL protocols [10]. This distinction is consequential: most existing analyses either assume known participation probabilities or restrict attention to simplified availability models that do not capture this uncertainty. Following [27], we adopt a Random Access Model (RAM) to formalize the phenomenon. In the RAM setting, an independent random mechanism operates at each communication round: it receives all clients’ local updates
2
and returns a subset of participating clients according to a fixed but unknown distribution, inaccessible to both the clients and the server. This abstraction captures the stochastic, decentralized nature of participation in practical FL systems while cleanly decoupling availability from optimization dynamics. The two axes above are tightly coupled: non-IID data amplify the effect of unequal participation, and participation skew exacerbates non-IID bias. Although FedAvg converges under suitable smoothness and sampling conditions [3], [28], its performance deteriorates in regimes exhibiting both data heterogeneity and availability imbalance. Fig. 1 illustrates this interaction in a small FL instance with five user-specific data clusters. Under strongly non-IID data and skewed availability, FedAvg biases its decision boundary toward frequently participating clients, leaving rare users underfit. The framework proposed here, F EDE R AGE (Section III), rebalances the effective weighting of clients in light of stochastic participation, yielding both faster convergence and more equitable performance. A. Prior Work Methods that mitigate heterogeneity in FL fall broadly into two families: client-side optimization, which modifies the local objectives or updates so as to align local and global descent directions, and server-side aggregation, which reweights client updates to reflect heterogeneity in effort, data, or availability. The two are complementary. The method proposed here belongs to the first family, and we benchmark it against the state of the art of that type. Client-side optimization. F ED P ROX [29] stabilizes training with a proximal term that keeps local updates close to the global model, and SCAFFOLD [16] employs control variates to correct client drift, at the cost of communicating an additional model-sized vector per round. Complementary analyses [10], [28] establish convergence of local-update methods under random or partial participation. These approaches curb drift, but treat participation as either full or drawn from a known distribution. Server-side aggregation. F ED O PT and its variants [30] replace the plain server average with adaptive, momentum-based server updates; FedNova [17] normalizes contributions by local training effort; and anarchic FL [31] adapts aggregation to asynchronous participation. FedDisco [18] reweights clients according to label imbalance, while availability-aware client selection [22], [26] determines which clients to solicit under intermittent participation. These methods improve robustness, but the reweighting they apply presupposes knowledge of, or the ability to actively probe, the participation statistics. Availability versus importance distributions. A more recent thread makes explicit the distinction between the availability distribution, which governs how often each client reaches the server, and the importance distribution, which encodes the weighting the designer intends clients to receive in the global objective, whether for fairness, robustness, or operational reasons. When the two are misaligned, plain FedAvg converges to a surrogate objective weighted by the availability-induced marginal instead of to the intended one [10]. Transport-based aggregation removes this mismatch exactly, by casting aggregation as a masked optimal transport problem between the two marginals [32]; importancesampling and client-selection schemes pursue the same objective by other means [14], [33]. Each of these mechanisms, however,
requires the server to know—or to be able to estimate—the availability distribution, which enters the transport or importancesampling problem as a hard marginal constraint. The regime studied here is the complementary one, in which that distribution is genuinely inaccessible; the response proposed below is a riskaverse local objective that hedges over a neighborhood of the induced distribution instead of aligning to a prescribed target. A note on terminology. The word agnostic carries a different meaning in the agnostic federated learning of Mohri et al. [34], where the global model is trained against the worst-case mixture of client distributions, i.e., a minimax problem over a simplex of target weights. That formulation is agnostic to the deployment distribution, but presumes that the server can solicit and weight every client during training. Throughout this paper, “agnostic” instead denotes the algorithm’s ignorance of the participation law and that the server never observes, estimates, or uses R, and simply averages whatever it receives. B. Motivation for F EDE R AGE Most existing techniques treat data heterogeneity and stochastic participation as independent issues, whereas the two are coupled in practice: rarely available clients often hold rare or distinctive data. To address this joint difficulty, we introduce Federated Risk-Averse Averaging (F EDE R AGE), an FL algorithm built on a risk-averse framework that embeds the Conditional Value-atRisk (CVaR) into the local objective. Coupling the participation distribution with a mean–CVaR formulation causes F EDE R AGE to upweight high-loss and infrequently selected clients implicitly, conferring robustness to statistical and availability heterogeneity within a single DRO framework. The algorithm (Algorithm 2) retains the structure and per-round cost of FedAvg while admitting a convergence guarantee and improved operational fairness. A CVaR-based scheme of similar flavor was proposed in [27] and likewise rebalances updates toward underrepresented clients, but under a more restrictive availability model and without convergence guarantees. Related Wasserstein- and CVaR-based DRO formulations [14], [33], [35]–[38] improve robustness and fairness, but generally assume known participation probabilities or incur high computational cost. Stochastic first-order methods for CVaR and related DRO objectives are well understood in the centralized setting [39]; the difficulty specific to the present setting is that the nominal distribution is itself generated by an unobserved participation mechanism, so neither the reference measure nor its likelihood ratios are available to the algorithm. Contributions—Those are as follows: • General participation model. We formulate a stochastic model of client availability that extends the RAM of [27] to variablesize multi-client participation per round, inducing non-uniform and hidden sampling probabilities consistent with the behavior of deployed FL systems. • Convergence of agnostic FedAvg. We identify the objective that agnostic averaging actually minimizes under this model, and √ later establish an optimal O(1/ T ) rate for convex, possibly nonsmooth losses under an unknown, non-uniform, variablesize participation law. • Risk-aware formulation. We propose F EDE R AGE , a CVaRbased modification of the local objective that treats data and availability heterogeneity within a single DRO framework, at the cost of a single additional scalar of per-client state.
3
Algorithm 1 Agnostic Federated Averaging (FedAvg) Initialize: θi0 = 0 for i ∈ [N ]; horizon T ; local steps H; step size ηθ > 0; constraint set C ⊆ Θ. 2: for t = 1, 2, . . . , T H do 3: if t mod H = 0 then ▷ Global communication 4: Clients transmit local parameters through RAM. 5: Server receives S t ⊆ [N ]. 1 X t−1 6: Server aggregates: θ̂t = t θi . |S | t 1:
i∈S
Server broadcasts θ̂t and sets θit = θ̂t , ∀i ∈ [N ]. 8: else ▷ Local updates 9: Each client performs stochastic subgradient step: 10: θit = ΠC θit−1 − ηθ ∇θ fi (θit−1 ; ξit ) , ∀i ∈ [N ]. 1 PT θ̂τ H . 11: Return: T τ =1 7:
Convergence of F EDE R AGE. We prove that the agnostic FedAvg analysis transfers to the mean–CVaR objective, with the rate inflated by the explicit factor κ(α, γ) = (1 − γ) + γ/α where γ ∈ [0, 1] interpolates between mean (γ = 0) and CVaR (γ = 1), and α ∈ (0, 1] is the CVaR quantile level. • Empirical validation. We show that F EDE R AGE improves on state-of-the-art algorithms in both heterogeneous and restricted-availability regimes, in convergence rate, accuracy, and per-client fairness, with a margin that widens as the learning task becomes harder. Paper organization. Section II introduces the preliminaries and the problem setup. Section III presents the proposed F EDE R AGE framework and its primal and dual interpretations. Section IV develops the convergence analysis, with all proofs given in place. Section V reports the experiments and implementation details. Section VI concludes. •
II. P ROBLEM D EFINITION We tacitly consider a distributed multi-class classification task with feature space X ⊂ Rd , target classes C = {1, ..., C}, ′ parameter space Θ ⊆ Rd , a given loss function ℓ : C × C → R+ , and a parametric model (i.e., a learning representation) m : X × Θ → C 1 . Unlike traditional (centralized) learning, in Federated Learning (FL), data are distributed among N clients (or agents, or users), each with their own private dataset Di = {(Xi1 , Yi1 ), . . . , (Xini , Yini )} and local parameter θi ∈ Θ, as well as their own local expected loss n
f (θ; Di ) = EDi [ℓ(m(X, θ), Y )] =
i 1 X ℓ(m(Xij , θ), Yij ), (1) ni j=1
where Di denotes the corresponding empirical distribution induced by the local dataset Di , for each client i. Throughout the paper we will use Pnthe following conventions as well: fi (·) = f (·, Di ), f (·) = i=1 pi fi (·). As mentioned earlier, due to different potential scenarios, users transmit their parameters with different frequencies to the server. To formally model this phenomenon, we consider a Random Access Model (RAM) (initially formalized in [27] and substantially extended herein), that selects a subset of users at 1 While we work in the classification setting, our considerations work more generally, e.g, for regression tasks as well.
each round and transmits their parameters to the server with a fixed but unknown probability distribution (see Section II-B). The generic iterated agnostic coordination scheme under which we consider the FL problem throughout this paper is described as follows: At each (global) communication round, all N users (attempt to) transmit their local parameter vectors to the server (passing through the RAM), and the RAM selects M out of N users based on a certain but general probabilistic structure (see Section II-B for details). Then, the server aggregates the received parameter vectors (M in number) with an aggregation policy and broadcasts the aggregation result to all N clients (for them to subsequently process their local parameters). Under this setting, a conventional goal of the server (as in standard FL) is to find a global parameter θ∗ that performs optimally on the weighted loss of all users, i.e., to solve the problem (N ) X inf pi f (θ; Di )= EI∼P f (θ; DI ) , (2) θ∈Θ
i=1
where the weights {pi }N i=1 (defining P) constitute appropriate posterior client participation probabilities induced by the stochastic mechanism implemented by the RAM, reflecting the systemic randomness of user availability (see Section II-B). Problem 2 could (hopefully) be tackled by means of the (agnostic) Federated Average Algorithm (FedAvg) (see Algorithm 1), consisting of two alternating stages, also called rounds: local update rounds, and global communication rounds, closely resembling the generic coordination scheme outlined above. More specifically, during each local update round, all users optimize their respective parameters via mini-batch Stochastic Gradient Descent (SGD) run for H consecutive iterations2 . During each global communication round, the optimized parameters of all N users are transmitted towards the server, first passing through the RAM (which may also be thought of as an multi-erasure channel; see Section II-B). Then, the server aggregates the received parameters of the resulting M ≤ N users surviving the RAM by taking a simple (agnostic) average and subsequently broadcasts the result to all users, so that they can (re)-compute their local updates initialized at the new global parameter. At this point, it is worth mentioning that whether (agnostic) FedAvg (Algorithm 1) is in fact an appropriate method to solve Problem 2 remains an open question in the current literature. The agnostic nature of the algorithm —embodied in its use of uniform averaging over the M received parameters from the clients— may not necessarily account for the client availability distribution P induced by the RAM. Since this distribution is hidden from the server, the naive (though straightforward) averaging step in Line 4 of Algorithm 1 may misrepresent the actual statistical significance or “representativeness” of the contribution of each client to the global model. This issue raises fundamental concerns about the compatibility of FedAvg with the objective in Problem 2, particularly when the sampling process exhibits persistent heterogeneity. A rigorous treatment of this mismatch, including a detailed convergence analysis of FedAvg under a canonical probabilistic RAM structure and for a naturally chosen P is developed in Section II-B and later in Section IV. 2 For simplicity, we assume that all users employ the same number of local iterations H; this assumption can be relaxed in both analysis and practice.
4
A. An Alternative Representation of the FL Problem Suppose that all clients adopt a common mini-batch size b. Each mini-batch is a set ξij , with i ∈ [N ] and j ∈ {1, . . . , Nib }, SNib j where Nib := nbi ; let Dib = j=1 {ξi } be the collection of all mini-batches of size b. Writing the average loss over a mini-batch P ξ as f (θ; ξ) = 1b (X,Y )∈ξ ℓ(m(X, θ), Y ) and the average over PNib all mini-batches as f (θ; Dib ) = (1/Nib ) j=1 f (θ; ξij ), a doublecounting argument yields b
Ni 1 X b f (θ; Di ) = b Ni b j=1
= =
1 Nib b 1 ni
X
ℓ(m(X, θ), Y )
(X,Y )∈ξij
X (X,Y )∈Di
X
ni − 1 ℓ(m(X, θ), Y ) b−1
(3)
ℓ(m(X, θ), Y ) = f (θ; Di ),
(X,Y )∈Di
i −1 / Nib b = 1/ni . Hence, for every miniwhere we used nb−1 batch size b, Problem (2) can be re-expressed as ( N ) X b b inf pi f (θ; Di )= EI∼P f (θ; DI ) , (4) θ
i=1
or, more compactly, inf Eξ∼Qb [f (θ; ξ)] ,
(5)
θ
b
b
PN
b i=1 pi Qi ,
where Q denotes the mixture distribution Q = with Qbi the uniform distribution over Dib and P the participation distribution. Under Qb , the probability that ξ equals ξij is pi /Nib for i ∈ [N ] and j ∈ {1, . . . , Nib }, and zero otherwise. We write ξi for the random variable taking values ξij , j ∈ [Nib ], under Qbi . Problems (2), (4), and (5) share the same objective. In (4) and (5), however, the mini-batch size b appears as part of the problem formulation instead of as a hyperparameter of a particular solver (e.g. SGD). We therefore refer to b as the model mini-batch size, to distinguish it from the algorithmic minibatch size used within an SGD implementation. Operationally, solving (2) by SGD with algorithmic mini-batch b is equivalent to solving (4) or (5) by the same scheme with algorithmic minibatch 1. Remark 1. While the minibatch reformulation (5) does not seem to offer an apparent operational advantage concerning standard FL, the identification of the minibatch distribution Qb will be key to the development of our proposed approach for simultaneously dealing for the issues of data heterogeneity and limited client availability (i.e., general client drifts), following the general paradigm of distributionally robust optimization (DRO), as discussed in later Sections II-C and III. B. Canonical Probabilistic RAM FL is traditionally analyzed under the assumption that either all clients (full participation) or a fixed fraction of them (partial participation) participate in a round, the shortfall being attributed to device unavailability, battery constraints, or network failures [23]–[25]. In the simplest case the server is assumed to know the participation probabilities and to exploit them during aggregation, which, as discussed above, is impractical. To model
participation without such knowledge, we adopt and extend the Random Access Model (RAM) of [27]: an external, independent entity selects a subset of clients S t ⊆ [N ] at each communication round t. Canonical fixed-size RAM. Let M ∈ {1, . . . , N } be fixed. At each round t, the RAM selects M clients without replacement according to a stationary, possibly non-uniform selection prior R; that is, S t is drawn so that client i satisfies {i ∈ S t } with marginal probability P(i ∈ S t ) determined by R.3 Since all M selected clients reach the server and are weighted uniformly, the weight effectively borne by client i’s parameter is proportional to P(i ∈ S t )/M . Accordingly, the natural weight on client i’s empirical risk fi (θ) in the global objective is its probability of survival through the two-stage process of RAM selection followed by uniform averaging, i.e., P(i ∈ S t )/M : a client’s influence on the global model is proportional to its frequency of participation. These weights form a distribution over [N ]: " N # N N X X X t t t P(i ∈ S ) = E 1{i ∈ S } = E 1{i ∈ S } i=1
i=1 = E |S t | = M.
i=1
(6)
We may then plausibly take 1 X P(i ∈ S t ) = P(S t = S) 1{i ∈ S}, ∀i ∈ [N ]. (7) pi := M M S
Since the selection dynamics are stationary, the weights pi do not depend on t. The distribution P := (p1 , . . . , pN ) is shaped by the selection budget M : for M = N (full participation), pi = 1/N for all i regardless of R; for M = 1, P coincides with the RAM’s singleton sampling distribution. General case: variable-size RAM. When |S t | is not fixed, the normalized weights remain well defined through a convex combination over subset sizes: pi =
X R(S) 1{i ∈ S} , |S|
for all i ∈ [N ],
(8)
S⊆[N ]
where R(S) is the probability of selecting the subset S and, without loss of generality, R(∅) = 0. Indeed, conditioning on the selected subset and using that a uniformly averaged subset of size |S| assigns weight 1/|S| to each of its members, X 1 R(S) , pi = |S| 1{i ∈ S} | {z } | {z } S⊆[N ] t P(i weighted|S t =S) P(S =S)
which defines a valid probability distribution over [N ] and accounts for the expected relative contribution of each client across all sampled subsets. Expression (8) contains the fixedsize formula (7) as the special case R({S : |S| = M }) = 1, and permits unrestricted subset selection. The convergence guarantees of Section IV hold under (8) verbatim, since the participation model enters the analysis only through Lemma 4, which is proved directly from (8). For ease of comparison with state-ofthe-art algorithms that assume fixed-size participation, we focus henceforth on the case in which exactly M clients are selected per round. 3 If M = N , then regardless of R the marginal is uniform, P(i ∈ S t ) = 1, and the induced weights below satisfy pi = 1/N .
5
Algorithm 2 Federated Risk-Averse Averaging (F EDE R AGE) Input t θ1t , . . . , θN
Output θit1 , . . . , θitM
Stationary Erasure Channel Survival probability ∝ pi =
P(i∈S t ) M
Fig. 2: Canonical RAM structure: the N inputs θ1 , . . . , θN enter a stationary (N, M )-ary erasure channel (the RAM), producing M surviving outputs (a random subset of the inputs), where the survival probability of each θi is proportional to pi . C. Distributionally Robust Federated Learning (DRFL) The ineffectiveness of agnostic FedAvg under client drift may be understood as a failure to generalize to a statistically balanced treatment of clients and their datasets. Even when FedAvg solves its own objective optimally, that objective may be biased toward particular clients or sub-datasets and far from the intended learning outcome. This is a distribution shift in the training objective, caused by client drift arising from the RAM, from data inhomogeneity, or from both: clients’ loss contributions are weighted unequally, compromising fairness and degrading performance for underrepresented clients. This is precisely the situation of (2) (equivalently (5)) under the induced weighting (7). Accordingly, we adopt a distributionally robust federated learning (DRFL) formulation. Instead of optimizing against the fixed distribution Qb , we minimize the worst-case expected loss over a distributional neighborhood of Qb : inf
sup
θ Q∈U (Qb ) ϵ
Eξ∼Q [f (θ; ξ)],
Initialize: θi0 = 0, βi0 = 0 for all i ∈ [N ]; T, H, ηθ , ηβ > 0; 2: α ∈ (0, 1], γ ∈ [0, 1]; compact sets C, B. 3: for t = 1, . . . , T H do 4: if t mod H = 0 then ▷ Global communication 5: Clients transmit local parameters through RAM. t 6: Server samples active tset S ∼ R. 1 X θit−1 θ̂ 7: Server aggregates: t = t ; βit−1 |S | β̂ i∈S t 8: Server broadcasts to all clients. 9: else ▷ Local updates 10: Each client draws ξit ∼ Qbi ; γ 11: Computes wit = (1 − γ) + 1{f (θit−1 ; ξit ) ≥ βit−1 }; α 12: Performs stochastic subgradient step: t−1 t θi θi ηθ wit ∇θ fi (θit−1 ; ξit ) = ΠC×B 13: − . βit ηβ (1 − wit ) βit−1 P P T T 1 τH 1 14: Return: T , T τ =1 β̂ τ H . τ =1 θ̂ 1:
(9)
where the ambiguity set Uϵ (Qb ) = {Q : d(Q, Qb ) ≤ ϵ} is a distributional “ball” of radius ϵ centered at Qb in a distributional distance or divergence d, both of which are specified in Section III. Whereas (5) weights individual data points by the availabilityinduced distribution, Problem (9) optimizes uniformly over a set of nearby, and potentially more desirable, distributions. By construction, every Q ∈ Uϵ (Qb ) incurs an average loss no larger than the adversarial loss supQ∈Uϵ (Qb ) Eξ∼Q [f (θ; ξ)]; minimizing the latter therefore yields a parameter that performs well for all Q ∈ Uϵ (Qb ) simultaneously. As ϵ grows, the set Uϵ (Qb ) enlarges, admitting more pessimistic distributions and, at the same time, increasing the likelihood that it contains distributions more desirable than Qb ; a performance trade-off is thus implicit in the choice of ϵ. In the limit ϵ → ∞ the adversarial loss approaches supξ f (θ; ξ), whereas ϵ = 0 recovers the nominal loss Eξ∼Qb [f (θ; ξ)]. Problem (9) therefore spans the range between classical and maximally averse FL, providing a principled means of trading average-case behavior against robustness to distribution shift induced by general client drift. DRFL in the present setting poses an additional natural difficulty: Qb is unknown and cannot be manipulated, being implied by random process modeled by RAM and modeled through the RAM. We resolve this by exploiting the convex (Fenchel) duality between distributionally robust functionals and coherent risk measures, developed next. III. P ROPOSED A PPROACH : F EDE R AGE A. DRO via the Conditional Value-at-Risk Consider a random element ξ with base distribution Q′ , and let ξ 7→ f (ξ) ∈ R be integrable with respect to Q′ , so that f (ξ)
may be regarded as a random cost. The Conditional Value-at-Risk (CVaR) of f (ξ) at level α may be defined as [40], [41] 1 α CVaRξ∼Q′ [f (ξ)] ≜ inf β + Eξ∼Q′ (f (ξ) − β)+ , (10) β∈R α where (·)+ = max{·, 0} and α ∈ (0, 1] is the risk or confidence level. Equivalently, CVaR is the average of the loss over its worst (upper) α-tail reading Z 1 1 CVaRα [f (ξ)] = VaRu f (ξ) du, (11) α 1−α where VaRu denotes the u-quantile. For a continuous distribution this reduces to a conditional-tail-expectation form CVaRα [f (ξ)] = E f (ξ) | f (ξ) ≥ βα∗ , P f (ξ) ≥ βα∗ = α, with βα∗ an optimal β in (10). For general (in particular, discrete) distributions this identity may fail on account of an atom at the quantile, whereas (11) always holds. CVaR is a coherent risk measure—convex, monotone, translation equivariant, and positively homogeneous [41]—and admits the dual representation widely used in DRO CVaRα [f (ξ)] = sup EQ [f (ξ)],
(12)
Q∈Uα
where the ambiguity set Uα is dQ 1 ′ ∈ 0, α a.e.-Q , Uα = Q dQ′ and Q′ is the nominal (reference) distribution. CVaR is thus a worst-case expectation over a likelihood-ratio (Rényi-type) divergence ball of radius log(1/α), and instantiates (9) with ϵ = log(1/α). Varying α interpolates continuously between the expectation and the essential supremum: CVaR1 [f (ξ)] = E[f (ξ)],
lim CVaRα [f (ξ)] = ess sup f (ξ).
α→0+
As α → 0+ , the likelihood-ratio bound 1/α diverges and the ambiguity set expands toward the worst case, whereas α = 1 forces dQ/dQ′ = 1 a.e. and recovers the nominal expectation. This renders CVaR a natural risk-sensitive functional for robust optimization.
6
B. DRFL via the CVaR: F EDE R AGE
C. Risk-Averse (Primal) Interpretation of F EDE R AGE
To instantiate (9) in a manner computable without access to Qb , we combine the CVaR under the RAM-induced distribution with the risk-neutral objective, replacing (5) by the mean–CVaR problem
To interpret the objective (14), consider again the example of Fig. 1, with two infrequent clients (4 and 5) alongside three frequently participating ones (1–3). Agnostic PN FedAvg minimizes the participation-weighted loss f (θ) = i=1 pi fi (θ) of (2), in which the induced weights p4 , p5 are small, so that the local losses f4 (θ) and f5 (θ) contribute little to the global objective even when they remain large. Minimization of f is therefore driven by clients 1–3, and the resulting model fits the dominant clients while neglecting the rare patterns held by the underrepresented ones. The mean–CVaR integrand of (14) gα,γ (θ, β; ξ) := (1 − γ) f (θ; ξ) + γ β + α1 f (θ; ξ) − β + ,
i h inf (1 − γ) Eξ∼Qb [f (θ; ξ)] + γ CVaRα ξ∼Qb [f (θ; ξ)] ,
θ∈Θ
(13)
with α ∈ (0, 1] and γ ∈ [0, 1] tunable hyperparameters. Using the variational form (10), Problem (13) is equivalent to the joint problem inf
θ∈Θ, β∈R
fα,γ (θ, β),
where h i fα,γ (θ, β):= E (1 − γ)f (θ; ξ) + γ β + α1 f (θ; ξ) − β + . (14) The expectation over Qb is internal to the definition of fα,γ ; consequently, fα,γ (θ, β) denotes a deterministic quantity and no outer expectation is written anywhere below. Relative to agnostic FedAvg (Algorithm 1), the only modification required by (14) is the introduction of a single scalar β ∈ R, maintained locally alongside the model parameters, so that Algorithm 2 retains the two-phase structure of its risk-neutral counterpart. Both local updates are driven by the same scalar risk weight wit = (1 − γ) + αγ 1{fi ≥ β} of Line 8: the update direction in θ is wit ∇θ fi , whereas the subgradient with respect to β is selected as γ 1 − α1 1{fi ≥ β} = 1 − wit , and in particular involves no derivative of fi in β. We project β onto a compact interval B, which is done without loss of generality, since the optimizer β ⋆ of (10) is a finite value-at-risk lying in the range of the loss. Each local step uses a single model mini-batch ξit ∼ Qbi , i.e., algorithmic mini-batch size one, which permits tight control of the upper tail of the loss. Comparison relative to SCAFFOLD [16]. Several state-of-theart methods rely on gradient-aggregation mechanisms that require communicating additional model-sized vectors, widening the communication channel and enlarging the attack surface. SCAFFOLD [16] is the canonical instance: each client maintains and transmits a control variate of the same dimension d′ as the model, which is an estimate of that client’s local gradient. This approximately doubles the per-round uplink and, more significantly, exposes a second, gradient-valued quantity per client—precisely the object exploited by gradient-inversion and membership-inference attacks [5], [15], and one that is not protected by the averaging applied to the model update. F EDE R AGE transmits instead a single scalar βi , an estimate of a quantile of the client’s own loss distribution: it is smaller by a factor d′ , carries no directional information about the data, and has sensitivity bounded by the diameter of B, so that differentialprivacy noise calibrated to it costs a small fraction of the utility required to privatize a d′ -dimensional control variate. Both θi and βi reach the server only through plain averages, so F EDE R AGE is compatible with secure aggregation without modification. Robustness to heterogeneity is thus obtained through the local objective rather than through additional shared state.
whose expectation over ξ ∼ Qb is fα,γ (θ, β), modifies the influence ofP each mini-batch ξ in a risk-sensitive manner. Recall N that Qb = i=1 pi Qbi , so that a mini-batch of client i carries nominal mass pi /Nib under Qb ; the threshold β is accordingly a quantile (estimate) of the loss under the global mixture, maintained locally as βi between communication rounds and averaged at the server (Algorithm 2). Whenever the mini-batch loss f (θ; ξ) exceeds β, which at optimality is an (1 − α)-quantile under Qb , the corresponding subgradient is upweighted as ∇θ gα,γ (θ, β; ξ) = 1 − γ + αγ 1{f (θ; ξ) ≥ β} ∇θ f (θ; ξ), | {z } =: w(θ,β;ξ)
where ∇θ f (θ; ξ) denotes the measurable subgradient selection fixed in Section IV and w(θ, β; ξ) is precisely the scalar risk weight wit of Line 8 of Algorithm 2, evaluated at (θit−1 , βit−1 ; ξit ). The expression ω(θ, β; ξ) constitutes a risk-weighted prioritization mechanism. If the mini-batches of client i consistently incur large losses—whether because of infrequent RAM selection (small pi ) or because of misalignment with the global model (client drift)—they are more likely to exceed the threshold β, and their subgradients are scaled by a factor of up to κ(α, γ) = (1 − γ) + γ/α, amplifying their contribution to the update. Underrepresented or difficult data thereby receive proportionally greater attention, without the algorithm ever using, or even forming, an estimate of {pi }. The mean–CVaR objective is furthermore a smooth surrogate for the worst-case loss. In the limit γ = 1, α → 0+ , the CVaR term tends to ess supξ∼Qb f (θ; ξ), so that minimizing (14) approaches minimization of the largest mini-batch loss in the support of Qb , up to smoothing; since that support is the union of the clients’ mini-batch collections {Dib }i∈[N ] , this steers the global model toward regions in which the largest client losses maxi∈[N ] fi (θ) are reduced, thereby promoting an equity across clients that the risk-neutral formulation (2) does not enforce. D. Distributionally Robust (Dual) Interpretation of F EDE R AGE We now use the dual representation (12) to interpret the CVaR term in (14) in a complementary distributionally robust manner. Recall the expected loss over RAM-distributed mini-batches Eξ∼Qb [f (θ; ξ)] =
N X i=1
b
pi
1 Nib
Ni X j=1
b
fi (θ; ξij )
Ni N X X = qij fi (θ; ξij ), i=1 j=1
7
Comparison of Distributions
Probability of the Participation of Users
0.35
Uniform Distribution Original Distribution Modified Distribution
0.30 0.25 0.20 0.15 0.10 0.05 0.00
1
2
3 Users
4
5
(a) Client availability probabilities (light colors), the uniform distribution (dashed green line), and the effective availability distribution induced by CVaR with γ = 0.25 and α = 0.01. The change in the effective distribution is implicit, arising from the dual representation of CVaR.
(b) Given 100 data points with an initial weight distribution (black), the effective weights change with the mini-batch size. As the mini-batch approaches the full batch, the effective weights become uniform (green). This loss of variability suggests that too large a mini-batch degrades performance by reducing the effective degrees of freedom.
Fig. 3: (a) Effect of CVaR on the effective client-availability distribution. (b) Effect of mini-batch size on effective selection probabilities. Both illustrate how distributional variability influences federated optimization dynamics. o {q̂ij } = Q̂ ∈ Uα (Qb ) . where the weights qij = pi /Nib constitute Qb . By the dual form of CVaR, it follows that In words, the distributional robustness that CVaR confers on [f (θ; ξ)] = sup E [f (θ; ξ)] CVaRα b the mini-batch distribution Q̂ is inherited by the induced pointξ∼Q ξ∼Q̂ Q̂∈Uα (Qb ) level distribution Q̃: maximizing over the mini-batch ambiguity Nib N X set Uα (Qb ) is equivalent to maximizing over the structured X j j q̂i fi (θ; ξi ), = sup point-level set Ũα (Qb ), which couples the CVaR reweighting b Q̂∈Uα (Q ) i=1 j=1 with the RAM-induced participation weights pi . F EDE R AGE is therefore distributionally robust at the level of individual where the mini-batch ambiguity set is data points, hedging against the client drift produced jointly by o n q̂ij b b 1 data heterogeneity and skewed availability. This reweighting is Uα (Q ) = Q̂ pi ≤ N b α , i ∈ [N ], j ∈ [Ni ] . i realized implicitly, through the local objective, and never appears as an explicit aggregation weight at the server, which is what Expanding the loss over individual data points, we have allows the algorithm to operate without any knowledge of the Eξ∼Q̂ f (θ; ξ) participation law. Nib In the special case b = 1, in which mini-batches are single N XX j X 1 points, the two levels coincide: = q̂i b ℓ(m(X, θ), Y ) j i=1 j=1 (X,Y )∈ξi α CVaRα ℓ(m(X, θ), Y ) , b f (θ; ξ) = CVaR ξ∼Q (I,(X,Y ))∼ Q̃ " Nb # ni N X i X X j j k k 1 whereas for b > 1 the right-hand side is a relaxation induced by = q̂i 1{(Xi , Yi ) ∈ ξi } ℓ(m(Xik , θ), Yik ) b overlapping mini-batch structures (Fig. 3). Incorporating CVaR i=1 k=1 j=1 | {z } thus reweights samples according to their contribution to the ≜ q̃ik upper quantile of the loss distribution. At each communication ni N X X round, harder examples—data points or clients with higher loss— = q̃ik ℓ(m(Xik , θ), Yik ), are prioritized, so that the algorithm attends to poorly performing i=1 k=1 or underrepresented clients, improving robustness to data heterowhere the inherited weights {q̃ik } induce a reweighted importance geneity and worst-case performance. distribution Q̃ over individual data points with CVaR CVaRα ξ∼Qb f (θ; ξ) =
E(I,(X,Y ))∼Q̃ ℓ(m(X, θ), Y ) ,
sup Q̃∈Ũα
IV. C ONVERGENCE FOR C ONVEX L OSSES
(Qb )
with the inheritance uncertainty set n PNib j Ũα (Qb ) = Q̃ q̃ik = 1b j=1 q̂i 1{(Xik , Yik ) ∈ ξij }, q̃ik 1 pi ≤ ni α ,
i ∈ [N ], k ∈ [ni ],
This section develops the convergence analysis in two stages, with every proof given in place. We first treat the risk-neutral case γ = 0, i.e., agnostic FedAvg applied to the induced objective (5) (Sections IV-A through IV-C), and then extend the argument to the mean–CVaR objective fα,γ for γ > 0 and α ∈ (0, 1] (Section IV-D). The separation is deliberate: the risk-neutral analysis isolates the effect of unknown, variable-size
8
participation, and the risk-averse extension is then shown to cost exactly one explicit constant. Two sources of randomness enter. First, for each client i ∈ [N ], the random element ξi denotes a mini-batch of size b drawn uniformly without replacement from client i’s dataset; at time t we write ξit , and mini-batches are drawn independently across clients and rounds. Second, S t ⊆ [N ] denotes the subset of clients selected at round t under the RAM, i.i.d. across rounds and independent of {ξit }. Both sources are carried through every round, with the understanding that the sampled ξit are unused during global rounds and the outcome S t is unused during local rounds. We define the natural filtration {Ft }t , Ft := σ θis , ξis , S s : s ≤ t, i ∈ [N ] , which captures the model states, mini-batch draws, and participation history up to round t; the iterates θit are adapted to {Ft } and depend on Ft−1 only through θit−1 and the fresh randomness ξit or S t . Since the losses are convex and possibly nonsmooth, ∇fi (θ) and ∇f (θ; ξ) denote throughout a fixed measurable selection from the subdifferentials ∂fi (θ) and ∂θ f (θ; ξ), chosen so that the unbiasedness required in Assumption 2 holds; all inequalities below use only the convexity (subgradient) inequality and therefore remain valid for any such selection. Our structural hypotheses are the following two; the bounded-variance condition used in the analysis is derived from them rather than assumed. Assumption 1 (Convexity). The “instantaneous” losses f (·; ξ) are convex on Θ for every mini-batch ξ. Assumption 2 (Unbiasedness and Bounded Second Moment). For each i ∈ [N ] and every θ ∈ Θ, the stochastic subgradient is conditionally unbiased, Eξi [∇f (θ; ξi )] = ∇fi (θ), and sup Eξi ∥∇f (θ; ξi )∥2 ≤ G2 . θ∈Θ
Lemma 1 (Bounded Local Gradient Variance). Under Assumption 2, for every i ∈ [N ], sup Eξi ∥∇f (θ; ξi ) − ∇fi (θ)∥2 ≤ σi2 := G2 − inf ∥∇fi (θ)∥2 , θ∈Θ
θ∈Θ
and therefore the aggregate variance bound σ 2 := satisfies σ 2 ≤ G2 .
PN
2 i=1 pi σi
Proof. Fix θ ∈ Θ and set X := ∇f (θ; ξi ), so that EX = ∇fi (θ) by Assumption 2. The bias–variance identity yields 2
2
2
2
2
E∥X − EX∥ = E∥X∥ − ∥EX∥ ≤ G − ∥∇fi (θ)∥ . Taking the supremum over θ ∈ Θ gives the first claim, and the bound on σ 2 follows because {pi }i∈[N ] is a probability distribution and each σi2 ≤ G2 . We retain the symbol σ 2 below, as it is the sharper of the two constants and isolates the contribution of sampling noise; every statement below remains valid with σ 2 replaced by G2 . Throughout, C ⊆ Θ is convex and compact with Euclidean projection ΠC (·), and θ∗ denotes a minimizer of f over C, which exists by continuity of f and compactness of C. Since each fi is convex and finite on a neighborhood of the compact set C, it is Lipschitz on C; we let ℓ denote a common Lipschitz constant.
A. Preliminary Lemmata We first analyze a single projected stochastic subgradient step at the client side. Throughout, git := ∇f (θit−1 ; ξit ), so that E[git | Ft−1 ] = ∇fi (θit−1 ) by Assumption 2; this is the update direction of Line 9 of Algorithm 1. Conditional expectations are unrolled by the tower property. Lemma 2 (One-Step Progress). Let θit = ΠC (θit−1 − ηgit ) for i ∈ [N ] and η > 0. Under Assumptions 1 and 2 and Lemma 1, at every local round, E ∥θit − θ∗ ∥2 | Ft−1 ≤ ∥θit−1 − θ∗ ∥2 − 2η fi (θit−1 ) − fi (θ∗ ) + 2η 2 (σ 2 + G2 ).
(15)
∗
Proof. Since θ ∈ C and the projection onto a closed convex set is non-expansive, ∥θit − θ∗ ∥2 = ∥ΠC (θit−1 − ηgit ) − ΠC (θ∗ )∥2 ≤ ∥θit−1 − ηgit − θ∗ ∥2 = ∥θit−1 − θ∗ ∥2 − 2η⟨git , θit−1 − θ∗ ⟩ + η 2 ∥git ∥2 . Take E[ · | Ft−1 ] on both sides. Writing git = ∇fi (θit−1 ) + ζit with E[ζit | Ft−1 ] = 0, and noting that θit−1 is Ft−1 -measurable, E ⟨git , θit−1 − θ∗ ⟩ | Ft−1 = ⟨∇fi (θit−1 ), θit−1 − θ∗ ⟩, while ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 together with Assumption 2 and Lemma 1 gives E ∥git ∥2 | Ft−1 ≤ 2∥∇fi (θit−1 )∥2 + 2 σ 2 ≤ 2G2 + 2σ 2 . Combining the two displays, E ∥θit − θ∗ ∥2 | Ft−1 ≤ ∥θit−1 − θ∗ ∥2 − 2η⟨∇fi (θit−1 ), θit−1 − θ∗ ⟩ + 2η 2 (G2 + σ 2 ). The subgradient inequality for the convex function fi (Assumption 1) gives fi (θit−1 ) − fi (θ∗ ) ≤ ⟨∇fi (θit−1 ), θit−1 − θ∗ ⟩, and substituting it yields (15). We next bound the divergence between two clients’ parameter vectors within a communication round. Lemma 3 (Local Parameter Divergence). Let i, j ∈ [N ] and let τi , τj ∈ [SH, SH + H] be local steps between consecutive communication rounds S and S + 1. Under Assumption 2, τ E ∥θiτi − θj j ∥ FSH ≤ 4ηGH. Proof. Assume without loss of generality that τi ≥ τj , and set ∆t := θit − θjt . At each local step, non-expansiveness of the projection gives ∥∆t ∥ = ΠC (θit−1 − ηgit ) − ΠC (θjt−1 − ηgjt ) ≤ ∆t−1 − η(git − gjt ) , so that ∥∆t ∥2 ≤ ∥∆t−1 ∥2 − 2η⟨∆t−1 , git − gjt ⟩ + η 2 ∥git − gjt ∥2 . By Cauchy–Schwarz and Assumption 2, −2η⟨∆t−1 , git − gjt ⟩ ≤ 4ηG∥∆t−1 ∥, E∥git − gjt ∥2 ≤ 4G2 , 2 whence E ∥∆t ∥2 | Ft−1 ≤ ∥∆t−1 ∥ + 2ηG , and, by Jensen’s inequality, E[∥∆t ∥ | Ft−1 ] ≤ ∥∆t−1 ∥ + 2ηG. Since θiSH = θjSH = θ̂SH implies ∆SH = 0, iterating this recursion and using the tower property yields E[∥∆SH+h ∥ | FSH ] ≤ 2ηGh
9
Algorithm Uniform FedAvg F ED P ROX Scaffold F EDE R AGE
MNIST Non-Uniform
79.54 ± 8.70 79.19 ± 9.03 96.95† ± 0.26 96.02 ± 0.30
FashionMNIST Uniform Non-Uniform
78.19 ± 11.12 77.85 ± 10.96 95.01 ± 0.50 95.91† ± 0.41
75.08 ± 5.17 75.11 ± 5.22 84.24 ± 2.36 83.99† ± 1.71
61.82 ± 10.39 61.82 ± 10.38 77.36 ± 1.09 83.95† ± 1.03
CIFAR-10 Uniform Non-Uniform 51.43 ± 2.19 52.18 ± 0.74 51.21 ± 2.71 57.41† ± 1.51
50.61 ± 1.48 50.25 ± 1.75 50.57 ± 1.49 56.34† ± 0.61
TABLE I: Test accuracy (%) ± standard deviation for FedAvg, F ED P ROX, Scaffold, and F EDE R AGE on MNIST, FashionMNIST, and CIFAR-10 after 10,000 communication rounds, under uniform and non-uniform client availability. Entries marked † are statistically significant (two-sample Z-test at the 5% level, computed on the final ten communication rounds). Bold indicates the best mean in each column; blue indicates the best mean and standard deviation jointly, i.e., the largest value of mean − standard deviation, which is the relevant figure of merit when run-to-run stability is at stake. X X τ τ 1 = P(S t = S) |S| for h ∈ {0, . . . , H}; in particular E[∥θi j − θj j ∥ | FSH ] ≤ 1{i ∈ S} ∥θit−1 − θ∗ ∥2 τi S 2ηG(τj P − SH). Finally, by the triangle inequality and ∥θi − i∈[N ] # " τ τi s η∥g ∥, θi j ∥ ≤ s=τ X X i j +1 t−1 t 1 − θ∗ ∥2 = τ τ τ |S| P(S = S) 1{i ∈ S} ∥θi E ∥θiτi − θj j ∥ FSH ≤ E ∥θi j − θj j ∥ FSH S i∈[N ] τ X + E ∥θiτi − θi j ∥ FSH = pi ∥θit−1 − θ∗ ∥2 , ≤ 2ηG(τj − SH) + ηG(τi − τj ) i∈[N ] ≤ 3ηGH. Symmetrizing in i ↔ j and bounding by the worst case gives the stated constant 4ηGH.
where the last equality is the definition (8) of pi . Since S t is independent of Ft−1 and the iterates θit−1 are Ft−1 -measurable, the interchange above is justified.
Lipschitz continuity of the losses then yields the following. Corollary 1 (Local Value Divergence). For i, j ∈ [N ] and τi , τj ∈ [SH, SH + H], τ E |fi (θiτi ) − fi (θj j )| FSH ≤ 4ℓηGH. Proof. By ℓ-Lipschitz continuity of fi on C we have |fi (θ) − τ fi (θ′ )| ≤ ℓ∥θ − θ′ ∥ for all θ, θ′ ∈ C. Applying this to θiτi , θj j ∈ C, taking E[ · | FSH ], and invoking Lemma 3 gives the bound ℓ · 4ηGH. B. Client Availability and the Global Update The server P aggregation at global round t is denoted by θ̂t = |S1t | j∈S t θjt−1 . The following inequality relates this aggregation to the survival probabilities {pi }. It is the only point at which the participation model enters the analysis, and it is established directly from the general variable-size weights (8). Lemma 4 (Sample-to-Model Inequality). At every global round t, X E ∥θ̂t − θ∗ ∥2 | Ft−1 ≤ pi ∥θit−1 − θ∗ ∥2 . (16)
C. The Risk-Neutral Case We now state and prove convergence of agnostic FedAvg on the induced objective (5). Theorem 1 (Convergence of Agnostic FedAvg). Let Assump√ tions 1 and 2 hold. Then, with step size η = Θ 1/ T H , projected agnostic FedAvg satisfies " # T 1 X 1 sH ∗ √ θ̂ . E f − f (θ ) = O T s=1 T Proof. Fix a global round s ∈ {1, . . . , T }. Summing the bound of Lemma 2 over the H local steps of round s for client i, taking (s−1)H total expectations, and using θi = θ̂(s−1)H , E ∥θisH−1 − θ∗ ∥2 ≤ E ∥θ̂(s−1)H − θ∗ ∥2 − 2η
H−1 X
(s−1)H+h E fi (θi ) − fi (θ∗ )
h=0
+ 2Hη 2 (σ 2 + G2 ).
i∈[N ]
Proof. Since ∥ · ∥2 is convex and θ̂t − θ∗ is an average of the |S t | vectors {θit−1 − θ∗ }i∈S t , Jensen’s inequality gives " # X 2 t t−1 ∗ ∗ 2 1 E ∥θ̂ − θ ∥ | Ft−1 = ES t |S t | θi − θ Ft−1 i∈S t
#
" ≤ ES t
1 |S t |
X
∥θit−1 − θ∗ ∥2
Ft−1 .
i∈S t
Expanding the expectation over the sampling distribution and exchanging the order of the two finite sums, E ∥θ̂t − θ∗ ∥2 | Ft−1 X X 1 ≤ P(S t = S) |S| ∥θit−1 − θ∗ ∥2 S
i∈S
(17)
(s−1)H+h
Every local iterate θi lies in the round-s window, and θ̂sH is an average of end-of-round iterates of that same window; hence Corollary 1 applies to each pair and gives, in conditional expectation, (s−1)H+h − E fi (θi ) F(s−1)H ≤ − E fi (θ̂sH ) F(s−1)H + 4ℓηGH. Substituting into (17) and taking total expectations, E ∥θisH−1 − θ∗ ∥2 ≤ E ∥θ̂(s−1)H − θ∗ ∥2 − 2ηH E fi (θ̂sH ) − fi (θ∗ ) + 2Hη 2 (σ 2 + G2 ) + 8ℓη 2 GH 2 .
(18)
10
Lemma 4 at t = sH, together with the tower property, gives X pi E ∥θisH−1 − θ∗ ∥2 . (19) E ∥θ̂sH − θ∗ ∥2 ≤ i∈[N ]
Weighting (18) by pi , summing over i ∈ [N ], using from (2), and combining with (19), E ∥θ̂sH − θ∗ ∥2 ≤ E ∥θ̂(s−1)H − θ∗ ∥2 − 2ηH E f (θ̂sH ) − f (θ∗ ) 2
2
2
P
2
i pi fi = f
2
+ 2Hη (σ + G ) + 8ℓη GH .
(20)
Dividing by 2ηH and rearranging, E ∥θ̂(s−1)H − θ∗ ∥2 − E ∥θ̂sH − θ∗ ∥2 E f (θ̂sH )−f (θ∗ ) ≤ 2ηH 2 + η(σ + G2 ) + 4ℓηGH. (21) Summing over s = 1, . . . , T telescopes the first term and discards a nonnegative quantity; dividing by T and applying Jensen’s inequality to the convex function f gives # " T X θ̂sH − f (θ∗ ) E f T1 s=1
∥θ̂0 − θ∗ ∥2 + η(σ 2 + G2 ) + 4ℓηGH. (22) 2ηHT √ Setting D2 := ∥θ̂0 − θ∗ ∥2 and η = c/ T H for a constant c > 0, h P i T E f T1 s=1 θ̂sH − f (θ∗ ) q D2 c(σ 2 + G2 ) ≤ √ + √ + 4c ℓG H T , (23) 2c T H TH √ and for fixed H the dominant term is of order 1/ T , which is the claim. √ Theorem 1 establishes an O(1/ T ) rate in the number of communication rounds and is, to the best of our knowledge, the first convergence guarantee for convex federated optimization under unknown client availability, here in the general variable-size model (8). As the proof shows, the participation law enters only through Lemma 4, which was established directly from (8); the argument therefore covers variable-size random access without modification. Faster rates, of order 1/T , are available for strongly convex objectives under known participation distributions, but are not applicable in the present setting. We also note that the bound (22) contains no residual term that grows with T , in contrast with several earlier analyses of local-update methods. Section V examines this behavior empirically under both uniform and skewed availability. ≤
D. Extension to F EDE R AGE We now transfer the guarantee to the mean–CVaR objective fα,γ of (14). Define γ γ ∈ [0, 1], α ∈ (0, 1], κ(α, γ) := (1 − γ) + , α and note that κ(α, 0) = κ(1, γ) = 1 and κ(α, γ) ≥ 1 throughout. Theorem 2 (Convergence of F EDE R AGE). Let Assumptions 1 and 2 hold, and let C ⊆ Θ and B ⊂ R be convex and compact, with projections ΠC and ΠB . Consider projected agnostic FedAvg
applied to fα,γ over C×B, with global checkpoints (θ̂sH , β̂ sH ) as in Algorithm 2, and let (θ∗ , β√∗ ) ∈ argmin(θ,β)∈C×B fα,γ (θ, β). Then, with η = Θ 1/(κ(α, γ) T H) , h P i PT T E fα,γ T1 s=1 θ̂sH , T1 s=1 β̂ sH − fα,γ (θ∗ , β ∗ ) (1 − γ) + γ/α √ =O . (24) T Proof. Write u = (θ, β) ∈ C × B and h i gα,γ (θ, β; ξ) = (1 − γ)f (θ; ξ) + γ β + α1 f (θ; ξ) − β + , so that fα,γ (u) = Eξ∼Qb [gα,γ (u; ξ)] by (14). (i) Convexity. The map (θ, β) 7→ f (θ; ξ) − β is jointly convex by Assumption 1, and (·)+ is convex and nondecreasing, so the composition is jointly convex; adding the affine term β and the convex term (1 − γ)f (θ; ξ) with nonnegative coefficients preserves convexity. Hence gα,γ (· ; ξ) is convex on C×B for every ξ, and so is fα,γ as a convex combination of such functions. (ii) Subgradients and the algorithm. A measurable subgradient selection of gα,γ is ∂θ gα,γ = w ∇θ f (θ; ξ),
∂β Gα,γ = 1 − w,
with w = ω(θ, β; ξ) ∈ [1 − γ, κ], which is exactly the pair of directions used in Lines 8–9 of Algorithm 2. Consequently the local step of Algorithm 2 is a projected stochastic subgradient step on fα,γ over C ×B, conditionally unbiased by Assumption 2 and the independence of ξit from Ft−1 . (iii) Constants. Since 0 ≤ w ≤ κ and |1 − w| ≤ κ, the Lipschitz, second-moment, and variance constants of Assumption 2 and Lemma 1 transfer to fα,γ as ℓα,γ ≤ κ ℓ + 1,
G2α,γ ≤ κ2 (G2 + 1),
2 σα,γ ≤ κ2 σ 2 ,
the additive constants arising from the β-coordinate, whose subgradient is bounded by κ independently of the data. In particular 2 = O(κ2 ). ℓα,γ = O(κ), Gα,γ = O(κ), and σα,γ (iv) Transfer of the analysis. Lemmata 2–4 use only convexity, non-expansiveness of the projection onto a convex compact set, and the three constants above; moreover the server averages the pairs (θi , βi ) jointly with the same weights 1/|S t |, so Lemma 4 applies verbatim to the product iterate on C ×B, whose projection is the Cartesian product ΠC × ΠB . Repeating the proof of The2 orem 1 with (ℓ, G, σ 2 ) replaced by (ℓα,γ , Gα,γ , σα,γ ) therefore yields, for every η > 0, E fα,γ (θ̄, β̄) − fα,γ (θ∗ , β ∗ ) D2 2 + η σα,γ + G2α,γ + 4ℓα,γ η Gα,γ H, ≤ 2ηT H where (θ̄, β̄) denotes the average of the T global checkpoints and D := supu,v∈C×B ∥u − v∥ < the right-hand side √ ∞. Minimizing over η gives η ⋆ = Θ 1/(κ T H) and, for fixed H, the stated √ bound of order κ(α, γ)/ T . Remark 2 (The Price of Risk Aversion). Theorem 2 makes the cost of robustness explicit. Setting γ = 0 gives κ = 1 and recovers Theorem 1 exactly, whereas γ = 1 with α → 0+ inflates the bound by 1/α, consistent with the degeneration of the mean–CVaR objective to an essential supremum in that limit. Moderate values, γ ∈ [0.1, 0.5] and α ∈ [0.01, 0.1], suffice to
11
(a) MNIST (non-uniform)
(b) FashionMNIST (non-uniform)
(c) CIFAR-10 (non-uniform)
Fig. 4: Test accuracy over communication rounds under non-uniform availability on MNIST, FashionMNIST, and CIFAR-10.
Fig. 5: Participation probabilities {pi } for M = 3, N = 30. realize the empirical gains reported in Section V. We note also that κ multiplies an upper bound and does not by itself imply slower observed convergence, since the risk-averse objective simultaneously reshapes the optimization landscape. V. E XPERIMENTS We evaluate the proposed algorithm on three standard imageclassification benchmarks—MNIST, FashionMNIST, and CIFAR10—with the aim of assessing robustness to the two fundamental sources of difficulty in FL: restricted client availability and statistical heterogeneity. Each dataset is partitioned across 30 clients, with each client receiving data from at most two classes, which induces a strongly non-IID distribution and a prototypical heterogeneous FL setting. Two availability regimes are considered. Under uniform availability, every client is equally likely to be selected in each round, as is commonly assumed in the FL literature. Under skewed availability, participation is concentrated: most clients are selected in the majority of rounds, while a small subset— here the three clients holding the rarest classes—participate only sporadically, with per-round probabilities as low as those reported in Fig. 5. This models deployments in which availability is sparse and imbalanced. In all runs the RAM selects M = 3 of the N = 30 clients per round. We compare F EDE R AGE against plain FedAvg and two widely adopted heterogeneity-aware baselines. F ED P ROX [29] augments the local objectives with a proximal term that mitigates client drift and stabilizes convergence. SCAFFOLD [16] employs control
variates, i.e., auxiliary parameters that correct client updates and improve the alignment of local and global gradients. Transportbased aggregation [32] is not included as a baseline, as it requires server-side knowledge of the availability law and is therefore inapplicable in the agnostic regime studied here. In the uniform regime, in which statistical heterogeneity is the dominant source of variance, F EDE R AGE performs on par with or better than SCAFFOLD. On the most demanding benchmark, CIFAR-10, it outperforms SCAFFOLD notwithstanding the latter’s more elaborate update mechanism and larger memory footprint. On MNIST and FashionMNIST, SCAFFOLD attains a marginally higher final mean accuracy, but with markedly larger dispersion across runs, so that F EDE R AGE is preferable once mean and dispersion are read jointly (Table I and Fig. 4); this indicates more stable and more predictable convergence. F EDE R AGE also reaches competitive accuracy within fewer communication rounds. In the more realistic skewed regime, in which client drift and selection bias act simultaneously, the advantage of F EDE R AGE is more pronounced. It outperforms all baselines on the three benchmarks, with a margin that widens on the more complex datasets (Table I and Fig. 4). As shown in Fig. 6, the accuracy attained for the least frequently selected clients remains high, which is an essential property when availability is irregular and unpredictable. We further examine fairness by evaluating the global model on each client’s local test data over the final ten communication rounds. Fig. 6 indicates that SCAFFOLD, while adequate on average, underperforms substantially on the three least active clients, whereas F EDE R AGE delivers uniformly high accuracy across the client population—a property of interest in fairnesssensitive deployments. With respect to convergence, Theorem 2 guarantees a rate of √ order 1/ T in the number of communication rounds, up to the risk-dependent factor κ(α, γ) discussed in Remark 2. Empirically, we observe a consistent acceleration across datasets, in that the risk-weighted updates of Algorithm 2 reach a given accuracy level in fewer rounds (Fig. 4). With respect to computation and communication, SCAFFOLD maintains and transmits a control variate of the same dimension d′ as the model, approximately doubling the per-round communication, whereas F EDE R AGE introduces a single scalar β per client. Beyond the reduction in memory and bandwidth, this also reduces what each client discloses, as discussed in Section III. Under equal communication budgets, the saving may be reallocated to larger models or more frequent updates at no additional cost. In summary, the experiments indicate that F EDE R AGE attains
12
Fig. 6: Restricted client availability on FashionMNIST (dashed lines mark each mean across clients for each algorithm). Under the non-uniform participation profile of 5, F EDE R AGE remains accurate even for the three most infrequently available clients (IDs 27–29), which the baselines effectively never sample. (i) higher accuracy, (ii) improved per-client fairness, (iii) faster convergence, and (iv) lower overhead across the scenarios considered, which, together with the guarantees of Section IV, supports its practicality under restricted and unknown participation. A. Implementation Details and Ablations All algorithms were tuned by hyperparameter sweeps on a dedicated validation set, and all reported results are averaged over five independent runs with distinct random seeds. The sweeps cover the step sizes ηθ and ηβ , the number of local steps H, the proximal coefficient of F ED P ROX, and the risk parameters (α, γ) of F EDE R AGE. The selected values, the model architectures and data partitions used for each benchmark, the sensitivity of F EDE R AGE to (α, γ), and per-client accuracies for the uniformavailability regime are reported in the accompanying supplementary material, together with the code required to reproduce every figure and table. VI. C ONCLUSION AND F UTURE W ORK We have introduced a framework for federated learning under restricted, imbalanced, and unknown client availability. We first characterized and analyzed agnostic FedAvg under a general √ variable-size random-access model, establishing an O(1/ T ) rate for convex, possibly nonsmooth losses; we then constructed on that basis a distributionally robust, CVaR-based √ algorithm, F EDE R AGE, and proved a matching O(κ(α, γ)/ T ) guarantee in which the price of risk aversion is explicit. Experiments on standard benchmarks, under both uniform and highly imbalanced availability, indicate improved accuracy and stability relative to state-of-the-art methods, with the largest gains where participation is most skewed. Future Directions—Those are as follows: • Adaptive risk parameters. Selecting or adapting (α, γ) automatically during training could improve robustness and generalization further. • Multi-CVaR formulations. Imposing several CVaR constraints/components, each regulating a different aspect of the
objective, would afford finer control over client-level fairness and performance. • Hybrid alignment and hedging. When the availability law is partially observable, transport-based alignment and the CVaRbased hedging developed here compose naturally: one may align against an estimated availability distribution and rely on a risk-averse local objective to absorb the residual estimation error. Characterizing the resulting bias–robustness trade-off is an appealing direction. • Broader evaluation. Extending the evaluation to further domains, such as natural language processing or deployed federated systems, would strengthen the empirical case. • Fairness in FL. The experiments show that fairness, modeled here through the minimum per-client accuracy, is improved; a formal treatment, together with a comparison to the minimax notion of [34], remains open. • Nonconvex regimes. Extending both the agnostic and the riskaverse analyses beyond convexity, e.g., to stationarity guarantees for deep models, is an important next step. R EFERENCES [1] H. Rahimi and D. Kalogerias, “Convergence of agnostic federated averaging,” in Proc. IEEE Int. Workshop Comput. Adv. Multi-Sensor Adaptive Process. (CAMSAP), 2025, pp. 1–5. [2] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2017. [Online]. Available: https://arxiv.org/abs/1610.05492 [3] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 54, 2017, pp. 1273–1282. [Online]. Available: http://proceedings.mlr.press/v54/mcmahan17a.html [4] P. Kairouz, H. B. McMahan, B. Avent et al., “Advances and open problems in federated learning,” Foundations and Trends in Machine Learning, vol. 14, no. 1–2, pp. 1–210, 2021. [5] R. C. Geyer, T. Klein, and M. Nabi, “Differentially private federated learning: A client level perspective,” arXiv preprint arXiv:1712.07557, 2017. [Online]. Available: https://arxiv.org/abs/1712.07557 [6] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” arXiv preprint arXiv:1807.00459, 2018. [Online]. Available: https://arxiv.org/abs/1807.00459
13
[7] S. J. Reddi, J. Konečný, P. Richtárik, B. Póczós, and A. Smola, “AIDE: Fast and communication efficient distributed optimization,” arXiv preprint arXiv:1608.06879, 2016. [Online]. Available: https: //arxiv.org/abs/1608.06879 [8] G. F. Coppola, “Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing,” Ph.D. dissertation, University of Adelaide, 2015. [Online]. Available: https://digital.library.adelaide.edu.au/dspace/handle/2440/108087 [9] J. Konečný, H. B. McMahan, and D. Ramage, “Federated optimization: Distributed optimization beyond the datacenter,” arXiv preprint arXiv:1511.03575, 2015. [Online]. Available: https://arxiv.org/abs/1511.03575 [10] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra, “Federated learning with non-iid data,” arXiv preprint arXiv:1806.00582, 2018. [Online]. Available: https://arxiv.org/abs/1806.00582 [11] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998. [Online]. Available: https: //ieeexplore.ieee.org/document/726791 [12] S.-B. Lin, X. Guo, and D.-X. Zhou, “Distributed learning with regularized least squares,” Journal of Machine Learning Research, vol. 18, no. 1, pp. 3202–3232, 2017. [Online]. Available: https: //jmlr.org/papers/v18/16-577.html [13] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” arXiv preprint arXiv:1908.07873, 2019. [Online]. Available: https://arxiv.org/abs/1908.07873 [14] K. Pillutla, Y. Laguel, J. Malick, and Z. Harchaoui, “Federated learning with superquantile aggregation for heterogeneous data,” Machine Learning, vol. 113, no. 5, pp. 2955–3022, 2023. [Online]. Available: https://doi.org/10.1007/s10994-023-06332-x [15] B. Hitaj, G. Ateniese, and F. Pérez-Cruz, “Deep models under the GAN: Information leakage from collaborative deep learning,” in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2017. [Online]. Available: https://dl.acm.org/doi/10.1145/3133956.3134012 [16] S. P. Karimireddy, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh, “Scaffold: Stochastic controlled averaging for federated learning,” in Proceedings of the International Conference on Machine Learning (ICML), vol. 119, 2020, pp. 5132–5143. [Online]. Available: https://proceedings.mlr.press/v119/karimireddy20a.html [17] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the objective inconsistency problem in heterogeneous federated optimization,” in Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020, pp. 7611–7623. [Online]. Available: https://proceedings.neurips.cc/ paper files/paper/2020/file/564127c03caaab942e503ee6f810f54d-Paper.pdf [18] R. Ye, M. Xu, J. Wang, C. Xu, S. Chen, and Y. Wang, “Feddisco: Federated learning with discrepancy-aware collaboration,” in Proceedings of the International Conference on Machine Learning (ICML), vol. 202, 2023, pp. 39 879–39 902. [Online]. Available: https://proceedings.mlr.press/ v202/ye23f.html [19] M. Hong, M. Razaviyayn, and J.-S. P. Lee, “Gradient primal-dual algorithm converges to second-order stationary solution for nonconvex distributed optimization over networks,” in Proceedings of the International Conference on Machine Learning (ICML), vol. 80, 2018. [Online]. Available: https://proceedings.mlr.press/v80/hong18a.html [20] D. Jakovetić, “Distributed optimization: Algorithms and convergence rates,” Ph.D. dissertation, Carnegie Mellon University, 2013. [Online]. Available: https://repository.cmu.edu/dissertations/312/ [21] M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V. Josifovski, J. Long, E. J. Shekita, and B.-Y. Su, “Scaling distributed machine learning with the parameter server,” in Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2014, pp. 583–598. [Online]. Available: https://www.usenix.org/conference/osdi14/ technical-sessions/presentation/li mu [22] Y. J. Cho, J. Wang, and G. Joshi, “Towards understanding biased client selection in federated learning,” in Proc. Int. Conf. Artif. Intell. Statist. (AISTATS), ser. PMLR, vol. 151, 2022, pp. 10 351–10 375. [Online]. Available: https://proceedings.mlr.press/v151/jee-cho22a.html [23] J. Wang, Q. Liu, H. Liang, G. Joshi, H. V. Poor, A. K. Sahu, S. Stich, T. Wang, P. Kairouz, A. T. Suresh, and H. B. McMahan, “A field guide to federated optimization,” arXiv preprint arXiv:2107.06917, 2021. [Online]. Available: https://arxiv.org/abs/2107.06917 [24] H. Eichner, T. Koren, B. McMahan, N. Srebro, and K. Talwar, “Semi-cyclic stochastic gradient descent,” in Proceedings of the International Conference on Machine Learning (ICML), vol. 97, 2019, pp. 1764–1773. [Online]. Available: https://proceedings.mlr.press/v97/eichner19a.html [25] Y. Ruan, X. Zhang, S.-C. Liang, and C. Joe-Wong, “Towards flexible device participation in federated learning,” in Proceedings of the International Conference on Artificial Intelligence and Statistics
(AISTATS), vol. 130, 2021, pp. 3403–3411. [Online]. Available: https: //proceedings.mlr.press/v130/ruan21a.html [26] M. Ribero, H. Vikalo, and G. de Veciana, “Federated learning under intermittent client availability and time-varying communication constraints,” IEEE Journal of Selected Topics in Signal Processing, vol. 17, no. 1, pp. 98–111, 2023. [27] P. Theodoropoulos, K. E. Nikolakakis, and D. Kalogerias, “Federated learning under restricted user availability,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2024, arXiv:2309.14176. [28] A. Khaled, K. Mishchenko, and P. Richtárik, “First analysis of local GD on heterogeneous data,” arXiv preprint arXiv:1909.04715, 2019. [Online]. Available: https://arxiv.org/abs/1909.04715 [29] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” in Proc. Mach. Learn. Syst. (MLSys), vol. 2, 2020, pp. 429–450. [Online]. Available: https://proceedings.mlsys.org/paper files/paper/2020/ hash/1f5fe83998a09396ebe6477d9475ba0c-Abstract.html [30] S. J. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMahan, “Adaptive federated optimization,” in Proc. Int. Conf. Learn. Representations (ICLR), 2021. [Online]. Available: https://openreview.net/forum?id=LkFG3lB13U5 [31] H. Yang, X. Zhang, P. Khanduri, and J. Liu, “Anarchic federated learning,” in Proceedings of the International Conference on Machine Learning (ICML), vol. 162, 2022, pp. 25 331–25 363. [Online]. Available: https://proceedings.mlr.press/v162/yang22r.html [32] H. Rahimi and D. Kalogerias, “FedAVOT: Exact distribution alignment in federated learning via masked optimal transport,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2026, to appear. [33] T. A. Nguyen, T. D. Nguyen, L. T. Le, and C. T. Dinh, “On the generalization of wasserstein robust federated learning,” arXiv preprint arXiv:2206.01432, 2022. [Online]. Available: https://arxiv.org/abs/2206. 01432 [34] M. Mohri, G. Sivek, and A. T. Suresh, “Agnostic federated learning,” in Proc. Int. Conf. Mach. Learn. (ICML), ser. PMLR, vol. 97, 2019, pp. 4615– 4625. [Online]. Available: https://proceedings.mlr.press/v97/mohri19a.html [35] Y. Yu, S. P. Karimireddy, Y. Ma, and M. I. Jordan, “ScaffPD: Communication efficient fair and robust federated learning,” arXiv preprint arXiv:2307.13381, 2023. [Online]. Available: https: //arxiv.org/abs/2307.13381 [36] Y. Deng and M. M. Kamani, “Distributionally robust federated averaging,” in Advances in Neural Information Processing Systems (NeurIPS), 2020. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/ ac450d10e166657ec8f93a1b65ca1b14-Paper.pdf [37] J. Hong, H. Wang, Z. Wang, and J. Zhou, “Federated robustness propagation: Sharing adversarial robustness in federated learning,” arXiv preprint arXiv:2106.11264, 2021. [Online]. Available: https: //arxiv.org/abs/2106.11264 [38] S. Shi, Y. Guo, D. Wang, and Y. Zhu, “Distributionally robust federated learning for network traffic classification with noisy labels,” IEEE Transactions on Network and Service Management, 2023. [Online]. Available: https://ieeexplore.ieee.org/document/10265143 [39] D. Levy, Y. Carmon, J. C. Duchi, and A. Sidford, “Large-scale methods for distributionally robust optimization,” in Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020, pp. 8847–8860. [40] R. T. Rockafellar and S. Uryasev, “Optimization of conditional value-atrisk,” Journal of Risk, vol. 2, no. 3, pp. 21–41, 2000. [41] A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory. Philadelphia, PA: SIAM and Mathematical Optimization Society, 2009.