Scalable Optimization Methods for Machine Learning : Acceleration, Adaptivity and Structured Non-Convexity

This thesis aims at developing efficient optimization algorithms for solving large-scale machine learning problems. To cope with the increasing scale and complexity of such models, we focus on first-order and stochastic methods in which updates are carried out using only (noisy) information about function values and (sub)gradients. The broad question we ask is: given such algorithmic oracles, how can we best design algorithms that both have strong theoretical guarantees and are practically useful. To this end, we touch upon a wide range of problems and investigate various methods (including newly proposed and successful existing ones) for solving them. We pay significant attention to developing and analyzing methods that are easy to run at scale, less sensitive to parameter selection, and adaptive to the underlying problem structure. In somewhat more detail, the first part of the thesis focuses on two fundamental classes of optimization problems which underpin many modern machine learning applications. We begin with deterministic composite minimization problems and show how to adapt Anderson acceleration---a memory-efficient and line search-free method with strong adaptation ability---to proximal gradient methods. Motivated by sensitivity and instability issues of the classical stochastic gradient descent method (SGD), we then turn to stochastic problems and investigate a number of techniques for improving the practical performance of SGD and its relatives. We derive several novel convergence results that cover important settings for which previous theory did not apply. For example, we move beyond stochastic convex optimization and establish sample complexity results for a momentum extension of SGD on weakly convex functions, and we look beyond quadratic growth and demonstrate improved stability and convergence of gradient clipping of SGD on problems with rapidly growing gradients. In the second part, we consider somewhat more structured problems and explore how recent advances in first-order and stochastic optimization can be exploited to expedite solution times even further. The common feature of the algorithms in this part is that they are constructed through a careful combination of (i) acceleration and variance reduction techniques to decrease the total number of iterations; (ii) inexact (noisy) computations that execute each iteration faster, and only to the precision actually required; and (iii) efficient warm-start schemes. We establish complexity guarantees of the proposed algorithms and quantify the improved run time in terms of the problem-dependent parameters.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.QC 20210804