論文の概要: Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation

• arxiv url: http://arxiv.org/abs/2602.02445v1
• Date: Mon, 02 Feb 2026 18:41:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.367509
• Title: Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation
• Title（参考訳）: 非線形確率近似における有限サンプルワッサースタイン誤差境界と濃度不等式
• Authors: Seo Taek Kong, R. Srikant,
• Abstract要約: ワッサーシュタイン-$p$距離における非線形近似アルゴリズムの非漸近誤差境界を導出する。 正規化された最後の繰り返しは、$p$-ワッサーシュタイン距離のガウス分布に階数$_n1/6$で収束することを示し、$_n$はステップサイズである。 これらの分布保証は、モーメント境界やマルコフの不等式から得られるものより改善される高確率濃度の不等式を暗示する。
• 参考スコア（独自算出の注目度）: 6.800624963330628
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper derives non-asymptotic error bounds for nonlinear stochastic approximation algorithms in the Wasserstein-$p$ distance. To obtain explicit finite-sample guarantees for the last iterate, we develop a coupling argument that compares the discrete-time process to a limiting Ornstein-Uhlenbeck process. Our analysis applies to algorithms driven by general noise conditions, including martingale differences and functions of ergodic Markov chains. Complementing this result, we handle the convergence rate of the Polyak-Ruppert average through a direct analysis that applies under the same general setting. Assuming the driving noise satisfies a non-asymptotic central limit theorem, we show that the normalized last iterates converge to a Gaussian distribution in the $p$-Wasserstein distance at a rate of order $γ_n^{1/6}$, where $γ_n$ is the step size. Similarly, the Polyak-Ruppert average is shown to converge in the Wasserstein distance at a rate of order $n^{-1/6}$. These distributional guarantees imply high-probability concentration inequalities that improve upon those derived from moment bounds and Markov's inequality. We demonstrate the utility of this approach by considering two applications: (1) linear stochastic approximation, where we explicitly quantify the transition from heavy-tailed to Gaussian behavior of the iterates, thereby bridging the gap between recent finite-sample analyses and asymptotic theory and (2) stochastic gradient descent, where we establish rate of convergence to the central limit theorem.
• Abstract（参考訳）: 本稿では,Wasserstein-$p$距離における非線形確率近似アルゴリズムの漸近誤差境界を導出する。 最後の繰り返しに対する明示的な有限サンプル保証を得るために、離散時間過程と限定的なオルンシュタイン・ウレンベック過程を比較する結合論法を開発する。 我々の分析は、マルティンゲール差分やエルゴードマルコフ連鎖の関数を含む一般的な雑音条件によって駆動されるアルゴリズムに適用される。 この結果を補完し、同一の一般条件下で適用される直接解析により、ポリアク・ルパート平均の収束率を扱う。 駆動雑音が漸近的でない中心極限定理を満たすと仮定すると、正規化された最後の反復は、次数$γ_n^{1/6}$で$p$-ワッサーシュタイン距離のガウス分布に収束する。 同様に、Polyak-Ruppert平均はワッサーシュタイン距離に$n^{-1/6}$の速度で収束することが示される。 これらの分布保証は、モーメント境界とマルコフの不等式から得られるものより改善される高確率濃度の不等式を暗示する。 線形確率近似(英語版)は、重み付きからガウス的な反復の振る舞いへの遷移を明示的に定量化し、その結果、最近の有限サンプル解析と漸近的理論のギャップを埋めるものである。

関連論文リスト

• Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation [12.69327994479157]
  We consider linear two-time-scale approximation algorithm driven by martingale noise。 我々は、PolyakRuppert平均化を用いた2時間スケール近似のためのワッサーシュタイン-1距離に関する最初の漸近的中心極限定理を導出した。
  論文  参考訳（メタデータ） (2025-02-14T03:20:30Z)
• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  本研究では, 勾配勾配勾配(SGD)を一定のステップサイズで解くことで, 密接な凸と滑らかな問題を解く問題に対処する。 得られた推定子の平均二乗誤差を、反復数$n$に対して拡張する。 我々の分析は、時相マルコフ連鎖と見なされるSGDの特性に依存している。
  論文  参考訳（メタデータ） (2024-10-07T15:02:48Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• 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)

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

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