論文の概要: The ODE Method for Asymptotic Statistics in Stochastic Approximation and
Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2110.14427v3
- Date: Sun, 18 Jun 2023 18:11:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-22 06:36:26.676688
- Title: The ODE Method for Asymptotic Statistics in Stochastic Approximation and
Reinforcement Learning
- Title(参考訳): 確率近似と強化学習における漸近統計量のODE法
- Authors: Vivek Borkar, Shuhang Chen, Adithya Devraj, Ioannis Kontoyiannis and
Sean Meyn
- Abstract要約: この論文は、$d$-dimensional approximation recursion, $$theta_n+1=theta_n + alpha_n + 1 f(theta_n, Phi_n+1) $$ in ここで$Phi$は、一般的な状態空間上の幾何学的にエルゴード的なマルコフ連鎖である。
- 参考スコア(独自算出の注目度): 6.92974337901767
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The paper concerns the $d$-dimensional stochastic approximation recursion, $$
\theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \Phi_{n+1}) $$ in which
$\Phi$ is a geometrically ergodic Markov chain on a general state space
$\textsf{X}$ with stationary distribution $\pi$, and
$f:\Re^d\times\textsf{X}\to\Re^d$.
The main results are established under a version of the Donsker-Varadhan
Lyapunov drift condition known as (DV3), and a stability condition for the mean
flow with vector field $\bar{f}(\theta)=\textsf{E}[f(\theta,\Phi)]$, with
$\Phi\sim\pi$.
(i) $\{ \theta_n\}$ is convergent a.s. and in $L_4$ to the unique root
$\theta^*$ of $\bar{f}(\theta)$.
(ii) A functional CLT is established, as well as the usual one-dimensional
CLT for the normalized error.
(iii) The CLT holds for the normalized version, $z_n{=:} \sqrt{n}
(\theta^{\text{PR}}_n -\theta^*)$, of the averaged parameters,
$\theta^{\text{PR}}_n {=:} n^{-1} \sum_{k=1}^n\theta_k$, subject to standard
assumptions on the step-size. Moreover, the normalized covariance converges, $$
\lim_{n \to \infty} n \textsf{E} [ {\widetilde{\theta}}^{\text{ PR}}_n
({\widetilde{\theta}}^{\text{ PR}}_n)^T ] = \Sigma_\theta^*,\;\;\;\textit{with
$\widetilde{\theta}^{\text{ PR}}_n = \theta^{\text{ PR}}_n -\theta^*$,}
$$ where $\Sigma_\theta^*$ is the minimal covariance of Polyak and Ruppert.
(iv) An example is given where $f$ and $\bar{f}$ are linear in $\theta$, and
the Markov chain $\Phi$ is geometrically ergodic but does not satisfy (DV3).
While the algorithm is convergent, the second moment is unbounded: $ \textsf{E}
[ \| \theta_n \|^2 ] \to \infty$ as $n\to\infty$.
- Abstract(参考訳): 論文は、$d$-dimensional stochastic approximation recursion、$$$ \theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \phi_{n+1}) $$、$\phi$は一般状態空間上の幾何学的エルゴードマルコフ連鎖である$\textsf{x}$、定常分布$\pi$、$f:\re^d\times\textsf{x}\to\re^d$である。
主な結果はDonsker-Varadhan Lyapunov ドリフト条件 (DV3) とベクトル場 $\bar{f}(\theta)=\textsf{E}[f(\theta,\Phi)]$, with $\Phi\sim\pi$ による平均流の安定性条件の下にある。
(i)$\{ \theta_n\}$ は収束 a.s. であり、$L_4$ は一意根 $\theta^*$ of $\bar{f}(\theta)$ に収束する。
(ii)正規化誤差に対する通常の1次元CLTと同様に関数型CLTが確立される。
(iii) CLT は正規化バージョン $z_n{=:} \sqrt{n} (\theta^{\text{PR}}_n -\theta^*)$, 平均化パラメータ $\theta^{\text{PR}}_n {=:} n^{-1} \sum_{k=1}^n\theta_k$ を、ステップサイズに関する標準的な仮定に従って保持する。
さらに、正規化された共分散は、$$ \lim_{n \to \infty} n \textsf{E} [ {\widetilde{\theta}}^{\text{ PR}}_n ({\widetilde{\theta}}^{\text{ PR}}_n)^T ] = \Sigma_\theta^*,\;\;\;\;\textit{with $\widetilde{\theta}^{\text{ PR}}_n = \theta^{\text{ PR}}_n -\theta^*$,} $$$$\Sigma_\theta^*$はポリアクとルパートの最小共分散である。
(iv) 例えば、$f$ と $\bar{f}$ が $\theta$ において線型であり、マルコフ連鎖 $\Phi$ は幾何学的にエルゴード的であるが満足しない(DV3)。
アルゴリズムは収束するが、第二モーメントは非有界である: $ \textsf{E} [ \| \theta_n \|^2 ] \to \infty$ as $n\to\infty$。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳(メタデータ) (2024-02-01T07:21:32Z) - Convergence Rates for Stochastic Approximation: Biased Noise with
Unbounded Variance, and Applications [2.3134637611088653]
1951年にRobinsとMonroによって導入された近似アルゴリズムは $mathbff(boldsymboltheta) = mathbf0 という形の方程式を解く標準的な方法である。
本稿では,SA理論を拡張し,非ゼロ条件平均および/または条件分散の誤差を包含する。
さらに、収束率の推定を導出し、最適ステップサイズを計算して収束率を最大化する。
論文 参考訳(メタデータ) (2023-12-05T15:22:39Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳(メタデータ) (2023-05-10T01:12:11Z) - High-dimensional Location Estimation via Norm Concentration for Subgamma
Vectors [15.802475232604667]
位置推定では、既知の分布から$n$のサンプルが与えられます。
漸近的に、最大推定は誤差$mathcal N(0, frac1nmathcal I)$のクラム・ラオ境界を達成する。
我々は、Emphsmoothed estimator を用いて、$mathcal I_r$, the Fisher information of the $r$-smoothed の有限$n$の誤差を束縛する理論を構築した。
論文 参考訳(メタデータ) (2023-02-05T22:17:04Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21:43Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳(メタデータ) (2020-11-24T22:39:21Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳(メタデータ) (2020-09-30T04:44:45Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳(メタデータ) (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。