Discesa Stocastica del Gradiente

L'algoritmo di discesa stocastica del gradiente (stochastic gradient descent SGD) è una semplificazione dell'algoritmo di discesa del gradiente. Invece che calcolare esattamente il gradiente di $S(\boldsymbol\beta)$, per ogni iterazione, viene usato il gradiente di uno dei campioni $\ell_i$ scelto casualmente

$$\boldsymbol\beta_{t+1} = \boldsymbol\beta_{t} - \gamma_t \nabla \ell_i(\boldsymbol\beta_t)$$ (3.40)

SGD può essere usato per ottimizzare una qualunque funzione convessa su dominio convesso.

L'eventuale discesa stocastica del gradiente del secondo ordine non porta normalmente a miglioramenti.

Dal punto di vista pratico spesso si esegue l'aggiornamento su un numero di campioni (batch size) piccolo ma maggiore di 1, per ridurre il rumore del singolo campione ma evitando di fornire contributi troppo mediati come nel caso di discesa del gradiente completo.

Infine, per simulare un'inerzia al cambiamento, viene aggiunto un termine $\alpha$ chiamato momentum:

$$\boldsymbol\delta_{t} = - \gamma_t \nabla S(\boldsymbol\beta_t) + \alpha \boldsymbol\delta_{t-1}$$ (3.41)

I valori di $\alpha$ sono normalmente piccoli (per esempio 0.05).

Il momentum è la modifica ad SGD più semplice che permette di risolvere alcuni problemi tipici delle ottimizzazioni in machine learning. Oltre a SGD+momentum, esistono tantissime varianti per accelerare la convergenza negli algoritmi tipo di discesa del gradiente. Una lista, non esaustiva, è

• Nesterov Accelerate Gradient (NAG)
• AdaDelta
• Adaptive Gradient (AdaGrad)
• RMSProp (Rprop + SGD)
• Adam
• AdaMax
• Momentum
• Resilient Propagation (RProp)

Un survey dei vari algoritmi si può trovare in (Rud16).

Adam

Adam (KB14) (Adaptive Momentum estimation) cerca di sfrutatre i punti di forza sia di AdaGrad (Adaptive Gradient Algorithm) che di RMSProp (Root Mean Square Propagation).

AdaGrad ha per ogni parametro un learning-rate: questo è vantaggioso per quei problemi con gradienti sparsi. RMSProp ha anche esso un learning-rate per parametro ma che viene cambiato con la variazione della magnitudo del gradiente: questo algoritmo lavora bene online e su problemi non-stazionari.

Invece che aggiornare il learning-rate analizzando il momento di primo ordine (la media) come RMSProp, Adam sfrutta il momento di secondo ordine dei gradienti.