3
$\begingroup$

I am interested in finding an efficient algorithm for the following problem:

Let $x \in [0,1]^n$ be some vector, with $x_n = 1$. We want to recover $x$, solely by asking queries of the form $\texttt{argmax}(x + v)$ where $v \in \mathbb{R}^n$ is an arbitrary additive shift.

A simple algorithm is to do binary search over each component of $x$ one-by-one. This requires $O(n \log 1/\epsilon)$ queries to recover $x$ up to precision $\epsilon$.

A more involved approach is to first sort $x$ (which can be done with $n$ queries) and then perform $n$ binary searches to find the gaps between adjacent elements. I believe this should give something like $O(n \log 1/(n\epsilon))$.

Is it possible to do better? My intuition is that it might be, as every query $i \gets \texttt{argmax}(x + v)$ gives us $\log_2 n$ bits of information. So in principle we could hope for an algorithm that uses $O(\frac{n \log 1/\epsilon}{\log_2 n})$ queries.

$\endgroup$
2
  • 2
    $\begingroup$ One strategy that comes to mind: At each step, let $\mathcal{S}$ denote the set of all $x \in \mathbb{R}^n$ that are consistent with the responses to prior queries ($\mathcal{S}$ is the feasible region of a system of difference equations); sample $s$ randomly from $\mathcal{S}$; and let $v=-s$ and make a query with $v$. Heuristically, I suspect that the response to this query might be approximately uniformly distributed on $\{1,2,\dots,n\}$, hence convey $\lg n$ bits of information at each step. I have no bound or proof for worst-case number of queries. $\endgroup$
    – D.W.
    Commented Nov 15, 2023 at 19:55
  • 1
    $\begingroup$ Cross-posted mathoverflow.net/questions/458321/… $\endgroup$ Commented Nov 16, 2023 at 0:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.