1
Optimizing Server Placement for Vertical Federated Learning in Dynamic Edge/Fog Networks
arXiv:2605.09813v1 [cs.NI] 10 May 2026
Su Wang, Mung Chiang, Fellow, IEEE, and H. Vincent Poor, Life Fellow, IEEE
Abstract—We investigate the control and optimization of vertical federated learning (VFL), a class of distributed machine learning (ML) methods in which edge/fog devices contain separate data features, in dynamic edge/fog networks. Owing to heterogeneous data features and hardware across edge/fog networks, devices’ contributions to VFL vary substantially, and, moreover, dynamic edge/fog networks can lead to the permanent exit or entry of select data features. In this setting, our proposed methodology, server controlled VFL in dynamic networks (SC-DN), first establishes the existence of a global first-order stationary point for every global round, and then leverages this result to jointly optimize ML model training and resource consumption based on four key control variables: (i) server placement, (ii) deviceto-server transmit power, (iii) local device processor frequency, and (iv) local training iterations per global round. The resulting optimization formulation contains coupled variables as well as numerous forms of logarithmic constraints which we show is a mixed-integer signomial program, an NP-hard problem, and for which we develop a general solver. Finally, via experiments on both image and multi-modal datasets, we show that our methodology demonstrates superior classification/regression performance and resource consumption savings than even greedy methodologies. Index Terms—Federated learning, Vertical Federated Learning, Server Placement, Edge/Node Failures, Dynamic Edge/Fog
I. I NTRODUCTION Federated learning (FL) [1] is classified as either standard/horizontal FL [2], [3] or vertical FL (VFL) [4], [5], based on the structure of data distributed across an edge/fog network. In standard FL, the datasets at all nodes share an identical feature space, or, in other words, all data have the same dimension. This assumption is relaxed in VFL, with data partitioned across nodes so that each node has a subset of the total data features. In literature [6], [7], such VFL systems are more precisely referred to as having partitioned the underlying feature space across an edge/fog network. Consequently, the intersection of VFL and practical edge/fog networks introduces new forms of both data and devicelevel heterogeneity, on top of variation in devices’ CPU power and device-to-server transmission power often seen in FL network optimization [8], [9], [10]. This includes variations in the quantity, quality, and modality of local data features, as well as differences in local neural network architectures and ML model training methodologies. While existing works [6], Su Wang and H. Vincent Poor are with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ, USA. Email: {hw5731, poor}@princeton.edu. Mung Chiang is with the Department of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA. Email: [email protected].
[11], [12], [13] have examined the convergence of VFL methodologies, they rely on (i) a static set of system and ML model training parameters and (ii) a stable edge/fog network, i.e., the feature space is fixed for all training iterations and device-to-server links are unchanging. This tends to be unrealistic, particularly in edge/fog networks, which are known for their wide array of system parameters and time-varying nature [14], [15], [16]. To contextualize these ideas, consider the following potential applications: Wildfire Detection Systems via wireless sensor networks [17], [18] involve distributing a network of sensors across some environment. Each sensor obtains data from a limited section of the full setting, and the network is time-varying, as, for example, heavy rains or animal disturbances can damage existing sensors and more sensors can be added over time. Our proposed methodology aims to unify the insights across sensors efficiently, optimizing both the local training at sensors as well as server placement (i.e., position of the monitoring station/equipment). • Smart Grid Management can be accomplished by distributing edge/fog devices at different points of the grid [19], [20]. For instance, smart meters at residential housing, control monitors at power distribution centers, etc. can be jointly leveraged to develop a VFL system. In such a setting, electrical surge events, which take out individual devices, are likely to be decentralized, with varying impulse intensities at different points throughout the network. Simultaneously, new residential housing or additional power plants will be connected to the grid, and thus introduce new data features. Our proposed methodology seeks to optimize the training at individual devices while simultaneously controlling the server position to ensure the most contribution to the VFL process. •
In both these example applications and the overview in Fig. 1, heterogeneity in dynamic edge/fog networks introduces several mechanisms to VFL and, thus, opportunities for optimization and control. At the device-level, for example, it may not be worthwhile to have all devices perform the same number of local training iterations, as some devices may be on higher cost hardware (i.e., previous generation equipment) or have greater compute demands (i.e., from more complex ML models) while others may have low quality features (i.e., their compute costs may not be worth it relative to network ML performance gain). Meanwhile, at the networklevel, there are two main dynamics: (i) server placement, and (ii) device entry/exit. For server placement, the position of the server may induce trade-offs between devices connected to the
2
r-th Global Round:
Data Features Lost Features
Optimization + Implementation
Network Conditions
Local ML Model
Device Entry
Optimization Computation
Initial Embedding
Local ML Training All Device Control Parameters Features Partial Embeddings SGD Variant, Physical Device Learning Rate, Characteristics CPU Limits, etc.
Synchronized Embeddings
Device Exit
Combined Embeddings
Solution of Optimization
Server’s ML model
Environment Affects Transmissions
Device Control Parameters
Partial Embedding
r FIGURE 1: Overview of our SC-DN methodology. Prior to solving the SC-DN optimization (P ) for the r-th global round, the server, denoted by the UAV S, first obtains information about the network conditions, on the left side figure. Network conditions include devices’ partial embeddings, device entries, and device exits between the r − 1-th and the r-th global round. Thereafter, the server S solves the optimization in (P r ), synchronizes network-wide partial embeddings, moves to its new location based on the solution for (P r ), and assigns local ML model training and network hyper-parameters to active devices. Then, the r-th global round begins.
network and aggregate device-to-server transmission resource use. More noticeably, in dynamic edge/fog, new devices with unique local data features may enter the network (e.g., a network operator may install 5G equipment in new locations) and, simultaneously, old devices may exit the network, for instance a smartphone may travel outside of cellular range. Consequently, there is a need to understand the properties of VFL and their interplay in dynamic edge/fog networks, and, thereafter, to control these network properties to jointly optimize both expected VFL performance as well as networkwide resource consumption. A. Outline and Summary of Contributions Structurally, we first review existing literature in Sec. II, and introduce the system model and theoretical background in Sec. III. Then, we develop our theoretical convergence results in Sec. IV, which enable our SC-DN algorithm in Sec. V. Finally, we experimentally characterize our formulation for several settings in Sec. VI and conclude in Sec. VII. The key contributions are as follows: • Formulation of SC-DN: We develop SC-DN, a VFL methodology that proposes control of local device ML model training parameters and server placement. Our proposed methodology thus enables diverse forms of heterogeneity in dynamic edge/fog networks and the joint optimization of estimated VFL performance and aggregate network resource consumption. • VFL in Dynamic Edge/Fog Networks: We theoretically investigate the convergence properties of VFL in dynamic edge/fog networks. To this end, we first characterize the performance gap of real versus ideal training, showing that the gap is non-decreasing. Nonetheless, we show that overall system convergence is still feasible via the existence of a first-order stationary point, which is, moreover, separable with respect to the global training round.
Optimization Solution of SC-DN: We demonstrate that the SC-DN problem belongs to a class of mixed-integer signomial programs, which are highly non-convex and NP-hard, as a result of coupled and negative variables as well as logarithmic constraints. Then, we develop a tractable solution based on posynomial approximations for expressions involving negative variables and leverage Padé-approximants for non-posynomial and nonmonomial logarithmic expressions. The developed optimization transformation techniques, which are versatile yet general, offer a broader range of applicability for future VFL-based problems. • Empirical Evaluation of SC-DN in Dynamic Edge/Fog Networks: We perform an in-depth evaluation of SCDN via comparisons with baselines from literature and experiments on both image and multi-modal datasets. In all cases, we show that our proposed methodology has the ability to achieve convergence in dynamic edge/fog networks with more efficient resource consumption relative to baselines. Moreover, we further perform an in-depth characterization of our proposed optimization formulation, demonstrating its heterogeneous sensitivity to different control parameters as well as synergies in server placement (for example, the server moves towards devices that perform more local training). •
II. R ELATED W ORK A. Control and Optimization of FL Common aspects of device-level heterogeneity have been quite well studied in standard FL settings [21], [22], [23], [24]. For example, [24] was one of the first works to jointly optimize resource consumption in a standard FL setting, and [25] considered device-specific objective functions. Specifically with regards to edge/fog heterogeneity, [26] integrated physical device-level components, such as device CPU limitations and
3
device-to-server communication link reliability, in optimizing the FL process, and, more recently, works such as [21], [27] considered less common forms of heterogeneity, namely unique distributions of unlabeled data and economic incentives of training, respectively. However, in the VFL setting, heterogeneity across edge/fog networks is directly embedded at the architecture and data structure levels of the ML model training process. Specifically, at the data level, devices have unique quality, quantity, and (possibly) modality of local data features in VFL, which then influence the architecture of the neural network used. Such integrated edge/fog heterogeneity leads to a problem if a device has valuable data features but obsolete hardware (and thus a simple ML model architecture), then its output is unlikely to be highly valuable. As such, we develop an optimization formulation that, through trade-off comparisons between resource consumption and expected convergence benefits, controls both device-level training iterations (and costs) and server placement, to minimize the likelihood of deviceto-server links failing. B. Dynamic Edge/Fog Networks in Standard FL Many existing works have investigated dynamic edge/fog networks in standard/horizontal FL [16], [28], [29], [30]. In standard FL, the main problem is that the underlying data distributions throughout the network become time varying, and, as such, the subsequent ML model can become biased to fit different data distributions as devices enter or exit the network. To this end, existing work has developed methodologies around modified aggregation rules. For instance, [16] enables devices to remain within the network without necessarily contributing at every global aggregation, [31] adapts the global aggregation for actively training devices based on historically stored updates from inactive devices, and other works, such as [32], leverage device-to-device communications to maintain the same device participation levels (even in dynamic edge/fog networks) for standard FL. While these methodologies have proven to be quite effective in standard FL, VFL in dynamic edge/fog networks incurs different problems, as entire features, rather than data distributions, may enter or exit the network in an arbitrary manner. As such, the problem at the intersection of dynamic edge/fog and VFL is the maintenance of overall ML model and model training quality. To this end, we seek to lessen the impact of device exits and maximize the benefit of device entries via the aforementioned control parameters, and thus benefit both VFL training convergence and aggregate network resource use. C. VFL Advancements Historically, algorithms in distributed learning sought to overcome vertically partitioned data features via a fusion model at the server [7], [33]. More recent advancements have furthered these lines of research via incorporation of better feature selection algorithms [34], [35], [36] and asynchronous networks conditions [6], [37]. While existing work seeks to overcome heterogeneous local training iterations, we actively enable devices to have such device-specific hyperparameters,
if the trade-offs from performance and resource consumption are deemed worthwhile by the proposed SC-DN methodology. Moreover, we consider dynamic edge/fog networks, in which devices and their unique data features may exit the network entirely, and show that SC-DN, by sequentially optimizing a first-order stationary point, is able to overcome highly heterogeneous edge/fog environments. III. S YSTEM M ODEL AND P RELIMINARIES In the following, we first characterize the fixed network environment in Sec. III-A, then define the dynamic network variables in Sec. III-B, and finally explain the VFL mechanics and their interplay with our network in Sec. III-C. A. Network Properties At the network level, the system runs for a total of t ∈ T iterations where T = {0, · · · , T }. These iterations are then partitioned into R global synchronization rounds with a period of τ g iterations and R = ⌊T /τ g ⌋. At the individual level, the n-th device performs τnr local training iterations, ∀r ∈ R with R = {0, · · · , R}. Here, the server, indexed as the 0-th device, also performs local ML model training. Moreover, we denote the q-th local training iteration within the τnr rounds via the superscript (r, q), for q ∈ {0, · · · , τnr − 1}. This structure enables device-level heterogeneity and control, as a device n may run τnr ≤ τ g local iterations for any global round r. Meanwhile, the underlying network itself can change based on the global aggregation round r, so that the server S manages a time-varying network N r composed of N r devices. Given a particular aggregation round r, the network X×D r dataset X r = {xi }X is vertically i=1 with dimension R segmented, such that each device n ∈ N r has a local dataset {X n , Y}. Here, X n represents the data, which has dimension RX×Dn , and Y represents the set of labels, which X×Y has dimension . Within the above expressions, we have P R r that D = n∈N r Dn , where Dr and Dn represent the total data features within the network at global round r and the data features at device n respectively, while we use Y to denote the corresponding labels. At the datum level, we use xn,i to represent the i-th datum at device n and yi for the corresponding label. Finally, we assume that network devices synchronize matching indices for data and labels, similar to existing works in VFL [6], [34], [37]. On the ML model side, each network element n ∈ N r ∪ S (r,q) has a local ML model, fn , with parameters θn ∈ RGn for some global round r and local iteration q at the n-th network element, where Gn represents the dimension of the parameters at n. Specifically for devices n ∈ N r , the output of fn is a set of local embeddings of the data (r,q) X n represented as fn (θn , X n ). Meanwhile, the server’s r (r,q) ML model, denoted by f0 with parameters θ0 ∈ RG0 , e for data X r based on the outputs predicted labels Y cr , where embeddings of all historical devices n ∈ N r r c N = ∪r̂∈{0,··· ,r} N . In this manner, the server’s prediction retains the information from devices that have exited the network in previous global rounds re ∈ R, re < r. Formally, given a datum xi , the server outputs a predicted label yei =
4
(r,0) (r,0) (r,0) f0 (θ0 ; f1 (θ1 , xi )); · · · ; fN r (θN r , xi ); fˆN r +1 ; · · · ; fˆNcr ), where fˆ denotes cached embeddings from exited devices. For future expressions, we will use Θ(r) rather than (r,0) (r,0) (r,0) (θ0 ; f1 (θ1 , xi )); · · · ; fN r (θN r , xi ); fˆN r +1 ; · · · ; fˆNcr ) to denote the sets of all embeddings and ML model parameters, e.g., yei = f0 (Θ(r) , xi ), for ease of notation. This structure enables ML model training (via back-propagation) based on devices’ embeddings rather than complete ML model parameters, which both simplifies partial gradient computation and eases the network’s communication burdens as embeddings are typically much smaller in size than ML model parameters [38]. We explain the VFL process with these properties in Sec. III-C. Strictly speaking, r (r,0) (r,0) Θ(r) = [θ0 , · · · , θ cr ], Θ(r) ∈ RG , denotes global ML N model parameters during the r-th global round.1 However, as (r,0) partial embeddings such as f1 (θ1 ) are strictly dependent on and derived from their respective ML model parameters, (r,0) in this case θ1 , we will use Θ(r) to denote both the global ML model parameters as well as the set of all embeddings, and rely on context to distinguish between the two uses. We provide a high-level overview of the processes of our proposed SC-DN methodology, specifically summarizing the changing global ML model architecture as well as the local ML model training process from the point of view of the server and an active device in Fig. 2.
Overall Global Architecture at r+1-th Round Active Devices from r-th Round
Server at r+1-th Round
Feature Splitting
Server Saved Embeddings
Device Entries at start of r+1-th Round
Neural Network Layer
We focus on three main forms of network dynamics: (i) device exit, (ii) device entry, and (iii) device-to-server link failures, with two special cases of device idleness when τnr < τ g and τnr = 0. While complete device idleness τnr = 0 can be considered a form of network exit and subsequent reentry, we assume that such devices remain connected to the network, can continue to deliver local inference as needed, and expect to contribute in future global rounds. On the other hand, if device n were to exit the network, then we expect it is permanently damaged and thus will no longer contribute anything in future global rounds. This would be the case in wildfire detection systems when a fire disrupts wireless sensors and it is permanently damaged, for example. For devices that exit, our methodology can reuse their most recent embeddings prior to exit, as the network caches a copy of all embeddings during each global synchronization round. As an example, if the n-th device exits during the rth round, this means that the network saves its most recent (r,0) output embeddings, i.e., fbn = fn (θn ), at device n, as shown in Fig. 2, and those embeddings fbn no longer have any time-variation. Correspondingly, this means that ∀r̂ > r, (r̂,q) (r,0) θn = θn . Simultaneously, to model the network effect, we assume that any device n ∈ N r may exit so that n ∈ / N r̂ , ∀r̂ > r, and that each device n has an innate failure probability modeled by a Weibull distribution, which is commonly used to describe 1 Since both global and server’s ML model parameters depend, for any r,
r r they have dimension RG and d on the set of historical P network devices rN , c r G r r R 0 , where G = n∈N respectively. r Gn and G0 = N d
Output
From r+1-th round
New Embeddings
Input Embeddings to Server
Training Process at Active Devices at r+1-th Round n-th Active Device start of r+1-th Round
Fixed at Device n
Fixed Server n-Updated Embeddings
Label Loss
Backprop on ML model at n-th device Other Active Devices Static embeddings
Discarded Backprop
Static Embeddings for r+1-th Round Saved at Device n
Exited Devices
Training Process at Server at r+1-th Round Active Devices
Fixed Embeddings
Server at r+1-th Round Label Output
Loss
Exited Devices Static Embeddings for r+1-th Round Saved at Server
B. Dynamic Network Environment
Size from r-th round
Exited Devices at start of r+1-th Round
Backprop at Server
FIGURE 2: VFL model architectures and processes in dynamic edge/fog networks under the proposed SC-DN. At the global level, most recent embeddings from exited devices are saved by the server, while device entries expand the architecture of the server’s ML model. The training process at active devices is described from the perspective of an arbitrary active device n ∈ N r+1 , which performs local training using static embeddings from other devices. Similarly, the server performs local training with fixed embeddings from network devices. These fixed embeddings at active devices and the server are updated once at the start of every global round r.
device or sensor failures in practical networks [39], [40]. The Weibull PDF is defined as: kn −1 kn kn r (1) hn (r; λw , kn ) = exp−(r/λw ) , λw λw where λw represents the scale parameter or the variability of the distribution. The expression in (1) enables us to model three types of node exits with respect to global round r: (i) decreasing rate of failures (0 < kn < 1), (ii) constant rate of failure (kn = 1), (iii) increased failure rate over time (kn > 1). Although the Weibull distribution is continuous, we use it only to generate device-specific reliability parameters. Global rounds remain discrete, and device failures are evaluated at each round via a Bernoulli trial, with a bias determined by the Weibull parameters. Thus, the Weibull model introduces heterogeneity across devices rather than continuous-time evolution across rounds. Specifically, we randomly assign devices different underlying failure characteristics, via changes in kn and static λw = 1, in our experimental evaluation (Sec. VI). cr may enter so that n ∈ N r̂ , Conversely, devices n ∈ / N ∀r̂ > r. This would be the case as networks get upgraded,
5
e.g., the growth of 5G equipment, or usage becomes more pervasive, e.g., smartphone adoption in the 2010s. We model the VFL effect by expanding both the set of embeddings and the dimension of the server’s ML model parameters. For example, assume that no device exits and that a device n̂ enters the network during the r-th global round, then, during the r+1(r+1) become hth round, the global ML modeli parameters Θ (r+1,0) (r+1,0) (r+1,0) θ0 , · · · , θN r , θn̂ and the server’s ML model (r+1,0)
θ0 becomes enlarged to accommodate n̂’s embeddings as shown in Fig. 2. On the network side, we consider the rate of entry as a Poisson process, with constant rate λp and their geographic positions within the network based on [41]. We use the notation N r to denote the set of active devices within the network at the start of global round r. In the case that a device n ∈ N r exits the network during round r, it is treated as having effectively run τnr = 0 local training iterations. Then, for the subsequent global round r + 1, it r+1 \ N r+1 . \ is treated as an exited device, i.e., n ∈ N r c Analogously, for a device n ∈ / N that enters the network during the r-th global round waits until the beginning of the r + 1-th round before becoming an active device N r+1 in the system. Finally, similar to previous work on FL aggregation point mobility [15], we treat the server as a UAV, modeling all devices n ∈ N r and server S as objects within a 3D grid. We model device-to-server links as a combination of air-to-air (A2A) and air-to-ground/ground-to-air (A2G/G2A) channels. Moreover, motivated by sample applications in Sec. I, both A2A and A2G/G2A channels are themselves mixtures of lineof-sight (LoS) and non-line-of-sight (NLoS) links, similar to [42], [43]. There is a separate line of literature, [15], [44], that considers A2A channels as strictly LoS, which can easily be obtained by adjusting the parameters below for device-toserver communications. The server’s position is denoted by ϕrS = (ϕrx,S , ϕry,S , ϕrz,S ), as its position can change based on the global aggregation round r, while each device n’s position is described by fixed ϕn = (ϕx,n , ϕy,n , ϕz,n ). We then measure their Euclidean distance by q d(ϕrS , ϕn )= (ϕrx,S− ϕx,n )2 +(ϕry,S− ϕy,n )2 +(ϕrz,S− ϕz,n )2 . (2)
For A2G/G2A channels, the probability of having an LoS link between server S and any device n ∈ N r at round r is given by [45], [46]: r,LoS,A2G Pn,S =
exp −β
1 + ψ Tx,A2G ×
Tx,A2G
h
r,A2G θn,S − ψ Tx,A2G
i −1
(3) ,
where ψ Tx,A2G and β Tx,A2G are constants depending on the r,A2G carrier frequency and the environment conditions, and θn,S is the elevation angle between nodes defined r the respective |ϕz,S −ϕz,n | r,A2G as θn,S = 180 × arcsin . The corresponding r π d(ϕ ,ϕn ) S
r,NLoS,A2G probability of a NLoS link is given by Pn,S = 1−
r,LoS,A2G Pn,S . We can thus obtain the path loss of a A2G/G2A link from node n ∈ N r to server S as follows: αPL,A2G PLr,A2G = µPL d(ϕrS , ϕn ) × n,S h i (4) r,LoS,A2G r,NLoS,A2G Pn,S × η LoS,A2G + Pn,S × η NLoS,A2G ,
where η NLoS,A2G , η LoS,A2G > 1 denotes the excessive path loss factor, αPL,A2G is the path-loss exponent, µPL = 4πf Tx /clight with f Tx for the carrier frequency and clight for the speed of light. Then the data-rate between a device n and the server S is ! Pnr /PLr,A2G n,S r,A2G , (5) Rn,S = B n,S log2 1 + σn2 where B n,S denotes the bandwidth, σn2 = N0 B n,S denotes the noise power with N0 as the noise spectral density, and Pnr as the transmit power for the r-th global round. Meanwhile, for A2A channels, we follow [42], [43], allowing for probabilistic LoS and NLoS in cluttered altitude environments in which relative altitude differences remain informative of blockage likelihood and follows from the sample use-cases in Sec. I. Accordingly, the LoS probability, path-loss, and rate expressions for A2A channels follows the same functional form as that in (3), (4), and (5), with A2G parameters replaced by A2Aspecific constants, namely ψ Tx,A2A and β Tx,A2A which then r,LoS,A2A r,NLoS,A2A r,A2A influence Pn,S and Pn,S and ultimately Rn,S . Leveraging (5), we can then compute the delay of transmission between any device n ∈ N r and the server S as d,r r , where Mn denotes the size of device n’s Tn,S = Mn /Rn,S d,r ML model. Should device n exhibit delay Tn,S > T max in its device-to-server transmission at a global round r, then the server marks the device as a link failure, meaning that, even if device n has τnr > 0, the next global round r + 1 will proceed as if device n did not perform local training. In this manner, device-to-server distance, transmission power, server placement, and ML model size all influence link failures. C. VFL Mechanics We consider a network that performs VFL using a variant of stochastic parallel block coordinate descent (PBCD) [47], [48]. In doing so, our setting considers a three-stage cyclic process: (i) active devices n ∈ N r ∪S perform local ML model training based on network embeddings and their local data, (ii) active devices n ∈ N r ∪ S, after τ g (or τnr ) local training (r,τ r −1) iterations, transmit their local embeddings fn (θn n , X n ) to the server S, and (iii) the server S synchronizes the embeddings across all active network devices, repeating this process for every r ∈ R. The network’s overall goal is to minimize the global loss: X
(r)
F (Θ
1 X )= ℓi (Θ(r) |yi ), X i=1
(6)
where ℓi is the loss function for a datum xi and label yi which we will omit for future expressions. The corresponding global gradient over all parameters Θ(r) is defined as X
∇F (Θ(r) ) =
1 X ∇ℓi (Θ(r) ). X i=1
(7)
6
In order to minimize (6), network elements n ∈ N r ∪ S compute partial gradients, defined as: X
∇n F (Θ(r) ) =
1 X ∇n ℓi (Θ(r) ), X i=1
with the corresponding stochastic version defined as: 1 X ∇n ℓi (Θ(r) ), gn (Θ(r) ) = B r
(8)
r
(r,q)
Proximal SGD: wn = (1 − ηnr µ)τn −1−q , where 0 < µ < 1 is the proximal parameter [50]. r −q τn (r,q) • SGD with momentum: wn = 1−ρ 1−ρ , where 0 < ρ < 1 is the momentum parameter [51]. At each global round r, each device n can choose a different form of SGD to run locally, possibly leading to dynamic (r,q) changes for wn across global aggregations. •
(9)
i∈X B
IV. T HEORETICAL R ESULTS
where X rB denotes the minibatch B of indexes at the r-th global round. The ∇n notation in (8) and (9) refers to taking the derivative of ℓi with respect to the parameters at the n-th index, or, in other words, the n-th component of Θ(r) . To compute partial gradients, each network element n ∈ N r ∪ S must receive embeddings, i.e., ML model outputs (r,q) of the form fn̂ (θn̂ , X n̂ ), from all other network elements r n̂ ∈ N ∪ S, n̂ ̸= n. If the latest embeddings are transmitted at every time instant t ∈ T , this adds significant overhead in terms of latency and communication burden. Moreover, owing to devices’ data processing heterogeneity, not all devices may have new embeddings to share. As such, embeddings are instead synchronized across network elements only after each global aggregation, r ∈ R. This means that, within a global aggregation round r, each device n ∈ N r only updates its own local ML model parameters while relying on the initial embeddings from other devices n̂ ∈ N r , n̂ ̸= n, received at the start of the r-th global round. Formally, we represent the q-th local training iteration for a device n within a global round r as:
To control and optimize server placement for VFL in dynamic edge/fog, we analyze the convergence of VFL systems, showing that it is possible to converge towards a global round specific first-order stationary point. To this end, we make the following assumptions common to FL literature [3], [15]:
θn(r,q+1) = θn(r,q) − ηnr wn(r,q) gn (Θ(r,q) ), n
(10)
where q ∈ {0, · · · , τ g − 1}, ηnr is the learning rate for the (r,q) refers to the n-th device within the r-th global round, wn scaling coefficient from variants of stochastic gradient descent (SGD) for the q-th iteration within the r-th global round at device n, and h i (r,0) (r,0) Θ(r,q) = θ0 , · · · , θn(r,q) , · · · , θ cr . (11) n N
(r,q) θn
(r,q) Θn
To summarize, we use gn , and to describe the stochastic gradients and model parameters resulting from dynamic edge/fog networks with device exits/entries and τnr ≤ (r,q) τ g . For comparison purposes, we also introduce gbn , θbn , and (r,q) b Θn to represent the ideal gradients and model parameters as a result of perfect network conditions (i.e., no device entries or exits - all devices are present from the start) and τnr = τ g for all network devices. (r,q) In (10), the scaling coefficient wn depends on the form of SGD used, similar to previous FL literature [6], [49]. This structure enables the combined analysis of devices with different SGD optimizers within a single VFL framework. For this work, we consider three forms of SGD. We perform an in-depth analysis of these methods and their impact on convergence conditions of Theorem 1 in Appendix C, but, for (r,q) conciseness, summarize their impact on wn below. •
(r,q)
Standard SGD: wn
= 1, ∀r, q, n.
Assumption 1 (Smoothness). The gradients for loss functions ℓ(·) are Lipschitz continuous, ∀n ∈ N r , ∀r ∈ R, and (r) (r) Θ1 , Θ2 ∈ RG : (r)
(r)
(r)
(r)
∥∇ℓ(Θ1 ) − ∇ℓ(Θ2 )∥ ≤ Lr ∥Θ1 − Θ2 ∥, (r)
(r)
(r)
(r)
∥∇n ℓ(Θ1 ) − ∇n ℓ(Θ2 )∥ ≤ Lrn ∥Θ1 − Θ2 ∥,
(12) (13)
where 0 < Lr < ∞ and 0 < Lrn < ∞. Assumption 2 (Bounded Gradients). The full and stochastic partial derivatives are bounded with constants Qmax < ∞, n for any mini-batch X B , set of model parameters Θ(r) , ∀n ∈ N r ∪ S, and ∀r ∈ R: 2 ∥∇n F (Θ(r) )∥2 ≤ (Qmax n ) ,
(14)
2 EX rB [∥gn (Θ(r) )∥2 ] ≤ (Qmax n ) .
(15)
Assumption 3 (Bounded Variance). The variances of stochastic partial derivatives relative to the full partial derivatives are bounded with constants σn ≤ ∞, ∀n ∈ N r ∪ S and ∀r ∈ R: EX rB [∥∇n F (Θ(r) ) − gn (Θ(r) )∥2 ] ≤ σn2 .
(16)
Assumption 4 (Unbiased Gradients). Given mini-batch X B , the stochastic partial derivatives are unbiased ∀n ∈ N r ∪ S and ∀r ∈ R: EX rB [gn (Θ)] = ∇n F (Θ).
(17)
The above Assumptions 1-4 can be applied for both real or ideal network settings. Next, we use Assumptions 1-4 to investigate the impact of local training iterations for both real and ideal networks in the following Lemma. Lemma 1. (Stochastic Gradients in a Global Round) Given a global aggregation round r, the expected difference between stochastic gradients at iteration q ≤ τnr versus iteration 0 can be bounded as: h i EX rB ∥gn (Θ(r,q) ) − gn (Θ(r,0) )∥2 ≤ n n (18) r r (r,max) 2 2 2 4τnr (Qmax ) + σ η L w , n n n n n for dynamic edge/fog networks and τnr ≤ τ g . Proof. See Appendix A.
■
7
To summarize, Lemma 1 bounds the change in stochastic gradients for any device based on the local training iterations τnr as well as the estimated effectiveness of each training (r,max) iteration (modeled by ηnr Lrn wn ), e.g., larger learning rates r ηn imply more change per training iteration. By leveraging Lemma 1, we can next investigate the gap between real and ideal ML model parameter induced losses in Proposition 1, where real ML model parameters refer to those produced in heterogeneous and dynamic edge/fog networks and ideal ML model parameters refer to those that result from perfect conditions. Subsequently, we develop a criteria based on gradients for convergence in Theorem 1, also enabled in part by the result of Lemma 1. Proposition 1. (Global Cumulative Gap Between Ideal and Real Parameters) Given some global aggregation round r and cr , we can bound the gap between set all historical devices N ideal and real ML model parameter induced losses by: R X
b (r,0) ) − F (Θ(r,0) ) ≤ F (Θ
cr N X 1
R X
∥∇n F (θn(r,0) )∥2
2 r=0 n=0 ! r−1 X r Lr + 1 r y r c) r (C2 N (C1 + C3 ) , + y 2 y=0
r=0
(19) h i 2 2 max max 4 2 C1 = 64τ g (τnmax Lmax (Qmax n ) (ηn wn ) n ) + σn , (20)
2
Proof. See Appendix B.
h
i 2 2 (Qmax ) + σ n n .
cr N X
∥∇n F (Θ(r,0) )∥2 n
r=0 n=0r n∈N
≤
R−1 X
cr N X
" υnr
r=0 n=0r n∈N
# (23) max 2 F (Θ(0,0) ) + 2 (Qn ) + σn2 Υrn , RN r
where υnr =
1 r,eff r (r,max) τnr,eff ηnr w(r) ηn wn n − τn 2
■
The main takeaway from Proposition Pr−1 1 is via the interplay between the (C1 + C3 ) and the y=0 terms. If any device exits the network, enters the network after r = 0, or incurs compute heterogeneity in the form of τnmax < τ g , then there will be a (C1 + C3 ) > 0 and C2 > 0, both of which rapidly PNcr r accumulate magnitude as n=0 r grows exponentially. To summarize, Proposition 1 implies that as the VFL training progresses, if some features or training iterations are lost at any point, then the ideal versus the real ML model parameters will accumulate a gap in performance as training proceeds. This makes sense, as if a device n exits the network, then it will lead to compounded differences across all subsequent global aggregation rounds per the update rule in (10) because the real gradients accumulate training results on a different dataset than that of the ideal scenario. Even though Proposition 1 shows that the ML model parameters for VFL in dynamic edge/fog networks will not converge to those of the ideal case of a static, perfect network, the real ML model parameters may still be able to converge to a local optimal point. In the following, we investigate this idea, deriving a first-order stationary point to characterize real parameter convergence and its conditions as their pertain to the variants of SGD under consideration.
,
(24)
τnr,eff = τnr prn represents the effective local training iterations A kn as a result of the survival function prn = e−(rn ) derived from (1), and rnA is the global round immediately following the entry of device n into the network. This requires that 0 < 1 − √
+1
ρ < e −1 2 e 2 and 0 < ηnr < 2τ1r µ , given an SGD with n momentum parameter ρ, and SGD update scaling a proximal 1 factor µ. Note that W−1 − 2√ represents the −1 branch e of the Lambert W function [52]. ■
Proof. See Appendix C.
(22)
−1
Υrn = (τnr,eff Lrn )2 (ηnr wn(r,max) )3 +Lr (τnr,eff ηnr wn(r,max) )2 , (25)
(21)
and C3 = 8 ((τ g − τnmax )ηnmax wnmax )
R−1 X
W
where
max max 2 C2 = 32(τnmax Lmax n ηn w n ) ,
Theorem 1. (Separable First Order Stationary Points) Assuming τnr > 0 at active devices (n ∈ N r , r ∈ R), then the sum of first order stationary points across all devices in all global aggregations r ∈ R can be bounded as follows:
Remark 1. Assuming effective local ML model training, Lipschitz-smooth coefficients, Lrn ∀n, generally decrease over time. This is because well-trained ML models tend to be smoother and less sensitive to small input changes - precisely what a smaller Lipschitz-smooth coefficient signifies [53], [54]. As a result, the gradient bound in Theorem 1 also takes ML model quality (via training progression) into account. Theorem 1 demonstrates that, under specific conditions for the learning rates, momentum and proximal SGD parameters, the system can achieve a first-order stationary point with finite error as the number of global aggregation rounds grows, i.e., as R → ∞. The scaling coefficient, υnr = (r)
(r,max)
−1
τnr,eff ηnr wn − 12 τnr,eff ηnr wn , has an additional effect of penalizing small local training iterations as τnr → 0. Furthermore, the statement and bound of Theorem 1 are separable with respect to r, which enables global round specific optimization in Sec. V. Both of these effects will subsequently be exploited via geometric programming, explained next in our proposed SC-DN optimization. V. SC-DN O PTIMIZATION In the following sections, we first develop the SC-DN optimization, which jointly manages the ML training convergence rates and overall network resource consumption in Sec. V-A, and thereafter develop our solution methodology in Sec. V-B. A summary of the SC-DN methodology is presented in Algorithm 1.
8
Algorithm 1 SC-DN Operation
Algorithm 2 Relative Importance Estimation via Exclusion
0
1: Input: Initial network N 2: for r ∈ R do 3: Devices n ∈ N r transmit local training parameters (batch size
B, ML model size Mn , Lipschitz-smooth value Lrn , device position ϕn , learning rate ηnr , and training mechanisms wrn and wnr,max ) to the server S. 4: Network computes each device’s relative importance to the VFL process via Algorithm 2. 5: Server solves the optimization formulation in (P r ) via an iterative sequence of inner-approximations, outlined in Algor rithm 3 and thereby obtaining Pnr , ϕrS , gnr , τnr , αn , ∀n. r 6: Using Pnr , ϕrS , gnr , τnr , αn , ∀n, the network engages in stochastic PBCD. 7: Update the network structure based on any device exits or entries, thus obtaining N r+1 . 8: end for
A. Optimization Formulation SC-DN aims to balance the trade-offs between improved ML model training and various network system resource consumption elements. It does so via the control of ML model training iterations as well as numerous systems parameters, such as device-to-server transmission power, local CPU clock frequency, and time-varying server position. Formally, we pose SC-DN as the following optimization problem: X X (P) : arg min ψG γnr ξnr r ,τ r ,αr ,∀r∈R,∀n∈N r Pnr ,ϕrS ,gn n n
r∈R n∈N r
| + ψR
X X
αnr Enr,Tx +ψ P
r∈R n∈N r
|
{z
(b)
X X
{z
}
Enr,P +ψ S
X
(a)
r∈R n∈N r
}
|
{z
(c)
ESr,M
r∈R
}
|
{z
(d)
subject to (0,0) ) max 2 2 r r r F (Θ +2 (Qn ) +σn Υn , n∈N r , r∈R, (27) ξn =e υn RN r M Pr n n r,A2G , if ϕz,n = 0 or ϕrz,S = 0, n∈N r , r∈R, Rn,S r,Tx En = Mn Pnr r,A2A , if ϕz,n > 0 and ϕrz,S > 0, n∈N r , r∈R, R n,S
(28) 3φ a B n n Enr,P = τnr (gnr )2 , n ∈ N r , r ∈ R, (29) 2φ bn r r r ESr,M = K H eϕs,z +K A PSr,A+K L dxy (ϕr−1 S , ϕS ), n∈N , r∈R (30) Enr,Tx ≤ T max , n ∈ N r , r ∈ R, Pnr τnr (1 − αnr ) ≤ 0, n ∈ N r , r ∈ R, αnr ∈ {0, 1}, n ∈ N r , r ∈ R, 4b vn τnr ≤ , n ∈ N r , r ∈ R, r gn 3Bvn ϕrz,S PSr,A ≥ − log 1− max +log ϕz r max 0 ≤ ϕx,S ≤ ϕx , r ∈ R, 0 ≤ ϕry,S ≤ ϕmax y , r ∈ R,
(31) (32) (33) (34) ! r−1
1−
ϕz,S
ϕmax z
, r ∈ R,
importance γ r = [γ min ]N n=0 , min and max relative importance values γ min = 1 and γ max . 2: Output: Relative importance values γ r+1 . 3: for n ∈ N r do 4: At the τnr -th local training iteration, compute the final embed(r,τ r ) ding fn (Θn n , X n ). (r,q) 5: Transmit the final embedding fn (Θn , X n ) from device n to the server S. 6: end for (r,τ r ) 7: Server S computes its final embedding f0 (Θ0 0 , X 0 ). 8: Increment the global round, r → r + 1. (r,τ r ) 9: Server S aggregates the latest embeddings fn (Θn n , X n ) from the network,r i.e., n ∪ S ∈ N r . e r = [Fenr ]N er 10: Let F n=0 , where Fn is VFL loss from the deliberate exclusion of device n. 11: for n ∈ N r do 12: From Θ(r+1,0) , zero out only the embeddings for device n, (r+1,0) e (r+1,0) i.e., fn (Θn , X n ) = 0, to obtain Θ . n (r+1) e 13: Evaluate F (Θn ), recording the resulting loss as Fenr . 14: end for e r from largest to smallest. 15: Sort the exclusion loss vector F e r to 16: Linearly scale the values from γ min to γ max based on the F obtain γ r+1 . 17: Return: relative importance values γ r+1 for the next global round.
0 ≤ ϕrz,S ≤ ϕmax z , r ∈ R,
(38)
0 ≤ Pnr ≤ P n , n ∈ N r , r ∈ R,
(39)
gnmin ≤ gnr ≤ gnmax , n ∈ N r , r ∈ R, 0 ≤ τnr ≤ τ g , n ∈ N r , r ∈ R.
(40) (41)
} (26)
αnr
1: Input: Global round r, active network N r , uniform relative r
(35) (36) (37)
Objective of (P): At a high level, the objective function in (26) balances the trade-offs between VFL convergence and aggregate network resource consumption, which is a combination of (i) device-to-server transmission energies, (ii) device data processing (i.e., for local ML model training) energies, and (iii) server movement energy. In particular, (a) models the VFL convergence via the bound for firstorder stationary points in Theorem 1 multiplied by a relative importance term, γnr . The result in Theorem 1 captures the ML model training hyperparameter heterogeneity as well as the progression of local ML model training within the Lipschitzsmooth coefficients [55], [56], [57], [58] and we abstract the relationships between data feature quality/quantity and ML architecture by introducing a relative importance factor, γnr > 1 ∀n ∈ N r , r ∈ R to ensure that the upper bound for the first-order stationary point is maintained. To estimate γ r , we develop Algorithm 2, which re-assesses devices’ impact to overall performance of VFL via iteratively testing exclusion of output embeddings prior to the start of each global round. On the other hand, the network resource consumption terms are subdivided into three main categories: (i) device-to-server transmission energies in (b), (ii) device data processing (i.e., for local ML model training) energies in (c), and (iii) server movement energies in (d). We model whether or not a device n transmits to the server S with a variable αnr = {0, 1}, where αnr = 1 if n transmits to the server and αnr = 0
9
otherwise. Using this indicator variable, the device-to-server transmission energy term in (b) controls device transmission power Pnr and the server position ϕrS , as high device-to-server transmission energy at device n can be mitigated if the server S is in close physical proximity to device n. Similarly, the device data processing energy term in (c) influences the CPU clock frequency setting gnr and the number of local training iterations τnr , and the server movement energy in term (d) minimizes the change in server position. We can shift the optimization’s emphasis on terms (a), (b), (c), and (d) in (26) by adjusting the scaling coefficients ψ G , ψ R , ψ P , and ψ S ≥ 0. In the extreme case, ψ R = ψ P = ψ S = 0 means the network operation has no direct resource consumption considerations. Constraints of (P): The first four expressions, (27)-(30), are definitions to model the ML model training and convergence, the device-to-server transmission energies, devices’ data processing energies, and the server movement energies, respectively. The expression in (27) slightly modifies the upper bound from Theorem 1 with an additive constant ϵG > 0 within the denominator of υnr to obtain υ enr . We do so for computational G reasons as a small ϵ > 0 helps (P) obtain convergence when τnr ≈ 0. For the remaining terms, (28) follows directly from the previously explained expression in (5), while the other expressions, (29) and (30), require further explanation. The data processing energy (29) is characterized by the devices’ CPU clock frequency gnr , batch size B, effective capacitance coefficient an of its chipset [59], total number of connections φn in the n-th device’s ML model, and FLOPs per CPU cycle φ bn . Based on methods from [60], [61], we approximate the total FLOPs of compute required for local ML training as 3τnr Bφn , from which we subsequently divide φ bn to obtain the effective CPU cycles needed for training. Thereafter, we leverage the formulas for data processing energy from [59] to obtain the expression in (29). Meanwhile, as we model the server to be a UAV with three dimensional movement capabilities, the corresponding server movement energy use in (30) is the composition of three types of movement: (i) hovering, (ii) altitude change, and (iii) lateral movement. The r hovering energy is modeled as K H eϕz,S , with the various coefficients all abstracted into K H , and the energy and altitude ϕrz,S relationship as e [62], [63]. Similarly, the altitude climbing energy grows non-linearly with altitude [64], [62], which we model via an abstracted coefficient K A and Pnr described later in (35). Finally, we model the lateral movement similar to previous works [15], [65], [66] by multiplying the change in r xy-distance dxy (ϕr−1 S , ϕS ) between different global rounds L with a constant K . Next, we use (31)-(35) to model the physical relationships within SC-DN. We ensure that devices with non-zero τnr , which we model via a binary variable αnr = 1, adhere to the network’s maximum device-to-server transmission delay in (31). On the other hand, devices with τnr = 0 are assumed to incur no device-to-server transmissions via the αnr Enr,Tx term in the objective function (26) and no local ML model training, which (32) ensures as (33) restricts αnr to either 0 or 1. For feasible local data processing, we introduce (34) to ensure that the increase in compute power demanded by larger τnr can be handled by increases in the CPU frequency gnr . The last
Algorithm 3 Optimization solver for problem (P r ) 1: Input: Convergence criterion. 2: Output: x⋆ , objective of (P r ) evaluated at x⋆ 3: Set the iteration count b = 0. 4: Choose a feasible point [x]0 . 5: Obtain the monomial approximations (42), (43), (44), (48), (49),
(50), (51), (52) given [x]b . 6: Replace the results in the approximation of Problem (P r ) (see ′ (P r ) in Appendix D-B). 7: With logarithmic change of variables, transform the resulting GP problem to a convex problem. 8: b = b + 1 9: Obtain the solution of the convex problem using current art solvers (e.g., CVXPY [67]) to determine [x]b . 10: if two consecutive solutions [x]b−1 and [x]b do not meet the specified convergence criterion then 11: Go to line 5 and redo the steps using [x]b . 12: else 13: Set the solution of the iterations as [x]⋆ = [x]b . 14: end if
constraint (35) models the altitude power use by the server, which increases non-linearly as the altitude increases [62], [64], and, when altitude decreases, has the added effect of allowing Pnr = 0 (as the server can decrease altitude without energy/power expenditure). For the last set of constraints in (36)-(41), we define the upper and lower limits for the optimization variables, thus limiting the system to a feasible range. Specifically, (36)(38) limit the server’s travel zone, while (39)-(41) model the devices’ feasible ranges for device-to-server transmission power, local CPU clock frequency, and local training iterations per global round, respectively. Separability of (P): Solving the formulation for (P) requires knowing the full state of the network for all r ∈ R, which, in dynamic edge/fog networks with unpredictable device exits and entries, may not be feasible. As such, we propose solving (P) on a per global round basis via the modified formulation (P r ), as follows: X (P r ) : arg min ψG γnr ξnr r ,τ r ,αr ,∀n∈N r Pnr ,ϕrS ,gn n n
n∈N r
| + ψR
X
αnr Enr,Tx +ψ P
n∈N r
|
{z
(b)
}
subject to (27) − (41).
X
{z
(a)
}
Enr,P +ψ S ESr,M | {z } n∈N r (d) | {z }
(45)
(c)
(46)
B. Solution Methodology In (P r ) and by extension (P), the optimization variables are coupled together, for instance the choice of local training iterations τnr influences the CPU clock frequency gnr . These variable couplings manifest themselves through the multiplication of optimization variables, as in the expression for data 2 processing energy in (29) which contains τnr (gnr ) . While multiplied variables can be addressed via leveraging standard geometric programming techniques [68], the proposed SCDN formulation has variable combinations that involve (i) optimization variables in the numerator and denominator of
10
h i τ r,eff Ãrn xb−1 r 1 (r,max) n r r,eff r (r) G b̃ Ãn (x) = τn ηn wn − wn + ϵ ≥ An (x; b) ≜ h i r,eff b−1 2 τn
r
L̃ (x) = χ
r,L
+2
X
r
r−1 r b̃ (x; b) ≜ ϕS,j ϕS,j ≥ L
j∈{x,y}
χr,L L̃r ([x]b−1 ) [χr,L ]b−1
Definition 1. A monomial is defined as a function2 f : β Rj++ → R of the form f (ζ) = kζ1β1 · · · ζj j , where k > 0, ζ = [ζ1 , · · · , ζj ], and βo ∈ R, ∀o ∈ [1, · · · , j]. A posynomial h is defined as a sum of monomials, having form h(ζ) = PM βjm β1m m k ζ · · · ζ , k m > 0 and βo ∈ R, ∀m. j m=1 m 1 An augmented discussion of GP is provided in Appendix D-A, but the key point is that solving a GP requires a posynomial objective function subject to posynomial inequality and monomial equality constraints to enable a logarithmic change of variables and thus solution via modern solvers.3 The proposed optimization in (P r ) violates GP rules by having non-posynomial objective function terms in (45) and nonposynomial inequality constraints in (32) and (35). Specifically, (45)(a) contains a posynomial denominator within υ enr , (45)(b) divides by a logarithm which is neither a posynomial nor a monomial (and negative variables within the denominator of the logarithm), and (45)(d) contains negative r variables within dxy (ϕr−1 S , ϕS ). Meanwhile, on the constraint side, (32) contains a negative variable and (35) consists of (negative) logarithms with negative variables therein. 2 Rj ++ denotes the strictly positive quadrant of a j-dimensional Euclidean
space. r 3 That being said, the pure exponential function eϕz,S in (30) is neither a monomial nor a posynomial, but modern solvers with disciplined GP functionality [69] can approximate it with appropriate form under the hood.
L̃r ([x]b−1 )
h i r,T b−1 χn r X̃n ([x]b−1 )
h i r ϵGb−1 r b−1 Ãn ([x ]) Ãn x
r−1
! [χr,L ]b−1
r,T r b−1 ) r r,T r r b̃ r (x; b) ≜ χn X̃n ([x] X̃n (x) = χn + τn αn ≥ X h i n r,T b−1 χn
logarithms such as the transmission energy term of (28), (ii) negative variables embedded within the device-to-server distance expression of d(ϕrS , ϕn ) from (27), and (iii) negative variables within logarithms which appear in constraint (35). As a result of these complex relationships among optimization variables, (P r ) instead belongs to the class of mixed-integer signomial programs, which have been proven to be NP-hard and highly non-convex [68]. To solve (P r ) tractably, we develop a set of modifications and approximations for violating terms in the objective function (45) and the constraints (27)-(41). These approximations convert (P r ) from a mixed-integer signomial program into a geometric programming problem, which, after undergoing a logarithmic change of variables, can then be solved as a convex programming problem in modern optimization libraries such as CVXPY [67], [69]. Thus to fully explain our solution methodology, we must first explain geometric programming programming (GP), which requires defining monomials and posynomials.
h i r,eff b−1 r w(r) − 1 w(r,max) τn ηn n 2 n r b−1 Ãn ([x ])
Y
ϕrS,j L̃r ([x]b−1 )
j∈{x,y}
[ϕrS,j ]b−1
r
r r r τn αn X̃n ([x]b−1 )
r
(42)
b−1
! 2ϕS,j [ϕS,j ]
L̃r ([x]b−1 )
(43)
r b−1
! [τn αn ]
r ([x]b−1 ) X̃n
(44)
r αr ]b−1 [τn n
The main issue of the non-logarithmic violating terms is the presence of negative variables and/or divisions by posynomials. To overcome these challenges, we use the method of penalty functions and auxiliary optimization variables [70] to approximate (i) the negative optimization variables and (ii) posynomial divisors. This method replaces the violating terms within the objective function by auxiliary variables and introduces corresponding posynomial inequality constraints. Moreover, the conversion method for posynomial divisors is encapsulated within that for negative variables, as we will now show. For terms with negative variables, we bound them using a unique auxiliary variable, obtaining the general form: a(x) − b(x) < χ, where a(x) represents the positive variables, b(x) captures the negative variables, and χ > 0 is the auxiliary variable. Rearranging this expression yields a(x) b(x)+χ ≤ 1, which contains a posynomial divisor and is, thus, not yet a posynomial inequality constraint. We proceed by approximating the posynomial denominator with a monomial, which transforms the expression into a posynomial inequality constraint (as the division of a posynomial by a monomial is a posynomial). To do so, we leverage the arithmetic-geometric mean (AM-GM) inequality: Lemma 2. (AM-GMPInequality [71]) Consider a posynomial M function h(ζ) = m=1 um (ζ), where each um (ζ) is a monomial, ∀m. The following inequality holds: γm (ζb) u (ζ) m h(ζ) ≥ b h(ζ) ≜ , γm ζb m=1 M Y
(53)
where γm ζb = um ζb /h ζb , and ζb > 0 is a fixed point. The AM-GM inequality yields an initial, monomial bound that achieves near equality with its original posynomial, after iterative refinement. We leverage this method for the venr r term in (45)(a), the dxy (ϕr−1 S , ϕS ) term in (45)(d), and the r (1 − αn ) term in (32) to obtain their resulting approximations in (42), (43), and (44), respectively. On the other hand, both (45)(b) and (35) contain logarithmic terms, which are neither monomials nor posynomials, and, as such, we must first transform the logarithm expressions. For (45)(b), we leverage a [2/1]-Padé approximant [72] to first transform the logarithm in the denominator, obtaining (47). Subsequently, we develop a monomial bound on the negative variables within the distance terms d(ϕrS , ϕn ), yielding (48),
11
r,Tx
En
r 2Mn log(2)σ 2 η eff,A2G Gr,A2G 3σ 2 η eff,A2G Gr,A2G n,S n,S + 2Pn
r b−1 χr,D ) n,S D̃n,S ([x]
r b̃ ϕS,j ϕn,j ≥ D n,S (x; b) ≜
r
6σ
2
η
LoS,A2G
r,LoS
χn
+η
NLoS,A2G
!
r,D b−1 [χ ] n,S D̃ r ([x]b−1 ) n,S
b−1 [χr,D n,S ]
j∈{x,y,z}
T̃n,S (x) = B n,S
(47)
b̃ r (x; ℓ) T n,S
r
X
r r,D D̃n,S (x) = χn,S + 2
≈
r,NLoS
χn
PL
µ
r
Y
r ϕrS,j D̃n,S ([x]b−1 )
j∈{x,y,z}
[ϕrS,j ]b−1
b−1
! 2ϕn,j [ϕS,j ]
D̃ r ([x]b−1 ) n,S
.
(48)
αPL,A2G PL,A2G /2 r,D α r χn,S + Pn ≥
" # αPL,A2G PL,A2G /2 ℓ−1 r,LoS r,D α 6B n,S σ 2 η LoS,A2G µPL χn χ n,S
αPL,A2G /2 r χr,LoS χr,D T̃n,S ([x]ℓ−1 ) n n,S b̃ T n,S (x; ℓ) ≜ PL,A2G /2 ℓ−1 r,D α χr,LoS χ n n,S
T̃ r ([x]ℓ−1 ) n,S
r
(49)
αPL,A2G PL,A2G /2 r,NLoS r,D α 6B n,S σ 2 η NLoS,A2G µPL χn χ n,S "
r,+
(x) = χ
r,A
M
r,A
+ ϵ + 1 + PS
b̃ ≥E
r,+
(x; b) ≜
r ℓ−1
T̃ r ([x]ℓ−1 ) n,S
αPL,A2G /2 r χr,NLoS χr,D T̃n,S ([x]ℓ−1 ) n,S n PL,A2G /2 ℓ−1 r,NLoS r,D α χn χn,S
Ẽ
#ℓ−1
r Pnr T̃n,S ([x]ℓ−1 )
! B n,S [Pn ]
T̃ r ([x]ℓ−1 ) n,S
[Pnr ]ℓ−1
r,+ χr,A ẼS ([x]b−1 )
!
.
h i r,A b−1 PS r,+ (1+ϵM ) ([x]b−1 ) Ẽ r,A r,+ b−1 r,+ ) S b−1 ) PS ẼS ([x] r,+ b−1 ẼS ([x] ) ẼS ([x] h ib−1 r,A
[χr,A ]b−1 r,+ ([x]b−1 ) Ẽ S
[χr,A ]b−1
PS
(50)
Ẽ
r,−
r,E
(x) = χ b
+ϵ
M
b̃ ≥E
r,−
(x; b) ≜
M ! [χbr,E ]b−1 r,− r,− ϵ b−1 r,− χ br,E ẼS ([x]b−1 ) ẼS ([x]b−1 ) r,− b−1 Ẽ ([x] ) S Ẽ ([x] ) S r,E b−1
[b χ
h ib−1 max χ b r,E
r
r,E
Õ (x) = χ b
max r−1 b̃ ϕz + ϕz,S ≥ O
r
(x; b) ≜
(51)
]
χ br,E Õ r ([x]b−1 ) [b χr,E ]b−1
after which we obtain a secondary monomial bound for the resulting posynomial within the denominator of (47) in (49). The difference of logarithms constraint in (35) requires a different strategy as a result of negative variables both inside and outside of the logarithm. At a high level, our methodology for (35) is a four step process involving (i) a rearrangement of (35) via log(x) − log(y) = log xy and exponentiation of both sides, (ii) the introduction of an auxiliary variable and equality constraint for the resulting exponential function (as exponential functions are neither monomial nor posynomials), (iii) conversion of the equality constraint into a pair of inequality constraints, and (iv) AM-GM inequality based monomial bounds for the non-posynomial denominators, which we summarize in (50)-(52). As the full derivations for the above methodology are quite lengthy, we only provide a high-level overview of our solution methodology for SC-DN above and leave their details to Appendix D-B. Our optimization solver, summarized in Algorithm 3, iteratively refines the approximations in (42)-(52), starting with an initial value for the solution [x]0 which is an initial estimate of all of the optimization variables (i.e., ϕrS , Pnr , gnr , τnr , αnr ∀n ∈ N r ). For accessibility, we only show the expressions for A2G paths in (42) and (49). Additional approximation terms for A2A paths as a result of (3)-(5) are left to Appendix D-C. The only requirement is that the initial estimate [x]0 contains feasible values for (P r ) - our solver will then iteratively converge to the optimal. Specifically, for the b-th optimization iteration, our solver obtains a solution [x]b by transforming the problem in (P r ) into a solvable convex program, which
! ϕz
Õ r ([x]b−1 )
r
Õ ([x]
b−1
)
r−1 ϕ z,S Õ r ([x]b−1 ) ,
(52)
is achieved by transforming the objective function and constraints into convex terms around the previous estimate [x]b−1 . Our method of posynomial condensation for monomial approximation depends on normalized variable ratios, a sample of which is shown in (48)-(52). While larger networks increase the problem width/size, they do not introduce additional curvature or conditioning effects [73], [68], i.e., the posynomial approximation process remains intact, and therefore larger network size does not meaningfully affect convergence speed, which we will verify experimentally in Sec. VI. VI. N UMERICAL E VALUATION In this section, we evaluate the performance of the proposed SC-DN methodology, first presenting the experimental setup in Sec. VI-A. Then, we characterize the proposed optimization formulation in Sec. VI-B, showing (i) monotonically stable convergence, (ii) interplay among machine learning (ML) model training, server position, and max transmit time, and (iii) heterogeneous scaling variable impacts on (P r ). Finally, we evaluate the overall SC-DN methodology on VFL performance for both static and dynamic edge/fog in Sec. VI-C. A. Experimental Setup Unless stated otherwise, all experiments are the averaged result of ten independent runs performed using scaling coefficients ψ G = 1e−3, ψ P = 1e−9, ψ R = 1e3, ψ S = 1e−4, and auxiliary variable penalty coefficients (explained in Appendix D-B) of ψb = 1e−4. Additional systems parameters
12
101 0 5 10 15 20 25 30
Approximation Iteration
10 7 10 9
0 5 10 15 20 25 30
to model the device-to-server data rates in (28) are chosen similar to prior work [15], [45], [46]: N0 = −174dBm/Hz, αPL,A2G = 2, αPL,A2A = 2.2, ψ Tx,A2G = 11.95, β Tx,A2G = 0.14, ψ Tx,A2A = 10.5, β Tx,A2A = 0.12, η LoS,A2G = 3dB, η NLoS,A2G = 23dB, η LoS,A2A = 3dB, η NLoS,A2A = 17dB, f Tx = 2GHz, and B n,S = 2MHz. We set the transmit power of the devices in the range [23, 25]dBm, and the server’s position limits are set to be a 3D-cube such that = 100. = ϕmax ϕmax = ϕmax z x y Meanwhile, our VFL experiments are performed on three datasets: (i) MNIST [74] - greyscale image recognition, (ii) CIFAR10 [38] - RGB object classification, and (iii) Pawpularity [75] - a multi-modal regression dataset consisting of image and tabular data, to model the likelihood of pet adoption. Moreover, we use an 80/20 train-test split for the Pawpularity dataset, as an open testing dataset is not available. Subsequently, we partition the dataset based on random feature splitting across the network devices, and, as a result, devices have unique local ML model architectures (i.e., unique layer dimensions) with uniform output dimension. For the VFL training setup, we set the global synchronization period to be τ g = 5 with thirty total synchronization rounds (i.e., R = 30). The estimated gradient variables in (45)(a) differ based on the dataset, each of which employs different ML model architectures. As such, we use ψ G = 1e−2, ψ G = 1e−3, and ψ G = 1e−2 for MNIST, CIFAR10, and Pawpularity, respectively. Additionally, different ML model architectures result in different empirical Lipschitz-smooth coefficients. To estimate each coefficient, we compute the spectral norms of the model’s weight matrices, multiply them together, square the result, and scale by a loss-function-dependent constant (bounded by 1 for both mean squared error and cross-entropy). This procedure follows from standard results in convex optimization and deep learning theory [55], [56], [57], [58]. For SC-DN specifically, it is applied at the start of each global round, after the server receives the latest model parameters from active devices, so that smoothness coefficients naturally track training progression, and, moreover, evaluate the overhead induced by the smoothness parameters estimation process in Appendix E-D. Moreover, to assess the overhead costs of the proposed SC-DN methodology, we additionally evaluate the runtimes for Algorithm 2 and 3 in Appendix E-C2.
0.4
5
10 1
4
10 3
3
10 5
2
0.2
10 7
1
0.0
10 9
0
Max Tx Time - T max (s)
Approximation Iteration
r FIGURE 3: Convergence of (P ) for various network sizes. The server’s initial position is varied between central positioning in Fig. 3a) and a random position in Fig. 3b). In both cases, the objective function (45) decreases monotonically as a result of Algorithm 3.
0.6
10 5
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
100
0.8
10 3
b) Average Tx Power vs T max Avg Local Iterations ( nr )
102
1.0
Max Tx Time - T max (s)
r
FIGURE 4: Feasibility of (P ) with respect to max transmit time max
T , when the server’s initial position is in the center of the network. We evaluate the impact of varying T max with respect to max transmit time and device selection status in Fig. 4a), and average device-toserver transmission power and average local training iterations in Fig. 4b).
50 40 30
a) Server XY Positions Final Server Start 50 T max = 5e 6 Final 40 max
b) Server YZ Positions Server Start
10 2
Final
10 3
Device #1 T = 5e 7 30 Final T max = 5e 2
20 10 Device #2 30
20 10 0
40
X Position (m)
50
T max = 5e 6 Final Device #1 T max = 5e 2
Final
T max = 5e 7
Device #2 10
20
30
40
Y Position (m)
50
T max (s)
103
Device #2
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
10 1
Local Tx Time (s)
104
a) Local Tx Time vs T max
Device Selection Status ( nr ) Average Tx Power (W)
a) Center
Device #1
N=6 N = 10 b) Random
Z Position (m)
N=4
Y Position (m)
Objective Function Value
N=2 N=8
10 4 10 5 10 6
FIGURE 5: Device and server positions corresponding to the same experiment in Fig. 4. For both the devices and the server, Fig. 5a) shows their XY positions while Fig. 5b) depicts the YZ positions.
For the device-level ML models, we use two layer multilayer perceptrons (MLP)s with hidden dimension of 64 for MNIST, modified AlexNet [76] classifiers for CIFAR10 such that the three linear layers have 1024, 512, and 10 output neurons respectively, and two layer convolutional neural networks (CNN)s, with 16 and 32 maps and kernel size of 5, as well as two layer MLPs with hidden dimension of 64 for Pawpularity (devices with the image modalities use CNNs while devices with tabular modalities use MLPs). Since feature splitting across devices does not necessitate unique MLP architectures, our MNIST experiments will have identical ML model architectures across devices. By contrast, experiments involving CNNs (i.e., CIFAR10 and Pawpularity) will contain devices with unique ML model architectures based on their data features, as the number of data features influences the dimensions of the convolutional layers’ outputs to the linear layers. Moreover, as a result of feature splitting, CIFAR10 and Pawpularity experiments have zero padding to 64 × 64 and 28 × 28 per image channel only when the input images have insufficient unpadded dimensions for the convolutional layers. Finally, we want to emphasize that the above feature splitting makes the classification problems very difficult, and, as such, we evaluate their performance via top-3 accuracy [77]. As each dataset requires different ML architectures so that the size of ML model parameters Mn varies based on dataset,
13
0.6
10 5
5
10 1
4
10 3
3
10 5
2
0.2
10 7
1
0.0
10 9
0
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
10 9
0.4
b) Average Tx Power vs T max Avg Local Iterations ( nr )
0.8
10 3
10 7
1.0
Max Tx Time - T max (s)
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
10 1
Device #2
Device Selection Status ( nr ) Average Tx Power (W)
Device #1
a) Local Tx Time vs T max Local Tx Time (s)
we adjust the T max parameter to obtain reasonable deviceto-server transmit times, using T max = 1e−3 for MNIST, T max = 1e3 for CIFAR10, and T max = 1e2 for Pawpularity. Similarly, we have dataset specific learning rates, ηnr = 1e−1 for MNIST, ηnr = 1e−3 for CIFAR10, and ηnr = 1e−3 or ηnr = 1e−2 for devices with images or tabular data from Pawpularity respectively; these learning rates also decrease by half every 5 global synchronization rounds. Conversely, for the server-level ML model, we use the same two layer MLP, with cr Ỹ , hidden layer dimension 64, and output input dimension N dimension Ỹ , where Ỹ is the number of unique labels (10 for MNIST and CIFAR10 and 1 for regression/Pawpularity), since the main purpose of this ML model is fusion of devices’ partial embeddings.
Max Tx Time - T max (s)
r
FIGURE 6: Feasibility of (P ) with respect to max transmit time max
T , with random initial server position. Otherwise, experimental setup investigates identical properties as that of Fig. 4, with similar takeaways.
B. Optimization Characterization 1) General Convergence: We first confirm the convergence of Algorithm 3 for networks of various sizes in Fig. 3. For the various networks, our iterative methodology for (P r ), summarized in Algorithm 3, displays monotonic convergence to the optimal point, reaching it after approximately 15 iterations, and maintains stability thereafter. Secondly, from Fig. 3, we can see that larger networks demonstrate larger objective function values, even at convergence, as a result of the additional device-to-server transmissions even at the optimal state. That being said, the fact that the objective function values are approximately equivalent until roughly the 10-th iteration of Algorithm 3 suggests that the initial iterations are primarily focused on minimizing the approximation error, with the final few rounds serving to fine-tune the optimization variables to their optimal values. Moreover, regardless of the server’s initial position - center and random in Fig. 3a) and 3b), respectively - our methodology for (P r ) is able to yield monotonic convergence to the optimal point. We further investigate these different server starting positions within Appendix E. In particular, we show that these conclusions hold for origin, maximum, and random edge server initial positions, and further verify convergence via studying the standard deviations of these results. We next examine the behavior of (P r ) when feasibility is restricted via adjusting T max . 2) Response to Transmission Time Limits: In Fig. 4 and Fig. 5, we examine the impact of maximum device-to-server transmit time T max on the SC-DN formulation as a whole. Since these experiments are expository in nature, we show single experiments which better highlight the on/off device selection status αnr and changes in server position, instead of the standard averaged results over 10 independent runs, which obfuscates this information. At the surface level, as the time T max gets smaller, individual devices would be expected to increase their transmission power to ensure compliance with (31), which is confirmed in Fig. 4a) and Fig. 4b) up to T max = 5e−5. However, when T max decreases beyond 1e−6, SC-DN turns device 2 in Fig. 4 off, setting α1r = 0 in Fig. 4a) and ensuring that τ1r = 0 in Fig. 4b). Even further decreases to T max result in both devices turning off and no training occurring (i.e., αnr = 0 and τnr = 0 ∀n) in Fig. 4a)
and Fig. 4b) respectively, as adherence to (31) can no longer be maintained with non-zero αnr . The server placement, visualized as a function of T max , adheres to these above changes in Fig. 5. While both devices are active and training τnr > 0 and T max ≤ 5e−5, the server’s final position - both XY-dimensions in Fig. 5a) as well as YZ-dimensions in Fig. 5b) - is at the midpoint between that of both devices. Then, when T max = 5e−6, only device 1 is active, and the reasoning being that, even with Pnr = P max , the resulting right hand side of (31) may still be larger than T max unless the server is right beside the device. In Fig. 5, the server chooses to be physically close to device 1, which appears to have the best benefit to the network overall. Finally, when T max is infeasibly small at 5e−7, all devices are turned off. In response, the server maintains its xy-position per Fig. 5b) but lets its z-position drop to 0 in Fig. 5b) to eliminate hovering energy use and thus minimize overall resource consumption. These takeaways are further reinforced by Fig. 6 and 7, in which the initial position of the server is randomly determined. In fact, aside from the fact that local transmit times and effective device-to-server transmit power in Fig. 6 are nominally different than in the central initial server placement case of Fig. 4, the server selections are identical, with device 2 becoming inactive after T max ≤ 5e−6. The behavior of the server position with respect to T max remains similar, as well, with the server moving closer to the active device 1 when T max = 5e−6 before eventually dropping altitude to 0 for T max = 5e−7 to save on hovering altitude energy costs when both devices become inactive. Finally, we note that these patterns of behavior remain consistent across a wider variety of initial server positions, including origin, max, and random network edge starting positions, all of which are further discussed in Appendix E. 3) Scaling Variable Characteristics: Finally, we examine the characteristic curves of the different scaling variables, ψ G , ψ R , ψ P , and ψ S , for static networks of varying sizes in Fig. 8. The first two figures, Fig. 8a) and Fig. 8b), primarily focus on how the scaling of ψ G and ψ P influences the ML convergence aspects of (P r ), while the last two figures, Fig. 8c) and Fig. 8d), investigate the sensitivity of device-toserver transmission and server movement energies to changes
14
= 5e 6 Device #1
Final
T max = 5e 2 30 maxFinal T = 5e 7 20 10 10
20
Device #2 30
40
X Position (m)
40
3 Device #1 10
30
Final
20
T max = 5e 2
10
Final
0 50
10 2
0
T max (s)
40 Server Start
T
b) Server YZ Positions Server Start
50
Z Position (m)
Y Position (m)
50
a) Server XY Positions Final max
10 4 10 5
T max = 5e 7 10 6 Device #2 10 20 30 40 50 Y Position (m)
FIGURE 7: Experiment corresponds to that in Fig. 6, with the server’s initial position randomly determined. Aside from differing XY positions, the behaviors are similar to those shown in Fig. 5.
in ψ R and ψ S , respectively. For these figures, R = 1 and the server’s initial position is central, i.e., (ϕ0x,S , ϕ0y,S , ϕ0z,S ) = (50, 50, 50). Both Fig. 8a) and Fig. the change in average P 8b) examine τr training iterations, i.e., n∈N r Nnr , and normalized estimated gradient from Theorem 1 with respect to increasing ψ G scaling. In this regard, both characteristic curves confirm intuition, as larger ψ G in Fig. 8a) emphasizes smaller estimated gradients in (P r ) and therefore more training iterations via averaged τnr . Conversely, in Fig. 8b), larger ψ P means that training iterations τnr result in larger data processing energy costs in (P r ), and, as such, the network reduces the average training iterations as ψ P grows, which in turn leads to larger estimated gradients. The second takeaway from both Fig. 8a) and Fig. 8b) is that larger networks generally see smaller average training iterations and larger estimated gradients, regardless of ψ G or ψ P . These two effects are both the result that larger networks physically have more devices, therefore (i) the total estimated gradient expressions in (P r ) contain more additive terms, and (ii) some devices demonstrate greater energy and training efficiency than other devices (as a result of heterogeneous hardware) leading to greater differences in local training iterations across devices. We next examine the sensitivity of (P r ) to ψ R , the deviceto-server transmission energy cost scaling, in Fig. 8c). Here, χD n represents the squared device-to-server distances, whose form as an auxiliary variable is introduced and explained in Appendix D-B. The general trend as ψ R grows larger is that the transmission energy costs become a more important consideration. Thus, Fig. 8c) shows that larger ψ R leads to lower average transmission power Pnr at devices in order to save on energy costs and, simultaneously, the average deviceto-server distances increases. This divergent effect on average transmission power and average device-to-server distances is because the server decides to choose specific devices to keep active (i.e., keep τnr > 0 through αnr = 1) and other devices to set inactive (i.e. allow τnr → 0 by setting αnr = 0) via constraints (31)-(33). Subsequently, the server then moves towards the active devices and further away from the inactive ones, leading to both (i) larger squared device-to-server distances and (ii) smaller average transmission power with growing ψ R At large enough values of ψ R such as ψ R = 1e12, device-to-server transmission energy costs become prohibitive in general. In response, the average transmission power goes
to 0 as all devices become inactive (i.e., αnr = 0), and, simultaneously, the device-to-server distances become stable as the server maintains its starting XY-position and lets its Zposition drop to 0 (i.e., ϕrS = (50, 50, 0)) to save on altitude maintenance energy per (30). Finally, Fig. 8d) examines the average device-to-server transmission power and server’s XY position relative to increasing server movement cost scaling, ψ S . We use separate y-axis scalings for average transmission power in Fig. 8c) and d), specifically W and mW respectively. This is because variations in ψ R lead to device-to-server transmission powers that span multiple orders of magnitude, as ψ R directly weights communication energy in the objective (P r ). In contrast, changes in ψ S induce only modest variations. Here, we only show the server’s XY positions because the Z dimension has the same switching behavior for large ψ S as that of Fig. 8c) for large ψ R . As ψ S increases from 1e−6 to 1e2, the energy costs of moving the server are increasing. In response, the network reduces the server’s XY position movements, substituting them instead with larger average device-to-server transmission power to maintain the timing constraints in (31)(33). Subsequently, in the regime of ψ S between 1e2 to 1e10, server movement is prohibitively costly, causing the server to stay physically still while the average device-to-server transmission power continues to increase (with the exception for networks of 10 devices, in which some devices become inactive instead). Finally, for ψ S ≥ 1e10, even hovering is too costly for the system, and the network devices all become inactive in response. These takeaways are further corroborated by Fig. 9, in which the server is initialized in a random starting location. Aside from differences in nominal values, e.g., the server XY position change versus ψ S in both Fig. 8d) and 9d), the general trends are preserved across both centralized and random server position initializations. Appendix E further corroborates the underlying trends for these characteristic curves for other server initial positions, and, moreover, performs a detailed ablation study, controlling the optimization iterations as well as the status (on/off) of CPU clock control, server movement, and device-to-server transmission energies. C. Evaluation of SC-DN In the following subsections, we examine SC-DN in both static (Sec. VI-C1) and dynamic networks (Sec. VI-C2). The static network experiments use full dataset feature partitions, meaning that all of the dataset’s features are available at every global round r ∈ R and devices have no overlapping features. On the other hand, in dynamic networks, networks may not have all of the features available ∀r ∈ R, and it is possible for devices to have overlapping features. Furthermore, as presented in Sec. III-B, we assume that devices are equally likely to have one of the three device failure regimes, indicated by the Weibull PDF expressions in (1), and device entries follow a Poisson arrival process with rate 0.5. Finally, with regards to local SGD method in Sec. III-C, devices follow (r,q) standard SGD wn = 1 in static networks while, in dynamic networks, devices randomly use either standard SGD, proximal
15
0.4
1e-3 1e-4 1e-5 1e-6 1e-7 1e-8
1e6 1e7 1e8 1e9 1e10 1e11 1e12 1e13
0.2 P Values
G Values
20
7e3
15
5e3
10
3e3
5
1e3
0
R Values
d) Varying S
Server XY-Pos Change (m)
0.6
9e3
60 40 20 0
1e-6 1e-4 1e-2 1e0 1e2 1e4 1e6 1e8 1e10
0.8
c) Varying R
10 Devices 10 Devices
Avg Sq D2S Dist ( nD) Avg Tx Power (mW)
1.0
1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
5 4 3 2 1 0
b) Varying P
6 Devices 6 Devices
Norm Gradient Avg Tx Power (W)
1.0 0.8 0.6 0.4 0.2
Norm Gradient Avg Train Iters ( nr )
5 4 3 2 1 0
a) Varying G
1e-10 1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
Avg Train Iters ( nr )
2 Devices 2 Devices
S Values
r
FIGURE 8: Characteristic curves for the various scaling coefficients of (P ) for three different network sizes, with abbreviations ‘Avg’
for average, ‘Iters’ for iterations, ‘Norm’ for normalized, ‘Tx’ for transmissions, ‘Sq D2S Dist’ for squared device-to-server distance, and ‘XY-pos’ for xy-position. These networks are all initialized with the server in a central position. The first two figures, Fig. 8a) and Fig. 8b), focus on the ML convergence aspects of (P r ) as both ψ G and ψ P influence the training iterations τnr of network devices. Conversely, the last two figures, Fig. 8c) and Fig. 8d), investigate the control over transmission energies and server position, respectively. Transmission energies that fall below 1e−8 in Fig. 8c) are equivalent to 0.
0.6 0.4 0.2 P Values
G Values
9e3
20
1e-3 1e-4 1e-5 1e-6 1e-7 1e-8
7e3
15
5e3
10
3e3
5
1e3
0
R Values
d) Varying S
Server XY-Pos Change (m)
0.8
c) Varying R
80 60 40 20 0
1e-6 1e-4 1e-2 1e0 1e2 1e4 1e6 1e8 1e10
1.0
10 Devices 10 Devices
Avg Sq D2S Dist ( nD) Avg Tx Power (mW)
b) Varying P
1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
5 4 3 2 1 0
1e6 1e7 1e8 1e9 1e10 1e11 1e12 1e13
1.0 0.8 0.6 0.4 0.2
6 Devices 6 Devices
Norm Gradient Avg Tx Power (W)
a) Varying G
Norm Gradient Avg Train Iters ( nr )
5 4 3 2 1 0
1e-10 1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
Avg Train Iters ( nr )
2 Devices 2 Devices
S Values
r FIGURE 9: Characteristic curves for the scaling coefficients of (P ) for three different network sizes, with identical abbreviations to that explained in Fig. 8. The server’s position in these networks is randomly initialized. The key trends demonstrated across ψ G , ψ P , ψ R , and ψ S are similar to those for central initial server positions in Fig. 8.
(r,q)
τ r −1−q
= r(1 − ηnr µ) n , or SGD with momentum SGD wn (r,q) 1−ρτn −q = wn , with µ and ρ chosen such that the 1−ρ conditions of Theorem 1 hold. 1) Static Networks: We examine the behavior of SC-DN relative to Max VFL, which is a greedy heuristic of VFL with τnr = τ g for all r ∈ R and n ∈ N r , GSP and VAFL. In particular, GSP, greedy server placement, is a heuristic augmentation of [78], while VAFL, vertical asynchronous federated learning [37], is further augmented by using the averaged τnr derived by our SC-DN methodology. The results on MNIST, CIFAR10, and Pawpularity are shown in Table I, Table II, and Table III respectively. Additional evaluation for random initial server position are left to Appendix E-B On all three datasets, SC-DN achieves comparable or better performances than Max VFL, GSP, and VAFL while requiring fewer (or similar) average training iterations and less average data processing energy. For instance, on MNIST with a network of 2 devices, we see that the average training iterations is 3.76 for SC-DN compared to 5.00 for Max VFL, 3.61 for GSP, and 3.44 for VAFL, while the final accuracies are 85.69%, 78.23%, 83.15%, and 75.23% respectively in Table I.
While MNIST demonstrates the biggest gaps in average training iterations between SC-DN and Max VFL at 1.24, 1.00, 1.08 for networks with 2, 4, and 6 respective devices, both CIFAR10 in Table II and Pawpularity in Table III confirm SCDN’s consistency in requiring fewer training iterations than Max VFL. Specifically, SC-DN uses 0.09, 0.26, 0.40 fewer iterations on CIFAR10 and 0.353, 0.145, 0.098 fewer iterations on Pawpularity for networks with 2, 4, and 6 respective devices. As a result of smaller average training iterations in Tables I-III, SC-DN is able to offer noticeable average data processing energy savings, yielding at least 25.8%, 14.5%, and 17.9% average data processing energy savings over Max VFL for MNIST, CIFAR10, and Pawpularity respectively. Relative to GSP and VAFL, SC-DN also achieves meaningful energy reductions. On MNIST at N = 2, SC-DN’s average energy of 224.08 J is substantially lower than GSP’s 340.51 J and VAFL’s 324.88 J, despite GSP and VAFL benefiting from SC-DN’s iteration assignments, as these baselines offer limited CPU control. This highlights that optimizing server placement or fault tolerance alone, without jointly controlling transmission power and CPU allocation, leaves significant
16
energy savings unrealized. On CIFAR10, SC-DN similarly consumes 22.85 kJ on average at N = 2, compared to 29.92 kJ for GSP and 29.97 kJ for VAFL, which are reductions of approximately 24% in both cases. The Pawpularity results in Table III further underscore this trend, with SC-DN using 6.10 kJ at N = 2 versus 9.83 kJ for GSP and 9.88 kJ for VAFL. Moreover, the standard deviations further reveal the advantages of SC-DN over all baselines. For accuracies on MNIST in Table I, SC-DN generally exhibits comparable or lower variability than Max VFL as the network size increases. While both methods show relatively large standard deviations for N = 4, SC-DN achieves lower standard deviations than Max VFL for all cases, 4.62% versus 12.25% for N = 2, 18.08% versus 21.14% for N = 4, and 9.23% versus 10.22% for N = 6, indicating more stable final performance for VFL in static networks. GSP and VAFL exhibit considerably higher accuracy standard deviations than SC-DN on MNIST, with GSP reaching 13.78% and VAFL 11.16% at N = 2, and GSP as high as 23.04% at N = 4, reflecting the instability introduced by optimizing placement or aggregation in isolation. Next, in terms of energy consumption, SC-DN demonstrates higher standard deviations in energy consumption compared to Max VFL across all network sizes. This behavior is expected, as SC-DN explicitly adapts device participation and local computation across rounds (confirmed by the higher standard deviations for local training iterations τnr ), leading to a wider range of per-round energy use. However, this increased variability does not translate to higher worst-case energy usage. In fact, the maximum energy values under SC-DN remain strictly lower than those of Max VFL, GSP, and VAFL for all N , confirming that SC-DN maintains both performance and resource efficiency advantages over all baselines. The core takeaways from Table I are further corroborated by Table II for CIFAR10 and Table III for Pawpularity. That being said, the experiments for Pawpularity in Table III do show that SC-DN has a higher standard deviation for final error, but these differences in standard deviation between SC-DN and Max VFL are limited to at most 0.001 across all network sizes. Moreover, the average final errors are identical for both methods, indicating that this marginal increase in variability does not impact the overall predictive performance, especially considering the energy savings offered by SC-DN. Meanwhile, GSP and VAFL produce comparable final MSE values to SCDN and Max VFL for N = 2 and N = 4 on Pawpularity, with the notable exception of VAFL at N = 6, where its final MSE degrades to 0.067 compared to SC-DN’s 0.055, GSP’s 0.056, and Max VFL’s 0.055. Nevertheless, SC-DN’s energy advantages over GSP and VAFL are preserved across all network sizes and datasets, further confirming that SC-DN’s joint optimization of placement, power, CPU, and iteration control is the key driver of its resource efficiency gains. Overall, Tables I-III are surprising as SC-DN’s fewer average training iterations lead to better or comparable performance to that of the baselines. The main reason is that SCDN is able to select devices with more useful data features and capable ML models to run more local training iterations via larger relative importance factor γnr , which was introduced within the statement of (P r ) in (45)(a). These effects allow
TABLE I: Performance of SC-DN relative to the greedy Max VFL, GSP, and VAFL for MNIST in static networks of varying size, in which the server is initialized in the center of the network. We denote the standard deviation as “Std”. In extreme cases, devices may be purposefully set as inactive following SC-DN.
SC-DN
Max VFL
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (J) Min Energy (J) Max Energy (J) Std Energy (J) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
85.69 4.62 224.08 30.31 299.85 105.64 3.76 0.47 5.00 1.81
68.86 18.08 240.24 84.74 300.13 77.34 4.00 1.31 5.00 1.34
66.61 9.23 235.04 87.36 300.80 83.57 3.92 1.33 5.00 1.45
78.23 12.25 472.32 457.82 516.30 16.25 5.00 5.00 5.00 0.00
GSP
62.90 21.14 472.55 461.20 504.43 12.74 5.00 5.00 5.00 0.00
62.37 10.22 472.30 459.41 512.06 14.73 5.00 5.00 5.00 0.00
VAFL
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (J) Min Energy (J) Max Energy (J) Std Energy (J) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
83.15 13.78 340.51 222.48 413.04 37.81 3.61 2.40 4.40 0.40
62.22 23.04 337.81 291.16 390.79 26.32 3.58 3.13 4.17 0.29
64.61 14.07 344.66 303.67 415.39 22.17 3.65 3.30 4.14 0.20
75.23 11.16 324.88 231.53 415.01 40.30 3.44 2.50 4.50 0.39
67.46 21.60 327.71 296.14 368.32 18.11 3.47 3.17 3.90 0.17
64.08 11.52 297.76 226.91 347.86 21.15 3.15 2.46 3.42 0.21
SC-DN to prevent biasing by devices with less informative or noisy data features, thus yielding higher performance and smaller average training iterations than the baselines. The second set of takeaways from Tables I-III concerns the impact of larger networks. Consistent across all three datasets, we see that, as the networks increase in size from 2 to 6 devices, the final training accuracies decrease for all methods on MNIST and CIFAR10, while the final error increases (i.e., worse performance) for both methods on Pawpularity. This is because the data features are fully partitioned across the networks. Under such conditions, larger networks have devices with fewer data features than those devices in smaller networks, on average. In this regard, Tables I-III also confirm intuition that concentrating data features leads to better performance. Moreover, as a result of data feature partitioning, larger networks with variable ML model architectures see lower average data processing energies in Tables I-III. For instance, the MNIST experiments in Table I use similar MLPs, whose sizes are independent of the number of data features. As a result, larger networks, with more distributed data features, demonstrate only minor changes (within 10% from N = 2 to N = 6) in average processing energy for all methods. By contrast, the CIFAR10 experiments in Table II rely on modified versions of Alexnet, with has both convolutional and linear layers. Here, more distributed data features reduces the size of devices’ ML models (i.e., number of neurons) as the output of the convolutional layers is smaller, thus leading to roughly 13% savings in average processing energy for the methodologies being compared as networks increase from 2 to 6 devices. Finally, the trends for average processing energies
17
TABLE II: Performance of SC-DN relative to greedy Max VFL, GSP, and VAFL baselines for CIFAR10 in static networks of varying size in which the server’s initial position is in the center of the network. SC-DN demonstrates an edge in final accuracies and energy savings as well as reduced variation, measured by standard deviation.
TABLE III: Multi-Modal Regression Performance on Pawpularity for SC-DN relative to greedy Max VFL, GSP, and VAFL in static networks of varying size with a centrally located initial server position. Final errors are identical yet SC-DN yields energy savings.
SC-DN SC-DN
Max VFL
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (kJ) Min Energy (kJ) Max Energy (kJ) Std Energy (kJ) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
95.44 2.98 22.85 18.30 23.99 2.28 4.91 4.57 5.00 0.17
65.08 5.70 21.19 8.03 23.99 5.63 4.75 3.47 5.00 0.52
61.88 5.93 19.91 5.47 23.99 6.91 4.60 3.06 5.00 0.71
95.41 2.96 33.40 28.84 34.54 2.28 5.00 5.00 5.00 0.00
GSP
64.64 8.93 31.48 16.65 34.54 6.18 5.00 5.00 5.00 0.00
55.33 8.97 29.93 12.90 34.54 7.99 5.00 5.00 5.00 0.00
92.61 4.34 29.92 24.22 34.54 2.701 4.48 4.00 5.00 0.28
63.66 8.46 28.23 13.65 32.70 5.84 4.47 4.10 4.73 0.16
Final Error (MSE) Std Error (MSE) Avg Energy (kJ) Min Energy (kJ) Max Energy (kJ) Std Energy (kJ) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
60.43 6.32 27.42 11.56 33.02 7.37 4.58 4.34 4.78 0.11
94.33 3.45 29.97 23.65 34.54 2.76 4.49 3.90 5.00 0.28
64.33 9.20 28.06 13.99 32.70 5.76 4.45 4.13 4.73 0.16
0.050 0.006 6.10 2.52 7.92 2.39 4.65 3.69 5.00 0.48
0.053 0.012 2.72 1.87 3.10 0.49 4.86 4.38 5.00 0.20
0.055 0.008 1.40 1.13 1.49 0.12 4.90 4.57 5.00 0.14
0.050 0.005 9.93 4.99 12.37 3.21 5.00 5.00 5.00 0.00
GSP
VAFL
0.053 0.012 4.35 3.22 4.85 0.64 5.00 5.00 5.00 0.00
0.055 0.007 2.23 1.85 2.41 0.15 5.00 5.00 5.00 0.00
VAFL
N=2 N=4 N=6 N=2 N=4 N=6
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (kJ) Min Energy (kJ) Max Energy (kJ) Std Energy (kJ) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
Max VFL
N=2 N=4 N=6 N=2 N=4 N=6
57.76 5.29 27.69 11.71 33.57 7.38 4.63 4.36 4.86 0.13
on Pawpularity in Table III mirror those of CIFAR10 as the devices with image data, which rely on CNNs, have average data processing energy that overshadows that of devices with MLPs for tabular data. While the above experiments and discussion focused on the case when the server’s initial position is in the center of the network, further experiments, when the server’s initial position is random in Appendix E, corroborate these insights. 2) Dynamic Edge/Fog Networks: In the following dynamic edge/fog experiments, we compare the proposed SC-DN methodology, with its time-varying ML model dimensions, relative to zero out condense (ZOC), a heuristic for VFL in dynamic edge/fog that discards embeddings and neurons from device exits, as well as GSP and VAFL, which are further augmented with SC-DN’s averaged τnr as described in Section VI-C1 as well as its framework of retaining past embeddings from devices which exit. These experiments, shown in Fig. 10-12, also investigate performances with and without the local training iterations τnr determined by the optimization (P r ) Aside from having τnr = τ g , experiments without (P r ) also follow a greedy methodology, maximizing the number of active devices without regard to device-to-server transmission power or server positioning. Thus, we evaluate the integration and importance of (P r ) within SC-DN. Comparing the accuracy curves of SC-DN and ZOC in Fig. 10a)-12a), we can see that SC-DN, via keeping the embeddings of devices that exit and expanding the dimension of the server’s fusion ML model with device entries, yields generally smooth convergence results. While keeping embeddings may appear intuitive, there are no guarantees, especially in dynamic edge/fog, that these embeddings will be
Final Error (MSE) Std Error (MSE) Avg Energy (kJ) Min Energy (kJ) Max Energy (kJ) Std Energy (kJ) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
0.050 0.005 9.83 4.52 12.37 3.27 4.93 4.30 5.00 0.18
0.053 0.013 4.29 2.86 4.85 0.70 4.92 4.43 5.00 0.13
0.056 0.007 2.15 1.74 2.33 0.17 4.82 4.54 5.00 0.12
0.050 0.006 9.88 4.41 12.37 3.28 4.95 4.40 5.00 0.12
0.053 0.012 4.31 3.15 4.85 0.68 4.95 4.57 5.00 0.11
0.067 0.019 2.16 1.70 2.35 0.18 4.84 4.58 4.98 0.11
derived from well trained devices and integrated throughout the network before such devices exit. As such, caching static embeddings from device exits and subsequently using them for ML model training at both server and remaining devices may introduce noise or damage convergence. Similarly, expanding the dimension of the server’s ML model with device entries may require lengthy recalibration, causing sudden drops in ML performance. Fortunately, experiments in Fig. 10a)-12a) show that this is generally not the case, with MNIST, CIFAR10, and Pawpularity experiments in Fig. 10a), Fig. 11 and Fig. 12a) respectively showing almost monotonic convergence. GSP and VAFL similarly exhibit smooth convergence across all three datasets, with GSP converging to approximately 75% on MNIST and 61% on CIFAR10, and VAFL reaching comparable values, though both trail SC-DN with (P r )’s final accuracy of approximately 82% on MNIST and 64% on CIFAR10. By contrast, ZOC shows the impact of discarding information from device exits. For MNIST in Fig. 10a), we see sharp declines in performance, roughly 8% for both instances of ZOC, once devices start to exit the network, around the 10-th global round. This trend similarly holds for CIFAR10 and Pawpularity with a roughly 5% drop in accuracies in Fig. 11a) and a roughly 25% increase in mean squared error in Fig. 12, respectively. To summarize, the main takeaways from Fig. 10a)-12a) are therefore that (i) even poorly trained embeddings from device exits can still have value in conditioning the ML model training at remaining devices, (ii) server ML model recalibration with device entries happens quickly, and (iii) SC-DN’s joint optimization yields smoother and more stable convergence than GSP and VAFL, which optimize placement or aggregation in isolation.
18
Global Rounds
0.2 0.0
w/ r
3.0 2.5
w/o r
0
20
Secondly, as in the static network experiments of Tables IIII, SC-DN offers energy savings in the dynamic edge/fog experiments of Fig. 10b)-12b) when the optimization (P r ) is applied. Specifically, (P r ) yields roughly 38%, 48%, and 43% process energy savings on MNIST, CIFAR10, and Pawpularity, respectively. The savings on all three datasets is driven by both lower average training iterations τnr shown in Fig. 10c), Fig. 11c), Fig. 12c) and lower CPU clock frequencies. Relative to GSP and VAFL, SC-DN with (P r ) also achieves meaningful energy reductions. On MNIST, SC-DN with (P r ) consumes approximately 0.25 kJ on average, compared to roughly 0.35 kJ for GSP and 0.35 kJ for VAFL, a reduction of approximately 29% in both cases. On CIFAR10, SC-DN with (P r ) uses approximately 22 kJ versus roughly 29 kJ for GSP and 28 kJ for VAFL. On Pawpularity, SC-DN with (P r ) consumes approximately 2.0 kJ compared to roughly 2.5 kJ for GSP and 2.5 kJ for VAFL. These reductions confirm that jointly optimizing placement, power, CPU, and iteration control yields energy savings beyond what greedy placement or fault-tolerant aggregation alone can achieve. That being said, while SC-DN’s energy savings over ZOC are limited when (P r ) is active, SC-DN does offer better value as it yields better performance over ZOC on all three datasets. When (P r ) is off, SC-DN and ZOC have identical average data processing energy use (and thus no standard deviation in average process energies) as both methods run τnr = τ g local training iterations for all global round and across all devices, but SC-DN yields better accuracy curves. Finally, while methodologies that leverage (P r ) to determine the local training iterations τnr exhibit larger standard deviations in average process energy across all three datasets in Fig. 10–12, we emphasize that the mean process energy plus one standard deviation for these adaptive schemes remains lower than the mean process energy under fixed iteration baselines τnr = τ g (i.e., without (P r )). The dynamic edge/fog experiments also confirm the value of the integrated optimization formulation within SC-DN. For instance, SC-DN with (P r ) offers better performance than
50 0
Global Rounds
FIGURE 10: Examining the accuracy, average energy, and average training iterations per global round for SC-DN on MNIST in dynamic networks with the central initial position for the server. Error bars in Fig. 10b) denote the standard deviation of average process energy. Additional tables for standard deviations for performance and change in training iterations are in Table XII and XIII in Appendix E.
55
10
Average nr
3.5
60 50 40 30
4.5 4.0 3.5
20
20
w/ r
Global Rounds
0
w/o r
20
Global Rounds
FIGURE 11: Examining the accuracy, average energy, and average training iterations per global round for SC-DN on CIFAR10 in dynamic networks. The server’s initial position is at the center of the network. Average training iterations are significantly and consistently lower than standard VFL across network devices. Table XIV and XV in Appendix E provide detailed standard deviation information for accuracies and changes in τnr .
GSP With ( r) With ( r)
ZOC SC-DN
a) Performance
0.12 0.10 0.08 0.06 0.04
0
10
20
Global Rounds
VAFL GSP VAFL Without ( r) With ( r) Without ( r) r r Without ( ) With ( ) Without ( r) c) Change in nr b) Energy Use 5 5.0 4
Average nr
20
0.4
60
GSP VAFL
10
0.6
4.0
a) Performance
3 2 1 0
GSP VAFL
0
4.5
65
Avg Process Energy (kJ)
50
0.8
c) Change in nr
VAFL GSP VAFL Without ( r) With ( r) Without ( r) Without ( r) With ( r) Without ( r) c) Change in nr b) Energy Use 70 5.0
Avg Process Energy (kJ)
60
1.0
5.0
GSP With ( r) With ( r)
ZOC SC-DN
Accuracy (%)
70
b) Energy Use
VAFL Without ( r) Without ( r)
Mean Squared Error (MSE)
Accuracy (%)
80
GSP With ( r) With ( r)
Average nr
Avg Process Energy (kJ)
a) Performance
VAFL Without ( r) Without ( r)
GSP VAFL
GSP With ( r) With ( r)
ZOC SC-DN
w/ r
w/o r
4.5 4.0 3.5
0
20
Global Rounds
FIGURE 12: Evaluating SC-DN via multi-modal regression on Pawpularity in dynamic networks through measurements of mean squared error, average processing energy, and average training iterations over global rounds. The server is initially in the center of the network. In particular, the sharp fluctuations of mean squared error highlight the impact of losing entire modalities on overall performance. Associated tables for accuracy and τnr standard deviations are presented in Table XVI and XVII in Appendix E.
SC-DN without (P r ) for all three datasets under evaluation, with 1%, 9%, and 20% improvements on MNIST, CIFAR10, and Pawpularity. Moreover, these improvements coincide with significant data processing energy savings across all three datasets, with rough savings of 75%, 77%, and 48% for MNIST, CIFAR10, and Pawpularity respectively. While (P r ) also yields energy savings for ZOC, the integration of (P r ) and ZOC does not produce similar performance benefits as that for SC-DN, thus, highlighting the integrated nature of our overall methodology. Similarly, while GSP and VAFL benefit from SC-DN’s iteration assignments, neither achieves the same combination of accuracy and energy efficiency as SC-DN with (P r ), further underscoring that joint optimization of server placement, transmission power, CPU allocation, and local iterations is the key driver of SC-DN’s performance and
19
efficiency gains. We further investigate the associated standard deviations for Fig. 10–12 in Table XII-XVII (Appendix E) to better assess the robustness of SC-DN under dynamic network conditions. To summarize, these tables show that SC-DN with (P r ) consistently yields the lowest variation in accuracy/error across all three datasets. Overall, SC-DN with (P r ) consistently exhibits the lowest variability in accuracy/error across all three datasets. In addition, Tables XII–XVII confirm that the process energy savings observed in Fig. 10–12 are accompanied by proportional reductions in the average number of local training iterations τnr across global rounds. Further analysis of SC-DN with (P r ) under random server initializations is provided in Appendix E. VII. C ONCLUSION We have investigated VFL in dynamic edge/fog networks, in which devices can enter, exit, or experience link failures to the server. To optimize and control for both device-level training parameters as well as server-level positioning, we proposed the SC-DN methodology, a joint performance and resource optimization framework to account for the various forms of heterogeneity at the intersection of VFL and edge/fog networks. In developing SC-DN, we obtained theoretical results to characterize the gap between real and ideal ML model parameter induced losses and, subsequently, developed a first-order stationary point to represent network convergence. Notably, we leverage the fact that the bound for the firstorder stationary point is separable with respect to the global rounds in order to formulate a concrete optimization problem that jointly balances (i) estimated gradients, (ii) data processing energies, (iii) device-to-server transmissions, and (iv) server placement energies. Since SC-DN, in its initial form, contained both coupled variables, negative variables, and logarithmic constraints, we showed that it belongs to a class of mixed-integer signomial programs, which are NPhard and non-convex, and proposed an iterative method based on refining convex inner approximations, which was enabled by Padé-approximants and posynomial condensations. Finally, we demonstrated both performance and energy efficiency improvements obtained by SC-DN relative to greedy methods for dynamic edge/fog on for classification on image datasets and regression on a multi-modal dataset. R EFERENCES [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. PMLR, 2017, pp. 1273–1282. [2] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 10, no. 2, pp. 1–19, 2019. [3] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1205–1221, 2019. [4] Y. Liu, Y. Kang, T. Zou, Y. Pu, Y. He, X. Ye, Y. Ouyang, Y.-Q. Zhang, and Q. Yang, “Vertical federated learning: Concepts, advances, and challenges,” IEEE Transactions on Knowledge and Data Engineering, vol. 36, no. 7, pp. 3615–3634, 2024.
[5] S. Ganguli, Z. Zhou, C. G. Brinton, and D. I. Inouye, “Fault-tolerant vertical federated learning on dynamic networks,” arXiv:2312.16638, 2023. [6] T. Castiglia, S. Wang, and S. Patterson, “Flexible vertical federated learning with heterogeneous parties,” IEEE Transactions on Neural Networks and Learning Systems, 2023, to appear. [7] H. Zheng, S. R. Kulkarni, and H. V. Poor, “Attribute-distributed learning: Models, limits, and algorithms,” IEEE Transactions on Signal Processing, vol. 59, no. 1, pp. 386–398, 2010. [8] S. Wang, S. Hosseinalipour, V. Aggarwal, C. G. Brinton, D. J. Love, W. Su, and M. Chiang, “Toward cooperative federated learning over heterogeneous edge/fog networks,” IEEE Communications Magazine, vol. 61, no. 12, pp. 54–60, 2023. [9] Z.-L. Chang, S. Hosseinalipour, M. Chiang, and C. G. Brinton, “Asynchronous multi-model dynamic federated learning over wireless networks: Theory, modeling, and optimization,” IEEE Transactions on Cognitive Communications and Networking, 2024, to appear. [10] L. Yuan, D.-J. Han, S. Wang, D. Upadhyay, and C. G. Brinton, “Communication-efficient multimodal federated learning: Joint modality and client selection,” arXiv:2401.16685, 2024. [11] J. Zhang, S. Guo, Z. Qu, D. Zeng, H. Wang, Q. Liu, and A. Y. Zomaya, “Adaptive vertical federated learning on unbalanced features,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 12, pp. 4006–4018, 2022. [12] G. Wang, B. Gu, Q. Zhang, X. Li, B. Wang, and C. X. Ling, “A unified solution for privacy and communication efficiency in vertical federated learning,” Advances in Neural Information Processing Systems, vol. 36, 2024. [13] T. J. Castiglia, A. Das, S. Wang, and S. Patterson, “Compressed-vfl: Communication-efficient learning with vertically partitioned data,” in Proceedings of the 39th International Conference on Machine Learning. PMLR, 2022, pp. 2738–2766. [14] D. C. Nguyen, M. Ding, P. N. Pathirana, A. Seneviratne, J. Li, D. Niyato, O. Dobre, and H. V. Poor, “6G internet of things: A comprehensive survey,” IEEE Internet of Things Journal, vol. 9, no. 1, pp. 359–383, 2021. [15] S. Wang, S. Hosseinalipour, M. Gorlatova, C. G. Brinton, and M. Chiang, “UAV-assisted online machine learning over multi-tiered networks: A hierarchical nested personalized federated learning approach,” IEEE Transactions on Network and Service Management, vol. 20, no. 2, pp. 1847–1865, 2022. [16] Y. Ruan, X. Zhang, S.-C. Liang, and C. Joe-Wong, “Towards flexible device participation in federated learning,” in Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 3403–3411. [17] U. Dampage, L. Bandaranayake, R. Wanasinghe, K. Kottahachchi, and B. Jayasanka, “Forest fire detection system using wireless sensor networks and machine learning,” Scientific Reports, vol. 12, no. 1, p. 46, 2022. [18] C. Rankine, M. M. do Espirito Santo, R. Fatland, M. Garcia et al., “Wireless sensing networks for environmental monitoring: Two case studies from tropical forests,” in Proceedings of the Seventh IEEE International Conference on eScience. IEEE, 2011, pp. 70–76. [19] V. C. Gungor, B. Lu, and G. P. Hancke, “Opportunities and challenges of wireless sensor networks in smart grid,” IEEE Transactions on Industrial Electronics, vol. 57, no. 10, pp. 3557–3564, 2010. [20] H. Huang, H. V. Poor, K. R. Davis, T. J. Overbye, A. Layton, A. E. Goulart, and S. Zonouz, “Toward resilient modern power systems: From single-domain to cross-domain resilience enhancement,” Proceedings of the IEEE, vol. 112, no. 4, pp. 365–398, 2024. [21] S. Wang, S. Hosseinalipour, and C. G. Brinton, “Multi-source to multitarget decentralized federated domain adaptation,” IEEE Transactions on Cognitive Communications and Networking, no. 3, pp. 1011–1025, 2024. [22] E. Chen, S. Wang, and C. G. Brinton, “Taming subnet-drift in d2denabled fog learning: A hierarchical gradient tracking approach,” in Proceedings of the 2024 IEEE Conference on Computer Communications. IEEE, 2024, pp. 2438–2447. [23] K. Luo, K. Zhao, T. Ouyang, X. Zhang, Z. Zhou, H. Wang, and X. Chen, “Efficient coordination of federated learning and inference offloading at the edge: A proactive optimization paradigm,” IEEE Transactions on Mobile Computing, 2024, to appear. [24] N. H. Tran, W. Bao, A. Zomaya, M. N. Nguyen, and C. S. Hong, “Federated learning over wireless networks: Optimization model design and analysis,” in Proceedings of the 2019 IEEE Conference on Computer Communications. IEEE, 2019, pp. 1387–1395.
20
[25] Z. Hu, K. Shaloudegi, G. Zhang, and Y. Yu, “Federated learning meets multi-objective optimization,” IEEE Transactions on Network Science and Engineering, vol. 9, no. 4, pp. 2039–2051, 2022. [26] J. Feng, L. Liu, Q. Pei, and K. Li, “Min-max cost optimization for efficient hierarchical federated learning in wireless edge networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 11, pp. 2687–2700, 2021. [27] A. Murhekar, Z. Yuan, B. Ray Chaudhury, B. Li, and R. Mehta, “Incentives in federated learning: Equilibria, dynamics, and mechanisms for welfare maximization,” Advances in Neural Information Processing Systems, vol. 36, 2024. [28] S. Wang, Y. Ruan, Y. Tu, S. Wagle, C. G. Brinton, and C. Joe-Wong, “Network-aware optimization of distributed learning for fog computing,” IEEE/ACM Transactions on Networking, vol. 29, no. 5, pp. 2019–2032, 2021. [29] H. Yang, X. Zhang, P. Khanduri, and J. Liu, “Anarchic federated learning,” in Proceedings of the 39th International Conference on Machine Learning. PMLR, 2022, pp. 25 331–25 363. [30] T. Huang, W. Lin, L. Shen, K. Li, and A. Y. Zomaya, “Stochastic client selection for federated learning with volatile clients,” IEEE Internet of Things Journal, vol. 9, no. 20, pp. 20 055–20 070, 2022. [31] X. Gu, K. Huang, J. Zhang, and L. Huang, “Fast federated learning in the presence of arbitrary device unavailability,” Advances in Neural Information Processing Systems, vol. 34, pp. 12 052–12 064, 2021. [32] M. Yemini, R. Saha, E. Ozfatura, D. Gündüz, and A. J. Goldsmith, “Robust federated learning with connectivity failures: A semi-decentralized framework with collaborative relaying,” arXiv:2202.11850, 2022. [33] B. Zhang, J. Geng, W. Xu, and L. Lai, “Communication efficient distributed learning with feature partitioned data,” in Proceedings of the 52nd Annual Conference on Information Sciences and Systems (CISS). IEEE, 2018, pp. 1–6. [34] J. Jiang, L. Burkhalter, F. Fu, B. Ding, B. Du, A. Hithnawi, B. Li, and C. Zhang, “VF-PS: How to select important participants in vertical federated learning, efficiently and securely?” Advances in Neural Information Processing Systems, vol. 35, pp. 2088–2101, 2022. [35] T. Castiglia, Y. Zhou, S. Wang, S. Kadhe, N. Baracaldo, and S. Patterson, “LESS-VFL: Communication-efficient feature selection for vertical federated learning,” in Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023, pp. 3757–3781. [36] A. Li, H. Peng, L. Zhang, J. Huang, Q. Guo, H. Yu, and Y. Liu, “Fedsdg-fs: Efficient and secure feature selection for vertical federated learning,” in Proceedings of the 2023 IEEE Conference on Computer Communications. IEEE, 2023, pp. 1–10. [37] T. Chen, X. Jin, Y. Sun, and W. Yin, “VAFL: A method of vertical asynchronous federated learning,” in Proceedings of the 2020 ICML Workshop on Federated Learning for User Privacy and Data Confidentiality, July 2020. [38] A. Krizhevsky, G. Hinton et al., “Learning multiple layers of features from tiny images,” 2009. [39] J. M. Bahi, M. Haddad, M. Hakem, and H. Kheddouci, “Distributed lifetime optimization in wireless sensor networks,” in Proceedings of the 2011 IEEE International Conference on High Performance Computing and Communications. IEEE, 2011, pp. 432–439. [40] T. Zhang and M. Xie, “Failure data analysis with extended weibull distribution,” Communications in Statistics—Simulation and Computation®, vol. 36, no. 3, pp. 579–592, 2007. [41] J. G. Andrews, R. K. Ganti, M. Haenggi, N. Jindal, and S. Weber, “A primer on spatial modeling and analysis in wireless networks,” IEEE Communications Magazine, vol. 48, no. 11, pp. 156–163, 2010. [42] W. Khawaja, I. Guvenc, D. W. Matolak, U.-C. Fiebig, and N. Schneckenburger, “A survey of air-to-ground propagation channel modeling for unmanned aerial vehicles,” IEEE Communications Surveys & Tutorials, vol. 21, no. 3, pp. 2361–2391, 2019. [43] W. Khawaja, O. Ozdemir, F. Erden, I. Guvenc, and D. W. Matolak, “Uwb air-to-ground propagation channel measurements and modeling using uavs,” in Proceedings of the 2019 IEEE Aerospace Conference. IEEE, 2019, pp. 1–10. [44] S. Zhang, H. Zhang, B. Di, and L. Song, “Cellular uav-to-x communications: Design and optimization for multi-uav networks,” IEEE Transactions on Wireless Communications, vol. 18, no. 2, pp. 1346– 1359, 2019. [45] A. Al-Hourani, S. Kandeepan, and A. Jamalipour, “Modeling air-toground path loss for low altitude platforms in urban environments,” in Proceedings of the 2014 IEEE Global Communuications Conference. IEEE, 2014, pp. 2898–2904.
[46] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Mobile unmanned aerial vehicles (uavs) for energy-efficient internet of things communications,” IEEE Transactions on Wireless Communications, vol. 16, no. 11, pp. 7574–7589, 2017. [47] P. Richtárik and M. Takáč, “Parallel coordinate descent methods for big data optimization,” Mathematical Programming, vol. 156, pp. 433–484, 2016. [48] Y. Nesterov, “Efficiency of coordinate descent methods on huge-scale optimization problems,” SIAM Journal on Optimization, vol. 22, no. 2, pp. 341–362, 2012. [49] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the objective inconsistency problem in heterogeneous federated optimization,” Advances in Neural Information Processing Systems, vol. 33, pp. 7611–7623, 2020. [50] L. Xiao and T. Zhang, “A proximal stochastic gradient method with progressive variance reduction,” SIAM Journal on Optimization, vol. 24, no. 4, pp. 2057–2075, 2014. [51] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in Proceedings of the 30th International Conference on Machine Learning. PMLR, 2013, pp. 1139–1147. [52] R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth, “On the lambert w function,” Advances in Computational Mathematics, vol. 5, pp. 329–359, 1996. [53] G. Blanc, N. Gupta, G. Valiant, and P. Valiant, “Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process,” in Proceedings of the Thirty Third Conference on Learning Theory. PMLR, 2020, pp. 483–513. [54] K. Ahn, A. Jadbabaie, and S. Sra, “How to escape sharp minima with random perturbations,” in Proceedings of the 41st International Conference on Machine Learning. PMLR, 2024, pp. 597–618. [55] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, “Spectral normalization for generative adversarial networks,” in Proceedings of the Sixth International Conference on Learning Representations, 2018. [56] S. Ducotterd, A. Goujon, P. Bohra, D. Perdios, S. Neumayer, and M. Unser, “Improving lipschitz-constrained neural networks by learning activation functions,” Journal of Machine Learning Research, vol. 25, no. 65, pp. 1–30, 2024. [57] B. Gao and L. Pavel, “On the properties of the softmax function with application in game theory and reinforcement learning,” arXiv:1704.00805, 2017. [58] D. Zou, R. Balan, and M. Singh, “On lipschitz bounds of general convolutional neural networks,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1738–1759, 2019. [59] C. T. Dinh, N. H. Tran, M. N. Nguyen, C. S. Hong, W. Bao, A. Y. Zomaya, and V. Gramoli, “Federated learning over wireless networks: Convergence analysis and resource allocation,” IEEE/ACM Transactions on Networking, vol. 29, no. 1, pp. 398–409, 2020. [60] J. Sevilla, L. Heim, M. Hobbhahn, T. Besiroglu, A. Ho, and P. Villalobos, “Estimating training compute of deep learning models,” 2022. [Online]. Available: https://epochai.org/blog/estimating-training-compute [61] D. Amodei and D. Hernandez, “Ai and compute,” 2018. [Online]. Available: https://openai.com/research/ai-and-compute [62] M. L. Salby, Fundamentals of Atmospheric Physics. Elsevier, 1996. [63] F. A. Administration, Aviation Weather Services. Aviation Supplies & Academics, 2001. [64] F. Gonzalez, A. Heckmann, S. Notter, M. Zurn, J. Trachte, and A. Mcfadyen, “Non-linear model predictive control for UAVs with slung/swung load,” in Proceedings of the 2015 IEEE International Conference on Robotics and Automation, 2015, pp. 1–1. [65] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” IEEE Transactions on Wireless Communications, vol. 16, no. 6, pp. 3747–3760, 2017. [66] Y. Zeng, J. Xu, and R. Zhang, “Energy minimization for wireless communication with rotary-wing UAV,” IEEE Transactions on Wireless Communications, vol. 18, no. 4, pp. 2329–2345, 2019. [67] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016. [68] M. Chiang, “Geometric programming for communication systems,” Foundations and Trends® in Communications and Information Theory, vol. 2, no. 1–2, pp. 1–154, 2005. [69] A. Agrawal, S. Diamond, and S. Boyd, “Disciplined geometric programming,” Optimization Letters, vol. 13, no. 5, pp. 961–976, 2019. [70] G. Xu, “Global optimization of signomial geometric programming problems,” European Journal of Operational Research, vol. 233, no. 3, pp. 500–510, 2014.
21
[71] R. J. Duffin and E. L. Peterson, “Reversed geometric programs treated by harmonic means,” Indiana University Mathematics Journal, vol. 22, no. 6, pp. 531–550, 1972. [72] F. TOPSØE1 , “Some bounds for the logarithmic function,” Inequality Theory and Applications, vol. 4, p. 137, 2007. [73] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [74] L. Deng, “The MNIST database of handwritten digit images for machine learning research,” IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141–142, 2012. [75] A. Howard, M. Jedi, and R. Holbrook, “Petfinder.my - pawpularity contest,” https://kaggle.com/competitions/petfinder-pawpularity-score, 2021, kaggle. [76] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” Advances in Neural Information Processing Systems, vol. 25, 2012. [77] M. Lapin, M. Hein, and B. Schiele, “Loss functions for top-k error: Analysis and insights,” in Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2016, pp. 1468–1477. [78] Z. Xu, W. Liang, W. Xu, M. Jia, and S. Guo, “Efficient algorithms for capacitated cloudlet placements,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 10, pp. 2866–2880, 2015. [79] R. Durrett, Probability: Theory and Examples. Cambridge University Press, 2019, vol. 49. [80] J. Stewart, Calculus, 8th ed. Cengage Learning, 2015.
22
A PPENDIX TABLE OF C ONTENTS Appendix A: Proof of Lemma 1
23
Appendix B: Proof of Proposition 1
25
Appendix C: Proof of Theorem 1
28
Appendix D: Solution to Optimization D-A Geometric Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D-B Optimization Problem Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D-C Summary of Resulting Optimization Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34 34 34 43
Appendix E: Additional Experiments E-A Optimization Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-B Integrated SC-DN Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-C Ablation Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45 45 50 56
23
A PPENDIX A P ROOF OF L EMMA 1 Lemma 1. (Stochastic Gradients in a Global Round) Given a global aggregation round r, the expected difference between stochastic gradients at iteration q ≤ τnr versus iteration 0 can be bounded as: i h EX rB ∥gn (Θ(r,q) ) − gn (Θ(r,0) )∥2 ≤ n n (18) r r (r,max) 2 2 2 ηn Ln wn , 4τnr (Qmax n ) + σn for dynamic edge/fog networks and τnr ≤ τ g . (r,q)
Proof. First, recall the notation Θn for r ∈ R, q ∈ {0, · · · , τqr − 1}, and n ∈ N r ∪ S, which was defined as h i (r,0) (r,0) (r,0) (r,0) (r,0) Θ(r,q) = θ0 ; f1 (θ1 ); · · · ; fn−1 (θn−1 ); fn (θn(r,q) ); fn+1 (θn+1 ); · · · ; fNcr (θ cr ) , n
(54)
N
(r,q)
The form of Θn allows us to define loss of the output of the ML model at device n for non-synchronization rounds (r,q) q ∈ {0, · · · , τnr − 1}. Next, we expand the definition of the partial gradients gn for the r-th global aggregation and the q-th (r,q) (r,q) update iteration at device n. Note that for notational convenience, we use gn to represent gn (Θn ). " EBr [∥gn(r,q) − gn(r,0) ∥2 ] = EBr (a)
Br
1 X ≤ r EBr B i=1 r
"
B (b) (Lr )2 X n ≤ EBr B r i=1
r
r
B B 2 1 X 1 X r i (r,q) i i r i (r,0) i i ∇ ℓ(Φ (x ); f (θ , x )|y ) − ∇ ℓ(Φ (x ); f (θ , x )|y ) n n n n n n n n n n B r i=1 B r i=1 #
# (55)
2
∇n ℓ(Φrn (xi ); fn (θn(r,q) , xin )|y i ) − ∇n ℓ(Φrn (xi ); fn (θn(r,0) , xin )|y i ) "
2
Θ(r,q) − Θ(r,0) n n
(56)
# ,
(57)
where (a) is due to Jensen’s inequality , (b) is via (13) in Assumption 1, and Φrn (xi ) is used to represent all non-n ML model parameters and embeddings to simplify notation. Next, let us investigate the update rule for the ML model parameters θnr,q . For any q-th iteration at a device n following global aggregation r, we have: θn(r,q) = θn(r,q−1) − ηnr wn(r,q−1) gn(r,q−1) .
(58)
Subsequently, we can obtain a similar expression ∀ξ ∈ {0, · · · , q − 1}, exemplified by the t − 1-th iteration: θn(r,q−1) = θn(r,q−2) − ηnr wn(r,q−2) gn(r,q−2) .
(59)
Continuing this process and substituting into (58) yields: q−1 X θn(r,q) = θn(r,0) − ηnr wn(r,ξ) gn(r,ξ)
(60)
ξ=0 (r,q)
(r,0)
(r,q)
Since Θn = [θ0 , · · · , θn continuing from (57), we have:
(r,0) N
(r,q)
, · · · , θ cr ], we have that Θn r r 2 B (c) (Ln ) X = EBr B r i=1 " r r 2 B (d) (Ln ) X EBr = B r i=1
(r,0)
− Θn
"
2
(r,q)
= [0, · · · , θn
X q−1
, · · · , 0], ∀j ̸= n. Now,
#
θn(r,q) − θn(r,0) − ηnr
(r,0)
− θn
wn(r,ξ) gn(r,ξ)
(61) 2# (62)
ξ=0
r
q−1 B X (e) (η r Lr )2 X (wn(r,ξ) )2 EBr [∥gn(r,ξ) ∥2 ], ≤ n rn B i=1 ξ=0 (r,q)
(r,0)
(63)
where (c) is via the result of Θn − Θn and the properties of euclidean norms with only a single non-zero entry, (d) is via (60), and (e) is via Jensen’s inequality. (r,ξ) In order to bound EBr [∥gn ∥2 ] further, we first investigate the implication of Assumption 2. Specifically, (14) and (15) enable us to leverage E[∥X + Y ∥p ] ≤ 2p (E[∥X∥p ] + E[∥Y ∥p ), (64)
24
∀p > 0, from [79]. Thus: (i)
EBr [∥gn(r,ξ) ∥2 ] = EBr [∥gn(r,ξ) + ∇n F (Θ(r,ξ) ) − ∇n F (Θ(r,ξ) )∥2 ] n n (ii)
(r,ξ)
≤ 4EBr [∥gk
− ∇n F (Θ(r,ξ) )∥2 ] + 4EBr [∥∇n F (Θ(r,ξ) )∥2 ]
(65) (66)
(iii)
≤ 4σn2 + 4∥∇n F (Θ(r,ξ) )∥2 ,
(67)
where (i) introduces a 0 term, (ii) leverages (64) with p = 2, and (iii) follows from Assumption 3. Combining the result (67) into (63) yields: q−1 B X (f ) (η r Lr )2 X 2 2 ≤ n n (wn(r,ξ) )2 4∥∇n F (Θ(r,ξ) )∥ + 4σ n n B i=1
(68)
ξ=0
r τX 2 n −1 max 2 2 r r (r,ξ) ≤ 4 ∥∇n F (Θn )∥ + σn ηn Ln wn
(g)
(69)
ξ=0
where (f ) results from (67), and (g) bounds ∇n F (Θ(r,ξ) ) by ∇n F (Θmax n ), the largest n-th partial gradient across all local iterations ξ ∈ {0, · · · , τkr − 1} and global rounds r ∈ R. This completes the proof. ■
25
A PPENDIX B P ROOF OF P ROPOSITION 1 Proposition 1. (Global Cumulative Gap Between Ideal and Real Parameters) Given some global aggregation round r and set cr , we can bound the gap between ideal and real ML model parameter induced losses by: all historical devices N R X
b (r,0) ) − F (Θ(r,0) ) ≤ F (Θ
r
R X
c N X 1
∥∇n F (θn(r,0) )∥2 2 r=0 r=0 n=0 X ! r−1 Lr + 1 r r y r c) (C1 + C3 ) + r (C2 N , 2 y y=0
where
(19)
h i 2 max max 4 max 2 2 C1 = 64τ g (τnmax Lmax (Q ) (η w ) ) + σ n n n n n ,
(20)
max max 2 C2 = 32(τnmax Lmax n ηn w n ) ,
(21)
and 2
C3 = 8 ((τ g − τnmax )ηnmax wnmax )
i h 2 2 (Qmax ) + σ n n .
(22)
Proof. We first leverage the smoothness assumption (Assumption 1) to obtain the following: (a)
b (r,0) ) − F (Θ(r,0) ) ≤ ∇F (Θ(r,0) )T (Θ b (r,0) − Θ(r,0) ) + F (Θ
Lr b (r,0) ∥Θ − Θ(r,0) ∥2 2
cr N (b) X
cr N Lr X b(r,0) (r,0) T b(r,0) (r,0) = ∇n F (θn ) (θn − θn ) + ∥θn − θn(r,0) ∥2 2 n=0 n=0 cr cr N N (c) X 1 1 b(r,0) Lr X b(r,0) (r,0) 2 (r,0) 2 ∥θn − θn(r,0) ∥2 ≤ ∥∇n F (θn )∥ + ∥θn − θn ∥ + 2 2 2 n=0 n=0 cr N r 1 L + 1 b(r,0) (d) X = ∥∇n F (θbn(r,0) )∥2 + ∥θn − θn(r,0) ∥2 , 2 2 n=0
(70) (71)
(72)
(73)
where (a) is from Assumption 1, (b) simply from expanding the definition of ∥ · ∥2 , (c) via ab ≤ 1/2a2 + 1/2b2 , and (d) combines like terms together. (r,q) (r,q) to represent gn (Θn ). Next, the focus is on bounding the Similar to the proof of Lemma 1, we will again use gn (r,0) (r,0) 2 ∥θbn − θn ∥ component. Thus y
∥θbn(r,0) − θn(r,0) ∥2 =
r−1 τX n −1 X y=0
ηny wn(y,q) (gn(y,q) − gbn(y,q) ) −
q=0
g τX −1 y q=τn
ηny wn(y,q) gbn(y,q)
y
g
q=0
y q=τn
2 (74)
τn −1 r−1 τX −1 X X y y (y,q) 2 (y,q) (y,q) 2 g y y (y,q) 2 (y,q) 2 (ηn wn ) ∥b gn ∥ ≤ 2r τn (ηn wn ) ∥gn − gbn ∥ + (τ − τn )
(e)
y=0
(75)
y
τn −1 r−1 X X ≤ 2r 4τny (ηny wn(y,q) )2 ∥b gn(y,q) − gbn(y,0) ∥2 + ∥gn(y,q) − gn(y,0) ∥2 + ∥gn(y,0) − gbn(y,0) ∥2
(f )
y=0
+ (τ g − τny )
q=0 g τX −1
(ηny wn(y,q) )2 ∥b gn(y,q) ∥2 ,
(76)
y q=τn
P P where (e) is via ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 and ( i∈N xi )2 ≤ N i∈N x2i , and (f ) is via the 3-variable parallelogram law, i.e. ∥a + b + c∥2 ≤ 4(∥a∥2 + ∥b∥2 + ∥c∥2 ). Combining the result of (76) and (73), and subsequently taking the expectation over a mini-batch B on both sides yields: y τn −1 r−1 X X (r,0) (r,0) 2 y y (y,q) 2 b E[∥θn − θn ∥ ] ≤ 2r (ηn wn ) E[∥b 4τn gn(y,q) − gbn(y,0) ∥2 ] + E[∥gn(y,q) − gn(y,0) ∥2 ] | {z } | {z } y=0 q=0 (i)
+ E[∥gn(y,0) − gbn(y,0) ∥2 ] | {z } (iii)
+ (τ g − τny )
g τX −1
y (y,q) 2 (y,q) 2 (ηn wn ) E[∥b g ∥ ] , | n{z } y
q=τn
(iv)
(ii)
(77)
26
via linearity of expectation. To bound (77)(i)-(iv), we use the following components and techniques: •
for (77)(i) and (ii), we can leverage Lemma 1 to obtain 2 2 2 g y y (y,max) EB [∥b gn(y,q) − gbn(y,0) ∥2 ] ≤ 4 (Qmax ) + σ τ η L w n n n n n and EB [∥gn(y,q) − gn(y,0) ∥2 ] ≤ 4
•
2 2 (Qmax n ) + σn
(78)
2 y y y (y,max) τn ηn Ln wn
(79)
for (77)(iii), we expand the definition of gb and g, then use the smoothness assumption in Assumption 1 to obtain: 2 EB [∥gn(y,0) − gbn(y,0) ∥2 ] ≤ (Lrn )
cr N X
(y,0)
EB [∥θj
(y,0) 2
− θbj
∥ ]
(80)
j=0 •
for (77)(iv), we have that b (y,q) )∥2 ≤ 4σ 2 + 4 ∇n F (Θmax ) 2 , EB [∥b gny,q ∥2 ] ≤ 4σn2 + 4∥∇n F (Θ n n n
(81)
which follows immediately from (65)-(67). Thus, we end up with the following bound for (77), y
EB [∥θbn(r,0) − θn(r,0) ∥2 ] ≤ 2r
2 τn −1 r−1 X X 2 2 y y y (y,max) 4τny (ηny wn(y,q) )2 4 (Qmax ) + σ τ η L w n n n n k n y=0
q=0
cr 2 N X (y,0) (y,0) 2 2 2 g y y (y,max) y 2 b + 4 (Qmax ) + σ τ η L w E [∥θ − θ ∥ ] + 4(L ) B n n n n n n j j
j=0
2 2 + (τ g − τny )2 (ηny wn(y,max) )2 4 (Qmax ) + σ n n
(82)
r−1 X g y y 2 y (y,max) 4 max 2 2 ≤r 64τ (τn Ln ) (ηn wn ) (Qn ) + σn y=0
+ 32(τny Lyn ηny wn(y,max) )2
cr N X
(y,0)
EB [∥θj
2 2 2 ∥ ] + 8 (τ g − τny )ηny wn(y,max) (Qmax ) + σ n n
(y,0) 2
− θbj
(83)
j=0
≤r
r−1 X y=0
64τ |
g
2 max max 4 (τnmax Lmax n ) (ηn wn )
2 2 (Qmax n ) + σn
{z
}
C1 r
max max 2 + 32(τnmax Lmax n ηn w n )
|
{z
C2
}
c N X
(y,0) (y,0) 2 EB [∥θj − θbj ∥2 ] + 8 ((τ g − τnmax )ηnmax wnmax )
2 2 (Qmax n ) + σn
(84)
j=0
|
{z
}
C3
Notice that the expression in (84) can be expressed as cr r−1 N X X y C1 + C2 Arn ≤ r Aj + C 3 , y=0
(85)
j=0
(r,0) (r,0) (y,0) (y,0) where Arn = EB [∥θbn − θn ∥2 ] and Ayj = EB [∥θbj − θj ∥2 ]. Assuming that ML model parameters are initialized to (0,0) (0,0) cr . The expression in (85) appears to admit some be the same, i.e., θn = θbn , we have that A0n = 0 and A0j = 0 ∀j, n ∈ N recursive relationship, which we can examine more closely for r = {1, · · · , 5} to obtain the following: X A1n ≤ C1 + C2 A0j + C3 ≡ C1 + C3 (86) d 0 j∈N
A2n ≤ 2
1 X y=0
C1 + C2
X y d j∈N
Ayj + C3 = 2 C1 + C2
X d 0 j∈N
A0j + C3 + 2 C1 + C2
X d 1 j∈N
A1j + C3
27
= 2 C1 + C2
X X A0j + C3 + 2 C1 + C2 C1 + C 2 A0ĵ + C3 + C3
X d 0 j∈N
d 1 j∈N
d 0 ĵ∈N
X X X d c1 + C3 22 + 2C2 N c1 + 2C2 R ≤ C1 22 + 2C2 N A0j + 2C2 C2 A0ĵ ≤ (C1 + C3 ) 22 + 2C2 N
d 1 j∈N
d 1 j∈∈N
2 2 2 d d d d d d R R R R R R 3 + 3C2 N + 3C2 N (2 + 2C2 N ) + C3 3 + 3C2 N + 3C2 N (2 + 2C2 N ) 2 2 2 d d R R ≡ (C1 + C3 ) 3 + (3 + 3 × 2 )C2 N + (3 × 2)(C2 N ) d d d d d d R (22 + 2C N R ) + 4C N R (32 + 3C N R + 3C N R (22 + 2C N R )) A4 ≤ (C1 + C3 ) 42 + 4C2 K + 4C2 N 2 2 2 2 2
A3n ≤ C1
(87)
d 1 ĵ∈N
2
(88)
n
d d d R + (4 × 2 + 4(3 + 3 × 22 ))(C N R )2 + 4 × 3 × 2(C N R )3 ≡ (C1 + C3 ) 42 + (4 + 4 × 22 + 4 × 32 )C2 N (89) 2 2 d d R + (5 × 2 + 5(3 + 3 × 22 ) + 5(4 + 4 × 22 + 4 × 32 ))(C N R )2 A5n ≤ (C1 + C3 ) 52 + (5 + 5 × 22 + 5 × 32 + 5 × 42 )C2 N 2 2 3 4 d d R R + (5 × 3 × 2 + 5(4 × 2 + 4 × 3 + 4 × 3 × 2 ))(C2 N ) + 5 × 4 × 3 × 2(C2 N ) (90) d R as a single In the expansions above, we iteratively expand ∀y > 0 until y = 0 so that A0j = 0 appears. If we treat C2 N d R variable, then we can see that the number of additive coefficients per unique power of C2 N follows the binomial coefficients. Simultaneously, we can bound each individual additive coefficient by rr , as an example see the initial bound for A5k in (90) wherein r! ≡ 5! ≤ 5 × 4 × 3 × 22 ≤ 55 ≡ rr . Together, these two points enable a general upper bound given any r ∈ R, r ≥ 0 as follows: X r−1 r r d R )y r (C2 N (91) Arn ≤ (C1 + C3 ) y y=0 Leveraging the result of (91) into (84) and returning to the original statement in (73) yields b (r,0) ) − F (Θ(r,0) ) ≤ F (Θ
cr N X 1 n=0
2
Lr + 1 ∥∇n F (θn(r,0) )∥2 + (C1 + C3 ) 2
X r−1 r r y d R r (C2 N ) , y y=0
(92)
which completes the proof. ■
28
A PPENDIX C P ROOF OF T HEOREM 1 Theorem 1. (Separable First Order Stationary Points) Assuming τnr > 0 at active devices (n ∈ N r , r ∈ R), then the sum of first order stationary points across all devices in all global aggregations r ∈ R can be bounded as follows: R−1 X
cr N X
∥∇n F (Θ(r,0) )∥2 n
r=0 n=0r n∈N
≤
R−1 X
r
"
c N X
υnr
r=0 n=0r n∈N
where υnr =
(23)
# max 2 r F (Θ(0,0) ) 2 + 2 (Qn ) + σn Υn , RN r
1 r,eff r (r,max) τnr,eff ηnr w(r) ηn wn n − τn 2
−1 ,
(24)
Υrn = (τnr,eff Lrn )2 (ηnr wn(r,max) )3 + Lr (τnr,eff ηnr wn(r,max) )2 ,
(25) k
n A τnr,eff = τnr prn represents the effective local training iterations as a result of the survival function prn = e−(rn ) derived A from (1), and rn is the global round immediately following the entry of device n into the network. This requires that 0 < ρ < 1 W−1 − 2√ + 12 e
and 0 < ηnr < 2τ1r µ , given an SGD with momentum parameter ρ, and a proximal SGD update scaling factor n 1 represents the −1 branch of the Lambert W function [52]. µ. Note that W−1 − 2√ e e
Proof. From Assumption 1, we have at the global level that Lr 2 F (Θ(r+1,0) ) − F (Θ(r,0) ) ≤ ∇F (Θ(r,0) )T Θ(r+1,0) − Θ(r,0) + Θ(r+1,0) − Θ(r,0) . 2 (r,q)
(r,q)
to represent gn (Θn
Using gn steps
) as in the proof of Lemma 1, we can then bound (93) via the following sequence of
F (Θ(r+1,0) ) − F (Θ(r,0) ) 2 r r cr cr τn −1 τn −1 N N X (i) X Lr X (r,0) X (r,0) T (r,0) r (r,q) (r,q) (r,0) r (r,q) (r,q) (r,0) ∇n F (Θn ) θn − ≤ ηn wn gn − θn + θ − ηn wn gn − θn 2 n=0 n n=0 q=0 q=0 r r τn −1 τn −1 X (ii) X 2 Lr X r X (r,0) T r (r,q) (r,q) ≤ ∇n F (Θn ) − ηn wn gn + τn (ηnr wn(r,q) )2 gn(r,q) 2 r r q=0 q=0 n∈N
(iii)
=
X
r τn −1
−
X
gn(r,q) − gn(r,0) + gn(r,0)
q=0
n −1 X τX
n∈N r
(95)
(96)
r
ηnr wn(r,q) ∇n F (Θ(r,0) )T n
r
=
(94)
n∈N
n∈N r (iv)
(93)
ηnr wn(r,q) ∇n F (Θ(r,0) )T n
gn(r,0) − gn(r,q)
q=0
τn −1 2 Lr r X r (r,q) 2 (r,q) + τ (η w ) gn 2 n q=0 n n
r τn −1 Lr r X r (r,q) (r,0) T (r,0) − ηn wn ∇n F (Θn ) gn + τn (ηnr wn(r,q) )2 2 q=0 q=0
(97)
r τn −1
X
gn(r,q) (98)
(v)
≤
r τn −1
X X n∈N r
r τn −1
q=0
ηnr wn(r,q)
1 1 ∥∇n F (Θ(r,0) )∥2 + ∥gn(r,0) − gn(r,q) ∥2 n 2 2 r
τn −1 Lr r X T (r,0) − ηnr wn(r,q) ∇n F (Θ(r,0) ) g + τ (ηnr wn(r,q) )2 n n n 2 q=0 q=0
X
gn(r,q)
2
,
(99)
Pτnr −1 r (r,q) (r,q) (r+1,0) (r,0) where (i) is via the update rule, i.e., θn = θn − q=0 ηn wn gn across all components of Θ(r,0) , (ii) is from PN −1 P (r,0) N −1 ( i=0 xi )2 ≤ N i=0 x2i and uses the fact that exited devices have τnr = 0, (iii) introduces ±gn , (iv) rearranges the 1 2 1 2 expression from (iii), and (v) leverages ab ≤ 2 a + 2 b . Next, taking the expectation with respect to a mini-batch Br of data on both sides of (99) yields: EBr [F (Θ(r+1,0) ) − F (Θ(r,0) )] = F (Θ(r+1,0) ) − F (Θ(r,0) )
2
29
r
n −1 X τX
(vi)
≤
n∈N r
ηnr wn(r,q)
q=0
1 1 (r,0) 2 (r,q) (r,0) 2 ∥∇n F (Θn )∥ + EBr [∥gn − gn ∥ ] 2 2
r τn −1 2 Lr r X r (r,q) r (r,q) (r,0) T (r,0) − τ η w EBr ηn wn ∇n F (Θn ) EBr [gn ] + 2 n q=0 n n q=0 r τn −1
X
gn(r,q)
2
(100)
r
n −1 X τX
(vii)
≤
n∈N r r τn −1
X
−
ηnr wn(r,q)
q=0
r r r (r,max) 2 1 2 2 2 ∥∇n F (Θ(r,0) )∥ + 2 Q + σ n max n τn ηn Ln wn 2
L ηnr wn(r,q) ∥∇n F (Θ(r,0) )∥2 + n
X 1
≤
2
n∈N r r τn −1
X
−
τnr
2
q=0 (viii)
r
r τn −1
X
ηnr wn(r,q)
2
4 Q2max + σn2
(101)
q=0
r r 2 r (r,max) 3 2 2 2 τnr ηnr wn(r,max) ∥∇n F (Θ(r,0) )∥ + 2 Q + σ ηn wn n max n (τn Ln )
2 r r (r,max) 2 2 2 r τ η w Q + σ ηnr wn(r,q) ∥∇n F (Θ(r,0) )∥ + 2L n n n max n n
(102)
q=0 (ix)
=
X 1 2
n∈N r
X
+
r τn −1
τnr ηnr wn(r,max) −
X
ηnr wn(r,q) ∥∇n F (Θ(r,0) )∥2 n
q=0
2
2 Q2max + σn
2
(τnr Lrn )
ηnr wn(r,max)
3
2 + Lr τnr ηnr wn(r,max) ,
(103)
n∈N r
where (vi) is from taking the expectation of both sides and the linearity of expectation, (vii) leverages Lemma 1 and (r,max) (r,q) and simplifies terms, and (ix) combines like terms together. Assumption 4, (viii) takes wn ≤ wn Rearranging the terms in (103) yields r
n −1 X τX
∥∇n F (Θ(r,0) )∥2 ≤ F (Θ(r,0) ) − F (Θ(r+1,0) ) n
2 3 2 2 2 r r 2 r (r,max) r r (r,max) 2 Qmax + σn (τn Ln ) ηn wn + L τn ηn wn
n∈N r
+
1 ηnr wn(r,q) − τnr ηnr wn(r,max)
q=0
X
(104)
n∈N r
PNcr P and, using the full expression n=0,n∈N r in place of n∈N r , we can take the average of (104) over the global aggregation rounds r ∈ {0, · · · , R − 1} to obtain " τnr −1 R−1 1 r r (r,max) 1 1 X X X r (r,q) (r,0) 2 ηn wn − τn ηn wn ∥∇n F (Θn )∥ ≤ F (Θ(0,0) ) − F (Θ(R,0) ) R r=0 2 R q=0 n∈N r (105) # R−1 3 2 X X 2 + 2 Q2max + σn2 (τnr Lrn ) ηnr wn(r,max) + Lr τnr ηnr wn(r,max) . r=0 n∈N r
cr (via the notation Summarizing this result in terms of all historical network devices N (r,0) ∇n F (Θn ) then yields R−1 X
cr N X
∥∇n F (Θ(r,0) )∥2 ≤ n
r=0 n=0r n∈N
R−1 X
r
cr τn −1 N X X
r=0 n=0r n∈N
2
2 Q2max + σn
2
(τnr Lrn )
ηnr wn(r,max)
PNcr
3
1 ηnr wn(r,q) − τnr ηnr wn(r,max)
q=0
2
+ Lr τnr ηnr wn(r,max)
n=0,n∈N r ) as well as the gradients
−1 "
F (Θ(0,0) ) + RN r (106)
# 2
. (r,0)
In order for the result in (106) to hold, the network must ensure that the coefficients on ∥∇n F (Θn positive. Thus, we require:
)∥2 from (105) are
τqr −1
1 ηnr wn(r,q) − τnr ηnr wn(r,max) > 0. 2 q=0
X
(107)
30
We can express (107) in a simplified form via the following steps: (x)
r τn −1
⇒
X
1 r r (r,max) τ η w 2 n n n
ηnr wn(r,q) >
q=0 (xi)
r τn −1
⇒
X
wn(r,q) >
q=0 (xii)
⇒ τnr wrn >
(xiii)
⇒ wrn >
(108)
1 r r,max τ w 2 n n
(109)
1 r (r,max) τ w 2 n n
(110)
1 (r,max) w , 2 n
(111) (r,q)
where (x) rearranges (107), (xi) divides both sides by ηnr , (xii) uses wrn to denote the average wn within some global P (r,q) r r r aggregation round r and notes that q wn ≡ τn wn , and (xiii) divides by τn . (r,q) Since the values for wn depend on the specific local optimizer used for ML model training, we next analyze the condition in (111) for three popular optimizers: (i) standard SGD, (ii) SGD with momentum, and (iii) proximal SGD. Pτnr −1 (r,q) (r,q) (r,τ r ) (r,0) (r,q) • Standard SGD This method has update rule: θn n = θn − ηnr q=0 wn gn , with wn = 1 ∀r, q, n. Thus, (r,max) 1 1 r wn = 1 and 2 wn = 2 ∀r, n. Therefore, (111) holds ∀r, n. •
(r,τ r )
r
(r,τ r −1)
SGD with momentum This method has a momentum buffer: un n r = ρu(r,τrn −1) − gn n r , where ρ is a tuning (r,τ ) (r,τ −1) (r,τ ) parameter such that 0 < ρ < 1 [50], and a subsequent update rule: θn n = θn n − ηnr un n . Recursively expanding r the momentum buffer for all q ∈ {0, · · · , τn − 1} yields r (r,τn )
(r,τ r −1)
un
(r,τ r −1)
= ρun n + gn n r (r,τ −2) (r,τ r −2) (r,τ r −1) = ρ ρun n + gn n + gn n .. .
(112) r τn −1
=
r
X
ρτn −1−q gn(r,q) .
q=0
Next, combining (112) with the update rule and then recursively expanding yields r τn −1
(r,τ r ) (r,τ r −1) θn n = θn n − ηnr
X
r
ρτn −1−q gn(r,q)
q=0 (r,τ r −2) = θn n − ηnr
r τX n −2
r τn −1 r ρτn −2−q gn(r,q) +
q=0
X
r
ρτn −1−q gn(r,q)
(113)
q=0
.. . r τn −1
= θn(r,0) − ηnr
s XX
ρs−q gn(r,q) .
s=0 q=0 (r,t)
By inspection, wn
=
Pτnr −1 s≥q
ρs−q and therefore 1−ρ wn(r,q) =
r τn −q
1−ρ
.
(r,max)
(114) (r,q)
To analyze the impact of (114) on (111), we first find wn . Since 0 < ρ < 1, then the maximum for wn when τnr → ∞ and q → 0. Thus, we have the following asymptotic upper bound: wn(r,max) ≤
1 . 1−ρ
appears
(115)
On the other hand, the average wrn can be found as follows: r
wrn =
τn −1 X r 1 (1 − ρτn −t ) r τn (1 − ρ) q=0
(116)
31
r τn −1 r X 1 r τn −q = r τ −ρ ρ τn (1 − ρ) n q=0 r 1 τn r 1 − (ρ) 1 r τn τ −ρ = r τn (1 − ρ) n 1 − ρ1
(117)
(118)
r
1 1 ρτn +1 − ρ = . + r 1 − ρ τn (1 − ρ)2
(119)
Examining the convergence condition (111) with the result of wrn in (119) and the expression of wnr,max in (115) results in the following: r 1 1 1 1 ρτn +1 − ρ 1 r ≥ wn = + > wn(r,max) , (120) 1 − ρ τnr (1 − ρ)2 21−ρ 2 which after some rearrangement yields an updated convergence condition: r
h(τnr ) = ρτn +1 +
τ rρ τnr − ρ − n ≥ 0. 2 2
Taking the limit of h(τnr ) at the two extreme (i.e., τnr → 0 and τnr → ∞) yields two conditions: τ →0 h(τnr ) = ρ1 − ρ ≥ 0, r τ →∞ τ h(τnr ) = n (1 − ρ) − ρ ≥ 0. 2
(121)
(122) (123)
The first condition in (122) is satisfied forr momentum parameters constrainedr such that 0 < ρ < 1. Similarly, the τ τ condition in (123) is obviously true because 2n (1−ρ) → ∞ as τnr → ∞ and thus 2n (1−ρ) > ρ immediately for 0 < ρ < 1. If we can next show that h(τnr ) is a strictly increasing function for τnr ≥ 1, then we will have shown that the convergence condition in (121) is spanned by (122) and (123), and thus holds ∀τnr > 0 and ∀ρ < 1/2. We can show that h(τnr ) is a r dh(τn ) strictly increasing function by showing that dτ r > 0. In this regard, we first take the derivative of h(τnr ) with respect n to τnr obtaining: r dh(τnr ) 1 ρ = ρτn +1 log(ρ) + − . r dτn 2 2
(124)
r
Since the ρτn +1 log(ρ) term in (124) is a negative value that decreases in magnitude as τnr → ∞, (124) is an increasing quantity with respect to τnr . We next show the conditions for which (124) is positive at the lower limit by examining (124) at τnr → 0, obtaining: dh(τnr ) 1 ρ = ρ log(ρ) + − > 0. r dτn 2 2
(125)
Since (125) contains a product log term, we can reformulate to obtain a convergence condition on ρ based on the Lambert W function [52] as follows: 1 1 (xiv) ⇒ ρ log(ρ) − <− , (126) 2 2 1 1 (xv) ρ ⇒ √ log(ρ) − <− √ , (127) 2 e 2 e ρ 1 (xvi) log √ρe ⇒ log √ e <− √ , (128) e 2 e ρ 1 (xvii) ⇒ log √ < Wω̃ − √ , (129) e 2 e (xviii)
1 Ww̃ − 2√ + 12 e
(xix)
1 W−1 − 2√ + 21 e
⇒ ρ<e
⇒ ρ<e
,
(130)
,
(131)
where (xiv) rearranges (125), (xv) multiplies √1e on both sides, (xvi) uses the logarithmic equivalent of the left hand side of (xv), (xvii) uses the definition of the Lambert W function, (xviii) rearranges the form of (xvii), and (xix) chooses the only feasible real branch (the −1 branch) of the Lambert W function [52].
32
W
1 − √ +1
To summarize, the above analysis showed that, for 0 < ρ < e −1 2 e 2 , h(τnr ) is an increasing function of τnr and that h(τnr ) > 0 when ∀τnr > 0. Thus, we have showed that (111) holds for SGD with momentum. •
Proximal SGD This method relies on a parameter 0 < µ < 1 [51] and has update rule: r r r r (r,τn ) (r,τn −1) (r,τn −1) (r,τn −1) r (r,0) θn = θn − ηn gn + µ(θn − θn ) .
(132)
Subtracting θ (r,0) on both sides of (132) yields r (r,τn )
θn
(r,τ r −1) (r,τ r −1) − θn(r,0) − ηnr gn n + µ(θn n − θn(r,0) ) r (xx) (r,τn −1) (r,τ r −1) r (r,0) = (1 − ηn µ) θn − θn − ηnr gn n r (r,τn −1)
− θn(r,0) = θn
(xxi)
=
(133) (134)
r τn −1
−ηnr
X
r
(1 − ηnr µ)τn −1−q gn(r,q) ,
(135)
q=0 r (r,τn −1)
where (xx) follows from rearranging, and (xxi) is from recursively expanding θn yields: r τn −1 X r r (r,τn ) (r,0) r θn = θn − ηn (1 − ηnr µ)τn −1−q gn(r,q) ,
(r,0)
− θn
. Rearranging (135)
(136)
q=0 (r,q)
and, by inspection, wn
r
= (1 − ηnr µ)τn −1−q . (r,q)
To satisfy (111), we first find the maximum and average for wn
, resulting in r
wn(r,max) = max(1 − ηnr µ)τn −1−q < 1,
(137)
as 0 < ηnr < 1 and 0 < µ < 1 so that 0 < ηnr µ < 1, and r
wrn =
τn −1 r 1 X (1 − ηnr µ)τn −1−q r τn q=0
(138)
τ r −1
r
n (1 − ηnr µ)τn −1 X (1 − ηnr µ)−q = τnr q=0 τnr 1 r 1 − r τn −1 r 1−η µ (1 − ηn µ) n = 1 τnr 1− r
(139)
(140)
1−ηn µ
i 1 h τr = r r 1 − (1 − ηnr µ) n ηn µτn
(141) (r,max)
via algebraic manipulation and the sum of finite geometric series. Formatting the above wn SGD in the form of (111) yields: i 1 1 h 1 τr wrn = r r 1 − (1 − ηnr µ) n > > wn(r,max) , ηn µτn 2 2
and wrn for proximal (142)
and, simplifying returns the following condition for convergence: ηnr µτnr . 2 We next expand the left hand side of (143) via the binomial theorem to obtain r r r τn X r τn τnr −q τ r τn r q r r (1 − ηn µ) = 1 (−ηn µ) = 1 − τn (ηn µ) + n (ηnr µ)2 + Enr q 2 q=0 r
(1 − ηnr µ)τn < 1 −
where we define
(143)
(144)
r
Enr =
τn r X τ n
q=3
q
(−ηnr µ)q ,
(145)
33
as an error term associated with exponents ≥ 3. Using (144) and (145), we will next show that Enr ≤ 0. Via the ratio test, we can compare the magnitude of individual terms in Enr , obtaining τr!
(ηnr µ)q q!(τ rn−q)! n
τr! (ηnr µ)q+1 (q+1)!(τnr −q−1)! n
=
1 q+1 > 1, ηnr µ τnr − q
(146)
as a result of τnr ≥ q and only for ηnr < µτ1 r . Therefore, n r r τn τn r q − (ηn µ) + (ηnr µ)q < 0 q q+1 for 3 ≤ q ≤ τnr and q ∈ 2Z + 1, and
(147)
Enr ≤ 0,
(148)
r which enables us to upper bound (1 − ηnr µ)τn as follows: r
(1 − ηnr µ)τn < 1 − τnr (ηnr µ) + (τnr ηnr µ)2 .
(149)
η r µτ r If we can show that the bound in (149) is still less than 1 − n 2 n from (143), then we will have proven the convergence
condition. In this regard, 1 − τnr (ηnr µ) + (τnr ηnr µ)2 < 1 − r r (xxii) τn ηn µ
⇒
2
(xxiii) 1
⇒
(xxiv)
2
ηnr µτnr 2
(150)
− (τnr ηnr µ)2 > 0
(151)
− τnr ηnr µ > 0
(152)
1 , 2τnr µ
(153)
⇒ ηnr <
where (xxii)-(xxiv) follow from algebra manipulations. To summarize, we have now shown that the convergence condition in (143) (and thus (111) as well) requires that ηnr < 2τ1r µ . Therefore, proximal SGD enables the convergence n in (106) for ηnr < 2τ1r µ . n
Thus, for (106) to converge for networks with devices that may employ a combination of (i) standard SGD, (ii) SGD with momentum, and/or (iii) proximal SGD as local optimizers, the network requires 0 < ρ < e
1 + 12 W−1 − 2√ e A kn
Finally, replacing τnr with the device failure probability adjusted τnr,eff = τnr prn , where prn = e−(rn ) noting that τnr,eff retains the same properties as τnr yields the result.
and 0 < ηnr < 2τ1r µ . n
and prn > 0 ∀n, r, and ■
34
A PPENDIX D S OLUTION TO O PTIMIZATION In order to obtain a solution for (P), we first transform it from a signomial program to a geometric one, which, after a logarithmic change of variables, becomes a convex program. To explain this methodology, we first present geometric programming preliminaries in Sec. D-A and then expand on the details of our transformations for the terms in (P) that violate geometric programming rules in Sec. D-B. A. Geometric Programming A standard GP is a non-convex problem formulated as minimizing a posynomial under posynomial inequality constraints and monomial equality constraints [68]: min g0 (y) y
s.t.
(154)
gi (y) ≤ 1, i = 1, · · · , I, fℓ (y) = 1, ℓ = 1, · · · , L, (n) (1) (n) (1) PMi β β β βℓ · · · ynℓ , ∀ℓ. The key idea is to transform such a problem di,m y1 i,m · · · yni,m , ∀i, and fℓ (y) = dℓ yP where gi (y) = m=1 1 n to a convex one via the log-sum-exp function, i.e., h(y) = log j=1 eyj where log denotes the natural logarithm. Thus GP in its standard format can be transformed into a convex program, specifically via a logarithmic change of variables and constants such that zi = log(yi ), bi,m = log(di,m ), bℓ = log(dℓ ), and via the application of log on the objective and constraints of (154). The result is as follows: M0 X ⊤ e(β0,m z+b0,m ) min log
z
m=1
s.t. log
Mi X
(155)
⊤
e(βi,m z+bi,m ) ≤ 0, i = 1, · · · , I,
m=1 ⊤ βℓ z + bℓ = 0, ℓ = 1, · · · , L,
h i⊤ i⊤ h (1) (n) (1) (n) where z = [z1 , · · · , zn ]⊤ , βi,m = βi,m , · · · , βi,m , ∀i, m, and βℓ = βℓ , · · · , βℓ , ∀ℓ. B. Optimization Problem Transformation Next, we revisit (P) and transform it from a signomial program to a geometric program. For ease of discussion, we reproduce (P) with the full expressions for all terms below: X X X X X X X r,M (P) : arg min ψG ξnr +ψ R Enr,Tx +ψ P Enr,P +ψ S ES (156) r ,τ r ,αr ,∀n Pnr ,ϕrS ,gn n n
r∈R n∈N r
|
{z
(a)
r∈R n∈N r
}
|
{z
(b)
r∈R n∈N r
}
|
{z
(c)
r∈R
}
|
{z
(d)
}
subject to ξnr =
γnr (r) (r,max) τnr,eff ηnr wn − 21 τnr,eff ηnr wn
"
1 2 2 F (Θ(0,0) ) + 2 (Qmax n ) + σn RN r #
(τnr,eff Lrn )2 (ηnr wn(r,max) )3 + Lr (τnr,eff ηnr wn(r,max) )2
Enr,Tx =
M Pr n n r,A2G , Rn,S r n Pn Mr,A2A , Rn,S
,
if ϕz,n = 0 or ϕrz,S = 0, n∈N r , r∈R, if ϕz,n > 0 and ϕrz,S > 0, n∈N r , r∈R,
(157)
(158)
3φn an B r 2 (gn ) , 2φ bn r r ESr,M = K H eϕs,z + K A PSr,A + K L dxy (ϕr−1 S , ϕS ),
(160)
0 ≤ Pnr ≤ P n , ∀r ∈ R, ∀n ∈ N r ,
(161)
Enr,P = τnr
E r,Tx αnr n r ≤ T max , Pn τnr (1 − αnr ) ≤ 0,
(159)
(162) (163)
35
αnr ∈ {0, 1},
(164)
0 ≤ ϕrx,S ≤ ϕmax x , ∀r ∈ R,
(165)
0 ≤ ϕry,S ≤ ϕmax y , ∀r ∈ R,
(166)
0 ≤ ϕrz,S ≤ ϕmax z , ∀r ∈ R, 4φ bn τnr ≤ , ∀r ∈ R r gn 6Bkn (hn kn + Dn + Y ) gnmin ≤ gnr ≤ gnmax , ∀r ∈ R, ∀n ∈ N r 0 ≤ τnr,eff ≤ τ g , ∀r ∈ R, ∀n ∈ N r ! ϕr−1 ϕrz,S z,S r,A PS ≥ − log 1 − max + log 1 − max . ϕz ϕz
(167) (168) (169) (170) (171)
In the following, we will convert (P) into a GP format, starting with the objective function (156). Our methodology involves approximating the terms that do not adhere to the GP format by bounding them with auxiliary variables and by iteratively refining a series of inner approximations. In this regard, we will use the variable ℓ to denote the ℓ-iteration of the approximation. Simultaneously, these auxiliary variables will be added to the objective function with multiplicative penalty coefficients to induce equality with the terms that they are bounding. Term (a) in Objective Function. For practical solvers, the denominator of ξnr in term (a) can lead to numerical instability and therefore convergence issues when τnr,eff → 0. As such, we introduce an ϵG > 0 on the order of O(10−6 ) to the denominator of ξnr and obtain: γnr . (172) (r) (r,max) + ϵG τnr,eff ηnr wn − 12 τnr,eff ηnr wn However, (172) contains a division over a posynomial, the result of which is not a posynomial, and thus is not yet in the form of GP. To this end, we leverage the AM-GM mean inequality (Lemma 2) to approximate the denominator with a monomial as follows: 1 (r,max) Ãrn (x) = τnr,eff ηnr w(r) w + ϵG ≥ − n 2 n (r) 1 (r,max) r,eff ℓ−1 r ηn (wn − 2rwn ℓ−1 )[τn ] (173) Ãn ([x ]) ℓ−1 r ϵGℓ−1 r,eff r r τ Ã x Ãn ([x n b̃ (x; ℓ) ≜ n ]) Ãrn xℓ−1 A , h iℓ−1 n r,eff τn (r)
(r,max)
> 0 and ϵG is a constant so that ϵG = [ϵG ]ℓ−1 . To summarize, we as, following the conditions of Theorem 1, wn − 21 wn thus convert the expression in (157) of term (a) in (P) into the following GP compatible format:
ξnr =
"
# max 2 1 (0,0) 2 r,eff r 2 r (r,max) 3 r r,eff r (r,max) 2 F (Θ ) + 2 (Qn ) + σn (τn Ln ) (ηn wn ) + L (τn ηn wn ) . b̃ r (x; ℓ) RN r A n γnr
(174)
Term (b) in Objective Function. Term (b) has a number of components that violate the GP format. Since the methodology for A2G and A2A paths is similar (with A2G coefficients swapped for their respective A2A coefficients), we will explain the conversion of Enr,Tx using A2G paths to demonstrate. Expanding the full form of Enr,Tx yields Mn Pnr
Enr,Tx =
B n,S log2
Pnr 1 + 2 PL r PL,A2G r,LoS,A2G r,LoS,A2G σ (µ d(ϕS ,ϕn ))α +η NLoS,A2G (1−Pn,S )) (ηLoS,A2G Pn,S
where d(ϕrS , ϕn ) =
q
(ϕrS,x − ϕn,x )2 + (ϕrS,y − ϕn,y )2 + (ϕrS,z − ϕn,z )2 ,
and r,LoS,A2G Pn,S =
1+ψ
Tx,A2G
× exp −β
Tx,A2G
h i −1 r,A2G Tx,A2G θn,S − ψ ,
,
(175)
(176)
(177)
as defined within the main manuscript. The expression in (175) poses several issues, namely the logarithm, the posynomials in r,A2G the denominator (further embedded within the logarithm), the negative variables, and the arcsin function embedded in θn,S in (177).
36
We begin by addressing the negative variables within the expression for Euclidean distance terms, i.e., d(ϕrS , ϕn )-terms. As r such, we first introduce an auxiliary variable, χr,D n,S > 0, to bound the squared Euclidean distance terms (i.e., the d(ϕS , ϕn )terms without the square root). Simultaneously, we also introduce a constraint to approximate the posynomial and negative terms within those expressions as follows: X 2 2 ϕrS,j − ϕn,j ≤ χr,D (d(ϕrS , ϕn )) = (178) n,S , j∈{x,y,z} 2 2 r + (ϕn,j ) j∈{x,y,z} ϕS,j ≤ 1, P r χr,D n,S + 2 j∈{x,y,z} ϕS,j ϕn,j
P
(179)
where (179) follows from rearranging (178). Since the constraint in (179) contains a division by posynomials, which is not in the GP format, we next approximate it with the AM-GM inequality (per Lemma 2) as follows: X r D̃n,S (x) = χr,D ϕrS,j ϕn,j ≥ (180) n,S + 2 j∈{x,y,z} r,D ℓ−1
b̃ r (x; ℓ) ≜ D n,S
r ℓ−1 χr,D ) n,S D̃n,S ([x] r,D ℓ−1 [χn,S ]
] n,S ! [χ r ℓ−1 D̃ ([x] n,S
r ϕrS,j D̃n,S ([x]ℓ−1 ) [ϕrS,j ]ℓ−1
)
Y j∈{x,y,z}
We thus obtain a GP compliant form for the constraint in (179): 2 P 2 r + (ϕn,j ) j∈{x,y,z} ϕS,j
r
ℓ−1
D̃ ([x] n,S
)
[ϕS,j ] ! 2ϕn,j r ℓ−1
.
≤ 1.
b̃ r (x; ℓ) D n,S
(181)
Next, we address the line-of-sight probability term in (177), starting with the absolute value term within the numerator of the arcsin operator. We introduce an auxiliary variable χr,z n,S > 0 and transform the absolute value as follows: |ϕrS,z − ϕn,z | ≤ χr,z n,S
(182)
r,z r − χr,z n,S ≤ ϕS,z − ϕn,z ≤ χn,S ,
(183)
where (183) follows from (182). The overall expression in (183) leads to the following two inequalities
and
ϕrS,z − ϕn,z ≤ χr,z n,S ϕrS,z ≤1 ϕn,z + χr,z n,S
(184)
ϕrS,z − ϕn,z ≥ −χr,z n,S ϕn,z ≤ 1. ϕrS,z + χr,z n,S
(185)
Since these above two expressions contain posynomial denominators, we first convert them into a monomial form as follows: r,z ℓ−1
r,+ϕn,zℓ−1 b̃ r,+ (x; ℓ) ≜ D̃r,+ ([x]ℓ−1 ) D̃n,S r,+ ([x] ) D̃n,S (x) = ϕn,z + χr,z ≥ D n,S n,S n,S
r,+ ℓ−1 χr,z ) n,S D̃n,S ([x] r,z ℓ−1 [χn,S ]
] n,S ! [χ r,+ D̃
n,S
([x]ℓ−1 )
.
(186)
.
(187)
and r
b̃ r,− r,− D̃n,S (x) = ϕrS,z + χr,z n,S ≥ D n,S (x; ℓ) ≜ Thus, we have GP-compliant inequalities:
r,− ϕrS,z D̃n,S ([x]ℓ−1 ) [ϕrS,z ]ℓ−1
ϕrS,z b̃ r,+ (x; ℓ) D n,S
and
ϕn,z r,− b̃ (x; ℓ) D n,S
D̃
n,S
r,z ℓ−1
ℓ−1
[ϕS,z ] ! r,−
([x]ℓ−1 )
r,− ℓ−1 χr,z ) n,S D̃n,S ([x] r,z ℓ−1 [χn,S ]
] n,S ! [χ r,− D̃
n,S
([x]ℓ−1 )
≤1
(188)
≤ 1.
(189)
37
r,D The auxiliary variables χr,z n,S and χn,S together enable updating the arcsin expression as 3 r,z r,z χr,z χ χ 1 n,S n,S n,S arcsin q ≈q + q , r,D r,D 6 χn,S χn,S χr,D n,S
(190)
where the approximation consists of the first three terms of the Taylor series [80] as the arcsin function itself is neither a monomial nor a posynomial [73]. The penultimate issue in (177) is then the exponential function on the denominator. As the exponential function is neither a posynomial nor a monomial [73] and direct application of AM-GM inequality preserves the exponential function, we introduce a simplifying variable χ br,Pr n,S to act as an equality constraint and substitute, i.e., 3 r,z r,z χ χ 1 Tx,A2G 180 n,S n,S Tx,A2G Tx,A2G (191) ψ + q χ br,Pr , q +β n,S = exp −β r,D r,D π 6 χn,S χn,S 3 r,z r,z Tx,A2G χn,S 180β 1 χn,S Tx,A2G Tx,A2G log(b χr,Pr ψ = 0, (192) + q −β q n,S ) + r,D r,D π 6 χ χ n,S
n,S
where (192) takes the logarithm of (191) and then rearranges the resulting expression. Next, since equality constraints on posynomials (and exponential/logarithm functions) are not in the format of GP, we convert it to a pair of inequality constraints Pr enabled by an auxiliary variable χr,Pr > 0. Thus obtaining n,S > 0 and a small constant ϵ 3 r,z r,z χn,S 180β Tx,A2G χn,S 1 Tx,A2G Tx,A2G Pr log(b χr,Pr ψ ≥ χr,Pr (193) + q q −β n,S ) + n,S − ϵ , r,D r,D π 6 χ χ n,S
n,S
3 r,z r,z χ χ 1 n,S n,S Tx,A2G Tx,A2G Pr ψ ≤ χr,Pr + q −β q n,S + ϵ , r,D r,D 6 χn,S χn,S
log(b χr,Pr n,S ) +
Tx,A2G
180β π
(194)
which, after rearranging and using the Padé approximation for log(b χr,Pr br,Pr n,S ) ≈ χ n,S − 1 [72], yields: Tx,A2G Tx,A2G χr,Pr ψ +1 n,S + β !
≤1
3
χr,z n,S
Tx,A2G
180β χ br,Pr n,S + π
q
χr,D n,S
+ 16
χr,z n,S
q
180β χ br,Pr n,S + π
r,z qχn,S + 1 6 χr,D n,S
+ ϵPr
χr,D n,S
Tx,A2G
χr,z q n,S χr,D n,S
(195)
!3 ≤ 1.
Tx,A2G ψ Tx,A2G + 1 + ϵPr χr,Pr n,S + β
(196)
Both (195) and (196) contain posynomial denominators and thus are not yet in the format of GP. As such, we next perform posynomial condensation via the AM-GM inequality to obtain the following monomial denominators: 3 r,z r,z Tx,A2G χn,S 180β 1 χn,S Pr Q̃r,+ br,Pr + q q +ϵ ≥ n,S (x) = χ n,S + r,D r,D π 6 χ χ n,S
r,Pr ℓ−1 ] n,S r,+ Q̃ ([x]ℓ−1 ) n,S
n,S
[χ b
r,+
b̃ (x; ℓ) ≜ Q n,S
r,+ ℓ−1 χ br,Pr ) n,S Q̃n,S ([x] ℓ−1 [b χr,Pr n,S ]
q r,z r,D ℓ−1 Q̃r,+ n,S ([x] )χn,S / χn,S ℓ−1 q r,D χr,z / χ n,S n,S
!
ϵPr ℓ−1 ℓ−1 Q̃r,+ Q̃r,+ ) n,S ([x] ) n,S ([x]
r ℓ−1 r,z r,D 180β Tx,A2G χ / χ π n,S n,S r,+ Q̃ ([x]ℓ−1 ) n,S
30β Tx,A2G π
3 q Q̃r,+ ([x]ℓ−1 ) χr,z / χr,D n,S n,S n,S " # ℓ−1 3 q r,D r,z χn,S / χn,S
" χ Q̃
r,z / n,S
r χ
r,D n,S
3 #ℓ−1
r,+ ([x]ℓ−1 ) n,S
,
(197)
38
as ϵPr is a constant, for the denominator in (197) and r,Pr Tx,A2G Tx,A2G Q̃r,− ψ + 1 + ϵPr ≥ n,S (x) = χn,S + β r,Pr ℓ−1
b̃ r,− (x; ℓ) ≜ Q n,S
r,− ℓ−1 χr,Pr ) n,S Q̃n,S ([x] r,Pr ℓ−1 [χn,S ]
[χ ] n,S ! r,− Q̃
n,S
([x]ℓ−1 )
β Tx,A2G ψ Tx,A2G r,− ℓ−1 )
ℓ−1 Q̃n,S ([x] Q̃r,− ) n,S ([x]
ϵPr
1 r,−
ℓ−1 Q̃n,S ([x] Q̃r,− ) n,S ([x]
ℓ−1 )
r,−
ℓ−1 Q̃n,S ([x] Q̃r,− ) n,S ([x]
ℓ−1 )
,
(198) as β Tx,A2G , ψ Tx,A2G , 1, and ϵPr are constants, for the denominator in (198). Substituting the monomials in (197) and (198) into (195) and (196), respectively, then yields the following GP compliant inequalities: Tx,A2G Tx,A2G χr,Pr ψ +1 n,S + β
b̃ r,+ (x; ℓ) Q n,S χr,z n,S
Tx,A2G
180β χ br,Pr n,S + π
≤ 1,
χr,D n,S
!3
χr,z n,S
+ 61
q
(199)
q
χr,D n,S
≤ 1.
b̃ r,− (x; ℓ) Q n,S
(200)
r,LoS,A2G > 0 to abstract as follows: Returning to Pn,S in (177), we introduce χr,LoS n r,LoS,A2G Pn,S =
1 1 + ψ Tx,A2G χ br,Pr n,S
≤ χr,LoS , n
(201)
≤ 1.
(202)
which, after re-arranging, gives: 1 χr,LoS + ψ Tx,A2G χr,LoS χ br,Pr n n n,S
As before, the denominator in (202) is a posynomial and thus not yet in the format of GP. Leveraging posynomial condensation via AM-GM inequality, we again obtain: R̃nr,LoS,A2G (x) = χr,LoS + ψ Tx,A2G χr,LoS χ br,Pr n n n,S ≥ b̃ r,LoS,A2G (x; ℓ) ≜ R n
R̃nr,LoS,A2G ([x]ℓ−1 ) χr,LoS n
r,LoS ℓ−1 [χn ] ! r,LoS,A2G
r,LoS,A2G ([x]ℓ−1 ) χ br,Pr χr,LoS n n,S R̃n r,LoS r,Pr ℓ−1 [χn χ bn,S ]
([x]ℓ−1 )
R̃n
[χr,LoS ]ℓ−1 n
!ψ
r,Pr ℓ−1 Tx,A2G [χr,LoS χ ] b n n,S r,LoS,A2G R̃n ([x]ℓ−1 )
(203) ,
as ψ Tx,A2G is a constant. Thus, returning to (202), we have the inequality: 1
≤1
r,LoS,A2G
b̃ R n
(204)
(x; ℓ)
r,LoS,A2G As we also consider NLoS involving −Pn,S , we must introduce a secondary auxiliary variable χr,NLoS > 0 such that n r,LoS,A2G 1 − Pn,S =1−
1
≤ χr,NLoS , n
(205)
≤ 1.
(206)
1 + ψ Tx,A2G χ br,Pr n,S
which, after re-arranging yields ψ Tx,A2G χ br,Pr n,S r,NLoS χr,NLoS + ψ Tx,A2G χ br,Pr n n,S χn
Converting the denominator in (206) into a GP-compliant form yields: r,NLoS R̃nr,NLoS,A2G (x) = χr,NLoS + ψ Tx,A2G χ br,Pr ≥ n n,S χn r,NLoS,A2G
b̃ R n
(x; ℓ) ≜
χr,NLoS R̃nr,NLoS,A2G ([x]ℓ−1 ) n [χr,NLoS ]ℓ−1 n
r,NLoS ℓ−1 [χn ] ! r,NLoS,A2G
([x]ℓ−1 )
R̃n
(207)
r,Pr r,NLoS ℓ−1 χ ] n,S n r,NLoS,A2G R̃n ([x]ℓ−1 )
ψ Tx,A2G [χ b
r,NLoS r,NLoS,A2G χ br,Pr R̃n ([x]ℓ−1 ) n,S χn r,NLoS ℓ−1 [b χr,Pr ] n,S χn
!
,
39
as ψ Tx,A2G is a constant. Thus, we have the following inequality ψ Tx,A2G χ br,Pr n,S b̃ r,NLoS,A2G (x; ℓ) R n
≤1
(208)
Returning to the full expression for Enr,Tx in (175), we thus have: Mn Pnr
Enr,Tx =
.
B n,S log2 1 +
σ2
µPL
Pnr αPL,A2G q χr,D n,S
(209)
η LoS,A2G χr,LoS + η NLoS,A2G χr,NLoS n n
Approximating the log2 term in (209) via the [2/1]-Padé approximation from [72] enables: PL q r,D αPL,A2G NLoS,A2G r,NLoS Enr,Tx ≈ 2Mn log(2)σ 2 η LoS,A2G χr,LoS (µ + η χ χn,S ) n n q PL r,D αPL,A2G NLoS,A2G r,NLoS r × 3σ 2 η LoS,A2G χr,LoS + η χ (µ χ ) + 2P n n n n,S −1 q PL r,D αPL,A2G NLoS,A2G r,NLoS r B n,S 6σ 2 η LoS,A2G χr,LoS (µ χ ) . + η χ + P n n n n,S
(210)
Since the denominator in (210) is a posynomial, we convert in into the GP-format as follows: PL αPL,A2G r,D αPL,A2G /2 r 2 LoS,A2G r,LoS r NLoS,A2G r,NLoS + Pn ≥ T̃n,S (x) = B n,S 6σ η χn +η χn µ χn,S " # PL,A2G /2 ℓ−1 αPL,A2G r,LoS r,D α 6B n,S σ 2 η LoS,A2G µPL χn χ n,S
(
αPL,A2G /2
)
(
)
T̃ r ([x]ℓ−1 ) n,S
ℓ−1 r χr,LoS χr,D ([x] ) T̃n,S n,S b̃ r (x; ℓ) ≜ n T n,S αPL,A2G /2 ℓ−1 r,D χr,LoS χ n n,S
# " PL,A2G /2 ℓ−1 αPL,A2G r,NLoS r,D α χn χ 6B n,S σ 2 η NLoS,A2G µPL n,S
(
PL,A2G
)
(
)
T̃ r ([x]ℓ−1 ) n,S
α /2 ℓ−1 r,D r χr,NLoS ([x] ) T̃n,S χ n n,S αPL,A2G /2 ℓ−1 r,NLoS r,D χn χn,S
r ℓ−1
ℓ−1 r Pnr T̃n,S ([x] ) ℓ−1 [Pnr ]
[Pn ] ! Bn,S r ℓ−1 T̃
n,S
([x]
)
.
(211) Thus, we finally have the following GP-compliant expression for EnrTx as follows: 2 eff,A2G r,A2G r 2Mn log(2)σ 2 η eff,A2G Gr,A2G 3σ η G + 2P n n,S n,S Enr,Tx ≈ , (212) r b̃ T n,S (x; ℓ) αPL,A2G q r,A2G r,D eff,A2G LoS,A2G r,LoS NLoS,A2G r,NLoS PL where η = η χn χn and Gn,S = µ +η χn,S To summarize, we obtain the following GP-compliant constraint and objective term: P
j∈{x,y,z}
ϕrS,j
2
2
+ (ϕn,j )
b̃ r (x; ℓ) D n,S
≤ 1,
ϕrS,z r,+
≤ 1, b̃ (x; ℓ) D n,S ϕn,z ≤ 1, r,− b̃ (x; ℓ) D
(213) (214) (215)
n,S
Tx,A2G Tx,A2G χr,Pr ϕ +1 n,S + β
b̃ r,+ (x; ℓ) Q n,S
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(216)
40
Tx,A2A Tx,A2A χr,Pr ϕ +1 n,S + β
b̃ r,+ (x; ℓ) Q n,S
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
χr,z 180β Tx,A2G q n,S + 16 χ br,Pr n,S + π χr,D n,S
χr,z q n,S χr,D n,S
b̃ r,− (x; ℓ) Q n,S χr,z n,S
Tx,A2A
180β χ br,Pr n,S + π
q
χr,D n,S
χr,z n,S
+ 16
!3
1 b̃ R n
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(218)
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
(219)
!3
q χr,D n,S
b̃ r,− (x; ℓ) Q n,S r,LoS,A2G
(217)
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(220)
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
(221)
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(222)
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
(223)
(x; ℓ) 1
r,LoS,A2A
b̃ R n
(x; ℓ)
ψ Tx,A2G χ br,Pr n,S r,NLoS,A2G (x; ℓ)
b̃ R n
ψ Tx,A2A χ br,Pr n,S b̃ r,NLoS,A2A (x; ℓ) R n Enr,Tx ≈
Enr,Tx ≈
r 2Mn log(2)σ 2 η eff,A2G Gr,A2G 3σ 2 η eff,A2G Gr,A2G n,S n,S + 2Pn b̃ r (x; ℓ) T n,S 2 eff,A2A r,A2A r 2Mn log(2)σ η Gn,S 3σ 2 η eff,A2A Gr,A2A n,S + 2Pn b̃ r (x; ℓ) T n,S
, if ϕz,n = 0 or ϕrz,S = 0,
(224)
, if ϕz,n > 0 and ϕrz,S > 0.
(225) (226)
Term (d) in Objective Function. The server movement energy term (i.e., term (d)) within (P) consists of three components, r (i) the hovering energy - K H eϕS,z , (ii) the altitude change energy - K A PSr,A , and (iii) the lateral movement energy r K L dxy (ϕr−1 S , ϕS ). Of these components, only the lateral movement energy is problematic in its current form for GP, and we discuss its conversion to GP format herein. The altitude change energy does pose problems to GP, but those problems are abstracted into the constraint in (171). As such, we focus on herein. rthe lateral movement energy 2 P r−1 r−1 r r As defined in the main manuscript, dxy (ϕS , ϕS ) = and, as such, the lateral movement j∈{x,y} ϕS,j − ϕS,j distance contains negative terms, which are not in the form of GP. We thus introduce an auxiliary variable, χr,L > 0, to convert the expression into a GP format as follows: 2 X r 2 r (dxy (ϕr−1 ϕr−1 ≤ χr,L (227) S , ϕS )) = S,j − ϕS,j j∈{x,y}
P
ϕr−1 S,j P
j∈{x,y}
χr,L + 2
2
+ ϕrS,j
2
r−1 r j∈{x,y} ϕS,j ϕS,j
≤1
(228)
where (228) follows from rearranging (227). The constraint in (228) has a posynomial denominator, which we convert to a monomial via the AM-GM inequality: X r L̃r (x) = χr,L + 2 ϕr−1 S,j ϕS,j ≥ j∈{x,y} r
b̃ (x; ℓ) ≜ L
χ
r,L
r
ℓ−1
L̃ ([x] ) [χr,L ]ℓ−1
ℓ−1 ! [χr r,L ]ℓ−1 L̃ ([x]
r−1
)
Y j∈{x,y}
ϕrS,j L̃r ([x]ℓ−1 ) [ϕrS,j ]ℓ−1
r
ℓ−1
] ! 2ϕS,jr [ϕS,j ℓ−1 L̃ ([x]
(229)
)
.
41
Using the result of posynomial condensation, we then update (228) obtaining: 2 2 P r−1 ϕ + ϕrS,j S,j j∈{x,y} ≤ 1, b̃ r (x; ℓ) L
(230)
and substitute the auxiliary variable into the server movement energy term yielding: p r ESr,M = K H eϕS,z + K A PSr,A + K L χr,L .
(231)
To summarize, we replace the original term (d) in (P) with the following GP-compliant constraint and objective:
P
j∈{x,y}
ϕr−1 S,j
2
+ ϕrS,j
2 ≤ 1,
b̃ r (x; ℓ) L r
ESr,M = K H eϕS,z + K A PSr,A + K L
(232)
p χr,L .
(233)
Constraint (163). Constraint (163) contains a negative variable (i.e., −αnr ) which is not in the form of GP. We introduce another auxiliary variable, χr,T n > 0, to convert the constraint into a GP-compliant form as follows: τnr (1 − αnr ) ≤ χr,T n , τnr ≤ 1, r r χr,T n + τn αn
(234) (235)
where (235) rearranges the expression in (234). Since (235) contains a posynomial denominator, we again leverage the AM-GM inequality to obtain a monomial equivalent expression as follows: r r X̃nr (x) = χr,T n + τn αn ≥ r,T ℓ−1
[χrn ]ℓ−1
r,T r ℓ−1 b̃ (x; ℓ) ≜ χn X̃n ([x] ) X h i n ℓ−1 χr,T n r
X̃n ([x]
)
τnr αnr X̃nr ([x]ℓ−1 )
ℓ−1 ! [τrnr αrn ]ℓ−1 X̃n ([x]
ℓ−1
[τnr αnr ]
(236)
)
.
We then substitute the resulting monomial in (236) into the inequality in (235), obtaining:
r
τnr
≤ 1.
(237)
b̃ (x; ℓ) X n Constraint (171). Since the altitude component of term (d) in (156) and (171) are intertwined, we will discuss them together in this section. The difference of logarithms expression in (171) contains logarithms, negative terms, and negative terms within the logarithms, which makes the overall expression difficult to work with. As such, we first rearrange (171) as follows: r,A
ePS ≥
ϕmax − ϕr−1 z z,S
,
(238)
≤ 1,
(239)
ϕmax − ϕrz,S z r,A
ϕmax + ePS ϕrz,S z r,A
ePS ϕmax + ϕr−1 z z,S
where (238) uses the fact that log(x) − log(y) = log x/y and then exponentiates both sides, and (239) rearranges (238) further. Since the exponential function in the denominator of (239) is neither a posynomial nor a monomial [73] and direct application of AM-GM inequality preserves the exponential function, we introduce a simplifying variable χ br,E to act as an PSr,A equality constraint and substitute for e , i.e., r,A
χ br,E = ePS , r,E
log(b χ
) − PSr,A = 0,
(240) (241)
where (241) rearranges and then exponentiates both sides of (240). However, since equality constraints on posynomials (and exponential/logarithm functions) are not in the format of GP, we convert it to a pair of inequality constraints enabled by an auxiliary variable χr,A > 0 and a small constant ϵM > 0. Specifically, log(b χr,E ) − PSr,A ≥ χr,A − ϵM ,
(242)
42
log(b χr,E ) − PSr,A ≤ χr,A + ϵM , r,E
which, after rearranging and using the Padé approximation for log(b χ
χr,A + PSr,A + 1 ≤ 1, χ br,E + ϵM χ br,E
χr,A + ϵM + 1 + PSr,A
r,E
)≈χ b
(243) − 1 [72], yields: (244)
≤ 1.
(245)
Both (244) and (245) contain posynomial denominators and thus are not yet in the format of GP. As such, we next perform posynomial condensation via the AM-GM inequality to obtain the following monomial denominators: Ẽ r,− (x) = χ br,E + ϵM ≥ r,E
r,−
b̃ E
χ b
(x; ℓ) ≜
ẼSr,− ([x]ℓ−1 ) [b χr,E ]ℓ−1
[χ b r,E ]ℓ−1 ! r,− Ẽ S
([x]ℓ−1 )
(246)
r,− ϵM ℓ−1 ẼSr,− ([x]ℓ−1 ) ẼS ([x] ) ,
as ϵM is a constant, for the denominator in (244) and Ẽ r,+ (x) = χr,A + ϵM + 1 + PSr,A ≥ r,A ℓ−1
b̃ r,+ (x; ℓ) ≜ E
χr,A ẼSr,+ ([x]ℓ−1 ) [χr,A ]ℓ−1
[χr,A ]ℓ−1 ! r,+ Ẽ S
([x]ℓ−1 )
(1+ϵM ) r,+
ẼSr,+ ([x]ℓ−1 )
Ẽ S
([x]ℓ−1 )
P S ] [r,+
r,A r,+ PS ẼS ([x]ℓ−1 ) h iℓ−1 PSr,A
Ẽ S
([x]ℓ−1 )
(247) ,
as ϵM and 1 are constants, for the denominator in (245). Substituting the monomials in (246) and (247) into (244) and (245), respectively, then yields the following GP compliant inequalities: χr,A + PSr,A + 1 ≤ 1, b̃ r,− (x; ℓ) E χ br,E
≤ 1.
r,+
b̃ E
(248) (249)
(x; ℓ)
With the establishment of (240) via (248)-(249), we then substitute χ br,E into (239), obtaining: ϕmax +χ br,E ϕrz,S z
≤ 1,
χ br,E ϕmax + ϕr−1 z z,S
(250)
which now features a posynomial denominator that we can convert to a monomial as follows: Õr (x) = χ br,E ϕmax + ϕr−1 z z,S ℓ−1
b̃ r (x; ℓ) ≜ O
ℓ−1
χ br,E Õr ([x]
)
max r,E ] ! ϕz r[χb ℓ−1 Õ ([x]
r−1
)
ℓ−1
[b χr,E ]
r
ℓ−1
Õ ([x]
)
r ϕz,Sℓ−1 Õ ([x]
(251) )
,
as both ϕmax and ϕr−1 z z,S are constants during the r-th global round. Thus, (250) becomes ϕmax +χ br,E ϕrz,S z ≤ 1. b̃ r (x; ℓ) O
(252)
To summarize, the above process converted (171), which was not GP-compliant, into the following GP-compliant inequalities: χr,A + PSr,A + 1 ≤ 1, b̃ r,− (x; ℓ) E χ br,E
≤ 1, b̃ (x; ℓ) E ϕmax +χ br,E ϕrz,S z ≤ 1. r b̃ (x; ℓ) O r,+
(253) (254)
(255)
43
C. Summary of Resulting Optimization Formulation Combining all the aforementioned adjustments to (P) (and by extension (P r )), including auxiliary variables and adjusted ′ constraints, yields our final optimization formulation (P ), which is an iterative optimization, where at each iteration, the ′ ′ optimization admits the GP form. The global round separated formulation (P r ) follows immediately from (P ), and is thus omitted for conciseness.
′
(P ) : arg min ψ G
X X r∈R n∈N r
+ ψb
X X
ξnr + ψ R
αnr Enr,Tx + ψ P
r∈R n∈N r
X X
Enr,P + ψ S
r∈R n∈N r
X
X r,D r,z r,Pr r,LoS χn,S + χr,T + χr,L + χr,A + χr,NLoS n + χn,S + χn,S + χn n
r∈R
n∈N r
X
ESr,M
! r∈R (256)
subject to "
# max 2 1 (0,0) 2 r,eff r 2 r (r,max) 3 r r,eff r (r,max) 2 F (Θ ) + 2 (Qn ) + σn (τn Ln ) (ηn wn ) + L (τn ηn wn ) , b̃ r (x; ℓ) RN r A n 2 eff,A2G r,A2G r 2Mn log(2)σ 2 η eff,A2G Gr,A2G 3σ η G + 2P n n,S n,S , if ϕz,n = 0 or ϕrz,S = 0, Enr,Tx ≈ r b̃ T n,S (x; ℓ) 2 eff,A2A r,A2A r 2Mn log(2)σ 2 η eff,A2A Gr,A2A 3σ η G + 2P n n,S n,S Enr,Tx ≈ , if ϕz,n > 0 and ϕrz,S > 0. r b̃ T n,S (x; ℓ) γnr
ξnr =
(257)
(258)
(259) (260)
Enr,P = τnr
3φn an B r 2 (gn ) , 2φ bn
(261)
r
p
ESr,M = K H eϕS,z + K A PSr,A + K L χr,L , 2 P 2 r + (ϕn,j ) j∈{x,y,z} ϕS,j ≤ 1, ∀n ∈ N r , ∀r ∈ R, r b̃ Dn,S (x; ℓ) r ϕS,z ≤ 1, r,+ b̃ (x; ℓ) D n,S ϕn,z ≤ 1, r,− b̃ (x; ℓ) D
(262) (263) (264) (265)
n,S
Tx,A2G Tx,A2G χr,Pr ϕ +1 n,S + β
b̃ r,+ (x; ℓ) Q n,S Tx,A2A Tx,A2A χr,Pr ϕ +1 n,S + β
b̃ r,+ (x; ℓ) Q n,S
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(266)
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
(267)
χr,z 180β Tx,A2G q n,S χ br,Pr + 16 n,S + π χr,D n,S
χr,z q n,S χr,D n,S
b̃ r,− (x; ℓ) Q n,S Tx,A2A
180β χ br,Pr n,S + π
χr,z n,S
q
χr,D n,S
+ 16
b̃ r,− (x; ℓ) Q n,S 1
q
χr,D n,S
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(268)
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
(269)
!3
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
r,LoS,A2G
b̃ R n
χr,z n,S
!3
(x; ℓ)
(270)
44
1 r,LoS,A2A
b̃ R n
≤ 1, if ϕz,n > 0 and ϕrz,S > 0,
(271)
≤ 1, if ϕz,n = 0 or ϕrz,S = 0,
(272)
(x; ℓ)
ψ Tx,A2G χ br,Pr n,S r,NLoS,A2G b̃ R n
(x; ℓ)
ψ Tx,A2A χ br,Pr n,S
≤ 1, if ϕz,n > 0 and ϕrz,S > 0, r,NLoS,A2A b̃ Rn (x; ℓ) 2 2 P r−1 ϕ + ϕrS,j S,j j∈{x,y} ≤ 1, ∀n ∈ N r , ∀r ∈ R, r b̃ L (x; ℓ) τnr ≤ 1, ∀n ∈ N r , ∀r ∈ R, r b̃ X (x; ℓ) n r,A
χ b
+ PSr,A + 1
≤ 1, ∀r ∈ R, r,− b̃ E (x; ℓ) χ br,E ≤ 1, ∀r ∈ R, b̃ r,+ (x; ℓ) E +χ br,E ϕrz,S ϕmax z ≤ 1, ∀r ∈ R, r b̃ (x; ℓ) O Enr,Tx ≤ T max , ∀n ∈ N r , ∀r ∈ R, Pnr 0 ≤ Pnr ≤ P n , ∀n ∈ N r , ∀r ∈ R,
(273)
(274) (275) (276) (277)
(278)
αnr
(279)
r 0 ≤ ϕrx,S ≤ ϕmax x , ∀n ∈ N , ∀r ∈ R,
(281)
r 0 ≤ ϕry,S ≤ ϕmax y , ∀n ∈ N , ∀r ∈ R,
(282)
r 0 ≤ ϕrz,S ≤ ϕmax z , ∀n ∈ N , ∀r ∈ R, 6τnr Bkn (hn kn + Dn + Y ) ≤ 1, ∀n ∈ N r , ∀r ∈ R, 4φ bn gnr gnmin ≤ gnr ≤ gnmax , ∀n ∈ N r , ∀r ∈ R, 0 ≤ τnr,eff ≤ τ g , ∀n ∈ N r , ∀r ∈ R, αnr ∈ {0, 1}, ∀n ∈ N r , ∀r ∈ R, r,Pr r,T r,L r,A r,LoS χr,D , χr,z , χr,NLoS > 0, ∀n ∈ N r , ∀r ∈ R. n n,S , χn , χ , χ n,S , χn,S , χn
(283)
r,Pr r,T r,L r,A r,LoS Variables: Pnr , ϕrS , gnr , τnr , αnr , χr,D , χr,z , χr,NLoS , ∀n ∈ N r , ∀r ∈ R. n n,S , χn , χ , χ n,S , χn,S , χn
(280)
(284) (285) (286) (287) (288) (289)
45
A PPENDIX E A DDITIONAL E XPERIMENTS In the following, we further examine the behavior of (P r ) and its integration with the full SC-DN methodology in response to various server initial positions in Appendix E-A and E-B, respectively. A. Optimization Experiments In the following, we further investigate aspects of our proposed optimization (P r ) and our associated solution methodology developed in Appendix D in response to various server initial positions. While the main manuscript focused on central 0 min min min and random initial positions, the following experiments focus on (i) origin or ϕ = ϕ , ϕ , ϕ , (ii) max or y z Smin max x max max 0 ϕ0S = ϕmax , ϕ , ϕ , and (iii) random edge such that, for j ∈ {x, y, z}, ϕ ∈ ϕ , ϕ . x y z j j j,S
Objective Function Value
N=2
N=4
N=6 b) Max
a) Origin
N=8
N = 10 c) REdge
104 103 102 101 100 0 5 10 15 20 25 30
Approximation Iteration
0 5 10 15 20 25 30
0 5 10 15 20 25 30
Approximation Iteration
Approximation Iteration
r FIGURE 13: Convergence of (P ) when the server is initialized at the network origin, max, and at a random edge (REdge) of the network. In all three cases, the objective function (45) continues to decrease monotonically as a result of Algorithm 3, with incremental differences based on server initial position.
We begin by further investigating the convergence of (P r ) in Fig 13. Comparing and contrasting the convergence of (P r ) in Fig. 3 and 13, we can see that the general convergence trends are all monotonically decreasing and similar, regardless of the server’s initial position. This indicates that our proposed SC-DN methodology consistently converges to high-quality solutions regardless of the server’s starting position. Moreover, differences across initial server positions are limited to small nominal shifts in the objective values, which arise naturally from differing initial server locations. This follows in part because our optimization coefficients, namely ψ G = 1e − 3, ψ P = 1e − 9, ψ R = 1e3, and ψ S = 1e − 4, are chosen such that their separate objective function terms remain on a similar order of magnitude. These conclusions are further supported by the average and standard deviation tables in Table IV-VIII. While the nominal values across these tables demonstrates slight differences, overall the values both average and standard deviation values trend downwards, which highlight that the proposed SC-DN methodology consistently converges to high-quality solutions regardless of the server’s starting position. r TABLE IV: Variability in convergence of (P ) from Fig. 3a). Server initialized at the network center. The average and standard deviations are reported at iterations 1, 15, and 30 of Algorithm 3.
Average Value of (P r )
r TABLE V: Variability in convergence of (P ) from Fig. 3b) with random initial server position. The average and standard deviations are reported at iterations 1, 15, and 30 of Algorithm 3.
Standard Deviation of (P r )
Average Value of (P r )
Standard Deviation of (P r )
Devices
1
15
30
1
15
30
Devices
1
15
30
1
15
30
2 4 6 8 10
9.92e4 9.93e4 9.92e4 9.92e4 9.93e4
4.87e-1 9.77e-1 1.46e0 2.00e0 2.53e0
3.00e-1 7.38e-1 1.25e0 1.79e0 2.30e0
3.04e2 1.62e2 1.30e2 1.04e2 1.20e2
2.61e-1 3.10e-1 2.96e-1 3.00e-1 4.64e-1
1.76e-1 2.06e-1 2.46e-1 2.51e-1 4.08e-1
2 4 6 8 10
9.92e4 9.93e4 9.93e4 9.93e4 9.93e4
5.01e-1 1.10e0 1.60e0 2.09e0 2.68e0
3.05e-1 7.47e-1 1.26e0 1.80e0 2.31e0
2.81e2 1.78e2 1.71e2 1.20e2 1.32e2
2.52e-1 5.03e-1 3.50e-1 3.26e-1 5.64e-1
1.75e-1 2.08e-1 2.46e-1 2.53e-1 4.09e-1
These trends are further corroborated by the average and standard deviation results in Tables IV–VIII. Across all server initialization strategies, the average value of the objective (P r ) decreases by several orders of magnitude from approximation iteration 1 to 30, while the associated standard deviation experience similar reductions. Notably, although different initial server positions introduce modest nominal differences, the relative ordering and rate of convergence remain highly consistent. Moreover, the standard deviation values at later iterations, 15 and 30, become tightly clustered across all initialization cases, indicating diminished sensitivity to initialization and improved solution stability. This behavior suggests that the proposed SCDN methodology effectively mitigates the impact of unfavorable initial server placements and converges toward comparable high-quality solutions. More noticeable differences become apparent in subsequent experiments where the weighting of server movement energy is increased via ψ S , thereby directly amplifying the influence of the server position changes on the optimization process.
46
TABLE VI: Average and standard deviation measurements at iteration 1, 15, and 30 of the experiment in Fig. 13a). The server is initialized at the network origin.
Average Value of (P r )
TABLE VII: Average and standard deviation measurements at iteration 1, 15, and 30 of the experiment in Fig. 13b). The server is initialized at the network maximum.
Standard Deviation of (P r )
Average Value of (P r )
Standard Deviation of (P r )
Devices
1
15
30
1
15
30
Devices
1
15
30
1
15
30
2 4 6 8 10
9.95e4 9.95e4 9.95e4 9.95e4 9.95e4
7.41e-1 1.19e0 1.77e0 2.30e0 2.85e0
3.13e-1 7.53e-1 1.27e0 1.81e0 2.31e0
2.46e2 1.47e2 1.18e2 1.10e2 9.05e1
4.55e-1 3.41e-1 4.32e-1 3.93e-1 5.53e-1
1.81e-1 2.09e-1 2.46e-1 2.52e-1 4.09e-1
2 4 6 8 10
9.91e4 9.94e4 9.93e4 9.93e4 9.94e4
4.71e-1 1.61e0 1.57e0 2.19e0 2.69e0
3.15e-1 7.56e-1 1.27e0 1.81e0 2.32e0
1.26e2 1.74e2 1.37e2 1.14e2 1.19e2
2.79e-1 1.96e0 3.68e-1 4.25e-1 5.11e-1
1.73e-1 2.04e-1 2.46e-1 2.51e-1 4.09e-1
TABLE VIII: Average and standard deviation measurements at iteration 1, 15, and 30 of the experiment in Fig. 13c). Random network edges are chosen as the server’s starting position.
Average Value of (P r )
Standard Deviation of (P r )
Devices
1
15
30
1
15
30
2 4 6 8 10
9.94e4 9.94e4 9.94e4 9.94e4 9.95e4
6.93e-1 1.14e0 1.65e0 2.24e0 2.79e0
3.13e-1 7.55e-1 1.28e0 1.81e0 2.31e0
2.72e2 1.34e2 1.58e2 1.04e2 1.02e2
4.81e-1 3.41e-1 3.91e-1 3.98e-1 5.59e-1
1.78e-1 2.07e-1 2.45e-1 2.52e-1 4.10e-1
Next, we perform experiments to examine local transmit time, device-to-server transmit power, and server positioning as functions of the device-to-server transmit time T max . These experiments also vary the server’s initial position, and, at a highlevel, demonstrate the same qualitative trends, independent of server starting position. From the main manuscript, we can see that, for the centralized (Fig. 4 and 5) and random (Fig. 6 and Fig. 7) initial server positions, the network first compensates for tighter latency constraints through increased transmit power before transitioning to selective device activation as T max becomes sufficiently small (i.e., T max = 5e−6).
10 7
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
10 9
Max Tx Time - T max (s)
10 3
0.2 0.0
10 9
4
40
3
10 5 10 7
50
2 1 0
Max Tx Time - T max (s) r
FIGURE 14: Feasibility and characteristics of (P ) with respect to the maximum transmit time T max . The server is initialized at the network origin. Device 2 is the last active device when T max becomes limiting.
a) Server XY Positions
20 10 Server 10T
40
Final
30
T max = 5e
30
0
Device #1
T
Final max
Start Final max
= 5e 7 0
20
2
= 5e 6 Device #2
X Position (m)
40
b) Server YZ Positions Device #1
20
T
10 3
Final max
= 5e 2
10
Server Final Start T max = 5e 6 0 Final Device #2 max T
= 5e 7 0
20
Y Position (m)
10 2
T max (s)
0.4
5
Z Position (m)
0.6
10 5
10 1
Y Position (m)
0.8
10 3
b) Average Tx Power vs T max Avg Local Iterations ( nr )
1.0
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
Local Tx Time (s)
10 1
Device #2
Device Selection Status ( nr ) Average Tx Power (W)
Device #1
a) Local Tx Time vs T max
10 4 10 5
40
10 6
FIGURE 15: Experiment corresponding to Fig. 14, with the server’s initial position randomly determined. Device 2 is the last active device owing to its proximity to the server’s starting position.
We see similar trends when the server’s initial position is at the network origin (Fig. 14 and Fig. 15), and at a random network edge (Fig. 18 and Fig. 19), except that the device-to-server transmit times and powers differ nominally. Moreover, for these experiments, device 1 is chosen to remain active for limiting T max , i.e., 5e−6. By contrast, when the initial server position is at the network maximum or origin, the behaviors have notable differences. when the server is initialized at the network maximum (Fig. 16 and Fig. 17), the proposed formulation (P r ) shifts the critical point to T max = 5e−5 at which the server can sustain active devices, reflecting the increased communication burden induced by this placement. In particular, for T max = 5e−6, both devices are set inactive instead. Meanwhile, when the server is initialized at the network origin, (P r ) chooses to keep device 1 active in Fig. 14 and Fig. 15, instead of device 2, as device 1 is much closer to the origin. Overall, while the qualitative transition behavior of (P r ) remains consistent, the server’s initial position does influence the precise operating threshold points, particularly under resource-constrained conditions such as small T max .
47
4
80
3
10 5
2
0.2
10 7
1
10 9
0.0
10 9
0
Max Tx Time - T max (s)
r
the maximum transmit time T , with the server initialized at the network maximum. (P r ) determines that it is more resource efficient for both devices to become inactive at T max = 5e−6, rather than 5e−7 as observed in other experiments.
0.6
10 5
0.4
10 7
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
10 9
5
10 1
4
10 3
3
10 5
2
0.2
10 7
1
0.0
10 9
0
Max Tx Time - T max (s)
40
Device #1 10 4 2 maxFinal T = 5e 6 10 5 Device #2
Device #2 0
25
50
75
100
X Position (m)
a) Server XY Positions Server Start Final max
20 0
100
T80 = 5e 7
80
60
T
20 0
Final max
= 5e 6 Device #1 Final T max = 5e 2 Device #2
40
Max Tx Time - T max (s)
r FIGURE 18: Feasibility and characteristics of (P ) with respect to the maximum transmit time T max . The server starts at a random edge of the network, and trends follow those from the central initial server position of Fig. 4.
10 3
100
Y Position (m)
0.8
10 3
b) Average Tx Power vs T max Avg Local Iterations ( nr )
1.0
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
Local Tx Time (s)
10 1
60
Final
T max = 5e
0
25
50
75
Y Position (m)
100
FIGURE 17: Experiment corresponding to Fig. 16, with the server’s initial position at the network maximum. Owing to this initial positioning, (P r ) similarly identifies it as more resource efficient to stop training at T max = 5e−6 rather than 5e−7.
Device #2
Device Selection Status ( nr ) Average Tx Power (W)
Device #1
a) Local Tx Time vs T max
20
Max Tx Time - T max (s)
max
10 2
Device #1 40 Final T max = 5e 2 0
FIGURE 16: Feasibility and characteristics of (P ) with respect to
= 5e 6 80
60
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
10 7
T
b) Server YZ Positions Server Start
100
0
20
X Position (m)
40
b) Server YZ Positions Server Start
10 2 10 3
60
T max (s)
10 3
a) Server XY Positions Server Start Final max
T max (s)
100
Z Position (m)
5
Z Position (m)
0.4
10 1
Y Position (m)
0.6
10 5
b) Average Tx Power vs T max Avg Local Iterations ( nr )
1.0 0.8
10 3
5e -2 5e -3 5e -4 5e -5 5e -6 5e -7
Local Tx Time (s)
10 1
Device #2
Device Selection Status ( nr ) Average Tx Power (W)
Device #1
a) Local Tx Time vs T max
10 4
Final
40
max 5e 6 FinalT =Device #1 10 5 20 T max = 5e 2 Final max Device #2 T = 5e 7 10 6
0
0
25
50
75
Y Position (m)
100
FIGURE 19: Experiment corresponding to Fig. 18, with the server’s initial position chosen at a random network edge. While the server position is different, the general trends follows those of Fig. 5.
Finally, regarding our experiments to characterize the four scaling coefficients, namely ψ G , ψ P , ψ R , and ψ S , of (P r ), the qualitative trends established by Fig. 8 and 9, in which the server starts at the network center, are maintained by our subsequent experiments varying the server’s starting position in Fig. 20, 21, and 22. That being said, these alternative server initial positions typically demonstrate much higher nominal changes in server XY positions for ψ G ≤ 1e0. Specifically, the server XY position change for central server initializations in Fig. 8d) typically fall under 60m, whereas all other server position initializations exceed 60m with random initializations in Fig. 9d) exceeding 80m for ψ G = 1e−6.
0.6 0.4 0.2 P Values
1e-3 1e-4 1e-5 1e-6 1e-7 1e-8
9e3
d) Varying S
15
60
10
40
3e3
5
20
1e3
0
0
7e3 5e3
R Values
20
Server XY-Pos Change (m)
0.8
c) Varying
1e-6 1e-4 1e-2 1e0 1e2 1e4 1e6 1e8 1e10
1.0
Avg Sq D2S Dist ( nD) Avg Tx Power (mW)
b) Varying
10 Devices 10 Devices
R
1e6 1e7 1e8 1e9 1e10 1e11 1e12 1e13
G Values
5 4 3 2 1 0
6 Devices 6 Devices
Norm Gradient Avg Tx Power (W)
1.0 0.8 0.6 0.4 0.2
P
1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
a) Varying
Norm Gradient Avg Train Iters ( nr )
5 4 3 2 1 0
G
1e-10 1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
Avg Train Iters ( nr )
2 Devices 2 Devices
S Values
r FIGURE 20: Characteristic curves for the various scaling coefficients of (P ) for three different network sizes, with identical abbreviations to that explained in Fig. 8 and 9. The server’s position in these networks is the network origin.
We further investigate the visual characteristic curves in Fig. 8 and 9 in the main manuscript as well as Fig. 20-22 by examining their averages and standard deviations in Fig. 23-27 below. These figures report both the average values and their associated standard deviations for key performance metrics, as the scaling coefficients ψ G , ψ P , ψ R , and ψ S are varied. The overall qualitative trend across these five figures is similar. With regards the variation in average normalized gradients and training iterations controlled by ψ G and ψ P in sub-figures a)-d) of Fig. 23-27, we can see that, across different server starting
48
positions, the standard deviations are generally modest, significantly smaller than the average values. The one exception is for smaller networks of 2 devices at transition periods, namely ψ G = 1e−5. Here, the standard deviations can be quite large as the server aims to prioritize the device (as there are only 2 devices) with lower training costs and highest estimated upside, and thus the differences between the two devices can be more substantial as indicated by Fig. 24b) for example.
0.6 0.4 0.2
9e3
1e-3 1e-4 1e-5 1e-6 1e-7 1e-8
P Values
G Values
20
d) Varying S
Server XY-Pos Change (m)
0.8
c) Varying R
15
60
5e3
10
40
3e3
5
20
1e3
0
0
7e3
1e-6 1e-4 1e-2 1e0 1e2 1e4 1e6 1e8 1e10
1.0
10 Devices 10 Devices
Avg Sq D2S Dist ( nD) Avg Tx Power (mW)
b) Varying P
1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
5 4 3 2 1 0
1e6 1e7 1e8 1e9 1e10 1e11 1e12 1e13
1.0 0.8 0.6 0.4 0.2
6 Devices 6 Devices
Norm Gradient Avg Tx Power (W)
a) Varying G
Norm Gradient Avg Train Iters ( nr )
5 4 3 2 1 0
1e-10 1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
Avg Train Iters ( nr )
2 Devices 2 Devices
R Values
S Values
r FIGURE 21: Characteristic curves for the various scaling coefficients of (P ) for three different network sizes. Initially, the server is at the network maximum. Aside from the network becoming inactive earlier in Fig. 21c), at ψ R = 1e11 instead of 1e12, the key trends remain similar as those in previous experiments.
0.6 0.4 0.2
1e-3 1e-4 1e-5 1e-6 1e-7 1e-8
P Values
20
9e3
d) Varying S
Server XY-Pos Change (m)
0.8
c) Varying
Avg Sq D2S Dist ( nD) Avg Tx Power (mW)
1.0
15
60
10
40
3e3
5
20
1e3
0
0
7e3 5e3
1e-6 1e-4 1e-2 1e0 1e2 1e4 1e6 1e8 1e10
G Values
b) Varying
10 Devices 10 Devices
R
1e6 1e7 1e8 1e9 1e10 1e11 1e12 1e13
5 4 3 2 1 0
Norm Gradient Avg Tx Power (W)
1.0 0.8 0.6 0.4 0.2
6 Devices 6 Devices
P
1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
a) Varying
Norm Gradient Avg Train Iters ( nr )
5 4 3 2 1 0
G
1e-10 1e-9 1e-8 1e-7 1e-6 1e-5 1e-4 1e-3 1e-2 1e-1
Avg Train Iters ( nr )
2 Devices 2 Devices
R Values
S Values
r
FIGURE 22: Characteristic curves for the various scaling coefficients of (P ) for three different network sizes, with identical abbreviations
to that explained in Fig. 8. The server’s initial position is at a random network edge.
1e-10 1e-5 1e-1 Value of G
2 4 Avg Iters nr
f) Avg Sq Dist vs R Value of R 1e6 1e10 1e13
Avg Tx Pow (W)
e) Avg Tx Pow vs R
0
10 4 10 5 1e6 1e10 1e13 Value of R
0 2500 5000 Avg Sq D2S Dist ( nD)
0.5 0.0
Network Size = 10
d) Avg Iters vs P Value of P 1e-9 1e-5 1e-1
1.0
c) Avg Grad vs P
1e-9 1e-5 1e-1 Value of P
g) Avg Tx Pow vs S
10 1
0
2 4 Avg Iters nr
h) XY Change vs S Value of S 1e-6 1e2 1e10
0.0
Norm Gradient
0.5
Network Size = 6
b) Avg Iters vs G
Avg Tx Pow (W)
1.0
a) Avg Grad vs G
Value of G 1e-10 1e-5 1e-1
Norm Gradient
Network Size = 2
10 3 1e-6 1e2 1e10 Value of S
0 20 40 Server XY Change (m)
FIGURE 23: Average and standard deviation of convergence metrics, iteration count, transmit power, and server movement as functions of the objective weighting parameters ψ G , ψ P , ψ R , and ψ S . Error bars indicate one standard deviation. The server starts at the center of the network.
49
Meanwhile, for the scaling coefficients ψ R and ψ S of (P r ) that exert a greater influence on communication and server movement, we see similarly stable trends across sub-figures e)-h) of Fig. 23-27. However, differently from earlier sub-figures, the standard deviations here are generally more pronounced, albeit still significantly smaller than their respective average values, regardless of the initial server position. This behavior is expected, as communication power and server mobility are more directly coupled to spatial geometry and link conditions, which naturally introduce higher variability across independent runs.
1e-10 1e-5 1e-1 Value of G
0
10 4 10 5 10 6
2 4 Avg Iters nr
f) Avg Sq Dist vs R Value of R 1e6 1e10 1e13
Avg Tx Pow (W)
e) Avg Tx Pow vs R
1e6 1e10 1e13 Value of R
c) Avg Grad vs
Network Size = 10 P
Value of P 1e-9 1e-5 1e-1
1.0 0.5 0.0
1e-9 1e-5 1e-1 Value of P
0
g) Avg Tx Pow vs S
10 1 10 3
0 5000 Avg Sq D2S Dist ( nD)
d) Avg Iters vs P
2 4 Avg Iters nr
h) XY Change vs S Value of S 1e-6 1e2 1e10
0.5 0.0
b) Avg Iters vs
Norm Gradient
a) Avg Grad vs
G
Avg Tx Pow (W)
1.0
Network Size = 6 G
Value of G 1e-10 1e-5 1e-1
Norm Gradient
Network Size = 2
1e-6 1e2 1e10 Value of S
0 25 50 Server XY Change (m)
FIGURE 24: Average and standard deviation of convergence metrics, iteration count, transmit power, and server movement as functions of the objective weighting parameters ψ G , ψ P , ψ R , and ψ S . Error bars indicate one standard deviation. The initial position of the server is randomly determined.
1e-10 1e-5 1e-1 Value of G
2 4 Avg Iters nr
f) Avg Sq Dist vs R Value of R 1e6 1e10 1e13
Avg Tx Pow (W)
e) Avg Tx Pow vs R
0
10 4 10 6 1e6 1e10 1e13 Value of R
0 10000 Avg Sq D2S Dist ( nD)
c) Avg Grad vs
0.5 0.0
d) Avg Iters vs P Value of P 1e-9 1e-5 1e-1
0.0
1.0
Network Size = 10 P
1e-9 1e-5 1e-1 Value of P
g) Avg Tx Pow vs S
0
2 4 Avg Iters nr
h) XY Change vs S Value of S 1e-6 1e2 1e10
0.5
b) Avg Iters vs
Norm Gradient
a) Avg Grad vs
G
Avg Tx Pow (W)
1.0
Network Size = 6 G
Value of G 1e-10 1e-5 1e-1
Norm Gradient
Network Size = 2
10 2 10 3 10 4 1e-6 1e2 1e10 Value of S
0 50 100 Server XY Change (m)
FIGURE 25: Corresponding to Fig. 20, in which the server starts at the origin, we examine the average and standard deviation of convergence metrics, iteration count, transmit power, and server movement with error bars to indicate one standard deviation.
This is especially noticeable for smaller networks during transition points, such as ψ R = 1e10 for sub-figure e). In these regimes, the optimization actively trades off transmit power against server re-positioning, and with only a small number of devices, individual device locations can exert a stronger influence on the optimal solution. As a result, while the average transmit power decreases systematically with increasing ψ R , the associate variation increases. Importantly, these transition regime induced fluctuations do not alter the overall monotonic trends (corroborated previously in Fig. 8-9 and Fig. 20-22).
50
1e-10 1e-5 1e-1 Value of G
2 4 Avg Iters nr
f) Avg Sq Dist vs R Value of R 1e6 1e10 1e13
Avg Tx Pow (W)
e) Avg Tx Pow vs R
0
10 4 10 5 10 6 1e6 1e10 1e13 Value of R
Value of P 1e-9 1e-5 1e-1
1.0 0.5 0.0
1e-9 1e-5 1e-1 Value of P
g) Avg Tx Pow vs S
10 1 10 3
0 5000 10000 Avg Sq D2S Dist ( nD)
d) Avg Iters vs P
0
2 4 Avg Iters nr
h) XY Change vs S Value of S 1e-6 1e2 1e10
0.0
Network Size = 10
c) Avg Grad vs P Norm Gradient
0.5
Network Size = 6
b) Avg Iters vs G
Avg Tx Pow (W)
1.0
a) Avg Grad vs G
Value of G 1e-10 1e-5 1e-1
Norm Gradient
Network Size = 2
1e-6 1e2 1e10 Value of S
0 50 100 Server XY Change (m)
FIGURE 26: Corresponding to Fig. 21, in which the server starts at the network maximum, we examine the average and standard deviation of convergence metrics, iteration count, transmit power, and server movement with error bars to indicate one standard deviation.
1e-10 1e-5 1e-1 Value of G
10 4 10 5 10 6
2 4 Avg Iters nr
f) Avg Sq Dist vs R Value of R 1e6 1e10 1e13
Avg Tx Pow (W)
e) Avg Tx Pow vs R
0
1e6 1e10 1e13 Value of R
0 5000 10000 Avg Sq D2S Dist ( nD)
Value of P 1e-9 1e-5 1e-1
1.0 0.5 0.0
Network Size = 10
d) Avg Iters vs P
1e-9 1e-5 1e-1 Value of P
g) Avg Tx Pow vs S
10 1
0
2 4 Avg Iters nr
h) XY Change vs S Value of S 1e-6 1e2 1e10
0.0
c) Avg Grad vs P Norm Gradient
0.5
Network Size = 6
b) Avg Iters vs G
Avg Tx Pow (W)
1.0
a) Avg Grad vs G
Value of G 1e-10 1e-5 1e-1
Norm Gradient
Network Size = 2
10 3 1e-6 1e2 1e10 Value of S
0 50 Server XY Change (m)
FIGURE 27: Average and standard deviation of convergence metrics, iteration count, transmit power, and server movement as functions of the objective weighting parameters ψ G , ψ P , ψ R , and ψ S . Error bars indicate one standard deviation. Each run places the server initially at a random network edge.
B. Integrated SC-DN Experiments Next, we investigate the variability of integrated SC-DN experiments, quantified via standard deviation, where the solution of (P r ) directs the operation of the VFL process. In addition, we present complementary experiments in which the server’s initial position is selected randomly, allowing us to assess the robustness of the integrated SC-DN framework. Since the experiments involving standard deviations and central initial server position have already been discussed for static networks within the main manuscript, we begin by discussing static networks when the server is randomly placed. Thereafter, we will discuss the variability for dynamic networks with both central and random initial server positions. Tables IX-XI compare the performance of the proposed SC-DN methodology against Max VFL, GSP, and VAFL for MNIST, CIFAR10, and Pawpularity datasets, when the server’s initial position is random. These tables show that SC-DN maintains (or improves) learning performance while reducing energy consumption and training iteration requirements relative to all baselines, even when the server starts from a random location. This mirrors the trends observed for central initial server position, indicating that the benefits of SC-DN are robust to server placement uncertainty.
51
TABLE IX: Performance of SC-DN relative to the greedy Max VFL, GSP, and VAFL for MNIST in static networks of varying size, in which the server has random initial position. We denote the standard deviation as “Std”. The takeaways remain similar to the case with central initial server position in Table I.
SC-DN
TABLE X: Performance of SC-DN relative to greedy Max VFL, GSP, and VAFL for CIFAR10 in static networks of varying size in which the server’s initial position is random. SC-DN demonstrates an edge in final accuracies and energy savings as well as reduce variation, measured by standard deviation.
Max VFL
SC-DN
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (J) Min Energy (J) Max Energy (J) Std Energy (J) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
85.68 4.65 223.02 31.04 298.19 105.74 3.75 0.47 5.00 1.81
68.22 19.05 240.23 87.82 300.47 77.25 4.00 1.31 5.00 1.35
67.08 8.45 235.97 89.00 300.62 83.40 3.92 1.33 5.00 1.45
78.18 12.26 473.62 457.91 518.48 18.68 5.00 5.00 5.00 0.00
GSP
62.00 22.65 473.52 460.39 523.28 15.04 5.00 5.00 5.00 0.00
62.37 10.22 475.14 462.39 523.87 16.60 5.00 5.00 5.00 0.00
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (kJ) Min Energy (kJ) Max Energy (kJ) Std Energy (kJ) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
85.34 7.98 358.37 277.66 445.90 42.14 3.78 3.00 4.30 0.39
65.05 18.63 347.68 291.30 403.26 24.35 3.67 3.07 4.37 0.25
95.37 2.94 22.85 18.30 23.99 2.28 4.91 4.57 5.00 0.17
VAFL
66.34 14.06 339.22 299.53 369.75 17.93 3.57 3.22 3.94 0.15
70.72 19.76 345.37 238.48 443.16 43.43 3.64 2.60 4.40 0.41
64.16 24.03 338.56 297.95 395.39 24.26 3.57 3.23 4.07 0.22
60.13 13.07 21.21 8.03 23.99 5.60 4.75 3.47 5.00 0.51
63.35 7.06 19.93 5.47 23.99 6.92 4.60 3.06 5.00 0.71
89.43 17.65 33.40 28.84 34.54 2.28 5.00 5.00 5.00 0.00
GSP
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (J) Min Energy (J) Max Energy (J) Std Energy (J) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
Max VFL
64.24 10.44 341.62 306.18 396.45 22.16 3.60 3.22 4.10 0.20
58.94 13.77 31.50 16.65 34.54 6.15 5.00 5.00 5.00 0.00
53.24 7.64 29.95 12.90 34.54 8.00 5.00 5.00 5.00 0.00
VAFL
N=2 N=4 N=6 N=2 N=4 N=6 Final Acc (%) Std Acc (%) Avg Energy (kJ) Min Energy (kJ) Max Energy (kJ) Std Energy (kJ) Avg Iters (τnr ) Min Iters (τnr ) Max Iters (τnr ) Std Iters (τnr )
92.65 4.27 29.92 24.22 34.54 2.70 4.48 4.00 5.00 0.28
58.12 12.05 28.23 13.65 32.70 5.80 4.47 4.10 4.73 0.16
53.36 14.57 26.95 11.35 32.61 7.26 4.50 4.22 4.72 0.13
94.10 3.61 29.97 23.65 34.54 2.76 4.49 3.90 5.00 0.28
56.76 19.01 28.04 13.99 32.70 5.71 4.44 4.13 4.73 0.16
58.23 11.93 26.98 11.09 33.02 7.25 4.51 4.18 4.78 0.16
TABLE XI: Multi-Modal Regression Performance on Pawpularity for SC-DN relative to greedy Max VFL, GSP, and VAFL in static networks of varying size with a randomly located initial server position. Final errors are identical yet SC-DN yields energy savings.
SC-DN
Max VFL
N=2 N=4 N=6 N=2 N=4 N=6 Final Error (MSE) 0.050 Std Error (MSE) 0.006 Avg Energy (kJ) 6.10 Min Energy (kJ) 2.51 Max Energy (kJ) 7.94 Std Energy (kJ) 2.39 Avg Iters (τnr ) 4.65 r Min Iters (τn ) 3.69 Max Iters (τnr ) 5.00 Std Iters (τnr ) 0.48
0.053 0.012 2.73 1.87 3.10 0.50 4.86 4.38 5.00 0.20
0.055 0.007 1.41 1.13 1.51 0.12 4.92 4.66 5.00 0.12
0.050 0.005 9.93 4.99 12.40 3.21 5.00 5.00 5.00 0.00
GSP
0.053 0.012 4.36 3.22 4.85 0.65 5.00 5.00 5.00 0.00
0.055 0.007 2.23 1.85 2.45 0.16 5.00 5.00 5.00 0.00
VAFL
N=2 N=4 N=6 N=2 N=4 N=6 Final Error (MSE) 0.050 Std Error (MSE) 0.005 Avg Energy (kJ) 9.60 Min Energy (kJ) 4.30 Max Energy (kJ) 12.40 Std Energy (kJ) 3.13 Avg Iters (τnr ) 4.83 Min Iters (τnr ) 4.30 r Max Iters (τn ) 5.00 Std Iters (τnr ) 0.20
0.053 0.013 4.17 2.79 4.84 0.65 4.78 4.33 5.00 0.15
0.055 0.007 2.12 1.78 2.38 0.16 4.76 4.54 4.92 0.11
0.050 0.005 9.47 4.69 12.40 3.11 4.77 3.90 5.00 0.28
0.053 0.012 4.18 2.81 4.84 0.68 4.78 4.37 5.00 0.14
0.055 0.007 2.14 1.70 2.33 0.16 4.80 4.56 4.98 0.10
Moreover, when comparing standard deviations across these three tables, SC-DN also shows lower or comparable variability, aside from a very incremental increase in the standard deviation of error for Pawpularity in Table XI. Even when the variability of SC-DN is higher than Max VFL, its worst-case energy consumption remains strictly lower. For example, in the MNIST experiments of Table IX with N = 6, the maximum energy consumption per global round is 0.301 kJ for SC-DN, compared to 0.335 kJ for Max VFL, despite SC-DN having a larger standard deviation (0.083 kJ versus 0.011 kJ). Similarly, GSP and VAFL exhibit considerably higher worst-case energy consumption than SC-DN on MNIST at N = 6, with maximum energy values of 369.75 J and 396.45 J respectively, compared to SC-DN’s 300.62 J, further confirming that SC-DN’s adaptive resource
52
control yields more favorable energy distributions than all baselines.
In other tasks, SC-DN improves both worst-case energy consumption and variability. For instance, in the multi-modal regression experiments on Pawpularity, displayed in Table XI with N = 6. Here, the maximum energy consumption is reduced from 2.451 kJ under Max VFL to 1.507 kJ under SC-DN, while the corresponding standard deviations decrease from 1.704 kJ to 1.406 kJ. GSP and VAFL similarly show higher maximum energy consumption than SC-DN on Pawpularity at N = 6, with values of 2.38 kJ and 2.33 kJ respectively versus SC-DN’s 1.51 kJ, while achieving identical final MSE values of 0.055, consistent with the central initialization results in Table III. Taken together, these quantitative results indicate that although SCDN may exhibit higher variance in some settings, its energy distributions are skewed toward lower values, yielding consistently lower worst-case (i.e., max energy consumption) outcomes. A similar trend is observed for the average number of training iterations, where SC-DN converges faster on average than Max VFL, GSP, and VAFL. Overall, considering Tables IX–XI jointly, SC-DN continues to provide a more favorable accuracy, energy, and training iteration trade-off than Max VFL, GSP, and VAFL, even under randomly initialized server positions.
Next, we investigate dynamic networks when the server’s initial position is random in Fig. 28-30. While the nominal results have small differences relative to Fig. 10-12 for central server initializations, we note that the qualitative trends remain identical. For example, both Fig. 11 and 29 have SC-DN with (P r ) demonstrating a clear performance advantage after roughly 10 global rounds. Likewise, GSP and VAFL continue to occupy a middle ground in terms of both accuracy and energy consumption across all three datasets, consistent with the trends observed under central server initialization. These results therefore indicate that the proposed SC-DN framework is able to effectively adapt to the server’s initial position, enabling performance gains even under dynamic network conditions.
We analyze SC-DN’s performance improvements further in Tables XII-XVII, which present the average and standard deviations for the four methodologies in Fig. 10-12 (center initial server location) and Fig. 28-30 (random initial server location).
Focusing first on the standard deviation results for the central server initialization, we observe that SC-DN with (P r ) not only achieves the highest average accuracies and lowest mean squared error across the three datasets, but also consistently exhibits the smallest standard deviations at 4.69% for MNIST in Table XII, 1.27% for CIFAR10 in Table XIV, and 0.006 mean squared error for Pawpularity in XVI. This indicates that the gains provided by SC-DN are not driven by isolated favorable realizations, but rather reflect stable and repeatable performance across global rounds and network dynamics. In contrast, competing methods display either higher or comparable variability with noticeably lower average performance (e.g., SC-DN without (P r )), highlighting a less reliable tradeoff between accuracy and consistency.
Simultaneously, we can confirm energy efficiency of SC-DN by investigating Tables XIII (MNIST), XV, (CIFAR10), and XVII (Pawpularity) for the details on average training iterations at different global rounds. As expected, the greedy baselines without (P r ) always operate at the maximum allowable number of local iterations and therefore exhibit no variability across rounds. Meanwhile, especially for early global rounds, SC-DN with (P r ) maintains lower average iterations. Even when accounting for variability, the average plus one standard deviation for SC-DN during early global rounds remains strictly below the maximum number of local training iterations per round for non-(P r ) baselines. These results highlight that (P r ) returns its performance gains while reducing the local computation burden, thereby improving overall energy efficiency in dynamic network settings.
53
50 0
10
20
Global Rounds
4.5
0.6 0.4
4.0 3.5
0.2
3.0
0.0
2.5
w/ r
w/o r
0
55 50
20
0
0.12 0.10 0.08 0.06 0
10
20
Global Rounds
50 40 30
3 2
20
20
4
w/ r
w/o r
0
20
Global Rounds
FIGURE 29: Under dynamic network conditions, we examine the changes in accuracy, average process energy, and training iterations per global round for SC-DN on CIFAR10, with the server initialized at random locations. Compared to the similar experiment in MNIST in Fig. 28, average iterations are more volatile, reflecting the increased task complexity. Error bars denote one standard deviation.
VAFL GSP VAFL Without ( r) With ( r) Without ( r) r r Without ( ) With ( ) Without ( r) c) Change in nr b) Energy Use 5 5.0 4
Average nr
Avg Process Energy (kJ)
a) Performance
10
60
Global Rounds
3 2 1 0
GSP VAFL
GSP With ( r) With ( r)
ZOC SC-DN Mean Squared Error (MSE)
60
Global Rounds
FIGURE 28: Examining the accuracy, average energy, and average training iterations per global round for SC-DN on MNIST in dynamic networks with the random initial position for the server. The error bars in Fig. 28 indicate the standard deviation. Additional tables for standard deviations for performance and change in training iterations are in Table XII and XIII.
0.04
a) Performance
65
Average nr
0.8
c) Change in nr
VAFL GSP VAFL Without ( r) With ( r) Without ( r) Without ( r) With ( r) Without ( r) c) Change in nr b) Energy Use 70 5
GSP VAFL
60
5.0
GSP With ( r) With ( r)
ZOC SC-DN
Avg Process Energy (kJ)
70
b) Energy Use
1.0
VAFL Without ( r) Without ( r)
Accuracy (%)
Accuracy (%)
80
GSP With ( r) With ( r)
Average nr
Avg Process Energy (kJ)
a) Performance
VAFL Without ( r) Without ( r)
GSP VAFL
GSP With ( r) With ( r)
ZOC SC-DN
w/ r
w/o r
4.5 4.0 3.5
0
20
Global Rounds
FIGURE 30: With the server initialized at random locations, we examine the performance of SC-DN on Pawpularity in dynamic networks. SC-DN continues to yield high performance and energy efficiency. Complementary statistics for the variability in accuracy and training iterations are reported in Table XVI and XVII.
When the server’s initial position is randomized in Fig. 28-30, the nominal values of both the averages and standard deviations shift slightly. However, the qualitative ordering of the methods remains unchanged. In all cases, SC-DN with (P r ) continues to provide the most favorable combination of high average accuracy and low variability in Tables XII-XVII, demonstrating robustness to uncertainty in server placement. These results collectively suggest that the benefits of SC-DN extend beyond mean performance improvements, offering enhanced stability and predictability in dynamic network environments.
54
TABLE XII: Average accuracies at global rounds 5, 10, 15, and 20. These evaluations are done on MNIST with dynamic networks, both central and random initial server positions are considered. The notation “w/” denotes “with” while “w/o” denotes “without”.
TABLE XIII: Average training iterations at global rounds 5, 10, 15, and 20. These evaluations are done on MNIST with dynamic networks, for central and random initial server positions. The notation “w/” denotes “with” while “w/o” denotes “without”.
Central Server Initial Position
Central Server Initial Position
Method SC-DN w/ (P r ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Average Accuracy (%)
Standard Deviation (%)
5
5
10
15
20
10
15
61.05 71.99 81.52 82.54 19.09 13.50 5.63 59.92 66.83 60.00 66.08 17.27 10.81 19.07 60.31 72.01 78.48 78.63 19.04 14.52 9.97 60.98 65.48 65.46 63.68 20.15 9.93 18.41 58.50 68.29 68.54 70.67 16.91 10.73 12.12 58.22 68.07 70.77 74.64 20.64 16.82 15.94
Method
Average Iterations (τnr ) 5
10
15
20
5
10
15
20
SC-DN w/ (P r ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
2.54 2.59 5.00 5.00 3.92 3.65
3.60 3.75 5.00 5.00 3.72 3.41
5.00 5.00 5.00 5.00 5.00 5.00
5.00 5.00 5.00 5.00 5.00 5.00
1.38 1.35 0.00 0.00 0.89 0.96
1.16 1.04 0.00 0.00 0.91 0.84
0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00
20 4.79 10.69 12.37 11.92 10.98 8.33
Random Server Initial Position Method r
SC-DN w/ (P ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Random Server Initial Position
Average Accuracy (%)
Standard Deviation (%)
5
5
10
15
20
Standard Deviation
10
15
64.07 71.89 80.70 81.80 18.40 13.79 5.50 59.92 66.83 60.00 66.08 17.27 10.81 19.07 58.88 71.99 78.06 79.60 19.91 14.52 8.58 60.64 64.66 65.45 63.82 19.71 9.35 18.41 56.78 65.60 65.73 73.71 16.64 9.41 16.31 57.89 67.55 67.65 74.69 20.51 17.73 16.16
Average Iterations (τnr )
Method
20 4.81 10.69 9.39 12.21 12.42 10.42
r
SC-DN w/ (P ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Standard Deviation
5
10
15
20
5
10
15
20
2.55 2.59 5.00 5.00 3.87 3.65
3.60 3.75 5.00 5.00 3.66 3.11
5.00 5.00 5.00 5.00 5.00 5.00
5.00 5.00 5.00 5.00 4.88 5.00
1.38 1.35 0.00 0.00 0.90 0.96
1.17 1.04 0.00 0.00 0.81 0.98
0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.38 0.00
TABLE XIV: Average accuracies at global rounds 5, 10, 15, and 20. These evaluations are done on CIFAR10 with dynamic networks, both central and random initial server positions are considered. The notation “w/” denotes “with” while “w/o” denotes “without”.
TABLE XV: Average training iterations at global rounds 5, 10, 15, and 20. These evaluations are done on CIFAR10 with dynamic networks, for central and random initial server positions. The notation “w/” denotes “with” while “w/o” denotes “without”.
Central Server Initial Position
Central Server Initial Position
Method r
SC-DN w/ (P ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Average Accuracy (%)
Standard Deviation (%)
5
5
10
15
20
10
15
55.51 57.80 63.10 63.57 8.84 9.11 1.54 55.93 52.08 56.61 52.85 6.78 9.72 6.16 55.67 59.47 62.61 62.31 7.50 6.32 3.30 55.85 51.28 55.28 51.89 8.59 11.55 6.92 55.65 60.81 61.63 59.90 9.84 4.92 3.15 54.24 61.06 61.12 60.95 10.91 3.89 4.82
Average Iterations (τnr )
Method
20 1.27 7.68 4.51 8.82 6.71 6.09
r
SC-DN w/ (P ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Random Server Initial Position Method SC-DN w/ (P r ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Standard Deviation (%)
5
5
15
20
10
15
20
5
10
15
20
3.44 3.45 5.00 5.00 3.81 3.78
3.95 3.97 5.00 5.00 3.89 3.64
3.97 4.00 5.00 5.00 4.42 4.32
4.19 3.79 5.00 5.00 4.26 4.06
0.93 0.93 0.00 0.00 1.02 0.97
0.74 0.75 0.00 0.00 0.70 0.72
0.92 0.88 0.00 0.00 0.86 0.61
0.68 0.68 0.00 0.00 0.73 0.69
Random Server Initial Position
Average Accuracy (%) 10
Standard Deviation
5
10
15
54.46 58.04 62.35 62.93 8.59 8.99 2.34 56.45 52.28 55.55 52.02 6.87 10.65 8.33 55.53 58.46 61.52 61.74 7.53 7.84 4.84 54.60 51.24 52.49 52.49 8.26 11.41 10.67 55.12 59.90 58.92 59.06 8.64 2.31 5.94 53.46 58.78 58.68 59.84 11.06 5.80 3.51
Method
Average Iterations (τnr ) 5
10
15
20
5
10
15
20
SC-DN w/ (P r ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
3.44 3.45 5.00 5.00 3.23 3.02
3.95 3.97 5.00 5.00 2.65 2.40
4.07 4.10 5.00 5.00 3.95 4.45
4.07 4.00 5.00 5.00 4.00 3.97
0.93 0.93 0.00 0.00 0.92 1.09
0.74 0.75 0.00 0.00 1.13 0.88
0.77 0.74 0.00 0.00 0.83 0.62
0.72 0.67 0.00 0.00 0.64 0.66
20 2.42 7.73 5.07 9.58 5.25 3.47
Standard Deviation
55
TABLE XVI: Average errors at global rounds 5, 10, 15, and 20. These evaluations are done on Pawpularity with dynamic networks, both central and random initial server positions are considered. The notation “w/” denotes “with” while “w/o” denotes “without”.
TABLE XVII: Average training iterations at global rounds 5, 10, 15, and 20. These evaluations are done on Pawpularity with dynamic networks, for central and random initial server positions. The notation “w/” denotes “with” while “w/o” denotes “without”.
Central Server Initial Position
Central Server Initial Position
Average MSE
Method 5 SC-DN w/ (P r ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
10
15
Standard Deviation 20
5
10
15
Method
Average Iterations (τnr ) 5
10
15
20
5
10
15
20
SC-DN w/ (P r ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
4.60 4.60 5.00 5.00 4.66 4.67
4.78 4.78 5.00 5.00 4.55 4.77
4.88 4.88 5.00 5.00 4.18 4.58
4.40 4.32 5.00 5.00 4.83 4.61
0.57 0.57 0.00 0.00 0.51 0.43
0.28 0.28 0.00 0.00 0.49 0.36
0.18 0.18 0.00 0.00 0.90 0.47
0.57 0.68 0.00 0.00 0.51 0.55
20
0.101 0.061 0.055 0.048 0.065 0.030 0.019 0.006 0.094 0.091 0.079 0.079 0.068 0.057 0.044 0.041 0.100 0.062 0.054 0.064 0.066 0.035 0.019 0.053 0.094 0.092 0.071 0.085 0.069 0.056 0.030 0.067 0.088 0.097 0.074 0.058 0.058 0.086 0.067 0.015 0.118 0.106 0.083 0.063 0.098 0.068 0.031 0.015 Random Server Initial Position Average MSE
Method 5 r
SC-DN w/ (P ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
10
15
Random Server Initial Position
Standard Deviation 20
5
Standard Deviation
10
15
Average Iterations (τnr )
Method
20
0.100 0.059 0.054 0.047 0.065 0.030 0.019 0.003 0.095 0.099 0.077 0.081 0.068 0.054 0.044 0.048 0.100 0.062 0.054 0.064 0.066 0.035 0.019 0.053 0.094 0.092 0.071 0.085 0.069 0.056 0.030 0.067 0.213 0.122 0.081 0.055 0.333 0.096 0.068 0.012 0.088 0.092 0.069 0.055 0.068 0.073 0.034 0.013
r
SC-DN w/ (P ) ZOC w/ (P r ) SC-DN w/o (P r ) ZOC w/o (P r ) GSP VAFL
Standard Deviation
5
10
15
20
5
10
15
20
4.73 4.73 5.00 5.00 4.73 4.70
4.70 4.78 5.00 5.00 4.75 4.97
4.63 4.88 5.00 5.00 4.69 4.80
4.40 4.40 5.00 5.00 4.77 4.85
0.50 0.50 0.00 0.00 0.49 0.51
0.35 0.28 0.00 0.00 0.39 0.09
0.73 0.18 0.00 0.00 0.35 0.25
0.57 0.57 0.00 0.00 0.22 0.19
56
C. Ablation Study 1) Impact of control variables of (P r ): For the following ablation study, we isolate the contribution of each component of (P r ) by selectively disabling server movement, CPU cost optimization, and transmission power optimization in turn, while keeping all other components active. We also investigate the impact of the number of optimization iterations on final ML model performance. These results are summarized in Fig. 31 (optimization iterations) and Table XVIII (the remaining ablation aspects). Fig. 31 shows that SC-DN’s performance is robust to the number of optimization iterations used to solve (P r ), with rapid convergence towards stable accuracies and MSE. While our experiments use 30 optimization iterations for more stable performance, we note that resource-limited network operations can choose to perform fewer iterations with similar final performances. We discuss this aspect further, as it pertains to providing network operations with flexibility to trade off runtime against solution quality, in Table XIX.
68
80
Accuracy (%)
Accuracy (%)
90 70 60 50 10 20 30 40 50
b) CIFAR10
66 64 62 60 58
Optim Iters
10 20 30 40 50
b) Pawpularity
0.07
Mean Squared Error
a) MNIST
0.06 0.05 0.04 0.03
Optim Iters
10 20 30 40 50
Optim Iters
FIGURE 31: The impact of optimization iterations on the ML model performances for SC-DN.
Meanwhile, for the remaining ablation aspects in Table XVIII Across all three datasets, disabling any single component leads to only minor changes in final ML model performance, confirming that no single component is solely responsible for accuracy gains, while the corresponding resource savings (from including each component) can be substantial. r TABLE XVIII: Ablation on the components of P . Results shown are averaged accuracies (%) for MNIST and CIFAR10 and mean squared error (MSE) values for Pawpularity in experiments involving dynamic networks.
Dataset
Final Performance Full SC-DN
Final Performance w/o Server Movement
SC-DN Savings Server Energy (%)
MNIST CIFAR-10 Pawpularity
82.17 ± 6.79 63.82 ± 1.44 0.0475 ± 0.0070
83.05 ± 6.87 64.14 ± 0.78 0.0473 ± 0.0050
17.26% 62.76% 7.83%
Dataset MNIST CIFAR-10 Pawpularity
Full SC-DN 82.17 ± 6.79 63.82 ± 1.44 0.0475 ± 0.0070
w/o CPU Costs 83.06 ± 6.81 63.99 ± 0.79 0.0464 ± 0.0050
Saved CPU cycles (%) 98.99% 86.87% 98.24%
Dataset MNIST CIFAR-10 Pawpularity
Full SC-DN 82.17 ± 6.79 63.82 ± 1.44 0.0475 ± 0.0070
w/o Tx Power Costs 82.95 ± 7.16 64.22 ± 0.93 0.0465 ± 0.0064
Saved Tx energy (%) 75.95% 89.00% 53.55%
For instance, including server movement into the optimization leads to server energy savings of 62.76% on CIFAR-10 and 17.26% on MNIST, at the cost of less than 1% performance degradation. Similarly, including the CPU cost optimization leads to CPU cycle savings of 86.87% to 98.99% depending on the dataset, while including transmission power optimization leads to saved Tx energy of 53.55% to 89.00%, both of which have negligible impact on final model performance. These results demonstrate that each component of SC-DN’s joint optimization contributes meaningfully to resource efficiency, even when its individual impact on model accuracy is modest. 2) Overhead costs of Algorithm 2 and 3: We evaluate the practical computational overhead introduced by Algorithm 2 (importance via exclusion) and Algorithm 3 (per-round optimization solver). Algorithm 2 requires additional forward passes per global round, as each device’s importance score is estimated by excluding it from the aggregation. Fig. 32 reports the resulting server wall-clock time and total added forward passes as a function of the number of network devices, N . Across all three evaluated datasets (MNIST, CIFAR-10, and Pawpularity), the per-round wall-clock overhead remains under 20 ms for N ≤ 10, with forward passes increasing linearly from approximately 4 ms at N = 2 to 20 at N = 10, consistent with linear scaling relative to the number of network devices.
57
0.020 0.015 0.010 0.005 2
4
6
8
Network Devices (N)
10
Avg. Total Forward Passes
Average Runtime (s)
MNIST CIFAR10 a) Server Wall-Clock Time (Alg 2)
20
Pawpularity b) Added Forward Passes (Alg 2)
15 10 5 2
4
6
8
Network Devices (N)
10
FIGURE 32: Computational overhead of Algorithm 2 as a function of the number of network devices, N . Fig. 32a) shows average server wall-clock time per round across three datasets (MNIST, CIFAR-10, Pawpularity) with error bars denoting one standard deviation. Meanwhile, Fig. 32b) examines the average total number of added forward passes per round, which scales linearly with N.
Next, we have measured the wall-clock runtime of the per-round optimization solver (Algorithm 3) as a function of the number of network devices N in Fig. 33. Therein, the runtime scales linearly with N, with an empirical fit of 2.47N − 1.80 seconds, demonstrating that the overhead grows predictably and manageably with network size. Moreover, this result is for optimization overhead when network operators perform 30 optimization iterations of (P r ). For faster runtimes (and cheaper overhead), network operators can reduce the number of optimization iterations performed, at a minor cost to performance per Fig. 31.
Average Total Runtime (s)
Optimization Wall-Clock Runtime 120
Linear fit: 2.47N - 1.80 Measured (mean ± std)
100 80 60 40 20 0
0
10
20
30
Network Devices (N)
40
50
FIGURE 33: Wall-clock runtime of the per-round optimization solver (i.e., Algorithm 3) as a function of the number of network devices, N . Points denote the mean ± one standard deviation over 10 independent runs. The dashed line shows a linear fit (2.47N − 1.80), confirming that solver runtime scales linearly with N.
58
D. Smoothness Constants Estimation and Overhead The Lipschitz smoothness constants Lrn and Lr are estimated at the beginning of each global round. This incurs no additional communication overhead, as the server computes Lrn directly from the model parameters that active devices already transmit at the end of each round. Each smoothness constant is estimated by computing the spectral norms of the device’s ML model weight matrices, multiplying them together, and squaring the result; this quantity is then scaled by a loss-function-dependent constant, which is upper bounded by 1 for both mean squared error and cross-entropy. This approach follows standard results in convex optimization and deep learning theory [55], [56], [57], [58]. Table XIX reports the average smoothness estimation time relative to local ML model training time across all three datasets. Estimation accounts for 0.51%–11.29% of local training time depending on model complexity, with an absolute cost under 4 seconds in all cases, confirming that the estimation overhead is lightweight in practice. TABLE XIX: Comparison of Lipschitz-smooth estimation and device ML model training times. Across all three datasets, the estimation time is a fraction of the ML model training time.
Dataset
Average Lipschitz-smooth Estimation Time (s)
Average Device Local Training Time (s)
Estimation Overhead (%)
MNIST CIFAR-10 Pawpularity
0.015 3.82 0.44
2.92 33.83 6.39
0.51% 11.29% 6.89%