Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Asynchronous First-Order Algorithms for Large-Scale Optimization: Analysis and Implementation
KTH, School of Electrical Engineering and Computer Science (EECS), Automatic Control.ORCID iD: 0000-0003-1725-2901
2019 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Developments in communication and data storage technologies have made large-scale data collection more accessible than ever. The transformation of this data into insight or decisions typically involves solving numerical optimization problems. As the data volumes increase, the optimization problems grow so large that they can no longer be solved on a single computer. This has created a strong interest in developing optimization algorithms that can be executed efficiently on multiple computing nodes in parallel. One way to achieve efficiency in parallel computations is to allow for asynchrony among nodes, which corresponds to making the nodes spend less time coordinating with each other and more time computing, possibly based on delayed information.  However, asynchrony in optimization algorithms runs the risk of otherwise convergent algorithms divergent, and convergence analysis of asynchronous algorithms is generally harder. In the thesis, we develop theory and tools to help understand and implement asynchronous optimization algorithms under time-varying, bounded information delay.

In the first part, we analyze the convergence of different asynchronous optimization algorithms. We first propose a new approach for minimizing the average of a large number of smooth component functions. The algorithm uses delayed partial gradient information, and it covers delayed incremental gradient and delayed coordinate descent algorithms as special cases. We show that when the total loss function is strongly convex and the component functions have Lipschitz-continuous gradients, the algorithm has a linear convergence rate. The step size of the algorithm can be selected without knowing the bound on the delay, and still, guarantees convergence to within a predefined level of suboptimality. Then, we analyze two different variants of incremental gradient descent algorithms for regularized optimization problems.  In the first variant, asynchronous mini-batching, we consider solving regularized stochastic optimization problems with smooth loss functions. We show that the algorithm with time-varying step sizes achieves the best-known convergence rates under synchronous operation when (i) the feasible set is compact or (ii) the regularization function is strongly convex, and the feasible set is closed and convex. This means that the delays have an asymptotically negligible effect on the convergence, and we can expect speedups when using asynchronous computations. In the second variant, proximal incremental aggregated gradient, we show that when the objective function is strongly convex, the algorithm with a constant step size that depends on the maximum delay bound and the problem parameters converges globally linearly to the true optimum.

In the second part, we first present POLO, an open-source C++ library that focuses on algorithm development. We use the policy-based design approach to decompose the proximal gradient algorithm family into its essential policies. This helps us handle combinatorially increasing design choices with linearly many tools, and generates highly efficient code with small footprint.  Together with its sister library in Julia, POLO.jl, our software framework helps optimization and machine-learning researchers to quickly prototype their ideas, benchmark them against the state-of-the-art, and ultimately deploy the algorithms on different computing platforms in just a few lines of code. Then, using the utilities of our software framework, we build a new, ``serverless'' executor for parallel Alternating Direction Method of Multipliers (ADMM) iterations. We use Amazon Web Services' Lambda functions as the computing nodes, and we observe speedups up to 256 workers and efficiencies above 70% up to 64 workers. These preliminary results suggest that serverless runtimes, together with their availability and elasticity, are promising candidates for scaling the performance of distributed optimization algorithms.

Abstract [sv]

Den snabba utvecklingen inom kommunikations- och datalagringsteknik har gjort storskalig datainsamling mer tillgänglig än någonsin. För att omvandla denna data till insikt eller beslut löser man ofta någon form av numeriskt optimeringsproblem. När datavolymerna ökar blir dessa optimeringsproblem så stora att de inte längre kan lösas på en enda dator. Detta har skapat ett stort intresse för att utveckla optimeringsalgoritmer som kan exekveras effektivt på flera parallella datornoder. Ett sätt att uppnå effektivitet i parallella beräkningar är att låta noderna arbeta asynkront: på detta sätt spenderar noderna mindre tid på att koordinera med varandra och mer tid på beräkningar.  Beräkningarna måste dock ibland baseras på fördröjd information.  Asynkronism medför dock en risk att annars konvergenta optimeringsalgoritmer inte längre konvergerar, och det finns i dagsläget väldigt begränsat matematiskt stöd för analys av asynkrona optimeringsalgoritmer. I avhandlingen utvecklar vi ny teori och verktyg för att hjälpa till att förstå och implementera asynkrona optimeringsalgoritmer under tidsvarierande och begränsad informationsfördröjning.

I den första delen av avhandlingen analyserar vi konvergensen för olika asynkrona optimeringsalgoritmer. Vi föreslår först ett nytt tillvägagångssätt för att minimera medelvärdet av ett stort antal differentierbara komponentfunktioner. Algoritmen använder fördröjd partiell gradientinformation, och inkluderar fördröjda inkrementella gradientalgoritmer och koordinatreduktionsalgoritmer som specialfall. Vi visar att när den totala förlustfunktionen är strarkt konvex och komponentfunktionerna har Lipschitz-kontinuerliga gradienter så konvergerar algoritmen linjärt.  Steglängden för algoritmen kan väljas utan vetskap om den övre gränsen på informationsfördröjningen och garanterar ändå konvergens till en given nivå av suboptimalitet. Därefter analyserar vi två varianter av inkrementella gradientalgoritmer för regulariserade optimeringsproblem. Den första varianten, asynkron mini-batching, används för att lösa regulariserade stokastiska optimeringsproblem med deriverbara förlustfunktioner. Vi visar att algoritmen med tidsvarierande steglängd uppnår de bäst kända konvergenshastigheterna för motsvarande synkrona algoritm när (i) den tillåtna mängden är kompakt eller (ii) regulariseringsfunktionen är starkt konvex och den tillåtna mängden är sluten och konvex. Detta innebär att tidsfördröjningen har en asymptotiskt försumbar effekt på konvergensen, och vi kan förvänta oss att asynkrona beräkningar ger en kortare beräkningstid. För den andra varianten, proximal inkrementell aggregerad gradientnedstigning, visar vi att när målfunktionen är starkt konvex, så konvergerar algoritmen linjärt till den korrekta lösningen ifall man använder en konstant stegstorlek som beror på den maximala tidsfördröjningen.

I den andra delen av avhandlingen presenterar vi först POLO, ett öppen källkodsbibliotek för algoritmutveckling skrivet i C++. Vi använder en policy-baserad designmetod för att dekomponera proximala gradientalgoritmer till deras grundläggande byggstenar. Detta tillåter oss att hantera en kombinatorisk mängds designval med linjärt många komponenter och resulterar i effektiv kod med litet fotavtryck. Tillsammans med sitt systerbibliotek skrivet i Julia, POLO.jl, ger vårat ramverk forskare inom optimering och maskininlärning en möjlighet att snabbt skapa prototyper av sina idéer, testa dem mot algoritmer från forskningens framkant, och senare distribuera algoritmerna på olika datorplattformar med bara några rader av kod. Vidare framställer vi en ny ``serverlös'' exekverare för en parallell variant av den alternerande riktningsmetoden för multiplikatorer (ADMM) med hjälp av verktygen i vårat ramverk. Vi använder Amazon Web Services Lambda-funktioner som datornoder, och vi observerar kortare körtid upp till 256 arbetare och en parallella effektiviteten på över 70% upp till 64 arbetare. Dessa preliminära resultat tyder på att serverlösa exekveringsmiljöer, med deras tillgänglighet och elasticitet, är lovande kandidater för att skala upp distribuerade optimeringsalgoritmer.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2019. , p. 165
Series
TRITA-EECS-AVL ; 2019:6
Keywords [en]
convex, optimization, asynchronous, algorithms, parallel, distributed, large-scale, big data, software, serverless
National Category
Control Engineering
Research subject
Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-245995ISBN: 978-91-7873-066-7 (print)OAI: oai:DiVA.org:kth-245995DiVA, id: diva2:1295016
Public defence
2019-03-29, F3, Kungliga Tekniska högskolan, Lindstedtsvägen 26, Stockholm, 10:00 (English)
Opponent
Supervisors
Funder
Swedish Foundation for Strategic Research Swedish Research Council
Note

QC 20190311

Available from: 2019-03-11 Created: 2019-03-08 Last updated: 2019-03-11Bibliographically approved

Open Access in DiVA

2019-Aytekin(2470 kB)109 downloads
File information
File name FULLTEXT01.pdfFile size 2470 kBChecksum SHA-512
04a28d981fc8595921be3d0d6d7b76aecd1d20915259e4c98d4c5903cd421a4988fac9a24d8047c1d0b944ea5da400c594f94b87becf56179b5e0e503ca9a56d
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Aytekin, Arda
By organisation
Automatic Control
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 109 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 648 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf