オンライン最適化とは? オンライン近接勾配法のリグレット上界

オンライン最適化とは,最小化すべき目的関数が逐次的に変化する最適化問題です.応用の重要性から機械学習のコミュニティでも研究されています.

この記事では,オンライン最適化の問題設定,アルゴリズムの性能評価指標(リグレット),そして代表的なアルゴリズムであるオンライン近接勾配法

\[ x_t = \red{\argmin_{x\in \R^d} \Big\{ \inner{p_{t-1}}{x} + g(x) + \frac{\eta_t}{2}\|x - x_{t-1}\|^2 \Big\}} \]

を解説します.さらに,オンライン近接勾配法のリグレット上界を証明します.

問題設定

この記事で考えるオンライン最適化は,以下のような設定です.

  • 学習者 L(Learner)と敵対者 A(Adversary)がいる.
  • L と A には事前に凸関数 $g: \R^d \to \R \cup \{+\infty\}$ の完全な情報が与えられる.
  • 各時刻 $t=1,\dots,T$ で,
    1. L は $x_t \in \R^d$ を選択.
    2. A は凸関数 $f_t:\R^d \to \R$ と劣勾配 $p_t \in \partial f_t(x_t)$ を選択1
    3. L は損失 $f_t(x_t) + g(x_t)$ を被り,劣勾配 $p_t$ を知る.
  • L は累積損失 $\dis \sum_{t=1}^T \big(f_t(x_t) + g(x_t) \big)$ を小さくしたい.

凸関数 $f_t$ が敵対者によって「敵対的に」選ばれるため,この設定は特に敵対的オンライン凸最適化と呼ばれます.

この他に,凸関数 $f_t$ が「確率的に」選ばれる設定も盛んに研究されています.そのような設定は確率的オンライン凸最適化と呼ばれます.また,関数が凸とは限らない設定も考えられます.

関数 $g$ はいわゆる正則化項にあたるものです.$g$ を凸集合の標示関数(indicator function)とすれば,凸制約を扱うこともできます.

後々の表記を簡単にするために $\dis F_t(x) \ceq f_t(x) + g(x)$ とおいておきます.

評価指標: リグレット

学習者 L が各時刻で $x_t$ を選ぶためのアルゴリズムを考えます.L の目標は累積損失 $\sum_{t=1}^T F_t(x_t)$ を小さくすることですが,敵対者 A は関数 $f_t$ を自由に選べてしまうため,A がすごく「イジワル」だったら,L にはどうしようもありません.

そこで,オンライン最適化では仮想的な比較対象 C を想定し,L の累積損失は C の累積損失と比べてどれくらい大きいか? でアルゴリズムの良し悪しを測ります.A がすごくイジワルだったら C の累積損失も大きくなるはずなので,その時は L の累積損失が大きくても諦める,という考え方です.

この「$($L の累積損失$) - ($C の累積損失$)$」という評価指標はリグレット(regret,後悔)と呼ばれます.もちろんリグレットは小さい方が嬉しいです.

最もよく用いられる比較対象 C の設定は,「$f_1,\dots,f_T$ の情報を事前に全て知っている(予知できる)かわりに,各時刻 $t$ で共通の $x \in \R^d$ しか選択できない」というものです.このとき,リグレットは

\[ R_T \ceq \class{red}{\sum_{t=1}^T F_t(x_t) - \min_{x \in \R^d} \sum_{t=1}^T F_t(x)} \]

と書けます(C は十分賢いことを想定しています).本記事ではこのリグレットの定義を用います.

誤解しやすいですが,この定義のリグレットは必ず正になるとは限りません.

オンライン近接勾配法

「敵対者 A がどんな振る舞いをしてもリグレットは○○以下になる」と言えるような $x_t$ の決定アルゴリズムがあると嬉しいです.そのようなアルゴリズムで代表的なものがオンライン近接勾配法です.

記事冒頭にも書きましたが,以下のように $x_t$ $(t=1,2,\dots,T)$ を定めます:

\begin{equation} \label{update-rule} x_t = \class{red}{\argmin_{x\in \R^d} \Big\{ \inner{p_{t-1}}{x} + g(x) + \frac{\eta_t}{2}\|x - x_{t-1}\|^2 \Big\}}.\end{equation}

ただし $p_0 \ceq \0$(ゼロベクトル)とし,初期点 $x_0 \in \R^d$ は $g(x_0) < \infty$ となる点を任意に選びます.$\eta_1,\dots,\eta_T > 0$ はステップサイズを表すパラメータで,定め方は状況に応じて変えます.

$\inner{a}{b}$ はベクトル $a,b \in \R^d$ の標準的な内積 $\sum_{i=1}^d a_i b_i$ を表し,$\|a\|$ はユークリッドノルム $\|a\| = \sqrt{\sum_{i=1}^d |a_i|^2}$ を表します.また,$\argmin_{x \in \R^d} f(x)$ は $f$ を最小化する $x \in \R^d$ を表します2

$x_t$ を決めるために $p_t$ の情報は使っていないことに注意して下さい($p_1,\dots,p_{t-1}$ の情報は使っています).

このアルゴリズムは通常の最適化問題に対する近接勾配法とよく似ています.実際,$f_1=\dots=f_T = f$ とすると,$f$ が微分できるとは限らない場合の近接勾配法と一致します.

リグレット上界

$\dom g \ceq \{ x \in \R^d \mid g(x) < \infty \}$ とおきます.

学習者 L がオンライン近接勾配法を使って $x_t$ を決めた場合,リグレットは以下のように上から押さえられます:

定理 $1$

  • $f_1,\dots,f_T$ は $\dom g$ 上で $L$-リプシッツ連続
  • $\dis \max_{x,y\in \dom g} \|x-y\| \leq D$

のとき,$\dis \eta_t = \red{\frac{L}{D}\sqrt{T}}$ と定めると,$\dis R_T \leq \red{LD \sqrt{T}}.$

定理 $2$

  • $f_1,\dots,f_T$ は $\dom g$ 上で $L$-リプシッツ連続
  • $f_1,\dots,f_T$ は $\dom g$ 上で $\mu_f$-強凸,$g$ は $\mu_g$-強凸(ただし $(\mu_f, \mu_g) \neq (0, 0)$)

のとき,$\eta_t = \red{(\mu_f + \mu_g) (t-1)}$ と定めると,$\dis R_T \leq \red{\frac{L^2}{2(\mu_f + \mu_g)}(1 + \log T )}.$

関数 $f$ が任意の $x,y \in X$ に対し,\[ |f(x) - f(y)| \leq L \|x-y\| \]を満たすとき,$f$ は $X$ 上で $L$-リプシッツ連続と言います.$L$ が小さいほど「関数値が緩やかに変化する」ため,リグレットを小さくできます.

仮定によってリグレット上界のオーダーが異なることに注意して下さい.定理 $1$ では $R_T = \red{O(\sqrt{T})}$,定理 $2$ では $R_T=\red{O(\log T)}$ です.

この定理はミニマックス定理の証明に応用することができます!
ミニマックス定理の意味と初等的証明

定理の証明

結構難しいです.大学院レベルの連続最適化の知識を前提として証明します(ごめんなさい......).

方針

近接勾配法の収束証明と同様に,更新式と $f_t$ の強凸性から導かれる不等式たちを足します.さらにヤングの不等式とリプシッツ連続性を使って評価します.

$\mu \ceq \mu_f + \mu_g$ とおきます.定理 $1$ と $2$ を途中まで同時に証明します(定理 $1$ では $\mu=0$ と考えます).どちらの場合も $\eta_t = \eta_1 + \mu (t-1)$ を満たしていることに注意します.

証明(途中まで)

比較対象 C は $x^* \in \R^d$ を選ぶとします.更新式 \eqref{update-rule} の $\argmin$ の中身は $(\eta_t + \mu_g)$-強凸なので,\[ \inner{p_{t-1}}{x_t - x^*} + g(x_t) - g(x^*) \leq \frac{\eta_t}{2} \|x_{t-1} - x^*\|^2 - \frac{\eta_t}{2} \|x_t - x_{t-1}\|^2 - \frac{\eta_t + \mu_g}{2} \|x_t - x^*\|^2 \]が成り立ちます.また,$f_t$ の $\mu_f$-強凸性より,\[ f_t(x_t) - f_t(x^*) \leq \inner{p_t}{x_t - x^*} - \frac{\mu_f}{2} \|x_t - x^*\|^2 \]が成り立ちます.これら $2$ 式を足すと,\begin{align}\label{proof-ineq3} F_t(x_t) - F_t(x^*) \leq \inner{p_t - p_{t-1}}{x_t - x^*} + \frac{\eta_t}{2} \|x_{t-1} - x^*\|^2 - \frac{\eta_t + \mu}{2} \|x_t - x^*\|^2 - \frac{\eta_t}{2} \|x_t - x_{t-1}\|^2 \end{align}を得ます.さらにこの式を $t=1,\dots,T$ について足し,ゴリゴリ計算すると(→ 補足),\begin{align} \label{proof-ineq4} \red{R_T \leq \frac{\eta_1}{2} \|x_0 - x^*\|^2 + \frac{L^2}{2}\sum_{t=1}^{T} \frac{1}{\eta_1 + \mu t}} \end{align}が得られます.

定理 $ 1 $ の証明

$\mu = 0$ と $\dis \max_{x,y\in \dom g} \|x-y\| \leq D$ より,$\dis R_T \leq \frac{D^2\eta_1}{2} + \frac{L^2T}{2\eta_1}$ となります.この右辺を最小にするために $\dis \eta_1 = \frac{L}{D}\sqrt{T}$ とすると,所望の上界を得ます.

定理 $ 2 $ の証明

$\|x_0-x^*\|$ を消すために $\eta_1 =0$ とすると,$\dis R_T \leq \frac{L^2}{2\mu}\sum_{t=1}^{T} \frac{1}{t} $ となります.右辺を高校数学でもおなじみの「短冊分割」で評価すると,所望の上界を得ます.

補足: ゴリゴリ計算の詳細

式 \eqref{proof-ineq3} を $t=1,\dots,T$ ついて足し合わせます.

左辺の和はリグレット $R_T$ と等しくなります.

右辺第 $1$ 項の和は\begin{align*}&\indent\sum_{t=1}^T \inner{p_t - p_{t-1}}{x_t - x^*}\\ &= \inner{p_T}{x_T - x^*} - \sum_{t=1}^{T}\inner{p_{t-1}}{x_t - x_{t-1}} \\&\leq \frac{1}{2\eta_{T+1}}\|p_T\|^2 + \frac{\eta_{T+1}}{2}\|x_T - x^*\|^2 + \sum_{t=1}^{T}\Big( \frac{1}{2\eta_t}\|p_{t-1}\|^2 + \frac{\eta_t}{2}\|x_t - x_{t-1}\|^2 \Big) \\&\leq \frac{L^2}{2\eta_{T+1}} + \frac{\eta_{T+1}}{2}\|x_T - x^*\|^2 + \sum_{t=1}^{T}\Big( \frac{L^2}{2\eta_t} + \frac{\eta_t}{2}\|x_t - x_{t-1}\|^2 \Big) \\&= \frac{L^2}{2} \sum_{t=1}^{T} \frac{1}{\eta_{t+1}} + \frac{\eta_{T+1}}{2}\|x_T - x^*\|^2 +\sum_{t=1}^{T}\frac{\eta_t}{2}\|x_t - x_{t-1}\|^2 \\&= \frac{L^2}{2} \sum_{t=1}^{T} \frac{1}{\eta_1 + \mu t} + \frac{\eta_{T+1}}{2}\|x_T - x^*\|^2 +\sum_{t=1}^{T}\frac{\eta_t}{2}\|x_t - x_{t-1}\|^2 \end{align*}と評価できます.$1$ 行目の等号には $p_0 = \0$ を,$2$ 行目の不等号にはヤングの不等式を,$3$ 行目の不等号には $f_t$ の $L$-リプシッツ連続性と同値な不等式 $\max \{ \|p\| \mid p \in \partial f_t(x) \} \leq L$ を使いました.

右辺のそれ以外の項の和は,\begin{align*}&\indent\sum_{t=1}^T \bigg( \frac{\eta_t}{2} \|x_{t-1} - x^*\|^2 - \frac{\eta_t + \mu}{2} \|x_t - x^*\|^2 - \frac{\eta_t}{2} \|x_t - x_{t-1}\|^2 \bigg) \\ &= \sum_{t=1}^T \bigg( \frac{\eta_t}{2} \|x_{t-1} - x^*\|^2 - \frac{\eta_{t+1}}{2} \|x_t - x^*\|^2 - \frac{\eta_t}{2} \|x_t - x_{t-1}\|^2 \bigg) \\ &= \frac{\eta_{1}}{2}\|x_0 - x^*\|^2 - \frac{\eta_{T+1}}{2}\|x_T - x^*\|^2 - \sum_{t=1}^T \frac{\eta_t}{2} \|x_t - x_{t-1}\|^2\end{align*}となります.

これらを組み合わせると式 \eqref{proof-ineq4} を得ます.

  1. 劣勾配とは勾配を微分不可能な凸関数に拡張したものです.$f_t$ が微分可能ならば,劣勾配の集合(劣微分という) $\partial f_t(x_t)$ は一点のみからなるため,選択の余地はなくなります.$f_t$ の微分可能性を仮定して,劣勾配を勾配に読み替えても問題ありません.
  2. 更新式 \eqref{update-rule} の $\argmin$ の中身は $x$ について強凸なので,最小化する $x$ がちょうど一つ存在します.
タイトルとURLをコピーしました