Reliable and Efficient Distributed Machine Learning

• With the ever-increasing penetration and proliferation of various smart Internet of Things (IoT) applications, machine learning (ML) is envisioned to be a key technique for big-data-driven modelling and analysis. Since massive data generated from these IoT devices are commonly collected and stored in a distributed manner, ML at the networks, e.g., distributed machine learning (DML), has been a promising emerging paradigm, especially for large-scale model training. In this thesis, we explore the optimization and design of DML algorithms under different network conditions. Our main research with regards to DML can be sorted into the following four aspects/papers as detailed below.In the first part of the thesis, we explore fully-decentralized ML by utilizing alternating direction method of multipliers (ADMM). Specifically, to address the two main critical challenges in DML systems, i.e., communication bottleneck and stragglers (nodes/devices with slow responses), an error-control-coding-based stochastic incremental ADMM (csI-ADMM) is proposed. Given an appropriate mini-batch size, it is proved that the proposed csI-ADMM method has a $O( 1/\sqrt{k})$) convergence rate and $O(1/{\mu ^2})$ communication cost, where $k$ denotes the number of iterations and $\mu$ is the target accuracy.  In addition, tradeoff between the convergence rate and the number of stragglers, as well as the relationship between mini-batch size and number of stragglers, are both theoretically and experimentally analyzed. In the second part of the thesis, we investigate the asynchronous approach for fully-decentralized federated learning (FL). Specifically, an asynchronous parallel incremental block-coordinate descent (API-BCD) algorithm is proposed, where multiple nodes/devices are active in an asynchronous fashion to accelerate the convergence speed. The solution convergence of API-BCD is theoretically proved and simulation results demonstrate its superior performance in terms of both running speed and communication costs compared with state-of-the-art algorithms.The third part of the thesis is devoted to the study of jointly optimizing communication efficiency and wireless resources for FL over wireless networks. Accordingly, an overall optimization problem is formulated, which is divided into two sub-problems, i.e., the client scheduling problem and the resource allocation problem for tractability. More specifically, to reduce the communication costs, a communication-efficient client scheduling policy is proposed by limiting communication exchanges and reusing stale local models. To optimize resource allocation at each communication round of FL training, an optimal solution based on linear search method is derived. The proposed communication-efficient FL (CEFL) algorithm is evaluated both analytically and by simulation. The final part of the thesis is a case study of implementing FL in low Earth orbit (LEO) based satellite communication networks. We investigate four possible architectures of combining ML in LEO-based computing networks. The learning performance of the proposed strategies is evaluated by simulation and results validate that FL-based computing networks can significantly reduce communication overheads and latency.

• Med ökat genomslag och spridning av olika smarta Internet of Things (IoT) applikationer, förväntas maskininlärning (ML) bli en nyckelteknik för modellering ochanalys av stora data mängder. Eftersom data från dessa IoT enheter vanligtvis sparaslokalt har ML på nätverksnivå, t.ex. distribuerad maskininlärning (DML), blivit en lovande ny paradigm, särskilt för storskalig modellträning. I denna avhandling utforskarvi optimeringen och designen av DML algoritmer under olika förutsättningar i nätverken. Vår huvudsakliga forskning i hänseende till DML är fördelad i fyra papper,beskrivna enligt nedan.I första delen av denna avhandling tittar vi på fullt decentraliserad ML genom nyttjandet av älternating direction method of multipliers"(ADMM). Mer specifikt föreslårvi en "error-control-coding-baserad stochastic incremental ADMM"(csl-ADMM) föratt tackla de två mest kritiska utmaningarna i DML system, dvs. flaskhalsar i kommunikation och eftersläpare (noder/enheter med långsam respons). Givet en lämpligmini-batch storlek visar vi att den föreslagna csl-ADMM metoden konvergerar medO(1/√k) med en kommunikationskostnad på O(1/µ2), där k är antalet iterationer ochv är sökt noggrannhet. Vi ger även en teoretisk och experimentell analys av sambandetmellan konvergenshastighet och antalet eftersläpare samt sambandet mellan mini-batchstorlek och antalet eftersläpare.I avhandlingens andra del undersöker vi den asynkrona hanteringen av fullt decentraliserad kollaborativ inlärning (FL, eng. Federated Learning). Specifikt föreslår vi enalgoritm för äsynchronous parallel incremental block-coordinate descent"(API-BCD),där flera enheter/noder är asynkront aktiva för att öka konvergens hastigheten. Vi gerteoretiskt bevis för API-BCD lösningens konvergens samt visar simuleringar som demonstrerar dess överlägsna prestanda i termer av både hastighet och kommunikationskostnader jämfört med state-of-the-art algoritmer.Avhandlingens tredje del är en studie i att simultant optimera kommunikations effektivitet och hanteringen av trådlösa resurser för FL över trådlösa nätverk. Ett övergripande optimeringsproblem formuleras, som delas upp i två delproblem, schemaläggning av klienter och ett resursallokerings problem. För att reducera kommunikationskostnaderna, föreslås en effektiv kommunikations policy för schemaläggning av klienter som begränsar kommunikation och återanvändandet av lokala modeller som blivitmindre relevanta med tiden. För att optimera resurs allokeringen i varje kommunikations runda av FL träning, härleds en optimal lösning baserad på en linjär sök metod.Den föreslagna kommunikationseffektiva FL (CEFL, eng. Communication EfficientFL) algoritmen utvärderas både analytiskt och med simulering.Den sista delen av avhandlingen är en fallstudie där FL implementeras i satellitkommunikationsnätverk i låg omloppsbana (LEO, eng. Low Earh Orbit). Vi undersökerfyra möjliga arkitekturer för kombinering av ML i satellitburna datornätverk. Prestandan av de föreslagna strategierna utvärderas via simuleringar och resultaten visar attFL-baserade datornätverk kan anmärkningsvärt minska kommunikationsoverhead ochlatens.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering (hsv//eng)

Nyckelord

Distributed machine learning

federated learning

communication efficiency

decentralized optimization

Electrical Engineering

Elektro- och systemteknik

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)