論文の概要: Convergence of Stochastic Approximation via Martingale and Converse
Lyapunov Methods
- arxiv url: http://arxiv.org/abs/2205.01303v1
- Date: Tue, 3 May 2022 04:51:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-04 22:31:25.968622
- Title: Convergence of Stochastic Approximation via Martingale and Converse
Lyapunov Methods
- Title(参考訳): Martingale と Converse Lyapunov 法による確率近似の収束
- Authors: M. Vidyasagar
- Abstract要約: 我々は、近似アルゴリズムの収束を証明するための非常に一般的なフレームワークを開発するために、Gladyshev (1965) で最初に提案されたアイデアに基づいて構築する。
これらのアイデアはマーチンゲール法に基づいており、ODE法に基づく収束証明よりもいくつかの点で単純である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper is dedicated to Prof. Eduardo Sontag on the occasion of his
seventieth birthday. In this paper, we build upon the ideas first proposed in
Gladyshev (1965) to develop a very general framework for proving the almost
sure boundedness and the convergence of stochastic approximation algorithms.
These ideas are based on martingale methods and are in some ways simpler than
convergence proofs based on the ODE method, e.g., Borkar-Meyn (2000). First we
study the original version of the SA algorithm introduced in Robbins-Monro
(1951), where the objective is to determine a zero of a function, when only
noisy measurements of the function are available. The proof makes use of the
general framework developed here, together with a new theorem on converse
Lyapunov stability, which might be of independent interest. Next we study an
alternate version of SA, first introduced in Kiefer-Wolfowitz (1952). The
objective here is to find a stationary point of a scalar-valued function, using
first-order differences to approximate its gradient. This problem is analyzed
in Blum (1954), but with a very opaque proof. We reproduce Blum's conclusions
using the proposed framework.
- Abstract(参考訳): この論文はエドゥアルド・ソンタグ教授の70歳の誕生日に捧げられている。
本稿では、Gladyshev (1965) で最初に提案されたアイデアに基づいて、ほぼ確実な有界性と確率近似アルゴリズムの収束性を証明するための非常に一般的な枠組みを構築する。
これらのアイデアはマーチンゲール法に基づいており、例えば Borkar-Meyn (2000) など ODE 法に基づく収束証明よりも単純である。
まず、ロビンス・モンロ(1951)で導入されたSAアルゴリズムの原版について検討し、関数の雑音測定しかできないとき、関数の零点を決定することが目的である。
この証明は、ここで開発された一般の枠組みを利用し、逆リアプノフ安定性に関する新しい定理は独立に興味を持つかもしれない。
次に、Kiefer-Wolfowitz (1952) で最初に導入された SA の代替版について研究する。
ここでの目標は、一階差を使って勾配を近似してスカラー値関数の定常点を見つけることである。
この問題は Blum (1954) で解析されるが、非常に不透明な証明である。
提案手法を用いてBlumの結論を再現する。
関連論文リスト
- Understanding Progressive Training Through the Framework of Randomized
Coordinate Descent [1.6758573326215689]
我々は、よく知られたプログレッシブトレーニング手法(PT)のプロキシであるランダム化プログレッシブトレーニングアルゴリズム(RPT)を提案する。
RPT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is first PT is
論文 参考訳(メタデータ) (2023-06-06T12:27:54Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳(メタデータ) (2023-04-04T04:32:29Z) - A Primal-dual Approach for Solving Variational Inequalities with
General-form Constraints [81.32297040574083]
Yang et al. (2023) は最近、一階法により等式と不等式制約で変分不等式 (VIs) を解くというオープンな問題に対処した。
本稿では,各イテレーションで約1つのサブプロブレムを解くウォームスタート手法を採用する。
我々はこの収束を証明し、演算子が$L$-Lipschitz および monotone であるとき、この不正確な-ACVI 法の最後の繰り返しのギャップ関数が $mathcalO(frac1sqrtK)$ で減少することを示す。
論文 参考訳(メタデータ) (2022-10-27T17:59:09Z) - Robust Counterfactual Explanations for Random Forests [76.84947521482631]
本研究では,アンサンブルモデルのロバスト性とベース学習者のロバスト性との関係について検討する。
既存の手法が驚くほど低いロバスト性を与えることを示す: 単純な反事実の妥当性は、ほとんどのデータセットで50%以下である。
本手法は, 反実的説明から初期観測までの距離をわずかに増加させるだけで, 高いロバスト性を実現する。
論文 参考訳(メタデータ) (2022-05-27T17:28:54Z) - Gaussian Processes and Statistical Decision-making in Non-Euclidean
Spaces [96.53463532832939]
我々はガウス過程の適用性を高める技術を開発した。
この観点から構築した効率的な近似を幅広く導入する。
非ユークリッド空間上のガウス過程モデルの集合を開発する。
論文 参考訳(メタデータ) (2022-02-22T01:42:57Z) - Formalization of a Stochastic Approximation Theorem [0.22940141855172028]
近似アルゴリズムは、ターゲットが不明な環境でターゲット値を近似するために使用される反復的な手順である。
もともとは1951年にRobinsとMonroによって発表された論文で、近似の分野は飛躍的に成長し、応用領域に影響を与えている。
論文 参考訳(メタデータ) (2022-02-12T02:31:14Z) - Manifold Hypothesis in Data Analysis: Double Geometrically-Probabilistic
Approach to Manifold Dimension Estimation [92.81218653234669]
本稿では, 多様体仮説の検証と基礎となる多様体次元推定に対する新しいアプローチを提案する。
我々の幾何学的手法はミンコフスキー次元計算のためのよく知られたボックスカウントアルゴリズムのスパースデータの修正である。
実データセットの実験では、2つの手法の組み合わせに基づく提案されたアプローチが強力で効果的であることが示されている。
論文 参考訳(メタデータ) (2021-07-08T15:35:54Z) - Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric
Perceptron [21.356438315715888]
我々は、ニューラルネットワークの単純なモデルである対称バイナリパーセプトロンモデルを検討する。
このモデルのためのいくつかの予想を確立する。
この証明手法は,小さなグラフ条件付け手法の密な反部分に依存する。
論文 参考訳(メタデータ) (2021-02-25T18:39:08Z) - Variational Intrinsic Control Revisited [7.6146285961466]
Gregorらによるオリジナルの研究で、2つのVICアルゴリズムが提案された: 1つは明示的にオプションを表すもので、もう1つは暗黙的にそれを行うものである。
後者で用いられる本質的な報酬は環境に偏りがあり、最適解に収束することを示した。
本稿では,この動作を補正し,最大エンパワーメントを達成するための2つの方法を提案する。
論文 参考訳(メタデータ) (2020-10-07T09:00:48Z) - The FMRIB Variational Bayesian Inference Tutorial II: Stochastic
Variational Bayes [1.827510863075184]
このチュートリアルは、オリジナルのFMRIB Variational Bayesチュートリアルを再考する。
この新しいアプローチは、機械学習アルゴリズムに適用された計算方法に多くの類似性を持ち、恩恵を受けている。
論文 参考訳(メタデータ) (2020-07-03T11:31:52Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳(メタデータ) (2020-05-12T16:44:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。