確率的近似

Family of iterative methods

確率近似法は、求根問題や最適化問題に典型的に用いられる反復法の一種です。確率近似法の再帰更新規則は、収集されたデータがノイズによって乱れている場合の線形系の解法や、直接計算できずノイズを含む観測値から推定するしかない関数の極値を近似する場合などに用いられます。

簡単に言えば、確率近似アルゴリズムは、確率変数に依存する関数の期待値である形式の関数を扱います。その目的は、そのような関数を直接評価することなく、その特性を復元することです。代わりに、確率近似アルゴリズムは、のランダムサンプルを用いて、零点や極値などの特性を効率的に近似します。 ${\textstyle f(\theta )=\operatorname {E} _{\xi }[F(\theta ,\xi )]}$ ${\textstyle \xi }$ ${\textstyle f}$ ${\textstyle F(\theta ,\xi )}$ ${\textstyle f}$

近年、確率的近似は統計学や機械学習の分野、特にビッグデータを扱う環境において広く応用されています。これらの応用は、確率的最適化手法やアルゴリズムから、 EMアルゴリズムのオンライン版、時間的差分による強化学習、ディープラーニングなど多岐にわたります。^[1]確率的近似アルゴリズムは、社会科学においても集団ダイナミクスを記述するために用いられており、学習理論における架空の遊びやコンセンサスアルゴリズムをその理論を用いて研究することができます。^[2]

この種の最も初期の、そして典型的なアルゴリズムは、それぞれ 1951 年と 1952 年に導入されたRobbins–MonroアルゴリズムとKiefer–Wolfowitzアルゴリズムです。

ロビンズ・モンローアルゴリズム

1951年にハーバート・ロビンズとサットン・モンローによって導入されたロビンズ・モンローアルゴリズム^[3]は、関数 が期待値として表される根探索問題を解く手法を提示した。関数と定数 があり、方程式がで唯一の根を持つとする。関数 を直接観測することはできないが、代わりに となる確率変数 の測定値を得ることができると仮定する。このアルゴリズムの構造は、以下の形式の反復を生成することである。 ${\textstyle M(\theta )}$ ${\textstyle \alpha }$ ${\textstyle M(\theta )=\alpha }$ ${\textstyle \theta ^{*}.}$ ${\textstyle M(\theta ),}$ ${\textstyle N(\theta )}$ ${\textstyle \operatorname {E} [N(\theta )]=M(\theta )}$

$${\displaystyle \theta _{n+1}=\theta _{n}-a_{n}(N(\theta _{n})-\alpha )}$$

ここで、は正のステップサイズの列である。ロビンズとモンローは^{[3] 、定理2}が（したがって確率的にも）に収束することを証明した。また、ブルーム^[4]は後に、次の式が成り立つという条件のもとで、収束は確率1で起こることを証明した。 ${\displaystyle a_{1},a_{2},\dots }$ ${\displaystyle \theta _{n}}$ ${\displaystyle L^{2}}$ ${\displaystyle \theta ^{*}}$

• ${\textstyle N(\theta )}$一様境界があり、
• ${\textstyle M(\theta )}$非減少である、
• ${\textstyle M'(\theta ^{*})}$存在し、肯定的であり、
• シーケンスは次の要件を満たします。 ${\textstyle a_{n}}$

$${\displaystyle \qquad \sum _{n=0}^{\infty }a_{n}=\infty \quad {\mbox{ and }}\quad \sum _{n=0}^{\infty }a_{n}^{2}<\infty \quad }$$これらの条件を満たす特定のステップシーケンスは、ロビンズ・モンローによって提案され、に対して という形式をとります。 のような他の級数も可能ですが、 におけるノイズを平均化するには、上記の条件を満たす必要があります。 ${\textstyle a_{n}=a/n}$ ${\textstyle a>0}$ ${\displaystyle a_{n}={\frac {1}{n\ln n}},{\frac {1}{n\ln n\ln \ln n}},\dots }$ ${\textstyle N(\theta )}$

例

一連の独立したサンプルから確率分布の平均を推定する問題を考えてみましょう。 ${\displaystyle \theta ^{*}}$ ${\displaystyle X_{1},X_{2},\dots }$

とすると、 の唯一の解は望ましい平均 です。RMアルゴリズムは次式を与えます。これは、損失関数 を持つ確率的勾配降下法と同等です。また、加重平均とも同等です。一般に、となるような関数が存在する場合、ロビンス・モンローアルゴリズムは損失関数 を持つ確率的勾配降下法と同等です。ただし、RMアルゴリズムは収束するために が存在する必要はありません。 ${\displaystyle N(\theta ):=\theta -X}$ ${\textstyle \operatorname {E} [N(\theta )]=0}$ ${\displaystyle \theta ^{*}}$ $${\displaystyle \theta _{n+1}=\theta _{n}-a_{n}(\theta _{n}-X_{n})}$$ ${\displaystyle L(\theta )={\frac {1}{2}}\|X-\theta \|^{2}}$ $${\displaystyle \theta _{n+1}=(1-a_{n})\theta _{n}+a_{n}X_{n}}$$ ${\displaystyle L}$ ${\displaystyle \nabla L(\theta )=N(\theta )-\alpha }$ ${\displaystyle L(\theta )}$ ${\displaystyle L}$

複雑さの結果

1. が2回連続的に微分可能で、強凸であり、 の最小値がの内部に属する場合、ロビンズ・モンローアルゴリズムは目的関数に関して漸近的に最適な収束率 を達成し、 となる。ここで はにおけるの最小値である。^{[5] [6]} ${\textstyle f(\theta )}$ ${\textstyle f(\theta )}$ ${\textstyle \Theta }$ ${\textstyle \operatorname {E} [f(\theta _{n})-f^{*}]=O(1/n)}$ ${\textstyle f^{*}}$ ${\textstyle f(\theta )}$ ${\textstyle \theta \in \Theta }$
2. 逆に、滑らかさと強い凸性の両方の仮定を欠く一般的な凸の場合、NemirovskiとYudin ^[7]は、目的関数値に関する漸近的に最適な収束率は であることを示しました。彼らはまた、この収束率を改善できないことも証明しました。 ${\textstyle O(1/{\sqrt {n}})}$

その後の発展とポリアック・ルパート平均化

ロビンズ・モンローアルゴリズムは、2回連続微分可能かつ強凸性の仮定の下では理論的には良好な結果を達成できるものの、実装すると非常に低い性能となる可能性がある。これは主に、このアルゴリズムがステップサイズシーケンスの選択に非常に敏感であり、漸近的に最適なステップサイズポリシーが初期段階では非常に有害となる可能性があるためである。^{[6] [8]} ${\textstyle O(1/n)}$

Chung (1954) ^[9]と Fabian (1968) ^[10]は、 （または）のときに最適収束速度が達成されることを示した。Lai と Robbins ^{[11] [12]}は、漸近分散が最小となるようなを推定するための適応型手順を設計した。しかし、このような最適手法の適用には、多くの場合入手が困難な多くの事前情報が必要である。この欠点を克服するために、Polyak (1991) ^[13]と Ruppert (1988) ^[14]はそれぞれ独立に、軌道の平均化というアイデアに基づく新しい最適アルゴリズムを開発した。Polyak と Juditsky ^[15]はまた、線形および非線形の根探索問題に対して、より長いステップと反復の平均化を使用することで Robbins–Monro 法を加速する方法を提示した。このアルゴリズムは次の構造を持つ。が唯一の根に収束するためには、ステップシーケンスが十分にゆっくりと減少するという条件に依存する。つまり、 ${\textstyle O(1/{\sqrt {n}})}$ ${\textstyle a_{n}=\bigtriangledown ^{2}f(\theta ^{*})^{-1}/n}$ ${\textstyle a_{n}={\frac {1}{(nM'(\theta ^{*}))}}}$ ${\textstyle M'(\theta ^{*})}$ ${\textstyle \theta _{n}}$ $${\displaystyle \theta _{n+1}-\theta _{n}=a_{n}(\alpha -N(\theta _{n})),\qquad {\bar {\theta }}_{n}={\frac {1}{n}}\sum _{i=0}^{n-1}\theta _{i}}$$ ${\displaystyle {\bar {\theta }}_{n}}$ ${\displaystyle \theta ^{*}}$ ${\displaystyle \{a_{n}\}}$

A1) $${\displaystyle a_{n}\rightarrow 0,\qquad {\frac {a_{n}-a_{n+1}}{a_{n}}}=o(a_{n})}$$

したがって、 のシーケンスはこの制約を満たしているが、実際には満たしていないため、ステップが長くなります。ロビンズ・モンローアルゴリズムで概説されている仮定の下では、結果として得られる修正は、同じ漸近的に最適な収束率をもたらしますが、より堅牢なステップサイズポリシーが適用されます。^[15]これに先立ち、より長いステップを使用して反復を平均化するというアイデアは、連続凸目的関数を持つ確率的最適化問題や凸凹鞍点問題を解く場合について、ネミロフスキーとユディンによって既に提案されていました^[16]。これらのアルゴリズムは、非漸近的な収束率 を達成することが確認されています。 ${\textstyle a_{n}=n^{-\alpha }}$ ${\textstyle 0<\alpha <1}$ ${\textstyle \alpha =1}$ ${\textstyle O(1/{\sqrt {n}})}$ ${\textstyle O(1/{\sqrt {n}})}$

より一般的な結果は、クシュナーとイェン^[17]の第11章で、補間時間、補間プロセス、補間正規化プロセスを次のように 定義することによって示されています。 ${\textstyle t_{n}=\sum _{i=0}^{n-1}a_{i}}$ ${\textstyle \theta ^{n}(\cdot )}$ ${\textstyle U^{n}(\cdot )}$

$${\displaystyle \theta ^{n}(t)=\theta _{n+i},\quad U^{n}(t)=(\theta _{n+i}-\theta ^{*})/{\sqrt {a_{n+i}}}\quad {\mbox{for}}\quad t\in [t_{n+i}-t_{n},t_{n+i+1}-t_{n}),i\geq 0}$$反復平均を、関連する正規化誤差を とします。 ${\displaystyle \Theta _{n}={\frac {a_{n}}{t}}\sum _{i=n}^{n+t/a_{n}-1}\theta _{i}}$ ${\displaystyle {\hat {U}}^{n}(t)={\frac {\sqrt {a_{n}}}{t}}\sum _{i=n}^{n+t/a_{n}-1}(\theta _{i}-\theta ^{*})}$

仮定A1)と次の仮定A2)に基づき

A2) が に弱収束するような、フルヴィッツ行列と対称正定値行列があります。ここで は の定解であり、は標準ウィーナー過程です。 ${\textstyle A}$ ${\textstyle \Sigma }$ ${\textstyle \{U^{n}(\cdot )\}}$ ${\textstyle U(\cdot )}$ ${\textstyle U(\cdot )}$ $${\displaystyle dU=AU\,dt+\Sigma ^{1/2}\,dw}$$ ${\textstyle w(\cdot )}$

が満たされ、 と定義する。そして、各 に対して、 ${\textstyle {\bar {V}}=(A^{-1})'\Sigma (A')^{-1}}$ ${\textstyle t}$

$${\displaystyle {\hat {U}}^{n}(t){\stackrel {\mathcal {D}}{\longrightarrow }}{\mathcal {N}}(0,V_{t}),\quad {\text{where}}\quad V_{t}={\bar {V}}/t+O(1/t^{2}).}$$

平均化のアイデアが成功したのは、元のシーケンスと平均化されたシーケンスの時間スケールが分離されており、前者の時間スケールの方が高速であるためです。 ${\textstyle \{\theta _{n}\}}$ ${\textstyle \{\Theta _{n}\}}$

確率的最適化への応用

が微分可能かつ凸である次の確率的最適化問題を解くとすると、この問題はの根を求めることと等価です。ここで は、選択された効果とランダム効果の関数としての「観測された」コストとして解釈できます。実際には の解析的な形を得るのは難しいかもしれませんが、ロビンス・モンロー法はを近似する系列を生成することができます。ただし、 の条件付き期待値がちょうど となるようなを生成できれば、つまり は で定義される条件付き分布からシミュレートされます。 $${\displaystyle g(\theta ^{*})=\min _{\theta \in \Theta }\operatorname {E} [Q(\theta ,X)],}$$ ${\textstyle g(\theta )=\operatorname {E} [Q(\theta ,X)]}$ ${\displaystyle \theta ^{*}}$ ${\displaystyle \nabla g(\theta )=0}$ ${\displaystyle Q(\theta ,X)}$ ${\displaystyle \theta }$ ${\displaystyle X}$ ${\displaystyle \nabla g(\theta )}$ ${\displaystyle (\theta _{n})_{n\geq 0}}$ ${\displaystyle \theta ^{*}}$ ${\displaystyle (X_{n})_{n\geq 0}}$ ${\displaystyle X_{n}}$ ${\displaystyle \theta _{n}}$ ${\displaystyle \nabla g(\theta _{n})}$ ${\displaystyle X_{n}}$

$${\displaystyle \operatorname {E} [H(\theta ,X)|\theta =\theta _{n}]=\nabla g(\theta _{n}).}$$

の不偏推定値 です。が に依存する場合、一般に、勾配の不偏推定値となるランダムな結果を生成する自然な方法はありません。IPA法または尤度比法のいずれかが適用可能な特殊なケースでは、不偏勾配推定値 を得ることができます。 を とは独立に生成される「基本的な」ランダム過程と見なし、かつ となるような微分積分​​交換演算の正規化条件の下で生成される場合、 は基本勾配の不偏推定値を与えます。ただし、一部の用途では、 の条件付き期待値が に近いものの完全には等しくない差分法を使用する必要があります。 ${\displaystyle H(\theta ,X)}$ ${\displaystyle \nabla g(\theta )}$ ${\displaystyle X}$ ${\displaystyle \theta }$ ${\displaystyle H(\theta ,X)}$ ${\displaystyle H(\theta ,X)}$ ${\displaystyle X}$ ${\displaystyle \theta }$ ${\displaystyle \operatorname {E} {\Big [}{\frac {\partial }{\partial \theta }}Q(\theta ,X){\Big ]}=\nabla g(\theta )}$ ${\displaystyle H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)}$ ${\displaystyle H(\theta ,X)}$ ${\displaystyle \nabla g(\theta )}$

最小化を根を求める問題と同一視することで、ロビンス・モンローアルゴリズムと同様に、確率近似を適用して最小値の再帰解を定義することができる。 ${\displaystyle \nabla g(\theta )=0}$

$${\displaystyle \theta _{n+1}=\theta _{n}-\varepsilon _{n}H(\theta _{n},X_{n+1}).}$$

アルゴリズムの収束

次の結果は、アルゴリズムが収束するための十分な条件を示している：^[18] ${\displaystyle \theta _{n}}$

C1) ${\displaystyle \varepsilon _{n}\geq 0,\forall \;n\geq 0.}$

C2) ${\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}=\infty }$

C3) ${\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}^{2}<\infty }$

C4) ${\displaystyle |X_{n}|\leq B,{\text{ for a fixed bound }}B.}$

C5) ${\displaystyle g(\theta ){\text{ is strictly convex, i.e.}}}$

$${\displaystyle \inf _{\delta \leq |\theta -\theta ^{*}|\leq 1/\delta }\langle \theta -\theta ^{*},\nabla g(\theta )\rangle >0,{\text{ for every }}0<\delta <1.}$$

すると、ほぼ確実に収束します。 ${\displaystyle \theta _{n}}$ ${\displaystyle \theta ^{*}}$

これらの条件について、直感的な説明をいくつか示します。 が一様有界確率変数であると仮定します。C2) が満たされない場合、つまり の場合、は有界列となり、初期推定値が から大きく離れていると、反復計算は に収束しません。C3) に関しては、がに収束する場合、 ${\displaystyle H(\theta _{n},X_{n+1})}$ ${\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}<\infty }$ $${\displaystyle \theta _{n}-\theta _{0}=-\sum _{i=0}^{n-1}\varepsilon _{i}H(\theta _{i},X_{i+1})}$$ ${\displaystyle \theta ^{*}}$ ${\displaystyle \theta _{0}}$ ${\displaystyle \theta ^{*}}$ ${\displaystyle \theta _{n}}$ ${\displaystyle \theta ^{*}}$

$${\displaystyle \theta _{n+1}-\theta _{n}=-\varepsilon _{n}H(\theta _{n},X_{n+1})\rightarrow 0,{\text{ as }}n\rightarrow \infty .}$$したがって，が成り立つ必要があり，条件C3)はそれを保証します。自然な選択は です。条件C5)は の形状に関するかなり厳しい条件であり、アルゴリズムの探索方向を与えます。 ${\displaystyle \varepsilon _{n}\downarrow 0}$ ${\displaystyle \varepsilon _{n}=1/n}$ ${\displaystyle g(\theta )}$

例（確率的勾配法が適切な場合）

を仮定する。ここでは微分可能であり、は に依存しない確率変数である。この場合、は の平均に依存し、この問題には確率的勾配法が適切であろう。^[8] ${\displaystyle Q(\theta ,X)=f(\theta )+\theta ^{T}X}$ ${\displaystyle f}$ ${\displaystyle X\in \mathbb {R} ^{p}}$ ${\displaystyle \theta }$ ${\displaystyle g(\theta )=\operatorname {E} [Q(\theta ,X)]=f(\theta )+\theta ^{T}\operatorname {E} X}$ ${\displaystyle X}$ ${\displaystyle H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)={\frac {\partial }{\partial \theta }}f(\theta )+X.}$

キーファー・ウォルフォウィッツアルゴリズム

キーファー・ウォルフォウィッツアルゴリズムは、1952年にジェイコブ・ウォルフォウィッツとジャック・キーファー^[19]によって導入され、ロビンズ・モンローアルゴリズムの発表に触発されたものである。しかし、このアルゴリズムは関数の最大値の確率的推定法として提示された。

点 で最大値をとる関数を とする。は未知であると仮定する。しかし、 （ただし ）という特定の観測は、任意の点 において行うことができる。アルゴリズムの構造は勾配法に類似しており、反復は次のように生成される。 ${\displaystyle M(x)}$ ${\displaystyle \theta }$ ${\displaystyle M(x)}$ ${\displaystyle N(x)}$ ${\displaystyle \operatorname {E} [N(x)]=M(x)}$ ${\displaystyle x}$

${\displaystyle x_{n+1}=x_{n}+a_{n}\cdot \left({\frac {N(x_{n}+c_{n})-N(x_{n}-c_{n})}{2c_{n}}}\right)}$

ここで、 とは独立です。各ステップにおいて、 の勾配はを用いた中心差分法に類似した近似値で近似されます。したがって、 列は勾配近似に用いられる有限差分幅の列を指定し、 列はその方向に沿った正のステップサイズの列を指定します。 ${\displaystyle N(x_{n}+c_{n})}$ ${\displaystyle N(x_{n}-c_{n})}$ ${\displaystyle M(x)}$ ${\displaystyle h=2c_{n}}$ ${\displaystyle \{c_{n}\}}$ ${\displaystyle \{a_{n}\}}$

KieferとWolfowitzは、ある一定の正則性条件が満たされれば、がの確率でに収束することを証明し、その後Blum ^[4]は1954年に、次の条件が満たされれば、がほぼ確実にに収束することを示した。 ${\displaystyle M(x)}$ ${\displaystyle x_{n}}$ ${\displaystyle \theta }$ ${\displaystyle n\to \infty }$ ${\displaystyle x_{n}}$ ${\displaystyle \theta }$

• ${\displaystyle \operatorname {Var} (N(x))\leq S<\infty }$すべてのために。 ${\displaystyle x}$
• この関数は唯一の最大値（最小値）を持ち、強い凹状（凸状）である。 ${\displaystyle M(x)}$
  • このアルゴリズムは、関数が実行可能空間全体にわたって強い大域的凸性（凹性）を維持するという要件を伴って初めて提示されました。この条件は領域全体に課すには制約が厳しすぎるため、キーファーとウォルフォウィッツは、最適解を含むことが知られているコンパクト集合にこの条件を課せば十分であると提案しました。 ${\displaystyle M(\cdot )}$ ${\displaystyle C_{0}\subset \mathbb {R} ^{d}}$
• この関数は次のような正則性条件を満たします。 ${\displaystyle M(x)}$
  • が存在し、 ${\displaystyle \beta >0}$ ${\displaystyle B>0}$ $${\displaystyle |x'-\theta |+|x''-\theta |<\beta \quad \Longrightarrow \quad |M(x')-M(x'')|<B|x'-x''|}$$
  • が存在し、 ${\displaystyle \rho >0}$ ${\displaystyle R>0}$ $${\displaystyle |x'-x''|<\rho \quad \Longrightarrow \quad |M(x')-M(x'')|<R}$$
  • 任意の に対して、 が存在する。 ${\displaystyle \delta >0}$ ${\displaystyle \pi (\delta )>0}$ $${\displaystyle |z-\theta |>\delta \quad \Longrightarrow \quad \inf _{\delta /2>\varepsilon >0}{\frac {|M(z+\varepsilon )-M(z-\varepsilon )|}{\varepsilon }}>\pi (\delta )}$$
• 選択されたシーケンスとは次の条件を満たす正の数の無限シーケンスでなければならない。 ${\displaystyle \{a_{n}\}}$ ${\displaystyle \{c_{n}\}}$
  • ${\displaystyle \quad c_{n}\rightarrow 0\quad {\text{as}}\quad n\to \infty }$
  • ${\displaystyle \sum _{n=0}^{\infty }a_{n}=\infty }$
  • ${\displaystyle \sum _{n=0}^{\infty }a_{n}c_{n}<\infty }$
  • ${\displaystyle \sum _{n=0}^{\infty }a_{n}^{2}c_{n}^{-2}<\infty }$

Kiefer と Wolfowitz が推奨する適切なシーケンスの選択は、およびです。 ${\displaystyle a_{n}=1/n}$ ${\displaystyle c_{n}=n^{-1/3}}$

その後の展開と重要な問題

1. Kiefer-Wolfowitzアルゴリズムでは、各勾配計算において、アルゴリズムの反復ごとに少なくとも異なるパラメータ値をシミュレートする必要があります。ここで、は探索空間の次元です。つまり、が大きい場合、Kiefer-Wolfowitzアルゴリズムは反復ごとにかなりの計算量を必要とし、収束が遅くなります。 ${\displaystyle d+1}$ ${\displaystyle d}$ ${\displaystyle d}$
   1. この問題に対処するため、スポールは同時摂動を用いて勾配を推定することを提案した。この手法では、次元に関わらず、反復ごとに2回のシミュレーションのみが必要となる。^[20] ${\displaystyle d}$
2. 収束に必要な条件において、強い凸性（または凹性）を満たし、かつ唯一の解を含む、事前に決定されたコンパクト集合を特定する能力を見つけることは困難な場合があります。現実世界の応用において、領域が非常に大きい場合、これらの仮定はかなり制限的になり、非常に非現実的になる可能性があります。

さらなる展開

これらのアルゴリズムについては、収束条件、収束速度、多変量およびその他の一般化、ステップサイズの適切な選択、考えられるノイズモデルなどに関する広範な理論的文献が蓄積されている。^{[21] [22]これらの手法は}制御理論 にも応用されており、最適化または零点を求める未知の関数が時間とともに変化する可能性がある。この場合、ステップサイズは零に収束するのではなく、関数を追跡するように選択する必要がある。^{[21] 、第2版、第3章} ${\displaystyle a_{n}}$

C.ヨハン・マスレリエスとR.ダグラス・マーティンは、確率的近似をロバスト 推定に適用した最初の人物であった。^[23]

確率近似アルゴリズム（ロビンズ・モンローアルゴリズムやキーファー・ウォルフォウィッツアルゴリズムを含む）を解析するための主なツールは、1956年に発表されたアリエ・ドヴォレツキーの定理である^。[24]

参照

• 確率的勾配降下法
• 確率的分散減少

参考文献

1. Toulis, Panos; Airoldi, Edoardo (2015). 「確率的近似に基づくスケーラブルな推定戦略：従来の結果と新たな知見」. Statistics and Computing . 25 (4): 781– 795. doi :10.1007/s11222-015-9560-y. PMC  4484776. PMID  26139959 .
2. Le Ny, Jerome. 「確率的近似アルゴリズム入門」(PDF) .モントリオール工科大学. 教育ノート. 2016年11月16日閲覧。
3. Robbins, H. ; Monro, S. (1951). 「確率的近似法」.数理統計年報. 22 (3): 400. doi : 10.1214/aoms/1177729586 .
4. Blum, Julius R. (1954-06-01). 「確率1で収束する近似法」.数理統計年報. 25 (2): 382– 386. doi : 10.1214/aoms/1177728794 . ISSN  0003-4851.
5. Sacks, J. (1958). 「確率的近似法の漸近分布」.数理統計年報. 29 (2): 373– 405. doi : 10.1214/aoms/1177706619 . JSTOR  2237335.
6. Nemirovski, A. ; Juditsky, A. ; Lan, G. ; Shapiro, A. (2009). 「確率計画法へのロバストな確率近似アプローチ」SIAM Journal on Optimization . 19 (4): 1574. doi :10.1137/070704277.
7. 最適化における問題の複雑さと手法の効率性、A. NemirovskiとD. Yudin、 Wiley-Intersci. Ser. Discrete Math 15 John Wiley New York (1983) 。
8. 確率的探索と最適化入門：推定、シミュレーション、制御、JC Spall、John Wiley Hoboken、NJ、（2003）。
9. Chung, KL (1954-09-01). 「確率的近似法について」.数理統計年報. 25 (3): 463– 483. doi : 10.1214/aoms/1177728716 . ISSN  0003-4851.
10. ファビアン、ヴァーツラフ (1968年8月1日). 「確率近似における漸近的正規性について」.数理統計年報. 39 (4): 1327– 1332. doi : 10.1214/aoms/1177698258 . ISSN  0003-4851.
11. Lai, TL; Robbins, Herbert (1979-11-01). 「適応型設計と確率的近似」. The Annals of Statistics . 7 (6): 1196– 1221. doi : 10.1214/aos/1176344840 . ISSN  0090-5364.
12. ライ、ツェ・リョン;ハーバート・ロビンス（1981-09-01）。 「確率的近似スキームにおける傾き推定の一貫性と漸近効率」。Zeitschrift für Wahrscheinlichkeitstheorie および Verwandte Gebiete。56 (3): 329–360。土井: 10.1007/BF00536178。ISSN  0044-3719。S2CID  122109044。
13. Polyak, BT (1991). 「新しい確率的近似型手順（ロシア語）」.オートメーションとリモートコントロール. 7 (7).
14. Ruppert, David (1988). 緩やかに収束するロビンス・モンロー過程からの効率的な推定量 (技術レポート 781). コーネル大学オペレーションズ・リサーチ・インダストリアル・エンジニアリング学部.
15. Polyak, BT; Juditsky, AB (1992). 「平均化による確率的近似の加速」SIAM Journal on Control and Optimization . 30 (4): 838. doi :10.1137/0330046.
16. 凸凹関数の鞍点を近似するための最急降下法のCezari収束について、A. NemirovskiとD. Yudin、「 Dokl. Akad. Nauk SSR 2939」（1978年（ロシア語））、Soviet Math. Dokl. 19（1978年（英語））。
17. Kushner, Harold; George Yin, G. (2003-07-17). 確率的近似と再帰アルゴリズム | Harold Kushner | Springer. www.springer.com. ISBN 9780387008943. 2016年5月16日閲覧。
18. Bouleau, N. ; Lepingle, D. (1994). 確率過程の数値解析法. ニューヨーク: John Wiley. ISBN 9780471546412。
19. Kiefer, J.; Wolfowitz, J. (1952). 「回帰関数の最大値の確率的推定」.数理統計年報. 23 (3): 462. doi : 10.1214/aoms/1177729392 .
20. Spall, JC (2000). 「同時摂動法による適応確率近似」. IEEE Transactions on Automatic Control . 45 (10): 1839– 1853. doi :10.1109/TAC.2000.880982.
21. Kushner, HJ ; Yin, GG (1997).確率的近似アルゴリズムとその応用. doi :10.1007/978-1-4899-2696-8. ISBN 978-1-4899-2698-2。
22. 確率的近似と再帰的推定、ミハイル・ボリソビッチ・ネヴェルソンとラファイル・ザルマノビッチ・ハスミンスキー、イスラエル科学翻訳プログラムとB.シルバーによる翻訳、プロビデンス、ロードアイランド州：アメリカ数学会、1973年、1976年。ISBN 0-8218-1597-0。
23. Martin, R.; Masreliez, C. (1975). 「確率的近似によるロバスト推定」. IEEE Transactions on Information Theory . 21 (3): 263. doi :10.1109/TIT.1975.1055386.
24. Dvoretzky, Aryeh (1956). 「確率近似について」. Neyman, Jerzy (編). Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, 1954–1955, vol. I . University of California Press. pp.  39– 55. MR  0084911.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Stochastic_approximation&oldid=1320073982"