First-Order Algorithms for Communication Efficient Distributed Learning

• Innovations in numerical optimization, statistics and high performance computing have enabled tremendous advances in machine learning algorithms, fuelling applications from natural language processing to autonomous driving.To deal with increasing data volumes, and to keep the training times of increasingly complex machine learning models reasonable, modern optimization algorithms distribute both data and computations over a large number of machines. However, these algorithms face challenges, from hardware and data heterogeneity (as different machines have different processors and data) to privacy and security issues (where data can be extracted from the transmitted parameters).Among these challenges, communication overhead constitutes a major performance bottleneck of the algorithms.Communicating millions of problem parameters between machines has been reported to consumeup to 80% of the training time. To alleviate the communication bottleneck, we develop theory and strategies in this thesis to design communication-efficient optimization algorithms. In the first part, we provide unified analysis frameworks for first-order algorithms using direct or error-compensated compression. We first identify key characteristics of the compression errors induced by many of the most popular compression strategies in the literature. We then perform a unified analysis of the convergence properties of first-order algorithms for general families of deterministic and stochastic gradient compression algorithms.Our results give explicit expressions for how compression accuracy and the amount of asynchrony affect the step-sizes and guaranteed convergence times. We next turn our attention to error-compensated compression algorithms.We develop theoretical explanations for why error-compensated compression algorithms attain solutions with arbitrarily higher accuracy than direct compression algorithms.Our results provide strong convergence guarantees of error-compensated compression algorithms for  distributed and federated learning problems. In the second part, we provide flexible tuning frameworks to optimize convergence performance of compression algorithms for a  variety of system architectures. We start by analyzing data-dependent complexity that explains why direct compression algorithms are more communication-efficient than full-precision algorithms in practice. This complexity leads to automatic tuning strategies that enable popular compression algorithms on different communication networks to maximize both the convergence progress towards the solution and the communication efficiency. We then turn our attention to diminishing step-size schedules to maximize the convergence speed of  the algorithms using noisy gradients.Our analysis framework is based on two classes of systems that characterize the impact of the step-sizes on the speed of noisy gradient algorithms.Our results show that such step-size schedules enable these algorithms to enjoy the optimal rate. Applications of the algorithms in the thesis to central machine learning problems on benchmark data validate our theoretical results.

• Enorma framsteg inom maskininlärningsalgoritmer förbättrar centrala tillämpningar av artificiell intelligens, från naturlig språkbehandling till autonom körning, tack vare innovation inom numerisk optimering och högpresterande datorsystem. Dessa optimeringsbaserade algoritmer använder miljarder maskiner för att samordnat lösa storskaliga problem inom önskvärd träningstid. Emellertid utgör de utmaningar, från hårdvaru- och dataheterogenitet (eftersom olika enheter har olika datorkraft och data) till integritets- och säkerhetsproblematik (där data kan extraheras från de överförda parametrarna). Bland dessa utmaningar utgör kommunikationsoverhead en stor del av prestandaflaskhalsen för algoritmerna. Att kommunicera miljoner problemparametrar mellan maskiner har rapporterats förbruka upp till 80% av träningstiden. För att lätta kommunikationsflaskhalsen utvecklar vi teori och strategier i denna avhandling för att designa kommunikationseffektiva optimeringsalgoritmer. I den första delen tillhandahåller vi enhetliga analysramverk för att analysera prestanda för första ordningens optimeringsalgoritmer med direkt eller felkompenserad komprimering, på en enda maskin och över flera maskiner. Vi skisserar först definitioner av kompressionstekniker som täcker in många kompressorer av praktiskt intresse. Sedan analyserar vi konvergens av första ordningens algoritmer som använder antingen deterministisk eller stokastisk kompression. Våra resultat påvisar den explicita effekten av kompressionsnoggrannhet och asynkrona fördröjningar på steglängd, konvergenshastighet och lösningsnoggrannhet för direktkomprimeringsalgoritmer. Vi vänder sedan vår uppmärksamhet till felkompenserade komprimeringsalgoritmer. Vi utvecklar teoretiska förklaringar till varför felkompenserade komprimeringsalgoritmer uppnår lösningar med godtyckligt högre noggrannhet än direkta komprimeringsalgoritmer. Våra resultat visar starka konvergensgarantier för felkompenserade komprimeringsalgoritmer för distribuerade och federerade inlärningsproblem. I den andra delen tillhandahåller vi flexibla inställningsramverk för att optimera konvergensprestanda för komprimeringsalgoritmer för en mängd olika systemarkitekturer. Vi börjar med att analysera databeroende komplexitet som förklarar varför direktkomprimeringsalgoritmer är mer kommunikationseffektiva än fullprecisionsalgoritmer i praktiken. Denna komplexitet leder till automatiska inställningsstrategier som möjliggör populära komprimeringsalgoritmer på olika kommunikationsnätverk för att maximera både framskridandet av konvergensen mot lösningen och kommunikationseffektiviteten. Vi riktar sedan vår uppmärksamhet mot steglängdsminskningsscheman för att maximera konvergenshastigheten för de algoritmer som använder stokastiska gradienter. Vår analysram baseras på två klasser av system som kännetecknar steglängdernas inverkan på hastigheten av stokastiska gradientalgoritmer. Våra resultat visar att sådana steglängdsscheman gör det möjligt för dessa algoritmer att åtnjuta den optimala hastigheten. Simuleringar av algoritmer i denna avhandling på verkliga problem med referensdatamängder validerar våra teoretiska resultat.

Ämnesord

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

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

Nyckelord

Communication efficient learning

Optimization algorithms

Quantization

Error compensation

First-order algorithms

Stochastic gradient descent

Electrical Engineering

Elektro- och systemteknik

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)