# Over-the-Air Federated Learning with Joint Adaptive Computation and Power
Control ††thanks: This work is supported in part by NSF-2112471 (AI-EDGE).

1st Given Name Surname  dept. name of organization (of Aff.)
name of organization (of Aff.)
City, Country
email address or ORCID  Haibo Yang, Peiwen Qiu, Jia Liu and Aylin Yener
Dept. of Electrical and Computer Engineering, The Ohio State University
{yang.9292<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper considers over-the-air federated learning (OTA-FL). OTA-FL exploits
the superposition property of the wireless medium, and performs model
aggregation over the air for free. Thus, it can greatly reduce the
communication cost incurred in communicating model updates from the edge
devices. In order to fully utilize this advantage while providing comparable
learning performance to conventional federated learning that presumes model
aggregation via noiseless channels, we consider the joint design of
transmission scaling and the number of local iterations at each round, given
the power constraint at each edge device. We first characterize the training
error due to such channel noise in OTA-FL by establishing a fundamental lower
bound for general functions with Lipschitz-continuous gradients. Then, by
introducing an adaptive transceiver power scaling scheme, we propose an over-
the-air federated learning algorithm with joint adaptive computation and power
control (ACPC-OTA-FL). We provide the convergence analysis for ACPC-OTA-FL in
training with non-convex objective functions and heterogeneous data. We show
that the convergence rate of ACPC-OTA-FL matches that of FL with noise-free
communications.

##  I Introduction

In recent years, advances in machine learning (ML) have achieved astonishing
successes in many applications that transform our society, e.g., in computer
vision, natural language processing, and robotics. Traditionally, ML training
tasks often reside in cloud-based large data-centers that process training
data in a centralized fashion. However, due to the rapidly increasing demands
for training data, high latency and costs of data transmissions, as well as
data privacy/security concerns, aggregating all data to the cloud for ML
training is unlikely to remain feasible. To address these challenges,
federated learning (FL) [1] has recently emerged as a prevailing distributed
ML paradigm. FL employs multiple clients, typically deployed over wireless
edge networks, to locally train a learning model and exchange only
intermediate updates between the server and clients. FL provides better
avenues for privacy protection by avoiding the transmission of local data,
while also being able to leverage parallel clients computation for training
speedup.

However, FL also inherits many design challenges of distributed ML. One of the
main challenges of FL stems from the communication constraint in the iterative
FL learning process, particularly in resource (bandwidth and power)-limited
wireless FL systems [2, 3, 4]. To receive the update information from multiple
clients in each round, the conventional wisdom is to use orthogonal spectral
or temporal channels for each client and avoid interference among the clients.
However, this is neither desirable (since as the number of clients increases,
the available rate per edge device decreases, lengthening the communication
duration), nor necessary (since only the aggregated model updates is needed at
the server) in FL.

Over-the-air FL (OTA-FL) has recently emerged as an effective approach in that
it exploits the superposition property of the wireless medium to perform model
aggregation “for free” by allowing simultaneous transmission of all clients’
updates [5, 6, 7]. Specifically, under OTA-FL, the server directly recovers a
noisy aggregation of the clients’ model updates that transmit in the same
spectral-temporal channel, rather than trying to decode each client’s model
update first in orthogonal spectral or temporal channels. As a result, OTA-FL
dramatically reduces the communication costs and overheads from collecting the
update from each client, and accordingly enjoys better communication
parallelism regardless of the number of clients.

However, despite of the aforementioned salient features in terms of
communication efficiency, several issues remain in OTA-FL. First, the
convergence analysis of OTA-FL often assumes noise-free communications (see
Section II for more in-depth discussions). Moreover, existing works on OTA-FL
have not considered data heterogeneity, (i.e., datasets among clients are
non-i.i.d. and with unbalanced sizes) and system heterogeneity (i.e., the
computation and communication capacities varies among clients and could be
time-varying [2, 3] simultaneously). Therefore, a fundamental question in OTA-
FL system design is: how to develop an efficient OTA-FL training algorithm
that can handle both data and system heterogeneity under noisy channels.

In this paper, we answer this question by studying the impact of channel noise
on OTA-FL and proposing an over-the-air federated learning algorithm with
joint adaptive computation and power control (ACPC-OTA-FL) for edge devices
with heterogeneous capabilities. Our main contributions are summarized as
follows:

  * •

We first characterize the training error of the conventional OTA-based FedAvg
algorithm[1] by establishing a lower bound of the convergence error under
Gaussian multiple access channels (MAC) for general functions with Lipschitz
continuous gradients. Our lower bound indicates that there is a non-vanishing
convergence error due to channel noise compared with those convergence results
of OTA-FL under the noise-free assumption. This insight motivates us to
propose our ACPC-OTA-FL algorithm that considers local computation and power
control co-design to best utilize the power resources at the edge devices.

  * •

Our ACPC-OTA-FL algorithm allows each client to (in a distributed manner)
adaptively determine its transmission power level and number of local update
steps to fully utilize the computation and communication resources. We show
that, even with non-i.i.d. and unbalanced datasets, ACPC-OTA-FL converges to a
stationary point with an $\mathcal{O}(1/\sqrt{mT})$ convergence rate for
nonconvex objective functions in training, where $m$ is the number of clients
and $T$ is the total number of training iterations. This result further
implies a linear speedup in the number of clients and matches that of the
noise-free FedAvg algorithm.

##  II Related Work

OTA-FL utilizes over-the-air computation through analog transmission in
wireless MAC [5, 8, 6, 9, 10, 11, 12, 13]. Despite the advantage of high
scalability for large amount of clients, existing works on OTA-FL[9, 10, 11,
12, 13] have empirically shown that the channel noise substantially degrades
the learning performance. Therefore, theoretically quantifying the impact of
channel noise on convergence needs more in-depth investigation (See Section
IV).

To mitigate the impacts of channel noise under limited transmission power
constraints, one popular approach is to utilize uniform transceiver scaling
for all clients. For example, references [12, 11, 14] have considered an
identical sparsity pattern to reduce communication overhead. Reference [15]
has proposed a new learning rate scheme that considers the quality of the
gradient estimation; Reference [16] has developed a uniform-forcing
transceiver scaling for OTA function computation, while the work in [17] has
studied the optimal power control problem by taking gradient statistics into
account. Reference [18] has proposed an uniform transceiver scaling by
considering data heterogeneity. A common approach of these existing works
above is to formulate the power control problem separately to satisfy the
power constraints after the local computation at clients. Moreover, data and
system heterogeneity and adapting the power resources for computation is not
tied to transmission power control, despite the fact that each edge device is
constrained in total power that is needed for both computation and
communication. Due to the coupling of computation and communication processes,
a joint adaptive computation and power control for OTA-FL is necessary in
order to better mitigate the combined impacts of channel noise, power
constraints, as well as data and system heterogeneity, which constitutes the
main goal of this paper.

##  III System Model

In this section, we first introduce our OTA-FL model in Section III-A and then
the communication model in Section III-B.

###  III-A Over-the-Air Federated Learning Model

We consider a FL system with one server and $m$ clients in total. Each client
$i\in[m]$ contains a private local dataset $D_{i}$. Each local dataset $D_{i}$
is i.i.d. sampled from a distribution $\mathcal{X}_{i}$. In this paper, we
consider non-i.i.d. datasests across users, i.e.,
$\mathcal{X}_{i}\neq\mathcal{X}_{j}$ if $i\neq j,\forall i,j\in[m]$. The goal
of FL is to collaboratively train a global learning model by solving an
optimization problem in the form of:

$\min_{\mathbf{x}\in\mathbb{R}^{d}}F(\mathbf{x})\triangleq\min_{\mathbf{x}\in\mathbb{R}^{d}}\sum_{i\in[m]}\alpha_{i}F_{i}(\mathbf{x},D_{i}),$
(1)

where $\mathbf{x}\in\mathbb{R}^{d}$ is the model parameter,
$\alpha_{i}=\frac{|D_{i}|}{\sum_{i\in[m]}|D_{i}|}$ denotes the proportion of
client $i$’s dataset size in the entire population. In this paper, we consider
the unbalanced data setting: $\alpha_{i}\neq\alpha_{j}$ if $i\neq j$. In (1),
$F_{i}(\mathbf{x},D_{i})\triangleq\frac{1}{|D_{i}|}\sum_{\xi^{i}_{j}\in
D_{i}}F(\mathbf{x},\xi^{i}_{j})$ is the local objective function, where
$\xi^{i}_{j}$ is the $j$-th sample in $D_{i}$. In FL,
$F_{i}(\mathbf{x},D_{i})$ is assumed to be non-convex in general.

In each communication round $t$, the server broadcasts the latest global model
parameter $\mathbf{x}_{t}$ to each client. Upon receiving $\mathbf{x}_{t}$,
client $i$ performs local computations with
$\mathbf{x}^{i}_{t,0}=\mathbf{x}_{t}$:

$\mathbf{x}^{i}_{t,k+1}=\mathbf{x}^{i}_{t,k}-\eta\nabla
F(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k}),\quad k=0,\ldots,\tau_{t}^{i}-1,$ (2)

where $\tau_{t}^{i}$ denotes the total number of local steps at client $i$ in
round $t$ and $\xi^{i}_{t,k}$ is a random data sample used by client $i$ in
step $k$ in round $t$. We note that one key feature of the OTA-FL model in
this paper is that we allow $\tau_{t}^{i}$ to be time-varying and device-
dependent. While this makes the OTA-FL model more practical and flexible, it
also introduces an extra dimension of challenges in algorithmic design and
convergence analysis.

After finishing the local iterations, each client returns the update of model
parameters back to server. Upon the reception of returned updates from all
clients, the server aggregates and updates the global model $\mathbf{x}_{t}$.
In OTA-FL, the aggregation process on the server side happens automatically
over-the-air thanks to the superposition property of the wireless medium. The
specific communication model will be described in Section III-B.

###  III-B Communication Model

We consider an OTA-FL system in which the server broadcasts to all clients in
a downlink channel and the clients transmit to the server through a common
uplink channel synchronously. We assume an error-free downlink when
broadcasting the global model. This is a reasonable assumption when the server
has access to more power and bandwidth resources compared to edge devices. As
a result, each client receives an error-free global model parameter
$\mathbf{x}_{t}$ for its local computation in the beginning of each round $t$,
i.e., $\mathbf{x}^{i}_{t,0}=\mathbf{x}_{t}$. For the uplink, we consider a
Gaussian MAC, where the output the channel in each communication round $t$ is:

$\mathbf{y}_{t}=\sum_{i\in[m]}h_{t}^{i}\mathbf{z}^{i}_{t}+\mathbf{w}_{t}.$ (3)

In (3), $\mathbf{z}^{i}_{t}\in\mathbb{R}^{d}$ is the input from client $i$,
$h_{t}^{i}$ is the channel gain of client $i$, and
$\mathbf{w}_{t}\sim\mathcal{N}(\mathbf{0},\sigma_{c}^{2}\mathbf{I}_{d})$ is an
additive Gaussian channel noise.

We also consider an instantaneous power constraint at each client in each
communication round:

$\|\mathbf{z}^{i}_{t}\|^{2}\leq P_{t}^{i},\quad\forall i\in[m],\forall t,$ (4)

where $P_{t}^{i}$ is the maximum transmission power limit for client $i$ in
communication round $t$.

##  IV Impacts of Channel Noise and System-Data Heterogeneity on OTA-FL

In Section IV-A, we first characterize the impact of the channel noise on OTA-
FL when directly applying the standard FedAvg framework with SGD local updates
without considering power control at each client. Then, in Section IV-B, we
provide a concrete example to further illustrate the impact of channel noise
coupled with heterogeneous numbers of local updates, i.e., system
heterogeneity, on OTA-FL performance.

###  IV-A Impact of Channel Noise on OTA-FL

To study the impact of channel noise, we first consider a general $L$-smooth
objective function (i.e., having $L$-Lipschitz continuous gradients) with a
single local step, i.e., $\tau_{t}^{i}=1,\forall i\in[m],t\in[T]$. We note
that we consider the original FedAvg where model parameters
$\\{\mathbf{x}_{t}^{i},i\in[m]\\}$ are aggregated over-the-air without any
further scaling. Consequently, the channel output could be simplified as
$\mathbf{x}_{t+1}=\mathbf{x}_{t}-\eta\nabla
F(\mathbf{x}_{t},\xi_{t})+\mathbf{w}_{t}$, where
$\xi_{t}\triangleq\\{\xi^{i}_{t},\forall i\in[m]\\}$ represents one collective
data batch composed of random samples $\\{\xi^{i}_{t},\forall i\\}$ from all
clients. Then, we have the following theorem to characterize the impact of the
channel noise on the OTA version of the FedAvg algorithm:

######  Theorem 1 (Lower Bound for Gaussian Channel).

Consider an OTA-FL system for training an $L$-smooth objective function
$F(\mathbf{x})$ with an optimal solution $\mathbf{x}^{*}$. Supposed that each
client uses local SGD updates that are subject to additive white Gaussian
noise (AWGN), i.e., $\mathbf{x}_{t+1}=\mathbf{x}_{t}-\eta\nabla
F(\mathbf{x}_{t},\xi_{t})+\mathbf{w}_{t}$, where $\eta<\frac{1}{L}$ and
$\mathbf{w}_{t}\sim\mathcal{N}(\mathbf{0},\sigma_{c}^{2}\mathbf{I}_{d})$.
Then, the sequence $\\{\mathbf{x}_{t}\\}$ satisfies the following recursive
relationship:

$\displaystyle\mathbb{E}\left[\|\mathbf{x}_{t+1}-\mathbf{x}^{*}\|^{2}\right]\geq\mathbb{E}\left[\left(1-\eta
L\right)^{2}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}\right]+\eta^{2}\sigma^{2}+\sigma_{c}^{2},$

which further implies the following lower bound for the training convergence:

$\displaystyle\lim_{t\rightarrow\infty}\mathbb{E}\left[\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}\right]\geq\frac{\eta^{2}\sigma^{2}+\sigma_{c}^{2}}{1-\left(1-\eta
L\right)^{2}},$ (5)

where the stochastic gradient noise is assumed to be Gaussian, i.e., $\nabla
F(\mathbf{x}_{t},\xi_{t})-\nabla
F(\mathbf{x}_{t})\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I}_{d})$.

###### Proof Sketch.

By assuming independent stochastic gradient noise and channel noise, we could
decouple these noise terms and thus producing an iteration relation of
$\|\mathbf{x}_{t}-\mathbf{x}_{*}\|$ by $L$-smoothness with proper learning
rate $\eta<\frac{1}{L}$. As the channel noise exists in every round, such
noise variance term $\sigma_{c}^{2}$ is non-vanishing even for infinitely many
rounds. Due to space limitation, we refer readers to Appendix VIII for the
complete proof. ∎

Theorem 1 suggests that there is a non-vanishing convergence error due to the
Gaussian MAC noise when only standard SGD updates are used locally at each
client. This motivates us to develop joint adaptive computation and power
control for OTA-FL to mitigate the MAC noise effect.

###  IV-B Impacts of System-Data Heterogeneity on OTA-FL

As discussed in above Section III-A, the FL optimization problem considered in
this paper contains non-convex objective function, heterogeneous (non-i.i.d.)
data, and different number of local updates $\tau_{t}^{i}$ at each client. As
shown in previous work [19], different number of local steps (or optimization
processes) among clients introduce objective inconsistency, rendering
potentially arbitrary deviation from optimal solutions in conventional FL.
Next, we show that similar negative impacts of data heterogeneity and
different number of local steps also affect the OTA-FL performance even under
proper power control. This insight further motivates the need for a joint
adaptive computation and power control.

Here, we use the GD method for each client’s local update and omit the channel
noise for now to clearly characterize the above factors in FL. That is, each
client $i\in[m]$ takes local steps as follows:

$\displaystyle\mathbf{x}^{i}_{t,k+1}=\mathbf{x}^{i}_{t,k}-\eta\nabla
F_{i}(\mathbf{x}^{i}_{t,k}),\quad\forall k\in[\tau_{i}].$ (6)

Then, a power control factor at client $i$ is applied as follows:
$\mathbf{z}^{i}_{t}=\beta_{i}\left(\mathbf{x}^{i}_{t,\tau_{i}}-\mathbf{x}^{i}_{t,0}\right)$.
The aggregation with power control factor $\beta$ on the server side can be
written as

$\displaystyle\mathbf{x}_{t+1}-\mathbf{x}_{t}$
$\displaystyle=\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left(\mathbf{x}^{i}_{t,\tau_{i}}-\mathbf{x}^{i}_{t,0}\right).$
(7)

We now consider the following OTA-FL example:

######  Example 1 (Deviation of Objective Value under Disjoint Power Control
and System-Data Heterogeneity).

Consider quadratic objective functions:

$\displaystyle F_{i}(\mathbf{x})$
$\displaystyle=\frac{1}{2}\mathbf{x}_{t}\mathbf{H}_{i}\mathbf{x}-\mathbf{e}_{i}^{T}\mathbf{x}+\frac{1}{2}\mathbf{e}_{i}^{T}\mathbf{H}_{i}^{-1}\mathbf{e}_{i},\forall
i\in[m],\text{ and }$ $\displaystyle F(\mathbf{x})$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}F_{i}(\mathbf{x})=\frac{1}{2}\mathbf{x}_{t}\bar{\mathbf{H}}\mathbf{x}-\bar{\mathbf{e}_{i}}^{T}\mathbf{x}+\frac{1}{2}\sum_{i=1}^{m}\alpha_{i}\mathbf{e}_{i}^{T}\mathbf{H}_{i}^{-1}\mathbf{e}_{i},$

where $\mathbf{H}_{i}\in\mathbb{R}^{d\times d}$ is invertible,
$\bar{\mathbf{H}}\triangleq\sum_{i=1}^{m}\alpha_{i}\mathbf{H}_{i}$,
$\mathbf{e}_{i}\in\mathbb{R}^{d}$ is an arbitrary vector, and
$\bar{\mathbf{e}}\triangleq\sum_{i=1}^{m}\alpha_{i}\mathbf{e}_{i}$. Let each
client take $\tau_{i}$ GD steps. Then, the generated sequence
$\\{\mathbf{x}_{t}\\}$ satisfies:

$\displaystyle\lim_{t\rightarrow\infty}\mathbf{x}_{t}$
$\displaystyle=\hat{\mathbf{x}},$ (8)

where the limit point $\hat{\mathbf{x}}$ can be computed as:

$\displaystyle\hat{\mathbf{x}}$
$\displaystyle=\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}\mathbf{H}_{i}\right]^{-1}\times$
(9)
$\displaystyle\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}\mathbf{e}_{i}\right].$

For the quadratic objective function $F(\mathbf{x})$, the closed-form solution
is $\mathbf{x}^{*}=\bar{\mathbf{H}}^{-1}\bar{\mathbf{e}}$. Comparing
$\mathbf{x}^{*}$ and $\hat{\mathbf{x}}$, we can see a deviation that depends
on problem hyper-parameter $\mathbf{H}$, learning rate $\eta$, local step
numbers $\tau_{i}$, factor $\beta_{i}$ and $\beta$.∎

Due to space limitation, we provide the proof details of this example in
Appendix VIII. It can be seen from this example that the complex coupling
between power control and system-data heterogeneity renders a highly non-
trivial OTA-FL power control and algorithmic design to guarantee convergence
to an optimal solution. This further motivates our OTA-FL algorithm design
with joint adaptive computation and power control in Section V.

##  V Algorithm Design

Algorithm 1 Adaptive Over-the-Air Federated Learning.

1:  _Init: global mode $\mathbf{x}_{0}$._

2: for $t=0,\dots,T-1$ do

3: Server broadcasts latest global model $\mathbf{x}_{t}$ to each device.

4: for each client $i\in[m]$ do

5: Each client locally and adaptively trains model via SGD (10) under power
constraints and transmits $\delta^{i}_{t}$ by transmission scaling as in (11).

6: end for

7: The server aggregates and updates global model by receiver rescaling (12).

8: end for

To address the negative impacts of channel noise and system-data heterogeneity
in Section IV, we propose an over-the-air federated learning algorithm with
joint adaptive computation and power control (ACPC-OTA-FL) as shown in
Algorithm 1. The basic idea of our ACPC-OTA-FL algorithm is to utilize a time-
varying dynamic number of local SGD steps at each client under the
instantaneous power constraint at this particular client. Specifically, given
a server-side power control scaling factor $\beta_{t}$, each client $i$
chooses to perform $\tau_{t}^{i}$ local SGD steps as follows:

$\displaystyle\mathbf{x}^{i}_{t,k+1}=\mathbf{x}^{i}_{t,k}-\eta\nabla
F(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k}),\quad k=1,\ldots,\tau_{t}^{i},$ (10)

under the time-varying and client-dependent power constraints $P_{t}^{i}$ such
that $\|\delta^{i}_{t}\|^{2}\leq P_{t}^{i}$, where
$\delta^{i}_{t}=\beta_{t}^{i}(\mathbf{x}^{i}_{t,\tau_{t}^{i}}-\mathbf{x}^{i}_{t,0})$
and

$\displaystyle\beta_{t}^{i}=\frac{\beta_{t}\alpha_{i}}{\tau^{i}_{t}}.$ (11)

Given power constraints $P$ and $\beta$, we can choose $\tau^{i}_{t}$ based on
trail-and-error or greedy approach whenever the power constraints are
satisfied. For simplicity, we ignore fading for now. The uplink channel output
is $\sum_{i=1}^{m}\delta^{i}_{t}+\mathbf{w}_{t}$. With power control rescaling
on the server side, the global model is aggregated and updated as:

$\displaystyle\mathbf{x}_{t+1}$
$\displaystyle=\mathbf{x}_{t}+\sum_{i=1}^{m}\frac{\delta^{i}_{t}}{\beta_{t}}+\tilde{\mathbf{w}}_{t}.$
(12)

As mentioned earlier, we assume a Gaussian channel noise
$\mathbf{w}_{t}\sim\mathcal{N}(\mathbf{0},\sigma_{c}^{2}\mathbf{I}_{d})$ and
thus
$\tilde{\mathbf{w}}_{t}\sim\mathcal{N}(\mathbf{0},\frac{\sigma_{c}^{2}}{\beta_{t}^{2}}\mathbf{I}_{d})$.
The novelty of our algorithm lies in utilizing a time-varying dynamic local
steps to fully exploit the computation and communication power resources.

There are two advantages in our algorithm compared to previous works. First,
we jointly consider the computation-communication co-design due to their
complex coupling relationship as shown in Section IV-B. As a result, more
powerful clients with more computation capacities and transmission power will
execute more local update steps and have a large fraction in the server-side
aggregation. This adaptive and client-dependent design is different from
previous works [16, 12, 11, 14, 15, 17, 18], which considered the
communication problem separately after finishing local update computation and
used an uniform power control scaling factor without considering the
heterogeneity among the clients. Second, our ACPC-OTA-FL algorithm alleviates
the straggler (i.e., slow client) problem by allowing different local step
numbers across clients in each communication round. Before providing the
theoretical convergence result, we first state our assumptions:

######  Assumption 1.

($L$-Lipschitz Continuous Gradient) There exists a constant $L>0$, such that
$\|\nabla F_{i}(\mathbf{x})-\nabla F_{i}(\mathbf{y})\|\leq
L\|\mathbf{x}-\mathbf{y}\|$, $\forall\mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$,
and $i\in[m]$.

######  Assumption 2.

(Unbiased Local Stochastic Gradients and Their Bounded Variance) Let $\xi_{i}$
be a random local data sample at client $i$. The local stochastic gradient is
unbiased and has a bounded variance, i.e., $\mathbb{E}[\nabla
F_{i}(\mathbf{x},\xi_{i})]=\nabla F_{i}(\mathbf{x})$, $\forall i\in[m]$, and
$\mathbb{E}[\|\nabla F_{i}(\mathbf{x},\xi_{i})-\nabla
F_{i}(\mathbf{x})\|^{2}]\leq\sigma^{2}$, where the expectation is taken over
the local data distribution $\mathcal{X}_{i}$.

######  Assumption 3.

(Bounded Stochastic Gradient) There exist a constant $G\geq 0$, such that the
norm of each local stochastic gradient is bounded: $\mathbb{E}[\|\nabla
F_{i}(\mathbf{x},\xi_{i})\|^{2}]\leq G^{2}$, $\forall i\in[m]$.

Assumptions 1–2 are common in the analysis of SGD-based algorithms. Assumption
3 is also widely used in OTA-FL with non-i.i.d. datasets (e.g., [12, 20, 18]).
With these three assumptions, we have the following convergence result:

######  Theorem 2 (Convergence Rate).

Let $\\{\mathbf{x}_{t}\\}$ be the global model generated by Algorithm 1. Under
Assumptions 1\- 3 and a constant learning rate $\eta_{t}=\eta,\forall
t\in[T]$, it holds that:

$\min_{t\in[T]}\mathbb{E}\|\nabla
F(\mathbf{x}_{t})\|^{2}\leq\underbrace{\frac{2\left(F(\mathbf{x}_{0})-F(\mathbf{x}_{*})\right)}{T\eta}}_{\mathrm{optimization\,error}}+\underbrace{L\eta\sigma^{2}\sum_{i=1}^{m}\alpha_{i}^{2}}_{\mathrm{statistical\,error}}\\\
+\underbrace{mL^{2}\eta^{2}G^{2}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau_{i}\right)^{2}}_{\mathrm{local\,update\,error}}+\underbrace{\frac{L\sigma_{c}^{2}}{\eta\beta^{2}}}_{\begin{subarray}{c}\mathrm{channel\,noise}\\\
\mathrm{error}\end{subarray}},$ (13)

where
$\left(\tau_{i}\right)^{2}=\frac{\sum_{t=0}^{T-1}\left(\tau^{i}_{t}\right)^{2}}{T}$
and
$\frac{1}{\bar{\beta}^{2}}=\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{\beta_{t}^{2}}$.

###### Proof Sketch.

In each round, the average global model update is the same as noise-free
FedAvg since the channel noise is independent Gaussian with zero mean. Thus,
we can decouple the channel noise term as an extra error scaled by
$\frac{\sigma_{c}^{2}}{\beta_{t}^{2}}$ when calculating the function descent
($F(\mathbf{x}_{t+1})-F(\mathbf{x}_{t})$) in each round by the $L$-smoothness.
Then, the technical challenge lies in heterogeneous local steps across
clients. By simulating mini-batch SGD method, we could further bound the
difference
$\frac{1}{2}\eta_{t}\mathbb{E}_{t}[\|\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}(\nabla
F_{i}(\mathbf{x}_{t})-\nabla
F_{i}(\mathbf{x}^{i}_{t,k}))\|^{2}]\leq\frac{1}{2}\eta_{t}^{3}mL^{2}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau^{i}_{t}\right)^{2}G^{2}$,
which accounts for the size of dataset, data heterogeneity and different local
steps. The above two terms correspond to channel noise error and local update
error, respectively. Following the classic analysis for SGD-based methods, the
optimization error and statistical error could be similarly derived, and the
final convergence result naturally follows. Due to space limitation, we
relegate the full proof to Appendix VIII. ∎

Theorem 2 characterizes four sources of errors that affect the convergence
rate: 1) the optimization error dependent on the distance between the initial
guess and optimal objective value; 2) the statistical error due to the use of
stochastic gradients rather than full gradients; 3) local update error from
local update steps coupled with data heterogeneity; and 4) channel noise error
from over-the-air transmissions. Among these four errors, only the
optimization error (first term) vanishes as the total number of iterations $T$
gets large, while other three terms are independent of $T$.

Similar to classic SGD or FedAvg convergence analysis, diminishing learning
rates $\mathcal{O}(\frac{1}{\sqrt{T}})$ can be used to remove the statistical
and local update errors and obtain a convergence error bound
$\min_{t\in[T]}\mathbb{E}\|\nabla
F(\mathbf{x}_{t})\|^{2}=\mathcal{O}(\frac{1}{\sqrt{T}})$. To mitigate the
channel noise error, the parameter $\beta$ needs to be chosen judiciously.
Given $\delta_{t}^{i}$ in communication round $t$, we can set
$\beta_{t}^{2}=\min_{i\in[m]}\\{\frac{P_{t}^{i}(\tau_{t}^{i})^{2}}{\|\delta_{t}^{i}\|^{2}\alpha_{i}^{2}}\\}$.
If the $\delta_{t}^{i}$-information is unavailable, we can choose
$\|\delta_{t}^{i}\|^{2}\leq\eta_{t}^{2}(\tau_{t}^{i})^{2}G^{2}$ by its upper
bound, and thus $\beta_{t}^{2}=\frac{P_{t}}{\alpha_{i}^{2}\eta_{t}^{2}G^{2}}$,
where $P_{t}=\min_{i\in[m]}P_{t}^{i}$. For the special case with
$P=P_{t}^{i},\forall i,t$, $\alpha_{i}=\frac{1}{m}$ (balanced datasets), and
identical local steps $\tau_{t}^{i}=\tau,\forall i,t$, the channel noise error
(the fourth term) becomes $\frac{\eta\sigma_{c}^{2}G^{2}}{Pm^{2}}$, and the
following result immediately follows from Theorem 2:

######  Corollary 1 (Convergence Rate).

Let
$\alpha_{i}=\frac{1}{m},\tau_{i}=\tau,\eta=\frac{\sqrt{m}}{\sqrt{T}},\beta^{2}=\frac{m}{\eta^{2}}$,
the convergence rate of ACPC-OTA-FL under the special case above is
$\mathcal{O}(\frac{\sigma^{2}+1}{\sqrt{mT}})+\mathcal{O}(\frac{m\tau^{2}G^{2}}{T})+\mathcal{O}(\frac{\sigma_{c}^{2}}{\sqrt{mT}})$.

Corollary 1 implies that, if $\tau\leq\frac{T^{1/4}}{m^{3/4}}$, a linear
speedup in terms of the number of clients (i.e.,
$\mathcal{O}(\frac{1}{\sqrt{mT}})$) can be achieved, which shows the benefits
of parallelism and matches the convergence rate of FedAvg in noise-free
communication environment [21, 22].

Lastly, we note that it is straightforward to extend our results to fading
channels with known CSI. Specifically, the adaptive computation and power
control strategy for fading channels is to choose local steps $\tau^{i}_{t}$
such that $\|\delta^{i}_{t}\|^{2}\leq P_{t}^{i}$, where
$\delta^{i}_{t}=\beta_{t}^{i}\left(\mathbf{x}^{i}_{t,\tau_{i}}-\mathbf{x}^{i}_{t,0}\right),\beta_{t}^{i}=\frac{\beta_{t}\alpha_{i}}{\tau^{i}_{t}h_{t}^{i}}$,
and $P_{t}^{i}>0$ represents the maximum transmission power for client $i$ in
round $t$. Under this joint computation and power control, the received signal
remains the same as that in the non-fading OTA-FL setting. Thus, the same
convergence results in Theorem 2 and Corollary 1 continue to hold.

##  VI Numerical Results

In this section, we conduct numerical experiments to verify our theoretical
results using logistic regression on the MNIST dataset [23]. Following the
same procedure as in existing works [20, 1, 22], we distribute the data evenly
to $m=10$ clients in a label-based partition to impose data heterogeneity
across the clients, where the heterogeneity level can be characterized by a
parameter $p$. As the MNIST dataset contains $10$ classes of labels in total,
$p=10$ represents the i.i.d. case. The smaller the $p$-value, the more
heterogeneous the data across clients. We simulate Gaussian MAC with signal-
to-noise ratios (SNRs) of $-1$ dB, 10 dB and 20 dB.

TABLE I: Logistic regression test Accuracy (%) for ACPC-OTA-FL compared with COTAF and FedAvg on the MNIST dataset. Non-IID Level | Algorithm | Signal-to-Noise Ratio
---|---|---
-1 dB | 10 dB | 20 dB
$p=1$ | ACPC-OTA-FL | 78.22 | 89.08 | 89.54
COTAF | 46.55 | 65.54 | 85.92
FedAvg | 67.49 | 68.08 | 67.65
$p=2$ | ACPC-OTA-FL | 81.89 | 89.58 | 90.43
COTAF | 63.59 | 78.80 | 86.57
FedAvg | 71.55 | 78.03 | 79.86
$p=5$ | ACPC-OTA-FL | 86.48 | 90.64 | 91.20
COTAF | 79.64 | 86.52 | 90.82
FedAvg | 74.76 | 82.84 | 85.40
$p=10$ | ACPC-OTA-FL | 86.21 | 90.75 | 91.08
COTAF | 86.43 | 91.08 | 92.63
FedAvg | 76.26 | 84.94 | 88.11

We illustrate the test accuracy of ACPC-OTA-FL compared with COTAF [18] and
FedAvg [1] in Table I. Two key observations are in order: 1) Test accuracy
drops significantly by directly applying FedAvg algorithm to wireless OTA-FL
(up to $20\%$ accuracy drop) under large channel noise, which validates our
Theorem 1 and is consistent with existing works[9, 10, 11]; and 2) Under power
control, both ACPC-OTA-FL and COTAF could alleviate the channel noise impacts
in the i.i.d. data setting ($p=10$). But in the highly heterogeneous data
($p=1,2$) and/or low SNR settings, our ACPC-OTA-FL algorithm outperforms COTAF
by a large margin. For example, when $\text{SNR}=-1\,\mathrm{dB}$ and $p=1$,
ACPC-OTA-FL improves the test accuracy by 31.76% and 10.73% compared to COTAF
and FedAvg, respectively. The intuition is that the gradient returned from the
clients vary dramatically in highly heterogeneous data settings, and thus
utilizing an adaptive local steps under limited power constraints allows each
client to fully exploit both computation and communication resources.

##  VII Conclusion

In this paper, we considered the joint adaptive local computation (number of
local steps) and power control for OTA-FL. We first characterized the training
error due to channel noise for conventional OTA-FL by establishing a
fundamental lower bound for general objective functions with Lipschitz-
continuous gradients. This motivated us to propose an over-the-air federated
learning algorithm with joint adaptive computation and power control (ACPC-
OTA-FL) to mitigate the impacts of channel noise on the learning performance,
while taking the device heterogeneity into consideration. We analyzed the
convergence of ACPC-OTA-FL with non-convex objective functions and
heterogeneous data, and shown that the convergence rate of ACPC-OTA-FL matches
that of FedAvg with noise-free communications.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [2] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [3] H. B. McMahan _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1, 2021.
  * [4] S. Niknam, H. S. Dhillon, and J. H. Reed, “Federated learning for wireless communications: Motivation, opportunities, and challenges,” _IEEE Communications Magazine_ , vol. 58, no. 6, pp. 46–51, 2020.
  * [5] O. Abari, H. Rahul, and D. Katabi, “Over-the-air function computation in sensor networks,” _arXiv preprint arXiv:1612.02307_ , 2016.
  * [6] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via over-the-air computation,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 3, pp. 2022–2035, 2020.
  * [7] G. Zhu, J. Xu, K. Huang, and S. Cui, “Over-the-air computing for wireless data aggregation in massive iot,” _IEEE Wireless Communications_ , vol. 28, no. 4, pp. 57–65, 2021.
  * [8] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning based on over-the-air computation,” in _ICC 2019-2019 IEEE international conference on communications (ICC)_. IEEE, 2019, pp. 1–6.
  * [9] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 1, pp. 491–506, 2019.
  * [10] T. Sery and K. Cohen, “On analog gradient descent learning over multiple access fading channels,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 2897–2911, 2020.
  * [11] M. M. Amiri and D. Gündüz, “Federated learning over wireless fading channels,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 5, pp. 3546–3557, 2020.
  * [12] ——, “Machine learning at the wireless edge: Distributed stochastic gradient descent over-the-air,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 2155–2169, 2020.
  * [13] ——, “Over-the-air machine learning at the wireless edge,” in _2019 IEEE 20th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2019, pp. 1–5.
  * [14] G. Zhu, Y. Du, D. Gündüz, and K. Huang, “One-bit over-the-air aggregation for communication-efficient federated edge learning: Design and convergence analysis,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 3, pp. 2120–2135, 2020.
  * [15] H. Guo, A. Liu, and V. K. Lau, “Analog gradient aggregation for federated learning over wireless networks: Customized design and convergence analysis,” _IEEE Internet of Things Journal_ , vol. 8, no. 1, pp. 197–210, 2020.
  * [16] L. Chen, X. Qin, and G. Wei, “A uniform-forcing transceiver design for over-the-air function computation,” _IEEE Wireless Communications Letters_ , vol. 7, no. 6, pp. 942–945, 2018.
  * [17] N. Zhang and M. Tao, “Gradient statistics aware power control for over-the-air federated learning in fading channels,” in _2020 IEEE International Conference on Communications Workshops (ICC Workshops)_. IEEE, 2020, pp. 1–6.
  * [18] T. Sery, N. Shlezinger, K. Cohen, and Y. C. Eldar, “Over-the-air federated learning from heterogeneous data,” _IEEE Transactions on Signal Processing_ , 2021.
  * [19] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the objective inconsistency problem in heterogeneous federated optimization,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * [20] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” in _International Conference on Learning Representations_ , 2020. [Online]. Available: https://openreview.net/forum?id=HJxNAnVtDS
  * [21] H. Yu, S. Yang, and S. Zhu, “Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, no. 01, 2019, pp. 5693–5700.
  * [22] H. Yang, M. Fang, and J. Liu, “Achieving linear speedup with partial worker participation in non-IID federated learning,” in _International Conference on Learning Representations_ , 2021. [Online]. Available: https://openreview.net/forum?id=jDdzh5ul-d
  * [23] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.

##  VIII Proof

See 1

###### Proof.

$\displaystyle\mathbb{E}\left[\|\mathbf{x}_{t+1}-\mathbf{x}^{*}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\mathbf{x}_{t}-\eta\nabla
F(\mathbf{x}_{t},\xi_{t})+\mathbf{w}_{t}-\mathbf{x}^{*}\|^{2}\right]$ (14)
$\displaystyle=\mathbb{E}\left[\|\mathbf{x}_{t}-\mathbf{x}^{*}-\eta\nabla
F(\mathbf{x}_{t})\|^{2}\right]+\mathbb{E}\left[\|\eta\nabla
F(\mathbf{x}_{t},\xi_{t})-\eta\nabla
F(\mathbf{x}_{t})\|^{2}\right]+\mathbb{E}\left[\|\mathbf{w}_{t}\|^{2}\right]$
(15)
$\displaystyle=\mathbb{E}\left[\|\mathbf{x}_{t}-\mathbf{x}^{*}-\eta\left(\nabla
F(\mathbf{x}_{t})-\nabla
F(\mathbf{x}^{*})\right)\|^{2}\right]+\eta^{2}\sigma^{2}+\sigma_{c}^{2}$ (16)
$\displaystyle\geq\mathbb{E}\left[\left(\|\mathbf{x}_{t}-\mathbf{x}^{*}\|-\eta\|\nabla
F(\mathbf{x}_{t})-\nabla
F(\mathbf{x}^{*})\|\right)^{2}\right]+\eta^{2}\sigma^{2}+\sigma_{c}^{2}$ (17)
$\displaystyle\geq\mathbb{E}\left[\left(1-\eta
L\right)^{2}\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}\right]+\eta^{2}\sigma^{2}+\sigma_{c}^{2}$
(18)

∎

Example 1 Consider quadratic objective functions:

$\displaystyle F_{i}(\mathbf{x})$
$\displaystyle=\frac{1}{2}\mathbf{x}_{t}\mathbf{H}_{i}\mathbf{x}-\mathbf{e}_{i}^{T}\mathbf{x}+\frac{1}{2}\mathbf{e}_{i}^{T}\mathbf{H}_{i}^{-1}\mathbf{e}_{i},\forall
i\in[m],\text{ and }$ $\displaystyle F(\mathbf{x})$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}F_{i}(\mathbf{x})=\frac{1}{2}\mathbf{x}_{t}\bar{\mathbf{H}}\mathbf{x}-\bar{\mathbf{e}_{i}}^{T}\mathbf{x}+\frac{1}{2}\sum_{i=1}^{m}\alpha_{i}\mathbf{e}_{i}^{T}\mathbf{H}_{i}^{-1}\mathbf{e}_{i},$

where $\mathbf{H}_{i}\in\mathbb{R}^{d\times d}$ is invertible,
$\bar{\mathbf{H}}\triangleq\sum_{i=1}^{m}\alpha_{i}\mathbf{H}_{i}$,
$\mathbf{e}_{i}\in\mathbb{R}^{d}$ is an arbitrary vector, and
$\bar{\mathbf{e}}\triangleq\sum_{i=1}^{m}\alpha_{i}\mathbf{e}_{i}$. Let each
client take $\tau_{i}$ GD steps. Then, the generated sequence
$\\{\mathbf{x}_{t}\\}$ satisfies:

$\displaystyle\lim_{t\rightarrow\infty}\mathbf{x}_{t}$
$\displaystyle=\hat{\mathbf{x}},$ (19)

where the limit point $\hat{\mathbf{x}}$ can be computed as:

$\displaystyle\hat{\mathbf{x}}$
$\displaystyle=\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}\mathbf{H}_{i}\right]^{-1}\times$
(20)
$\displaystyle\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}\mathbf{e}_{i}\right].$

For the quadratic objective function $F(\mathbf{x})$, the closed-form solution
is $\mathbf{x}^{*}=\bar{\mathbf{H}}^{-1}\bar{\mathbf{e}}$. Comparing
$\mathbf{x}^{*}$ and $\hat{\mathbf{x}}$, we can see a deviation that depends
on problem hyper-parameter $\mathbf{H}$, learning rate $\eta$, local step
numbers $\tau_{i}$, factor $\beta_{i}$ and $\beta$.∎

###### Proof.

Consider quadratic objective functions:

$\displaystyle F_{i}(\mathbf{x})$
$\displaystyle=\frac{1}{2}\mathbf{x}_{t}\mathbf{H}_{i}\mathbf{x}-\mathbf{e}_{i}^{T}\mathbf{x}+\frac{1}{2}\mathbf{e}_{i}^{T}\mathbf{H}_{i}^{-1}\mathbf{e}_{i},$
(21) $\displaystyle F(\mathbf{x})$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}F_{i}(\mathbf{x})=\frac{1}{2}\mathbf{x}_{t}\bar{\mathbf{H}}\mathbf{x}-\bar{\mathbf{e}_{i}}^{T}\mathbf{x}+\frac{1}{2}\sum_{i=1}^{m}\alpha_{i}\mathbf{e}_{i}^{t}\mathbf{H}_{i}^{-1}\mathbf{e}_{i},$
(22)

where $\mathbf{H}_{i}\in\mathbb{R}^{d\times d}$ is invertible matrix,
$\bar{\mathbf{H}}=\sum_{i=1}^{m}\alpha_{i}\mathbf{H}_{i}$,
$\mathbf{e}_{i}\in\mathbb{R}^{d}$ is arbitrary vector, and
$\bar{\mathbf{e}}=\sum_{i=1}^{m}\alpha_{i}\mathbf{e}_{i}$. It is easy to show
the optimum for each local and global objective function are
$\mathbf{x}_{i}^{*}=\mathbf{H}_{i}^{-1}\mathbf{e}_{i},\forall i\in[m]$ and
$\mathbf{x}^{*}=\bar{\mathbf{H}}^{-1}\bar{\mathbf{e}}$.

The local update for each client $i\in[m]$ is as follows:

$\displaystyle\mathbf{x}^{i}_{t,k+1}$
$\displaystyle=\mathbf{x}^{i}_{t,k}-\eta\left[\mathbf{H}_{i}\mathbf{x}^{i}_{t,k}-\mathbf{e}_{i}\right]$
(23)
$\displaystyle=\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)\mathbf{x}^{i}_{t,k}+\eta\mathbf{e}_{i}$
(24)

Then we have the recursive equation for one local step by rearranging 24:

$\displaystyle\mathbf{x}^{i}_{t,k+1}-\mathbf{c}^{i}_{t}$
$\displaystyle=\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)\left(\mathbf{x}^{i}_{t,k}-\mathbf{c}^{i}_{t}\right),$
(25)

where $\mathbf{c}^{i}_{t}=\mathbf{H}_{i}^{-1}\mathbf{e}_{i}$.

$\displaystyle\mathbf{x}^{i}_{t,\tau_{i}}-\mathbf{c}^{i}_{t}$
$\displaystyle=\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\left(\mathbf{x}^{i}_{t,0}-\mathbf{c}^{i}_{t}\right),$
(26) $\displaystyle\mathbf{x}^{i}_{t,\tau_{i}}-\mathbf{x}^{i}_{t,0}$
$\displaystyle=\left[\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}-\mathbf{I}\right]\mathbf{H}_{i}^{-1}\left(\mathbf{e}_{i}-\mathbf{H}_{i}\mathbf{x}^{i}_{t,0}\right)$
(27)
$\displaystyle=\mathbf{K}_{i}(\eta)\left(\mathbf{e}_{i}-\mathbf{H}_{i}\mathbf{x}^{i}_{t,0}\right),$
(28)

where we define
$\mathbf{K}_{i}(\eta)=\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}$.

Aggregation:

$\displaystyle\mathbf{x}_{t+1}-\mathbf{x}_{t}$
$\displaystyle=\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left(\mathbf{x}^{i}_{t,\tau_{i}}-\mathbf{x}^{i}_{t,0}\right)$
(29)
$\displaystyle=\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\left(\mathbf{e}_{i}-\mathbf{H}_{i}\mathbf{x}^{i}_{t,0}\right),$
(30) $\displaystyle\mathbf{x}_{t+1}$
$\displaystyle=\left[\mathbf{I}-\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\mathbf{H}_{i}\right]\mathbf{x}_{t}+\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\mathbf{e}_{i},$
(31) $\displaystyle\mathbf{x}_{t+1}-\hat{\mathbf{x}}$
$\displaystyle=\left[\mathbf{I}-\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\mathbf{H}_{i}\right]\left(\mathbf{x}_{t}-\hat{\mathbf{x}}\right),$
(32) $\displaystyle\mathbf{x}_{t}$
$\displaystyle=\left[\mathbf{I}-\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\mathbf{H}_{i}\right]^{t}\left(\mathbf{x}_{0}-\hat{\mathbf{x}}\right)+\hat{\mathbf{x}},$
(33)

where
$\hat{\mathbf{x}}:=\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\mathbf{H}_{i}\right]^{-1}\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\mathbf{K}_{i}(\eta)\mathbf{e}_{i}\right]=\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}\mathbf{H}_{i}\right]^{-1}\left[\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left[\mathbf{I}-\left(\mathbf{I}-\eta\mathbf{H}_{i}\right)^{\tau_{i}}\right]\mathbf{H}_{i}^{-1}\mathbf{e}_{i}\right]$.

As $t$ goes to sufficiently large, we have

$\lim_{t\rightarrow\infty}\mathbf{x}_{t}=\hat{\mathbf{x}}.$

∎

Theorem 2 (Convergence Rate). Let $\\{\mathbf{x}_{t}\\}$ be the global model
generated by Algorithm 1. Under Assumptions 1\- 3 and a constant learning rate
$\eta_{t}=\eta,\forall t\in[T]$, it holds that:

$\min_{t\in[T]}\mathbb{E}\|\nabla
F(\mathbf{x}_{t})\|^{2}\leq\underbrace{\frac{2\left(F(\mathbf{x}_{0})-F(\mathbf{x}_{*})\right)}{T\eta}}_{\mathrm{optimization\,error}}+\underbrace{L\eta\sigma^{2}\sum_{i=1}^{m}\alpha_{i}^{2}}_{\mathrm{statistical\,error}}+\underbrace{mL^{2}\eta^{2}G^{2}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau_{i}\right)^{2}}_{\mathrm{local\,update\,error}}+\underbrace{\frac{L\sigma_{c}^{2}}{\eta\beta^{2}}}_{\begin{subarray}{c}\mathrm{channel\,noise}\\\
\mathrm{error}\end{subarray}},$ (34)

where
$\left(\tau_{i}\right)^{2}=\frac{\sum_{t=0}^{T-1}\left(\tau^{i}_{t}\right)^{2}}{T}$
and
$\frac{1}{\bar{\beta}^{2}}=\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{\beta_{t}^{2}}$.

###### Proof.

$\displaystyle\mathbf{x}_{t+1}-\mathbf{x}_{t}$
$\displaystyle=\sum_{i=1}^{m}\frac{\beta_{i}}{\beta}\left(\mathbf{x}^{i}_{t,\tau^{i}_{t}}-\mathbf{x}^{i}_{t,0}\right)+\tilde{\mathbf{w}}_{t}$
(35)
$\displaystyle=\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\left(\mathbf{x}^{i}_{t,\tau^{i}_{t}}-\mathbf{x}^{i}_{t,0}\right)+\tilde{\mathbf{w}}_{t}$
(36)
$\displaystyle=\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\eta_{t}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})\right)+\tilde{\mathbf{w}}_{t}$ (37)

Due to L-smoothness, we have one step descent in expectation conditioned on
$\mathbf{x}_{t}$,

$\displaystyle\mathbb{E}_{t}[F(\mathbf{x}_{t+1})]-F(\mathbf{x}_{t})\leq\left<\nabla
F(\mathbf{x}_{t}),\mathbb{E}_{t}\left[\mathbf{x}_{t+1}-\mathbf{x}_{t}\right]\right>+\frac{L}{2}\mathbb{E}_{t}\left[\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\|^{2}\right]$
(38) $\displaystyle=\left<\nabla
F(\mathbf{x}_{t}),\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\eta_{t}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\right>+\frac{L}{2}\mathbb{E}_{t}\left[\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}\eta_{t}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})\right)+\tilde{\mathbf{w}}_{t}\bigg{\|}^{2}\right]$
(39) $\displaystyle=-\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}+\eta_{t}\left<\nabla F(\mathbf{x}_{t}),\nabla
F(\mathbf{x}_{t})-\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\right>$ (40)
$\displaystyle+\frac{L}{2}\mathbb{E}_{t}\left[\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}\eta_{t}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})\right)+\tilde{\mathbf{w}}_{t}\bigg{\|}^{2}\right]$
(41) $\displaystyle=-\frac{1}{2}\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}-\frac{1}{2}\eta_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}+\frac{1}{2}\eta_{t}\mathbb{E}_{t}\bigg{\|}\nabla
F(\mathbf{x}_{t})-\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}$ (42)
$\displaystyle+\frac{L}{2}\mathbb{E}_{t}\left[\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}\eta_{t}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})\right)+\tilde{\mathbf{w}}_{t}\bigg{\|}^{2}\right]$
(43) $\displaystyle=-\frac{1}{2}\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}-\frac{1}{2}\eta_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}+\frac{1}{2}\eta_{t}\mathbb{E}_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}$
(44)
$\displaystyle+\frac{L\eta_{t}^{2}}{2}\mathbb{E}_{t}\left[\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})\right)\bigg{\|}^{2}\right]+\frac{L\sigma_{c}^{2}}{2\beta_{t}^{2}}$
(45) $\displaystyle\leq-\frac{1}{2}\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}+\frac{1}{2}\eta_{t}\mathbb{E}_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}$
(46)
$\displaystyle+\frac{L\eta_{t}^{2}}{2}\mathbb{E}_{t}\left[\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})\right)-\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}\right]+\frac{L\sigma_{c}^{2}}{2\beta_{t}^{2}}$
(47) $\displaystyle\leq-\frac{1}{2}\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}+\frac{1}{2}\eta_{t}\mathbb{E}_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}$
(48)
$\displaystyle+\frac{L\eta_{t}^{2}}{2}\sum_{i=1}^{m}\mathbb{E}_{t}\left[\bigg{\|}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}^{i}_{t,k},\xi^{i}_{t,k})-\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}\right]+\frac{L\sigma_{c}^{2}}{2\beta_{t}^{2}}$
(49) $\displaystyle\leq-\frac{1}{2}\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}+\frac{1}{2}\eta_{t}\mathbb{E}_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}+\frac{L\eta_{t}^{2}}{2}\sum_{i=1}^{m}\alpha_{i}^{2}\sigma^{2}+\frac{L\sigma_{c}^{2}}{2\beta_{t}^{2}}$
(50)

The first inequality holds if $\eta_{t}\leq\frac{1}{L}$.

$\displaystyle\frac{1}{2}\eta_{t}\mathbb{E}_{t}\bigg{\|}\sum_{i=1}^{m}\frac{\alpha_{i}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla
F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}\leq\frac{1}{2}\eta_{t}m\sum_{i=1}^{m}\frac{(\alpha_{i})^{2}}{(\tau^{i}_{t})^{2}}\mathbb{E}_{t}\bigg{\|}\sum_{k=0}^{\tau^{i}_{t}-1}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}$
(51)
$\displaystyle\leq\frac{1}{2}\eta_{t}m\sum_{i=1}^{m}\frac{(\alpha_{i})^{2}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\mathbb{E}_{t}\bigg{\|}\left(\nabla
F_{i}(\mathbf{x}_{t})-\nabla F_{i}(\mathbf{x}^{i}_{t,k})\right)\bigg{\|}^{2}$
(52)
$\displaystyle\leq\frac{1}{2}\eta_{t}mL^{2}\sum_{i=1}^{m}\frac{(\alpha_{i})^{2}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\mathbb{E}_{t}\bigg{\|}\left(\mathbf{x}_{t}-\mathbf{x}^{i}_{t,k}\right)\bigg{\|}^{2}$
(53)
$\displaystyle\leq\frac{1}{2}\eta_{t}^{3}mL^{2}\sum_{i=1}^{m}\frac{(\alpha_{i})^{2}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}\mathbb{E}_{t}\bigg{\|}\sum_{j=0}^{k}\nabla
F_{i}(\mathbf{x}^{i}_{t,j},\xi^{i}_{t,j})\bigg{\|}^{2}$ (54)
$\displaystyle\leq\frac{1}{2}\eta_{t}^{3}mL^{2}\sum_{i=1}^{m}\frac{(\alpha_{i})^{2}}{\tau^{i}_{t}}\sum_{k=0}^{\tau^{i}_{t}-1}k^{2}G^{2}$
(55)
$\displaystyle\leq\frac{1}{2}\eta_{t}^{3}mL^{2}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau^{i}_{t}\right)^{2}G^{2}$
(56)

Plugging inequality (56) into (50), we have

$\displaystyle\mathbb{E}_{t}[F(\mathbf{x}_{t+1})]-F(\mathbf{x}_{t})\leq\left<\nabla
F(\mathbf{x}_{t}),\mathbb{E}_{t}\left[\mathbf{x}_{t+1}-\mathbf{x}_{t}\right]\right>+\frac{L}{2}\mathbb{E}_{t}\left[\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\|^{2}\right]$
(57) $\displaystyle\leq-\frac{1}{2}\eta_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}+\frac{1}{2}\eta_{t}^{3}mL^{2}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau^{i}_{t}\right)^{2}G^{2}+\frac{L\eta_{t}^{2}}{2}\sum_{i=1}^{m}\alpha_{i}^{2}\sigma^{2}+\frac{L\sigma_{c}^{2}}{2\beta_{t}^{2}}$
(58)

Rearranging and telescoping:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\eta_{t}\mathbb{E}_{t}\|\nabla
F(\mathbf{x}_{t})\|^{2}$
$\displaystyle\leq\frac{2\left(F(\mathbf{x}_{0})-F(\mathbf{x}_{T})\right)}{T}+mL^{2}\frac{1}{T}\sum_{t=0}^{T-1}\eta_{t}^{3}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau^{i}_{t}\right)^{2}G^{2}+L\sigma^{2}\sum_{i=1}^{m}\alpha_{i}^{2}\frac{1}{T}\sum_{t=0}^{T-1}\eta_{t}^{2}+L\sigma_{c}^{2}\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{\beta_{t}^{2}}$
(59)

Let $\eta_{t}=\eta$ be constant learning rate,
$\left(\tau_{i}\right)^{2}=\frac{\sum_{t=0}^{T-1}\left(\tau^{i}_{t}\right)^{2}}{T}$
then we have:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla
F(\mathbf{x}_{t})\|^{2}$
$\displaystyle\leq\frac{2\left(F(\mathbf{x}_{0})-F(\mathbf{x}_{T})\right)}{T\eta}+mL^{2}\eta^{2}G^{2}\sum_{i=1}^{m}(\alpha_{i})^{2}\left(\tau_{i}\right)^{2}+L\eta\sigma^{2}\sum_{i=1}^{m}\alpha_{i}^{2}+\frac{L\sigma_{c}^{2}}{\eta\beta^{2}},$
(60)

where
$\frac{1}{\bar{\beta}^{2}}=\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{\beta_{t}^{2}}$.
∎


The problem of communicating sensor measurements over shared networks is  prevalent in many modern large-scale distributed systems such as cyber-physical systems, wireless sensor networks and the internet of things. Due to bandwidth constraints, the system designer must jointly design decentralized medium access transmission and estimation policies that accommodate a very large number of devices in extremely contested environments such that the collection of all observations is reproduced at the destination with the best possible fidelity. We formulate a remote estimation problem in the mean-field regime where a very large number of sensors communicate their observations to an access point, or base-station, under a strict constraint on the maximum fraction of transmitting devices. We show that in the mean-field regime, this problem exhibits a structure which enables tractable optimization algorithms. More importantly, we obtain a data-driven learning scheme that admits a finite sample-complexity guarantee on the performance of the resulting estimation system under minimal assumptions on the data's probability density function.

Networks, medium access control, stochastic optimization, convex-concave procedure, statistical learning

§ INTRODUCTION

State estimation is a fundamental building block of control systems subject to uncertain disturbances. Most modern applications rely on smart sensors that collect and transmit data to a remote location. In particular, for cyber-physical systems, where a large number of sensors collect and transmit data over a bandwidth limited network, there is a need to communicate efficiently and maintain the quality of the estimates as close as possible to optimal. Moreover, these conflicting goals must be achieved under the lack of knowledge of the underlying stochastic model of the environment. This task requires a combination of techniques in machine learning, decision-theory, and optimization.

Consider a distributed remote estimation system, where a very large number of sensors collect data and communicate with a destination over a constrained network.

To obtain a tractable problem, we assume that the data is independent and identically distributed across sensors. When the number of sensors in the system tends to infinity, this assumption leads to an optimization problem for which the optimal communication policy is determined by designing a quantizer under a rate constraint, a problem known to be non-convex. We show how to obtain a locally optimal solution using an algorithm known as the Convex-Concave procedure, which is guaranteed to converge regardless of the underlying probability density function of the data.

During the last decade, there has been significant research activity in systems with an asymptotically large number of coupled decision-making agents [Mahajan et al., 2013, Gagrani et al., 2020, Sanjari and Yüksel, 2021]. Such problem formulations are very relevant in modern applications such as industrial internet of things, where many tiny, low-power devices sense the environment and communicate with a remote gateway, base-station or access point [Gatsis, 2021]. Another application where the mean-field regime is appropriate for analysis is in robotic swarms [Zheng et al., 2021].
State estimation for control of power systems in the mean-field regime has been considered in the literature <cit.>. The main idea behind studying teams with an infinite number of identical/symmetric agents is to allow the system designer to perform the optimization over a single policy instead of accounting for the overwhelming combinatorial-like complexity that arise from the interactions among finitely many discrete agents.

The problem of remote estimation over a collision channel was introduced in [Vasconcelos and Martins, 2017] for a finite number of sensors communicating over a channel with unit capacity. Recently, [Zhang et al., 2021] extended the setup for a channel with arbitrary capacity, and introduced the first instance of such remote estimation problems when the distribution is unknown. Finally, [Vasconcelos and Mitra, 2021] considered using a nonparametric statistics technique known as Kernel Density Estimation (KDE) [Wasserman, 2006], to obtain a scheme that is more stable and and sample-efficient than the one obatained via empirical-risk minimization, also known as sample average approximation in the stochastic programming literature [Shapiro et al., 2021]. We use the fact that our algorithm is independent of the data's pdf to come up with a data-driven scheme where the system designer relies only on a finite collection of data points using KDE. KDE enables a data-based algorithm and with the choice of a Gaussian kernel, which leads to an algorithm is free of integrals, implying in great numeric stability [Asi and Duchi, 2019]. More importantly, we obtain a finite sample complexity bound on the probability that system will operate within the desired collision free regime, as a function of the state-dimension, the number of samples and a capacity back-off parameter. Our sample complexity result reveals an information theoretic interpretation, where the number of samples required to guarantee operation in the target regime is inversely proportional to how far we are willing to operate from the system capacity.

System diagram: A large number of decision makers in a remote estimation system communicating their observations to a base station or access point without coordination, and its block diagram abstraction considered for analytical problem formulation herein.

§ PROBLEM SETUP

Consider a remote estimation system where a collection of $n$ agents observe independent and identically distributed (iid) random vectors $\{X_i\}_{i=1}^n$, where $X_i \in \mathbb{R}^d$ and $X_i \sim f$, $i\in \{1,\cdots,n\}$. Assume throughout this paper that the data's probability density function (pdf) $f$ is smooth, and supported over the entire $\mathbb{R}^d$.[For instance, this assumption is satisfied if a Gaussian mixture describes the data well and encompasses a broad class of distributions.] The agents communicate their observations to a remote destination over a shared communication medium: only a portion $\kappa(n)<n$ of the agents is allowed to communicate noiselessly at any time. The agents behave strategically as to which observations to transmit. After observing $X_i$, the $i$-th agent makes a binary decision $U_i\in\{0,1\}$ to transmit its observation ($U_i=1$) or to remain silent ($U_i=0$). The decision variable $U_i$ is computed according to a policy $\gamma_i:\mathbb{R}^d \rightarrow \{0,1\}$, such that $U_i=\gamma_i(X_i).$

If the number of transmissions is less than or equal to the capacity $\kappa(n)$, all the transmitted observations are perfectly recovered at the receiver, and only the non-received obervations need to be estimated. If the number of transmissions is larger than the channel capacity $\kappa(n)$, nothing can be decoded at the receiver, and all of the observations need to be estimated. This is mathematically described by the following estimation rule:

\begin{equation}\label{eq:estimator}
\hat{X}_i = \begin{cases}
X_i, &  \text{if} \ \ \sum_{j=1}^nU_j \leq \kappa(n), \ U_i=1 \\
\theta_i, &  \text{if} \ \ \sum_{j=1}^nU_j \leq \kappa(n), \ U_i=0 \\
\alpha_i, &  \text{if} \ \ \sum_{j=1}^nU_j > \kappa(n)
\end{cases}
\end{equation}

where $\theta_i,\alpha_i \in \mathbb{R}^d$, $i\in \{1,\cdots,n\}$. Our goal is to jointly design the communication policies $\boldsymbol{\gamma}\Equaldef \{\gamma_i\}_{i=1}^n$ and the estimation parameters $\boldsymbol{\theta}\Equaldef \{\theta_i\}_{i=1}^n$ and $\boldsymbol{\alpha}\Equaldef \{\alpha_i\}_{i=1}^n$ that minimize the normalized mean-squared error (NMSE) between the observations and their estimates:

\begin{equation}\label{eq:nmse}
\mathcal{J}_n(\boldsymbol{\gamma},\boldsymbol{\theta},\boldsymbol{\alpha}) \Equaldef \frac{1}{n} \mathbf{E} \left[ \sum_{i=1}^n\big\|X_i-\hat{X}_i\big\|^2 \right].
\end{equation}

If $\lim_{n\rightarrow \infty} \kappa(n)/n = \bar{\kappa} \in (0,1)$, the problem of jointly optimizing the NMSE with respect to the transmission and estimation policies for a system where $n\rightarrow \infty$ is equivalent to solving:

\begin{align}\label{eq:problem}
\underset{\gamma \in \Gamma, \ \theta \in \mathbb{R}^d}{\mathrm{minimize}} \qquad & \mathbf{E}\big[\|X-\theta\|^2 \mid U=0\big]\mathbf{P}\big(U=0 \big)  \\
\mathrm{subject \ to}\qquad & \mathbf{P}\big(U=1 \big) \leq \bar{\kappa},
\end{align}

where $X\sim f$ and $\Gamma = \big\{ \gamma \mid \gamma: \mathbb{R}^d \rightarrow \{0,1\}\big\}$.

Using the law of total expectation, we expand the NMSE in <ref> as:

\begin{multline}
\mathcal{J}_n(\boldsymbol{\gamma},\boldsymbol{\theta},\boldsymbol{\alpha})
=  \frac{1}{n} \sum_{i=1}^n \mathbf{E} \left[ \big\|X_i-\hat{X}_i\big\|^2 \ \bigg|\ U_i=0,\sum_{j\neq i}^n U_j \leq \kappa(n)\right]\mathbf{P}\left(U_i=0\right) \mathbf{P}\left( \sum_{j=1}^n U_j\leq \kappa(n) \right) \\
+ \frac{1}{n} \sum_{i=1}^n \mathbf{E} \left[ \big\|X_i-\hat{X}_i\big\|^2 \ \bigg|\ U_i=1,\sum_{j\neq i}^n U_j \leq \kappa(n)-1\right]\mathbf{P}\left(U_i=1\right) \mathbf{P}\left( \sum_{j\neq i}^n U_j\leq \kappa(n) -1 \right)
\\ +
\frac{1}{n} \mathbf{E} \left[ \sum_{i=1}^n\big\|X_i-\hat{X}_i\big\|^2 \ \bigg|\ \sum_{j=1}^n U_j > \kappa(n)\right]\mathbf{P}\left( \sum_{j=1}^n U_j > \kappa(n) \right).
\end{multline}

Then, using the definition of the estimator in <ref>, and the iid assumption, we get:

\begin{multline}
\mathcal{J}_n(\boldsymbol{\gamma},\boldsymbol{\theta},\boldsymbol{\alpha})
=  \frac{1}{n} \sum_{i=1}^n \mathbf{E} \left[ \big\|X_i-\theta_i\big\|^2 \ \bigg|\ U_i=0\right]\mathbf{P}\left(U_i=0\right) \mathbf{P}\left( \sum_{j=1}^n U_j\leq \kappa(n) \right) %\\
%+ \frac{1}{n} \sum_{i=1}^n \mathbf{E} \left[ \big\|X_i-\hat{X}_i\big\|^2 \ \bigg|\ U_i=1,\sum_{j\neq i}^n U_j \leq \kappa(n)-1\right]\mathbf{P}\left(U_i=1\right) \mathbf{P}\left( \sum_{j\neq i}^n U_j\leq \kappa(n) -1 \right)
\\ +
\frac{1}{n} \mathbf{E} \left[ \sum_{i=1}^n\big\|X_i-\alpha_i\big\|^2 \ \bigg|\ \sum_{j=1}^n U_j > \kappa(n)\right]\mathbf{P}\left( \sum_{j=1}^n U_j > \kappa(n) \right).
\end{multline}

From the iid assumption of the observation sequence $\{X_i\}_{i=1}^n$, we may assume without loss of optimality that every agent uses the same policy $\gamma_i = \gamma, \ i\in\{1,\cdots,n\}$. Thus, the number of agents that decide to communicate their observations to the receiver is a Binomial random variable. Let $p = \mathbf{P}(U_i=1)$.

For $\bar{\kappa} \in (0,1)$, the following holds:

\begin{equation}\label{eq:convergence}
\lim_{n\rightarrow \infty} \frac{\kappa(n)}{n} = \bar{\kappa} \ \ \ \Longrightarrow \ \ \ \mathbf{P}\Bigg(\sum_{j=1}^n U_j > \kappa(n)\Bigg) \longrightarrow \mathbf{1}(p>\bar{\kappa}), \ \ \mathrm{a.e.}
\end{equation}

The last step is proved using the following sequence of identities:

\begin{multline}
\lim_{n\rightarrow \infty} \mathbf{P}\Bigg(\sum_{j=1}^n U_j > \kappa(n)\Bigg) =  \lim_{n\rightarrow \infty} \mathbf{E} \left[ \mathbf{1}\left(\frac{1}{n}\sum_{j=1}^nU_j > \frac{\kappa(n)}{n}\right)\right] \\
\stackrel{(a)}{=}  \mathbf{E} \left[ \lim_{n\rightarrow \infty}  \mathbf{1}\left(\frac{1}{n}\sum_{j=1}^nU_j > \frac{\kappa(n)}{n}\right)\right]
\stackrel{(b)}{=}  \mathbf{E} \Big[  \mathbf{1}\big(p > \bar{\kappa}\big)\Big]  \stackrel{(c)}{=}  \mathbf{1}\big(p > \bar{\kappa}\big),
\end{multline}

where $(a)$ follows from the Lebesgue dominated convergence theorem, $(b)$ follows from the strong law of large numbers, and $(c)$ follows from the fact that the argument of the expectation operator is a deterministic function. Therefore, using the fact that $\{X_i\}$ is iid, we argue that $\theta_1=\theta_2=\cdots$. Moreover, it is possible to show that the optimal value of $\alpha^\star_i$ satisfies:

\begin{equation}
\lim_{n\rightarrow \infty} \alpha^\star_i = \mathbf{E}\bigg[X_i  \  \bigg|  \  \sum_{j=1}^nU_j>\kappa(n)\bigg] = \mathbf{E}[X], \ \ i\in\{1,2,\cdots\}.
\end{equation}

Observe from <ref> that by an appropriate choice of $p$, we may operate in one of two regimes: the collision-free regime ($p\leq \bar{\kappa}$) or the constant-collision regime ($p>\bar{\kappa}$). And consequently, the NMSE in the regime when $n\rightarrow \infty$ becomes:

\begin{equation}\label{eq:Jinfty}
\mathcal{J}_{\infty} (\gamma,\theta) = \begin{cases}
\mathbf{E}\big[\|X-\theta\|^2 \mid U=0\big]\mathbf{P}\big(U=0 \big)  & \text{if} \ \ \mathbf{P}\big(U=1 \big) \leq \bar{\kappa} \\
\mathbf{E}\big[\|X- \mathbf{E}[X]\|^2 \big] & \text{otherwise.}
\end{cases}
\end{equation}

Clearly, the constant-collision regime offers worse performance than the collision-free regime.

Notice that in the asymptotic regime, the optimization variables $\boldsymbol{\alpha}$ are not present, meaning that the detrimental effect of collisions can be mitigated by adjusting the probability of transmission to operate below the asymptotic channel capacity parameter $\bar{\kappa}$.

§ SOLVING THE OPTIMIZATION PROBLEM

Once the constrained optimization problem for the remote estimation system in the asymptotic regime is established, we may obtain the structure of its optimal solutions. Notice that there are two variables in the optimization problem:  the function $\gamma$, and a vector $\theta$. Therefore, this is an infinite dimensional problem. Moreover, the objective in the optimization problem is non-convex.

Writing the Lagrangian associated with <ref>, we characterize its saddle points. Let $\lambda \geq 0$ and define:

\begin{equation}\label{eq:Lagrangian}
\mathcal{L}(\gamma,\theta,\lambda) \Equaldef \int_{\mathbb{R}^d} \|x-\theta\|^2 \mathbf{1}\big(\gamma(x) = 0 \big) f(x)dx + \lambda\Big(\int_{\mathbb{R}^d}  \mathbf{1}\big(\gamma(x) = 1 \big) f(x)dx -\bar{\kappa} \Big)
\end{equation}

First, we have the following structural result, which establishes that the communication policy in every saddle point is of the threshold type <cit.>.

If $(\theta^\star, \gamma^\star, \lambda^\star)$ is a saddle-point of $\mathcal{L}(\theta,\gamma,\lambda)$, then

\begin{equation}\label{eq:threshold}
\gamma^\star(x) = \begin{cases}
0, & \text{if} \ \ \|x-\theta^\star\|^2 \leq \lambda^\star \\
1, & \text{otherwise.}
\end{cases}
\end{equation}

\begin{equation}\label{eq:probability}
\mathbf{P} \big(\|X-\theta^\star\|^2 > \lambda^\star \big) = \bar{\kappa}
\ \ \
\ \ \
\theta^{\star} = \frac{1}{1-\bar{\kappa}}\int_{\mathbb{R}^d} x\mathbf{1}\big(\| x-\theta^{\star}\|^2 \leq \lambda^\star  \big) f(x)dx.
\end{equation}

From the definition of the Lagrangian in <ref>, for any $\theta \in \mathbb{R}^d$ and $\lambda \geq 0$, the communication policy that minimizes it may be constructed by assigning to a set $\mathcal{A}_0 \subset \mathbb{R}^d$, all the points $x\in \mathbb{R}^d$ such that $\| x-\theta\|^2\leq \lambda$. Otherwise, the point is assigned to $\mathcal{A}_1 = \mathbb{R}^d\setminus\mathcal{A}_0$. If there are any sets with non-zero measure for which $\| x-\theta\|^2\leq \lambda$ assigned to $\mathcal{A}_1$, we can reduce the Lagrangian even further and $(\theta^\star, \gamma^\star, \lambda^\star)$ would not constitute a saddle-point.

To establish the second result, we take the derivative of <ref> with respect to $\lambda$ and use <ref>, which leads to:

\begin{eqnarray}
\frac{\partial}{\partial \lambda}\mathcal{L}(\gamma^\star,\theta^\star,\lambda^\star) = 0 &\Longrightarrow & \int_{\mathbb{R}^d} \mathbf{1}\big(\gamma^{\star}(x) = 1 \big) f(x)dx = \mathbf{P}\Big(\|X -\theta^\star \|^2> \lambda^\star \Big) = \bar{\kappa}.
\end{eqnarray}

Lastly, taking the gradient of <ref> with respect to $\theta$, we have:

\begin{eqnarray}
\nabla_{\theta}\mathcal{L}(\gamma^\star,\theta^\star,\lambda^\star) = 0 &\Longrightarrow & \int_{\mathbb{R}^d} -2(x-\theta^\star)\mathbf{1}\big( \gamma^\star(x) = 0 \big) f(x)dx =0.
\end{eqnarray}

Then, using the characterization in <ref>, we have:

\begin{equation}\label{eq:centroid}
\int_{\mathbb{R}^d}x\mathbf{1}\big( \|x-\theta^\star \|^2 \leq \lambda^\star \big) f(x)dx = \theta^\star \underbrace{\int_{\mathbb{R}^d}\mathbf{1}\big( \|x-\theta^\star \|^2 \leq \lambda^\star \big) f(x)dx}_{= 1-\bar{\kappa}}.
\end{equation}

The structural results stated in Proposition <ref> help us define an algorithm that converges to a saddle-point of the Lagrangian and therefore defines a locally optimal policy for the remote estimation system in the asymptotic regime. First, consider the Laplacian when $\lambda$ and $\theta$, are arbitrarily fixed. Then, using <ref>, we obtain the function $\tilde{\mathcal{L}}: \mathbb{R}^{d+1} \rightarrow \mathbb{R}$ defined as:

\begin{equation}\label{eq:mod_laplacian}
\tilde{\mathcal{L}}(\theta,\lambda) \Equaldef \mathcal{L}(\gamma^\star,\theta,\lambda) = \mathbf{E}\Big[\min\big\{ \| X-\theta\|^2,\lambda \big\}\Big] - \lambda\bar{\kappa}.
\end{equation}

We are now interested in minimizing the function $\tilde{\mathcal{L}}$ over $\theta$ for any $\lambda\geq 0$. The function in <ref> is non-convex in $\theta$. In fact, this new objective function is the expectation of a clipped convex function, which is known to lead to NP hard problems for discrete random variables [Barratt et al., 2020]. Therefore, there is little hope that we will be able to obtain globally optimal solutions without making additional assumptions on the problem's structure. However, the function possess a very convenient structure, namely, that the term in the expectation can be decomposed as a difference of convex functions, also known as a DC decomposition. The DC decomposition enables the use of an algorithm known as the Convex-Concave Procedure (CCP) [Lipp and Boyd, 2016]. For the purpose of optimization over $\theta$, we may temporarily ignore the term $-\lambda\bar{\kappa}$.

§.§ Convex-Concave Procedure

To obtain a DC decomposition of the objective function, simply notice that the expectation of the minimum can be expressed as follows:

\begin{equation}
\mathbf{E}\Big[\min\big\{ \| X-\theta\|^2,\lambda \big\}\Big] = \mathbf{E}\Big[\|X-\theta\|^2+\lambda\Big] - \mathbf{E}\Big[\max\{\|X-\theta\|^2,\lambda\}\Big].
\end{equation}

Let $\mathcal{G}_{\lambda}(\theta)\Equaldef\mathbf{E}\big[\max\big\{\|X-\theta\|^2,\lambda \big\}\big]$. The CCP consists of approximating the objective function by replacing $\mathcal{G}_{\lambda}(\theta)$ with its affine approximation at a point $\theta_k \in \mathbb{R}^d$, then minimizing the resulting approximate convex function. Conveniently, the decomposition above leads to:

\begin{equation}
\theta_{k+1} = \arg \min_{\theta \in \mathbb{R}^d} \Big\{ \mathbf{E}\big[\|X-\theta\|^2\big]+\lambda - \Big( \mathcal{G}_\lambda(\theta_k) + g_\lambda(\theta_k)^T(\theta-\theta_k) \Big)  \Big\},
\end{equation}

where $g_{\lambda}$ is any subgradient of $\mathcal{G}_\lambda$. The first benefit of using the DC decomposition above where the first function is quadratic, is that solving the optimization problem above is equivalent to finding the solution of the first-order optimality condition

\begin{equation}
\nabla_{\theta} \tilde{\mathcal{L}}(\theta_{k+1},\lambda) = - \mathbf{E}\big[2(X-\theta_{k+1})\big] - g_\lambda(\theta_k) =0 \Longrightarrow \theta_{k+1} = \frac{1}{2}g_\lambda(\theta_k)+\mathbf{E}[X].
\end{equation}

The second benefit of using the DC decomposition stems from the fact that computing a subgradient $g_{\lambda}$ of the expectation of pointwise maximum of functions is extremely simple. For instance, using elementary subgradient calculus, the following is a suitable choice:

\begin{equation}
g_\lambda(\theta) = -2\mathbf{E}\Big[\big(X-\theta\big)\mathbf{1}\big(\|X-\theta\|^2>\lambda\big)\Big],
\end{equation}

which leads to:

\begin{equation}\label{eq:CCP}
\theta_{k+1} = \mathbf{E}\Big[X\mathbf{1}\big(\|X-\theta_k\|^2\leq\lambda\big)\Big] + \theta_{k}\mathbf{P}\big(\|X-\theta_k\|^2>\lambda\big).
\end{equation}

The recursion in <ref> is guaranteed to converge [Lanckriet and Sriperumbudur, 2009, Lipp and Boyd, 2016]. Moreover, this convergence is irrespective of the pdf $f$ of the random vector $X$. Then, by considering the limit of the sequence $\{\theta_k\}\rightarrow \theta^\star$, we have:

\begin{equation}
\theta^\star = \frac{\mathbf{E}\Big[X\mathbf{1}\big(\|X-\theta^\star\|^2\leq\lambda\big)\Big]}{1-\mathbf{P}\big(\|X-\theta^\star\|^2 > \lambda\big)}.
\end{equation}

If $\lambda$ is chosen such that $\mathbf{P}\big(\|X-\theta^\star\|^2 > \lambda\big) =\bar{\kappa}$, the CCP in <ref> converges to a saddle point of the Lagrangian and defines a locally optimal solution of the optimization problem in the asymptotic regime. Algorithm <ref> summarizes the discussion above.

A subgradient method for minimizing on objective function $J(\theta)$ is a recursion of the form $\theta_{k+1} = \theta_{k} - \alpha_kj(\theta_k)$, where $j$ is a subgradient of $J$. Unless $J$ is a convex function, such algorithms are not guaranteed to converge. However, the algorithm in <ref> can be understood as a subgradient method with a constant step-size. The CCP can be expressed as

\begin{equation}
\theta_{k+1} = \theta_{k} - \frac{1}{2}j(\theta_k),
\end{equation}

where $j(\theta) = -2\big(\mathbf{E}[X]-\theta\big)-g_\lambda(\theta)$
is a subgradient of the objective function in <ref>. This is a remarkable fact because the exact convergence to a local minimizer of a non-convex function with a constant step-size happens very fast in contrast to the typical decreasing step-size sequence with square-summability and non-summability conditions required for convergence in the convex case.

Data-driven policy optimization for remote estimation in the mean-field regime

* Given a batch of data $\mathcal{D}=\{x_m\}_{m=1}^M$, estimate $\hat{f}_M$. If $f$ is known, $\hat{f}_M \gets f$

* Initialization: Compute:

\begin{equation*}
\theta_0 \gets \int_{\mathbb{R}^d} x\hat{f}_M(x)dx
\end{equation*}

and solve for $\lambda^\star$ the following equation:

\begin{equation*}
\int_{\mathbb{R}^d} \mathbf{1}(\|x -\theta_0\|^2\leq \lambda^\star) \hat{f}_M(x)dx = 1 - \bar{\kappa}
\end{equation*}

Set $\lambda_0 \gets \lambda^\star.$

* Iteration:  For $k=0, 1, 2,\cdots$

a. Repeat the following recursion until convergence to $\theta^\star$

\begin{equation*}
\theta_{\ell+1} \gets \int_{\mathbb{R}^d} x \mathbf{1}(\|x -\theta_\ell\|^2\leq \lambda_k) \hat{f}_M(x)dx - \bar{\kappa}\theta_\ell
\end{equation*}

Set $\theta_{k+1} \gets \theta^\star$

b. Solve for $\lambda^\star$ the following equation

\begin{equation*}
\int_{\mathbb{R}^d} \mathbf{1}(\|x - \theta_k\|^2\leq \lambda^\star) \hat{f}_{M}(x)dx = 1 - \bar{\kappa}
\end{equation*}

Set $\lambda_{k+1} \gets \lambda^\star$

c. Repeat until convergence

§ DATA-DRIVEN ALGORITHM

One remarkable feature of this problem is the number of structural and convergence results we can obtain without the explicit knowledge of the pdf $f$. However, our algorithm relies on the availability of a smooth pdf to compute the sequence of thresholds $\lambda_k$. For that reason, a data-driven version of our algorithm cannot rely on non-smooth approximations, e.g. using the empirical distribution of the data. Our problem requires a smooth data-driven approximation. One alternative is to use Kernel Density Estimation (KDE), where the pdf $f$ is approximated by:

\begin{equation}
\hat{f}_{M}(x)=\frac{1}{M}\sum_{m=1}^M \prod_{j=1}^d\frac{1}{\sqrt{2\pi}h_M}\exp\left(-\frac{(x_j-x_{mj})^2}{2h_M} \right) \ \ \text{with} \ \ h_M = \frac{1.06}{M^{1/5}}\min\left\{s,\frac{Q}{1.34}\right\},
\end{equation}

which corresponds to KDE using a product Gaussian kernel [Wasserman, 2006].

The quantity $M$ is the number of data samples in a batch, $s$ is the sample standard deviation and $Q$ is the interquantile range[The interquantile range is the difference between the 75th and 25th percentiles of the data.]. In addition to the smoothness of the estimate $\hat{f}_M$, one special feature of using KDE to approximate the pdf is that the estimation quality can be quantified via the mean-squared integration error (MISE):

\begin{equation}\label{eq:MISE}
\mathrm{MISE} = \mathbf{E}\left[\int_{\mathbb{R}^d}\big|\hat{f}_{M}(x)-f(x) \big|^2dx\right]= \mathcal{O}\Big(M^{-4/(d+4)}\Big),
\end{equation}

where the expectation is taken with respect to the true distribution $f$ from which the data samples $\{x_m \}_{m=1}^M$ are drawn. It can be shown that no other non-parametric density estimation scheme can produce estimates with a better sample-complexity if the estimation quality is measured using the MISE criterion [Van der Vaart, 2000].

Since the algorithm described in the previous section is agnostic to the pdf $f$, a data-driven version of it simply uses a KDE $\hat{f}_M$ instead of $f$. Following [Wasserman, 2006], we have $\hat{f}_M \stackrel{P}{\rightarrow} f$, $M\rightarrow \infty$. Therefore, <Ref> produces good estimates of locally optimal solutions to <ref> as the size of the data-set increases. In the next section, we provide a sample complexity result to obtain good data-driven locally optimal solutions to <ref> in the absence of knowledge of the true probabilistic model $f$.

§ SAMPLE COMPLEXITY ANALYSIS

Consider a random batch of data samples $\{X_m\}_{m=1}^M$. Assuming that $(\hat{\theta}_M,\hat{\lambda}_M)$ are computed using the procedure in Algorithm 1, they are considered in this section as random variables. Thus, using the approximate pdf to obtain a channel access policy parametrized by $(\hat{\theta}_M,\hat{\lambda}_M)$ may yield a true probability of channel access that violates the constraint in <ref>. Such violation may be very detrimental. Here, we would like to provide a finite sample guarantee that the true probability of channel access when using a policy computed from sampled data will not violate the channel capacity constraint with high-probability.
Let $\mathbf{P}(U=1) = 1 - \int_{\hat{\theta}_M-\sqrt{\hat{\lambda}_M}}^{\hat{\theta}_M+\sqrt{\hat{\lambda}_M}} f(x)dx,$ and notice that this quantity is itself a random variable.

Consider a remote estimation system designed according to Algorithm 1. Assume that the pdf of the observations $f(x)$ is smooth with full support on $\mathbb{R}^d$. For a wireless network with assymptotic capacity $\bar{\kappa}$ and a channel access policy designed to operate with probability of transmission $\bar{\kappa}-\delta$, for $\delta\in(0,\bar{\kappa})$. Then, the true probability that the the capacity constraint will be violated decays to zero with a rate that satisfies:

\begin{equation}
\mathbf{P}\Big( \mathbf{P}(U=1)>\bar{\kappa} \Big) \leq \mathcal{O}\left(\frac{1}{\delta M^{2/(d+4)}}\right).
\end{equation}

To guarantee that the probability constraint will be met with high probability, we need to back off from the capacity by a pre-specified constant $\delta\in(0,\bar{\kappa})$.
Let $\hat{\mathbf{P}}(U=1) \Equaldef  1 - \int_{\hat{\theta}_M-\sqrt{\hat{\lambda}_M}}^{\hat{\theta}_M+\sqrt{\hat{\lambda}_M}} \hat{f}_M(x)dx = \bar{\kappa}$ (by design). Then, notice that

\begin{equation}
\mathbf{P}\left( \hat{\mathbf{P}}(U=1)-\mathbf{P}(U=1) \geq \delta \right) \leq \mathbf{P}\left( \big|\hat{\mathbf{P}}(U=1)-\mathbf{P}(U=1) \big|\geq \delta \right).
\end{equation}

The following inequalities hold:

\begin{eqnarray*}
\Big|\mathbf{P}(U=1)-\hat{\mathbf{P}}(U=1)\Big| & = & \left|\int_{\hat{\theta}_M-\sqrt{\hat{\lambda}_M}}^{\hat{\theta}_M-\sqrt{\hat{\lambda}_M}} \Big[\hat{f}_M(x)-f(x)\Big]dx\right| \\
& \stackrel{(a)}{\leq} & \int_{\mathbb{R}} \mathbf{1}\Big({\hat{\theta}_M-\sqrt{\hat{\lambda}_M}} \leq x \leq {\hat{\theta}_M-\sqrt{\hat{\lambda}_M}} \Big) \left|\hat{f}_M(x)-f(x)\right|dx \\
&\stackrel{(b)}{\leq}  & \left(2\sqrt{\hat{\lambda}_M}\right)^{1/2} \left(\int_{\mathbb{R}}\left|\hat{f}_M(x)-f(x)\right|^2dx\right)^{1/2}
\end{eqnarray*}

where $(a)$ follows from the Triangle inequality and $(b)$ follows from Hölder's inequality. Finally, we apply the expectation operator with respect to the data $\{X_m\}_{m=1}^M$, obtaining via the Cauchy-Scharz inequality the following bound:

\begin{equation}
\mathbf{E}\left[\Big|\mathbf{P}(U=1)-\hat{\mathbf{P}}(U=1)\Big|\right] \leq \left(2\mathbf{E}\left[\sqrt{\hat{\lambda}_M}\right]\right)^{1/2} \left(\mathbf{E}\left[\int_{\mathbb{R}^d}\left|\hat{f}_M(x)-f(x)\right|^2dx\right]\right)^{1/2}.
\end{equation}

Now, since we obtain $\hat{\lambda}_M$ from an algorithmic procedure that depends on a batch of sampled data, we have very little control over it, but we can guarantee that this term is bounded for any number of samples $M$.

Therefore, using <ref>, we obtain:
$\mathbf{E}\left[\Big|\mathbf{P}(U=1)-\hat{\mathbf{P}}(U=1)\Big|\right] = \mathcal{O}\big(M^{-2/(d+4)}\big).$

The following holds:

\begin{equation}
\mathbf{P}\big( \mathbf{P}(U=1) > \bar{\kappa} \big)  = %\mathbf{P}\big[ \mathbf{P}(U=1) - (\bar{\kappa}-\delta)> \delta \big] \\
%& = &
\mathbf{P}\big(\mathbf{P}(U=1) - \hat{\mathbf{P}}(U=1)> \delta \big) \\
\stackrel{(c)}{\leq}  \frac{\mathbf{E}\big[ \big| \mathbf{P}(U=1) - \hat{\mathbf{P}}(U=1) \big|  \big]}{\delta},
\end{equation}

where $(c)$ follows from Markov's inequality.

The result above mimics results related to the capacity in the Shannon sense. To guarantee a decay in the probability of violating the channel capacity constraint we back off from $\bar{\kappa}$ by $\delta$. Notice that as $\delta \rightarrow 0$, our scheme based on KDE requires an increasingly large number of samples.

§ NUMERICAL RESULTS

Consider data samples generated according to the following Gaussian mixture:

\begin{equation}
X \sim 0.2\mathcal{N}(-2,0.2)  + 0.2\mathcal{N}(-1,0.075)   + 0.1\mathcal{N}(0,0.1)   + 0.3\mathcal{N}(1,0.1)  + 0.2\mathcal{N}(2,0.1).
\end{equation}

Numerical results.

Assuming that this distribution is known, and setting $\bar{\kappa}=0.5$, <ref> results in $\theta^\star=0.0592$ and $\lambda^\star = 1.5063.$ The value of the optimal NMSE in the asymptotic regime is $\mathcal{J}_{\infty}^\star = 0.3411$. Using the data-driven approach based on KDE for several different sample sizes ($M=10^3,10^4,10^5$), we obtain the curves displayed in <ref>, where we vary the capacity back-off parameter from $\delta=10^{-5}$ to $10^{-1}$. The estimation performance of the system degrades with $\delta$, but the probability that the capacity constraint will be violated decreases sharply to zero even for moderate values of the sample size <ref> (right, top). However, the KDE is very sensitive to $M$, which can be seen from <ref> (left), yielding in a large variance in performance for smaller values of $M$, e.g. $M=10^3$ <ref> (right, bottom). An important observation is that the performance for systems designed using a random batch of data, quickly concentrate around their means, e.g. $M>10^4$.[All the code used to obtain the numerical results contained herein can be found on <https://github.com/mullervasconcelos/L4DC22.git>]

§ CONCLUSIONS AND FUTURE WORK

Scalability issues often challenge modern communication networks and their medium access control mechanisms. We argue that when it comes to applications such as the Internet of Things or in robotic swarms, it is beneficial from the analytical perspective to study the design of policies in the mean-field regime, i.e., systems with an infinite number of devices. One problem of interest consists of estimating an iid process where each random variable is accessed by a different device and transmitted over a constrained network to a remote location. Here, we showed that the interference between simulataneously transmitting agents can be effectively mitigated with appropriate design. More importantly, if we back off from the channel capacity by a constant amount, we can guarantee that the data-driven design based on Kernel Desnity Estimation will perform satisfactorily, meaning, will not violate a probability constraint with high probability.

[Asi and Duchi, 2019]
Hilal Asi and John C. Duchi.
The importance of better models in stochastic optimization.
Proceedings of the National Academy of Sciences, 1160
(46):0 22924–22930, 2019.

[Barratt et al., 2020]
Shane Barratt, Guillermo Angeris, and Stephen Boyd.
Minimizing a sum of clipped convex functions.
Optimization Letters, 140 (8):0 2443–2459,

[Chen et al., 2017]
Yue Chen, Ana Bušić, and Sean P. Meyn.
State estimation for the individual and the population in mean field
control with application to demand dispatch.
IEEE Transactions on Automatic Control, 620
(3):0 1138–1149, 2017.

[Gagrani et al., 2020]
Mukul Gagrani, Sagar Sudhakara, Aditya Mahajan, Ashutosh Nayyar, and Yi Ouyang.
Thompson sampling for linear quadratic mean-field teams.
arXiv:2011.04686, 2020.

[Gatsis, 2021]
Konstantinos Gatsis.
Linear regression over networks with communication guarantees.
In Proceedings of the 3rd Conference on Learning for Dynamics
and Control, number 144, pages 767–778. PMLR, 2021.

[Lanckriet and Sriperumbudur, 2009]
Gert Lanckriet and Bharath K Sriperumbudur.
On the convergence of the concave-convex procedure.
Advances in neural information processing systems,
22:0 1759–1767, 2009.

[Lipp and Boyd, 2016]
Thomas Lipp and Stephen Boyd.
Variations and extension of the convex–concave procedure.
Optimization and Engineering, 170 (2):0
263–287, 2016.

[Mahajan et al., 2013]
Aditya Mahajan, Nuno C. Martins, and Serdar Yüksel.
Static LQG teams with countably infinite players.
In 52nd IEEE Conference on Decision and Control, pages
6765–6770, 2013.

[Sanjari and Yüksel, 2021]
Sina Sanjari and Serdar Yüksel.
Optimal solutions to infinite-player stochastic teams and mean-field
IEEE Transactions on Automatic Control, 660
(3):0 1071–1086, 2021.

[Shapiro et al., 2021]
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski.
Lectures on stochastic programming: modeling and theory.
SIAM, 2021.

[Van der Vaart, 2000]
Aad W. Van der Vaart.
Asymptotic statistics.
Cambridge university press, 2000.

[Vasconcelos and Martins, 2017]
Marcos M. Vasconcelos and Nuno C. Martins.
Optimal estimation over the collision channel.
IEEE Transactions on Automatic Control, 620
(1):0 321–336, January 2017.

[Vasconcelos and Mitra, 2021]
Marcos M. Vasconcelos and Urbashi Mitra.
A sample-efficient scheme for channel resource allocation in
networked estimation.
In IEEE International Conference on Acoustics, Speech and
Signal Processing, 2021.

[Wasserman, 2006]
Larry Wasserman.
All of nonparametric statistics.
Springer Science & Business Media, 2006.

[Zhang et al., 2021]
Xu Zhang, Marcos M. Vasconcelos, Wei Cui, and Urbashi Mitra.
Distributed remote estimation over the collision channel with and
without local communication.
IEEE Transactions on Control of Network Systems (early
access), 2021.

[Zheng et al., 2021]
Tongjia Zheng, Qing Han, and Hai Lin.
Transporting robotic swarms via mean-field feedback control.
IEEE Transactions on Automatic Control (early access), 2021.

Our goal is to study the trade-off between task performance and latency in the following system model.

Suppose that data is distributed and is collected at $N$ non-collocated devices. We assume that each information source observes independent and identically distributed random variables. At time $k$, the collection $\mathcal{I}^U(k) \triangleq \{x_i(k)\}_{i=1}^N$ represents the unfiltered batch of data observed at all the nodes. Ideally, one would like to transmit the entire set $\mathcal{I}^U(k)$ to the cloud, as the performance of the ML task is potentially better with more data available to it. One example, is the estimation of the mean of the distribution: the more data we have available, the smaller the variance of the estimate and thus, a better performance is achieved.

Each sensor can then decide whether to transmit of not its observation to the cloud, therefore, reducing the congestion and consequently the latency over the network. Suppose each sensor uses a (measurable) stationary policy $\mu_i:\mathbb{R}^d \rightarrow \{0,1\}$ to schedule its data or not over the network. Let

\begin{equation}
U_i(k) = \mu_i\big(x_i(k) \big), \ \ i\in[N].
\end{equation}

This implies that there is another data bath, which we call the filtered information block:

\begin{equation}
\mathcal{I}^F(k)\Equaldef \{x_i(k) \mid U_i(k)=1\}.
\end{equation}

Let $D(k)$ denote the latency (or delay) of transmitting the block of filtered data $\mathcal{I}^F(k)$ over the network. On the otherhand, the more data is transmitted, the network becomes more congested, and the task is completed with a certain latency, which may not be tolerable. The degree to which latency is tolerated is captured by a constraint:

\begin{equation}
\mathbf{P}\big(D(k)\leq \tau\big) > 1-\delta.
\end{equation}

§.§ Estimation task

Consider a random i.i.d. sequence $\{\Theta_k\}_{k=1}^\infty$, $\Theta_k\sim \mathcal{N}(0,1)$. At every time-step $k$, $\Theta_k$ is measured by $N$ sensors:

\begin{equation}
Y^i_k = \Theta_k + Z^i_k, \ \ i\in[N],
\end{equation}

where $\{Z^i_k\}$ is i.i.d. with $Z^i_k \sim \mathcal{N}(0,\sigma^2).$

Let's try to understand what happens with a single