論文の概要: On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration

• arxiv url: http://arxiv.org/abs/2004.04719v1
• Date: Thu, 9 Apr 2020 17:54:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-15 02:45:46.486714
• Title: On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Title（参考訳）: 線形確率近似に就て : 微細なポリアークラッパートと非漸近濃度
• Authors: Wenlong Mou, Chris Junchi Li, Martin J. Wainwright, Peter L. Bartlett, Michael I. Jordan
• Abstract要約: The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
• 参考スコア（独自算出の注目度）: 115.1954841020189
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We undertake a precise study of the asymptotic and non-asymptotic properties of stochastic approximation procedures with Polyak-Ruppert averaging for solving a linear system $\bar{A} \theta = \bar{b}$. When the matrix $\bar{A}$ is Hurwitz, we prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity. The CLT characterizes the exact asymptotic covariance matrix, which is the sum of the classical Polyak-Ruppert covariance and a correction term that scales with the step size. Under assumptions on the tail of the noise distribution, we prove a non-asymptotic concentration inequality whose main term matches the covariance in CLT in any direction, up to universal constants. When the matrix $\bar{A}$ is not Hurwitz but only has non-negative real parts in its eigenvalues, we prove that the averaged LSA procedure actually achieves an $O(1/T)$ rate in mean-squared error. Our results provide a more refined understanding of linear stochastic approximation in both the asymptotic and non-asymptotic settings. We also show various applications of the main results, including the study of momentum-based stochastic gradient methods as well as temporal difference algorithms in reinforcement learning.
• Abstract（参考訳）: 我々は、線形系 $\bar{A} \theta = \bar{b}$ を解くために、Polyak-Ruppert平均化を用いた確率近似法の漸近的および非漸近的特性を正確に研究する。 行列 $\bar{A}$ が Hurwitz であるとき、固定されたステップサイズと無限大となる反復数を持つ平均化された反復に対する中心極限定理 (CLT) を証明する。 cltは、古典的なpolyak-ruppert共分散の和である厳密な漸近共分散行列と、ステップサイズでスケールする補正項を特徴付ける。 雑音分布の尾について仮定すると、主項が任意の方向におけるCLTの共分散に一致する非漸近濃度不等式を普遍定数まで証明する。 行列 $\bar{A}$ がHurwitz ではなく、その固有値に非負の実部分しか持たないとき、平均化 LSA の手順が平均二乗誤差で実際に$O(1/T)$レートを達成できることを証明する。 この結果は漸近的および非漸近的設定の両方において線形確率近似をよりよく理解する。 また,強化学習における時間差アルゴリズムと同様に,運動量に基づく確率的勾配法の研究を含む,主な結果の様々な応用を示す。

関連論文リスト

• Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent [14.19520637866741]
  我々は、勾配勾配のポリアック=ルパート平均的反復に対する中心極限定理において、非漸近収束率を確立する。 最適化問題に対する信頼度セットを構築するための乗算器ブートストラップの非漸近的妥当性を実証する。
  論文  参考訳（メタデータ） (2025-02-10T17:49:05Z)
• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。 得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。 我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
  論文  参考訳（メタデータ） (2024-10-07T15:02:48Z)
• Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients [0.8749675983608172]
  動力学的ランゲヴィンダイナミクスに基づく後進手段の非バイアス化手法を提案する。 提案した推定器は偏りがなく、有限分散となり、中心極限定理を満たす。 以上の結果から、大規模アプリケーションでは、非バイアスアルゴリズムは「ゴールドスタンダード」なハミルトニアン・モンテカルロよりも2～3桁効率が良いことが示された。
  論文  参考訳（メタデータ） (2023-11-08T21:19:52Z)
• Convergence and concentration properties of constant step-size SGD through Markov chains [0.0]
  定常段差勾配勾配(SGD)を用いた滑らかで強凸な目標の最適化について検討する。 緩やかに制御された分散を伴う不偏勾配推定に対して、反復は全変動距離の不変分布に収束することを示す。 全ての結果は無症状であり、その結果はいくつかのアプリケーションを通して議論されている。
  論文  参考訳（メタデータ） (2023-06-20T12:36:28Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization [4.932130498861987]
  一定段差がゼロとなる極限において, 適切にスケールされた定常分布の挙動について検討する。 極限スケールの定常分布は積分方程式の解であることを示す。
  論文  参考訳（メタデータ） (2021-11-11T17:39:50Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)

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

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