論文の概要: Formalization of a Stochastic Approximation Theorem
- arxiv url: http://arxiv.org/abs/2202.05959v1
- Date: Sat, 12 Feb 2022 02:31:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-18 12:01:18.503053
- Title: Formalization of a Stochastic Approximation Theorem
- Title(参考訳): 確率近似定理の形式化
- Authors: Koundinya Vajjha, Barry Trager, Avraham Shinnar, Vasily Pestun
- Abstract要約: 近似アルゴリズムは、ターゲットが不明な環境でターゲット値を近似するために使用される反復的な手順である。
もともとは1951年にRobinsとMonroによって発表された論文で、近似の分野は飛躍的に成長し、応用領域に影響を与えている。
- 参考スコア(独自算出の注目度): 0.22940141855172028
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic approximation algorithms are iterative procedures which are used
to approximate a target value in an environment where the target is unknown and
direct observations are corrupted by noise. These algorithms are useful, for
instance, for root-finding and function minimization when the target function
or model is not directly known. Originally introduced in a 1951 paper by
Robbins and Monro, the field of Stochastic approximation has grown enormously
and has come to influence application domains from adaptive signal processing
to artificial intelligence. As an example, the Stochastic Gradient Descent
algorithm which is ubiquitous in various subdomains of Machine Learning is
based on stochastic approximation theory. In this paper, we give a formal proof
(in the Coq proof assistant) of a general convergence theorem due to Aryeh
Dvoretzky, which implies the convergence of important classical methods such as
the Robbins-Monro and the Kiefer-Wolfowitz algorithms. In the process, we build
a comprehensive Coq library of measure-theoretic probability theory and
stochastic processes.
- Abstract(参考訳): 確率近似アルゴリズム(英: Stochastic approximation algorithm)は、目標が未知で直接観測がノイズによって破壊される環境において、目標値の近似に使用される反復的な手順である。
これらのアルゴリズムは、例えば、ターゲット関数やモデルが直接知られていない場合、ルートフィンディングや関数最小化に有用である。
もともと1951年にrobbinsとmonroによって発表された論文で、確率近似の分野は急速に成長し、適応的信号処理から人工知能まで応用領域に影響を与えるようになった。
例えば、機械学習の様々なサブドメインにおいてユビキタスである確率的勾配降下アルゴリズムは、確率的近似理論に基づいている。
本稿では、Aryeh Dvoretzkyによる一般収束定理の形式的証明(コーク証明アシスタント)を与える。これは、ロビンス・モンロやキーファー・ヴォルフォヴィッツアルゴリズムのような重要な古典的手法の収束を意味する。
この過程で、測度論的確率論と確率過程の包括的なcoqライブラリを構築する。
関連論文リスト
- Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳(メタデータ) (2023-07-08T15:41:48Z) - The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。
ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。
ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
論文 参考訳(メタデータ) (2022-06-14T12:30:11Z) - Gaussian Processes and Statistical Decision-making in Non-Euclidean
Spaces [96.53463532832939]
我々はガウス過程の適用性を高める技術を開発した。
この観点から構築した効率的な近似を幅広く導入する。
非ユークリッド空間上のガウス過程モデルの集合を開発する。
論文 参考訳(メタデータ) (2022-02-22T01:42:57Z) - Laplace Matching for fast Approximate Inference in Generalized Linear
Models [27.70274403550477]
本論文では,高い近似品質を実現しつつ,計算的に安価に設計した近似推論フレームワークを提案する。
我々が emphLaplace Matching と呼ぶこの概念は、指数群のパラメータ空間間の閉形式、近似、双方向変換を含む。
これにより、GLMにおける推論を(小さな近似誤差で)共役推論に変換する。
論文 参考訳(メタデータ) (2021-05-07T08:25:17Z) - Statistical Inference for Polyak-Ruppert Averaged Zeroth-order
Stochastic Gradient Algorithm [10.936043362876651]
過去10年間、複数の機械学習モデルにおける推定やトレーニングは、勾配アルゴリズムの実行と同義語になってきた。
まず、ゼロ次設定でPolyak-Ruppert平均勾配アルゴリズムの中心限界を確立する。
論文 参考訳(メタデータ) (2021-02-10T00:47:20Z) - Mean-Field Approximation to Gaussian-Softmax Integral with Application
to Uncertainty Estimation [23.38076756988258]
ディープニューラルネットワークにおける不確実性を定量化するための,新しい単一モデルに基づくアプローチを提案する。
平均場近似式を用いて解析的に難解な積分を計算する。
実験的に,提案手法は最先端の手法と比較して競合的に機能する。
論文 参考訳(メタデータ) (2020-06-13T07:32:38Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳(メタデータ) (2020-05-21T17:36:09Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳(メタデータ) (2020-03-27T05:13:29Z) - Scalable Approximate Inference and Some Applications [2.6541211006790983]
本稿では,近似推論のための新しいフレームワークを提案する。
提案する4つのアルゴリズムは,Steinの手法の最近の計算進歩に動機付けられている。
シミュレーションおよび実データを用いた結果から,アルゴリズムの統計的効率と適用性を示す。
論文 参考訳(メタデータ) (2020-03-07T04:33:27Z) - SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for
Gaussian Process Regression with Derivatives [86.01677297601624]
本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。
我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
論文 参考訳(メタデータ) (2020-03-05T14:33:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。