5
$\begingroup$

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

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

1 Answer 1

2
+25
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$
    – fedja
    Nov 22, 2023 at 19:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.