論文の概要: Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way

• arxiv url: http://arxiv.org/abs/2410.13067v1
• Date: Wed, 16 Oct 2024 21:49:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:17:56.393924
• Title: Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way
• Title（参考訳）: 2時間線形確率近似:定数ステップサイズは長い道のりを進む
• Authors: Jeongyeol Kwon, Luke Dotson, Yudong Chen, Qiaomin Xie,
• Abstract要約: マルコフ過程のレンズを通した等質化スキームについて検討する。 我々は、定段化によって導入された分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。
• 参考スコア（独自算出の注目度）: 12.331596909999764
• License:
• Abstract: Previous studies on two-timescale stochastic approximation (SA) mainly focused on bounding mean-squared errors under diminishing stepsize schemes. In this work, we investigate {\it constant} stpesize schemes through the lens of Markov processes, proving that the iterates of both timescales converge to a unique joint stationary distribution in Wasserstein metric. We derive explicit geometric and non-asymptotic convergence rates, as well as the variance and bias introduced by constant stepsizes in the presence of Markovian noise. Specifically, with two constant stepsizes $\alpha < \beta$, we show that the biases scale linearly with both stepsizes as $\Theta(\alpha)+\Theta(\beta)$ up to higher-order terms, while the variance of the slower iterate (resp., faster iterate) scales only with its own stepsize as $O(\alpha)$ (resp., $O(\beta)$). Unlike previous work, our results require no additional assumptions such as $\beta^2 \ll \alpha$ nor extra dependence on dimensions. These fine-grained characterizations allow tail-averaging and extrapolation techniques to reduce variance and bias, improving mean-squared error bound to $O(\beta^4 + \frac{1}{t})$ for both iterates.
• Abstract（参考訳）: 2時間確率近似(SA)の従来の研究は、主に段差の減少による平均二乗誤差の有界化に焦点をあてていた。 本研究では、マルコフ過程のレンズによるスキームの安定化について検討し、両方の時間スケールの反復がワッサーシュタイン計量の特異な共同定常分布に収束することを証明した。 我々は、マルコフノイズの存在下での定段化によって生じる分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。 具体的には、2つの定数ステップサイズ $\alpha < \beta$ で、両方のステップサイズを $\Theta(\alpha)+\Theta(\beta)$ として線形にスケールする一方、遅いイテレート(resp., faster iterate)スケールの分散は $O(\alpha)$ (resp.) という独自のステップサイズでのみスケールする。 は$O(\beta)$である。 以前の研究とは異なり、我々の結果は$\beta^2 \ll \alpha$ のような追加の仮定や次元への余分な依存を必要としない。 これらのきめ細かい特徴付けにより、ばらつきとバイアスを低減し、平均二乗誤差を両方の繰り返しに対して$O(\beta^4 + \frac{1}{t})$に制限する。

関連論文リスト

• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。 得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。 我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
  論文  参考訳（メタデータ） (2024-10-07T15:02:48Z)
• Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes [9.689344942945652]
  定常的なステップサイズとマルコフデータを持つ線形近似(LSA)を考える。 この極限のバイアスベクトルは、ステップサイズに関して無限級数展開を持つことを示す。 リチャードソン・ロームバーグ外挿法と$mge 2$ stepsizes を用いてバイアスを低減できることが示される。
  論文  参考訳（メタデータ） (2022-10-03T14:11:03Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• 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)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
  一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。 SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
  論文  参考訳（メタデータ） (2020-06-14T11:12:05Z)
• 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)
• 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)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise [28.891930079358954]
  線形2時間スケールSAスキームに対して有限時間解析を行う。 我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。 一致した下界を持つ予測誤差の拡張を示す。
  論文  参考訳（メタデータ） (2020-02-04T13:03:17Z)

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

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