Aller au boulot

Gradient Descent

Multi-variable function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$, defined differentiable in a neighborhood of a point $x\in {\mathbb{R}}^n$, for $\lambda \in {\mathbb{R}}_{+}$ small enough,

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

leads to $f(x_{k+1})\le f(x_k)$.

If $f$ convex and $\nabla f$ Lipschitz, $f_k$ converge to a local mimimum.

Optimization : Momentum

Let $\gamma <1,v_0=0$,

$$\{\begin{array}{ll}{x}_{k+1}& =x_k-v_k\\ v_k& =\gamma v_{k-1}+\lambda \nabla f(x_k)\end{array}$$

The momentum term increases for dimensions whose gradients point in the same directions and reduces updates for dimensions whose gradients change directions. As a result, we gain faster convergence and reduced oscillation.

Optimization : Nesterov

Version with correction,

$$\{\begin{array}{ll}{x}_{k+1}& =x_k-v_k\\ v_k& =\gamma v_{k-1}+\lambda \nabla f(x_k-\gamma v_{k-1})\end{array}$$

This anticipatory update prevents us from going too fast and results in increased responsiveness, which has significantly increased the performance of RNNs on a number of tasks.

Adagrad

It adapts the learning rate to the parameters, performing larger updates for infrequent and smaller updates for frequent parameters. For this reason, it is well-suited for dealing with sparse data.

$$x_{k+1}=x_k-\frac{\lambda }{\sqrt{G_k+ϵ}}\nabla f(x_k)$$

Application : learned to recognize cats in Youtube videos; GloVe word embeddings.

Adadelta

Adadelta is an extension of Adagrad that seeks to reduce its aggressive, monotonically decreasing learning rate. Instead of accumulating all past squared gradients, Adadelta restricts the window of accumulated past gradients to some fixed size w.

RMSprop

RMSprop and Adadelta have both been developed independently around the same time stemming from the need to resolve Adagrad’s radically diminishing learning rates. RMSprop in fact is identical to the first update vector of Adadelta.

$$v(x_k,t):=\gamma v(x_k,t-1)+(1-\gamma )(\nabla f(x_k){)}^2$$

$$x_{k+1}=x_k-\frac{\eta }{\sqrt{v(x_k,t)}}\nabla f(x_k)$$

Adam

Adaptive Moment Estimation (Adam) is another method that computes adaptive learning rates for each parameter. In addition to storing an exponentially decaying average of past squared gradients $v_k$ like Adadelta and RMSprop, Adam also keeps an exponentially decaying average of past gradients $u_k$, similar to momentum.

$$\begin{array}{rl}{u}_k& ={\beta }_1{u}_{k-1}+(1-{\beta }_1)\nabla f(x_k)\\ v_k& ={\beta }_2{v}_{k-1}+(1-{\beta }_2){\nabla }^{2}f(x_k)\end{array}$$

$$\begin{array}{rl}{\hat{u}}_k& =\frac{u_k}{1-{\beta }_1}\\ {\hat{v}}_k& =\frac{v_k}{1-{\beta }_2}\end{array}$$

$$x_{k+1}=x_k-\frac{\eta }{\sqrt{{\hat{v}}_k}+ϵ}\nabla f(x_k)$$