Nesterovaccelerering

Nesterovaccelerering, ofta kallad Nesterovs accelerationsmetod eller Nesterov-momentum, är en metod inom optimering som används för att snabba upp konvergensen hos gradientbaserade algoritmer. Den introducerades av Yuri Nesterov 1983 och är särskilt effektiv för släta konvexa mål.

Grundidén är att använda ett momentum och att gradienten evalueras vid en lookahead-punkt snarare än vid den aktuella punkten. Detta ger en bättre riktning mot minimipunkten jämfört med vanlig gradientnedstigning.

En vanligt förekommande formulering involverar två sekvenser, x_k och y_k: man uppdaterar y_k genom att lägga till en del av skillnaden mellan nuvarande och föregående punkt: y_k = x_k + beta_k (x_k - x_{k-1}). Därefter tas ett gradientsteg vid y_k: x_{k+1} = y_k - (1/L) grad f(y_k), där L är gradientens Lipschitz-konstant. Parametern beta_k och relaterade t-parametrar definieras ofta genom t_{k+1} = (1 + sqrt(1 + 4 t_k^2))/2 och beta_k = (t_k - 1)/t_{k+1}.

Teoretiskt ger metoden för konvexa och glatta funktioner konvergenshastigheten f(x_k) - f(x*) = O(1/k^2). För starkt konvexa funktioner kan den ge linjär konvergens med rätt parametrar. I praktiken används Nesterovaccelerering även i icke-konvexa problem och som en komponent i större optimeringsrutiner inom maskininlärning.

Jämfört med heavym-ball-metoden (Polyak) fokuserar Nesterovaccelerering mer på lookahead-gradienten, vilket ofta ger bättre prestanda i praktiken på högdimensionella problem.

Se även: gradientnedstigning, momentum, Nesterovs accelerated gradient, heavy-ball.