論文の概要: 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}'$ のアルゴリズムの振る舞いによって近似することができるか?
最初の結果は、すべての妥当なノイズモデルの下で、統計クエリアルゴリズムの幅広いクラスが実際にそうであることを示している。
次に、付加雑音の特定の場合において、この等価性はすべてのアルゴリズムに対して成立することを示す。
最後に、すべてのアルゴリズムと妥当なノイズモデルに対して、このステートメントを最大限の汎用性で証明するアプローチを図示する。
関連論文リスト
- Adaptive and oblivious statistical adversaries are equivalent [18.385321286452747]
あらゆる種類の汚職に対して, サンプル適応的, サンプル公開的敵は, サンプルサイズに匹敵する因子に富んでいることを示す。
対応するサンプル適応逆数が入力を破損した場合に同じ課題を解くアルゴリズムが$A'$であることを示す。
論文 参考訳（メタデータ） (2024-10-17T13:42:56Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。
提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
論文 参考訳（メタデータ） (2024-03-31T02:03:35Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳（メタデータ） (2023-10-23T04:07:26Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。