{'fraction_non_alphanumeric': 0.04125964010282776, 'fraction_numerical': 0.009768637532133676, 'mean_word_length': 4.5296375266524525, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Over-the-air Computing for Fast Distributed Optimization: Beamforming Design and Convergence Analysis

Distributed optimization concerns the optimization of a common function in a distributed network, which finds a wide range of applications ranging from machine learning to vehicle platooning. Its key operation is to aggregate all local state information (LSI) at devices to update their states. The required extensive message exchange and many iterations cause a communication bottleneck when the LSI is high dimensional or at high mobility. To overcome the bottleneck, we propose in this work the framework of distributed over-the-air computing (AirComp) to realize a one-step aggregation for distributed optimization by exploiting simultaneous multicast beamforming of all devices and the property of analog waveform superposition of a multi-access channel. We consider two design criteria. The first one is to minimize the sum AirComp error (i.e., sum mean-squared error (MSE)) with respect to the desired average-functional values. An efficient solution approach is proposed by transforming the non-convex beamforming problem into an equivalent concave-convex fractional program and solving it by nesting convex programming into a bisection search. The second criterion, called zero-forcing (ZF) multicast beamforming, is to force the received over-the-air aggregated signals at devices to be equal to the desired functional values. In this case, the optimal beamforming admits closed form. Both the MMSE and ZF beamforming exhibit a centroid structure resulting from averaging columns of conventional MMSE/ZF precoding. Last, the convergence of a classic distributed optimization algorithm is analyzed. The distributed AirComp is found to accelerate convergence by dramatically reducing communication latency. Another key finding is that the ZF beamforming outperforms the MMSE design as the latter is shown to cause bias in subgradient estimation.


I. INTRODUCTION
Distributed optimization concerns the optimization of a common function in a distributed network comprising a cluster of edge devices connected by device-to-device (D2D) links [1].
The broad field covers two popular areas: distributed machine learning aiming at leveraging local data and computer resources at edge devices to train a global artificial-intelligence (AI) model [2], and distributed consensus finding a wide range of applications in, for example, swarms of drones or robots and vehicle platooning [3]. A fundamental operation in distributed optimization, which is usually implemented using an iterative gradient-descent algorithm, is to aggregate all local state information (LSI) and use the result to update the states of all devices in each round. The required extensive message exchange and many rounds cause a communication bottleneck when the LSI is high dimensional (e.g., distributed learning) or at high mobility (e.g., drones). To overcome the bottleneck, we propose in this work the framework of distributed over-the-air computing (AirComp) to realize a one-step aggregation for distributed optimization by exploiting simultaneous multicast beamforming by all devices and the property of analog waveform superposition of a multi-access channel. To develop the framework, beamforming designs to rein in channel distortion are presented and the convergence of distributed optimization adopting distributed AirComp is studied.
Recent years have witnessed fast-growing interests in distributed machine learning as driven by the distillation of enormous mobile data into artificial intelligence (AI) to power nextgeneration applications ranging from industrial automation to smart cities and extended reality.
Relevant research mainly focuses on the efficient deployment of federated learning, arguably the most popular distributed learning framework, at the network edge, giving rise to the fast growing area of federated edge learning (FEEL) [4]. FEEL gains popularity for its capabilities of leveraging local data while helping to preserve their privacy and distributed computation resources. Typically implemented in networks with a star topology, the FEEL algorithm iterates between 1) aggregation at an edge server over local models, which are updated by edge devices using local data and uploaded over wireless channels, to update a global model, and 2) broadcast of the model to all devices for updating, until the global model converges. The main challenge confronting efficient FEEL is the communication bottleneck caused by uploading highdimensional local modes (or stochastic-gradients) from potentially many devices over a multiaccess channel. The required large number of rounds/iterations (e.g., tens to hundreds of rounds) exacerbates the issue. Attempts to overcome the bottleneck have led to the proposal of different techniques including radio resource management [5], [6], model quantization [7], [8], and device scheduling [9], [10]. One particular class of techniques of our interest, known as over-the-air FEEL, features the application of AirComp to realize over-the-air model aggregation in FEEL [11]- [14]. The principle underpinning AirComp (as well as over-the-air FEEL) is to exploit the waveform superposition property such that the signal received at the server approximates a desired aggregation function of linear analog modulated data (e.g., local models/gradients) simultaneously transmitted by devices [12], [15].
Most recently, researchers have studied distributed FEEL targeting a cluster of devices without coordination by a sever and connected by D2D links [16]- [18]. The original techniques for server-assisted FEEL can be adopted by arranging the devices to take turn or use orthogonal channels to play the role of edge server [17], [19]. As the resultant sequential aggregation is time consuming, attempts on realizing parallel operations have been made by selecting multiple weakly coupled clusters of devices to perform simultaneous intra-cluster aggregation [16], [18].
Such approaches are ineffective for a single cluster of devices with tightly coupled links such as a drone swarm or a vehicle platoon, and still require multiple time slots to complete aggregation over all devices. Fundamentally, the drawback of the existing approaches is rooted in attempting to orthogonalize multiple aggregation processes in distributed optimization. On the contrary, we advocate fusing them into a single multi-aggregation process to enable a one-step distributed aggregation over all devices. Thereby, the resultant design, termed distributed AirComp, supports fast distributed FEEL and distributed optimization at large.
Consider the aggregation operation of distributed optimization among K devices. The goal of designing distributed AirComp is to realize one-step updating of the states of all devices via over-the-air aggregation over their LSI. To this end, all devices simultaneously multicast LSI to their peers and at the same time receive aggregated LSI via full-duplex communication [20].
We propose provisioning devices with transmit antenna arrays to enable multicast beamforming for reining in the sum AirComp error. On the other hand, the use of receive arrays can support aggregation beamforming as studied in [15]. To simplify our design, we assume single receive antenna at devices. The extension of the current design to include aggregation beamforming is straightforward but make the design tedious without new insight. Usually targeting a singlecell system, traditional multicast beamforming at the base station aims to efficiently deliver information to multiple receivers under their quality-of-service requirements. Mathematically, the beamforming design can be formulated as an optimization problem with the objective of minimizing the required transmission resources at the base station (e.g., power and array size) under the constraints of receive signal-to-noise ratios (SNRs) [21], [22]. Another popular "maxmin" formulation targets maximizing the lowest rate or receive SNR among the receivers under a transmission power constraint [23], [24]. Consider the context of distributed AirComp. Define the AirComp error as the deviation of an aggregated signal from the desired average-functional value due to channel fading and noise. Then the multicast beamforming from the perspective of an individual device aims to minimize the sum AirComp error over other devices under a transmission power constraint. Solving such a problem is no more difficult than the mentioned traditional ones. However, the new challenge arises from K simultaneous over-the-air aggregation processes coupling multicast beamforming at K devices. This necessitates the joint beamforming design that should account for all D2D-channel states in the system. To be precise, the multicast radiation patterns of K devices should be jointly optimized under individual power constraints such that their over-the-air superposition leads to the minimization of sum AirComp error.
AirComp requires the aggregated signal arriving at a device to be scaled by a factor, called alignment level, to balance approaching a desired functional value and noise amplification [25].
The said problem is further complicated by the need of optimization over the alignment level.
In contrast, transmit beamforming for single-aggregation AirComp is simple as its main purpose is to overcome the fading of an associated single-user channel, and hence is irrelevant to the current problem [15], [26].
In this work, besides proposing the principle of distributed AirComp as described earlier, we design distributed multicast beamforming to materialize the principle and further apply the design to distributed optimization. The key contributions and findings are summarized as follows.
• MMSE beamforming for distributed AirComp: Consider the design criterion of minimizing the sum AirComp error defined as the sum mean-squared error (MSE) over all devices with respect to the desired average-functional values. We propose an efficient approach for optimally solving the mentioned problem of distributed multicast beamforming. Without compromising the optimality, the optimal alignment factor conditioned on beamforming is derived in a closed form and substituted into the original problem. Even though the resultant problem is still non-convex, it can be transformed into an equivalent concave-convex fractional program. The transformation admits an efficient solution method that nests solving a convex problem into a bisection search. The results reveal that the optimal multicast beamforming at a device is steered along the centroid of the column vectors of a traditional MMSE precoder for the associated D2D multiuser channel to the peers, thereby balancing their AirComp errors; at least one device transmits with full power while some devices transmit with partial power.
• Zero-forcing (ZF) beamforming for distributed AirComp: Consider the design criterion of forcing all receive signal power to approach a uniform level for the purpose of aggregation without attempting to avoid potential noise amplification as in the MMSE case. To minimize the resultant sum AirComp error, the ZF multicast beamformers conditioned on the alignment factor can be reduced into a single-device design with the solution derived in a closed form. It is observed to have a similar centroid form as the MMSE counterpart but is based on a traditional ZF precoder. Given the beamformers, the alignment factor is obtained as the minimum of a derived expression over devices, which represents an attempt to cope with the weakest set of D2D links limiting the performance of distributed AirComp.
• Convergence of distributed optimization: The preceding distributed AirComp framework is applied to implement distributed optimization over D2D links, which is based on the widelyused distributed dual averaging algorithm. The convergence analysis shows that AirComp errors induce bias terms in the gap between the minimized loss function and its ground truth. The key finding is that the MMSE and ZF designs for distributed multicast beamforming lead to biased and unbiased estimations of ground-truth stochastic subgradients at devices, respectively. Consequently, at a low-to-medium receive SNR, the former results in a converged test accuracy substantially lower than that in the ideal (noise-free) case while the loss of the ZF counterpart is negligible. This is opposite to the fact that ZF is sub-optimal in terms of minimizing the sum MMSE AirComp error. For both designs, the said loss is shown to diminish as the transmit SNR grows by being inversely proportional to its square root.
The remainder of this paper is organized as follows. An overview of distributed AirComp is given in Section II. The MMSE and ZF designs of distributed multicast beamforming are presened in Sections III and IV, respectively. The application of distributed AirComp to distributed optimization is studied in Section V. Experimental results are presented in Section VI, followed by concluding remarks in Section VII.

A. System Model
As illustrated in Fig. 1, the considered distributed system comprises K edge devices without coordination by a server. Each device is equipped with N t transmit antennas and one single receive antenna to support multicast beamforming and full-duplex communication. The number of transmit antennas is assumed sufficiently large, i.e., (N t K −1), to provide enough degreesof-freedom (DoF) for each device to support simultaneous aggregations at (K − 1) peers. For full-duplex communication, it is assumed that a transmitter is perfectly decoupled from a receiver at the same device via passive and/or active self-inference cancellation [27] as illustrated in Fig. 1.
As the process of distributed optimization spans multiple rounds, time is divided into rounds with a fixed duration denoted as T cmm ; each round is further divided into D symbol slots.
Channels are assumed to be static in each round and varying over rounds. For simplicity, each link is assumed frequency non-selective with the bandwidth represented by B, giving the symbol duration T s = 1 B . Global channel state information (CSI) is available at each device via estimation exploiting channel reciprocity or efficient feedback [15]. The required training overhead is assumed negligible compared with high-dimensional LSI exchange. In each round, each device, say device k, transmits a symbol vector, denoted as s k , that comprises D symbols and spans the round duration of T cmm = DT s .

B. Distributed AirComp Design
An iterative algorithm for distributed optimization (see Appendix A) comprises multiple communication rounds. In each round, all devices broadcast their LSI simultaneously using linear analog modulation and multicast beamforming, and at the same time receive the overthe-air aggregated signals from other devices. All devices are assumed to be synchronized via a common clock. Consider an arbitrary round, for each device, say device k, let p k ∈ C Nt×1 denote the multicast beamformer under the power constraint, p k 2 P 0 , with P 0 representing the maximum power. Then the over-the-air aggregated signal vector received by the device, denoted as y k , is given as where s denotes the symbol row vector transmitted by device , h k ∈ C Nt×1 is the channel vector for the link from device to k, andw k ∼ CN (0, σ 2 I) is channel noise. Upon receiving the aggregated signal, it is scaled as shown below to yield the desired aggregation form: where η is the alignment factor that helps to reduce the AirComp error.
Consider round n and device k. The transmitted symbol vector is a linear analog modulated . Normalization of the variable is necessary for meeting the transmission power constraint and avoiding a nonzero DC level, which unnecessarily increases the power. For distributed optimization with a general objective function, typically the statistics of the elements of z k (n) are different and also vary over rounds (see e.g., [28]). Define the round-dependent mean and variance of local state variables, which are assumed uniform for all devices, as . These parameters can be estimated offline and stored at devices [28]. Let q(·) denote the normalization function such as s k (n) = q(z k (n)) = z k (n)−M (n) Note that E[s k (n)] = 0 due to the non-uniform distributions of the elements in s k (n). Then the received signal is denormalized as where the channel noise w k ∼ CN 0, V 2 σ 2 (K−1) 2 η I .

C. Distributed Optimization and Performance Metric
In distributed optimization, there exist local objective functions associated with individual devices. The function for device k is denoted as f k : R D → R. Following the common assumptions, each function is assumed to be convex and hence sub-differentiable, but not necessarily smooth.
The global objective, denoted as f , is related to local objectives by for a common state of devices. Then the goal of distributed optimization is to find the optimal common state x , which represents a consensus among devices, that minimizes the objective. Mathematically, where the state space X is a closed, D-dimensional convex set.
A classic algorithm, distributed dual averaging, for solving (4) is discussed in Appendix A.
In this algorithm, the local state of each device, say device , contains a primal variable and a dual variable, which are denoted as x (n) ∈ R D and z (n) ∈ R D for round n, respectively. Each round, say round n, of the algorithm comprises a three-step procedure simultaneously executed at each device, say device : (1) calculate a stochastic subgradientg (n) of its local loss function at x (n); (2) aggregate the dual variables of all other devices and apply the result together with g (n) to update the local dual variable as z (n + 1); (3) project z (n + 1) onto the feasible set X to obtain the updated primal variable x (n + 1) [29]. Only Step (2) requires information exchange among devices. We focus on its one-step implementation using distributed AirComp in the preceding subsection. To this end, (27) for Step (2) at device is modified as where the received signal r (n) is given in (3) and β is a constant weight (see Appendix A).
Note that the ideal received signal, namely the ground truth, is 1 AirComp error is suitably defined as the sum mean-square-error (MSE) between the received signal and its ground-truth: where the expectation is taken over the distribution of the transmitted symbol and the received noise w is developed based on fractional programming.

A. Optimal Distributed Multicast Beamforming
Consider an arbitrary round with its index omitted for ease of notation. With the sum AirComp error in (6), the mentioned optimization problem is formulated as follows Due to the coupling of {p k } and η, Problem (P1) is non-convex and hence directly solving it is difficult. To overcome the difficulty, an alternative approach is presented as follows.
First, given {p k }, Problem (P1) is reduced to the following conditional problem: The objective in (7) is found to be convex and then the optimal η mmse is obtained as Next, we proceed to optimize {p k }. Substituting η mmse in (8) into Problem (P1) gives Problem (P1.1) remains non-convex. Nevertheless, the result in the following lemma can transform this problem into a tractable equivalent form.
It can be straightforwardly proved by a simple variable substitution.
, the optimal solution of (P1.1) can be written asp k = −p k , where p k is the optimal solution of (P1.2). Sincep k and p k correspond to the same optimal value of the objective of (P1.1), considering the case in Lemma 1 where K is sufficient for the purpose of solving Problem (P1.1). This allows a property of factional program to be applied.
To this end, define the upper contour set of a function f : R n → R at c = f (x 0 ) for some x 0 ∈ R n as the set {x ∈ X : f (x) c}. One useful property of the concave-convex fractional program in Lemma 1 is its strict quasi-concavity [30]. Specifically, the upper contour sets of the objective of Problem (P1.2), are convex. By introducing an auxiliary variable α(α > 0), which corresponds to the aligned fraction, Problem (P1.2) can be written as the convex problem of maximization over α as follows: To solve the above problem requires consideration of a related problem of transmission power minimization described as follows. Define the maximum power as p max = max k p k 2 2 . Then given α, the mentioned problem is given as  Select α u so that α = α u makes p (α u ) defined in (P1.4) larger than P 0 .

B. Centroid Beamforming
To shed light on the structure of the optimal MMSE design of distributed multicast beamformer, we consider a special case when the number of antennas be the matrix with its -th column being h H k with = k. In the current case, H k is an invertible full-rank matrix. The convexity of Problem (P1.4) allows its KKT conditions to be a sufficient and necessary condition for its optimal solution. Based on the KKT conditions, Lemmas 4 and 5 are obtained as follows with proofs in Appendix E.
and those with full-power transmission are given as where µ k is the regularization term that diminishes as the SNR increases.
The result in (9) shows that the direction of the optimal beamforming of a device with partial-power transmission points to the centroid of the column vectors of a ZF or a regularized channel-inversion precoder. Such a design overcomes fading of multiuser channels to facilitate simultaneous signal alignments at other devices while balancing their AirComp errors.

IV. ZERO-FORCING DESIGN OF DISTRIBUTED MULTICAST BEAMFORMING
In this section, we consider the ZF design criterion of forcing the received signals to approach the desired ground-truth values without consideration of channel noise. Under this criterion, a low-complexity design of distributed multicast beamforming is presented as follows. Conditioned on the alignment factor η, the ZF criterion allows the joint beamforming design to be decoupled into the following individual beamforming problems formulated for device k as where the objective function is termed as misalignment error. Note that in this case, since N t K − 1, there is sufficient DoF to align the channels, i.e., H H k p k = √ η1 (K−1) , ∀k is always satisfied. Therefore H H k p k − √ η1 (K−1) 2 = 0 always has non-trivial solutions. Then following lemma gives a solution with the smallest norm. Proposition 1. When N t K − 1, given the alignment factor η, the misalignment error of device k is minimized by following ZF multicast beamforming: where η is chosen to meet the power constraint.
Proof. See Appendix F.
The beamformer in (11) can be written in a centroid form similarly as its MMSE counterpart, Specifically, this multicast beamforming is given by the centroid of the column vectors of a traditional ZF precoder for the associated D2D multiuser channel to the peers. However, it should be noted that compared with MMSE beamforming, this ZF scheme can potentially amplify the noise and is therefore vulnerable to deep fading.
By substituting (11) in Proposition 1, the problem of alignment-error minimization over the alignment factor η is Since the objective of Problem (P2.1) is a monotonically decreasing function of η, the optimal η ZF is directly given as By constructing a Rayleigh quotient as following, we have where (a) is due to that H H k H k is a hermitian matrix and λ min (.), λ max (.) correspond to the minimum and maximum eigenvalue of given matrix separately. Using this upper bound on η ZF leads to an upper bound on the sum AirComp error in the current case: Note that the minimum eigenvalue λ min H H k H k is a monotonically increasing function of N t [26]. This demonstrates the diversity gain of increasing the transmit array size for reducing the sum AirComp error. Next, comparing the sum AirComp errors of the MMSE and ZF designs, it is worth mentioning that MSE mmse MSE ZF .

V. APPLICATION TO DISTRIBUTED OPTIMIZATION
In this section, we consider the application of distributed AirComp designed in the preceding sections to provide an efficient air interface for implementing the distributed-optimization algorithm in Appendix A in a D2D network. The effects of AirComp error on its convergence are charaterized mathematically. For tractable analysis, several assumptions commonly made in the literature (see e.g., [31]) are also adopted in this work.

Assumption 1 (Continuity). Each local objective function is L-Lipschitz continuous:
where L is a constant.
Assumption 2 (Local Gradient Estimation). The stochastic subgradientg k (n) at the k-th device is an unbiased estimate of the ground-truth local subgradient, g k (n) ∈ ∂f k (x k (n)), with bounded second moment: where Ω is a given constant.

A. Effects of AirComp Error
In this subsection, we investigate the effects of AirComp error on the subgradient estimation and state updating, which are the key operations of distributed optimization. The variables in the subsequent analysis follow those defined in Appendix A.
First, consider round n, the receive signal vector at device k in (3) can be rewritten as where the random variable ∆ k (n) defined below represents the distortion caused by wireless propagation: Note that the summation of ∆ k (n) 2 over devices gives the sum AirComp error in (6). Then based on (5) and (30), the state variable at device i is updated as whereĝ k (n) represents the channel distorted version of the stochastic subgradient,ĝ k (n), namelŷ g k (n) =g k (n) + β∆ k (n).
Next, the effects of AirComp error are reflected by the deviation of the noisy subgradient, g k (n), from its ground truth. Consider ZF beamforming designed in Section IV. From its definition, the channel distortion in (18), ∆ k (n), reduces to channel noise: ∆ k (n) = w k (n).
It follows from this fact and Assumption 1 that the noisy subgradientĝ k (n) yields an unbiased estimate of the ground truth: Consider MMSE beamforming designed in Section III. It follows from (18) and its definition, the corresponding noisy subgradient, however, is a biased estimate of the ground truth: where E [s (n)] = 0 as discussed in Section II. Even though the MMSE beamforming achieves lower AirComp error as defined in (6) than the ZF counterpart, the former's biased subgradient estimation leads to worse convergence performance as elaborated in the next subsection.
Last, a result useful for convergence analysis is obtained by bounding the deviation of the state variable (i.e., dual variable), z k (n), from its average z(n) = 1 K k z k (n), termed dual-variable deviation. Note that it also serves as a measure of the deviation of individual noisy subgradients.
Mathematically, the deviation is defined as E z(n) − z k (n) * with · * = sup u=1 ., u denoting the dual norm. To bound the dual-variable deviation, based on Assumption 2, the second moment of the noisy sub-gradient,ĝ k (n), can be bounded as: where the AirComp error MSE(n) defined in (6) applies to both the cases of ZF and MMSE beamforming. Using the bound, the desired result is obtained as follows.
Lemma 6. For distributed optimization using distributed AirComp (with either MMSE or ZF beamforming), the expected dual-variable deviation can be bounded as: where ξ = Ω 2 + β 2 maxn MSE(n) K and λ 2 is the second largest eigenvalue of the edge-weight matrix P.
Proof. See Appendix G.
One can observe from the above result that dual-variable deviation grows with the numbers of rounds and users following O(log(N √ K)). Nevertheless, it is shown in the next section that with a properly chosen step size, the noisy primal variables, {x k (N )}, can asymptotically approach the optimal point as the number of rounds, N , increases.

B. Convergence Analysis
The convergence of the distributed-optimization algorithm (see Appendix A) as implemented using distributed AirComp is analyzed as follows. To begin with, given N rounds, the convergence is evaluated using the metric of expected suboptimality gap, x k (N ) and x represent the noisy state at device k and the optimal point, respectively.
Theorem 1 (Convergence with Distributed AirComp). Given the optimal point x , assume that the proximal function satisfying (26) in Appendix A is bounded by some constant R as ψ (x ) ≤ R 2 . Let the step size α(n) be chosen as α(n) = R √ 1−λ 2 4ξ √ n . Then the expected suboptimality gap can be bounded for the ZF multicast beamforming as and for the MMSE design as where λ 2 is the second largest eigenvalue of the edge-weight matrix P.
Proof. See Appendix H.
In the above results, those terms comprising the AirComp error, MSE(n), reflect the effects of distributed AirComp. For a sanity check, substituting MSE(n) = 0 into the results in Theorem 1 yields the existing result for the ideal case of noiseless channels [29]. Next, comparing with (24), the last term at the right-hand size of (25)  devices take turn to broadcast their LSI to peers based on time-division multiple access (TDMA). ZF precoding is applied.
• Single-aggregation AirComp: In each round, the K AirComp processes in the system are orthogonalized or equivalently completed sequentially using TDMA, giving the name of the scheme. Consequently, the per-round latency is K-time higher than that of the proposed distributed AirComp although the AirComp error is smaller as demonstrated in the sequel.
The traditional beamforming design for a multiple-input-single-output channel is applied together with effective channel inversion for receive-signal alignment, which is a special case of the AirComp design in [15].

A. Performance of Distributed AirComp
In Fig. 2, the per-round communication latency for LSI exchange between K devices is compared between the proposed distributed AirComp and benchmarking schemes for a varying number of devices, K. The transmit SNR is 20 dB. To support the number of devices as many as 50, each device is provisioned with a large-scale array with N t = 100. One can observe that the feature of simultaneous multicasting enables the proposed distributed AirComp to keep the latency constant instead of increasing with the number of devices as for the benchmarking schemes. Distributed AirComp is observed to achieve much lower latency than the latter with the gap increasing rapidly as K grows. When there are many devices (e.g., 50), the latency reduction of distributed AirComp is more than two-order of magnitude with respect to (w.r.t.) digital communication and about 50-time w.r.t. single-aggregation AriComp.
Next, the curves of AirComp error versus transmit SNR, number of transmit antennas N t , and number of devices K are plotted in Fig. 3(a), 3(b), and 3(c), respectively. By default, the number of devices K = 5. All simulation results demonstrate decreasing AirComp error as any of the three parameters increases. Relatively small array sizes, N t = 4 and N t = 18, are considered in Fig. 3(a) and and 3(c), respectively, to investigate the limitations of distributed AirComp. One can observe from Fig. 3(a) that distributed AirComp, which strives to support K AirComp processes simultaneously despite a small array size, incurs about 10-time larger AirComp error than single-aggregation AirComp. Furthermore, as shown in Fig. 3(c), the former sees that the AirComp error saturates as K increases, indicating the cancellation of the opposite effects of aggregation gain in error suppression and severer receive-signal misalignment. The above disadvantage of distributed AirComp as a price for dramatic latency reduction is alleviated when the array size increases as shown in Fig. 3(b). For instance, for N t = 40, the error ratio between distributed AirComp and single-aggregation counterpart reduces to below 4 times. In addition, it can be observed that for distributed AirComp, MMSE multicast beamforming outperforms the ZF design in the regimes of low-to-medium SNRs or array size or as the number of devices grows.

B. Performance of Distributed Optimization
Consider FEEL, a typical scenario of distributed optimization, where the number of devices

A. Distributed Optimization Algorithm
Consider distributed optimization in a distributed network described by an undirected graph denoted as G = (V, E), where V represents the set of K nodes (e.g., edge devices) and E represents the set of edges. Each edge, say the one connecting the kth and th node, is assigned a non-negative weight denoted as P k . Then the graph structure can be specified by the K × K weight matrix P with (k, )th element being P k . In particular, two nodes k = are connected (i.e., (k, ) ∈ E) if and only if P k > 0 or otherwise P k = 0. The matrix P is constrained to be doubly stochastic, namely that K =1 P k = K k=1 P k = 1. Given the distributed network, the problem of distributed optimization in (4) can be solved using the classic iterative algorithm of distributed dual averaging described as follows [29], [31].
To begin with, let each device, say device k, maintain a two-variable state, (z k (n), x k (n)), each being a D×1 row vector with real elements and x k (n) ∈ X , which is the support of the objective function. Moreover, a key component of the algorithm is a proximal function ψ : R D → R that is assumed to be 1-strongly convex with respect to some norm · : One example of such a function is ψ(x) = 1 2 x 2 . For device k, the state variable x k (n) ∈ X represents the local estimate of the optimal solution for (4) at iteration n. Recall thatg k (n) represents the stochastic subgradient of the local loss function as computed at device k using local data. Then given non-increasing step size {α(n)}, all devices perform simultaneous updating of their states [31]: for all k and the n iteration, x k (n + 1) = Π ψ X (z k (n + 1), α(n)) , where the constant β ∈ (0, 1), N (k) represents the neighbourhood of node k on the graph G, and Π ψ X the projection function defined as Π ψ X (z k (n + 1), α(n)) := argmin x∈X z k (n + 1), x + 1 α(n) ψ(x) (29) with ψ(.) being the proximal function that satisfies (26). For ease of notation, define the weight matrix W = (1 − β)I + βP with the (k, )th element denoted as W k . Then (27) is rewritten as Note that the updating in (30) is for node k to compute a consensus based on the states of the peers. On the other hand, the projection function in (29) yields x k (n + 1) that minimizes an averaged first-order approximation of the objective function. It is assumed that ψ(x) 0 ∀ x ∈ X and ψ(0) = 0 without loss of generality.
The above updating procedure is iterated until a consensus on the minimum of the objective is reached, as the changes of the states of all devices fall below a given threshold. Specifically, given a threshold ε, the convergence criterion can be specified using the expected suboptimality gap [29]: where ε is a given constant and the expectation in (31) taken over all sources of randomness.

B. Proof of Lemma 1
First, given K it is direct to see that the objective function of P1.2 is positive. Denote x k = Re(h H k p k ), y k = Im(h H k p k ) as the real and imaginary parts of h H k p k , respectively. Then the numerator and denominator of objective function of Problem (P1.2) can be written as Notice that the eigenvalues of the Hessian matrix of function B(x, y) : e 1 = 2Kσ 2 (Kσ 2 + K k = (x 2 k +y 2 k )) 3/2 , e 2 = e 3 = · · · = e 2K(K−1) = 2 (Kσ 2 + K k = (x 2 k +y 2 k )) 1/2 are all positive numbers, hence the B(x, y) is a convex function. Then, since A(x) is a linear function, one can obtain that the the Problem (P1.2) is a concave-convex fractional program, with its objective function proved to be strictly quasi-concave and pseudo-concave [30]. Therefore, the objective function of Problem (P1.2) is a positive unimodal function and Problem (P1.2) has an unique optimal solution, and the proof is completed.

C. Proof of Lemma2
It is first to prove that for any α 1 α 2 , p k (α 1 ) p k (α 2 ) by contradiction. Assume there exists α 1 α 2 such that p k (α 1 ) > p k (α 2 ). Since Problem P1.2 has been proved to be an strictly quasi-concave function, then for α 1 α 2 , the size of feasible region P 1 for α = α 1 is larger than or equal to the size of P 2 for α = α 2 , which means we can at least find a set of {p k } in P 1 that makes p k (α 1 ) = p k (α 2 ). This contradicts the previous assumption and thus for any Moreover, for α = 0, we have p k = 0, ∀k, and thus p k (α) = 0. Then, for any α > 0, there must ∃ p k such that p k 2 > 0, which means p k (α) > 0. To this end, p k (α) cannot be a constant function for all α. Then the proof is finished.

D. Proof of Lemma 3
First, the objective of Problem (P1.4) is linear and the second constraint is a convex set. Then given any α, left-hand-side of the first constraint can be regarded as a 2-norm function and hence convex. Then the right-hand-side of the first constraint is a linear function. Therefore, the proof is completed.

E. Proof of Lemma 4 and Lemma 5
We first give the corresponding Lagrange function of Problem (P1.4) as below where λ and {v k } are the Lagrangian multipliers. The KKT conditions are given by In (33), the first condition indicates ∃k, v k = 0. This reveals that for any α, at least one device transmits with power p (α). Then by Lemma 2, one can conclude that for the maximum aligned fraction α, at least one device transmits with the maximum power P 0 . Next By denoting µ k = 2v k c 0 λ , then the desired results are obtained.

F. Proof of Proposition 1
The problem of finding the smallest norm solution for H H k p k − √ η1 (K−1) 2 = 0 is equivalent to the following optimization problem: This problem is convex since both the objective and feasible region are convex. By reusing Lagrange multiplier λ, the Lagrange function can be written as The KKT conditions are given by Take the first condition into the second one, one can get the expression of λ. Then take λ back to the first condition, the desired result is obtained.

G. Proof of Lemma 6
From (19), the average state in round n is given as Define the matrix Φ(n, s) = W n−s+1 . Then, for the state update z k (n + 1) at device k, it is expanded as follows z k (n + 1) = K

H. Proof of Theorem 1
The proof is close to the convergence proof for distributed dual averaging [31] with some modifications. First, an useful lemma is introduced as follows.
For the ZF beamforming case, by (20), one can find that the last term of (42) is equal to zero. By taking the upper bound in Lemma 6 into (42) and with ψ (x ) ≤ R 2 , α(n) = R √ 1−λ 2 4ξ √ n , the convergence for ZF beamforming in Theorem 1 can be obtained. However, for the MMSE beamforming case, by (21), the last term of (42) is nonzero due to the biased gradient.
Nevertheless, this term can be bounded as The last inequality follows from E [ x k (n) − x ] E [ x k (0) − x ] and x k (0) = 0, ∀k. Taking this into (42), then Theorem 1 is proved.