最適化問題におけるステップサイズが大きいほど、収束速度が速くなり、数十年にわたる勾配降下法アルゴリズムの従来の考え方を覆すものとなった。

機械学習の世界では、最適化問題は非常に重要であり、世界をより良い方向に変える可能性があります。最適化問題は、携帯電話の GPS が目的地までの最短ルートを計算したり、旅行ウェブサイトが旅程に合った最も安い航空券を検索したりするなど、何かを達成するための最善の方法を求めます。一方、機械学習アプリケーションは、データ内のパターンを分析することで学習し、与えられた最適化問題に対して最も正確で人間に優しい答えを提供しようとします。

単純な最適化問題の場合、最適な解決策を見つけるのは単なる計算の問題です。 1847 年、フランスの数学者オーギュスタン＝ルイ・コーシーは、天文学的な計算というかなり複雑な例を研究しました。当時、彼は現在では勾配降下法として知られる一般的な最適化手法の先駆者であり、最適化手法の中で最も古典的かつ最も単純な一次手法の 1 つです。

現在、ほとんどの機械学習プログラムは、複雑さが少なく操作が簡単なため、勾配降下法に大きく依存しており、他の分野でもデータの分析やエンジニアリング問題の解決に勾配降下法が使用されています。数学者たちは100年以上にわたって勾配降下法の改良に取り組んできました。しかし、先月の論文では、勾配降下法に関する基本的な仮定が間違っている可能性があることが示されました。

この論文のタイトルは「長いステップによるより高速な勾配降下法の証明」であり、その唯一の著者はジョンズ・ホプキンス大学の応用数学および統計学の助教授であるベンジャミン・グリマー氏である。彼は発見したものにとても驚き、自分の直感が打ち砕かれたように感じた。

彼の直感に反する結果は、与えられた問題に対する最善の答えを見つけるための長年守られてきたルールを破れば、勾配降下法がほぼ 3 倍速くなる可能性があることを示しました。より具体的に言うと、研究者が長年信じてきたこととは反対に、予想外に大きなステップサイズを含めることで、勾配降下アルゴリズムをより高速に実行できると彼は主張しています。

論文アドレス: https://arxiv.org/pdf/2307.06324.pdf

この理論的進歩は機械学習のより難しい問題には当てはまらないかもしれないが、研究者に勾配降下法についての理解を再考させるきっかけとなるかもしれない。

「我々は勾配降下法の背後にある理論を完全には理解していないことが判明した」とMITの最適化研究者シュボモイ・ダス・グプタ氏は言う。「この研究により、勾配降下法の仕組みの理解に一歩近づくことになる」

ベンジャミン・グリマー

では、この作品の具体的な内容を見ていきましょう。

研究概要

この論文では、コンピュータ支援分析技術を使用して、滑らかな凸最適化における勾配降下法の収束速度が明らかに速くなることを実証します。ここで著者らは、非一定ステップサイズ戦略を考慮しながら、一次法のほとんどの分析で使用される典型的な単一反復誘導ではなく、複数反復の全体的な効果を分析します。

ステップ サイズを大きくすると短期的には目的の値が増加しますが、長期的には収束が確実に速くなることが示されています。さらに、著者らは簡単な数値検証を通じて、より速い O (1/T log T) 勾配降下速度を証明する仮説も提案しました。

具体的には、私たちの証明は、与えられたアルゴリズムの最悪ケースのパフォーマンスを計算または制約する問題インスタンスを半正定値プログラム (SDP) として扱うパフォーマンス推定問題 (PEP) の考え方に基づいています。関連する SDP の実行可能なソリューションの存在を通じて、著者らは非定数ステップ サイズ スキームを適用した後の下降保証を証明し、より高速な収束保証を獲得します。

実際には、より高速であることが証明される非定数ステップ サイズの勾配降下法を設計するということは、平均ステップ サイズ値が大きい単純なステップ サイズ パターンを見つけることに相当します。与えられたパターンの証明は簡単で、半正定値計画法を使用して達成できます。定理 3.1 を参照してください。

以下の表 1 は、より高速な収束保証を備えた直接ステップ サイズ パターンを示しています。各パターンは、コンピューターで生成された正確な算術半正定値計画法ソリューションを使用して検証されます。今後の作業では、より大きなステップ サイズを持つ直接モードと、一定でない周期的な大きなステップ サイズを処理できるその他の戦略が特定される予定です。

しかし、長くて直接的なステップサイズのパターン h を見つけることは難しく、すべての直接的なパターンの集合は非凸であるため、多くの場合、無駄なローカル検索が発生します。表1に示すように、長さt = 2^m−1のパターンは、t = 2^m−1 − 1を2回繰り返し、途中に新しい長いステップを追加し、長さ2^m−1 − 1のサブパターンの長いステップを手動で短くすることによって作成されます。著者らは、この再帰パターンは、以前の研究における二次最小化の巡回およびフラクタルチェビシェフパターンと強い類似性があるが、それらの間の関連性は証明されていないと述べている。

著者らは、このアプローチは、ペンシルバニア大学の最適化研究者であるジェイソン・アルトシュラー氏が最初に提案したアプローチと非常によく似ていると述べている。アルトシュラー氏は、長さ2または3のステップの繰り返しパターンを確立し、最小化に向かってより速く収縮することで、滑らかで強い凸型の最小化を達成した。

詳細については原文論文を参照してください。

小さな一歩から大きな一歩へ、長さの限界を突破

小さいステップ サイズの方が優れていることを証明した人はいませんが、この分野では何十年もの間、小さいステップ サイズを使用するのが常識でした。これは、勾配降下法の方程式では、ステップ サイズが 2 以下であることを意味します。

コンピュータ支援技術が進歩するにつれて、最適化理論家たちはその技術を極限までテストし始めました。たとえば、数学プログラミング誌に最近発表された研究では、ダス・グプタ氏と他の研究者は、50 ステップに制限されたアルゴリズムの最適なステップ サイズを見つけるようにコンピューターに要求しました。これは一種のメタ最適化問題です。最適な 50 ステップの長さは大きく異なり、シーケンス内の 1 ステップの長さは 37 近くに達し、一般的な長さの上限である 2 をはるかに上回っていることがわかりました。

論文アドレス: https://link.springer.com/article/10.1007/s10107-023-01973-1

この結果は、最適化研究者が何かを見逃していることを示唆しています。そこで、好奇心から、グリマーはダス・グプタの数値結果をより一般的な定理に変換しました。 50 ステップという恣意的な上限を破るために、彼は繰り返し可能なシーケンスの最適なステップ長を探求し、繰り返しごとに最適な答えに近づきました。グリマーは、コンピュータに歩数と長さのシーケンスの順列を何百万回も実行させ、最も速く答えに収束するものを見つけ出しました。

グリマーは、最も速いシーケンスには常に 1 つの共通点があることを発見しました。それは、中間のステップが常に大きく、そのサイズは繰り返しシーケンスのステップ数によって決まるということです。 3 ステップのシーケンスの場合、最大ステップ長は 4.9 です。15 ステップのシーケンスの場合、アルゴリズムは 29.7 のステップ長を推奨します。テスト内の最長の 127 ステップのシーケンスの場合、中央の最大ステップ長は 370 です。最終結果は、シーケンスが連続した小さなステップ速度よりも約 3 倍速く最適ポイントに到達することを示しています。

この理論は斬新だが、現在の用法を変えることはできない。

このループアプローチは、勾配降下法についての異なる考え方を表していると、フランスのパレゾー工科大学の最適化研究者であるエメリック・ディウルヴー氏は言う。 「問題を1段階ずつ考えるのではなく、連続して複数の段階に分けて考えるべきだというのが私の直感でした」と彼は語った。「多くの人がそれを見逃していると思います。」

しかし、これらの洞察は研究者の勾配降下法についての考え方を変えるかもしれないが、この手法の現在の使用方法は変わらないかもしれない。結局のところ、グリマーの論文は、鋭い曲がりのない滑らかな関数と、底に単一の最適値を持つボウルのような形をした凸関数にのみ焦点を当てていました。これらの機能は理論的には基本的なものですが、実際にはそれほど重要ではありません。機械学習の研究者が使用する最適化手順は、多くの場合、はるかに洗練されています。

モントリオール大学の最適化と機械学習の研究者であるゴーティエ・ギデル氏は、グリマー氏の大きなステップのアプローチを高速化できる改良された技術がいくつかあるが、それには追加コストがかかると述べている。そのため、人々は、ステップ サイズを適切に組み合わせることで、通常の勾配降下法が勝利することを期待してきました。残念ながら、新たな研究による3倍のスピードアップは十分ではない。

ギデル氏は「これはわずかな改善を示していますが、本当の疑問は、この差を本当に埋めることができるのか、ということだと思います」と問いかけた。

これらの結果は、著者らを夜も眠れぬままにさせるもう一つの理論的な謎も生み出している。歩幅の理想的なパターンがなぜこのように対称的な形になるのでしょうか?最も大きなステップが常にちょうど真ん中にあるだけでなく、その両側に同じパターンが表示されます。ズームインを続け、シーケンスを細分化すると、大きなステップが小さなステップに囲まれた「ほぼフラクタルなパターン」が得られます。この繰り返しは、根本的な構造が最適解を支配していることを示唆していますが、まだ誰もそれを説明できていません。

しかし、この記事の著者は少なくとも希望を抱いている。「私がこのパズルを解けなくても、他の誰かが解くだろう。」