Till innehåll på sidan

Scalable Optimization Methods for Machine Learning

Acceleration, Adaptivity and Structured Non-Convexity

Tid: To 2021-08-26 kl 16.00

Plats: F3, Zoom-link: https://kth-se.zoom.us/j/69857318021, Kungliga Tekniska högskolan, Lindstedtsvägen 26, Stockholm (English)

Ämnesområde: Elektro- och systemteknik

Respondent: Vien Van Mai , Reglerteknik

Opponent: Professor John Duchi, Stanford university

Handledare: Mikael Johansson, Reglerteknik

Exportera till kalender

Abstract

Denna avhandling behandlar effektiva optimeringsalgoritmer för att lösa storskaliga maskininlärningsproblem. För att hantera den ständigt ökande skalan och komplixiteten i maskininlärningsmodeller fokuserar vi på första ordningens metoder. Dessa metoder använder sig av inexakt information om funktionsvärden och (sub)gradienter för att hitta en optimal lösning. Vårt mål är att förstå hur man, under dessa förutsättningar, designar optimeringsalgoritmer som har starka teoretiska garantier och presterar väl i praktiken. Vi beaktar viktiga problemklasser för maskininlärningstillämpningar och studerar ett flertal olika lösningsmetoder (både helt nya algoritmer och framgångsrika existerande metoder).  Vi lägger stor vikt vid att utveckla och analysera metoder som är enkla att exekvera för storskaliga problem, som fungerar väl för ett brett spektrum av designparametrar, och som kan anpassa sig till och utnyttja problemstruktur.

Mer specifikt så fokuserar den första delen av avhandlingen på två fundamentala problemklasser som förekommer i många moderna tillämpningar av maskininlärning. Vi börjar med att studera optimeringsproblem med målfunktioner som har en deriverbar och en icke-glatt komponent. Vi visar hur Anderson-acceleration, en minneseffektiv och linjesökningsfri metod med goda adaptionsegenskaper, kan anpassas till denna typ av problem. Motiverade av välkända problem med parameterkänslighet och instabilitet hos den klassiska stokastiska subgradientmetoden (SGD) studerar vi sedan ett antal tekniker för att förbättra metodens praktiska prestanda. Vi härleder ett flertal nya konvergensresultat under antaganden där det tidigare inte fanns någon tillämpbar teori. T.ex. så studerar vi momentum-varianter av SGD på svagt konvexa funktioner och etablerar resultat för sampelkomplexitet, och vi visar hur metoder som begränsar gradientens norm gör det möjligt att hantera stokastiska optimeringsproblem med snabbt växande gradienter. 

I den andra delen av avhandlingen så behandlar vi några specifika problem med ytterligare struktur. Vi undersöker hur nya forskningsresultat för första ordningens metoder kan utnyttjas för att ytterligare minska tiden det tar att hitta en optimal lösning. Den gemensamma nämnaren hos metoderna som utvecklas i denna del av avhandlingen är att de är bygger på en omsorgsfullt vald kombination av (i) accelerations- och variansreduceringstekniker som minskar antalet iterationer som krävs för att hitta en lösning; (ii) inexakta beräkningar som gör att varje iteration kan exekveras snabbare, genom att beräkna resultat med endast den precision som krävs; samt (iii) effektiva tekniker för att varmstarta algoritmen från tidigare lösningar.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-299186