# Recover unknown vector through shifted argmax queries

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.

• 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.
– D.W.
Nov 15 at 19:55
• Cross-posted mathoverflow.net/questions/458321/… Nov 16 at 0:44