論文の概要: The Curse of Memory in Stochastic Approximation: Extended Version
- arxiv url: http://arxiv.org/abs/2309.02944v2
- Date: Sun, 17 Sep 2023 17:16:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-19 22:04:28.843783
- Title: The Curse of Memory in Stochastic Approximation: Extended Version
- Title（参考訳）: 確率近似における記憶の呪い:拡張版
- Authors: Caio Kalil Lauand and Sean Meyn
- Abstract要約: 適応制御の初期から、制御システムコミュニティ内で近似の理論と応用が成長してきた。
近年の結果, (十分小さい) ステップサイズ$alpha>0$のSAの顕著な性能が確認されている。
- 参考スコア（独自算出の注目度）: 1.534667887016089
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Theory and application of stochastic approximation (SA) has grown within the
control systems community since the earliest days of adaptive control. This
paper takes a new look at the topic, motivated by recent results establishing
remarkable performance of SA with (sufficiently small) constant step-size
$\alpha>0$. If averaging is implemented to obtain the final parameter estimate,
then the estimates are asymptotically unbiased with nearly optimal asymptotic
covariance. These results have been obtained for random linear SA recursions
with i.i.d. coefficients. This paper obtains very different conclusions in the
more common case of geometrically ergodic Markovian disturbance: (i) The
$\textit{target bias}$ is identified, even in the case of non-linear SA, and is
in general non-zero. The remaining results are established for linear SA
recursions: (ii) the bivariate parameter-disturbance process is geometrically
ergodic in a topological sense; (iii) the representation for bias has a simpler
form in this case, and cannot be expected to be zero if there is multiplicative
noise; (iv) the asymptotic covariance of the averaged parameters is within
$O(\alpha)$ of optimal. The error term is identified, and may be massive if
mean dynamics are not well conditioned. The theory is illustrated with
application to TD-learning.
- Abstract（参考訳）: 確率近似(英語版)(sa)の理論と応用は、適応制御の初期から制御系コミュニティの中で成長してきた。
本稿では,SAの顕著な性能を(十分小さい)定数ステップサイズ$\alpha>0$で証明した最近の結果から,この話題を新たに考察する。
平均化が最終的なパラメータ推定を得るために実施されると、その推定は漸近的にほぼ最適な漸近共分散でバイアスされない。
これらの結果は, ランダム線形SA再帰係数に対して得られた。
本稿では,幾何学的エルゴードマルコフの乱れのより一般的な場合において,非常に異なる結論を得る。
(i)$\textit{target bias}$は、非線形 SA の場合においても特定され、一般には 0 でない。
残りの結果は線形SA再帰のために確立される。
(ii)二変量パラメータ・ディストバンス過程は、トポロジカルな意味で幾何学的にエルゴード的である。
三) バイアスの表現は、この場合においてより単純な形式であり、乗法ノイズがあるときはゼロであるとは期待できない。
(iv)平均パラメータの漸近共分散は最適な$o(\alpha)$以内である。
誤差項は特定され、平均力学が十分に条件づけられていない場合、大きすぎる可能性がある。
この理論はtd-learningに応用されている。
関連論文リスト
- Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - Binary Classification of Gaussian Mixtures: Abundance of Support
Vectors, Benign Overfitting and Regularization [39.35822033674126]
生成ガウス混合モデルに基づく二項線形分類について検討する。
後者の分類誤差に関する新しい非漸近境界を導出する。
この結果は, 確率が一定である雑音モデルに拡張される。
論文 参考訳（メタデータ） (2020-11-18T07:59:55Z) - Convergence Analysis of Riemannian Stochastic Approximation Schemes [39.32179384256228]
本稿では,最適化問題に取り組むための相関近似 (SA) スキームのクラスを解析する。
得られた条件は, 従来よりかなり軽度であることを示す。
第3に、平均場関数を小さなバイアスにしか推定できない場合、および/または、サンプルが鎖から引き出される場合を考える。
論文 参考訳（メタデータ） (2020-05-27T11:24:58Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z) - On Low-rank Trace Regression under General Sampling Distribution [9.699586426043885]
クロスバリデード推定器は一般仮定でほぼ最適誤差境界を満たすことを示す。
また, クロスバリデーション推定器はパラメータ選択理論に着想を得た手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2019-04-18T02:56:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。