論文の概要: Adaptive and oblivious statistical adversaries are equivalent

• arxiv url: http://arxiv.org/abs/2410.13548v1
• Date: Thu, 17 Oct 2024 13:42:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:17:53.735469
• Title: Adaptive and oblivious statistical adversaries are equivalent
• Title（参考訳）: 適応的および難解な統計的敵は等価である
• Authors: Guy Blanc, Gregory Valiant,
• Abstract要約: あらゆる種類の汚職に対して, サンプル適応的, サンプル公開的敵は, サンプルサイズに匹敵する因子に富んでいることを示す。 対応するサンプル適応逆数が入力を破損した場合に同じ課題を解くアルゴリズムが$A'$であることを示す。
• 参考スコア（独自算出の注目度）: 18.385321286452747
• License:
• Abstract: We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are \emph{equivalent} up to polynomial factors in the sample size. This resolves the main open question introduced by \cite{BLMT22} and further explored in \cite{CHLLN23}. Specifically, consider any algorithm $A$ that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm $A'$ that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of $A'$ is simple and maintains the computational efficiency of $A$: It requests a polynomially larger sample than $A$ uses and then runs $A$ on a uniformly random subsample. One of our main technical tools is a new structural result relating two distributions defined on sunflowers which may be of independent interest.
• Abstract（参考訳）: 我々は,相手がサンプルを破損した場合に,学習などの統計処理を行う能力に関する根本的な問題を解決する。 このような敵は、彼らができる汚職の種類と、サンプルに関する彼らの知識レベルによって特定される。 後者は、汚職を選択する際のサンプルの内容を知っているサンプル適応敵と、そうでないサンプル適応敵とを区別する。 あらゆる種類の汚職に対して、サンプル適応的およびサンプル公開的敵は、サンプルサイズの多項式因子まで \emph{equivalent} であることが証明される。 これは \cite{BLMT22} によってもたらされた主要な開質問を解決し、さらに \cite{CHLLN23} で探索する。 具体的には、サンプル公開の敵が入力を破損しても統計処理を解くアルゴリズムを$A$と考えてみよう。 対応するサンプル適応逆数が入力を破損した場合に同じ課題を解くアルゴリズムが$A'$であることを示す。 A'$の構成は単純で、$A$の計算効率を維持する:$A$よりも多項式的に大きいサンプルを要求し、一様ランダムなサブサンプル上で$A$を実行します。 我々の主要な技術ツールの1つは、独立した興味を持つかもしれないひまわりに定義された2つの分布に関する新しい構造結果である。

関連論文リスト

• Bias Mimicking: A Simple Sampling Approach for Bias Mitigation [57.17709477668213]
  本稿では,新しいクラス条件サンプリング手法であるBias Mimickingを紹介する。 Bias Mimickingは、4つのベンチマークで3%の精度でサンプリングの精度を向上する。
  論文  参考訳（メタデータ） (2022-09-30T17:33:00Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• On the power of adaptivity in statistical adversaries [18.973408992715203]
  統計的問題における対向雑音モデルに関する基礎的問題について検討する。 アルゴリズムの振舞い $mathcalA'$ は、アルゴリズムの $mathcalA'$ のアダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダクティブ・アダクショナル・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ(英語版)によって常によく近似することができるか?
  論文  参考訳（メタデータ） (2021-11-19T18:26:25Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Binary classification with ambiguous training data [69.50862982117127]
  教師付き学習では、ドメインの専門家でさえラベル付けが難しい曖昧な(A)サンプルに直面します。 この問題は、ラベルなしサンプルが必ずしも難しいサンプルではないため、半教師付き学習とは大きく異なる。
  論文  参考訳（メタデータ） (2020-11-05T00:53:58Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。