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

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Clustering with Non-adaptive Subset Queries [16.662507957069813]
  Given a query $S subset U$, $|S|=2$, the oracle returns yes if the points are in the same cluster and no otherwise. For adaptive algorithms with pair-wise queries, the number of required queries is known to be $Theta(nk)$. Non-adaptive schemes require $Omega(n2)$ queries, which matches the trivial $O(n2)$ upper bound attained by querying every pair of points.
  arXiv  Detail & Related papers  (2024-09-17T05:56:07Z)
• 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)
• 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)
• 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.