Exponentiated Gradient Descent + Meta-Learning = Adaptive Learning Rate

指数梯度下降 + 元学习 = 自适应学习率 苏剑林 · 2022-03-03 · Mathematics optimization gradient optimizer

A couple of days ago I came across a Google paper, Step-size Adaptation Using Exponentiated Gradient Updates, and learned some new concepts from it, so let me write them up here and share them. There are two main pieces of content: one is exponentiated gradient descent for non-negative optimization, and the other is a learning-rate adjustment algorithm based on the idea of meta-learning. Both are quite interesting, and readers who are curious might want to take a look themselves.

Exponentiated Gradient Descent

Most people are probably familiar with plain gradient descent, which refers to minimizing an unconstrained function $\mathcal{L}(\boldsymbol{\theta})$ using the following update rule:

\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta}_t)\end{equation}

where $\eta$ is the learning rate. However, many tasks are not unconstrained; for the simplest case of non-negativity constraints, we can instead use the following update rule:

\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t \odot \exp\left(- \eta\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta}_t)\right)\label{eq:egd}\end{equation}

Here $\odot$ denotes elementwise multiplication (the Hadamard product). It's easy to see that as long as the initial $\boldsymbol{\theta}_0$ is non-negative, $\boldsymbol{\theta}_t$ will remain non-negative throughout the update process — this is what's called "exponentiated gradient descent" for non-negative constrained optimization. more

How should we understand this "exponentiated gradient descent"? It's not hard — we just need to convert it back to the unconstrained case and derive it from there. If $\boldsymbol{\theta}$ is non-negative, then $\boldsymbol{\varphi}=\log\boldsymbol{\theta}$ can be either positive or negative, so we can set $\boldsymbol{\theta}=e^{\boldsymbol{\varphi}}$, turning it into an unconstrained optimization problem in terms of $\boldsymbol{\varphi}$, which we can then solve with ordinary gradient descent:

\begin{equation}\boldsymbol{\varphi}_{t+1} = \boldsymbol{\varphi}_t - \eta\nabla_{\boldsymbol{\varphi}}\mathcal{L}(e^{\boldsymbol{\varphi}_t}) = \boldsymbol{\varphi}_t - \eta e^{\boldsymbol{\varphi}_t}\odot\nabla_{e^{\boldsymbol{\varphi}}}\mathcal{L}(e^{\boldsymbol{\varphi}_t})\end{equation}

We regard the $e^{\boldsymbol{\varphi}_t}\odot$ part of the gradient as merely rescaling the learning rate, so it isn't essential, and we drop it to get

\begin{equation}\boldsymbol{\varphi}_{t+1} = \boldsymbol{\varphi}_t - \eta \nabla_{e^{\boldsymbol{\varphi}}}\mathcal{L}(e^{\boldsymbol{\varphi}_t})\end{equation}

Exponentiating both sides gives

\begin{equation}e^{\boldsymbol{\varphi}_{t+1}} = e^{\boldsymbol{\varphi}_t}\odot\exp\left( - \eta \nabla_{e^{\boldsymbol{\varphi}}}\mathcal{L}(e^{\boldsymbol{\varphi}_t})\right)\end{equation}

Substituting back for $\boldsymbol{\theta}=e^{\boldsymbol{\varphi}}$ recovers equation $\eqref{eq:egd}$.

Adjusting the Learning Rate via Meta-Learning

When it comes to Meta Learning, most readers, like myself, have probably heard the term often but rarely worked with it directly. Roughly speaking, the relationship between ordinary machine learning and meta-learning is like the relationship between a "function" and a "functional" in mathematics — a functional is a "function of functions," while meta-learning is "learning how to learn." That is, it's a methodology about the process of "learning" itself. What we're about to introduce is a good example: "using gradient descent to adjust gradient descent."

Let's start from ordinary gradient descent. Denote the gradient of the objective function $\mathcal{L}$ as $\boldsymbol{g}$, so the update formula is

\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta\boldsymbol{g}_t\end{equation}

We want to adjust the learning rate for each component individually, so we introduce a non-negative variable $\boldsymbol{\nu}$ of the same size as the parameters, and modify the update formula as

\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta\boldsymbol{\nu}_{t+1}\odot\boldsymbol{g}_t\label{eq:update}\end{equation}

So, what rule should $\boldsymbol{\nu}$ follow when it's updated? Remember that our ultimate goal is still to minimize $\mathcal{L}$, so the update rule for $\boldsymbol{\nu}$ should also be gradient descent — and since $\boldsymbol{\nu}$ is required to be non-negative, we use exponentiated gradient descent here:

\begin{equation}\boldsymbol{\nu}_{t+1} = \boldsymbol{\nu}_t \odot\exp\left(- \gamma\nabla_{\boldsymbol{\nu}_t}\mathcal{L}\right)\label{eq:update-nu}\end{equation}

Note that $\mathcal{L}$ is nominally only a function of $\boldsymbol{\theta}$, but according to $\eqref{eq:update}$, at time step $t$ we have $\boldsymbol{\theta}_t = \boldsymbol{\theta}_{t-1} - \eta\boldsymbol{\nu}_t\odot\boldsymbol{g}_{t-1}$, so by the chain rule,

\begin{equation}\nabla_{\boldsymbol{\nu}_t}\mathcal{L} = -\eta\boldsymbol{g}_{t-1} \odot\nabla_{\boldsymbol{\theta}_t}\mathcal{L}= -\eta\boldsymbol{g}_{t-1} \odot\boldsymbol{g}_t\end{equation}

Substituting this into the update formula $\eqref{eq:update-nu}$ for $\nu$ gives

\begin{equation}\boldsymbol{\nu}_{t+1} = \boldsymbol{\nu}_t \odot\exp\left( \gamma\eta\boldsymbol{g}_{t-1} \odot\boldsymbol{g}_t\right)\end{equation}

Combining $\gamma\eta$ into a single parameter $\gamma$, the overall update formula for the model becomes:

\begin{equation}\begin{aligned}&\boldsymbol{\nu}_{t+1} = \boldsymbol{\nu}_t \odot\exp\left( \gamma\boldsymbol{g}_{t-1} \odot\boldsymbol{g}_t\right) \\ &\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta\boldsymbol{\nu}_{t+1}\odot\boldsymbol{g}_t\end{aligned}\end{equation}

If $\boldsymbol{\nu}$ is initialized to all ones, then we'll have

\begin{equation}\boldsymbol{\nu}_{t+1} = \exp\left(\gamma\sum_{k=1}^t\boldsymbol{g}_{k-1} \odot\boldsymbol{g}_k\right)\end{equation}

We can see that the underlying idea of this method's learning-rate adjustment is: if the gradient of a particular component tends to have the same sign across two consecutive steps, then the corresponding accumulated term will be positive, meaning we can afford to increase the learning rate slightly; if the gradient tends to flip sign across two consecutive steps, then the corresponding accumulated term is likely negative, meaning we should shrink the learning rate slightly.

Note that this is quite different from how Adam adjusts the learning rate. Adam's idea is that if the gradient of a component has been small for a long time, that means the corresponding parameter probably hasn't been learned well yet, so it tries to enlarge its learning rate. Each approach has its own logic, in its own way.

A Brief Summary

This post is basically a set of notes on two concepts: "exponentiated gradient descent" and "meta-learning-based learning rate adjustment." Exponentiated gradient descent is a simple and effective scheme for non-negative constrained optimization, while meta-learning-based learning rate adjustment is an easy-to-understand application of meta-learning. When introducing the latter, I simplified things a bit compared to the form used in the original paper, but the underlying idea is the same.