論文の概要: On the Sample Complexity of Robust Binary Hypothesis Testing

• arxiv url: http://arxiv.org/abs/2605.24741v1
• Date: Sat, 23 May 2026 21:29:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:18.357843
• Title: On the Sample Complexity of Robust Binary Hypothesis Testing
• Title（参考訳）: ロバスト二項仮説テストの複雑さについて
• Authors: Shankar Vallinayagam, Ankit Pensia, Varun Jog,
• Abstract要約: 3つの標準モデル: $varepsilon$-additive (Huber), $varepsilon$-subtractive, $varepsilon$-total (TV)。 減数的汚染については, 汚染分布が最小限であることを示すとともに, 明示的な公式を提示する。 汚染モデルの適応バージョンに結果を拡張します。
• 参考スコア（独自算出の注目度）: 12.19213920217024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the sample complexity of robust binary hypothesis testing under three standard contamination models: $\varepsilon$-additive (Huber), $\varepsilon$-subtractive, and $\varepsilon$-total variation (TV), denoted by $n^*_{\mathrm{Hub}}(\varepsilon)$, $n^*_{\mathrm{Sub}}(\varepsilon)$, and $n^*_{\mathrm{TV}}(\varepsilon)$, respectively. For subtractive contamination, we show that least favourable distributions exist and provide explicit formulas for the same, bringing this model in line with the classical Huber and TV models. Next we show that in all three models, sample complexity may be highly unstable in the contamination parameter $\varepsilon$, increasing by polynomial factors even for $o(\varepsilon)$ perturbations. Similarly, there may be polynomial factor gaps between the sample complexities when $\varepsilon$ is known exactly versus when it is known up to $o(\varepsilon)$ error. Despite the instability of the sample complexity in all models, we show that the sample complexities across models are comparable up to constant-factor rescaling of $\varepsilon$. Specifically, for any fixed $δ_0>0$, the following hold for all distributions $p$ and $q$: (i) $n^*_{\mathrm{Hub}}(\varepsilon) \lesssim n^*_{\mathrm{TV}}(\varepsilon) \lesssim n^*_{\mathrm{Hub}}(2\varepsilon)$, (ii) $n^*_{\mathrm{Sub}}(\varepsilon) \lesssim n^*_{\mathrm{TV}}(\varepsilon) \lesssim n^*_{\mathrm{Sub}}((2+δ_0)\varepsilon)$, and (iii) $n^*_{\mathrm{Sub}}(\varepsilon) \lesssim n^*_{\mathrm{Hub}}(\varepsilon) \lesssim n^*_{\mathrm{Sub}}((1+δ_0)\varepsilon)$, and the scaling constants are tight. Finally, we extend our results to adaptive versions of the contamination models.
• Abstract（参考訳）: 3つの標準汚染モデルにおいて、ロバストな二項仮説テストのサンプル複雑性について検討する: $\varepsilon$-additive (Huber), $\varepsilon$-subtractive, $\varepsilon$-total variation (TV)、それぞれ$n^*_{\mathrm{Hub}}(\varepsilon)$, $n^*_{\mathrm{Sub}}(\varepsilon)$, $n^*_{\mathrm{TV}}(\varepsilon)$。 減算的汚染に対して、最も好ましくない分布が存在し、同じ公式を明示することを示し、このモデルを古典的なフーバーやテレビモデルと一致させる。 次に、3つのモデルすべてにおいて、サンプルの複雑さは汚染パラメータ$\varepsilon$において非常に不安定であり、$o(\varepsilon)$摂動の多項式因子によって増加する可能性があることを示す。 同様に、サンプル複体の間には$\varepsilon$が正確に、$o(\varepsilon)$エラーである場合にも多項式係数ギャップがある。 すべてのモデルにおけるサンプルの複雑さの不安定さにもかかわらず、モデル間のサンプルの複雑さは$\varepsilon$の定数要素再スケーリングに匹敵することを示した。 具体的には、任意の固定された$δ_0>0$に対して、すべての分布に対して以下のホールドが$p$と$q$である。 (i) $n^*_{\mathrm{Hub}}(\varepsilon) \lesssim n^*_{\mathrm{TV}}(\varepsilon) \lesssim n^*_{\mathrm{Hub}}(2\varepsilon)$ (ii) $n^*_{\mathrm{Sub}}(\varepsilon) \lesssim n^*_{\mathrm{TV}}(\varepsilon) \lesssim n^*_{\mathrm{Sub}}((2+δ_0)\varepsilon)$ (iii) $n^*_{\mathrm{Sub}}(\varepsilon) \lesssim n^*_{\mathrm{Hub}}(\varepsilon) \lesssim n^*_{\mathrm{Sub}}((1+δ_0)\varepsilon)$。 最後に, 汚染モデルの適応バージョンに結果を拡張した。

関連論文リスト

• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• The Price of Tolerance in Distribution Testing [31.10049510641336]
  サンプルの複雑さは [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2 であることが示され、この2つの既知事例の間に円滑なトレードオフをもたらす。 また、p$ と$q$ の両方が未知である寛容同値検定の問題についても同様の特徴を与える。
  論文  参考訳（メタデータ） (2021-06-25T03:59:42Z)
• Mathematical comparison of classical and quantum mechanisms in optimization under local differential privacy [0.0]
  我々は、$mathrmEC_n(varepsilon)not=mathrmCQ_n(varepsilon)$ for every $nge3$を示し、$mathrmEC_n(varepsilon)$と$mathrmCQ_n(varepsilon)$の差をある方法で見積もる。
  論文  参考訳（メタデータ） (2020-11-19T17:05:11Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)

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

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