[offconvex和訳]How to Escape Saddle Points Efficiently
Saddle Pointを効率よく脱出する方法
Chi Jin and Michael Jordan, Jul 19, 2017 (訳 Hiroki Naganuma, May 29th, 2020)
この記事は、下記の記事を翻訳したものです。直感的な理解を目的として、一部解説を加え意訳している箇所もあります。
Saddle Pointを脱出する方法は、非凸最適化において核となる問題となっています。最近の研究では、勾配降下法(GD)が一般的にSaddle Pointを漸近的に脱出することが示されていますが、 (Rong Ge氏とBen Recht氏のブログ記事を参照)その効率性は重要な問題となっています。Saddle Pointを素早く抜けることができるのか、学習の速度を大きく遅らせてしまうのか？脱出の可能性(rate of escape)は次元数に応じてどのように変化するのでしょうか？この記事では、最近の研究(How to Escape Saddle Points Efficiently)について説明します。論文内で、効効率性の問題に対する最初の証明可能な答えを提供し、驚くべきことに、適切な摂動を加えたGDが効率的にSaddle Pointを逃れることを示します。実際には、収束速度と次元への依存性の観点から見ると、ほとんど鞍点が存在しないかのように見えます。
Perturbing Gradient Descent
ここでは、古典的な勾配降下法(GD)を考えます。つまり、関数f:R^{d}→Rが与えられた場合、負の勾配の方向に移動することで関数を最小化しようとします。
ここで 、η はstep sizeです。GDが理論的によく理解されていたのは凸関数における最適化の場合であって、一般化的な非凸最適化の場合はあまり研究されていませんでした。GDは非凸関数の最適化の場合、定常点(∇f(x)=0の点)の近くに素早く収束することがわかっていますが、これらの定常点は局所最小値や局所最大値、Saddle Pointである可能性があります。
GDが定常点(局所最大値であっても)から遠ざかることがないことは明らかです。したがって、ある程度のランダム性を組み込むためにGDを少し修正する必要があります。文献では2つの簡単な方法が研究されています。
Intermittent Perturbations: Ge, Huang, Jin, Yuan (2015)はGDにランダムな摂動を加えることによって、GDがSaddle Pointを多項式時間で回避することを初めて保証しました。(Rong Ge氏のブログを参照)
Random Initialization: Lee et al. 2016はランダムな初期化だけで、明示的にGDが漸近的に(すなわち、ステップ数が無限大になるにつれて)Saddle Pointを回避することを示しました。(Ben Recht氏のブログを参照)
漸近的な多項式時間でSaddle Pointを避けることができるという結果は一般的な理論にとっては重要ですが、実用的な非凸問題における勾配ベースのアルゴリズムの成功を説明するには不十分です。しかしながら、学習曲線が長時間にわたってフラットになる場合でも、漸近的な挙動がまだ始まっていないことをユーザーが知る由もありません。このように、GDが信頼できるというわけではありません。最後に、GDが高次元においても、凸最適化で知られるような有利な特性を持つことを保証するものはありません。
この問題に対する一つの合理的なアプローチは、二次(Hessian-baseed)アルゴリズムの検討です。これらのアルゴリズムは一般的にGDよりも反復あたりの計算コストがかなり高く、実装が複雑になりますが、効率的なSaddle Pointから逃れることを可能にする、Saddle Point周辺の幾何学的情報を提供します。そのため、先行研究にはHessian-baseedのアルゴリズムに関しての理解に関するが文献に出てきており、良い効率性の結果が得られています。
Is GD also efficient? Or is the Hessian necessary for fast escape of saddle points?
GDも効率的なのか？それともSaddle Pointを早急に脱出するにはヘッセ行列が必要なのか？この最初の問いに対しては、ランダムな初期化戦略を考えると、結果は否定的なものになります。実際、このアプローチは一般的に効率が悪いことが証明されており、最悪の場合、Saddle Pointを脱出するのに指数関数的な時間がかかります。(“On the Necessity of Adding Perturbations(摂動の追加の必要性について)”の項を参照)
しかしながら、摂動を与える戦略を考慮すると、かなり異なった、そして実証的な結果が得られることが判明しました。この結果を述べるために、我々が分析するアルゴリズムを明確にします。
ここでは摂動 ξt は適切に小さな半径を持つゼロを中心とした球から一様にサンプリングされ、 勾配が適当に小さいときに反復計算に加えられます。このような特別な選択は、解析的な目的のために行われます。このブログでは、一様なノイズが必要であるとは考えていません。また、勾配が小さいときにのみノイズが追加されることが必須であるとも考えていません。
Strict-Saddle and Second-order Stationary Points
このブログでは、Saddle Pointを、classicalなSaddle Pointと局所最大値の両方を含むものとして定義します。Saddle Pointは、少なくとも一方向に沿って局所的に最大化された停留値です。Saddle Pointと局所最小値は、ヘッセ行列の最小固有値によって下記のように分類されます。
さらに、λmin(∇2f(x))<0となる式中下のカテゴリのSaddle Pointを、Strict Saddle Pointと呼ぶことにします。
Non-strict Saddle Pointでは谷の中ではflatになりますが、Strict Saddle Pointは曲率が厳密に負の方向に沿った方向が少なくとも1つはある必要があります。このような方向が存在することで、勾配に基づくアルゴリズムはSaddle Pointを逃れる可能性があります。一般的に、局所最小値とNon-strict Saddle Pointを区別することはNP困難です。そのため、我々を含めこれまでの研究者たちはStrict Saddle Pointのエスケープに焦点を当ててました。形式的には、平滑性に関して以下の2つの標準的な仮定を行います。
古典的な理論では、一次定常点(∇f(x)=0)を求めるための反復回数を制限して、ϵ一次定常点|∇f(x)|≤ϵに収束することを研究しています。Strict Saddle Pointの脱出の速度と二次の定常点への収束を∇f(x)=0、λmin(∇²f(x))≧0としての定義をϵ-versionとして定式化します。
この定義では、ρは上で紹介したHessian Lipschitz 定数です。このスケーリングは Nesterov and Polyak 2006 の慣例に従う。
Applications
実用的な非凸関数の問題では広範囲において、すべてのSaddle PointがStrictであるということが証明されてきました。このような問題には、主成分分析、正準相関分析、直交制約付きテンソル分解、位相回復、matrix sensing、辞書学習、行列補完、およびその他の非凸における低ランク問題が含まれますが、これらに限定されるものではありません。さらに、これら全ての非凸問題において、全ての局所的最小値が大域的最小値であることも判明しています。したがって、上記のような場合には、ϵ二次定常点を求めるための一般的で効率的なアルゴリズムは、これらの非凸問題を大域的に保証して解くための効率的なアルゴリズムとなります。
Escaping Saddle Point with Negligible Overhead
一次の定常点の古典的なケースでは、GDは非常に有利な理論的性質を持つことが知られています。
Theorem(Nesterov 1998): 上述したAssumption 1 が成立する場合、η=1/ℓとなるGDは 2ℓ(f(x_0)-f*)/ϵ² 反復でϵ一次定常点に到達する。
この定理では、x_0 は初期点、f* は大域的最小となる関数値である。この定理によると、どんなgradient-Lipschitz関数でも、次元数d に明示的な依存をせずに、O(1/ϵ²) 反復のGDによって定常点を見つけることができることを示しています。これは元の文献内では”dimension-free optimization”と呼んでいます。もちろん、勾配計算のコストは O(d) であるため、GD の全体実行時間は O(d)として計算されます。dに関する線形スケーリングは、深層学習のような現代の高次元非凸問題では特に重要です。
ここでは、2次の定常点に対応する問題を取り上げます。私たちが期待できる最善の方法は何でしょうか？以下の方法は実現できるのでしょうか？
- dimension-freeな反復回数
- O(1/ϵ²) の収束率
- (Nesterov 1998)と同様に、ℓと(f(x_0)-f*)に依存する
驚くべきことに、小さな対数因子に関しても、上記3つすべてが可能です。
Main Theorem: Assumption1 と 2 が成立する場合、η=O(1/ℓ)のPerturbed gradient descent (PGD)は、O^{~}(ℓ(f(x_0)-f*)/ϵ²)の反復で、高確率でϵ二次定常点を見つけます。
ここで、O^{~}()は対数的な因子しか隠していません。 実際、私達の結果では次元への依存はlog⁴(d)だけです。
そのため上記の定理は、GDの摂動された形式では、Hessian-Lipschitz条件の下で、GDが一次の定常点に収束するのとほぼ同じ時間で二次の定常点に収束することを主張しています。この意味で、Perturbed gradient descent (PGD)がStrict Saddle Pointをほぼ自由に逃れることができることができます。
以下の章で、上記のの結果の根底にある直感のいくつかについての議論に移ります。
Why do polylog(d) iterations suffice?
Strict Saddle Pointの仮定では、最悪の場合、脱出できる方向はd次元の中で1つしかないということを意味しています。直感的には、降下方向の探索には少なくともpoly(d)の反復が必要ですが，なぜpolylog(d)だけで十分なのでしょうか？
関数が、Saddle Pointの近傍で二次関数であると仮定した簡単なケースを考えてみましょう。
すなわち、目的関数を f(x)=x⊤Hx とし、原点の Saddle Pointで、定数ヘシアン H=diag(-1,1,⋯,1) とします。この場合、最初の方向だけがSaddle Point脱出時の方向(固有値-1が負の方向)になります。この場合の反復の一般的な形式を計算することは簡単です。
Saddle Pointをゼロとし、ゼロを中心とした半径1の球B_0(1)からx_0が一様にサンプリングされるように摂動を加えます。関数値の減少分は以下のように表すことができます。
ステップサイズを 1/2 とし、λ_iをヘッセ行列Hのi番目の固有値とし、α_i=e_i⊤x_0 を初期点 x0 の i 番目の方向の成分とすると、∑²_{d_i=1} α²_i=|x_0|²=1となる。したがって以下の通りとなる。
単純な確率論では、B_0(1)で一様にサンプリングすると、高確率で少なくとも第1方向にΩ(1/d)成分が発生することを示しています。つまり、α²_1=Ω(1/d)となります。上記の式にα_1を代入すると、関数値を一定量だけ減少させるには、最大でもO(log d)反復が必要であることがわかります。
Pancake-shape stuck region for general Hessian
一定のヘッセ行列の場合、摂動x_0が集合{x| |e⊤_1x|²≤O(1/d)}∩B_0(1) に収束したときだけ、Saddle Point を脱出するのに非常に長い時間がかかると結論づけられます。この集合をstuck regionと呼んでいて、今回の場合は平坦な円盤状(flat disk)になっています。一般的に、ヘッセ行列が一定でなくなると、stuck regionは、左のグラフで緑色の物体として描かれているように、non-flat pancake型になります。
一般的にこの領域では解析的な式を持つことはありません。これまでのSaddle Point 周辺のダイナミクスを解析する試みでは、stuck region を平面集合で近似しようとしていました。その結果、非常に小さなステップサイズが必要となり、それに対応して膨大な計算量が要求されます。stuck region の形状はわかりませんが、非常に薄いことはわかっています。
このpancakeの “薄さ “を特徴づけるために、脱出の方向に沿ってO(1/√d)で区切られた仮想的な摂動点w,uの2点を研究しました。もし、wとuからGDを実行すると、結果として得られるtrajectoryのうち少なくとも1つは非常に速くSaddle Pointから脱出することがわかります。
このことは、stuck region の厚さが最大でもO(1/√d)であることを意味しており、そのためランダムな摂動が stuck region に収束する可能性はほとんどないことを示しています。
On the Necessity of Adding Perturbations
ここまで、標準的な勾配降下法のアルゴリズムを修正する2つの可能な方法を議論してきました。 前者は断続的な摂動を加えることで、後者はランダムな初期化に依存しています。後者は漸近的な収束を示すが、一般的には効率的な収束は得られません。Gradient Descent Can Take Exponential Time to Escape Saddle Points, NeurIPS2017 では、かなり自然なランダム初期化スキームと、”病的でない”関数を用いても、ランダム初期化のみを用いたGDはSaddle Pointによって著しく遅くなり、指数関数的に時間がかかることを示しています。Perturbed gradient descent (PGD)の挙動は衝撃的なほどに異なっていて、計算時間の観点からも優位にSaddle Pointを逃れることができます。この結果を確立するために、ガウス分布や超立方体上の一様分布を含む非常に一般的なクラスからのランダムな初期化を考慮し、Assumption1とAssumption2の両方を満たす滑らかな目的関数を構築しました。
この関数は、ランダムな初期化を行っても、高確率でGDとPGDの両方が局所的な最小値に到達する前に、d個のStrict Saddle Pointの近傍を順次移動しなければならないように構築されています。すべてのStrict Saddle Pointでは逃れる方向が一つしかありません。(d=2の場合は左のグラフを参照)
GDが一連のSaddle Pointの近傍を移動すると、後のSaddle Pointに更に近づいてしまい、その結果、逃げるのに時間がかかるようになります。実際、i番目のSaddle Pointを脱出する時間は、e_iとしてスケールします。一方、Perturbed gradient descen(PGD)は、これまでの挙動に依存しない少ないステップ数で常にどのSaddle Pointからも脱出することができます。この現象は、右上図の実験で確認されています(d=10の実験)。
Conclusion
この投稿では、摂動された形の勾配降下法 Perturbed gradient descent(PGD)が、標準的な勾配降下法において一次の定常点に収束するのとほぼ同じ速度で二次の定常点に収束することを示しました。このことは、Saddle Pointを効率的に逃れるためにヘッセ行列の情報は必要ないことを示唆しており、GD(およびSGD)のような基本的な勾配ベースのアルゴリズムが非凸の設定で驚くほどうまく機能する理由を説明するのに役立ちます。この新しい方法が効率的な収束したという結果によって、行列センシング/補完のような非凸問題に直接適用して、効率的なグローバルなConvergence Rateを確立させることができます。
もちろん、一般的な非凸最適化にはまだ多くの未解決の問いがあります。「Momentumを追加することで、二次の定常点への収束率が向上するのか？」といった課題や、「どのようなタイプの局所最小値が扱いやすいか？」「局所最小値を効率的に回避するために、局所最小値に構造的な仮定を課すことができるか？」などがあります。しかし、非凸最適化はゆっくりと、しかし着実に進展しています。ある時点で、現在の「黒魔術」のようなものから「サイエンス」になることが期待されています。
