SAGE: Optimal-Stopping Peer Selection for Decentralised Federated Learning
arXiv:2609.23773v1 [cs.DC] 20 Sep 2026
Ke Xiao, Qiyuan Wang, Christos Anagnostopoulos School of Computing Science, University of Glasgow, Glasgow, UK {ke.xiao, qiyuan.wang, christos.anagnostopoulos}@glasgow.ac.uk Abstract—Decentralised federated learning replaces server aggregation with peer-to-peer model exchange, making collaborator selection a local decision under uncertainty. Fixed probe budgets waste effort on easy choices yet fall short when peers are hard to distinguish. We propose SAGE (Sequential Anchor-Gated Exchange), an optimal-stopping peer selector under a one-modelbearing-exchange budget. A receiver scores candidate neighbours on receiver-owned anchor evidence and selects once an advantage is certified. It continues probing only while further evidence repays its cost, and otherwise falls back to random gossip. We show that the stopping problem admits an optimal rule attained at a finite stage, and that the anchor schedule is order-optimal in the peer-risk gap and the confidence level. We further show that the selector never returns a peer worse than random gossip with high probability, and prove that no such guarantee holds for selectors that commit without a certificate. A separability threshold follows, below which no probing budget improves on gossip. Experiments span two image benchmarks, two graph families and three heterogeneity levels. Selectors that always act on their evidence lose to gossip in every configuration tested. SAGE-OS matches gossip on 75.5% less evidence than a fixed budget, at half the communication overhead of two published selectors. The operative decision is not which peer to rank first, but whether the evidence justifies ranking at all. Index Terms—decentralised federated learning, peer selection, gossip learning, anchor validation, adaptive communication
I. I NTRODUCTION Federated learning typically delegates communication and aggregation to a server [1]. In decentralised FL (DFL) there is no such coordinator: clients interact over a graph and each must choose its own collaborator from a local neighbourhood [2], [3]. Under non-IID data that choice is consequential, because a client that spends its one communication opportunity on an incompatible neighbour raises its local loss rather than lowering it. The choice is also sharply asymmetric in cost. Exchanging a model costs the full parameter payload, whereas scoring a candidate on a handful of held-out examples costs only a few predictions. A client can therefore afford to look before it commits — but only if it knows how long to look. Existing peer selectors rank collaborators by local loss, collaborator utility, task or model similarity, selection frequency, or communication cost [7]–[11], and implicitly assume that one fixed evaluation budget is the right amount of evidence for every decision. It is not. An easy neighbourhood is settled by a handful of examples. An ambiguous one may never resolve. Evidence spent there is wasted twice: once in probe cost, and again if the client acts on a ranking the evidence does
not support. We therefore ask a different question: not which peer ranks first, but whether the available evidence justifies ranking at all. Below an explicit threshold on neighbourhood separability, no probing budget improves on random gossip. A receiver starts with a small receiver-owned anchor batch and queries candidate neighbours for bounded loss scores or predictions. In the privacy-preferred form only anchor inputs are sent, labels remain at the receiver, and losses are computed locally from the returned predictions. The batch is enlarged until the best candidate is statistically separated from the runner-up; if confidence is not reached within the probe budget, the client abstains and falls back to random gossip. Only the selected peer transmits the model-bearing object. We make four contributions. First, we formulate peer selection as sequential evidence acquisition under an explicit outside option. A receiver faces a three-action decision at every stage — commit to a peer, buy more evidence, or fall back to gossip — and we cast this as a finite-horizon optimal-stopping problem under a one-modelbearing-exchange constraint. To our knowledge this is the first treatment of decentralised collaborator selection in which the amount of evidence, rather than the ranking rule, is the object of optimisation. Second, we show that the resulting anchor schedule is orderoptimal. Evidence demand scales as Θ(M 2 ∆−2 k log(1/δ)) in the risk gap separating the best neighbour from its closest competitor. We establish both directions of this bound. No selection rule, however adaptive, can certify the best peer from fewer anchors. Third, we establish the conditions under which informed selection is worth attempting at all. We prove that a receiver following our rule never returns a peer worse than random gossip with high probability. No comparable guarantee holds for selectors that commit to the empirically best peer without a certificate. This asymmetry governs their relative behaviour in the experiments. We further identify an explicit separability threshold below which no probing budget can improve on gossip, and show that denser neighbourhoods should abandon probing earlier than sparse ones. Fourth, we evaluate the method against random gossip, fixed-budget anchor selection, two published peer selectors, and two ablations of our own design, across twelve configurations spanning two datasets, two graph families, and three heterogeneity levels. Selectors that always act on their evidence are beaten by uniform gossip on every metric in
every configuration. Our stopping rule recovers gossip-level performance on roughly a quarter of the evidence a fixed budget spends, at half the communication overhead of the published selectors.
j1
ωj ⋆
anchor inputs x cached at the peer predictions back dk per stage
k
II. R ELATED W ORK Decentralised optimisation and gossip learning replace the server with local mixing over graph edges [2], [4], [5]. Communication-efficient approaches additionally sparsify or compress the exchanged information [6]. SAGE is orthogonal to these mechanisms: it asks which feasible neighbour should receive the single model-bearing interaction. Recent DFL methods increasingly make collaboration selective. PENS evaluates peer models on local data [7]; FedeRiCo estimates collaborator utility [8]; PFedDST combines task similarity, loss, and selection frequency [9]; DFLStar selects informative neighbours using last-layer similarity [10]; and OCD-FL balances knowledge gain against communication/energy cost [11]. More recent work learns or adapts the collaboration structure itself: DPFL constructs resourceconstrained collaboration graphs [12], DFedPGP uses directed asymmetric collaboration [13], DFedMQ jointly adapts collaborator selection and topology [14], and CFNS combines multiple factors for neighbour selection under local differential privacy [15]. DA-DPFL instead reduces training and communication cost through dynamic sparse aggregation [16]. These approaches address whom/how to collaborate or what to exchange; SAGE addresses the complementary question of how much pre-exchange evidence to acquire before committing to one peer, with statistically certified selection, explicit abstention to gossip, and cost-aware stopping. Selecting the lowest-risk candidate from a common evidence batch is a pure-exploration problem, and our confidence gate is the decentralised analogue of a racing rule: Hoeffding races prune candidates whose bounds separate [22], and action elimination and best-arm identification formalise the sample complexity of doing so [23], [25]. The Θ(∆−2 log(1/δ)) scaling we establish matches the classical bounds for that problem [24], [26]. Two differences matter here. All candidates are scored on the same anchor batch rather than allocated samples adaptively, so the relevant regime is uniform rather than adaptive allocation. The receiver also holds an outside option, gossip, that pure-exploration formulations lack. Abstention rather than identification is therefore the operative decision. Optimal stopping has also appeared in federated systems, but for different decisions. Dogan-Tusha et al. use the secretary problem to select participating IoT nodes from local-model accuracy and received-signal strength [20], while dynamic hierarchical FL has used optimal stopping to choose relay nodes for energy-efficient parameter upload [21]. These works stop over which node/relay to accept; SAGE instead stops over how much receiver-owned statistical evidence to acquire before a decentralised peer exchange. To the best of our knowledge, SAGE is the first work to formulate sequential
j⋆
j2
model ω: one peer only t = 1) (Bk
j3
j5
j4 labels y never leave k
Fig. 1. Peer selection under a one-model-bearing-exchange budget. Receiver k scores every feasible neighbour on its own held-out anchors, exchanging only inputs and returned predictions, and then admits a full representation from exactly one peer. The probe channel is cheap and reusable; the heavy edge is paid once.
evidence acquisition for peer selection in fully decentralised federated learning as an optimal-stopping problem. SAGE combines cross-evaluation with lightweight knowledge exchange. PENS demonstrates loss-based peer evaluation [7], while distillation shows that predictions or logits can transfer model knowledge without full-model exchange [18], [19]. SAGE keeps model-bearing communication to one peer per round while making the evidence budget adaptive. III. P ROBLEM S ETTING Let G = (V, E) be a communication graph, where V = {1, . . . , K} is the set of K clients and E is the set of communication links. Client k has local dataset Dk , private data distribution Pk , and neighbour set Nk . The round index is t, while j indexes a candidate neighbour of receiver k. Figure 1 illustrates the setting. At round t, client k first performs local optimisation and may then initiate a model-bearing peer exchange. Let Bkt denote the number of neighbours from which client k receives a model-bearing object in that round, that is, one carrying model parameters rather than predictions. SAGE studies the communication-constrained setting Bkt = 1,
(1)
meaning that client k ultimately selects exactly one neighbour for the full representation/model exchange. This is a design constraint of SAGE, not a universal assumption of decentralised learning: methods that mix with all neighbours can have Bkt = dk (or another value determined by their communication schedule). Importantly, Bkt = 1 constrains only the expensive model-bearing exchange. SAGE may still probe multiple candidate neighbours using lightweight evidence before choosing the single peer. Keeping Bkt = 1 across the peer-selection baselines isolates whether better selection justifies its probing overhead. The selected neighbour is jkt ∈ Nk . Let Θtk denote the complete predictor of client k at the start of round t. We write Θt,+ for the model immediately after local optimisak tion in round t but before peer mixing. In the remainder,
the superscript “+” denotes the post-local-update/pre-mixing state. After mixing, the resulting shared state is indexed by t + 1. We decompose the predictor as Θk = (ωk , ϕk ), where ωk is the shared representation block and ϕk is a clientlocal classifier head. Only ω is model-bearing in the main implementation, while ϕ remains local, as in representationpersonalised FL [17]. After peer selection, receiver k mixes its locally updated representation with that of the selected neighbour: ωkt+1 = (1 − αmix )ωkt,+ + αmix ωjt,+ t ,
(2)
k
where αmix ∈ [0, 1] is the peer-mixing coefficient and ωkt+1 is the shared block carried into the next round. The peerselection objective is receiver compatibility rather than necessarily global accuracy. Let x and y denote an input and its label, ℓ(·) the probe loss, and t Rk,j = E(x,y)∼Pk [ℓ(Θt,+ j ; x, y)]
(3)
be the risk of candidate neighbour j on receiver k’s distribution t after the current local-update phase. Lower Rk,j means that peer j is more compatible with client k under the chosen probe loss. Client k cannot evaluate (3) exactly, so it uses a receiverowned anchor set Ak ⊂ Dk . For an anchor batch of size m = |Ak |, the empirical anchor risk is X bt,(m) = 1 ℓ(Θt,+ (4) R j ; x, y). k,j m (x,y)∈Ak
For readability, when analysing a fixed client-round below we b(m) . suppress the superscripts t, + and write Rk,j and R k,j The anchor set Ak is sampled from a held-out local anchor pool disjoint from client k’s optimisation and safety-validation data. In the default protocol, client k retains y, sends only x, and computes the bounded loss locally from each candidate’s returned prediction. This avoids disclosing labels or model parameters during probing, although the queried inputs and returned predictions remain exposed. When stronger protection is required, the probing interface can be combined with differential privacy or secure computation techniques, with any induced randomness or approximation incorporated into the confidence analysis. Only the selected peer transmits the model-bearing object. IV. SAGE: S EQUENTIAL A NCHOR -G ATED E XCHANGE A. Confidence-Gated Selection A fixed anchor size, e.g., 32–64 samples, ignores the local decision geometry. ‘Easy’ choices waste probes, whereas ambiguous choices can still be unstable. SAGE instead ties evidence acquisition to ranking confidence. Assume the perexample probe loss is bounded in [0, M ], where M > 0 is a known loss bound. A certified choice requires a bounded anchor loss (e.g., classification error); a clipped cross-entropy score can be logged as an additional variant. SAGE uses a nested anchor schedule M = {m1 < m2 < · · · < mL = mmax },
(5)
where mℓ is the cumulative number of anchors used at stage ℓ, L is the number of probing stages, and mmax is the maximum anchor budget per decision. Because the same decision is inspected at several stages, the confidence bound must account for both candidate peers and repeated looks. Lemma 1 (Stage-uniform anchor reliability). Let dk = |Nk | be the receiver degree, L the number of anchor stages, and δ ∈ (0, 1) the per-client-round failure probability. With probability at least 1 − δ, b(mℓ ) − Rk,j ≤ rℓ R k,j
∀j ∈ Nk , ℓ = 1, . . . , L,
where the stage-ℓ confidence radius is s log(2dk L/δ) . rℓ = M 2mℓ
(6)
(7)
At stage ℓ, let ĵ1 and ĵ2 be the lowest- and second-lowest empirical-risk peers. SAGE accepts ĵ1 when b(mℓ ) − R b(mℓ ) > 2rℓ . R k,ĵ k,ĵ 2
1
(8)
Otherwise it increases the anchor budget. If no winner is separated by mmax , SAGE abstains from deterministic anchor selection and samples a random active neighbour. The confidence parameter δ is therefore a per client-round decision confidence level. Theorem 1 (Correct confident selection). Whenever condition (8) holds on the event in Lemma 1, ĵ1 is the true minimumrisk neighbour in Nk . Theorem 1 is the main correctness guarantee. The following propositions are finite-sample and stopping results indicating the sufficient conditions and bounds used by SAGE’s decision rule. Let j ⋆ be the true best neighbour and let ∆k = min⋆ (Rk,j − Rk,j ⋆ ) j̸=j
(9)
be the true best-versus-runner-up risk gap. Proposition 1. With probability at least 1 − δ, SAGE is guaranteed to satisfy the stopping rule once m>
2dk L 8M 2 log . 2 ∆k δ
(10)
Equation (10) is the main design insight. A decisive neighbourhood (∆k large) needs few probes. An ambiguous neighbourhood (∆k small) has quadratic probe cost and should often abstain rather than force a ranking. The next result shows that this quadratic dependence is not an artefact of the analysis but intrinsic to the problem: no selection rule, adaptive or otherwise, can certify the best peer with fewer than Ω(M 2 ∆−2 k log(1/δ)) anchors. Theorem 2 (Anchor lower bound). Fix ∆ ∈ (0, 1/2] and δ ∈ (0, 1/4). Consider a receiver with two candidate neighbours whose per-anchor probe losses take values in {0, M }, evaluated on a common anchor batch of size m. Any selection
rule that identifies the lower-risk neighbour with probability at least 1 − δ on every instance with risk gap ∆ requires m ≥
1 − ∆2 /M 2 M 2 1 1 3 M2 log . (11) · 2 log ≥ · 8 ∆ 4δ 32 ∆2 4δ
Theorem 2 matches Proposition 1 in both ∆−2 and k log(1/δ). The residual gap is a constant factor and the additive log(dk L) that the union bound of Lemma 1 pays for covering dk peers and L repeated looks; closing it would require an anytime confidence sequence rather than a stage-uniform one. B. Optimal Stopping and Gossip Fallback The fixed rule “probe until confidence or mmax ” leaves one decision unresolved: an ambiguous client may already know that another probe batch is not worth its cost. We therefore treat random gossip as an explicit outside option and cast anchor acquisition as a finite-horizon optimal-stopping problem, following the standard select/continue logic of optimal stopping [27], [28]. Let Fℓ denote the information available fromPall probe observations after stage ℓ. Let Rk,RG = d−1 j∈Nk Rk,j be the expected anchor risk of choosing k uniformly at random from the dk neighbours, and let ĵ1,ℓ be the empirically best peer at stage ℓ. We express all decision costs in risk-equivalent units. If c0 is the raw cost of one anchor–peer evaluation and χ > 0 converts one unit of prediction risk into the same raw cost scale, define the single normalized cost parameter c0 (12) λ := . χ Thus λ is the probing cost of one additional anchor–peer evaluation measured relative to one unit of predictive risk. The conditional costs (superscripts sel, RG, and cont denote immediate peer selection, immediate random gossip, and continued probing) become Jℓsel = E[Rk,ĵ1,ℓ | Fℓ ],
(13)
JℓRG = E[Rk,RG | Fℓ ], Jℓcont = λdk (mℓ+1 − mℓ ) + E[Vℓ+1 (Fℓ+1 ) | Fℓ ],
(14) (15)
where Vℓ (Fℓ ) is the minimum expected remaining decision cost from stage ℓ onward. The optimal value satisfies Vℓ (Fℓ ) = min{Jℓsel , JℓRG , Jℓcont },
(16)
with VL = min{JLsel , JLRG }. Thus the exact Bayesian optimal policy switches to gossip whenever JℓRG ≤ min{Jℓsel , Jℓcont }.
(17)
Before using (16) we record that the problem it describes is well posed: an optimal rule exists, the recursion computes it, and the optimum is attained at a finite stage. The finite horizon makes this elementary: no uniform-integrability or regularity conditions are required beyond boundedness of the probe loss. Theorem 3 (Existence of an optimal stopping rule). Let the per-example probe loss be bounded in [0, M ] with
λ, dk , mmax < ∞, and let Π be the set of policies adapted to (Fℓ )L ℓ=1 . Then: (i) the recursion (16) with terminal condition VL = min{JLsel , JLRG } is well defined, and Vℓ (Fℓ ) equals the infimum over Π of the expected remaining decision cost from stage ℓ; (ii) the stopping time τ ⋆ = min{ℓ ≤ L : min{Jℓsel , JℓRG } ≤ Jℓcont }
(18)
satisfies τ ⋆ ≤ L almost surely and is optimal, so the infimum in (i) is attained; RG and to (iii) at τ ⋆ it is optimal to select ȷ̂1,τ ⋆ if Jτsel ⋆ ≤ Jτ ⋆ gossip otherwise. Theorem 3 justifies speaking of the optimal policy, but it does not yield an implementable one, because Jℓcont requires the conditional law of future probe outcomes. Equation (16) requires a posterior model for future probe outcomes. SAGE therefore uses a distribution-free sufficient rule derived from the same stopping principle. Let us define the empirical neighbourhood risk and empirical advantage of the currently best peer over random gossip as: 1 X b(mℓ ) b(mℓ ) . Rk,j , Aℓ = R̄ℓ − R (19) R̄ℓ = k,ĵ1,ℓ dk j∈Nk
On the event in Lemma 1, |Rk,RG − R̄ℓ | ≤ rℓ . Proposition 2 (Advantage over gossip). If Aℓ > 2rℓ ,
(20)
then the empirically best peer is guaranteed to have lower true anchor risk than uniform random gossip: Rk,ĵ1,ℓ < Rk,RG . Proposition 2 certifies a single decision. Because SAGE-OS selects only when that certificate fires and otherwise gossips, the guarantee extends from the certificate to the whole policy. Theorem 4 (Gossip safety). On the event of Lemma 1, the peer jkt returned by Algorithm 1 satisfies Rk,jkt ≤ Rk,RG . Consequently, for a probe loss bounded in [0, M ], h i E Rk,jkt ≤ Rk,RG + δM. (21) The same bound holds for VANILLA SAGE, whose certificate (8) identifies the true minimiser and therefore also a peer no worse than the neighbourhood mean. Remark 1 (No such bound exists for always-commit rules). b(m) whether or not AQ-128 and SAGE-NF return arg minj R k,j a certificate fires, so neither branch of the argument applies and the conclusion genuinely fails. When the neighbourhood b(m) is determined by sampling noise is near-tied, arg minj R k,j and lands above Rk,RG with probability approaching that of a uniform draw, a quantity that is bounded by no function of δ. This asymmetry — a policy-level guarantee for the variants permitted to abstain, and none for those that must commit — is what separates the two families experimentally.
The normalized incremental stage cost is probe Cℓ+1 = λdk (mℓ+1 − mℓ ),
(22)
and the same confidence set upper-bounds the most that perfect peer information could improve upon gossip. Proposition 3 (Value-of-perfect-information bound). On the event in Lemma 1, Rk,RG − min Rk,j ≤ Aℓ + 2rℓ .
(23)
probe Cℓ+1 ≥ [Aℓ + 2rℓ ]+
(24)
j∈Nk
Consequently, is a sufficient condition for stopping: even perfect information about the best peer cannot repay one more probe stage relative to immediate gossip, where [z]+ = max{z, 0}. If no peer is already certified to beat gossip by (20), SAGE-OS therefore switches to random gossip. Two consequences of (24) characterise when peer selection is worth attempting at all. The first is an impossibility statement: below a threshold determined by λ, the degree, and the first stage of the schedule, no probing budget whatsoever can improve on gossip. Proposition 4 (Gossip dominance). Let Gk = Rk,RG − minj∈Nk Rk,j be the value of perfect peer information. If λ dk m1 ≥ Gk ,
(25)
then immediate random gossip is optimal: every policy that acquires any anchor evidence incurs at least as much total cost, regardless of the schedule M, the horizon L, or the realised observations. Because Gk ≤ maxj Rk,j −minj Rk,j , a receiver can certify dominance from the observed spread alone. Proposition 4 is the theoretical counterpart of the finding in Section VI that always-committing selectors are beaten by gossip in every configuration. At the operating point used there (λ = 2×10−3 , m1 = 16, and dk = 6, a representative degree lying between the two graph families) the threshold is Gk ≈ 0.19. Under a bounded 0–1 probe loss, gossip therefore dominates unless mean and minimum neighbour error differ by more than 19 percentage points. Neighbourhoods that separable are rare, which accounts for the low certified-selection rate and the high gossip rate. The second consequence formalises the topology effect. The continuation margin is µℓ (d) = λd(mℓ+1 − mℓ ) − [Aℓ + 2rℓ (d)]+ , with SAGE-OS continuing while µℓ (d) < 0. Proposition 5 (Degree monotonicity). Fix a stage ℓ and an empirical advantage Aℓ . If p (26) λ (mℓ+1 − mℓ ) dk 2mℓ log(2dk L/δ) ≥ M, then µℓ is strictly increasing in dk , and consequently the stopping stage ℓ⋆ (dk ) is non-increasing in dk : denser neighbourhoods switch to gossip no later than sparser ones.
Algorithm 1 SAGE-OS at client k in round t Require: Active neighbours Nkt , schedule m1 < · · · < mL , confidence δ, normalized probe cost λ 1: for ℓ = 1, . . . , L do 2: Evaluate all active neighbours on the first mℓ receiver anchors b(mℓ ) , rℓ , R̄ℓ , and Aℓ 3: Compute R k,j 4: Let ĵ1 be the empirical best peer 5: if Aℓ > 2rℓ then 6: Select jkt ← ĵ1 {certified better than RG} 7: break 8: else if ℓ = L then 9: jkt ∼ Uniform(Nkt ); break 10: else probe 11: Cℓ+1 ← λ|Nkt |(mℓ+1 − mℓ ) probe 12: if Cℓ+1 ≥ [Aℓ + 2rℓ ]+ then 13: jkt ∼ Uniform(Nkt ) {optimal-stop fallback} 14: break 15: end if 16: end if 17: end for 18: Request exactly one model-bearing object from jkt and mix using (2)
Condition (26) holds at every stage of the schedule (27) for dk ≥ 3, hence throughout both graph families studied here, whose mean degrees are ≈ 7.35 and ≈ 5.64. Proposition 5 therefore predicts the ordering observed in Section VI, in which the denser Erdős–Rényi graph triggers cost-based gossip more often than the scale-free graph at every matched dataset and heterogeneity level. Propositions 2 and 3 therefore act as distribution-free certificates for membership of the stopping region of Theorem 3: whenever (24) fires, stopping is optimal, so every costtriggered gossip decision taken by SAGE-OS coincides with an optimal stop. The converse does not hold — the condition is sufficient, not necessary — so SAGE-OS may continue at stages where the Bayes-optimal policy would already have stopped. Closing that gap requires exactly the posterior model that (16) needs and (24) avoids, so the residual excess is paid in probe cost rather than in selection quality. Only the ratio c0 /χ affects the decision, so λ removes a degree of freedom while retaining a direct interpretation: larger λ makes probing expensive and triggers earlier gossip. Beprobe cause Cℓ+1 scales linearly with dk , the boundary is topology dependent — high-degree clients pay more to screen another batch and should gossip earlier unless their peer advantage is correspondingly larger, a prediction the experiments confirm. Condition (8) remains the stronger certificate when the goal is to identify the true best peer rather than merely one better than gossip. Under time-varying availability, Nkt ⊆ Nk is the active feasible neighbour set in round t. a) The proposed method and its ablations.: SAGE-OS, given in Algorithm 1, is the method we propose. It certifies
(a) nested anchor schedule and the three exits select ȷ̂1 if Aℓ > 2rℓ
mℓ = 16
continue
mℓ = 32
continue
mℓ = 64
continue
mℓ = 128
exhausted ⇒ gossip
gossip if λdk (mℓ+1 − mℓ ) ≥ [Aℓ + 2rℓ ]+
risk-equivalent units
(b) what evidence could still resolve, vs. what the next stage costs (λ = 2×10−3 , δ = 0.1, dk = 6) 1 0.8 continue: evidence still worth buying
0.6 0.4
stop → gossip: next stage cannot repay its cost 64
0.2 0
16
32
128
cumulative anchors mℓ 2rℓ
probe Cℓ+1
Fig. 2. The stopping rule. (a) At each stage the receiver may certify a peer, buy the next anchor batch, or abandon probing for gossip. (b) The confidence width 2rℓ bounds what further evidence could still resolve and shrinks as −1/2 mℓ , while the cost of the next batch grows with the schedule increment and the degree. Once the curves cross, even perfect peer information cannot repay another stage, which is why terminations concentrate at the middle stages rather than at mmax . Panel (b) is drawn at dk = 6, a representative degree between the two graph families used in Section V.
a peer when that peer is provably better than the randomgossip outside option via (20), and switches to gossip before mmax whenever the next probing stage cannot justify its cost under (24). Two ablations remove one component each, so that the contribution of sequential evidence acquisition, of abstention, and of cost-aware stopping can be separated. Figure 2 summarises the resulting policy and the quantitative reason it terminates early. VANILLA SAGE removes the cost-aware stopping branch. It follows the same nested anchor schedule and the same confidence machinery, selects a peer once the best-versus-runner-up condition (8) is certified, but when confidence is unresolved it always advances to the next anchor stage, probing to mmax before abstaining to uniform random gossip. It therefore reaches the same three outcomes as SAGE-OS — select, or gossip — but has no way to recognise partway through that a decision will not resolve. VANILLA SAGE versus SAGE-OS isolates the value of cost-aware early stopping. SAGE-NF removes abstention instead. It uses the same sequential confidence test as VANILLA SAGE, but if no peer is certified by mmax it deterministically selects the empirical best peer rather than reverting to gossip. VANILLA SAGE versus SAGE-NF isolates the value of declining to act on unresolved evidence. With the fixed-budget control AQ-128, the four anchorbased selectors form a spectrum. AQ-128 always commits on a fixed budget and SAGE-NF always commits on an adaptive one. VANILLA SAGE abstains after exhausting the budget, and SAGE-OS abstains as soon as continuing stops paying. V. E XPERIMENTAL E VALUATION The experiments combine budget-matched controls, which isolate SAGE’s adaptive-probing mechanism under Bkt = 1, with external peer-selection baselines that test competitiveness
with prior DFL methods. Client count, representation model, training horizon, and graph families are shared wherever the comparator permits; any external method with a different communication pattern is measured under that native pattern rather than silently altered. The evaluation addresses five questions. RQ1: is SAGEOS competitive with PENS and PFedDST in predictive performance? RQ2: does sequential probing use less evidence than fixed-mmax AQ-128 without degrading performance? RQ3: does cost-aware stopping reduce evidence use beyond confidence gating alone? RQ4: how does graph topology change the value of adaptive selection? RQ5: how do nonIIDness and task difficulty affect evidence demand? Each is settled in the correspondingly tagged subsection of Section VI.
A. Experimental Setup The study uses Fashion-MNIST (FMNIST) and CIFAR-10 with K = 50 clients and T = 250 communication rounds. After the Dirichlet allocation, each client’s local data is split into three disjoint parts: 80% for local optimisation, 10% as an anchor pool used only for peer probing, and 10% as a local evaluation set used for client-level accuracy reporting. The dataset test set remains shared and is used only for global accuracy and macro-F1. Separating the anchor and local evaluation pools prevents the same samples from both choosing the peer and evaluating client-level performance. Each client uses the same convolutional encoder–decoder representation model as the parent study. FMNIST maps 1 × 28 × 28 inputs to a 64-dimensional latent representation with base width 16; CIFAR-10 maps 3×32×32 inputs to a 128-dimensional latent space with base width 32. The classifier head has two fully connected layers. Training uses Adam with learning rate 10−3 , one local epoch per round, and mini-batch size 64. Encoder– decoder weights are model-bearing and are exchanged after peer selection while classifier heads remain local. The peermixing coefficient is fixed to αmix = 0.5, giving equal weight to the receiver and selected peer representation. Label heterogeneity is generated using a Dirichlet allocation with αDir ∈ {0.05, 0.1, 0.3}, representing severe, strong, and moderate non-IIDness. These regimes emphasise the setting in which neighbour quality is heterogeneous and informed peer selection can be beneficial. The same client partition is reused across all methods. We use two graph families: a connected Erdős–Rényi (ER) graph with p = 0.15 (expected degree ≈ 7.35) and a Barabási–Albert scale-free graph with mBA = 3 (realised mean degree ≈ 5.64). Together they contrast relatively homogeneous connectivity with heterogeneous node degree while retaining non-trivial candidate pools for peer selection. One graph instance is generated per configuration and reused by every method, and all methods within a configuration share the same client partition and initialisation. Each reported cell is a single matched run; dispersion across independent seeds is not quantified, and Section VII states which claims this affects.
B. Baselines The anchor schedule, shared by all three SAGE variants, is M = {16, 32, 64, 128},
mmax = 128,
(27)
with per-decision confidence δ = 0.10 and, for SAGE-OS, normalized probing cost λ = 2 × 10−3 . The anchor subsets are nested, so stage 32 reuses the first 16 anchors and adds only 16 new examples, while later stages reuse all earlier evidence. If a client’s anchor pool contains fewer than mmax samples, the schedule is truncated to the largest feasible stage; if fewer than 16 anchors are available, the client falls back directly to RG. Because each client holds only 10% of its local shard as an anchor pool, this truncation is active for a large fraction of clients and is the reason the fixed-budget control does not consume its full nominal budget in Section VI. All SAGE variants use the 0–1 classification error as a bounded probe loss for the confidence rule, so M = 1 exactly. The budget-matched core isolates SAGE under the same one-model-bearing-exchange constraint: L OCAL uses no peer exchange; RG chooses one neighbour uniformly without selection evidence; and AQ-128 spends the largest feasible anchor budget on every decision and always selects the empirically best peer. The three SAGE variants are as defined in Section IV. The contrast that carries the main claim is AQ-128/SAGE-NF (always commit) against VANILLA SAGE/SAGE-OS (permitted to abstain), with RG as the outside option all four are measured against. PENS [7] is the closest performance-based neighbour selector, using cross-evaluated loss to identify compatible peers. PF ED DST [9] combines loss, task similarity, and selection frequency. PENS uses a model-based neighbour-discovery phase and merges multiple peers, so both are measured under their native communication pattern rather than being forced to Bkt = 1; their realised exchange cost is reported in Section VI. C. Metrics and Protocol We report three metric groups covering learning quality, evidence use, and communication cost. Learning. Global accuracy and macro-F1 on the shared test set, together with mean client accuracy (Client) and worstclient accuracy (Weak). Both are averaged over clients and are distinct from the L OCAL baseline, which performs no peer exchange. Evidence efficiency. With final anchor stage mk,t and degree dk,t , the saving over a fixed mmax budget is P k,t dk,t mk,t P . (28) Saving = 1 − mmax k,t dk,t P Because (28) is normalized by the nominal mmax k,t dk,t , the fixed-budget control AQ-128 itself records a non-zero saving that reflects anchor-pool truncation rather than adaptivity; the adaptive gain of SAGE and SAGE-OS is the increment above that value. We report the complementary quantity, budget consumed = 100% − Saving, which is normalized by the nominal budget and therefore comparable across all
configurations. We additionally report the stopping-stage distribution, the RG-fallback rate, and, for SAGE-OS, the costtriggered early-gossip rate. Communication. CommOH is the number of modelbearing exchanges per round relative to RG. All budgetmatched methods satisfy Bkt = 1 and therefore have CommOH = 1.000 by construction; probe traffic is reported separately as budget consumed. PENS and PFedDST exceed 1 because their native mechanisms exchange models with more than one peer per round. a) Configurations.: Both datasets are run at all three heterogeneity levels under both topologies, giving 12 configurations and 8 methods per configuration. All of them are reported; none are omitted. VI. R ESULTS AND D ISCUSSION We report all twelve configurations: two datasets (FMNIST, CIFAR-10), two topologies (ER, scale-free), and three heterogeneity levels (αDir ∈ {0.05, 0.1, 0.3}). Table I gives global accuracy and macro-F1, Table II client-level accuracy, and Table III evidence use and stopping behaviour. Throughout, budget consumed is 100% − Saving with Saving as in (28), Stop@m the fraction of decisions terminating at stage m, RG fb (RG fallback) the total gossip rate, and Cost-RG the subset triggered by the cost rule (24); always commit denotes AQ128 and SAGE-NF. A. Committing to the empirically best peer is worse than gossiping (RQ2) The principal finding in Table I is negative. The two alwayscommitting variants, AQ-128 and SAGE-NF, are beaten by uniform random gossip in all twelve configurations, with mean accuracy 0.3509 and 0.3531 against 0.3782 for RG. The result is not an artefact of the metric: RG also beats both of them 12/12 on macro-F1 (Table I) and 12/12 on mean client accuracy (Table II). PENS shows the same pattern more mildly, falling below RG in 11/12 configurations. Theorem 4 and Remark 1 predict this outcome, and the gap widens where neighbourhoods are hardest to separate. Spending a full anchor budget and then acting on it is therefore not merely wasteful but actively harmful under Bkt = 1. Two mechanisms appear to combine. Anchor risk is a noisy proxy for post-mixing utility, so the arg-min over bk,j is frequently not the arg-max of realised improvement. R In addition, every client applies the same deterministic rule, so exchanges concentrate on a few locally attractive peers and erode the representation diversity that gossip supplies. This justifies treating gossip as an explicit outside option in (16) rather than a degenerate fallback. B. Abstention recovers gossip-level performance (RQ2) The two variants permitted to abstain close that gap almost exactly, as Theorem 4 requires. VANILLA SAGE reaches mean accuracy 0.3763, within 0.2 points of RG, and beats both always-commit variants everywhere on accuracy and macroF1 alike. SAGE-OS reaches 0.3750 and is ahead of RG in
TABLE I P REDICTIVE PERFORMANCE : GLOBAL ACCURACY ( LEFT ) AND MACRO -F1 ( RIGHT ). B OLD MARKS THE BEST METHOD PER ROW AND METRIC . Global accuracy ↑
Macro-F1 ↑
Dataset
Topo. α
LOCAL
RG
PENS
PFed
AQ-128
NF
Van.
OS
LOCAL
RG
PENS
PFed
AQ-128
NF
Van.
OS
FMNIST
SF SF SF ER ER ER
0.05 0.10 0.30 0.05 0.10 0.30
0.2764 0.3641 0.5815 0.2703 0.3642 0.5818
0.3039 0.4075 0.6429 0.3114 0.4104 0.6430
0.3090 0.4031 0.6323 0.3108 0.4024 0.6346
0.3099 0.4102 0.6420 0.3142 0.4119 0.6417
0.2865 0.3864 0.6252 0.2955 0.3826 0.6293
0.2863 0.3867 0.6230 0.2961 0.3869 0.6321
0.2971 0.4075 0.6391 0.3083 0.4077 0.6473
0.2889 0.4079 0.6425 0.3131 0.4121 0.6439
0.1673 0.2528 0.5155 0.1672 0.2531 0.5157
0.1882 0.3005 0.5843 0.1967 0.3041 0.5845
0.1964 0.2979 0.5734 0.1975 0.2966 0.5757
0.1962 0.3049 0.5847 0.2003 0.3053 0.5831
0.1724 0.2796 0.5646 0.1805 0.2740 0.5692
0.1716 0.2788 0.5638 0.1798 0.2763 0.5716
0.1809 0.3019 0.5799 0.1948 0.3019 0.5899
0.1747 0.3005 0.5841 0.1979 0.3047 0.5863
CIFAR-10 SF SF SF ER ER ER
0.05 0.10 0.30 0.05 0.10 0.30
0.1749 0.2173 0.3124 0.1744 0.2176 0.3143
0.2089 0.2732 0.4260 0.2081 0.2732 0.4296
0.1939 0.2460 0.3927 0.1917 0.2423 0.3917
0.2012 0.2593 0.4080 0.2006 0.2667 0.4101
0.1725 0.2302 0.4048 0.1902 0.2159 0.3918
0.1793 0.2346 0.4049 0.1966 0.2156 0.3948
0.2091 0.2621 0.4264 0.2056 0.2734 0.4320
0.2072 0.2643 0.4319 0.1791 0.2734 0.4355
0.0809 0.1197 0.2325 0.0811 0.1199 0.2327
0.1156 0.1754 0.3610 0.1148 0.1763 0.3644
0.1025 0.1508 0.3247 0.0988 0.1472 0.3239
0.1072 0.1607 0.3411 0.1064 0.1688 0.3404
0.0813 0.1351 0.3386 0.0985 0.1206 0.3219
0.0885 0.1394 0.3385 0.1033 0.1189 0.3245
0.1143 0.1644 0.3599 0.1132 0.1756 0.3665
0.1140 0.1662 0.3651 0.0896 0.1748 0.3683
0.3208
0.3782 0.3625 0.3730
0.3509
0.3531 0.3763 0.3750
0.2282
0.2888 0.2738 0.2833
0.2614
0.2629 0.2869 0.2855
Mean
7 of 12 configurations. Since VANILLA SAGE and SAGENF share an identical confidence test and differ only in what happens when no peer is certified, the 2.3-point mean accuracy gap between them (0.3763 vs 0.3531) is attributable entirely to the ability to decline. The value of anchor evidence in this regime is thus largely diagnostic: it identifies the decisions in which no peer can be trusted, and its payoff is realised by not acting on them. C. Optimal stopping makes abstention cheap (RQ3) Table III quantifies the effect of the cost rule. It beats AQ-128 and SAGE-NF in 11 of 12 configurations on both accuracy and macro-F1, and matches or exceeds VANILLA SAGE in 8 of 12, on far less evidence: mean saving 75.50% against 50.48% and 47.67%. Averaged over the twelve configurations, SAGE-OS concedes 0.13 accuracy points to VANILLA SAGE and saves 25.0 points of evidence. The exchange rate is therefore about 190 points of evidence per accuracy point conceded, which quantifies the effect of cost-aware stopping relative to confidence gating alone. The moderate-heterogeneity setting exhibits the mechanism most sharply. On FMNIST/scale-free at αDir = 0.3, VANILLA SAGE and SAGE-OS both end up gossiping on more than 97% of decisions and land within 0.004 accuracy of one another (0.6391 and 0.6425). VANILLA SAGE reaches that outcome only after probing to a mean of 78.00 anchors, exhausting the full budget on 33.9% of decisions. SAGE-OS determines at stage 32 that no certificate is attainable, stops at a mean of 45.19 anchors, and never reaches 128. Both end in gossip, at markedly different cost. Across the full matrix VANILLA SAGE exhausts the budget on 24–34% of decisions while SAGE-OS does so on at most 2.0%. D. Outcome and cost together Figure 3 reports every configuration rather than an average, and four readings follow. The split between committing and abstaining is categorical. The medians of AQ-128 and SAGE-NF are −2.11 and −2.09 points, with worst cases approaching −5.7. PENS is above gossip once. SAGE-OS is above gossip in seven of twelve, with a positive median of +0.03. Its negative mean comes
from a single outlier, examined below, not from a systematic deficit. SAGE-OS wins outright more often than any other method. It is the best of all eight selectors in four of twelve configurations, against three each for gossip, PF ED DST and VANILLA SAGE. Macro-F1 agrees: its median is −0.01 points, level with gossip, while PF ED DST sits at −0.45 and the committing variants remain at 0/12 with medians near −2.2. The advantage grows as neighbourhoods become separable. At αDir = 0.05 SAGE-OS averages −1.10 points against gossip; at 0.10, −0.16; at 0.30, +0.31, winning three of four. The published selectors move the other way, PF ED DST from −0.16 to −0.99 and PENS from −0.67 to −2.25. Topology shows the same asymmetry: on the denser Erdős–Rényi family SAGE-OS beats gossip in five of six configurations, against two of six on scale-free graphs. This is the regime Proposition 5 concerns, and the direction matches. Cost differences are unambiguous. SAGE-OS consumes 24.5% of the fixed anchor budget, against 49.5% for VANILLA SAGE and SAGE-NF and 52.3% for AQ-128. It issues one model-bearing exchange per round, against 1.784 for PENS and 1.980 for PF ED DST. Both are normalized counts rather than estimates. Quality differences among the leading methods are smaller than their spread across configurations, so we claim no ordering there. What separates them is cost, and the margin is roughly twofold on both axes. E. Where Vanilla SAGE remains the better choice One axis runs the other way, and it is a genuine tradeoff rather than a rounding artefact. On worst-client accuracy (Weak, Table II) VANILLA SAGE is the strongest method in the study, averaging 0.6557 against 0.6275 for SAGE-OS and 0.6164 for RG, and beating SAGE-OS 6–4–2 (win–tie–loss); mean client accuracy shows the same weaker ordering (0.9117 vs 0.9089). The clients most in need of a good collaborator are exactly those with the smallest, most skewed shards, for which anchor evidence is noisiest and a certificate emerges only late; stopping at stage 32 denies them the deeper evidence that would have served them. Macro-F1 shows the same compression, SAGE-OS splitting 6–6 with both VANILLA SAGE and PFedDST against 8/12 on accuracy. Where worst-client fairness is the objective and probe budget is not binding, VANILLA SAGE is the appropriate
TABLE II C LIENT- LEVEL ACCURACY: MEAN (C LIENT ) AND WORST- CLIENT (W EAK ). VANILLA SAGE LEADS ON W EAK (S ECTION VI). Client ↑
Weak ↑
Dataset
Topo.
αDir
RG
AQ-128
SAGE-NF
Vanilla
SAGE-OS
RG
AQ-128
SAGE-NF
Vanilla
SAGE-OS
FMNIST
SF SF SF ER ER ER
0.05 0.10 0.30 0.05 0.10 0.30
0.9768 0.9701 0.9183 0.9748 0.9665 0.9190
0.9702 0.9617 0.9091 0.9733 0.9518 0.9173
0.9710 0.9622 0.9123 0.9739 0.9567 0.9187
0.9748 0.9702 0.9239 0.9755 0.9695 0.9206
0.9731 0.9680 0.9235 0.9701 0.9736 0.9218
0.6667 0.8235 0.7971 0.6667 0.8571 0.8116
0.7576 0.8235 0.7869 0.7273 0.7059 0.7869
0.7273 0.8163 0.7327 0.8000 0.7647 0.7705
0.7576 0.8824 0.8143 0.6667 0.8391 0.7869
0.6970 0.8391 0.7869 0.6667 0.8736 0.7971
CIFAR-10
SF SF SF ER ER ER
0.05 0.10 0.30 0.05 0.10 0.30
0.9166 0.8747 0.8142 0.9226 0.8668 0.8097
0.8896 0.8389 0.7908 0.8987 0.8430 0.7823
0.8997 0.8401 0.8000 0.9044 0.8189 0.7820
0.9187 0.8766 0.8049 0.9126 0.8815 0.8116
0.9108 0.8706 0.8062 0.9006 0.8684 0.8205
0.5000 0.2500 0.6190 0.5000 0.3333 0.5714
0.4545 0.3333 0.5227 0.5000 0.3333 0.5918
0.5000 0.2500 0.5682 0.5000 0.1667 0.6122
0.5000 0.3333 0.6349 0.5000 0.5000 0.6531
0.5000 0.2500 0.6327 0.5000 0.3333 0.6531
0.9108
0.8939
0.8950
0.9117
0.9089
0.6164
0.6103
0.6007
0.6557
0.6275
Mean
(a) every configuration, relative to gossip
(b) by heterogeneity regime | = median
0/12 > RG
SAGE-NF
0/12 > RG
PENS
1/12 > RG
PFedDST
4/12 > RG
Vanilla
5/12 > RG
SAGE-OS
7/12 > RG
−6
−4
−2
0
1 mean pts vs. gossip
AQ-128
2
4
SAGE-OS
Vanilla
PFedDST
PENS
0 −1 −2 0.05
0.10
(d) model traffic
(c) evidence cost (all 12 configurations) AQ-128
52.3
SAGE-NF
0.30
Dirichlet α (less heterogeneous →)
accuracy relative to random gossip (points)
PFedDST
1.98
49.5
Vanilla
PENS
49.5
SAGE-OS
SAGE family
24.5
0
10
20
30
1.78
40
50
60
1
0
probe budget consumed (% of the fixed 128-anchor budget)
1
2
model exchanges per round
Fig. 3. Measured outcome and cost, from Tables I–III. (a) Accuracy relative to uniform random gossip, one point per configuration, median marked. The two always commit selectors are below gossip everywhere; SAGE-OS is above it in seven of twelve. (b) The same quantity by heterogeneity regime: SAGEOS improves as neighbourhoods become easier to separate, while the published selectors degrade. (c)–(d) Probe budget consumed and model traffic, both normalized counts rather than estimates.
variant. Where the joint performance–cost criterion governs — the setting this paper targets — SAGE-OS dominates, trading a 0.03-point mean accuracy difference for a 25-point increase in evidence saving. F. Competitiveness with published selectors at half the exchange cost (RQ1) SAGE-OS exceeds PENS in 10/12 and PF ED DST in 8/12 configurations on global accuracy, and its mean accuracy (0.3750) is above both (0.3625 and 0.3730). It does so at CommOH = 1.000 against 1.784 for PENS and 1.980 for PFedDST, i.e. roughly half the model-bearing traffic. The margin is largest on the harder task: on CIFAR-10/scalefree at αDir = 0.3, SAGE-OS reaches 0.4319 accuracy and 0.3651 macro-F1 against 0.3927/0.3247 for PENS and 0.4080/0.3411 for PFedDST. On FMNIST the three are closer and PFedDST leads in three configurations, SAGE-OS is
therefore competitive on the easier task and ahead on the harder one, at half the exchange cost in both. G. Stopping behaviour follows the theory (RQ4, RQ5) Proposition 1 predicts that evidence demand scales with the inverse square of the peer-risk gap ∆k , so certification should become rarer as neighbourhoods become harder to separate. Table III confirms this. Proposition 4 set the scale: at this operating point gossip provably dominates unless mean and minimum neighbour error differ by roughly 19 points, so high gossip rates are the predicted regime rather than a defect. Certified selection — the complement of the RG-fallback rate — occurs on roughly 16–26% of decisions at αDir = 0.05, where sharply skewed label distributions make peers genuinely different, but collapses to 0.2–5% at αDir = 0.3, where peers are close to interchangeable. SAGE-OS converts that collapse into savings instead of wasted probes: its Cost-RG rate rises
TABLE III P ROBE BUDGET CONSUMED AND STOPPING BEHAVIOUR . B UDGET CONSUMED IS 100% − Saving WITH S AVING AS IN (28); IT IS NORMALIZED BY THE NOMINAL BUDGET AND IS THEREFORE COMPARABLE ACROSS ALL CONFIGURATIONS . S TOP @128 IS THE FRACTION OF DECISIONS EXHAUSTING THE SCHEDULE , RG FB (RG FALLBACK ) THE TOTAL GOSSIP RATE , AND C OST-RG THE SUBSET TRIGGERED BY THE COST RULE (24). Budget consumed ↓
Vanilla SAGE
SAGE-OS
Dataset
Topo.
αDir
AQ-128
Vanilla
SAGE-OS
Stop@128
RG fb
Stop@32
Stop@128
Cost-RG
FMNIST
SF SF SF ER ER ER
0.05 0.10 0.30 0.05 0.10 0.30
39.23% 53.77% 62.77% 45.76% 57.84% 62.11%
35.11% 49.12% 62.59% 42.05% 54.63% 62.04%
21.68% 27.71% 29.42% 17.82% 26.14% 27.57%
25.6% 30.9% 33.9% 28.0% 32.4% 33.9%
83.2% 78.4% 97.4% 76.0% 89.3% 97.4%
26.4% 39.6% 49.6% 50.8% 56.6% 79.7%
0.0% 2.0% 0.0% 0.0% 2.0% 0.0%
22.5% 30.5% 52.0% 26.4% 38.8% 71.7%
CIFAR-10
SF SF SF ER ER ER
0.05 0.10 0.30 0.05 0.10 0.30
48.27% 48.49% 55.14% 44.56% 53.92% 56.14%
43.35% 43.57% 54.98% 38.11% 52.78% 55.88%
21.43% 26.15% 27.41% 19.47% 23.38% 25.83%
24.2% 24.3% 31.9% 24.2% 31.7% 31.6%
79.2% 83.9% 95.0% 84.4% 93.6% 95.4%
36.4% 36.9% 43.0% 46.8% 58.4% 70.1%
0.0% 0.0% 0.0% 0.0% 0.0% 0.0%
20.5% 33.5% 44.3% 23.8% 40.1% 56.8%
52.33%
49.52%
24.50%
29.4%
87.8%
49.5%
0.3%
38.4%
Mean
monotonically with αDir in every dataset–topology pair, from 22.5% to 30.5% to 52.0% on FMNIST/scale-free and from 23.8% to 40.1% to 56.8% on CIFAR-10/ER. Topology acts through degree, also as predicted. Because the stage cost (22) scales linearly with dk , the stopping boundary should bind earlier on denser graphs. It does. At every matched dataset and heterogeneity level, the ER graph (expected degree ≈ 7.35) triggers more cost-based gossip than the scale-free graph (mean degree ≈ 5.64): 38.8% versus 30.5% on FMNIST at αDir = 0.1, and 40.1% versus 33.5% on CIFAR-10 at the same level. Savings follow the same ordering, 73.86% versus 72.29% and 76.62% versus 73.85%. Neither effect was tuned; both follow from the cost model. H. Where aggressive stopping hurts One configuration departs from this pattern, and we report it as a boundary of the method. On CIFAR-10/ER at αDir = 0.05 — the hardest task at the most severe heterogeneity — SAGEOS reaches 0.1791 accuracy against 0.2056 for VANILLA SAGE, 0.1902 for AQ-128, and 0.2081 for RG, despite recording the largest evidence saving in the matrix (80.53%). This single configuration accounts for essentially the whole difference between the VANILLA SAGE and SAGE-OS column means: excluding it, SAGE-OS averages 0.3928 against 0.3918 for VANILLA SAGE. The diagnosis follows from (24). With λ fixed, the threshold probe Cℓ+1 = λdk (mℓ+1 − mℓ ) is scale-free in the probe cost but not in the achievable risk reduction. When the task is hard and the neighbourhood is extremely skewed, the observed advantage [Aℓ + 2rℓ ]+ is small at stage 32, even though a true advantage would have emerged later. The rule is correct given its inputs, but the inputs are uninformative at that stage. A bk,j , or an anytime λ that adapts to the observed spread of R confidence sequence in place of the stage-uniform bound, is the natural remedy and is left to future work. VII. C ONCLUSION AND L IMITATIONS We introduced SAGE, which casts decentralised peer selection as sequential evidence acquisition, and SAGE-OS, its optimal-stopping instantiation: select once a peer’s advantage over gossip is certified, revert to gossip as soon as further
probing cannot repay its cost. The stopping problem admits an optimal rule attained at a finite stage, and the anchor schedule is order-optimal in the peer-risk gap and the confidence level. The selector also carries a policy-level guarantee that it never returns a peer worse than gossip. We show that no such guarantee can hold for selectors that commit without a certificate. That asymmetry, with a separability threshold below which no probing budget improves on gossip, predicts what the experiments find. VANILLA SAGE reaches the same decisions by probing to exhaustion, at twice the cost. The operative decision is not which peer to rank first, but whether the evidence justifies ranking at all. The results also bound the claim: anchor risk is a noisy proxy for post-exchange utility, so SAGE-OS matches gossip cheaply rather than beating it. Each cell is a single matched run, so sub-point margins are ties; only the always-commitversus-abstain gap (≈ 2.3 points, 12/12 in direction on three metrics) and the ≈ 25-point Saving gap survive, and the worstclient lead of VANILLA SAGE is the most seed-sensitive claim reported here. The cost parameter λ is fixed and δ, M unswept; overhead is counted in evaluations rather than seconds;. A PPENDIX A P ROOFS This appendix collects the proofs of the results stated in Sections IV. Numbering follows the main text. Proof of Lemma 1 For a deviation threshold ϵ > 0, Hoeffding’s inequality gives probability at most 2 exp(−2mℓ ϵ2 /M 2 ) for a fixed peer and stage. Setting this to δ/(dk L) and applying a union bound over all peers and stages yields (7). Proof of Theorem 1 bk,j − rℓ and R b For any peer j ̸= ĵ1 , Rk,j ≥ R k,ĵ1 ≤ Rk,ĵ1 + rℓ . Because ĵ2 is the best empirical competitor, (8) implies bk,j − rℓ > R b R k,ĵ1 + rℓ for every j ̸= ĵ1 . Hence Rk,j > Rk,ĵ1 .
Proof of Proposition 1 On the uniform-confidence event, the empirical gap between the true best peer and any competitor is at least ∆k − 2rℓ . The stopping rule is therefore guaranteed if ∆k − 2rℓ > 2rℓ , i.e., rℓ < ∆k /4. Substituting (7) and rearranging yields (10). Proof of Theorem 2 Write ∆′ = ∆/M and construct two instances. Under P , ′ neighbour 1 has per-anchor loss M ·Ber( 21 − ∆2 ) and neighbour ′ 2 has M ·Ber( 12 + ∆2 ), so neighbour 1 is the minimiser and the risk gap is ∆; under Q the two are exchanged. Both instances are admissible, so a rule correct with probability 1 − δ on each must, writing A for the event that it outputs neighbour 2, satisfy P (A) ≤ δ and Q(Ac ) ≤ δ. The Bretagnolle–Huber inequality gives P (A) + Q(Ac ) ≥ 21 exp(−KL(P m , Qm )), 1 . The m anchors are i.i.d. and whence KL(P m , Qm ) ≥ log 4δ each yields one observation per neighbour, so KL(P m , Qm ) = m [KL(Ber(p), Ber(q)) + KL(Ber(q), Ber(p))] with p = 12 − ∆′ 1 ∆′ 2 2 , q = 2 + 2 . Using KL(Ber(a), Ber(b)) ≤ (a−b) /(b(1− ′2 b)) and p(1 − p) = q(1 − q) = (1 − ∆ )/4 bounds the bracket 1 by 8∆′2 /(1 − ∆′2 ). Combining, 8m∆′2 /(1 − ∆′2 ) ≥ log 4δ , ′ which rearranges to (11); the second inequality uses ∆ ≤ 1/2. Proof of Theorem 3 Every cost in (16) is bounded in absolute value by M + λdk mmax , so all conditional expectations exist and are finite and the recursion is well defined. We induct backwards on ℓ. At ℓ = L continuation is unavailable, so the remaining cost of any policy is JLsel or JLRG and VL is by construction the smaller of the two, establishing (i) at the horizon. Assume (i) holds at stage ℓ + 1. A policy at stage ℓ either stops, incurring Jℓsel or JℓRG , or continues, incurring the stage cost λdk (mℓ+1 − mℓ ) plus a remaining cost that by the induction hypothesis is at least E[Vℓ+1 | Fℓ ]; in either case its cost is at least min{Jℓsel , JℓRG , Jℓcont } = Vℓ . Conversely the policy that takes a minimising action at stage ℓ and behaves optimally thereafter attains Vℓ , proving (i) at stage ℓ. For (ii), the minimising action at τ ⋆ is by (18) a stopping action, and τ ⋆ ≤ L because stopping is forced at the horizon; the policy that continues before τ ⋆ and stops at τ ⋆ therefore attains V1 . Claim (iii) is the identity of the minimiser in (16) at ℓ = τ ⋆ . Proof of Proposition 2 b On the uniform-confidence event, Rk,ĵ1,ℓ ≤ R k,ĵ1,ℓ + rℓ and Rk,RG ≥ R̄ℓ − rℓ . Condition (20) makes the first quantity strictly smaller than the second. Proof of Theorem 4 Algorithm 1 returns a peer in exactly two ways. If it selects at some stage ℓ, condition (20) held, and Proposition 2 gives Rk,ȷ̂1,ℓ < Rk,RG on the Lemma 1 event. Otherwise it draws uniformly from Nkt , whose expected anchor risk is Rk,RG by definition. Both branches satisfy the stated inequality. The event holds with probability at least 1 − δ, and on its complement the risk is at most M , giving (21). For VANILLA SAGE, Theorem 1 gives Rk,ȷ̂1 = minj Rk,j ≤ Rk,RG whenever it selects.
Proof of Proposition 3 On the uniform-confidence event, Rk,RG ≤ R̄ℓ + rℓ and b minj Rk,j ≥ R k,ĵ1,ℓ − rℓ . Subtracting yields (23). Any probe continuation policy must pay at least Cℓ+1 before obtaining additional information, whereas perfect information could reduce the risk relative to gossip by at most the right-hand side of (23). Hence (24) makes further probing unable to recover its cost. Proof of Proposition 4 Any policy that probes evaluates all dk active neighbours on at least m1 anchors, incurring cost at least λdk m1 in riskequivalent units before observing anything. Its expected risk is at least minj Rk,j , attained only by an oracle that always selects the true minimiser. Its total cost is therefore at least λdk m1 + minj Rk,j , whereas immediate gossip costs Rk,RG . Condition (25) makes the former at least the latter. Proof of Proposition 5 Differentiating, ∂d [λd(mℓ+1 −mℓ )] = λ(m p ℓ+1 −mℓ ), a positive constant, while ∂d [2rℓ (d)] = M/(d 2mℓ log(2dL/δ)), which is positive but O(1/d). Condition (26) states exactly that the former dominates the latter, so µℓ is strictly increasing in dk . A larger µℓ makes the stopping test fire at the same or an earlier stage, giving monotonicity of ℓ⋆ . R EFERENCES [1] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. AISTATS, 2017, pp. 1273–1282. [2] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent,” in NeurIPS, 2017, pp. 5330–5340. [3] L. Yuan, Z. Wang, L. Sun, P. S. Yu, and C. G. Brinton, “Decentralized federated learning: A survey and perspective,” IEEE Internet of Things Journal, vol. 11, no. 21, pp. 34617–34638, 2024. [4] R. Ormándi, I. Hegedűs, and M. Jelasity, “Gossip learning with linear models on fully distributed data,” Concurrency and Computation: Practice and Experience, vol. 25, no. 4, pp. 556–571, 2013. [5] I. Hegedűs, G. Danner, and M. Jelasity, “Gossip learning as a decentralized alternative to federated learning,” in Distributed Applications and Interoperable Systems, 2019, pp. 74–90. [6] A. Koloskova, S. U. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in Proc. ICML, 2019, pp. 3478–3487. [7] N. Onoszko, G. Karlsson, O. Mogren, and E. L. Zec, “Decentralized federated learning of deep neural networks on non-IID data,” in ICML Workshop on Federated Learning for User Privacy and Data Confidentiality, 2021. [8] Y. Sui, J. Wen, Y. Lau, B. L. Ross, and J. C. Cresswell, “Find your friends: Personalized federated learning with the right collaborators,” in NeurIPS Workshop on Federated Learning: Recent Advances and New Challenges, 2022. [9] M. Fan, K. Li, T. Zhang, Q. Tian, and B. Geng, “PFedDST: Personalized federated learning with decentralized selection training,” in Proc. Int. Joint Conf. Neural Networks (IJCNN), 2025, pp. 1–8. [10] B. Soltani, V. Haghighi, Y. Zhou, Q. Z. Sheng, and L. Yao, “DFLStar: A decentralized federated learning framework with self-knowledge distillation and participant selection,” in Proc. ACM CIKM, 2024, pp. 2108– 2117. [11] N. Masmoudi and W. Jaafar, “OCD-FL: A novel communicationefficient peer selection-based decentralized federated learning,” IEEE Transactions on Vehicular Technology, vol. 74, no. 4, pp. 6856–6861, 2025.
[12] S. Kharrat, M. Canini, and S. Horváth, “DPFL: Decentralized personalized federated learning,” in Proc. AISTATS, 2025, pp. 5086–5094. [13] Y. Liu, Y. Shi, Q. Li, B. Wu, X. Wang, and L. Shen, “Decentralized directed collaboration for personalized federated learning,” in Proc. CVPR, 2024, pp. 23168–23178. [14] B. Jiang, J. Wu, G. Yue, X. Cui, J. Wang, and H. H. Song, “DFedMQ: Decentralized federated learning based on dynamic selection collaboration and topology optimization,” IEEE Internet Things J., vol. 12, no. 18, pp. 37682–37694, 2025. [15] N. Guo, Y. Pan, and Y. Yang, “Decentralized federated learning with local differential privacy and comprehensive neighbor selection,” in Proc. 14th Int. Conf. Communication and Network Security (ICCNS), 2024, pp. 21–28. [16] Q. Long, Q. Wang, C. Anagnostopoulos, and D. Bi, “Decentralized personalized federated learning based on a conditional ‘sparse-to-sparser’ scheme,” IEEE Trans. Neural Netw. Learn. Syst., vol. 36, no. 10, pp. 19160–19174, 2025. [17] L. Collins, H. Hassani, A. Mokhtari, and S. Shakkottai, “Exploiting shared representations for personalized federated learning,” in Proc. ICML, 2021, pp. 2089–2099. [18] C. Bucilă, R. Caruana, and A. Niculescu-Mizil, “Model compression,” in Proc. ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), 2006, pp. 535–541. [19] T. Lin, L. Kong, S. U. Stich, and M. Jaggi, “Ensemble distillation for robust model fusion in federated learning,” in NeurIPS, vol. 33, 2020, pp. 2351–2363.
[20] S. Dogan-Tusha, F. El Bouanani, and M. Qaraqe, “Optimal stopping theory-based online node selection in IoT networks for multi-parameter federated learning,” IEEE Trans. Mach. Learn. Commun. Netw., vol. 3, pp. 659–676, 2025, doi: 10.1109/TMLCN.2025.3567370. [21] Z. Li, S. Zou, and X. Chen, “On dynamic node cooperation strategy design for energy efficiency in hierarchical federated learning,” Electronics, vol. 12, no. 11, Art. no. 2362, 2023, doi: 10.3390/electronics12112362. [22] O. Maron and A. W. Moore, “Hoeffding races: Accelerating model selection search for classification and function approximation,” in NIPS, 1993, pp. 59–66. [23] E. Even-Dar, S. Mannor, and Y. Mansour, “Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems,” J. Mach. Learn. Res., vol. 7, pp. 1079–1105, 2006. [24] S. Mannor and J. N. Tsitsiklis, “The sample complexity of exploration in the multi-armed bandit problem,” J. Mach. Learn. Res., vol. 5, pp. 623–648, 2004. [25] J.-Y. Audibert, S. Bubeck, and R. Munos, “Best arm identification in multi-armed bandits,” in COLT, 2010, pp. 41–53. [26] E. Kaufmann, O. Cappé, and A. Garivier, “On the complexity of bestarm identification in multi-armed bandit models,” J. Mach. Learn. Res., vol. 17, no. 1, pp. 1–42, 2016. [27] Y. S. Chow, H. Robbins, and D. Siegmund, Great Expectations: The Theory of Optimal Stopping. Boston, MA: Houghton Mifflin, 1971. [28] G. Peskir and A. Shiryaev, Optimal Stopping and Free-Boundary Problems. Basel, Switzerland: Birkhäuser, 2006.