バックトラッキングラインサーチ

（制約なし）数理最適化において、バックトラッキング直線探索は、与えられた探索方向に沿って移動する量を決定する直線探索法である。この手法を用いるには、目的関数が微分可能であり、かつその勾配が既知であることが必要である。

この手法では、直線探索方向に沿った移動のステップサイズを比較的大きく推定することから始め、ステップサイズと目的関数の局所勾配に基づいて期待される減少量に十分対応する目的関数の減少が観測されるまで、ステップサイズを反復的に縮小（すなわち「バックトラッキング」）します。一般的な停止基準は、アルミヨ・ゴールドスタイン条件です。

バックトラッキング直線探索は、典型的には勾配降下法（GD）で用いられますが、他の状況でも用いることができます。例えば、ヘッセ行列が正定値行列である場合、ニュートン法と組み合わせて用いることができます。

モチベーション

開始位置と探索方向が与えられた場合、直線探索のタスクは、目的関数を適切に削減するステップ サイズを決定すること（つまり、連続的に微分可能であると仮定）です。つまり、に対して減少するの値を見つけることです。ただし、 の値を見つけて を正確に最小化するために大量のリソースを費やすことは通常望ましくありません。これは、特定の 1 つの方向に沿ってより正確な最小値を見つけるために必要な計算リソースを、より適切な探索方向を識別するために使用できるためです。直線探索によって改善された開始点が特定されると、通常は新しい方向で別の直線探索が実行されます。つまり、目標は、 を実際に最小化する値を見つけることではなく、目的関数に妥当な量の改善をもたらす の値を特定することだけです。 ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \alpha >0}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle C^{1}}$ ${\displaystyle \alpha }$ ${\displaystyle f(\mathbf {x} +\alpha \,\mathbf {p} )}$ ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \alpha }$ ${\displaystyle f}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

バックトラッキング直線探索は、大きな推定値から開始し、それを反復的に縮小していく。この縮小は、局所関数の勾配に基づいて、目的関数の減少が達成されると思われる減少と十分に一致するほど小さい値が見つかるまで続けられる。${\displaystyle \alpha }$ ${\displaystyle \nabla f(\mathbf {x} )\,.}$

探索方向に沿った関数の局所的な傾きを と定義する（ここで はドット積を表す）。 は局所的に減少する可能性のあるベクトル、すなわち であると仮定する。 ${\displaystyle \alpha }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle m=\nabla f(\mathbf {x} )^{\mathrm {T} }\,\mathbf {p} =\langle \nabla f(\mathbf {x} ),\mathbf {p} \rangle }$ ${\displaystyle \langle \cdot ,\cdot \rangle }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle m<0}$

選択された制御パラメータに基づいて、アルミヨ・ゴールドスタイン条件は、現在の位置から修正された位置への段階的な移動が、 目的関数の適切な減少を達成するかどうかをテストする。この条件は、以下の条件を満たす場合満たされる（アルミヨ（1966）参照）。${\displaystyle c\,\in \,(0,1)}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} +\alpha \,\mathbf {p} }$ ${\displaystyle f(\mathbf {x} +\alpha \,\mathbf {p} )\leq f(\mathbf {x} )+\alpha \,c\,m\,.}$

この条件は、直線探索の一部として適切に使用すれば、ステップサイズが過度に大きくならないようにすることができます。しかし、この条件だけでは、ステップサイズがほぼ最適であることを保証するには不十分です。なぜなら、十分に小さい の値であれば、この条件を満たすからです。 ${\displaystyle \displaystyle \alpha }$

したがって、バックトラッキング直線探索戦略は、比較的大きなステップ サイズから開始し、 Armijo-Goldstein 条件が満たされるまで、 それを係数で繰り返し縮小します。${\displaystyle \tau \,\in \,(0,1)}$

およびの正の値が 1 未満の場合、探索は有限ステップ数後に終了します。たとえば、Armijo は、 Armijo (1966) で との両方に1 ⁄ 2 を使用しました。${\displaystyle c}$ ${\displaystyle \tau }$ ${\displaystyle c}$ ${\displaystyle \tau }$

アルゴリズム

この条件はArmijo (1966) によるものです。最大候補ステップサイズ値 から開始し、探索制御パラメータ および を用いると、バックトラッキング直線探索アルゴリズムは次のように表すことができます。 ${\displaystyle \alpha _{0}>0\,}$ ${\displaystyle \tau \,\in \,(0,1)}$ ${\displaystyle c\,\in \,(0,1)}$

1. 反復カウンタを設定します。${\displaystyle t=-c\,m}$ ${\displaystyle j\,=\,0}$
2. 繰り返し増分と設定が満たされるまで${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\alpha _{j}\,\mathbf {p} )\geq \alpha _{j}\,t,}$ ${\displaystyle j}$ ${\displaystyle \alpha _{j}=\tau \,\alpha _{j-1}\,.}$
3. 解決策として返します。${\displaystyle \alpha _{j}}$

つまり、Armijo–Goldstein 条件が満たされるまで、各反復で 係数を減らします。${\displaystyle \alpha _{0}}$ ${\displaystyle \tau \,}$

バックトラッキング直線探索を用いた関数最小化の実践

実際には、上記のアルゴリズムは通常、最小値が存在し、各ステップで適切に選択されることを条件として、最小値に収束するシーケンス,を生成するために反復されます。勾配降下法の場合、は として選択されます。 ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle n=1,2,...}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle -\nabla f(\mathbf {x} _{n})}$

アルミヨ・ゴールドスタイン条件を満たす に対する の値は および に依存するため、以下では と表記されます。 は、、にも依存しますが、これらの依存関係は、最適化問題に関して固定されていると仮定すれば暗黙的に残すことができます。 ${\displaystyle \alpha _{j}}$ ${\displaystyle j}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \alpha (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle f}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \tau }$ ${\displaystyle c}$

詳細な手順は以下のとおりです（Armijo（1966）、Bertsekas（2016）を参照）。

1. 初期の開始点を選択し、反復カウンタを設定します。${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle n=0}$
2. 何らかの停止条件が満たされるまで、下降方向 を選択し、位置を に更新し、 を増分します。${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}+\alpha (\mathbf {x} _{n},\mathbf {p} _{n})\,\mathbf {p} _{n}}$ ${\displaystyle n}$
3. 最小化位置と関数の最小値として返します。${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle f(\mathbf {x} _{n})}$

良好な動作を保証するためには、 がいくつかの条件を満たす必要があります。大まかに言えば、は からあまり離れてはいけません 。正確なバージョンは以下のとおりです（例えば、Bertsekas (2016)を参照）。以下の2つの条件を満たす定数があります。 ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \nabla f(\mathbf {x} _{n})}$ ${\displaystyle C_{1},C_{2}>0}$

1. すべての n について、です。ここで、は のユークリッド ノルムです。(これにより、 であれば も であることが保証されます。より一般的には、であれば も です。) より厳密なバージョンでは、逆の不等式も必要になります。つまり、正の定数 についてです。${\displaystyle \|\mathbf {p} _{n}\|\geq C_{1}\,\|\nabla f(\mathbf {x} _{n})\|}$ ${\displaystyle \|y\|}$ ${\displaystyle y}$ ${\displaystyle \mathbf {p} _{n}=0}$ ${\displaystyle \nabla f(\mathbf {x} _{n})=0}$ ${\displaystyle \lim _{n\rightarrow \infty }\mathbf {p} _{n}=0}$ ${\displaystyle \lim _{n\rightarrow \infty }\nabla f(\mathbf {x} _{n})=0}$ ${\displaystyle \|\mathbf {p} _{n}\|\leq C_{3}\,\|\nabla f(\mathbf {x} _{n})\|}$ ${\displaystyle C_{3}>0}$
2. すべての n について、 です 。(この条件は、と の方向が類似していることを保証します。)${\displaystyle \|\mathbf {p} _{n}\|\,\|\nabla f(\mathbf {x} _{n})\|\leq -C_{2}\,\langle \mathbf {p} _{n},\nabla f(\mathbf {x} _{n})\rangle }$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle -\nabla f(\mathbf {x} _{n})}$

学習率の下限

これは、関数 f、点、および降下方向に依存して 、すべての学習率がArmijoの条件を満たすような正の数を体系的に見つける方法があるかどうかという疑問に答えるものです。 のとき、 の 順に選択できます 。ここで、 は点 付近の勾配の局所リプシッツ定数です（リプシッツ連続性 を参照）。関数 が の場合、 は点 における関数のヘッセ行列に近くなります。詳細については、Armijo (1966) を参照してください。 ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \alpha \leq \beta (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$ ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle 1/L(\mathbf {x} )\,}$ ${\displaystyle L(\mathbf {x} )\,}$ ${\displaystyle \nabla f\,}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle C^{2}}$ ${\displaystyle L(\mathbf {x} )\,}$ ${\displaystyle \mathbf {x} }$

学習率の上限

の同じ状況において、興味深い疑問は、Armijoの条件（つまり、「バックトラッキング直線探索を用いた関数最小化の実践」のセクションで定義されているように に限界がない場合）において、どの程度大きな学習率を選択できるかということです。 が極限点（存在する場合）に近い場合、学習率を大きくすると収束が速くなるからです。例えば、Wolfeの条件ではについては言及されていませんが、曲率条件と呼ばれる別の条件が導入されています。 ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle \alpha _{0}}$

構築されたシーケンスが非退化臨界点に収束することを望む場合、学習率の上限が存在することが示されます。Truong & Nguyen (2020) を参照してください。学習率は、上からおおよそ によって制限される必要があります。ここで、H は極限点における関数のヘッシアン、はその逆関数、および線形演算子 のノルムです。したがって、この結果は、たとえば、モース関数に対してバックトラッキング直線探索を使用する場合に適用されます。次元 1 ではが数値であるため、この上限はセクション「学習率の下限」の下限と同じサイズである ことに注意してください 。${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle ||H||\times ||H^{-1}||^{2}}$ ${\displaystyle H^{-1}}$ ${\displaystyle ||.||}$ ${\displaystyle H}$

一方、極限点が退化している場合、学習率は無限大となる可能性があります。例えば、バックトラッキング直線探索の修正版である無限バックトラッキング勾配降下法（Truong & Nguyen (2020) 参照）では、学習率を の半分のサイズにすることができます。ここで は定数です。 のような単純な関数を用いた実験では、無限バックトラッキング勾配降下法は、「バックトラッキング直線探索を用いた関数最小化の実践」のセクションで説明した基本バージョンよりもはるかに速く収束することが示されています。 ${\displaystyle ||\nabla f(\mathbf {x} _{n})||^{-\gamma }}$ ${\displaystyle 1>\gamma >0}$ ${\displaystyle f(x,y)=x^{4}+y^{4}}$

時間効率

特に大規模最適化において、バックトラッキング直線探索の使用に反対する議論は、Armijo の条件を満たすのにコストがかかるというものです。これを回避する方法 (いわゆる双方向バックトラッキング) があり、理論的には十分な保証があり、ディープ ニューラル ネットワークで良好な結果が得られてテストされています。Truong & Nguyen (2020) を参照してください。 (そこでは、Cifar10 や Cifar100 などのデータセットで、Armijo の条件と、Momentum や NAG などの一般的なアルゴリズムとの組み合わせの適切で安定した実装も見つかります。) シーケンスが収束する場合 (反復最適化法を使用する場合の希望どおり)、n が十分に大きい場合、学習率のシーケンスはほとんど変化しないことがわかります。したがって、 の探索で、常に から開始すると 、シーケンスが から大きく離れていることが判明した場合に多くの時間を無駄にします 。代わりに、から開始して を検索する必要があります。 2つ目の観察結果は、が よりも大きくなる可能性があるので、学習率を増加させる必要がある（アルゴリズムの項で述べたように、単に減少させるのではなく）。双方向バックトラッキングの詳細なアルゴリズムは以下のとおりである。ステップnにおいて ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{n-1}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{n-1}}$

1. 設定します。設定と反復カウンタを設定します。${\displaystyle \gamma _{0}=\alpha _{n-1}}$ ${\displaystyle t=-c\,m}$ ${\displaystyle j\,=\,0}$
2. （Armijo の条件が満たされる場合は学習率を上げます。） の場合、この条件と の条件が満たされている間、j を繰り返し設定して増加させます。${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$ ${\displaystyle \gamma _{j}\leq \alpha _{0}}$ ${\displaystyle \gamma _{j+1}=\gamma _{j}/\tau }$
3. （そうでない場合、アルミヨの条件が満たされない場合は学習率を下げる。）対照的に、条件が満たされるまで繰り返し増分して設定する。${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{0}\,\mathbf {p} )<\gamma _{j}\,t,}$ ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$ ${\displaystyle j}$ ${\displaystyle \gamma _{j}=\tau \,\gamma _{j-1}\,.}$
4. 学習率を返します。${\displaystyle \gamma _{j}}$ ${\displaystyle \alpha _{n}}$

（Nocedal & Wright（2000）には、上記の1）、3）、4）を含むアルゴリズムの説明がありますが、引用された論文以前にはディープニューラルネットワークでテストされていませんでした。）

双方向バックトラッキングと標準的な勾配降下法を組み合わせたハイブリッド手法を用いることで、さらに時間を節約できます。この手法は理論的な保証も高く、テスト性能も良好です。大まかに言うと、双方向バックトラッキングを数回実行し、そこから得られる学習率を、関数値が増加する場合を除き、そのまま使用します。具体的な手順は以下のとおりです。まず、数値と数値 をそれぞれ 1 つずつ選択します。 ${\displaystyle N}$ ${\displaystyle m\leq N}$

1. 反復カウンタ j=0 を設定します。
2. 手順では、双方向バックトラッキングを使用します。${\displaystyle jN+1,\ldots ,jN+m}$
3. セット内の各ステップ k において、 を設定します。 の場合、および を選択します。（したがって、この場合は学習率は変更しません。） の場合、双方向バックトラッキングを使用します。 k を 1 ずつ増やして、これを繰り返します。${\displaystyle jN+m+1,\ldots ,jN+N-1}$ ${\displaystyle \alpha =\alpha _{k-2}}$ ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})\geq 0}$ ${\displaystyle \alpha _{k-1}=\alpha _{k-2}}$ ${\displaystyle x_{k}=x_{k-1}+\alpha _{k-1}p_{k-1}}$ ${\displaystyle \alpha _{k-2}}$ ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})<0}$
4. j を 1 増やします。

理論的保証（勾配降下法の場合）

より複雑なウルフの条件と比較すると、アルミヨの条件はより理論的な保証が優れています。実際、バックトラッキング直線探索とその修正法は、臨界点への収束と鞍点 の回避に関するあらゆる数値最適化アルゴリズムの中で、最も理論的に保証された手法です（下記参照）。

臨界点とは、目的関数の勾配が 0 になる点のことです。局所的最小値は臨界点ですが、局所的最小値ではない臨界点も存在します。一例として、鞍点が挙げられます。鞍点とは、関数が（局所的）最大値となる方向が少なくとも 1 つある臨界点のことです。したがって、これらの点は局所的最小値からはほど遠いものです。たとえば、関数に鞍点が 1 つ以上ある場合、その関数は凸関数にはなり得ません。鞍点と最適化アルゴリズムの関係は、大規模（つまり高次元）最適化では、最小値よりも鞍点の方が多い可能性が高いことです（Bray & Dean (2007) を参照）。したがって、優れた最適化アルゴリズムは鞍点を回避できる必要があります。ディープラーニングの設定でも、鞍点はよく見られます（Dauphin et al. (2014) を参照）。したがって、ディープラーニングに適用するには、非凸関数の結果が必要です。

臨界点への収束について：例えば、コスト関数が実解析関数である場合、収束が保証されることが Absil, Mahony & Andrews (2005) で示されています。基本的な考え方は、実解析関数が満たすŁojasiewicz 不等式を利用することです。Łojasiewicz不等式 を満たす滑らかでない関数の場合、上記の収束保証は拡張されます。Attouch, Bolte & Svaiter (2011) を参照してください。Bertsekas (2016) では、バックトラック直線探索によって構築されたすべてのシーケンスについて、クラスター点（つまり、サブシーケンスが収束する場合は、1つのサブシーケンスの極限）が臨界点であることが証明されています。最大可算個の臨界点を持つ関数（モース関数など）とコンパクト部分階数を持つ関数、および学習率 <1/L の標準勾配法（「確率的勾配降下法」のセクションを参照）を用いたリプシッツ連続勾配を持つ関数の場合、収束が保証されます。例えば、Lange (2013) の第12章を参照してください。ここでコンパクト部分階数に関する仮定は、ユークリッド空間のコンパクト集合のみを扱うことを確実にするためのものです。一般的なケース、つまり が であり、最大可算個の臨界点を持つと仮定される場合には、収束が保証されます。Truong & Nguyen (2020) を参照してください。同じ参考文献では、バックトラッキング直線探索の他の修正（「学習率の上限」のセクションで言及されている無制限バックトラッキング勾配降下法など）についても同様に収束が保証されており、関数が最大可算個の臨界点を持つ場合でも、収束挙動に関するいくつかの非自明な事実を推測することができます。 ${\displaystyle f}$ ${\displaystyle C^{1}}$

確率的設定において、勾配がリプシッツ連続であるという同じ仮定の下、学習率逓減法（「確率的勾配降下法」のセクションを参照）のより制限的なバージョン（学習率の和が無限大で、学習率の二乗和が有限であることも条件とする）を使用し、さらに関数が厳密に凸関数であるとすると、Robbins & Monro (1951) のよく知られた結果において収束が確立されます。より制限の少ない逓減法への一般化については、Bertsekas & Tsitsiklis (2006) を参照してください。これらの結果（非凸関数の場合）は、これまで他の最適化アルゴリズムでは証明されていません。^[要出典]

鞍点の回避について：例えば、コスト関数の勾配がリプシッツ連続であり、学習率が1/L未満の標準勾配降下法を選択した場合、初期点をランダムに選択すると（より正確には、ルベーグ測度零点の集合の外側）、構築されたシーケンスは非退化鞍点に収束しません（Lee et al. (2016)で証明済み）。また、より一般的には、構築されたシーケンスは退化鞍点に収束しないことも真です（Panageas & Piliouras (2017)で証明済み）。勾配がリプシッツ連続であり、学習率逓減法（「確率的勾配降下法」のセクションを参照）を使用するという同じ仮定の下で、鞍点の回避はPanageas、Piliouras & Wang (2019)で確立されています。 ${\displaystyle \mathbf {x} _{0}}$

特殊なケース: (標準) 確率的勾配降下法 (SGD)

言うまでもないことですが、コスト関数の勾配がリプシッツ連続で、リプシッツ定数 L の場合、学習率を定数として選択し、サイズ とすると、バックトラッキング直線探索の特殊なケース（勾配降下法）が得られます。これは、少なくとも Armijo (1966) で使用されています。ただし、この方式では L の適切な推定値が必要です。そうでない場合、学習率が大きすぎる（1/L に比べて）と、方式には収束の保証がありません。コスト関数が関数 f(t)=|t| の（点 0 付近の）平滑化である場合に問題が発生することは明らかです。ただし、このような適切な推定は、大きな次元では困難で面倒です。また、関数の勾配が全体的にリプシッツ連続でない場合も、この方式には収束の保証がありません。たとえば、これは Bertsekas (2016) の演習に似ており、コスト関数と、選択した一定の学習率に対して、ランダムな初期点を持つこの特別なスキームによって構築されたシーケンスは、グローバル最小値 0 に収束しません。 ${\displaystyle 1/L}$ ${\displaystyle f(t)=|t|^{1.5}\,}$

学習率が1/Lで制限されなければならないという条件を気にしないのであれば、この特別な手法はずっと以前から、少なくとも1847年にコーシーによって用いられており、標準GD（確率的勾配降下法（ここではSGDと略記）と混同しないように注意）と呼ぶことができます。確率的な設定（深層学習におけるミニバッチ設定など）では、標準GDは確率的勾配降下法（SGD）と呼ばれます。

コスト関数が大域的に連続した勾配を持っている場合でも、ディープラーニングのコスト関数の Lipschitz 定数の適切な推定は、ディープニューラルネットワークの次元が非常に高いことを考えると、実現不可能または望ましくない可能性があります。 そのため、標準の GD または SGD を適用する際に学習率を微調整する手法があります。 1 つの方法は、グリッド検索から多くの学習率を選択し、いくつかの学習率が良好な結果をもたらすことを期待することです。 (ただし、損失関数が大域的な Lipschitz 連続勾配を持たない場合、上記の例はグリッド検索が役に立たないことを示しています。) もう 1 つの方法は、いわゆる適応型標準 GD または SGD で、代表的なものとしては Adam、Adadelta、RMSProp などがあります。確率的勾配降下法に関する記事を参照してください。適応型標準 GD または SGD では、学習率は各反復ステップ n で変化できますが、勾配降下法のバックトラッキング直線探索とは異なる方法です。どうやら、バックトラッキング直線探索を勾配降下法に使用すると、Armijo の条件が満たされるまでループ探索を行う必要があるため、コストが高くなるようですが、適応型標準 GD または SGD ではループ探索は不要です。これらの適応型標準 GD または SGD のほとんどは、すべての n に対して、バックトラッキング直線探索による勾配降下法のような降下特性を持ちません。この特性を持ち、優れた理論的特性を持つものはごくわずかですが、それらはバックトラッキング直線探索、またはより一般的には Armijo の条件 Armijo (1966) の特殊なケースであることがわかります。 1 つ目は、前述のように、L を適切に推定できる場合に、学習率を定数 <1/L に選択する場合です。 2 つ目は、有名な論文 Robbins & Monro (1951) で使用されている、いわゆる減少学習率で、この場合も関数が全体的に Lipschitz 連続勾配を持ち (ただし Lipschitz 定数は不明な場合があります)、学習率が 0 に収束する場合です。 ${\displaystyle f(t)=|t|^{1.5}\,}$ ${\displaystyle f(x_{n+1})\leq f(x_{n})}$

まとめ

要約すると、バックトラッキング直線探索（およびその修正）は、実装が簡単で、非常に一般的な関数に適用でき、非常に優れた理論的保証（臨界点への収束と鞍点の回避の両方について）があり、実際にうまく機能する方法です。

逓減学習率や学習率が1/L未満の標準勾配法など、理論的に良好な保証を持つ他のいくつかの手法は、いずれも目的関数の勾配がリプシッツ連続であること、バックトラッキング直線探索の特殊なケースであること、またはアルミヨの条件を満たすことを要求します。この手法を適用するには、事前にコスト関数が連続微分可能であることが必要ですが、実際には、や のような稠密開集合上で連続微分可能な関数にもこの手法を適用できます。 ${\displaystyle f(t)=|t|}$ ${\displaystyle f(t)=ReLu(t)=\max\{t,0\}}$

参照

• 勾配降下法
• 確率的勾配降下法
• ウルフ条件

参考文献

• Absil, PA; Mahony, R.; Andrews, B. (2005). 「解析的コスト関数に対する降下法の反復収束」SIAM J. Optim. 16 (2): 531– 547. doi :10.1137/040605266.
• アルミジョ, ラリー (1966). 「リプシッツ連続な第1偏導関数を持つ関数の最小化」. Pacific J. Math . 16 (1): 1– 3. doi : 10.2140/pjm.1966.16.1 .
• Attouch, H.; Bolte, J.; Svaiter, BF (2011). 「半代数的問題およびTame問題に対する降下法の収束：近似アルゴリズム、順方向-逆方向分割、および正規化ガウス-ザイデル法」.数理計画. 137 ( 1–2 ): 91–129 . doi : 10.1007/s10107-011-0484-9 .
• Bertsekas, Dimitri P. (2016)、非線形計画法、Athena Scientific、ISBN 978-1886529052
• Bertsekas, DP; Tsitsiklis, JN (2006). 「誤差を考慮した勾配法における勾配収束」SIAM J. Optim. 10 (3): 627– 642. CiteSeerX  10.1.1.421.193 . doi : 10.1137/S1052623497331063 .
• Bray, AJ; Dean, DS (2007). 「大次元空間上のガウス場の臨界点の統計」. Physical Review Letters . 98 (15): 150– 201. arXiv : cond-mat/0611023 . Bibcode :2007PhRvL..98o0201B. doi : 10.1103/PhysRevLett.98.150201 . PMID  17501322.
• Dauphin, YN; Pascanu, R.; Gulcehre, C.; Cho, K.; Ganguli, S.; Bengio, Y. (2014). 「高次元非凸最適化における鞍点問題の特定と解決」NeurIPS . 14 : 2933–2941 . arXiv : 1406.2572 .
• ランゲ、K. (2013).最適化. ニューヨーク:シュプリンガー・フェアラーク出版. ISBN 978-1-4614-5838-8。
• デニス, JE ;シュナーベル, RB (1996).制約なし最適化と非線形方程式の数値解析法. フィラデルフィア: SIAM Publications. ISBN 978-0-898713-64-0。
• Lee, JD; Simchowitz, M.; Jordan, MI; Recht, B. (2016). 「勾配降下法は最小解にのみ収束する」. Proceedings of Machine Learning Research . 49 : 1246–1257 .
• Nocedal, Jorge ; Wright, Stephen J. (2000)、数値最適化、Springer-Verlag、ISBN 0-387-98793-2
• Panageas, I.; Piliouras, G. (2017). 「勾配降下法は最小解にのみ収束する：非孤立臨界点と不変領域」第8回理論計算機科学イノベーション会議 (ITCS 2017) (PDF) . ライプニッツ国際情報科学会議 (LIPIcs). 第67巻. ダグストゥール城 – ライプニッツ情報科学センター. pp. 2:1–2:12. doi : 10.4230/LIPIcs.ITCS.2017.2 . ISBN 9783959770293。
• Panageas, I.; Piliouras, G.; Wang, X. (2019). 「一次解法はほぼ常に鞍点を回避する：ステップサイズが消失する場合」（PDF） . NeurIPS . arXiv : 1906.07772 .
• ロビンズ, H.; モンロー, S. (1951). 「確率的近似法」. Annals of Mathematical Statistics . 22 (3): 400– 407. doi : 10.1214/aoms/1177729586 .
• Truong, TT; Nguyen, H.-T. (2020年9月6日). 「バックトラッキング勾配降下法と大規模最適化におけるいくつかの応用．第2部：アルゴリズムと実験」.応用数学と最適化. 84 (3): 2557– 2586. doi : 10.1007/s00245-020-09718-8 . hdl : 10852/79322 .