Loading…
Thumbnail Image

Distributed function approximation over noisy channels

Frey, Matthias

FG Netzwerk-Informationstheorie

Over-the-Air (OTA) computation is the problem of computing functions of distributed data over a wireless channel without transmitting the entirety of the data to a central point. By avoiding such costly transmissions, OTA computation schemes can achieve a better-than-linear (depending on the function, often logarithmic or even constant) scaling of the communication cost as the number of transmitters grows. Among the most common functions computed OTA are linear functions such as weighted sums. In this work, we propose and analyze a method for the approximation of functions of distributed arguments over noisy channels. This method can be used as an analog OTA computation scheme for a class of functions that contains linear functions as well as some nonlinear functions such as p-norms of vectors. We prove error bound guarantees that are valid for fast-fading channels and all distributions of fading and noise contained in the class of sub-Gaussian distributions. This class includes Gaussian distributions, but also many other practically relevant cases such as Class A Middleton noise and fading with dominant line-of-sight components. In addition, there can be correlations in the fading and noise so that the presented results also apply to, for example, block fading channels and channels with bursty interference. We do not rely on any stochastic characterization of the distributed arguments of the OTA computed function; in particular, there is no assumption that these arguments are drawn from identical or independent probability distributions. Our analysis relies on tools from high-dimensional statistics which we adapt so that they are applicable to the scenario at hand. The resulting error guarantees are nonasymptotic and therefore provide error bounds that are valid for a finite number of channel uses. OTA computation has a huge potential for reducing communication cost in applications such as Machine Learning (ML)-based distributed anomaly detection in large wireless sensor networks. We show this potential with two examples of how our OTA computation scheme can be used to vastly increase the efficiency of Vertical Federated Learning (VFL) over a wireless channel. We also illustrate the efficiency gain with numerical simulations for a few example cases. Then, we move on to propose a new method to protect OTA computation schemes against passive eavesdropping. Our method uses a friendly jammer whose signal is – contrary to common intuition – stronger at the legitimate receiver than it is at the eavesdropper. It works for a large class of analog OTA computation schemes and we give details on the special case of computing an arithmetic average over an Additive White Gaussian Noise (AWGN) channel. The derived secrecy guarantee translates to a lower bound on the eavesdropper’s mean square error while the question of how to provide operationally more significant guarantees such as semantic security remains open for future work. As key ingredients in proving the security guarantees, we propose and prove generalizations of known results on channel resolvability and coding for compound channels for the case of continuous channel input and output alphabets.
Funktionsberechnung im Funkkanal ist eine Methode, Funktionen verteilter Daten ohne eine vollständige Übertragung der Daten zu einem zentralen Punkt zu berechnen. Indem solche Übertragungen vermieden werden, kann erreicht werden, dass der Ressourcenverbrauch weniger schnell als linear mit der Anzahl der Sender wächst. Abhängig von der zu berechnenden Funktion kann dieses Wachstum dann in vielen Fällen logarithmisch oder sogar konstant sein (d.h. die zur Funktionsberechnung nötigen Kanalressourcen wachsen überhaupt nicht, wenn die Anzahl der Sender wächst). Zu den am häufigsten im Funkkanal berechneten Funktionen gehören lineare Funktionen wie z.B. gewichtete Summen. In der vorliegenden Arbeit führen wir eine Methode zur verteilten Approximation von Funktionen in verrauschten Kanälen ein. Diese Methode kann als Verfahren zur analogen Funktionsberechnung im Funkkanal genutzt werden. Sie ist auf eine Klasse von Funktionen anwendbar, die zum einen alle linearen Funktionen, zum anderen aber auch einige nichtlineare Funktionen wie die p-Norm von Vektoren enthält. Wir zeigen Fehlerschranken für unser Verfahren, die in Kanälen mit Fast Fading gelten, wobei sowohl die Verteilung des Fadings als auch die des Rauschens zur Klasse der sub-Gauß’schen Wahrscheinlichkeitsverteilungen gehören müssen. Diese Klasse enthält nicht nur alle Normalverteilungen, sondern auch viele andere in der Praxis relevanten Verteilungen wie z.B. Class-A-Rauschen nach Middleton und Fadingverteilungen mit einer dominanten Sichtkomponente. Zudem sind unsere Fehlerschranken auch dann noch gültig, wenn es Korrelationen in der Verteilung des Fadings und/oder Rauschens gibt, sodass unsere Ergebnisse beispielsweise auch auf Kanäle mit Blockfading oder gebündelt auftretender Interferenz anwendbar sind. Dabei verwenden wir keinerlei stochastische Charakterisierung der Argumente der über den Funkkanal zu berechnenden Funktion. Dies bedeutet insbesondere, dass keine Annahme über identische Verteilung oder Unabhängigkeit dieser Argumente nötig ist. Unsere Analyse baut auf Werkzeugen aus der hochdimensionalen Statistik auf, die wir derart anpassen, dass sie im vorliegenden Szenario anwendbar sind. Die sich daraus ergebenden Fehlerschranken sind nichtasymptotisch, d.h. sie sind für jede beliebige (endliche) Anzahl von Kanalnutzungen gültig. Funktionsberechnung im Funkkanal bietet ein riesiges Potenzial, in Anwendungen wie z.B. der auf maschinellem Lernen basierenden Anomaliedetektion in großen Sensornetzen die zur Kommunikation nötigen Ressourcen drastisch zu reduzieren. Wir veranschaulichen dieses Potenzial, indem wir zwei Beispiele ausführen, die zeigen, wie unsere Methoden zur Funktionsberechnung im Funkkanal die Effizienz von vertikalem föderierten Lernen enorm steigern können. Wir illustrieren diesen Effizienzgewinn außerdem für einige ausgesuchte Spezialfälle anhand numerischer Simulationen. Anschließend führen wir ein neues Verfahren ein, um Funktionsberechnungen im Funkkanal gegen passive Lauscher zu schützen. Unsere Methode basiert auf der Kooperation der legitimen Kommunikationspartner mit einem Jammer, dessen Signal – entgegen den normalerweise in diesem Zusammenhang gemachten Annahmen – beim legitimen Empfänger in einer größeren Signalstärke ankommt als beim Lauscher. Sie funktioniert für eine große Klasse von Verfahren zur Funktionsberechnung über den Funkkanal, und wir führen den Spezialfall der Berechnung eines arithmetischen Mittelwerts über einen Kanal mit additivem weißen normalverteilten Rauschen detailliert aus. Dabei erhalten wir eine Sicher- heitsgarantie, die den durchschnittlichen quadratischen Fehler des Lauschers nach unten begrenzt. Die Frage, wie stärkere Sicherheitsgarantien (z.B. semantische Sicherheit) gegeben werden können, bleibt dabei für zukünftige Forschungsarbeiten offen. Die wichtigsten informationstheoretischen Zutaten für den Beweis der Sicherheitsgarantie sind Verallgemeinerungen bekannter Ergebnisse zur Resolvability von Kanälen und zur Kommunikation über Compound-Kanäle für den Fall kontinulierlicher Ein- und Ausgabealphabete, die wir im Rahmen dieser Arbeit ebenfalls beweisen.