Deep Learning Optimization

Optimization is a very difficult problem; usually one has to carefully design an objective function and related constraints, and also make sure the problem to be optimized is a convex function, but most real-world problems are non-convex. For non-convex optimization problems there are some basic optimization methods: SGD, Momentum, AdaGrad, RMSProp, Adam and so on

Stochastic Gradient Descent (SGD)

---

// stochastic gradient descent

Given the dataset $X=\\{x^{(1)},x^{(2)},...,x^{(n)}\\}$ and the dataset labels $Y=\\{y^{(1)}, y^{(2)},...,y^{(n)}\\}$

Learner $f(x;w)$, learning rate (step size) $\alpha$

For enough iterations

{

Randomly select data: $\\{x^{(j)}, y^{(j)}\\}$

Compute the loss gradient: $\nabla\mathbf{w}=\frac{\partial{L(y^{(j)},f(x^{(j)};w))}}{\partial{w}}$

Modify the weights: $\mathbf{w_i}=\mathbf{w_i}-\alpha\nabla\mathbf{w}$

}

---

The above randomly selects one data point from the dataset for gradient descent, so a strong random effect appears during training. To avoid this randomness, multiple data points can be selected for the gradient computation and then averaged.

As for the learning rate, in the algorithm above the learning rate stays constant, which in the later stage of training causes the algorithm to oscillate around the optimal solution. To eliminate or alleviate this, we can decrease the learning rate as much as possible when approaching the optimal solution

Combining the two gives the following gradient descent algorithm

---

// learning-rate-decayed mini-batch gradient descent

Given the dataset $X=\\{x^{(1)},x^{(2)},...,x^{(n)}\\}$ and the dataset labels $Y=\\{y^{(1)}, y^{(2)},...,y^{(n)}\\}$

Randomly sample $m$ data points, number of training epochs $k$, minimum learning rate decay value $b$, learner $f(x;w)$

Initial learning rate (step size) $\alpha_0$

For $i <= k$

{

Randomly sample $m$ data points: $\\{(x^{(i)},y^{(i)}),...,(x^{(m)},y^{(m)}\\}$

Compute the average loss gradient of the sampled data: $\nabla \mathbf{w} = \frac{1}{m}\sum^m_{j=1}\frac{\partial{L(y^{(j)},f(x^{(j)};w)})}{\partial{\mathbf{w}}}$

Compute the decayed learning rate: $a_i=(i-\frac{i}{k})a_0+\frac{i}{k}b$

Modify the network weights: $\mathbf{w}_i=\mathbf{w}_i-\alpha\nabla\mathbf{w}$

}

---

Momentum

Although the algorithm above solves the problems of oscillation around the optimal solution and of randomness, it cannot guarantee that the solution found by the algorithm is the global optimum; the algorithm may afterwards find a local optimum, that is, a saddle point.

To escape the saddle point, the physical concept of momentum can be used to break out of it, giving the following momentum stochastic gradient descent method

---

// momentum method

Given the dataset $X=\\{x^{(1)},x^{(2)},...,x^{(n)}\\}$ and the dataset labels $Y=\\{y^{(1)}, y^{(2)},...,y^{(n)}\\}$

Initial velocity $v$, random sample size $m$, number of training epochs $k$

Learner $f(x;w)$, initial learning rate $\alpha$, initial momentum parameter $\beta$

For $i <= k$

{

Randomly sample $m$ data points: $\\{(x^{(i)},y^{(i)}),...,(x^{(m)},y^{(m)}\\}$

Compute the average loss gradient of the sampled data: $\nabla \mathbf{w} = \frac{1}{m}\sum^m_{j=1}\frac{\partial{L(y^{(j)},f(x^{(j)};w)})}{\partial{\mathbf{w}}}$

Update the velocity: $v=\beta v-\alpha\nabla\mathbf{w}$

Update the parameters: $\mathbf{w}=\mathbf{w}+v$

}

---

In practice, commonly used values of $\beta$ are 0.5, 0.9 or 0.99, tuned according to the specific problem, but adjusting $\beta$ is not as important as adjusting $\alpha$, so it does not really need to be chosen as a hyperparameter — an appropriate value is generally enough. The momentum method exhibits slight oscillation in the later stage of training.

NAG (Nesterov accelerated gradient)

To solve the problem of slight oscillation in the momentum method, NAG uses $\mathbf{w}-\beta v_{t-1}$ as an approximation of the value the parameters will take at the next step, so the gradient is computed at the future position; it performs very well on sparse data. The velocity update is written as follows:

$$ v_t = \beta v_{t-1}+\alpha\nabla_\mathbf{w} J(\mathbf{w}-\beta v_{t-1}) $$

where $J(\cdot)$ is the loss function. When the gradient direction is about to change, NAG can know in advance, thereby weakening this process and reducing useless iterations.

AdaGrad, Adelta and RMSProp

The algorithms above all use a single global learning rate, so all parameters advance with a uniform stride, but the parameters in a network may not all have consistent descent gradients and directions at the same time. The following algorithms configure the learning rate individually for each parameter

AdaGrad

This algorithm simply accumulates the square of the historical gradient of each dimension, and then divides by that historical gradient when updating (the square is used to remove the sign of the gradient, accumulating only the magnitude of the gradient)

$$cache_i = cache_i+(\nabla\mathbf{w}_i)^2$$

Update the parameters:

$$\mathbf{w}_i=\mathbf{w}_i-\frac{\alpha}{\sqrt{cache_i}+\delta}\nabla\mathbf{w}_i$$

where $\delta=10^{-7}$ prevents numerical overflow caused by division by zero

AdaGrad makes the learning rate larger for parameters whose accumulated gradient magnitude is small (<1), making network training faster, and smaller when the accumulated gradient magnitude is large (>1), slowing down network training

But with AdaGrad the learning rate decreases very quickly as the number of epochs grows, that is, the algorithm easily reduces the learning rate too much

Adelta

This method improves on the situation in Adgard where the learning rate becomes very small as the number of iterations increases, mainly by replacing $cache$ with the decayed average of the squared gradients of the past. The parameter update formulas are as follows:

$$ \begin{aligned} \mathbf{w}_t &= \mathbf{w}_{t-1} - \frac{\alpha}{\sqrt{E[g^2]_t}+\delta}g_t \\ E[g^2]_t &= \frac{1}{t}\sum_{i=1}^t g_i^2 \\ g_t &= \nabla\mathbf{w}_t \end{aligned} $$

This denominator is equivalent to the root mean square of the gradient (in mathematical statistics, the root mean square is the square root of the average of the squared data). So it can be abbreviated as:

$$ \mathbf{w}_t = \mathbf{w}_{t-1}-\frac{\alpha}{RMS[g]_t}g_t $$

The averaging part can be replaced with an incremental form, introducing the hyperparameter $\gamma$ (usually set to 0.9) to weigh the importance of past versus current gradients:

$$ E[g^2]_t = \gamma E[g^2]_{t-1}+(1-\gamma)g_t^2 $$

The learning rate can also be replaced with $RMS[\Delta\mathbf{w}]$, so that no learning rate needs to be preset.

$$ \begin{aligned} \Delta\mathbf{w}_t &= -\frac{RMS[\Delta\mathbf{w}]_{t-1}}{RMS[g]_t}g_t \\ \mathbf{w}_t &= \mathbf{w}_{t-1}+\Delta\mathbf{w}_t \\ \end{aligned} $$

RMSProp

To solve the problem that AdaGrad’s learning rate decays too fast, the RMSProp algorithm introduces a decay factor, striking a balance between “past” and “now” when accumulating gradients; $\beta$ adjusts the amount of decay, with commonly used values of 0.9 or 0.5

$$cache_i=\beta cache_i+(1-\beta)(\nabla \mathbf{w}_i)^2$$

In the parameter update stage it is the same as AdaGrad

$$\mathbf{w}_i=\mathbf{w}_i-\frac{\alpha}{\sqrt{cache_i}+\delta}\nabla\mathbf{w}_i$$

Adam

This algorithm is a fine-tuned version of Momentum + RMSProp; by default this optimization method is recommended

At the beginning the gradients are very small, so $r$ and $v$ are often close to 0, and therefore we also need to adjust $r$ and $v$

$$ \begin{aligned} vb=\frac{v}{1-\beta^t_1} \\ rb=\frac{r}{1-\beta^t_2} \end{aligned} $$

where $t$ denotes the number of training steps, so this algorithm only scales up the respective values according to the decay factors during the first few rounds of training, and very soon $vb$ and $rb$ decay to $v$ and $r$

---

// Adam

Given the dataset $X=\\{x^{(1)},x^{(2)},...,x^{(n)}\\}$ and the dataset labels $Y=\\{y^{(1)}, y^{(2)},...,y^{(n)}\\}$

Initial velocity $v$, random sample size $m$, number of training epochs $k$

Learner $f(x;w)$, initial learning rate $\alpha$, initial momentum parameter $\beta_1$

Learning rate decay parameter $\beta_2$, $\delta=10^{-7}$

For $i <= k$

Randomly sample $m$ data points: $\\{(x^{(i)},y^{(i)}),...,(x^{(m)},y^{(m)}\\}$

Compute the current sampled data gradient: $g = \frac{1}{m}\sum^m_{j=1}\frac{\partial{L(y^{(j)},f(x^{(j)};w)})}{\partial{\mathbf{w}}}$

Update the current velocity: $v=\beta_1 v+(1-\beta_1)g$

Update the current learning rate: $r=\beta_2 r+(1-\beta_2)g^2$

Update the step count: $t=t+1$

$$ \begin{aligned} vb=\frac{v}{1-\beta^t_1} \\ rb=\frac{r}{1-\beta^t_2} \end{aligned} $$

Update the parameters:

$$w=w-\frac{\alpha}{\sqrt{rb}+\delta}vb$$