交互最適化アルゴリズムとその統計的収束

外れ値にロバストなスパース線形回帰：交互最適化アルゴリ
ズムとその統計的収束
東京工業大学大学院社会理工学研究科片山翔太
統計数理研究所数理・推論研究系藤澤洋徳
線形回帰問題において，外れ値に対してロバストな回帰係数の推定を考える．ある未知
の n 次元ベクトル w∗ を加えた次のモデルを仮定する：
y = Xβ ∗ + w∗ + ε.
ここで，y は n 次元応答ベクトル, X は n × p 説明変数行列，β ∗ は未知の p 次元回帰係数
ベクトル, そして ε は E(ε) = 0, Var(ε) = σ 2 Ip をみたす p 次元誤差ベクトルである．な
お，上記の w∗ が外れ値を意味していることに注意しておく．外れ値 w∗ にスパース性を
仮定することは自然であるため，She and Owen (2011) は，チューニングパラメータ λw,i
を持つスパースペナルティ関数 P (·; λw,i ) を用いて (β ∗ , w∗ ) を次のように推定している：
∑
1
ˆ w)
ˆ = argmin ∥y − Xβ − w∥22 +
(β,
P (wi ; λw,i ).
2n
β,w
i=1
n
(1)
ここで wi は w の第 i 要素である．これにより，外れ値に対してロバストに β ∗ が推定で
きる．実際，She and Owen (2011) は従来のロバスト推定量と βˆ の関係性を与えている．
例えば, P (·; ·) として LASSO ペナルティを用いれば βˆ は Huber 型となり，SCAD ペナル
ティを用いれば Hampel 型となることなどが示されている．
しかしながら，説明変数の次元 p が大きな場合，上記の推定量 βˆ が不安定になることは
明らかである．そこで本報告では，(1) の自然な拡張である次の推定量
∑
∑
1
argmin L(β, w) :=
∥y − Xβ − w∥22 +
λβ,i |βi | +
P (wi ; λw,i )
2n
β,w
i=1
i=1
p
n
を考える．陽な解を求めることは一般に不可能なため，β, w に対して交互に繰り返し最
適化を行うと，第 k + 1 ステップでの解は次で与えられる：
β k+1 = argmin L(β, wk ),
β
wik+1 = Θ(yi − xTi β k+1 ; λw,i ).
1
ここで，xi は X の第 i 行ベクトルであり，Θ(x; λw,i ) = argminwi 2n
(x − wi )2 + P (wi ; λw,i )
である．なお，β k+1 は Coordinate Descent アルゴリズムなどで容易に計算できる．この
とき，適切にチューニングパラメータを与えると，ある条件の下で，∥β k+1 − β ∗ ∥2 の非漸
近上界が得られることを示す．得られた上界から，推定アルゴリズムの初期値の影響がス
テップサイズの指数オーダで減少するための条件や，∥β k+1 − β ∗ ∥2 の収束レートが確認
できる．詳細は当日報告する．

Download Report