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 (più precisamente, l'antigradiente) della funzione obiettivo $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, definendo il passo di aggiornamento:

$$\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 è sufficientemente vicino alla soluzione e il valore di $\gamma$ è abbastanza piccolo, il ritmo di convergenza ottenibile è praticamente lineare.

Poiché il parametro $\gamma$ è scelto manualmente, l'approccio risulta empirico e dipendente dal problema, se non dall'esperienza dell'utilizzatore. Confrontando l'equazione (3.37) con l'equazione (3.36), si osserva che il metodo di Newton è di fatto un caso particolare di discesa del gradiente, in cui il parametro scalare $\gamma$ viene sostituito da una matrice definita positiva $\boldsymbol\Gamma_t$, ottenuta come inversa dell'Hessiana nel punto corrente:

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

La discesa del gradiente del secondo ordine corrisponde quindi all'algoritmo di Newton, che - sotto opportune ipotesi - garantisce una convergenza quadratica, in contrasto con la convergenza lineare della discesa del gradiente classica.