# スパース推定

---

## 目次

正則化学習における、

* 座標降下法
* 交互方向乗数法
* 双対拡張ラグランジュ関数法
* 双対交互方向乗数法

---

## 座標降下法

---

## そもそも座標降下法とは？

---

### 座標降下法

最適化問題 $$\min_{x_1, x_2 \in \Bbb R} f(x_1, x_2)$$

軸 $x_i$ を選び、$\min_{x_i} f(x_1, x_2)$ を計算する。

これを収束するまで繰り返すアルゴリズム

---

座標降下法

## (図)

---

ところで、

スパース正則化関数の多くは、座標ブロックごとに別れた関数の和として表せる

$$
\psi(\mathbb w) = \sum_{m=1}^M \psi_m(\Bbb w^{(m)}),~~~~ \Bbb w = \begin{pmatrix}\Bbb w^{(1)}\\\vdots\\\Bbb w^{(M)}\\\end{pmatrix}
$$

---

例: $L_1$正則化関数

$$
\begin{eqnarray}
\|\Bbb w\| &=& \sum_{j=1}^d|w_j|, &\Bbb w &=& \begin{pmatrix}w_1\\\vdots\\ w_d\\\end{pmatrix}\\
\psi(\mathbb w) &=& \sum_{m=1}^M \psi_m(\Bbb w^{(m)}),~~~~ &\Bbb w &=& \begin{pmatrix}\Bbb w^{(1)}\\\vdots\\\Bbb w^{(M)}\\\end{pmatrix}
\end{eqnarray}
$$

---

定義

$f$の$\Bbb w^{(m)}$に沿った偏微分

$$
\nabla_m f(\Bbb w) = \left(\frac{\partial f(\Bbb w)}{\partial w_j^{(m)}}\right)_{j\in G_m}
$$

<small>

ただし $G_m$ は $\Bbb w^{(m)}$ のインデックス集合

</small>

---

これを利用して座標降下法を行う。

$\Bbb w^{(m)}$を座標軸として選ぶことに注意する

---

### 座標降下法

最適化問題 $$\min_{x_1, x_2 \in \Bbb R} f(x_1, x_2)$$

軸 $x_i$ を選び、$\min_{x_i} f(x_1, x_2)$ を計算する。

これを収束するまで繰り返す

----

## 座標降下法

最適化問題 $$\min_{\Bbb w \in \Bbb R^d} f(\Bbb w) + \psi(\Bbb w)$$

軸 $\Bbb w^{(m)}~~(m\in \{1,\cdots ,M\})$ を選び、$\min_{\Bbb w^{(m)}} f(\Bbb w) + \psi(\Bbb w)$ を計算することで$\Bbb w_{k+1}$を得る

これを収束するまで繰り返す

----

## 座標降下法

<small>

最適化問題 $$\min_{\Bbb w \in \Bbb R^d}f(\Bbb w_k) + (\nabla f(\Bbb w_k))^T(\Bbb w - \Bbb w_k) + \frac{L}{2}\|\Bbb w - \Bbb w_k\|^2 + \psi(\Bbb w)$$

軸 $\Bbb w^{(m)}~~(m\in \{1,\cdots ,M\})$ を選び、$\min_{\Bbb w^{(m)}} f(\Bbb w_k) + (\nabla f(\Bbb w_k))^T(\Bbb w - \Bbb w_k) + \frac{L}{2}\|\Bbb w - \Bbb w_k\|^2 + \psi(\Bbb w)$ を計算することで$\Bbb w_{k+1}$を得る

これを収束するまで繰り返す

$\because ~~~L$-平滑な凸関数 $f$ は

$$
f(\Bbb w) \leq f(\Bbb w_k) + (\nabla f(\Bbb w_k))^T(\Bbb w - \Bbb w_k) + \frac{L}{2}\|\Bbb w - \Bbb w_k\|^2
$$

を満たし、右辺と左辺の差も大きくないため、上界最小化法を用いることが出来る。

</small>

----

<small>$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$最適化問題 $$\min_{\Bbb w \in \Bbb R^d}f(\Bbb w_k) + (\nabla f(\Bbb w_k))^T(\Bbb w - \Bbb w_k) + \frac{L}{2}\|\Bbb w - \Bbb w_k\|^2 + \psi(\Bbb w)$$

k回目の反復において、

$$\Bbb g^{(m)} = \nabla_mf(\Bbb w_k)$$

とする。軸 $\Bbb w^{(m)}~~(m\in \{1,\cdots ,M\})$ を選び、
$$
\Bbb w_{k+1}^{(m)} = \argmin_{\Bbb w^{(m)}\in \Bbb R}\left\{\Bbb g^{(m)T}\Bbb w^{(m)} + \frac{L}{2}\|\Bbb w^{(m)} - \Bbb w_k^{(m)}\|^2 + \psi(\Bbb w^{(m)})\right\}\\
\Bbb w_{k+1}^{(m')} = \Bbb w_{k}^{(m')}~~~(m' \neq m,~~m' \in \{1,\cdots ,M\})\\
\Bbb w_{k+1} = \begin{pmatrix}\Bbb w_{k+1}^{(1)}\\\vdots\\\Bbb w_{k+1}^{(M)}\end{pmatrix}$$
を計算する。$\Bbb w_0$はあらかじめ定めておき、これを収束するまで繰り返す

</small>

---

ところで、近接写像を定義する。$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$

$$
prox(\Bbb w | \phi) := \argmin_{\Bbb w' \in \Bbb R^d}\left\{\phi(\Bbb w') + \frac{1}{2}\|\Bbb w - \Bbb w'\|^2\right\}
$$

---

<small>$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$k回目の反復において、

$$\Bbb g^{(m)} = \nabla_mf(\Bbb w_k)$$

とする。軸 $\Bbb w^{(m)}~~(m\in \{1,\cdots ,M\})$ を選び、

$$
\Bbb w_{k+1}^{(m)} = prox\left(\Bbb w_k - \frac{\Bbb g_k}{L}|\frac{\psi}{L}\right)\\
\Bbb w_{k+1}^{(m')} = \Bbb w_{k}^{(m')}~~~(m' \neq m,~~m' \in \{1,\cdots ,M\})\\
\Bbb w_{k+1} = \begin{pmatrix}\Bbb w_{k+1}^{(1)}\\\vdots\\\Bbb w_{k+1}^{(M)}\end{pmatrix}~,~~~~~~prox(\Bbb w | \phi) := \argmin_{\Bbb w' \in \Bbb R^d}\left\{\phi(\Bbb w') + \frac{1}{2}\|\Bbb w - \Bbb w'\|^2\right\}
$$
を計算する。$\Bbb w_0$はあらかじめ定めておき、これを収束するまで繰り返す

</small>

---

## 近接写像のかたちで表記できると何がいいのか

<small>

* 正則化関数だけを元に計算が可能になるから、問題の切り分けができる

* 最小値計算が定式化できる場合が多いので、更新式の作成に困らない
+ $\newcommand{\argmin}{\mathop{\rm argmin}\limits}$例えば、$L_1$正則化なら $$prox(\Bbb q | C\|\cdot\|) = \begin{cases}q_j - C & (C \leq q_j) \\ 0 & (-C < q_j < C) \\ q_j + C & (q_j \leq -C)\end{cases}$$と書ける

</small>

---

## 交互方向乗数法

---

## ラグランジュ関数の復習

<small>

$$
\min_{\Bbb x \in \Bbb R^p,~\Bbb y \in \Bbb R^q}f(\Bbb x) + g(\Bbb y)~~s.t.~~A\Bbb x + B\Bbb y = \Bbb 0\tag1
$$

に対し、

$$
L(\Bbb x, \Bbb y, \boldsymbol\lambda) = f(\Bbb x) + g(\Bbb y) + \boldsymbol\lambda^T(A\Bbb x + B\Bbb y)~,\\
L_p(\Bbb x, \Bbb y, \boldsymbol\lambda) = L(\Bbb x, \Bbb y, \boldsymbol\lambda) + \frac{\rho}{2}\|A\Bbb x + B\Bbb y\|^2
$$

このようなラグランジュ関数と拡張ラグランジュ関数を用意し、

$$
\min_{\Bbb x \in\Bbb R^p,~\Bbb y \in \Bbb R^q}\max_{\boldsymbol \lambda}L_p(\Bbb x, \Bbb y, \boldsymbol \lambda)
$$

を計算することで、(1)における最適な$\Bbb x, \Bbb y$を得ることができる。

</small>

---

## そもそも交互方向乗数法とは？

<small>

線形等式制約付き最適化問題をとく解法。

$$
\min_{\Bbb x \in \Bbb R^p,~\Bbb y \in \Bbb R^q}f(\Bbb x) + g(\Bbb y)~~s.t.~~A\Bbb x + B\Bbb y = \Bbb 0\tag1
$$

を満たす最適な$\Bbb x, \Bbb y$は

$$
\min_{\Bbb x \in\Bbb R^p,~\Bbb y \in \Bbb R^q}\max_{\boldsymbol \lambda}L_p(\Bbb x, \Bbb y, \boldsymbol \lambda)
$$

で得られるので、

* $\Bbb x_k$ を $\min_{\Bbb x}L_p(\Bbb x, \Bbb y_{k-1}, \boldsymbol\lambda_{k-1})$ をもとに計算
* $\Bbb y_k$ を $\min_{\Bbb y}L_p(\Bbb x_k, \Bbb y, \boldsymbol\lambda_{k-1})$ をもとに計算
* $\boldsymbol \lambda_k$ を $\max_{\boldsymbol \lambda}L_p(\Bbb x_k, \Bbb y_k, \boldsymbol \lambda)$ をもとに計算

を繰り返せばよい。

</small>

----

具体的には、

$$
L_\rho(\Bbb x, \Bbb y, \boldsymbol\lambda) = f(\Bbb x) + g(\Bbb y) + \boldsymbol\lambda^T(A\Bbb x + B\Bbb y) + \frac{\rho}{2}\|A\Bbb x + B\Bbb y\|^2~
$$

に対し、交互方向乗数方を行う。<br>初期解 $\Bbb x_0 \in \Bbb R^p,~\Bbb y_0\in\Bbb R^q,~\boldsymbol \lambda,~k=0$ を定め、$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$

$$
\begin{eqnarray}
\Bbb x_{k+1} &=&\argmin_{\Bbb x \in \Bbb R^p}L_\rho(\Bbb x, \Bbb y_{k}, \boldsymbol \lambda_{k})\\
&=&\argmin_{\Bbb x \in \Bbb R^p}\left\{f(\Bbb x) + \frac{\rho}{2}\|A\Bbb x + B\Bbb y_k + \boldsymbol \lambda_k / \rho\|^2\right\}\\
~
\Bbb y_{k+1} &=&\argmin_{\Bbb y \in \Bbb R^p}L_\rho(\Bbb x_{k+1}, \Bbb y, \boldsymbol \lambda_{k})\\
&=&\argmin_{\Bbb x \in \Bbb R^p}\left\{g(\Bbb x) + \frac{\rho}{2}\|A\Bbb x_k + B\Bbb y + \boldsymbol \lambda_k / \rho\|^2\right\}\\
~
\boldsymbol\lambda_{k+1} &=& \boldsymbol\lambda_{k} + \rho(A\Bbb x_{k+1} + B\Bbb y_k)
\end{eqnarray}
$$
を、収束するまで$k=1,2,...$に対して行う。

----

更に、この交互方向乗数法を拡張する。拡張することで、$\Bbb x, \Bbb y$の更新式の関数が対角化できる。$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$

行列 $Q\succeq O,~P\succeq O$ 、パラメータ

初期解 $\Bbb x_0 \in \Bbb R^p,~\Bbb y_0\in\Bbb R^q,~\boldsymbol \lambda,~k=0$ を定め、$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$

$$
\begin{eqnarray}
\Bbb x_{k+1} &=&\argmin_{\Bbb x \in \Bbb R^p}\left\{L_\rho(\Bbb x, \Bbb y_{k}, \boldsymbol \lambda_{k}) + \frac{1}{2}\|\Bbb x - \Bbb x_k\|^2_Q\right\}\\
~
\Bbb y_{k+1} &=&\argmin_{\Bbb y \in \Bbb R^p}\left\{L_\rho(\Bbb x_{k+1}, \Bbb y, \boldsymbol \lambda_{k}) + \frac{1}{2}\|\Bbb y - y_k\|^2_P\right\}\\
~
\boldsymbol\lambda_{k+1} &=& \boldsymbol\lambda_{k} + \rho(A\Bbb x_{k+1} + B\Bbb y_k)
\end{eqnarray}
$$
を、収束するまで$k=1,2,...$に対して行う。

----

更新式をこのようにすると、$\newcommand{\argmin}{\mathop{\rm argmin}\limits}$

$$
\Bbb x_{k+1} = \argmin_{\Bbb x\in \Bbb R^p}\left\{f(\Bbb x) + \frac{\eta_1}{2}\left\|\Bbb x + \frac{1}{\eta_1}[A^T(\rho B\Bbb y_k + \boldsymbol\lambda_k)]\right\|\right\}
$$

---

特に、今回の最適化問題は

$$
\begin{eqnarray}
\min_{\Bbb w \in \Bbb R^d} ~~~& f(\Bbb x) + \psi(\Bbb y)\\
s.t. ~~~& \Bbb x - \Bbb y = \Bbb 0
\end{eqnarray}
$$

のように書けるため、損失関数の最適化と正則化項の正則化をわけることができる。

---

また、 正則化項は前述の理由で、近接写像が計算しやすい形のものを選ぶと便利。

よって、元の正則化関数を、近接写像が計算しやすい関数$\psi$と行列$B$に分離したほうが便利なことがあるので

$$
\begin{eqnarray}
\min_{\Bbb w \in \Bbb R^d} ~~~& f(\Bbb x) + \psi(\Bbb y)\tag2 \\
s.t. ~~~& B\Bbb x - \Bbb y = \Bbb 0
\end{eqnarray}
$$

について考えたほうが問題が解きやすい。

---
<!--

交互方向乗数法を(2)に適用する

---

<small>

$$
\min_{\Bbb x \in \Bbb R^p,~\Bbb y \in \Bbb R^q}f(\Bbb x) + g(\Bbb y)~~s.t.~~B\Bbb x - \Bbb y = \Bbb 0\tag1
$$

を満たす最適な$\Bbb x, \Bbb y$は

$$
\min_{\Bbb x \in\Bbb R^p,~\Bbb y \in \Bbb R^q}\max_{\boldsymbol \lambda}L_p(\Bbb x, \Bbb y, \boldsymbol \lambda)
$$

で得られるので、

* $\Bbb x_k$ を $\min_{\Bbb x}L_p(\Bbb x, \Bbb y_{k-1}, \boldsymbol\lambda_{k-1})$ をもとに計算
* $\Bbb y_k$ を $\min_{\Bbb y}L_p(\Bbb x_k, \Bbb y, \boldsymbol\lambda_{k-1})$ をもとに計算
* $\boldsymbol \lambda_k$ を $\max_{\boldsymbol \lambda}L_p(\Bbb x_k, \Bbb y_k, \boldsymbol \lambda)$ をもとに計算

を繰り返せばよい。

</small>

---

-->
<!--

## 今後の展望

* 近接勾配法の収束性について軽く書く
* 交互方向乗数法しっかり埋める
* 実験は重回帰のなにかをLassoでとくつもり
* その他２つのアルゴリズムにおいては時間を読んで、可能なら片方採用する
* スライドをpower pointでつくりかえる