論文の概要: Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation
- arxiv url: http://arxiv.org/abs/2207.04475v2
- Date: Wed, 29 Mar 2023 11:11:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-30 19:02:08.548153
- Title: Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation
- Title（参考訳）: 線形確率近似によるポリak-ruppert平均イテレートの有限時間高確率境界
- Authors: Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov
- Abstract要約: 本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
- 参考スコア（独自算出の注目度）: 22.51165277694864
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper provides a finite-time analysis of linear stochastic approximation
(LSA) algorithms with fixed step size, a core method in statistics and machine
learning. LSA is used to compute approximate solutions of a $d$-dimensional
linear system $\bar{\mathbf{A}} \theta = \bar{\mathbf{b}}$ for which
$(\bar{\mathbf{A}}, \bar{\mathbf{b}})$ can only be estimated by
(asymptotically) unbiased observations
$\{(\mathbf{A}(Z_n),\mathbf{b}(Z_n))\}_{n \in \mathbb{N}}$. We consider here
the case where $\{Z_n\}_{n \in \mathbb{N}}$ is an i.i.d. sequence or a
uniformly geometrically ergodic Markov chain. We derive $p$-th moment and
high-probability deviation bounds for the iterates defined by LSA and its
Polyak-Ruppert-averaged version. Our finite-time instance-dependent bounds for
the averaged LSA iterates are sharp in the sense that the leading term we
obtain coincides with the local asymptotic minimax limit. Moreover, the
remainder terms of our bounds admit a tight dependence on the mixing time
$t_{\operatorname{mix}}$ of the underlying chain and the norm of the noise
variables. We emphasize that our result requires the SA step size to scale only
with logarithm of the problem dimension $d$.
- Abstract（参考訳）: 本稿では, 線形確率近似(LSA)アルゴリズムの有限時間解析, 統計学および機械学習における中核的手法について述べる。
LSA は、$d$-次元線型系 $\bar{\mathbf{A}} \theta = \bar{\mathbf{b}}$ の近似解を計算するのに使われ、$(\bar{\mathbf{A}}, \bar{\mathbf{b}})$ は(漸近的に)非偏見的観測 $\{(\mathbf{A}(Z_n),\mathbf{b}(Z_n))\}_{n \in \mathbb{N}}$ によってのみ推定できる。
ここでは、$\{Z_n\}_{n \in \mathbb{N}}$ が i.d. 列あるいは一様エルゴード的マルコフ連鎖である場合を考える。
lsa で定義されるイテレートとその polyak-ruppert-averaged バージョンに対する p$-th moment と高確率偏差境界を導出する。
平均化 LSA イテレートに対する有限時間インスタンス依存境界は、我々が得られる先行項が局所漸近ミニマックス極限と一致するという意味で鋭い。
さらに、境界の残りの項は、基礎となるチェーンとノイズ変数のノルムの混合時間 $t_{\operatorname{mix}}$ に強く依存していることを認めています。
我々は,問題次元が$d$の対数でのみスケールするには,SAステップサイズが必要であることを強調した。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
この論文は$d$-dimensional recursion approximation, $$theta_n+1=theta_n + alpha_n + 1 f(theta_n, Phi_n+1)に関するものである。
主な結果は、ドスカー・バラダン・リャプノフドリフト条件(DV3)の平均流とバージョンに関する追加条件の下で確立される。
a example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometryal.
論文 参考訳（メタデータ） (2021-10-27T13:38:25Z) - Tight High Probability Bounds for Linear Stochastic Approximation with
Fixed Stepsize [41.38162218102825]
本稿では,線形近似 (LSA) アルゴリズムの漸近的解析を行う。
我々は、より弱い条件下での LSA の性能に高い確率境界を導出する:$(bf A_n, bf b_n): n in mathbbN*$。
bf A_n: n in mathbbN*$ {\displaystyle \mathbbN*=} の列について追加の仮定なしでは、我々の結論は改善できないことを示す。
論文 参考訳（メタデータ） (2021-06-02T16:10:37Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。