論文の概要: Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation
- arxiv url: http://arxiv.org/abs/2207.04475v1
- Date: Sun, 10 Jul 2022 14:36:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-12 14:34:59.938730
- 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$次元線形系の近似解を計算するために用いられる。
次数 $(p α t_operatornamemix)1/2d1/p$ を LSA の最終反復モーメントの$p$-番目のモーメントに設定する。
- 参考スコア（独自算出の注目度）: 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 through
(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, and derive $p$-moments inequality
and high probability bounds for the iterates defined by LSA and its
Polyak-Ruppert averaged version. More precisely, we establish bounds of order
$(p \alpha t_{\operatorname{mix}})^{1/2}d^{1/p}$ on the $p$-th moment of the
last iterate of LSA. In this formula $\alpha$ is the step size of the procedure
and $t_{\operatorname{mix}}$ is the mixing time of the underlying chain
($t_{\operatorname{mix}}=1$ in the i.i.d. setting). We then prove finite-time
instance-dependent bounds on the Polyak-Ruppert averaged sequence of iterates.
These results are sharp in the sense that the leading term we obtain matches
the local asymptotic minimax limit, including tight dependence on the
parameters $(d,t_{\operatorname{mix}})$ in the higher order terms.
- 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.i.d. 列または一様幾何学的にエルゴードマルコフ鎖であり、 lsa とそのポリアック・ラッパート平均化バージョンで定義されるイテレートに対する $p$-moments の不等式と高い確率境界が導かれる場合を考える。
より正確には、次数 $(p \alpha t_{\operatorname{mix}})^{1/2}d^{1/p}$ の有界を LSA の最終反復点の$p$-番目のモーメントに設定する。
この式では、$\alpha$ は手続きのステップサイズであり、$t_{\operatorname{mix}}$ は、基礎となるチェーンの混合時間 (t_{\operatorname{mix}}=1$ in the i.i.d. set) である。
次に、イテレートのPolyak-Ruppert平均列上の有限時間インスタンス依存境界を証明する。
これらの結果は、我々が得る先行項が、高次項のパラメータ $(d,t_{\operatorname{mix}})$ に対する厳密な依存を含む局所漸近的ミニマックス極限と一致するという意味で鋭い。
関連論文リスト
- 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) $$$ ここで、Phi_n $は一般的な状態空間上の過程である。
主な結果は,ドスカー・バラダン・リャプノフドリフト条件(DV3): (i)適切なリャプノフドリフト条件(DV3)の,平均流とバージョンに関する追加条件の下で確立される。
論文 参考訳（メタデータ） (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。