In recent years, edge computing has become an increasingly popular computing paradigm to enable real-time data processing and mobile intelligence. Edge computing allows computing at the edge of the network, where data is generated and distributed at the nearby edge servers to reduce the data access latency and improve data processing efficiency. In addition, with the advance of Artificial Intelligence of Things (AIoT), not only millions of data are generated from daily smart devices, such as smart light bulbs, smart cameras, and various sensors, but also a large number of parameters of complex machine learning models have to be trained and exchanged by these AIoT devices. Classical cloud-based platforms have difficulty communicating and processing these data/models effectively with sufficient privacy and security protection. Due to the heterogeneity of edge elements including edge servers, mobile users, data resources, and computing tasks, the key challenge is how to effectively manage resources (e.g. data, services) and schedule tasks (e.g. ML/FL tasks) in the edge clouds to meet the QoS of mobile users or maximize the platform's utility. To that end, this dissertation studies joint resource management and task scheduling for mobile edge computing. The key contributions of the dissertation are two-fold. Firstly, we study the data placement problem in edge computing and propose a popularity-based method as well as several load-balancing strategies to effectively place data in the edge network. We further investigate a joint resource placement and task dispatching problem and formulate it as an optimization problem. We propose a two-stage optimization method and a reinforcement learning (RL) method to maximize the total utilities of all tasks. Secondly, we focus on a specific computing task, i.e., federated learning (FL), and study the joint participant selection and learning scheduling problem for multi-model federated edge learning. We formulate a joint optimization problem and propose several multi-stage optimization algorithms to solve the problem. To further improve the FL performance, we leverage the power of the quantum computing (QC) technique and propose a hybrid quantum-classical Benders' decomposition (HQCBD) algorithm as well as a multiple-cuts version to accelerate the convergence speed of the HQCBD algorithm. We show that the proposed algorithms can achieve the consistent optimal value compared with the classical Benders' decomposition running in the classical CPU computer, but with fewer convergence iterations. / Computer and Information Science

Federated learning is a framework in machine learning that allows for training a model while maintaining data privacy. Moreover, it allows clients with their own data to collaborate in order to build a stronger, shared model. Federated learning is of particular interest to healthcare data, since it is of the utmost importance to respect patient privacy while still building useful diagnostic tools. However, healthcare data can be complicated — data format might differ across providers, leading to unexpected inputs and incompatibility between different providers. For example, electrocardiograms might differ in sampling rate or number of leads used, meaning that a classifier trained at one hospital might be useless to another. We propose using autoencoders to address this problem, transforming important information contained in electrocardiograms to a uniform input, where federated learning can then be used to train a strong classifier for multiple healthcare providers. Furthermore, we propose using statistically-guided hyperparameter tuning to ensure fast convergence of the model.

<p><br></p><p>How to set privacy parameters is a crucial problem for the consistent application of DP in practice. The current privacy parameters do not provide direct suggestions for this problem. On the other hand, different databases may have varying degrees of information leakage, allowing attackers to enhance their attacks with the available information. This dissertation provides an additional interpretation of the current DP notions by introducing a framework that directly considers the worst-case average failure probability of attackers under different levels of knowledge. </p><p><br></p><p>To achieve this, we introduce a novel measure of attacker knowledge and establish a dual relationship between (type I error, type II error) and (prior, average failure probability). By leveraging this framework, we propose an interpretable paradigm to consistently set privacy parameters on different databases with varying levels of leaked information. </p><p><br></p><p>Furthermore, we characterize the minimax limit of private parameter estimation, driven by $1/(n(1-2p))^2+1/n$, where $p$ represents the worst-case probability risk and $n$ is the number of data points. This characterization is more interpretable than the current lower bound $\min{1/(n\epsilon^2),1/(n\delta^2)}+1/n$ on $(\epsilon,\delta)$-DP. Additionally, we identify the phase transition of private parameter estimation based on this limit and provide suggestions for protocol designs to achieve optimal private estimations. </p><p><br></p><p>Last, we consider a federated learning setting where the data are stored in a distributed manner and privacy-preserving interactions are required. We extend the proposed interpretation to federated learning, considering two scenarios: protecting against privacy breaches against local nodes and protecting privacy breaches against the center. Specifically, we consider a non-convex sparse federated parameter estimation problem and apply it to the generalized linear models. We tackle two challenges in this setting. Firstly, we encounter the issue of initialization due to the privacy requirements that limit the number of queries to the database. Secondly, we overcome the heterogeneity in the distribution among local nodes to identify low-dimensional structures.</p>

<p>  </p> <p>Federated learning (FL) has emerged as a promising approach for training machine learning models on distributed data while ensuring privacy preservation and data locality. However, one key challenge in FL optimization is the lack of high probability guarantees, which can undermine the trustworthiness of FL solutions. To address this critical issue, we introduce Federated Averaging with post-optimization (FedAvg-PO) method, a modification to the Federated Averaging (FedAvg) algorithm. The proposed algorithm applies a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the FedAvg method. These modifications allow to significantly improve the large-deviation properties of FedAvg which improve the reliability and robustness of the optimization process. The novel complexity analysis shows that FedAvg-PO can compute accurate and statistically guaranteed solutions in the federated learning context. Our result further relaxes the restrictive assumptions in FL theory by developing new technical tools which may be of independent interest. The insights provided by the computational requirements analysis contribute to the understanding of the scalability and efficiency of the algorithm, guiding its practical implementation.</p>

L'apprentissage fédéré est un paradigme émergent qui permet à un grand nombre de clients disposant de données hétérogènes de coordonner l'apprentissage d'un modèle global unifié sans avoir besoin de partager les données entre eux ou avec un stockage central. Il améliore la confidentialité des données, car celles-ci sont décentralisées et ne quittent pas les dispositifs clients. Les algorithmes standard d'apprentissage fédéré impliquent le calcul de la moyenne des paramètres du modèle ou des mises à jour du gradient pour approcher le modèle global au niveau du serveur. Cependant, dans des environnements hétérogènes, le calcul de la moyenne peut entraîner une perte d'information et conduire à une mauvaise généralisation en raison du biais induit par les gradients dominants des clients. Nous supposons que pour mieux généraliser sur des ensembles de données non-i.i.d., les algorithmes devraient se concentrer sur l'apprentissage du mécanisme invariant qui est constant tout en ignorant les mécanismes parasites qui diffèrent entre les clients. Inspirés par des travaux récents dans la littérature sur la distribution des données, nous proposons une approche de calcul de la moyenne masquée par le gradient pour FL comme alternative au calcul de la moyenne standard des mises à jour des clients. mises à jour des clients. Cette technique d'agrégation des mises à jour des clients peut être adaptée en tant que remplacement dans la plupart des algorithmes fédérés existants. Nous réalisons des expériences approfondies avec l'approche de masquage du gradient sur plusieurs algorithmes FL avec distribution, monde réel et hors distribution (en tant qu'algorithme fédéré). Hors distribution (comme le pire des scénarios) avec des déséquilibres quantitatifs. déséquilibres quantitatifs et montrent qu'elle apporte des améliorations constantes, en particulier dans le cas de clients hétérogènes. clients hétérogènes. Des garanties théoriques viennent étayer l'algorithme proposé. / Federated learning is an emerging paradigm that permits a large number of clients with heterogeneous data to coordinate learning of a unified global model without the need to share data amongst each other or to a central storage. In enhances data privacy as data is decentralized and do not leave the client devices. Standard federated learning algorithms involve averaging of model parameters or gradient updates to approximate the global model at the server. However, in heterogeneous settings averaging can result in information loss and lead to poor generalization due to the bias induced by dominant client gradients. We hypothesize that to generalize better across non-i.i.d datasets, the algorithms should focus on learning the invariant mechanism that is constant while ignoring spurious mechanisms that differ across clients. Inspired from recent works in the Out-of-Distribution literature, we propose a gradient masked averaging approach for FL as an alternative to the standard averaging of client updates. This client update aggregation technique can be adapted as a drop-in replacement in most existing federated algorithms. We perform extensive experiments with gradient masked approach on multiple FL algorithms with in-distribution, real-world, and out-of-distribution (as the worst case scenario) test datasets along with quantity imbalances and show that it provides consistent improvements, particularly in the case of heterogeneous clients. Theoretical guarantees further supports the proposed algorithm.

No description available.

With increasing amounts of data coming fromconnecting progressively more devices, new machine learningmodels have risen. For wireless networks the idea of using adistributed approach to machine learning has gained increasingpopularity, where all nodes in the network participate in creatinga global machine learning model by training with the localdata stored at each node, an example of this approach is calledfederated learning. However, traditional communication protocolshave been proven inefficient. This opens up opportunities todesign new machine-learning specific communication schemes.The concept ofOver-the-air computationis built on the fact thata wireless communication channel can naturally compute somelinear functions, for instance the sum. If all nodes in a networktransmits simultaneously to a server, the signals are aggregatedbefore reaching the server. / I takt med denökande datamängden frånallt fler uppkopplade enheter har nya modeller för mask-ininlärning dykt upp. För trådlösa nätverk har idén att appliceradecentraliserade maskininlärnings modellerökat i popularitet,där alla noder i nätverket bidrar till en global maskininlärningsmodell genom att träna på den data som finns lokalt på varjenod. Ett exempel på en sådan metodärFederated Learning.Traditionella metoder för kommunikation har visat sig varaineffektiva vilket öppnar upp möjligheten för att designa nyamaskininlärningsspecifika kommunikationsscheman. Konceptetover-the-air computationutnyttjar det faktum att en trådlöskommunikationskanal naturligt kan beräkna vissa funktioner,som exempelvis en summa. Om alla noder i nätverket sändertill en server samtidigt aggregeras signalerna genom interferensinnan de når servern. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

With the emerging Internet of Things (IoT) paradigm, more than a billion sensing devices will be collecting an unprecedented amount of data. Simultaneously, the field of data analytics is being revolutionized by modern machine learning (ML) techniques that enable sophisticated processing of massive datasets. Many researchers are envisioning a combination of these two technologies to support exciting applications such as environmental monitoring, Industry 4.0, and vehicular communications. However, traditional wireless communication protocols are inefficient in supporting distributed ML services, where data and computations are distributed over wireless networks. This motivates the need for new wireless communication methods. One such method, over-the-air computation (AirComp), promises to communicate with massive gains in terms of energy, latency, and spectrum efficiency compared to traditional methods. The expected efficiency of AirComp is due to the complete spectrum sharing for all participating devices. Unlike in traditional physical-layer communications, where interference is avoided by allocating orthogonal communication channels, AirComp promotes interference to compute a function of the individually transmitted messages. However, AirComp can not reconstruct functions perfectly but introduces errors in the process, which harms the convergence rate and region of optimality of ML algorithms. The main objective of this thesis is to develop methods that reduce these errors and analyze their effects on ML performance. In the first part of this thesis, we consider the general problem of designing wireless methods for ML applications. In particular, we present an extensive survey which divides the field into two broad categories, digital communications and analog over-the-air-computation. Digital communications refers to orthogonal communication schemes that are optimized for ML metrics, such as classification accuracy, privacy, and data-importance, rather than traditional communication metrics such as fairness, data rate, and reliability. Analog over-the-air-computation refers to the AirComp method and its application to distributed ML, where communication-efficiency, function estimation, and privacy are key concerns. In the second part of this thesis, we focus on the analog over-the-air computation problem. We consider a network setup with multiple devices and a server that can be reached via a single hop, where the wireless channel is modeled as a multiple-access channel with fading and additive noise. Over such a channel, the AirComp function estimate is associated with two types of error: 1) misalignment errors caused by channel fading and 2) noise-induced errors caused by the additive noise. To mitigate these errors, we propose AirComp with retransmissions and develop the optimal power control scheme for such a system. Furthermore, we use optimization theory to derive bounds on the convergence of an AirComp-supported ML system that reveal a relationship between the number of retransmissions and loss of the ML model. Finally, with numerical results we show that retransmissions can significantly improve ML performance, especially for low-SNR scenarios. / Med Internet of Things (IoT)-paradigmen, kommer över en miljard sensorenheter att samla en mängd data som saknar motstycke. Samtidigt har dataanalys revolutionerats av moderna maskininlärningstekniker (ML) som möjliggör avancerad behandling av massiva dataset. Många forskare föreställer sig en kombination av dessa två two teknologier för att möjliggöra spännande applikationer som miljöövervakning, Industri 4.0, och fordonskommunikation. Tyvärr är traditionella kommunikationsprotokoll ineffektiva när det kommer till att stödja distribuerad maskininlärning, där data och beräkningar är utspridda över trådlösa nätverk. Detta motiverar behovet av nya trådlösa kommunikationsprotokoll. Ett protokoll, over-the-air computation (AirComp), lovar att kommunicera med enorma fördelar när det kommer till energieffektivitet, latens, and spektrumeffektivitet jämfört med traditionella protkoll. AirComps effektivitet beror på den fullständiga spektrumdelningen mellan alla medverkande enheter. Till skillnad från traditionell ortogonal kommunikation, där interferens undviks genom att allokera ortogonala radioresurser, så uppmuntrar AirComp interferens och nyttjar den för att räkna ut en funktion av de kommunicerade meddelanderna. Dock kan inte AirComp rekonstruera funktioner perfekt, utan introducerar fel i processen vilket försämrar konvergensen av ML-algoritmer. Det huvudsakliga målet med den här avhandlingen är att utveckla metoder som minskar dessa fel och att analysera de effekter felen har på prestandan av distribuerade ML-algoritmer. I den första delen av avhandlingen behandlar vi det allmänna problemet med att designa trådlösa nätverksprotokoll för att stödja ML. Specifikt så presenterar vi en utförlig kartläggning som delar upp fältet i två kategorier, digital kommunikation och analog AirComp. Digital kommunikation syftar på ortogonala kommunikationsprotokoll som är optimerade för ML-måttstockar, t.ex. klassifikationskapabilitet, integritet, och data-vikt (data-importance), snarare än traditionella kommunikationsmål såsom jämlikhet, datahastighet, och tillförlitlighet. Analog AirComp syftar till AirComps applicering till distribuerad ML, där kommunikationseffektivitet, funktionsestimering, och integritet är viktiga måttstockar. I den andra delen av avhandlingen fokuserar vi på det analoga AirComp-problemet. Vi beaktar ett nätverk med flera enheter och en server som kan nås via en länk, där den trådlösa kanalen modelleras som en multiple-access kanal (MAC) med fädning och additivt brus. Över en sådan kanal så associeras AirComps funktionsestimat med två sorters fel: 1) felinställningsfel orsakade av fädning och 2) brusinducerade fel orsakade av det additiva bruset. För att mildra felen föreslår vi AirComp med återsändning och utvecklar den optimala "power control"-algoritmen för ett sådant system. Dessutom använder vi optimeringsteori för att härleda begränsningar på konvergensen av ett AirCompsystem för distribuerad ML som tydliggör ett förhållande mellan antalet återsändningar och förlustfunktionen för ML-modellen. Slutligen visar vi att återsändningar kan signifikant förbättra ML-prestanda genom numeriska resultat, särskilt när signal-till-brus ration är låg. / <p>QC 20220909</p>

This thesis examines resource allocation for Federated Learning in wireless networks. In Federated learning a server and a number of users exchange neural network parameters during training. This thesis aims to create a realistic simulation of a Federated Learning process by creating a channel model and using compression when channel capacity is insufficient. In the thesis we learn that Federated learning can handle high ratios of sparsification compression. We will also investigate how the choice of users and scheduling schemes affect the convergence speed and accuracy of the training process. This thesis will conclude that the choice of scheduling schemes will depend on the distributed data distribution.

<p dir="ltr">Decentralized learning is the key to training deep neural networks (DNNs) over large distributed datasets generated at different devices and locations, without the need for a central server. They enable next-generation applications that require DNNs to interact and learn from their environment continuously. The practical implementation of decentralized algorithms brings about its unique set of challenges. In particular, these algorithms should be (a) compatible with time-varying graph structures, (b) compute and communication efficient, and (c) resilient to heterogeneous data distributions. The objective of this thesis is to enable efficient decentralized learning in deep neural networks addressing the abovementioned challenges. Towards this, firstly a communication-efficient decentralized algorithm (Sparse-Push) that supports directed and time-varying graphs with error-compensated communication compression is proposed. Second, a low-precision decentralized training that aims to reduce memory requirements and computational complexity is proposed. Here, we design ”Range-EvoNorm” as the normalization activation layer which is better suited for low-precision decentralized training. Finally, addressing the problem of data heterogeneity, three impactful advancements namely Neighborhood Gradient Mean (NGM), Global Update Tracking (GUT), and Cross-feature Contrastive Loss (CCL) are proposed. NGM utilizes extra communication rounds to obtain cross-agent gradient information whereas GUT tracks global update information with no communication overhead, improving the performance on heterogeneous data. CCL explores an orthogonal direction of using a data-free knowledge distillation approach to handle heterogeneous data in decentralized setups. All the algorithms are evaluated on computer vision tasks using standard image-classification datasets. We conclude this dissertation by presenting a summary of the proposed decentralized methods and their trade-offs for heterogeneous data distributions. Overall, the methods proposed in this thesis address the critical limitations of training deep neural networks in a decentralized setup and advance the state-of-the-art in this domain.</p>