# 论文翻译: Learning values across many orders of magnitude

Hado van Hasselt, Arthur Guez, Matteo Hessel, Volodymyr Mnih, David Silver. “Learning values across many orders of magnitude.” In Advances in Neural Information Processing Systems, pp. 4287-4295. 2016. [pdf]

## 符号系统

$Y_t$ 目标 (target) ${\bf W}$ 标准化层权重
$\tilde{Y}_t$ 标准化后的目标 ${\boldsymbol b}$ 标准化层bias
${\boldsymbol \Sigma}_t$, ${\boldsymbol \mu}_t$ 学习到的scaleshift $h_{\boldsymbol \theta}$ 模型参数
$g(\cdot)$ 标准化函数 $f(\cdot)$ 原函数

## 第二章 Adaptive normalization with Pop-Art

We propose to normalize the targets $Y_t$, where the normalization is learned separately from the approximating function. We consider an affine transformation of the targets

We can then define a loss on a normalized function $g(X_t)$ and the normalized target $\tilde{Y}_ T$. THe unnormalized approximation for any input $x$ is then given by $f(x) = {\boldsymbol \Sigma} g(x) + {\boldsymbol \mu}$, where $g$ is the normalized function and $f$ is the unnormalized function.

Thereby, we decompose the problem of learning an appropriate normalization from learning the specific shape of the function. The two properties that we want to simultaneosly achieve are

(ART) to update scale ${\boldsymbol \Sigma}$ and shift ${\boldsymbol \mu}$ such that ${\boldsymbol \Sigma}^{-1} (Y - {\boldsymbol \mu})$ is approproately normalized, and
(POP) to preserve the outputs of the unnormalized function when we change the scale and shift.

### 2.1 POP: Preserving outputs precisely

Unless care is taken, repeated updates to the normalization might make learning harder rather than easier because the normalized targets become non-stationary. More importantly, whenever we adapt the normalization based on a certain target, this would simultaneously change the output of the unnormalized function of all inputs.

The only way to avoid changing all outputs of the unnormalized function whenever we update the scale and shift is by changing the normalized function $g$ itself simultaneously. The goal is the preserve the outputs from before the change of normalization, for all inputs. This prevents the normalization from affecting the approximation, which is appropriate because its objective is solely to make learning easier, and to leave solving the approximation itself to the optimization algorithm.

Without loss of generality the unnormalized function can be written as

It is not uncommon for deep neural networks to end in a linear layer, and the $h_ { {\boldsymbol \theta} }$ can be the output of the last (hidden) layer of non-linearities. Alternatively, we can always add a square linear layer to any non-linear function $h_ { {\boldsymbol \theta} }$ to ensure this constraint, for instance initialized as ${\bf W}_ 0 = {\bf I}$ and ${\boldsymbol b}_ 0 = {\boldsymbol 0}$.

Proposition 1. Consider a function $f: \mathbb{R}^n \rightarrow \mathbb{R}^k$ as

where $h_ {\boldsymbol \theta}: \mathbb{R}^n \rightarrow \mathbb{R}^m$ is any non-linear function of $x\in \mathbb{R}^n$, ${\boldsymbol \Sigma}$ is a $k\times k$ matrix, ${\boldsymbol \mu}$ and ${\boldsymbol b}$ are $k$-element vectors, and ${\bf W}$ is a $k\times m$ matrix. Consider any change of the scale and shift parameters from ${\boldsymbol \Sigma}$ to ${\boldsymbol \Sigma}_ \text{new}$ and from ${\boldsymbol \mu}$ to ${\boldsymbol \mu}_ \text{new}$, where ${\boldsymbol \Sigma}_ \text{new}$ is non-singular. If we then additionally change the parameters ${\bf W}$ and ${\boldsymbol b}$ to ${\bf W}_ \text{new}$ and ${\boldsymbol b}_ \text{new}$, defined by

then the outputs of the unnormalized function $f$ are preserved precisely in the sense that

For the special case of scalar scale and shift, with ${\boldsymbol \Sigma} \equiv \sigma {\bf I}$ and ${\boldsymbol \mu} \equiv \mu {\boldsymbol 1}$, the updates to ${\bf W}$ and ${\boldsymbol b}$ become ${\bf W}_ \text{new} = (\sigma/\sigma_\text{new}) {\bf W}$ and ${\boldsymbol b}_ \text{new} = (\sigma {\boldsymbol b} + {\boldsymbol \mu} - {\boldsymbol \mu}_ \text{new})/\sigma_ \text{new}$. After updating the scale and shift we can update the output of the normalized function $g_ { {\boldsymbol \theta}, {\bf W}, {\boldsymbol b} } (X_ t)$ toward the normalized $\tilde{Y}_ t$, using any learning algorithm.

Algorithm 1 is an example implementation of SGD with Pop-Art for a squared loss. It can be generalized easily to any other loss by changin the definition of ${\boldsymbol \delta}$. Notice that ${\bf W}$ and ${\boldsymbol b}$ are updated twice: first to adapt to the new scale and shift to preserve the outputs of the function, and then by SGD. The order of these updates is important because it allows us to use the new normalization immediately in the subsequent SGD update.

• 更新标准化参数(Pop)
• 更新函数拟合模型内层($h_ { {\boldsymbol \theta} }$), (算法中红框标注部分)
• 由SDG更新标准化层参数

### 2.2 ART: Adaptively rescaling targets

A natual choice is to normalize the targets to approximately have zero mean and unit variance. For clarity and conciseness, we consider scalar normalizations. If we have data $\{ ( X_ i, Y_ i ) \}_ {i=1}^t$ up to some time $t$, we then may desire

This can be generalized to incremental updates

Here $\nu_t$ estimates the second moment of the targets and $\beta_t\in [0, 1]$ is a step size. If $\nu_t -\mu_t^2$ is positive initially then it will always remain so, although to avoid issues with numerical precision it can be useful to enforce a lower bound explicitly by requiring $\nu_t -\mu_t^2 \geq \epsilon$ with $\epsilon >0$. For full equivalence to above one we can use $\beta_t = 1/t$. If $\beta_t = \beta$ is constant we get exponential moving averages, placing more weight on recent data points which is appropriate in non-stationary settings.

A constant $\beta$ has the additional benefit of never becoming negligibly small. Consider the first time a target is observed that is much larger than all previously observed targets. If $\beta_t$ is small, our statistics would adapt only slightly, and the resulting update may be large enough to harm the learning. If $\beta_t$ is not too small, the normalization can adapt to the large target before updating, potentially making learning more robust.

Proposition 2. When using updates above to adapt the normalization parameters $\sigma$ and $\mu$, the normalized targets are bounded for all $t$ by

For instance, if $\beta_t = \beta = 10^{-4}$ for all $t$, then the normalized target is guaranteed to be in $(-100, 100)$.

It is an open question whether it is uniformly best to normalize by mean and variance. In the appendix we discuss other normalization updates, based on percentiles and mini-batches, and derive correspondences between all of these.

### 2.3 An equivalence for stochastic gradient descent

We now step back and analyze the effect of the magnitude of the errors on the gradients when using regular SDG. This analysis suggests a different normalization algorithm, which has an interesting correspondence to Pop-Art SGD.

We consider SGD updates for an unnormalized multi-layer function of form $f_ { {\boldsymbol \theta}, {\bf W}, {\boldsymbol b} } (X) = {\bf W} h_ { \boldsymbol \theta}(X) + {\boldsymbol b}$. The update for the weight matrix ${\bf W}$ is

where ${\boldsymbol \delta}_ t = f_ { {\boldsymbol \theta}, {\bf W}, {\boldsymbol b} } (X) - Y_t$ is gradient of the squared loss, which we here call unnormalized error. The magnitude of this update depends linearly on the magnitude of the error, which is appropriate when the inputs are normalized, because then the ideal scale of the weights depends linearly on the magnitude of the targets.

Now consider the SGD update to the parameters of $h_ { {\boldsymbol \theta} }$, ${\boldsymbol \theta}_ t = {\boldsymbol \theta}_ {t-1} - \alpha {\boldsymbol J}_ t {\bf W}_ {t-1}^\intercal {\boldsymbol \delta}_ t$ where ${\boldsymbol J}_ t = ( \nabla h_ { {\boldsymbol \theta}, 1 } (X), \ldots, \nabla h_ { {\boldsymbol \theta}, m } (X) )^\intercal$ is the Jacobian for $h_ { {\boldsymbol \theta} }$. The magnitudes of both the weights ${\bf W}$ and the erros ${\boldsymbol \delta}$ depend linearly on the magnitude of the targets. This means that the magnitude of the update for ${\boldsymbol \theta}$ depends quaratically on the magnitude of the targets. There is no compelling reason for these updates to depend at all on these magnitudes because the weights in the top layer already ensure appropriate scaling. In other words, for each doubling of the magnitudes of the targets, the updates to the lower layers quadruple for no clear reason.

: 一般多层网络中, lower layer | upper layer的概念是根据搭建的顺序而言, 接近Input的为lower layer, 而接近Output的为upper layer。（此前对这两者理解正好相反🤣）

This analysis suggests an algorithmic solution, which seems to be novel in and of itself, in which we track the magnitude of the targets in a separate parameter $\sigma_t$, and then multiply the updates for all lower layers with a factor $\sigma_t^{-2}$. A more general version of this for matrix scallings is given in Algorithm 2.

We prove an interesting, and perhaps surprising, connection to the Pop-Art algorithm.

Proposition 3. Consider two functions defined by

where $h_ { {\boldsymbol \theta} }$ is the same differentiable function in both cases, and the functions are initialized identically, using ${\boldsymbol \Sigma}_ 0 = {\bf I}$ and ${\boldsymbol \mu}={\bf 0}$, and the same initial ${\boldsymbol \theta}_ 0$, ${\bf W}_ 0$ and ${\boldsymbol b}_ 0$. Consider updating the first function using Algorithm 1 (Pop-Art SGD) and the second using Algorithm 2 (Normalized SDG). Then, for any sequence of non-singular scales $\{ {\boldsymbol \Sigma}_ t \}_ {t=1}^\infty$ and shift $\{ {\boldsymbol \mu}_ t \}_ {t=1}^\infty$, the algorithms are equivalent in the sense that 1) the sequences $\{ {\boldsymbol \theta}_ t \}_ {t=0}^\infty$ are identical, 2) the outputs of the functions are identical, for any input.

The proposition shows a duality between normalizing the targets, as in Algorithm 1, and changing the updates, as in Algorithm 2. This allows us to gain more intuition about the algorithm. In particular, in Algorithm 2 the updates in top layer are not normalized, thereby allowing the last linear layer to adapt to the scale of the targets. That said, these methods are complementary, and it is straightforward to combing Pop-Art with other optimization algorithms than SGD.

## 总结与思考

Ph.D candidate of EIC at HUST.