極値

その点の近くで最大・最小になる点。 局所最適解と同じ概念。

必要条件#

$$\nabla f(x^{\star })=0$$

これを満たす点を停留点と呼ぶ。 極値なら停留点だが、逆は成り立たない（鞍点も停留点）。

十分条件#

ヘッセ行列で判定する。

$H(x^{\star })$	結論
正定値	狭義の極小
負定値	狭義の極大
不定	鞍点
半定値（0 固有値あり）	判定不能

高次元では鞍点が多い#

固有値の符号がランダムに決まると考えると、 $n$ 個すべてが同符号になる確率は $2^{-n}$ 程度。 つまり高次元の停留点はほとんどが鞍点になる。

Dauphin らは、深層学習の非凸最適化で問題になるのは 局所解より鞍点であると論じた。 勾配が消えるので進まないが、脱出方向は存在する。 SGD のノイズが 鞍点脱出に効くと考えられているのはこの文脈。

制約があるとき#

制約付きでは $\nabla f=0$ は成り立たない。 制約の境界で押さえられているため。 そこでの最適性条件がKKT 条件。

参考文献#

• Yann N. Dauphin et al. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. NeurIPS, 2014. https://arxiv.org/abs/1406.2572
• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5