Fugu-MT 論文翻訳(概要): Testing Juntas Optimally with Samples

論文の概要: 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)
PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。我々はアルゴリズムをほぼ一致する下界で補完する。
論文参考訳（メタデータ） (2025-02-20T18:32:02Z)
Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
論文参考訳（メタデータ） (2024-06-21T20:56:35Z)
Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文参考訳（メタデータ） (2024-03-14T15:04:45Z)
On Learning for Ambiguous Chance Constrained Problems [2.7152798636894193]
この場合、$theta$のサンプルが$nu$から引き出されるサンプル問題により、元の問題は「適切に近似できる」ことが示される。また、この近似に関連するサンプルの複雑さ、すなわち$epsilon,delta>0$に対して$nu$から引かなければならないサンプルの数を導出する。
論文参考訳（メタデータ） (2023-12-31T17:25:43Z)
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文参考訳（メタデータ） (2023-09-20T21:41:59Z)
Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
論文参考訳（メタデータ） (2023-02-07T10:39:44Z)
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)
Nonasymptotic one-and two-sample tests in high dimension with unknown covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文参考訳（メタデータ） (2021-09-01T06:22:53Z)
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)
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文参考訳（メタデータ） (2020-12-16T17:58:45Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)
The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文参考訳（メタデータ） (2020-07-16T04:23:57Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)
Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文参考訳（メタデータ） (2020-02-18T16:14:55Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

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