Gradiente a passo costante e convergenza

Dall'ottimalità a un algoritmo

Nel problema non vincolato $\min_{x\in\mathbb R^n}f(x)$, con $f$ non convessa, trovare un minimo globale è in generale difficile. L'obiettivo realistico è un punto stazionario, dove $\nabla f(x)=0$, perché è la condizione necessaria di minimo locale. Se $f$ è di classe $C^2$, in un minimo locale l'hessiana è anche semidefinita positiva.

Un algoritmo parte da $x_0$ e genera punti $x_k$. Se $\nabla f(x_k)=0$ ha finito. Altrimenti cerca un $x_{k+1}$ con

$$f(x_{k+1})<f(x_k)$$

Si assume che $f$ sia limitata inferiormente. Non serve che il minimo esista, ma senza questa ipotesi i valori potrebbero scendere fino a $-\infty$ e il problema non sarebbe ben posto.

Direzione e passo

Il nuovo punto si cerca lungo una direzione di discesa $d_k$, cioè con derivata direzionale negativa:

$$\lim_{t\to0^+}\frac{f(x_k+td_k)-f(x_k)}{t}=\nabla f(x_k)^\top d_k<0$$

La scelta più semplice è l'antigradiente $d_k=-\nabla f(x_k)$. Il punto nuovo è

$$\begin{gathered} x_{k+1}=x_k-\eta_k\nabla f(x_k)\\ \eta_k>0 \end{gathered}$$

Lo scalare $\eta_k$ è il passo (step size, o passo di ricerca unidimensionale). Nelle reti neurali si chiama learning rate, tasso di apprendimento.

Una ricerca unidimensionale semplice prova un passo grande, per esempio $\eta=10$, e lo dimezza finché $f$ non diminuisce. Termina dopo un numero finito di tentativi, perché la derivata direzionale è negativa e quindi per $t$ abbastanza piccolo $f(x_k+td_k)<f(x_k)$. Ogni tentativo però costa una valutazione di $f$, che può essere molto costosa. Ci si chiede allora quando si può fissare il passo una volta per tutte.

Gradiente Lipschitz e lemma di discesa

Il metodo del gradiente a passo costante usa lo stesso $\eta$ a ogni iterazione $k=0,1,\dots$:

$$x_{k+1}=x_k-\eta\nabla f(x_k)$$

Serve un'ipotesi più forte di $f\in C^1$: il gradiente è Lipschitz continuo su $\mathbb R^n$, cioè esiste $L>0$ tale che

$$\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|\qquad\forall x,y\in\mathbb R^n$$

È la definizione già vista per le funzioni scalari, con la norma al posto del valore assoluto perché il gradiente è un vettore.

Lemma di discesa (senza dimostrazione). Se $\nabla f$ è Lipschitz continuo su $\mathbb R^n$ con costante $L$, per ogni $x$ e ogni $d$ in $\mathbb R^n$

$$f(x+d)\le f(x)+\nabla f(x)^\top d+\frac L2\|d\|^2$$

Il lemma maggiora $f(x+d)$ con una funzione quadratica di $d$ che dipende solo da $f(x)$, da $\nabla f(x)$ e da $L$. Così il decremento si controlla senza valutare $f$ nel punto nuovo.

La stima del lemma di discesa

stima in $x_{k+1}$$f(x_{k+1})$$x$

• $f$
• stima del lemma
• $f(x_k)$

$x_k$

2

$\eta$

1

La convergenza

Il metodo genera due successioni: i punti $\{x_k\}$ in $\mathbb R^n$ e i valori $\{f(x_k)\}$ in $\mathbb R$. Per la seconda vale un risultato in più: una successione reale monotona decrescente tende a $-\infty$ oppure a un limite finito. Se $f$ è limitata inferiormente resta solo il secondo caso.

Proposizione. Sia $f$ limitata inferiormente, con $\nabla f$ Lipschitz continuo su $\mathbb R^n$ con costante $L$, e sia

$$0<\eta<\frac2L$$

Allora, se nessun $x_k$ è stazionario,

$$\lim_{k\to\infty}\|\nabla f(x_k)\|=0$$

Dimostrazione. Si applica il lemma con $x=x_k$ e $d=-\eta\nabla f(x_k)$. Poiché $\nabla f(x_k)^\top d=-\eta\|\nabla f(x_k)\|^2$ e $\|d\|^2=\eta^2\|\nabla f(x_k)\|^2$:

$$\begin{aligned} f(x_{k+1})&\le f(x_k)-\eta\|\nabla f(x_k)\|^2\\ &\quad+\frac L2\eta^2\|\nabla f(x_k)\|^2\\ &=f(x_k)-\eta\Bigl(1-\frac{L\eta}2\Bigr)\|\nabla f(x_k)\|^2 \end{aligned}$$

Con $\eta>0$ e $\eta<2/L$ entrambi i fattori $\eta$ e $1-L\eta/2$ sono positivi. Poiché $\nabla f(x_k)\neq0$, il termine sottratto è positivo, quindi $f(x_{k+1})<f(x_k)$. La successione $\{f(x_k)\}$ è decrescente e $f$ è limitata inferiormente, quindi $f(x_k)\to\bar f>-\infty$. Anche $f(x_{k+1})\to\bar f$, perché è la stessa successione con l'indice spostato. Riordinando la stima:

$$\begin{aligned} 0&\le\eta\Bigl(1-\frac{L\eta}2\Bigr)\|\nabla f(x_k)\|^2\\ &\le f(x_k)-f(x_{k+1}) \end{aligned}$$

Il membro di destra tende a $0$ e la costante davanti alla norma non dipende da $k$. Per il teorema del confronto $\|\nabla f(x_k)\|\to0$. $\blacksquare$

L'intervallo $0<\eta<2/L$ serve proprio a rendere positivo il decremento garantito. Il metodo costa solo il calcolo del gradiente e ha una regola fissa per il passo. Il limite pratico è che $L$ di solito non si conosce. Per questo nei programmi di addestramento delle reti neurali il learning rate ha un valore predefinito, per esempio $10^{-1}$: se il metodo oscilla lo si riduce, per esempio a $10^{-3}$; se non oscilla ma è lento lo si aumenta, per esempio a $0{,}7$.

Iterate del gradiente al variare del passo

$x$

• $f$
• $(x_k,f(x_k))$

$\eta$

1,5

Punti limite e insiemi di livello

Proposizione. Nelle ipotesi precedenti, ogni punto limite di $\{x_k\}$ è stazionario.

Dimostrazione. Sia $\bar x$ un punto limite: esiste un insieme di indici $K$ con $x_k\to\bar x$ per $k\to\infty$, $k\in K$. Il gradiente e la norma sono continui, quindi

$$\|\nabla f(\bar x)\|=\lim_{\substack{k\to\infty\\k\in K}}\|\nabla f(x_k)\|=0$$

perché tutta la successione $\|\nabla f(x_k)\|$ tende a $0$. $\blacksquare$

Resta da garantire che i punti limite esistano. Per il teorema di Bolzano-Weierstrass basta che $\{x_k\}$ sia limitata. Assumerlo direttamente sarebbe però un'ipotesi a posteriori, sulla successione prodotta dal metodo: tanto varrebbe assumere che converga alla soluzione. Servono ipotesi a priori, sul problema, cioè su $f$.

Dato $\alpha\in\mathbb R$, l'insieme di livello di $f$ rispetto ad $\alpha$ è

$$\{x\in\mathbb R^n:\ f(x)\le\alpha\}$$

purché non sia vuoto: se $f(x)>\alpha$ per ogni $x$, $\alpha$ non definisce un insieme di livello.

Un insieme di livello in una variabile

$x$

• $f$
• $\alpha$
• insieme di livello

$\alpha$

0,4

Con $\alpha=f(x_0)$ si ottiene l'insieme di livello iniziale, non vuoto perché contiene $x_0$:

$$\mathcal L_0=\{x\in\mathbb R^n:\ f(x)\le f(x_0)\}$$

Proposizione. Se $\mathcal L_0$ è compatto e $f(x_{k+1})<f(x_k)$ per ogni $k$, allora $x_k\in\mathcal L_0$ per ogni $k$, quindi $\{x_k\}$ è limitata e ha punti limite.

Dimostrazione. Da $f(x_1)<f(x_0)$ segue $x_1\in\mathcal L_0$. Da $f(x_2)<f(x_1)<f(x_0)$ segue $x_2\in\mathcal L_0$, e per induzione $x_k\in\mathcal L_0$ per ogni $k$. Un compatto è limitato, e una successione limitata in $\mathbb R^n$ ha punti limite per Bolzano-Weierstrass. $\blacksquare$

Chiedere che $\mathcal L_0$ sia compatto dipende ancora dalla scelta di $x_0$. Si evita con un'ipotesi su $f$ soltanto. In una variabile, $f$ è coerciva se tende a $+\infty$ sia per $x\to-\infty$ sia per $x\to+\infty$, come nella figura.

Proposizione (senza dimostrazione). Se $f$ è continua e coerciva, ogni suo insieme di livello è compatto. In particolare lo è $\mathcal L_0$, qualunque sia $x_0$.

Se $x_0$ è già stazionario non si genera nessun punto nuovo, e $\mathcal L_0$ resta comunque ben definito.

Funzioni quadratiche

Si consideri una funzione quadratica con $Q$ simmetrica definita positiva:

$$f(x)=\frac12x^\top Qx+c^\top x$$

Il gradiente è $Qx+c$, quindi il punto stazionario risolve il sistema lineare

$$Q\bar x=-c$$

Minimizzare $f$ equivale quindi a risolvere un sistema lineare. Un metodo diretto, per esempio la fattorizzazione di Cholesky, costa $O(n^3)$ e conviene se $n$ non è grande. Per $n$ grande serve un metodo iterativo. Il metodo del gradiente converge solo asintoticamente, mentre il metodo del gradiente coniugato, specifico per le quadratiche e non trattato qui, termina in un numero finito di iterazioni, al più pari al numero di autovalori distinti di $Q$. Con $Q$ di ordine $10\,000$ e $100$ autovalori distinti bastano al più $100$ iterazioni. Prima di applicare un metodo generico conviene quindi cercare un metodo adatto alla struttura della funzione.

Dimostrazioni

Dimostrati: convergenza del metodo del gradiente a passo costante; stazionarietà dei punti limite; iterati nell'insieme di livello compatto.

Senza dimostrazione: lemma di discesa; compattezza degli insiemi di livello delle funzioni coercive.