目的関数の最小化を考えましょう. 勾配法では,以下のようにパラメータを更新していきます.

はステップサイズ.

1ステップ分の更新を考えましょう. とすると,我々が示したいのは,

これだけではなにも議論できないので,これからは目的関数はリプシッツ連続 (Lipschitz continuous) だとします. ではまずリプシッツ連続の定義から始めましょう.

に対して,集合を以下の性質を有する集合とします.

  • はk回微分可能で連続
  • のp階微分とすると, .

この時はリプシッツ連続であるという.

今,目的関数がだとしましょう.この時,以下が成立します.

さて,再び勾配法による一回分の更新を考えましょう. とすると,(1)より,

したがって,,つまり,であれば,が言えます. つまり,当たり前かもしれませんが,勾配法によって関数が単調に減少するかはステップサイズの決め方に依存するということです. ここから,ステップサイズの決め方がいかに重要かがわかりますね.

問題なのはがわからないということです. もっともナイーブなステップサイズの決定方法はとして,適当にを決めてやることですが,これだと必ずしもとなっている保証はありません.そこで,なんらかの工夫が必要です.

基本的には,更新の際に,となるを選べば良いわけですが,どうやったら良いのでしょうか? 適当にを決めましょう.この時,となってしまったとします. この時の戦略は,を大きくするか,小さくするかです.どうしたらいいでしょう?

もしも,更新によって関数値が増加してしまう時,つまりの時,ステップサイズがとなっていることがわかります.ここから,となるまでを小さくしていけば良いことがわかります. これは,更新によって,局所解または最適解を通り過ぎてしまったので,通り過ぎない程度に引き戻すことに相当します. こんな感じでステップサイズを決めれば,一応目的関数は単調に減少していきます.

まとめると,勾配法を使う際に最低限考えなければならないことは,となるように更新することで,これはステップサイズの決定に委ねられる.ステップサイズは,を満たすように決めれば良いが,もしこれが満たされない場合はステップサイズを小さくしていけば良い.

こんな感じですかね.実際は,ステップサイズの決め方にもGoldstein-Armijo ruleとか,いろいろあるのでそれを使えばいいんですけどね.