Resource-Aware Hierarchical Federated Learning in Wireless Video Caching Networks
Md Ferdous Pervej, Member, IEEE, and Andreas F. Molisch, Fellow, IEEE
Part of this work will be presented at the 2024 IEEE International Conference on Communications (ICC) <cit.>.
This work was supported by NSF-IITP Project 2152646.
The authors are with the Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA 90089 USA (e-mail<EMAIL_ADDRESS>molisch@usc.edu).

Pervej et al.: Resource-Aware HFL in Wireless Video Caching Networks

The majority of wireless video traffic is caused by a few popular files requested by many users. Backhaul traffic congestion therefore can be alleviated by predicting the to-be-requested content and storing it at various levels in wireless video caching networks.
While traditional machine learning (ML) algorithms may efficiently capture the rapid changes in global content popularity, there is an increasing requirement for a privacy-preserving solution to predict users' future demands.
Motivated by this, we propose in this paper a novel resource-aware hierarchical federated learning (RawHFL) solution for such prediction.
In particular, since users make content requests based on individual needs and preferences, the proposed RawHFL considers a practical dataset update technique where users can only update their local base stations with the requested content's information.
Besides, since resources are limited, we adopt a partial client participation case and derive the convergence bound of the proposed RawHFL algorithm.
Furthermore, the convergence bound depends on the client selection, the number of local training rounds and the trained gradients' successful reception at the base stations (BSs).
Based on this bound, we minimize a weighted utility function to optimize client selection and clients' a) local rounds, b) CPU frequencies and c) transmission powers jointly to train the RawHFL energy efficiently under practical resource constraints.
Our extensive simulation results validate the proposed algorithm's superior test accuracy and energy expense compared to baseline algorithms.
Backhaul traffic congestion caused by the video traffic of a few popular files can be alleviated by storing the to-be-requested content at various levels in wireless video caching networks.
Typically, content service providers (CSPs) own the content, and the users request their preferred content from the CSPs using their (wireless) internet service providers (ISPs).
As these parties do not reveal their private information and business secrets, traditional techniques may not be readily used to predict the dynamic changes in users' future demands.
Motivated by this, we propose a novel resource-aware hierarchical federated learning (RawHFL) solution for predicting user's future content requests.
A practical data acquisition technique is used that allows the user to update its local training dataset based on its requested content.
Besides, since networking and other computational resources are limited, considering that only a subset of the users participate in the model training, we derive the convergence bound of the proposed algorithm.
Based on this bound, we minimize a weighted utility function for jointly configuring the controllable parameters to train the RawHFL energy efficiently under practical resource constraints.
Our extensive simulation results validate the proposed algorithm's superiority, in terms of test accuracy and energy cost, over existing baselines.

Federated learning, resource-aware hierarchical federated learning, resource optimization, video caching.

§ INTRODUCTION

Video streaming is the dominant source of data traffic in wireless networks: approximately $3$ out of $5$ video views are generated from wireless devices <cit.>, accounting for some $70 \%$ of bits sent over the air.
This traffic not only burdens the over-the-air transmission but also the backhaul: since the videos are owned by some csp, e.g., YouTube, Netflix, Amazon Prime Video, HBO, Hulu, to name a few, and stored in the cloud servers used by the csp, the requested videos need to be obtained from the cloud by the isp and transported over its backhaul in order to be delivered to the requester node.
As such, continuous deliveries of the requested content can overwhelm the backhaul network due to large bandwidth requirements engendered by the combination of large data amount and latency constraints required for the qoe.
These problems can be greatly mitigated by caching at (or near) the wireless edge <cit.>, i.e., wireless networks can store the to-be-requested content at the bs, reducing repetitive extractions and saving considerable backhaul resources.
Therefore, if the csp and the isp collaborate, they can design a practical solution to ameliorate the load for the backhaul.

Placement of the content and delivery of the requested content are the two main components of a video caching network <cit.>.
Among many design parameters of a video caching network, two main elements are the content placement and delivery of the requested content <cit.>.
Typically, the storage size required to store all content available from the csp far exceeds the capacity of a local cache.
Consequently, it is critical to know the most likely to-be-requested content sets during the content placement phase.
Unfortunately, determination of these to-be-requested content is challenging: they may deviate considerably from the most recently used ones and may also differ significantly from the global or even regional most-popular files.
This is particularly true when the users have individual preferences and follow a preference-popularity tradeoff in making their requests.
This is particularly true when the users have individual preferences and do not always request the most popular content.
Thanks to ml, such changes can be accurately captured by carefully designing the ml model and its training algorithm.
Nonetheless, the need for large amounts of training data samples to accurately learn the ml model parameters remains a challenge.

Additionally, content caching becomes inevitably difficult due to the need to protect privacy and business secrets.
In order to get the requested content from the csp, the user must place the request using its serving bs.
However, neither the ue nor the csp wants to reveal the exact content ID to the serving bs: the ue as a matter of privacy, and the csp because the user requests are business secrets that it does not disclose to the isp, which often is a competitor.
Conversely,  while the ue can place an encrypted content request to the csp via the serving bs, the bs does not wish to reveal the exact spatial information of the requester ue to the csp, since that is its business secret.
The above factors must be considered in designing any ml algorithm for wireless video caching networks.
Fortunately, these challenges can be handled with fl, which enables distributed model training on users' devices, thus protecting the users' data privacy.
While traditional fl follows a parameter server paradigm, where a central server coordinates the training process for the distributed clients[A user is usually named by the terms ue and client in wireless networks and fl, respectively. We use these terms interchangeably in this paper.], almost all practical wireless networks have hierarchical structures <cit.>.
Therefore, it is critical to devise an efficient hfl considering the cooperation among the ue, isp and csp.

§.§ State-of-the-Art

Content placement is widely investigated to maximize chr and/or minimize content delivery delay.
Recently, Javedankherad et al. leveraged a weighted vertex graph coloring and a greedy algorithm for mobility-aware content placement to maximize the chr <cit.>.
Malak et al. optimized cache placement and transmission power to minimize transmission delays in multi-hop wireless heterogeneous networks <cit.>.
Qian et al. first derived closed-form solutions for cache placement and transcoding, followed by designing trading contracts between a communication, caching and computing resource provider and mobile network operators in order to minimize personalized content delivery delay <cit.>.
Considering users' long-term request patterns, Ning et al. jointly optimized cache placement and content recommendations in order to minimize content delivery costs <cit.>.
While these studies show the benefits of content caching, dynamic changes in user preferences, leading to frequent changes in global/regional content popularity, still cause significant challenges in wireless video caching networks.

ml is widely used in literature <cit.> to apprehend the dynamic changes in content popularity.
These works broadly fall into two ml domains, namely ($1$) supervised learning and ($2$) rl.
In the supervised ml category, existing works <cit.> mainly used some variants of rnn to predict future content popularity or cache placement.
Besides, drl is also widely used <cit.> to learn long-term cache placement policy.
However, these works mainly adopted a centralized ml strategy, considering training datasets are centrally available.
This assumption differs in many practical cases where training data are only available to the end users who want to protect their data privacy.

Many recent studies <cit.> leveraged fl-based solutions for different content caching applications in order to protect users' data privacy.
Qiang et al. proposed an adaptive fl-based proactive content caching solution <cit.>, where two sets of drl agents were used to learn two tasks: subset client selection and clients' local training rounds selection.
They then leveraged fl to aggregate the models of these drl agents.
<cit.> also used two separate drl agent sets — one at the user level for learning computation offloading policy and one at the edge server level for learning content placement policy — and applied federated aggregation of these drl models.
A similar strategy was also adopted by Wang et al., where clients' mobility and preferences were first utilized to cluster the clients <cit.>.
They then let each cluster head train a drl model to learn the cache placement.
In <cit.>, users learned their content preferences and shared the context information and the learned preferences with their associated ap, who then partitioned the users and got popularity scores for the content.
These popularity scores were then used to train stochastic variance reduced gradient models to predict the global content popularity.
In <cit.>, users first learned their content preferences, followed by sharing their context information and learned preferences with their associated ap.
The ap then partitioned the users and derived popularity scores of the content that they leveraged to train stochastic variance reduced gradient models to predict the global content popularity.
User partitioning was also exploited by Li et al., who considered mobility and social behavior to partition the users in a device-to-device network <cit.>.
The authors then proposed an attention-weighted fl algorithm for predicting the content popularity.
An attention-weighted fl algorithm was proposed by Li et al. for predicting content popularity in a device-to-device network, leveraging a similar user partitioning strategy based on mobility and social behavior <cit.>.
Khanal et al. also proposed a self-attention-based fl algorithm to predict cell-wise content popularity in vehicular networks <cit.>.

Lin et al. proposed a proactive caching scheme using stacked autoencoders for global content popularity prediction <cit.>.
Maale et al. considered a uav-assisted caching network <cit.>, where popular content of the ground users was placed in the uav's limited cache to ensure ground users' qoe.
Cao et al. proposed a similar mobility-aware content caching solution <cit.>, where FL was used to predict users' trajectories and content popularity.
These prediction results were then used to place the contents to minimize content delivery costs.
Feng et al. also considered a similar approach <cit.>, which first predicted the residence time of moving vehicles and then utilized that to predict content popularity in each bs.

§.§ Our Contributions

While <cit.> showed ml improves caching performance, these centralized ml methods are not suitable due to privacy concerns.
Besides, although some studies <cit.> only considered users' data privacy, collaboration among the three entities involved, i.e., ue, bs and csp, was not addressed.
Furthermore, the above works do not consider sporadic content request patterns and the important fact that the users' training datasets are not readily available: they need to process their requested content's information to prepare their training datasets.
Additionally, an hfl based solution is preferable due to the hierarchical architecture of practical networks.
Moreover, while clients have limited computational power and energy resources, the isp has limited radio resources.
As such, coordination among these parties is needed to ensure an efficient video caching platform.
Due to these reasons, we propose a novel rawhfl algorithm where the clients train their local model to predict their to-be-requested content.
More specifically, our key contributions are summarized as follows:

* Considering a realistic multi-cell wireless network consisting of multiple bs and clients, where clients request content from a csp using encrypted tagged IDs, we leverage privacy-preserving collaboration among these three parties to bring an efficient video caching solution.

* Due to resource scarcity, the proposed rawhfl only selects a subset of the clients for model training.
Furthermore, acknowledging the well-known system and data heterogeneity, we derive rawhfl's convergence bound, which reveals that the global gradient norm depends on the successful reception of the selected clients' trained accumulated gradients and their local training rounds.

* To that end, we jointly optimize client selection and clients' (i) local training rounds, (ii) cpu cycles and (iii) transmission power to minimize a weighted utility function that facilitates rawhfl's convergence and minimizes energy expense under delay, energy and radio resource constraints.
As the original problem is non-convex, we transform it into a relaxed difference of convex programming problems and use a low-complexity iterative solution.

* Our extensive simulation results validate that the proposed solution outperforms existing baselines in terms of test accuracy and energy expense in a resource-constrained setting.
Moreover, the proposed RAW performs nearly identically to the ideal case performance of hfedavg <cit.> in all examined scenarios.

The rest of the paper is organized as follows.
Section <ref> presents our system model, content request model and preliminaries of hfl.
In Section <ref>, we first summarize the proposed rawhfl and then present our detailed theoretical analysis.
Besides, Section <ref> describes our joint problem formulation, followed by problem transformations and solutions.
Section <ref> presents our extensive simulation results, followed by the concluding remarks in Section <ref>.
Moreover, Table <ref> summarizes the important notations used in this paper.

Summary of important variables

Parameter      Definitions
$u$, $\mathcal{U}$     User $u$, all user set
$b$, $\mathcal{B}$     base station $b$, all BS set
$l$, $\mathrm{L}$      $l^{\mathrm{th}}$ SGD round, upper bound for local SGD round
$e$, $E$       $e^{\mathrm{th}}$ edge round, total edge round
$k$, $K$      $k^{\mathrm{th}}$ global round, total global round
$t$     $t^{th}$ discrete slot at which UE may request content
$\mathcal{U}_b$, $\mathcal{U}_b^{k,e}$     BS $b$'s UE set; selected UE/client set of BS $b$ during edge round $e$ of global round $k$
$\mathrm{L}_u^{k,e}$     UE/client $u$'s local SGD round during edge round $e$ of global round $k$
$g$, $G$     Genre $g$; total genres
$c_g$, $\mathcal{C}_g$, $\mathcal{C}$     $c^{\mathrm{th}}$ content of genre $g$; all content set in genre $g$; entire content catalog
$\Bar{C}_g$, $C$     Total content in genre $g$; total content in the catalog
$z$, $Z$, $\mathcal{Z}$     $z^{\mathrm{th}}$ pRB; total pRBs; pRB set
$\mathcal{D}_{u,\mathrm{raw}}^0$     UE $u$'s initial historical dataset
$p_{u,\mathrm{ac}}$     UE $u$'s probability of being active (making a content request)
$\mathrm{1}_{u,c_g}^t$     Binary indicator function that defines whether $u$ requests content $c_g$ during slot $t$
$p_{u,g}$     UE $u$'s preference to genre $g$
$\Upsilon$     Dirichlet distribution's concentration parameter for the genre preference
$\mathcal{D}_{u,\mathrm{proc}}^{t}$, $\mathrm{D}_{u,\mathrm{proc}}^{t}$     UE $u$'s processed dataset; total samples in UE $u$'s processed dataset
$f_u(\cdot)$; $f_b(\cdot)$, $f(\cdot)$     UE $u$'s loss function; BS $b$'s loss function; global loss function
$\mathbf{w}_u^{k,e,l}$, $\mathbf{w}_b^{k,e}$, $\mathbf{w}^{k}$     UE/Client $u$'s local model during SGD round $l$ of edge round $e$ of global round $k$; BS $b$'s edge model during edge round $e$ of global round $k$; global model during round $k$
$g_u(\mathbf{w}_{u}^{k,e,l})$     UE $u$'s gradient during $l^{\mathrm{th}}$ local round of $e^{\mathrm{th}}$ edge round of $k^{\mathrm{th}}$ global round
$\tilde{g}_u^{k,e}$     UE $u$'s accumulated gradients during $e^{\mathrm{th}}$ edge round of $k^{\mathrm{th}}$ global round
$\eta$     Learning rate
$\alpha_u$, $\alpha_b$     UE $u$'s trained model/accumulated gradients' weight; BS $b$'s model/accumulated gradients' weight
$\mathrm{1}_{u, \mathrm{sl}}^{k,e}$; $\mathrm{p}_{u, \mathrm{sl}}^{k,e}$     Binary indicator function to define whether $u$ is selected in edge round $e$ of global round $k$; success probability of $\mathrm{1}_{u,\mathrm{sl}}^{k,e}$
$\mathrm{t}_{u,\mathrm{cp}}^{k,e}$; $\mathrm{e}_{u,\mathrm{cp}}^{k,e}$     UE $u$'s local model training time and energy overheads during edge round $e$ of global round $k$
$\mathrm{t}_{u,\mathrm{up}}^{k,e}$; $\mathrm{e}_{u,\mathrm{up}}^{k,e}$     UE $u$'s accumulated gradient offloading time and energy overheads during edge round $e$ of global round $k$
$\mathrm{t_{th}}$     Deadline threshold to finish one edge round
$P_{u,\mathrm{tx}}^{k,e}$; $P_{u, \mathrm{max}}$     Transmission power of $u$; maximum allowable transmission power of $u$
$\mathrm{e}_{u,\mathrm{bud}}$     Energy budget of $u$ for each edge round
$\mathrm{1}_{u,\mathrm{sc}}^{k,e}$; $\mathrm{p}_{u,\mathrm{sc}}^{k,e}$     Binary indicator function to define whether accumulated gradient of $u$ is received by the bs; success probability of $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$
$\phi$; $s$     Floating point precision; client's uplink payload size for the accumulated gradients
$\beta$     Smoothness of the loss function
$\sigma^2$     Bounded variance of the gradients
$\epsilon_{0}^2$     Bounded divergence between the local and the edge loss functions
$\epsilon_{1}^2$     Bounded divergence between the edge and the global loss functions
$\varphi_b^{k,e}$     Utility function for the joint optimization problem

Network system model

§ SYSTEM MODEL

§.§ Network Model

This paper considers a video caching wireless network, where distributed ue, denoted by $\mathcal{U}=\{u\}_{u=0}^{U-1}$, can request content from a csp using their serving bs.
Let us denote the bs set by $\mathcal{B}=\{b\}_{b=0}^{B-1}$ and the user set associated with BS $b$ by $\mathcal{U}_b$.
Besides, a ue is only associated with a single bs and $\mathcal{U} = \bigcup_{b=0}^{B-1} \mathcal{U}_b$.
For simplicity, we assume that all bs are operated and controlled by the same isp.
The considered system model is shown in Fig. <ref>.
Denote the content catalog of the csp by $\mathcal{C}=\{\mathcal{C}_g\}_{g=0}^{G-1}$, where $\mathcal{C}_g = \{c_g\}_{c=0}^{\bar{C}_g-1}$ represents the content set of genre $g$.
Therefore, the content catalog has a fixed set of $C = \sum_{g=0}^{G-1} \Bar{C}_g$ content[While new content may arrive/generate at the csp, given that the csp has a limited storage capacity, following standard practice <cit.>, we assume the number of content that the csp can store remains fixed.].
The csp and the isp have mutual agreements that enable the csp to install one es to every bs of the isp.
This lets the csp leverage the es' limited storage and computation power to devise an efficient fl-based caching solution.
Furthermore, we assume that the csp and the isp are entirely different entities under two different business organizations and, therefore, always keep their operations secrets from each other.
As such, the csp neither reveals the information of the ue's requested content nor shares what content it stores in the es with the bs.
The ue, on the other hand, know the exact content information and can place their content requests using encrypted temporal tag IDs via their associated bs.
Fig. <ref> shows the privacy protection procedures at different nodes.
Furthermore, the csp can frequently change these encrypted tag IDs and their mapping with the original content to further enhance its operational secrets.

Privacy protection in different nodes

The network operates in discrete time slots, denoted by $t$, and the duration between two consecutive slots is $\kappa$ seconds.
The isp dedicates $\Bar{\mathrm{Z}}$ hz bandwidth to perform the fl training.
More specifically, each bs of the isp utilizes $\Bar{\mathrm{Z}}$ hz bandwidth, which they divide into $Z$ orthogonal prb, for sharing the fl-related payloads with the participating ue and the es.
Denote the pRB set by $\mathcal{Z}=\{z\}_{z=0}^{Z-1}$.
We assume that node association, resource allocations and csi are known at the bs.
Besides, the neighboring bs can utilize $\Bar{\mathrm{Z}}$ hz bandwidth for the fl task from different portions of their entire operating bandwidth to avoid inter-cell interference[If the bs have to use the same portion of the bandwidth, they can coordinate and assign the prb in neighboring cells and/or use advanced beamforming techniques such as zero-forcing for interference-free communication.] <cit.>.
Moreover, since orthogonal prb are used within each cell, there is no intra-tier interference.
Furthermore, we consider that the wireless channel between the ue and the bs is dominated by large-scale fading since users are stationary in our system model, and practical networks can exploit enough diversity to mitigate small-scale fading.
As such, we model the large-scale path loss and log-Normal shadowing following $3$GPP's urban macro model <cit.>.

§.§ Content Request Model

A ue may or may not request content during a slot $t$, depending on its need.
Let $p_{u,\mathrm{ac}}$ be the probability that the $u^{\mathrm{th}}$ ue makes a content request, which can also be interpreted as the activity level of the ue.
Besides, given that the ue makes a content request, we use a binary variable $\mathrm{1}_{u,c_g}^{t}$ to denote if the ue requests content $c_g$ in slot $t$.
Furthermore, each ue has a small initial historical raw dataset, denoted by $\mathcal{D}_{u,\mathrm{raw}}^0$.
Therefore, for $t>0$, each ue updates its local raw dataset using the requested content's information as

\begin{equation}
\label{datasetEvol}
\begin{aligned}
\mathcal{D}_{u,\mathrm{raw}}^t &\coloneqq
\begin{cases}
\mathcal{D}_{u,\mathrm{raw}}^{t-1} \bigcup \big\{ \mathbf{x}(\mathrm{1}_{u,c_g}^t), \mathbf{y}(\mathrm{1}_{u,c_g}^t) \big\}, \rs\rs\rs  & \text{if $u$ is active}, \\
\mathcal{D}_{u,\mathrm{raw}}^{t-1}, & \text{otherwise},
\end{cases}\rs,\rs\rs
\end{aligned}
\end{equation}

where $\mathbf{x}(\mathrm{1}_{u,c_g}^t)$ and $\mathbf{y}(\mathrm{1}_{u,c_g}^t)$ are the feature and label vectors of the requested content, respectively.
Note that (<ref>) makes ue's dataset size time-varying and essentially captures natural data sensing methods in many practical applications <cit.>.

We consider a popularity-preference tradeoff in ue's content request model owing to the fact that both individual preference and global content popularity can influence the ue in choosing the content to request.
In particular, we assume that each ue has a genre preference, denoted by $p_{u,g}$, such that $0\leq p_{u,g} \leq 1$ and $\sum_{g=0}^{G-1} p_{u,g}=1$.
These genre preferences are modeled following a symmetric Dirichlet distribution $\mathrm{Dir}(\pmb{\Upsilon})$, where the $\pmb{\Upsilon}$ is the concentration parameter <cit.>.
At first, the ue selects a genre $g$ based on its preference, from which it picks the most popular content during its first request.
In the subsequent content request, it can either exploit the most similar content from the same genre with probability $\upsilon_u$ or explore the most popular content from a different genre, $g' \neq g$, with probability $(1-\upsilon_u)$.
Note that each content has its own distinctive feature set that can be used to calculate its similarity with other content in the same genre.

§.§ Hierarchical Federated Learning: Preliminaries

In this paper, we consider that the central server, es, bs and the distributed clients collaboratively train an ml model, parameterized by $\mathbf{w} \in \mathbb{R}^d$.
The task is to predict the to-be-requested content of these ue so that the video caching network can make the most out of the limited storage of the es[Our solution is general and can easily be extended for other tasks.].
The ue process their local raw datasets acquired by (<ref>) to train the ml model locally.
Let us denote the processed dataset by $\mathcal{D}_{u,\mathrm{proc}}^t = \{\mathbf{x}_{u}^a, \mathbf{y}_{u}^a\}_{a=0}^{\mathrm{D}_{u,\mathrm{proc}}^t - 1}$, where $(\mathbf{x}_{u}^a, \mathbf{y}_u^a)$ is the $a^{\mathrm{th}}$ (processed) training samples[The exact processing of the raw data samples shall depend on the application/simulation. More details are provided in the Section <ref>.], and $\mathrm{D}_{u,\mathrm{proc}}^t$ is the total training samples.
The ue train the ml model using their processed datasets to minimize the following local loss function.

\begin{equation}
\label{localLossFunc}
\begin{aligned}
f_u (\mathbf{w} | \mathcal{D}_{u,\mathrm{proc}}^t) \coloneqq [1/\mathrm{D}_{u,\mathrm{proc}}^t] \sum\nolimits_{(\mathbf{x}_{u}^a, \mathbf{y}_u^a) \in \mathcal{D}_{u,\mathrm{proc}}^t} \mathrm{l}\left(\mathbf{w} | (\mathbf{x}_{u}^a, \mathbf{y}_u^a) \right),
\end{aligned}
\end{equation}

where $\mathrm{l}\left(\mathbf{w} | (\mathbf{x}_{u}^a, \mathbf{y}_u^a)\right)$ is the loss associated with the $a^{\mathrm{th}}$ data sample.

We consider an hfl <cit.>, where the clients share their model with their immediate upper tier, i.e., the es, since the clients cannot directly communicate with the central server.
As such, each es minimizes the following loss function.

\begin{equation}
\label{esLossAllClientsParticipate}
\begin{aligned}
f_{b} (\mathbf{w} | \mathcal{D}_{b}^t) \coloneqq \sum\nolimits_{u \in \mathcal{U}_b} \alpha_u f_u (\mathbf{w} | \mathcal{D}_{u,\mathrm{proc}}^t),
\end{aligned}
\end{equation}

where $\alpha_u$ is the weight of the $u^{\mathrm{th}}$ client in BS $b$ and $\mathcal{D}_b^t \coloneqq \bigcup_{u \in \mathcal{U}_b} \mathcal{D}_{u,\mathrm{proc}}^t$.
Note that we use the same notation $b$ in the subscript to represent the es of the $b^{\mathrm{th}}$ bs for brevity.
Furthermore, the top-most tier, i.e., the central server, minimizes the following global loss function.

\begin{equation}
\label{centralLossAllClietnsParticipate}
\begin{aligned}
f(\mathbf{w} | \mathcal{D}^t) \coloneqq \sum\nolimits_{b=0}^{B-1} \alpha_b f_b (\mathbf{w} | \mathcal{D}_{b}^t), % = \sum\nolimits_{b=0}^{B-1} \alpha_b \sum\nolimits_{u \in \mathcal{U}_b} \alpha_u^t f_u (\mathbf{w} | \mathcal{D}_{u}^t),
\end{aligned}
\end{equation}

where $\alpha_b$ is the weight of the es of the $b^{\mathrm{th}}$ bs at the central server and $\mathcal{D}^t \coloneqq \bigcup_{b=0}^{B-1} \mathcal{D}_b^t$.
Recall that clients' datasets are not stationary and keep evolving following (<ref>).
Therefore, the global optimal model $\mathbf{w}^{*}$ may not necessarily remain stationary <cit.>.
The central server thus wants to find the optimal $\mathbf{w}^{*}$ in each $t$ as follows.

\begin{equation}
\begin{aligned}
\mathbf{w}^{*} &= \underset{\mathbf{w} }{\text{arg min}} \quad f(\mathbf{w} | \mathcal{D}^t), \quad \forall t.
\end{aligned}
\end{equation}

§ RESOURCE-AWARE HIERARCHICAL FEDERATED LEARNING: CONVERGENCE ANALYSIS

Time flow in the proposed system model

§.§ Resource-Aware Hierarchical Federated Learning Model

The proposed rawhfl is designed on top of the general hfl <cit.> framework under explicit consideration of the available computational, radio and energy resources.
In the proposed rawhfl, each tier performs its local rounds before sending its updated model parameters to its upper tier.
In particular, we use the terms local round, edge round and global round to describe the local rounds of clients, es and the central server, respectively.
Fig. <ref> describes the flow of these rounds, where clients' local training happens between two edge rounds.
Besides, we consider a fully synchronous updating procedure at the upper tiers, i.e., in the es and the central server, which leads to a deadline-constrained case.
More specifically, this necessitates receiving the trained model parameters of the client at the es during the es' model update.
Moreover, due to limited resources, rawhfl considers partial client participation by only selecting $\bar{\mathcal{U}}_b^{k,e} \subseteq \mathcal{U}_b$ clients for each es (of each bs) during each edge round $e$ of each global round $k$.
Let $\mathrm{1}_{u,\mathrm{sl}}^{k,e}$ denote client's participation during $e^{\mathrm{th}}$ edge round of the $k^{\mathrm{th}}$ global round, which is defined as

\begin{equation}
\begin{aligned}
\mathrm{1}_{u,\mathrm{sl}}^{k,e} &=
\begin{cases}
1, &\text{with probability } \mathrm{p}_{u, \mathrm{sl}}^{k,e},\\
0, &\text{otherwise},
\end{cases}.
\end{aligned}
\end{equation}

It is worth noting that the objective of each es in rawhfl differs from (<ref>) when $\bar{\mathcal{U}}_b^{k,e} \subset \mathcal{U}_b$.
More specifically, each es wants to minimize the following loss in rawhfl.

\begin{equation}
\label{esLossRawHFL}
f_{b} (\mathbf{w} | \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u, \mathrm{proc}}^t ) \coloneqq \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u f_u (\mathbf{w} | \mathcal{D}_{u,\mathrm{proc}}^t),
\end{equation}

where $\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u = 1$ and $t$ is the time slot at which the $e^{\mathrm{th}}$ edge round starts.

Without loss of generality, let $\mathbf{w}^k$ and $\mathbf{w}_b^{k,e}$ denote the global model during global round $k$ and the edge model of the es of bs $b$ during the $e^\mathrm{th}$ edge round of the $k^\mathrm{th}$ global round, respectively.
When $e=0$, each es receives the updated global model from the central server.
The es then forwards its current local model to its bs, which broadcasts[Following existing literature <cit.>, downlink communication overheads are ignored in this paper.] the model to the selected clients.
Each $u \in \bar{\mathcal{U}}_b^{k,e}$ then synchronizes its local model as

\begin{equation}
\mathbf{w}_u^{k,e,0} \gets \mathbf{w}_b^{k,e}.
\end{equation}

The client then trains the received model for $\mathrm{L}_{u}^{k,e}$ sgd rounds to minimize the loss function defined in (<ref>).
As such, the local updated model is

\begin{equation}
\label{localModUp}
\begin{aligned}
\mathbf{w}_{u}^{k,e,\mathrm{L}_{u}^{k,e}}
&= \mathbf{w}_{u}^{k, e, 0} - \eta \sum\nolimits_{l=0}^{\mathrm{L}_{u}^{k,e}-1} g_u(\mathbf{w}_{u}^{k,e,l}),
\end{aligned}
\end{equation}

where $\eta$ is the learning rate and $g_u(\mathbf{w}_{u}^{k,e,l})$ is the stochastic gradient.
Note that $1 \leq \mathrm{L}_{u}^{k,e} \leq \mathrm{L}$, where $\mathrm{L}$ is the maximum local SGD rounds.
Besides, $\mathrm{L}_u^{k,e}$ can be different for different clients because each client has a deadline of $\mathrm{t_{th}}$ seconds and an energy budget of $\mathrm{e}_{u,\mathrm{bd}}$ Joules during each edge round.

Note that, in each sgd step, we let each client randomly sample $\mathrm{n}$ mini-batches, which yields the following local computation time overhead

\begin{equation}
\label{localCompTime}
\mathrm{t}_{u,\mathrm{cp}}^{k,e} = \mathrm{L}_{u}^{k,e} \times \mathrm{n} \bar{\mathrm{n}} \mathrm{c}_u \mathrm{D}_u / f_u^{k,e},
\end{equation}

where $\bar{\mathrm{n}}$, $\mathrm{c}_u$, $\mathrm{D}_u$ and $f_u^{k,e}$ are the batch size, number of cpu cycles to compute $1$-bit data, data sample size in bits, and the cpu frequency.
The corresponding energy expense is calculated as <cit.>

\begin{equation}
\begin{aligned}
\mathrm{e}_{u,\mathrm{cp}}^{k,e}
&= \mathrm{L}_{u}^{k,e} \times 0.5\zeta \mathrm{n} \bar{\mathrm{n}} \mathrm{c}_u \mathrm{D}_u (f_u^{k,e})^2,
\end{aligned}
\end{equation}

where $0.5\zeta$ is the effective capacitance of the CPU chip.

Once the local training is finished, each client sends its accumulated gradients $\tilde{g}_u^{k,e} \coloneqq \sum_{l=0}^{\mathrm{L}_u^{k,e}-1} g_u(\mathbf{w}_{u}^{k,e,l})$ to its associated bs as an encrypted payload.
This uplink communication causes time and energy overheads for the clients.
The required time to complete the uplink transmission is calculated as

\begin{equation}
\label{gradientOffload}
\mathrm{t}_{u,\mathrm{up}}^{k,e} = \mathrm{s}/ \big(\omega \log_2 \big[1 + \gamma_{u}^{k,e}\big] \big),
\end{equation}

where $\mathrm{s} = d \times (\phi+1)$ bits <cit.> is the payload size, $\phi$ is the fpp, $\omega$ is the bandwidth of a prb and $\gamma_u^{k,e}$ is the snr, which is derived as

\begin{equation}
\label{snr}
\gamma_{u}^{k,e} = \beta_{u}^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e} / (\omega \varsigma^2),
\end{equation}

where $P_{u,\mathrm{tx}}^{k,e}$ is the uplink transmission power, $\beta_u^{k,e}$ is the large-scale path loss, $\zeta_u^{k,e}$ is the log-Normal shadowing and $\varsigma^2$ is the noise variance.
Besides, we calculate the energy expense for the client's uplink transmission as

\begin{equation}
\mathrm{e}_{u,\mathrm{up}}^{k,e} = \mathrm{s} P_{u,\mathrm{tx}}^{k,e} / \big(\omega \log_2 \big[1 + \gamma_{u}^{k,e}\big]\big).
\end{equation}

Once the bs receives client's $\tilde{g}_u^{k,e}$, it forwards the payload to its es.
Note that the overheads in forwarding the received $\tilde{g}_u^{k,e}$ to the es are ignored since the es is embedded in the same bs.
When the deadline $\mathrm{t_{th}}$ expires, the es aggregates the received gradients and updates its edge model as

\begin{equation}
\label{edgeUpdateRule}
\begin{aligned}
\mathbf{w}_b^{k, e+1}
&= \mathbf{w}_{b}^{k,e} - \eta \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \big[\mathrm{1}_{u,\mathrm{sc}}^{k,e}/\mathrm{p}_{u,\mathrm{sc}}^{k,e}\big]
\tilde{g}_u^{k,e},
\end{aligned}
\end{equation}

where $\alpha_u \coloneqq 1/|\bar{\mathcal{U}}_b^{k,e}|$ and $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$ is defined as

\begin{equation}
\begin{aligned}
\mathrm{1}_{u,\mathrm{sc}}^{k,e} &=
\begin{cases}
1, &\text{with probability } \mathrm{p}_{u, \mathrm{sc}}^{k,e},\\
0, &\text{otherwise},
\end{cases}.
\end{aligned}
\end{equation}

We use $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$ to capture whether $\tilde{g}_u^{k,e}$ is received by the bs successfully within the allowable deadline.
It is worth noting that the client selection strategy can allow us to select similar computationally capable clients who can perform nearly identical local sgd rounds.
Besides, we consider mini-batch sgd, and each client selects $\mathrm{n}$ mini-batches.
As such, putting equal weight on the client's accumulated gradients is practical[Different weighting strategies can also be easily incorporated.].

Each es and bs repeats the above steps for $E$ edge rounds.
After that, each es forwards its updated edge model to the central server[The transmission between the es and the central server happens in the network's backhaul, and the corresponding time and energy overheads incur on the es and the bs. We kept our focus on the overheads for the clients and thus ignored these overheads.], which minimizes the following global loss.

\begin{equation}
\label{centralLossRawHFL}
f(\mathbf{w}^k | \cup_{b=0}^{B-1} \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u,\mathrm{proc}}^t) \coloneqq \sum\nolimits_{b=0}^{B-1} \alpha_b f_{b} \big(\mathbf{w}^k | \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u, \mathrm{proc}}^t \big).
\end{equation}

The central server aggregates the received edge models and updates the global model as

\begin{equation}
\label{globalUpdateRule}
\begin{aligned}
\rs\rs \rs \rs \mathbf{w}^{k+1}
% &= \sum_{b=0}^{B-1} \rs \alpha_b \mathbf{w}_b^{k, E}
\rs= \mathbf{w}^k \rs - \eta \sum\nolimits_{e=0}^{E-1} \sum\nolimits_{b=0}^{B-1} \rs \alpha_b \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \big[\mathrm{1}_{u,\mathrm{sc}}^{k,e} / \mathrm{p}_{u,\mathrm{sc}}^{k,e}\big] \tilde{g}_u^{k,e} \rs. \rs\rs\rs\rs
\end{aligned}
\end{equation}

The updated global model is then broadcast to the es, which forward the updated models to their bs, and each bs broadcasts the model to the selected clients.
The above process is repeated for $K$ global rounds.
These steps are summarized in Algorithm <ref>.
Note that from hereon onward, we have used $f_u(\mathbf{w})$, $f_b(\mathbf{w})$ and $f(\mathbf{w})$ to represent $f_u(\mathbf{w}| \mathcal{D}_{u,\mathrm{proc}}^t)$, $f_b(\mathbf{w} | \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u,\mathrm{proc}}^t)$ and $f(\mathbf{w} | \cup_{b=0}^{B-1} \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u,\mathrm{proc}}^t)$, respectively, for notational simplicity.

Global model: $\mathbf{w}^0$; total global round $K$, number of edge rounds $E$
$k=0$ to $K-1$
$b=1$ to $B$ in parallel
Receives updated global model $\mathbf{w}_b^{k,0} \gets \mathbf{w}^k$
$e=0$ to $E-1$

BS $b$ receives optimized $\mathrm{1}_{u, \mathrm{sl}}^{k,e}, \mathrm{L}_{u}^{k,e}$ and $f_{u}^{k,e}$ *c.f. (<ref>)
$u$ in $\bar{\mathcal{U}}_b^{k,e}$ in parallel
Get updated edge model $\mathbf{w}_{u}^{k,e,0} \gets \mathbf{w}_b^{k,e}$
Perform $\mathrm{L}_u^{k,e}$ mini-batch SGD rounds and get updated local model based on (<ref>)
Offload accumulated gradients $\tilde{g}_u^{k,e}$ to the bs

Update edge model $\mathbf{w}_b^{k, e+1}$ using update rule in (<ref>)

Update global model $\mathbf{w}^{k+1}$ based on the update rule in (<ref>)

Trained global model $\mathbf{w}^K$
RawHFL Algorithm

§.§ Convergence of RawHFL

We make the following assumptions for our theoretical analysis, which are standard in the literature <cit.>.

$\beta$-smoothness: The loss functions in all nodes are $\beta$-smooth, i.e., $\Vert \nabla f(\mathbf{w}) - \nabla f(\mathbf{w}')\Vert \leq \beta \Vert \mathbf{w} - \mathbf{w}' \Vert$, where $\Vert \cdot \Vert$ is the $L_2$ norm.

Unbiased sgd: mini-batch gradients are unbiased, i.e., $\mathbb{E}_{\xi \sim \mathcal{D}_{u,\mathrm{proc}}} \left[ g_u(\mathbf{w}) \right] = \nabla f_u(\mathbf{w})$, where $\mathbb{E} [\cdot]$ is the expectation operator, and $\xi$ is client's randomly sampled mini-batch.

Bounded variance: variance of the gradients is bounded, i.e., $\Vert g_u(\mathbf{w}) - \nabla f_u(\mathbf{w}) \Vert^2 \leq \sigma^2$.

Independence: a) the stochastic gradients are independent of each other in different episodes and b) accumulated gradient offloading is independent of client selection and each other in each edge round $e$.

Bounded divergence: divergence between the a) local and edge and b) edge and global loss functions are bounded, i.e., for all $u$, $b$ and $\mathbf{w}$

\begin{align}
&\sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \Vert \nabla f_u(\mathbf{w}) - \nabla f_b(\mathbf{w}) \Vert^2 \leq \epsilon_0^2,\\
&\sum_{b=0}^{B-1} \alpha_b \Big\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \rs \alpha_u \nabla \tilde{f}_{u} (\mathbf{w}) - \sum_{b'=0}^{B-1} \alpha_{b'} \rs \rs \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \rs\rs \alpha_{u'} \nabla \tilde{f}_{u'} (\mathbf{w}) \Big\Vert^2 \leq \epsilon_1^2, \label{ES_Central_Loss_Divergence}
\end{align}

where $\nabla \tilde{f}_u (\mathbf{w}) \coloneqq \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_u (\mathbf{w})$.

Suppose $\eta < \mathrm{min}\left\{\frac{1}{2\sqrt{5} \beta \mathrm{L}}, \frac{1}{\beta E \mathrm{L}} \right\}$ and the above assumptions hold.
Then, the average global gradient norm from $K$ global rounds of rawhfl is upper-bounded as

\begin{align}
\label{theorem1_eqn}
& \frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \big[\Vert \nabla f(\mathbf{w}^k) \Vert^2 \big]
\leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \Big\{ \mathbb{E} [ f(\mathbf{w}^k) ] - \mathbb{E} [ f(\mathbf{w}^{k+1}) ] \Big\} \nonumber\\
& + \frac{2 \beta \eta \mathrm{L} \sigma^2}{K} \sum_{k=0}^{K-1} \frac{\mathrm{N}_1^k}{\Omega^k} + \frac{18 E \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{\mathrm{N}_2}{\Omega^k} + \nonumber\\
&\frac{20 \mathrm{L} \beta^2 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{2 \beta \eta \mathrm{L}}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \times \nonumber\\
& \rs \rs \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{N}_u  \big[(1/\mathrm{p}_{u,\mathrm{sc}}^{k,e}) - 1 \big] \sum\nolimits_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \big[\big\Vert g_u (\mathbf{w}_u^{k, e, l}) \big\Vert^2 \big],
\end{align}

where the expectations depend on clients' randomly selected mini-batches and $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$'s.
Besides, $\Omega^k \coloneqq \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e}$, $\mathrm{N}_1^k \coloneqq  60 \beta^3 \eta^3 E^3 \mathrm{L}^3 + 3 \beta \eta E \mathrm{L} +  \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \left(\alpha_b + 4 E \mathrm{L} \beta \eta \right) \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2$, $\mathrm{N}_2 \coloneqq 1 + 20 \beta^2 \eta^2 E^2 \mathrm{L}^2$ and $\mathrm{N}_{u} \coloneqq  E + 3 \beta \eta \mathrm{L} + 4 \beta \eta E \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right)$.

Using the aggregation rule defined in (<ref>) and $\beta$-smoothness assumption, we start with

\begin{align}
\leq f(\mathbf{w}^k) - \nonumber \\
& \eta \bigg<\nabla f(\mathbf{w}^k),  \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} g_u\big(\mathbf{w}_u^{k, e,l}\big) \bigg> + \nonumber\\
& \frac{\beta \eta^2}{2} \bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} \bigg\Vert^2,
\end{align}

where $\left< \mathbf{a}, \mathbf{b} \right>$ is the inner product of the vectors $\mathbf{a}$ and $\mathbf{b}$.

Then, we derive the upper bounds of the second and third terms.
Plugging these results and assuming $\eta \leq \frac{1}{\beta E \mathrm{L}}$, we get the following after doing some algebraic manipulations.

\begin{align}
\label{theorem1_Mid_Bound}
&\frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \left[\left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 \right]
\leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \left[ \frac{\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right] }{\Omega^k} \right] + \nonumber\\
&\frac{2 \beta \eta \sigma^2}{K} \sum_{k=0}^{K-1} \left[\frac{\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} }{\Omega^k} \right] + \frac{2 \beta \eta E}{K} \times \nonumber\\
&\sum_{k=0}^K \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs\rs \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \rs \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \big[\big\Vert g_u (\mathbf{w}_u^{k, e, l}) \big\Vert^2 \big] + \nonumber\\
& \frac{2 \mathrm{L} \beta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] + \nonumber\\
&\frac{2 \beta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \rs \alpha_u \rs \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right]\rs. \rs
\end{align}

When learning rate $\eta \leq \mathrm{min} \left\{\frac{1}{\beta E \mathrm{L}}, \frac{1}{3\sqrt{2} \beta \mathrm{L}} \right\}$, we can derive the difference between the client's model and the es's model in (<ref>) as

\begin{align}
\label{lemama1_Eqn}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] \nonumber\\
&\leq \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \times \nonumber\\
&\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs  \alpha_u \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right].
\end{align}

Similarly, when $\eta < \mathrm{min}\left\{\frac{1}{2\sqrt{5} \beta \mathrm{L}}, \frac{1}{\beta E \mathrm{L}} \right\}$, we have

\begin{align}
\label{lemma2_eqn}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] \nonumber\\
&\leq \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \nonumber\\
&\frac{60 \beta^2 \sigma^2 E^3 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{180 \beta^2 \epsilon_0^2 E^3 \mathrm{L}^4 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} +\frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \big(\alpha_u + \nonumber\\
&15 E \beta^2 \eta^2 \mathrm{L}^3 \big) \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right].
\end{align}

Finally, we plug (<ref>) and (<ref>) into (<ref>) to find the final bound in (<ref>).
The detailed proof is left to the supplementary material.

The first term with $\{\cdot\}$ on the right-hand side of (<ref>) captures the change in the central server's loss function in two consecutive global rounds.
The second term with $\sigma^2$ arises due to the bounded variance assumption of the gradients.
The third and fourth terms with $\epsilon_0^2$ and $\epsilon_1^2$, respectively, appear due to the bounded divergence between the loss functions.
Moreover, the fifth term stems from the wireless channel between the clients and their serving bs.

When all clients perform the same number of sgd rounds, i.e., $\mathrm{L}_u^{k,e}=\mathrm{L}$, $\forall u, k$ and $e$, the convergence bound in Theorem <ref> boils down to

\begin{align*}
\label{corr0}
& \frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \big[\Vert \nabla f(\mathbf{w}^k) \Vert^2 \big]
\leq \frac{2 ( \mathbb{E} [f(\mathbf{w}^0)] - \mathbb{E} [ f(\mathbf{w}^{K}) ])} {\eta E K \mathrm{L}} + \nonumber\\
&[2 \beta \eta \sigma^2 / (E K) ] \sum\nolimits_{k=0}^{K-1} \mathrm{N}_1^k + 18 \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^2 \mathrm{N}_2 + 20 \beta^2 \epsilon_1^2 \eta^2 E^2 +\nonumber\\
& \frac{2 \beta \eta}{E K} \sum_{k=0}^K \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs\rs \alpha_u \mathrm{N}_u \rs\rs \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \big[\big\Vert g_u (\mathbf{w}_u^{k, e, l}) \big\Vert^2 \big],
\end{align*}

Moreover, when $\mathrm{p}_{u,\mathrm{sc}}^{k,e}$'s are $1$'s, i.e., all selected clients' accumulated gradients are received successfully, we have

\begin{align}
& \frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \big[\Vert \nabla f(\mathbf{w}^k) \Vert^2 \big]
\leq \frac{2 ( \mathbb{E} [f(\mathbf{w}^0)] - \mathbb{E} [ f(\mathbf{w}^{K}) ])} {\eta E K \mathrm{L}} + \nonumber\\
& \frac{2 \beta \eta \sigma^2}{E K} \sum\nolimits_{k=0}^{K-1} \mathrm{N}_1^k + 18 \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^2 \mathrm{N}_2 + 20 \beta^2 \epsilon_1^2 \eta^2 E^2,
\end{align}

which is analogous to existing studies <cit.>.

From the above Theorem and Corollary, it is quite evident that the convergence bound depends on $\bar{\mathcal{U}}_b^{k,e}$'s, $\Omega^k$'s and $\mathrm{p}_{u,\mathrm{sc}}^{k,e}$'s.
As such, in the sequel, we optimize the intertwined fl and wireless networking parameters jointly in order to facilitate rawhfl's convergence.

§ RAWHFL: JOINT PROBLEM FORMULATION AND SOLUTIONS

§.§ Joint Problem Formulation

Based on the theoretical analysis in Section <ref>, we want to focus on the controllable terms of the convergence bound in (<ref>), which are $\bar{\mathcal{U}}_b^{k,e}$'s, $\Omega^k$'s and $\mathrm{p}_{u,\mathrm{sc}}^{k,e}$'s, such that the average global gradient norm after $K$ global rounds is minimized.
Intuitively, some clients may have some predicaments in performing local model training due to multifarious factors, such as residing at the cell edge, poor wireless channel quality, limited energy budget and low computational resources, to name a few.
Besides, while a large $\mathrm{L}_u^{k,e}$ may increase $\Omega^k$, which improves the convergence rate, this is more complex in a constrained wireless network for the following reasons.
More sgd rounds mean more local training overheads, leaving less time and energy for the uplink transmission once the local training is over.
Therefore, if the clients do not have sufficient time and energy left to transmit their trained accumulated gradients, the bs and, hence, the es cannot utilize these clients' contributions in the edge model aggregation.
Moreover, if $\mathrm{p}_{u,\mathrm{sc}}^{k,e}=0$, the last term of (<ref>) can blow up, making the theoretical bound $\infty$.
As such, it is critical to jointly optimize client selection and clients' local sgd rounds, cpu frequencies and transmission powers to make the convergence rate faster.

To that end, each client transmits its accumulated gradients $\tilde{g}_u^{k,e}$ as a single wireless packet.
Besides, as modern wireless networks have countermeasures for packet loss[All practical wireless networks have cyclic redundancy check, hybrid automatic repeat request and error correction mechanisms in place <cit.>.], we assume that the transmitted packet can be decoded error-free if received during the aggregation time.
In particular, we define $\mathrm{p}_{u,\mathrm{sc}}^{k,e} = \mathrm{Pr}\{[ \mathrm{t}_{u,\mathrm{cp}}^{k,e} + \mathrm{t}_{u,\mathrm{up}}^{k,e} \leq \mathrm{t_{th}}\}$.
Then, we enforce $\mathrm{t}_{u,\mathrm{cp}}^{k,e} + \mathrm{t}_{u,\mathrm{up}}^{k,e} \leq \mathrm{t_{th}}$ as a constraint to ensure $\mathrm{p}_{u,\mathrm{sc}}^{k,e}=1$ so that the last term in (<ref>) becomes $0$.
Moreover, from (<ref>) and (<ref>), it is evident that $\mathrm{p}_{u,\mathrm{sc}}^{k,e}$ depends on $\mathrm{L}_{u}^{k,e}$, $f_u^{k,e}$ and $P_{u,\mathrm{tx}}^{k,e}$.
Due to these facts, we pose the following optimization problem that can be solved in each edge round to jointly configure the intertwined optimization variables.

\begin{align}
\underset{\pmb{\mathrm{1}}_{\mathrm{sl}}^{k,e}, \pmb{\mathrm{L}}^{k,e}, \pmb{f}^{k,e}, \pmb{P}_{\mathrm{tx}}^{k,e}}{ \mathrm{min} } \quad \varphi_b^{k,e} \coloneqq \frac{1}{\sum\nolimits_{b=0}^{B-1}  \alpha_b \sum\nolimits_{u \in \mathcal{U}_b} \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot [\alpha_u \mathrm{L}_u^{k,e} ] } \\
&\mathrm{s.t.} \quad C_1:  \quad \mathrm{1}_{u,\mathrm{sl}}^{k,e} \in \{0,1\}, \quad \forall u, k, e\\
&\quad C_2: \quad \sum\nolimits_{u \in \mathcal{U}_b} \mathrm{1}_{u,\mathrm{sl}}^{k,e} = Z, \quad \forall b, k, e \\
&\quad C_3: \begin{cases}
\left(\pmb{\mathrm{1}}_{b,\mathrm{sl}}^{k,e}\right)^T \pmb{\mathrm{1}}_{b, \mathrm{sl}}^{k,e-1} \leq \Psi, & \text{if } k=0 ~\&~ 1\leq e \leq E-1, \\
\left(\pmb{\mathrm{1}}_{b, \mathrm{sl}}^{k,e}\right)^T \pmb{\mathrm{1}}_{b,\mathrm{sl}}^{k-1,E-1} \leq \Psi, & \text{if } k \neq 0 ~\&~ (e+1)=E,
\end{cases} \label{cons_C3} \\
&\quad C_4: \quad 1 \leq \mathrm{L}_u^{k,e} \leq \mathrm{L}, ~ \mathrm{L}_u^{k,e} \in \mathbb{Z}^{+}, \quad \forall u, k, e \\
&\quad C_5: \quad f_u^{k,e} \leq f_{u, \mathrm{max}},
\quad \forall u, k, e\\
&\quad C_6: \quad 0 \leq P_{u,\mathrm{tx}}^{k,e} \leq P_{u, \mathrm{max}}, \quad \forall u, k, e\\
&\quad C_7: \quad \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot [ \mathrm{t}_{u,\mathrm{cp}}^{k,e} + \mathrm{t}_{u,\mathrm{up}}^{k,e} ] \leq \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot \mathrm{t_{th}}, \quad \forall u, k, e \\
&\quad C_8: \quad \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot [\mathrm{e}_{u,\mathrm{cp}}^{k,e} + \mathrm{e}_{u,\mathrm{up}}^{k,e} ] \leq \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot \mathrm{e}_{u, \mathrm{bd}}, \forall u, k, e
\end{align}

where $\pmb{\mathrm{1}}_{b,\mathrm{sl}}^{k,e} = \big\{\mathrm{1}_{u,\mathrm{sl}}^{k,e}\big\}_{u\in\mathcal{U}_b}$, $\pmb{\mathrm{1}}_{\mathrm{sl}}^{k,e}=\big\{\pmb{\mathrm{1}}_{b,\mathrm{sl}}^{k,e}\big\}_{b=0}^{B-1}$, $\pmb{\mathrm{L}}^{k,e}=\Big\{\big\{\mathrm{L}_u^{k,e}\big\}_{u \in \mathcal{U}_b}\Big\}_{b=0}^{B-1}$, $\pmb{f}^{k,e}=\Big\{\big\{f_u^{k,e}\big\}_{u \in \mathcal{U}_b}\Big\}_{b=0}^{B-1}$, $\pmb{P}_{\mathrm{tx}}^{k,e}=\Big\{\big\{P_{u,\mathrm{tx}}^{k,e}\big\}_{u \in \mathcal{U}_b}\Big\}_{b=0}^{B-1}$ and $\Psi$ is a positive constant.
Note that $C_1$ is the binary client selection constraint, while $C_2$ ensures only $Z$ clients are selected in each bs.
Besides, $C_3$ ensures that at least $\Psi$ new clients are selected in two consecutive edge rounds.
Furthermore, constraints $C_4$, $C_5$ and $C_6$ confirm that the client selects its local iteration, cpu frequency and transmission power within the upper bounds, respectively.
Finally, constraints $C_7$ and $C_8$ satisfy the deadline and energy constraints, respectively.

While problem (<ref>) can find the decision variables for each edge round, it may not optimally minimize the right-hand side of (<ref>).
As the controllable terms can change in each edge round, one should minimize the right-hand side of (<ref>) for all edge rounds at the beginning of the first global round, i.e., before starting the model training, to get the optimal solution.
However, since the wireless links between the clients and the bs vary and are unknown beforehand, it is impossible to know the optimal parameters for all edge rounds of all global rounds at the beginning of model training.
Therefore, a myopic perspective is necessary to optimize the decision variables in each edge round.

The clients can share their $P_{u, \mathrm{max}}$'s, $f_{u,\mathrm{max}}$'s and $\mathrm{e}_{u,\mathrm{bd}}$'s with their associated bs.
Then, the bs can collaborate since they are under the same isp, which allows the isp to solve (<ref>) centrally.
Once the problem is solved, each bs can broadcast the optimized parameters to the selected clients.
However, (<ref>) is a binary mixed-integer non-linear optimization problem and is NP-hard.
Therefore, in the following, we first transform this complex problem into a weighted utility minimization problem, followed by approximating the non-convex constraints and solving the transformed problem using an iterative solution.

§.§ Problem Transformations and Solution

Intuitively, one may equivalently choose $\varphi_b^{k,e} \coloneqq - \sum\nolimits_{b=0}^{B-1}\alpha_b \sum\nolimits_{u \in \mathcal{U}_b} \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot [\alpha_u \mathrm{L}_u^{k,e} ]$ as the objective function in (<ref>), which should be minimized if the clients are selected to maximize the weighted summation of their $\mathrm{L}_u^{k,e}$'s.
However, neither the equivalent objective nor the original one in (<ref>) seeks an energy-efficient solution, as the clients with the maximum possible $\mathrm{L}_u^{k,e}$'s are likely to be selected with these two objective functions.
Besides, it is practical to consider that clients may request new content only after watching the previously requested video content.
As such, a new training sample may only be available at the client's local dataset after a while.
Due to these factors, we consider that the interval between two edge rounds, i.e., $\mathrm{t_{th}}$, is at least as long as the duration of the video.
Therefore, we concentrate on the energy costs.
More specifically, we revise $\varphi_b^{k,e}$ to balance the weight between $\mathrm{L}_{u}^{k,e}$'s and the corresponding energy expenses of the clients as

\begin{align}
\label{utilFunc}
\varphi_b^{k,e} \coloneqq & - \theta \sum\nolimits_{b=0}^{B-1}\alpha_b \sum\nolimits_{u \in \mathcal{U}_b} \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot [\alpha_u \mathrm{L}_u^{k,e} ] + \nonumber\\
&\qquad (1-\theta)\sum\nolimits_{b=0}^{B-1}\alpha_b \sum\nolimits_{u \in \mathcal{U}_b} \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot [\alpha_u \mathrm{e}_{u,\mathrm{tot}}^{k,e} ],
\end{align}

where $\mathrm{e}_{u, \mathrm{tot}}^{k,e} = \mathrm{e}_{u, \mathrm{cp}}^{k,e} + \mathrm{e}_{u, \mathrm{up}}^{k,e}$ and $\theta \in [0,1]$.

Since the problem is still non-convex and NP-hard, we introduce relaxations that allow the problem to be solved more efficiently.
At first, we drop the integer constraint on $\mathrm{L}_{u}^{k,e}$.
Let $\bar{\mathrm{L}}_{u}^{k,e} \coloneqq \mathrm{1}_{u,sl}^{k,e} \cdot \mathrm{L}_{u}^{k,e}$ be a new variable.
Then, we introduce the following constraints to replace the multiplication of the binary and continuous variables.

\begin{align}
1 \cdot \mathrm{1}_{u, \mathrm{sl}}^{k,e} &\leq \bar{\mathrm{L}}_{u}^{k,e} \leq \mathrm{L} \cdot \mathrm{1}_{u, \mathrm{sl}}^{k,e}; \quad 0 \leq \bar{\mathrm{L}}_{u}^{k,e} \leq \mathrm{L}. \label{sgdIterC1}\\
1 \cdot (1 - \mathrm{1}_{u, \mathrm{sl}}^{k,e}) &\leq \mathrm{L}_{u}^{k,e} - \bar{\mathrm{L}}_{u}^{k,e} \leq \mathrm{L} \cdot (1 - \mathrm{1}_{u,\mathrm{sl}}^{k,e}) \label{sgdIterC2}.\\
\bar{\mathrm{L}}_{u}^{k,e} &\leq \mathrm{L}_u^{k,e} + (1 - \mathrm{1}_{u,\mathrm{sl}}^{k,e}) \mathrm{L} \label{sgdIterC3}.
\end{align}

After this, we equivalently transform the binary client selection constraint as

\begin{align}
&\sum_{b=0}^{B-1}\sum_{u \in \mathcal{U}_b} \mathrm{1}_{u,\mathrm{sl}}^{k,e} - \sum_{b=0}^{B-1}\sum_{u \in \mathcal{U}_b} (\mathrm{1}_{u,\mathrm{sl}}^{k,e} )^2 \leq 0, \label{transformBinaryClientSel} \\
& 0 \leq \mathrm{1}_{u,\mathrm{sl}}^{k,e} \le 1.
\end{align}

We then use (<ref>) in objective function (<ref>) to add a penalty when the client selection decision is not $0$ or $1$ as

\begin{align}
&\tilde{\varphi}_b^{k,e} \coloneqq - \beta \sum\nolimits_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \mathcal{U}_b} \rs\rs \alpha_u \bar{\mathrm{L}}_u^{k,e} + (1-\beta)\sum\nolimits_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \mathcal{U}_b} \rs \rs \alpha_u [\Tilde{\mathrm{e}}_{u,\mathrm{cp}}^{k,e} + \nonumber\\
&~ \Tilde{\mathrm{e}}_{u,\mathrm{up}}^{k,e} ] + \varrho \big( \sum\nolimits_{b=0}^{B-1} \sum\nolimits_{u \in \mathcal{U}_b} \mathrm{1}_{u,\mathrm{sl}}^{k,e} - \sum\nolimits_{b=0}^{B-1}\sum\nolimits_{u \in \mathcal{U}_b} (\mathrm{1}_{u,\mathrm{sl}}^{k,e} )^2 \big),
\label{utilFuncWithPenalty}
\end{align}

where $\Tilde{\mathrm{e}}_{u,\mathrm{cp}}^{k,e} = \bar{\mathrm{L}}_u^{k,e} \times 0.5\zeta \mathrm{n} \bar{\mathrm{n}} \mathrm{c}_u \mathrm{D}_u (f_u^{k,e})^2$, $\Tilde{\mathrm{e}}_{u,\mathrm{up}}^{k,e} = \mathrm{s} P_{u,\mathrm{tx}}^{k,e} \mathrm{1}_{u,\mathrm{sl}}^{k,e} / \big(\omega \log_2 \big[1 + \gamma_{u}^{k,e}\big]\big)$ and $\varrho > 0$ is a positive constant.
However, the last quadratic term in (<ref>) is still a problem and is thus approximated using a first-order Taylor series, resulting in the following modified objective function.

\begin{align}
\label{objFunc}
&\rs\rs \rs \Bar{\varphi}_b^{k,e} \coloneqq - \beta \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \mathcal{U}_b} \rs \rs \alpha_u \bar{\mathrm{L}}_u^{k,e} + (1-\beta)\sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \mathcal{U}_b} \rs \rs \alpha_u [\Bar{\mathrm{e}}_{u,\mathrm{cp}}^{k,e} + \Bar{\mathrm{e}}_{u,\mathrm{up}}^{k,e} ] + \nonumber\\
& \varrho \big( \sum\nolimits_{b=0}^{B-1} \sum_{u \in \mathcal{U}_b} \rs [1 - 2 \cdot \mathrm{1}_{u,\mathrm{sl}}^{k,e,(i)} ] \mathrm{1}_{u,\mathrm{sl}}^{k,e} + \rs \sum\nolimits_{b=0}^{B-1} \sum_{u \in \mathcal{U}_b} \rs (\mathrm{1}_{u,\mathrm{sl}}^{k,e, (i)} )^2 \big), \rs\rs \rs
\end{align}

where $\bar{\mathrm{e}}_{u,\mathrm{cp}}^{k,e} = \zeta \mathrm{n} \bar{\mathrm{n}} \mathrm{c}_u \mathrm{D}_u f_u^{k,e,(i)} \big[0.5 f_u^{k,e,(i)} \bar{\mathrm{L}}_u^{k,e} + \bar{\mathrm{L}}_u^{k,e,(i)} f_u^{k,e} - f_u^{k,e,(i)} \bar{\mathrm{L}}_u^{k,e,(i)} \big]$ and $\mathrm{1}_{u,\mathrm{sl}}^{k,e,(i)}$, $\bar{\mathrm{L}}_u^{k,e,(i)}$ and $f_u^{k,e,(i)}$ are some initial feasible points.

We now turn the focus on the non-convex constraints.
First, we approximate the energy requirement for the accumulated gradient offloading as

\begin{align}
\label{offloadEnergyApprox}
\Tilde{\mathrm{e}}_{u,\mathrm{up}}^{k,e}
&\approx \frac{\mathrm{s} \log(2)}{\omega} \bigg[ P_{u,\mathrm{tx}}^{k,e,(i)} \mathrm{1}_{u,\mathrm{sl}}^{k,e} \Big/ \log\bigg[1 + \frac{\beta_u^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)} }{\omega \varsigma^2} \bigg] + \nonumber\\
&\frac{\mathrm{1}_{u,\mathrm{sl}}^{k,e,(i)} \log\bigg[1 + \frac{\beta_u^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)} }{\omega \varsigma^2} \bigg] - \frac{\beta_u^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)} \mathrm{1}_{u,\mathrm{sl}}^{k,e,(i)} }{\omega\varsigma^2 + \beta_u^{k,e}\zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)} } }{\left(\log\bigg[1 + \frac{\beta_u^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)} }{\omega \varsigma^2} \bigg] \right)^2} \times \nonumber\\
& \left(P_{u,\mathrm{tx}}^{k,e} - P_{u,\mathrm{tx}}^{k,e,(i)}\right) \bigg]
\coloneqq \Bar{\mathrm{e}}_{u,\mathrm{up}}^{k,e}
\end{align}

Similarly, we approximate the non-convex local computation time as

\begin{align}
\bar{\mathrm{t}}_{u,\mathrm{cp}}^{k,e}
% = \frac{\mathrm{n} \mathrm{c}_u \mathrm{D}_u \bar{\mathrm{L}}_{u}^{k,e}} {f_u^{k,e}}
\rs \approx [\mathrm{n} \bar{\mathrm{n}} \mathrm{c}_u \mathrm{D}_u/f_u^{k,e,(i)}] \big(\bar{\mathrm{L}}_u^{k,e,(i)} \rs - \bar{\mathrm{L}}_{u}^{k,e,(i)} f_u^{k,e} / f_u^{k,e,(i)} \rs + \bar{\mathrm{L}}_u^{k,e}  \big)\!,\rs\rs
\end{align}

Furthermore, the non-convex offloading time constraint is approximated as follows:

\begin{align}
&\tilde{\mathrm{t}}_{u,\mathrm{up}}^{k,e} \coloneqq \mathrm{1}_{u,\mathrm{sl}}^{k,e} \cdot \mathrm{s} / \bigg(\omega \log_2 \bigg[1 + \frac{\beta_{u}^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e}}{\omega \varsigma^2} \bigg] \bigg) \nonumber\\
&\approx \frac{\mathrm{s} \log(2)}{\omega}\bigg[  \mathrm{1}_{u,\mathrm{sl}}^{k,e}/ \log \bigg[1 + \frac{\beta_{u}^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)}}{\omega \varsigma^2} \bigg]  - \nonumber\\
& \frac{\mathrm{1}_{u, \mathrm{sl}}^{k,e,(i)} \beta_{u}^{k,e} \zeta_u^{k,e} }{\left(\omega\varsigma^2 + \beta_{u}^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)} \right) \left( \log \bigg[1 + \frac{\beta_{u}^{k,e} \zeta_u^{k,e} P_{u,\mathrm{tx}}^{k,e,(i)}}{\omega \varsigma^2} \bigg] \right)^2} \times \nonumber\\
& \left(P_{u,\mathrm{tx}}^{k,e} - P_{u,\mathrm{tx}}^{k,e,(i)} \right) \bigg]
\coloneqq \bar{\mathrm{t}}_{u,\mathrm{up}}^{k,e}
\end{align}

To that end, we pose the transformed problem as

\begin{align}
\underset{\pmb{\mathrm{1}}_{\mathrm{sl}}^{k,e}, \bar{\pmb{\mathrm{L}}}^{k,e}, \pmb{\mathrm{L}}^{k,e}, \pmb{f}^{k,e}, \pmb{P}^{k,e} }{ \mathrm{min} } \quad \bar{\varphi}_b^{k,e} \\
&\mathrm{s.t.} \quad  \quad 0 \leq \mathrm{1}_{u,\mathrm{sl}}^{k,e} \leq 1, \quad \forall u,k,e \\
&\qquad \quad C_2, C_3, ~ 1 \leq \mathrm{L}_u^{k,e} \leq \mathrm{L}, ~ (\ref{sgdIterC1}), (\ref{sgdIterC2}), (\ref{sgdIterC3}), C_5, C_6 \\
&\qquad \quad \bar{\mathrm{t}}_{u,\mathrm{cp}}^{k,e} + \bar{\mathrm{t}}_{u,\mathrm{up}}^{k,e} \leq \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot \mathrm{t_{th}}, \quad \forall u, k, e \\
&\qquad \quad \bar{\mathrm{e}}_{u,\mathrm{cp}}^{k,e} + \bar{\mathrm{e}}_{u,\mathrm{up}}^{k,e} \leq \mathrm{1}_{u, \mathrm{sl}}^{k,e} \cdot \mathrm{e}_{u, \mathrm{bd}}, \forall u, k, e
\end{align}

where the constraints are similar as in (<ref>).

Initial points $\mathrm{1}_{u,\mathrm{sl}}^{k,e,(i)}$'s, $\bar{\mathrm{L}}_{u}^{k,e,(i)}$, $\mathrm{L}_{u}^{k,e,(i)}$, $f_u^{k,e,(i)}$'s, $P_{u,\mathrm{tx}}^{k,e,(i)}$'s, $i=0$, total iteration $I$, precision level $\bar{\varepsilon}$ and $\rho$
$i \gets i+1$
Solve (<ref>) using $\mathrm{1}_{u,\mathrm{sl}}^{k,e,(i-1)}$'s, $\mathrm{L}_{u}^{k,e,(i-1)}$, $\bar{\mathrm{L}}_{u}^{k,e,(i-1)}$, $f_u^{k,e,(i-1)}$'s, $P_{u,\mathrm{tx}}^{k,e,(i-1)}$'s and $\rho$, and get optimized $\mathrm{1}_{u,\mathrm{sl}}^{k,e}$'s, $\mathrm{L}_{u}^{k,e}$'s, $\bar{\mathrm{L}}_{u}^{k,e}$'s, $f_u^{k,e}$'s and $P_{u,\mathrm{tx}}^{k,e}$'s
$\mathrm{1}_{u,\mathrm{sl}}^{k,e,(i)} \gets \mathrm{1}_{u,\mathrm{sl}}^{k,e}$; $\mathrm{L}_{u}^{k,e,(i)} \gets \mathrm{L}_u^{k,e}$; $\bar{\mathrm{L}}_{u}^{k,e,(i)} \gets \bar{\mathrm{L}}_{u}^{k,e}$; $f_u^{k,e,(i)} \gets f_u^{k,e}$; $P_{u,\mathrm{tx}}^{k,e,(i)} \gets P_{u,\mathrm{tx}}^{k,e}$

Until converge with precision $\bar{\varepsilon}$ or $i=I$
Optimal $\mathrm{1}_{u,\mathrm{sl}}^{k,e}$'s, $\mathrm{L}_{u}^{k,e}$'s, $\bar{\mathrm{L}}_{u}^{k,e}$'s, $f_u^{k,e}$'s and $P_{u,\mathrm{tx}}^{k,e}$'s
Iterative Solution for (<ref>)

This transformed problem (<ref>) now belongs to the class of “difference of convex programming" problems.
Starting with some initial feasible points, we can iteratively solve the problem using existing tools such as CVX <cit.>.
In particular, we use Algorithm <ref> to solve this problem.
Note that the above iterative solution is well known to converge to a local stationary point of the original problem in polynomial time <cit.>.
Problem (<ref>) has $5U$ decision variables and $(2B+12U)$ constraints.
As such, the worst-case time complexity of running Algorithm <ref> for $I$ iterations is $\mathcal{O}\left(I \times 125U^3 [12U+2B]\right)$ <cit.>.
It is worth noting that while the proposed algorithm yields a sub-optimal solution, the empirical performance of the proposed rawhfl is nearly identical to the performance of the ideal case hfedavg <cit.>.

§ SIMULATION RESULTS AND DISCUSSIONS

Locations of the ue and bs in one realization

§.§ Simulation Setting

We perform extensive simulations with different parameter settings to show the performance of the proposed solution.
We consider a total $B=4$ bs, each serving $|\mathcal{U}_b|=12$ ue with a coverage radius of $400$ meters, as shown in Fig. <ref>.
Therefore, there are total $U=48$ clients.
Besides, $G=8$, $\bar{C}_g=32, \forall g$, $C=256$, $K=100$, $E=4$, $\mathrm{L}=50$, $\mathrm{n}=10$, $\bar{\mathrm{n}}=32$, $\phi=32$ <cit.>, $\zeta=2\times10^{-28}$ <cit.>, $I=50$, $\rho=1$, $\theta=0.4$ and $\kappa=\mathrm{t_{th}}=150$ seconds.
We uniformly randomly select the activity levels $p_{u,\mathrm{ac}}$'s and the probability of exploiting similar content in the same genre $\upsilon_u$'s from $[0.2, 0.8]$ and $[0.1, 0.8]$, respectively.
Furthermore, for the genre preferences $p_{u,g}$'s, we use $\mathrm{Dir}(\pmb{0.3})$.
The $c_u$'s, $f_{u,\mathrm{max}}$'s, $\mathrm{e}_{u,\mathrm{bd}}$'s and $P_{u, \mathrm{max}}$'s are uniformly randomly drawn from $[25, 40]$ cycles, $[1.2, 2.0]$ GHz, $[0.8, 1.5]$ Joules and $[20,30]$ dBm, respectively.
The carrier frequency is $2.4$ GHz.
The prb size is $\omega=3 \times 180$ kHz, while we vary the number of prb based on $|\Bar{\mathcal{U}}_b^{k,e}|$'s.
We model the path loss and line-of-sight probabilities following the $3$GPP urban macro model <cit.>.
A simple fully connected (FC) neural network[Our proposed rawhfl solution is general.
Other ml models, e.g., rnn or transformers, can also be used.] with the following architecture: $\mathrm{FC}(\mathrm{input\_shape}, 512) \rightarrow \mathrm{FC}(512, 256) \rightarrow \mathrm{FC}(256, \mathrm{output\_shape})$ is used.
Moreover, a sliding window technique is used to prepare the processed datasets $\mathcal{D}_{u,\mathrm{proc}}^t$'s for model training.
Particularly, we consider that each client processes its raw dataset such that the previous slot's requested content's feature set and the current slot's requested content ID are used as the feature and label, respectively.
Finally, as the clients are randomly dropped, and their system configurations are generated randomly, we completely repeat our simulations $10$ times in order to get an average performance.
In the following, unless mentioned otherwise, the average performance from these $10$ trials is reported.

Client's eligible frequency

Optimized client selection frequencies

§.§ Performance Analysis

In a resource-constrained environment, client selection is necessary due to the following factors.
Firstly, the wireless network has limited radio resources.
In many cases, $Z < |\mathcal{U}_b|$ is realistic as a practical network has many other tasks to perform simultaneously.
Secondly, since wireless channels vary, some clients may have poor link quality that can prolong the accumulated gradient offloading.
Thirdly, some clients may not have sufficient energy budgets to offload their accumulated gradients.
Finally, depending on the system configurations, some clients may need extended time to complete the local training even though the link quality is good.
As such, appropriate client selection based on the available resources is essential.
Moreover, since we have a constrained environment, some clients may not even be eligible to participate in model training when their required time and/or energy overheads are beyond their budgets.

We observe a similar trend in our simulation results.
In Fig. <ref>, we show the eligible clients, i.e., the clients who can perform at least one local sgd round, for $K=100$ global rounds in $1$ of the $10$ simulation runs.
Recall that client selection happens in each edge round, and each global round has $E=4$ edge rounds, leading to a total $4 \times 100$ edge rounds in Fig. <ref>.
As expected, some clients are only eligible to be selected in a few edge rounds.
For example, client $45$ is eligible to be selected only in $18$ edge rounds.
Moreover, we plotted the client selection frequency with our proposed solution of (<ref>) in Fig. <ref> for different $|\mathcal{U}_b|$'s.
It is worth pointing out that Algorithm <ref> yields a sub-optimal solution while the constraint $C_3$ in (<ref>) only ensures at least $\Psi$ different clients are selected in two consecutive edge rounds.
It is worth pointing out that since Algorithm <ref> yields a sub-optimal solution, the client selection strategies may not be optimal.
Our results in Fig. <ref> validate that Algorithm <ref> finds the subset client set (and other decision variables) to minimize the objective function to satisfy all constraints.
As such, in the following, we utilize Algorithm <ref> and report the average performance of the $10$ simulation repeats.

Now, we investigate how the convergence performance of rawhfl varies with different $|\bar{\mathcal{U}}_b^{k,e}|$'s.
Intuitively, the number of available training data should affect the model performance.
When only a few clients are selected, the model is trained on the few samples of these clients.
This can be detrimental if appropriate clients are not selected, especially when data heterogeneity is severe.
As such, rawhfl may require more training to achieve a certain level of accuracy when $|\bar{\mathcal{U}}_b^{k,e}|$ is small.
Moreover, a client's content request probability from the same genre, $\upsilon_u$, determines how frequently the client requests similar content from the same genre.
A high $\upsilon_u$ means less exploration, i.e., more exploitation from the same genre.
As such, a high $\upsilon_u$ is expected to yield better prediction performance since the client has fewer variations in its content requests.

Our simulation results also show similar trends in Figs. <ref> - <ref>.
Note that these test results are the average of all clients' individual test datasets.
We observe that the value of $\upsilon_u$ governs the test accuracy and test loss.
For example, when all clients randomly select their respective $\upsilon_u$ from $0.1$ to $0.8$, the test accuracy after $K=100$ global rounds is around $45\%$.
When all clients have the same $\upsilon_u$, in Fig. <ref> and Fig. <ref>, we also observe that a large $\upsilon_u$ leads to faster convergence.
Moreover, the test loss and test accuracy performances improve when $|\bar{\mathcal{U}}_b^{k,e}|$ increases regardless of the value of $\upsilon_u$'s.
For example, with $|\bar{\mathcal{U}}_b^{k,e}|=2$, the test accuracy fluctuates when $\upsilon_u \in [0.1, 0.8]$ and $\upsilon_u=0.3$ and reaches a plateau after $K=81$ global rounds when $\upsilon_u=0.7$.
Moreover, when $\upsilon_u=0.7$, the test accuracy reaches a plateau after about $K=4$ global rounds with $|\mathcal{U}_b| \geq 4$ selected clients per bs.

Global round vs test metrics: $\upsilon_u \in [0.1, 0.8]$

Global round vs test metrics: $\upsilon_u = 0.3$

Global round vs test metrics: $\upsilon_u = 0.7$

However, while more clients, i.e., large $|\bar{\mathcal{U}}_b^{k,e}|$, may help RawHFL converge faster, that comes with higher bandwidth and energy overheads.
On the one hand, the isp will require more prb to schedule the clients for wireless transmission.
On the other hand, the total energy cost per edge round also increases since more clients participate in the training process.
However, regardless of the number of participating clients, the per-client energy cost in each edge round can be non-trivial.
More specifically, when $|\bar{\mathcal{U}}_b^{k,e}|$ increases, (<ref>) must choose the defined number of clients so that the utility function is minimized.
In doing so, it may select some clients with higher energy expenses that can be a byproduct of poor wireless links.
However, the total energy costs per client can still be similar due to varying wireless links, different local sgd rounds and sub-optimal solutions of (<ref>) in different edge rounds.
Our simulation results in Fig. <ref> and Fig. <ref> also validate these claims.
Note that Fig. <ref> shows the cdf of the total energy expenses per bs during each edge round $e$ for different client set sizes.
Besides, Fig. <ref> shows the cdf of per client total energy expense during each edge round for different $|\mathcal{U}_b|$'s.
For example, the probability of total energy expense of $50\%$ of bs are more than $3.4$ Joules, $6.6$ Joules, and $9.9$ Joules for $|\bar{\mathcal{U}}_b^{k,e}|=2$, $|\bar{\mathcal{U}}_b^{k,e}|=4$ and $|\bar{\mathcal{U}}_b^{k,e}|=6$, respectively.
Moreover, per client energy expense per edge round is quite similar in Fig. <ref>.

CDF of total energy expense in the BS

CDF of client's total energy expense

§.§ Performance Comparisons

To the best of our knowledge, no previous studies exactly considered our system design and used hfl for video caching.
Therefore, we use the traditional hfedavg algorithm <cit.> and modify it to accommodate our system model for comparison.
We consider two modifications.
The first one calculates the smallest sgd rounds that all clients can perform without violating any constraints.
We call this modified baseline hfedavg-M$1$.
There are few clients who cannot even perform a single sgd round.
These clients are dropped, and then the minimum sgd rounds that the retained clients can all perform without violating any constraints are calculated in the second modification.
We call this baseline hfedavg-M$2$.
Finally, we also consider the ideal case, where no constraints are enforced.
This one is termed hfedavg-UB and is indeed the upper bound of hfedavg <cit.>.
Note that these baselines require $Z=|\mathcal{U}_b|$ pRBS for clients' gradient sharing.

Note that hfedavg should work poorly in constrained cases, since some clients may be unable to participate in the training process due to time or energy overheads beyond the allowable budgets.
This is particularly an impediment for the hfedavg-M$1$ baseline, as all clients are required to train the same number of local sgd rounds.
Therefore, if any clients fail to participate in model training during an edge round, we discard performing model training during that edge round.
This extreme case is alleviated in the hfedavg-M$2$ baseline, where we first drop the stragglers.
As such, it is expected that hfedavg-M$1$ will perform poorly compared to the hfedavg-M$2$ baseline.
Furthermore, the hfedavg-UB baseline should provide the best possible performance, as all clients would train their local models for the maximum allowable number of sgd rounds in a perfect environment.
However, in reality, the corresponding energy overheads can be much higher than some of the client's energy budgets, which we ignore to get the upper-bounded performance.
Compared to these baselines, the proposed rawhfl selects a subset of the clients and minimizes the energy expense, since our joint objective function is designed as the weighted combination of energy expense and total local iterations of the clients.

Our simulation results in Fig. <ref> also reflect these trends.
More specifically, we observe that the test accuracies of hfedavg baselines in the constrained case lag significantly compared to the hfedavg-UB.
Besides, hfedavg-M$1$ and hfedavg-M$2$ baselines do not reach a plateau even after $K=100$ global rounds.
Furthermore, the proposed rawhfl—with $|\bar{\mathcal{U}}_b^{k,e}|=4$ clients selected per bs—performs nearly identically to the hfedavg-UB baselines in terms of test accuracy.
However, it is evident that the proposed rawhfl requires significantly lower energy to finish $K=100$ global rounds.
Particularly, the energy expense grows linearly as the global round increases with significantly steep slopes for the hfedavg-M$2$ and hfedavg-UB baselines.
Besides, it is expected that hfedavg-M$1$ has the lowest energy expense since there are many stragglers due to extreme resource constraints that lead to no model training in many edge rounds.
For example, when $K=50$, the test accuracies of hfedavg-M$1$, hfedavg-M$1$, hfedavg-UB and rawhfl are about $8.29\%$, $15.92\%$, $45.78\%$ and $46.27\%$, respectively, with energy overheads of $155.83$, $5388.07$, $6671.59$ and $1341.1$ Joules.
Moreover, the proposed rawhfl delivers nearly identical test accuracy as of the hfedavg-UB after $K=100$ global rounds with a factor 5 lower energy overheads of hfedavg-UB.

We now also compare the results with centralized sgd and naive popularity-based Top-popular baselines.
Note that in centralized sgd, we assume all datasets are available centrally to show the performance gap with rawhfl.
In particular, we consider the Top-$M$ accuracy metric, which we define as the probability that the true requested content is within the Top-$M$ predicted content.
Intuitively, the Top-$M$ accuracy should improve with the increase of $M$, as the actual requested content has a higher chance of being one of the Top-$M$ predicted content.
Moreover, while the fl algorithms are expected to exhibit the performances as observed in the above discussions, the centralized sgd is the ideal performance since the ml model gets exposed to the datasets of all clients.
Furthermore, since the clients request content following a popularity-preference tradeoff, the Top-Popular baseline is expected to perform worse.

Our simulation results in Fig. <ref> also validate the above claims.
Note that the solid lines show the mean Top-$M$ accuracy while the shaded areas show the standard deviations of the test accuracies across all $U=48$ clients in Fig. <ref>.
Particularly, our solution yields about $31.18\%$, $29.99\%$ and $37.68\%$ higher (Top-$1$) test accuracies than hfedavg-M$1$, hfedavg-M$2$ and Top-Popular baselines, respectively.
Besides, rawhfl and hfedavg-UB have nearly identical test accuracies for all $M$'s.
Furthermore, centralized sgd has about $6.91\%$ higher (Top-$1$) test accuracy than rawhfl.
Moreover, for $M \leq 7$, we see the superior performance of the centralized sgd as expected.
The rawhfl and hfedavg-UB baselines can catch up with the performance of the centralized sgd when $M \geq 8$.
The results also reveal that the actual content is almost surely within the Top-$8$ predicted contents, which can significantly help in designing the cache placement.
Moreover, for all $M$'s, the other hfedavg baselines perform poorly as those are not suitable for a resource-constrained environment.
Finally, naive popularity-based prediction does not work since the content requests are modeled following an exploration-exploitation tradeoff.

Baseline comparisons: FL round vs. accuracy and energy expense ($\upsilon_u \in [0.1, 0.8]$)

Top-$M$ accuracy comparisons: probability that requested content is in the Top-$M$ predicted content ($\upsilon_u \in [0.1, 0.8]$)

Performance comparison: $\!K\!\!=\!400$, $E\!=\!4$, $\mathrm{t_{th}}\!\!=\!150$ s, $\upsilon_u=0.3$

FL Algorithm     Test Accuracy     Energy Expense [J]
RawHFL-$|\Bar{\mathcal{U}}_b|=2$     $0.2875 \pm 0.0216$     $1411.86 \pm 114.39$
RawHFL-$|\Bar{\mathcal{U}}_b|=4$     $0.2900 \pm 0.0203$     $2726.47 \pm 196.57$
RawHFL-$|\Bar{\mathcal{U}}_b|=6$     $0.2936 \pm 0.0182$     $3936.33 \pm 245.58$
Central-SGD     $0.3993 \pm 0.0908$     N/A
H-FedAvg-M$1$     $0.1329 \pm 0.0642$     $385.86 \pm 539.42$
H-FedAvg-M$2$     $0.1417 \pm 0.0961$      $10789.89 \pm 392.03$
H-FedAvg-UB <cit.>     $0.2959 \pm 0.0170$      $13343.20 \pm 549.23$
Top-Popular     $0.0998 \pm 0.0431$     N/A

Performance comparison: $\!K\!\!=\!400$, $E\!=\!4$, $\mathrm{t_{th}}\!\!=\!150$ s, $\upsilon_u=0.7$

FL Algorithm     Test Accuracy     Energy Expense [J]
RawHFL-$|\Bar{\mathcal{U}}_b|=2$     $0.6991 \pm 0.0145$     $1397.20 \pm 113.66$
RawHFL-$|\Bar{\mathcal{U}}_b|=4$     $0.6996 \pm 0.0146$     $2697.75 \pm 183.30$
RawHFL-$|\Bar{\mathcal{U}}_b|=6$     $0.6996 \pm 0.0146$     $3929.11 \pm 242.59$
Central-SGD     $0.6967 \pm 0.0151$     N/A
H-FedAvg-M$1$     $ 0.2742 \pm 0.0575$     $321.26 \pm 475.35$
H-FedAvg-M$2$     $0.3734 \pm 0.0836$     $10794.98 \pm 372.43$
H-FedAvg-UB <cit.>     $0.6991 \pm 0.0145$      $13345.56 \pm 552.34$
Top-Popular     $0.0659 \pm 0.0377$     N/A

Performance comparison: $\!K\!\!=\!400$, $E\!=\!4$, $\mathrm{t_{th}}\!\!=\!150$ s, $\upsilon_u \in [0.1, 0.8]$

FL Algorithm     Test Accuracy     Energy Expense [J]
RawHFL-$|\Bar{\mathcal{U}}_b|=2$     $0.4487 \pm 0.1921$     $1391.57 \pm 126.04$
RawHFL-$|\Bar{\mathcal{U}}_b|=4$     $ 0.4628 \pm 0.1974$     $2681.83 \pm 179.21$
RawHFL-$|\Bar{\mathcal{U}}_b|=6$     $0.4594 \pm 0.1940$      $3971.23 \pm 264.24$
Central-SGD     $0.5319 \pm 0.1401$     N/A
H-FedAvg-M$1$     $0.1510 \pm 0.1015$     $328.21 \pm 452.40$
H-FedAvg-M$2$     $0.1629 \pm 0.1019$     $10797.98 \pm 364.41$
H-FedAvg-UB <cit.>     $0.4579 \pm 0.1988$     $13349.68 \pm 541.72$
Top-Popular     $0.0860 \pm 0.0415$     N/A

To that end, we examine how these baselines perform for different $\upsilon_u$.
As such, we list the test accuracy and energy expense of these baselines in Tables <ref> -  <ref>.
These results reveal that while rawhfl achieves nearly identical test accuracies compared to the hfedavg-UB baseline, it is more energy efficient.
Moreover, although centralized sgd outperforms the fl algorithms in all examined scenarios, the test accuracy gap with our proposed rawhfl depends on the value of the $\upsilon_u$.
Particularly, this gap is higher when $\upsilon_u$ is small and decreases as $\upsilon_u$ increases.
This is due to the fact that a higher $\upsilon_u$ increases more personalized content requests from the client's preferred genre, leading to a clear trend in their datasets.
However, a smaller $\upsilon_u$ leads to more exploration of different genres, leading to irregular request patterns that are hard to predict.
Since the centralized sgd can access all clients' training datasets, the severity of these irregularities can be predicted better with centralized sgd.

§ CONCLUSION

Considering a realistic dataset acquisition method, this paper proposed a privacy-preserving rawhfl solution for predicting users' to-be-requested content in resource-constrained wireless video caching networks.
Our theoretical analysis revealed that the convergence bound of the proposed algorithm depends on the fl and wireless networking parameters, as these parameters determine whether the es receives the trained gradients from the clients.
Besides, the formulated weighted utility function enabled energy-efficient training of the proposed rawhfl by jointly selecting clients, local training rounds, cpu frequencies and uplink wireless transmission power.
Furthermore, our extensive simulation results indicate that more clients yield better test performances at the expense of higher energy costs.
Moreover, our solution delivers nearly identical performance to the ideal case with significantly lower energy costs.

Acknowledgements: We thank Prof. Minseok Choi, Omer Gokalp Serbetci and Yijing Zhang for helpful discussions.

§ SUPPLEMENTARY MATERIAL

§.§ Key Equations

Recall that the ue minimizes the following local loss function.

\begin{equation}
\label{localLossFunc_apndx}
\begin{aligned}
f_u (\mathbf{w} | \mathcal{D}_{u,\mathrm{proc}}^t) \coloneqq [1/\mathrm{D}_{u,\mathrm{proc}}^t] \sum\nolimits_{(\mathbf{x}_{u}^a, \mathbf{y}_u^a) \in \mathcal{D}_{u,\mathrm{proc}}^t} \mathrm{l}\left(\mathbf{w} | (\mathbf{x}_{u}^a, \mathbf{y}_u^a) \right),
\end{aligned}
\end{equation}

where $\mathrm{l}\left(\mathbf{w} | (\mathbf{x}_{u}^a, \mathbf{y}_u^a)\right)$ is the loss associated with the $a^{\mathrm{th}}$ data sample.
The ue minimizes (<ref>) by taking $\mathrm{L}_u^{k,e}$ sgd steps as

\begin{equation}
\label{localModUp_apndx}
\begin{aligned}
\mathbf{w}_{u}^{k,e,\mathrm{L}_{u}^{k,e}}
&= \mathbf{w}_{u}^{k, e, 0} - \eta \sum\nolimits_{l=0}^{\mathrm{L}_{u}^{k,e}-1} g_u(\mathbf{w}_{u}^{k,e,l}),
\end{aligned}
\end{equation}

where $\eta$ is the learning rate and $g_u(\mathbf{w}_{u}^{k,e,l})$ is the stochastic gradient.

Besides, the es want to minimize the following loss

\begin{equation}
\label{esLossRawHFL_apndx}
f_{b} (\mathbf{w} | \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u, \mathrm{proc}}^t ) \coloneqq \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u f_u (\mathbf{w} | \mathcal{D}_{u,\mathrm{proc}}^t),
\end{equation}

where $\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u = 1$.
Each es follows the following aggregation rule.

\begin{equation}
\label{edgeUpdateRule_apndx}
\begin{aligned}
\mathbf{w}_b^{k, e+1}
&= \mathbf{w}_{b}^{k,e} - \eta \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \big[\mathrm{1}_{u,\mathrm{sc}}^{k,e}/\mathrm{p}_{u,\mathrm{sc}}^{k,e}\big]
\tilde{g}_u^{k,e},
\end{aligned}
\end{equation}

where $\tilde{g}_u^{k,e} \coloneqq \sum_{l=0}^{\mathrm{L}_u^{k,e}-1} g_u(\mathbf{w}_{u}^{k,e,l})$ and $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$ is defined as

\begin{equation}
\begin{aligned}
\mathrm{1}_{u,\mathrm{sc}}^{k,e} &=
\begin{cases}
1, &\text{with probability } \mathrm{p}_{u, \mathrm{sc}}^{k,e},\\
0, &\text{otherwise},
\end{cases}.
\end{aligned}
\end{equation}

The central server wants to minimize the following loss function

\begin{equation}
\label{centralLossRawHFL_apndx}
f(\mathbf{w}^k | \cup_{b=0}^{B-1} \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u,\mathrm{proc}}^t) \coloneqq \sum\nolimits_{b=0}^{B-1} \alpha_b f_{b} \big(\mathbf{w}^k | \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u, \mathrm{proc}}^t \big),
\end{equation}

where $\sum_{b=0}^{B-1}\alpha_b = 1$.
Moreover, the central server uses the following aggregation rule.

\begin{equation}
\label{globalUpdateRule_apndx}
\begin{aligned}
\mathbf{w}^{k+1}
&= \sum_{b=0}^{B-1}  \alpha_b \mathbf{w}_b^{k, E}
= \mathbf{w}^k - \eta \sum\nolimits_{e=0}^{E-1} \sum\nolimits_{b=0}^{B-1} \alpha_b \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \big[\mathrm{1}_{u,\mathrm{sc}}^{k,e} / \mathrm{p}_{u,\mathrm{sc}}^{k,e}\big] \tilde{g}_u^{k,e}.
\end{aligned}
\end{equation}

In the following, we have used $f_u(\mathbf{w})$, $f_b(\mathbf{w})$ and $f(\mathbf{w})$ to represent $f_u(\mathbf{w}| \mathcal{D}_{u,\mathrm{proc}}^t)$, $f_b(\mathbf{w} | \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u,\mathrm{proc}}^t)$ and $f(\mathbf{w} | \cup_{b=0}^{B-1} \cup_{u \in \bar{\mathcal{U}}_b^{k,e}} \mathcal{D}_{u,\mathrm{proc}}^t)$, respectively, for notational simplicity.
Moreover, from the definition of the loss functions, it is easy to notice that $\nabla f_b(\mathbf{w}) = \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}\alpha_u \nabla f_u(\mathbf{w})$ and $\nabla f(\mathbf{w}) = \sum_{b=0}^{B-1} \alpha_b \nabla f_b(\mathbf{w}) = \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}\alpha_u \nabla f_u(\mathbf{w})$.

§.§ Key Assumptions

We make the following assumptions for our theoretical analysis, which are standard in the literature <cit.>.

$\beta$-smoothness: The loss functions in all nodes are $\beta$-smooth, i.e., $\Vert \nabla f(\mathbf{w}) - \nabla f(\mathbf{w}')\Vert \leq \beta \Vert \mathbf{w} - \mathbf{w}' \Vert$, where $\Vert \cdot \Vert$ is the $L_2$ norm.

Unbiased sgd: mini-batch gradients are unbiased, i.e., $\mathbb{E}_{\xi \sim \mathcal{D}_{u,\mathrm{proc}}} \left[ g_u(\mathbf{w}) \right] = \nabla f_u(\mathbf{w})$, where $\mathbb{E} [\cdot]$ is the expectation operator, and $\xi$ is client's randomly sampled mini-batch.

Bounded variance: variance of the gradients is bounded, i.e., $\Vert g_u(\mathbf{w}) - \nabla f_u(\mathbf{w}) \Vert^2 \leq \sigma^2$.

Independence: a) the stochastic gradients are independent of each other in different episodes and b) accumulated gradient offloading is independent of client selection and each other in each edge round $e$.

Bounded divergence: divergence between the a) local and edge and b) edge and global loss functions are bounded, i.e., for all $u$, $b$ and $\mathbf{w}$

\begin{align}
&\sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \Vert \nabla f_u(\mathbf{w}) - \nabla f_b(\mathbf{w}) \Vert^2 \leq \epsilon_0^2,\\
&\sum_{b=0}^{B-1} \alpha_b \Big\Vert \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \rs \alpha_u \nabla \tilde{f}_{u} (\mathbf{w}) - \sum_{b'=0}^{B-1} \alpha_{b'} \rs \rs \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \rs\rs \alpha_{u'} \nabla \tilde{f}_{u'} (\mathbf{w}) \Big\Vert^2 \leq \epsilon_1^2, \label{ES_Central_Loss_Divergence_apndx}
\end{align}

where $\nabla \tilde{f}_u (\mathbf{w}) \coloneqq \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_u (\mathbf{w})$.

§ PROOF OF THEOREM <REF>

Suppose $\eta < \mathrm{min}\left\{\frac{1}{2\sqrt{5} \beta \mathrm{L}}, \frac{1}{\beta E \mathrm{L}} \right\}$ and the above assumptions hold.
Then, the average global gradient norm from $K$ global rounds of rawhfl is upper-bounded as

\begin{align}
\label{theorem1_eqn_apndx}
& \frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \big[\Vert \nabla f(\mathbf{w}^k) \Vert^2 \big]
\leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \Big\{ \mathbb{E} [ f(\mathbf{w}^k) ] - \mathbb{E} [ f(\mathbf{w}^{k+1}) ] \Big\} + \frac{2 \beta \eta \mathrm{L} \sigma^2}{K} \sum_{k=0}^{K-1} \frac{\mathrm{N}_1^k}{\Omega^k} + \frac{18 E \beta^2 \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{\mathrm{N}_2}{\Omega^k} + \nonumber\\
&\squad \frac{20 \mathrm{L} \beta^2 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{2 \beta \eta \mathrm{L}}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \sum\nolimits_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{N}_u  \big[(1/\mathrm{p}_{u,\mathrm{sc}}^{k,e}) - 1 \big] \sum\nolimits_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \big[\big\Vert g_u (\mathbf{w}_u^{k, e, l}) \big\Vert^2 \big],
\end{align}

where the expectations depend on clients' randomly selected mini-batches and $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$'s.
Besides, $\Omega^k \coloneqq \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e}$, $\mathrm{N}_1^k \coloneqq  60 \beta^3 \eta^3 E^3 \mathrm{L}^3 + 3 \beta \eta E \mathrm{L} +  \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b  \left(\alpha_b + 4 E \mathrm{L} \beta \eta \right) \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u\right)^2$, $\mathrm{N}_2 \coloneqq 1 + 20 \beta^2 \eta^2 E^2 \mathrm{L}^2$ and $\mathrm{N}_{u} \coloneqq  E + 3 \beta \eta \mathrm{L} + 4 \beta \eta E \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right)$.

From our aggregation rule in (<ref>), we write the following

\begin{equation}
\label{convProofMainEq}
\begin{aligned}
= f \bigg(\mathbf{w}^k - \eta \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e}\bigg)\\
&\overset{(a)}{\leq} f(\mathbf{w}^k) + \bigg<\nabla f(\mathbf{w}^k), - \eta \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e}\bigg> + \frac{\beta \eta^2}{2} \bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} \bigg\Vert^2 \\
&= f(\mathbf{w}^k) - \eta \bigg<\nabla f(\mathbf{w}^k), \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} g_u\big(\mathbf{w}_u^{k, e,l}\big) \bigg> + \frac{\beta \eta^2}{2} \bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} \bigg\Vert^2,
\end{aligned}
\end{equation}

where $(a)$ stems from $\beta$-smoothness property, i.e., $f(\mathbf{y}) \leq f(\mathbf{x}) + \left<\nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x} \right> + \frac{\beta}{2}\Vert \mathbf{y} - \mathbf{x} \Vert^2$.

Now, taking expectation over both sides of (<ref>), we get

\begin{equation}
\label{convProofMainEq_1}
\begin{aligned}
\mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right]
&\leq ~ \mathbb{E} [f(\mathbf{w}^k)] - \underbrace{\eta \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1}  \mathbb{E} \left[\bigg<\nabla f(\mathbf{w}^k), \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} g_u\big(\mathbf{w}_u^{k, e,l}\big) \bigg>\right]}_{\mathrm{T}_1} + \\
&\bquad\bquad\squad \underbrace{\frac{\beta \eta^2}{2} \mathbb{E} \bigg[\bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} \bigg\Vert^2\bigg]}_{\mathrm{T}_2},
\end{aligned}
\end{equation}

where $\mathbb{E}[\cdot]$ depends on $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$'s and clients mini-batches.

Now, we simplify the $\mathrm{T}_1$ term as

\begin{align}
\mathrm{T}_1
&\overset{(a)}{=} -\eta \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1}  \Bigg<\nabla f(\mathbf{w}^k), \frac{\mathbb{E} \left[\mathrm{1}_{u,\mathrm{sc}}^{k,e}\right]}{ \mathrm{p}_{u,\mathrm{sc}}^{k,e}} \mathbb{E} \left[g_u\big(\mathbf{w}_u^{k, e,l}\big)\right] \Bigg> \nonumber\\
&\overset{(b)}{=} -\eta \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \left<\nabla f(\mathbf{w}^k),  \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right> \nonumber \\
&= -\frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \bigg[\left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 + \left\Vert \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 - \left\Vert \nabla f(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 \bigg] \nonumber\\
&= \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \left\Vert \nabla f(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 - \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 - \nonumber\\
&\bquad \bquad \mquad \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \left
\Vert \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2,
\end{align}

where $(a)$ appears from the independence of successful offloading of $\tilde{g}_u^{k,e}$'s and stochastic gradients.
Besides, $(b)$ stems from the fact that $\mathbb{E} [\mathrm{1}_{u,\mathrm{sc}}^{k,e}] = \mathrm{p}_{u,\mathrm{sc}}^{k,e}$ and $\mathbb{E} [g_u(\mathbf{w}_u^{k,e,l})] = \nabla f_u (\mathbf{w}_u^{k,e,l})$.

We also simplify the $\mathrm{T}_2$ term as follows:

\begin{align}
\mathrm{T}_2
&\overset{(a)} = \frac{\beta \eta^2}{2} \mathbb{E} \Bigg[\Bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} - \mathbb{E} \left[ \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} \right] \Bigg\Vert^2\Bigg] + \nonumber \\
&\bquad \bquad\mquad \frac{\beta \eta^2}{2} \left(\mathbb{E} \left[ \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} \right] \right)^2 \nonumber\\
&=\frac{\beta \eta^2}{2} \mathbb{E} \Bigg[\Bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \tilde{g}_u^{k,e} - \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1}\nabla f_u (\mathbf{w}_u^{k,e,l})  \Bigg\Vert^2\Bigg] + \nonumber \\
&\bquad \bquad\mquad \frac{\beta \eta^2}{2} \left\Vert  \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \nonumber\\
&\overset{(b)}{\leq} \frac{\beta \eta^2}{2} \mathbb{E} \Bigg[\Bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} g_u (\mathbf{w}_u^{k, e, l}) \pm \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} g_u (\mathbf{w}_u^{k, e, l}) - \nonumber\\
&\bquad \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e} - 1}\nabla f_u (\mathbf{w}_u^{k,e,l})  \Bigg\Vert^2\Bigg] + \frac{\beta E \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \nonumber\\
&\overset{(c)}{\leq} \frac{\beta \eta^2}{2} \mathbb{E} \Bigg[\Bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u  \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} g_u (\mathbf{w}_u^{k, e, l}) \left(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right) + \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \Bigg\Vert^2\Bigg] \nonumber \\
&\bquad \bquad \mquad + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \nonumber\\
&\leq \beta \eta^2 \mathbb{E} \Bigg[\Bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u  \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} g_u (\mathbf{w}_u^{k, e, l}) \left(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right) \Bigg\Vert^2 \Bigg] + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 + \nonumber\\
&\bquad \bquad \beta \eta^2 \mathbb{E} \Bigg[\Bigg\Vert \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \Bigg\Vert^2\Bigg]  \nonumber\\
&\leq \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[\Bigg\Vert g_u (\mathbf{w}_u^{k, e, l}) \left(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \right) \Bigg\Vert^2 \Bigg] + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 + \nonumber\\
&\bquad \bquad \beta \eta^2 \mathbb{E} \Bigg[\Bigg\Vert \sum_{b=0}^{B-1} \alpha_b \sum_{e=0}^{E-1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \Bigg\Vert^2\Bigg] \nonumber \\
&\overset{(d)}{=} \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] \times \mathbb{E} \Bigg[\bigg(\frac{\mathrm{1}_{u,\mathrm{sc}}^{k,e}} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg)^2\Bigg]  +  \nonumber\\
& \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 + \beta \eta^2 \mathbb{E} \Bigg\{ \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \Bigg\Vert \sum_{e=0}^{E-1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \Bigg\Vert^2 \nonumber\\
& + \underbrace{\sum_{b=0}^{B-1} \alpha_b \bigg[ \sum_{e=0}^{E-1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \bigg] \times \sum_{b'=1, b' \neq b}^B \alpha_{b'}^{k} \bigg[ \sum_{e=0}^{E-1} \sum_{u \in \mathcal{U}_{b'}^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \bigg]}_{T_1}  \Bigg\}  \nonumber \\
&\overset{(e)}{=} \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 + \nonumber\\
&\bquad\bquad \beta \eta^2 \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \mathbb{E} \Bigg[ \Bigg\Vert \sum_{e=0}^{E-1} \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left( g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \right) \Bigg\Vert^2 \Bigg]  \nonumber \\
&\overset{(f)}{=} \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 + \nonumber\\
&\bquad\bquad \beta \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \Bigg[ \Bigg\Vert g_u (\mathbf{w}_u^{k, e, l}) - \nabla f_u (\mathbf{w}_u^{k,e,l}) \Bigg\Vert^2 \Bigg] \nonumber \\
&\overset{(g)}{\leq} \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 + \nonumber\\
&\bquad\bquad \beta \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \sigma^2 \nonumber\\
&= \beta \eta^2 \sigma^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \nonumber\\
& \bquad\bquad \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2,
\end{align}

where $(a)$ comes from the definition of variance.
$(b)$ stems from the fact that $\Vert \sum_{j=1}^J \mathbf{x}_j \Vert^2 \leq J \sum_{j=1}^J \Vert \mathbf{x}_j \Vert^2$, and from the convexity of $\Vert \cdot \Vert$ and Jensen inequality $\Vert \sum_{j=1}^J \alpha_j \mathbf{x}_j \Vert^2 \leq \sum_{j=1}^J \alpha_j \Vert \mathbf{x}_j \Vert^2$.
Besides, the notation $\pm~ \mathbf{x}$ is used to indicate that $(+\mathbf{x} - \mathbf{x})$ for brevity.
In $(c)$, we use the fact that $1 \leq \mathrm{L}_u^{k,e} \leq \mathrm{L}$ in the last term.
Furthermore, we get $(d)$ using the fact that $\mathrm{1}_{u,\mathrm{sc}}^{k,e}$ and $g_u(\mathbf{w}_{u}^{k,e,l})$ are independent.
$(e)$ is true since $\mathbb{E}[T_1] = 0$ from the unbiased mini-batch gradient assumption, i.e., $\mathbb{E} [g_u(\mathbf{w}_u^{k,e,l})] = \nabla f_u (\mathbf{w}_u^{k,e,l})$.
Moreover, in $(f)$, we follow similar steps as in $(d)$ and $(e)$.
Finally, $(g)$ is obtained from the bounded variance assumption of the gradients.

Now, plugging $\mathrm{T}_1$ and $\mathrm{T}_2$ into (<ref>), we get

\begin{align}
\label{convProofMainEq_11}
&\mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right]
\leq \mathbb{E} [f(\mathbf{w}^k)] + \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \left\Vert \nabla f(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 - \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 - \nonumber\\
&\frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left
\Vert \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 + \beta \eta^2 \sigma^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + \nonumber\\
&\beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \frac{\beta E \mathrm{L} \eta^2}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left\Vert  \nabla f_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \nonumber\\
&= \mathbb{E} [f(\mathbf{w}^k)] + \beta \eta^2 \sigma^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \nonumber\\
&\mquad \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \left\Vert \nabla f(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 - \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 - \nonumber\\
&\mquad \frac{\eta}{2} \left(1 - \beta \eta E \mathrm{L} \right) \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left
\Vert \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2,
\end{align}

where the last term is non-negative when $\eta \leq \frac{1}{\beta E \mathrm{L}}$, as $\Vert \cdot \Vert \geq 0$.

To that end, as we are after an upper-bound, we drop the last term using $\eta \leq \frac{1}{\beta E \mathrm{L}}$.
Then we divide both sides by $\frac{\eta}{2}$, rearrange the terms and take expectations on both sides, which yields

\begin{align}
\label{convProofMainEq_12}
% & \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2
% \leq \mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right] + \beta \eta^2 \sigma^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + \nonumber\\
% & \beta E \eta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \frac{\eta}{2} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \left\Vert \nabla f(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 \nonumber\\
% &\mquad - \frac{\eta}{2} \left(1 - \beta \eta E \mathrm{L} \right) \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \left
% \Vert \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2.
&\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \mathbb{E} \bigg[ \left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 \bigg]
\leq \frac{2\left( \mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right]\right)}{\eta} + 2 \beta \eta \sigma^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + \nonumber\\
& 2 \beta \eta E \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \underbrace{\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \bigg[\left\Vert \nabla f(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 \bigg]}_{\mathrm{T}_3}.
\end{align}

We now bound the $\mathrm{T}_3$ term as

\begin{align}
\mathrm{T}_3 &
\overset{(a)}{=} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \left[\left\Vert \sum_{b'=0}^{B-1} \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'}  \nabla f_{u'}(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right] \right\Vert^2  \nonumber\\
&\overset{(b)}{=} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \left[\left\Vert \sum_{b'=0}^{B-1} \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'} \left[ \nabla f_{u'}(\mathbf{w}^k) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right] \right\Vert^2 \right] \nonumber\\
&\overset{(c)}{\leq} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \left[\left\Vert \nabla f_{u}(\mathbf{w}^k) \pm \nabla f_{u}(\mathbf{w}_{b}^{k,e}) - \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 \right] \nonumber\\
&\overset{(d)}{\leq} 2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \left[\left\Vert \nabla f_{u}(\mathbf{w}^k) - \nabla f_{u}(\mathbf{w}_{b}^{k,e}) \right\Vert^2 \right] + 2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \left[ \left\Vert \nabla f_{u}(\mathbf{w}_{b}^{k,e}) - \nabla f_{u}(\mathbf{w}_{u}^{k,e,l}) \right\Vert^2 \right] \nonumber\\
&\overset{(e)}{\leq} 2\beta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_{u}^{k,e}-1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] + 2 \beta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] \nonumber\\
&\overset{(f)}{\leq} 2\beta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] + 2 \mathrm{L} \beta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right],
\end{align}

where, in step $(a)$, we use the fact that $\nabla f(\mathbf{w}^k) = \sum_{b'=0}^{B-1} \alpha_{b'} \sum_{u' \in \bar{\mathcal{U}}_{b'}^{k,e}} \alpha_{u'}  \nabla f_{u'}(\mathbf{w}^k)$ by definition of the global loss function in (<ref>).
Besides, we write $(b)$ because $\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u = 1$ and $\sum_{b=0}^{B-1} \alpha_b=1$.
Furthermore, $(c)$ stems from Jensen inequality and $(d)$ appears from the fact $\Vert \sum_{j=1}^J \mathbf{x}_j \Vert^2 \leq J \sum_{j=1}^J \Vert \mathbf{x}_j \Vert^2$.
Moreover, we get to $(e)$ by using $\beta$-smoothness assumption.
Finally, we write $(f)$ since $1 \leq \mathrm{L}_u^{k,e} \leq \mathrm{L}$ and $\Vert \cdot \Vert \geq 0$.

Now, plugging $\mathrm{T}_3$ into (<ref>) and averaging over $K$ global rounds, we get

\begin{align}
\label{convProofMainEq_13}
% &\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e} \mathbb{E} \bigg[ \left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 \bigg]
% \leq \frac{2\left(\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right]\right)}{\eta} + 2 \beta \eta \sigma^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}}  \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} + \nonumber\\
% & 2 \beta \eta E \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + 2\beta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right] + \nonumber\\
% & 2 \mathrm{L} \beta^2 \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] - \frac{\eta}{2} \left(1 - \beta \eta E \mathrm{L} \right) \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \bigg[ \left \Vert \nabla f_u \big(\mathbf{w}_u^{k, e,l}\big) \right\Vert^2 \bigg] \nonumber \\
&\frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \left[\left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 \right]
\leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \left[ \frac{\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right] }{\Omega^k} \right] + \frac{2 \beta \eta \sigma^2}{K} \sum_{k=0}^{K-1} \left[\frac{\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} }{\Omega^k} \right] + \nonumber\\
&\squad \frac{2 \beta \eta E}{K} \sum_{k=0}^K \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \nonumber\\
&\squad \frac{2 \mathrm{L} \beta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] + \frac{2 \beta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \rs \alpha_u \rs \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right].
\end{align}

where $\Omega^k \coloneqq \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_{u}^{k,e}$.

When learning rate $\eta < \mathrm{min} \left\{ \frac{1}{\beta E \mathrm{L}}, \frac{1}{3\sqrt{2} \beta \mathrm{L}}\right\}$, the mean square error between the local model and the ES model is upper-bounded as

\begin{align}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert \mathbf{w}_{b}^{k,e} - \mathbf{w}_{u}^{k,e,l} \right\Vert^2 \right]
\leq \frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\bquad \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs  \alpha_u \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right].
\end{align}

The proof is left to Appendix <ref>.

When learning rate $\eta < \mathrm{min}\left\{\frac{1}{2\sqrt{5} \beta \mathrm{L}}, \frac{1}{\beta E \mathrm{L}} \right\}$, the mean square error between the edge model at the ES and the global model at the central server is upper-bounded as

\begin{align}
&\frac{1}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \mathbb{E} \left[ \left\Vert \mathbf{w}^k - \mathbf{w}_{b}^{k,e} \right\Vert^2 \right] \nonumber\\
&\leq \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{60 \beta^2 \sigma^2 E^3 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{180 \beta^2 \epsilon_0^2 E^3 \mathrm{L}^4 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
&\squad \frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right) \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right].
\end{align}

The proof is left to Appendix <ref>.

Final Results:
Using Lemma <ref> and Lemma <ref>, we write

\begin{align}
% &\frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \left[\left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 \right]
% \leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \left[ \frac{\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right] }{\Omega^k} \right] + \frac{2 \beta \eta \sigma^2}{K} \sum_{k=0}^{K-1} \left[\frac{\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} }{\Omega^k} \right] + \nonumber\\
% &\frac{2 \beta \eta E}{K} \sum_{k=0}^K \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \nonumber\\
% & 2 \mathrm{L} \beta^2 \Bigg[ \frac{4 E \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{60 \beta^2 \sigma^2 E^3 \mathrm{L}^3 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{180 \beta^2 \epsilon_0^2 E^3 \mathrm{L}^4 \eta^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{10 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} +  \nonumber\\
% &\bblue{\frac{4 E \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right)^2 \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right]} \Bigg] + 2 \beta^2 \Bigg[\frac{3 E \mathrm{L}^2 \eta^2 \sigma^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\
% & \frac{9 E \epsilon_0^2 \eta^2 \mathrm{L}^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{3 \mathrm{L}^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs \rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs\rs  \alpha_u \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg]\sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[ \left\Vert g_u (\mathbf{w}_u^{k, e, l})  \right\Vert^2 \right] \Bigg].
&\frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E} \left[\left\Vert \nabla f(\mathbf{w}^k)\right\Vert^2 \right]
\leq \frac{2}{\eta K} \sum_{k=0}^{K-1} \left[ \frac{\mathbb{E} [f(\mathbf{w}^k)] - \mathbb{E} \left[ f(\mathbf{w}^{k+1}) \right] }{\Omega^k} \right] + \frac{2 \beta \eta \sigma^2}{K} \sum_{k=0}^{K-1} \left[\frac{\sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \left(\alpha_b\right)^2 \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \left(\alpha_u \right)^2 \mathrm{L}_u^{k,e} }{\Omega^k} \right] + \nonumber\\
&\frac{2 \beta \eta E}{K} \sum_{k=0}^K \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b\sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \mathrm{L}_u^{k,e} \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \bigg[\frac{1} {\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2 \right] + \nonumber\\
& \frac{8 E \mathrm{L} \beta^2 \eta^2 \sigma^2} {K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \rs \left(\alpha_u\right)^2 \mathrm{L}_u^{k,e} + \frac{120 \sigma^2 E^3 \beta^4 \eta^4 \mathrm{L}^4}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} +  \frac{360 \epsilon_0^2 E^3 \beta^4 \eta^4 \mathrm{L}^5}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \frac{20 \mathrm{L} \beta^2 \epsilon_1^2 \eta^2 E^3}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} +  \nonumber\\
&\frac{8 E \mathrm{L} \beta^2 \eta^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} \sum_{e=0}^{E-1} \sum_{b=0}^{B-1} \rs \alpha_b \rs\rs \sum_{u \in \bar{\mathcal{U}}_b^{k,e}} \alpha_u \left(\alpha_u + 15 E \beta^2 \eta^2 \mathrm{L}^3 \right) \rs \bigg[\frac{1}{\mathrm{p}_{u,\mathrm{sc}}^{k,e}} - 1 \bigg] \sum_{l=0}^{\mathrm{L}_u^{k,e} - 1} \mathbb{E} \left[\left\Vert g_u (\mathbf{w}_u^{k, e, l}) \right\Vert^2\right] + \frac{6 E \beta^2 \eta^2 \sigma^2 \mathrm{L}^2}{K} \sum_{k=0}^{K-1} \frac{1}{\Omega^k} + \nonumber\\