バックトラックライン検索

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

この方法では、直線探索方向に沿った移動のステップ サイズを比較的大きく見積もってから開始し、ステップ サイズと目的関数のローカル勾配に基づいて、予想される減少量に十分対応する目的関数の減少が観察されるまで、ステップ サイズを繰り返し縮小します (つまり、「バックトラッキング」)。一般的な停止基準は、Armijo-Goldstein 条件です。

バックトラッキング直線探索は、通常、勾配降下法(GD) に使用されますが、他のコンテキストでも使用できます。たとえば、ヘッセ行列が正定値である場合は、ニュートン法で使用できます。

開始位置と探索方向が与えられた場合、直線探索のタスクは、目的関数 を適切に削減するステップ サイズを決定すること（つまり、連続的に微分可能であると仮定）、つまりに対して削減されるの値を見つけることです。ただし、 を正確に最小化するの値を見つけるために大量のリソースを費やすことは通常望ましくありません。これは、ある特定の方向に沿ってより正確な最小値を見つけるために必要な計算リソースを、より適切な探索方向を識別するために使用できるためです。直線探索によって改善された開始点が特定されると、通常は新しい方向で別の直線探索が実行されます。つまり、目標は、を実際に最小化する値を見つけることではなく、目的関数を適度に改善する の値を特定することだけです。 ${\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} \ラングル }$${\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 の条件を満たすような正の数を見つける体系的な方法があるかどうかという疑問に答えるものです。 のとき、 の順序で選択できます 。ここで、 は点 付近の勾配の局所 Lipschitz 定数です( Lipschitz 連続性を参照)。関数 の場合、 は点 における関数のヘッセ行列に近くなります。詳細については、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) を含むアルゴリズムの説明がありますが、このアルゴリズムは引用された論文以前にはディープ ニューラル ネットワークでテストされていませんでした。)

双方向バックトラッキングと基本的な標準勾配降下アルゴリズムをハイブリッドに組み合わせることで、さらに時間を節約できます。この手順は、理論的な保証もテスト パフォーマンスも優れています。大まかに言うと、双方向バックトラッキングを数回実行し、関数値が増加する場合を除き、そのとき得られた学習率を変更せずに使用します。具体的な手順は次のとおりです。まず、数値と数値 を事前に選択します。 ${\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増やします。

より複雑な Wolfe の条件と比較すると、Armijo の条件の方が理論的に保証されています。実際、これまでのところ、バックトラッキング直線探索とその修正は、臨界点への収束と鞍点 の回避に関するすべての数値最適化アルゴリズムの中で最も理論的に保証された方法です(以下を参照)。

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

臨界点への収束について: たとえば、コスト関数が実解析関数である場合、収束が保証されることが Absil、Mahony & Andrews (2005) で示されています。主なアイデアは、実解析関数が享受するŁojasiewicz の不等式を使用することです。 Łojasiewicz の不等式を満たす滑らかでない関数の場合、上記の収束保証は拡張されます。Attouch、Bolte & Svaiter (2011) を参照してください。 Bertsekas (2016) では、バックトラック直線探索によって構築されたすべてのシーケンスについて、クラスター ポイント (つまり、サブシーケンスが収束する場合は 1 つのサブシーケンスの極限) が臨界点であることが証明されています。最大で可算個の臨界点を持つ関数（モース関数など）とコンパクトなサブレベル、および学習率 <1/L の標準 GD を使用する Lipschitz 連続勾配の場合（「確率的勾配降下法」のセクションを参照）、収束が保証されます。たとえば、Lange (2013) の第 12 章を参照してください。ここで、コンパクトなサブレベルに関する仮定は、ユークリッド空間のコンパクトなセットのみを扱うようにするためのものです。一般的なケースでは、 が であり、最大で可算個の臨界点を持つと仮定されるだけで、収束が保証されます。Truong & Nguyen (2020) を参照してください。同じ参考文献では、同様に、バックトラッキング直線探索の他の修正（「学習率の上限」のセクションで説明した無制限のバックトラッキング勾配降下法など）でも収束が保証されており、関数に非可算個の臨界点がある場合でも、収束の振る舞いについていくつかの重要な事実を推測できます。確率的設定では、勾配がリプシッツ連続であり、学習率減少スキームのより制限的なバージョン（学習率の合計が無限大で、学習率の二乗の合計が有限であることも必要）を使用するという同じ仮定の下で（「確率的勾配降下法」のセクションを参照）、さらに関数が厳密に凸である場合、よく知られている Robbins & Monro (1951) の結果で収束が確立されます。学習率減少スキームの制限が少ないバージョンへの一般化については、Bertsekas & Tsitsiklis (2006) を参照してください。これらの結果（非凸関数の場合）は、これまで他の最適化アルゴリズムでは証明されていません。^{[引用が必要]} ${\displaystyle f}$${\displaystyle C^{1}}$

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

言うまでもないことですが、コスト関数の勾配がリプシッツ連続で、リプシッツ定数 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 年にCauchyによって使用されて以来、ずっと古くから使用されており、標準 GD と呼ぶことができます (確率的勾配降下法と混同しないでください。確率的勾配降下法はここでは SGD と略されます)。確率的設定 (ディープラーニングのミニバッチ設定など) では、標準 GD は確率的勾配降下法、または SGD と呼ばれます。

コスト関数が大域的に連続した勾配を持つ場合でも、ディープラーニングのコスト関数の Lipschitz 定数の適切な推定は、ディープニューラルネットワークの非常に高い次元を考えると、実現可能または望ましくない可能性があります。したがって、標準 GD または SGD を適用する際には、学習率を微調整する手法があります。 1 つの方法は、いくつかの学習率が良好な結果をもたらすことを期待して、グリッド検索から多くの学習率を選択することです。 (ただし、損失関数が大域的な Lipschitz 連続勾配を持たない場合、上記の例はグリッド検索が役に立たないことを示しています。) もう 1 つの方法は、いわゆる適応型標準 GD または SGD で、代表的なものとしては Adam、Adadelta、RMSProp などがあります。確率的勾配降下法に関する記事を参照してください。適応型標準 GD または SGD では、学習率は各反復ステップ n で変化することが許可されていますが、勾配降下法のバックトラッキング直線探索とは異なる方法です。どうやら、バックトラッキング直線探索を勾配降下法に使用するとコストが高くなるようです。これは、アルミヨの条件が満たされるまでループ探索を行う必要があるのに対し、適応型標準 GD または SGD ではループ探索は必要ないからです。これらの適応型標準 GD または SGD のほとんどは、勾配降下法のバックトラッキング直線探索のように、すべての n に対して降下特性 を持ちません。この特性を持ち、優れた理論的特性を持つものはごくわずかですが、それらはバックトラッキング直線探索、またはより一般的にはアルミヨの条件 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 の標準 GD など、優れた理論的保証がある他のいくつかの方法は、どちらも目的関数の勾配がリプシッツ連続であること、バックトラッキング直線探索の特殊なケースであることが判明していること、またはアルミヨの条件を満たしていることを必要とします。この方法を適用するには、事前にコスト関数が連続的に微分可能である必要がありますが、実際には、またはなどの稠密な開部分集合上で連続的に微分可能な関数にもこの方法を適用できます。 ${\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偏導関数を持つ関数の最小化」。パシフィックJ.数学。16 （1）：1–3。doi ：10.2140 / pjm.1966.16.1。
• Attouch, H.; Bolte , J.; Svaiter, BF (2011). 「半代数的および慣性問題に対する降下法の収束: 近似アルゴリズム、前方-後方分割、および正規化ガウス-ザイデル法」。数学プログラミング。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 .
• Lange, K. (2013).最適化. ニューヨーク: Springer-Verlag Publications. ISBN 978-1-4614-5838-8。
• Dennis, JE ; Schnabel, RB (1996)。制約なし最適化と非線形方程式の数値解析法。フィラデルフィア: SIAM Publications。ISBN 978-0-898713-64-0。
• Lee, JD; Simchowitz, M.; Jordan, MI; Recht, B. (2016). 「勾配降下法は最小値にのみ収束する」。機械学習研究の議事録。49 : 1246–1257。
• ノセダル、ホルヘ、ライト、スティーブン 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 .
• Robbins, H.; Monro, 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。{{cite journal}}: CS1 maint: date and year (link)