FedeRage: Provably Convergent Agnostic Federated Learning under General Client Drift

# Provably Convergent Agnostic Federated Learning under General Client Drift
Source: [https://arxiv.org/html/2609.21057](https://arxiv.org/html/2609.21057)
Dionysis KalogeriasSenior Member, IEEE††thanks:This work has been supported by the US National Science Foundation under Grants 2242215 and 2431860\.††thanks:Preliminary results leading to this paper were presented in part at the2025 IEEE International Workshop on Computational Advances in Multi\-Sensor Adaptive Processing \(CAMSAP\)˜\[[1](https://arxiv.org/html/2609.21057#bib.bib17)\]\.

###### 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𝒪⁡\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)rate for convex and possibly nonsmooth losses\. Building on this characterization, we propose*Federated Risk\-Averse Averaging*\(FedeRage\), 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\.FedeRageimplicitly upweights high\-loss and infrequently participating clients while adding only a*single scalar per\-client*, and admits an𝒪⁡\(κ/T\)\\mathcal\{O\}\(\\kappa/\\sqrt\{T\}\)rate in which the factorκ\\kappais 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,FedeRageremains 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\.

## IIntroduction

Federated 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](https://arxiv.org/html/2609.21057#bib.bib30),[3](https://arxiv.org/html/2609.21057#bib.bib22),[4](https://arxiv.org/html/2609.21057#bib.bib5),[5](https://arxiv.org/html/2609.21057#bib.bib25),[6](https://arxiv.org/html/2609.21057#bib.bib23),[7](https://arxiv.org/html/2609.21057#bib.bib36),[8](https://arxiv.org/html/2609.21057#bib.bib24)\]\. 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](https://arxiv.org/html/2609.21057#bib.bib22),[9](https://arxiv.org/html/2609.21057#bib.bib31)\]—and the process repeats until convergence \(see Algorithm[1](https://arxiv.org/html/2609.21057#alg1)\)\. 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](https://arxiv.org/html/2609.21057#bib.bib9),[11](https://arxiv.org/html/2609.21057#bib.bib32),[12](https://arxiv.org/html/2609.21057#bib.bib35)\]\. This induces*client drift*, the divergence of local optimization trajectories, which slows or destabilizes aggregation and degrades generalization; this has been studied extensively in the FL literature\[[13](https://arxiv.org/html/2609.21057#bib.bib34),[14](https://arxiv.org/html/2609.21057#bib.bib14),[15](https://arxiv.org/html/2609.21057#bib.bib26),[16](https://arxiv.org/html/2609.21057#bib.bib11),[17](https://arxiv.org/html/2609.21057#bib.bib12),[18](https://arxiv.org/html/2609.21057#bib.bib15)\]\. 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](https://arxiv.org/html/2609.21057#bib.bib27),[20](https://arxiv.org/html/2609.21057#bib.bib28),[21](https://arxiv.org/html/2609.21057#bib.bib33),[22](https://arxiv.org/html/2609.21057#bib.bib6),[23](https://arxiv.org/html/2609.21057#bib.bib19),[24](https://arxiv.org/html/2609.21057#bib.bib20),[25](https://arxiv.org/html/2609.21057#bib.bib21),[26](https://arxiv.org/html/2609.21057#bib.bib8)\]\. Such*restricted availability*systematically biases aggregation toward frequently active clients while underrepresenting sporadic participants, resulting in slower convergence and degraded fairness\[[27](https://arxiv.org/html/2609.21057#bib.bib16)\]\.

![Refer to caption](https://arxiv.org/html/2609.21057v1/DecisionBoundryfedAvg.png)
![Refer to caption](https://arxiv.org/html/2609.21057v1/DecisionBoundryFedeRAG.png)
![Refer to caption](https://arxiv.org/html/2609.21057v1/motivationexample.png)

Fig\. 1:Motivating example: Interaction of statistical heterogeneity and skewed availability\. Five clients possess highly non\-IID data \(clustered by user\)\. Client availability is skewed: three clients participate with probability0\.30\.3, two with0\.050\.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\.A key observation underlying this work is that, beyond being non\-uniform and potentially highly skewed, client availability is in practice alsounknown to the server, who nonetheless must coordinate aggregation in standard FL protocols\[[10](https://arxiv.org/html/2609.21057#bib.bib9)\]\. 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](https://arxiv.org/html/2609.21057#bib.bib16)\], 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 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](https://arxiv.org/html/2609.21057#bib.bib22),[28](https://arxiv.org/html/2609.21057#bib.bib29)\], its performance deteriorates in regimes exhibiting both data heterogeneity and availability imbalance\. Fig\.[1](https://arxiv.org/html/2609.21057#S1.F1)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,FedeRage\(Section[III](https://arxiv.org/html/2609.21057#S3)\), rebalances the effective weighting of clients in light of stochastic participation, yielding both faster convergence and more equitable performance\.

### I\-APrior 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\.*FedProx\[[29](https://arxiv.org/html/2609.21057#bib.bib1)\]stabilizes training with a proximal term that keeps local updates close to the global model, and SCAFFOLD\[[16](https://arxiv.org/html/2609.21057#bib.bib11)\]employs control variates to correct client drift, at the cost of communicating an additional model\-sized vector per round\. Complementary analyses\[[10](https://arxiv.org/html/2609.21057#bib.bib9),[28](https://arxiv.org/html/2609.21057#bib.bib29)\]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\.*FedOptand its variants\[[30](https://arxiv.org/html/2609.21057#bib.bib4)\]replace the plain server average with adaptive, momentum\-based server updates; FedNova\[[17](https://arxiv.org/html/2609.21057#bib.bib12)\]normalizes contributions by local training effort; and anarchic FL\[[31](https://arxiv.org/html/2609.21057#bib.bib13)\]adapts aggregation to asynchronous participation\. FedDisco\[[18](https://arxiv.org/html/2609.21057#bib.bib15)\]reweights clients according to label imbalance, while availability\-aware client selection\[[26](https://arxiv.org/html/2609.21057#bib.bib8),[22](https://arxiv.org/html/2609.21057#bib.bib6)\]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](https://arxiv.org/html/2609.21057#bib.bib9)\]\. Transport\-based aggregation removes this mismatch exactly, by casting aggregation as a masked optimal transport problem between the two marginals\[[32](https://arxiv.org/html/2609.21057#bib.bib18)\]; importance\-sampling and client\-selection schemes pursue the same objective by other means\[[14](https://arxiv.org/html/2609.21057#bib.bib14),[33](https://arxiv.org/html/2609.21057#bib.bib37)\]\. Each of these mechanisms, however, requires the server to know—or to be able to estimate—the availability distribution, which enters the transport or importance\-sampling 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 risk\-averse 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](https://arxiv.org/html/2609.21057#bib.bib2)\], 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ℛ\\mathcal\{R\}, and simply averages whatever it receives\.

### I\-BMotivation forFedeRage

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*\(FedeRage\), an FL algorithm built on a risk\-averse framework that embeds the*Conditional Value\-at\-Risk*\(CVaR\) into the local objective\. Coupling the participation distribution with a mean–CVaR formulation causesFedeRageto upweight high\-loss and infrequently selected clients implicitly, conferring robustness to statistical and availability heterogeneity within a single DRO framework\. The algorithm \(Algorithm[2](https://arxiv.org/html/2609.21057#alg2)\) 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](https://arxiv.org/html/2609.21057#bib.bib16)\]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](https://arxiv.org/html/2609.21057#bib.bib14),[33](https://arxiv.org/html/2609.21057#bib.bib37),[35](https://arxiv.org/html/2609.21057#bib.bib38),[36](https://arxiv.org/html/2609.21057#bib.bib39),[37](https://arxiv.org/html/2609.21057#bib.bib40),[38](https://arxiv.org/html/2609.21057#bib.bib41)\]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](https://arxiv.org/html/2609.21057#bib.bib7)\]; 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](https://arxiv.org/html/2609.21057#bib.bib16)\]to*variable\-size*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𝒪⁡\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)rate for convex, possibly nonsmooth losses under an unknown, non\-uniform, variable\-size participation law\.
- •*Risk\-aware formulation\.*We proposeFedeRage, a CVaR\-based 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\.
- •*Convergence ofFedeRage\.*We prove that the agnostic FedAvg analysis transfers to the mean–CVaR objective, with the rate inflated by the explicit factorκ⁡\(α,γ\)=\(1−γ\)\+γ/α\\kappa\(\\alpha,\\gamma\)=\(1\-\\gamma\)\+\\gamma/\\alphawhereγ∈\[0,1\]\\gamma\\in\[0,1\]interpolates between mean \(γ=0\\gamma=0\) and CVaR \(γ=1\\gamma=1\), andα∈\(0,1\]\\alpha\\in\(0,1\]is the CVaR quantile level\.
- •*Empirical validation\.*We show thatFedeRageimproves 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](https://arxiv.org/html/2609.21057#S2)introduces the preliminaries and the problem setup\. Section[III](https://arxiv.org/html/2609.21057#S3)presents the proposedFedeRageframework and its primal and dual interpretations\. Section[IV](https://arxiv.org/html/2609.21057#S4)develops the convergence analysis, with all proofs given in place\. Section[V](https://arxiv.org/html/2609.21057#S5)reports the experiments and implementation details\. Section[VI](https://arxiv.org/html/2609.21057#S6)concludes\.

Algorithm 1Agnostic Federated Averaging \(FedAvg\)1:Initialize:

θi0=𝟎\\theta\_\{i\}^\{0\}=\\mathbf\{0\}for

i∈\[N\]i\\in\[N\]; horizon

TT; local steps

HH; step size

ηθ\>0\\eta\_\{\\theta\}\>0; constraint set

𝒞⊆Θ\\mathcal\{C\}\\subseteq\\Theta\.

2:for

t=1,2,…,T​Ht=1,2,\\dots,THdo

3:if

tmodH=0t\\bmod H=0then⊳\\triangleright*Global communication*

4:Clients transmit local parameters through RAM\.

5:Server receives

St⊆\[N\]S^\{t\}\\subseteq\[N\]\.

6:Serveraggregates:

θ^t=1\|St\|​∑i∈Stθit−1\\displaystyle\{\\hat\{\\theta\}^\{t\}=\\frac\{1\}\{\|S^\{t\}\|\}\\sum\_\{i\\in S^\{t\}\}\\theta\_\{i\}^\{t\-1\}\}\.

7:Serverbroadcasts

θ^t\\hat\{\\theta\}^\{t\}and sets

θit=θ^t\\theta\_\{i\}^\{t\}=\\hat\{\\theta\}^\{t\},

∀i∈\[N\]\\forall i\\in\[N\]\.

8:else⊳\\triangleright*Local updates*

9:Each client performs stochastic subgradient step:

10:

θit=Π𝒞​\(θit−1−ηθ​∇θfi​\(θit−1,ξit\)\),∀i∈\[N\]\\theta\_\{i\}^\{t\}=\\Pi\_\{\\mathcal\{C\}\}\\\!\\left\(\\theta\_\{i\}^\{t\-1\}\-\\eta\_\{\\theta\}\\nabla\_\{\\theta\}f\_\{i\}\(\\theta\_\{i\}^\{t\-1\};\\xi\_\{i\}^\{t\}\)\\right\),\\ \\forall i\\in\[N\]\.

11:Return:

1T​∑τ=1Tθ^τ​H\\dfrac\{1\}\{T\}\\sum\_\{\\tau=1\}^\{T\}\\hat\{\\theta\}^\{\\tau H\}\.

## IIProblem Definition

We tacitly consider a distributed multi\-class classification task with feature space𝔛⊂ℝd\\mathfrak\{X\}\\subset\\mathbb\{R\}^\{d\}, target classes𝒞=\{1,…,C\}\\mathcal\{C\}=\\\{1,\.\.\.,C\\\}, parameter spaceΘ⊆ℝd′\\Theta\\subseteq\\mathbb\{R\}^\{d^\{\\prime\}\}, a given loss functionℓ:𝒞×𝒞→ℝ\+\\ell:\\mathcal\{C\}\\times\\mathcal\{C\}\\rightarrow\\mathbb\{R\}\_\{\+\}, and a parametric model \(i\.e\., a learning representation\)m:𝔛×Θ→𝒞m:\\mathfrak\{X\}\\times\\Theta\\rightarrow\\mathcal\{C\}111While we work in the classification setting, our considerations work more generally, e\.g, for regression tasks as well\.\. Unlike traditional \(centralized\) learning, inFederated Learning \(FL\), data are distributed amongNNclients \(or agents, or users\), each with their own private datasetDi=\{\(Xi1,Yi1\),…,\(Xini,Yini\)\}D\_\{i\}=\\\{\(X\_\{i\}^\{1\},Y\_\{i\}^\{1\}\),\\dots,\(X\_\{i\}^\{n\_\{i\}\},Y\_\{i\}^\{n\_\{i\}\}\)\\\}and local parameterθi∈Θ\\theta\_\{i\}\\in\\Theta, as well as their own local expected loss

f⁡\(θ,Di\)\\displaystyle\\hskip\-2\.0ptf\(\\theta;D\_\{i\}\)=𝔼𝒟i​\[ℓ⁡\(m⁡\(X,θ\),Y\)\]=1ni​∑j=1niℓ⁡\(m⁡\(Xij,θ\),Yij\),\\displaystyle=\\mathbb\{E\}\_\{\\mathcal\{D\}\_\{i\}\}\[\\ell\(m\(X,\\theta\),Y\)\]=\\frac\{1\}\{n\_\{i\}\}\\sum\_\{j=1\}^\{n\_\{i\}\}\\ell\(m\(X^\{j\}\_\{i\},\\theta\),Y^\{j\}\_\{i\}\),\(1\)where𝒟i\\mathcal\{D\}\_\{i\}denotes the corresponding empirical distribution induced by the local datasetDiD\_\{i\}, for each clientii\. Throughout the paper we will use the following conventions as well:fi​\(⋅\)=f⁡\(⋅,Di\),f⁡\(⋅\)=∑i=1npi​fi​\(⋅\)f\_\{i\}\(\\cdot\)=f\(\\cdot,D\_\{i\}\),f\(\\cdot\)=\\sum\_\{i=1\}^\{n\}p\_\{i\}f\_\{i\}\(\\cdot\)\.

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](https://arxiv.org/html/2609.21057#bib.bib16)\]and substantially extended herein\), that selects a subset of users at each round and transmits their parameters to the server with a fixed but unknown probability distribution \(see Section[II\-B](https://arxiv.org/html/2609.21057#S2.SS2)\)\.

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, allNNusers \(attempt to\) transmit their local parameter vectors to the server \(passing through the RAM\), and the RAM selectsMMout ofNNusers based on a certain but general probabilistic structure \(see Section[II\-B](https://arxiv.org/html/2609.21057#S2.SS2)for details\)\. Then, the server aggregates the received parameter vectors \(MMin number\) with an aggregation policy and broadcasts the aggregation result to allNNclients \(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θ∗\\theta^\{\*\}that performs optimally on the weighted loss of all users, i\.e\., to solve the problem

infθ∈Θ\{∑i=1Npif\(θ;Di\)=𝔼I∼𝒫\[f\(θ;DI\)\]\},\\displaystyle\\inf\_\{\\theta\\in\\Theta\}\\hskip\-1\.00374pt\\Bigg\\\{\\hskip\-2\.00749pt\\sum\_\{i=1\}^\{N\}p\_\{i\}f\(\\theta;D\_\{i\}\)\\hskip\-2\.00749pt=\\hskip\-1\.00374pt\\mathbb\{E\}\_\{I\\sim\\mathcal\{P\}\}\\big\[f\(\\theta;D\_\{I\}\)\\big\]\\hskip\-2\.00749pt\\Bigg\\\},\(2\)where the weights\{pi\}i=1N\\\{p\_\{i\}\\\}^\{N\}\_\{i=1\}\(defining𝒫\\mathcal\{P\}\) constitute appropriateposteriorclient participation probabilitiesinducedby the stochastic mechanism implemented by the RAM, reflecting thesystemic randomnessof user availability \(see Section[II\-B](https://arxiv.org/html/2609.21057#S2.SS2)\)\.

Problem[2](https://arxiv.org/html/2609.21057#S2.E2)could \(hopefully\) be tackled by means of the \(agnostic\)Federated Average Algorithm \(FedAvg\)\(see Algorithm[1](https://arxiv.org/html/2609.21057#alg1)\), consisting of two alternating stages, also calledrounds:local updaterounds, andglobal communicationrounds, 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 forHHconsecutive iterations222For simplicity, we assume that all users employ the same number of local iterationsHH; this assumption can be relaxed in both analysis and practice\.\. During each global communication round, the optimized parameters of allNNusers aretransmitted towards the server, first passing through the RAM\(which may also be thought of as an multi\-erasure channel; see Section[II\-B](https://arxiv.org/html/2609.21057#S2.SS2)\)\. Then, the server aggregates the received parameters of the resultingM≤NM\\leq Nusers 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](https://arxiv.org/html/2609.21057#alg1)\) is in fact an appropriate method to solve Problem[2](https://arxiv.org/html/2609.21057#S2.E2)remains an open question in the current literature\. The agnostic nature of the algorithm —embodied in its use of uniform averaging over theMMreceived parameters from the clients— may not necessarily account for the client availability distribution𝒫\\mathcal\{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](https://arxiv.org/html/2609.21057#alg1)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](https://arxiv.org/html/2609.21057#S2.E2), 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𝒫\\mathcal\{P\}is developed in Section[II\-B](https://arxiv.org/html/2609.21057#S2.SS2)and later in Section[IV](https://arxiv.org/html/2609.21057#S4)\.

### II\-AAn Alternative Representation of the FL Problem

Suppose that all clients adopt a common*mini\-batch size*bb\. Each mini\-batch is a setξij\\xi\_\{i\}^\{j\}, withi∈\[N\]i\\in\[N\]andj∈\{1,…,Nib\}j\\in\\\{1,\\dots,N^\{b\}\_\{i\}\\\}, whereNib:=\(nib\)N^\{b\}\_\{i\}:=\\binom\{n\_\{i\}\}\{b\}; letDib=⋃j=1Nib\{ξij\}D^\{b\}\_\{i\}=\\bigcup\_\{j=1\}^\{N^\{b\}\_\{i\}\}\\\{\\xi\_\{i\}^\{j\}\\\}be the collection of all mini\-batches of sizebb\. Writing the average loss over a mini\-batchξ\\xiasf⁡\(θ,ξ\)=1b​∑\(X,Y\)∈ξℓ⁡\(m⁡\(X,θ\),Y\)f\(\\theta;\\xi\)=\\frac\{1\}\{b\}\\sum\_\{\(X,Y\)\\in\\xi\}\\ell\(m\(X,\\theta\),Y\)and the average over all mini\-batches asf⁡\(θ,Dib\)=\(1/Nib\)​∑j=1Nibf⁡\(θ,ξij\)f\(\\theta;D\_\{i\}^\{b\}\)=\(1/N^\{b\}\_\{i\}\)\\sum\_\{j=1\}^\{N^\{b\}\_\{i\}\}f\(\\theta;\\xi\_\{i\}^\{j\}\), a double\-counting argument yields

f⁡\(θ,Dib\)\\displaystyle f\(\\theta;D\_\{i\}^\{b\}\)=1Nib​b​∑j=1Nib∑\(X,Y\)∈ξijℓ⁡\(m⁡\(X,θ\),Y\)\\displaystyle=\\frac\{1\}\{N^\{b\}\_\{i\}\\,b\}\\sum\_\{j=1\}^\{N^\{b\}\_\{i\}\}\\sum\_\{\(X,Y\)\\in\\xi\_\{i\}^\{j\}\}\\ell\(m\(X,\\theta\),Y\)\(3\)=1Nib​b​∑\(X,Y\)∈Di\(ni−1b−1\)​ℓ​\(m⁡\(X,θ\),Y\)\\displaystyle=\\frac\{1\}\{N^\{b\}\_\{i\}\\,b\}\\sum\_\{\(X,Y\)\\in D\_\{i\}\}\\binom\{n\_\{i\}\-1\}\{b\-1\}\\,\\ell\(m\(X,\\theta\),Y\)=1ni​∑\(X,Y\)∈Diℓ⁡\(m⁡\(X,θ\),Y\)=f⁡\(θ,Di\),\\displaystyle=\\frac\{1\}\{n\_\{i\}\}\\sum\_\{\(X,Y\)\\in D\_\{i\}\}\\ell\(m\(X,\\theta\),Y\)=f\(\\theta;D\_\{i\}\),where we used\(ni−1b−1\)/\(Nib​b\)=1/ni\\binom\{n\_\{i\}\-1\}\{b\-1\}/\\big\(N\_\{i\}^\{b\}\\,b\\big\)=1/n\_\{i\}\. Hence, for every mini\-batch sizebb, Problem \([2](https://arxiv.org/html/2609.21057#S2.E2)\) can be re\-expressed as

infθ\{∑i=1Npif\(θ;Dib\)=𝔼I∼𝒫\[f\(θ;DIb\)\]\},\\inf\_\{\\theta\}\\Bigg\\\{\\hskip\-1\.00374pt\\sum\_\{i=1\}^\{N\}p\_\{i\}f\(\\theta;D\_\{i\}^\{b\}\)\\hskip\-2\.00749pt=\\hskip\-1\.00374pt\\mathbb\{E\}\_\{I\\sim\\mathcal\{P\}\}\\big\[f\(\\theta;D\_\{I\}^\{b\}\)\\big\]\\hskip\-2\.00749pt\\Bigg\\\},\(4\)or, more compactly,

infθ𝔼ξ∼𝒬b​\[f⁡\(θ,ξ\)\],\\boxed\{\\inf\_\{\\theta\}\\,\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}\\left\[f\(\\theta;\\xi\)\\right\],\}\(5\)where𝒬b\\mathcal\{Q\}^\{b\}denotes the*mixture distribution*𝒬b=∑i=1Npi​𝒬ib\\mathcal\{Q\}^\{b\}=\\sum\_\{i=1\}^\{N\}p\_\{i\}\\,\\mathcal\{Q\}\_\{i\}^\{b\}, with𝒬ib\\mathcal\{Q\}\_\{i\}^\{b\}the uniform distribution overDibD\_\{i\}^\{b\}and𝒫\\mathcal\{P\}the participation distribution\. Under𝒬b\\mathcal\{Q\}^\{b\}, the probability thatξ\\xiequalsξij\\xi\_\{i\}^\{j\}ispi/Nibp\_\{i\}/N^\{b\}\_\{i\}fori∈\[N\]i\\in\[N\]andj∈\{1,…,Nib\}j\\in\\\{1,\\dots,N^\{b\}\_\{i\}\\\}, and zero otherwise\. We writeξi\\xi\_\{i\}for the random variable taking valuesξij\\xi\_\{i\}^\{j\},j∈\[Nib\]j\\in\[N\_\{i\}^\{b\}\], under𝒬ib\\mathcal\{Q\}\_\{i\}^\{b\}\.

Problems \([2](https://arxiv.org/html/2609.21057#S2.E2)\), \([4](https://arxiv.org/html/2609.21057#S2.E4)\), and \([5](https://arxiv.org/html/2609.21057#S2.E5)\) share the same objective\. In \([4](https://arxiv.org/html/2609.21057#S2.E4)\) and \([5](https://arxiv.org/html/2609.21057#S2.E5)\), however, the mini\-batch sizebbappears as part of the problem*formulation*instead of as a hyperparameter of a particular solver \(e\.g\. SGD\)\. We therefore refer tobbas the*model mini\-batch size*, to distinguish it from the*algorithmic mini\-batch size*used within an SGD implementation\. Operationally, solving \([2](https://arxiv.org/html/2609.21057#S2.E2)\) by SGD with algorithmic mini\-batchbbis equivalent to solving \([4](https://arxiv.org/html/2609.21057#S2.E4)\) or \([5](https://arxiv.org/html/2609.21057#S2.E5)\) by the same scheme with algorithmic mini\-batch11\.

### II\-BCanonical 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\[[25](https://arxiv.org/html/2609.21057#bib.bib21),[24](https://arxiv.org/html/2609.21057#bib.bib20),[23](https://arxiv.org/html/2609.21057#bib.bib19)\]\. 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](https://arxiv.org/html/2609.21057#bib.bib16)\]: an external, independent entity selects a subset of clientsSt⊆\[N\]S^\{t\}\\subseteq\[N\]at each communication roundtt\.

Canonical fixed\-size RAM\.LetM∈\{1,…,N\}M\\in\\\{1,\\ldots,N\\\}be fixed\. At each roundtt, the RAM selectsMMclients*without replacement*according to a stationary, possibly non\-uniform selection priorℛ\\mathcal\{R\}; that is,StS^\{t\}is drawn so that clientiisatisfies\{i∈St\}\\\{i\\in S^\{t\}\\\}with marginal probabilityℙ⁡\(i∈St\)\\mathbb\{P\}\(i\\in S^\{t\}\)determined byℛ\\mathcal\{R\}\.333IfM=NM=N, then regardless ofℛ\\mathcal\{R\}the marginal is uniform,ℙ⁡\(i∈St\)=1\\mathbb\{P\}\(i\\in S^\{t\}\)=1, and the induced weights below satisfypi=1/Np\_\{i\}=1/N\.Since allMMselected clients reach the server and are weighted uniformly, the weight effectively borne by clientii’s parameter is proportional toℙ⁡\(i∈St\)/M\\mathbb\{P\}\(i\\in S^\{t\}\)/M\. Accordingly, the natural weight on clientii’s empirical riskfi​\(θ\)f\_\{i\}\(\\theta\)in the global objective is its*probability of survival*through the two\-stage process of RAM selection followed by uniform averaging, i\.e\.,ℙ⁡\(i∈St\)/M\\mathbb\{P\}\(i\\in 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\]:

∑i=1Nℙ⁡\(i∈St\)\\displaystyle\\sum\_\{i=1\}^\{N\}\\mathbb\{P\}\(i\\in S^\{t\}\)=∑i=1N𝔼\[𝟙\{i∈St\}\]=𝔼\[∑i=1N𝟙\{i∈St\}\]\\displaystyle=\\sum\_\{i=1\}^\{N\}\\mathbb\{E\}\\big\[\\mathds\{1\}\\\{i\\in S^\{t\}\\\}\\big\]=\\mathbb\{E\}\\Bigg\[\\sum\_\{i=1\}^\{N\}\\mathds\{1\}\\\{i\\in S^\{t\}\\\}\\Bigg\]=𝔼⁡\[\|St\|\]=M\.\\displaystyle=\\mathbb\{E\}\\big\[\|S^\{t\}\|\\big\]=M\.\(6\)We may then plausibly take

pi:=ℙ⁡\(i∈St\)M=1M∑Sℙ\(St=S\)1\{i∈S\},∀i∈\[N\]\.p\_\{i\}:=\\frac\{\\mathbb\{P\}\(i\\in S^\{t\}\)\}\{M\}=\\frac\{1\}\{M\}\\sum\_\{S\}\\mathbb\{P\}\(S^\{t\}=S\)\\,\\mathds\{1\}\\\{i\\in S\\\},\\,\\forall i\\in\[N\]\.\(7\)Since the selection dynamics are stationary, the weightspip\_\{i\}do not depend ontt\. The distribution𝒫:=\(p1,…,pN\)\\mathcal\{P\}:=\(p\_\{1\},\\dots,p\_\{N\}\)is shaped by the selection budgetMM: forM=NM=N\(full participation\),pi=1/Np\_\{i\}=1/Nfor alliiregardless ofℛ\\mathcal\{R\}; forM=1M=1,𝒫\\mathcal\{P\}coincides with the RAM’s singleton sampling distribution\.

General case: variable\-size RAM\.When\|St\|\|S^\{t\}\|is not fixed, the normalized weights remain well defined through a convex combination over subset sizes:

pi=∑S⊆\[N\]ℛ⁡\(S\)\|S\|1\{i∈S\},for alli∈\[N\],\\boxed\{\\,p\_\{i\}=\\sum\_\{S\\subseteq\[N\]\}\\frac\{\\mathcal\{R\}\(S\)\}\{\|S\|\}\\,\\mathds\{1\}\\\{i\\in S\\\}\\,,\}\\quad\\text\{for all \}i\\in\[N\],\(8\)whereℛ⁡\(S\)\\mathcal\{R\}\(S\)is the probability of selecting the subsetSSand, without loss of generality,ℛ⁡\(∅\)=0\\mathcal\{R\}\(\\emptyset\)=0\. Indeed, conditioning on the selected subset and using that a uniformly averaged subset of size\|S\|\|S\|assigns weight1/\|S\|1/\|S\|to each of its members,

pi=∑S⊆\[N\]1\|S\|1\{i∈S\}⏟ℙ⁡\(i​weighted∣St=S\)​ℛ⁡\(S\)⏟ℙ⁡\(St=S\),p\_\{i\}=\\sum\_\{S\\subseteq\[N\]\}\\underbrace\{\\tfrac\{1\}\{\|S\|\}\\,\\mathds\{1\}\\\{i\\in S\\\}\}\_\{\\mathbb\{P\}\(i\\text\{ weighted\}\\mid S^\{t\}=S\)\}\\,\\underbrace\{\\mathcal\{R\}\(S\)\}\_\{\\mathbb\{P\}\(S^\{t\}=S\)\},which defines a valid probability distribution over\[N\]\[N\]and accounts for the expected relative contribution of each client across all sampled subsets\. Expression \([8](https://arxiv.org/html/2609.21057#S2.E8)\) contains the fixed\-size formula \([7](https://arxiv.org/html/2609.21057#S2.E7)\) as the special caseℛ⁡\(\{S:\|S\|=M\}\)=1\\mathcal\{R\}\(\\\{S:\|S\|=M\\\}\)=1, and permits unrestricted subset selection\. The convergence guarantees of Section[IV](https://arxiv.org/html/2609.21057#S4)hold under \([8](https://arxiv.org/html/2609.21057#S2.E8)\) verbatim, since the participation model enters the analysis only through Lemma[4](https://arxiv.org/html/2609.21057#Thmlemma4), which is proved directly from \([8](https://arxiv.org/html/2609.21057#S2.E8)\)\. For ease of comparison with state\-of\-the\-art algorithms that assume fixed\-size participation, we focus henceforth on the case in which exactlyMMclients are selected per round\.

Inputθ1t,…,θNt\\theta\_\{1\}^\{t\},\\dots,\\theta\_\{N\}^\{t\}StationaryErasure ChannelOutputθi1t,…,θiMt\\theta\_\{i\_\{1\}\}^\{t\},\\dots,\\theta\_\{i\_\{M\}\}^\{t\}Survival probability∝pi=ℙ⁡\(i∈St\)M\\propto p\_\{i\}=\\tfrac\{\\mathbb\{P\}\(i\\in S^\{t\}\)\}\{M\}Fig\. 2:Canonical RAM structure: theNNinputsθ1,…,θN\\theta\_\{1\},\\dots,\\theta\_\{N\}enter a stationary\(N,M\)\(N,M\)\-ary erasure channel \(the RAM\), producingMMsurviving outputs \(a random subset of the inputs\), where the survival probability of eachθi\\theta\_\{i\}is proportional topip\_\{i\}\.
### II\-CDistributionally 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](https://arxiv.org/html/2609.21057#S2.E2)\) \(equivalently \([5](https://arxiv.org/html/2609.21057#S2.E5)\)\) under the induced weighting \([7](https://arxiv.org/html/2609.21057#S2.E7)\)\.

Accordingly, we adopt a*distributionally robust federated learning*\(DRFL\) formulation\. Instead of optimizing against the fixed distribution𝒬b\\mathcal\{Q\}^\{b\}, we minimize the worst\-case expected loss over a distributional neighborhood of𝒬b\\mathcal\{Q\}^\{b\}:

infθsup𝒬∈𝕌ϵ​\(𝒬b\)𝔼ξ∼𝒬​\[f⁡\(θ,ξ\)\],\\boxed\{\\inf\_\{\\theta\}\\sup\_\{\\mathcal\{Q\}\\in\\mathds\{U\}\_\{\\epsilon\}\(\\mathcal\{Q\}^\{b\}\)\}\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}\}\[f\(\\theta;\\xi\)\],\}\(9\)where the*ambiguity set*𝕌ϵ​\(𝒬b\)=\{𝒬:d⁡\(𝒬,𝒬b\)≤ϵ\}\\mathds\{U\}\_\{\\epsilon\}\(\\mathcal\{Q\}^\{b\}\)=\\\{\\mathcal\{Q\}:\\mathrm\{d\}\(\\mathcal\{Q\},\\mathcal\{Q\}^\{b\}\)\\leq\\epsilon\\\}is a distributional “ball” of radiusϵ\\epsiloncentered at𝒬b\\mathcal\{Q\}^\{b\}in a distributional distance or divergenced\\mathrm\{d\}, both of which are specified in Section[III](https://arxiv.org/html/2609.21057#S3)\. Whereas \([5](https://arxiv.org/html/2609.21057#S2.E5)\) weights individual data points by the availability\-induced distribution, Problem \([9](https://arxiv.org/html/2609.21057#S2.E9)\) optimizes uniformly over a set of nearby, and potentially more desirable, distributions\.

By construction, every𝒬∈𝕌ϵ​\(𝒬b\)\\mathcal\{Q\}\\in\\mathds\{U\}\_\{\\epsilon\}\(\\mathcal\{Q\}^\{b\}\)incurs an average loss no larger than the adversarial losssup𝒬∈𝕌ϵ​\(𝒬b\)𝔼ξ∼𝒬​\[f⁡\(θ,ξ\)\]\\sup\_\{\\mathcal\{Q\}\\in\\mathds\{U\}\_\{\\epsilon\}\(\\mathcal\{Q\}^\{b\}\)\}\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}\}\[f\(\\theta;\\xi\)\]; minimizing the latter therefore yields a parameter that performs well for all𝒬∈𝕌ϵ​\(𝒬b\)\\mathcal\{Q\}\\in\\mathds\{U\}\_\{\\epsilon\}\(\\mathcal\{Q\}^\{b\}\)simultaneously\. Asϵ\\epsilongrows, the set𝕌ϵ​\(𝒬b\)\\mathds\{U\}\_\{\\epsilon\}\(\\mathcal\{Q\}^\{b\}\)enlarges, admitting more pessimistic distributions and, at the same time, increasing the likelihood that it contains distributions more desirable than𝒬b\\mathcal\{Q\}^\{b\}; a performance trade\-off is thus implicit in the choice ofϵ\\epsilon\. In the limitϵ→∞\\epsilon\\rightarrow\\inftythe adversarial loss approachessupξf⁡\(θ,ξ\)\\sup\_\{\\xi\}f\(\\theta;\\xi\), whereasϵ=0\\epsilon=0recovers the nominal loss𝔼ξ∼𝒬b​\[f​\(θ,ξ\)\]\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}\[f\(\\theta;\\xi\)\]\. Problem \([9](https://arxiv.org/html/2609.21057#S2.E9)\) 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:𝒬b\\mathcal\{Q\}^\{b\}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\.

## IIIProposed Approach: FedeRage

Algorithm 2Federated Risk\-Averse Averaging \(FedeRage\)1:Initialize:

θi0=𝟎\\theta\_\{i\}^\{0\}=\\mathbf\{0\},

βi0=0\\beta\_\{i\}^\{0\}=0for all

i∈\[N\]i\\in\[N\];

T,H,ηθ,ηβ\>0T,H,\\eta\_\{\\theta\},\\eta\_\{\\beta\}\>0;

2:

α∈\(0,1\]\\alpha\\in\(0,1\],

γ∈\[0,1\]\\gamma\\in\[0,1\]; compact sets

𝒞,ℬ\\mathcal\{C\},\\mathcal\{B\}\.

3:for

t=1,…,T​Ht=1,\\ldots,THdo

4:if

tmodH=0t\\bmod H=0then⊳\\trianglerightGlobal communication

5:Clients transmit local parameters through RAM\.

6:Server samples active set

St∼ℛS^\{t\}\\sim\\mathcal\{R\}\.

7:Serveraggregates:

\[θ^tβ^t\]=1\|St\|​∑i∈St\[θit−1βit−1\]\\displaystyle\{\\begin\{bmatrix\}\\hat\{\\theta\}^\{t\}\\\\ \\hat\{\\beta\}^\{t\}\\end\{bmatrix\}=\\frac\{1\}\{\|S^\{t\}\|\}\\sum\_\{i\\in S^\{t\}\}\\begin\{bmatrix\}\\theta\_\{i\}^\{t\-1\}\\\\ \\beta\_\{i\}^\{t\-1\}\\end\{bmatrix\}\};

8:Serverbroadcaststo all clients\.

9:else⊳\\trianglerightLocal updates

10:Each client draws

ξit∼𝒬ib\\xi\_\{i\}^\{t\}\\sim\\mathcal\{Q\}\_\{i\}^\{b\};

11:Computes

wit=\(1−γ\)\+γα1\{f\(θit−1;ξit\)≥βit−1\}w\_\{i\}^\{t\}=\(1\-\\gamma\)\+\\dfrac\{\\gamma\}\{\\alpha\}\\,\\mathds\{1\}\\\{f\(\\theta\_\{i\}^\{t\-1\};\\xi\_\{i\}^\{t\}\)\\geq\\beta\_\{i\}^\{t\-1\}\\\};

12:Performs stochastic subgradient step:

13:

\[θitβit\]=Π𝒞×ℬ​\{\[θit−1βit−1\]−\[ηθ​wit​∇θfi​\(θit−1,ξit\)ηβ​\(1−wit\)\]\}\\begin\{bmatrix\}\\theta\_\{i\}^\{t\}\\\\ \\beta\_\{i\}^\{t\}\\end\{bmatrix\}=\\Pi\_\{\\mathcal\{C\}\\times\\mathcal\{B\}\}\\left\\\{\\begin\{bmatrix\}\\theta\_\{i\}^\{t\-1\}\\\\ \\beta\_\{i\}^\{t\-1\}\\end\{bmatrix\}\-\\begin\{bmatrix\}\\eta\_\{\\theta\}w\_\{i\}^\{t\}\\nabla\_\{\\theta\}f\_\{i\}\(\\theta\_\{i\}^\{t\-1\};\\xi\_\{i\}^\{t\}\)\\\\ \\eta\_\{\\beta\}\(1\-w\_\{i\}^\{t\}\)\\end\{bmatrix\}\\right\\\}\.

14:Return:

1T​∑τ=1Tθ^τ​H,1T​∑τ=1Tβ^τ​H\\frac\{1\}\{T\}\\sum\_\{\\tau=1\}^\{T\}\\hat\{\\theta\}^\{\\tau H\},\\frac\{1\}\{T\}\\sum\_\{\\tau=1\}^\{T\}\\hat\{\\beta\}^\{\\tau H\}\.

### III\-ADRO via the Conditional Value\-at\-Risk

Consider a random elementξ\\xiwith base distribution𝒬′\\mathcal\{Q\}^\{\\prime\}, and letξ↦f⁡\(ξ\)∈ℝ\\xi\\mapsto f\(\\xi\)\\in\\mathbb\{R\}be integrable with respect to𝒬′\\mathcal\{Q\}^\{\\prime\}, so thatf⁡\(ξ\)f\(\\xi\)may be regarded as a random cost\. The*Conditional Value\-at\-Risk*\(CVaR\) off⁡\(ξ\)f\(\\xi\)at levelα\\alphamay be defined as\[[40](https://arxiv.org/html/2609.21057#bib.bib3),[41](https://arxiv.org/html/2609.21057#bib.bib10)\]

CVaRξ∼𝒬′α⁡\[f⁡\(ξ\)\]≜infβ∈ℝ\[β\+1α​𝔼ξ∼𝒬′​\[\(f⁡\(ξ\)−β\)\+\]\],\\operatorname\{CVaR\}^\{\\alpha\}\_\{\\xi\\sim\\mathcal\{Q\}^\{\\prime\}\}\[f\(\\xi\)\]\\triangleq\\inf\_\{\\beta\\in\\mathbb\{R\}\}\\left\[\\beta\+\\frac\{1\}\{\\alpha\}\\,\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}^\{\\prime\}\}\\big\[\(f\(\\xi\)\-\\beta\)\_\{\+\}\\big\]\\right\],\(10\)where\(⋅\)\+=max⁡\{⋅,0\}\(\\cdot\)\_\{\+\}=\\max\\\{\\cdot,0\\\}andα∈\(0,1\]\\alpha\\in\(0,1\]is the*risk or confidence level*\. Equivalently, CVaR is the average of the loss over its worst \(upper\)α\\alpha\-tail reading

CVaRα⁡\[f⁡\(ξ\)\]=1α​∫1−α1VaRu​\[f⁡\(ξ\)\]​𝑑u,\\operatorname\{CVaR\}^\{\\alpha\}\[f\(\\xi\)\]=\\frac\{1\}\{\\alpha\}\\int\_\{1\-\\alpha\}^\{1\}\\mathrm\{VaR\}\_\{u\}\\big\[f\(\\xi\)\\big\]\\,\\mathrm\{d\}u,\(11\)whereVaRu\\mathrm\{VaR\}\_\{u\}denotes theuu\-quantile\. For a*continuous*distribution this reduces to a conditional\-tail\-expectation form

CVaRα⁡\[f⁡\(ξ\)\]=𝔼⁡\[f⁡\(ξ\)∣f⁡\(ξ\)≥βα∗\],ℙ⁡\(f⁡\(ξ\)≥βα∗\)=α,\\operatorname\{CVaR\}^\{\\alpha\}\[f\(\\xi\)\]=\\mathbb\{E\}\\big\[f\(\\xi\)\\mid f\(\\xi\)\\geq\\beta^\{\*\}\_\{\\alpha\}\\big\],\\quad\\mathbb\{P\}\\big\(f\(\\xi\)\\geq\\beta^\{\*\}\_\{\\alpha\}\\big\)=\\alpha,withβα∗\\beta^\{\*\}\_\{\\alpha\}an optimalβ\\betain \([10](https://arxiv.org/html/2609.21057#S3.E10)\)\. For general \(in particular, discrete\) distributions this identity may fail on account of an atom at the quantile, whereas \([11](https://arxiv.org/html/2609.21057#S3.E11)\) always holds\.

CVaR is a coherent risk measure—convex, monotone, translation equivariant, and positively homogeneous\[[41](https://arxiv.org/html/2609.21057#bib.bib10)\]—and admits the dual representation widely used in DRO

CVaRα⁡\[f⁡\(ξ\)\]=sup𝒬∈𝕌α𝔼𝒬​\[f⁡\(ξ\)\],\\operatorname\{CVaR\}^\{\\alpha\}\[f\(\\xi\)\]=\\sup\_\{\\mathcal\{Q\}\\in\\mathds\{U\}\_\{\\alpha\}\}\\mathbb\{E\}\_\{\\mathcal\{Q\}\}\[f\(\\xi\)\],\(12\)where the ambiguity set𝕌α\\mathds\{U\}\_\{\\alpha\}is

𝕌α\\displaystyle\\mathds\{U\}\_\{\\alpha\}=\{𝒬\|d​𝒬d​𝒬′∈\[0,1α\]​a\.e\.\-​𝒬′\},\\displaystyle=\\left\\\{\\mathcal\{Q\}\\ \\middle\|\\ \\frac\{\\mathrm\{d\}\\mathcal\{Q\}\}\{\\mathrm\{d\}\\mathcal\{Q\}^\{\\prime\}\}\\in\\left\[0,\\tfrac\{1\}\{\\alpha\}\\right\]\\text\{ a\.e\.\-\}\\mathcal\{Q\}^\{\\prime\}\\right\\\},and𝒬′\\mathcal\{Q\}^\{\\prime\}is the nominal \(reference\) distribution\. CVaR is thus a worst\-case expectation over a likelihood\-ratio \(Rényi\-type\) divergence ball of radiuslog⁡\(1/α\)\\log\(1/\\alpha\), and instantiates \([9](https://arxiv.org/html/2609.21057#S2.E9)\) withϵ=log⁡\(1/α\)\\epsilon=\\log\(1/\\alpha\)\. Varyingα\\alphainterpolates continuously between the expectation and the essential supremum:

CVaR1⁡\[f⁡\(ξ\)\]=𝔼⁡\[f⁡\(ξ\)\],limα→0\+CVaRα⁡\[f⁡\(ξ\)\]=ess​sup⁡f​\(ξ\)\.\\operatorname\{CVaR\}^\{1\}\[f\(\\xi\)\]=\\mathbb\{E\}\[f\(\\xi\)\],\\quad\\lim\_\{\\alpha\\rightarrow 0^\{\+\}\}\\operatorname\{CVaR\}^\{\\alpha\}\[f\(\\xi\)\]=\\esssup f\(\\xi\)\.Asα→0\+\\alpha\\to 0^\{\+\}, the likelihood\-ratio bound1/α1/\\alphadiverges and the ambiguity set expands toward the worst case, whereasα=1\\alpha=1forcesd​𝒬/d​𝒬′=1\\mathrm\{d\}\\mathcal\{Q\}/\\mathrm\{d\}\\mathcal\{Q\}^\{\\prime\}=1a\.e\. and recovers the nominal expectation\. This renders CVaR a natural risk\-sensitive functional for robust optimization\.

### III\-BDRFL via the CVaR:FedeRage

To instantiate \([9](https://arxiv.org/html/2609.21057#S2.E9)\) in a manner computable without access to𝒬b\\mathcal\{Q\}^\{b\}, we combine the CVaR under the RAM\-induced distribution with the risk\-neutral objective, replacing \([5](https://arxiv.org/html/2609.21057#S2.E5)\) by the mean–CVaR problem

infθ∈Θ\[\(1−γ\)​𝔼ξ∼𝒬b​\[f⁡\(θ,ξ\)\]\+γ​CVaRξ∼𝒬bα​\[f⁡\(θ,ξ\)\]\],\\boxed\{\\inf\_\{\\theta\\in\\Theta\}\\Big\[\(1\-\\gamma\)\\,\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}\[f\(\\theta;\\xi\)\]\+\\gamma\\,\\operatorname\{CVaR\}^\{\\alpha\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}\[f\(\\theta;\\xi\)\]\\Big\],\}\(13\)withα∈\(0,1\]\\alpha\\in\(0,1\]andγ∈\[0,1\]\\gamma\\in\[0,1\]tunable hyperparameters\. Using the variational form \([10](https://arxiv.org/html/2609.21057#S3.E10)\), Problem \([13](https://arxiv.org/html/2609.21057#S3.E13)\) is equivalent to the joint problem

infθ∈Θ,β∈ℝfα,γ​\(θ,β\),\\displaystyle\\inf\_\{\\theta\\in\\Theta,\\,\\beta\\in\\mathbb\{R\}\}\\ f\_\{\\alpha,\\gamma\}\(\\theta,\\beta\),where

fα,γ​\(θ,β\):=𝔼⁡\[\(1−γ\)​f​\(θ,ξ\)\+γ⁡\[β\+1α​\(f⁡\(θ,ξ\)−β\)\+\]\]\.\\displaystyle\\hskip\-6\.02249ptf\_\{\\alpha,\\gamma\}\(\\theta,\\beta\)\\hskip\-2\.00749pt:=\\hskip\-1\.00374pt\\mathbb\{E\}\\bigg\[\(1\\hskip\-1\.00374pt\-\\hskip\-1\.00374pt\\gamma\)f\(\\theta;\\xi\)\\hskip\-1\.00374pt\+\\hskip\-1\.00374pt\\gamma\\Big\[\\beta\\hskip\-1\.00374pt\+\\hskip\-1\.00374pt\\tfrac\{1\}\{\\alpha\}\\big\(f\(\\theta;\\xi\)\\hskip\-1\.00374pt\-\\hskip\-1\.00374pt\\beta\\big\)\_\{\+\}\\Big\]\\bigg\]\.\\hskip\-6\.02249pt\(14\)The expectation over𝒬b\\mathcal\{Q\}^\{b\}is internal to the definition offα,γf\_\{\\alpha,\\gamma\}; consequently,fα,γ​\(θ,β\)f\_\{\\alpha,\\gamma\}\(\\theta,\\beta\)denotes a deterministic quantity and no outer expectation is written anywhere below\.

Relative to agnostic FedAvg \(Algorithm[1](https://arxiv.org/html/2609.21057#alg1)\), the only modification required by \([14](https://arxiv.org/html/2609.21057#S3.E14)\) is the introduction of a single scalarβ∈ℝ\\beta\\in\\mathbb\{R\}, maintained locally alongside the model parameters, so that Algorithm[2](https://arxiv.org/html/2609.21057#alg2)retains the two\-phase structure of its risk\-neutral counterpart\. Both local updates are driven by the same scalar risk weightwit=\(1−γ\)\+γα𝟙\{fi≥β\}w\_\{i\}^\{t\}=\(1\-\\gamma\)\+\\frac\{\\gamma\}\{\\alpha\}\\mathds\{1\}\\\{f\_\{i\}\\geq\\beta\\\}of Line 8: the update direction inθ\\thetaiswit​∇θfiw\_\{i\}^\{t\}\\nabla\_\{\\theta\}f\_\{i\}, whereas the subgradient with respect toβ\\betais selected asγ\[1−1α𝟙\{fi≥β\}\]=1−wit\\gamma\\big\[1\-\\frac\{1\}\{\\alpha\}\\mathds\{1\}\\\{f\_\{i\}\\geq\\beta\\\}\\big\]=1\-w\_\{i\}^\{t\}, and in particular involves no derivative offif\_\{i\}inβ\\beta\. We projectβ\\betaonto a compact intervalℬ\\mathcal\{B\}, which is done without loss of generality, since the optimizerβ⋆\\beta^\{\\star\}of \([10](https://arxiv.org/html/2609.21057#S3.E10)\) is a finite value\-at\-risk lying in the range of the loss\. Each local step uses a single model mini\-batchξit∼𝒬ib\\xi\_\{i\}^\{t\}\\sim\\mathcal\{Q\}\_\{i\}^\{b\}, i\.e\.,algorithmicmini\-batch size one, which permits tight control of the upper tail of the loss\.

Comparison relative to SCAFFOLD\[[16](https://arxiv.org/html/2609.21057#bib.bib11)\]\.Several state\-of\-the\-art methods rely on gradient\-aggregation mechanisms that require communicating additional model\-sized vectors, widening the communication channel and enlarging the attack surface\. SCAFFOLD\[[16](https://arxiv.org/html/2609.21057#bib.bib11)\]is the canonical instance: each client maintains and transmits a control variate of the same dimensiond′d^\{\\prime\}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\[[15](https://arxiv.org/html/2609.21057#bib.bib26),[5](https://arxiv.org/html/2609.21057#bib.bib25)\], and one that is not protected by the averaging applied to the model update\.FedeRagetransmits instead a single scalarβi\\beta\_\{i\}, an estimate of a quantile of the client’s own loss distribution: it is smaller by a factord′d^\{\\prime\}, carries no directional information about the data, and has sensitivity bounded by the diameter ofℬ\\mathcal\{B\}, so that differential\-privacy noise calibrated to it costs a small fraction of the utility required to privatize ad′d^\{\\prime\}\-dimensional control variate\. Bothθi\\theta\_\{i\}andβi\\beta\_\{i\}reach the server only through plain averages, soFedeRageis compatible with secure aggregation without modification\. Robustness to heterogeneity is thus obtained through the*local objective*rather than through additional shared state\.

\(a\) Client availability probabilities \(light colors\), the uniform distribution \(dashed green line\), and the effective availability distribution induced by CVaR withγ=0\.25\\gamma=0\.25andα=0\.01\\alpha=0\.01\. The change in the effective distribution is implicit, arising from the dual representation of CVaR\.![Refer to caption](https://arxiv.org/html/2609.21057v1/NormalizedSelectionProbabilitiesvsOriginalDistribution.png)\(b\) Given100100data 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\.
### III\-CRisk\-Averse \(Primal\) Interpretation ofFedeRage

To interpret the objective \([14](https://arxiv.org/html/2609.21057#S3.E14)\), consider again the example of Fig\.[1](https://arxiv.org/html/2609.21057#S1.F1), with two infrequent clients \(44and55\) alongside three frequently participating ones \(11–33\)\. Agnostic FedAvg minimizes the participation\-weighted lossf⁡\(θ\)=∑i=1Npi​fi​\(θ\)f\(\\theta\)=\\sum\_\{i=1\}^\{N\}p\_\{i\}f\_\{i\}\(\\theta\)of \([2](https://arxiv.org/html/2609.21057#S2.E2)\), in which the induced weightsp4,p5p\_\{4\},p\_\{5\}are small, so that the local lossesf4​\(θ\)f\_\{4\}\(\\theta\)andf5​\(θ\)f\_\{5\}\(\\theta\)contribute little to the global objective even when they remain large\. Minimization offfis therefore driven by clients11–33, and the resulting model fits the dominant clients while neglecting the rare patterns held by the underrepresented ones\.

The mean–CVaR integrand of \([14](https://arxiv.org/html/2609.21057#S3.E14)\)

gα,γ​\(θ,β,ξ\)\\displaystyle g\_\{\\alpha,\\gamma\}\(\\theta,\\beta;\\xi\):=\(1−γ\)​f​\(θ,ξ\)\+γ⁡\(β\+1α​\(f⁡\(θ,ξ\)−β\)\+\),\\displaystyle:=\(1\-\\gamma\)\\,f\(\\theta;\\xi\)\+\\gamma\\Big\(\\beta\+\\tfrac\{1\}\{\\alpha\}\\big\(f\(\\theta;\\xi\)\-\\beta\\big\)\_\{\+\}\\Big\),whose expectation overξ∼𝒬b\\xi\\sim\\mathcal\{Q\}^\{b\}isfα,γ​\(θ,β\)f\_\{\\alpha,\\gamma\}\(\\theta,\\beta\), modifies the influence of each mini\-batchξ\\xiin a risk\-sensitive manner\. Recall that𝒬b=∑i=1Npi​𝒬ib\\mathcal\{Q\}^\{b\}=\\sum\_\{i=1\}^\{N\}p\_\{i\}\\,\\mathcal\{Q\}^\{b\}\_\{i\}, so that a mini\-batch of clientiicarries nominal masspi/Nibp\_\{i\}/N\_\{i\}^\{b\}under𝒬b\\mathcal\{Q\}^\{b\}; the thresholdβ\\betais accordingly a quantile \(estimate\) of the loss under the*global*mixture, maintained locally asβi\\beta\_\{i\}between communication rounds and averaged at the server \(Algorithm[2](https://arxiv.org/html/2609.21057#alg2)\)\. Whenever the mini\-batch lossf⁡\(θ,ξ\)f\(\\theta;\\xi\)exceedsβ\\beta, which at optimality is an\(1−α\)\(1\-\\alpha\)\-quantile under𝒬b\\mathcal\{Q\}^\{b\}, the corresponding subgradient is upweighted as

∇θgα,γ\(θ,β;ξ\)=\(1−γ\+γα1\{f\(θ;ξ\)≥β\}\)⏟=:w⁡\(θ,β,ξ\)∇θf\(θ;ξ\),\\displaystyle\\nabla\_\{\\theta\}\\,g\_\{\\alpha,\\gamma\}\(\\theta,\\beta;\\xi\)=\\underbrace\{\\big\(1\-\\gamma\+\\tfrac\{\\gamma\}\{\\alpha\}\\,\\mathds\{1\}\\\{f\(\\theta;\\xi\)\\geq\\beta\\\}\\big\)\}\_\{=:\\,w\(\\theta,\\beta;\\xi\)\}\\,\\nabla\_\{\\theta\}f\(\\theta;\\xi\),where∇θf​\(θ,ξ\)\\nabla\_\{\\theta\}f\(\\theta;\\xi\)denotes the measurable subgradient selection fixed in Section[IV](https://arxiv.org/html/2609.21057#S4)andw⁡\(θ,β,ξ\)w\(\\theta,\\beta;\\xi\)is precisely the scalar risk weightwitw\_\{i\}^\{t\}of Line 8 of Algorithm[2](https://arxiv.org/html/2609.21057#alg2), evaluated at\(θit−1,βit−1,ξit\)\(\\theta\_\{i\}^\{t\-1\},\\beta\_\{i\}^\{t\-1\};\\xi\_\{i\}^\{t\}\)\.

The expressionω⁡\(θ,β,ξ\)\\omega\(\\theta,\\beta;\\xi\)constitutes a risk\-weighted prioritization mechanism\. If the mini\-batches of clientiiconsistently incur large losses—whether because of infrequent RAM selection \(smallpip\_\{i\}\) or because of misalignment with the global model \(client drift\)—they are more likely to exceed the thresholdβ\\beta, and their subgradients are scaled by a factor of up toκ⁡\(α,γ\)=\(1−γ\)\+γ/α\\kappa\(\\alpha,\\gamma\)=\(1\-\\gamma\)\+\\gamma/\\alpha, 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\}\\\{p\_\{i\}\\\}\.

The mean–CVaR objective is furthermore a smooth surrogate for the worst\-case loss\. In the limitγ=1\\gamma=1,α→0\+\\alpha\\to 0^\{\+\}, the CVaR term tends toess​supξ∼𝒬b⁡f​\(θ,ξ\)\\esssup\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}f\(\\theta;\\xi\), so that minimizing \([14](https://arxiv.org/html/2609.21057#S3.E14)\) approaches minimization of the largest mini\-batch loss in the support of𝒬b\\mathcal\{Q\}^\{b\}, up to smoothing; since that support is the union of the clients’ mini\-batch collections\{Dib\}i∈\[N\]\\\{D\_\{i\}^\{b\}\\\}\_\{i\\in\[N\]\}, this steers the global model toward regions in which the largest client lossesmaxi∈\[N\]⁡fi​\(θ\)\\max\_\{i\\in\[N\]\}f\_\{i\}\(\\theta\)are reduced, thereby promoting an equity across clients that the risk\-neutral formulation \([2](https://arxiv.org/html/2609.21057#S2.E2)\) does not enforce\.

### III\-DDistributionally Robust \(Dual\) Interpretation ofFedeRage

We now use the dual representation \([12](https://arxiv.org/html/2609.21057#S3.E12)\) to interpret the CVaR term in \([14](https://arxiv.org/html/2609.21057#S3.E14)\) in a complementary distributionally robust manner\. Recall the expected loss over RAM\-distributed mini\-batches

𝔼ξ∼𝒬b​\[f​\(θ,ξ\)\]\\displaystyle\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}\[f\(\\theta;\\xi\)\]=∑i=1Npi​\(1Nib​∑j=1Nibfi​\(θ,ξij\)\)=∑i=1N∑j=1Nibqij​fi​\(θ,ξij\),\\displaystyle=\\sum\_\{i=1\}^\{N\}p\_\{i\}\\Big\(\\tfrac\{1\}\{N\_\{i\}^\{b\}\}\\sum\_\{j=1\}^\{N\_\{i\}^\{b\}\}f\_\{i\}\(\\theta;\\xi\_\{i\}^\{j\}\)\\Big\)=\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\_\{i\}^\{b\}\}q\_\{i\}^\{j\}\\,f\_\{i\}\(\\theta;\\xi\_\{i\}^\{j\}\),
where the weightsqij=pi/Nibq\_\{i\}^\{j\}=p\_\{i\}/N\_\{i\}^\{b\}constitute𝒬b\\mathcal\{Q\}^\{b\}\. By the dual form of CVaR, it follows that

CVaRξ∼𝒬bα⁡\[f⁡\(θ,ξ\)\]\\displaystyle\\operatorname\{CVaR\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}^\{\\alpha\}\[f\(\\theta;\\xi\)\]=sup𝒬^∈𝕌α​\(𝒬b\)𝔼ξ∼𝒬^​\[f⁡\(θ,ξ\)\]\\displaystyle=\\sup\_\{\\hat\{\\mathcal\{Q\}\}\\in\\mathds\{U\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)\}\\mathbb\{E\}\_\{\\xi\\sim\\hat\{\\mathcal\{Q\}\}\}\[f\(\\theta;\\xi\)\]=sup𝒬^∈𝕌α​\(𝒬b\)∑i=1N∑j=1Nibq^ij​fi​\(θ,ξij\),\\displaystyle=\\sup\_\{\\hat\{\\mathcal\{Q\}\}\\in\\mathds\{U\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\_\{i\}^\{b\}\}\\hat\{q\}\_\{i\}^\{j\}\\,f\_\{i\}\(\\theta;\\xi\_\{i\}^\{j\}\),where the mini\-batch ambiguity set is

𝕌α\(𝒬b\)=\{𝒬^\|q^ijpi≤1Nib​α,i∈\[N\],j∈\[Nib\]\}\.\\displaystyle\\mathds\{U\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)=\\Big\\\{\\hat\{\\mathcal\{Q\}\}\\,\\Big\|\\,\\tfrac\{\\hat\{q\}\_\{i\}^\{j\}\}\{p\_\{i\}\}\\leq\\tfrac\{1\}\{N\_\{i\}^\{b\}\\alpha\},\\ i\\in\[N\],\\,j\\in\[N\_\{i\}^\{b\}\]\\Big\\\}\.
Expanding the loss over individual data points, we have

𝔼ξ∼𝒬^​\[f​\(θ,ξ\)\]\\displaystyle\\mathbb\{E\}\_\{\\xi\\sim\\hat\{\\mathcal\{Q\}\}\}\\big\[f\(\\theta;\\xi\)\\big\]=∑i=1N∑j=1Nibq^ij​∑\(X,Y\)∈ξij1b​ℓ​\(m⁡\(X,θ\),Y\)\\displaystyle=\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\_\{i\}^\{b\}\}\\hat\{q\}\_\{i\}^\{j\}\\sum\_\{\(X,Y\)\\in\\xi\_\{i\}^\{j\}\}\\tfrac\{1\}\{b\}\\,\\ell\(m\(X,\\theta\),Y\)=∑i=1N∑k=1ni\[1b∑j=1Nibq^ij1\{\(Xik,Yik\)∈ξij\}\]⏟≜q~ik​ℓ​\(m⁡\(Xik,θ\),Yik\)\\displaystyle=\\sum\_\{i=1\}^\{N\}\\sum\_\{k=1\}^\{n\_\{i\}\}\\underbrace\{\\Bigg\[\\tfrac\{1\}\{b\}\\sum\_\{j=1\}^\{N\_\{i\}^\{b\}\}\\hat\{q\}\_\{i\}^\{j\}\\,\\mathds\{1\}\\\{\(X\_\{i\}^\{k\},Y\_\{i\}^\{k\}\)\\in\\xi\_\{i\}^\{j\}\\\}\\Bigg\]\}\_\{\\triangleq\\,\\tilde\{q\}\_\{i\}^\{k\}\}\\ell\(m\(X\_\{i\}^\{k\},\\theta\),Y\_\{i\}^\{k\}\)=∑i=1N∑k=1niq~ik​ℓ​\(m⁡\(Xik,θ\),Yik\),\\displaystyle=\\sum\_\{i=1\}^\{N\}\\sum\_\{k=1\}^\{n\_\{i\}\}\\tilde\{q\}\_\{i\}^\{k\}\\,\\ell\(m\(X\_\{i\}^\{k\},\\theta\),Y\_\{i\}^\{k\}\),
where the*inherited*weights\{q~ik\}\\\{\\tilde\{q\}\_\{i\}^\{k\}\\\}induce a reweighted importance distribution𝒬~\\tilde\{\\mathcal\{Q\}\}over individual data points with CVaR

CVaRξ∼𝒬bα⁡\(f⁡\(θ,ξ\)\)\\displaystyle\\operatorname\{CVaR\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}^\{\\alpha\}\\big\(f\(\\theta;\\xi\)\\big\)=sup𝒬~∈𝕌~α​\(𝒬b\)𝔼\(I,\(X,Y\)\)∼𝒬~​\[ℓ⁡\(m⁡\(X,θ\),Y\)\],\\displaystyle\\qquad=\\sup\_\{\\tilde\{\\mathcal\{Q\}\}\\in\\tilde\{\\mathds\{U\}\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)\}\\ \\mathbb\{E\}\_\{\(I,\(X,Y\)\)\\sim\\tilde\{\\mathcal\{Q\}\}\}\\big\[\\ell\(m\(X,\\theta\),Y\)\\big\],
with the inheritance uncertainty set

𝕌~α\(𝒬b\)=\{𝒬~\|\\displaystyle\\tilde\{\\mathds\{U\}\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)=\\Big\\\{\\tilde\{\\mathcal\{Q\}\}\\ \\Big\|\\q~ik=1b∑j=1Nibq^ij1\{\(Xik,Yik\)∈ξij\},\\displaystyle\\tilde\{q\}\_\{i\}^\{k\}=\\tfrac\{1\}\{b\}\\textstyle\\sum\_\{j=1\}^\{N\_\{i\}^\{b\}\}\\hat\{q\}\_\{i\}^\{j\}\\,\\mathds\{1\}\\\{\(X\_\{i\}^\{k\},Y\_\{i\}^\{k\}\)\\in\\xi\_\{i\}^\{j\}\\\},q~ikpi≤1ni​α,i∈\[N\],k∈\[ni\],\\displaystyle\\tfrac\{\\tilde\{q\}\_\{i\}^\{k\}\}\{p\_\{i\}\}\\leq\\tfrac\{1\}\{n\_\{i\}\\alpha\},\\ i\\in\[N\],\\,k\\in\[n\_\{i\}\],\{q^ij\}=𝒬^∈𝕌α\(𝒬b\)\}\.\\displaystyle\\\{\\hat\{q\}\_\{i\}^\{j\}\\\}=\\hat\{\\mathcal\{Q\}\}\\in\\mathds\{U\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)\\Big\\\}\.In words, the distributional robustness that CVaR confers on the mini\-batch distribution𝒬^\\hat\{\\mathcal\{Q\}\}is*inherited*by the induced point\-level distribution𝒬~\\tilde\{\\mathcal\{Q\}\}: maximizing over the mini\-batch ambiguity set𝕌α​\(𝒬b\)\\mathds\{U\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\)is equivalent to maximizing over the structured point\-level set𝕌~α​\(𝒬b\)\\tilde\{\\mathds\{U\}\}\_\{\\alpha\}\(\\mathcal\{Q\}^\{b\}\), which couples the CVaR reweighting with the RAM\-induced participation weightspip\_\{i\}\.FedeRageis therefore distributionally robust at the level of individual data points, hedging against the client drift produced jointly by data heterogeneity and skewed availability\. This reweighting is realized*implicitly*, through the local objective, and never appears as an explicit aggregation weight at the server, which is what allows the algorithm to operate without any knowledge of the participation law\.

In the special caseb=1b=1, in which mini\-batches are single points, the two levels coincide:

CVaRξ∼𝒬bα⁡\(f⁡\(θ,ξ\)\)=CVaR\(I,\(X,Y\)\)∼𝒬~α⁡\(ℓ⁡\(m⁡\(X,θ\),Y\)\),\\displaystyle\\operatorname\{CVaR\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}^\{\\alpha\}\\big\(f\(\\theta;\\xi\)\\big\)=\\operatorname\{CVaR\}\_\{\(I,\(X,Y\)\)\\sim\\tilde\{\\mathcal\{Q\}\}\}^\{\\alpha\}\\big\(\\ell\(m\(X,\\theta\),Y\)\\big\),whereas forb\>1b\>1the right\-hand side is a relaxation induced by overlapping mini\-batch structures \(Fig\.[3](https://arxiv.org/html/2609.21057#S3.F3)\)\. Incorporating CVaR thus reweights samples according to their contribution to the upper quantile of the loss distribution\. At each communication round, harder examples—data points or clients with higher loss—are prioritized, so that the algorithm attends to poorly performing or underrepresented clients, improving robustness to data heterogeneity and worst\-case performance\.

## IVConvergence for Convex Losses

This section develops the convergence analysis in two stages, with every proof given in place\. We first treat the risk\-neutral caseγ=0\\gamma=0, i\.e\., agnostic FedAvg applied to the induced objective \([5](https://arxiv.org/html/2609.21057#S2.E5)\) \(Sections[IV](https://arxiv.org/html/2609.21057#S4)\-A through[IV](https://arxiv.org/html/2609.21057#S4)\-C\), and then extend the argument to the mean–CVaR objectivefα,γf\_\{\\alpha,\\gamma\}forγ\>0\\gamma\>0andα∈\(0,1\]\\alpha\\in\(0,1\]\(Section[IV](https://arxiv.org/html/2609.21057#S4)\-D\)\. The separation is deliberate: the risk\-neutral analysis isolates the effect of unknown, variable\-size participation, and the risk\-averse extension is then shown to cost exactly one explicit constant\.

Two sources of randomness enter\. First, for each clienti∈\[N\]i\\in\[N\], the random elementξi\\xi\_\{i\}denotes a mini\-batch of sizebbdrawn uniformly without replacement from clientii’s dataset; at timettwe writeξit\\xi\_\{i\}^\{t\}, and mini\-batches are drawn independently across clients and rounds\. Second,St⊆\[N\]S^\{t\}\\subseteq\[N\]denotes the subset of clients selected at roundttunder the RAM, i\.i\.d\. across rounds and independent of\{ξit\}\\\{\\xi\_\{i\}^\{t\}\\\}\. Both sources are carried through every round, with the understanding that the sampledξit\\xi\_\{i\}^\{t\}are unused during global rounds and the outcomeStS^\{t\}is unused during local rounds\. We define the natural filtration\{ℱt\}t\\\{\\mathcal\{F\}\_\{t\}\\\}\_\{t\},

ℱt:=σ\(θis,ξis,Ss:s≤t,i∈\[N\]\),\\mathcal\{F\}\_\{t\}:=\\sigma\\big\(\\theta\_\{i\}^\{s\},\\xi\_\{i\}^\{s\},S^\{s\}:s\\leq t,\\,i\\in\[N\]\\big\),which captures the model states, mini\-batch draws, and participation history up to roundtt; the iteratesθit\\theta\_\{i\}^\{t\}are adapted to\{ℱt\}\\\{\\mathcal\{F\}\_\{t\}\\\}and depend onℱt−1\\mathcal\{F\}\_\{t\-1\}only throughθit−1\\theta\_\{i\}^\{t\-1\}and the fresh randomnessξit\\xi\_\{i\}^\{t\}orStS^\{t\}\.

Since the losses are convex and possibly nonsmooth,∇fi​\(θ\)\\nabla f\_\{i\}\(\\theta\)and∇f​\(θ,ξ\)\\nabla f\(\\theta;\\xi\)denote throughout a fixed measurable selection from the subdifferentials∂fi​\(θ\)\\partial f\_\{i\}\(\\theta\)and∂θf⁡\(θ,ξ\)\\partial\_\{\\theta\}f\(\\theta;\\xi\), chosen so that the unbiasedness required in Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2)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” lossesf⁡\(⋅,ξ\)f\(\\cdot;\\xi\)are convex onΘ\\Thetafor every mini\-batchξ\\xi\.

###### Assumption 2\(Unbiasedness and Bounded Second Moment\)\.

For eachi∈\[N\]i\\in\[N\]and everyθ∈Θ\\theta\\in\\Theta, the stochastic subgradient is conditionally unbiased,𝔼ξi​\[∇f​\(θ,ξi\)\]=∇fi​\(θ\)\\mathbb\{E\}\_\{\\xi\_\{i\}\}\[\\nabla f\(\\theta;\\xi\_\{i\}\)\]=\\nabla f\_\{i\}\(\\theta\), and

supθ∈Θ𝔼ξi​\[‖∇f​\(θ,ξi\)‖2\]≤G2\.\\sup\_\{\\theta\\in\\Theta\}\\mathbb\{E\}\_\{\\xi\_\{i\}\}\\big\[\\\|\\nabla f\(\\theta;\\xi\_\{i\}\)\\\|^\{2\}\\big\]\\leq G^\{2\}\.

###### Lemma 1\(Bounded Local Gradient Variance\)\.

Under Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2), for everyi∈\[N\]i\\in\[N\],

supθ∈Θ𝔼ξi​\[‖∇f​\(θ,ξi\)−∇fi​\(θ\)‖2\]≤σi2:=G2−infθ∈Θ‖∇fi​\(θ\)‖2,\\sup\_\{\\theta\\in\\Theta\}\\mathbb\{E\}\_\{\\xi\_\{i\}\}\\big\[\\\|\\nabla f\(\\theta;\\xi\_\{i\}\)\-\\nabla f\_\{i\}\(\\theta\)\\\|^\{2\}\\big\]\\leq\\sigma\_\{i\}^\{2\}:=G^\{2\}\-\\inf\_\{\\theta\\in\\Theta\}\\\|\\nabla f\_\{i\}\(\\theta\)\\\|^\{2\},and therefore the aggregate variance boundσ2:=∑i=1Npi​σi2\\sigma^\{2\}:=\\sum\_\{i=1\}^\{N\}p\_\{i\}\\sigma\_\{i\}^\{2\}satisfiesσ2≤G2\\sigma^\{2\}\\leq G^\{2\}\.

###### Proof\.

Fixθ∈Θ\\theta\\in\\Thetaand setX:=∇f​\(θ,ξi\)X:=\\nabla f\(\\theta;\\xi\_\{i\}\), so that𝔼​X=∇fi​\(θ\)\\mathbb\{E\}X=\\nabla f\_\{i\}\(\\theta\)by Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2)\. The bias–variance identity yields

𝔼​‖X−𝔼​X‖2=𝔼​‖X‖2−‖𝔼​X‖2≤G2−‖∇fi​\(θ\)‖2\.\\mathbb\{E\}\\\|X\-\\mathbb\{E\}X\\\|^\{2\}=\\mathbb\{E\}\\\|X\\\|^\{2\}\-\\\|\\mathbb\{E\}X\\\|^\{2\}\\leq G^\{2\}\-\\\|\\nabla f\_\{i\}\(\\theta\)\\\|^\{2\}\.Taking the supremum overθ∈Θ\\theta\\in\\Thetagives the first claim, and the bound onσ2\\sigma^\{2\}follows because\{pi\}i∈\[N\]\\\{p\_\{i\}\\\}\_\{i\\in\[N\]\}is a probability distribution and eachσi2≤G2\\sigma\_\{i\}^\{2\}\\leq G^\{2\}\. ∎

We retain the symbolσ2\\sigma^\{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\\sigma^\{2\}replaced byG2G^\{2\}\.

Throughout,𝒞⊆Θ\\mathcal\{C\}\\subseteq\\Thetais convex and compact with Euclidean projectionΠ𝒞​\(⋅\)\\Pi\_\{\\mathcal\{C\}\}\(\\cdot\), andθ∗\\theta^\{\*\}denotes a minimizer offfover𝒞\\mathcal\{C\}, which exists by continuity offfand compactness of𝒞\\mathcal\{C\}\. Since eachfif\_\{i\}is convex and finite on a neighborhood of the compact set𝒞\\mathcal\{C\}, it is Lipschitz on𝒞\\mathcal\{C\}; we letℓ\\elldenote a common Lipschitz constant\.

### IV\-APreliminary Lemmata

We first analyze a single projected stochastic subgradient step at the client side\. Throughout,git:=∇f​\(θit−1,ξit\)g\_\{i\}^\{t\}:=\\nabla f\(\\theta\_\{i\}^\{t\-1\};\\xi\_\{i\}^\{t\}\), so that𝔼⁡\[git∣ℱt−1\]=∇fi​\(θit−1\)\\mathbb\{E\}\[g\_\{i\}^\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=\\nabla f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\)by Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2); this is the update direction of Line 9 of Algorithm[1](https://arxiv.org/html/2609.21057#alg1)\. Conditional expectations are unrolled by the tower property\.

###### Lemma 2\(One\-Step Progress\)\.

Letθit=Π𝒞​\(θit−1−η​git\)\\theta\_\{i\}^\{t\}=\\Pi\_\{\\mathcal\{C\}\}\(\\theta\_\{i\}^\{t\-1\}\-\\eta g\_\{i\}^\{t\}\)fori∈\[N\]i\\in\[N\]andη\>0\\eta\>0\. Under Assumptions[1](https://arxiv.org/html/2609.21057#Thmassumption1)and[2](https://arxiv.org/html/2609.21057#Thmassumption2)and Lemma[1](https://arxiv.org/html/2609.21057#Thmlemma1), at every local round,

𝔼⁡\[‖θit−θ∗‖2∣ℱt−1\]\\displaystyle\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]≤‖θit−1−θ∗‖2\\displaystyle\\leq\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}−2​η​\(fi​\(θit−1\)−fi​\(θ∗\)\)\\displaystyle\\quad\-2\\eta\\big\(f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\)\-f\_\{i\}\(\\theta^\{\*\}\)\\big\)\+2​η2​\(σ2\+G2\)\.\\displaystyle\\quad\+2\\eta^\{2\}\(\\sigma^\{2\}\+G^\{2\}\)\.\(15\)

###### Proof\.

Sinceθ∗∈𝒞\\theta^\{\*\}\\in\\mathcal\{C\}and the projection onto a closed convex set is non\-expansive,

‖θit−θ∗‖2\\displaystyle\\\|\\theta\_\{i\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}=‖Π𝒞​\(θit−1−η​git\)−Π𝒞​\(θ∗\)‖2\\displaystyle=\\\|\\Pi\_\{\\mathcal\{C\}\}\(\\theta\_\{i\}^\{t\-1\}\-\\eta g\_\{i\}^\{t\}\)\-\\Pi\_\{\\mathcal\{C\}\}\(\\theta^\{\*\}\)\\\|^\{2\}≤‖θit−1−η​git−θ∗‖2\\displaystyle\\leq\\\|\\theta\_\{i\}^\{t\-1\}\-\\eta g\_\{i\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}=‖θit−1−θ∗‖2−2​η​⟨git,θit−1−θ∗⟩\+η2​‖git‖2\.\\displaystyle=\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}\-2\\eta\\langle g\_\{i\}^\{t\},\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\rangle\+\\eta^\{2\}\\\|g\_\{i\}^\{t\}\\\|^\{2\}\.Take𝔼\[⋅∣ℱt−1\]\\mathbb\{E\}\[\\,\\cdot\\mid\\mathcal\{F\}\_\{t\-1\}\]on both sides\. Writinggit=∇fi​\(θit−1\)\+ζitg\_\{i\}^\{t\}=\\nabla f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\)\+\\zeta\_\{i\}^\{t\}with𝔼⁡\[ζit∣ℱt−1\]=0\\mathbb\{E\}\[\\zeta\_\{i\}^\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=0, and noting thatθit−1\\theta\_\{i\}^\{t\-1\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable,

𝔼⁡\[⟨git,θit−1−θ∗⟩∣ℱt−1\]=⟨∇fi​\(θit−1\),θit−1−θ∗⟩,\\mathbb\{E\}\\big\[\\langle g\_\{i\}^\{t\},\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\rangle\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]=\\langle\\nabla f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\),\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\rangle,while‖a\+b‖2≤2​‖a‖2\+2​‖b‖2\\\|a\+b\\\|^\{2\}\\leq 2\\\|a\\\|^\{2\}\+2\\\|b\\\|^\{2\}together with Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2)and Lemma[1](https://arxiv.org/html/2609.21057#Thmlemma1)gives

𝔼⁡\[‖git‖2∣ℱt−1\]≤2​‖∇fi​\(θit−1\)‖2\+2​σ2≤2​G2\+2​σ2\.\\mathbb\{E\}\\big\[\\\|g\_\{i\}^\{t\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]\\leq 2\\\|\\nabla f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\)\\\|^\{2\}\+2\\,\\sigma^\{2\}\\leq 2G^\{2\}\+2\\sigma^\{2\}\.Combining the two displays,

𝔼⁡\[‖θit−θ∗‖2∣ℱt−1\]≤‖θit−1−θ∗‖2−2​η​⟨∇fi​\(θit−1\),θit−1−θ∗⟩\+2​η2​\(G2\+σ2\)\.\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]\\leq\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}\\\\ \-2\\eta\\langle\\nabla f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\),\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\rangle\+2\\eta^\{2\}\(G^\{2\}\+\\sigma^\{2\}\)\.\(16\)The subgradient inequality for the convex functionfif\_\{i\}\(Assumption[1](https://arxiv.org/html/2609.21057#Thmassumption1)\) givesfi​\(θit−1\)−fi​\(θ∗\)≤⟨∇fi​\(θit−1\),θit−1−θ∗⟩f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\)\-f\_\{i\}\(\\theta^\{\*\}\)\\leq\\langle\\nabla f\_\{i\}\(\\theta\_\{i\}^\{t\-1\}\),\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\rangle, and substituting it yields \([15](https://arxiv.org/html/2609.21057#S4.E15)\)\. ∎

We next bound the divergence between two clients’ parameter vectors within a communication round\.

###### Lemma 3\(Local Parameter Divergence\)\.

Leti,j∈\[N\]i,j\\in\[N\]and letτi,τj∈\[S​H,S​H\+H\]\\tau\_\{i\},\\tau\_\{j\}\\in\[SH,SH\+H\]be local steps between consecutive communication roundsSSandS\+1S\+1\. Under Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2),

𝔼⁡\[‖θiτi−θjτj‖\|ℱS​H\]≤4​η​G​H\.\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{\\tau\_\{i\}\}\-\\theta\_\{j\}^\{\\tau\_\{j\}\}\\\|\\,\\big\|\\,\\mathcal\{F\}\_\{SH\}\\big\]\\leq 4\\eta GH\.

###### Proof\.

Assume without loss of generality thatτi≥τj\\tau\_\{i\}\\geq\\tau\_\{j\}, and setΔt:=θit−θjt\\Delta\_\{t\}:=\\theta\_\{i\}^\{t\}\-\\theta\_\{j\}^\{t\}\. At each local step, non\-expansiveness of the projection gives

‖Δt‖\\displaystyle\\\|\\Delta\_\{t\}\\\|=‖Π𝒞​\(θit−1−η​git\)−Π𝒞​\(θjt−1−η​gjt\)‖\\displaystyle=\\big\\\|\\Pi\_\{\\mathcal\{C\}\}\(\\theta\_\{i\}^\{t\-1\}\\\!\-\\eta g\_\{i\}^\{t\}\)\-\\Pi\_\{\\mathcal\{C\}\}\(\\theta\_\{j\}^\{t\-1\}\\\!\-\\eta g\_\{j\}^\{t\}\)\\big\\\|≤‖Δt−1−η⁡\(git−gjt\)‖,\\displaystyle\\leq\\big\\\|\\Delta\_\{t\-1\}\-\\eta\(g\_\{i\}^\{t\}\-g\_\{j\}^\{t\}\)\\big\\\|,so that‖Δt‖2≤‖Δt−1‖2−2​η​⟨Δt−1,git−gjt⟩\+η2​‖git−gjt‖2\\\|\\Delta\_\{t\}\\\|^\{2\}\\leq\\\|\\Delta\_\{t\-1\}\\\|^\{2\}\-2\\eta\\langle\\Delta\_\{t\-1\},g\_\{i\}^\{t\}\-g\_\{j\}^\{t\}\\rangle\+\\eta^\{2\}\\\|g\_\{i\}^\{t\}\-g\_\{j\}^\{t\}\\\|^\{2\}\. By Cauchy–Schwarz and Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2),

−2​η​⟨Δt−1,git−gjt⟩≤4​η​G​‖Δt−1‖,𝔼​‖git−gjt‖2≤4​G2,\-2\\eta\\langle\\Delta\_\{t\-1\},g\_\{i\}^\{t\}\-g\_\{j\}^\{t\}\\rangle\\leq 4\\eta G\\\|\\Delta\_\{t\-1\}\\\|,\\quad\\mathbb\{E\}\\\|g\_\{i\}^\{t\}\-g\_\{j\}^\{t\}\\\|^\{2\}\\leq 4G^\{2\},whence𝔼⁡\[‖Δt‖2∣ℱt−1\]≤\(‖Δt−1‖\+2​η​G\)2\\mathbb\{E\}\\big\[\\\|\\Delta\_\{t\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]\\leq\\big\(\\\|\\Delta\_\{t\-1\}\\\|\+2\\eta G\\big\)^\{2\}, and, by Jensen’s inequality,𝔼⁡\[‖Δt‖∣ℱt−1\]≤\|Δt−1\|\+2​η​G\\mathbb\{E\}\[\\\|\\Delta\_\{t\}\\\|\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq\\\|\\Delta\_\{t\-1\}\\\|\+2\\eta G\. SinceθiS​H=θjS​H=θ^S​H\\theta\_\{i\}^\{SH\}=\\theta\_\{j\}^\{SH\}=\\hat\{\\theta\}^\{SH\}impliesΔS​H=0\\Delta\_\{SH\}=0, iterating this recursion and using the tower property yields𝔼⁡\[‖ΔS​H\+h‖∣ℱS​H\]≤2​η​G​h\\mathbb\{E\}\[\\\|\\Delta\_\{SH\+h\}\\\|\\mid\\mathcal\{F\}\_\{SH\}\]\\leq 2\\eta Ghforh∈\{0,…,H\}h\\in\\\{0,\\dots,H\\\}; in particular𝔼⁡\[‖θiτj−θjτj‖∣ℱS​H\]≤2​η​G​\(τj−S​H\)\\mathbb\{E\}\[\\\|\\theta\_\{i\}^\{\\tau\_\{j\}\}\-\\theta\_\{j\}^\{\\tau\_\{j\}\}\\\|\\mid\\mathcal\{F\}\_\{SH\}\]\\leq 2\\eta G\(\\tau\_\{j\}\-SH\)\. Finally, by the triangle inequality and‖θiτi−θiτj‖≤∑s=τj\+1τiη​‖gis‖\\\|\\theta\_\{i\}^\{\\tau\_\{i\}\}\-\\theta\_\{i\}^\{\\tau\_\{j\}\}\\\|\\leq\\sum\_\{s=\\tau\_\{j\}\+1\}^\{\\tau\_\{i\}\}\\eta\\\|g\_\{i\}^\{s\}\\\|,

𝔼⁡\[‖θiτi−θjτj‖\|ℱS​H\]\\displaystyle\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{\\tau\_\{i\}\}\-\\theta\_\{j\}^\{\\tau\_\{j\}\}\\\|\\,\\big\|\\,\\mathcal\{F\}\_\{SH\}\\big\]≤𝔼⁡\[‖θiτj−θjτj‖\|ℱS​H\]\\displaystyle\\leq\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{\\tau\_\{j\}\}\-\\theta\_\{j\}^\{\\tau\_\{j\}\}\\\|\\,\\big\|\\,\\mathcal\{F\}\_\{SH\}\\big\]\+𝔼⁡\[‖θiτi−θiτj‖\|ℱS​H\]\\displaystyle\\quad\+\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{\\tau\_\{i\}\}\-\\theta\_\{i\}^\{\\tau\_\{j\}\}\\\|\\,\\big\|\\,\\mathcal\{F\}\_\{SH\}\\big\]≤2​η​G​\(τj−S​H\)\+η​G​\(τi−τj\)\\displaystyle\\leq 2\\eta G\(\\tau\_\{j\}\-SH\)\+\\eta G\(\\tau\_\{i\}\-\\tau\_\{j\}\)≤3​η​G​H\.\\displaystyle\\leq 3\\eta GH\.Symmetrizing ini↔ji\\leftrightarrow jand bounding by the worst case gives the stated constant4​η​G​H4\\eta GH\. ∎

TABLE I:Test accuracy \(%\)±\\pmstandard deviation for FedAvg,FedProx, Scaffold, andFedeRageon MNIST, FashionMNIST, and CIFAR\-10 after10,00010\{,\}000communication rounds, under uniform and non\-uniform client availability\. Entries marked†are statistically significant \(two\-sampleZZ\-test at the5%5\\%level, computed on the final ten communication rounds\)\.Boldindicates the best mean in each column;blueindicates 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\.Lipschitz continuity of the losses then yields the following\.

###### Corollary 1\(Local Value Divergence\)\.

Fori,j∈\[N\]i,j\\in\[N\]andτi,τj∈\[S​H,S​H\+H\]\\tau\_\{i\},\\tau\_\{j\}\\in\[SH,SH\+H\],

𝔼⁡\[\|fi​\(θiτi\)−fi​\(θjτj\)\|\|ℱS​H\]≤4​ℓ​η​G​H\.\\mathbb\{E\}\\big\[\|f\_\{i\}\(\\theta\_\{i\}^\{\\tau\_\{i\}\}\)\-f\_\{i\}\(\\theta\_\{j\}^\{\\tau\_\{j\}\}\)\|\\,\\big\|\\,\\mathcal\{F\}\_\{SH\}\\big\]\\leq 4\\ell\\eta GH\.

###### Proof\.

Byℓ\\ell\-Lipschitz continuity offif\_\{i\}on𝒞\\mathcal\{C\}we have\|fi​\(θ\)−fi​\(θ′\)\|≤ℓ​‖θ−θ′‖\|f\_\{i\}\(\\theta\)\-f\_\{i\}\(\\theta^\{\\prime\}\)\|\\leq\\ell\\\|\\theta\-\\theta^\{\\prime\}\\\|for allθ,θ′∈𝒞\\theta,\\theta^\{\\prime\}\\in\\mathcal\{C\}\. Applying this toθiτi,θjτj∈𝒞\\theta\_\{i\}^\{\\tau\_\{i\}\},\\theta\_\{j\}^\{\\tau\_\{j\}\}\\in\\mathcal\{C\}, taking𝔼\[⋅∣ℱS​H\]\\mathbb\{E\}\[\\,\\cdot\\mid\\mathcal\{F\}\_\{SH\}\], and invoking Lemma[3](https://arxiv.org/html/2609.21057#Thmlemma3)gives the boundℓ⋅4​η​G​H\\ell\\cdot 4\\eta GH\. ∎

### IV\-BClient Availability and the Global Update

The server aggregation at global roundttis denoted byθ^t=1\|St\|​∑j∈Stθjt−1\\hat\{\\theta\}^\{t\}=\\frac\{1\}\{\|S^\{t\}\|\}\\sum\_\{j\\in S^\{t\}\}\\theta\_\{j\}^\{t\-1\}\. The following inequality relates this aggregation to the survival probabilities\{pi\}\\\{p\_\{i\}\\\}\. 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](https://arxiv.org/html/2609.21057#S2.E8)\)\.

###### Lemma 4\(Sample\-to\-Model Inequality\)\.

At every global roundtt,

𝔼⁡\[‖θ^t−θ∗‖2∣ℱt−1\]≤∑i∈\[N\]pi​‖θit−1−θ∗‖2\.\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]\\leq\\sum\_\{i\\in\[N\]\}p\_\{i\}\\,\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}\.\(17\)

###### Proof\.

Since∥⋅∥2\\\|\\cdot\\\|^\{2\}is convex andθ^t−θ∗\\hat\{\\theta\}^\{t\}\-\\theta^\{\*\}is an average of the\|St\|\|S^\{t\}\|vectors\{θit−1−θ∗\}i∈St\\\{\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\}\_\{i\\in S^\{t\}\}, Jensen’s inequality gives

𝔼⁡\[‖θ^t−θ∗‖2∣ℱt−1\]\\displaystyle\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]=𝔼St​\[‖1\|St\|​∑i∈Stθit−1−θ∗‖2\|ℱt−1\]\\displaystyle=\\mathbb\{E\}\_\{S^\{t\}\}\\Bigg\[\\Big\\\|\\tfrac\{1\}\{\|S^\{t\}\|\}\\sum\_\{i\\in S^\{t\}\}\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\Big\\\|^\{2\}\\,\\Big\|\\,\\mathcal\{F\}\_\{t\-1\}\\Bigg\]≤𝔼St​\[1\|St\|​∑i∈St‖θit−1−θ∗‖2\|ℱt−1\]\.\\displaystyle\\leq\\mathbb\{E\}\_\{S^\{t\}\}\\Bigg\[\\tfrac\{1\}\{\|S^\{t\}\|\}\\sum\_\{i\\in S^\{t\}\}\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}\\,\\Big\|\\,\\mathcal\{F\}\_\{t\-1\}\\Bigg\]\.Expanding the expectation over the sampling distribution and exchanging the order of the two finite sums,

𝔼⁡\[‖θ^t−θ∗‖2∣ℱt−1\]\\displaystyle\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{t\}\-\\theta^\{\*\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\big\]≤∑Sℙ⁡\(St=S\)​1\|S\|​∑i∈S‖θit−1−θ∗‖2\\displaystyle\\leq\\sum\_\{S\}\\mathbb\{P\}\(S^\{t\}=S\)\\,\\tfrac\{1\}\{\|S\|\}\\sum\_\{i\\in S\}\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}=∑Sℙ\(St=S\)1\|S\|∑i∈\[N\]𝟙\{i∈S\}∥θit−1−θ∗∥2\\displaystyle=\\sum\_\{S\}\\mathbb\{P\}\(S^\{t\}=S\)\\,\\tfrac\{1\}\{\|S\|\}\\sum\_\{i\\in\[N\]\}\\mathds\{1\}\\\{i\\in S\\\}\\,\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}=∑i∈\[N\]\[∑S1\|S\|ℙ\(St=S\)1\{i∈S\}\]∥θit−1−θ∗∥2\\displaystyle=\\sum\_\{i\\in\[N\]\}\\Bigg\[\\sum\_\{S\}\\tfrac\{1\}\{\|S\|\}\\,\\mathbb\{P\}\(S^\{t\}=S\)\\,\\mathds\{1\}\\\{i\\in S\\\}\\Bigg\]\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\}=∑i∈\[N\]pi​‖θit−1−θ∗‖2,\\displaystyle=\\sum\_\{i\\in\[N\]\}p\_\{i\}\\,\\\|\\theta\_\{i\}^\{t\-1\}\-\\theta^\{\*\}\\\|^\{2\},where the last equality is the definition \([8](https://arxiv.org/html/2609.21057#S2.E8)\) ofpip\_\{i\}\. SinceStS^\{t\}is independent ofℱt−1\\mathcal\{F\}\_\{t\-1\}and the iteratesθit−1\\theta\_\{i\}^\{t\-1\}areℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable, the interchange above is justified\. ∎

### IV\-CThe Risk\-Neutral Case

We now state and prove convergence of agnostic FedAvg on the induced objective \([5](https://arxiv.org/html/2609.21057#S2.E5)\)\.

###### Theorem 1\(Convergence of Agnostic FedAvg\)\.

Let Assumptions[1](https://arxiv.org/html/2609.21057#Thmassumption1)and[2](https://arxiv.org/html/2609.21057#Thmassumption2)hold\. Then, with step sizeη=Θ⁡\(1/T​H\)\\eta=\\Theta\\big\(1/\\sqrt\{TH\}\\big\), projected agnostic FedAvg satisfies

𝔼⁡\[f⁡\(1T​∑s=1Tθ^s​H\)−f⁡\(θ∗\)\]=𝒪⁡\(1T\)\.\\boxed\{\\;\\mathbb\{E\}\\\!\\left\[f\\Big\(\\frac\{1\}\{T\}\\sum\_\{s=1\}^\{T\}\\hat\{\\theta\}^\{sH\}\\Big\)\-f\(\\theta^\{\*\}\)\\right\]=\\mathcal\{O\}\\\!\\left\(\\frac\{1\}\{\\sqrt\{T\}\}\\right\)\.\\;\}

###### Proof\.

Fix a global rounds∈\{1,…,T\}s\\in\\\{1,\\dots,T\\\}\. Summing the bound of Lemma[2](https://arxiv.org/html/2609.21057#Thmlemma2)over theHHlocal steps of roundssfor clientii, taking total expectations, and usingθi\(s−1\)​H=θ^\(s−1\)​H\\theta\_\{i\}^\{\(s\-1\)H\}=\\hat\{\\theta\}^\{\(s\-1\)H\},

𝔼⁡\[‖θis​H−1−θ∗‖2\]≤𝔼⁡\[‖θ^\(s−1\)​H−θ∗‖2\]−2η∑h=0H−1𝔼\[fi\(θi\(s−1\)​H\+h\)−fi\(θ∗\)\]\+2​H​η2​\(σ2\+G2\)\.\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{sH\-1\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\leq\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{\(s\-1\)H\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\\\ \-2\\eta\\sum\_\{h=0\}^\{H\-1\}\\mathbb\{E\}\\big\[f\_\{i\}\(\\theta\_\{i\}^\{\(s\-1\)H\+h\}\)\-f\_\{i\}\(\\theta^\{\*\}\)\\big\]\\\\ \+2H\\eta^\{2\}\(\\sigma^\{2\}\+G^\{2\}\)\.\(18\)Every local iterateθi\(s−1\)​H\+h\\theta\_\{i\}^\{\(s\-1\)H\+h\}lies in the round\-sswindow, andθ^s​H\\hat\{\\theta\}^\{sH\}is an average of end\-of\-round iterates of that same window; hence Corollary[1](https://arxiv.org/html/2609.21057#Thmcorollary1)applies to each pair and gives, in conditional expectation,

−𝔼⁡\[fi​\(θi\(s−1\)​H\+h\)\|ℱ\(s−1\)​H\]≤−𝔼⁡\[fi​\(θ^s​H\)\|ℱ\(s−1\)​H\]\+4​ℓ​η​G​H\.\-\\,\\mathbb\{E\}\\big\[f\_\{i\}\(\\theta\_\{i\}^\{\(s\-1\)H\+h\}\)\\,\\big\|\\,\\mathcal\{F\}\_\{\(s\-1\)H\}\\big\]\\leq\\\\ \-\\,\\mathbb\{E\}\\big\[f\_\{i\}\(\\hat\{\\theta\}^\{sH\}\)\\,\\big\|\\,\\mathcal\{F\}\_\{\(s\-1\)H\}\\big\]\+4\\ell\\eta GH\.Substituting into \([18](https://arxiv.org/html/2609.21057#S4.E18)\) and taking total expectations,

𝔼⁡\[‖θis​H−1−θ∗‖2\]≤𝔼⁡\[‖θ^\(s−1\)​H−θ∗‖2\]−2​η​H​𝔼​\[fi​\(θ^s​H\)−fi​\(θ∗\)\]\+2​H​η2​\(σ2\+G2\)\+8​ℓ​η2​G​H2\.\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{sH\-1\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\leq\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{\(s\-1\)H\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\\\ \-2\\eta H\\,\\mathbb\{E\}\\big\[f\_\{i\}\(\\hat\{\\theta\}^\{sH\}\)\-f\_\{i\}\(\\theta^\{\*\}\)\\big\]\\\\ \+2H\\eta^\{2\}\(\\sigma^\{2\}\+G^\{2\}\)\+8\\ell\\eta^\{2\}GH^\{2\}\.\(19\)Lemma[4](https://arxiv.org/html/2609.21057#Thmlemma4)att=s​Ht=sH, together with the tower property, gives

𝔼⁡\[‖θ^s​H−θ∗‖2\]≤∑i∈\[N\]pi​𝔼​\[‖θis​H−1−θ∗‖2\]\.\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{sH\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\leq\\sum\_\{i\\in\[N\]\}p\_\{i\}\\,\\mathbb\{E\}\\big\[\\\|\\theta\_\{i\}^\{sH\-1\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\.\(20\)Weighting \([19](https://arxiv.org/html/2609.21057#S4.E19)\) bypip\_\{i\}, summing overi∈\[N\]i\\in\[N\], using∑ipi​fi=f\\sum\_\{i\}p\_\{i\}f\_\{i\}=ffrom \([2](https://arxiv.org/html/2609.21057#S2.E2)\), and combining with \([20](https://arxiv.org/html/2609.21057#S4.E20)\),

𝔼⁡\[‖θ^s​H−θ∗‖2\]≤𝔼⁡\[‖θ^\(s−1\)​H−θ∗‖2\]−2​η​H​𝔼​\[f⁡\(θ^s​H\)−f⁡\(θ∗\)\]\+2​H​η2​\(σ2\+G2\)\+8​ℓ​η2​G​H2\.\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{sH\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\leq\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{\(s\-1\)H\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\\\\ \-2\\eta H\\,\\mathbb\{E\}\\big\[f\(\\hat\{\\theta\}^\{sH\}\)\-f\(\\theta^\{\*\}\)\\big\]\\\\ \+2H\\eta^\{2\}\(\\sigma^\{2\}\+G^\{2\}\)\+8\\ell\\eta^\{2\}GH^\{2\}\.\(21\)Dividing by2​η​H2\\eta Hand rearranging,

𝔼⁡\[f⁡\(θ^s​H\)−f⁡\(θ∗\)\]≤𝔼⁡\[‖θ^\(s−1\)​H−θ∗‖2\]−𝔼⁡\[‖θ^s​H−θ∗‖2\]2​η​H\+η⁡\(σ2\+G2\)\+4​ℓ​η​G​H\.\\mathbb\{E\}\\big\[f\(\\hat\{\\theta\}^\{sH\}\)\-f\(\\theta^\{\*\}\)\\big\]\\leq\\frac\{\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{\(s\-1\)H\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\-\\mathbb\{E\}\\big\[\\\|\\hat\{\\theta\}^\{sH\}\-\\theta^\{\*\}\\\|^\{2\}\\big\]\}\{2\\eta H\}\\\\ \+\\eta\(\\sigma^\{2\}\+G^\{2\}\)\+4\\ell\\eta GH\.\(22\)Summing overs=1,…,Ts=1,\\dots,Ttelescopes the first term and discards a nonnegative quantity; dividing byTTand applying Jensen’s inequality to the convex functionffgives

𝔼⁡\[f⁡\(1T​∑s=1Tθ^s​H\)−f⁡\(θ∗\)\]≤‖θ^0−θ∗‖22​η​H​T\+η⁡\(σ2\+G2\)\+4​ℓ​η​G​H\.\\mathbb\{E\}\\\!\\left\[f\\\!\\Big\(\\tfrac\{1\}\{T\}\\sum\_\{s=1\}^\{T\}\\hat\{\\theta\}^\{sH\}\\Big\)\-f\(\\theta^\{\*\}\)\\right\]\\\\ \\leq\\frac\{\\\|\\hat\{\\theta\}^\{0\}\-\\theta^\{\*\}\\\|^\{2\}\}\{2\\eta HT\}\+\\eta\(\\sigma^\{2\}\+G^\{2\}\)\+4\\ell\\eta GH\.\(23\)SettingD2:=‖θ^0−θ∗‖2D^\{2\}:=\\\|\\hat\{\\theta\}^\{0\}\-\\theta^\{\*\}\\\|^\{2\}andη=c/T​H\\eta=c/\\sqrt\{TH\}for a constantc\>0c\>0,

𝔼⁡\[f⁡\(1T​∑s=1Tθ^s​H\)−f⁡\(θ∗\)\]≤D22​c​T​H\+c⁡\(σ2\+G2\)T​H\+4​c​ℓ​G​HT,\\mathbb\{E\}\\\!\\left\[f\\\!\\Big\(\\tfrac\{1\}\{T\}\\textstyle\\sum\_\{s=1\}^\{T\}\\hat\{\\theta\}^\{sH\}\\Big\)\-f\(\\theta^\{\*\}\)\\right\]\\\\ \\leq\\frac\{D^\{2\}\}\{2c\\sqrt\{TH\}\}\+\\frac\{c\(\\sigma^\{2\}\+G^\{2\}\)\}\{\\sqrt\{TH\}\}\+4c\\,\\ell G\\sqrt\{\\tfrac\{H\}\{T\}\},\(24\)and for fixedHHthe dominant term is of order1/T1/\\sqrt\{T\}, which is the claim\. ∎

Theorem[1](https://arxiv.org/html/2609.21057#Thmtheorem1)establishes an𝒪⁡\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{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](https://arxiv.org/html/2609.21057#S2.E8)\)\. As the proof shows, the participation law enters only through Lemma[4](https://arxiv.org/html/2609.21057#Thmlemma4), which was established directly from \([8](https://arxiv.org/html/2609.21057#S2.E8)\); the argument therefore covers variable\-size random access without modification\. Faster rates, of order1/T1/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 \([23](https://arxiv.org/html/2609.21057#S4.E23)\) contains no residual term that grows withTT, in contrast with several earlier analyses of local\-update methods\. Section[V](https://arxiv.org/html/2609.21057#S5)examines this behavior empirically under both uniform and skewed availability\.

### IV\-DExtension toFedeRage

We now transfer the guarantee to the mean–CVaR objectivefα,γf\_\{\\alpha,\\gamma\}of \([14](https://arxiv.org/html/2609.21057#S3.E14)\)\. Define

κ⁡\(α,γ\):=\(1−γ\)\+γα,γ∈\[0,1\],α∈\(0,1\],\\kappa\(\\alpha,\\gamma\):=\(1\-\\gamma\)\+\\frac\{\\gamma\}\{\\alpha\},\\qquad\\gamma\\in\[0,1\],\\ \\alpha\\in\(0,1\],and note thatκ⁡\(α,0\)=κ⁡\(1,γ\)=1\\kappa\(\\alpha,0\)=\\kappa\(1,\\gamma\)=1andκ⁡\(α,γ\)≥1\\kappa\(\\alpha,\\gamma\)\\geq 1throughout\.

###### Theorem 2\(Convergence ofFedeRage\)\.

Let Assumptions[1](https://arxiv.org/html/2609.21057#Thmassumption1)and[2](https://arxiv.org/html/2609.21057#Thmassumption2)hold, and let𝒞⊆Θ\\mathcal\{C\}\\subseteq\\Thetaandℬ⊂ℝ\\mathcal\{B\}\\subset\\mathbb\{R\}be convex and compact, with projectionsΠ𝒞\\Pi\_\{\\mathcal\{C\}\}andΠℬ\\Pi\_\{\\mathcal\{B\}\}\. Consider projected agnostic FedAvg applied tofα,γf\_\{\\alpha,\\gamma\}over𝒞×ℬ\\mathcal\{C\}\\times\\mathcal\{B\}, with global checkpoints\(θ^s​H,β^s​H\)\(\\hat\{\\theta\}^\{sH\},\\hat\{\\beta\}^\{sH\}\)as in Algorithm[2](https://arxiv.org/html/2609.21057#alg2), and let\(θ∗,β∗\)∈argmin\(θ,β\)∈𝒞×ℬfα,γ​\(θ,β\)\(\\theta^\{\*\},\\beta^\{\*\}\)\\in\\operatorname\*\{argmin\}\_\{\(\\theta,\\beta\)\\in\\mathcal\{C\}\\times\\mathcal\{B\}\}f\_\{\\alpha,\\gamma\}\(\\theta,\\beta\)\. Then, withη=Θ⁡\(1/\(κ⁡\(α,γ\)​T​H\)\)\\eta=\\Theta\\big\(1/\(\\kappa\(\\alpha,\\gamma\)\\sqrt\{TH\}\)\\big\),

𝔼⁡\[fα,γ​\(1T​∑s=1Tθ^s​H,1T​∑s=1Tβ^s​H\)−fα,γ​\(θ∗,β∗\)\]=𝒪⁡\(\(1−γ\)\+γ/αT\)\.\\mathbb\{E\}\\\!\\left\[f\_\{\\alpha,\\gamma\}\\Big\(\\tfrac\{1\}\{T\}\\textstyle\\sum\_\{s=1\}^\{T\}\\hat\{\\theta\}^\{sH\},\\ \\tfrac\{1\}\{T\}\\textstyle\\sum\_\{s=1\}^\{T\}\\hat\{\\beta\}^\{sH\}\\Big\)\-f\_\{\\alpha,\\gamma\}\(\\theta^\{\*\},\\beta^\{\*\}\)\\right\]\\\\ =\\mathcal\{O\}\\\!\\left\(\\frac\{\(1\-\\gamma\)\+\\gamma/\\alpha\}\{\\sqrt\{T\}\}\\right\)\.\(25\)

###### Proof\.

Writeu=\(θ,β\)∈𝒞×ℬu=\(\\theta,\\beta\)\\in\\mathcal\{C\}\\times\\mathcal\{B\}and

gα,γ​\(θ,β,ξ\)=\(1−γ\)​f​\(θ,ξ\)\+γ⁡\[β\+1α​\(f⁡\(θ,ξ\)−β\)\+\],g\_\{\\alpha,\\gamma\}\(\\theta,\\beta;\\xi\)=\(1\-\\gamma\)f\(\\theta;\\xi\)\+\\gamma\\Big\[\\beta\+\\tfrac\{1\}\{\\alpha\}\\big\(f\(\\theta;\\xi\)\-\\beta\\big\)\_\{\+\}\\Big\],so thatfα,γ​\(u\)=𝔼ξ∼𝒬b​\[gα,γ​\(u,ξ\)\]f\_\{\\alpha,\\gamma\}\(u\)=\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{Q\}^\{b\}\}\[g\_\{\\alpha,\\gamma\}\(u;\\xi\)\]by \([14](https://arxiv.org/html/2609.21057#S3.E14)\)\.

*\(i\) Convexity\.*The map\(θ,β\)↦f⁡\(θ,ξ\)−β\(\\theta,\\beta\)\\mapsto f\(\\theta;\\xi\)\-\\betais jointly convex by Assumption[1](https://arxiv.org/html/2609.21057#Thmassumption1), and\(⋅\)\+\(\\cdot\)\_\{\+\}is convex and nondecreasing, so the composition is jointly convex; adding the affine termβ\\betaand the convex term\(1−γ\)​f​\(θ,ξ\)\(1\-\\gamma\)f\(\\theta;\\xi\)with nonnegative coefficients preserves convexity\. Hencegα,γ​\(⋅,ξ\)g\_\{\\alpha,\\gamma\}\(\\cdot\\,;\\xi\)is convex on𝒞×ℬ\\mathcal\{C\}\\times\\mathcal\{B\}for everyξ\\xi, and so isfα,γf\_\{\\alpha,\\gamma\}as a convex combination of such functions\.

*\(ii\) Subgradients and the algorithm\.*A measurable subgradient selection ofgα,γg\_\{\\alpha,\\gamma\}is

∂θgα,γ=w​∇θf​\(θ,ξ\),∂βGα,γ=1−w,\\partial\_\{\\theta\}g\_\{\\alpha,\\gamma\}=w\\,\\nabla\_\{\\theta\}f\(\\theta;\\xi\),\\qquad\\partial\_\{\\beta\}G\_\{\\alpha,\\gamma\}=1\-w,withw=ω⁡\(θ,β,ξ\)∈\[1−γ,κ\]w=\\omega\(\\theta,\\beta;\\xi\)\\in\[1\-\\gamma,\\kappa\], which is exactly the pair of directions used in Lines 8–9 of Algorithm[2](https://arxiv.org/html/2609.21057#alg2)\. Consequently the local step of Algorithm[2](https://arxiv.org/html/2609.21057#alg2)is a projected stochastic subgradient step onfα,γf\_\{\\alpha,\\gamma\}over𝒞×ℬ\\mathcal\{C\}\\times\\mathcal\{B\}, conditionally unbiased by Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2)and the independence ofξit\\xi\_\{i\}^\{t\}fromℱt−1\\mathcal\{F\}\_\{t\-1\}\.

*\(iii\) Constants\.*Since0≤w≤κ0\\leq w\\leq\\kappaand\|1−w\|≤κ\|1\-w\|\\leq\\kappa, the Lipschitz, second\-moment, and variance constants of Assumption[2](https://arxiv.org/html/2609.21057#Thmassumption2)and Lemma[1](https://arxiv.org/html/2609.21057#Thmlemma1)transfer tofα,γf\_\{\\alpha,\\gamma\}as

ℓα,γ≤κ​ℓ\+1,Gα,γ2≤κ2​\(G2\+1\),σα,γ2≤κ2​σ2,\\ell\_\{\\alpha,\\gamma\}\\leq\\kappa\\,\\ell\+1,\\quad G^\{2\}\_\{\\alpha,\\gamma\}\\leq\\kappa^\{2\}\(G^\{2\}\+1\),\\quad\\sigma^\{2\}\_\{\\alpha,\\gamma\}\\leq\\kappa^\{2\}\\sigma^\{2\},the additive constants arising from theβ\\beta\-coordinate, whose subgradient is bounded byκ\\kappaindependently of the data\. In particularℓα,γ=𝒪⁡\(κ\)\\ell\_\{\\alpha,\\gamma\}=\\mathcal\{O\}\(\\kappa\),Gα,γ=𝒪⁡\(κ\)G\_\{\\alpha,\\gamma\}=\\mathcal\{O\}\(\\kappa\), andσα,γ2=𝒪⁡\(κ2\)\\sigma^\{2\}\_\{\\alpha,\\gamma\}=\\mathcal\{O\}\(\\kappa^\{2\}\)\.

*\(iv\) Transfer of the analysis\.*Lemmata[2](https://arxiv.org/html/2609.21057#Thmlemma2)–[4](https://arxiv.org/html/2609.21057#Thmlemma4)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\)\(\\theta\_\{i\},\\beta\_\{i\}\)jointly with the same weights1/\|St\|1/\|S^\{t\}\|, so Lemma[4](https://arxiv.org/html/2609.21057#Thmlemma4)applies verbatim to the product iterate on𝒞×ℬ\\mathcal\{C\}\\times\\mathcal\{B\}, whose projection is the Cartesian productΠ𝒞×Πℬ\\Pi\_\{\\mathcal\{C\}\}\\times\\Pi\_\{\\mathcal\{B\}\}\. Repeating the proof of Theorem[1](https://arxiv.org/html/2609.21057#Thmtheorem1)with\(ℓ,G,σ2\)\(\\ell,G,\\sigma^\{2\}\)replaced by\(ℓα,γ,Gα,γ,σα,γ2\)\(\\ell\_\{\\alpha,\\gamma\},G\_\{\\alpha,\\gamma\},\\sigma^\{2\}\_\{\\alpha,\\gamma\}\)therefore yields, for everyη\>0\\eta\>0,

𝔼⁡\[fα,γ​\(θ¯,β¯\)−fα,γ​\(θ∗,β∗\)\]\\displaystyle\\mathbb\{E\}\\big\[f\_\{\\alpha,\\gamma\}\(\\bar\{\\theta\},\\bar\{\\beta\}\)\-f\_\{\\alpha,\\gamma\}\(\\theta^\{\*\},\\beta^\{\*\}\)\\big\]≤D22​η​T​H\+η⁡\(σα,γ2\+Gα,γ2\)\+4​ℓα,γ​η​Gα,γ​H,\\displaystyle\\qquad\\leq\\frac\{D^\{2\}\}\{2\\eta TH\}\+\\eta\\big\(\\sigma^\{2\}\_\{\\alpha,\\gamma\}\+G\_\{\\alpha,\\gamma\}^\{2\}\\big\)\+4\\ell\_\{\\alpha,\\gamma\}\\,\\eta\\,G\_\{\\alpha,\\gamma\}H,where\(θ¯,β¯\)\(\\bar\{\\theta\},\\bar\{\\beta\}\)denotes the average of theTTglobal checkpoints andD:=supu,v∈𝒞×ℬ‖u−v‖<∞D:=\\sup\_\{u,v\\in\\mathcal\{C\}\\times\\mathcal\{B\}\}\\\|u\-v\\\|<\\infty\. Minimizing the right\-hand side overη\\etagivesη⋆=Θ⁡\(1/\(κ​T​H\)\)\\eta^\{\\star\}=\\Theta\\big\(1/\(\\kappa\\sqrt\{TH\}\)\\big\)and, for fixedHH, the stated bound of orderκ⁡\(α,γ\)/T\\kappa\(\\alpha,\\gamma\)/\\sqrt\{T\}\. ∎

![Refer to caption](https://arxiv.org/html/2609.21057v1/mnist_superexp.png)\(a\) MNIST \(non\-uniform\)
![Refer to caption](https://arxiv.org/html/2609.21057v1/fmnist-superexp.png)\(b\) FashionMNIST \(non\-uniform\)
![Refer to caption](https://arxiv.org/html/2609.21057v1/cifar-superexp.png)\(c\) CIFAR\-10 \(non\-uniform\)

Fig\. 4:Test accuracy over communication rounds under non\-uniform availability on MNIST, FashionMNIST, and CIFAR\-10\.

## VExperiments

![Refer to caption](https://arxiv.org/html/2609.21057v1/userprobs.png)Fig\. 5:Participation probabilities\{pi\}\\\{p\_\{i\}\\\}forM=3M=3,N=30N=30\.We evaluate the proposed algorithm on three standard image\-classification benchmarks—*MNIST*,*FashionMNIST*, and*CIFAR\-10*—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 across3030clients, 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](https://arxiv.org/html/2609.21057#S5.F5)\. This models deployments in which availability is sparse and imbalanced\. In all runs the RAM selectsM=3M=3of theN=30N=30clients per round\.

We compareFedeRageagainst plain FedAvg and two widely adopted heterogeneity\-aware baselines\.FedProx\[[29](https://arxiv.org/html/2609.21057#bib.bib1)\]augments the local objectives with a proximal term that mitigates client drift and stabilizes convergence\. SCAFFOLD\[[16](https://arxiv.org/html/2609.21057#bib.bib11)\]employs control variates, i\.e\., auxiliary parameters that correct client updates and improve the alignment of local and global gradients\. Transport\-based aggregation\[[32](https://arxiv.org/html/2609.21057#bib.bib18)\]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,FedeRageperforms 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 thatFedeRageis preferable once mean and dispersion are read jointly \(Table[I](https://arxiv.org/html/2609.21057#S4.T1)and Fig\.[4](https://arxiv.org/html/2609.21057#S4.F4)\); this indicates more stable and more predictable convergence\.FedeRagealso reaches competitive accuracy within fewer communication rounds\.

In the more realistic*skewed*regime, in which client drift and selection bias act simultaneously, the advantage ofFedeRageis more pronounced\. It outperforms all baselines on the three benchmarks, with a margin that widens on the more complex datasets \(Table[I](https://arxiv.org/html/2609.21057#S4.T1)and Fig\.[4](https://arxiv.org/html/2609.21057#S4.F4)\)\. As shown in Fig\.[6](https://arxiv.org/html/2609.21057#S5.F6), 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](https://arxiv.org/html/2609.21057#S5.F6)indicates that SCAFFOLD, while adequate on average, underperforms substantially on the three least active clients, whereasFedeRagedelivers uniformly high accuracy across the client population—a property of interest in fairness\-sensitive deployments\.

With respect to*convergence*, Theorem[2](https://arxiv.org/html/2609.21057#Thmtheorem2)guarantees a rate of order1/T1/\\sqrt\{T\}in the number of communication rounds, up to the risk\-dependent factorκ⁡\(α,γ\)\\kappa\(\\alpha,\\gamma\)discussed in Remark[2](https://arxiv.org/html/2609.21057#Thmremark2)\. Empirically, we observe a consistent acceleration across datasets, in that the risk\-weighted updates of Algorithm[2](https://arxiv.org/html/2609.21057#alg2)reach a given accuracy level in fewer rounds \(Fig\.[4](https://arxiv.org/html/2609.21057#S4.F4)\)\.

With respect to*computation and communication*, SCAFFOLD maintains and transmits a control variate of the same dimensiond′d^\{\\prime\}as the model, approximately doubling the per\-round communication, whereasFedeRageintroduces a single scalarβ\\betaper client\. Beyond the reduction in memory and bandwidth, this also reduces what each client discloses, as discussed in Section[III](https://arxiv.org/html/2609.21057#S3)\. 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 thatFedeRageattains \(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](https://arxiv.org/html/2609.21057#S4), supports its practicality under restricted and unknown participation\.

![Refer to caption](https://arxiv.org/html/2609.21057v1/fmnistaccuracy_peruser.png)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](https://arxiv.org/html/2609.21057#S5.F5),FedeRageremains accurate even for the three most infrequently available clients \(IDs 27–29\), which the baselines effectively never sample\.### V\-AImplementation 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ηθ\\eta\_\{\\theta\}andηβ\\eta\_\{\\beta\}, the number of local stepsHH, the proximal coefficient ofFedProx, and the risk parameters\(α,γ\)\(\\alpha,\\gamma\)ofFedeRage\. The selected values, the model architectures and data partitions used for each benchmark, the sensitivity ofFedeRageto\(α,γ\)\(\\alpha,\\gamma\), and per\-client accuracies for the uniform\-availability regime are reported in the accompanying supplementary material, together with the code required to reproduce every figure and table\.

## VIConclusion and Future Work

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𝒪⁡\(1/T\)\\mathcal\{O\}\(1/\\sqrt\{T\}\)rate for convex, possibly nonsmooth losses; we then constructed on that basis a distributionally robust, CVaR\-based algorithm,FedeRage, and proved a matching𝒪⁡\(κ⁡\(α,γ\)/T\)\\mathcal\{O\}\(\\kappa\(\\alpha,\\gamma\)/\\sqrt\{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\(α,γ\)\(\\alpha,\\gamma\)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 CVaR\-based 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](https://arxiv.org/html/2609.21057#bib.bib2)\], remains open\.
- •*Nonconvex regimes\.*Extending both the agnostic and the risk\-averse analyses beyond convexity, e\.g\., to stationarity guarantees for deep models, is an important next step\.

## References

- \[1\]H\. Rahimi and D\. Kalogerias\(2025\)Convergence of agnostic federated averaging\.InProc\. IEEE Int\. Workshop Comput\. Adv\. Multi\-Sensor Adaptive Process\. \(CAMSAP\),pp\. 1–5\.Cited by:[FedeRage: Provably Convergent Agnostic Federated Learning under General Client Drift](https://arxiv.org/html/2609.21057#id4)\.
- \[2\]J\. Konečný, H\. B\. McMahan, F\. X\. Yu, P\. Richtárik, A\. T\. Suresh, and D\. Bacon\(2017\)Federated learning: strategies for improving communication efficiency\.arXiv preprint arXiv:1610\.05492\.External Links:[Link](https://arxiv.org/abs/1610.05492)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1)\.
- \[3\]B\. McMahan, E\. Moore, D\. Ramage, S\. Hampson, and B\. A\. y\. Arcas\(2017\)Communication\-efficient learning of deep networks from decentralized data\.InProceedings of the International Conference on Artificial Intelligence and Statistics \(AISTATS\),Vol\.54,pp\. 1273–1282\.External Links:[Link](http://proceedings.mlr.press/v54/mcmahan17a.html)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1),[§I](https://arxiv.org/html/2609.21057#S1.p4.1)\.
- \[4\]P\. Kairouz, H\. B\. McMahan, B\. Avent,et al\.\(2021\)Advances and open problems in federated learning\.Foundations and Trends in Machine Learning14\(1–2\),pp\. 1–210\.External Links:[Document](https://dx.doi.org/10.1561/2200000083)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1)\.
- \[5\]R\. C\. Geyer, T\. Klein, and M\. Nabi\(2017\)Differentially private federated learning: a client level perspective\.arXiv preprint arXiv:1712\.07557\.External Links:[Link](https://arxiv.org/abs/1712.07557)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1),[§III\-B](https://arxiv.org/html/2609.21057#S3.SS2.p3.1)\.
- \[6\]E\. Bagdasaryan, A\. Veit, Y\. Hua, D\. Estrin, and V\. Shmatikov\(2018\)How to backdoor federated learning\.arXiv preprint arXiv:1807\.00459\.External Links:[Link](https://arxiv.org/abs/1807.00459)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1)\.
- \[7\]S\. J\. Reddi, J\. Konečný, P\. Richtárik, B\. Póczós, and A\. Smola\(2016\)AIDE: fast and communication efficient distributed optimization\.arXiv preprint arXiv:1608\.06879\.External Links:[Link](https://arxiv.org/abs/1608.06879)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1)\.
- \[8\]G\. F\. Coppola\(2015\)Iterative parameter mixing for distributed large\-margin training of structured predictors for natural language processing\.Ph\.D\. Thesis,University of Adelaide\.External Links:[Link](https://digital.library.adelaide.edu.au/dspace/handle/2440/108087)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1)\.
- \[9\]J\. Konečný, H\. B\. McMahan, and D\. Ramage\(2015\)Federated optimization: distributed optimization beyond the datacenter\.arXiv preprint arXiv:1511\.03575\.External Links:[Link](https://arxiv.org/abs/1511.03575)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p1.1)\.
- \[10\]Y\. Zhao, M\. Li, L\. Lai, N\. Suda, D\. Civin, and V\. Chandra\(2018\)Federated learning with non\-iid data\.arXiv preprint arXiv:1806\.00582\.External Links:[Link](https://arxiv.org/abs/1806.00582)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p2.1),[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p4.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§I](https://arxiv.org/html/2609.21057#S1.p3.1)\.
- \[11\]Y\. LeCun, L\. Bottou, Y\. Bengio, and P\. Haffner\(1998\)Gradient\-based learning applied to document recognition\.Proceedings of the IEEE86\(11\),pp\. 2278–2324\.External Links:[Link](https://ieeexplore.ieee.org/document/726791)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[12\]S\. Lin, X\. Guo, and D\. Zhou\(2017\)Distributed learning with regularized least squares\.Journal of Machine Learning Research18\(1\),pp\. 3202–3232\.External Links:[Link](https://jmlr.org/papers/v18/16-577.html)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[13\]T\. Li, A\. K\. Sahu, A\. Talwalkar, and V\. Smith\(2019\)Federated learning: challenges, methods, and future directions\.arXiv preprint arXiv:1908\.07873\.External Links:[Link](https://arxiv.org/abs/1908.07873)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[14\]K\. Pillutla, Y\. Laguel, J\. Malick, and Z\. Harchaoui\(2023\)Federated learning with superquantile aggregation for heterogeneous data\.Machine Learning113\(5\),pp\. 2955–3022\.External Links:[Document](https://dx.doi.org/10.1007/s10994-023-06332-x),[Link](https://doi.org/10.1007/s10994-023-06332-x)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p4.1),[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[15\]B\. Hitaj, G\. Ateniese, and F\. Pérez\-Cruz\(2017\)Deep models under the GAN: information leakage from collaborative deep learning\.InProceedings of the ACM SIGSAC Conference on Computer and Communications Security,External Links:[Link](https://dl.acm.org/doi/10.1145/3133956.3134012)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.21057#S3.SS2.p3.1)\.
- \[16\]S\. P\. Karimireddy, S\. Kale, M\. Mohri, S\. J\. Reddi, S\. U\. Stich, and A\. T\. Suresh\(2020\)SCAFFOLD: stochastic controlled averaging for federated learning\.InProceedings of the International Conference on Machine Learning \(ICML\),Vol\.119,pp\. 5132–5143\.External Links:[Link](https://proceedings.mlr.press/v119/karimireddy20a.html)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p2.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§III\-B](https://arxiv.org/html/2609.21057#S3.SS2.p3.1),[§III\-B](https://arxiv.org/html/2609.21057#S3.SS2.p3.1.1),[§V](https://arxiv.org/html/2609.21057#S5.p3.1)\.
- \[17\]J\. Wang, Q\. Liu, H\. Liang, G\. Joshi, and H\. V\. Poor\(2020\)Tackling the objective inconsistency problem in heterogeneous federated optimization\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.33,pp\. 7611–7623\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2020/file/564127c03caaab942e503ee6f810f54d-Paper.pdf)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p3.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[18\]R\. Ye, M\. Xu, J\. Wang, C\. Xu, S\. Chen, and Y\. Wang\(2023\)FedDisco: federated learning with discrepancy\-aware collaboration\.InProceedings of the International Conference on Machine Learning \(ICML\),Vol\.202,pp\. 39879–39902\.External Links:[Link](https://proceedings.mlr.press/v202/ye23f.html)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p3.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[19\]M\. Hong, M\. Razaviyayn, and J\. P\. Lee\(2018\)Gradient primal\-dual algorithm converges to second\-order stationary solution for nonconvex distributed optimization over networks\.InProceedings of the International Conference on Machine Learning \(ICML\),Vol\.80\.External Links:[Link](https://proceedings.mlr.press/v80/hong18a.html)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[20\]D\. Jakovetić\(2013\)Distributed optimization: algorithms and convergence rates\.Ph\.D\. Thesis,Carnegie Mellon University\.External Links:[Link](https://repository.cmu.edu/dissertations/312/)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[21\]M\. Li, D\. G\. Andersen, J\. W\. Park, A\. J\. Smola, A\. Ahmed, V\. Josifovski, J\. Long, E\. J\. Shekita, and B\. Su\(2014\)Scaling distributed machine learning with the parameter server\.InProceedings of the USENIX Symposium on Operating Systems Design and Implementation \(OSDI\),pp\. 583–598\.External Links:[Link](https://www.usenix.org/conference/osdi14/technical-sessions/presentation/li_mu)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[22\]Y\. J\. Cho, J\. Wang, and G\. Joshi\(2022\)Towards understanding biased client selection in federated learning\.InProc\. Int\. Conf\. Artif\. Intell\. Statist\. \(AISTATS\),PMLR, Vol\.151,pp\. 10351–10375\.External Links:[Link](https://proceedings.mlr.press/v151/jee-cho22a.html)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p3.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[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\(2021\)A field guide to federated optimization\.arXiv preprint arXiv:2107\.06917\.External Links:[Link](https://arxiv.org/abs/2107.06917)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§II\-B](https://arxiv.org/html/2609.21057#S2.SS2.p1.1)\.
- \[24\]H\. Eichner, T\. Koren, B\. McMahan, N\. Srebro, and K\. Talwar\(2019\)Semi\-cyclic stochastic gradient descent\.InProceedings of the International Conference on Machine Learning \(ICML\),Vol\.97,pp\. 1764–1773\.External Links:[Link](https://proceedings.mlr.press/v97/eichner19a.html)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§II\-B](https://arxiv.org/html/2609.21057#S2.SS2.p1.1)\.
- \[25\]Y\. Ruan, X\. Zhang, S\. Liang, and C\. Joe\-Wong\(2021\)Towards flexible device participation in federated learning\.InProceedings of the International Conference on Artificial Intelligence and Statistics \(AISTATS\),Vol\.130,pp\. 3403–3411\.External Links:[Link](https://proceedings.mlr.press/v130/ruan21a.html)Cited by:[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§II\-B](https://arxiv.org/html/2609.21057#S2.SS2.p1.1)\.
- \[26\]M\. Ribero, H\. Vikalo, and G\. de Veciana\(2023\)Federated learning under intermittent client availability and time\-varying communication constraints\.IEEE Journal of Selected Topics in Signal Processing17\(1\),pp\. 98–111\.External Links:[Document](https://dx.doi.org/10.1109/JSTSP.2022.3224590)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p3.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1)\.
- \[27\]P\. Theodoropoulos, K\. E\. Nikolakakis, and D\. Kalogerias\(2024\)Federated learning under restricted user availability\.InProc\. IEEE Int\. Conf\. Acoust\., Speech, Signal Process\. \(ICASSP\),Note:arXiv:2309\.14176Cited by:[1st item](https://arxiv.org/html/2609.21057#S1.I1.i1.p1.1),[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1),[§I](https://arxiv.org/html/2609.21057#S1.p2.1),[§I](https://arxiv.org/html/2609.21057#S1.p3.1),[§II\-B](https://arxiv.org/html/2609.21057#S2.SS2.p1.1),[§II](https://arxiv.org/html/2609.21057#S2.p2.1)\.
- \[28\]A\. Khaled, K\. Mishchenko, and P\. Richtárik\(2019\)First analysis of local GD on heterogeneous data\.arXiv preprint arXiv:1909\.04715\.External Links:[Link](https://arxiv.org/abs/1909.04715)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p2.1),[§I](https://arxiv.org/html/2609.21057#S1.p4.1)\.
- \[29\]T\. Li, A\. K\. Sahu, M\. Zaheer, M\. Sanjabi, A\. Talwalkar, and V\. Smith\(2020\)Federated optimization in heterogeneous networks\.InProc\. Mach\. Learn\. Syst\. \(MLSys\),Vol\.2,pp\. 429–450\.External Links:[Link](https://proceedings.mlsys.org/paper_files/paper/2020/hash/1f5fe83998a09396ebe6477d9475ba0c-Abstract.html)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p2.1),[§V](https://arxiv.org/html/2609.21057#S5.p3.1)\.
- \[30\]S\. J\. Reddi, Z\. Charles, M\. Zaheer, Z\. Garrett, K\. Rush, J\. Konečný, S\. Kumar, and H\. B\. McMahan\(2021\)Adaptive federated optimization\.InProc\. Int\. Conf\. Learn\. Representations \(ICLR\),External Links:[Link](https://openreview.net/forum?id=LkFG3lB13U5)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p3.1)\.
- \[31\]H\. Yang, X\. Zhang, P\. Khanduri, and J\. Liu\(2022\)Anarchic federated learning\.InProceedings of the International Conference on Machine Learning \(ICML\),Vol\.162,pp\. 25331–25363\.External Links:[Link](https://proceedings.mlr.press/v162/yang22r.html)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p3.1)\.
- \[32\]H\. Rahimi and D\. Kalogerias\(2026\)FedAVOT: exact distribution alignment in federated learning via masked optimal transport\.InProc\. IEEE Int\. Conf\. Acoust\., Speech, Signal Process\. \(ICASSP\),Note:To appearCited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p4.1),[§V](https://arxiv.org/html/2609.21057#S5.p3.1)\.
- \[33\]T\. A\. Nguyen, T\. D\. Nguyen, L\. T\. Le, and C\. T\. Dinh\(2022\)On the generalization of wasserstein robust federated learning\.arXiv preprint arXiv:2206\.01432\.External Links:[Link](https://arxiv.org/abs/2206.01432)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p4.1),[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1)\.
- \[34\]M\. Mohri, G\. Sivek, and A\. T\. Suresh\(2019\)Agnostic federated learning\.InProc\. Int\. Conf\. Mach\. Learn\. \(ICML\),PMLR, Vol\.97,pp\. 4615–4625\.External Links:[Link](https://proceedings.mlr.press/v97/mohri19a.html)Cited by:[§I\-A](https://arxiv.org/html/2609.21057#S1.SS1.p5.1),[5th item](https://arxiv.org/html/2609.21057#S6.I1.i5.p1.1)\.
- \[35\]Y\. Yu, S\. P\. Karimireddy, Y\. Ma, and M\. I\. Jordan\(2023\)Scaff\-PD: communication efficient fair and robust federated learning\.arXiv preprint arXiv:2307\.13381\.External Links:[Link](https://arxiv.org/abs/2307.13381)Cited by:[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1)\.
- \[36\]Y\. Deng and M\. M\. Kamani\(2020\)Distributionally robust federated averaging\.InAdvances in Neural Information Processing Systems \(NeurIPS\),External Links:[Link](https://proceedings.neurips.cc/paper/2020/file/ac450d10e166657ec8f93a1b65ca1b14-Paper.pdf)Cited by:[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1)\.
- \[37\]J\. Hong, H\. Wang, Z\. Wang, and J\. Zhou\(2021\)Federated robustness propagation: sharing adversarial robustness in federated learning\.arXiv preprint arXiv:2106\.11264\.External Links:[Link](https://arxiv.org/abs/2106.11264)Cited by:[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1)\.
- \[38\]S\. Shi, Y\. Guo, D\. Wang, and Y\. Zhu\(2023\)Distributionally robust federated learning for network traffic classification with noisy labels\.IEEE Transactions on Network and Service Management\.External Links:[Link](https://ieeexplore.ieee.org/document/10265143)Cited by:[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1)\.
- \[39\]D\. Levy, Y\. Carmon, J\. C\. Duchi, and A\. Sidford\(2020\)Large\-scale methods for distributionally robust optimization\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.33,pp\. 8847–8860\.Cited by:[§I\-B](https://arxiv.org/html/2609.21057#S1.SS2.p1.1)\.
- \[40\]R\. T\. Rockafellar and S\. Uryasev\(2000\)Optimization of conditional value\-at\-risk\.Journal of Risk2\(3\),pp\. 21–41\.Cited by:[§III\-A](https://arxiv.org/html/2609.21057#S3.SS1.p1.1)\.
- \[41\]A\. Shapiro, D\. Dentcheva, and A\. Ruszczyński\(2009\)Lectures on stochastic programming: modeling and theory\.SIAM and Mathematical Optimization Society,Philadelphia, PA\.External Links:[Document](https://dx.doi.org/10.1137/1.9780898718751)Cited by:[§III\-A](https://arxiv.org/html/2609.21057#S3.SS1.p1.1),[§III\-A](https://arxiv.org/html/2609.21057#S3.SS1.p2.1)\.