Mobilizing Personalized Federated Learning in Infrastructure-Less and Heterogeneous Environments via Random Walk Stochastic ADMM
Authors: Ziba Parsons
Fei Dou
Houyi Du
Zheng Song
Jin Lu
Venue: NeurIPS 2023 poster (2023)
Keywords: Mobilized Federated Networks
Personalized Federated Learning
Random Walk
Stochastic ADMM
TL;DR: We proposed a new personalized federated learning optimization algorithm for dynamic networks called Random Walk Stochastic ADMM (RWSADMM).

Abstract: This paper explores the challenges of implementing Federated Learning (FL) in practical scenarios featuring isolated nodes with data heterogeneity, which can only be connected to the server through wireless links in an infrastructure-less environment. To overcome these challenges, we propose a novel mobilizing personalized FL approach, which aims to facilitate mobility and resilience. Specifically, we develop a novel optimization algorithm called Random Walk Stochastic Alternating Direction Method of Multipliers (RWSADMM). RWSADMM capitalizes on the server's random movement toward clients and formulates local proximity among their adjacent clients based on hard inequality constraints rather than requiring consensus updates or introducing bias via regularization methods. To mitigate the computational burden on the clients, an efficient stochastic solver of the approximated optimization problem is designed in RWSADMM, which provably converges to the stationary point almost surely in expectation. Our theoretical and empirical results demonstrate the provable fast convergence and substantial accuracy improvements achieved by RWSADMM compared to baseline methods, along with its benefits of reduced communication costs and enhanced scalability.

Mobilizing Personalized Federated Learning in Infrastructure-Les and Heterogeneous Environments via Random Walk Stochastic ADMM
Ziba Parsons CIS Department University of Michigan Dearbor, MI w Abbapars@umich edu
Fei Dou School of Computing University of Georgia Athens, GA fei www.uga..eacc.oooooo edu
Houyi Du CIS Department University of Michigan Dearborn, MI houyidu umi ch.chh... edu
Zheng Song
Jin Lu
CIS Department University of Michigan Dearborn,
School of Computing University of Georgia Athens, GA jin 1ww.ga.eaaa..u
zhesong@umin umi ch edu
Abstract
This paper explores the challenges of implementing Federated Learning (FL. in practical scenarios featuring isolated nodes with data heterogeneity, which can only connected to the server through wireless links in an infrastructure-less environ- ment. To overcome these challenges, we propose novel mobilizing personalized FL approach, which aims facilitate mobility and resilience. Specifically, we develop novel optimization algorithm called Random Walk Stochastic Alternttnn Direction Method Multipliers (RWSADMM), RWSADMM capitalizes on the server's random movement toward clients and formulates local proximity among their adjacent clients based on hard inequality constraints rather than requiring consensus updates or introducing bias via regularization methods. To mitigate the computational burden on the clients, an efficient stochastic solver of the ap- proximated optimization problem is designed in RWSADMM, which provably converges to the stationary point almost surely in expectation. Our theoretical and empirical results demonstrate the provable fast convergence and substantial accuracy improvements achieved by RWSADMM compared to baseline methods, along with its benefits of reduced communication costs and enhanced scalability.
Introduction
Federated Learning (FL) 12 4 is distributed machine learning paradigm that enables clients to learn shared model without sharing their private data. Unlike traditional machine learning approaches that rely central servers for model training. FL allows clients to collaborate and train the model in a distributed manner, overcoming privacy issues related to passing data to a central server. Despite its advancements, real- wolldwrldd upplications in environments with insufficient network support continue to face challenges. a) Maintaining consistent and reliable connections between the central server and clients becomes exceedingly challenging in environments lacking network infrastructures, e.g., natural disasters or military warzones. While intermittent connectivity may be available through satellite networks, the instability and limited capacity of such networks prevent the transmission of large data volumes, making it difficult to collect model updates from soldiers or first responders. b) The non-IID mon-indeeendent and identically distributed) nature of clients' data, characterized by heterogeneity across the network, can hinder the generalization of the global model
37th Conference on Neural Information Processing Systems (NcurIPS 2023), New Orleans, USA.

---

for each client. Addressing these challenges is crucial for practical FL in such environments. In this paper, we propose RWSADMM, a novel FL scheme that uses Random Walk (RW) algorithm to enable server mobility among client clients. These dynamic approach benefits scenarios with limited internet connectivity, where clients form clusters using local short-range transmission devices.
For example, in various contexts such as robotics, emergency response, or military operations, consider a scenario where individuals or entities are equipped with integrated visual augmentation systems (IVAS) [5]. To facilitate the collection of model updates from these entities, a mobile unit equipped with a powerful computer navigates the environment [o]. communicating with locations through a network, which might be satellite- satellite-based or another suitable alternative. Upon reaching an entity, the mobile unit employs short-range communication technologies such as WiFi direct, Zigbee 77.. or Bluetooth to establish connections with nearby IVAS devices. Through these connections, the unit collects model updates and distributes new models as necessary. graph-based representation is utilized to determine the order of interactions, where entities are depicted as nodes, and the edge between an entity and its neighbor indicates that the neighbor is within the communication range of the unit that reaches the entity. This graph assists the mobile unit in making informed decisions about the order in which it engages with the entities.
Various applicable examples of such constrained network situations span across different domains, including ad hoc wireless learning 8 g I0, wildlife tracking [T] 12 Internet of Underwater
Things (IoUT) [14 [5]. natural disaster management [16] 17), military operations [18], or fostering a
digital democracy 19 20 which assists in overcoming restrictions imposed by regimes that prohibit internet access to civilians.
Specifically, to address challenge a), propose an algorithmic framework called RWSADMM (Fig. D. short for Random Walk Alternating Directional method of Multipliers, which considers a dynamic reachability graph among distributed clients using a movable vehicle as the central server. Clients are represented as nodes in the graph, with edges denoting neighborhood connections. Personal devices, referred as local clients, establish dynamic connectivity with the server when the server is nearby. The server connects with a selected client and its neighbors while moving between locations using a non-hoon non-homogeneous RW algorithm for probabilistic navigation. In each computation round, the vehicle broadcasts and gathers local model updates from residing clients, who rely on short-range communication to interact with the moving server, when it's within the communication range. The received updates are aggregated and used to update the global model iteratively.
To tackle the second challenge (b) arising from the heterogeneity of data distribution among clients, RWSADMM incorporates model personalization through local proximity among adjacent clients using hard inequality constraints, as opposed to unconstrained optimization with regularization tech- niques that may induce model bias. By formulating the problem with these constraints, RWSADMM reduces the computational complexity for clients, effectively mitigating the limitations of local computational power. This is achieved by designing the solver to the stochastic approximation of the minimization subproblem within the typical ADMM algorithm.
Mobil lzod server location
Mozilized server losation
Clants partic paling the update
Clants particineting the spdate Cilnns not partiipating in the updane
Clents not part cipating in the updaite
(c) Mobilized FL between clients and the server
(a) step &
(b) step +
Figure I: This illustration showcases the training process using the RWSADMM algorithm. A vehicle, serving the mobile server, navigates between different clients using a random walk strategy. (a) In step k. the server moves to client 13, covering the clients in (13) for FL model training and completing the aggregation step. (b) In step l + 1, client 5 is selected, and the vehicle moves to client 5. The training and aggregation steps occur within the zone encompassing (5).

---

Our research makes three main contributions. Firstly, our proposed RWSADMM algorithm is the first attempt enable mobilizing FL with efficient communication and computation in an infrastructure-less setting. The RWSADMM framework involves a server dynamically moving between different regions of clients and receiving updates from one or a few clients residing in the selected zone, which reduces communication costs and enhances system flexibility. Secondly, to address the issue of data heterogeneity among clients, RWSADMM formulates local proximity among adjacent clients based on hard inequality constraints, avoiding the introduction of model bias via consensus updates. This approach provides an alternative realization of personalization, which is crucial when dealing with highly heterogeneous data distributions. Thirdly, to mitigate the computational burden on the clients, an efficient stochastic solver of the subproblem is designed in RWSADMM, which provably converges to the stationary point almost surely in expectation under mild conditions independent of the data distributions. Our theoretical and empirical results demonstrate the superiority of our proposed algorithm over state-of-the-ar personalized Federated Learning (FL.) algorithms, providing empirical evidence for the effectiveness of our approach.
2 Related Work
This paper is relevant to two distinct research areas, which are reviewed in two separate sections: FL frameworks that tackle data heterogeneity and ADMM- FL frameworks.
FL with data heterogeneity FL was initially introduced as FedAvg, client-server- based framework that didn't allow clients to personalize the global model their local data M. This led to poor convergence due to local data heterogeneity, negatively impacting the global FL. model's performance on individual clients. Recent works proposed a two-stage approach to personalize the global model. In the first stage, the FL global model is trained similarly to FedAvg. However, the second stage is included to personalize the global model for each local client through additional training on their local data. (21] demonstrated that FedAvg is equivalent to Reptile, new meta-learning algorithm, when each client collects the same amount of local data. To learn global model that performs well for most participating clients, [22) proposed an improved version, Per-FedAvg. This new variant aims to learn a good initial global model that can adapt quickly to local heterogeneous data. An extension of Per-FedAvg, called PFedMe [23], introduced lg f2-norm regularization term to balance the agreement between local and global models and the empirical loss. (24) proposed Ditto, a
multi-task learning- based FL. framework that provides personalization while promoting fairnsss and robustness to byzantine attacks. Ditto uses a regularization term to encourage personalized local models to be close to the optimal global model. [25] proposed to interpolate local and global models to train local models while also contributing to the global model. However, scaling these approaches can be challenging due to high communication costs, reliance on strong assumptions about network connectivity, or the requirement to compute second-order gradients. Additionally, there is a potential for enhancing the algorithms' overall performance.
ADMM-based FL The Alternating Direction Method of Multipliers (ADMM) is a widely recognized algorithm that effectively tackles optimization problems across multiple domains. In recent studies, ADMM has been successfully employed in distributed learning, as demonstrated by several works
32 33 In Federated Learning (FL) context, researchers have proposed various methods to address specific challenges. For handling falsified data in Byzantine settings, [34 introduced a robust ADMM-based approach. To mitigate local computational burdens in FL., [35 developed an inexact ADMM-basee algorithm suitable for edge learning configurations. FL itself enables local training without the need to share personal data between clients and the server. Despite the advantages of Fl., there is still a concern regarding clients' privacy. Analyzing the parameter differences in the trained models uploaded by each client can compromise their privacy. To tackle this issue, (36) proposed an inexact ADMM-based federated lcarning algorithm that incorporates differential privacy (DP) techniques (37). By leveraging DP, the algorithm enhances privacy protection during the FL process. These ADMM- based frameworks also have high communication costs, ranging from O(n) to O(n²) per iteration, depending on the network's density with n clients. [38] introduced a Proximal Primal-Dual Algorithm (Prox-PDA) to enable network nodes to compute the set of first-order stationary solutions collectively. Moreover, these algorithms do not account for data heterogeneity in their framework designs, leading to performance deterioration in such scenarios. The most similar algorithm to RWSADMM is called Walkman (39]. Walkman is an
26
27
28
29 30,
31
ADMM-based framework utilizing the random walk technique for distributed optimization. In

---

Walkman, the communication and computation costs are reduced by activating only one agent at each step. Compared to other ADMM-based approaches, including Walkman, RWSADMM has several distinctive features. RWSADMM leverages stochastic approximation to reduce computation costs per iteration and enforces hard inequality constraints instead of consensus to manage heterogeneous data, resulting in increased robustness. Additionally, RWSADMM considers the dynamic graph, allowing it to adapt to changing network conditions and potentially improve communication efficiency. RWSADMM also incorporates hard constraint parameter to promote local proximity among clients instead of using a regularization term as Walkman does to promote client consensus. This approach better balances personalization and global optimization. Finally, while Walkman is fully distributed without server involvement, RWSADMM is a server-basee approach in which the server aggregates information from small group of clients in each computation round.
3 Random Walk Stochastic ADMM (RWSADMM)
Before delving into the specifics of the proposed algorithm, we present the key notation used throughout this research. x IRd represents a vector with length d and e is defined as a vector with entries equal to I and X E R depicts matrix with rows and d columns. [x]; represents the ith element of vector x and [ is the (i. j) th element of matrix X. [X]: [X] represent the ith row and jth column of matrix X, respectively. (x)( is used to denote the jth entry of the gradient of fx). The inner product of A and B is shown as (A, B). E2 indicates the expectation given the past .i..... E1-1. @ represents the Hadamard product/element-vii the Kronecker product between two matrices. Finally, Norm of vector x is denoted as ||||
product and @ represents
EL |a,/", x Rd and Frobenius norm of matrix X is written as |X||
Σ
m j=1
Let us first define our Mobilizing FL. problem. Mobilizing FI., which involves a mobile server, can be formulated as an optimization problem on connected graph g = (V, The graph comprises set of n clients, represented as V = 21, 12, ...; Un and a set of m edges, denoted as E. The objective to minimize the average loss function across all clients while adhering to inequality constraints that ensure local proximity among the clients' respective local models. The optimization problem can be formulated mathematically as follows:
(ES(x))) s.t. |x xy1 -x--xyl e,, E (L......n)). e N(()/v,
miit
Micm ERP T2
where fx;:) represents the local loss function with the model parameter as x; for the client the vertex set (i) contains client and its neighboring clients, and E; is the non-consensus relaxation between local neighboring clients to replace model consensus requirement in typical FL. In our proposed FL method, we model the server's 's movement as dynamic Markov Chain, introducing a dynamic element to the traditional ADMM- approach. This work is the first to consider dynamic mobile server within the ADMM-based FL framework. In RWSADMM, client-server communication occurs only when the server close to a client. The sequence of client indices that are updated, denoted as ig, evolves based on non-homogeneous Markov Chain with a state space of 1,.... n [40]. To describe the transition dynamics of the Markov Chain, we employ the non- homogencous Markovian transition matrix P(k). which represents the probabilities of transitioning between clients at time k. Specifically, the conditional probability of selecting client j as the next client, given that client i is the current client, is defined as:
P(K))s Pr (is+1 jlùx = i) [0.1]
(2)
Additionally, it is assumed that the server determines the probability of all possible locations for its next destination based on the transition matrix P(k) at time k. This provides a probabilistic approach to server navigation, allowing it to move around the network more effectively. To guarantee convergence, RWSADMM depends on the frequency of revisiting each agent. This quality is described by the mixing time of the algorithm. An assumption for the mixing time is as follows:
Assumption 3.1.
The random walk (iz))20, Us. E V forms irreducible and aperiodic (ergodic)
Markov Chain with transition probability matrix of P(k) E Raxa defined in Eq. (2) and stationary
distribution π satisfying limg-poo πe" P (k) π.. The mixing time (for a given ö > 0) is defined as
the smallest integer (0) such that Vi E V,
(()) TT| $ ST.
(3)

---

where т, == min ,. This inequality states the fact that regardless of the current state i and time k. the probability of visiting each state after r(6) steps is (close to π. that is, Vi. E V.
((()) T 6x.
Eq. 4 used prove the sufficient descent of Lyapunov function La in Section 3.1. Let's also define
muz lim Ply = max(P(())e))
(5)
from which one can further obtain P()] I ||aaall for all k. Namely, the matrix P Paa is computed the element-wii wise maximum matrix among all the matrices P(k), for ls 0, ...... Therefore, the mixing time requirement in Eq. (3) guaranteed to hold for
V2 l0)
V2
T(6) PP)
In
(6)
ÓT.
maz)
8%.
where (PP) := sup [
|||||| /I f 0,f R".. Using Eq. 5
have vp, c(P) S
(PP) ma)
max and the inequality (a) can be inferred.
3.1 Algorithm
In this section, derive RWSADMM by integrating random walk and stochastic inexact approx- imation techniques into ADMM. Considering X == row((1, x E I2xx" F(X) ==
Ex= (x;). where the operation row(() refers to row-wise stacking of vectors 's. The mobilizing FL P..rrolem can be expressed as:
1 F(X) Y Vi.. X n
min
s.t. 11y,- -1yal $10 1 I,...,
where 1 = [1 1. 1] R" n4 denotes the volume of the vertex set (t)). The constraint implies that |x; Xyl S E,, Vi = 1.... n and Vj E (i) through the triangle inequality. y; stored on the server necessarily introduced as a local proximity of (i).. We can obtain the augmented Lagrangian for problem
(8) where E; = 6/2 and Z, E R.P are the dual variable and B is the barrier parameter. The RWSADMM algorithm minimizes the augmented Lagrangian [y Imm X, Zi..) in an iterative manner. At each iteration k2 only a subset of clients covered by the mobilized server, the clients in ((ss), participate in the federated update. The following updates are performed:
L 1m
I [F() Σ (Z. 1 sy, XNtal ( +
B Σ ||| y,, Xwrol - e.
Xis arg min La(y (y Xiu 2,),
arg min La X Zwoa).
Y4
where Yl., x and z denote the groups of variables of the local parameters stored by client in at the (I: 1)th update. After solving these subproblems, we update the multiplier Zi, as follows:
2i = + A( x =e,,
Next, we derive the solver of each subproblem. The three steps are noted as Updating X Updating Y and Updating Zi.- Updating x,, min (x:,, + (Zlg, (y', - x,,l- -.,,) f Illy'a - xx, Ei,
The Problem 9 can be solved iteratively, consuming significant computational resources for the local clients. Furthermore, the computational complexity increases as the local dataset grows, as is often true in woal-world applications. By utilizing the stochasticity and first-order subgradient expansion, we arrive at a more computationally efficient approximation of the original problem in Eq. TO)..
min 9t, (xl, (xi, x(,) (Zi. Iy, xx,, -.,)) 3 + -xxl
E
(10)
In Eq. 10 E, denotes few samples randomly selected by client it from its feature set and their ground truth labels in pairs at the k-th iteration. The function gi, (x(_ Eip)) is defined as

---

the stochastic gradient of fi. (x²,) at x The stochastic approximation can tremendously reduce memory consumption and save computational costs each iteration. By setting the subgradient of the objective function in Eq. (TO) to zero, we can derive the closed-form solution in Eq. (TI).
Xi, Yy bii sgn(t") sogn(t)) @ (e: (x, f.,)) - vi.
sgm((t) (di
9n (x. (11)
3
where the signum function sgn(-) extracts the signs of a vector and t'2 V/a x/_
Updating y : We solve the following problem
yi. Xw(aa & e..) + 11 Xxrewl 1 e.ull
(12)
Y4
one can readily derive closed-fome form solution for the problem 12 as:
34
X1x
+ +EL, @ sgm(t;,))
(13)
JENN
where ti, y X is similar to that of Eq. (1) exeept the updated x. Specifically, via mathematical induction, we can attain the new updated form of yi. below, which can also reduce the communication cost from (n) to O(1):
Ziu
EiL) sgn(t,,)] [x]
+ei sgm((!))
(14)
The Lagrangian multiplier i can updated strictly following the standard ADMM scheme below:
Updating z
312 x xB [x,, -y -E4,]
(15)
The coefficient used in Eq. 15 is decayed in each process step to achieve better convergence.
Please refer Appendix for the entire RWSADMM algorithm framework.
4 Theoretical Analysis
In this section, present the theoretical convergence guarantee of RWSADMM. To ensure its convergence, certain common assumptions are made regarding the properties of the loss functions. The assumptions are as follows:
Assumption 4.1. The objective function f(x) is bounded from below and coercive over RR,, that is, for any sequence {x* Fkzo C R.,
if ||**|| k-00
f(()
(16)
Assumption 4.2. The objective function fx(''s 's are smooth, that is, ft are differentiable, and its gradients are L-Lipschitz, that is, Vu, v E E2" [9]
[V V/((v]l S L|lu- vll. Vi I....,
(17)
Remark: In consequence it also holds that Vu, E
[u) f(v)s VVi(v" v) = u vII Vi I.....n.
(18)
Assumption 4.3. The objective function f is M-Lipschitz, that is, Vu, R2
[f(u) - f(v) < M
(19)
Assumption 4.4. The first-order stochastic gradient sampled, which returns noisy but unbiased estimate of the gradient of f at any point x E IR,, that is, Vx E TR.,
[e(g(x, {) = (f(x)
(20)
Remark: Substituting Eq. 200 into Eq. 17 one can obtain that for 1, .......0 we have
Relg(n, {)] (ello(v s T.Ilu- |vl
(21)
Substituting Eq. 20 into Eq. (1),, for 1,..., n,, obtain
f((u) - f((v) & Eclo(v.e)) -) ワ | vlI
(22)

---

Assumption 4.5, The noise variance of the stochastic gradient is bounded as:
[x(lV g(x, ())) v exp(1). for x.
(23)
This condition bounds the expectation of fx,) (xx,, &.)l Using Jensen's inequality, this condition implies bounded variance [41].
We revisit the related crucial properties of the Markov Chain. The first time that the Markov Chain (ix 220 hits agent is denoted as T, == minkk ig = i}. and maximum value of T over all clients is defined as T' max ................................ }. For l T, let r(k, i) denote the iteration of the last visit to agent i before k, mathematically we have
Tk,, max is i, < kj.
(24)
To prove the convergence of our proposed algorithm, two Lyapunov functions defined for RWSADMM are required to be investigated:
Lg = Lsly". "asly,"";,"""""" 22), M = LB
1
y -y y,,h.,0p
((h.))+1
(25)
where L,(y*, x=; ) defined in Eq. 8 The M is utilized in the convergence analysis. To
guarantee the convergence of our algorithm, first, refer to the asymptotic analysis of the nonhomo- geneous Markov chain presented in 42). Define & (Ak,)) I) with & 2 as the product of the transition probability matrices for the Markov chain from time 1 to k i.e., ((k, P(k)... (I)) with 2 I.
Then we have the following convergence result:
Lemma 4.6. Consider
1. Vs, limk-rox + (k: eeee".
2. The convergence of & geometric and the rate of convergence considering Vk, with k 2
2 0, is given by
(k. 1 S (1
(26)
4n
Using Lemma 4.6 the convergence analysis of the algorithm is as follows.
Lemma 4.7. Under Assumptions 4.1 and 4.2 if > 21 + 2, (M2)) is lower bounded and convergent, the iterates x* Z" 1:20 generated by RWSADMM is bounded.
The proof sketch and the detailed convergence proof are presented in Appendix B Using Lemma 4.7
and B.6 we can present the convergence of RWSADMM in Theorem 4.8
Theorem 4.8. Let Assumption 4.5 hold. For B > 2 holds that any limit point (y", X* Zz) of the sequence (y*, X z generated by RWSADMM satisfies y =x;", i stationary point of Eq. with probability that is,
.,..., n. where y
Pr(0 Σ (vly)))
(27)
If the objective function of Eq. is convex, then y* is minimizer
Next, Theorem 4.9 further presents that the algorithm converges sublinearly. This is comparable to the convergence rate of other FL methods [43 44 24, (25), but the existing methods didn't 't consider the dynamic graph and infrastructure-less environment. The detailed proof is offered in Appendix C
Theorem 4.9. Under Assumptions 33.I).
4.1 and (4.2) with given 8 in Lemma 4.7 and local
variables initiated as fi(x)) = [x, Vi {1. [I.....n. n.., there exists sequence {g 3k20 with
{g*} E 0L k+1 satisfying
min TE KSK
C
(L
f), VK 7(6) +2
(28)
K
where C/ is a constant depending on B, L, and y, and (6)).
Communication Complexity Using Theorem 4.9 the communication complexity of RWSADMM for nonconvex nonsmooth problems is as follows. To achieve ergodic gradient deviation
1i s for any K > 7(8) + 2, it is sufficient to have E, = RSk

---

K (L - f) s (a)
C
K 0
z(0)² +1
(29)
(a) is achieved by taking Lg and as constants and independent of n and the network structure. Using the r55 definition from O by setting ò = 1/2 and assuming the reversible Markov chain with P(k)T P(k), the communication complexity is
0 (1 (g
-
In-n
(30)
Communication Comparison Among the baseline frameworks, Per-FedAvg [22] and APFL [25] have addressed the communication complexity their respective frameworks. By assuming that Assumption 3.1 holds and utilizing Eq. (30). we can determine the communication complexity of RWSADMM as ((w-t) for K iterations. In comparison, Per-FedAvg exhibits a higher commu- nication complexity of ((w-3/3) In the case APFL, all clients are assumed to be used in each computation round to ensure convergence in nonconvex settings. The communication complexity of APFL is determined as (/33/4-3/4)) where represents the total number of clients. Consequently, when n is large, APFL exhibits a significantly higher communication rate than RWSADMM. Overall, the communication complexity analysis suggests that RWSADMM offers superior scalability and communication efficiency compared existing methods.
Experimental Results
Setup We evaluate the performance of RWSADMM using heterogeneous data distributions. All the experiments are conducted on a workstation with Threadripper Pro 5955WX, 64GB DDR4 RAM, and NVidia 4090 GPU. All frameworks are performed on standard FL benchmark datasets (MNIST 45. Synthetic 223, and CIFARIO (46) with 10-class labels and convex and non-convex models. Multinomial logistic regression (MLR), multilayer perceptron network (MLP), and convolutional neural network (CNN) models are utilized for strongly convex and two non-convex settings, respec- tively. We create moderately dynamic connected graph of randomly placed nodes where each node has at least 5 neighboring nodes at k-th update. We set the probability transition matrix ((:)) as [P(k]]ij = 1 //de((i)) and set up the experiments for N = 20 clients with regeneration frequency of 10 steps for the dynamic graph. The data is split among clients using a pathological non-IID setting. The data each client contains portion of labels (two out of ten labels), and the allocated data size for each client is variable. For the Synthetic data, we use the same data generative procedures of 23 with 60 features and 100 clients. All local datasets are split randomly with 75% and 25% for training and testing, respectively. The models' details, the rationale behind graph construction, and hyperparameter tuning for B, K. and selected value further described in Appendix D
Performance Comparison The performance of RWSADMM is compared with FedAvg as benchmark and several state-of-the-art personalized FL algorithms such as Per-FedAvg 22), pFedMe [23], APFL 25), and Ditto (24. The test accuracy and training loss for the MNIST dataset is depicted in Fig. (Synthetic and CIFAR10 figures presented in Appendix D). Test accuracy and time cost
for all the datasets are reported in Table]] []
The test accuracy progress curves of RWSADMM for all the models 2a 2c have significantly faster convergence. For the non-convex models (2b). RWSADMM reaches convergence after 200 iterations, while the rest of the algorithms, except Ditto, work toward convergence until 600 iterations. The performance curves are shown for 100 iterations for consistency. When tested on MNIST with MLP, RWSADMM demonstrated comparable performance against pFedMe. In the test on Synthetic data with MIR models, RWSADMM exhibited a significant advantage over the other methods, with an improved margin of 14.95%. Regarding computational efficiency, RWSADMM is slower than FedAvg and Per-FedAvg, but faster than PFedMe. Furthermore, RWSADMM converges in fewer iterations (200 iterations) than PFedMe (600 iterations). RWASDMM is also run for more extensive networks with 50 and 100 nodes as a separate set of experiments. The performance comparison results and diagrams are also in Appendix D.
6 Conclusion and Future Work
This study proposes novel approach called RWSADMM, designed for systems with isolated nodes connected via wireless links to the mobile server without relying on pre-existing communication

---

1.00
Strengly convex MUR
Non-ccowex
1.00
Non-corvex
Teat A.c.Aocuuu CECUUAAA
0.85
APFL
0.00
APL
40%
0.50
Dit
0.00
Dits
RASSADMM
0.00
Data
Phadng
PerArg
Porbug
Fedlug
FedAug
Festing
prediee
presthe
profie
20
40
100
40
102
Pounce
(a) MLR acc
(b) MLP acc
(c) CNN acc
Strongly conves MUR
1.00
Non-cenvex MLP
1.00
Non-corwex CNN
ATPL
0.00
Ditia
0.00
0.80
0.40
prodie
Fedlivg
0.60
Teddug
prostM
Traasnng LoG
60
prodiee
Fuskip
0.30
0.40
0.20
0.10
0.00
20
40
100
100
Global
(d) MLR loss
(e) MLP Joss
(I) CNN loss
Figure 2: Performance comparison (test accuracy and training loss) of RWSADMM, PeeMMe. Per- Avg, FedAvg, APFL, and Ditto for MNIST dataset for the MLR (a 2d 2f models. The first 100 iterations plotted to show the convergence progress better.
MLP
26
2e and CNN
Synthetic
Frameworks
MLR
MLP
CNN
MLL
MLP
((3)
(60(3))
auc(
[s]
FedAvg
0.02
128
98.79
155
83.83-1 0.15
2655
77.62 0.11
592
80.64
0.22
680
PerAvg
94.37 0.04
0.08
2432
0.09
267
260
pFedMe
00.62 0.04
448
99.46++
0.01
649
99
0.06
5541
83.20
+ 0.06
254
86.36 + 0.15
1413
Ditto
97.37
0.02
276
78
0.03
425
199
20
3273
86
0.03
85.26
0.30
79
APFL
XASADMX Cour method)
98.63
0.01
167
99.29
0.02
295
99.52
0.04
3857
96.44 1: 0.12
473
97.17 1: 0.18
692
CIFARIO MLP
Frameworks
MLR
CNN
acc(%)
acc(%)
((s)
aco(Sk)
FedAvg
0.01
160
0.05
38.65
78
PerAvg
47-43 = 0.09
192
60:25
0.07
255
83.52
pFedMe
67.53 0.34
515
78.12
0.38
340
83.56
0.05
34801
Ditto
75.2 0.01
225
81.57
0.13
259
86
0:02
2189
APFL
RNSADNY (our method)
80.72 2: 0.11
131
84.99 1 0.20
253
87.08
0.03
3759
Table 1: Performance comparisons of FedAvg. Per-FedAvg, PFedMe, Ditto, APFL,, and RWSADMM frameworks on MNIST, Synthetic, and CIFAR10 datasets. Three models are utilized for each dataset, and each model's ss converged accuracy (%) and time consumption (seconds) are reported. Each configuration is executed for ten iterations, and variance is calculated to compute the degree of confidence for test accuracy rates.
infrastructure. The algorithm enables the server to move randomly toward a local client, establishing local proximity among adjacent clients based on hard inequality constraints, addressing the chal- lenge of data heterogeneity. Theoretical and experimental results demonstrate that RWSADMM costeronve and communication-efficin This study primarily focuses on the methodological framework for RWSADMM. Future research directions should explore essential techniques such as incorporating differential privacy techniques and examining scalability in more extensive network and dataset scenarios. Further investigation is needed to assess the implementation in physical networks and evaluate the effect of communication delays in the real world.
surpassing current state-of the-art FL frameworks.

---

7 Acknowledgement
This research was partially supported by the NSF 2122309 and NSF 2104337.
References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiin learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[2] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020,
[3] Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang. Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: comprehensive survey. IEEE Communications Surveys & Tutorials, 22(3):2031 203:)2033-2063, 2020.
[4] Syreen Banabilah, Moayad Aloqaily, Eitaa Alsayed, Nida Malik, and Yaser Jararweh. Federated learning review: Fundamentals, enabling technologies, and future applications. Information Processing & Management, 59(6):10306) 2022.
[5] David A Handelman, Corban G Rivera, Robert St Amant, Emma A Holmes, Andrew R Badger, and Bryanna Y Yeh. Adaptive human-robot teaming through integrated symbolic and subsymbolic artificial intelligence: preliminary results. In Artificial Intelligence and Machine Learning for Mulli-Domain Operations Applications IV, volume 12113, pages 145-157. SPIE, 2022.
[6] J Michael Gilmore. Warfighter information Neework-tactionn (win-t) increment 2. 2015.
[7] Fal Sadikin and Sandeep Kumar. Zighee iot intrusion detection system: hybrid approach with rule-based and machine learning anomaly detection. In loTBDS, pages 57-68, 2020.
[8] Nishat I Mowla, Nguyen H Tran, Inshil Doh, and Kijoon Chae. Federated learning- baased cognitive detection of jamming attack in flying ad-hoc network. IEEE Access, 8:4338 43500, 2019.
[9] Beibei Li, Yukun Jiang, Wenbin Sun, Weina Niu, and Peiran Wang. Fedvanet: Efficient federated learning with non-iid data for vehicular ad hoc networks. In 2021 IEEE Global Communications Conference (GLOBECOM)) pages 1 1-6. IEEE, 2021.
[10] Hideya Ochiai, Yuwei Sun, Qingzhe Jin, Nattanon Wongwiwatchai, and Hiroshi Esaki. Wireless ad hoc federated learning: A fully distributed cooperative machine learning. arXiv preprint arXiv:2205.11 11779, 2022.
[11] Xiaohan Liu, Tao Yang, and Baoping Yan. Internet of things for wildlife monitoring. In 2015 IEEE/CIC International Conference Communications in China-Wann Workshops (CIC/ICCC), pages 62-66. IEEE, 2015.
[12] Viktor Toldov, Laurent Clavier, and Nathalie Mitton. Multi-channel distributed mac protocol for wsn-based wildlife monitoring. In 2018 14th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), pages 1-8. IEEE, 2018.
[13] Bilal Arshad, Johan Barthelemy, Elliott Pilton, and Pascal Perez. Where is my deerl-wildlife tracking and counting via edge computing and deep learning. In 2020 IEEE SENSORS, pages 1-4. IEEE, 2020.
[14] Chien-Chi Kao, Yi-Shan Lin, Geng-De Wu, and Chun-Ju Huang. A comprehensive study on the internet of underwater things: applications, challenges, and channel models. Sensors, 17(7):1477, 2017.
[15] Nancy Victor, Mamoun Alazab, Sweta Bhattacharya, Sindri Magnusson, Praveen Kumar Reddy Maddikunta, Kadiyala Ramana, Thippa Reddy Gadekallu, et al. Federated learning for iout: Concepts, applications, challenges and opportunities. arXiv preprint
2022.

---

[16] Lulwa Ahmed, Kashif Ahmad, Naina Said, Basheer Qolomany, Junaid Qadir, and Ala Al-Fuqaha. Active learning based federated learning for waste and natural disaster image classification. IEEE Access, 8:208518-228 208551,, 2020.
[17] Ahmed Imteaj, Irfan Khan, Javad Khazaei, and Mohammad Hadi Amini. Fedresilience: fed- erated learning application to improve resilience of resource-constrainee critical infrastructures. Electronics, 10(16):1917, 2021.
[18] Amit Kumar Bairwa and Sandeep Joshi. Mla-rpm: A machine learning approach to enhance trust for secure routing protocol in mobile ad hoc networks, Int J Adv Sci Technol, 29(04): 1265-
1 11274, 2020.
[19] Dirk Helbing and Evangelos Pournaras. Society: Build digital democracy. Nature, 327(7576):33 34, 2015.
[20] John Gastil and Robert Richards. Embracing digital democracy; A call for building an online civic commons. PS: Political Science & Politics, 50(3):758-763 2017.
[21] Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv preprint (1xXiv:1999.1448800 2019.
[22] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostie meta-learning approach. Advances in Neural Information Processing Systems, 33:3557-3568, 2020.
[23] Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 18:21394-21405 2020.
[24] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6367-6368. PMLR, 2021.
[25] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003.13400 2020.
[26] Chaouki Ben Issaid, Anis Elgabli, Jihong Park, Mehdi Bennis, and Mérouane Debbah. Commu- nication efficient distributed learning with censored, quantized, and generalized group admm. arXiv preprint arXiv:2009.0644 09459, 2020.
[27] Anis Elgabli, Jihong Park, Sabbir Ahmed, and Mehdi Bennis. L-fgadmm: Layer-wise federated group admm for communication efficient decentralized deep learning. In 2020 IEEE Wireless Communications and Networking Conference (WCNC), pages 1-6. IEEE, 2020.
[28] Zonghao Huang, Rui Hu, Yuanxiong Guo, Eric Chan-Tin, and Yanmin Gong. Dp-admm: Admm-based distributed learning with differential privacy. IEEE Transactions on Information Forensics and Security, 15:1002-1012, 2019.
[29] Peter Graf, Jennifer Annoni, Christopher Bay, Dave Biagioni, Devon Sigler, Monte Lunacek, and Wesley Jones. Distributed reinforcement learning with admm-rl. In 2019 American Control Conference (ACC), pages 4159-4160 4166. IEEE, 2019.
[30] Zijie Zheng, Lingyang Song, Zhu Han, Geoffrey Ye Li, and H Vincent Poor. A stackelberg game approach to proactive caching in large-scale mobile edge networks. IEEE Transactions on Wireless Communications, 77(8)5518-5211 2018.
[31] Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Improving the privacy and accuracy of admm-based distributed algorithms. In International Conference on Machine Learning, pages 5795-5805. PMLR, 2018
[32] Changkyu Song, Sejong Yoon, and Vladimir Pavlovic. Fast admm algorithm for distributed optimization with adaptive penalty. Proceedings of the AAAI Conference on Artificial Intelligence, volume 30:1, 2016.

---

[33] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and TrendsS in Machine learning, 3(1):1-122, 2011.
[34] Qunwei Li, Bhavya Kailkhura, Ryan Goldhahn, Priyadip Ray. and Pramod K Varshney. Robust federated learning using admm in the presence of data falsifying byzantines. arXiv preprint arXiv:1710.05241 2017.
[35] Sheng Yue, Ju Ren, Jiang Xin, Sen Lin, and Junshan Zhang. Inexact-admm based federated meta-learning for fast and continual edge learning. In Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Compuling, pages 91-100, 2021.
[36] Minseok Ryu and Kibaek Kim. Differentially private federated learning via inexact admm. arXiv preprint (.X.::2006006//1 2021.
[37] Kang Wei, Jun Li, Ming Ding. Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454- 3469, 2020.
[38] Mingyi Hong, Davood Hajinezhad, and Ming-Min Zhao. Prox-pda: The proximal primal- dual algorithm for fast distributed nonconvex optimization and learning over networks. In International Conference on Machine Learning, pages 1529-1538. PMLR, 2017.
[39] Xianghui Mao, Kun Yuan, Yubin Hu, Yuantao Gu, Ali Sayed, and Wotao Yin. Walkman: random- maalm algorithm for decentralized optimization. IEEE
A communication-efiin Transactions on Signal Processing, 68:2513-2528, 2020.
[40] Sundhar Ram, Nedić, and Venugopal V Veeravalli. Incremental stochastic subgradient algorithms for convex optimization. SIAM Journal on Optimization, 20(2):691-717, 2009.
[41] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd international conference on artificial intelligence and statistics, pages 983-992. PMLR, 2019.
[42] Angelia Nedic, Alex Olshevsky, Asuman Ozdaglar, and John N Tsitsiklis. Distributed subgradi- ent methods and quantization effects. In 2008 47th IEEE conference on decision and control, pages 4177-4184. IEEE, 2008
[43] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 1132-5144, PMLR, 2020.
[44] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019.
[45] Yann LeCun. The mnist database of handwritten digits. htt:://ann.. lecun. com/exdb/nnist/, 1998.
[46] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009.
[47] Jia Hu, Tiande Guo, and Congying Han. Stochastic linearized generalized alternating direction method of multipliers: Expected convergence rates and large deviation properties. Mathematical Structures in Computer Science, pages 1-18, 2023.
[48] Kai Lai Chung and Paul Erdos. On the application of the borel-cantelli lemma. Transactions of the American Mathematical Sociery, 72(1):179-186, 1952.
[49] Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.


Reviews:
[{"review_id": "xP6TWOj2vE", "reviewer": "Reviewer_46UP", "summary": "This paper proposes a new FL setting that involves a dynamically moving server among clients residing in different regions and receiving updates from clients of the selected region through wireless links. The proposed algorithm RWSADMM addresses personalization and data heterogeneity by minimizing the local proximity among neighbor nodes of each client. Additionally, the authors apply a first-order subgradient expansion for computational complexity reduction, which is useful for real-world applications. The algorithm is demonstrated to converge provably faster than baseline methods through theoretical analysis and experimental comparisons.", "questions": "In the current problem, the server moves through a random walk. However, in practical situations, shouldn't the server actively modify its routing to reach unseen nodes? \n\nLooking at the Experimental setup in Section 5, there are only 20 clients. Considering the trend in recently published Federated learning works, shouldn't the proposed algorithm be compatible with scenarios involving a larger number of clients?\n\nIn Figure 2, although PerAvg and APFL are FL works geared to data heterogeneity, their performances are significantly lower compared to FedAvg. Why does this discrepancy occur?\n\nWhat are the confidence intervals for the reported performance in Figure 2 and Table 1? It is important to report confidence intervals, as performance can vary significantly  depending on how the spatial relationship between nodes is initialized.\n\nThe proposed setting (mobilized federated learning) seems somewhat unrealistic. In a war situation where long-range communication is not supported, is there a need for federated learning? Considering that neural networks are large and transmitting them via tactical vehicles would be challenging, wouldn't it be better to transmit data for distributed learning or perform centralized learning on the server, rather than transmitting model updates? ", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper introduces a novel asynchronous mobilizing federated learning setting that can be \nutilized in realistic war situations where communication infrastructure is unavailable. Additionally, \nit establishes a mathematical framework based on dynamic graph-based representation, allowing the server to move through the field and interact with various clients to update the neural network.\n\nThe proposed algorithm surpasses the baseline methods by a significant margin, demonstrating notably faster convergence rates, particularly in realistic non-IID scenarios.\n\nThe methodology employed in this study is a theoretically sound solution derived from the analysis of dynamic Markov Chain and Alternating Direction Method of Multipliers.\n\nThe proposed RWSADMM algorithm ensures convergence based on commonly assumed properties of the loss function. Furthermore, the communication complexity of RWSADMM is compared to existing methods like Per-FedAvg and APFL, providing theoretical evidence of its superior scalability.\n\nIn the proposed setting, both convex and non-convex models converge faster and exhibit higher accuracy performance compared to the baseline methods.\n", "weaknesses": "The proposed setting (mobilized federated learning) seems somewhat unrealistic. In a war situation where long-range communication is not supported, is there a need for federated learning? Considering that neural networks are large and transmitting them via tactical vehicles would be challenging, wouldn't it be better to transmit data for distributed learning or perform centralized learning on the server, rather than transmitting model updates? \n\nThe proposed Markov Chain does not seem to effectively represent the problem situation (mobilized federated learning). In real scenarios, nodes within the communication range of the communication vehicle should be selected, but the proposed algorithm does not consider the physical distances between nodes. Additionally, considering realistic situations like Figure 3, where nodes (walking soldiers) move and the topology keeps changing, the Markov Chain used in this paper cannot reflect spatial rearrangements of participating nodes.\n\nI am concerned about privacy issues. In the proposed algorithm, each node needs to receive model updates from neighboring nodes to calculate the proximity term. However, this process can expose the data that the node possesses, as it can be extracted from the updates of other nodes. Furthermore, simultaneous reception of model updates from multiple nodes can result in communication overhead.\n\nThere is a lack of ablation study on the proposed components. There is no analysis on how well the proposed local proximity term resolves data heterogeneity, and no trade-off analysis on how much computational resources are saved through first-order expansion and the corresponding impact on performance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your follow-up questions and comments. Below we address each question and minor questions in a point by point fashion.\n\nWeakness 1: Realism and Transmission burden:\n\nAnswer 1: a) Realism of the Proposed Setting:\nSince we know that traditional federated learning may not be practical in such scenarios, the motivation for mobilized federated learning is to address the challenges posed by the constrained communication environment. In a war situation, communication infrastructure may be severely compromised or even non-existent. In contrast to centralized learning, which heavily relies on a stable and high-bandwidth connection to the server, mobilized federated learning leverages local communication within tactical vehicles. By adopting our mobilized federated learning, we strike a balance between model performance and maintaining data confidentiality. The decentralized nature of data ensures the continuity of learning even in adverse conditions, providing a vital advantage in the field.\nb) Transmission/Communication Burden:\nIn the paper, we proved the improved communication complexity with other methods. Existing methods such as model compression and compiler compression can be readily combined with our method to improve the communication burden.\n\nWeakness 2: Restriction of the Markov Chain Representation:\n\nAnswer 2: We employed a Time-inhomogeneous Markov Chain in our design, which allows for dynamic changes in the Markov Transition Matrix. This dynamic property enables the model to effectively depict the physical dynamical distance between nodes and account for the nodes' changing locations over time. In Figure 3, it can be observed that the nodes' locations undergo changes. Our primary objective was to develop a straightforward yet efficient method to capture the communication dynamics in response to dynamic topology within the network for communication.\nTo achieve this, the server keeps receiving updated spatial information on the nodes via satellite communication. The random walk model we adopted operates in two iterative steps: Firstly, based on the locations of the nodes and the battle vehicle, the connectivity graph is updated. The subsequent stop for the battle vehicle is restricted to a few connected nodes that are reachable, effectively considering the constraints imposed by the vehicle's mobility and the reachability between the vehicle and nodes. Secondly, the random walk algorithm is executed to select one node from the reachable nodes. Thus, our random walk model incorporates considerations of the temporal and spatial correlation among nodes, further enhancing its performance in dynamic scenarios.\nWhile Figure 3 illustrates nodes' location changes with no drastic shifts, our model has been designed to cater to situations with more substantial topological variations. Our experiments demonstrate the model's robustness and effectiveness in practical scenarios with dynamic topologies, providing valuable insights into its applicability.\n\nWeakness 3: Privacy issues:\n\nAnswer 3: To mitigate the privacy risks associated with the exchange of model updates among nodes, we can adopt specific measures to safeguard sensitive information. By implementing existing encrypted aggregation and privacy-preserving techniques, we can significantly reduce the exposure of individual data during the update calculation process.\n \nWeakness 4: Ablation study:\n\nAnswer 4: In Section D.3 of the supplementary materials, we conducted a comprehensive hyperparameter study to assess the effectiveness of the local proximity term in addressing data heterogeneity through the parameter tuning of \\beta. We further performed a thorough computational analysis to quantify the computational resource savings achieved by incorporating the first-order approximation, along with its impact on overall performance. We direct your attention to Table 2 enclosed within the attached PDF in the rebuttal. The findings depicted in the table reveal that the proposed first-order stochastic approximation yielded superior accuracy results while incurring less time costs. This outcome is well-founded since it obviates the need to solve the local subproblem to its optimal solution in every iteration. By mitigating the high risk of overfitting to local data and its associated computational overhead, our approach facilitates a more efficient global convergence process.\n\nQ1: Modify its routing to reach unseen nodes:\n\nA1: In our design, we have indeed taken this aspect into careful consideration. The server's movement is modeled as a generalized random walk which relies on a time-nonhomogeneous Markov matrix to determine the server's transitions. This dynamic feature allows us to modify the Markov matrix temporally, enabling the server to adapt its routing strategy as the situation evolves. By leveraging the time-nonhomogeneous Markov matrix, the server can effectively navigate through the network, reaching unseen nodes or avoiding hazardous areas in battlefields or buildings after a disaster.\n\nQ2: A larger number of clients in the experiment:\n\nA2:  In the main context, the majority of experiments were conducted using 20 clients. Nonetheless, to thoroughly assess the performance of RWSADMM with optimal configurations, additional experiments were conducted with 50 and 100 nodes. The empirical results from these experiments are provided in Appendix D.6.\n \nQ3: Discrepancy in the experimental result? Standard Deviation of the reported performance?\n\nA3: We observed that the performance of APFL appears to be lower compared to FedAvg in some settings. This discrepancy can be attributed to the handling of highly heterogeneous data across participant clients during one round of updates in the APFL algorithm. The experimental outcomes presented in Table 1 and Figure 2 have been updated in the response PDF. The calculation of standard deviations involves conducting ten iterations for each framework, indicating the confidence intervals."}, {"review_id": "RtdCZ8i1vB", "reviewer": "Reviewer_J9bJ", "summary": "This paper proposes random walk stochastic method based on traditional ADMM, which enables personalized federated learning considering the mobility of clients and using a mobilized server. The authors solve the optimization of the stored client’s model parameters through Lagrangian and dual problem. The theoretical analysis proves the convergence performance of the proposed algorithm based on assumptions 4.1 to 4.5. The paper validates the performance of the algorithm by comparing its accuracy and loss with APFL/Ditto/PerAvg/FedAvg/pFedMe.", "questions": "1.On page 8, the authors claim RWSADMM’s O(\\omega^{-1}) communication complexity is better than Per-FedAvg’s O(\\omega^{-3/2}) complexity. This hold when \\omega ranges from 0 to 1, but the authors seem not to discuss or define the range of the parameter.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This paper realizes the mobilizing federated learning in a in an infrastructure-less environment for the first time.\n2.This paper has rigorously proposed the RWSADMM algorithm and rigorously proves its convergence performance.\n3.The paper solves the model update faster by solving the dual problem and achieves better communication cost.", "weaknesses": "1.The paper assume the mobilized server wanders in the region following a random walk pattern, and uses the warzone as an example. In a drastic combat, the mobilized server should usually follow a more regularized route instead of randomly wandering in the field. Also, the client are also set to be stationary in the paper, which can not represent usual moving soldiers and devices. Therefore, I think the system model is not very realistic, and the applicability of the system in a real war may be limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely value your positive review of our work and the words of encouragement you've provided. We are open and receptive to any further insights you might have to offer. We will respond to each question individually.\n\nWeakness 1: Wandering in the dynamic geometric network topology:\n\nAnswer 1: Our approach incorporates a time-inhomogeneous Markov transition matrix, allowing us to dynamically adjust and adapt the regularized route of the mobilized server based on real-time information.\nUnlike a fixed random walk pattern, our method can intelligently modify the server's movement pattern to respond to changes in the combat environment. As the situation evolves and new data becomes available, the Markov transition matrix is updated in real-time, enabling the server to adjust its route and navigation strategy.\nThis adaptability is particularly crucial in drastic combat scenarios, where the environment can change rapidly and unpredictably. By continuously updating the Markov transition matrix, our method ensures that the mobilized server remains agile and responsive to super dynamically changing conditions.\n\nWeakness 2: Stationary nodes \n\nAnswer 2: The nodes are not stationary. They update their locations periodically to the server via satellite communications. Based on the real-time locations of the nodes and the vehicle as well as the status on the battlefield, the reachability graph can be calculated. \n\nQ1: On page 8, the authors claim RWSADMM’s O(\\omega^{-1}) communication complexity is better than Per-FedAvg’s O(\\omega^{-3/2}) complexity. This holds when \\omega ranges from 0 to 1, but the authors seem not to discuss or define the range of the parameter.\n\nA1:  We can assume that \\omega represents a small (less than 1) positive parameter similar to [22][25], which can be realized by controlling gradient magnitudes through common weight regularization techniques such as L1 or L2 regularization in the models. This could prompt the model to adopt lighter weights, resulting in reduced gradients, consequently yielding a smaller value for \\omega.\n\n"}, {"review_id": "GTSHxLckPV", "reviewer": "Reviewer_cJVn", "summary": "Authors consider in this paper a Federated Learning framework with a mobile server. They propose an algorithm named Random Walk Stochastic Alternating Direction Method of Multipliers (RWSADMM) for networks with instability and limited capacity. To overcome the non-IID nature of clients' data, they ensure local proximity among adjacent clients using hard inequality constraints. Their theoretical and empirical results demonstrate the effectiveness of RWSADMM.", "questions": "Can authors elaborate more regarding employing the dynamic Markov Chain to model the server's movement?\nThe introduction of the y-variable in Eq. (7) is unclear.\nIf one of the neighboring nodes of the selected node in an iteration fails to respond, does the algorithm still work?", "limitations": "The mobility model considered in this paper is of limited applicability. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The mobile Federated Learning in infrastructure-less environment is an important problem. The paper is well organized with rigorous theoretic analysis.", "weaknesses": "The random walk mobility model is over simplified and is not a realistic model for wireless adhoc network. The random walk model was initially developed to emulate the unpredictable movement of particles in physics. It is a memoryless mobility model that does not consider temporal and spatial correlation. In addition, topology control technique is a  must to ensure reliable operation of a wireless adhoc network in reality and therefore such a memoryless assumption is hardly the case in many real life applications.   \nAlthough the concept of the Federated Learning (FL) framework with a mobile server is interesting, it seems to be a special case of asynchronous FL, where only a subset of clients is selected to participate in the update in each iteration. Authors are recommended to elaborate the difference between this work and existing asynchronous FL work in the literature. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your diligent inquiry and thoughtful comments. In the subsequent sections, we will provide a detailed response to each of your questions.\n\nWeakness 1: model is over simplified:\n\nAnswer 1: In our model, we enhance the conventional random walk by introducing a time-inhomogeneous Markov Probability Transition matrix denoted as P(k), where 'k' signifies the time index. Unlike the conventional fixed Probability Transition matrix 'P' in a standard random walk, our approach accommodates the dynamic movement patterns of nodes over time, rendering it better suited for real-world infrastructureless environments. Our proposed model functions through two iterative phases, both of which contribute to a more authentic portrayal of mobility patterns within the environment:\n\nConnectivity Graph Update: We revise the connectivity graph based on the node and battle vehicle positions. This step ensures that the potential destinations for the battle vehicle are confined to its connected nodes—those that are practically attainable or aligned with its specific route plan. This approach takes into account the limitations and constraints imposed by the mobility of the vehicle.\n\nRandom Walk Algorithm with Accessible Nodes: The model employs the generalized random walk algorithm to choose a node from the set of accessible nodes guided by the transition matrix P(k). This selection process takes into consideration the spatial correlation between the battle vehicle and the nodes, resulting in more realistic mobility patterns that closely mirror the actual movement of the network components.\n\n \nWeakness 2: Elaborate the difference between this work and existing asynchronous FL work \n\nAnswer 2: \nInfrastructureless Environment: Our RWSADMM framework is tailored to operate in scenarios where the network infrastructure is significantly inadequate, unreliable, or nonexistent. In contrast, many existing asynchronous FL methods, as pointed out in [r1][r2], assume a certain level of network infrastructure that guarantees timely model updates.This calls for certain level of network infrastructure that guarantees the timely model update. Whereas our RWSADMM framework excels precisely in situations where the network's capabilities are highly constrained, ensuring that convergence is achieved even without the need for deterministic or stochastic bounded delay constraints.\n\nConvergence in Challenging Conditions: Our method is designed to achieve convergence under conditions that are far more challenging than those typically encountered in traditional asynchronous FL. The incorporation of mobility patterns, dynamic changes in the environment, and the adaptability of our approach further distinguish our work from other asynchronous optimization strategies.\n\n[r1] Chen, Tianyi, et al. \"Vafl: a method of vertical asynchronous federated learning.\" arXiv preprint arXiv:2007.06081 (2020).\n\n[r2] Xu, Chenhao, et al. \"Asynchronous federated learning on heterogeneous devices: A survey.\" arXiv preprint arXiv:2109.04269 (2021). \n\n\nQ1: Elaborate more dynamic Markov Chain to model the server's movement? \n\nA1: In a dynamic and uncertain environment like a warzone, the server's movement cannot be assumed to always follow a fixed pattern or remain consistent over time. We employ a dynamic time-inhomogeneous Markov Chain to capture the time-varying nature of the server's movement. In this approach, the transition probabilities are allowed to change as a function of time or the current state, enabling us to model the server's mobility more realistically. The use of a non-homogeneous Markov Chain allows the server to adapt its movement pattern based on situational changes, terrain conditions, and tactical considerations.\nE.g., let us denote the state space of the Markov Chain as S = {s_1, s_2, ..., s_n}, where each state s_i represents a specific device in the warzone. The transition probability matrix at time t is denoted by P(t) = [p_ij(t)], where p_ij(t) represents the probability of transitioning from state s_i to state s_j at time t.\nConsider a simplified warzone scenario with three specific soldiers (clients): A, B, and C. Let the state space be S = {A, B, C}, representing the three clients. We initialize the transition probability matrix P(0) as follows:\nP(0) = | p_AA(0) p_AB(0) p_AC(0) |\n| p_BA(0) p_BB(0) p_BC(0) |\n| p_CA(0) p_CB(0) p_CC(0) |\nFor instance, assume that the server starting from B has received new intelligence information indicating that client A currently moves to an unsafe or unreachable area due. This new information can be factored into updating the transition probabilities for the server's next movement.\nLet's assume we have the following updated transition probability matrix P(1) after considering the tactical considerations:\nP(1) = | p_AA(1) p_AB(1) p_AC(1) |\n| p_BA(1) p_BB(1) p_BC(1) |\n| p_CA(1) p_CB(1) p_CC(1) |\nIn this case, we have modified the probabilities p_CA(1) and p_BA(1) to reflect a reduced likelihood of transitioning to location A from its current state. This reduction is a consequence of the tactical decision to avoid the route to A due to environmental concerns.\n\nQ2: The introduction of the y-variable in Eq. (7) is unclear. \n\nA2: The description of y is explained in lines 184 and 185, as y_i is stored on the server which is the local proximity of N(i) for client i. In other words, y_i is the local proximity of the local variables of agent i and its neighbors N(i). \n\nQ3: If one of the neighboring nodes of the selected node in an iteration fails to respond, does the algorithm still work?\n\nA3:If one of the neighboring nodes fails, the server can move on to proceed to aggregate model updates from the neighboring nodes that do respond successfully. Our mobilized FL framework allows for typical weighted aggregation of updates, where nodes that have communication failure can be assigned weights of 0 in the temporal aggregation process. "}]

Author rebuttal:
We extend our gratitude to the reviewers for their insightful feedback, which has provided us an opportunity to clarify and refine our work. In response to the raised concerns, we present a comprehensive overview of our approach's enhancements and differentiators, as well as clarifications on critical aspects.

Oversimplification and Realism:
We have meticulously addressed the concern of oversimplification through the incorporation of a time-inhomogeneous Markov Probability Transition matrix (P(k)). This novel feature, in contrast to conventional fixed transition matrices, effectively captures dynamic movement patterns of nodes over time. The connectivity graph update and the subsequent random walk algorithm with accessible nodes collectively contribute to a more authentic portrayal of mobility patterns in real-world infrastructureless environments.

Distinguishing Asynchronous FL Framework:
Our RWSADMM framework stands apart from existing asynchronous FL methods, as we specialize in scenarios characterized by inadequate or non-existent network infrastructure. While traditional approaches assume certain infrastructure levels, our framework thrives in very constrained and infrastructureless environments, ensuring convergence without deterministic or stochastic bounded delay constraints which are often required in the existing asynchronous distributed learning. Furthermore, our method provably excels in challenging conditions through the integration of mobility patterns and dynamic environmental adjustments.

Adapting to Changing Topologies:
To address concerns about wandering topology, our approach integrates a time-inhomogeneous Markov transition matrix. This enables real-time adaptation of the mobilized server's route based on evolving information. By intelligently modifying the server's movement, our approach ensures responsiveness to rapidly changing combat environments, effectively addressing the issue of wandering topology.

Dynamic Nodes and Communication Burden:
Contrary to the assumption of stationary nodes, our nodes update positions via satellite communications, which enables calculation of the reachability graph based on real-time locations. We have demonstrated improved communication complexity and highlight the potential integration of model compression and compiler optimization techniques to alleviate communication burden.

Quantifying Complexities and Privacy Measures:
Regarding the clarification of \omega in our communication complexity claim, we clarify that it represents a small positive parameter, akin to existing references. To address privacy concerns, our approach is readily to work with existing encrypted aggregation and privacy-preserving techniques such as differential privacy to minimize data exposure during update calculations.

Ablation Study and Experimental Results:
Our supplementary materials contain a detailed hyperparameter study and trade-off analysis, which indicate the effectiveness of the local proximity term in resolving data heterogeneity. More results that are updated regarding the confidence intervals can be seen in the rebuttal PDF.


Meta-review: The main challenge studied in the paper is to apply the methodology of Federated Learning (FL) to practical scenarios featuring isolated nodes with data heterogeneity, which can only be connected to the server through wireless links in an infrastructure-less environment. The paper proposes a mobilizing personalized FL approach, which aims to facilitate mobility and resilience. The main novelty of the proposed approach is to allow the server to make (random, but targeted) movement toward clients and formulates local proximity among their adjacent clients based on hard inequality constraints rather than requiring consensus updates or introducing bias via regularization methods. This of course integrated through an optimization method, hence introducing Random Walk Stochastic Alternating Direction Method of Multipliers (RWSADMM). 

Most of the reviewers (also myself) are in favor of accepting the paper. After discussion the paper with the reviewers, I believe that the major concerns have been resolved. I recommend the authors to carefully apply all the excellent comments from the reviewers. Specifically the comments of Reviewer CJVn. I also think that the authors should rewrite the introduction in a way that it encompasses a more general set of scenarios (not just the ones related to warzones). The main reason that I am recommending the paper for acceptance is that I believe the proposed method will apply to more general settings (e.g. settings in robotics) and the idea of make the server mobile is a novel one.
Decision: Accept (poster)