Discesa del Gradiente

L'algoritmo di discesa del gradiente (gradient descent GD o steepest descent) aggiorna i pesi $\boldsymbol\beta$ a ogni iterazione usando il gradiente (anzi l'antigradiente) di $S(\boldsymbol\beta)$:

$$\boldsymbol\beta_{t+1} = \boldsymbol\beta_{t} - \gamma \nab... ...{t} - \gamma \sum_{i=1}^{n} \nabla \ell_i(\boldsymbol\beta_t)$$ (3.37)

ovvero

$$\boldsymbol\delta_t = - \gamma \sum_{i=1}^{n} \nabla \ell_i(\boldsymbol\beta_t)$$ (3.38)

dove $\gamma$ è un fattore di ottimizzazione opportunamente scelto (in machine learning è chiamato learning rate). Sotto opportune assunzioni se il punto di partenza è prossimo alla soluzione e il fattore $\gamma$ abbastanza basso, il ritmo di convergenza che si può ottenere è praticamente lineare.

Avendo inserito nell'espressione (3.37) un parametro $\gamma$ deciso dall'utente, questo approccio è empirico e dipendente dal problema se non dall'esperienza dell'utilizzatore umano. A seguito di questa osservazione e confrontando l'equazione di discesa del gradiente con l'equazione (3.36), si intuisce che il metodo di Newton è di fatto un caso particolare di discesa del gradiente. Si può ottenere pertanto una migliore ottimizzazione sostituendo il parametro scalare $\gamma$ con la matrice definita positiva $\boldsymbol\Gamma_t$ ottenuta dall'inversa dell'Hessiana nel punto:

$$\boldsymbol\beta_{t+1} = \boldsymbol\beta_{t} - \boldsymbol\Gamma_t \nabla S(\boldsymbol\beta_t)$$ (3.39)

Una discesa del gradiente del secondo ordine è pertanto l'algoritmo di Newton ottenendo, sotto opportune ipotesi, invece di una convergenza lineare una convergenza quadratica.