論文の概要: Stability and Convergence of Distributed Stochastic Approximations with
large Unbounded Stochastic Information Delays
- arxiv url: http://arxiv.org/abs/2305.07091v1
- Date: Thu, 11 May 2023 18:54:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-15 14:55:51.351060
- Title: Stability and Convergence of Distributed Stochastic Approximations with
large Unbounded Stochastic Information Delays
- Title（参考訳）: 大規模非有界確率的情報遅延を伴う分散確率近似の安定性と収束
- Authors: Adrian Redder, Arunselvan Ramaswamy, Holger Karl
- Abstract要約: 情報処理の年代 (AoIPs): 単位成長特性を持つ非負整数上の過程を紹介する。
任意のモーメント境界を持つAoIPは、無限に時間の分数を超えることはできないことを示す。
適度に選択されたステップサイズと組み合わせると、この性質は分散SAの安定性に十分であることがわかった。
- 参考スコア（独自算出の注目度）: 4.34720256795424
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We generalize the Borkar-Meyn stability Theorem (BMT) to distributed
stochastic approximations (SAs) with information delays that possess an
arbitrary moment bound. To model the delays, we introduce Age of Information
Processes (AoIPs): stochastic processes on the non-negative integers with a
unit growth property. We show that AoIPs with an arbitrary moment bound cannot
exceed any fraction of time infinitely often. In combination with a suitably
chosen stepsize, this property turns out to be sufficient for the stability of
distributed SAs. Compared to the BMT, our analysis requires crucial
modifications and a new line of argument to handle the SA errors caused by AoI.
In our analysis, we show that these SA errors satisfy a recursive inequality.
To evaluate this recursion, we propose a new Gronwall-type inequality for
time-varying lower limits of summations. As applications to our distributed
BMT, we discuss distributed gradient-based optimization and a new approach to
analyzing SAs with momentum.
- Abstract（参考訳）: 任意のモーメント境界を持つ情報遅延を持つ確率近似(SA)にBMT(Borkar-Meyn stability Theorem)を一般化する。
遅延をモデル化するために, 単位成長特性を持つ非負整数の確率過程である age of information process (aoips) を導入する。
任意のモーメント境界を持つAoIPは、無限に時間の分数を超えることはできないことを示す。
適度に選択されたステップサイズと組み合わせると、この性質は分散SAの安定性に十分であることがわかった。
BMTと比較すると,AoIによるSAの誤りに対処するためには,重要な修正と新たな議論が必要である。
本分析では,これらSA誤差が再帰的不等式を満たすことを示す。
この再帰を評価するために, 時変下限に対する新しいグロンウォール型不等式を提案する。
分散BMTへの応用として、分散勾配に基づく最適化と、運動量を持つSAを解析するための新しいアプローチについて論じる。
関連論文リスト
- Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。
近年の研究では、この問題をアクター批判の枠組みで研究している。
線形関数近似を用いた時間差分学習(TD)について検討した。
論文 参考訳（メタデータ） (2024-10-29T03:40:53Z) - Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。
本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。
我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
論文 参考訳（メタデータ） (2024-10-03T09:07:13Z) - Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits [0.0]
対称な報酬分布のための分布自由データ駆動型 UCB アルゴリズムを提案する。
パラメータフリーなRMM-UCB法では,重み付き分布であっても,ほぼ最適の残差を証明した。
論文 参考訳（メタデータ） (2024-06-09T10:06:50Z) - Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。
本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
論文 参考訳（メタデータ） (2024-04-03T00:41:19Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - KL Convergence Guarantees for Score diffusion models under minimal data assumptions [9.618473763561418]
注目すべき課題は、包括的な定量的結果の欠如という形で続いている。
この記事では、Ornstein-Uhlenbeck半群とその運動論的対応から生じる一定のステップサイズを持つスコア拡散モデルに焦点を当てる。
論文 参考訳（メタデータ） (2023-08-23T16:31:08Z) - From Optimality to Robustness: Dirichlet Sampling Strategies in
Stochastic Bandits [0.0]
本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。
この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
論文 参考訳（メタデータ） (2021-11-18T14:34:21Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。