# Recover unknown vector through shifted argmax queries

$$\DeclareMathOperator*{\argmax}{arg\,max}$$ 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) := \argmax_{1 \le i \le n}{x_i + v_i}$$ where $$v \in \mathbb{R}^n$$ is an arbitrary additive shift. In case of multiple occurrences of the maximum value, the smallest $$i$$ is returned.

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$$.

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.

• Since "argmax" is not a standard mathematics concept (it is a computer language concept), can we formulate this otherwise? Nov 15, 2023 at 14:38
• looks like $\mathsf{argmax}(x) = \arg\max_i |x_i|$ is the intended interpretation?
– Mark
Nov 15, 2023 at 22:22
• It's $\arg \max_i x_i$, without the absolute value Nov 15, 2023 at 23:38
• Cross-posted cs.stackexchange.com/questions/162966/… Nov 16, 2023 at 0:44

The following argument suggests that the factor $$O(n)$$ cannot be improved. Suppose for a contradiction that $$x\in\{0,1\}^n$$ and after queries with $$v_1,\dots,v_{n-1}\in\mathbb R^n$$ we determined that $$x=(1,\dots,1)$$.
Pick an index $$j\in\{1,\dots,n\}$$ which was an answer for no queries and let $$x'\in\{0,1\}^n$$ be the same as $$x$$ with the only difference that the $$j$$th component of $$x'$$ is $$0$$. Then for $$x'$$ we obtain the same query answers as for $$x$$, so we cannot hope to distinguish $$x$$ from $$x'$$, a contradiction.
• Due to the discrete nature of the problem, one would really expect $\frac{n}{\log n}\color{red}{\log\frac n\varepsilon}$ rather than just $\log\frac 1\varepsilon$, which is in full agreement with your observation but still leaves a lot of room for possible improvement when $\varepsilon$ is much smaller than $1/n$. Nov 22, 2023 at 19:10