非凸問題の落とし穴とリスタート

谷が複数あるとき

興味深いモデルの多くは凸ではありません。目的関数には複数の局所最小、鞍点、平坦な高原があり、勾配降下法は出発した谷にただ転がり込みます。$f(x)=x^4-3x^2+x$ を考えましょう。導関数 $4x^3-6x+1$ は $x=-1.301$、$x=0.170$、$x=1.131$ でゼロになります。最初と最後が最小値で $f=-3.514$ と $f=-1.070$、真ん中はその間の山です。小さなステップの降下は $x_0=2$ からだと局所最小にすぎない $1.131$ で終わり、$x_0=-2$ からだと大域最小の $-1.301$ で終わります。$0.170$ の山の両側にある $x_0=0.1$ と $x_0=0.2$ のようにごく近い2つの出発点でも、別の谷に着きます。

鞍点はもう一つの罠です。そこでは勾配はゼロですが、ヘッセ行列は正負両方の固有値を持ち、関数はある方向では下がり別の方向では上がります。高次元では停留点の大半が鞍点で、単純な勾配降下法はその近くで這うように遅くなります。モメンタム、ミニバッチのノイズ、2次の情報は脱出の助けになります。広い範囲で勾配が極小の高原は、収束のように見えてそうではありません。

標準的な対策はリスタートです。$K$ 個の異なる出発点から最適化を走らせ、目的関数値が最も低い結果を残します。各出発点が独立に確率 $p$ で大域的な谷に着くなら、$K$ 回のうち少なくとも1回が着く確率は $1-(1-p)^K$ です。$p=0.2$、$K=10$ で $0.893$、$99\%$ に届くには $K\ge\ln0.01/\ln0.8=20.6$、つまり21回の出発が必要です。出発点そのものを良くすることも有効です。凸緩和の解、前日のキャリブレーション、最も重要な少数のパラメータに対するグリッド探索などです。

• 局所最小：降下は出発した谷で終わるので、出発点が答えを決めます。
• 鞍点と高原：最小値でないのに勾配がゼロか極小。モメンタムとノイズが助けになります。
• リスタート：$K$ 回の出発が成功する確率は $1-(1-p)^K$。最良の目的関数値を残します。

ラボ：採点される内容

• 大域最小値15点
• x = 2 から始める15点
• 近い2つの出発点15点
• ランダムリスタートの成功確率15点
• 何回のリスタートか15点
• 鞍点の近く10点
• リスタート結果の比較15点