An Interior-Point Method for Large-Scale L1-Regularized Least Squares

March 5, 2022

前処理付共役勾配法により、スパースな説明変数をもつリッジ回帰の学習を高速化する。リッジ回帰の目的関数は、凸関数だが微分可能ではない。また、リッジ回帰の係数はスパースになりやすい。そこで、目的関数を最小化する係数の探索を、線形不等式制約つきの凸二次計画問題とらえ、前処理付共役勾配法をつかった内点法で係数の更新方向を探索する。

$$x\in \boldsymbol{\rm R}^n$を係数、$y\in \boldsymbol{\rm R}^m$を目的変数、$A\in \boldsymbol{\rm R}^{m\times n} $をデータとする線形モデル$y=Ax+v$があるときL1正則化項つきの目的関数は以下になる。

$$ \text{minimize}\ {\\mid\mid Ax-y\mid \mid}^2\_2 +\lambda \mid\mid x \mid\mid\_1\\\\ $$

$$ \mid\mid x\mid \mid \_1 = \sum^n\_i\mid x\_i\mid $$

$$ \lambda > 0 $$

これを線形不等式制約つきの凸二次計画問題におきかえると

$$ \text{minimize} \mid\mid Ax-y\mid\mid^2\_2 + \lambda \sum^n\_{i=1}u\_i $$

$$ \text{subject to} -u\_i\le x\_i \le u\_i, i = 1,\dots n $$

まず、$-u_i\le x_i \le u_i $に対するバリア関数を導入する。

$$ \Phi (x, u) = -\sum\_{i=1}^n\log(u\_i + x\_i) - \sum^n\_{i=1}\log(u\_i-x\_i) $$

$$ \text{dom} \Phi = \\{(x, u)\in \boldsymbol{\rm R}^n \times \boldsymbol{\rm R}^n \mid\ \mid x\_i \mid < u\_i, i= 1,\dots n\\} $$

このとき、0から$\infty$までとりえるパラメタ$t$をもつ中心パスは

$$ \phi\_t(x, u) = t\mid\mid Ax - y \mid\mid^2\_2 + t \sum^n\_{i=1}\lambda u\_i +\Phi(x,u) $$

になる。

アルゴリズムは、入力に、反復終了の条件$\epsilon_{\text{rel}} > 0 $のほかパラメタ$\alpha$, $\beta$, $\mu$, $s_{\min}$をとる。はじめに、$t:= 1/\lambda, u:= 1 = (1,\dots,1)\in \boldsymbol{\rm R}^n$ で初期化する。そして以下の手順をくりかえす。

はじめに、前処理付共役勾配法で$(\Delta x, \Delta u)$をもとめる。

次に、以下をみたす最小の$k>=0$をもとめ、$s=\beta^k$により、$(x, u) := s(\Delta x, \Delta u)$と更新する。

$$ \phi\_t(x+\beta^k\Delta x, u+\beta^k\Delta u) \le \phi\_t (x, u) + \alpha \beta^k\nabla\phi\_t (x, u)^\top [\Delta x \Delta u] $$

また、$t$も更新する。

$$ t := \begin{cases} \max \\{ \mu \min \\{2n / \eta, t\\}, t\\},& s \ge s\_{\min} \\\\ t,& s < s\_{\min} \end{cases} $$

そして、$\eta / G(\upsilon)\le \epsilon_{\text{rel}}$であれば、終了し、そうでなければ最初の手順にもどる。

$$ \begin{align} \eta &= \mid\mid Ax - y \mid\mid^2\_2 + \lambda \mid\mid x \mid\mid\_1 - G(\upsilon) \\\\ G(\upsilon) &= -(1/4)\upsilon^\top \upsilon - \upsilon^\top y \\\\ \upsilon &= 2s(Ax - y) \end{align} $$

論文をこちらからダウンロードできます。