International audience

Channels with synchronization errors, exhibiting deletion and insertion errors, find practical applications in DNA storage, data reconstruction, and various other domains. The presence of insertions and deletions renders the channel with memory, complicating capacity analysis. For instance, despite the formulation of an independent and identically distributed (i.i.d.) deletion channel more than fifty years ago, and proof that the channel is information stable, hence its Shannon capacity exists, calculation of the capacity remained elusive. However, a relatively recent result establishes the capacity of the deletion channel in the asymptotic regime of small deletion probabilities by computing the dominant terms of its capacity expansion. This paper extends that result to binary insertion channels, determining the dominant terms of the channel capacity for small insertion probabilities and establishing capacity in this asymptotic regime. Specifically, we consider two i.i.d. insertion channel models: the simple insertion channel, where a random bit may be inserted after each transmitted bit, and the Gallager insertion model, for which a bit is replaced by two random bits with a certain probability. To prove our results, we build on methods used for the deletion channel, employing Bernoulli(1/2) inputs for achievability and coupling this with a converse using stationary and ergodic input processes, and show that the channel capacity differs only in the higher order terms from the achievable rates with i.i.d. inputs. The results, for instance, show that the capacity of the simple insertion channel is higher than that of the Gallager insertion channel, and quantify the difference in the asymptotic regime.

Channels with synchronization errors, such as deletions and insertions, are encountered in DNA storage, data reconstruction, and other applications. These errors introduce memory to the channel, complicating its capacity analysis. As an example of synchronization error channels, this paper analyzes binary insertion channels for small insertion probabilities, identifying dominant terms of the capacity expansion, and hence establishing its capacity in this regime. This is accomplished by using independent and identically distributed (i.i.d.) Bernoulli$(1/2)$inputs for achievability and a converse based on the use of stationary and ergodic processes that match closely with each other, differing only in higher-order terms.

Deep neural networks offer reliable solutions for many classification and regression tasks; however, their applicability in real-time wireless applications with simple sensor networks is limited due to the significant amount of bandwidth required for data transmission. In this study, we propose a multisensor wireless inference system where an edge device combines features sensed by different sensors. Due to the limited computational capabilities of sensors, the features obtained through the front part of the network are transmitted to the edge device, which uses Lp-norm inspired and LogSumExp (LSE) approximations for the maximum operation to obtain transformation-invariant features. These features can be transmitted in an over-the-air manner, ensuring bandwidth-efficient transmission. We also consider multi-modal network branches for sensors based on their computational capabilities, improving the overall performance by using data obtained from both computationally limited and powerful devices enhancing the usefulness of the overall sensed data.

We study federated learning (FL) with over-the-air aggregation over time-varying wireless channels. Independent workers compute local gradients based on their local datasets and send them to a parameter server (PS) through a time-varying multipath fading multiple access channel via orthogonal frequency-division multiplexing (OFDM). We assume that the workers do not have channel state information, hence the PS employs multiple antennas to alleviate the fading effects. Wireless channel variations result in inter-carrier interference, which has a detrimental effect on the performance of OFDM systems, especially when the channel is rapidly varying. We examine the effects of the channel time variations on the convergence of the FL with over-the-air aggregation, and show that the resulting undesired interference terms have only limited destructive effects, which do not prevent the convergence of the learning algorithm. We also validate our results via extensive simulations, which corroborate the theoretical expectations.

Large-scale machine learning and data mining methods routinely distribute computations across multiple agents to parallelize processing. The time required for the computations at the agents is affected by the availability of local resources and/or poor channel conditions, thus giving rise to the “straggler problem.” In this paper, we address this problem for distributed approximate matrix multiplication. In particular, we employ Unequal Error Protection (UEP) codes to obtain an approximation of the matrix product to provide higher protection for the blocks with a higher effect on the multiplication outcome. We characterize the performance of the proposed approach from a theoretical perspective by bounding the expected reconstruction error for matrices with uncorrelated entries. We also apply the proposed coding strategy to the computation of the back-propagation step in the training of a Deep Neural Network (DNN) for an image classification task in the evaluation of the gradients. Our numerical experiments show that it is indeed possible to obtain significant improvements in the overall time required to achieve DNN training convergence by producing approximation of matrix products using UEP codes in the presence of stragglers.

We study federated learning over wireless channels where a massive dataset is distributed across independent workers which compute their local gradients based on their own datasets. Workers send their gradients through a multipath fading multiple access channel with orthogonal frequency division multiplexing to mitigate the frequency selectivity of the channel. We assume that there is no channel state information (CSI) at the workers, and the parameter server (PS) employs multiple antennas to align the received signals. To reduce the power consumption and hardware costs, we employ complex-valued low-resolution analog-to-digital converters (ADCs) at the receiver side, and study the effects of practical low-cost ADCs on the learning performance. Our results show that the impairments caused by low-resolution ADCs, including those of one-bit ADCs, do not prevent the convergence of the federated learning algorithm, and the multipath channel effects vanish when a sufficient number of antennas are used at the PS.

We study distributed machine learning (ML) sys-tems where independent workers compute local gradients based on their local datasets and send them to a parameter server (PS) through a time-varying multipath fading multiple access channel (MAC) via orthogonal frequency-division multiplexing (OFDM). We assume that the workers do not have channel state information (CSI), and hence the PS employs multiple antennas to remove the fading effects. Time variations in the wireless channel result in inter-carrier interference (ICI), which has a detrimental effect on the performance of OFDM systems, especially when the channel variations are rapid. To examine the effects of channel variations on federated learning systems, we perform an analysis of the interference in the aggregate gradient term at the PS due to Doppler, and show that the undesired effects caused by them are limited. Specifically, the ICI term becomes insignificant for slow to moderate time variations. We also validate our theoretical expectations via simulations and demonstrate that the destructive effect of ICI can be alleviated for moderate level of channel variations.

We study collaborative machine learning systems where a massive dataset is distributed across independent workers which compute their local gradient estimates based on their own datasets. Workers send their estimates through a multipath fading multiple access channel with orthogonal frequency division multiplexing to mitigate the frequency selectivity of the channel. We assume that there is no channel state information (CSI) at the workers, and the parameter server (PS) employs multiple antennas to align the received signals. To reduce the power consumption and the hardware costs, we employ complex-valued low-resolution digital-to-analog converters (DACs) and analog-to-digital converters (ADCs), at the transmitter and the receiver sides, respectively, and study the effects of practical low-cost DACs and ADCs on the learning performance. Our theoretical analysis shows that the impairments caused by low-resolution DACs and ADCs, including those of one-bit DACs and ADCs, do not prevent the convergence of the federated learning algorithms, and the multipath channel effects vanish when a sufficient number of antennas are used at the PS. We also validate our theoretical results via simulations, and demonstrate that using low-resolution, even one-bit, DACs and ADCs causes only a slight decrease in the learning accuracy.