Novel Hessian-Based Algorithms for Unconstrained Optimization

QC 20240515

Abstract

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.

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