.
定義
.
.
.
. . .
.
.
w
t:
以下の停止基準による近似的なDAL
法で得られる点列．∥∇ ϕ
t(α
t) ∥ ≤ q
γ
ηt
∥ w
t+1− w
t∥
µ 1/γ:
損失関数の微分∇ f
ℓのリプシッツ定数.
¶
.
定理
2
.
.
.
. . .
.
.
定理
1
と同じ仮定のもとで∥ w
t+1− w
∗∥ ≤ 1
√ 1 + 2ση
t∥ w
t− w
∗∥ .
⇒ η
t が増加するなら，w
t はw
∗に超１次収束する．収束レートは厳密な場合
( ∥∇ ϕ
t(α
t) ∥ = 0)
より少し悪い．同程度の収束レートは内部最小化をもう少し厳しくすることで達成 可能 ∥∥∇wt+1ϕt(α−wt)t∥∥
≤ O(1/η
t).
冨岡 亮太(東大) RAMP2011 2011-10-25 22 / 37
. . . . . .
定理 2 （近似的最小化）
.
定義
.
.
.
. . .
.
.
w
t:
以下の停止基準による近似的なDAL
法で得られる点列．∥∇ ϕ
t(α
t) ∥ ≤ q
γ
ηt
∥ w
t+1− w
t∥
µ 1/γ:
損失関数の微分∇ f
ℓのリプシッツ定数.
¶
.
定理
2
.
.
.
.
.
定理
1
と同じ仮定のもとで∥ w
t+1− w
∗∥ ≤ 1
√ 1 + 2ση
t∥ w
t− w
∗∥ .
⇒ η
t が増加するなら，w
t はw
∗に超１次収束する．収束レートは厳密な場合
( ∥∇ϕ
t(α
t)∥ = 0)
より少し悪い．同程度の収束レートは内部最小化をもう少し厳しくすることで達成 可能 ∥∥∇wt+1ϕt(α−wt)t∥∥
≤ O(1/η
t).
冨岡 亮太(東大) RAMP2011 2011-10-25 22 / 37
. . . . . .
.
定理
1
の証明（エッセンス）.
.
.
. . .
.
.
w
t+1は，f(w) +
2η1t
∥ w − w
t∥
2を最小化するので，(w
t− w
t+1)/η
t∈ ∂f (w
t+1)
（劣微分に入る）従って
(Beck & Teboulle 09)
，f (w
∗) − f (w
t+1) ≥ D
(w
t− w
t+1)/η
t, w
∗− w
t+1E
.
w∗ wt+1 f(w∗)
f(wt+1)
冨岡 亮太(東大) RAMP2011 2011-10-25 23 / 37
. . . . . .
.
定理
2
の証明（エッセンス）.
.
.
. . .
.
.
f (w
∗) − f (w
t+1) ≥ D
(w
t− w
t+1)/η
t, w
∗− w
t+1E − 1
2γ ∥∇ ϕ
t(α
t) ∥
2| {z }
近似最小化のコスト
.
1/γ:
損失関数の微分∇ f
ℓのリプシッツ定数．w∗ wt+1 f(w∗)
f(wt+1)
. . . . . .
構造付きスパース推定問題のための最適化手法
Alternating Direction Method of Multipliers (ADMM)
冨岡 亮太(東大) RAMP2011 2011-10-25 25 / 37
. . . . . .
拡張ラグランジュ法 [Powell 69; Hestenes 69]
.
最小化問題
.
.
.
. . .
.
.
minimize
x,z
f(x) + λ ∥ z ∥
1, s.t. z = Φx
.
拡張ラグランジアン
.
.
.
. . .
.
.
L
η(x , z, α) = f (x ) + λ ∥ z ∥
1+ α
⊤(z − Φx ) + η
2 ∥ z − Φx ∥
2.
.
拡張ラグランジュ法
.
.
.
.
.
拡張ラグランジアンを
x , z
に関して最小化: (x
t+1, z
t+1) = argmin
x∈Rn,z∈Rm
L
ηt(x , z , α
t).
ラグランジュ乗数を更新
: α
t+1= α
t+ η
t(z
t+1− Φx
t+1).
x
とz
の間に絡みが発生!
（別々に最小化できない）冨岡 亮太(東大) RAMP2011 2011-10-25 26 / 37
. . . . . .
Alternating Direction Method of Multipliers (ADMM; Gabay
& Mercier 76)
.
拡張ラグランジアン
.
.
.
. . .
.
.
L
η(x , z, α) = f (x ) + λ ∥ z ∥
1+ α
⊤(z − Φx ) + η
2 ∥ z − Φx ∥
2.
拡張ラグランジアンを
x
に関して最小化: x
t+1= argmin
x∈Rn
L
ηt(x , z
t, α
t).
拡張ラグランジアンを
z
に関して最小化: z
t+1= argmin
z∈Rm
L
ηt(x
t+1, z , α
t).
ラグランジュ乗数を更新
: α
t+1= α
t+ η
t(z
t+1− Φx
t+1).
今更新した
x
t+1がz
t+1の計算に入っているところがポイント．冨岡 亮太(東大) RAMP2011 2011-10-25 27 / 37
. . . . . .
ADMM (Gabay & Mercier 76)
.
拡張ラグランジアン
.
.
.
. . .
.
.
L
η(x , z, α) = f (x ) + λ∥ z ∥
1+ α
⊤(z − Φx ) + η
2 ∥ z − Φx ∥
2.
書き直すと
x
t+1= argmin
x∈Rn
L
ηt(x , z
t, α
t).
z
t+1= argmin
z∈Rm
L
ηt(x
t+1, z, α
t).
α
t+1= α
t+ η
t(z
t+1− Φx
t+1).
z
に関する最小化はProx
作用素prox
λ/ηt（簡単）．x
に関する最小化は行列Φ
が変数を絡ませるのでちょっと難しい．1
反復あたりのコストが同じなら近接勾配法より経験的に速い（理 論的には不明）双対側での
Douglas Rachford Splitting
と等価⇒
ステップサイズη
によらずADMM
は安定．(Lions & Mercier 76; Eckstein & Bertsekas 92)
. . . . . .
ADMM (Gabay & Mercier 76)
.
拡張ラグランジアン
.
.
.
. . .
.
.
L
η(x , z, α) = f (x ) + λ ∥ z ∥
1+ α
⊤(z − Φx ) + η
2 ∥ z − Φx ∥
2.
書き直すと
x
t+1= argmin
x∈Rn
³
f(x) + η
t2 ∥ z
t− Φx + α
t/η
t∥
2´ . z
t+1= argmin
z∈Rm
L
ηt(x
t+1, z, α
t).
α
t+1= α
t+ η
t(z
t+1− Φx
t+1).
z
に関する最小化はProx
作用素prox
λ/ηt（簡単）．
x
に関する最小化は行列Φ
が変数を絡ませるのでちょっと難しい．1
反復あたりのコストが同じなら近接勾配法より経験的に速い（理 論的には不明）双対側での
Douglas Rachford Splitting
と等価⇒
ステップサイズη
によらずADMM
は安定．(Lions & Mercier 76; Eckstein & Bertsekas 92)
冨岡 亮太(東大) RAMP2011 2011-10-25 28 / 37
. . . . . .
ADMM (Gabay & Mercier 76)
.
拡張ラグランジアン
.
.
.
. . .
.
.
L
η(x , z, α) = f (x ) + λ ∥ z ∥
1+ α
⊤(z − Φx ) + η
2 ∥ z − Φx ∥
2.
書き直すと
x
t+1= argmin
x∈Rn
³
f(x) + η
t2 ∥ z
t− Φx + α
t/η
t∥
2´ . z
t+1= argmin
z∈Rm
³
λ ∥ z ∥
1+ η
t2 ∥ z − Φx
t+1+ α
t/η
t∥
2´ . α
t+1= α
t+ η
t(z
t+1− Φx
t+1).
z
に関する最小化はProx
作用素prox
λ/ηt（簡単）．x
に関する最小化は行列Φ
が変数を絡ませるのでちょっと難しい．1
反復あたりのコストが同じなら近接勾配法より経験的に速い（理 論的には不明）双対側での
Douglas Rachford Splitting
と等価⇒
ステップサイズη
によらずADMM
は安定．(Lions & Mercier 76; Eckstein & Bertsekas 92)
. . . . . .
ADMM (Gabay & Mercier 76)
.
拡張ラグランジアン
.
.
.
. . .
.
.
L
η(x , z, α) = f (x ) + λ ∥ z ∥
1+ α
⊤(z − Φx ) + η
2 ∥ z − Φx ∥
2.
書き直すと
x
t+1= argmin
x∈Rn
³
f(x) + η
t2 ∥ z
t− Φx + α
t/η
t∥
2´ . z
t+1= argmin
z∈Rm
³
λ ∥ z ∥
1+ η
t2 ∥ z − Φx
t+1+ α
t/η
t∥
2´ . α
t+1= α
t+ η
t(z
t+1− Φx
t+1).
z
に関する最小化はProx
作用素prox
λ/ηt（簡単）．x
に関する最小化は行列Φ
が変数を絡ませるのでちょっと難しい．1
反復あたりのコストが同じなら近接勾配法より経験的に速い（理 論的には不明）双対側での
Douglas Rachford Splitting
と等価⇒
ステップサイズη
によらずADMM
は安定．(Lions & Mercier 76; Eckstein & Bertsekas 92)
冨岡 亮太(東大) RAMP2011 2011-10-25 28 / 37
. . . . . .
テンソルの穴埋め問題への凸最適化の適用 [Liu+09,
Signoretto +10, Tomioka+10, Gandy+11]
凸最適化の適用のポイント
:
テンソルの行列化(Matricization)
テンソルがTucker
分解の意味で低ランク⇔
そのテンソルの行列化は（行列の意味で）低ランクn 1n 2 n 3 n 1 n 2 n 2 n 2
n 3
モード1 行列化
n 1n 2 n 3 n 2 n 3 n 3 n 3
n 1
モード2 行列化
X
(1)X
(2). . . . . .
テンソルの穴埋め問題への ADMM の適用
数学的な定式化
: minimize
x,z1,...,zK∈RN
1
2λ ∥ Ωx − y ∥
2+ X
K k=1γ
k∥ | {z } Z
k∥
S1低ランク化
,
s.t. P
kx = z
k(k = 1, . . . , K ),
x
は推定すべきテンソルをベクトルとして書いたもの．y ∈ R
Mは観測．（M ≪ N = n
1n
2· · · n
K)
P
k はモードk
行列化の操作を行列で表現したもの．P
k⊤P
k= I
（行列化は直交変換）．すべてのモードが同時に低ランクになるように正則化．
冨岡 亮太(東大) RAMP2011 2011-10-25 30 / 37
. . . . . .
テンソルの穴埋め問題への ADMM の適用
拡張ラグランジアン
L
η(x , { Z
k}
Kk=1, { α
k}
Kk=1) = 1
2λ ∥ Ωx − y ∥
2+ X
K k=1γ
k∥ Z
k∥
S1+ X
K k=1³
α
k⊤(P
kx − z
k) + η
2 ∥ P
kx − z
k∥
2´ .
x
に関する最小化P
k が直交行列なので解析的にO(N)
で計算可能．Z
k（z
k を行列として並べたもの）に関する最小化はSchatten 1-
ノ ルムに関するProx
作用素．ラグランジュ乗数ベクトルは制約の数（モードの数）だけ必要．
. . . . . .