e4exp
commented
3 years ago 1. introduction
STOCHASTIC approximation（SA）は、確率的探索アルゴリズムの重要な一分野である。
ニューラルネットワークのバックプロパゲーション、離散事象系の摂動解析、再帰的最小二乗法や最小平均二乗法、シミュレーテッドアニーリングなど、多くの有名な手法がSAの特殊なケースです。
したがって、一般的なSA手法の進歩は、幅広い実用的な実装に影響を与える可能性がある。
本論文では、SAアルゴリズムの収束を加速するためのアプローチを紹介する。
本質的なアイデアは、"simultaneous perturbation "という概念を用いて、最適化すべき損失関数のヘシアン行列（または、ルートファインディングのヤコビアン行列）を効率的かつ容易に推定することである。
このヘシアン行列は、決定論的最適化の有名なNewton-Raphsonアルゴリズムの確率論的アナログであるSA再帰で使用され、収束を促進します。
ここでは、微分可能な損失関数（スカラー）を最小化する問題を考えます。
典型的な例としては，設計パラメータの関数としてのプロセスの出力の平均二乗誤差の測定値が挙げられます．
実用的な多くのケースでは，これは，次のような一意の最小化を求めることと同じです．
勾配のない設定では，様々なthetaの値のときに，例えば，L(theta) の観測,たとえばy(theta) の測定値が得られると仮定している． これらの測定値には，ランダムなノイズが含まれていてもいなくてもよい． この設定では，（ノイズの有無にかかわらず） g(theta)の直接測定値は得られないものとします． 勾配ベースのケースでは、通常、ノイズが加わっていても、g(theta)の直接測定値が得られると仮定する。 基本的な問題は，利用可能な情報（L(theta)の測定値および／またはg(theta)）を用いて， theta* を推定することである． これは、基本的には局所的な制約のない最適化問題です（ただし、制約付き最適化のために微分可能なペナルティ関数を使用する場合は、この形式になります）。 SAの拡張として、複数のローカルミニマムが存在する場合の大域的な最適解を求めたり、制約条件が存在する場合の最適化があり（例えば、Styblinski and Tang [39]、Chin [5]、Kushner and Yin [15, pp.77-79, 100-101など]、Sadegh [29]を参照）、ここでのアプローチはこれらの拡張の文脈で適用されることが期待されますが、本稿ではこれらの一般化には焦点を当てません。 ここでの適応型同時摂動（ASP）アプローチは、2つの並列な再帰帰を作成するという単純なアイデアに基づいていますが、1つは推定用、もう1つはヘシアン行列の推定用です。 第1の再帰は、ニュートン-ラプソンアルゴリズムの確率的アナログであり、第2の再帰は、イテレーションごとのヘシアン推定値のサンプル平均を得る。 問題のすべてのパラメータを（1つずつではなく）一緒に変化させる同時摂動の考え方は2回目の再帰でのイテレーションごとのヘシアン推定値を形成するのに利用される。 これにより、2次適応アルゴリズムを実現するための効率的な手段となります。 特に、勾配なしのケースでは、任意の次元pの勾配とヘシアンの両方を推定するために、各反復において4つの関数測定y()のみが必要です。 勾配ベースのケースでは、各反復において3つの勾配測定が必要であり、これも任意の次元pに対して必要である(実用的な実装では、後述のセクションII-Dで議論するように、アルゴリズムの動作を確認するために1つ以上の追加値が有用である)。 ASPは比較的単純な適応的アプローチですが、他の2階調タイプのアプローチ（決定論的または確率論的）と同様に、実装には注意が必要です。 これには、初期条件の選択と、発散を避けるための「ステップサイズ」係数の選択が含まれます。 (これには、初期条件の選択や発散を避けるための「ステップサイズ」係数の選択が含まれます（ただし、以下の表記でステップサイズa_k = 1/k を選択するだけで、漸近的に最適またはそれに近い性能が得られます）。) これらの問題については、後のセクションで説明します。
適応型SAの概念は以前から知られていましたが（Venter[41]、Nevel'son and Has'minskii[23, ch.7]など）、その実装はあまり成功していません。 一般的な多変量問題の広い範囲で実用的に実装可能な適応型手法は提案されていないようです（例えば、「（ゲイン配列の）最適な選択は、リスク（損失）関数のヘシアンを含むが、これは一般的に未知であり、推定が困難である」Yakowitzら[44]より）。 その難しさを説明するために、既存のアプローチのいくつかをまとめてみましょう。 Fabian[10]は、適応型SAアルゴリズムの勾配とヘシアンの推定値を、それぞれ有限差分近似と有限差分近似の差分のセットを用いて形成しています。 これは、推定値thetaの更新ごとにO(p^2)測定を行うことになり、pが大きい場合には非常にコストがかかります。 Kaoら[13]は、決定論的最適化の準ニュートン法の類似性に基づいたヒューリスティックなアプローチを提示しています。 このアプローチでは、各反復において、O(p)関数の測定値y()に加えて、別の線探索のためのいくつかの追加測定値を使用します。 勾配ベースの場合、Ruppert [27]は、勾配測定値の有限差分を取ることで、ヘシアン推定値を形成します。 同様に、Wei[43]は、適応型Robbins-MonroアルゴリズムのためのVenter[41]およびNevel'son and Has'minskii[23, ch. 7]アプローチの多変量拡張を提案しています。 RuppertとWeiの両アプローチは、各反復についてO(p)の測定y()を必要とする。 これらのアプローチは、反復ごとに必要な関数や勾配の測定数が多くなる可能性がある点で、ASPアプローチとは異なります。 上記に関連して、基礎となるモデルの詳細な知識を持つ特別なSA推定の設定において、ヘシアン行列を適応的に推定する手段も数多く存在します（例えば、Macchi and Eweda [19]、Benvenisteら[1, ch. 3-4]、Ljung [17]、Yin and Zhu [45]を参照）。
Ruppert [28]やPolyak and Juditsky [25]が勾配ベースの場合に、Dippon and Renz [7]が勾配フリーの場合に報告している反復の平均化という概念も、SAの2次（最適またはそれに近い）収束の一形態を提供する。 この魅力的でシンプルなアイデアは、「基本的な」一次SA再帰から得られる反復のサンプル平均を、「.Learning」の最終的な推定値として使用することに基づいています。 勾配ベースのケースでは、平均化された反復の漸近的な平均二乗誤差は、確率的なニュートン-ラプソンのようなアルゴリズムで真のヘシアンを使用して得られるものと同じであることが示されます。 つまり，反復平均化法は，ヘシアン行列の知識や推定を必要とせずに，可能な限り最小の平均二乗誤差を達成することができる． 勾配のないケースでは，Dippon and Renz [7]によって定義された正確な意味で，反復平均解はほぼ漸近的に最適となります． いくつかの数値的な研究は、反復平均化の利点を支持している（例えば、Yin and Zhu [45]、Kushner and Yin [15, ch. 11]）。 しかし、筆者や他の研究者による有限サンプル分析（例えば、Maryak [21]、Spall and Cristion [38]、および、本稿のセクションV）は、反復平均化の漸近的な約束を実際に実現するのは難しいかもしれないことを示している。 これは考えてみれば当然のことです。 反復平均が成功するためには、個々の反復の大部分がほぼ一様にtheta in R^p 周辺で推移し、反復の平均が個々の反復の大部分よりもthetaに近い平均を生成することが必要である。 しかし，適切に設計された（「安定した」）アルゴリズムは，反復回数が解から離れているときにほぼ一様にtheta周辺で飛び回ることはないので（さもなければ発散する可能性がある），反復回数の大部分が解の周りに一様に分布するための唯一の方法は，個々の反復回数が解の近くにあることです． 適切に設計されたアルゴリズムを用いたほとんどの実用的な設定では、解に向かってtehtaの成分がほぼ（固有の確率的変動性を前提として）単調に移動することが観察され、反復回数の「予算」を超えたとき、または反復回数が非常にゆっくりと近くに移動し始めたとき（人は期待する！）に、ユーザーはアルゴリズムを終了します。 しかし、後者の状況は、まさに反復の平均化がうまく機能し始めるときです（実際には、アルゴリズムが単調な段階にある間は、反復の平均化は、まだtheta近くに落ち着いていないtheta 成分の精度を損なう傾向があります！）。 このことは、実用的な有限サンプル問題における反復平均化の役割は、その単純さと漸近的な正当性にもかかわらず、真の2次効率を達成することではないかもしれないことを示唆しています （1つの役割は、Kushner and Yin [15, ch.11]のように、平均化された解を反復プロセスにフィードバックすることで、アルゴリズムの安定性を高めることかもしれません）2。
セクションIIでは，一般的なASPアプローチについて説明し，基本的な一次SAアルゴリズムの同時摂動形式（すなわちSPSAアルゴリズム）に関連する本質的な方法論をまとめています。 このセクションでは，実際の実装においてユーザが考慮すべき実用的なガイドラインについてもまとめています。 セクションIIIおよび関連する付録AとBでは、ASPの理論的な正当性の一部を説明し、theta反復法とヘシアン推定法の両方がほぼ確実に収束するための条件を確立しています。 セクションIVと付録Aでは、この収束をもとに、勾配ベースの場合と勾配なしの場合の両方において、ASPの漸近的な正規性を証明しています。 最も重要なことは、セクションIVでは、漸近的正規性を用いて、ASPの反復の統計的推定誤差を分析し、誤差が漸近的に最適またはほぼ最適であることを示す。 セクションVではASPの数値解析を行い、セクションVIでは結論を述べる。
確率的近似法（Stochastic Approximation: SA）は，ノイズの多い入力情報を用いて損失関数を最小化したり，ルート探索を行ったりする問題に長年適用されてきた． 他の確率的探索アルゴリズムと同様に、アルゴリズムの係数を調整する必要があり、アルゴリズムの性能に大きな影響を与えます。 これらの係数を決定論的なニュートン-ラプソンアルゴリズムのSAアナログに従って選択すると、アルゴリズムの最適またはそれに近い形が得られることが知られています。 しかし、このアルゴリズム形式を実現するために必要なヘシアン行列（または根探しのためのヤコビ行列）を直接決定することは、実際には困難または不可能な場合が多かった。 この論文では、ヘシアン行列を推定する簡単な方法に基づいて、関心のある主要なパラメータを同時に推定する、一般的な適応型SAアルゴリズムを紹介する。 このアプローチは、勾配のない最適化（Kiefer-Wolfowitz）とルート探索/ストキャスティック勾配ベース（Robbins-Monro）の両方の設定に適用され、以前に紹介した「同時摂動（SP）」のアイデアに基づいています。 このアルゴリズムでは，問題の次元に関係なく，反復ごとに少数の損失関数または勾配の測定を行うだけで，ヘシアンと主要なパラメータを適応的に推定することができます． 本論文では、適応的SPアプローチの紹介に加え、実用的な実装方法、漸近理論、および自明ではない数値評価を示しています。 また，適応的SP法と反復平均法による加速SAを比較した議論と数値解析も行っている．