論文の概要: Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation
- arxiv url: http://arxiv.org/abs/2112.12770v1
- Date: Thu, 23 Dec 2021 18:47:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2021-12-24 14:54:44.121616
- Title: Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation
- Title（参考訳）: マルコフ線形確率近似の最適およびインスタンス依存保証
- Authors: Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright, Peter L. Bartlett
- Abstract要約: 標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
- 参考スコア（独自算出の注目度）: 77.84027086542827
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic approximation procedures for approximately solving a
$d$-dimensional linear fixed point equation based on observing a trajectory of
length $n$ from an ergodic Markov chain. We first exhibit a non-asymptotic
bound of the order $t_{\mathrm{mix}} \tfrac{d}{n}$ on the squared error of the
last iterate of a standard scheme, where $t_{\mathrm{mix}}$ is a mixing time.
We then prove a non-asymptotic instance-dependent bound on a suitably averaged
sequence of iterates, with a leading term that matches the local asymptotic
minimax limit, including sharp dependence on the parameters $(d,
t_{\mathrm{mix}})$ in the higher order terms. We complement these upper bounds
with a non-asymptotic minimax lower bound that establishes the
instance-optimality of the averaged SA estimator. We derive corollaries of
these results for policy evaluation with Markov noise -- covering the
TD($\lambda$) family of algorithms for all $\lambda \in [0, 1)$ -- and linear
autoregressive models. Our instance-dependent characterizations open the door
to the design of fine-grained model selection procedures for hyperparameter
tuning (e.g., choosing the value of $\lambda$ when running the TD($\lambda$)
algorithm).
- Abstract（参考訳）: 本研究では,エルゴードマルコフ連鎖から長さn$の軌跡を観測し,d$次元線形不動点方程式を近似する確率近似法について検討する。
最初に、標準スキームの最後の反復の2乗誤差に基づいて、順序 $t_{\mathrm{mix}} \tfrac{d}{n}$の非漸近境界を示し、ここで$t_{\mathrm{mix}}$ は混合時間である。
次に、適切な平均化されたイテレート列上の非漸近的インスタンス依存境界を証明し、高次項において$(d, t_{\mathrm{mix}})$のパラメータに対する鋭い依存を含む局所漸近的ミニマックス極限に一致する先行項を持つ。
これらの上界を非漸近ミニマックス下界で補い、平均化されたSA推定器のインスタンス最適性を確立する。
マルコフノイズを用いた政策評価のためのこれらの結果は、すべての$\lambda \in [0, 1)$に対するTD($\lambda$)アルゴリズムファミリーと線形自己回帰モデルをカバーする。
インスタンス依存のキャラクタリゼーションは、ハイパーパラメータチューニングのためのきめ細かいモデル選択手順の設計への扉を開く(例えば、td($\lambda$)アルゴリズムを実行するときに$\lambda$の値を選択する)。
関連論文リスト
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。
我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation [22.51165277694864]
本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
論文 参考訳（メタデータ） (2022-07-10T14:36:04Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。