論文の概要: Online Learning with Adversaries: A Differential Inclusion Analysis
- arxiv url: http://arxiv.org/abs/2304.01525v1
- Date: Tue, 4 Apr 2023 04:32:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 15:13:02.081009
- Title: Online Learning with Adversaries: A Differential Inclusion Analysis
- Title（参考訳）: 広告主によるオンライン学習:差分包摂分析
- Authors: Swetha Ganesh, Alexandre Reiffers-Masson, Gugan Thoppe
- Abstract要約: 測定モデル $Y = AX,$ where $X$ を考えると、$Y$ は確率変数であり、$A$ は既知の高い行列である。
それぞれのインスタンスで$Y$の座標の1つのサンプルが利用可能であり、そのゴールはこれらのサンプルを通して$mu := mathbbE[X]$を推定することである。
ほぼ確実に$mu$に収束する最初の非同期オンラインアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 72.03204542524018
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the measurement model $Y = AX,$ where $X$ and, hence, $Y$ are
random variables and $A$ is an a priori known tall matrix. At each time
instance, a sample of one of $Y$'s coordinates is available, and the goal is to
estimate $\mu := \mathbb{E}[X]$ via these samples. However, the challenge is
that a small but unknown subset of $Y$'s coordinates are controlled by
adversaries with infinite power: they can return any real number each time they
are queried for a sample. For such an adversarial setting, we propose the first
asynchronous online algorithm that converges to $\mu$ almost surely. We prove
this result using a novel differential inclusion based two-timescale analysis.
Two key highlights of our proof include: (a) the use of a novel Lyapunov
function for showing that $\mu$ is the unique global attractor for our
algorithm's limiting dynamics, and (b) the use of martingale and stopping time
theory to show that our algorithm's iterates are almost surely bounded.
- Abstract（参考訳）: 測定モデル $y = ax,$ ここで $x$ とすると、$y$ は確率変数であり、$a$ は事前の既知の背の高い行列である。
それぞれのインスタンスにおいて、$y$の座標の1つのサンプルが利用可能であり、目標はこれらのサンプルから$\mu := \mathbb{e}[x]$を推定することである。
しかし、Y$の座標の小さいが未知の部分集合は無限の力を持つ敵によって制御される。
そのような対向的な設定のために、ほぼ確実に$\mu$に収束する最初の非同期オンラインアルゴリズムを提案する。
この結果は,新たな差分包摂法に基づく2時間スケール解析を用いて証明する。
証明の2つの重要なハイライトは
(a)新しいリアプノフ関数を用いて、$\mu$が我々のアルゴリズムの制限力学のユニークなグローバルな誘引子であることを示し、
(b)マルティンゲールと停止時間理論を用いて、我々のアルゴリズムの反復がほぼ確実に有界であることを示す。
関連論文リスト
- Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Solving Constrained Variational Inequalities via an Interior Point
Method [88.39091990656107]
制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。
本稿では,2種類の問題においてACVIの収束保証を提供する。
この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
論文 参考訳（メタデータ） (2022-06-21T17:55:13Z) - A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous
Q-Learning and TD-Learning Variants [39.28675942566465]
本稿では,値に基づく非同期RLアルゴリズムのクラスに対する有限サンプル収束保証について検討する枠組みを開発する。
副産物として、偏差トレードオフ、すなわちRLにおけるブートストラップの効率に関する理論的知見を提供する。
論文 参考訳（メタデータ） (2021-02-02T15:48:19Z) - Learning Sign-Constrained Support Vector Machines [0.24466725954625884]
符号制約下で経験的リスクを最小化するための2つの最適化アルゴリズムを開発した。
2つのアルゴリズムのうちの1つは、投影勾配法に基づいており、投影勾配法の各イテレーションは計算コストが$o(nd)である。
訓練例と類似性が特徴ベクトルを構成する場合,符号制約が有望な手法であることを実証する。
論文 参考訳（メタデータ） (2021-01-05T12:08:17Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳（メタデータ） (2020-03-27T05:13:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。