論文の概要: 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$の値を選択する)。

関連論文リスト

• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation [22.51165277694864]
  本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。 LSAは$d$次元線形系の近似解を計算するために用いられる。 次数 $(p α t_operatornamemix)1/2d1/p$ を LSA の最終反復モーメントの$p$-番目のモーメントに設定する。
  論文  参考訳（メタデータ） (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)
• Asymptotic Convergence Rate and Statistical Inference for Stochastic Sequential Quadratic Programming [59.36379287247961]
  制約付き非線形最適化問題を解くために、逐次2次アルゴリズム(StoSQP)を適用する。 分布関数の収束度を定量的に測定するために、$(x_t, lambda_t)$に対してベリー・エスキーを確立する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• 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)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Retrospective Approximation for Smooth Stochastic Optimization [1.0323063834827415]
  我々は,普遍近似問題サイズパラダイムとしてふりかえり近似(ra)を提案する。 線形探索準探索によるRAの性能について,不条件最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
  論文  参考訳（メタデータ） (2021-03-07T16:29:36Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。