論文の概要: Sharp Gaussian approximation for Polyak--Ruppert averaged linear stochastic approximation
- arxiv url: http://arxiv.org/abs/2611.15442v1
- Date: Wed, 11 Nov 2026 13:15:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.148524
- Title: Sharp Gaussian approximation for Polyak--Ruppert averaged linear stochastic approximation
- Title(参考訳): Polyak-Ruppert 平均線形確率近似に対するシャープガウス近似
- Abstract要約: 固定次元の凸集合上の近似誤差に対して位数$n-1$の上限を証明する。
この範囲で最速のレートは$n-1/2$で、$=1/2$に達する。
- 参考スコア(独自算出の注目度): 30.826724786263565
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study how quickly the normalized Polyak--Ruppert average approaches its Gaussian limit in linear stochastic approximation with bounded i.i.d.\ coefficients. For step sizes decaying as $k^{-γ}$, with $1/2\leγ<1$, we prove an upper bound of order $n^{γ-1}$ on the approximation error over convex sets in fixed dimension. A matching lower bound holds for every fixed model. The fastest rate in this range is $n^{-1/2}$, attained at $γ=1/2$. We also obtain an $O(n^{-1/2})$ bound on the error of the recursive multiplier bootstrap procedure.
- Abstract(参考訳): 我々は、正規化されたポリアック-ルパート平均が、有界な i.d.\ 係数を持つ線形確率近似におけるガウス極限にいかに早く近づくかを研究する。
ステップサイズが$k^{-γ}$、$/2\leγ<1$とすると、固定次元の凸集合上の近似誤差に対して位数$n^{γ-1}$の上限が証明される。
一致した下界は、固定されたモデルごとに保持される。
この範囲で最速のレートは$n^{-1/2}$で、$γ=1/2$に達する。
また、再帰的乗算ブートストラップ手順の誤差に基づいて$O(n^{-1/2})$バウンドを得る。
関連論文リスト
- Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions [50.90629146297993]
期待値において精度$varepsilon$に達する複雑さを導出する。
上界は提案手法YETIにより達成される。
下界は、任意の一階法で困難であるインスタンスの族を明示的に構成することで得られる。
論文 参考訳(メタデータ) (2026-11-03T02:01:46Z) - Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent [15.054399128586232]
すべての固定指数 $in(1/2,1)$ に対して、一次元の滑らかで強凸な例は、コルモゴロフと凸距離における位数 $n1/2-+n-1$ の制限的分散を伴う近似誤差を持つ。
非線形バイアスは、ガウス参照が有限線型化分散を使用するときでさえ$n1/2-$に寄与する。
論文 参考訳(メタデータ) (2026-10-31T17:47:59Z) - Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。
学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。
定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
論文 参考訳(メタデータ) (2026-09-30T18:26:29Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳(メタデータ) (2025-09-20T20:18:49Z) - Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks [2.7195102129095003]
以下の2つの問題について検討する。
1つ目は、$mathbbRd+1$の任意のソノイドがハウスドルフ距離で$n$の線分で近似できる誤差を決定することである。
2つ目は、変動空間上の浅いReLU$k$ニューラルネットワークの均一ノルムにおける最適近似率を決定することである。
論文 参考訳(メタデータ) (2023-07-28T03:43:17Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。