10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about a binary search that at every level makes O(log n) query pairs (one for max of left hand side, one for max of right hand side) and records who wins. Then, after O(log n) rounds the algorithm proceeds recursively on the side that "won" the most times. A brief calculation in my head seemed to indicate that this worked with probabilty $1-1/n^c$ in the setting where one input is $2$ and all others are $0$ ... i might be way off though. $\endgroup$ – daniello Oct 18 '17 at 10:28
  • $\begingroup$ @daniello That works when there is a gap between the largest and second-largest values. The general case seems to be more difficult though. $\endgroup$ – Thomas Oct 18 '17 at 20:45
  • $\begingroup$ note to self: read the entire question before commenting $\endgroup$ – daniello Oct 19 '17 at 14:24
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I haven't actually thought about lower bounds very much, since I'm hoping for an upper bound. :) $\Omega(\log n)$ holds even in the noiseless case. I think we should be able to prove a $\Omega(\log^2 n)$ lower bound. $\endgroup$ – Thomas Oct 10 '17 at 14:49
  • $\begingroup$ OK. I have a sketch of a $\Omega(\log^2 n)$ lower bound, but it's a bit complicated. $\endgroup$ – Thomas Oct 10 '17 at 15:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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