FedRTS: Federated Robust Pruning via Combinatorial Thompson Sampling
Authors: Hong Huang
Jinhai Yang
Yuan Chen
Jiaxun Ye
Dapeng Wu
Venue: NeurIPS 2025 poster ()
Keywords: Federared Learning
Neural Network Pruning
Combinatorial Thompson Sampling
Primary area: deep_learning

Abstract: Federated Learning (FL) enables collaborative model training across distributed clients without data sharing, but its high computational and communication demands strain resource-constrained devices. While existing methods use dynamic pruning to improve efficiency by periodically adjusting sparse model topologies while maintaining sparsity, these approaches suffer from issues such as **greedy adjustments**, **unstable topologies**, and **communication inefficiency**, resulting in less robust models and suboptimal performance under data heterogeneity and partial client availability. To address these challenges, we propose **Fed**erated **R**obust pruning via combinatorial **T**hompson **S**ampling (FedRTS),a novel framework designed to develop robust sparse models. FedRTS enhances robustness and performance through its Thompson Sampling-based Adjustment (TSAdj) mechanism, which uses probabilistic decisions informed by stable and farsighted information,  instead of deterministic decisions reliant on unstable and myopic information in previous methods. Extensive experiments demonstrate that FedRTS achieves state-of-the-art performance in computer vision and natural language processing tasks while reducing communication costs, particularly excelling in scenarios with heterogeneous data distributions and partial client participation. Our codes are available at: https://github.com/Little0o0/FedRTS.

FedRTS: Federated Robust Pruning via Combinatorial Thompson Sampling
Hong Huang, Jinhai Yang, Yuan Chen, Jiaxun Ye, Dapeng Wu
Department of Computer Science
City University of Hong Kong
Hong Kong SAR, China
fhohuang-c, jinhayang7-c, ychen2752-c, jiaxunye-cH0my cityu. edu dpwu@ieee.ozg org
Abstract
Federated Learning (FL) enables collaborative model training across distributed clients without data sharing, but its high computational and communication de- mands strain resource snoource-consrainee devices. While existing methods use dynamic pruning to improve efficiency by periodically adjusting sparse model topologies while maintaining sparsity, these approaches suffer from issues such as greedy adjustments, unstable topologies, and communication inefficiency, resulting less robust models and suboptimal performance under data heterogeneity and par- tial client availability. To address these challenges, we propose Federated Robust pruning via combinatorial Thompson Sampling (FedRTS), novel framework designed to develop robust sparse models. FedRTS enhances robustness and per- formance through its Thompson Sampling-based Adjustment (TSAdj) mechanism, which uses probabilistic decisions informed by stable and farsighted information, instead of deterministic decisions reliant unstable and myopic information in previous methods. Extensive experiments demonstrate that FedRTS achieves state-of- the-art performance in computer vision and natural language processing tasks while reducing communication costs, particularly excelling in scenarios with heterogeneous data distributions and partial client participation. Our codes available at: hhttps://githi http://b..comm/ttteee//////eeeee
1 Introduction
enables edge devices with private local data to collabora- tively train model without sharing data. However, substantial computational and communication demands for training deep learning models often exceed the resource limitations of edge devices in
Federated learning (FL. 30 25
65
cross-device FL scenarios. Although neural network pruning [12] 40 33 offers promising solu- tion by removing redundant parameters, traditional pruning methods depend on resource-intensive dense model training, rendering them impractical for privacy-preserved and resource-constrained FL environments.
To address these challenges, recent federated pruning frameworks [ 47 57
have within FL. These frameworks employ a two-loop training process: in the inner loop, model weights are updated through standard FL. rounds with fixed model topology; in the outer loop, the server adjusts the model topology by pruning and reactivating parameters [1I), illustrated in Fig. [ (left). This iterative process generates specialized sparse model without dense model training, significantly reducing computational costs.
24
19
adopted dynamic sparse training techniques [I 48 22
Despite these advancements, existing frameworks challenges model topology adjustment, as illustrated in Fig. (lft). (1) Greedy adjustment:
57
8 42 suffer from three critical
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

5 Myopic Unstable
Server
Farsighted and Stable
Aggregated Weights & Grad
Adjusted Weights
Probability
Updated Probabilly
U Probabilistic
9,0 Deterministic
Distribution
Distribution
2. Topology Adjustment via Probability
Pruning Reactivating
ALAA
Aggregated
Adjusted Weights
Weights
1. Partiak Aggregation
Aggregation Distribution Updating
Participated in previous rounds
f Communicational Inefficiency
Not participaated in current round
Communicational
Weights Top Grad lix
Effeclancy
Weights & Grad
Weights & Grad
Weights Grad
Weights & Top Grad ldx
Weights & Top Grad Idx
Other Clients
Client 1
Client
Other Clients
Client 1
Client N
Greedy Topology Adjustment in Baseline Frameworks Robust Thompson Sampling- basen Adjustment (TSAdi) in FedRTS
Illustration of topology adjustment in existing baselines and FedRTS. Left: Existing baselines adjust model topology based on myopic and unstable aggregated weights and gradients via deterministic magnitude pruning and reactivating, resulting in greedy adjustment and high communication overhead. Right: FedRTS introduces Thompson Sampling-basee Adjustment (TSAdj) to adjust the topology based on farsighted and stable probability distributions, achieving robust topology and low communication overhead.
Figure/ 1:
Current methods rely on myopic, aggregated information from a small subset of participating clients, ignoring data from the majority of unseen clients and prior knowledge. This leads to greedy adjustments and reduced robustmess [25. (2) Unstable topology: Deterministic adjustments based solely on aggregated information are prone to instability due to heterogeneous data distributions, resulting in unstable model topologies. (3) Communication inefficiency: Transmitting extensive auxiliary data (e.g., full-size gradients) for topology updates imposes high communication costs. These limitations hinder the ability current methods to handle client availability, data heterogeneity, and communication costs effectively, ultimately leading to suboptimal performance and inefficient resource utilization.
To address these challenges, we reframe federated pruning as a combinatorial multi-armed bandit (CMAB) [5) problem and identify the above issues located in myopic observation and deterministic decision. Building on this insight, we propose Federated Rubust pruming via combinatorial Thompson Sampling (FedRTS). a novel framework designed to derive robust sparse models for cross-device Fl., as illustrated in Fig. 2 FedRTS introduces the Thompson Sampling-based Adjustment (TSAdi) mechanism, depicted in Fig. (right), to address the shortcomings of existing methods. First, TSAdj leverages farsighted probability distributions (including prior information from unseen clients) to mitigate the impact of partial client participation. Second, it uses probabilistic decisions based on stable, comprehensive information for topology adjustment. Third, FedRTS reduces communication overhead by requiring clients to upload only top-gradient indices instead of dense gradients.
We evaluate FedRTS on computer vision and natural language processing datasets, demonstrating its effectiveness in handling client availability and data heterogeneity, FedRTS achieves higher accuracy, better generalization, and lower communication costs compared to state-of-the-an (SOTA) methods. For instance, on the CIFAR-10 dataset with the ResNet18 model, FedRTS achieves either a 5. % accuracy improvement or a 33.3% reduction in communication costs compared to SOTA frameworks. To our knowledge, this paper is the first work to analyze federated pruning through a CMAB lens and apply combinatorial Thompson sampling stabilize topology adjustments in FL.
2
Preliminary and Challenges
2.1 Federated Dynamic Pruning
In federated pruning, .V'' resource-constrained clients collaboratively train sparse model using their local datasets D,,, n E http:////hhhccccooooooooo//////r
Given the target density d', the objective is to solve the
Baseline's workflow:

---

following optimization problem:
N (W, m. Dn), s.t. d d,
min W.m
where W represents the model weights, E {0, (W) denotes the sparse model topology (also called mask), Jn (-) is the objective function depending on the task of the n-th for client n (e.g..
cross-entropy loss for the image classification task), d sum(m) is the density of the topology m. (m))
and Pn. is set as the proportion of the data size of client n, typically set pa. (Dn)/ Σ (Da).
To solve the problem in Eq. I under the target density constraint d', existing federated pruning frameworks [1 57 24
19
18 42) apply dynamic sparse training techniques [TT 48] [22]. These
frameworks iteratively adjust sparse on-device models during training while maintaining the density level d S d' The process begins with a sparse model initialized via random pruning and follows two-loop training procedure: In the inner loop, the model topology m remains fixed, and the model weights W updated through traditional FL rounds. After AT inner loops, as illustrated in Fig. [ (left), the framework enters the outer loop, where clients upload additional data (specifically, the gradients of the pruned weights) the server. The server then adjusts the model topology by pruning and reactivating based on the aggregated weights and gradients.
2.2 CMAB-Based Problem Formulation
The Combinatorial Multi-Armed Bandit (CMAB) [5 55 26
is sequential decision-makee making frame- work where an agent selects combinations of arms (called super arms) with unknown reward distribu- tions. The objective is to maximize cumulative rewards by balancing the exploration of uncertain arms and the exploitation of high-performing ones.
We formulate the topology adjustment as CMAB problem, where each link m, in the model topology serves as an arm. each outer loop I, the server selects an action St, which includes K arms, where K = d(m)). Selected arms i E S. are activated, while others i $ S: are deactivated, i.e,, ma,i Lees, After playing action, the new sparse weights W; = W0 C my will be distributed to the clients for further training. The server then observes outcomes X, (X,,1,... .X, for all arms, drawn from distributions with unknown expectation μ. After that, the server obtains the unknown rewards R2 R(S,, Xt). At the next round t + the previous information {X+|1 < S it is the input to the adjustment algorithm to select the action S Following previous work 26) we assume that the expected reward of an action St only depends on S, and and the mean vector μ4, i.e. there exists function such that [[ = Ex, [RS X.)] = r(S.. p)). Assuming the number of adjustments is T, the goal of CMAB is to maximize the cumulative reward, i.e., max Σ IR [R.)] 1 r(S,,
2.3 Challenges in Previous Federated Dynamic Pruning Methods
From the CMAB aspect, we can rigorously analyse the challenges in the previous methods. After taking the action S, to determine topology my, previous methods observe the delay outcomes X; at the next outer loop + defining Xt,, for i-th arm with the top importance score; otherwise. Xe.; = 0. And the next action S2+1 is selected merely based on current outcomes X,, i.e.
S = [i 1}. Thereby, they face three significant challenges:
Existing frameworks only observe the outcomes in the outer loop, ignoring the inner loop. Moreover, they discard all previous outcomes {X S S 1-1,, excluding information from unseen clients and previous data, leading to a myopic and greedy topology adjustment that is difficult exploit from a global view.
Greedy Adjustment:
Previous methods make a deterministic decision to select an action S, based on unreliable outcomes only, without considering the high variance of outcomes and the expectation of distribution μ. Therefore, the selected action St is hard to maximize the reward r r(St, 14), leading to an unstable topology.
Unstable Topology:
Communication Inefficiency: To compute the outcomes X, for all arms, existing frameworks use the magnitudes of aggregated weights and gradients as importance scores for active and inactive
In this paper. (:) is the cardinal number of the set.
3

---

Full-size
Pruned Weights
Probability Aggregrated Distribution
Updated Probability
Aggregrated Weights
Adjusted Weights
Weights
Weights
Distribution
Adjusiment Probability
Pruning
Server
3. Aggregation
5. Aggregation
Clients
Updating
Ü Udlating
Top Grad Idx
2. Training
4. Training
Inner Loop for Weights Updating
Outer Loop for Topology Adjustment by TSAdj
The overview of the FedRTS, which integrates TSAdj and utilizes the two-loop updating develop a robust sparse model.
Figure 2:
arms, respectively. As result, clients must upload gradients for inactive weights, leading to a total communication cost comparable to that of dense model, thus lacking communication efficiency. Although some approaches try to mitigate this by uploading only the top gradients [18, [1] or placing adjustments on the client side [[ these greedy methods make the adjustment more unstable, leading to suboptimal performance.
3 Methodology
In this section, we present FedRTS, a novel federated pruning framework designed to develop robust model topologies, as illustrated in Fig. 2 We begin by detailing the TSAdj mechanism, which serves as the core component for searching robust sparse topologies. Next, we provide an overview of FedRTS that integrates TSAdj. Finally, provide the theoretical regret upper bound of TSAdj.
3.1 Thompson Sampling- Adjustment (TSAdj)
We find that the core source of the aforementioned challenges in existing methods lies in deterministic decision strategies and myopic observations. Therefore, we propose the Thompson Sampling- -ased Adjustment (TSAdj) mechanism, which includes a probabilistic decision strategy based on farsighted observations. Moreover, TSAdj effectively reduces communication overheads.
Compared directly using myopic outcomes X, make deterministic decisions, our proposed TSAdj maintains individual posterior probability distributions for each link in the model topology m during training. The higher feedback link i has gained from previous observations, the closer the expectation of its probability E[P. approaches 1, indicating higher likelihood of being selected. In the outer loop for topology adjustment, the server samples random variables ç, where & P., and selects an action S; as follows:
S. {i Top(E, K)},
where Top(E, K) are the indices of top-K elements in ç. The action S; is determined by the posterior distributions P, rather than deterministically based on outcomes, thereby providing more stable topology with lower variance [1 compared to existing approaches.
Unlike existing approaches that develop the outcomes using immediate and myopic data in the outer loop, TSAdj derives much more comprehensive outcomes X, from both the inner and outer loops. After performing action S., the outcome X, is observed in the end of loop 4, and is formulated fusion of individual outcomes X and aggregated outcomes X:99.
X, = 7x + +11 7) Σ P.X..
WEC,
where y is the trade-off ratio, C, is the set of clients that participate FL in loop t. This fusion mechanism mitigates biases that arise from unstable aggregated data.
We consider the seni-outsomes for X-000 and X7 the inner loop, iee, only the arms i S, have the outcomes. We define constant < K, which denotes the number of core links (arms) in the

---

model topology, and during the adjustment, we expect that K - R less important links are pruned. while K x candidate links are reactivated. Following previous methods, we use the magnitude of weights to get the outcomes for active arms E St. Therefore, at the end of inner loop, we have
2 h(i, (W x), X h(i, [ k)), E
where W241 and W represent the aggregated weights and client n's weights, respectively. Here we use ++ instead of i because the local training is finished. 1(-) is a discriminative function defined as h(i, r. k) TTpp(w..)) In the inner loop, for arms i & St, both the aggregated outcomes X2, and the individual outcomes Xy, are set to None.
We consider the full outcomes of X and X for outer loop. Beyond the outcomes of active arms in Eq. we estimate the outcomes for inactive arms i $ St using the magnitudes of their gradients,
X 0.5, XL, h(i, G - x); $ St,
where the 17+11 denotes the gradients of the weights W Here, K - is used to treat some inactivated arms as candidates for reactivation. We do not use the aggregated gradients G to compute X due to the high variance. Notably, to achieve Eq. 5 the clients only need to upload the Top indices of gradients magnitude, 1 = significantly reducing the communication overhead.
K k), rather than the full gradients,
To construct posterior probability distribution, TSAdj updates the distribution based on outcomes X, Following the Thompson Sampling framework, each P, is modeled as Beta distribution with factors a; 3,, representing the likelihood of selecting an arm into Sy: a higher as shifts E[P;] towards whereas higher 3, shifts towards The (as, B.) are updated via Bayes' rule, leveraging its conjugacy properties and using the outcomes Xz, as follows:
(as, (.) (a. + XXe, 3, + A(1 X(,)), X1,3 # None,
(6)
where is a scaling factor that determines the influence of outcomes. Over time, the distribution gradually converges towards the true distribution, aligning with the observed outcomes. The overflow TSAdj is shown in Algorithm
Algorithm 1 TSAdj
Input: Participated clients Ct, uploaded sparse weights (Wi+))eee and top gradients' indices (Ir hne,, trade-off ratio 7, scaling factor X, global distribution factors (a,, .), number of selected arms K, sparse model topology my-
Output:
Updated sparse weights W4+1 and topology m4+1
W + Enec, Wr
X {X")nEC, < calculate with W (Wiiheee, and (IAii by Eq. and Eq.
X, (ar, Bi) t -aa AXX,, 3, x(1 X,,)). for 1,2, 2...... (X,) and X,, * None
X2 < yX +(1-7)
S411 filE: E Top(E, K)). ς= (E:kk Bela(a; 3,)) // Select new action
m++1 t- (1ES.+1)
Adjust topology based on selected action
W411 WHth O m4+1
In summary, TSAdj leverages the posterior probability distributions P to probabilistically guide topology adjustments and uses comprehensive outcomes X₃ to update the distributions, which mitigates instability caused by myopic adjustments, enabling smoother convergence and developing a more reliable topology. Moreover, TSAdj requires the clients to upload only the most critical gradient information, thereby reducing the communication overhead.
3.2 Proposed FedRTS framework
FedRTS is novel federated pruning framework designed to address the limitations of existing dynamic sparse training methods by integrating the Thompson Sampling-based Adjustment (TSAdj) mechanism, as illustrated in Fig. 2 The framework begins with an initialized model weight and sparse topology sampled from Beta distributions P. FedRTS employs a two-loop training process to iteratively update model weights and refine the sparse topology.
5

---

In the inner loop, the model topology remains fixed while the server updates the model weights and distribution P based on semi-outcomes. In the outer loop, the server collects the full outcomes by requiring clients to upload the top gradient indices of inactivated weights. Using this information, the server applies TSAdj to make robust topology adjustments, and the updated topology then distributed to clients. FedRTS continues this iterative process until model convergence. The details of FedRTS are shown in Algorithm and Sec. B.2
By integrating TSAdj, FedRTSS introduces a novel approach to sparse topology adjustment. Leverag- ing Thompson Sampling, it mitigates the instability caused by unstable aggressive topology, ensuring smoother convergence through probabilistically guided adjustments based on historical information. This adaptive adjustment strategy enhances the robustness of the sparse topology and improves overall model performance in FL tasks.
3.3 Overhead Analysis
The overhead of TSAdj arises from maintaining and sampling the Beta distribution on the server. In each round, the server performs the following operations with (Ct) sampled clients: weight averaging with a time complexity of (((C,)())) computing the outcome using Quicksort with an expected time complexity of (((C))WW) element-wise Beta distribution updates in O((W)) and arms selection ((W)). The overall complexity thus simplifies to O((C,) (W)). Compared to the baseline complexities of FedMef, FedTiny, and PrunelL, which are also ((C))W)) TSAdj achieves the same computational order. This demonstrates that TSAdj introduces no significant additional computational burden the server, even with large models.
Critically, TSAdj introduces no additional computations on client devices compared the federated pruning baseline, as its overhead is entirely server-side. In cross-device federated learning, the server typically assumed to possess substantial computational resources; therefore, TSAdj only introduces a slight overhead on the system.
3.4 Theoretical Analysis
For simplifications, we omit the inner loop of FedRTS to isolate the TSAdj mechanism and consider only semi-outcomes, i.e., ignore the outcomes Xt,; that & S. We adopt the following assumptions:
Assumption 3.1. (I-comtinuitty) AL E TR. VS, p. pl satisfies (r(S, p) (') Lll 1'Il1-
Assumption 3.2. (Independent importance score) The importance scores used pruning are treated as mutually independent.
Assumption 3.3. (Mean-field Approximation) when {z;} are mutually independent, the discrimi- native function h(()) admits a mean-field approximation: h(l,, x, K) = 1ie(z,x) Re 12,2a. where the threshold a is determined relf-consistentlly via mean-field decoupling (independent of individual x:)) and satisfies (x:) Σx2) CDF;(a) K, where CDF, the cumulative distribution function of x.-
Assumption 3.1 is standard in bandit optimization work
26
implicitly or Assumption 3.2
explicitly adopted in pruning methods 46 12 52
Assumption
3.3 holds for large scale (a))
(>100k) 53 54 35).
While weight magnitudes are not strictly theoretically independent when used as importance scores, both empirical and theoretical evidence supports simplification in Assumption 3.2 (1) Recent work demonstrates that trained weights in large networks exhibit asymptotic independence [54] (33. and
(2) this assumption is well-established in the pruning work [22 46 where weight dependencies
typically disregarded during selection. While other importance scores (e.g.. Fisher information (52)) might better satisfy independence, they are computationally prohibitive in FL. Thus, we follow prior works [24] 19 to apply weight magnitude pruning, acknowledging minor discrepancy between theory and practice. Under assumptions 3.2 and 3.3 outcomes X,,; simplify to:
X = 72 + (1 - 7) Σ
pm W7,220 iE S.
(7)
which is mutually independent.

---

CIFAR-10
CINIC-10
TinylmageNet
SVHN
0.75
0.00
ResNet18
Mean Mean
0.800
0.65
0.775
0.59
0.750
0.60
Accuracy
0.48
0.6
ShuffieNetV2
0.55
0.045
0.45
0.42
0.035
0.030
Commmumicaiin Cost Ratio
Communicction Cost Ratio
Communiccttio Cost Ratio
Communication Cost Ratio
FedAVG
PruneFL
FedTiny
FedMef
FedSGC
FedDST
FedRTS
Figure 3: Testing accuracy of FedRTS and different federated pruning baselines the four CV datasets with different densities, where the ratio is communication cost relative to dense FedAVG.
To analyze the worst-case performance of TSAdj. we define the cumulative regret Reg(T") as:
Reg(T (T)
Σ
As
(8)
where As, =S" - (.)
0} and S is the greedy optimal action based on which is obtained by Algorithm 3 The maximum reward gap is set as Amax = maxş As. The maximum reward gap of actions containing arm s A max maxs:es As. define S and S, are sequences, the k-th element added to S We
K), and & E denote ST. (s. ................................ $ and Si. (St.1. st,a). For any arm define the marginal reward gap -r(S r( (s). Inspired by previous work 26], we provide a regret upper
ie.. 5 (8i,....
k) S₁
Ar, = r S p))
bound for TSAdj.
Theorem 3.4. (Upper Bound) Under assumptions 3.2
3.3 and 3.1 and with outcomes X, defined in
Eg. 7 the regret Reg(T) TSAdj can be upper bounded by:
6A mAx log
KU + 8KE
RTg(T)
Σ sf
2K + 4(W)
A maz
(A, 2LKeJ²
6
Amaz L2 Log
=
Σ
max kigg:;
A maz
A
for any such that Vs + s and s Sr, As,k > 2LKe, where universal constant.
The proof is provided in Sec.
C.2 Crucially, theorem hold for any pruning method satisfying
Assumption 3.2 and 3.3 including future advancements in efficient independent-scoring techniques.
4 Evaluation
To validate the efficacy of FedRTS, conduct comprehensive experiments in this section. Notably, we evaluate each experiment five times, reporting the mean results along with the standard errors. In the figures, the shaded area represents the standard emors. In the table, the best results are highlighted in purple color, while the second-ber -bstt results are marked in blue color.
4.1 Experiment Setup
We provide overview of the experimental setup in this section, with additional details in Sec.
7

---

Density
Target
Method
PPL
Avg. Acc
Comm. Cost 4
0.8
FedAVG
20.56
014387
260.41MB
FedDST
20.10
0.4261
138.30 MBB
Mean Accuracy
FedSGC
26.13
0,4110
207.45 MB
50%
0.6
FedMef
20.61
0.4352
165.96 MB
FedRTS
18.54
0.4422
138.84 MB
FedDST
24.46
0.4263
86.26 MBB
FedSGC
32.39
0.3939
129.39 MB
0.4
FedAVG
30%
FedMef
21.00
0.4304
103.51 MB
FedDST
FedRTS
18.56
0.4405
86.44 MB
FedMef
FedDST
26.49
0,4219
60.22 MB
0.2
FedRTS
20%
FedSGi:
FedMef
43.00
21.53
0,4293
72.26 MB
IID
1
0.5
0.3
0.1
VedRTS
19.93
0,4333
60.34 MB
Degree of Data Heterogenelly
Table I: Performance comparison on TinyStories with GPT-2-32M.
Figure 4: Accuracy on CIFAR-I0 under various degrees of data heterogeneity.
Datasets and Models. Following previous work [88 19 1 24 on federated dynamic pruning, we conduct experiments on CV tasks using two lightweight models, ResNet18 [3] and Shuf- fleNetV2 [66], across four well-known image classification datasets: CIFAR-10 27.. CINIC-10 77.
TinylmageNet [8] and SVHN 43 For NLP tasks, we use the GPT-2-32M model on the TinyStories dataset [10,, language understanding benchmark designed for small language models.
Federated Learning Settings. Following the settings used in previous frameworks [8
19 [. we
conduct T maz = 500 communication rounds with 5 local training epochs. Batch sizes are set to 64 for CV tasks and 16 for NLP tasks. each round, 10 clients are randomly selected from total of N 100 clients. To generate data heterogeneity on the client, we utilize the Dirichlet distribution with factor a. The types of heterogeneity for CV and NLP tasks are different. CV tasks apply label imbalance with default. We perform an outer loop for topology adjustment every AT 10 inner loops until the total number of loops / reaches Tend 300. The optimizer used is SGD, with a learning rate of 7) 0.01.
0.5 by default. Unlabeled NLP tasks set data quantity imbalance, with
5 by
Baseline Settings. We select the following SOTA federated pruning frameworks as baselines: PruneFL (24]. FedTiny (18), FedDST [. FedSGC [57], and FedMef [19]. These methods incorporate dynamic pruning in FL and achieve SOTA performance across various settings, as detailed in Sec. F.2
Implementation Details. Following previous work [8] 19], we exclude bias terms, normalization layers, and the output layer from pruning while ensuring the overall density d < d'. Layer-wise sparsity follows the Kidos-RenniiKerneee distribution [II] We set the scaling factor A = 10 to match the number of selected clients per loop, ensuring that the averaged information maintains individual- level influence. The trade-off ratio is set as y = 0.5 to assign equal importance to the individual and
aggregated model. We set the layer-wise x² K duady (1 (1+ cos (7/- (.s.)) )) where K is the number
of active weights at /-th layer and Caaj is 0.4 by default, is adopted directly from prior works [19 Training FLOPs and communication costs are calculated as described in Sec. F.4
4.2 Performance Evaluation
To show the effectiveness of FedRTS, we conduct experiments on CV and NLP tasks under various target density levels. Broader experiments including efficiency analysis are in Sec. E.2 and E.3
Computer Vision Tasks. the CV tasks, we conduct experiments using the ResNet18 and Shuf- fleNetV2 models, testing four target density levels: 50%, 30%, 20%, and 10% on CIFAR-10, 10, CINIC-10, TinylmageNet, and SVHN datasets, reporting the accuracy and communication costs ratio per outer loop. In some cases, FedRTS achieves similar accuracy to FedAVG at the 30% density ratio; therefore, results for the 50% density ratio are omitted. As shown in Fig. B FedRTS consistently outperforms all baseline methods in most scenarios in terms of both accuracy and communication efficiency. For instance, in the experiment with ResNet18 in CIFAR-10, 10, FedRTS achieves a 5.1% 1% improvement in accuracy tion cost. These gains are attributed to the robust adjustment, stable topology, and communication efficiency provided by TSAdj in FedRTS.
the best baseline methods while maintaining a similar communica-
An evident trend is the superior accuracy achieved by ResNet18 compared to ShuffleNetV2, due to ResNet18's larger parameter space and higher representational capacity. Furthermore, FedDST and

---

0.75
0.750
Mean Accuracy
0.70
Accuracy
0.700
0.65
FedTiny
0.675
(y=
0.60
FedDST
FedRTS (y-1)
ded
0.650
FedRTS (y=
0.55
FedRTS
FedRTS
0.625
100%
50%
30%
10%
10%
20% Target Density
30%
Participation
Figure 5: Accuracy CIFAR-10 10 with various participation ratios of clients.
Figure 6: Accuracy on CIFAR-10 10 for FedRTS and various variants.
FedMef consistently outperform other baseline methods. Based on these empirical observations, we select R the default CV model and identify FedDST and FedMef as the primary reference for subsequent experiments.
Natural Language Processing Tasks. To evaluate the effectiveness of FedRTS across different domains, we conduct experiments on NLP tasks using the TinyStories dataset with the GPT-2- 32M model. We test three target density levels: 50%, 30%, and 20%. Perplexity (PPL), which assesses model performance by considering the entire probability distribution in generated text, serves the primary evaluation metric. As shown in Tab. T FedRTS outperforms all baselines, demonstrating its superiority in the NLP domain. Notably, FedRTS achieves better performance in perplexity than in accuracy-bord based evaluations, even surpassing full-size FedAVG low-density levels. This improvement may stem from its probabilistic adjustment strategy, which enhances flexibility and adaptability during optimization. Unlike deterministic approaches, probabilistic adjustment enables FedRTS to prioritize critical parameters effectively, improving its ability to adapt to complex probability distributions. This particularly beneficial for NLP tasks, where capturing intricate text patterns is essential, leading to lower perplexity and stronger performance in low-resource settings.
4.3 Robustness Analysis
To demonstrate the robustness of FedRTS in the face of heterogeneous data distributions and partial client participation, conduct experiments with different degrees of data heterogeneity and client availability in this section. Further experiments on the impact the hyperparameters X, K, and AT' are provided in Sec.
The Impact of Data Heterogeneity, Data heterogeneity, or non-independent and identically dis- tributed (non-IID) data, is critical factor affecting performance in FL. To demonstrate the robustness of FedRTS, we conduct experiments with varying degrees of data heterogeneity on the CIFAR- 10 and TinyStories datasets. By adjusting the Dirichlet distribution factor data heterogeneity, where a lower a indicates higher heterogeneity. As shown in Fig and Fig. [4] FedRTS outperforms all baselines, particularly in highly heterogeneous settings, demonstrating its effectiveness handling non-lII data. This improvement is primarily attributed to the stable topology produced by TSAdj in FedRTS.
control the degree of
The Impact of Client Availability. Client availability is another significant challenge in FL. To evaluate the robustness of FedRTS under different levels of client availability, conduct experiments with participation ratios of 100%, 50%, 30%, 10% using a total adopt high learning rate of I with SGD, as Adam
clients. To mitigate slow
convergence at lower participation levels, exhibited instability with NaN values in our experiments. As shown in Fig. 5) FedRTS consistently outperforms all baselines, particularly at low participation ratios, demonstrating its adaptability and robustness in limited-client scenarios.
4.4
Ablation Study
To analyze the individual contributions of FedRT'S in addressing greedy and unstable topology adjustment problems, conduct ablation study on the CIFAR-10 dataset with various target

---

density levels. We consider the benefits of FedRTS to come from three aspects: probabilistic decision, farsighted information, and stability from the fusion mechanism in Eq. To evaluate these aspects independently, we consider the following variants of FedRTS: (1) FedRTS (T = 0): This variant does not use the aggregated information to update the probability distribution. (2) FedRTS (7 = 1): This variant only uses the aggregated information to update the probability distribution, which disables the fusion mechanism to reduce stability. (3) FedRTS without TS (r) = 1); This variant fuses historical information via momentum mechanism similar to FedAdam [49] and uses deterministic adjustment to obtain the new topology, disabling both probabilistic decision and fusion mechanism. (4) FedTiny: This serves as baseline to evaluate the overall effectiveness of FedRTS, disabling all three aspects.
The results in Fig. [ demonstrrate the effectiveness of FedRTS. First, the performance of FedRTS and FedRTS (y = 0) is similar but better than FedRTS ( = 1), demonstrating that aggregated information suffers from instability. A fusion mechanism including individual information can make the adjusted topology more stable and achieve better performance. Second, without deterministic adjustment, FedRTS w/o TS (? = 1) performs much worse than FedRTS ( 1), indicating the benefits of probabilistic adjustment. Third, FedRTS w/o 7S (7 i) better than FedTiny, showing the effectiveness of farsighted information. Thus, the ablation study demonstrates FedRTS's effectiveness in terms of probabílistic decision, farsighted information, and stability from the fusion mechanism.
5
Limitation
While FedRTS with TSAdj effectively addresses key challenges: greedy adjustments, unstable topologies, and communication inefficiency in federated dynamic pruning, our approach shares common limitation with prior magnitude-based pruning methods [12 46). The theoretical analysis relies on Assumption 3.2 which presumes independence among importance scores. In practice, weight magnitudes exhibit only asymptotic independence [53]. creating a minor but acknowledged gap between theory and empirical results.
We considered alternative importance metrics like Fisher information [52 that might better satisfy the independence requirement. However, their computational complexity makes them impractical for federated settings with literature, therefore adopt magnitude-basee pruning while transparently acknowledging this theoretical-empirical discrepancy, a compromise that reflects the inherent trade-offs in practical federated learning systems.
clients. Following established practice in the pruning
While the mean-field approximation in Assumption 3.3 provides theoretical grounding for TSAdj, its validity weakens for extremely small models (<100K parameters) where finite-size effectt become significant [53]. However, at such small scales, the benefits of pruning become marginal, as these models can typically be trained directly on-device without compression. Thus, this limitation has minimal practical impact on FedRTS.
The FedRTS also presents the following two limitations. Fairness and bias: The method dynamically adjusts model structure per global feedback. In highly heterogeneous settings, this could uninten- tionally bias the model toward data-rich or majority-class clients. Security/privacy considerations: While the method reduces communication cost, sharing top gradient indices might still leak sensitive information.
6 Conclusion
In this paper, we analyze federated pruning from the perspective of combinatorial multi multi-armed bandits and identify key limitations in existing methods, including greedy adjustments, unstable topologies, and communication inefficiencies. To address these challenges, we propose Federated Robust Pruning via Combinatorial Thompson Sampling (FedRTS), novel framework for developing robust sparse models. The core component of FedRTS, the Thompson Sampling-based Adjustment (TSAdj) module, enhances robustness and performance by making probabilistic decisions based on stable, farsighted information rather than deterministic decisions driven by unstable, myopic observations. We provide a theoretical regret upper bound for TSAdj and conduct extensive experiments, demonstrating that FedRTS achieves ofate--f--hh-ant performance in both computer vision and natural language processing tasks.
10

---

Acknowledgments and Disclosure of Funding
This paper is partially supported by Hong Kong Research Grants Council (RGC) grant C1042-23GF and grant #1 #11203523 and Hong Kong Innovation and Technology Fund (ITF) grant MHP/061/23 and grant MHP/034/22.
References
[1] Sameer Bibikar, Haris Vikalo, Zhangyang Wang, and Xiaohan Chen. Federated dynamic sparse training: Computing less, communicating less, yet learning better. Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 6080-6088, 2022.
[2] Ning Chen, Tie Qiu, Weisheng Si, and Dapeng Oliver Wu. Daimo: motif density enhances topology robustness for highly dynamic scale-free iot. IEEE Transactions on Mobile Computing. 2024.
[3] Ning Chen, Tie Qiu, Xiaobo Zhou, Songwei Zhang, Weisheng Si, and Dapeng Oliver Wu. distributed co-evolutionary optimization method with motif for large-scale iot robustness. IEEE/ACM Transactions on Networking, 3265):4085-4099 2024.
[4] Ning Chen, Songwei Zhang, Xiaobo Zhou, Song Cao, and Tie Qiu. Fast robustness enhancement for dynamic iiot topology with adaptive bayesian learning. IEEE Transactions Mobile Computing, 2025.
[5] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference machine learning, pages 151-159. PMLR, 2013.
[6] Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research, 17 1-0): 2016.
[7] L. N. Darlow, J. Crowley, A. Antoniou, and A. Storkey, Cinic-10 is imagenet or 2018.
10. arXiv preprint
[8] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pages 248-255. Ieee, 2009.
[9] Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXivv1907.04840 2019.
[10] Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english? arXiv preprint arXiv:2305.07759 2023.
[11] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pages 2943-2952. PMLR, 2020.
[12] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural works with pruning, trained quantization and huffman coding. arXiv preprint a 110.0095,,.00149, 2015.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778. IEEE, 2016.
[14] Yihui Hc, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. Proceedings of the IEEE international conference on computer vision, pages 1389-1399 2017.
[15] Robert Hönig, Yiren Zhao, and Robert Mullins. Dadaquant: Doubly-adaptive quantization for communication-effcieent federated learning. International Conference on Machine Learning, pages 8852-8866. PMLR, 2022.

---

[16] Juntao Hu, Zhengjie Yang. Peng Wang, Guanyi Zhao, Hong Huang, Zhimin Zong, and Dapeng Oliver Wu. Federated learning for medical image analysis: Privacy-preserving paradigms and clinical challenges. Transactions Artificial Intelligence, 1(1):153-169 2025.
[17] Hong Huang and Dapeng Wu. Quaff: Quantized parameter-effiieet fine-tuning under outlier spatial stability hypothesis. arXiv preprint arXiv:2505, 14742, 2025.
[18] Hong Huang, Lan Zhang, Chaoyue Sun, Ruogu Fang. Xiaoyong Yuan, and Dapeng Wu. Distributed pruning towards tiny neural networks in federated learning. In 2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS), pages 190-201. IEEE, 2023.
[19] Hong Huang, Weiming Zhuang, Chen Chen, and Lingjuan Lyu. Fedmef: Towards memory- efficient federated dynamic pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 27548-27557, 2024.
[20] Hong Huang, Decheng Wu, Rui Cen, Guanghua Yu, Zonghang Li, Kai Liu, Jianchen Zhu, Peng Chen, Xue Liu, and Dapeng Wu. Tequila: Trapping-fiet ternary quantization for large language models. arXiv preprint arXiv:2509. 2,389, 2025.
[21] Steven A Janowsky. Pruning versus clipping in neural networks. Physical Review A, 31(2)) 6600, 1989.
[22] Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top- kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33: 20744 20744-20754, 2020.
[23] Divyansh Jhunjhunwala, Advait Gadhikar, Gauri Joshi, and Yonina C Eldar. Adaptive quantiza- tion of model updates for communication--ffici federated learning. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3110-3114. IEEE, 2021.
[24] Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K Leung, and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices. IEEE Transactions on Neural Networks and Learning Systems, 34(12):0034410036 2022.
[25] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and trends@ machine learning, 14(1-2):1- 1-000 2021.
[26] Fang Kong, Yueran Yang, Wei Chen, and Shuai Li. The hardness analysis of thompson sampling for combinatorial semi-bandits with greedy oracle. Advances in Neural Information Processing Systems, 34:26701-26713 2021.
[27] A. Krizhevsky, G. Hinton, and et al. Learning multiple layers of features from tiny images. In Proceedings of the International Conference on Machine Learning. PMLR, 2009.
[28] Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
[29] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2018.
[30] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint 1907v21907.022166 2019.
[31] Zonghang Li, Tao Li, Wenjiao Feng, Rongxing Xiao, Jianshu She, Hong Huang. Mohsen Guizani, Hongfang Yu, Qirong Ho, Wei Xiang, and Steve Liu. Prima.cpp: Fast 30-70b llm inference on heterogeneous and low-resource home clusters, 2025. URI. https:tpp/.. / //arxivv org/ hte/aabs/5000 08791
12

---

[32] Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learning efficient convolutional networks through network slimming. Proceedings of the IEEE international conference on computer vision, pages 2736-2744, 2017.
[33] Xiaolong Ma, Minghai Qin, Fei Sun, Zejiang Hou, Kun Yuan, Yi Xu, Yanzhi Wang, Yen-Kuang Chen, Rong Jin, and Yuan Xie. Effective model sparsification by scheduled grow-and-prune methods. arXiv preprint arXiv:2/06.0988) 2021.
[34] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Commuuication-efficiin learning of deep networks from decentralized data. In Artificial intelligence and statistics, puges 1273-1282. PMLR, 2017.
[35] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean- field theory of two-layers neural networks: dimension -ree bounds and kernel limit. In Conference on learning theory, pages 2388-24644 PMLR, 2019.
[36] Fanxu Meng, Hao Cheng, Ke Li, Huixiang Luo, Xiaowei Guo, Guangming Lu, and Xing Sun. Pruning filter in filter. Advances in Neural Information Processing Systems, 13:17629-77640, 2020.
[37] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1-12, 2018.
[38] P Molchanov, S Tyree, T Karras, T Aila, and J Kautz. Pruning convolutional neural networks for resource efficient inference. In 5th International Conference on Learning Representations, ICLR 2017-Conference Track Proceedings, 2019.
[39] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:161..064a 2016.
[40] Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11264-11272 2019.
[41] Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from a network via relevance assessment. Advances in neural information processing systems, 1, 1988.
[42] Muhammad Tahir Munir, Muhammad Mustansar Saced, Mahad Ali, Zafar Ayyub Qazi, and Ihsan Ayyub Qazi. Fedprune: Towards inclusive federated learning. arXiv preprint arXiv:2110.1 14205, 2021.
[43] Y. Netzer, T. Wang. A. Coates, A. Bissacco, B. Wu, and A. Ng Reading digits in natural images with unsupervised feature learning. In Proceedings of the 2011 Neural Information Processing Systems (NIPS), 2011.
[44] Jeff M Phillips. Chernoff-hoeffding inequality and applications. arXiv preprint 2012.
[45] Hongming Piao, Yichen Wu, Dapeng Wu, and Ying Wei. Federated continual learning via prompt-based dual knowledge transfer. In Forty-first International Conference on Machine Learning, 2024.
[46] Xin Qian and Diego Klabjan. A probabilistic approach neural network pruning. In Interna- tional Conference on Machine Learning, pages 6640-8649, PMLR, 2021.
[47] Xinchi Qiu, Javier Rernandez-Marques, Pedro PB Gusmao, Yan Gao, Titouan Parcollet, and Nicholas Donald Lane. Zerofl: Efficient on-device training for federated learning with local sparsity. arXiv preprint arXiv:2208. 02507, 2022.
[48] Md Aamir Raihan and Tor Aamodt. Sparse weight activation training. Advances in Neural Information Processing Systems, 13:15625-1 2020.
13

---

[49] Sashank Reddi, Zachary Charles. Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
[50] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-efficenn federated learning method with periodic averaging and quantization. In International conference on artificial intelligence and statistics, pages 2021- 2031. PMLR, 2020.
[51] Aadirupa Saha and Branislav Kveton, Only pay for what is uncertain: Variance-adaptive thompson sampling, arXiv preprint arXiv:2303.09033 2023.
[52] Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. Advances in Neural Information Processing Systems, 33:1 33:18098-18109 2020.
[53] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 130G3):1800-1852, 2020.
[54] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725-752, 2020.
[55] Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1 2019.
[56] Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33:6377-653 -3899 2020.
[57] Chris Xing Tian, Yibing Liu, Haoliang Li, Ray CC Cheung, and Shiqi Wang. Gradient-congruity guided federated sparse training. arXiv preprint arXiv:2405.01 0155.0118) 1889, 2024.
[58] Shuguang Wang, Qian Zhou, Kui Wu, Jinghuai Deng, Dapeng Wu, Wei-Bin Lee, and Jianping Wang. Interventional root cause analysis of failures in multi-sensor fusion perception systems. Proceedings 2025 Network and Distributed System Security Symposium, 2025. URL https //api.semanticaaaee
org/ wwtp/orpp///rDDDD Corpus 276862477
[59] Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pages 544--122 PMLR, 2018.
[60] Yun Wang, Junjie Hu, Junhui Hou, Chenghao Zhang, Renwei Yang, and Dapeng Oliver Wu. Rose: Robust supersuue stereo matching under adverse weather conditions. arXiv preprint arXiv:2509.I9165. 2025.
[61] Yun Wang. Kunhong Li, Longguang Wang, Junjie Hu, Dapeng Oliver Wu, and Yulan Guo. Adstereo; Efficient stereo matching with adaptive downsampling and disparity alignment. IEEE Transactions on Image Processing, 2025.
[62] Yun Wang. Jiahao Zheng, Chenghao Zhang, Zhanjic Zhang, Kunhong Li, Yongjian Zhang, and Junjie Hu. Dualnet: Robust self-supervised stereo matching with pseudo-label supervision. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 1178-8186. 2025.
[63] Yichen Wu, Hongming Piao, Long- Kai Huang, Renzhen Wang, Wanhua Li, Hanspeter Pfister, Deyu Meng, Kede Ma, and Ying Wei. Sd-lora: Scalable decoupled low-rank adaptation for class incremental learning. arXiv preprint arXiv:2501.13119. 2025.
[64] Zhengjie Yang, Sen Fu, Wei Bao, Dong Yuan, and Albert Zomaya. Hierarchical federated learning with momentum acceleration in multi-tier networks. IEEE Transactions on Parallel and Distributed Systems, 34(10):262922) 22411, 2023.
[65] Zhengwu Yang and Han Zhang. Comparative analysis of structured pruning and unstructured pruning. In International Conference on Frontier Computing, pages 882-889. Springer, 2021.
[66] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6848-6856, 2018.
14

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificcton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The identified challenges and key claims presented in both the abstract and introduction precisely align with the paper's core contributions and methodological scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
15

---

Justification: In Section S
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
In the Section 3.4 and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All information, including hyperparameters, pseudo-code, is disclosed, and the source code is given.
Guidelines:
16

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets are public, and the anonymized version of codes is given, with a detailed readme file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nisscccppblic//uuut http:///cc/giiee//eeeuuubiiiiiin
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
17

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: answerYes
Justification:
In the Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experiments were performed five times with different random seeds, and standard errors are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: In the Section
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://earrpps.cccppll///ccccha
Answer: [Yes]
Justification: Yes, all respects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the Section D
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses such risks.
19

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not use existing assets
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssithcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
20

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standadd components.
Please refer to LLM policy (https://neuria) http://uurrips..ccoeeeeeeeeeeeee /00t:///eccc.eoeeeeee//////////0 for what should or should not be described.
21

---

Appendices Contents
Related Work
23
A.1 Neural Network Pruning
23
A.2 Federated Pruning...
23
A.3 Combinatorial Multi-Arm Bandit
23
Algorithm
24
B.1 TSAdj
24
B.2 FedRTS
24
Theoretical Details
26
Greedy Optimal Action
26
Proof of Theorem
26
Lemmas
27
D Broader Impact
29
Additional Experiments Results
29
E,1
The Impact of Hyperparameters
29
E.1.1
The Impact of trade-off ................................
29
E.1.2
The Impact of the scaling factor X
30
E.1.3
The Impact of the number of core links fi
30
E.1.4
The Impact of Adjustment Interval A7
30
E.2
Efficiency Analysis
30
E.2.1
Training Cost
30
E.2.2
Convergence Behavior
31
Broader Experiments
32
E.3.
FedRTS vs. FedCUCB
32
E.3.2
Pruning vs. Weights Quantization
32
Additional Setup Details
Datasets
33
Baselines
33
................................
Extra Information
34
Communication and Computational Cost
34
F4.1
Compression Strategy
34
F4.2
Communication Cost
34
E4.3
Computational FLOPs
35
22

---

A Related Work
A.1 Neural Network Pruning
is a widely used technique for reducing the computational and memory footprint of neural networks by eliminating redundant parameters. Pruning methods can be categorized into structured pruning [36 14 32 39], which removes entire structures like filters or layers, and unstructured pruning [12 21). which targets individual weights. While structured pruning simplifies model deployment by maintaining regular architectures, it often suffers from significant performance degradation at higher sparsity levels (e.g., beyond 10% (39), limiting its compression potential. In contrast, unstructured pruning can achieve sparsity levels exceeding 50% with minimal accuracy loss, making it a more flexible approach. For this reason, our discussion focuses primarily on unstructured pruning.
Neural network pruning [41 28
Traditional pruning pipelines follow train-prune peppp-ruuueaaatee rrune-retrain paradigm: dense model is first trained, less important weights are pruned based on some criterion (e.g.. magnitude [2], gradients [41,88],
or Fisher information (52]). and the model is then fine-tuned to recover performance. However, this process is computationally expensive, as it requires training a dense model before pruning.
To avoid this overhead, recent work explores dynamic sparse training (DST) [37 [1] where sparse topologies are optimized during training without ever densifying the model. While promising. existing DST methods rely on deterministic high variance in model performance and inefficient exploration sparse topologies, especially in federated learning scenarios with heterogeneous data and partial client participation. To mitigate these challenges, we propose TSAdj, a probabilistic adjustment mechanism that enables more stable and robust sparse topology evolution.
aandiing-an-regrowwl strategies, which can lead to
A.2 Federated Pruning
Federated Pruning is a technique that applies neural network pruning within the Federated Learning (FL. process. To avoid the requirements of dense training in traditional pruning methods, some previous methods determine the sparse model topology before federated training and do not adjust during the FL process, such SNIP [29] and Synflow (56). This approach of pruning initialization may overlook crucial data information, potentially leading to suboptimal model structures.
Dynamic sparse training methods, such those employed by PruneFL 24 adjust the model during FL rounds. However, these methods require the entire model gradient to sent to the server to ensure final performance, resulting in high communication costs. FedDST [[] and FedSGC [57] alleviate this issue by applying dynamic sparse training on clients. FedTiny [18) and FedMef [19 require clients only upload the Top gradients. Despite these advancements, these methods adjust the model topology based on limited information from the currently selected clients, leading to issues of greedy adjustment and unstable topology. FedRTS addresses these challenges by applying TSAdj, significantly mitigating the problems associated with limited client information and enhancing the robustness of model adjustments by leveraging probabilistic distributions.
A.3 Combinatorial Multi-Arm Bandit
The Multi-Armed Bandit (MAB) problem [55] is a fundamental framework for decision-making under uncertainty, where agent repeatedly selects among multiple actions ("arms") with initially unknown rewards to maximize cumulative gains. The Combinatorial Multi-Armed Bandit (CMAB) [5] extends this classic problem scenarios where rewards depend on combinations of selected arms rather than individual choices.
Two primary approaches have emerged for solving CMAB problems: The first is the Combinatorial Upper Confidence Bound (CUCB) [. which uses optimistic reward estimates to balance exploration and exploitation. The second is Combinatorial Thompson Sampling (CTS) [6] 59), which employs probabilistic sampling from posterior distributions to dynamically adjust its strategy.
While CUCB's deterministic nature makes it theoretically appealing for analysis, its inherent op- timism 5 can lead to persistently selecting clearly suboptimal arm combinations. This behavior prevents stable convergence, making CUCB less suitable in dynamic pruning where consistent per-
23

---

formance is erucial, as will be discussed in detail in Sec. E.3.1 For this reason, we built our TSAdj method on the more adaptive CTS framework.
B Algorithm
B.1
TSAdj
In each loop s, the aggregated weights W will be calculated in each loop when the server receives the weights W from each client E Ct and TSAdj is invoked to adjust the sparse topology my only in the outer loop. The outcomes X,,; for link m, are computed as described in Equation which balances global and client-specific contributions. Specifically, outcomes X and X are calculated based on Equations 4 on the server, using the aggregated weights W++1 and the uploaded weights 1 while X",, will be updated in the outer loop using the indices of the top K x gradients 1 from each client n based on Equation Outcomes X and X are combined to compute the final outcome X,, for link m. in Equation where y E [o, 1] controls the trade-off between global and client-specifie contributions, and p. reflects the relative weight of client based the size of its local dataset D,.. A larger y emphasizes client-specific observations, while a smaller yy prioritizes global contributions.
The posterior probability distribution P for each link m, in the topology m modeled as beta distribution parameterized by (a), At initialization, (a;, Be) are set to small positive values (e.g,, a; = 3, = 1) to represent uniform prior, ensuring that all links have an equal probability of activation at the outset. The beta parameters (as, 3.) for each link m, are then updated incorporating with the computed outcomes Xt.,, via Equation [6] where À controls the trade-off between exploration and exploitation by adjusting the impact of the current outcomes on the beta distribution's 's update. A larger À increases the influence of the current loop's outcomes Xt,s, accelerating the concentration of the Beta distribution towards certain probability. Conversely, smaller À preserves uncertainty to encourage exploration. Over time, as a and B, grow under the influence of and Xt,,, the Beta distribution becomes sharper and more concentrated, reflecting an increasingly certain probability of selecting m; as an active link in the topology m.
In each loop I, the topology adjustment dynamically activates or deactivates links based on probabilistic action S. in Equation where & is sampled from the updated posterior distribution P. For each link m, the probability& P.. Links are activated if their probabilities & rank among the top K in magnitude. The TSAdj mechanism outputs the updated sparse topology m4+1 and the weights W++1 O mc+1, where @ denotes glement-wise multiplication. The updated mask m441 represents the optimized topology for the next training loop + 1.
independently sampled from its corresponding Beta distribution
B.2 FedRTS
The framework of FedRTS begins by initializing the global model weights Wo and sparse mask mo with a predefined sparsity level d'. The sparse mask mp determines the active parameters in the initial global model. Additionally, hyperparameters such the total number of training loops Tend and the adjustment interval AT are set. These parameters control the frequency of topology adjustments and the overall training duration.
The training process conducted over Teaa loops. At the beginning each training loop I, the server employs a random sampling mechanism to select subset of clients C, from the total N available clients for participation in the training process. This sampling process is conducted uniformly at random, ensuring that each client, indexed by from ,..., V. has equal probability of being chosen. This randomized partial participation mechanism not only avoids bias in client selection but also ensures scalability and reduces communication overhead, making it well-suited for large-scale distributed systems.
The server then broadcasts the global sparse weights W₁ and the corresponding mask m, to all participating clients C.. Each selected client n E C, trains the received model (W,, m.) on its local dataset D, for fixed number of loops, producing intermediate outputs. Specifically, gradients G will be computed only during outer loops for topology adjustment. The client identifies the gradients with the top K K magnitudes based on the gradients G and upload its corresponding
24

---

Algorithm 2 FedRTS
Initial model Wo. target sparsity d', learning rate y,, maximum of training loops Tend. maximum of loops T maz. adjustment interval AT, training datasets (DaJNEN. v, the number of core links
Input:
Output: Final sparse model WT Tmao? Mima
Randomly initialize mo with sparsity d', for each loop = 0, 2, Tmax 1 do // The server does
Sample random subset of clients C2 Broadcast server sparse model (Wa, m2) to all clients n E Ce
for each client n E Ct do The client does
WT, mg <- Wt, my // Fetch global model
W & W fn (WT", mc, Dn) m
Transmit W to server if mod AT's = and < Tend then
Sample batch data B, ~ Dn
G < V fn m,, Bn) @ my
4 < {ili E Top[[GT+ K k)} // Top K - k magnitudes' indices
Transmit 4,41 to server
end if end for
// The server does
if mod AT 0 and / < T Tend then
W m++1 < TSAdi( (W Wiiee,, ( Algorithm.
else
// Update beta distribution based on weights' outcomes
Wo + Σnec, Pn W
M4+1 &- my // inner loop do not update topology
X (XP) JnEC, calculate with Wagg and (W (Wneh by Eq.
X, XX,99 +1 Enec. X,
for each links i= 1,,,.... (X,) do
(as, B.) < (a; + AX 8 X(1 - Xt,)),, X1, # None
end for
end if end for
indices Z = {ili E Top Cep(Gr+l,,K - =)), representing the most promising links for the potential reactivation, rather than the complete gradients to the server, further reducing communication overhead. In contrast, weights W are computed and uploaded to the server during both inner and outer loops facilitate global aggregation. Unlike gradients, which are selectively uploaded, the complete set of weights is transmitted to ensure comprehensive integration into the global model.
Upon receiving the locally updated gradient indices Iy in the outer loop and weights W from the participating clients, the server aggregates the weights to update global model weights W using a weighted average formula. Mathematically, the aggregated weights W are computed as: w >neci Ecc, Pr.Wi W If the current loop is an outer loop (i.c., mod AT = 0), the server invokes the TSAdj mechanism to adjust the sparse mask my, The updated mask m is then applied to the global model.
After completing Tend training loops, the server outputs the final globally aggregated weights W and an optimized mask mT.... both derived from the iterative training involving all participating clients. The weights WT.... represent the learned parameters that effectively accommodate heteroge- neous data distributions, while the topology MT.... preserves the robust and reliable structure of the model.
25

---

C Theoretical Details
C.1 Greedy Optimal Action
Algorithm 3 Greedy Optimal Action
Input: The mean vector μl and action size K
Return: The greedy optimal action S"
Initialize: 5" = 1
for E I,...,, K do
- S* U fargmax r(5 (i)
end for
C.2 Proof of Theorem
The cumulative regret Reg(T) is defined as:
T
Reg(T) = E Σ
As
(10)
1=1
where As, max - r(E,, u), 0} and S the greedy optimal action based on μ., which is obtained by Alg. 3 The maximum reward gap is set as Amax maxy As. The maximum reward gap of actions containing arm is max maxs:es As. We define S* and S, are sequences, sk) S. (st,1...., st, and st E S is the k-th element added to S* We For any arm s, define the marginal reward gap
i.e., S" = (......,
denote S (s $ and St,k =
A - p)) r(S (s).
Theorem, (Upper Bound) Under assumptions 3.2 3.3 and 3.1 and with outcomes defined in Eq.
the regret (Tg(T) TSAdj can be upper bounded by:
6Amax L log
KU +8Ke*
Reg(T) S
Σ stoe
max koogs
(Da,k 2LKE}²
2K ((W)
e6
maz
(1I)
Amaz 1 Io
max Σ
=0
kisgs
A
sp8;
for any e such that Vs + Si and & St, As, > 2LKe, where U is a universal constant.
Proof. For any arm 8 + 8i, we apply the exploration price F(i) as
6oo (D,,k 2LKe)²
F(s)
max k:
(12)
Therefore, at the 1-th iteration, there are two events
3 log 2N,,
(W)} + Er.i - fee 2 A = Bie (I.......
(13)
B, = 3i (1...., (W)) = 1u4 A 12
3 3lg T
(14)
2N,
where N2,o
Σt= l.es, is number oberservations of arm 8 and ars
No. Σt= Eoes, Xr,s is the empirical mean outcome of s at the start of round
Based on Eq. 13 and 14 the regret Reg(T) can be devided into three terms as
(Tg(T) <
E
AAA B, Ast
+ E
Σ 1
As,
+
Σ
(15)
We provide the Lemma and obtain
to bound these three terms one by one. Therefore, we can
64 max 2 log +
KU + 8KK
(Tg(T) < Σ
max kisg St
[Ask 2LKc)²
2K 12K + 4(W)
6
A Amaz
(16)
26

---

C.2.1
Lemmas
Lemma C.1. Under all assumptions and settings in Theorem 3.4
we have
T
6 L L2 T (A.,A 2LKee²
KU + SKEE
E
1 1-ALA-B, As.
max A
2K +
eb
Amax (17)
Proof. To bound this term, should study the difference between St,k and sk. that is, this term be bounded by
T
K
ALA- As.
E
Σ
As
ALAL-BBACU
E
1g m
- Se
A
max
k=1
(18)
where Ct denotes an event which is defined as
Ci, = (5 St,k-1 A st + St, |15,s 18 11x0 S...
(19)
We define Êts = fér,lé E 5} and μs = {uili E 5}. According to Lemma C.4 Eq. 18 can be bounded by:
the first term in
K
K
T
UK
E
Σ
As.
1 des BrACUN
As, 1 SFF
+
A
max
6
T
K
UK
<
As
(FF.
+ 6
Amar
UK
E
Σ
Ag. ISES.AN..
+ c6 maz
UK F(s)Amax max
Σ
6 Amar
8t8e
64 max L log T
UK
(A, 2LKE)²
+
c
moas
(20)
where U a universal constant, Based on Lemma
C.5 the second term can be bounded by
8K max-
M -Mngll Amax S 2K
(21)
Combining Eq. 20 and Eq.
we have
6A max 2 log (A
KU + SKE
LAA-B As
max St
+ 2K +
A Amaz (22)
2LKe)²
Lemma C.2. Under all assumptions and setting in Theorem 3.4 we have
T
A. As.
< 24 (W).
(23)
27

---

Proof.
E
1 A
St
E
1 AA
Aax
1=1
(
T
E
11. 28..
Amax
T
3log T 2N
ΣΣΣ
TP
NN. |N. =
1Ec. - -meal?>
A Amax
Σ r
3 logg? T
Σ
PP PNNe3 = r) TP (Ee.. i
Ne, =7)
A Amax-
2N
(24)
According to Lemma C.6 we have
(W) T T-1
3 3log T
ΣΣΣ
P(N,, = T) .P
No.i 7
A max
2N,,,
(W)
T T-1
P PNV = - 22xpp(333oo log T)
(25)
im1 t=
(W) 2
max
22 max (W).
Lemma C.3. With all assumptions and setting in Theorem 3.4 we have
T
1B, As.
< m (W).
(26)
Proof.
E
1 B,
Si
E
Σ
B:
A Amax
(W)
T
E
Amax
{2>
INt,
1=1
(27)
(W)
T T-1
3 3log? T 2N,,
P
No. = 1us me.
A max
Σ
P (Nv, TT) (Im iieeo
3 3lgg T
No,1 = r)
A max-
2N,,
According to Lemma
C.7
we have
(W) T
3 3log T 2N,,
ΣΣΣ
P PN,, = P
[M: irr
No. =
A Amax
(W)
P (Ne. T) 2exp(-33log Amxx
(28)
Fml tm rml
(W) T
1m tm
24 max (W).
28

---

Lemma C.4. Under all assumptions and settings in Theorem 3.4 with Ci,s defined in Eq. 19 we
have
U UAmaz
E
Σ
As.
1-A,A-BAACL4
S
s. I.
(29)
e
SEST
Proof.
This Lemma is a special case in [26] (Lemma 1), setting the size of the unit as and = CC". Lemma C.5. With all assumptions and setting in Theorem 3.4 we have
8 2²
E
1 2 M
beot -ag Se
Amax S 2 max
(30)
Proof. This Lemma is special case in 126 (Lemma 3), setting the size of each unit as 1. Lemma C.6. With all assumptions and setting in Theorem 3.4 for any arm i E {1,-.. (W)) and round f, we have
IP (1Er.i - pe,ll > aks, 3r,s) S 2 eexp(=2eNN.)
(31)
where ot and Be, are the values of a4 and Be the TSAdj before the start of round
Proof. This Lemma has been proved in [59 (Lemma 3).
Lemma C.7. With all assumptions and setting in Theorem 3.4 let X,,..., .XK be indentical
independent random variable such that X2 [0, 1] and [[,,] for any E {1,.... K). Then for any 2 0, we have
K X;
1
Kc S 2cxxp(22K3)
(32)
Proof. This Lemma can be proved by Chernorff-Hoeffdim Bound in (Theorem 1.1).
D Broader Impact
Beyond its technical contributions, FedRTS holds significant practical potential for democratizing efficient federated learning. By substantially reducing communication and computation costs dynamic sparse training, our approach could broaden the adoption of FL. in resource-constrained environments, such the Internet of Things [31
58 edge perception 61
62 60), and
privacy-senge sewacy-sensitive medical applications [16]. However, like all pruning-based methods, FedRT'S carries a risk of inadvertently amplifying biases sparsity patterns disproportionately discard weights that encode features of minority classes. To mitigate this, recommend integrating our method with fairness-aware regularization and continual learning techniques 45. 63 in sensitive domains. Future work will explicitly investigate the societal implications of deploying FedRTS scale, with focus on applications where model sparsity may impact predictive reliability.
E Additional Experiments Results
To further validate our findings, we perform additional experiments to investigate the impact of various hyperparameters and the convergence behavior of proposed methods.
E.1
The Impact of Hyperparameters
E.1.1
The Impact of trade-off ratio
The trade-off off ratio y modulates the weight of individual models' information. Traditional methods only incorporate the information from the aggregated model, which is insufficient. To verify the impact of individual models' information, we conduct experiments on the trade-off ratio y. As illustrated in Fig. 7 the test accuracy reaches its peak when the 7 value is between 0.3 and 0.5. This indicates that the information from both individual models and the aggregated model is significant in model topology adjustment.
29

---

Testing Accuracy
Testing Accuracy
0.720
0.715
0.710
0.715
0.705
0.0
0.2
0.4
0.6
0.8
10
15
20
Trade-off Ratio y)
Scaling Factor (A)
Figure Impact of trade-off ratio 7
Figure 8: Impact of the scaling factor
AT
3
5
10
20
CIFAR-10
CINIC-1O
FL.Pss
Comm. Cost
FLOPs
Comm. Cost
FedDST
0.664
0.683
0.723
0.716
FeaDST
3.4E16
221.9 GB
8.2E16
290.7 GB
FedMef
0.745
0.737
0.713
0.705
FedMaf
3.5F16
227.6 GB
6.1
222.3 GB
FedRTS
0.735
0.722
0.734
0.731
FedRTS
3.1E16
204.2 GB
2,9E16
105.6 GB
Table 3: The overall training FLOPs and com- municational cost (Comm. Cost) for FedRTS and other frameworks to reach the accuracy of dense FedAVG.
Table 2: Performance under Different Adjust-
ment Interval (AT)
E.1.2 The Impact of the scaling factor
The scaling factor regulates the impact of the current reward (t) at step t. A À value that is too small will amplify the uncertainty in Thompson Sampling. whereas À value that is too large will disregard the uncertainty arising from insufficient samples. Thus, selecting an appropriate value for is crucial for enhancing FedRTS's performance. In a separate set of experiments, the influence of the reward scaling À on the results is investigated. Figure & shows that the test accuracy attains its maximum at approximately 0.73 when À is 10.
E.1.3 The Impact of the number of core links K
The number of core links & critically controls the adjustment intensity (the number of weights pruned and reactivated) in each outer loop, creating essential trade-off: large values lead sluggish topology evolution, while small k risks substantial information loss. We formalize this through our decay schedule: K² = K Cadi (1 + cos ( ( Tend ))',, where K' is the number of active weights at
1-th layer. Our empirical investigation CIFAR- 10 in Fig. [3 demonstrates FedRTS's robustness across varying Cladj. consistently outperforming baseline methods.
E.1.4 The Impact of Adjustment Interval AT
In federated dynamic sparse training, the adjustment interval (AT) between two outer loops for adjustment critically influences model performance through a fundamental trade-off. Excessively long intervals may delay the discovery of optimal sparse patterns, while overly frequent adjustments can prevent adequate model adaptation between updates and require higher resource consumption.
Our experiments with FedRTS CIFAR-10 explored this trade-off by evaluation with various ad- justment intervals (AT' E {3, 5, 10, 20)). As depicted in Table FeaRTS consistently outperformed baseline methods across most cases. Notably, FedRTS's performance improved with shorter intervals, demonstrating FedRTS's unique ability to quickly recover from topology changes, which a crucial advantage in dynamic sparse training scenarios.
E.2
Efficiency Analysis
E.2.1
Training Cost
We evaluate FedRTS's efficiency by analyzing training costs on CIFAR-10 and CINIC-10. To compare expenses, measure total training FLOPs and communication costs required to match the
30

---

0.8
0.8
Validation Accuracy
Validation Accuracy
0.6
0.6
0.4
FedAVG
FedAVG
FedDST FedMef
FedDST
FedMef
FedRTS
FedRTS
100
150
200
Cumulative Communication Cost (GB)
Cumulative FLOPs (x1015)
Figure 9: Validation accuracy of FedRTS and SOTA frameworks on CIFAR-10 dataset for cu- mulative communicational cost.
Figure 10: Validation accuracy of FedRTS and SOTA frameworks on CIFAR- 10 dataset for cu- mulative FL.OPs during training.
0.6
0.6
Validation Accuracy
Validation Accuracy
0.5
0.4
0.4
FedAVG
0.3
FedAVG
FedDST
FedDST
0.2
FedMef
0.2
FedMef
FedRTS
FedRTS
50
100
150
200
10
30
60
Cumulative Communication Cost (GB)
Cumulative FLOPs (x1075)
Figure 11: Validation accuracy of FedRTS and SOTA frameworks on CINIC-10 dataset for cu- mulative communicational cost during training.
Figure 12: Validation accuracy of FedRTS and SOTA frameworks on CINIC-10 dataset for cu- mulative FLOPs during training.
testing accuracy of dense FedAVG. The accuracy is averaged over 10 rounds to mitigate variance from random factors, ensuring a more stable evaluation.
As shown in Tab, 3 FedRTSS achieves the testing accuracy of dense FedAVG with significantly lower costs. On CINIC-TO, it achieves 48% training FL.OPs and the communication cost compared the best baseline FedMef, which highlights the efficiency of FedRTS.
E.2.2 Convergence Behavior
Convergence crucial for effective learning, precise predictions, and optimized resource use. To evaluate this, we track the validation accuracy of FedRT'S and SOTA frameworks on CIFAR- and CINIC-10 against cumulative communication and computational costs, as shown Fig. Fig. I0 Fig. I1 and Fig. [2] Accuracy is averaged over 10 rounds to reduce variance and provide a stable representation. Our experimental results demonstrate distinct convergence patterns across datasets. On 10, FedRTS exhibits superior convergence characteristics throughout the entire training process. The CINIC-10 dataset reveals more complex trajectory: while FedDST initially demon- strates higher performance during early training phases, FedRTS consistently surpasses competing methods later stages when considering both communication efficiency and computational costs. These empirical results provide strong evidence for the effectiveness of the TSAdj mechanism in Fe- dRTS, particularly optimizing the trade-off between model performance resource consumption during federated training.
31

---

23
FedAVG
FedMef
Mcan Accuracy
0.73
FedRTS
Perplexityy
22
0.72
0.71
MedMef
0.70
FedRTS
20
0.8
0.7
0.6
0.5
0.4
0.3
0.2
5
3
2
1
adjustment ratio ang
Degree of Data Heterogenelty
Figure 13: Accuracy on CIFAR- 10 with ResNet under various degrees of adjustment ratio Cldjj.
Figure 14: Perplexity on TinyStories under var- ious degrees of data heterogeneity. The lower represents higher non-IID degree.
E.3 Broader Experiments
E.3.1 FedRTS vs. FedCUCB
The Combinatorial Upper Confidence Bound (CUCB) is another optimization method for the Combi- natorial Multi-Armed Bandit (CMAB) problem. Unlike Combinatorial Thompson Sampling (CTS), which relies probabilistic sampling. CUCB employs deterministic optimistic reward estimates to balance exploration and exploitation. However, its inherent optimism can lead to persistently selecting suboptimal arm combinations, particularly in dynamic pruning scenarios where adaptability crucial.
CUCB maintains upper confidence bounds (UCBs) rather than probability distributions for each arm i, which formulated as
3 log
Pt. = Pe.3 + V 24;
(33)
where V denotes the number of times arm has been selected, Pr,i denotes the empirical mean reward (initialized as joo = 0). The selected arms for action S, are determined by
S: = {i E Top K)}
For the selected arms S, with outcomes Xte empirical mean is updated as:
i St 11+1, i S. P
i S E S
(34)
The next round's action selection then uses the updated UCB Aet1, computed by Eq. 33
notable drawback of FedCUCB is its handling of under-explored ("bad") arms. If arm is rarely selected (low 1,,, its confidence bound Ju, grows indefinitely as f + co, eventually forcing its selection. This behavior disrupts convergence, as the algorithm repeatedly revisits suboptimal arms instead of refining the topology.
To evaluate this limitation, propose FedCUCB, federated pruning framework based on CUCB. In contrast to FedRTS, FedCUCB maintains UCB üe and define the outcomes X, as same in Eq. 3 The results in Fig. 15 demonttraassss that FedCUCB performs slightly worse than FedRTS, but still outperform other baselines.
E.3.2 Pruning vs. Weights Quantization
Parallel to pruning-based approaches, quantization techniques 50
23
20 offer an alternative
for reducing communication overhead in FL. While both strategies aim to alleviate transmission costs,
32

---

Methnd
Comm, Cost
FLOPS
Memory
Aec.
FedAVG
89.52 MB
17.88+12
134.29MB
77.24
Accuracy
0.75
TedPAQ
22.48 MB
17.84122
134.29
73.34
FedDST
20.85 MB
3.8++12
31.28 MB
68.31
0.70
FedRTS
20.85 MB
3.8++1
31,28 MB
73,41
Table 4: Performance and training cost comparison between federated pruning (FedDST, FedRTS) and federated quantization (FedPAQ) frameworks on CIFAR-10 10 using ResNet18. FedPAQ apply 8-bit quantization, while FedDST and FedRTS employ target density of d' = 0.2.
0.65
0.2
0.4
0.6
0.8
Communication Cost
FedAvG
Fedminy
RedSCC FedMiet
FedCucB FedRTS
Accuracy CIFAR-10 with ResNet18 for FedRTS, FedCUCB and other fed- erated dynamic pruning methods.
Figure 15:
weights quantization operates after dense local training, whereas pruning enables sparse training by design. This fundamental difference grants pruning distinct advantages in resource-constrainee settings: it reduces computation through selective updates, lowers memory usage by maintaining dynamic sparsity, and ensures consistent communication efficiency across rounds.
Empirical evidence supports these trade-offs. As shown in Table our FedRTS outperforms 8-bit FedPAQ [50]. weights quantization baseline, in computational and memory efficiency, while retain- ing competitive model accuracy. This makes pruning more holistic solution for FL. deployments on edge devices.
F Additional Setup Details
F1
Datasets
In the CV tasks, apply our approach using ResNet18 on CIFAR-10, CINIC-I0, TinyImageNet, and SVHN datasets.
CIFAR-I0: It contains 50,000 training images and 10,000 testing images. Each image in CIFAR-10 is a 3x32x32 RGB image, implying 10 classes of objects.
CINIC-10: It contains three equal subsets train, validation, and test-each comprising 90,000 images. CINIC-10 is an extended version of CIFAR-10 that includes additional images from ImageNet.
TinylmageNet: contains 200 classes with 500 training images, 50 validation images, and 50 test images per class, each resized to 64x64 pixels.
SVHN: There are 73,257 digit images in the training set and 26,032 images in the testing set. The digit images are obtained from house numbers in Google Street View images.
In the NLP tasks, choose GPT-2-32M the backbone model with the TinyStories dataset. TtoySto contains synthetically generated short stories that only use limited vocabulary. We truncate each story to 256 tokens, with 2, 120,000 stories used for training and 22,000 for testing.
F.2 Baselines
The selected federated pruning baselines differ in their approaches to sparse model initialization and subsequent model topology adjustment:
PruneFL: Initializes the sparse model by training on a powerful device and applies adaptive pruning by importance measure. In our inplementation, we perform random pruning instead of pruning with powerful devices due to resource constraints. Moreover, we set the time l of each parameter with 1.
33

---

FedDST: Applies dynamic sparse training on clients and performs greedy aggregation to produce a new global topology.
FedTiny: Initializes the model by adaptive batch normalization selection and adjusts the model mask based on the aggregated top-K gradients parameters.
FedSGC: Adjusts model topology devices guided by the gradient congruity, which is similar to FedDST but requires extra communication cost.
FedMef: Utilizes budget-aware extrusion to transfer essential information of pruned parame-
ters to other parameters and reduces activation memory by scaled activation pruning.
F.3 Extra Information
The experiments are simulated via multi process on an Nvidia RTX 5880 GPU, an Intel Core i9 CPU with 48 GB of memory,
F44
Communication and Computational Cost
In our experiments, we analyzed the proposed FedRTS against other methods by examining the computational FLOPs and communication costs. We began by introducing sparse compression strategies and then detailed how we calculated these metrics.
F.4.1 Compression Strategy
When storing a matrix, two key components are values and positions. Compression techniques focus on reducing the storage required for the positions of non-zero values within the matrix. Consider a scenario where we aim to store the positions of m non-zero values with a b-bit width in sparse matrix M. which comprises n elements and has shape of ne. The density of the matrix, denoted by d = m/n, determines the compression scheme applied to represent M. The storage involves using bits to represent the positions of the non-zero values, resulting in an overall storage size of s.
For density (d E [0.9, 1)), dense scheme utilized, leading to 8 nb.
For density d E [0.3, 0.9), the bitmap (BM) method is employed, storing map with bits, where = n and = o + mbb
For density d E [0.1, 0.3), the coordinate offset (COO) scheme is applied, storing elements with their absolute offsets and requiring o = m [log2]] extra bits for position storage. Thus, o + mb.
the overall storage becomes
For density d E [O., 0.1), the compressed sparse row (CSR) and compressed sparse column (CSC) methods are used based on size considerations. These methods use column and row indexes to store element positions, with CSR needing o = m m|logzne + n, [lggmm] bits. The overall storage size is s 0 mb.
Reshaping is performed on tensors before compression, enabling the determination of the memory required for training the network's 's parameters.
F.4.2 Communication Cost
In terms of communication costs, FedRTS shares communication cost strategy similar to that of FedTiny. In contrast to other baseline methods like FedDST, where clients need to upload TopK gradients the server every AR rounds facilitate parameter expansion, the quantity of TopK gradients, denoted as &., aligns with the number of marked parameters 0 low. Here, & = (11-sa 8m Mag with C 0.2(1 + cos Retop E )representing the adjustment rate for the t-th iteration. This results in minimal upload overhead. Moreover, there is no communication overhead for the model mask m during download since sparse storage formats like bitmap and coordinate offset contain the same element position information. Auxiliary data such as the learning rate schedule are excluded.
We define the storage for dense and sparse parameters as Oa and O., respectively. Notably, in the inner loop, federated pruning methods except FedAVG share the same communication cost, which amounts to 20.. However, in the outer loop, different federated learning frameworks exhibit varying communication costs. The communication costs of different federated learning frameworks in the outer loop are detailed below:
34

---

FedAVG:
The data exchange amounts to 20,, encompassing the uploading and downloading
of dense parameters.
FedDST: In this scenario, the model mask does necessitate additional space for storage as the compressed sparse parameters already embody the mask information. Hence, the data exchange per round stands at 20,, covering the upload and download of sparse parameters.
PruneFL: PrumeFL requires the clients to upload the full-size gradients squared for adjust- ment, therefore, the data exchange in the outer loop is O₂ + O..
FedSGC: FedSGC requires the server to send the gradient congruity to server for each round, which has the same size as sparse weight. Therefore, the data exchange in the outer loop 30
FedTiny and FedMef: In comparison FedDST, FedTiny and FedMef entail the upload of TopK gradients every AR rounds. Therefore, the maximum data exchange per round sums up 20,- + Og, where Og signifies the storage required for the TopK gradients.
FedRTS: When compared to FedTiny and FedMef. FedRTS only requires uploading the index of the TopK gradients every A AR rounds, while Fed'Tiny and FedMef necessitate uploading both the index and the values of TopK gradients at the same intervals. Consequently, the maximum data exchange per round amounts to 20, + 0.50g, where Og represents the storage needed for the TopK gradients.
F.4.3 Computational FLOPs
Training FLOPs encompass both forward-pass FLOPs and backward-pass FLOPs, with operations tallied per-layer basis. During the forward pass, layer activations are sequentially computed using prior activations and layer parameters. In the backward pass, each layer computes activation gradients and parameter gradients, with twice as many FLOPs expended in the backward pass as in the forward pass. FLOPs related to batch normalization and loss calculation are excluded.
In detailed breakdown, assuming inference FLOPs for dense and static sparse models denoted as Fa and F, respectively, and the local iteration count is E, the maximum training FLOPs for each framework are follows:
FedAVG: Requires training a dense model, resulting in training FLOPs per round amounting 3FaE.
PruneFL: it requires calculating the dense gradients for each backward, therefore the training FLOPs is (2Fa + F.).E
FedMef: Introduces a minor calculation overhead for BaF and SAP. Therefore, the
maximum training FLOPs are estimated as 3(F, + F.)(E - 1) + (F, + F.) + 2Fa- where Fo represents the computational overhead of BaE and SAP. Fo is approximated as F. 4(1 smmng +,, with 4(1 - 8m mm representing the FLOPs for regulariza- tion and WSConv, andn,,lggn, indicating the FLOPs for activation pruning.
FedRTS, FedTiny, FedSGC, and FedDST: Implement RigL-based methods to adjust model architectures, necessitating clients to compute dense gradients in the final iteration. The maximum training FLOPs sum up to 3F,(E 1) + F, 2F
35


Reviews:
[{"review_id": "SUCzZ7zKz1", "reviewer": "Reviewer_aLmC", "summary": "This paper proposes FedRTS, a novel federated pruning framework that improves the robustness, efficiency, and adaptability of sparse model training in federated learning (FL) environments. At the core of FedRTS is the Thompson Sampling-based Adjustment (TSAdj) mechanism, which formulates topology adjustment as a combinatorial multi-armed bandit problem. Rather than relying on deterministic and short-sighted decisions, TSAdj makes probabilistic, history-aware selections of model connections based on both local (client) and global (server-aggregated) outcomes.\n\nThe framework introduces a fusion mechanism that blends individual and aggregated observations to mitigate instability and variance in sparse topology updates. Additionally, it reduces communication overhead by requiring clients to upload only top-gradient indices instead of full updates.\n\nFedRTS is evaluated on both computer vision (e.g., CIFAR-10 with ResNet18) and natural language processing (TinyStories with GPT-2) tasks under various sparsity levels, data heterogeneity, and client availability conditions. Across all settings, it consistently outperforms existing sparse FL baselines in terms of accuracy, communication cost, and robustness. An ablation study further confirms that the gains stem from the probabilistic adjustment strategy, use of farsighted information, and the stability offered by the fusion mechanism.", "questions": "Computational Overhead of TSAdj\nWhile FedRTS improves communication efficiency, TSAdj maintains and samples from Beta distributions for each model link, which could be expensive for large-scale models (e.g., GPT-2).\nQuestion: Can the authors provide a computational complexity analysis or empirical runtime comparison (e.g., per round) against baseline methods?\nEvaluation impact: Addressing this would clarify scalability concerns and reinforce the practicality of FedRTS in large models.\n\nValidation of Inactive Link Outcome Estimation (Eq. 5)\nThe estimation of outcomes for inactive links via gradient magnitudes is a key part of reducing communication cost, but its reliability is not rigorously evaluated.\nQuestion: How sensitive is TSAdj's performance to this heuristic? Can the authors quantify its accuracy or compare it with alternative estimators (e.g., partial gradient transmission)?\nEvaluation impact: A justification or ablation could strengthen confidence in the outcome modeling and the robustness of FedRTS.\n\nHyperparameter Sensitivity and Tuning\nThe paper briefly mentions that hyperparameters (γ, λ, κ, ∆T) affect performance, but defers analysis to the appendix.\nSuggestion: Please summarize key findings on sensitivity (e.g., which parameters are most impactful, how robust is the method to mis-tuning) in the main paper.\nEvaluation impact: Improved clarity here would support broader applicability and ease of adoption.\n\nReal-world FL Setting or Simulation Realism\nThe current evaluation is thorough but confined to synthetic federated setups.\nSuggestion: Could the authors comment on (or ideally include) experiments in more realistic FL settings (e.g., device-level heterogeneity, on-device constraints)?\nEvaluation impact: Demonstrating FedRTS under deployment-like conditions would significantly strengthen the practical significance of the work.\n\nBroader Applicability Beyond Pruning\nFedRTS is positioned as a pruning method, but the TSAdj mechanism could, in principle, generalize to other structural decisions in FL.\nQuestion: Do the authors envision applications of TSAdj beyond pruning (e.g., layer-wise selection, gradient sparsification)? If so, a brief discussion would be valuable.", "limitations": "The authors have not explicitly discussed the limitations or potential negative societal impacts of their work. While the technical contributions are strong, the paper would benefit from a short section or paragraph acknowledging:\n\nScalability limitations: TSAdj may introduce overhead when scaling to very large models with millions of parameters. A discussion of this trade-off is important for deployment feasibility.\nFairness and bias: The method dynamically adjusts model structure per global feedback. In highly heterogeneous settings, this could unintentionally bias the model toward data-rich or majority-class clients.\nSecurity/privacy considerations: While the method reduces communication cost, sharing top gradient indices might still leak sensitive information. A brief mention of this risk and possible mitigations (e.g., differential privacy) would be constructive.\nSuggestion: Add a limitations section addressing scalability, bias in client selection/topology adaptation, and communication-related privacy concerns. This would strengthen the paper’s transparency and societal responsibility.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 1, "strengths_and_weaknesses": "Strengths\n\nOriginality: Novel framing of federated pruning as a combinatorial bandit problem; innovative use of Thompson Sampling for sparse topology adjustment.\nQuality: Strong theoretical foundation (regret bound), well-designed TSAdj algorithm, and comprehensive experiments across modalities (CV/NLP) and FL challenges (non-IID, partial participation).\nSignificance: Addresses a core bottleneck in sparse FL—instability and communication inefficiency—with clear improvements over strong baselines (FedAVG, FedDST, FedMef).\nClarity: Method and motivations are well-explained; algorithm steps, equations, and experiment setup are easy to follow. Ablation study isolates contributions effectively.\n\nWeaknesses\n\nComputational cost of maintaining and sampling Beta distributions for large models is not analyzed.\nOutcome estimation for inactive links relies on heuristic (gradient magnitude) without deeper justification or validation.\nLack of real-world deployment or large-scale FL setting; all evaluations are in simulated environments.\nHyperparameter sensitivity (e.g., γ, λ) is deferred to the appendix, limiting insight into robustness in the main text.", "was_revised": true, "final_justification": "The authors have added experiments to address my concerns. It is a strong paper now.", "rebuttal": "We sincerely appreciate the reviewer aLmC's __detailed and insightful feedback__ and we are encouraged by the recognition of our paper’s strong theoretical foundation, well-designed algorithm, comprehensive experiments, and clear explanations. We have carefully addressed the concerns in detail in the responses below to enhance clarity and refinement.\n\n> **Q1 & W1** Computational cost of maintaining and sampling Beta distributions for large models is not analyzed.  \n\nIn TSAdj's design, the server performs the following operations at each round: \nweights aggregation iterates exactly $\\langle C_t \\rangle$ times, requiring $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$ for weight averaging, $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$ for outcome computation (expected time with Quick Sort), $\\mathcal{O}(\\langle W \\rangle)$ for updating beta distributions and sampling probabilities, $\\mathcal{O}(\\langle W \\rangle) $ for arms selection. \n\nThe overall complexity simplifies to  $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$. \n\nCompared to baselines' complexity (e.g., FedMef/FedTiny/PruneFL's $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$), our proposed TSAdj achieves the same computational complexity order, demonstrating that TSAdj introduces no significant additional computational burden on the server.\n\n**Most importantly, TSAdj introduces no additional computation on devices compared to the baseline**. Its overhead is entirely server-side. In cross-device FL, the server is typically assumed to have substantial computational resources; therefore, TSAdj does not impose a significant extra burden compared to the baselines.\n\n> **Q2.1 & W2**  Outcome estimation for inactive links relies on heuristic (gradient magnitude) without deeper justification or validation.\n\nOur use of gradient magnitude for estimating outcomes of inactive links (Eq. 5) is motivated by both empirical precedent and theoretical intuition:\n1.Empirical: Gradient magnitude is a key metric in dynamic sparse training. Methods like FedTiny, FedMef, and RigL focus on parameters with large gradients for reactivation, ensuring fair comparison.\n2. Theoretical: Large gradient magnitudes indicate a parameter's importance for model optimization. Keeping parameters with high gradients can notably reduce loss, aligning with pruning theory's \"saliency\" principle.\n\nHowever, we admit this heuristic and may not capture complex parameter interactions, we will explore theoretically grounded alternatives in future work.\n\n[1] Evci, Utku, et al. \"Rigging the lottery: Making all tickets winners.\" International conference on machine learning. PMLR, 2020.\n\n\n> **Q2.2** Can the authors quantify its accuracy or compare it with alternative estimators (e.g., partial gradient transmission)\n\nWe compared FedRTS with FedTiny using both partial and full gradient transmission on CIFAR-10. The results show that FedRTS achieves higher accuracy than FedTiny with full gradient transmission, while incurring lower communication cost than FedTiny with partial gradient transmission. This is because FedRTS only needs to transmit a binary (0/1) mask matrix instead of the gradient values.\n\n|| Acc | Comm. Cost |\n|--|-|-|\n| FedTiny (partial gradient) |0.554| 25.32 MB   |\n|  FedTiny (full gradient)   |0.573| 55.19 MB   |\n| FedRTS|0.580| 20.85 MB   |\n\n> **Q3 & W4**  Please summarize key findings on sensitivity (e.g., which parameters are most impactful, how robust is the method to mis-tuning) in the main paper.\n\nWe will add a new subsection in Section 4.3, summarizing key findings on hyperparameter sensitivity. \n* $\\gamma$ controls the balance between individual and aggregated information: a large $\\gamma$ places greater emphasis on aggregated information, while a small  $\\gamma$ concentrates more on individual outcomes.\n* $\\lambda$ scales the evidence added to the beta distributions' parameters ($\\alpha$, $\\beta$), which directly affect link selection: a large $\\lambda$ results in large increments to $\\alpha$ and $\\beta$ for selected links, accelerating the convergence of their distributions and promoting exploitation of current high-performing links. Conversely, a small $\\lambda$ applies small increments, maintaining higher uncertainty for less frequently selected links and encouraging exploration.\n* $\\kappa$ determines the layer-wise pruning rate: a large $\\kappa$ leads to slower topology evolution, while a small $\\kappa$ risks substantial information loss.\n* $\\Delta T$ impacts the frequency of topology adjustments: a large $\\Delta T$ may delay the convergence to stable topology, while a small $\\Delta T$ leads to frequent adjustments incurring higher resource costs.\n\nThe most impactful parameters are $\\gamma$ and $\\lambda$ as accuracy varies $\\pm 1.2$% for $\\gamma \\in [0, 1]$ and accuracy peaks at $\\lambda = 10$ ($+1.8$% v.s. $\\lambda = 1$). However, FedRTS still outperforms other baselines even with suboptimal hyperparameters based on the ablation study, demonstrating the robustness to mis-tuning.\n\n> **Q4 & W3** The current evaluation is thorough but confined to synthetic federated setups. Could the authors comment on experiments in more realistic FL settings?\n\nWe plan to include real-world FL deployments in future work. Here, we briefly discuss the expected effects and dependencies of FedRTS’s unstructured sparsification in practical settings: __1. Communication Efficiency:__ FedRTS’s sparse updates can be readily compressed using standard sparse storage schemes (e.g., CSR/CSC, BitMap), achieving similar communication cost savings as reported in this paper, without hardware dependencies. __2. Memory/Storage Efficiency:__ The sparse models generated by FedRTS can leverage existing sparse ML engines (e.g., PyTorch’s torch.sparse_coo_tensor, TinyML) to reduce memory usage. For example, MCUNet [2] reports a 3.8× memory reduction for 90%-sparse models using TinyML. 3. __Computation Efficiency:__ Latency gains from unstructured sparsity are hardware-dependent. For instance, Jiang et al. [3] demonstrate 1.5–2.5× training speedups on Raspberry Pi 4 using sparse kernels.\n\n[2] Lin, Ji, et al. \"Mcunet: Tiny deep learning on iot devices.\" Advances in neural information processing systems 33 (2020): 11711-11722.\n\n[3] Jiang, Yuang, et al. \"Model pruning enables efficient federated learning on edge devices.\" IEEE Transactions on Neural Networks and Learning Systems 34.12 (2022): 10374-10386.\n\n> **Q5** Do the authors envision applications of TSAdj beyond pruning (e.g., layer-wise selection, gradient sparsification)?\n\nYes, the TSAdj mechanism can generalize to __any decision problem requiring adaptive, long-term optimization under uncertainty__. For instance, TSAdj could be applied to layer-wise selection or gradient sparsification by dynamically activating/deactivating layers or gradients based on the maintained Beta distributions. A consideration, as the reviewer noted earlier, is that maintaining Beta distributions introduces some overhead. Therefore, TSAdj is best suited for distributed settings, such as FedRTS, where the cost can be centralized to a powerful host or parallelized to clients. We view these extensions as exciting future directions and welcome further exploration.\n\n> **Limitation**  The authors have not explicitly discussed the limitations or potential negative societal impacts of their work.\n\nWe will include the following limitations in the paper:\n\n1. __Scalability:__ TSAdj maintains Beta distributions for parameter-level decisions, which may introduce additional overhead when scaling to extremely large models with millions of parameters on the server. Although servers typically have substantial resources and the computational complexity remains comparable to baseline methods, further optimizations (e.g., hierarchical grouping or parameter sharing) are needed for deployment on very large models.\n\n2. __Fairness and Bias:__ Because TSAdj dynamically adjusts the model structure based on global feedback, in highly heterogeneous settings, this mechanism could unintentionally bias the model toward data-rich clients or majority-class distributions. Future work will explore fairness-aware adjustments to mitigate such risks.\n\n3. __Security and Privacy:__ While FedRTS reduces communication costs by transmitting only sparse updates (e.g., top gradient indices), this information could still leak sensitive details about client data. Integrating techniques such as differential privacy or secure aggregation into FedRTS could strengthen privacy guarantees."}, {"review_id": "5i6WOINDQC", "reviewer": "Reviewer_EiZ9", "summary": "This paper reframes federated dynamic pruning as a combinatorial multi-armed bandit (CMAB) problem. The key idea is to replace the deterministic, greedy topology updates used in prior work with a Thompson-Sampling-based Adjustment (TSAdf). This makes pruning decisions probabilistic, history-aware and communication-efficient (only largest gradients). The authors derive an upper bound on the regret. RedRTS either improves accuracy up to 5.1pp or reduces communication by 33% on vision and NLP benchmarks.", "questions": "- Pruning is mainly for large models rather than ResNet18. Given that federated learning is evaluated even on LLMs, please evaluate on large models that can show the impact of pruning explicitly.\n\n- Magnitude-based pruning is the most traditional method. Other methods, such as Fisher-information, can outperform but were simply deemed due to their computational burden. Can you empirically quantify the pros and cons of these methods?\n\n- Assumption 3.2 (independence between weight magnitude) is not true, which needs to be justified clearly.", "limitations": "Please state the limitations of your work in Conclusion to facilitate further work.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- Utilizing Thompson sampling is reasonable and new in the FL literature\n- Theoretical regret analysis is provided with proof. \n- Evaluation on both computer vision and NLP tasks\n- Superior accuracy with less communication cost\n\n**Weaknesses**\n- Lack of evaluation on modern large models that shows the impact of pruning more clearly.\n- Magnitude-based pruning is applied but other metric, such as Fisher-information, would be good to be compared empirically.\n- Assumption 3.2 (independence between weight magnitude) incurs discrepancy between practice and theory.", "was_revised": true, "final_justification": "The rebuttal has addressed my concerns successfully.", "rebuttal": "We sincerely appreciate the reviewer's detailed feedback, which has guided us to strengthen our work. We’ve addressed your concerns: evaluating pruning on large models (via OPT-125M experiments), comparing magnitude-based pruning with Fisher-information, and clarifying Assumption 3.2’s independence. Below, we detail these efforts to enhance our paper’s rigor.\n\n> **W1 & Q1** Lack of evaluation on modern large models that shows the impact of pruning more clearly.\n\nWe have conducted additional experiments on the OPT-125M model using the OIG/Chip2 dataset and evaluated it on the last-word prediction task in Lambada. To balance cost and feasibility, we used 100 clients, selecting 8 clients per round, with a target density of 0.5.\n\n|OPT-125M | \tAcc | Comm|\n|--|-|-|\n|FedAVG|\t0.4311|\t 1.05 GB|\n|FedMef|\t0.4307 |\t0.59 GB|\n|FedRTS|\t0.4315 |\t0.55 GB|\n\nThese results demonstrate that FedRTS maintains higher accuracy with lower communication cost on LLM. We note that cross-device FL is seldom used to fully train LLMs due to the extremely high cost on local devices.\n\n\n> **W2 & Q2**  Magnitude-based pruning is applied but other metrics, such as Fisher-information, would be good to be compared empirically.\n\nWe appreciate the reviewer's suggestion to evaluate Fisher-information-based pruning versus magnitude-based pruning (FedRTS). While the Fisher-based approach empirically achieves 0.1% higher accuracy by approximating the Hessian inverse for better parameter importance estimation [1], it introduces prohibitive overheads in the FL setting. \n\nSpecifically, Fisher-based pruning requires dense gradient computations (e.g., multiplications) because it employs the Sherman-Morrison formula to approximate direct inverse Hessian operations, which would otherwise exhibit cubic complexity in the number of parameters. However, this approach still maintains quadratic $\\mathcal{O}(\\langle W \\rangle^2)$ complexity per batch - substantially higher than FedRTS's linear $\\mathcal{O}(\\langle W \\rangle)$ operations. The detailed formula of the empirical Fisher is: \n\n$$\\hat{F_{n+1}^{-1}} = \\hat{F_n^{-1}} - \\frac{\\hat{F_n^{-1}}\\nabla l_{n+1}\\nabla l_{n+1}^T\\hat{F_n^{-1}}}{N + \\nabla l_{n+1}^T\\hat{F_n^{-1}}\\nabla l_{n+1}}$$\n\nFurthermore, a good approximation of the empirical Fisher needs a large number of samples for recurrent computation which is mentioned in Fisher approximation. Hence, its computational cost approaches that of dense FedAVG, which directly contradicts the core objective of federated pruning - reducing resource consumption especially on devices. Therefore, magnitude-based pruning (FedRTS) achieves an efficiency-accuracy balance in cross-device FL's setting.\n\n|Method| Acc | FLOPs |\n|--|-|-|\n|FedRTS (Fisher-information-based pruning) |0.7112| 1.31E+13 |\n|FedRTS (Magnitude-based pruning) |0.710225| 3.82E+12  |\n\n[1] Singh S P, Alistarh D. Woodfisher: Efficient second-order approximation for neural network compression[J]. Advances in Neural Information Processing Systems, 2020, 33: 18098-18109.\n\n> **W3 & Q3**  Assumption 3.2 (independence between weight magnitude) incurs discrepancy between practice and theory.\n\nWe acknowledge that Assumption 3.2 (independent importance scores) is a simplification. However, this stems from the nature of magnitude-based pruning, a standard practice in prior federated pruning methods [2, 3] .\n\nWhile strict independence is not absolute, theoretical and empirical evidence shows that trained weights in large networks exhibit asymptotic independence [4, 5], supporting this approximation.\n\nNotably, our Theorem 3.4 is agnostic to specific pruning techniques; it holds for any method satisfying Assumptions 3.2 and 3.3, including future advancements in generating independent scores.\n\n[2] Yuang Jiang, Shiqiang Wang, Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K Leung, and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices. IEEE Transactions on Neural Networks and Learning Systems, 34(12):10374–10386, 2022.\n\n[3] Hong Huang, Weiming Zhuang, Chen Chen, and Lingjuan Lyu. Fedmef: Towards memory-efficient federated dynamic pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 27548–27557, 2024.\n\n[4] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 130(3):1820–1852, 2020.\n\n[5] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725–752, 2020.\n\n\n> **Limitations** Please state the limitations of your work in Conclusion to facilitate further work.\n\nWe thank the reviewer for this valuable suggestion. We will state the limitations of our proposed FedRTS in Conclusion of the revised version to explicitly discuss the boundaries of our work and facilitate further work."}, {"review_id": "QWEKckccHW", "reviewer": "Reviewer_UDMM", "summary": "The goal of the paper is to propose a federated solution for robust model pruning. The key design of this manuscript is the proposed FedRTS, which can produce robust sparse models via combinatorial Thompson sampling. The author claims that the proposed FedRTS improves robustness and performance using a Thompson Sampling-based Adjustment (TSAdj) mechanism and addresses three critical issues of existing approaches—greedy adjustments, unstable topologies, and communication inefficiency. Authors evaluate proposed methods using Lightweight CV models (ResNet18, ShuffleNetV2) and one small NLP model (GPT-2 32M) on TinyStories.", "questions": "Typo: Rubust -> Robust (L45)\n\nAuthors may compare the relevant resource use of different methods. Ideally, just performance gain is not enough for real-world distributed ML. To show the practicability of the proposed method in a real-world setting, authors may provide more details about resource usage (communication/computation cost). In the proposed method, besides the standard FL stage, Thompson Sampling-based Adjustment may introduce an overhead of computation and reduce the practicality in the real-world deployment. The author may update Table 1 to include a comparison of computation costs.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1. This is an interesting work with notable results in terms of performance in different settings. I also appreciated the efforts to evaluate the methods, notably the experiment settings (Sec. 4.2). This work addressed an important problem in the field, and so will be of interest to the readership of the conference. \n\n2. The paper is well-written and easy to follow.\n\n3. A novel Thompson Sampling-based Adjustment (TSAdj) mechanism is proposed, and the methodology is evaluated via multiple publicly available datasets.\n\nWeaknesses:\n\n1. Assumptions in theoretical analysis may not hold in practice. The theoretical analysis (Section 3.3, Theorem 3.4) relies on several simplifying assumptions. For example, Assumption 3.2. (Independent importance score) The importance scores used for pruning are treated as mutually independent. However, in real neural networks, weight dependencies exist, and such independence or approximations may not hold, especially in small models or sensitive layers (e.g., attention heads in NLP).\n\n2. Design choices for hyperparameters are heuristic. Several components, such as the trade-off parameter γ in fusion, the scaling factor λ, and the number of core links κ, are chosen empirically or based on prior works. Though some tuning is shown in Appendix E, there is no systematic analysis of how sensitive FedRTS is to these choices. This can affect reproducibility and robustness in other settings, especially if applied to unseen tasks or models.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer UDMM for the detailed review and valuable feedback on our manuscript. We are encouraged that they found our work interesting and appreciated that the paper is well-written and easy to follow. Below, we provide detailed responses to all questions.\n\n\n> **W1** Assumptions in theoretical analysis may not hold in practice. **The theoretical analysis (Section 3.3, Theorem 3.4) relies on several simplifying assumptions.** For example, Assumption 3.2. (Independent importance score) The importance scores used for pruning are treated as mutually independent.\n\nWe acknowledge that the assumption of independent importance scores is a simplification. However, this assumption stems from the nature of __magnitude-based pruning__, rather than our regret analysis itself. Prior pruning methods [1,2] commonly rank individual weight magnitudes to assign importance, and treating these scores as independent has become a standard practice.\nMoreover, while weight magnitudes are not strictly independent, both theoretical results and empirical evidence suggest that __trained weights exhibit asymptotic independence__ [3,4], lending support to this assumption.\n\nImportantly, our Theorem 3.4 is __agnostic to the specific pruning technique__; it holds for __any pruning method__ satisfying Assumptions 3.2 and 3.3, including future methods that generate independent importance scores more efficiently.\n\n[1] Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural net works with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 355 2015\n\n[2] Xin Qian and Diego Klabjan. A probabilistic approach to neural network pruning. In International Conference on Machine Learning, pages 8640–8649. PMLR, 2021.\n\n[3] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 130(3):1820–1852, 2020.\n\n[4]  Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725–752, 2020.\n\n> **W2** Design choices for hyperparameters are heuristic. Several components, such as the trade-off parameter γ in fusion, the scaling factor λ, and the number of core links κ, are chosen empirically or based on prior works. Though some tuning is shown in Appendix E, there is no systematic analysis of how sensitive FedRTS is to these choices. This can affect reproducibility and robustness in other settings, especially if applied to unseen tasks or models.\n\nWe appreciate the reviewer’s insightful feedback regarding the empirical selection of hyperparameters and we acknowledge that the hyperparameter values tested in our ablation studies (Appendix E) were selected based on empirical priors from related works and initial exploratory experiments rather than through a comprehensive systematic approach (e.g., grid search over continuous parameter spaces). Despite this method, we ensured our parameter selection process maintained full transparency and reproducibility. Furthermore, we conducted systematic sensitivity analyses for each parameter as detailed below:\n* $\\gamma$ controls the balance between individual and aggregated information: a large $\\gamma$ places greater emphasis on aggregated information, while a small  $\\gamma$ concentrates more on individual outcomes.\n* $\\lambda$ scales the evidence added to the beta distributions' parameters ($\\alpha$, $\\beta$), which directly affect link selection: a large $\\lambda$ results in large increments to $\\alpha$ and $\\beta$ for selected links, accelerating the convergence of their distributions and promoting exploitation of current high-performing links. Conversely, a small $\\lambda$ applies small increments, maintaining higher uncertainty for less frequently selected links and encouraging exploration.\n* $\\kappa$ determines the layer-wise pruning rate: a large $\\kappa$ leads to slower topology evolution, while a small $\\kappa$ risks substantial information loss.\n* $\\Delta T$ impacts the frequency of topology adjustments: a large $\\Delta T$ may delay the convergence to stable topology, while a small $\\Delta T$ leads to frequent adjustments incurring higher resource costs.\n\nWhile our current analysis employs discrete sampling on hyperparameters' impacts, the conducted sensitivity analysis and empirical validation confirm FedRTS’s robustness and reproducibility. To directly address the reviewer's concern, we will implement systematic methods including grid search to comprehensively analyze FedRTS's sensitivity to these hyperparameters. This will be accompanied by: \n* A sensitivity heatmap quantifying performance variance across hyperparameters\n* Full publication of all hyperparameter configurations used in our experiments for reproducing\n\n\n> **Q1** Typo Rubust -> Robust (L45).\n\nThanks for pointing this out, we will revise it in the final version. \n\n\n> **Q2** In the proposed method, besides the standard FL stage, Thompson Sampling-based Adjustment may introduce an overhead of computation and reduce the practicality in the real-world deployment. The author may update Table 1 to include a comparison of computation costs.\n\nWe sincerely appreciate the reviewer's valuable feedback highlighting the necessity of resource cost evaluation for real-world applicability, especially concerning the potential overhead of TSAdj. We fully agree that performance gains must be evaluated alongside resource usage.\n\nIn TSAdj's design, all computations occur exclusively on the server, and clients incur zero additional FLOPs compared to baselines (FedDST/FedMef/FedTiny/PruneFL). The server-side FLOPs per outer loop include: global aggregation ($\\mathcal{O}( \\langle C_t \\rangle \\langle W \\rangle)$), outcome updating ($\\mathcal{O}(\\langle C_t \\rangle K)$), distribution updates ($\\mathcal{O}(\\langle W \\rangle)$), beta sampling ($\\mathcal{O}(\\langle W \\rangle)$), and mask adjustment ($\\mathcal{O}(\\langle C_t \\rangle (\\langle W \\rangle - K) + \\langle W \\rangle)$).\n\nTherefore, we can simplify the computational complexity to $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$ as $K = d \\langle W \\rangle$. Compared to the baselines' complexity $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$ (global aggregation and mask adjustment), our proposed TSAdj achieves the same computational complexity, demonstrating that TSAdj introduces no significant additional computational burden on the server.\n\n**Most importantly, TSAdj introduces no additional computation on devices compared to the baselines**. Its overhead is entirely server-side. In cross-device FL, the server is typically assumed to have substantial computational resources; therefore, TSAdj does not impose a significant extra burden compared to the baselines. Below is the revised Table 1 with on-device FLOPs analysis:\n\n\n|Target Density|Method|PPL| FLOPs|Comm. Cost|\n|-|-|-|-|-|\n|1|FedAVG|20.56|5.76E+08|260.41 MB|\n|50%|FedDST|20.10|1.24E+08|138.30 MB|\n|50%|FedSGC|26.13|1.28E+08|207.45 MB|\n|50%|FedMef|20.61|1.22E+08|165.96 MB|\n|50%|**FedRTS**|18.54|1.24E+08|138.84 MB|\n|30%|FedDST|24.46|3.89E+07|86.26 MB|\n|30%|FedSGC|32.39|3.86E+07|129.39 MB|\n|30%|FedMef|21.00|4.14E+07|103.51 MB|\n|30%|**FedRTS**|18.56|3.89E+07|86.44 MB|\n|20%|FedDST|26.49|2.00E+07|60.22 MB|\n|20%|FedSGC|43.00|2.17E+07|90.33 MB|\n|20%|FedMef|21.53|1.99E+07|72.26 MB|\n|20%|**FedRTS**|19.93|2.00E+07|60.34 MB|"}, {"review_id": "jIZaKBV2I5", "reviewer": "Reviewer_1eQR", "summary": "This paper addresses challenges such as instability introduced by traditional pruning methods in federated learning and further proposes a novel federated pruning approach based on Thompson Sampling. The authors conduct comprehensive theoretical analysis and empirical experiments to demonstrate the superiority of their method.", "questions": "1. When defining $f_n()$ in line 66, the authors could first define the loss function, then define the empirical risk or expected risk as the objective.\n2. Please provide the precise mathematical definition of the density $d$ mentioned in line 66.\n3. What does the symbol $\\mathbf{1}$ in line 84 represent?\n4. In line 87, what exactly is $X_t$ in the reward? Given that the authors mention it has a \"mean\"—please provide a precise definition of this random variable and clarify the source of its randomness.\n5. In line 125, does maintaining posterior probabilities for each link in TSAdj incur excessive computational overhead?\n6. Although the authors provide a regret analysis for the proposed pruning method, can they also provide a convergence analysis of the global model trained using this pruning method?\n7. The theoretical contributions of the paper are relatively weak. Please elaborate on the technical challenges involved in analyzing the regret of the Thompson Sampling algorithm in the federated learning pruning scenario considered in this paper.\n8. It is recommended that the authors consider more heterogeneous data splitting settings (e.g., concept shift or covariate shift) to evaluate the robustness of their proposed FedRTS method.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** This paper conducts very comprehensive experiments, validating the proposed methods across various model sizes and tasks in both the CV and NLP domains.\n\n\n**Weaknesses:** The authors do not appear to provide an in-depth analysis of the overhead of the sampling procedure in FedRTS, which may entail significant costs. Some notations and definitions are unclear (see specific questions for details). Additionally, the theoretical contributions are relatively weak.", "was_revised": true, "final_justification": "My final decision is to maintain my initial score. While the authors have provided a rebuttal outlining the contributions of the paper, I still argue that the work primarily applies Thompson sampling to federated pruning without formulating or addressing any fundamental problems, nor introducing new techniques.", "rebuttal": "We appreciate Reviewer 1eQR's insightful feedback, especially recognizing that our paper conducts very comprehensive experiments. We will address all concerns below.\n\n> **Q1** When defining $f_n$ in line 66, the authors could first define the loss function, then define the empirical risk or expected risk as the objective.\n\nThe loss function $f_n$ depends on the task of the $n$-th device, e.g., cross-entropy loss for the image classification task.  \n\n> **Q2** Please provide the precise mathematical definition of the density mentioned in line 66.\n\nThe density $d$ is defined as the ratio of non-zero elements to all elements, i.e., $d = \\frac{sum(m)}{\\langle m \\rangle}$, where $m$ denotes the binary mask, $sum(m)$ is the number of non-zero entries, and $\\langle m \\rangle$ is the total number of elements of $m$.\n\n> **Q3** What does the symbol **1** in line 84 represent?\n\n**1** denotes an indicator function, where $\\mathbf{1_{true}}= 1$, $\\mathbf{1_{false}}= 0$. We apologize for the mistake in line 84: it should be $m_{t,i} = \\mathbf{1}_{i \\in S_t}$. \n\n> **Q4** What exactly is $X_t$ in the reward? Please provide a precise definition of this random variable and clarify the source of its randomness.\n\n$X_t$ denotes the outcome (empirical importance) observed with selected arms $S_t$. For the active arm $i \\in S_t$, the $[X_t]_i$ is the probability of being among the top weight magnitudes after local training. For the inactive arm $i \\notin S_t$, the $[X_t]_i$ is the probability of being among the top gradient magnitudes after local training. These probabilities are computed through a voting mechanism as in Eqs.3, 4, and 5. The randomness of $X_t$ comes from the inherent stochasticity in the training process and random client sampling.\n\n> **Q5** Does maintaining posterior probabilities for each link in TSAdj incur excessive computational overhead?\n\nIn TSAdj's design, maintaining posterior probabilities **does not incur excessive overhead**. On the server, weights aggregation iterates exactly $\\langle C_t \\rangle$ times, requiring $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$ for weight averaging, $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$ for outcome computation (expected time with Quick Sort), $\\mathcal{O}(\\langle W \\rangle)$ for updating beta distributions and sampling probabilities, $\\mathcal{O}(\\langle W \\rangle) $ for arms selection. \n\nThe overall complexity simplifies to $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$. Compared to baselines' complexity (e.g., FedMef/FedTiny/PruneFL's $\\mathcal{O}(\\langle C_t \\rangle \\langle W \\rangle)$), our proposed TSAdj achieves the same computational complexity, demonstrating that TSAdj introduces no significant additional computational burden on the server.\n\nMost importantly, TSAdj’s overhead is **server-side**, and it has **NO extra computational overhead** compared to baselines on devices. In the cross-device FL, the server is usually assumed to have substantial resources.\n\n> **Q6** Although the authors provide a regret analysis for the proposed pruning method, can they also provide a convergence analysis of the global model trained using this pruning method?\n\nWe provide the following non-convex convergence analysis for our FedRTS. We need to add the following common assumptions,\n\n_Assumption 3.4 (Bounded variance of local gradients) There exist constants $\\beta$ and $\\zeta$ such that_\n\n$\\frac{1}{N} \\sum_{n=1}^N ||\\nabla f_n(W) - \\nabla f(W)||^2 \\le \\beta^2 ||\\nabla f(W)||^2 +  \\zeta^2$\n\n_Assumption 3.5 (Bounded gradients) The gradients are bounded by a constant $\\psi$, i.e., $\\mathbb{E}[||\\nabla f(W)||^2] \\le \\psi^2$._\n\n_Assumption 3.6 (Bounded weights) the weight magnitudes are bounded by a constant $\\varphi$, i.e.,_\n\n$\\mathbb{E}[||W||_\\infty] \\le \\varphi$\n\nAssumptions 3.4 and 3.5 follow prior works [1,2], and Assumption 3.6  is justified by the initialization scheme and the regularization term. Based on these assumptions, we establish the convergence upper bound for FedRTS.\n\n__Theorem 2 (Convergence of FedRTS)__. Under Assumptions 3.1 (L-continuity), 3.4, 3.5 and 3.6, for FedRTS with TSAdj with full client participation and arithmetic aggregation, $p_n = 1/N$, with learning rate $\\eta \\le \\frac{1}{2LE\\sqrt{3\\beta^2+3}}$, adjustment intensity $ \\kappa_t = K - \\frac{\\alpha_{adj}K}{\\sqrt{t}}$, the sparse model $W_t \\odot m_t$ satisfies the following upper bounds:\n\n$$\\min_{1 \\le t \\le T}  \\mathbb{E}\\left[||\\nabla f (W_t \\odot m_t)||^2\\right]   \\le  \\frac{\\Omega_1\\}{\\Delta T\\eta \\sqrt{T}}+ \\frac{\\Omega_2}{\\eta T} + \\Omega_3\\eta^2 $$\n\nwhere $\\Omega_1 =\\frac{12\\alpha_{adj} K(2\\psi\\varphi + \\varphi^2L)}{E}$, $\\Omega_2 = \\frac{12\\Delta f_0 }{E}$, $\\Omega_3 = 12L^2E^2\\zeta^2$ , $\\Delta f_0$ denotes the gap between initial model and optimal, i.e., $\\Delta f_0 = f(W_0 \\odot  m_0) - f*$, $f*$ is the optimal value. specifically, when $\\eta = \\frac{1}{2T^{1/6}LE\\sqrt{3\\beta^2+3}}$, consequently for a given $\\varepsilon > 0$ we have that \n$$ T = O(\\frac{1}{\\varepsilon^{3}\\Delta T^3} + \\frac{1}{\\varepsilon^{\\frac{6}{5}}} + \\frac{1}{\\varepsilon^{3}}) = O(\\frac{1}{\\varepsilon^3}). $$\n\n__proof.__\n\nDue to limited space, we provide a sketch of proof for the Theorem, and we can provide the proof to Lemma 1 and Lemma 2 in further discussion if the reviewer is interested. With the key Lemma 1 (Bound of topology adjustment) and Lemma 2 (Upper bound of local training), the bound of loss descent in one loop is \n\n$$ \\mathbb{E} \\left[ f(W_{t+1} \\odot m_{t+1}) - f(W_{t} \\odot m_{t}) \\right]  \\le - \\frac{1}{12} \\eta E \\mathbb{E}[||\\nabla f(W_{t} \\odot m_{t})||^2] + \\eta^3 L^2 E^3\\zeta^2 + (\\psi\\varphi + \\frac{L\\varphi^2}{2})(K-\\kappa_t) $$\n\nBy rearranging the terms, subtracting $f*$, and denoting the $r_t = \\mathbb{E}[f(W_{t} \\odot m_t) - F^*]>0$, $\\Omega_3 = 12L^2E^2\\zeta^2$ , the Inequality converts to\n\n$$\\mathbb{E}||\\nabla f(w_{t} \\odot m_t)||^2 \\le \\frac{12}{E\\eta}(r_{t} - r_{t+1})  + \\frac{6(2\\psi\\varphi + L\\varphi^2)}{E\\eta}(K - \\kappa_t) + \\Omega_3\\eta^2.$$\n\nAfter that, given the fact $\\min_{1\\le t \\le T}\\mathbb{E}[||\\nabla f(W_{t}\\odot m_t)||^2] \\le \\frac{1}{T}\\sum_{t=1}^{T}\\mathbb{E}[||\\nabla f(W_{t}\\odot m_t)||^2]$, by summing $t$ from $1$ to $T$, we can obtain\n\n$$ \\min_{1 \\le t \\le T} \\mathbb{E}||\\nabla f (W_t \\odot m_t)||^2  \\le \n \\frac{6(2\\psi\\varphi + L\\varphi^2)\\sum_{t=1}^{T}(K - \\kappa_t)}{E\\eta T} + \\frac{12r_0}{E\\eta T} + \\Omega_3\\eta^2.$$\n\nGiven the definition of $\\kappa  = K - \\frac{\\alpha_{adj}}{2}(1+\\cos{(\\frac{t\\pi}{T_{end}})})K$ is related to $t$ and the adjustment performs every $\\Delta T$, we use the fact \n\n$$\\sum_{t=1}^{T}(K - \\kappa_t) \\le \\frac{2\\sqrt{T}\\alpha_{adj}K}{\\Delta T}$$\n\nGiven $r_0 = \\Delta f_0 = f(w_0) - f*$, we can obtain\n\n$$\\min_{1 \\le t \\le T}  \\mathbb{E}\\left[||\\nabla f (W_t \\odot m_t)||^2\\right]   \\le  \\frac{\\Omega_1\\}{\\Delta T\\eta \\sqrt{T}}+ \\frac{\\Omega_2}{\\eta T} + \\Omega_3\\eta^2 $$\n\nwhere $\\Omega_1 =\\frac{12\\alpha_{adj} K(2\\psi\\varphi + \\varphi^2L)}{E}$, $\\Omega_2 = \\frac{12\\Delta f_0 }{E}$.\n\n**Lemma 1.** (Upper bound of topology adjustment) Under Assumptions 3.1 (L-continuity), 3.5, and 3.6, in the $t$-th loop, the information loss in the topology adjustment is bounded by\n   $$\\mathbb{E}\\left[ f(W_{t+1} \\odot m_{t+1}) - f(W_{t+1} \\odot m_{t}) \\right] \\le \\psi\\varphi \\sqrt{K - \\kappa_t}+ \\frac{(K -\\kappa_t) L\\varphi^2}{2},$$\n\n**Lemma 2.** (Upper bound of local training) Under Assumptions 3.1 (L-continuity) and 3.5, if $\\eta \\le \\frac{1}{2LE\\sqrt{3\\beta^2+3}}$, $p_n = 1/N$, then \n    $$\\mathbb{E} [f(W_{t+1} \\odot m_{t}) - f(W_t \\odot m_{t})] \\le  - \\frac{1}{12} \\eta E \\mathbb{E} \\left[||\\nabla f(W_{t} \\odot m_{t})||^2 \\right] + \\eta^3 L^2 E^3\\zeta^2$$\n\n__Remark.__ The convergence theorem provides valuable insight into how hyperparameters affect convergence. Specifically, a lower adjustment ratio $\\alpha_{adj}$, less frequent adjustments (i.e., a larger $\\Delta T$) may facilitate faster convergence. \n\n[1] Li, Y., & Lyu, X.. Convergence analysis of sequential federated learning on heterogeneous data. NeuIPS, 2023.\n\n[2]  Li, Xiang, et al. \"On the convergence of fedavg on non-iid data.\" ICLR 2020.\n\n> **Q7** Please elaborate on the technical challenges involved in analyzing the regret of the Thompson Sampling algorithm in the federated learning pruning scenario considered in this paper.\n\nThe main difficulty in this paper lies in the __unobservable reward function__. Since the server cannot directly access client data, the true impact of pruning decisions (i.e., the reward) cannot be observed, making it impossible to identify the global optimal arms at each step. Referring to the previous TS work [3], we use the empirical mean reward μ as a proxy for the unknown reward function and treat the greedy optimal arms as the target. Our work provides the __first__ theoretical baseline on federated pruning with TS, and we acknowledge that developing more sophisticated regret analyses for federated settings—particularly under challenges such as non-stationarity—remains an important avenue for future work.\n\n[3] Wang, Siwei, and Wei Chen. \"Thompson sampling for combinatorial semi-bandits.\" ICML, 2018.\n\n> **Q8**  It is recommended that the authors consider more heterogeneous data splitting settings (e.g., concept shift or covariate shift) to evaluate the robustness of their proposed FedRTS method.\n\nWe have evaluated FedRTS and FedMef under feature distribution skew (covariate shift). While maintaining quantity and label balance across clients, we injected different types of Gaussian noise into the input features. Each client randomly selected one of two or three types of Gaussian noise, each with distinct means and variances. The results on CIFAR-10 (0.3 density) are shown below:\n\n||IID|2-Type Noise|3-Type Noise |\n|-|-|-|-|\n| FedMef | 0.834 | 0.788| 0.784|\n| FedRTS | 0.838 | 0.792| 0.788|\n\nNotably, FedRTS consistently outperforms FedMef under different degrees of covariate shift, demonstrating its robustness in heterogeneous data-splitting settings."}]

Author rebuttal:

Meta-review: This paper aims to enhance existing federated pruning methods through probabilistic history-aware decisions based on a Thompson-sampling adjustment. Casting federated pruning as a combinatorial bandit problem is novel. Clear improvements over baselines are demonstrated, and a theoretical regret analysis with proof is provided.
Decision: Accept (poster)