論文の概要: Optimal Clustering with Noisy Queries via Multi-Armed Bandit
- arxiv url: http://arxiv.org/abs/2207.05376v1
- Date: Tue, 12 Jul 2022 08:17:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-13 14:28:04.136625
- Title: Optimal Clustering with Noisy Queries via Multi-Armed Bandit
- Title（参考訳）: マルチアームバンディットによるノイズクエリによる最適クラスタリング
- Authors: Jinghui Xia, Zengfeng Huang
- Abstract要約: 多くのアプリケーションによって動機づけられた私たちは、欠陥のあるオラクルでクラスタリングを研究します。
我々は,$O(fracn)delta2 + textpoly(k,frac1delta, log n)$クエリを用いた新しい時間アルゴリズムを提案する。
我々の主な要素は、我々の問題と多腕バンディットの興味深い関係である。
- 参考スコア（独自算出の注目度）: 19.052525950282234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by many applications, we study clustering with a faulty oracle. In
this problem, there are $n$ items belonging to $k$ unknown clusters, and the
algorithm is allowed to ask the oracle whether two items belong to the same
cluster or not. However, the answer from the oracle is correct only with
probability $\frac{1}{2}+\frac{\delta}{2}$. The goal is to recover the hidden
clusters with minimum number of noisy queries. Previous works have shown that
the problem can be solved with $O(\frac{nk\log n}{\delta^2} +
\text{poly}(k,\frac{1}{\delta}, \log n))$ queries, while
$\Omega(\frac{nk}{\delta^2})$ queries is known to be necessary. So, for any
values of $k$ and $\delta$, there is still a non-trivial gap between upper and
lower bounds. In this work, we obtain the first matching upper and lower bounds
for a wide range of parameters. In particular, a new polynomial time algorithm
with $O(\frac{n(k+\log n)}{\delta^2} + \text{poly}(k,\frac{1}{\delta}, \log
n))$ queries is proposed. Moreover, we prove a new lower bound of
$\Omega(\frac{n\log n}{\delta^2})$, which, combined with the existing
$\Omega(\frac{nk}{\delta^2})$ bound, matches our upper bound up to an additive
$\text{poly}(k,\frac{1}{\delta},\log n)$ term. To obtain the new results, our
main ingredient is an interesting connection between our problem and
multi-armed bandit, which might provide useful insights for other similar
problems.
- Abstract（参考訳）: 多くのアプリケーションによって動機付けられ、欠陥のあるオラクルでクラスタリングを研究する。
この問題では、$k$未知のクラスタに属する$n$アイテムが存在し、アルゴリズムは、2つのアイテムが同じクラスタに属するか否かをオラクルに問うことができる。
しかし、オラクルからの答えは、確率$\frac{1}{2}+\frac{\delta}{2}$でのみ正しい。
目標は、最小限のノイズクエリ数で隠れたクラスタをリカバリすることだ。
以前の研究では、この問題は$O(\frac{nk\log n}{\delta^2} + \text{poly}(k,\frac{1}{\delta}, \log n))$クエリで解決できることが示されており、$\Omega(\frac{nk}{\delta^2})$クエリは必須であることが知られている。
したがって、$k$ と $\delta$ の任意の値に対して、上界と下界の間には非自明なギャップがある。
本研究では, パラメータの幅が広い場合, 上界と下界の整合性について検討する。
特に、$O(\frac{n(k+\log n)}{\delta^2} + \text{poly}(k,\frac{1}{\delta}, \log n))$クエリを持つ新しい多項式時間アルゴリズムを提案する。
さらに、$\Omega(\frac{n\log n}{\delta^2})$という新しい下界を証明し、既存の$\Omega(\frac{nk}{\delta^2})$boundと組み合わせると、上界は加法$\text{poly}(k,\frac{1}{\delta},\log n)$ termに一致する。
新たな結果を得るためには,本問題とマルチアームバンディットとの間には興味深い関連性があり,他の類似した問題に対して有用な洞察を与える可能性がある。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文 参考訳（メタデータ） (2024-02-04T17:14:53Z) - Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。
我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
論文 参考訳（メタデータ） (2023-04-25T12:42:59Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳（メタデータ） (2022-11-19T11:14:19Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。
目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。
この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
論文 参考訳（メタデータ） (2021-09-08T19:48:27Z) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。