修士論文 要旨

Prediction-Correction Algorithm forTime-Varying Smooth Optimization(時間変化する平滑最適化問題に対する予測補正アルゴリズム)
数理情報学専攻 48216205
指導教員

1 はじめに時間変化する最適化問題は工学において広く現れ，重要な研究対象となっている．中でも，時間と共に変化する最適解の追跡精度の向上を目的として，様々な予測補正アルゴリズムと呼ばれる手法が提案されている．し究では，一般の非凸な大規模最適化問題に適用可能な予武田 朗子 教授

Algorithm 1 予測補正アルゴリズムの手続き
1: for k = 0, 1, 2, . . . do2:目的関数 f (·; tk ) が明らかになる3:f (·; tk ) に基づき，予測 xk|k−1 を xk に補正

4:f (·; tk+1 ) の近似関数に基づき，xk を初期点として xk+1|k を予測

かし，既存手法の理論保証は強凸関数に限定される上，そのほとんどが，大規模な問題へ適用困難である．本研

岩切 秀規

5:

損失 f (xk+1|k ; tk+1 ) を被る

6: end for

測補正アルゴリズムを新たに提案した．さらに，強凸でこれまでに，勾配降下法より高い精度を達成する予測ない目的関数に対する勾配降下法及び提案手法の収束補正アルゴリズムが様々提案されているが (e.g. [3, 2])，誤差の解析を行い，提案手法が勾配降下法を上回る精度

それらは全て，目的関数が強凸関数であるか，強凸関数を達成することを理論的に示した (表 1 参照)．と良い性質を備えた凸関数の和で書けることを仮定している．さらに，多くの既存アルゴリズムは，ヘッセ行2 時間変化する平滑最適化問題列やその逆行列を用いており，大規模な問題への適用が困難である．

以下の時間変化する平滑最適化問題を考える:

x∗k := argmin f (x; tk ), k ∈ N(1)

4 提案手法x∈Rd

ただし，tk := kh であり，h はサンプリング周期を表す．また，f (x; t) は x, t に対して滑らかとする．この問題においては，時不変な最適化問題とは異なり，各反復において h 以内に最適化問題を解かなければならないことから，毎反復，一定程度の誤差を許すことになる．そのため，最適解がなす軌道 {x∗k } への収束速度だ
けでなく，収束後の最適解軌道の追跡精度が重要になる．次章で，この追跡精度の向上を目的に開発された予測補正アルゴリズムについて紹介する．

3 予測補正アルゴリズム
予測補正アルゴリズム (Algorithm 1) は，補正ステップと予測ステップからなる．補正ステップでは，入手した目的関数 f (·; tk ) に対して，時不変な関数に対する最適化手法，例えば勾配降下法を適用する．予測ステップ

そこで本研究では，一般の非凸大規模問題に適用可能な予測補正アルゴリズムを新たに提案した．その手続
きを Algorithm 2 に示す．4 行目に示したように，提案手法の補正ステップは，勾配降下法そのものである．

5 行目が予測ステップに対応しており，これは，次の時刻における関数 f (·; tk+1 ) の 1 次の Taylor 級数近似の制約付き最小化問題

min f (xk ; tk ) + ⟨∇x f (xk ; tk ), x − xk ⟩ + h∇t f (xk ; tk )x∈Rds.t. ∥x − xk ∥ ≤ ζhの解となっている．予測ステップでは，勾配及び勾配のノルムしか用いないため，大規模な問題への適用も可能であることが分かる．

5 理論解析

では，次の時刻における関数値を予測した上で，良い性提案手法が勾配降下法と比べて良い精度を達成する質を持つ点 xk を予測する．最適解の追跡速度の向上にことを保証するにあたっては，目的関数の滑らかさの仮あたっては，関数の時間変化の特徴を捉えた優れた予測定に加え，以下の仮定が必要となる:手法を構築することが鍵となる．

Prediction-Correction Algorithm for Time-Varying Smooth Optimization( 時間変化する平滑最適化問題に対する予測補正アルゴリズム) (岩切 秀規)

図 1. 既存手法及び提案手法における収束誤差と必要なオラクルの比較．

アルゴリズムGD [1]U-FOPC [2]

AGT [3]

提案手法 (FOA-Min)

必要なオラクル

GradGrad, HessianGrad, Hessian inv.

Grad, Grad normPLO(h)-optimal√O( h)-stationary-

N/A

O(h2 )-optimal-N/A

O(h)-stationary

非凸Algorithm 2 提案手法
1: for k = 0, 1, 2, . . . do

いることが分かる．
また，上記の定理は，時間に関して平均を取った結果

2:

目的関数 f (·; tk ) が明らかになるについて評価しており，最悪ケースは評価できていない．

3:

xk = xk|k−1 − β∇x f (xk|k−1 ; tk )4:

∇x f (xk ;tk )xk+1|k = xk − ζh ∥∇x f (xk ;tk )∥そこで，本研究では，アルゴリズムが h5:

損失 f (xk+1|k ; tk+1 ) を被る

p2L1 (1 + Ḡ2 )-stationary point に到達した後も，全ての出力が勾配または関数値の意味で良い点になっていることを示した．

6: end for

仮定 1. ∃Z ≥ 0, ∀x ∈ Rd , ∀t ≥ 0, |∇t f (x; t)| −Z∥∇x f (x; t)∥ ≤ 0

6 数値実験
時間変化する線形回帰問題

この仮定は，目的関数の勾配が 0 に近づくとき，時間微分も同程度の速度で 0 に近づいていくことを要請している．これは，大変強い仮定のように思えるが，いくつかの重要な関数クラスがこの仮定を満たすことが示せる．例えば，以下の定理が示すように，強凸関数の最適化問題はこの仮定を満たすように同値変形できる:min f (x; tk ) :=x∈R101∥Ax − b(tk )∥2 ,2に対して，既存手法及び提案手法を適用した結果を図に示す．提案手法 (黄，緑) は既存手法に比べ，h が小さいときに既存手法を上回る精度を達成し，かつ，勾配のノルムの h への依存が理論保証通り O(h) となっていることが確認できる．

定理 5.1. 強凸な目的関数 f (x; t) がある滑らかさの仮定を満たすとする．このとき，目的関数を fˇ(x; t) :=Rtf (x; t) − 0 ∇t f (y; τ )|y=x∗ (τ ) dτ と再定義すると，この関数は，引き続き滑らかさの仮定を満たす上，仮定 1 を満たす．
他にも，時間変化と共に平行移動する関数 f (x+g(t))
を含むような重要な関数クラスがこの仮定を満たすことが示せる．
この仮定を用いると，非凸関数に対する提案手法の収束誤差を以下のように評価することができる．

図 2. 横軸にサンプリング周期，縦軸に最適性ギャップ (左) または勾配のノルム (右) を取った両対数プロット．

また，大規模な非凸最適化問題に対する提案手法の性能を確認するため，Netﬂix のレコメンドデータを用いて，時間変化する行列分解問題を実装した．ここでも，定理 5.2. 目的関数がある滑らかさの仮定及び仮定 1

提案手法が勾配降下法を上回る精度を達成した．

を満たすとする．このとき，アルゴリズムのパラメータを適切に定めることで，任意の k0 ∈ Z≥0 に対し，Tk0 :=fk0 −fk∗0
h2

回の反復における勾配のノルムの平均は，以下で抑えられる:

1T k0k0 +Tk0 −1X∇x f (xk|k−1 ; tk ) ≤ hq2L1 (1 + Ḡ2 )k=k0

同様の解析を行うと，勾配降下法に対しては，勾配の√ノルムの平均は O( h) となることから，提案手法の予√測の導入によって，精度が O( h) → O(h) と向上して

参考文献[1] A. Y. Popkov. Gradient methods for nonstationary
unconstrained optimization problems. Automation
and Remote Control, 66(6):883–891, 2005.
[2] A. Simonetto and E. Dall’Anese.
Predictioncorrection algorithms for time-varying constrained optimization. IEEE Transactions on Signal Processing,65(20):5481–5494, 2017.
[3] A. Simonetto, A. Mokhtari, A. Koppel, G. Leus, andA. Ribeiro. A class of prediction-correction methods
for time-varying convex optimization. IEEE Transactions on Signal Processing, 64(17):4576–4591, 2016.