近接勾配法のオンライン学習アルゴリズム

# **はじめに**
以前の記事で紹介したRDAのように、L1正則化によりスパース解が得られるオンライン学習アルゴリズムはいろいろ提案されています。今回はRDAに似たアルゴリズムであり、AISTATS 2011[1]とKDD 2013[2]でGoogleの研究者が発表したFTRL-Proximalアルゴリズムについて紹介します。
後半はFTRL-Proximalの解説がメインですが、「近接勾配法のバッチ更新式」とRDAやFTRL-Proximalを対比することで理解しやすくなると考え、タイトルは「近接勾配法のオンライン学習アルゴリズム」としています。

肝心のRDAとFTRL-Proximalのどちらがいいの？というところですが、~~論文の結果を見る限りたいして変わらない~~大規模な実データでFTRL-ProximalがFOBOSとRDAの両方に優位に上回ったよ、と書かれています（~~ひとつの自前データセットでだけな。ほかの小～中規模パブリックデータ6つでは全敗な件~~）。FOBOSについては記事を書いていませんが、FTRL-ProximalはFOBOSとRDAのハイブリッドアルゴリズムとして位置付けられています。

# **近接勾配法のオンライン学習アルゴリズム**
## **近接勾配法のバッチ更新式**
まず近接勾配法の復習をしつつ、オンライン学習アルゴリズムと対比しやすいように更新式を表記してみます。近接勾配法は

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm prox}_{\eta g}\left( \boldsymbol{w}_t - \eta \bigtriangledown f(\boldsymbol{w}_t) \right) \\
{\rm prox}_g(\boldsymbol{y})
 &\equiv {\rm argmin}_\boldsymbol{x} \left(
  g(\boldsymbol{x}) + \frac{1}{2} \parallel \boldsymbol{x} - \boldsymbol{y} \parallel^2
 \right)
\end{align}
```
でした。代入すると

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w}
 \left(
  \bigtriangledown f(\boldsymbol{w}_t)^T \boldsymbol{w} + g(\boldsymbol{w}) + \frac{1}{2\eta} \parallel \boldsymbol{w} - \boldsymbol{w}_t \parallel^2
 \right)
\end{align}
```
です。オンライン学習アルゴリズムと対比しやすいように、サンプル$n$に対する「1サンプルあたり」の損失関数$f_n$と正則化項$\psi$を導入して

```math
\begin{align}
f(\boldsymbol{w}) &= \sum_{n=1}^N f_n(\boldsymbol{w}) \\
g(\boldsymbol{w}) &= N \lambda \psi(\boldsymbol{w})
\end{align}
```
とします。$\psi$はL1やL2ノルム、$\lambda$は「1サンプルあたり」の正則化パラメータだと思うとイメージしやすいと思います。
すると

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w}
 \left\{
  \sum_{n=1}^N \bigtriangledown f_n(\boldsymbol{w}_t)^T \boldsymbol{w} + N \lambda \psi(\boldsymbol{w}) + \frac{1}{2\eta} \parallel \boldsymbol{w} - \boldsymbol{w}_t \parallel^2
 \right\}
\end{align}
```
となります。

バッチ更新式なので、
- **全てのサンプル$n$（$n=1,\cdots,N$）について現在の点$\boldsymbol{w}\_t$での勾配$\bigtriangledown f_n(\boldsymbol{w}_t)$を計算**しています。
- **現在の点$\boldsymbol{w}_t$からの二乗誤差**にペナルティを掛けています。

## **名無しのオンライン学習アルゴリズム**
バッチ更新式のように現在の点$\boldsymbol{w}_t$での勾配を**全てのサンプルについて**計算するのは大変なので、現在の点$\boldsymbol{w}_t$についての勾配を**現在のサンプル$t$についてのみ**計算して更新するオンライン学習を考えてみます。

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w} \left\{
    \sum_{s=1}^t \bigtriangledown f_s(\boldsymbol{w}_s)^T \boldsymbol{w}
    + t \lambda \psi(\boldsymbol{w})
    + \frac{1}{2\eta_t} \parallel \boldsymbol{w} - \boldsymbol{w}_t \parallel^2
   \right\}
\end{align}
```
なんとなくワークしそうな気がしますね。実際にワークするのかどうかは示す必要がありますが。

## **確率的近接勾配法： Regularized Dual Averaging（RDA）**
以前の記事で紹介したRDAは、「名無しのオンライン学習アルゴリズム」の第三項をさらに単純な$\frac{1}{2\eta_t} \parallel \boldsymbol{w} \parallel^2$として**原点からの二乗誤差**にペナルティを掛けた更新式：

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w} \left\{
    \sum_{s=1}^t \bigtriangledown f_s(\boldsymbol{w}_s)^T \boldsymbol{w}
    + t \lambda \psi(\boldsymbol{w})
    + \frac{1}{2\eta_t} \parallel \boldsymbol{w} \parallel^2
   \right\} \\
  &= {\rm prox}_{t \eta_t \lambda \psi}(-\eta_t \boldsymbol{g}_{1:t})
\end{align}
```
で、Regret解析によって収束性が示されています。ここで記載の簡略化のため$\boldsymbol{g}\_{1:t} \equiv \sum_{s=1}^t \boldsymbol{g}\_s$、$\boldsymbol{g}\_t \equiv \bigtriangledown f_t(\boldsymbol{w}_t) $を導入しています。

## **FTRL-Proximalアルゴリズム**
FTRL-Proximalアルゴリズムの更新式は次のようになります。

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w} \left\{
    \sum_{s=1}^t \bigtriangledown f_s(\boldsymbol{w}_s)^T \boldsymbol{w}
    + t \lambda \psi(\boldsymbol{w})
    + \frac{1}{2} \sum_{s=1}^t \sigma_s \parallel \boldsymbol{w} - \boldsymbol{w}_s \parallel^2
   \right\}
\end{align}
```
RDAとの違いは、第三項で**過去の系列$\boldsymbol{w}_s$（$s=1,\cdots,t$）からの二乗誤差**にペナルティを掛けている点です。
$\eta_t$の代わりに$\sigma_t$が導入されていますが、これは

```math
\begin{align}
\sigma_t
 \equiv \left\{
 \begin{array}{ll}
  \frac{1}{\eta_t} - \frac{1}{\eta_{t-1}} & t \geq 2 \\
  \frac{1}{\eta_1} & t = 1
 \end{array}
 \right.
\end{align}
```
と設定されており、ペナルティ項の係数の和$\sum_{s=1}^t \sigma_s$はRDAと同じく$\frac{1}{\eta_t}$となります。記載の簡略化のため$\boldsymbol{g}\_{1:t} \equiv \sum_{s=1}^t \boldsymbol{g}\_s$、$\boldsymbol{g}\_t \equiv \bigtriangledown f_t(\boldsymbol{w}_t) $を導入して

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w} \left\{
    \sum_{s=1}^t \bigtriangledown f_s(\boldsymbol{w}_s)^T \boldsymbol{w}
    + t \lambda \psi(\boldsymbol{w})
    + \frac{1}{2} \sum_{s=1}^t \sigma_s \parallel \boldsymbol{w} - \boldsymbol{w}_s \parallel^2
   \right\} \\
 &= {\rm argmin}_\boldsymbol{w} \left\{
     \boldsymbol{g}_{1:t}^T \boldsymbol{w}
     + t \lambda \psi(\boldsymbol{w})
     + \frac{1}{2} \sum_{s=1}^t \sigma_s \parallel \boldsymbol{w} - \boldsymbol{w}_s \parallel^2
    \right\} \\
 &= {\rm argmin}_\boldsymbol{w} \left\{
     \boldsymbol{g}_{1:t}^T \boldsymbol{w}
     + t \lambda \psi(\boldsymbol{w})
     + \frac{1}{2} \sum_{s=1}^t \sigma_s (\parallel \boldsymbol{w} \parallel^2 - 2 \boldsymbol{w}_s^T \boldsymbol{w} + \parallel \boldsymbol{w}_s \parallel^2)
    \right\} \\
 &= {\rm argmin}_\boldsymbol{w} \left\{
    \bigg( \boldsymbol{g}_{1:t} - \sum_{s=1}^t \sigma_s \boldsymbol{w}_s \bigg)^T \boldsymbol{w}
     + t \lambda \psi(\boldsymbol{w})
     + \frac{1}{2} \sum_{s=1}^t \sigma_s \parallel \boldsymbol{w} \parallel^2
    \right\} \\
 &= {\rm argmin}_\boldsymbol{w} \left\{
    \boldsymbol{z}_t^T \boldsymbol{w}
     + t \lambda \psi(\boldsymbol{w})
     + \frac{1}{2 \eta_t} \parallel \boldsymbol{w} \parallel^2
    \right\} \\
 &= {\rm argmin}_\boldsymbol{w} \left\{
       t \lambda \psi(\boldsymbol{w})
     + \frac{1}{2 \eta_t} \parallel \boldsymbol{w} + \eta_t \boldsymbol{z}_t \parallel^2
    \right\} \\
 &= {\rm prox}_{t \eta_t \lambda \psi}(-\eta_t \boldsymbol{z}_t) \\
\boldsymbol{z}_t
 &\equiv \boldsymbol{g}_{1:t} - \sum_{s=1}^t \sigma_s \boldsymbol{w}_s
\end{align}
```
RDAは平均勾配に対してProximal Operatorを適用するだけ：

```math
\begin{align}
\boldsymbol{w}_{t+1} = {\rm prox}_{t \eta_t \lambda \psi}(- \eta_t \boldsymbol{g}_{1:t})
\end{align}
```
でしたが、FTRL-Proximalアルゴリズムも$\boldsymbol{z}\_t = \boldsymbol{g}\_{1:t} - \sum_{s=1}^t \sigma_s \boldsymbol{w}_s$に対してProximal Operatorを適用するだけ：

```math
\begin{align}
\boldsymbol{w}_{t+1} = {\rm prox}_{t \eta_t \lambda \psi}(- \eta_t \boldsymbol{z}_t)
\end{align}
```
です。Proximal Operatorがわかっている正則化項であれば、RDAもFTRL-Proximalアルゴリズムも超簡単に導出できますね。

# **FTRL-Proximalアルゴリズムの実際**
ここまでは正則化項を明示的に定めずに展開を追ってきました。[2]ではL1/L2正則化の場合についての具体的なアルゴリズムが記載されていたり、特徴量別に異なる学習率を用いるAdaGradが導入されています。

## **L1正則化の場合**
[1]では$\psi(\boldsymbol{w})$は上記のように更新1回あたりの正則化項で記載されているのですが、[2]では更新回数に関わらない固定の正則化項$\Psi(\boldsymbol{w})=t \psi(\boldsymbol{w})$が使われています。
この場合

```math
\begin{align}
\boldsymbol{w}_{t+1}
 &= {\rm argmin}_\boldsymbol{w} \left\{
     \boldsymbol{g}_{1:t}^T \boldsymbol{w}
     + \lambda \Psi(\boldsymbol{w})
     + \frac{1}{2} \sum_{s=1}^t \sigma_s \parallel \boldsymbol{w} - \boldsymbol{w}_s \parallel^2
    \right\} \\
 &= {\rm prox}_{\eta_t \lambda \Psi}(-\eta_t \boldsymbol{z}_t)
\end{align}
```
となります。この式を用いる場合、更新回数で1万で調整した正則化パラメータ$\lambda$は、更新回数を10万にすると効き目が10分の1になり、正則化が効かなくなっていくことに注意が必要です。
ここでは論文の表記に合わせて、導出を追ってみます。

L1正則化（$\psi(\boldsymbol{w}) = \parallel \boldsymbol{w} \parallel_1$）の場合

```math
\begin{align}
\left( {\rm prox}_{\lambda \parallel \cdot \parallel_1}(\boldsymbol{x}) \right)_i
 = \left\{
    \begin{array}{ll}
     x_i - \lambda & x_i > \lambda \\
     0 & |x_i| \leq \lambda \\
     x_i + \lambda & x_i < -\lambda
    \end{array}
   \right.
\end{align}
```
なので

```math
\begin{align}
w_{t+1,i}
 &= \left\{
    \begin{array}{ll}
     -\eta_t z_{ti} - \eta_t \lambda_1 & -\eta_t z_{ti} > \eta_t \lambda_1 \\
     0 & |\eta_t z_{ti}| \leq \eta_t \lambda_1 \\
     -\eta_t z_{ti} + \eta_t \lambda_1 & -\eta_t z_{ti} < -\eta_t \lambda_1
    \end{array}
   \right. \\
 &= \left\{
    \begin{array}{ll}
     -\eta_t (z_{ti} + \lambda_1) & -z_{ti} > \lambda_1 \\
     0 & |z_{ti}| \leq \lambda_1 \\
     -\eta_t (z_{ti} - \lambda_1) & -z_{ti} < -\lambda_1
    \end{array}
   \right. \\
 &= \left\{
    \begin{array}{ll}
     0 & |z_{ti}| \leq \lambda_1 \\
     -\eta_t (z_{ti} - {\rm sign}(z_{ti}) \lambda_1) & {\rm otherwise}
    \end{array}
   \right.
\end{align}
```
となり、論文に記載の表記が得られます。

## **特徴量別学習率**
オンライン学習の学習率は、$\eta_t = \frac{1}{\sqrt{t}}$がよく用いられます。しかしながら低頻度で値が変わる特徴量（ほとんどの場合に$0$でごくたまに$1$になるような特徴量）の場合にこれを適用してしまうと、実用上の限られた反復回数学習する場合にはその「ごくたまに」が学習の初期なのか後半なのかで学習結果が大きく変わってきてしまいます。

そこでAdaGradの学習率：

```math
\begin{align}
\eta_{ti} = \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^t g_{si}^2}}
\end{align}
```
を用います。アルゴリズム表記の簡略化のため

```math
\begin{align}
n_{ti} \equiv \sum_{s=1}^t g_{si}^2
\end{align}
```
を導入すると、

```math
\begin{align}
\eta_{ti} = \frac{\alpha}{\beta + \sqrt{n_{ti}}}
\end{align}
```
であり、

```math
\begin{align}
\sigma_{ti}
 &= \frac{1}{\eta_t} - \frac{1}{\eta_{t-1}} \\
 &= \frac{1}{\alpha}\left( \sqrt{n_{t-1,i}+g_{ti}^2} - \sqrt{n_{t-1,i}} \right)
\end{align}
```
となります。

特徴量別学習率はFTRL-Proximalだから導入できる、というわけではなくRDAでも同様に導入できるかと思います。

## **特徴量別学習率のL1正則化FTRL-Proximalアルゴリズム**
$\boldsymbol{z}_t$の更新式は

```math
\begin{align}
\boldsymbol{z}_t
 &\equiv \boldsymbol{g}_{1:t} - \sum_{s=1}^t \sigma_s \boldsymbol{w}_s \\
 &= \boldsymbol{z}_{t-1} + \boldsymbol{g}_t - \sigma_t \boldsymbol{w}_t
\end{align}
```
であり、これを特徴量別に適用することを考えると

```math
\begin{align}
z_{ti}
 &= z_{t-1,i} + g_{ti} - \sigma_{ti} w_{ti}
\end{align}
```
となります。

以上より、特徴量別学習率のFTRL-Proximalアルゴリズム：

```math
\begin{align}
w_{ti}
 &= \left\{
    \begin{array}{ll}
     0 & |z_{ti}| \leq \lambda_1 \\
     - \left( \frac{\beta + \sqrt{n_{ti}}}{\alpha} \right)^{-1} (z_{ti} - {\rm sign}(z_{ti}) \lambda_1) & {\rm otherwise}
    \end{array}
   \right. \\
\sigma_{ti}
 &= \frac{1}{\alpha}\left( \sqrt{n_{t-1,i}+g_{ti}^2} - \sqrt{n_{t-1,i}} \right) \\
z_{ti}
 &= z_{t-1,i} + g_{ti} - \sigma_{ti} w_{ti} \\
n_{ti}
 &= n_{t-1,i} + g_{ti}^2
\end{align}
```
が得られます。

## **特徴量別学習率のL1/L2正則化FTRL-Proximalアルゴリズム**
L1正則化だけでなくL2正則化も導入すると、論文のAlgorithm 1と同じ

```math
\begin{align}
w_{ti}
 &= \left\{
    \begin{array}{ll}
     0 & |z_{ti}| \leq \lambda_1 \\
     - \left( \frac{\beta + \sqrt{n_{ti}}}{\alpha} + \lambda_2 \right)^{-1} (z_{ti} - {\rm sign}(z_{ti}) \lambda_1) & {\rm otherwise}
    \end{array}
   \right. \\
\sigma_{ti}
 &= \frac{1}{\alpha}\left( \sqrt{n_{t-1,i}+g_{ti}^2} - \sqrt{n_{t-1,i}} \right) \\
z_{ti}
 &= z_{t-1,i} + g_{ti} - \sigma_{ti} w_{ti} \\
n_{ti}
 &= n_{t-1,i} + g_{ti}^2
\end{align}
```
となります。

# **おわりに**
RDAとFTRL-Proximalどちらがいいか、というのは論文の結果を見る限りたいして変わらないんじゃないかな、という気がするので、まずは実装の簡単なRDAから、余力があってちょびっとでも改善したい！という場合にはFTRL-Proximalも試してみる、という使い方が良いように思われます。

# **参考文献**
[1] McMahan, H. Brendan. "Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization." (2011). 
[2] McMahan, H. Brendan, et al. "Ad click prediction: a view from the trenches." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.