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

数理計画用語集

近接勾配法

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

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

equation

ここで,equationは滑らかな凸関数equationは滑らかとは限らない”単純”な凸関数とする.equationの例としては凸集合equationについての表示関数equationや,機械学習の分野で良く表れる正則化項 equationequationなどがある.一般に目的関数equationは滑らかでは無いので,劣勾配法のような収束の遅い手法しか適用出来ない様に見えるが,equationが上記のような特徴を持つ二種の関数equationequationの和である点に着目した手法が近接勾配法である.近接勾配法のequation反復目における更新は次の通りである.

equation (1)

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

 近接勾配法は proximal operator という写像

equation

を用いて

equation (2)

とも表せる.実際に,凸関数最適解における劣微分はequationを含むという最適性条件を(1),(2)に適用すると(1)の解equationでは

equation (3)

を満たし,(2)の解equationにおいては

equation (4)

となる.(4)を更にequationで割れば

equation (4’)

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

 近接勾配法の収束速度を目的関数値の最適値との差で表した場合,その速度は適当な仮定のもとequationである事が知られているが,近接勾配法をequationまで加速させた手法もある.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 equation, 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.