Optimal Clustering with Noisy Queries via Multi-Armed Bandit
- URL: http://arxiv.org/abs/2207.05376v1
- Date: Tue, 12 Jul 2022 08:17:29 GMT
- Title: Optimal Clustering with Noisy Queries via Multi-Armed Bandit
- Authors: Jinghui Xia, Zengfeng Huang
- Abstract summary: Motivated by many applications, we study clustering with a faulty oracle.
We propose a new time algorithm with $O(fracn)delta2 + textpoly(k,frac1delta, log n)$ queries.
Our main ingredient is an interesting connection between our problem and multi-armed bandit.
- Score: 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.
Related papers
- On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
This paper considers the optimization problem of the form $min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, where $f(cdot)$ satisfies the Polyak--Lojasiewicz (PL) condition with parameter $mu$ and $f_i(cdot)_i=1n$ is $L$-mean-squared smooth.
arXiv Detail & Related papers (2024-02-04T17:14:53Z) - Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
We show that exact equilibria can be computed efficiently from $O(fracln Kepsilon)$ instead of $O(fracln Kepsilon2)$ queries.
We introduce a new technique for lower bounds, which allows us to obtain lower bounds of order $tildeOmega(frac1Kepsilon)$ for any $epsilon leq 1 / (cK4)$.
arXiv Detail & Related papers (2023-04-25T12:42:59Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
We consider the problem of latent bandits with cluster structure where there are multiple users, each with an associated multi-armed bandit problem.
We propose LATTICE which allows exploitation of the latent cluster structure to provide the minimax optimal regret of $widetildeO(sqrt(mathsfM+mathsfN)mathsfT.
arXiv Detail & Related papers (2023-01-17T17:49:04Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $s, s'$.
Also, we present a quantum algorithm consuming $fracn2+O(sqrtn)$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+Omega(1)$ queries.
arXiv Detail & Related papers (2022-11-19T11:14:19Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $Csubseteq0,1n$.
The goal is to identify $x$ using as few queries to the oracle as possible.
We develop a quantum query algorithm for this problem with query complexity $Oleft(sqrtfracnlog M log(n/log M)+1right)$, where $M$ is the size of $C$.
arXiv Detail & Related papers (2021-09-08T19:48:27Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
We propose an elegant theoretical model for studying clustering with a faulty oracle.
It was left as an open question whether one can obtain a query-optimal, time-efficient algorithm for the general case of $k$ clusters.
We provide a time-efficient algorithm with nearly-optimal query complexity (up to a factor of $O(log2 n)$) for all constant $k$ and any $delta$ in the regime when information-theoretic recovery is possible.
arXiv Detail & Related papers (2021-06-18T22:20:12Z) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
We give an algorithm for this task that achieves an expected $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$.
On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$ holds not only in expectation but always.
arXiv Detail & Related papers (2020-12-16T17:58:45Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020)
The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
arXiv Detail & Related papers (2020-02-17T10:53:50Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model.
Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.