論文の概要: Testing Juntas Optimally with Samples
- arxiv url: http://arxiv.org/abs/2505.04604v1
- Date: Wed, 07 May 2025 17:50:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-08 19:07:36.177183
- Title: Testing Juntas Optimally with Samples
- Title（参考訳）: ユンタをサンプルで最適にテストする
- Authors: Lorenzo Beretta, Nathaniel Harms, Caleb Koch,
- Abstract要約: これは、分布自由サンプルベースモデルにおけるブール関数の自然なクラスをテストするための最初の厳密な境界である。
我々の境界は特徴選択の問題にも当てはまり、ユンタテスターが関連する変数の集合を学ばなければならないことを示す。
- 参考スコア（独自算出の注目度）: 1.6112718683989882
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove tight upper and lower bounds of $\Theta\left(\tfrac{1}{\epsilon}\left( \sqrt{2^k \log\binom{n}{k} } + \log\binom{n}{k} \right)\right)$ on the number of samples required for distribution-free $k$-junta testing. This is the first tight bound for testing a natural class of Boolean functions in the distribution-free sample-based model. Our bounds also hold for the feature selection problem, showing that a junta tester must learn the set of relevant variables. For tolerant junta testing, we prove a sample lower bound of $\Omega(2^{(1-o(1)) k} + \log\binom{n}{k})$ showing that, unlike standard testing, there is no large gap between tolerant testing and learning.
- Abstract（参考訳）: 分布のない$k$-juntaテストに必要なサンプルの数に対して、$\Theta\left(\tfrac{1}{\epsilon}\left( \sqrt{2^k \log\binom{n}{k} } + \log\binom{n}{k} \right)\right)$の強い上限と下限を証明する。
これは、分布自由サンプルベースモデルにおけるブール関数の自然なクラスをテストするための最初の厳密な境界である。
我々の境界は特徴選択問題にも当てはまり、ユンタテスターが関連する変数の集合を学ばなければならないことを示す。
耐久ジャンタ試験では, 標準試験と異なり, 耐久試験と学習の間に大きなギャップはないことを示すために, サンプル値が$\Omega(2^{(1-o(1)) k} + \log\binom{n}{k})$ であることを証明する。
関連論文リスト
- Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning [10.903818216004703]
サブキューブ条件下での1,1n$の高次元分布の単調性試験について検討した。
本研究は,関数単調性テストのために開発された有向等尺不等式を用いて分布試験アルゴリズムを解析した最初のものである。
論文 参考訳（メタデータ） (2025-02-22T21:04:22Z) - Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。
このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。
信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
論文 参考訳（メタデータ） (2024-06-21T20:56:35Z) - GRASP: A Goodness-of-Fit Test for Classification Learning [8.122270502556374]
標準測度であるにもかかわらず、平均精度は、特徴ベクトル(Y|X$)が与えられたラベルの基本的な条件法則にモデルを適合させるのに失敗する。
我々のフレームワークは条件付き法則$Y|X$のパラメトリックな仮定を一切行わず、クエリを通してのみアクセス可能なブラックボックスオラクルモデルとして扱う。
論文 参考訳（メタデータ） (2022-09-05T17:18:43Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳（メタデータ） (2022-06-21T20:43:53Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - 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) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。