論文の概要: 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$の値を選択する)。
関連論文リスト
- 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) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - 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 Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。