Novel Hessian-Based Algorithms for Unconstrained Optimization

• There are several benefits of taking the Hessian of the objective function into account when designing optimization algorithms. Compared to using strictly gradient-based algorithms, Hessian-based algorithms usually require fewer iterations to converge. They are generally less sensitive to tuning of parameters and can better handle ill-conditioned problems. Yet, they are not universally used, due to there being several challenges associated with adapting them to various challenging settings. This thesis deals with Hessian-based optimization algorithms for large-scale, stochastic, distributed, and zeroth-order problems. For the large-scale setting, we contribute with a new way of deriving limited memory quasi-Newton methods, which we show can achieve better results than traditional limited memory quasi-Newton methods with less memory for some logistic and linear regression problems. For the stochastic setting, we relax the secant condition used in traditional quasi-Newton methods and derive a novel quasi-Newton update that always preserves positive definiteness. Based on this, we develop an algorithm that exhibits linear convergence toward a neighborhood of the optimal solution, even if gradient and function evaluations are subject to bounded perturbations. For the distributed setting, we contribute with two different projects. Firstly, we perform an analysis of how the error of a Newton-step is affected by the condition number and the number of iterations of a consensus-algorithm based on averaging. We show that the number of iterations needed to solve a quadratic problem with relative error less than ε grows logarithmically with 1/ε and also with the condition number of the Hessian of the centralized problem. Secondly, we consider how Hessians and Hessian approximations can be used to compensate for communication delays in asynchronous implementations of the Incremental Aggregated Gradient (IAG) algorithm. We provide a general convergence theorem that can be used to analyze delay compensation using various Hessian approximations, apply it to the previously proposed Curvature-Aided IAG (CIAG), and propose delay compensation with some cheaper Hessian approximations that nevertheless outperform IAG without delay compensation. For the zeroth order setting, we exploit the fact that a finite difference estimate of the directional derivative works as an approximate sketching technique and use this to propose a zeroth order extension of a sketched Newton method that has been developed to solve large-scale problems. With the extension of this method to the zeroth order setting, we address the combined challenge of large-scale and zeroth order problems. 

• Det finns flera fördelar med att ta hänsyn till målfunktionens Hessian när man utformar optimeringsalgoritmer. Jämfört med att använda strikt gradientbaserade algoritmer kräver Hessian-baserade algoritmer vanligtvis färre iterationer för att konvergera. De är generellt sett mindre känsliga för justering av parametrar och kan bättre hantera illa konditionerade problem. Ändå används de inte universellt, eftersom det finns flera utmaningar förknippade med att anpassa dem till olika utmanande förhållanden. Detta examensarbete behandlar Hessian-baserade optimeringsalgoritmer för storskaliga, stokastiska, distribuerade och nollte ordningens problem. För storskaliga problem bidrar vi med ett nytt sätt att härleda  kvasi-Newton-metoder med begränsat minne, som vi visar kan uppnå bättre resultat än traditionella sådana metoder med mindre minne för vissa logistiska och linjära regressionsproblem. För stokastiska problem relaxerar vi sekantvillkoret, som används i traditionella kvasi-Newton-metoder, och härleder en ny kvasi-Newton-uppdatering som alltid bevarar positiv definitihet. Baserat på detta utvecklar vi en algoritm som uppvisar linjär konvergens mot ett område kring den optimala lösningen, även om gradient- och funktionsevalueringar påverkas av begränsade störningar. För distribuerade problem bidrar vi med två olika projekt. För det första utför vi en analys av hur felet i ett Newton-steg påverkas av konditionstalet och antalet iterationer av en konsensusalgoritm baserat på medelvärdesbildning. Vi visar att antalet iterationer som behövs för att lösa ett kvadratiskt problem med relativt fel mindre än ε växer logaritmiskt med 1/ε och även med konditionstalet för Hessianen för det centraliserade problemet. För det andra överväger vi hur Hessianer och Hessianapproximationer kan användas för att kompensera för kommunikationsfördröjningar i asynkrona implementeringar av algoritmen Incremental Aggregated Gradient (IAG). Vi tillhandahåller en allmän konvergenssats som kan användas för att analysera fördröjningskompensering med hjälp av olika Hessianapproximationer, applicerar det på den tidigare föreslagna Curvature-Aided IAG (CIAG) och föreslår fördröjningskompensering med några billigare Hessianapproximationer som ändå överträffar IAG utan fördröjningskompensering. För nollte ordningens prolem utnyttjar vi det faktum att en finit-differens-estimering av riktningsderivatan fungerar som en ungefärlig sketchingteknik, och använder denna för att föreslå en nollte ordnings generalisering av en skeching-Newtonmetod som har utvecklats för att lösa storskaliga problem. Med utvidgningen av denna metod till att fungera då derivator inte är tillgängliga, hanterar vi den kombinerade utmaningen med storskaliga och nollte ordningens problem.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

Optimeringslära och systemteori

Optimization and Systems Theory

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)