論文の概要: Quantitative Error Bounds for Scaling Limits of Stochastic Iterative Algorithms
- arxiv url: http://arxiv.org/abs/2501.12212v1
- Date: Tue, 21 Jan 2025 15:29:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-22 14:23:58.581034
- Title: Quantitative Error Bounds for Scaling Limits of Stochastic Iterative Algorithms
- Title（参考訳）: 確率的反復アルゴリズムのスケーリング限界に対する定量的誤差境界
- Authors: Xiaoyu Wang, Mikolaj J. Kasprzak, Jeffrey Negrea, Solesne Bourguin, Jonathan H. Huggins,
- Abstract要約: アルゴリズムのサンプルパスとOrnstein-Uhlenbeck近似の非漸近関数近似誤差を導出する。
我々は、L'evy-Prokhorov と有界ワッサーシュタイン距離という2つの一般的な測度で誤差境界を構築するために、主要な結果を使用する。
- 参考スコア（独自算出の注目度）: 10.022615790746466
- License:
- Abstract: Stochastic iterative algorithms, including stochastic gradient descent (SGD) and stochastic gradient Langevin dynamics (SGLD), are widely utilized for optimization and sampling in large-scale and high-dimensional problems in machine learning, statistics, and engineering. Numerous works have bounded the parameter error in, and characterized the uncertainty of, these approximations. One common approach has been to use scaling limit analyses to relate the distribution of algorithm sample paths to a continuous-time stochastic process approximation, particularly in asymptotic setups. Focusing on the univariate setting, in this paper, we build on previous work to derive non-asymptotic functional approximation error bounds between the algorithm sample paths and the Ornstein-Uhlenbeck approximation using an infinite-dimensional version of Stein's method of exchangeable pairs. We show that this bound implies weak convergence under modest additional assumptions and leads to a bound on the error of the variance of the iterate averages of the algorithm. Furthermore, we use our main result to construct error bounds in terms of two common metrics: the L\'{e}vy-Prokhorov and bounded Wasserstein distances. Our results provide a foundation for developing similar error bounds for the multivariate setting and for more sophisticated stochastic approximation algorithms.
- Abstract（参考訳）: 確率勾配勾配勾配(SGD)や確率勾配ランゲヴィンダイナミクス(SGLD)を含む確率反復アルゴリズムは、機械学習、統計学、工学における大規模かつ高次元の問題の最適化とサンプリングに広く利用されている。
多くの研究がパラメータエラーを境界付け、これらの近似の不確かさを特徴付けている。
1つの一般的なアプローチは、特に漸近的なセットアップにおいて、アルゴリズムサンプルパスの分布を連続時間確率過程近似に関連付けるためにスケーリング制限解析を使用することである。
単変量設定に着目し、本論文では、Steinの交換可能なペアの無限次元版を用いたアルゴリズムサンプルパスとOrnstein-Uhlenbeck近似の間の非漸近関数近似誤差を導出する以前の研究に基づいて構築する。
このバウンダリは、穏やかな仮定の下で弱収束を示し、アルゴリズムの反復平均のばらつきの誤差に結びつくことを示す。
さらに、我々は、L\'{e}vy-Prokhorov と有界ワッサーシュタイン距離という2つの共通の測度で誤差境界を構築するために、主要な結果を使用する。
この結果は,多変量設定とより洗練された確率近似アルゴリズムのための類似の誤差境界の開発の基礎となる。
関連論文リスト
- Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。
本実験は, 勾配法よりも近似分散還元法の利点を実証する。
論文 参考訳（メタデータ） (2023-08-18T05:11:50Z) - Variational sparse inverse Cholesky approximation for latent Gaussian
processes via double Kullback-Leibler minimization [6.012173616364571]
後肢の変分近似とSIC制限したKulback-Leibler-Optimal近似を併用した。
この設定のために、我々の変分近似は反復毎の多対数時間で勾配降下によって計算できる。
本稿では,DKLGP(Double-Kullback-Leibler-Optimal Gaussian-process approximation)を提案する。
論文 参考訳（メタデータ） (2023-01-30T21:50:08Z) - Exponential Concentration in Stochastic Approximation [0.8192907805418583]
我々は,各ステップで目標に向かって反復的に進行する近似アルゴリズムの挙動を解析する。
我々はマルコフ近似アルゴリズム、具体的には射影勾配 Descent, Kiefer-Wolfowitz および Frank-Wolfe アルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-08-15T14:57:26Z) - Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。
軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。
また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文 参考訳（メタデータ） (2022-07-09T01:44:17Z) - Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
ガウスのプロセスはデータセットのサイズとともに違法にスケールする。
多くの近似法が開発されており、必然的に近似誤差を導入している。
この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。
本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
論文 参考訳（メタデータ） (2022-05-30T22:16:25Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Non-asymptotic bounds for stochastic optimization with biased noisy
gradient oracles [8.655294504286635]
関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。
提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
論文 参考訳（メタデータ） (2020-02-26T12:53:04Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。