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)$$ (4.45)

ovvero, definendo il passo di aggiornamento:

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

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 (4.45) con l'equazione (4.44), 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. In prossimità di un minimo locale regolare tale matrice è definita positiva:

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

Il metodo di Newton rappresenta un metodo di ottimizzazione del secondo ordine e, sotto opportune ipotesi di regolarità e con un'inizializzazione sufficientemente vicina alla soluzione, presenta una convergenza quadratica, in contrasto con la convergenza lineare tipica della discesa del gradiente classica.