Find an approximate argmax using only approximate max queries

Question

Consider the following problem.

There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query is specified by a set $S \subseteq \{1,\cdots,n\}$ and the corresponding answer is $\max_{i \in S} v_i$. The goal is to use as few queries as possible.

This problem is easy: We can use binary search to find the argmax with $O(\log n)$ queries. i.e. Build a complete binary tree with $n$ leaves corresponding to indices. Start at the root and walk down to a leaf as follows. At each node, query the maximum value in the right and left subtrees and then move to the child on the side with the larger answer. Upon reaching a leaf, output its index.

The following noisy version of this problem has come up in my research.

There are $n$ unknown values $v_1, \cdots, v_n$. These can be accessed with queries in which a set $S \subseteq \{1, \cdots, n\}$ is specified and a sample from $\mathcal{N}(\max_{i \in S} v_i,1)$ is returned. The goal is to identify $i_* \in \{1, \cdots, n\}$ such that $\mathbb{E}[v_{i_*}] \geq \max_i v_i - 1$ using as few queries as possible. (The expectation is over the choice of $i_*$, which depends on both the coins of the algorithm and the noisy query answers.)

Suppose we try to solve this using the same binary search strategy as before (but with noisy answers). It is reasonably easy to show that this achieves $\mathbb{E}[v_{i_*}] \geq \max_i v_i - O(\log n)$ and that this is tight in the worst case. We can reduce the error to the desired $1$ by repeating each query $O(\log^2 n)$ times and using the average (which drives down the variance). This gives an algorithm using $O(\log^3 n)$ queries.

Is there a better algorithm? I conjecture that $O(\log^2 n)$ queries suffice. And I believe I can prove a $\Omega(\log^2 n)$ lower bound. Also, the problem becomes easy -- i.e. $\tilde{O}(\log n)$ queries via binary search -- under the promise that there is a $\Omega(1)$ gap between the largest value and the second-largest value. If it helps, you can assume all the values are between $0$ and $O(\log n)$.

Answer 1

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$. Consider drawing the input by picking a permutation of these values uniformly at random.

The idea should be that if we fix the indices of all values except for values $B$ and $\frac{n-1}{n}B$, then we should be able to show the difference in the algorithm's probability of picking one versus the other is very small: The variation distance between the results of the algorithms' queries is very small given the 50-50 distribution on assignments of these values to the two available indices and the results of any sequence of queries.

This argument holds for each pair of adjacent values, so we get a chain of constraints on the probability the algorithm picks the highest, second-highest, ... values. This gives an upper bound on the expected value of the algorithm, so we set that upper bound to $B-1$ and see what the number of queries has to be.

I couldn't improve on $\log n$ with the above approach yet, but I think you might get $(\log n)^2$ if you can leverage the fact that queries can't help with multiple steps at once. I.e. if a query changes when we move the highest value to a different index, then one of those times it it doesn't change when we move any other value to a different index.

Differential privacy might be helpful for one of these steps, e.g. if we only think about the case where we swap the location of the two highest values, the "sensitivity" of this query is just $\frac{B}{n}$ and then advanced composition might be helpful.

Sorry this is half-baked, but hope it can be useful!