体系ガイド · 基礎から応用へ

凸性と最適化の保証

凸性、強凸性、滑らかさの役割を区別し、停留点の保証と制約付き最適化の注意点を例で理解します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 二点を結ぶ線分で定義する
  2. 一階の条件から大域最小を説明する
  3. 一意性にはさらに条件が要る
  4. 学習率の上限は滑らかさから考える
  5. 制約付きでは境界の解を確認する
  6. 非凸問題の局所的な成功を区別する
  7. この記事をロゲイアに質問する理解を確かめる

二点を結ぶ線分で定義する

凸集合では、集合の二点を結ぶ線分も集合に含まれます。その集合上の関数fが凸とは、0≤t≤1でf(tx+(1−t)y)≤tf(x)+(1−t)f(y)を満たすことです。グラフの二点を結ぶ線分が関数より上にある、と読みます。単に「下に丸く見える」という印象では、次元が高い場合や定義域に穴がある場合を判定できません。まず実行可能な領域が凸か、その上で関数の不等式が成り立つかを分けます。目的関数だけでなく制約も保証に関わります。

一階の条件から大域最小を説明する

微分可能な凸関数ではf(y)≥f(x)+∇f(x)ᵀ(y−x)です。制約のない問題で∇f(x)=0なら、どのyでもf(y)≥f(x)となり、xは大域最小です。局所的な微分の条件が全体の保証になる点が凸性の利点です。ただし最小点が存在するとは限りません。例えば実数全体でexp(x)は凸ですが、値は0に近づくだけで有限のxでは0になりません。停止条件に小さい勾配を使うときも、最小点の存在と近似精度の意味を別に考えます。

一意性にはさらに条件が要る

凸関数f(x)=0はすべての点で最小になり、解は一意ではありません。厳密凸なら存在する最小点は一意です。強凸はさらに一定の二次曲率の下限を持つ条件で、収束や誤差評価に役立ちます。二次関数f(x,y)=x²ではy方向が平らなので解は(0,y)という集合になりますが、x²+y²なら解は(0,0)だけです。「凸だから解が一つ」という説明は前者を見落とします。正則化項を加えて一意性を得る場合は、元の問題とは目的が変わることも確認してください。

学習率の上限は滑らかさから考える

勾配がL-Lipschitz連続である滑らかな関数では、勾配の変わり方に上限があります。f(x)=ax²/2、a>0ならL=aで、勾配降下の更新はx次=(1−ηa)xです。絶対値を縮めるには0<ηa<2が必要で、凸だから任意の学習率で収束するわけではありません。ηa=2では符号反転を繰り返し、2を超えると発散します。この例の学習率条件は定数曲率の二次関数についての計算です。一般の関数へ移す場合は滑らかさと方法の仮定を確かめます。

制約付きでは境界の解を確認する

f(x)=(x−2)²をx≤1の範囲で最小にすると、最小点はx=1です。その点で微分は−2で0ではありませんが、許された方向へ動くと値を下げられません。制約なしの停留条件をそのまま当てると解を見落とします。射影勾配法では更新後に実行可能集合へ戻しますが、集合の形と射影の計算方法も必要です。境界、目的関数、実行可能性をそれぞれ検算してください。より一般の制約では最適性条件に正則性などの仮定が加わるため、式の適用範囲を確認します。

非凸問題の局所的な成功を区別する

f(x)=x⁴−x²は0で勾配が0ですが、近くの非ゼロのxで値が負になるため、0は最小点ではありません。ニューラルネットワークの学習など非凸の問題では、勾配が小さいという結果だけで大域最適と呼べません。練習として二次関数のηaを0.5、1.5、2.5に変え、符号と絶対値を追ってください。前二つは収縮、最後は発散です。凸性、解の存在、一意性、滑らかさ、制約を一覧にすると、収束についてどこまで説明できるかが明確になります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

AI基盤へ進む · STEP 13

学習コースから次を選ぶ