FEAST: Federated Shared-Space Training for Resource-Heterogeneous Clients

FEAST: Federated Shared-Space Training for Resource-Heterogeneous Clients Bostan Khan, Masoud Daneshtalab Mälardalen University, Västerås, Sweden

arXiv:2608.09250v1 [cs.LG] 10 Aug 2026

Abstract Federated learning (FL) must serve devices with varying computational capabilities. A fixed model cannot suit all devices, while training one model per deployment limit is costly. Federated supernet training instead learns one elastic model with differently sized subnetworks, then deploys a suitable one to each device. When client inference budgets differ, however, parameters exclusive to high-cost subnetworks are reachable by fewer clients. We propose FEAST, a federated sharedspace training framework that counters this imbalance by jointly training multiple subnetworks within each client’s limit. Budget-tailored sub-supernet routing sends only the relevant supernet portion, and sparse aggregation merges the returned parameter slices. The trained supernet directly serves the subnetworks used during federation and supports post-hoc extraction of additional subnetworks without federated retraining. We further show that independently assigning clients’ trainingdata volumes and inference budgets can distort accuracy– inference-cost comparisons in heterogeneous FL simulations, and introduce a one-parameter γ-allocation protocol to control this coupling. In our experimental setup, the SuperFedNAS and DeepFedNAS supernet training procedures remain near chance at 25M and reach at most 17.09% at 596M inference MACs; FEAST reaches 71.06% at 596M, 2.4 points above the strongest model-heterogeneous weight-sharing baseline at its largest tier. Across CIFAR-100, CINIC-10, and TinyImageNet200, FEAST achieves the highest population-averaged accuracy among the evaluated weight-sharing methods when each client receives its largest affordable subnetwork. Sub-supernet routing reduces aggregate model-parameter traffic by 6.8× relative to full-supernet transmission.

1

Introduction

Federated learning (FL) trains a shared model from decentralized data without moving raw examples to a central server (McMahan et al. 2017; Kairouz et al. 2021). Yet one architecture is a poor fit for devices with different computational capabilities (Kairouz et al. 2021; Li et al. 2020): a model small enough for constrained devices underuses more capable ones, whereas a large model may be infeasible for much of the population. Training a separate federation for each deployment limit is costly. Federated supernet training offers a train-once, deploy-many alternative: learn one elastic Copyright © 2027, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

network containing parameter-sharing subnetworks of different sizes, then serve a suitable subnetwork to each device. Prior federated-supernet methods, including SuperFedNAS (Khare et al. 2024) and DeepFedNAS (Khan and Daneshtalab 2026b), pursue this train-once, deploy-many objective. Client-specific deployment limits, however, create an optimization asymmetry: parameters shared by low-cost subnetworks are reachable by nearly all clients, whereas parameters exclusive to high-cost subnetworks are reachable only by the high-budget minority. The amount and distribution of data held by that minority further determine the effective training signal available to those parameters. Our central question is therefore how to train a directly served elastic model when client budgets and data allocation jointly produce highly unequal parameter exposure. We formulate budget-constrained federated supernet training in terms of one elastic parameter tensor, overlapping subnetworks, client-specific affordable sets, and budgetdependent parameter reachability; we refer to this setting as a federated shared model space (FSMS). To train it, we introduce FEAST (FEderAted Shared-space Training). On each mini-batch, a client jointly trains the globally smallest, an affordable random intermediate, and its largest affordable cached variant, using the local maximum to distill the smaller variants. Budget-tailored routing transmits only the parameter envelope spanning the client’s affordable variants, and position-wise sparse, sample-count-weighted aggregation maps returned slices into the global tensor. The resulting supernet directly serves the cached variants and supports post-hoc extraction of additional variants without federated retraining. Resource-heterogeneous simulations also assign each client a budget and training data, commonly generating them independently even though system and data heterogeneity can interact in practice (Maeng et al. 2022; Wang and Gao 2025). In a low-budget-heavy population, this independence gives the high-budget minority no larger expected data share, although only those clients can reach parameters exclusive to high-cost variants. We therefore introduce a one-parameter allocation family in which γ = 0 recovers budget-independent allocation and γ = 1 makes expected data share proportional to capped budget (Sec. 3.1). Figure 1 shows that changing only this allocation relationship materially changes the observed accuracy–inference-

(a) γ = 0: compute-independent

(b) γ = 1: compute-proportional

Top-1 accuracy (%)

70 60 50 40 HeteroFL ScaleFL FIARSE FEAST (Ours)

30 20 25

50

100

200

400 600

Compute budget (MACs, millions)

25

50

100

200

400 600

Compute budget (MACs, millions)

Figure 1: Effect of compute–data allocation on CIFAR100 (Krizhevsky 2009) accuracy over the shared ≥ 25MMAC range for FEAST, HeteroFL (Diao, Ding, and Tarokh 2021), ScaleFL (Ilhan, Su, and Liu 2023), and FIARSE (Wu et al. 2024). γ = 0 makes expected data volume independent of client budget, whereas γ = 1 makes it proportional to the capped budget. Changing only this relationship raises accuracy at each method’s largest evaluated point. cost curves of all four methods. The compute–data relationship is therefore a consequential evaluation choice, rather than a neutral implementation detail. Our contributions are: • We formulate budget-constrained federated supernet training as an FSMS and establish nested budget reachability. We characterize expected routed and activation mass and derive a conditional finite-horizon stationarity bound whose dependence on the minimum routed computation across served parameters makes the cost of unequal coverage explicit. • We propose FEAST, which combines local minimum– random–maximum co-training and in-place distillation with budget-tailored sub-supernet routing and sparse aggregation to improve accuracy across the directly served model range. • We introduce a γ-controlled allocation protocol for studying how client inference capability and training-data allocation jointly shape the accuracy–inference-cost relationship. • Across CIFAR-100, CINIC-10, and TinyImageNet-200, FEAST achieves the strongest population-averaged accuracy among the evaluated weight-sharing methods under largest-affordable serving. Its advantage persists under equal total training computation on CIFAR-100, while sub-supernet routing substantially reduces communication relative to full-supernet transmission.

2

Related Work

Federated NAS and federated supernets. Federated NAS performs architecture search over decentralized, often nonIID client data, while resource-aware variants additionally account for device constraints (He, Annavaram, and Avestimehr 2020; Yuan et al. 2022). DC-NAS systematically samples the supernet search space and applies channel pruning to reduce client training cost (Venkatesha et al. 2023); FINCH uses hierarchical search (Liu et al. 2024); and PerFedRLNAS and Peaches personalize client architectures (Yao and Li 2024; Yan et al. 2024). The closest predecessors to our trainonce, deploy-many setting are SuperFedNAS and DeepFed-

NAS. SuperFedNAS co-trains a supernet and uses predictorguided post-training search for deployment targets (Khare et al. 2024); DeepFedNAS replaces random sampling with a Pareto-guided training cache and uses its fitness function for predictor-free selection (Khan and Daneshtalab 2026a,b). Resource-aware one-shot methods already restrict each client to resource-feasible subnetworks during federation; HAPFNAS combines this assignment with server-side distillation and personalized search (Yang and Liu 2025). A recent supernet-only framework reinterprets residual networks as supernets and directly serves depth-truncated subnetworks matched to client capability (Chen, Chen, and Zhong 2025). Building on these capabilities, FEAST trains a single elastic model whose variants are served directly under clientspecific inference budgets. Because parameters used only by larger variants are reachable by fewer clients, FEAST co-trains multiple affordable variants within each client and routes only the parameter slice covering the variants that client can train. Elastic networks and shared parameter spaces. Centralized elastic networks provide the underlying training mechanisms. Universally Slimmable Networks combine the sandwich rule with in-place distillation (Yu and Huang 2019); Once-for-All trains once and specializes to hardware constraints (Cai et al. 2020); and BigNAS optimizes child models for direct deployment without fine-tuning (Yu et al. 2020). Weight-sharing NAS reduces search cost but can suffer optimization interference and unreliable inherited-subnetwork rankings (Bender et al. 2018; Xie et al. 2021). These methods assume centralized access to the full supernet. FEAST adapts their training principles to a budget-constrained federation, where only high-budget clients can reach parameters exclusive to large variants. Model-heterogeneous federated learning. Modelheterogeneous FL matches client workloads to local capability. HeteroFL uses nested width-scaled networks (Diao, Ding, and Tarokh 2021); FjORD uses ordered dropout (Horvath et al. 2021); FedRolex rotates model slices (Alam et al. 2022); ScaleFL adapts depth and width with self-distillation (Ilhan, Su, and Liu 2023); and FIARSE performs importance-aware extraction (Wu et al. 2024). OFA-FL jointly optimizes resource-specific subnetworks within one federated model (Varma et al. 2023), while FedEL progressively covers a fixed network using runtime-budgeted training windows (Zhang et al. 2025). Split-Mix instead forms larger inference models by ensembling multiple separately parameterized base models at inference (Hong et al. 2022), so it falls outside our weight-sharing quantitative comparison. These methods support heterogeneous client workloads. Within this broader line, FEAST focuses on unequal client exposure across overlapping regions of a structured depth-width-expansion supernet while serving variants directly from the shared tensor. Coupled system and data heterogeneity. FL research has long recognized that system and statistical heterogeneity can interact and bias participation or optimization (Kairouz et al. 2021; Li et al. 2020). Maeng et al. study their interdependence in federated recommendation (Maeng et al. 2022), while Wang and Gao analyze intertwined device and data

heterogeneity under stale updates (Wang and Gao 2025). Resource-heterogeneous evaluations nevertheless commonly specify compute tiers and data partitions separately. To our knowledge, no prior resource-heterogeneous FL evaluation introduces an explicit parameter controlling the dependence between expected client data volume and inference budget. Our γ-parameterized protocol provides this control and is applied identically to FEAST and all evaluated baselines.

3.1

3

Method

Resource-Heterogeneous Evaluation Protocol

Client population and MAC budgets. Client i has an inference budget bi , defined as the maximum per-example inference cost, measured in MACs, of any individual variant it may train or deploy. This per-variant ceiling does not bound cumulative local-pass cost, as discussed in Sec. 3.4. To model a controlled low-end-heavy population, we draw N budget ranks from Zipf(s = 1.2) and map them to [25M, 1500M] MACs; Pisces uses the same exponent for moderately skewed client latency (Jiang et al. 2022). Served variants span approximately 25M–600M MACs. Raw bi determines affordability, while allocation uses balloc = min(bi , Bcap ) with i Bcap = 600M, preventing capability beyond the served range from increasing allocation weight. Supplementary Sec. A gives the exact rank-to-budget mapping. γ-allocation. Standard simulations often construct client data partitions independently of client budgets. In a lowend-heavy population, this gives the smaller subset of clients that can train high-cost variants no larger expected data share, which can limit optimization of variant-exclusive parameters. We control the dependence between a client’s expected data volume and budget through
γ balloc i qi (γ) = PN balloc = min(bi , Bcap ), (1)
, i alloc γ b j j=1 where γ ≥ 0. Setting γ = 0 yields uniform base weights qi (0) = 1/N , while γ = 1 makes the initial expected data share proportional to the capped budget. We use γ = 1 as a conservative first-order default, not as a universal deployment law, and apply the same allocation protocol to every evaluated method. Budget-aware Dirichlet partition. Let Ntrain denote the number of examples in the client-training pool after excluding server validation and BN-calibration data, and let class k contain Nk examples. We draw its initial client proportions as

ck,i = αdata Nk qi (γ). (2) P Before integer assignment, E[e pk,i ] = qi (γ) and i ck,i = αdata Nk . Thus, γ changes the target mean vector while preserving total per-class precision. It also changes component variances and hence the realized variability of shard sizes and per-class client allocations. Because local optimizer-step counts and sample-weighted aggregation depend on realized shard size, comparisons across γ characterize the complete coupled allocation protocol rather than a data-quantity-only e k ∼ Dir(ck,1 , . . . , ck,N ) , p

intervention. Integer assignment uses qi (γ)Ntrain as a perclient balancing cap while producing disjoint shards, so q(γ) is a pre-integer volume target rather than the exact realized sample-share vector. For a balanced K-class dataset, we report αeff = αdata Ntrain /(KN ) and set αdata so that αeff = 0.45 on all three datasets. Supplementary Sec. A gives the complete assignment and balancing procedure.

3.2

Federated Shared Model Space

We formulate federated supernet training in terms of a shared elastic parameter tensor, a family of overlapping inferencebudget-matched variants activated from that tensor, and a federation rule that restricts each client to affordable variants and maps its returned parameter values to the corresponding global positions. We refer to this formulation as a federated shared model space (FSMS). Shared elastic family and fixed cache. The server maintains an OFA-style ResNet M(θ) with |θ| = 55.68M parameters. An architecture a = (d, e, w) selects stage depths, expansion ratios, and widths, activating a shared slice θa ⊆ θ; variants therefore maintain no private weights. As in elasticnetwork training (Cai et al. 2020; Yu and Huang 2019), batch-normalization statistics are recalibrated separately for each evaluated operating point. The four-stage supernet (S = 4) uses base channels [128, 256, 512, 1024], additionalblock counts dℓ ∈ {0, . . . , 8}, stage-level expansion ratios eℓ ∈ {0.10, 0.14, 0.18, 0.22, 0.25}, and width multipliers {0.1, 0.2, . . . , 1.0}. Let H denote the resulting architecture space. From H, FEAST uses a fixed cache A ⊂ H of 56 variants spanning approximately 25M–600M MACs, generated once before federation by retargeting the Pareto-guided DeepFedNAS procedure (Khan and Daneshtalab 2026b,a). The cache fixes local choices, routing, and the reported serving and evaluation points; no architecture search occurs during federation. It does not delimit deployment: additional subnetworks can be extracted from the trained tensor and BN-recalibrated without further federated training, although we evaluate only A. Supplementary Sec. B gives the search space, offline objective, and cache construction. Affordable variants and structural asymmetry. Client i may activate only Ai = {a ∈ A | MAC(a) ≤ bi } ,

(3)

which we call its affordable variant set. In every realized population used here, Ai is nonempty and contains the globally smallest cached variant. Affordability uses the raw client budget bi , not the allocation-capped quantity balloc in Eq. (1); i the cap affects data allocation only. A parameter position is reachable by client i when some variant in Ai activates it. Consequently, low-cost regions are shared broadly, whereas high-cost-exclusive regions depend on the high-budget minority. FEAST addresses this structural asymmetry through budget-tailored routing and multi-variant co-training. Figure 2 summarizes one round. In the following, t indexes federation rounds and τ indexes local mini-batches. We next describe budget-tailored routing and sparse aggregation (Sec. 3.3), followed by local multi-variant co-training (Sec. 3.4).

Figure 2: One FEAST round. (a) The server routes each selected client a depth-width-bounded sub-supernet covering its affordable variants. (b) On each mini-batch, the client trains the global minimum, its local maximum, and an affordable random intermediate when available; the local maximum supplies detached soft targets to the smaller variants. (c) Returned slices are mapped to global positions and combined by sample-count-weighted sparse FedAvg.

3.3

FEAST: Budget-Tailored Sub-Supernet Routing

nested leading slices, bi ≤ bj implies

Client-specific routing. For selected client i, FEAST derives coordinate-wise depth and width bounds over its affordable set Ai : d∗i,ℓ = max dℓ (a),

ℓ = 1, . . . , S,

∗ wi,j = max wj (a),

j = 0, . . . , S.

a∈Ai a∈Ai

(4)

These maxima define the tightest depth–width envelope, under the implemented parameterization, that contains every affordable cached variant. They may arise from different variants, so the envelope can represent uncached combinations, but local sampling remains restricted to Ai . The server instantiates the reduced supernet, sizes retained tensors to support all globally allowed stage-level expansion ratios, copies the corresponding leading slices of the global weights, and records a map Ωi from local to global positions. We denote the covered global positions by Ui . If the bounds are global, routing reduces to the full supernet. Exact tensor construction is provided in Supplementary Sec. C. Nested routed support. For global position u, let ri (u) = I{u ∈ Ui }

(5)

indicate routing eligibility. Proposition 1 (Nested budget reachability). Because affordability is thresholded by budget and routed tensors are

Ai ⊆ Aj ,

Ui ⊆ Uj ,

ri (u) ≤ rj (u)

∀u.

(6)

Hence, positions exclusive to larger variants are routed only by an upper tail of the budget-ordered population. Supplementary Sec. F provides the proof and finite-population coverage analysis. Sparse sample-weighted aggregation. Let Di denote client i’s realized local shard and ni = |Di |. In round t, the server samples a cohort St of m clients uniformly without replacement from the N clients. Let θ̄i′ [u] be client i’s returned value mapped to global position u. The server averages each position only over selected clients whose routed envelopes contain it: P ′ i∈St ni θ̄i [u]    u∈U i P , ∃i ∈ St : u ∈ Ui , θ t+1 [u] = (7) i∈St ni    t u∈Ui θ [u], otherwise.

Normalization is therefore position-specific and samplecount-weighted; positions not routed in the round retain their previous global values. Aggregation follows routed coverage rather than local activation. Thus, a routed but unactivated position is still included through its returned tensor value. Supplementary Secs. C and F give the accumulator implementation and routed-versus-activated analysis.

Communication accounting. Ignoring metadata and using the same parameter precision in both directions, routing Pchanges the full-supernet round-trip payload 2mP to 2 i∈St Pi , where client i receives Pi of P parameters. Section 4.3 reports the reductions; Supplementary Sec. C gives the derivation.

3.4

FEAST: Local Multi-Variant Co-Training

Budget-conditioned variant selection. Figure 2(b) illustrates the local rule. On each mini-batch, client i trains the globally smallest cached variant, its largest affordable variant, and one affordable random intermediate when one exists. The two endpoints are amin = arg min MAC(a), a∈A

amax = arg max MAC(a). i

(8)

a∈Ai

Because amin ∈ Ai for every realized client, all selected clients optimize the same low-cost endpoint, while amax i directly optimizes the highest-cost endpoint permitted by bi . Let Aint contain the cached variants whose MAC costs lie i strictly between these endpoints. If this set is nonempty, the client samples arand uniformly from it for each mini-batch i,τ τ ; otherwise, the intermediate pass is skipped. When the endpoints coincide, the step reduces to supervised training of amin . Local objective and distillation. The same mixed-label tuple (x̃, ya , yb , λmix ), produced by the mixup/CutMix augmentation described in Sec. 4.1, is reused across all applicable passes. Let zi,τ (a) = f (x̃; θi , a); for logits z, define Lsup (z) = λmix LCE (z, ya ) + (1 − λmix )LCE (z, yb ), max p̂max ))) , i,τ = softmax(sg(zi,τ (ai X LKD (z, p̂) = − p̂c log softmax(z)c , c

Lstu (z) = (1 − ρkd )Lsup (z) + ρkd LKD (z, p̂max i,τ ). (9)

Here sg(·) denotes stop-gradient. The local maximum is evaluated first and optimized only with Lsup ; its detached distribution supervises the global minimum and, when present, the random intermediate through Lstu . We use ρkd = 0.5 and temperature T = 1 (no scaling). The client backpropagates each applicable loss, accumulates the gradients, clips their combined L2 norm to 10, and takes one optimizer step. This adapts in-place elastic-network distillation by using each client’s local maximum, rather than the globally largest variant, as the teacher (Yu et al. 2020; Yu and Huang 2019). The complete casewise objective and client procedure are given in Supplementary Sec. D. Although each activated variant satisfies MAC(a) ≤ bi , the cumulative cost of the sequential passes is not constrained by bi . Supplementary Sec. D gives the complete computation model. Structural exposure and finite-horizon result. Let V denote the set of up to three variants trained on one local minibatch, and let νi be its distribution for client i. Define the

expected activation multiplicity per local optimization step " # X (10) hi (u) = EV∼νi I{u ∈ θa } bi . a∈V

Here ri (u) controls routing and aggregation eligibility, whereas hi (u) counts expected local variant-activation multiplicity and may Pexceed one. Define the routed sample mass Mtroute (u) = n r (u) and the expected activation i∈S Pt i i mass Mtexp (u) = i∈St ni hi (u). Proposition 2 (Expected exposure and allocation). Conditioned on the realized budgets and local sample counts, uniform cohort sampling gives mX E[Mtroute (u)] = ni ri (u), N i (11) mX E[Mtexp (u)] = ni hi (u). N i

For the idealized pre-integer counterparts, the corresponding sums replace ni by N train qi (γ), and the routed allocation P share Wuroute (γ) = i qi (γ)ri (u) is nondecreasing in γ. This does not imply monotone activation exposure because hi (u) can change nonmonotonically with the affordable sampling pool. Theorem 1 (Routed-scale finite-horizon supervised stationarity). On the served support and before BN recalibration, let Fsup be the sample-weighted supervised multivariant reference objective, excluding KD, and assume it is lower bounded by Finf and LF -smooth. Let βi (u) be client i’s expected position-wise aggregation weight and Biloc its local P step count. Define ψu = i βi (u)Biloc and Ψ = diag(ψu ). Let 0 < ψmin ≤ ψmax denote the minimum and P maximum of ψu over served positions. Set HT = t<T ηt , P QT = t<T ηt2 , and ∆F = Fsup (θ 0 ) − Finf . Assume that the conditional mean update equals −ηt Ψ∇Fsup (θ t ) plus a discrepancy whose norm is at most ηt ε, and that the corresponding centered update noise, after division by ηt , has 2 second moment at most σround . If 0 < ηt ≤ (4LF ψmax )−1 , then 1 X ηt E∥∇Fsup (θ t )∥22 HT t<T   2 ∆F ε2 LF QT (ε2 + σround ) + 2 + ≤O . (12) ψmin HT ψmin ψmin HT This conditional result makes the dependence on ψmin explicit: a smaller minimum routed computation scale loosens the finite-horizon guarantee. The residual also depends on discrepancy and round noise, and the theorem does not certify a small ε. For high-cost-exclusive positions, increasing γ shifts idealized allocation toward the high-budget clients that route them. Because ψu also depends on aggregation weights and local step counts, this protocol change can affect ψu , but the theorem neither proves monotonicity of ψu nor predicts the numerical accuracy gap. Empirically, the CIFAR-100 largest-budget-minus-smallest-budget accuracy gap changes from −4.29 to +6.17 percentage points as γ increases from 0 to 1. Supplementary Sec. F gives exact assumptions, constants, proofs, and realized-partition qualifications.

4

Experiments

We test compute–data allocation, deployment accuracy across budgets and clients, and the mechanisms underlying FEAST. Supplementary Sec. E gives dataset settings, posthoc extraction, cost controls, parameter footprints, and full sensitivity results; communication is derived in Supplementary Sec. C.

4.1

Experimental Setup

We evaluate CIFAR-100 (Krizhevsky 2009), CINIC-10 (Darlow et al. 2018), and TinyImageNet-200 (Le and Yang 2015) with 100 clients, 10 sampled per round, one local epoch, batch size 64, and 4000 rounds. Budgets follow Zipf(s = 1.2) over 25M–1500M MACs; allocation uses the 600M cap, γ = 1, and matched αeff = 0.45. All methods use RandAugment(2, 6) with alternating Mixup and CutMix and matched optimization except FIARSE, which retains its original zero-weight-decay setting. For every method, we select the best validation checkpoint and deterministically recalibrate BN statistics using disjoint server-held samples. Supplementary Sec. E gives additional dataset and optimization details. We compare FEAST with HeteroFL (Diao, Ding, and Tarokh 2021), ScaleFL (Ilhan, Su, and Liu 2023), and FIARSE (Wu et al. 2024) at measured native operating points without interpolation: 56 cached FEAST variants, five HeteroFL widths, four ScaleFL depth–width levels, and FIARSE’s continuous mask family. We additionally transfer SuperFedNAS (SFN) (Khare et al. 2024) and DeepFedNAS (DFN) (Khan and Daneshtalab 2026b) to our expanded supernet and experimental setting, retaining their random and Pareto-path samplers and MaxNet’s cosine-annealed, overlap-aware aggregation. MACs measure one served variant’s per-example inference cost; the ceilings do not bound cumulative training, memory, latency, or energy. Supplementary Sec. E gives complete adaptation and operating-point details.

4.2

Allocation and Deployment Accuracy

Allocation. Changing only γ from 0 to 1 raises the largestmodel accuracy of FEAST, HeteroFL, ScaleFL, and FIARSE by 12.10, 20.66, 23.45, and 15.91 points, respectively (Fig. 1). For FEAST, the 596M result progresses from 58.96% at γ = 0 to 63.79%, 65.76%, 71.06%, and 74.83% at γ ∈ {0.25, 0.5, 1, 1.5}, showing gradual recovery. γ = 1 is a proportional default, not the best-performing sweep value (complete sweep in Supplementary Sec. E). At each method’s largest evaluated point, FEAST remains ahead of the strongest result among HeteroFL, ScaleFL, and FIARSE under both tested allocation settings, with a 6.22point lead at γ = 0 and a 2.41-point lead at γ = 1. Budgets and clients. Figure 3 shows that FEAST peaks at 72.61% on CIFAR-100, 85.19% on CINIC-10, and 53.94% on TinyImageNet. Across the shared ≥ 25M-MAC range, its smallest-to-largest accuracy changes are +6.17, +6.03, and +8.75 percentage points, whereas the corresponding weight-sharing baseline ranges are +20.07–+44.03, +19.81–+46.42, and +15.66–+33.74 points, respectively.

Table 1 reports largest-affordable serving over the fixed client population. For this metric, HeteroFL and ScaleFL use their fixed native tiers, whereas FIARSE is evaluated on a dense measured MAC grid over its continuous mask family. FEAST leads the strongest weight-sharing baseline by 12.61, 26.09, and 9.44 points on CIFAR-100, CINIC-10, and TinyImageNet, respectively. On CIFAR-100, restricting FEAST to four cached points aligned separately with the operating points effectively served by HeteroFL or ScaleFL retains approximately 96% and 98% of the corresponding population margins. The full 56-point cache adds only 1.08 and 0.53 accuracy points, respectively. This control isolates serving density; the residual margins still reflect complete-method differences in training and model space (Supplementary Sec. E). Post-hoc extraction. Fourteen uncached CIFAR-100 variants in the 25M–52M region have a mean absolute gap of 1.14 points from the cached curve, and the 30M variant reaches 64.35%, without further federated training. Reusing the architecture set on CINIC-10 and TinyImageNet gives gaps of 1.34 and 1.79 points, respectively (scope and extraction checks in Supplementary Sec. E).

4.3

Training Mechanisms and Controls

Training rule. Endpoint-only rules perform poorly away from their trained endpoints (Table 2). Relative to co-training both endpoints with KD, full FEAST raises the 50M, 229M, 408M, and 596M variants by 5.17, 9.43, 8.22, and 0.97 points while remaining within 0.13 points at 25M, isolating the contribution of random-intermediate coverage. Table 3 tests whether the training procedures of the two closest federated-supernet predecessors remain effective when transferred to the 25M–596M shared model space and evaluated under our common federation protocol. We retain each sampler together with MaxNet’s cosine-annealed, overlap-aware aggregation, so the comparison is a crosssetting stress test rather than a native-setting reproduction. All four transfers remain near chance at 25M; at 596M, the strongest reaches 17.09% versus FEAST’s 71.06%, a 53.97point difference. The result shows that these predecessor training procedures do not automatically extend to the expanded shared model space and client-heterogeneity setting, motivating FEAST’s local multi-variant co-training rule; performance in their native settings is outside the comparison’s scope. Training computation and parameter footprint. Under the analytic forward-plus-backward convolution-MAC proxy, Dataset CIFAR-100 CINIC-10 TinyImageNet

HeteroFL ScaleFL FIARSE FEAST

∆best

67.74 80.96 48.18

+12.61 +26.09 +9.44

41.50 54.87 27.38

35.78 52.16 25.83

55.13 53.91 38.74

Table 1: Population-averaged test accuracy (%) under largestaffordable serving for the fixed Zipf(s = 1.2) client population. ∆best is the FEAST margin over the strongest weightsharing baseline.

CIFAR-100

CINIC-10

Test accuracy (%)

TinyImageNet-200 55

70

80

60

50 45

70

40

50

35

60

30

40 50 FEAST HeteroFL ScaleFL FIARSE

30 20 25

50

100

200

25 20

40

15

400 600

25

50

MACs (M)

100

200

400 600

25

50

MACs (M)

100

200

400 600

MACs (M)

Figure 3: Accuracy at every measured operating point under γ = 1 for FEAST and the three weight-sharing baselines. Lines connect measured points only to guide the eye; sub-25M points lie outside FEAST’s studied deployment range. Training rule

25M

50M

229M

408M

596M

Global min. only Local max. only Global min. + local max. Global min. + local max. + KD Full FEAST

61.71 30.87 64.14 65.02 64.89

47.63 37.81 60.25 60.43 65.60

34.68 57.46 61.90 62.39 71.82

33.12 60.62 62.55 63.72 71.94

33.46 64.99 70.36 70.09 71.06

Table 2: CIFAR-100 component analysis under otherwise identical settings. Global min. denotes the cache-wide minimum variant, whereas local max. denotes each client’s largest affordable cached variant. Bold marks the highest accuracy in each column. Training strategy

25M

50M

229M

408M

596M

SFN, unconstrained DFN, unconstrained SFN, budget-constrained DFN, budget-constrained FEAST

1.05 1.05 1.03 1.00 64.89

1.01 1.06 1.21 1.09 65.60

0.92 1.25 2.61 3.00 71.82

2.32 3.11 9.40 10.86 71.94

5.19 4.46 16.76 17.09 71.06

Table 3: CIFAR-100 transfer results with each method’s sampler and MaxNet cosine-annealed, overlap-aware aggregation. Constrained variants additionally use our client budgets and γ = 1 allocation. Random classification accuracy is 1%. FEAST totals 31.01 PMACs, 1.56× its single-variant reference and 2.07×, 2.04×, and 1.03× the HeteroFL, ScaleFL, and FIARSE proxies. Matching this total gives baseline population averages of 44.44%, 39.23%, and 55.42%, leaving FEAST’s 67.74% ahead by 23.3, 28.5, and 12.3 points with 100/100 client wins. At 596M, FEAST’s training envelope is 35.60M parameters versus 11.22M–11.27M baseline payloads; its deployed model is 11.78M. Supplementary Sec. E gives proxy definitions and full footprint tables. Communication and sensitivity. Relative to transmitting its full 55.68M-parameter supernet, FEAST routing reduces the mean model-parameter payload to 8.17M parameters and aggregate model-parameter traffic by 6.8×; per-client-round model-parameter reductions average 43.8× (median 22.9×,

maximum 111×). Across s ∈ [0.8, 1.5], 596M accuracy remains 70.29–74.54%. Across four Dirichlet settings, FEAST beats FIARSE at all 20 matched anchors, with 25M-to-596M changes of 5.77–7.37 versus 21.25–23.25 points (full results in Supplementary Sec. E).

5

Conclusion

Federated supernet training offers a train-once, deploy-many route for client populations with heterogeneous deployment budgets, but our cross-setting stress test shows that the evaluated predecessor training procedures do not extend to a wider, budget-conditioned shared space. That broader setting creates unequal training exposure: parameters exclusive to high-cost variants are reachable only by the high-budget minority, and their effective training signal also depends on how data are distributed across budgets. We make this dependence explicit through the γ-controlled allocation protocol and formulate the setting through an elastic parameter space with client-specific affordability and nested parameter reachability. FEAST addresses the resulting optimization and communication challenges through local multi-variant cotraining, in-place distillation, budget-tailored sub-supernet routing, and position-wise sample-count-weighted aggregation. Across CIFAR-100, CINIC-10, and TinyImageNet-200, FEAST achieves the strongest population-averaged accuracy among the evaluated weight-sharing methods under largestaffordable serving. Sub-supernet routing substantially reduces aggregate model-parameter traffic relative to fullsupernet transmission. Future work should reduce the overhead of local multi-variant co-training and test the formulation on larger architectures and additional modalities.

References

Alam, S.; Liu, L.; Yan, M.; and Zhang, M. 2022. FedRolex: model-heterogeneous federated learning with rolling submodel extraction. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22. Curran Associates Inc. Bender, G.; Kindermans, P.-J.; Zoph, B.; Vasudevan, V.; and Le, Q. 2018. Understanding and Simplifying One-Shot Ar-

chitecture Search. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, 550–559. PMLR. Cai, H.; Gan, C.; Wang, T.; Zhang, Z.; and Han, S. 2020. Once-for-All: Train One Network and Specialize It for Efficient Deployment. In International Conference on Learning Representations (ICLR). Chen, Y.; Chen, D.; and Zhong, C. 2025. A Supernet-Only Framework for Federated Learning in Computationally Heterogeneous Scenarios. Applied Sciences, 15(10). Darlow, L. N.; Crowley, E. J.; Antoniou, A.; and Storkey, A. J. 2018. CINIC-10 Is Not ImageNet or CIFAR-10. arXiv preprint arXiv:1810.03505. Diao, E.; Ding, J.; and Tarokh, V. 2021. HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients. In International Conference on Learning Representations (ICLR). He, C.; Annavaram, M.; and Avestimehr, S. 2020. FedNAS: Federated Deep Learning via Neural Architecture Search. CoRR, abs/2004.08546. Hong, J.; Wang, H.; Wang, Z.; and Zhou, J. 2022. Efficient Split-Mix Federated Learning for On-Demand and In-Situ Customization. In International Conference on Learning Representations. Horvath, S.; Laskaridis, S.; Almeida, M.; Leontiadis, I.; Venieris, S.; and Lane, N. 2021. FjORD: Fair and accurate federated learning under heterogeneous targets with ordered dropout. Advances in Neural Information Processing Systems, 34: 12876–12889. Ilhan, F.; Su, G.; and Liu, L. 2023. ScaleFL: ResourceAdaptive Federated Learning with Heterogeneous Clients. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 24532–24541. Jiang, Z.; Wang, W.; Li, B.; and Li, B. 2022. Pisces: Efficient Federated Learning via Guided Asynchronous Training. In Proceedings of the 13th Symposium on Cloud Computing, SoCC ’22, 370–385. ACM. Kairouz, P.; McMahan, H. B.; Avent, B.; Bellet, A.; Bennis, M.; Bhagoji, A. N.; Bonawitz, K.; Charles, Z.; Cormode, G.; Cummings, R.; et al. 2021. Advances and Open Problems in Federated Learning. Foundations and Trends in Machine Learning, 14(1–2): 1–210. Khan, B.; and Daneshtalab, M. 2026a. DeepFedNAS: Efficient Hardware-Aware Architecture Adaptation for Heterogeneous IoT Federations via Pareto-Guided Supernet Training. arXiv:2601.15127. Khan, B.; and Daneshtalab, M. 2026b. DeepFedNAS: Pareto Optimal Supernet Training for Improved and Predictor-Free Federated Neural Architecture Search. In Proceedings of the 34th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 59–64. i6doc.com. ISBN 9782875870964. Khare, A.; Agrawal, A.; Annavajjala, A.; Behnam, P.; Lee, M.; Latapie, H.; and Tumanov, A. 2024. SuperFedNAS: Cost-Efficient Federated Neural Architecture Search for OnDevice Inference. In European Conference on Computer Vision (ECCV), 161–179. Springer.

Krizhevsky, A. 2009. Learning Multiple Layers of Features from Tiny Images. Technical report, University of Toronto. Le, Y.; and Yang, X. 2015. Tiny ImageNet Visual Recognition Challenge. Stanford CS231n course report. Li, T.; Sahu, A. K.; Zaheer, M.; Sanjabi, M.; Talwalkar, A.; and Smith, V. 2020. Federated Optimization in Heterogeneous Networks. In Proceedings of Machine Learning and Systems, volume 2, 429–450. Liu, J.; Yan, J.; Xu, H.; Wang, Z.; Huang, J.; and Xu, Y. 2024. Finch: Enhancing Federated Learning With Hierarchical Neural Architecture Search. IEEE Transactions on Mobile Computing, 23(5): 6012–6026. Maeng, K.; Lu, H.; Melis, L.; Nguyen, J.; Rabbat, M.; and Wu, C.-J. 2022. Towards Fair Federated Recommendation Learning: Characterizing the Inter-Dependence of System and Data Heterogeneity. In Proceedings of the 16th ACM Conference on Recommender Systems (RecSys), 156–167. ACM. McMahan, H. B.; Moore, E.; Ramage, D.; Hampson, S.; and y Arcas, B. A. 2017. Communication-Efficient Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 1273–1282. PMLR. Varma, K.; Diao, E.; Roosta, T.; Ding, J.; and Zhang, T. 2023. Once-for-all federated learning: Learning from and deploying to heterogeneous clients. In International Workshop on Federated Learning for Distributed Data Mining. Venkatesha, Y.; Kim, Y.; Park, H.; and Panda, P. 2023. Divide-and-conquer the NAS puzzle in resource-constrained federated learning systems. Neural Networks, 168: 569–579. Wang, H.; and Gao, W. 2025. Tackling Intertwined Data and Device Heterogeneities in Federated Learning with Unlimited Staleness. Proceedings of the AAAI Conference on Artificial Intelligence, 39(20): 21080–21089. Wu, F.; Wang, X.; Wang, Y.; Liu, T.; Su, L.; and Gao, J. 2024. FIARSE: Model-Heterogeneous Federated Learning via Importance-Aware Submodel Extraction. In Advances in Neural Information Processing Systems, volume 37, 115615– 115651. Xie, L.; Chen, X.; Bi, K.; Wei, L.; Xu, Y.; Wang, L.; Chen, Z.; Xiao, A.; Chang, J.; Zhang, X.; and Tian, Q. 2021. WeightSharing Neural Architecture Search: A Battle to Shrink the Optimization Gap. ACM Comput. Surv., 54(9). Yan, J.; Liu, J.; Xu, H.; Wang, Z.; and Qiao, C. 2024. Peaches: Personalized Federated Learning With Neural Architecture Search in Edge Computing. IEEE Transactions on Mobile Computing, 23(11): 10296–10312. Yang, A.; and Liu, Y. 2025. Heterogeneity-Aware Personalized Federated Neural Architecture Search. Entropy, 27(7): 759. Yao, D.; and Li, B. 2024. PerFedRLNAS: One-for-All Personalized Federated Neural Architecture Search. Proceedings of the AAAI Conference on Artificial Intelligence, 38(15): 16398–16406. Yu, J.; and Huang, T. S. 2019. Universally Slimmable Networks and Improved Training Techniques. In Proceedings of

the IEEE/CVF International Conference on Computer Vision (ICCV). Yu, J.; Jin, P.; Liu, H.; Bender, G.; Kindermans, P.-J.; Tan, M.; Huang, T.; Song, X.; Pang, R.; and Le, Q. 2020. BigNAS: Scaling Up Neural Architecture Search with Big SingleStage Models. In European Conference on Computer Vision (ECCV), 702–717. Springer. Yuan, J.; Xu, M.; Zhao, Y.; Bian, K.; Huang, G.; Liu, X.; and Wang, S. 2022. Resource-Aware Federated Neural Architecture Search over Heterogeneous Mobile Devices. IEEE Transactions on Big Data, 1–11. Zhang, L.; Chen, B.; Bian, J.; Wang, L.; and Xu, J. 2025. FedEL: Federated Elastic Learning for Heterogeneous Devices. In Advances in Neural Information Processing Systems, volume 38, 35665–35696.

Supplementary Material for FEAST: Federated Shared-Space Training for Resource-Heterogeneous Clients Bostan Khan, Masoud Daneshtalab Mälardalen University, Västerås, Sweden

Supplementary overview. This supplementary material provides the complete protocol, implementation, experimental, and theoretical details supporting the main paper. Section A gives the client-budget and partition construction; Sec. B describes the shared model space, fixed variant cache, and BN-calibration protocol; Sec. C gives sub-supernet routing, sparse aggregation, and communication analysis; Sec. D provides the complete local co-training procedure and training-computation model; Sec. E reports additional experimental details, post-hoc extraction, cost controls, parameter footprints, and sensitivity results; and Sec. F provides the structural and finite-horizon analysis.

A

Client Budget Generation and Partition Realization

Client population and MAC budgets. Client i receives a budget bi , defined as the maximum per-example inference MAC cost of any individual variant that it may train or deploy. We draw its resource rank from r−s Pr[rank = r] = PR , r ∈ {1, . . . , R}, (1) −s ℓ=1 ℓ with R = N and s = 1.2, following the moderate-skew setting used by Pisces (Jiang et al. 2022). Ranks represent budget levels rather than client identities, so several clients may draw the same rank. We map rank ri to a jittered continuous budget in [Bmin , Bmax ] = [25M, 1500M]:   ∆B ∆B Bmax − Bmin , ϵi ∼ U − , , ∆B = R−1 2 2 (2) bi = clip(Bmin + (ri − 1)∆B + ϵi ; Bmin , Bmax ) , where clip(x; L, U ) = min{U, max{L, x}}. The raw budget bi controls variant affordability. Data allocation uses Bcap = 600M MACs, the approximate served-model ceiling, so capability above the served range does not further increase allocation weight. γ-allocation.

Define
γ balloc i

, alloc γ j=1 bj

qi (γ) = PN

balloc = min(bi , Bcap ), (3) i

Copyright © 2027, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

where γ ≥ 0. Here, γ = 0 gives uniform allocation weights and γ = 1 gives weights proportional to capped budgets. Budget-aware Dirichlet partition. Let Ntrain denote the client-training pool after excluding server-held data, and let class k have a shuffled index set Ik of size Nk . We draw e k ∼ Dir(ck,1 , . . . , ck,N ) , p ck,i = αdata Nk qi (γ). (4) Before assigning class k, the implementation sets pek,i = 0 for clients whose accumulated count has reached qi (γ)Ntrain , and renormalizes the remaining entries to obtain pk . It then forms the first N − 1 integer split points    X  i   tk,i = Nk pk,j  , i = 1, . . . , N − 1, (5) j=1

and partitions the shuffled indices contiguously. The final segment extends to the end of Ik , so every example is assigned exactly once. The quantity qi (γ)Ntrain is a pre-class balancing cap, not an exact realized target. Whole-class segments can move a client above the cap, while masking and renormalization can leave another client below it and introduce class-order dependence. The complete partition is redrawn if any client receives fewer than ten examples. Before masking, ck,i E[e pk,i ] = PN = qi (γ), (6) j=1 ck,j

whereas the final integer shares can differ because of balancing, sequential class processing, integer splitting, and rejection resampling. The initial draw has total concentration sk =

N X i=1

ck,i = αdata Nk .

(7)

Thus, changing γ changes the target mean vector while preserving total per-class precision, although component-level variability changes with qi (γ). For comparison with a conventional symmetric Dirichlet over N clients, we report sk αdata Nk αeff,k = = , N N αdata Ntrain αeff = for a balanced K-class dataset. KN (8)

The CIFAR-100 realized client-size and local-step ranges are reported in Sec. F.5.

B

Federated Shared Model Space and Fixed Variant Cache

Elastic model and search space. The exact architecture choices for the 55.68M-parameter OFA-style ResNet described in the main paper are as follows. The model contains S = 4 elastic stages with base channels [128, 256, 512, 1024] and choices dℓ ∈ {0, . . . , 8}, ℓ = 1, . . . , S, eℓ ∈ {0.10, 0.14, 0.18, 0.22, 0.25}, ℓ = 1, . . . , S, wj ∈ {0, . . . , 9}, j = 0, . . . , S.

(9)

Here, dℓ is the additional stage depth, eℓ is a stagelevel expansion ratio, and wj indexes width multipliers {0.1, 0.2, . . . , 1.0} for the stem and four stages. These choices define the architecture space H. Fixed cache and offline construction. FEAST uses a fixed cache A ⊂ H of 56 architectures spanning approximately 25M–600M MACs. For each target budget Bν , the Pareto-guided DeepFedNAS procedure (Khan and Daneshtalab 2026b,a) selects a⋆ν = arg max FDFN (a) a∈H

s.t.

MAC(a) ≤ Bν ,

ρ(a) ≤ ρ0,ν .

(10)

The cited work defines the training-free fitness FDFN and effectiveness measure ρ. We reuse this offline construction procedure at the deployment budgets studied here; federation itself performs no architecture search. Client i can activate Ai = {a ∈ A | MAC(a) ≤ bi } .

(11)

Affordability uses the raw budget bi , whereas balloc affects i only data allocation.

B.1

Additional cache-generation details

Expansion is selected once per stage. Each target uses a genetic algorithm with population 256, 512 generations, mutation probability 0.3, feasibility-preserving initialization and mutation, tournament selection, single-point crossover, and elitism. Table 1 summarizes the main search and lowcompute extension. MACs are recomputed under each dataset’s active input and stem configuration; the TinyImageNet cache therefore spans 27M–601M MACs, explaining its slightly higher largest operating point. BN calibration for evaluation. For every evaluated operating point, BN running statistics are reset and recalibrated with the same server-held samples and image-level transformations in a fixed order; batch-level Mixup and CutMix are disabled during calibration.

Segment

Realized range

Variants

Main Low-compute extension

50M–596M 25M–75M

50 6

0.31 256/512 0.40 256/512

56

–

Merged and MAC-sorted 24.96M–595.67M

ρ0

Pop./gen.

–

Table 1: Construction of the fixed CIFAR-100/CINIC-10 variant cache. The effectiveness ceiling is relaxed for the low-compute extension to make targets below 50M MACs feasible; the search segment extends to 75M to provide overlap with the main cache during merging.

C Sub-Supernet Construction, Sparse Aggregation, and Communication Analysis Routing envelope and construction. The server samples a cohort St of m clients in round t and derives client-specific depth and width bounds from Ai : d∗i,ℓ = max dℓ (a),

ℓ = 1, . . . , S,

∗ wi,j = max wj (a),

j = 0, . . . , S.

a∈Ai

a∈Ai

(12)

The maxima may come from different cached variants, so the routed envelope can represent uncached combinations, although local sampling remains restricted to Ai . No separate expansion bound is used: each retained bottleneck supports the globally allowed expansion choices at its routed width, and a selected eℓ activates a leading channel slice at runtime. Global weights are copied by leading-dimension slicing. For W ∈ RCout ×Cin ×k×k , the client receives ∗ ∗ Wi = W [ :Cout , :Cin , :, :],

(13)

where the retained channel counts are implied by the routed width bounds. Batch-normalization, bias, and linear-layer tensors are sliced analogously. The server also stores a map Ωi from each local tensor position to its corresponding position in the global supernet. Suppressing the round index, we denote the routed state by θi ; with routing disabled, θi = θ t and Ωi is the identity map. Sparse sample-weighted aggregation. Let Ui be the global positions covered by Ωi , and let θ̄i′ [u] be client i’s returned value after mapping to global position u. The contributors are St (u) = {i ∈ St | u ∈ Ui }.

The global update is P |Di | θ̄i′ [u]  t (u)  i∈S P , θ t+1 [u] = i∈St (u) |Di |   t θ [u],

St (u) ̸= ∅,

(14)

(15)

St (u) = ∅.

The implementation realizes Eq. (15) with value and samplecount accumulators. A position is normalized only over returned sub-supernets that contain it; if none contains it, the previous global value is retained.

Metric

Full FEAST Routed FEAST

Mean parameters per client Total traffic reduction Mean client reduction Median client reduction Largest client reduction

55.68M 1.0× 1.0× 1.0× 1.0×

8.17M 6.8× 43.8× 22.9× 111×

with implicit mini-batch averaging and no temperature scaling. Students use

Communication accounting. Let P be the full-supernet parameter count and Pi the routed count for client i. Ignoring metadata and using the same precision, full-supernet roundtrip communicationPtransmits 2mP parameters, whereas routing transmits 2 i∈St Pi . The reduction factor is (16)

For client i, the corresponding factor is P/Pi . These ratios use FEAST’s full supernet as the reference payload. Table 2 reports both the ratio of aggregate payloads and the distribution of client-level reduction ratios. The former is a ratio of sums, whereas the latter summarizes individual ratios.

D

Complete Local Multi-Variant Co-Training Procedure

Variant selection. Each selected client trains up to three cached variants on every local mini-batch: the global minimum, its local maximum, and a randomly sampled affordable intermediate when one exists. The endpoints are amin = arg min MAC(a), a∈A

amax = arg max MAC(a). i

(17)

a∈Ai

Because the client-budget range begins at the served floor, amin ∈ Ai for every client. For local mini-batch τ , define  min Aint ) < MAC(a) i = a ∈ Ai MAC(a < MAC(amax )} . (18) i

When nonempty, the client resamples

int arand i,τ ∼ Uniform(Ai )

(19)

for each mini-batch. If amax = amin , the step reduces to i supervised training of the global minimum. Local objective and distillation. Each mini-batch produces one mixed-label tuple (x̃, ya , yb , λmix ), reused for every applicable variant. Let zi,τ (a) = f (x̃; θi , a) and Lsup (z) = λmix LCE (z, ya ) + (1 − λmix )LCE (z, yb ). (20)

For distinct endpoints, the local maximum is evaluated first with Lmax = Lsup (zi,τ (amax )). Its detached logits define i max p̂max ))) , i,τ = softmax(sg(zi,τ (ai

(22)

c

Table 2: FEAST-internal communication under the Zipf(s = 1.2) client population. Reduction factors are measured relative to sending FEAST’s full supernet to every selected client.

mP Rtcomm = P . i∈St Pi

where sg denotes stop-gradient. The KD loss is X LKD (z, p̂) = − p̂c log softmax(z)c ,

(21)

Lstu (z, p̂) = (1 − ρkd )Lsup (z) + ρkd LKD (z, p̂),

(23)

The mini-batch objective is  min amax = amin ,  i Lsup (zi,τ (a )), Aint =∅, i Li,τ = Lmax + Lmin , , amax ̸=amin i   Lmax + Lmin + Lrand , otherwise.

(24)

where ρkd = 0.5. Thus, Lmin = Lstu (zi,τ (a ), p̂max i,τ ) and, max rand when sampled, Lrand = Lstu (zi,τ (ai,τ ), p̂i,τ ). min

The client backpropagates each applicable component, accumulates the resulting gradients, clips their combined L2 norm to 10, and performs one optimizer step. The local maximum supplies detached soft targets to the smaller variants; the global minimum is trained by every selected client, and permini-batch intermediate sampling extends coverage across the affordable cache. Local training computation. The budget bi constrains each activated variant separately, not the cumulative cost of sequential local passes. Let Ti,t be client i’s mini-batches in round t, let ni,τ be the mini-batch size, and define  min amax = amin ,  i {a }, Aint =∅, min max i , Vi,τ = {a , ai }, (25) amax ̸=amin i   min rand max int {a , ai,τ , ai }, Ai ̸= ∅.

The analytic forward-plus-backward convolution-MAC proxy is X X fwd Ci,t = ni,τ MAC(a), τ ∈Ti,t a∈Vi,τ (26) train fwd bi,t C = κfb Ci,t , κfb = 3.

The factor κfb = 3 approximates backward convolution arithmetic as twice the forward pass. The proxy excludes optimizer, loss, augmentation, communication, aggregation, and other non-convolution operations, and is therefore not an endto-end latency or energy measure. For a realized schedule, P P b train . Expected totals the federation proxy is t i∈St C i,t average the random pass uniformly over Aint i and client participation under the common m/N sampling model while retaining realized mini-batch sizes. Each active variant satisfies MAC(a) ≤ bi , but cumulative local training is not bounded by bi . Algorithms 1 and 2 summarize the server and client operations, respectively.

E

Additional Experimental Details and Controls

This section preserves the complete supporting evidence referenced by the main Experiments section. It reports the

Algorithm 1 FEAST: one federation round

Algorithm 2 FEAST: local multi-variant co-training

Require: θ t , A, {(Di , bi )}N i=1 , m, ρkd , and routing flag Route 1: Sample client set St of size m 2: for each client i ∈ St do 3: Ai ← {a ∈ A | MAC(a) ≤ bi } 4: Set amin , amax , and Aint i i by Eqs. (17)–(18) 5: if Route then 6: (θi , Ωi ) ← CreateSubSupernet(θ t , Ai ) ▷ Sec. C 7: else 8: θi ← θ t ; Ωi ← IdentityMap(θ t ) 9: end if 10: θi′ ← ClientStep(θi , Di , amin , amax , Aint i i , ρkd ) 11: end for 12: θ t+1 ← SparseAggregate(θ t , {(θi′ , Ωi , |Di |)}i∈St ) ▷ Sec. C 13: return θ t+1

Require: θi , Di , amin , amax , Aint i i , and ρkd 1: θi ← Copy(θi ) 2: for each mini-batch τ with (x, y) ∈ Di do 3: Construct (x̃, ya , yb , λmix ) 4: Zero gradients = amin then 5: if amax i 6: Activate amin ; compute Lsup by Eq. (20); backward 7: else 8: Activate amax ; compute Lmax ; backward i 9: Compute p̂max i,τ by Eq. (21) 10: Activate amin ; compute Lmin by Eq. (23); backward 11: if Aint i ̸= ∅ then 12: Sample arand i,τ by Eq. (19) 13: Activate arand i,τ ; compute Lrand by Eq. (23); backward 14: end if 15: end if 16: Clip gradients to L2 norm 10; optimizer step 17: end for 18: return θi

dataset and operating-point details, the exact SFN/DFN transfer configuration, the scope of post-hoc extraction, trainingcomputation and parameter-footprint controls, and the full CIFAR-100 sensitivity sweeps.

E.1

Datasets, Calibration, and Operating Points

Table 3 gives the dataset-specific partition and calibration sizes. Training counts exclude the server-held validation set. For each evaluated operating point, BN statistics are recalibrated using the disjoint server-held calibration samples described in Sec. B. All methods train for 4000 communication rounds, with 10 of 100 clients sampled uniformly without replacement per round. Each selected client performs one local epoch with batch size 64. SGD uses initial learning rate 0.025, momentum 0.9, cosine decay over the 4000-round horizon, and gradient clipping to L2 norm 10. Weight decay is 10−4 except for FIARSE, which retains its original zeroweight-decay setting. Training uses RandAugment(2, 6) and alternates Mixup with parameter 0.4 and CutMix with parameter 1.0. Validation is evaluated every 20 rounds to select the checkpoint; the test set is not used for checkpoint selection. For CIFAR-100, 45,000 training examples are partitioned among clients and 5,000 are server-held, comprising 500 BN-calibration and 4,500 validation examples. For TinyImageNet, the corresponding counts are 90,000 client, 1,000 calibration, and 9,000 validation examples. CINIC-10 partitions all 90,000 examples from its training directory among clients and uses its separate 90,000-example validation directory for 9,000 calibration and 81,000 checkpoint-selection examples. The official test splits remain disjoint. After selecting the best-validation checkpoint, every evaluated operating point receives its own deterministic BN recalibration before the single final test evaluation. Table 4 summarizes the deployment structures used for the main comparison. FEAST is evaluated on all 56 cached variants, HeteroFL and ScaleFL on their fixed native levels, and FIARSE on measured points from its continuous mask family. No accuracy values are interpolated. For largest-affordable

Dataset CIFAR-100 CINIC-10 TinyImageNet

Classes

Resolution

Train/Test

αdata

BN cal.

100 10 200

32×32 32×32 64×64

45K/10K 90K/90K 90K/10K

0.1 0.005 0.1

500 9000 1000

Table 3: Dataset-specific settings. BN cal. is the number of disjoint server-held samples used to recalibrate each evaluated operating point. population evaluation, FIARSE is evaluated on a dense MAC grid because its mask family supports intermediate operating points. Baseline adaptations and assignment. HeteroFL, ScaleFL, and FIARSE use a common CIFAR-style ResNet substrate with hidden widths [64, 128, 256, 512], four stages, and two BasicBlocks per stage. The full-width models cost approximately 550M–555M MACs. CIFAR-100 and CINIC-10 use a stride-one stem without max pooling, while TinyImageNet uses its dataset-specific stem configuration. These adaptations align the methods’ compute ranges while retaining their defining mechanisms. HeteroFL (Diao, Ding, and Tarokh 2021) retains width multipliers {1/16, 1/8, 1/4, 1/2, 1}, top-left channel slicing, and position-wise aggregation. ScaleFL (Ilhan, Su, and Liu 2023) retains four depth–width levels with (blocks, width) equal to (3, 0.40), (4, 0.50), (5, 0.60), and (8, 1.00), together with its early-exit self-distillation. FIARSE (Wu et al. 2024) retains its magnitude-based unstructured masks, thresholdcontrolled biased gradient descent, and sparse-delta aggregation. All methods use the same client partitions, resource budgets, participation schedule, and augmentation protocol.

Method

Deployment structure

MAC range

FEAST HeteroFL ScaleFL FIARSE

56 cached variants 5 width tiers 4 depth–width levels continuous masks

25M–601M 2M–550M 35M–555M 9M–555M

Table 4: Native deployment structures of the four weightsharing methods. The upper FEAST value is 601M on TinyImageNet and 596M on CIFAR-100 and CINIC-10. Quantity FEAST subset (M MACs) FEAST, full 56 points FEAST, matched subset Baseline, native tiers Full margin Density contribution Residual margin FEAST client wins

HeteroFL-aligned

ScaleFL-aligned

25.0/34.6/139.0/549.4 67.74 66.66 41.50 26.24 1.08 25.16 100/100

34.6/71.7/128.2/549.4 67.74 67.21 35.78 31.96 0.53 31.43 100/100

Table 5: CIFAR-100 serving-density control under largestaffordable population evaluation. Accuracies and margins are percentages and percentage points, respectively. Differences are computed from the displayed values; density contribution is full-curve minus matched-subset accuracy. For population evaluation, each client receives the largest measured native operating point whose MAC cost does not exceed its budget. If no native point is affordable, the method’s smallest trained point is used as a minimum-tier fallback. This occurs only for ScaleFL: 32 clients on CIFAR-100 and CINIC-10, and 31 clients on TinyImageNet, have budgets below its approximately 35M-MAC minimum and therefore receive level 1. The ScaleFL population result should accordingly be read as largest-affordable serving with a minimumtier fallback for otherwise unserved clients. Operating-point density control. To isolate the effect of denser serving, we repeat the CIFAR-100 population evaluation after retaining only the cached FEAST variant nearest to each native HeteroFL or ScaleFL tier in MACs. Because client budgets begin at 25M MACs, HeteroFL’s 2M and 9M tiers both map to FEAST’s 25M floor, yielding four unique FEAST points; ScaleFL also yields four. We use the same fixed client budgets and largest-affordable rule as in the mainpaper population evaluation, without retraining or interpolating accuracy. Table 5 shows that only 1.08 and 0.53 points arise from density, leaving approximately 96% and 98% of the full margins. These residuals compare complete methods, not training rules alone, because model-space and cache-design differences remain. FIARSE is already evaluated densely.

E.2

SFN and DFN Transfer Configuration

The transferred SuperFedNAS (SFN) procedure uses its uniform random architecture sampler, whereas DeepFedNAS (DFN) uses its Pareto-path sampler. Both retain MaxNet’s overlap-aware aggregation, with its coefficient annealed by a cosine schedule from 0.9 to 0.125. The sampler and aggregation are therefore transferred together, rather than replacing

MaxNet aggregation with ordinary FedAvg. All four reported transfers use the canonical augmentation, optimizer, 100-client, 10%-participation, and 4000-round settings from the main paper. The unconstrained variants sample from the complete expanded supernet. The budgetconstrained variants additionally use the Zipf(s = 1.2) client budgets and γ = 1 allocation, and restrict each client to affordable architectures. The comparison asks whether each method’s sampler and MaxNet aggregation remain effective when transferred to the 25M–596M shared model space and evaluated under the federation protocol described in the main paper. It is a cross-setting stress test, not a reproduction in the methods’ original model spaces or client settings, and conclusions about performance in those native settings are outside its scope.

E.3

Post-Hoc Extraction

After federation, FEAST can search for an architecture under a requested MAC limit and extract its weights from the trained supernet. We use the training-free objective in Eq. (10) with population 512, 512 generations, mutation probability 0.3, and the cache-construction thresholds ρ0 = 0.40 below 50M MACs and ρ0 = 0.31 otherwise. Neither validation nor test accuracy enters selection. The extracted subnet receives architecture-specific BN recalibration, but no weight fine-tuning or further federated training. We searched 29 target budgets spanning approximately 25M–560M. The low-end results from 25M-52M MAC underlying the main-paper values use 14 logged GA outputs. Architectures discovered on CIFAR-100 are reused on CINIC10 and TinyImageNet, with MACs recomputed for TinyImageNet. Gaps are measured against the linearly interpolated cached-variant curve at the same realized MAC value. Dataset

Evaluation range

CIFAR-100 CIFAR-100

Low end: 25.54M–51.32M Full: 25.54M–557.91M

Mean |gap| (pp) 1.14 0.68

CINIC-10 CINIC-10

Low end: 25.53M–51.31M Full: 25.53M–557.83M

1.34 0.88

TinyImageNet TinyImageNet

Low end: 26.87M–54.65M Full: 26.87M–563.30M

1.79 1.03

Table 6: Mean absolute post-hoc extraction gap from the linearly interpolated cached-variant curve at the same MAC value. Low-end results use 14 GA outputs; full-range results use 29. At 30M MACs, the search subnet reaches 64.35% on CIFAR-100, only 0.33 points below the cached-curve reference. Together with Table 6, this shows that the trained supernet can serve additional architectures across the deployment range without further federated training. Client-side subnet extraction. We also compared extraction from routed 50M and 229M client sub-supernets against extraction from the complete server supernet. For cached variants, the minimum, an intermediate, and the largest affordable architecture at each budget matched across all 2352

Method HeteroFL ScaleFL FIARSE Single-variant reference FEAST

Logical PMAC Executed PMAC FEAST/executed 14.97 15.22 19.12 19.86 31.01

14.97 15.22 29.97 19.86 31.01

2.07× 2.04× 1.03× 1.56× 1.00×

Table 7: Expected convolution-MAC training proxies over 4000 rounds on CIFAR-100. The single-variant reference trains only each client’s deployed variant under the FEAST population and partition.

Method

Orig. r.

Match r.

Orig.

Match

Margin

Wins

HeteroFL ScaleFL FIARSE

4000 4000 4000

8286 8150 4139

41.50 35.78 55.13

44.44 39.23 55.42

23.30 28.51 12.33

100/100 100/100 100/100

Table 8: Equal-total-training-compute control on CIFAR-100. Original and matched columns are population-averaged accuracy (%) under largest-affordable serving. Margin is relative to FEAST’s 67.74%; wins counts client-level FEAST comparisons after compute matching. Displayed accuracies are rounded; margins use full-precision outputs. Method

tensor comparisons and all six accuracy measurements. Of the 14 logged low-end GA outputs, all fit the 229M payload and five fit the tighter 50M payload; every fitting output again matched full-supernet extraction exactly. Thus, client-side extraction is exact when the architecture lies within the routed payload’s position-specific depth and width limits, although MAC affordability alone does not guarantee this structural fit.

E.4

Training-Computation Controls

Equation (26) defines the analytic forward-plus-backward convolution-MAC proxy. It retains realized client shard sizes and the exact one-, two-, or three-variant local case, while averaging uniformly over the random intermediate and the common client-participation model. It excludes optimizer, loss, augmentation, communication, aggregation, and other non-convolution operations, and is not a latency or energy measurement. Table 7 reports the resulting 4000-round totals. FIARSE is shown under both logical active arithmetic and executed dense-convolution arithmetic. Its unstructured mask acts on the full dense weight tensors, so the latter represents the computation executed by the implementation and is used for the matched-compute control. Of the 100 FEAST clients, 31 use one variant per minibatch, six use two, and 63 use three. The federation-total FEAST-to-single-variant ratio is 1.56×; the client-level ratios range from 1.00× to 2.34×. Thus, the cumulative cost is lower than a uniform three-pass approximation because lowbudget clients frequently use degenerate one- or two-variant cases. Equal-total-training-compute control. We extend each baseline’s training horizon so that its total executed convolution-MAC proxy matches FEAST’s 31.01 PMACs, while retaining the same optimization schedule relative to that horizon. Table 8 reports the largest-affordable population results. For reference, under the original 4000-round training horizon, the largest-affordable population evaluation gives 67.74% for FEAST and 41.50%, 35.78%, and 55.13% for HeteroFL, ScaleFL, and FIARSE, respectively. The native low- and high-compute operating points change from 48.33%/68.40% to 52.20%/70.23% for HeteroFL, from 20.98%/65.01% to 23.25%/67.29% for ScaleFL, and from 48.20%/68.65% to 48.22%/68.58% for FIARSE. Longer training therefore improves HeteroFL and ScaleFL modestly

FEAST routed envelope HeteroFL ScaleFL FIARSE transmitted tensor

25M

50M

229M

408M

596M

0.50M 0.18M 0.07M 11.22M

2.41M 0.71M 0.07M 11.22M

10.02M 2.82M 0.61M 11.22M

20.61M 2.82M 0.61M 11.22M

35.60M 11.22M 11.27M 11.22M

Table 9: Client-side parameter counts during training at the five canonical CIFAR-100 budget anchors. and has little effect on FIARSE, while the 12.33–28.51-point population margins remain. This control indicates that the primary margins are not explained solely by FEAST’s greater convolution arithmetic.

E.5

Parameter Footprints

The server stores a 55.68M-parameter FEAST supernet, compared with 11.22M, 11.27M, and 11.22M parameters for the complete HeteroFL, ScaleFL, and FIARSE models, respectively. Client-side training and deployment require different quantities. Table 9 counts the transmitted training model. For FEAST, this is the routed envelope over all affordable cached variants; for HeteroFL and ScaleFL, it is the selected physical tier; and for FIARSE, it remains the complete dense tensor because masking does not reduce the transmitted parameter array. At 596M, the routed FEAST envelope is 3.0–3.2× larger than the three baseline payloads. This envelope supports the global minimum, any sampled intermediate, and the local maximum within one routed model; it is not the single architecture deployed for inference. Table 10 instead counts the single deployed model. The FEAST values are the parameters of the selected cached architecture. For FIARSE, they count active post-mask parameters rather than the transmitted dense tensor. At 25M–408M, the deployed FEAST variant lies between the smaller HeteroFL/ScaleFL models and the larger FIARSE active model. At 596M, its 11.78M parameters are within approximately 5% of all three baselines. The large high-budget footprint is therefore specific to multi-variant training, not single-variant deployment.

E.6

Resource and Label-Skew Sensitivity

Table 11 varies the Zipf exponent while holding γ = 1 and αdata = 0.1. Increasing s places more clients at low budgets and predictably reduces high-budget accuracy, but no tested setting inverts the curve. The 596M result remains 70.29%– 74.54%, and every higher-budget anchor exceeds the 25M

Method FEAST deployed variant HeteroFL ScaleFL FIARSE active parameters

25M

50M

229M

408M

596M

0.33M 0.18M 0.07M 0.51M

0.72M 0.71M 0.07M 1.02M

4.02M 2.82M 0.61M 4.64M

7.99M 2.82M 0.61M 8.25M

11.78M 11.22M 11.27M 11.22M

Table 10: Parameters in the single model deployed at each budget. Zipf s

25M

50M

229M

408M

596M

0.8 1.0 1.2 1.5

65.50 64.31 64.89 64.37

66.25 65.77 65.60 65.66

74.65 72.55 71.82 70.77

74.15 72.81 71.94 70.79

74.54 72.16 71.06 70.29

Table 11: CIFAR-100 sensitivity of FEAST to the resourceskew exponent. result. Table 12 compares FEAST and FIARSE under four nominal Dirichlet settings, with s = 1.2 and γ = 1 held fixed. αdata ∈ {0.05, 0.10, 0.30, 1.00} corresponds to αeff ∈ {0.225, 0.45, 1.35, 4.5}, respectively. FEAST exceeds FIARSE at all 20 matched anchor comparisons. Its 25M-to596M change remains 5.77–7.37 points, versus 21.25–23.25 points for FIARSE, while its 596M margin ranges from 2.41 to 7.69 points. The result supports robustness over the tested label-skew range without implying invariance to the partition parameter. γ sweep. For completeness, Table 13 reports the full fiveanchor FEAST sweep used by the main paper. The 596M result increases at every sampled value from γ = 0 through γ = 1.5, while the 25M-to-596M change progresses from −4.29 to +8.40 points. We use γ = 1 as the proportional cross-method default rather than claiming that it is optimal.

F

Structural and Finite-Horizon Analysis

This appendix isolates the theoretical claims needed to interpret the protocol and method contributions analyzed here. We first formalize the γ-allocation protocol independently of FEAST. We then characterize budget-dependent reachability, activation exposure, and sparse aggregation in the federated shared model space. Finally, an auxiliary frozengradient operator yields a routed computation scale that motivates a conditional finite-horizon bound for the full algorithm. Sparse-aggregation and implementation-specific effects are represented by bounded discrepancy terms; distillation, clipping, local drift, momentum, and weight decay are grouped rather than treated as separate theoretical contributions. Main-paper Proposition 1 is established by Proposition F.2; Proposition 2 combines Proposition F.3, Corollary F.1, and Proposition F.4; and Theorem 1 is stated with exact constants and proved in Sec. F.4.

F.1

Protocol allocation identity

The allocation protocol is a property of the simulated federation, not a component of FEAST. Let b = (b1 , . . . , bN )

αdata

Method

25M

50M

229M

408M

596M

Gap

0.05

FEAST FIARSE

64.19 42.47

64.89 51.21

72.06 54.88

72.60 62.53

71.56 63.87

7.37 21.40

0.10

FEAST FIARSE

64.89 45.40

65.60 55.05

71.82 59.75

71.94 66.72

71.06 68.65

6.17 23.25

0.30

FEAST FIARSE

65.09 42.09

65.28 51.41

72.03 54.85

72.24 62.99

71.42 64.78

6.33 22.69

1.00

FEAST FIARSE

64.66 42.42

65.19 50.54

70.77 55.14

70.74 61.72

70.43 63.67

5.77 21.25

Table 12: CIFAR-100 accuracy (%) and 25M-to-596M change across nominal Dirichlet settings. γ

25M

50M

229M

408M

596M

0 0.25 0.5 1.0 1.5

63.25 63.81 63.06 64.89 66.43

64.02 64.92 64.62 65.60 66.48

63.71 67.05 67.96 71.82 74.25

61.35 65.40 67.42 71.94 74.46

58.96 63.79 65.76 71.06 74.83

Table 13: FEAST sensitivity to γ on CIFAR-100 under otherwise identical budgets, partition-generation settings, training, and evaluation. denote the fixed client-budget vector, and let b̄i = min(bi , Bcap ) denote the budget used for data allocation. Definition F.1 (γ-allocation target) For γ ≥ 0, define N X

b̄γ qi (γ) = PN i

, γ j=1 b̄j

qi (γ) = 1.

(27)

i=1

For class k with Nk examples, the pre-integer allocation is e k ∼ Dir (αdata Nk q1 (γ), . . . , αdata Nk qN (γ)) . p

(28)

Proposition F.1 (Expected protocol allocation) For every class k and client i, E[e pk,i | b] = qi (γ),

N X

αdata Nk qi (γ) = αdata Nk .

i=1

(29) Consequently, define the idealized pre-integer client count by X n ei = Nk pek,i . (30) k

Then

E[e ni | b] = Ntrain qi (γ).

(31)

Proof. Conditioned on the fixed client-budget vector b, the concentrations ck,i = αdata Nk qi (γ) are fixed. Using the mean of a Dirichlet component, ck,i αdata Nk qi (γ) = qi (γ), E[e pk,i | b] = PN = PN αdata Nk j=1 qj (γ) j=1 ck,j (32) P where the final equality uses j qj (γ) = 1. The total concentration is N X i=1

ck,i = αdata Nk

N X i=1

qi (γ) = αdata Nk ,

(33)

which proves Eq. (29). By the definition of n ei ,P summing the expected class-wise counts over k and using k Nk = Ntrain gives Eq. (31). □ The per-class total precision is αdata Nk . Its symmetricequivalent per-client concentration is therefore αeff,k = αdata Nk /N ; for a balanced K-class dataset this reduces to the main-paper value αdata Ntrain /(KN ). The case γ = 0 denotes the uniform-qi endpoint of this same budget-aware construction, not a separate strict symmetric Dir(αdata ) draw. Individual component concentrations and marginal variances depend on qi (γ). Thus, the protocol changes the target mean vector under fixed total per-class precision; it does not hold all higher-order allocation statistics fixed. The implemented integer assignment and balancing constraints produce the realized data size ni , which can differ from both n ei and its expectation in Eq. (31). All FEAST results below are therefore stated for the realized data sizes {ni }N i=1 . The idealized mean is used only when explicitly instantiating the protocol model.

F.2

Reachability and activation exposure

Throughout the realized-partition analysis, assume that the PN client shards are disjoint and exhaustive, i=1 ni = Ntrain , that ni > 0 for every client, and that every budget can afford the global-minimum cached variant. These conditions hold for the canonical partitions analyzed below. Let A be the fixed variant cache and let Ai = {a ∈ A : MAC(a) ≤ bi }

(34)

be client i’s affordable set. The routed sub-supernet is the smallest implemented depth-width envelope containing all variants in Ai , with each retained block supporting all allowed expansion choices; its global parameter positions are denoted by Ui . Definition F.2 (Routed reachability) For a served position SN u ∈ U srv = i=1 Ui , define ri (u) = I{u ∈ Ui }.

(35)

Definition F.3 (Local activation exposure) On mini-batch τ , let Vi,τ be the set containing the global-minimum and local-maximum variants, with one uniformly sampled strict intermediate when available. Assume that this variant-set sampling rule is stationary across local mini-batches. Define     [ ai,τ (u) = I u ∈ θa , (36)   a∈Vi,τ   X hi (u) = E  I{u ∈ θa } bi  . (37) a∈Vi,τ

Here ri (u) determines aggregation eligibility, whereas hi (u) is the expected activation multiplicity per local optimization step and may exceed one. Coordinate activity satisfies ai,τ (u) ≤ ri (u). Sparse aggregation follows routed support, while supervised task gradients require coordinate activation. Tensor-level optimizer effects on routed but coordinate-inactive positions are absorbed into the algorithmic-discrepancy term used later.

Proposition F.2 (Nested budget reachability) If bi ≤ bj , then for every u. (38) Consequently, each served position is routed by an upper tail of the budget-ordered client population. Ai ⊆ Aj ,

Ui ⊆ Uj ,

ri (u) ≤ rj (u)

Proof. Affordability is defined by a budget threshold, so increasing the budget cannot remove a cached variant. Each routed depth or width bound is a coordinate-wise maximum over the affordable set. Taking a maximum over a superset cannot reduce any bound. The retained blocks and channel dimensions are nested leading slices, and each retained block supports all allowed expansion choices. Therefore, monotone depth-width bounds imply Ui ⊆ Uj , which proves the indicator inequality. □ For a cohort St of m clients sampled uniformly without replacement, define the realized routed sample mass and the sample-weighted activation-exposure proxy by X Mtroute (u) = ni ri (u), (39) i∈St

Mtexp (u) =

X

(40)

ni hi (u).

i∈St

With a fixed mini-batch size and one local epoch, this proxy is proportional, up to batching and rounding, to the expected round-level activation count. Proposition F.3 (Expected exposure) Conditioned on the realized budgets and local data sizes, N   mX E Mtroute (u) | {ni , bi }N = ni ri (u), i=1 N i=1

N   mX E Mtexp (u) | {ni , bi }N ni hi (u). i=1 = N i=1 P If Ru = i ri (u) clients route u, then
N −Ru

Pr[Mtroute (u) = 0] =

with value zero when N − Ru < m.

m
N m

,

(41) (42)

(43)

Proof. Each client has inclusion probability m/N . Linearity of expectation gives Eqs. (41) and (42). Equation (43) counts cohorts drawn entirely from the N − Ru clients that do not route the position. □

Corollary F.1 (Protocol instantiation) Assume that cohort sampling is independent of the idealized allocation draw. Under the idealized pre-integer counts {e ni }N i=1 , define exp route f f Mt (u) and Mt (u) by replacing ni with n ei in Eqs. (39) and (40). Then ftroute (u) | b] = E[M ftexp (u) | b] = E[M

N mNtrain X qi (γ)ri (u), N i=1

N mNtrain X qi (γ)hi (u). N i=1

(44)

(45)

Proof. Take expectation over the idealized allocation and substitute E[e ni | b] = Ntrain qi (γ) into the definitions above. □ The corollary preserves the contribution boundary: qi (γ) belongs to the evaluation protocol, hi (u) belongs to FEAST’s local co-training rule, and ri (u) belongs to FEAST’s routing and aggregation geometry. Proposition F.4 (γ increases routed allocation share) For a served position u, define Wuroute (γ) =

N X

(46)

qi (γ)ri (u).

i=1

Then Wuroute (γ) is nondecreasing in γ. Proof. Let = P xi exp(γxi )/ j exp(γxj ),

log b̄i .

Since

qi (γ)

d route W (γ) = Covq(γ) (ri (u), xi ). dγ u Its pairwise form is N N

1 XX qi (γ)qj (γ) ri (u) − rj (u) xi − xj . 2 i=1 j=1

=

(48)

Position-wise sparse aggregation

Let ∆i,t (u) be client i’s returned change at global position u. When Mtroute (u) > 0, define ωi,t (u) =

I{i ∈ St }ni ri (u) , Mtroute (u)

max fisup (θ) = Eξ∼Pi EV∼νi ℓsup ) i (ai

(47)

The capped budget b̄i is nondecreasing in bi . Hence, xi < xj implies bi < bj and therefore ri (u) ≤ rj (u) by Proposition F.2; pairs with xi = xj contribute zero. Every summand is thus nonnegative. □ Because the position-wise sparse weights defined in Sec. F.3 normalize by routed mass, a larger Wuroute (γ) does not directly scale an aggregate update. With fixed batching, allocation instead changes local step counts, which enter the routed computation scale ψu and effective client mixture ϖi (u) defined in that section. Remark F.1 (Scope of the monotonicity result) Proposition F.4 shows that increasing γ assigns more idealized data mass to clients whose routed sub-supernets contain position u. It does not imply that the activationPN weighted mass i=1 qi (γ)hi (u) is nondecreasing, because hi (u) need not be nondecreasing in client budget. Higherbudget clients have larger affordable sets and therefore different random-intermediate sampling pools. Activation monotonicity would require an additional assumption on the fixed cache and intermediate-variant sampling rule.

F.3

P For a covered position, ωi,t (u) ≥ 0 and i ωi,t (u) = 1. The effective client mixture is therefore position-dependent. Moreover, the denominator depends on ri (u) rather than ai,τ (u): a routed client remains part of the position-wise average even when no sampled variant activates the coordinate. Such a return may be unchanged or may contain tensor-level optimizer effects. This routed-versus-activated distinction is the source of the aggregation and algorithmic perturbations represented below. To connect this geometry to optimization, let Pi be the distribution of mixed-label tuples ξ generated from client i’s data, and write ℓsup i (a) = Lsup (zi (a; θ, ξ)), with the dependence on (θ, ξ) suppressed inside the expectation. The supervised reference loss is "

(49)

and extend ωi,t (u) = 0 when Mtroute (u) = 0. The exact server update is  N X   t ωi,t (u)∆i,t (u), Mtroute (u) > 0, θ [u] + t+1 θ [u] = i=1   t θ [u], Mtroute (u) = 0. (50)

+ (1 − ρkd )

X

#

ℓsup i (a)

} a∈V\{amax i

(51)

.

The inner sum matches client gradient accumulation, so resup peated activation of u Pis already represented in ∂u fi . With pi = ni /Ntrain and i ni = Ntrain , define Fsup (θ) =

N X

pi fisup (θ).

(52)

i=1

Distillation is excluded from this reference objective and enters the algorithmic discrepancy. Let Ft be the pre-round history, with Et [·] = E[· | Ft ]. For E local epochs and mini-batch size Bmb , let   ni Biloc = E (53) Bmb denote client i’s number of local optimizer steps per selected round. Canonically, E = 1 and Bmb = 64. Proposition F.5 (Auxiliary routed computation scale) Using the local-step counts in Eq. (53), define βi (u) = Et [ωi,t (u)], πu = Pr[Mtroute (u) > 0]. (54) P Then i βi (u) = πu . Define ψu =

N X

βi (u)Biloc ,

i=1

ϖi (u) =

βi (u)Biloc , ψu

(55)

Here βi (u) is client i’s expected aggregate share and ϖi (u) is the local-step-weighted effective client mixture. Consider the auxiliary frozen-gradient operator in which client i returns −ηt Biloc ∇fisup (θ t ), with no local drift, distillation, clipping, momentum, or weight decay. Its expected coordinate update satisfies   Et [θ t+1 [u] − θ t [u]] = −ηt ψu ∂u Fsup (θ t ) + eagg t (u) , (56) where N X
eagg (u) = ψ ϖi (u) − pi ∂u fisup (θ t ). (57) u t i=1

loc Moreover, if Bmin

then

loc = mini Biloc and Bmax = maxi Biloc ,

loc loc Bmin πu ≤ ψu ≤ Bmax πu .

(58)

P Proof. For every cohort, i ωi,t (u) equals one when u is Pcovered and zero otherwise, so taking expectation gives i βi (u) = πu . Substituting the auxiliary client return into Eq. (50) and taking conditional expectation gives − ηt

N X

βi (u)Biloc ∂u fisup (θ t )

i=1

= −ηt ψu

N X

(59) ϖi (u)∂u fisup (θ t ).

i=1

P Adding and subtracting ψu i pi ∂u fisup proves P Eqs. (56) and (57). The bounds in Eq. (58) follow from i βi (u) = πu loc loc and Bmin ≤ Biloc ≤ Bmax . □ Proposition F.5 motivates, but does not prove, the functional form assumed for full FEAST below; A2–A4 collect the departures in discrepancy and noise terms. Activation is encoded in ∂u fisup , whereas ψu captures routed coverage, local steps, and sparse normalization.

F.4

Routed-scale finite-horizon supervised stationarity

A1: Smooth reference objective. On the served support U srv , which contains every coordinate updated by Eq. (50), Fsup is lower bounded by Finf and has an LF -Lipschitz gradient on the analyzed domain. A2: Conditional decomposition relative to the auxiliary scale. Let Ψ = diag(ψu ), with ψu defined by Eq. (55), and let ∆t = θ t+1 − θ t . Define 1 Et [∆t ] − Ψ∇Fsup (θ t ), ηt 1 ζt = − ∆t − Ψ∇Fsup (θ t ) − et . ηt

Then et is Ft -measurable, Et [ζt ] = 0, and   θ t+1 = θ t − ηt Ψ∇Fsup (θ t ) + et + ζt .

(60) (61)

u∈U

ψmax = max ψu . srv u∈U

(62)

(63)

Because every served position has positive routed coverage and Biloc ≥ 1, Eq. (58) implies 0 < ψmin ≤ ψu ≤ ψmax < ∞.

with HT > 0. Under A1–A4, if

(64)

The activation profile is already encoded in the client supervised gradients; Ψ represents routed cohort coverage, local step counts, and position-wise sparse normalization.

t=0

1 4LF ψmax for every analyzed round, then 0 < ηt ≤

(68)

T −1 2 Fsup (θ 0 ) − Finf 1 X ηt E∥∇Fsup (θ t )∥22 ≤ HT t=0 ψmin HT   2 2LF QT + + ε2 2 ψmin ψmin HT LF QT 2 + σ . ψmin HT round (69)

Proof. Write gt = ∇Fsup (θ t ). By smoothness, Eq. (62), and Et [ζt ] = 0, Et Fsup (θ t+1 ) ≤ Fsup (θ t ) − ηt ⟨gt , Ψgt + et ⟩

LF ηt2 2 ∥Ψgt + et ∥22 + σround . 2 (70) Weighted Young’s inequality gives 1 (71) −⟨gt , et ⟩ ≤ ∥Ψ1/2 gt ∥22 + ∥Ψ−1/2 et ∥22 , 4 and ε2 ∥Ψgt ∥22 ≤ ψmax ∥Ψ1/2 gt ∥22 , ∥Ψ−1/2 et ∥22 ≤ . ψmin (72) Using ∥Ψgt + et ∥22 ≤ 2∥Ψgt ∥22 + 2ε2 and the step-size condition in Eq. (68), Eq. (70) becomes ηt Et Fsup (θ t+1 ) ≤ Fsup (θ t ) − ∥Ψ1/2 gt ∥22 2   ηt LF ηt2 2 2 + + L F ηt ε2 + σround . ψmin 2 (73) +

The operator Ψ is deterministic conditional on the realized partition and routed envelopes. Define ψmin = min ψu , srv

A4: Bounded round noise. Conditioned on Ft , 2 Et [ζt ] = 0, Et ∥ζt ∥22 ≤ σround . (66) A4 assumes a uniform conditional second-moment bound for the combined cohort, data, augmentation, and variantsampling noise. Theorem F.1 (Finite-horizon supervised stationarity) Let T −1 T −1 X X HT = ηt , QT = ηt2 , (67) t=0

The result uses the following conditional decomposition and assumptions. All quantities and norms below are restricted to U srv ; coordinates outside it are neither updated by Eq. (50) nor used by served variants.

et = −

alg A3: Bounded update discrepancy. Write et = eagg t +et . Almost surely, for constants εagg and εalg , ∥et ∥2 ≤ εagg + εalg =: ε. (65) The first label covers the position-dependent client mixture in Eq. (57); the second covers local drift, distillation, clipping, momentum, weight decay, and routed-but-unactivated optimizer updates. Only their sum is bounded here; no separate numerical estimate or small-error claim is made. The theorem studies dependence on ψmin at fixed ε; the absolute discrepancy bound is conservative because some components may contract with gradient magnitude.

Finally, ∥Ψ1/2 gt ∥22 ≥ ψmin ∥gt ∥22 . Taking total expectations, summing Eq. (73), using Fsup ≥ Finf , and dividing by ψmin HT /2 proves Eq. (69). □ The theorem concerns the trained shared tensor before evaluation-time BN recalibration, not exact convergence of the complete KD objective or the recalibrated operating points. The quantity ψmin is the minimum auxiliary routed computation scale; by Eq. (58), lower routed coverage can reduce this scale, and every term in the bound worsens as ψmin decreases. We do not claim that ε is small at the canonical ρkd = 0.5; the theorem exposes how the routed scale, aggregate update discrepancy, and round noise enter the finitehorizon neighborhood rather than certifying a tight numerical radius.

F.5

Canonical interpretation and empirical connection

For the canonical CIFAR-100 partition, 36 ≤ ni ≤ 1906, giving 1–30 local steps per client. Direct enumeration from the cache and budget vector gives Rmin = 11; with N = 100 and m = 10, the least-reachable profile is routed with probability
89 1−

10
100 ≈ 0.7062. 10

(74)

Thus, it is covered in approximately 70.62% of uniformly sampled rounds. The accompanying reproduction script computes πu and ψu for every routed profile under Proposition F.5, but these values do not numerically establish the unknown smoothness, discrepancy, or noise constants in Theorem F.1. The structural results give a direct interpretation of the main-paper ablation. High-cost-exclusive positions are routed by a smaller upper tail of the client population. Proposition F.4 shows that increasing γ shifts more idealized data mass toward that eligible tail, while Corollary F.1 shows that the activation-weighted mass also depends on FEAST’s hi (u). These relationships are consistent with the CIFAR-100 largest-budget-minus-smallest-budget operating-point accuracy gap changing from −4.29 points at γ = 0 to +6.17 at γ = 1. The coupled protocol is not a volume-only intervention, and the theory does not predict this numerical gap.

References Diao, E.; Ding, J.; and Tarokh, V. 2021. HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients. In International Conference on Learning Representations (ICLR). Ilhan, F.; Su, G.; and Liu, L. 2023. ScaleFL: ResourceAdaptive Federated Learning with Heterogeneous Clients. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 24532–24541. Jiang, Z.; Wang, W.; Li, B.; and Li, B. 2022. Pisces: Efficient Federated Learning via Guided Asynchronous Training. In Proceedings of the 13th Symposium on Cloud Computing, SoCC ’22, 370–385. ACM.

Khan, B.; and Daneshtalab, M. 2026a. DeepFedNAS: Efficient Hardware-Aware Architecture Adaptation for Heterogeneous IoT Federations via Pareto-Guided Supernet Training. arXiv:2601.15127. Khan, B.; and Daneshtalab, M. 2026b. DeepFedNAS: Pareto Optimal Supernet Training for Improved and Predictor-Free Federated Neural Architecture Search. In Proceedings of the 34th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 59–64. i6doc.com. ISBN 9782875870964. Wu, F.; Wang, X.; Wang, Y.; Liu, T.; Su, L.; and Gao, J. 2024. FIARSE: Model-Heterogeneous Federated Learning via Importance-Aware Submodel Extraction. In Advances in Neural Information Processing Systems, volume 37, 115615– 115651.

Related documents

• FedSAP: Federated Learning with Structured Adaptive Partitioning for Multi-Domain Heterogeneous Edge Devices#1156909
• FedTCS: Federated Learning with Time-based Client Selection to Optimize Edge Resources#644327
• PEFLL: Personalized federated learning by learning to learn#1134269
• Server-Enforced Watermarking in U-Shaped Split Federated Learning#1116166
• FedSPM: Routing-Enabled Federated Learning under Dual Heterogeneity via Semiparametric Mixture#1143833