論文の概要: On Detecting Some Defective Items in Group Testing
- arxiv url: http://arxiv.org/abs/2307.04822v1
- Date: Tue, 27 Jun 2023 10:12:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-16 04:05:54.779670
- Title: On Detecting Some Defective Items in Group Testing
- Title（参考訳）: グループテストにおける欠陥項目の検出について
- Authors: Nader H. Bshouty, Catherine A. Haddad-Zaknoon
- Abstract要約: グループテストは、合計$n$要素のうち最大$d$欠陥項目を特定するためのアプローチである。
本研究では, $ellleq d$ 欠陥項目のサブセットを特定する問題に焦点をあてる。
- 参考スコア（独自算出の注目度）: 0.11421942894219898
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Group testing is an approach aimed at identifying up to $d$ defective items
among a total of $n$ elements. This is accomplished by examining subsets to
determine if at least one defective item is present. In our study, we focus on
the problem of identifying a subset of $\ell\leq d$ defective items. We develop
upper and lower bounds on the number of tests required to detect $\ell$
defective items in both the adaptive and non-adaptive settings while
considering scenarios where no prior knowledge of $d$ is available, and
situations where an estimate of $d$ or at least some non-trivial upper bound on
$d$ is available.
When no prior knowledge on $d$ is available, we prove a lower bound of $
\Omega(\frac{\ell \log^2n}{\log \ell +\log\log n})$ tests in the randomized
non-adaptive settings and an upper bound of $O(\ell \log^2 n)$ for the same
settings. Furthermore, we demonstrate that any non-adaptive deterministic
algorithm must ask $\Theta(n)$ tests, signifying a fundamental limitation in
this scenario. For adaptive algorithms, we establish tight bounds in different
scenarios. In the deterministic case, we prove a tight bound of
$\Theta(\ell\log{(n/\ell)})$. Moreover, in the randomized settings, we derive a
tight bound of $\Theta(\ell\log{(n/d)})$.
When $d$, or at least some non-trivial estimate of $d$, is known, we prove a
tight bound of $\Theta(d\log (n/d))$ for the deterministic non-adaptive
settings, and $\Theta(\ell\log(n/d))$ for the randomized non-adaptive settings.
In the adaptive case, we present an upper bound of $O(\ell \log (n/\ell))$ for
the deterministic settings, and a lower bound of $\Omega(\ell\log(n/d)+\log
n)$. Additionally, we establish a tight bound of $\Theta(\ell \log(n/d))$ for
the randomized adaptive settings.
- Abstract（参考訳）: グループテストは、合計$n$要素の中から最大$d$欠陥アイテムを特定することを目的としたアプローチである。
これは、少なくとも1つの欠陥アイテムが存在するかどうかを決定するためにサブセットを調べることによって達成される。
本研究では,$\ell\leq d$ 欠陥項目のサブセットを特定する問題に焦点を当てた。
我々は,d$の事前知識が得られないシナリオや,少なくとも$d$の非自明な上限が利用できる状況を考慮して,適応的設定と非適応的設定の両方において,$\ell$欠陥項目を検出するために必要なテスト数の上限を上下に設定する。
d$に関する事前の知識が得られない場合、ランダム化された非適応設定における$ \omega(\frac{\ell \log^2n}{\log \ell +\log\log n})$のテストと、同じ設定で$o(\ell \log^2n)$の上限を証明します。
さらに、任意の非適応決定論的アルゴリズムが$\Theta(n)$テストを求めなければならず、このシナリオの基本的な制限を示す。
適応アルゴリズムの場合、異なるシナリオで厳密な境界を確立する。
決定論的な場合、$\Theta(\ell\log{(n/\ell)})$の厳密な境界を証明する。
さらに、ランダム化された設定では、$\Theta(\ell\log{(n/d)})$の厳密な境界を導出する。
d$、または少なくとも$d$の非自明な見積もりが知られているとき、決定論的非適応的設定に対して$\Theta(d\log (n/d))$、ランダム化された非適応的設定に対して$\Theta(\ell\log(n/d))$の厳密な境界を証明する。
アダプティブの場合、決定論的設定に対して$O(\ell \log (n/\ell))$の上界、および$\Omega(\ell\log(n/d)+\log n)$の下界を示す。
さらに、ランダム化適応設定に対して$\Theta(\ell \log(n/d))$の厳密な境界を確立する。
関連論文リスト
- Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。
この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
論文 参考訳（メタデータ） (2023-02-07T10:39:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Breaking The Dimension Dependence in Sparse Distribution Estimation
under Communication Constraints [18.03695167610009]
サンプルサイズ$n$が最低しきい値$n*(s, d, b)$を超えると、$Oleft( fracsn2bright)$の$ell$推定誤差を達成できることを示す。
対話的な設定のために,新しい木に基づく推定手法を提案し,次元自由収束を実現するために必要な最小サンプルサイズを,さらに$n*(s, d, b)$に縮めることを示した。
論文 参考訳（メタデータ） (2021-06-16T07:52:14Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。