確率近似

確率近似法は、根を求める問題や最適化問題に一般的に用いられる反復法の一種です。確率近似法の再帰的な更新規則は、収集したデータがノイズによって劣化している場合の線形システムの解法や、直接計算できずノイズのある観測値からしか推定できない関数の極値を近似するなど、様々な用途に利用できます。

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

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

この種のアルゴリズムの中で最も初期の、そして典型的な例は、それぞれ1951年と1952年に発表されたロビンス・モンローアルゴリズムとキーファー・ウォルフォウィッツアルゴリズムである。

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

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 )}$ アルゴリズムの構造は、次の形式の反復を生成することです。

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

ここ、 $a_{1},a_{2},\dots$ は正のステップサイズのシーケンスである。ロビンスとモンローは^{[ 3 ]}^定理2を証明した。 $\displaystyle \theta _{n}}$ 収束する $\displaystyle L^{2}}$ （したがって確率的にも） $\displaystyle \theta ^{*}}$ そして、Blum ^{[ 4 ]}は後に、以下の条件が満たされれば、収束は実際に確率 1 で起こることを証明した。

${\textstyle N(\theta )}$ 一様に有界であり、
${\textstyle M(\theta )}$ 減少しない、
${\textstyle M'(\theta ^{*})}$ 存在し、肯定的であり、
シーケンス ${\textstyle a_{n}}$ 以下の要件を満たします。

$\displaystyle \qquad \sum _{n=0}^{\infty }a_{n}=\infty \quad {\mbox{ および }}\quad \sum _{n=0}^{\infty }a_{n}^{2}<\infty \quad }$ これらの条件を満たす特定の手順は、ロビンス＝モンローによって提案されたもので、次の形式をとる。 ${\textstyle a_{n}=a/n}$ 、のために ${\textstyle a>0}$ .その他のシリーズ、例えば $a_{n}={\frac {1}{n\ln n}},{\frac {1}{n\ln n\ln \ln n}},\dots$ 可能ですが、ノイズを平均化するために ${\textstyle N(\theta )}$ 上記の条件を満たさなければなりません。

例

平均値を推定する問題について考えてみましょう $\displaystyle \theta ^{*}}$ 独立したサンプルのストリームから得られる確率分布 $X_{1},X_{2},\dots$ 。

させて $N(\theta ):=\theta -X$ すると、唯一の解決策は ${\textstyle \operatorname {E} [N(\theta )]=0}$ 望ましい平均値 $\displaystyle \theta ^{*}}$ RMアルゴリズムは私たちに $\theta _{n+1}=\theta _{n}-a_{n}(\theta _{n}-X_{n})$ これは損失関数を用いた確率的勾配降下法に相当する。 $L(\theta )={\frac {1}{2}}\|X-\theta \|^{2}$ これは加重平均にも相当します。 $\theta _{n+1}=(1-a_{n})\theta _{n}+a_{n}X_{n}$ 一般的に、何らかの関数が存在する場合 $L$ そのため $\nabla L(\theta )=N(\theta )-\alpha$ すると、ロビンス・モンローアルゴリズムは損失関数付き確率的勾配降下法と等価になる。 $L(\theta )$ しかし、RMアルゴリズムは $L$ 収束するために存在する。

複雑性の結果

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

その後の展開とポリャク・ルパート平均化

Robbins–Monroアルゴリズムは理論的には達成可能であるが、 ${\textstyle O(1/n)}$ 2回連続微分可能性と強凸性の仮定の下では、実装時にかなり悪いパフォーマンスを示す可能性があります。これは主に、アルゴリズムがステップサイズシーケンスの選択に非常に敏感であり、漸近的に最適とされるステップサイズポリシーが最初はかなり有害になる可能性があるという事実によるものです。^{[ 6 ]}^{[ 8 ]}

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

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

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

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

$\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$ 反復平均を $\Theta _{n}={\frac {a_{n}}{t}}\sum _{i=n}^{n+t/a_{n}-1}\theta _{i}$ そして関連する正規化誤差は ${\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 )}$ 静的解は $dU=AU\,dt+\Sigma ^{1/2}\,dw$ どこ ${\textstyle w(\cdot )}$ これは標準的なウィーナー法です。

満足し、定義する ${\textstyle {\bar {V}}=(A^{-1})'\Sigma (A')^{-1}}$ .次に、それぞれについて ${\textstyle t}$ 、

${\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}\}}$ 前者の時間スケールの方が速い。

確率的最適化への応用

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

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

ここ $H(\theta ,X)$ は不偏推定量である $\nabla g(\theta )$ 。もし $X$ に依存する $\theta$ 一般的に、ランダムな結果を生成する自然な方法は存在しない。 $H(\theta ,X)$ これは勾配の不偏推定量である。IPA法または尤度比法が適用可能な特殊なケースでは、不偏勾配推定量を得ることができる。 $H(\theta ,X)$ 。もし $X$ は、独立して生成される何らかの「根本的な」根底にあるランダムプロセスと見なされる。 $\theta$ また、微分積分交換演算に関するいくつかの正則化条件の下で、 $\operatorname {E} {\Big [}{\frac {\partial }{\partial \theta }}Q(\theta ,X){\Big ]}=\nabla g(\theta )$ 、それから $H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)$ は基本的な勾配不偏推定値を与えます。ただし、一部のアプリケーションでは、有限差分法を使用する必要があります。 $H(\theta ,X)$ 条件付き期待値は $\nabla g(\theta )$ しかし、完全に同じというわけではない。

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

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

アルゴリズムの収束

以下の結果は、 $\theta _{n}$ アルゴリズムが収束するためには：^{[ 18 ]}

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

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

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

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

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

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

それから $\theta _{n}$ 収束して $\theta ^{*}$ ほぼ間違いなく。

これらの条件について、直感的に説明してみましょう。 $H(\theta _{n},X_{n+1})$ は一様有界確率変数です。C2) が満たされない場合、つまり $\sum _{n=0}^{\infty }\varepsilon _{n}<\infty$ 、それから $\theta _{n}-\theta _{0}=-\sum _{i=0}^{n-1}\varepsilon _{i}H(\theta _{i},X_{i+1})$ は有界数列なので、反復は収束しない。 $\theta ^{*}$ 最初の推測が $\theta _{0}$ 遠すぎる $\theta ^{*}$ C3)については、 $\theta _{n}$ 収束して $\theta ^{*}$ それから

$\theta _{n+1}-\theta _{n}=-\varepsilon _{n}H(\theta _{n},X_{n+1})\rightarrow 0,{\text{ as }}n\rightarrow \infty .$ だから私たちは $\varepsilon _{n}\downarrow 0$ ，そして条件C3)がそれを保証します。自然な選択肢は $\varepsilon _{n}=1/n$ . 条件 C5) は、形状に関するかなり厳しい条件です。 $g(\theta )$ ;これはアルゴリズムの探索方向を示します。

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

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

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

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

させて $M(x)$ 点において最大値を持つ関数とする $\theta$ と想定されるのは $M(x)$ 不明であるが、いくつかの観察結果から $N(x)$ 、どこ $\operatorname {E} [N(x)]=M(x)$ いつでも作成できます $x$ アルゴリズムの構造は勾配法に似ており、反復は次のように生成されます。

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

どこ $N(x_{n}+c_{n})$ そして $N(x_{n}-c_{n})$ は独立している。各ステップで、 $M(x)$ は中心差分法に似た近似で、 $h=2c_{n}$ なので、シーケンスは $\{c_{n}\}$ は勾配近似に使用される有限差分幅のシーケンスを指定する一方、シーケンスは $\{a_{n}\}$ その方向に沿って取られる一連の正のステップサイズを指定します。

キーファーとウォルフォウィッツは、もし $M(x)$ ある一定の規則性条件を満たし、 $x_{n}$ 収束する $\theta$ 確率的に $n\to \infty$ そして後にブルム^{[ 4 ]}は1954年に $x_{n}$ 収束して $\theta$ ほぼ確実に、ただし以下の条件を満たす場合：

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

キーファーとウォルフォウィッツが推奨する適切なシーケンスの選択は次のとおりである。 $a_{n}=1/n$ そして $c_{n}=n^{-1/3}$ 。

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

キーファー・ウォルフォウィッツのアルゴリズムでは、各勾配計算に対して、少なくとも $d+1$ $d+1$ アルゴリズムの各反復ごとに異なるパラメータ値をシミュレートする必要がある。 $d$ $d$ は探索空間の次元です。これは、 $d$ $d$ が大きい場合、キーファー・ウォルフォウィッツアルゴリズムは反復ごとに相当な計算量を必要とし、収束が遅くなる。
1. この問題を解決するために、Spallは勾配を推定するために同時摂動を用いる方法を提案した。この方法では、次元に関係なく、反復ごとに2回のシミュレーションしか必要としない。 $d$ [ ²⁰^]
収束に必要な条件において、強い凸性（または凹性）を満たし、かつ唯一の解を含む、あらかじめ定められたコンパクトな集合を指定することは困難な場合がある。現実世界の応用においては、領域が非常に大きい場合、これらの仮定はかなり制約が厳しく、非現実的になりかねない。

さらなる展開

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

C. ヨハン・マスレリエとR. ダグラス・マーティンは、ロバスト推定に確率近似を初めて適用した。^{[ 23 ]}

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

参考文献

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

[:1-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日取得。

[rm-3] 1 2 Robbins, H. ; Monro, S. (1951). "確率近似法" . The Annals of Mathematical Statistics . 22 (3): 400. doi : 10.1214/aoms/1177729586 .

[:0-4] 1 2 Blum, Julius R. (1954-06-01). "確率1で収束する近似法" . The Annals of Mathematical Statistics . 25 (2): 382– 386. doi : 10.1214/aoms/1177728794 . ISSN 0003-4851 .

[jsacks-5] Sacks, J. (1958). "確率近似手順の漸近分布" . The Annals of Mathematical Statistics . 29 (2): 373– 405. doi : 10.1214/aoms/1177706619 . JSTOR 2237335 .

[NJLS-6] 1 2 Nemirovski, A. ; Juditsky, A.; Lan, G.; Shapiro, A. (2009). "Robust Stochastic Approximation Approach to Stochastic Programming". SIAM Journal on Optimization . 19 (4): 1574. doi : 10.1137/070704277 .

[NYcomp-7] 最適化における問題の複雑性と方法の効率性、A. Nemirovski および D. Yudin、 Wiley -Intersci. Ser. Discrete Math 15 John Wiley New York (1983) 。

[jcsbook-8] 1 2確率的探索と最適化入門：推定、シミュレーション、制御、JC Spall、 John Wiley Hoboken、NJ、（2003）。

[9] Chung, KL (1954-09-01). "確率近似法について" . The Annals of Mathematical Statistics . 25 (3): 463– 483. doi : 10.1214/aoms/1177728716 . ISSN 0003-4851 .

[10] Fabian, Vaclav (1968-08-01). "確率近似における漸近正規性について" . The Annals of Mathematical Statistics . 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] ポリャク、BT (1991) 「新しい確率近似型手順。（ロシア語）」オートメーションとリモートコントロール7 （ 7）。

[14] Ruppert, David (1988).ゆっくりと収束するロビンス・モンロー過程からの効率的な推定値(技術報告書 781). コーネル大学オペレーションズ・リサーチ・産業工学部。

[pj-15] 1 2 Polyak, BT; Juditsky, AB (1992). "平均化による確率近似の加速". SIAM Journal on Control and Optimization . 30 (4): 838. doi : 10.1137/0330046 .

[NY-16] 凸凹関数の鞍点近似のための最急降下法のチェザリの収束について、A. ネミロフスキー、D. ユーディン、 Dokl. Akad. Nauk SSR 2939、（1978年（ロシア語））、Soviet Math. Dokl. 19（1978年（英語））。

[17] クシュナー、ハロルド、ジョージ・イン、G. (2003年7月17日)。確率近似と再帰アルゴリズムと | ハロルド・クシュナー | Springer。www.springer.com。ISBN 97803870089432016年5月16日に取得。

[18] Bouleau, N. ; Lepingle, D. (1994). Numerical Methods for stochastic Processes . New York: John Wiley. ISBN 9780471546412。

[KW-19] Kiefer, J.; Wolfowitz, J. (1952). "回帰関数の最大値の確率的推定" . The Annals of Mathematical Statistics . 23 (3): 462. doi : 10.1214/aoms/1177729392 .

[Jsp-20] Spall, JC (2000). "同時摂動法による適応型確率近似". IEEE Transactions on Automatic Control . 45 (10): 1839–1853 . doi : 10.1109/TAC.2000.880982 .

[kushneryin-21] 1 2 Kushner, HJ ; Yin, GG (1997). Stochastic Approximation Algorithms and Applications . 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] ドヴォレツキー、アリエ( 1956)。「確率近似について」。ネイマン、イェジー(編) 『第 3 回バークレー数学統計学および確率シンポジウム議事録、1954–1955 年、第 I 巻』。カリフォルニア大学出版局。pp. 39–55。MR 0084911。

[ 2 ]

[ 3 ]

5

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

20

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]