Optimization Algorithms from a Dynamics Perspective (II): Adaptive Learning Rate Algorithms

Algorithm Overview

General gradient descent is as follows: \boldsymbol{\theta}_{n+1}=\boldsymbol{\theta}_{n} - \gamma \nabla_{\boldsymbol{\theta}} L(\boldsymbol{\theta}_{n}) Obviously, here \gamma is a hyperparameter, the learning rate, which may need different adjustments at different stages.

In contrast, RMSprop is: \begin{aligned} \boldsymbol{g}_{n+1} =& \nabla_{\boldsymbol{\theta}} L(\boldsymbol{\theta}_{n})\\ \boldsymbol{G}_{n+1}=&\lambda \boldsymbol{G}_{n} + (1 - \lambda) \boldsymbol{g}_{n+1}\otimes \boldsymbol{g}_{n+1}\\ \boldsymbol{\theta}_{n+1}=&\boldsymbol{\theta}_{n} - \frac{\tilde{\gamma}}{\sqrt{\boldsymbol{G}_{n+1} + \epsilon}}\otimes \boldsymbol{g}_{n+1} \end{aligned}

Algorithm Analysis

Comparing it with naive SGD, we find that in the update of \boldsymbol{\theta}, RMSprop replaces the original scalar learning rate \gamma with a vector: \boldsymbol{\gamma}=\frac{\tilde{\gamma}}{\sqrt{\boldsymbol{G}_{n+1} + \epsilon}} If we view this vector as the learning rate, then RMSprop has found a scheme that can assign different learning rates to each component of the parameters.

This adjustment of the learning rate is achieved through the factor \frac{1}{\sqrt{\boldsymbol{G}_{n+1} + \epsilon}}, where \boldsymbol{G}_{n+1} is the moving average of the squared gradients. Essentially, the "moving average" only makes the training process smoother; it is not the primary cause of the adjustment. The main active part is the "gradient" itself—that is, the magnitude of the gradient can be used to adjust the learning rate.

Local Minima and ODEs

To keep things simple, let’s start with a one-dimensional example. Suppose we want to find a local minimum of L(\theta). We introduce a virtual time parameter t and transform the problem into an ODE: \frac{d\theta}{dt}=\dot{\theta} = - L'(\theta) It is easy to determine that a local minimum of L(\theta) is a stable fixed point of this equation. Starting from any \theta_0, we numerically solve this ODE and expect it to eventually converge to this fixed point, thereby obtaining a local minimum.

The simplest Euler method uses \frac{\theta_{t+\gamma}-\theta_t}{\gamma} to approximate \dot{\theta}, resulting in: \frac{\theta_{t+\gamma}-\theta_t}{\gamma} = - L'(\theta_t) Which is: \theta_{t+\gamma} = \theta_t - \gamma L'(\theta_t) This is the gradient descent method, where \theta_{t+\gamma} corresponds to \theta_{n+1} and \theta_t corresponds to \theta_n, advancing by \gamma in each step.

The Idea of Variable Learning Rates

The question is, what is the best value for \gamma? From the perspective of "using \frac{\theta_{t+\gamma}-\theta_t}{\gamma} to approximate \dot{\theta}," a smaller \gamma is certainly more accurate. However, the smaller \gamma is, the more iterations are required, meaning the computational cost increases. Thus, while "the smaller, the better" is ideal, it is not practical.

Therefore, the most appropriate scheme is: each step should be just enough. But how do we know if it is enough?

Since we are using \frac{\theta_{t+\gamma}-\theta_t}{\gamma} to approximate \dot{\theta}, we must analyze the degree of approximation. According to the Taylor series, we have: \theta_{t+\gamma} = \theta_t + \gamma \dot{\theta}_t + \mathcal{O}(\gamma^2) In our case, \dot{\theta} = - L'(\theta), so we have: \theta_{t+\gamma} = \theta_t - \gamma L'(\theta_t) + \mathcal{O}(\gamma^2)

We can expect that when \gamma is relatively small, the error term \mathcal{O}(\gamma^2) < \gamma \left|L'(\theta_t)\right|. That is to say, under certain conditions, \gamma \left|L'(\theta_t)\right| itself is a measure of the error term. If we control \gamma \left|L'(\theta_t)\right| within a certain range, the error is also controlled. Namely: \gamma \left|L'(\theta_t)\right|\leq \tilde{\gamma} Where \tilde{\gamma} is a constant. We can even simply set \gamma \left|L'(\theta_t)\right|=\tilde{\gamma} (temporarily ignoring the possibility of L'(\theta_t)=0 to observe the core idea), which gives: \gamma = \frac{\tilde{\gamma}}{\left|L'(\theta_t)\right|} In this way, we adjust the learning rate through the gradient.

Moving Average Processing

Readers might criticize that substituting \gamma = \tilde{\gamma} / \left|L'(\theta_t)\right| back into the original iteration results in: \theta_{t+\tilde{\gamma} / \left|L'(\theta_t)\right|} = \theta_t - \tilde{\gamma}\cdot\text{sign}\big[L'(\theta_t)\big] You have only used the sign information of the gradient; isn’t this too wasteful? (It is too trivial: regardless of the gradient magnitude, \theta only moves by a fixed length in each iteration.)

Note that from the perspective of solving an ODE, this is not inherently wrong because the solution to an ODE is a trajectory (t, \theta(t)). In the processing above, although the movement of \theta becomes trivial, t becomes non-trivial; it is equivalent to swapping the roles of t and \theta, so it is still reasonable. However, if we care about the optimization problem—finding the minimum of L(\theta)—then the above formula is indeed somewhat trivial. If \theta only moves by a fixed length in each iteration, it becomes similar to a grid search, which is too inefficient.

Therefore, to improve this triviality while retaining the feature of using the gradient to adjust the learning rate, we can apply a "moving average" to the gradient. The result is: \begin{aligned}G_{t+\tilde{\gamma}}=& \lambda G_{t} + (1 - \lambda) |L'(\theta_t)|^2\\ \gamma =& \frac{\tilde{\gamma}}{\sqrt{G_{t+\tilde{\gamma}} + \epsilon}}\\ \theta_{t+\gamma} =& \theta_t - \gamma L'(\theta_t) \end{aligned} Here \lambda is a constant close to 1 but less than 1. In this way, G_t remains relatively stable within a certain range while retaining the characteristics of the gradient L'(\theta_t) to some extent. Using it to adjust the learning rate is a "clever" approach. To avoid confusion caused by the notation t+\tilde{\gamma} and t+\gamma, we use n and n+1 as subscripts to unify them: \begin{aligned}G_{n+1}=& \lambda G_{n} + (1 - \lambda) |L'(\theta_n)|^2\\ \gamma =& \frac{\tilde{\gamma}}{\sqrt{G_{n+1} + \epsilon}}\\ \theta_{n+1} =& \theta_n - \gamma L'(\theta_n) \end{aligned} \label{eq:rmsprop-1} This is the RMSprop algorithm mentioned at the beginning.

Furthermore, there is another important reason for the moving average: what we actually want to estimate is the mean of the squared gradients across the entire sample set. However, we can only calculate one batch at a time (so-called mini-batch gradient descent). Consequently, the result calculated each time is actually biased, and the moving average helps correct this bias to some extent.

High-dimensional Case Analysis

The discussion above covers the one-dimensional case. How do we generalize this to multiple dimensions?

Readers might think it is simple: just replace scalars with vectors. It is not quite that simple, because generalizing [eq:rmsprop-1] to high dimensions allows for at least two reasonable choices: \begin{aligned}G_{n+1}=& \lambda G_{n} + (1 - \lambda) \Vert \nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta}_n)\Vert^2\\ \gamma =& \frac{\tilde{\gamma}}{\sqrt{G_{n+1} + \epsilon}}\\ \boldsymbol{\theta}_{n+1} =& \boldsymbol{\theta}_n - \gamma \nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta}_n) \end{aligned} Or: \begin{aligned}\boldsymbol{G}_{n+1}=& \lambda \boldsymbol{G}_{n} + (1 - \lambda)\big(\nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta}_n)\otimes \nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta}_n)\big)\\ \boldsymbol{\gamma} =& \frac{\tilde{\gamma}}{\sqrt{\boldsymbol{G}_{n+1} + \epsilon}}\\ \boldsymbol{\theta}_{n+1} =& \boldsymbol{\theta}_n - \boldsymbol{\gamma}\otimes \nabla_{\boldsymbol{\theta}}L(\boldsymbol{\theta}_n) \end{aligned} \label{eq:rmsprop-n} The former uses the total norm of the gradient for accumulation, maintaining the scalar nature of the learning rate. The latter accumulates each component of the gradient separately; in this case, the adjusted learning rate becomes a vector, which is equivalent to assigning a different learning rate to each parameter. From the perspective of strict theoretical analysis, the first approach is more rigorous, but from the perspective of experimental results, the second is more effective.

The RMSprop algorithm we usually refer to is the latter [eq:rmsprop-n]. However, many practitioners of "deep learning alchemy" who prefer pure SGD criticize this vectorized learning rate for actually changing the direction of the gradient, leading to inaccurate gradients and ultimately suboptimal results. Readers who dislike vectorized learning rates might want to experiment with the former.