Sharp Noisy Binary Search with Monotonic Probabilities

• URL: http://arxiv.org/abs/2311.00840v1
• Date: Wed, 1 Nov 2023 20:45:13 GMT
• Title: Sharp Noisy Binary Search with Monotonic Probabilities
• Authors: Lucas Gretta, Eric Price
• Abstract summary: We revisit the noisy binary search model of Karp and Kleinberg. We produce an algorithm that succeeds with probability $1-delta$ from [ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta) right.
• Score: 5.563988395126509
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the noisy binary search model of Karp and Kleinberg, in which we have $n$ coins with unknown probabilities $p_i$ that we can flip. The coins are sorted by increasing $p_i$, and we would like to find where the probability crosses (to within $\varepsilon$) of a target value $\tau$. This generalized the fixed-noise model of Burnashev and Zigangirov , in which $p_i = \frac{1}{2} \pm \varepsilon$, to a setting where coins near the target may be indistinguishable from it. Karp and Kleinberg showed that $\Theta(\frac{1}{\varepsilon^2} \log n)$ samples are necessary and sufficient for this task. We produce a practical algorithm by solving two theoretical challenges: high-probability behavior and sharp constants. We give an algorithm that succeeds with probability $1-\delta$ from \[ \frac{1}{C_{\tau, \varepsilon}} \cdot \left(\lg n + O(\log^{2/3} n \log^{1/3} \frac{1}{\delta} + \log \frac{1}{\delta})\right) \] samples, where $C_{\tau, \varepsilon}$ is the optimal such constant achievable. For $\delta > n^{-o(1)}$ this is within $1 + o(1)$ of optimal, and for $\delta \ll 1$ it is the first bound within constant factors of optimal.

Related papers

• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
  We consider the problem $(mathrmP)$ of fitting $n$ standard Gaussian random vectors in $mathbbRd$ to the boundary of a centered ellipsoid, as $n, d to infty$. This problem is conjectured to have a sharp feasibility transition: for any $varepsilon > 0$, if $n leq (1 - varepsilon) d2 / 4$ then $(mathrmP)$ has a solution with high probability.
  arXiv  Detail & Related papers  (2023-07-03T17:46:23Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  We study pure exploration with infinitely many bandit arms generated i.i.d. from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability $1-delta$, within $varepsilon$ of being among the top $eta$-fraction of arms.
  arXiv  Detail & Related papers  (2023-06-03T04:00:47Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
  We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. We prove that $omega(log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states.
  arXiv  Detail & Related papers  (2022-09-29T03:34:03Z)
• Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
  A stream of integers in $[N]:=1,cdots,N$ is received from a sensor. The goal is to approximate the $n$ points received so far in $P$ by a single frequency. We prove that emphevery set $P$ of $n$ has a weighted subset $Ssubseteq P$.
  arXiv  Detail & Related papers  (2022-03-06T17:07:56Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  We give an algorithm for identifying a $k$-mixture using samples of $m=2k$ iid binary random variables. It suffices to know the moments to additive accuracy $w_mincdotzetaO(k)$.
  arXiv  Detail & Related papers  (2020-07-16T04:23:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

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.