トップ > 数理計画用語集 > 近接勾配法

数理計画用語集

近接勾配法

読み:きんせつこうばいほう
英名:Proximal Gradient Method
関連確率的勾配降下法ビッグデータ

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

$$ \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$ 反復目における更新は次の通りである.

$$ 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 という写像

$$ prox_h(x) = \ \mathrm{argmin}_u \left( h(u) + \displaystyle\frac{1}{2} \| u -x \|_2^2 \right), $$

を用いて

$$ 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_*}$ とすると

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

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

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

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

$$ \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 は三種の加速法を提案し [3],[4],[6], Beck らは ISTA の加速版である FISTA (Fast Iterative Shrinkage Thresholding Algorithm) [1] を提案した.これら加速法については,[5],[8]でも詳しく解説されている.

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

[参考]
[1] A.Beck, M.Teboulle, Fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J, Imaging Sciences, 2008.
[2] J.Duchi, Y.Singer, Efficient Online and Batch Learning Using Forward Backward Splitting, Jounal of Machine Learning Research, 10, 2009.
[3] Y.Nesterov, A method for unconstrained convex minimization problem with the rate of convergence $O(1/k^2)$, Doklady AN USSR, 269, 1983.
[4] Y.Nesterov, On an approach to the construction of optimal methods of minimization of smooth convex functions, Ekonom. i. Mat. Metody, 24, 1988.
[5] Y.Nesterov, Introductory lectures on convex optimization: Basic course, Kluwer, Boston, 2003.
[6] Y.Nesterov, Smooth minimization of non-smooth functions, Math.Program., Serie A, 103, 2005.
[7] Y.Nesterov, Gradient methods for minimizing composite objective function, Technical Report CORE Universite Catholique de Louvain, 2007.
[8] P.Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J., 2008.
[9] L.Xiao, Dual Averaging methods for regularized stochastic learning and online optimization. In Advances in Neural Information Processing Systems, 23, 2009.