Document

大規模凸計画問題に対する勾配法
京都大学大学院情報学研究科
山下信雄
最適化の研究者の立場(?)
応用のことはよくわからない．
⇒
• より広いクラスの問題に適用できる
アルゴリズムの枠組みの開発
（Bregman距離の導入）
• より緩い条件での収束性の証明
(局所的エラーバウンド性の元での解析)
アウトライン
1. 考える問題（Structured Convex Optimization）
2. 準備
–
–
Bregman距離，Bregman divergence
局所的エラーバウンド
3. 近接勾配法(Proximal Gradient method)
•
•
•
近接勾配法とその収束性
近接勾配法の実装
近接勾配法の高速化
4. 工夫
•
•
Bregman距離による工夫
局所的エラーバウンドによる工夫
5. まとめ
考える問題：
構造を持った凸計画問題
(structured convex optimization, composite convex optimization)
min f ( x)  h( x)  P( x)
s.t. x  Rn
•目的関数は f ( x)  h( x)  P( x)
* h は微分可能の凸関数
* P は特殊な形(構造)の凸関数
n
例： lasso
| x | ,
i 1
標示関数
i
group lasso
w
J
xJ
2
J
0 if x  S
P( x)  
S
 if x 
問題例1
L1正則化問題
n
min g ( Ax)    | xi |
i 1
＊ g は強凸関数
h( x)  g ( Ax)
P( x)    | xi |
問題例2
単体制約をもつ凸計画問題
h( x)   xi ln xi 
n
1 •
min  xi ln xi  x Kx
2
i 1
s.t. x  

ただし，  は単体制約：    z  R n

1 •
x Kx
2
 0 if x  
P( x)  
 otherwize

z

1
,
z

0


i
i 1

n
＊単体制約は単体の直積に一般化できる．
応用・条件付最大エントロピーモデル
[Collins, Globerson, Carreras, Bartlett, 2007]
・CTの画像復元
[Ben-Tal, Margalit, Nemirovski, 2001]
問題例
ハードマージンSVM
n
1 T
min x Kx   xi
2
i 1
n
s.t.
yx
i 1
i i
 0, x  0
ただし， yi {1,1}
h( x ) 
1 •
x Kx   xi
2

 0 if x  0,  yi xi  0
P( x)  
 otherwize

アウトライン
1. 考える問題（Structured Convex Optimization）
2. 準備
–
–
Bregman距離，Bregman divergence
局所的エラーバウンド
3. 近接勾配法(Proximal Gradient method)
•
•
•
近接勾配法とその収束性
近接勾配法の実装
近接勾配法の高速化
4. 工夫
•
•
Bregman距離による工夫
局所的エラーバウンドによる工夫
5. まとめ
Bregman距離
(Bregman divergence)
 を微分可能な(狭義)凸関数とする．
Bregman関数
B ( x, y)  ( x)  ( y)   ( y), x  y
性質１： B ( x, y)  0
性質２： B ( x, x)  0
距離のようなもの
1
2
例１：
のとき B ( x, y)  x  y
2
n 
n
 xi

(
x
)

x
ln
x
B
(
x
,
y
)

x
l
n

i
i のとき
 i 
例２：


i 1
i 1 
 yi
1
 ( x)  x
2
2


  yi  xi 


(局所的)エラーバウンド
ある問題の解集合を X とする．
*
次の条件を満たす定数  ,  が存在するとき
関数  を局所的エラーバウンドという．
(i) dist x, X *   ( x) x such that  (x)  

(ii)

 ( x )  0 x  X
*
*
*
応用：・収束率の解析（強凸性などのかわり）
・安定性の解析
・有効制約の同定
局所的エラーバウンドの例
線形システム： Ax  b, Cx  d
[Hoffman, 1952]

dist x, X
*



   Ax  b   max (d  Cx)i , 0


n
L1正則化問題： min g ( Ax)    | xi |
[Tseng, 2010]
ただし

i 1


dist x, X *   x  x 
x は， x から近接勾配法による反復点
アウトライン
1. 考える問題（Structured Convex Optimization）
2. 準備
–
–
Bregman距離，Bregman divergence
局所的エラーバウンド
3. 近接勾配法(Proximal Gradient method)
•
•
•
近接勾配法とその収束性
近接勾配法の実装
近接勾配法の高速化
4. 工夫
•
•
Bregman距離による工夫
局所的エラーバウンドによる工夫
5. まとめ
近接勾配法=近接点法+勾配法
近接点法
x
[Rockarfellar 1976]
[Censor, Zenios 1992], etc
k 1

1
k 
 argmin  f ( x)  B ( x, x ) 
tk


• 解が唯一でなくてもある局所的エラーバウンド性のもとで超一次収束
[Luque, 1984]
• 部分問題は非線形計画
劣勾配法（Mirror Descent法)
[Nemirovsky, Yudin, 1983]
x
k 1
• 実装が簡単
• f が微分不可能なとき，
収束が著しく遅くなる．
 k f ( xk )

1
k
k
k
k 
 argmin  f ( x )   , x  x  B x, x 
tk



tk  0 とする必要があるため，

近接勾配法
特別な構造：
f ( x)  h( x)  P( x)
＊ｈは微分可能
＊Pは微分不可能でもよいが特殊な構造
Pの構造を利用
hに対して勾配法，Pに対して近接点法を適用
x
k 1
 k
1
k
k
k 
 argmin h( x )  h( x ), x  x  P( x)  B x, x 
tk




近接勾配法の収束性(1)
*
x
定理１最適解が存在するとする．
k 1
k 1
B ( x , x )  tk Bh ( x , x ) が成り立つとき
k
f ( xk )  f * 
k
B ( x0 , x* )
k 1
t
i 0
h
k
が係数Lのリプシッツ連続で  が係数

tk 
とすれば仮定は成り立つ．
L
注：
h
 の強凸関数であれば，
1
O
反復回数は  
k
がリプシッツ連続でなくても成り立つことがある．
近接勾配法の収束性(2)
定理２定理１の仮定が成り立つとする．
次の局所的エラーバウンド性が成り立つとする．
min
B ( x , x )   B ( x , x
*
*
k
x X
*
k
k 1
)
k
*
このとき，  f ( x )  f ( x ) は０に一次収束する．
局所的エラーバウンド性は成り立つ十分条件：
• h が強凸関数
• L1正則化問題
近接勾配法の実装
• 近接勾配法はよい収束性を持っている．
• 部分問題：
1
min h( x )  h( x ), x  x  P( x)  B ( x, x k )
tk
k
s.t.
k
k
x  Rn
をいかに効率よく解くかが重要となる．
Key ＊Bregman距離の選択
＊Pの構造を利用した計算法の開発
実装例1：
L1正則化問題
n
[部分問題]
min
h( x ), x   
k
i 1
s.t.
Bregman距離に
1
xi  B ( x, x k )
tk
x  Rn
B ( x, y ) 
1
x y
2
2
を用いると
T ( y )  (max{ y, 0}   )sgn( y )
k 1
i
x
 T tk (( x  tk h( x ))i ), i  1,, n
k
k
Iterative Shrinkage Threshold Algorithm (ISTA)
実装例２
単体制約つき凸計画問題
1
k
min h( x ), x  B ( x, x )
tk
k
[部分問題]
n
s.t.
x
i 1
n
 ( x)   xi ln xi
 1, x  0
としたBregman距離を用いると
i 1
xik 1 
i
xik exp(tk h( x k )i )
n
k
k
x
exp(

t

h
(
x
)j)
 j
k
, i  1,, n
j 1
Exponentiated Gradient Algorithm (EG)
実装例3
ハードマージンSVM
[部分問題]
1
min h( x ), x  B ( x, x k )
tk
k
s.t.
x x
i
iP
iN
i
 0, x  0
n
 ( x)   xi ln xi
＊ｈは凸２次関数
＊Pはクラス+1の集合
＊Nはクラス-１の集合
としたBregman距離を用いると
i 1
部分問題のKKT条件は
k 1
x
tk h( x k )    ln i k  0 i  P
xi
xik 1
tk h( x )    ln k  0 i  N
xi
k
x
iP
k 1
i
  x kj 1  0
jN
実装例3
ハードマージンSVM


  ln 


x
x
iP
jN
exp(tk h( x )i )) 


k
k
j exp( tk h( x ) j )) 

k
i
k
xik 1  xik exp(tk h( x k )i )) exp(  ) i  P
xik 1  xik exp(tk h( x k )i )) exp(  ) i  N
O(n) で計算可能
近接勾配法の高速化
近接勾配法の大域的な反復回数は
1
f (x )  f (x )  O  
k
k
*
それまでの反復の情報を利用すると
 1 
f (x )  f (x )  O  2 
k 
k
に高速化できる．
*
高速化手法１
[Nesterov, 1983], [Beck, Teboulle, 2009]
{x }, {y }, {k } を更新
k
k
 1
 k
y  x  k 
 1 x  x k 1
  k 1 

1
k 1
k 1
k 1 2 
x  argmin  h( y ), x  P( x) 
x y

2
t
k


k 1
 k 1 
ISTA

k

 k4  4 k2   k2
2
高速化
Fast ISTA (FISTA)
Beck and Teboulle,
A fast iterative shrinkage-thresholding algorithm for linear inverse problems
SIAM Journal on Imaging Sciences, 2009.
高速化手法２
[Nesterov, 1988], [Auslender, Teboulle, 2006]
{xk }, { y k }, {z k },{ k } を更新
y k 1  (1   k ) x k   k z k

k
k 1
k 
z  argmin  h( y ), x  P( x)  B ( x, z ) 
tk


x k 1  (1   k ) x k   k z k 1
k 1
 k 1 
 k4  4 k2   k2
2
高速化手法３
[Nesterov 2005], [Tseng, 2008]
{xk }, { y k }, {z k },{ k } を更新
y k 1  (1   k ) x k   k z k
 k 1 h( y i ), x  P( x) 1

k 1
z  argmin 
  ( x) 
i 1
tk
 i 1

x k 1  (1   k ) x k   k z k 1
 k 1 
 k4  4 k2   k2
2
アルゴリズムの関係
近接勾配法
x
k 1

1
k
k 
 argmin  h( x ), x  P( x)  B ( x, x ) 
tk


h( x )  0
近接点法
ISTA
Pが標示関数
射影勾配法
Mirror Descent 法
EG法
高速化法
FISTA
高速化EG法
X. Zhang, A. Saha, S. V. N. Vishwanathan,
“Accelerated Training of Max-Margin Markov Networks
with Kernels”, Algorithmic Learning Theory (ALT), 2011
アウトライン
1. 考える問題（Structured Convex Optimization）
2. 準備
–
–
Bregman距離，Bregman divergence
局所的エラーバウンド
3. 近接勾配法(Proximal Gradient method)
•
•
•
近接勾配法とその収束性
近接勾配法の実装
近接勾配法の高速化
4. 工夫
•
•
Bregman距離による工夫
局所的エラーバウンドによる工夫
5. まとめ
問題に特化した工夫
f ( x)  h( x)  P( x)
これまでに紹介した手法，ISTA，FISTAやEG法は
Pの構造を利用
関数ｈの性質や最適解の構造(スパース性など)
の利用を考える
実用的な工夫
– 前処理 (スケーリング)
– ステップ幅の調整 (非単調直線探索)
– 分割法との融合
工夫１
関数ｈに適したBregman距離の選択
もし   h としたら， Bregman距離は
Bh ( x, x )  h( x)  h( x )  h( x ), x  x
k
k
k
k
tk  1 とした部分問題の目的関数は
h( x k )  h( x k ), x  x k  P( x)  Bh ( x, x k )
 h( x)  P( x)
部分問題は元の問題と同じになる！！
Bregman距離の選択例
なるべく  ( x)  h( x) となるように選ぶ
例１：単体制約をもつ凸計画問題
n
1 •
x
ln
x

x Kx

i
i
2
i 1
s.t. x  
n
 ( x)   xi ln xi
min
i 1
例２：成分(ブロック)ごとのスケーリング
n
1
2
1 •

(
x
)

K
x

ii i
h ( x )  x Kx
2 i 1
2
 ( x) 
1 •
x Dx
2
Dはブロック対角
工夫２：分割法
一部の成分を
x
k 1
xk
に固定した部分問題を解く解法


1
k
k
 argmin h( x ), x  g ( x)  B ( x, x ) 
tk
x j  x kj , jJ k 

ここで
• J k は固定する成分の添え字の集合
例：ガウス-ザイデル法
Coordinate gradient descent 法
SVMのSequential Minimal Optimization 法
解の性質を利用した J の選択
k
例：
[L1-L2最適化]


n
1 •
min x Kx    | xi |
2
i 1




*
*
*
J

i
x

0
,
J

i
x

0
,
J

i
x
もし，
P
i
N
i
0
i 0
が分かれば，線形方程式になる．( x* は最適解のひとつ．)
J
k
k
J
となるように
を構成できれば，
 J0
x
k 1


1
k
k
 argmin h( x ), x  g ( x)  B ( x, x ) 
tk
x j 0, jJ k 

としても解が求まる．(解がスパースなときに有効)
 ( xk ) 

局所的エラーバウンド
x k  T t ( x k  tk h( x k )) を用いた同定
k




J Pk  i xik   ( x k ) , J Nk  i xik    ( x k ) , J 0k  i | xik |  ( x k )
*
x
解が唯一のとき，十分大きいkに対して
J P  J Pk , J N  J Nk , J0  J0k
∵
xk  x* ,  ( xk )  0, J P  J Pk , J P  J Pk , J0  J0k
i  J 0 に対して
| xik || xik  xi* | x k  x*   ( x k )   ( x k )

まとめ
• 特殊な構造をもつ凸計画問題に対する
近接勾配法を紹介した．
• 高速化への工夫として
–
–
Bregman距離の選択
局所的エラーバウンドの利用
非線形最適化の研究では一般化，抽象化されすぎ
問題に特化した工夫で高速化が可能(かも)
（最適化の分野の）
サーベイ文献+α
[近接勾配法]
Paul Tseng, Approximation accuracy, gradient methods, and error bound for
structured convex optimization, Mathematical Programming, Ser, B, 125, pp.
263-296, 2010.
[エラーバウンド性]
Jong-Shi Pang, Error bounds in mathematical programming, Mathematical
Programming , 79, pp. 299-332, 1997.
[最新論文]
http://www.optimization-online.org/
ご清聴，ありがとうございました

Download Report