論文の概要: The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize

• arxiv url: http://arxiv.org/abs/2405.16732v1
• Date: Mon, 27 May 2024 00:23:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-28 19:35:41.695072
• Title: The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize
• Title（参考訳）: 確率近似におけるメモリと非線形性の連成と定数ステップサイズ
• Authors: Dongyan Huo, Yixuan Zhang, Yudong Chen, Qiaomin Xie,
• Abstract要約: 本稿では,データのマルコフ的依存性と非線形更新規則の同時性について考察する。 我々は,SA 反復 $theta_k$ と Markovian データ $x_k$ の相関関係を詳細に解析する。 我々は、$mathbbE[theta_infty]-thetaast=alpha(b_textm+b_textn+b_textc)+で与えられるSA繰り返しの偏りを正確に評価する。
• 参考スコア（独自算出の注目度）: 22.917692982875025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we investigate stochastic approximation (SA) with Markovian data and nonlinear updates under constant stepsize $\alpha>0$. Existing work has primarily focused on either i.i.d. data or linear update rules. We take a new perspective and carefully examine the simultaneous presence of Markovian dependency of data and nonlinear update rules, delineating how the interplay between these two structures leads to complications that are not captured by prior techniques. By leveraging the smoothness and recurrence properties of the SA updates, we develop a fine-grained analysis of the correlation between the SA iterates $\theta_k$ and Markovian data $x_k$. This enables us to overcome the obstacles in existing analysis and establish for the first time the weak convergence of the joint process $(x_k, \theta_k)_{k\geq0}$. Furthermore, we present a precise characterization of the asymptotic bias of the SA iterates, given by $\mathbb{E}[\theta_\infty]-\theta^\ast=\alpha(b_\text{m}+b_\text{n}+b_\text{c})+O(\alpha^{3/2})$. Here, $b_\text{m}$ is associated with the Markovian noise, $b_\text{n}$ is tied to the nonlinearity, and notably, $b_\text{c}$ represents a multiplicative interaction between the Markovian noise and nonlinearity, which is absent in previous works. As a by-product of our analysis, we derive finite-time bounds on higher moment $\mathbb{E}[\|\theta_k-\theta^\ast\|^{2p}]$ and present non-asymptotic geometric convergence rates for the iterates, along with a Central Limit Theorem.
• Abstract（参考訳）: 本研究では,マルコフデータを用いた確率近似 (SA) と非線形更新を定常ステップサイズ$\alpha>0$で検討する。 既存の作業は主に、i.d.データまたはリニア更新ルールに重点を置いている。 我々は新しい視点を採り、マルコフ的データ依存と非線形更新規則の同時存在を慎重に検討し、これらの2つの構造間の相互作用が、従来の手法では捉えられていない複雑さにどのように結びつくかを説明する。 SA更新の滑らかさと繰り返し特性を活用することにより、SA更新の相関関係を詳細に解析し、$\theta_k$ と Markovian のデータ $x_k$ を反復する。 これにより、既存の解析における障害を克服し、結合プロセス $(x_k, \theta_k)_{k\geq0}$ の弱収束を初めて確立することができる。 さらに、 SA 反復の漸近バイアスを正確に評価し、$\mathbb{E}[\theta_\infty]-\theta^\ast=\alpha(b_\text{m}+b_\text{n}+b_\text{c})+O(\alpha^{3/2})$ で与えられる。 ここで、$b_\text{m}$はマルコフノイズに関連付けられ、$b_\text{n}$は非線形性に結びついており、特に$b_\text{c}$はマルコフノイズと非線型性の間の乗法的相互作用を表しており、これは以前の研究では欠落している。 解析の副産物として、高次モーメント $\mathbb{E}[\|\theta_k-\theta^\ast\|^{2p}] と現在のイテレートに対する非漸近的幾何収束率と中央極限定理を導出する。

関連論文リスト

• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 切断のみを考慮し、有界な$p$-thモーメントでノイズを必要とする最先端技術と比較して、幅広い非線形性の保証を提供する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way [12.331596909999764]
  マルコフ過程のレンズを通した等質化スキームについて検討する。 我々は、定段化によって導入された分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。
  論文  参考訳（メタデータ） (2024-10-16T21:49:27Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• 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)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise [28.891930079358954]
  線形2時間スケールSAスキームに対して有限時間解析を行う。 我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。 一致した下界を持つ予測誤差の拡張を示す。
  論文  参考訳（メタデータ） (2020-02-04T13:03:17Z)

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

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