tkm2261's blog

研究員(OR屋) → データ分析官 → MLエンジニア → ニート → 米国CS PhDが諸々書いてます

理研AIP主催Micheal Jordan先生最適化セミナー聴講メモ

お久しぶりです。

今日は10/20に参加した、理研AIPでのMicheal Jordan先生の講演のメモを書いていきたいと思います。

参加を許可頂いた理研AIPの方や司会の福水先生も良い会をありがとうございました。

Talk by Prof. Michael I. Jordan (University of California, Berkeley, USA) | 革新知能統合研究センター

In this post, I am writing about Prof. Micheal Jordan's speak at Riken AIP in Oct. 20th. If you have some problems about this post, please inform to @tkm2261 on Twitter.

いまはニートなので参加したセミナーの報告をする義務は全く無いのですが、やらないのもケツの座りが良くないので簡単なメモだけ書いていきます。

免責:私の拙いリスニング力に基づいて書かれているので、各自必要な箇所は調べて下さい。検索できるようにワードはなるべく残します。

間違っている箇所は積極的にコメントで教えて下さい

私の備忘のためでもあるので、不確かでも不確かなりに聴講すぐの時点のメモを残したいと思います。

タイトルと要約

webサイトの告知と異なり2つのトークを聞くことが出来ました。

  • Part I: Variational, Hamiltonian and Symplectic Perspectives on Acceleration
  • Part II: How to Escape Saddle Points Efficiently

両方共、連続最適化のお話です。

Part. I 要約

  • Nesterovの加速法を始めとした、加速法はBergman Lagrangianを考える事により微分方程式として統一的に議論できる
  • この時、全ての加速法は同じ経路を異なる時間で進んでいると解釈できる。
  • ただし、この解析は経路が連続(おそらくステップサイズが無限小取れる)時の議論で、これを単に離散化(discretization)した時は精度保証ができず、実験的にも不安定だった。
  • コレに対してSympletic integrationを用いて離散化した場合を解析する、Nesterovの加速法よりも速く、先行研究より安定したアルゴリズムが構築出来た?

最後の方は早くて少し聞き取れていません。

少し前の資料ですが、スライドはこれっぽい

https://www.sigmetrics.org/sigmetrics2017/MI_Jordan_sigmetrics2017.pdf

Part. II 要約

  • PCA、Tensor分解など、局所解に悩む場面は多い
  • これらの学習において、如何に鞍点を抜けるか、如何に効率よく鞍点を抜けるかが重要になってくる
  • GDやSGDでの鞍点に対する研究はいくつかある
    • GDは漸近的に局所解を抜ける?
    • GDが局所解を抜けるのに指数時間かかる場合がある。
    • SGDは鞍点を多項式時間で抜ける?
  • 彼らの研究はPerturbation Gradient Descent(PGD)がSecond Order Stationary Point(SOSP)に収束する事を示した。
  • (SOSPは、鞍点でなく停留点である度合いを2次まで考慮したものと思われ、First Order Stationary Pointへの収束を示した先行研究のよりも、より鞍点を避けて、より停留点と思われる点に収束できると思われる。)

おそらく↓が元ネタなので参照下さい。

[1703.00887] How to Escape Saddle Points Efficiently

講演メモ

初めに

  • 最適化とコンピュータ資源にはトレードオフがある

    • 凸緩和でのエラー
    • 並列実行でのエラー
    • 最適化オラクルの性能
    • community complexity?
    • subsampleing
  • 近年のデータ解析の分野でも重要な問題

  • アルゴリズムを開発するだけでなく、下界を得ることは様々な場面で有用。

Part I: Variational, Hamiltonian and Symplectic Perspectives on Acceleration

  • 加速勾配法はsublinearのオーダーで収束する

  • Nemirovski先生などが、90年台により優れた収束性を持つアルゴリズムはないかと研究。

  • 一般的にモーメント法として知られている

  • 加速法がどういった最適化オラクルにはいるのだろうか

  • まだまだ加速法はミステリアスで解析されていない。

  • 加速法の解釈にはいくつか研究がある

    • Chebyshev polynomial
    • Linear Coupling
    • etc...
  • しかし依然として謎があり、一体加速法の裏には何があるのだろうか?何故、一度下がって上がった方が収束が速いのだろうか?

  • 加速法を連続(continious time perspective)(恐らくステップサイズが無限小取れる)を考えると、Boyd先生の研究により微分方程式として定義できる。

  • Bregman Lagrangianを導入して、最適化問題をBergman Lagrangianの時間で積分した値の最小化として考える。

  • この時、全ての加速法は同じ経路を異なる時間で移動する手法と考える事ができる。(All accelerated methods are traveling the same curve in space-time at different speeds)

  • p=2のときはNesterovの加速法で、P=3のときはaccelerated cubic-regularized Newton’s methodになる。

  • ただこの解析は、連続の場合であり離散化(discretization)をする必要がある。

  • ただしそのまま離散化すると、収束性の理論保証がなく、経験的に不安定なアルゴリズムとなる。

  • そこでSympletic integrationを用いる。物理の分野では有名

  • (ただし、この手法においてはconverce vs quantitiesのトレードオフがあるらしく、スライド無いでは『Is it possible to find discretiztion whose solutions exactly conserve these same quantities? YES!!』と言っていたが、分かる方解説求む)

  • Bergman Hamiltonian上でSympletic integrationを考えるとNesterovの加速法よりも(実験的に)速いアルゴリズムが開発できた。

  • Gradient法と組み合わせると、より安定したアルゴリズムとなった。

Part II:How to Escape Saddle Points Efficiently

  • 悪い局所解はいつも問題である。

  • 如何に鞍点を抜けるか、如何に効率よく鞍点を抜けるかが重要である

  • GDやSGDでの鞍点に対する研究はいくつかある

    • GDは漸近的に局所解を抜ける?
    • GDが局所解を抜けるのに指数時間かかる場合がある。
    • SGDは鞍点を多項式時間で抜ける?
  • PCA、Tensor分解など、局所解に悩む場面は多い

  • 1980年にNesterovが勾配降下法(GD)がFirst Order Stationary Point(FOSP)に収束することを示した。

  • 本研究はPerturbation Gradient Descent(PGD)がSecond Order Stationary Point(SOSP)に収束する事を示した。

  • (FOSPやSOSPは鞍点でなく停留点である度合いを示していると思われ。Second orderだとより停留点っぽいところに収束できる事が示せると思われる)

  • 幾何学的な解釈をすると、高次元の場合、鞍点付近では取れる値の幅がとても薄くなる。(恐らく勾配がなだらかすぎて鞍点判別&抜け出すのが難しい事を言っていると思う。わかった方解説求む)

  • この薄さが問題を難しくしている。

  • 先行研究ではoverdamped Langevin diffusionを用いて収束に必要な反復回数がO(d/¥epsilon2)だったのに対し、本研究ではoverdamped Langevin diffusionを用いてO(¥sqrt(d)/¥epsilon)を達成した。(dは次元、イプシロンは目標精度)