近接勾配法#

読み: きんせつこうばいほう
英名: Proximal Gradient Method

近接点法と勾配法を組み合わせた反復法で，次の構造を持つ最適化問題を対象とする．

(42)#\[\min_x \varphi(x) = f(x) + g(x).\]

ここで，\(f\) は滑らかな凸関数，\(g\) は滑らかとは限らない”単純”な凸関数とする．\(g\) の例としては凸集合 \(S\) についての表示関数 \(\delta_S(x) = 0 \ (x \in S), \ +\infty \ (x \notin S)\) や，機械学習の分野で良く表れる正則化項 \({\|x\|}_1\)，\({\|x\|}_2\) などがある．一般に目的関数 \(\varphi\) は滑らかでは無いので，劣勾配法のような収束の遅い手法しか適用できない様に見えるが，\(\varphi\) が上記のような特徴を持つ二種の関数 \(f\) と \(g\) の和である点に着目した手法が近接勾配法である．近接勾配法の \(t\) 反復目における更新は次の通りである．

(43)#\[x_{t+1} = \mathrm{argmin}_x \left(g(x) + f(x_t) + \nabla f(x_t)^\top(x-x_t) + \displaystyle\frac{1}{2\eta_t}\|x-x_t\|_2^2 \right). \ (1)\]

ただし，\(g\) は”単純”なので，この更新則は閉形式で表せるものとする．この反復は関数 \(f\) の一次近似モデルと \(g\) を足し合わせたものを \(x_t\) の近傍で最小化していることになる．\(f\) は滑らかなのでその勾配が利用でき，\(g\) については単純な構造を持つ関数なため劣勾配で近似することなくそのまま最小化が可能である．上述の \(L1\) 正則化項 \({\|x\|}_1\) には最適解の非零要素数を減らす意図がある様に，\(g\) には解にある種の構造を導入する目的がある場合が多い．それにも関らず劣勾配法を \(\varphi\) に適用してしまうと，その収束の遅さから \(g\) が示す構造を見つける事が困難となるが，近接勾配法はその構造を常に意識した更新をする．この様に，近接点法には劣勾配法より良い収束性があるだけでなく，解の構造の発見に優れているという特徴を持つ．特に \(L1\) 正則化の場合の近接勾配法は ISTA (Iterative Shrinkage Thresholding Algorithm) と呼ばれる．

近接勾配法と射影付き勾配法#

近接勾配法は，凸関数 \(h\) に対して proximal operator という写像

(44)#\[prox_h(x) = \ \mathrm{argmin}_u \left( h(u) + \displaystyle\frac{1}{2} \| u -x \|_2^2 \right)，\]

を用いて

(45)#\[x_{t+1} = prox_{\eta_t g} \left(x_t - \eta_t \nabla f(x_t)\right) = \ \mathrm{argmin}_u \left( \eta_t g(u) + \displaystyle\frac{1}{2} \left\| u - \left(x_t - \eta_t \nabla f(x_t)\right) \right\|_2^2 \right) \ (2)\]

とも表せる．実際に，凸関数の最適解における劣微分は \(0\) を含むという最適性条件を (1)，(2) に適用すると (1) の解 \(x_*\) では， \(x_*\) における \(g\) の劣勾配を \(\xi_{x_*}\) とすると

(46)#\[\xi_{x_*} + \nabla f(x_t) + \displaystyle\frac{1}{\eta_t} (x_* - x_t) = 0, (3)\]

を満たし，(2) の解 \(u_*\) においては， \(u_*\) における \(g\) の劣勾配を \(\xi_{u_*}\) とすると

(47)#\[\eta_t \xi_{u_*} + \left( u_* - \left( x_t - \eta_t \nabla f(x_t) \right) \right) = 0, (4)\]

となる．(4) を更に \(\eta_t\) で割れば

(48)#\[\xi_{u_*} + \nabla f(x_t) + \displaystyle\frac{1}{\eta_t}(u_* - x_t) = 0 \ (4')\]

となるので，両者の解が一致する事が確認できる．また (2) の反復は \(f\) について勾配法を適用した後に proximal operator を作用させた事になる．\(g\) が上述の標示関数 \(\delta_S\) の場合 proximal operator は凸集合 \(S\) への直交射影と同等なため，近接勾配法は射影付き勾配法の一般形と見なす事もできる．

近接勾配法の発展と応用#

近接勾配法の収束速度を目的関数値の最適値との差で表した場合，その速度は適当な仮定のもと \(O(1 / t)\) である事が知られているが，近接勾配法を \(O(1 / t^2)\) まで加速させた手法もある．Nesterov は三種の加速法を提案 [2, 3, 4] し， Beck らは ISTA の加速版である FISTA (Fast Iterative Shrinkage Thresholding Algorithm) [5] を提案した．これら加速法については，[19] でも詳しく解説されている．

近年，近接勾配法は機械学習分野においても多く応用されており，学習における各反復において唯一つの学習データしか用いないオンライン学習への拡張もなされている．例えば有名な手法として FOBOS (Forward Backward Splitting) [6] がある．また FOBOS よりも解の構造発見に優れた手法として RDA (Regularized Dual Averaging) [7] もある．

近接勾配法

目次

近接勾配法#

近接勾配法と射影付き勾配法#

近接勾配法の発展と応用#