論文の概要: On the power of adaptivity in statistical adversaries
- arxiv url: http://arxiv.org/abs/2111.10352v1
- Date: Fri, 19 Nov 2021 18:26:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-22 16:36:43.051903
- Title: On the power of adaptivity in statistical adversaries
- Title(参考訳): 統計的逆数における適応性の力について
- Authors: Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
- Abstract要約: 統計的問題における対向雑音モデルに関する基礎的問題について検討する。
アルゴリズムの振舞い $mathcalA'$ は、アルゴリズムの $mathcalA'$ のアダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダクティブ・アダクショナル・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ(英語版)によって常によく近似することができるか?
- 参考スコア(独自算出の注目度): 18.973408992715203
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a fundamental question concerning adversarial noise models in
statistical problems where the algorithm receives i.i.d. draws from a
distribution $\mathcal{D}$. The definitions of these adversaries specify the
type of allowable corruptions (noise model) as well as when these corruptions
can be made (adaptivity); the latter differentiates between oblivious
adversaries that can only corrupt the distribution $\mathcal{D}$ and adaptive
adversaries that can have their corruptions depend on the specific sample $S$
that is drawn from $\mathcal{D}$.
In this work, we investigate whether oblivious adversaries are effectively
equivalent to adaptive adversaries, across all noise models studied in the
literature. Specifically, can the behavior of an algorithm $\mathcal{A}$ in the
presence of oblivious adversaries always be well-approximated by that of an
algorithm $\mathcal{A}'$ in the presence of adaptive adversaries? Our first
result shows that this is indeed the case for the broad class of statistical
query algorithms, under all reasonable noise models. We then show that in the
specific case of additive noise, this equivalence holds for all algorithms.
Finally, we map out an approach towards proving this statement in its fullest
generality, for all algorithms and under all reasonable noise models.
- Abstract(参考訳): 本稿では,アルゴリズムが分布$\mathcal{D}$から引き出す統計的問題において,逆雑音モデルに関する基本的問題について検討する。
これらの敵の定義は、許容される腐敗の種類(ノイズモデル)と、これらの腐敗(適応性)を規定している。後者は、$\mathcal{d}$の分布を損なうことしかできない限定的な敵と、その腐敗を$\mathcal{d}$から引き出す特定のサンプル$s$に依存する適応的な敵とを区別する。
本研究では,文献で研究されているすべてのノイズモデルにおいて,難解な敵が適応的敵に効果的に等価であるか否かを検討する。
具体的には、従属敵の存在下でのアルゴリズム $\mathcal{a}$ の振る舞いは、常に適応敵の存在下で $\mathcal{a}'$ のアルゴリズムの振る舞いによって近似することができるか?
最初の結果は、すべての妥当なノイズモデルの下で、統計クエリアルゴリズムの幅広いクラスが実際にそうであることを示している。
次に、付加雑音の特定の場合において、この等価性はすべてのアルゴリズムに対して成立することを示す。
最後に、すべてのアルゴリズムと妥当なノイズモデルに対して、このステートメントを最大限の汎用性で証明するアプローチを図示する。
関連論文リスト
- Adversarially Robust Distributed Count Tracking via Partial Differential
Privacy [17.43748116766233]
分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。
このモデルは、各アイテムのストリームを受け取り、中央サーバと通信する、$k$のサイトを含む。
カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの通信に$sqrtk$ギャップがあることが知られている。
論文 参考訳(メタデータ) (2023-11-01T07:42:13Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳(メタデータ) (2023-10-23T04:07:26Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文 参考訳(メタデータ) (2022-11-14T13:09:12Z) - Minimax Rates for Robust Community Detection [19.229475414802213]
逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。
我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。
アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
論文 参考訳(メタデータ) (2022-07-25T04:45:16Z) - Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial
Corruptions [98.75618795470524]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-13T17:58:58Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳(メタデータ) (2021-10-25T02:53:24Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳(メタデータ) (2020-03-03T18:46:34Z) - Robust Stochastic Bandit Algorithms under Probabilistic Unbounded
Adversarial Attack [41.060507338755784]
本稿では,各ラウンドで敵が一定の確率で攻撃する攻撃モデルについて検討する。
そこで我々は, 中央値および探索支援UPBアルゴリズム(med-E-UCB)と中央値の$epsilon$-greedyアルゴリズム(med-$epsilon$-greedy)を提案する。
どちらのアルゴリズムも上記の攻撃モデルに対して確実に堅牢である。より具体的には、どちらのアルゴリズムも$mathcalO(log T)$ pseudo-regret (i.e.)を達成することを示す。
論文 参考訳(メタデータ) (2020-02-17T19:21:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。