A $\sqrt{2}$-accelerated FISTA for composite strongly convex problems

広大な、霧に包まれた谷の最低地点を探しているところだと想像してみてください。これは単なる谷ではありません。この谷の地面は、2種類の異なる素材でできています。一部分は、磨き上げられたアイススケートリンクのように滑らかで滑りやすい部分です。もう一方は、岩だらけの山道のように、ゴツゴツとしていて、突然の崖がある荒れた部分です。コンピュータサイエンスやデータの世界では、この「谷」は、顔を認識するスマートなAIを訓練したり、巨大な画像を圧縮する最善の方法を考え出したりといった、私たちが解決すべき複雑な問題を表現しています。通常、滑らかな部分は私たちが持っているデータを表し、荒れた部分は、解を単純または疎（スパース）に保つといった、私たちが従わなければならないルールを表しています。

この谷の底を見つけるために、コンピュータは「勾配降下法（グラディエント・ディセント）」と呼ばれる戦略を使います。これは、ハイカーが最も下り坂に感じられる方向に一歩踏み出す様子を想像してみてください。地面が滑らかであれば、ハイカーは素早く滑っていくことができます。しかし、地面がデコボコしていれば、ハイカーは立ち止まり、周囲を慎重に確かめ、注意深く一歩を踏み出さなければなりません。何十年もの間、科学的に知られている最高のハイカー（アルゴリズム）たちは、この底に到達することができましたが、特に谷の地形がトリッキーな場合、非常に長い時間がかかることがありました。彼らはジグザグに進んだり、行き過ぎたり、小さな窪みに捕まったりすることがあったのです。大きな問いは常にこうでした。「滑らかな部分では信じられないほど速く、かつ、荒れた部分でも慎重に動ける、迷うことのないハイカーを作れるだろうか？」

この論文は、SR2-FISTAという、超強力なハイカーを紹介しています。著者である植山寛聖氏は、これまでの既知の技術よりも速くこの混合地形を移動できる手法を設計しました。彼らは単に推測したのではなく、連続的な、流れるような動き（例えば、丘を下る川の流れのようなもの）を、コンピュータが実行できる一連の離散的なステップへと翻訳することで、この新しいハイカーを作り上げました。彼らの主な発見は、この新しいアルゴリズムが、以前のチャンピオンよりも大幅に速く谷の底に到達するということです。特に、谷が特定の形状（「強凸」であり、鋭く上向きに湾曲しており、単一の明確な底を保証している状態）を持つ場合に顕著です。

この論文は、この新しい手法が、速度の指数においてルート2（約1.41倍）の係数を含む特定の要因によって、数学的に速いことを証明しています。簡単に言えば、もし古い最良の手法が答えに近づくのに100ステップかかるとしたら、この新しい手法はより少ないステップで到達するか、あるいは同じ時間内に、より精密な答えに到達できるかもしれません。著者はまた、谷の「荒れた」部分が少し奇妙な形状（「弱凸」であり、技術的には完璧にデコボコしているわけではなく、緩やかな曲線を持っている状態）であっても、この手法が機能することを示しています。これは、医療画像や金融モデリングなどの実世界のシナルリオでよくあるケースです。彼らはこれをコンピュータ上でシミュレーションしただけでなく、このハイカーが必ず底を見つけるという厳密な数学的証明を提供し、さらにコンピュータが滑らかな部分の正確な滑らかさを知らない場合でも対処できる方法を示しました。

論文のストーリー

問題：混合地形の谷
この論文は、古典的な最適化問題に取り組んでいます。それは、$g(x)$ と $h(x)$ の和である関数 $f(x)$ の最小値を見つけることです。

• $g(x)$ は「滑らかな」部分です。滑らかで、うねるような丘を想像してください。滑り落ちるのは簡単ですが、非常に幅が広いかもしれません。
• $h(x)$ は「荒れた」部分です。ギザギザの岩場や壁を想像してください。滑らかに滑り降りることはできず、ジャンプするか、慎重に足を進めなければなりません。
• 目標： これら2つが合流する絶対的な最低地点を見つけることです。

現実の世界では、このようなことが常に起こっています。例えば、LASSO（統計学で使用される手法）では、$g(x)$ は予測と実際のデータの間の誤差（滑らか）であり、$h(x)$ は変数が多すぎることに対するペナルティ（荒れた、鋭い角のようなもの）である可能性があります。課題は、標準的な手法が、滑らかな部分でのスピードと、荒れた部分での慎重さのバランスを取るのに苦労することが多い点にあります。

旧チャンピオンとその欠陥
長年、「高速反復収縮閾値アルゴリズム（FISTA）」がゴールドスタンダードでした。これは、滑らかな部分で勢いを利用して加速しますが、岩の上では足を止めて足場を確認するハイカーのようなものです。それは速いのですが、限界があります。
また、ADR（加速デュアル正則化）と呼ばれる手法もあり、それがより速いと主張していました。しかし、本論文は、ADRは優れているものの、絶対的に最速ではないことを指摘しています。著者は、以前の手法には、谷の滑らかさと曲率の比の平方根を含む特定の公式によって決定される「速度制限」があったと述べています。

新しい発見：SR2-FISTA
著者は、SR2-FISTA（Square Root 2 Strongly Convex FISTA）と呼ぶ新しいアルゴリズムを提案しています。

• 構築方法： 単に古いステップを微調整するのではなく、彼らは物理学の観点からこの問題を見ました。彼らは、ITEM（情報理論的正確手法）と呼ばれる、連続時間モデル（粒子が時間をかけてどのように移動するかを記述する方程式）から出発しました。このモデルは、非常に特定の、変化する摩擦を持つ中で丘を滑り落ちる粒子を記述しています。
• 魔法の成分： このモデルにおける摩擦は一定ではなく、双曲線余弦関数（ファンシーな数学的曲線）によって記述されるように、時間の経過とともに変化します。この滑らかで流れるような動きを、コンピュータが実行できるステップへと注意深く「離散化」することで、彼らは新しいアルゴリズムを作り上げました。
• 結果： この論文は、この新しいアルゴリズムが、FISTAやADRよりも速い収束率で収束することを証明しています。具体的には、速度の公式における「指数」が $\sqrt{2}$ の係数によって改善されます。
  • もし古い手法が時速100マイルで走る車だとしたら、この新しい手法は、時間が経つにつれて効果が積み重なり、目的地に大幅に早く到着するような、より速い速度で走る車のようなものです。
  • 論文は、誤差（底までの距離）が、ステップごとに $(1 + \sqrt{2q})^{-k}$ という係数で減少することを示す数学的証明（定理6）を提供しています。ここで $q$ は、谷がいかに「強く」曲がっているかの尺度です。これは、以前の最良の収束率である $(1 + \sqrt{2q} - 6q)^{-k}$ よりも高速です。

「奇妙な」岩への対処
この論文のユニークな特徴は、「荒れた」部分（$h(x)$）が完全に凸ではない場合も扱うことです。数学的には、$h(x)$ は「弱凸」である可能性があります（わずかに逆方向に曲がっているかもしれませんが、問題全体を台無しにするほどではありません）。

• 古い手法の多くは、ユーザーが、荒れた部分を「扱いやすい（凸な）」ものに見えるように問題を書き換えることを要求していました。
• 著者の手法は、元の問題に対して直接機能します。たとえ荒れた部分が少し「揺らいで」いても、合計が依然として凸であれば（つまり、谷に底がある限り）、彼らのアルゴリズムは機能することを示しています。これは、ツールを使うために余計な数学の宿題をする必要がないことを意味するため、非常に大きな進歩です。

証明と数値
著者は自身の研究結果に非常に自信を持っています。単にシミュレーションを実行して「ほら、速いよ」と言ったのではありません。彼らは、リャプノフ関数（ハイカーが常に底に近づいていることを証明するエネルギーメーターのようなもの）を用いた厳密な数学的証明を提供しました。

• 彼らは、特定のタイプの問題（複合強凸）において、この手法が目的関数（谷の高さ）に対して既知の最速の収束率を達成することを証明しました。
• また、次元が10,000（非常に高次元の谷）の課題を用いた数値実験（セクション6）を実施しました。このテストにおいて、彼らのアルゴリズム（SR2FISTA）は、確かに従来のFISTAやADR手法よりも高速であり、理論を実践で裏付けました。

主張していないこと
この論文が主張していないことも重要です。

• 彼らは、あらゆるシナリオにおいて「絶対的に最速」のメソッドを見つけたとは主張していません。彼らの手法は、目的関数（$f(x_k) - f^*$）については最速である一方、文脈によっては、解への距離（$\|x_k - x^*\|^2$）においてより速いProx-ITEMと呼ばれる別の手法が存在することを認めています。しかし、本論文のような「荒れた（非滑らかな）」設定においては、距離の速度を常に目的関数の速度に変換できるわけではないため、目的関数の速度に関しては彼らの結果が最高となります。
• 彼らは、この手法が「非凸」問題（谷に複数の底があり、明確な経路がない場合）に機能するとは主張していません。彼らは、合計の問題が凸であることを厳格に求めています。

なぜこれが重要なのか
中学生やコンピュータがどのように学習するかに興味がある人にとって、この論文はレーシングカーのエンジンをアップグレードすることに似ています。すでに解決可能な問題を取り上げ、その解決をより速く、より効率的にします。データが指数関数的に増加している世界において、AIを訓練したり、複雑なエンジニアリング問題を解決したりする時間をわずか数パーセント短縮するだけでも、数百万ドルの費用と膨大な計算時間を節約できます。連続的な物理学に基づいた、数学的にエレガントなアプローチが、より速い離散アルゴリズムにつながることを証明することで、著者は、最も困難な最適化の課題に取り組むための、強力で新しいツールを私たちに提供したのです。