Learning Nearest-Neighbor Maps from Adaptive Queries

Abstract

We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set $H$ via a nearest-neighbor query oracle. Let $K\subset {\mathbb{R}}^d$ be a compact domain in a normed space $({\mathbb{R}}^d,\Vert \cdot \Vert )$ and let $H\subset K$ be a hidden set of $n$ points. Upon querying $q\in K$, the oracle returns some $h\in H$ with minimum distance from $q$. How many queries are required to exactly recover $H$? Previous work has studied this question in specific domains, namely the Boolean hypercube and the ${\ell }_2$-unit sphere. We generalize previous work and prove the tight worst-case query complexity bound of $\Theta (n\kappa )$, where $\kappa$ is the kissing number of the underlying norm. In the Euclidean norm, obtaining tight asymptotic bounds on $\kappa$ is a significant open question, although it is known that $\kappa =\exp (\Theta (d))$. Our second set of results shows that an exponential dependence on $d$ is required even in natural Euclidean domains: $\exp (\Omega (d))$ queries are needed in the ball, even when $n=2$, and $n\exp (\Omega (d))$ queries are needed in the cone. Lastly, we prove a sharper upper bound in the Euclidean sphere. Here, $d$ can be replaced by $\min (n,d)$ via a dimension reduction preprocessing step. This is a randomized version of a procedure due to Prabhu-Woodruff (ICML 2024) where we improve the query complexity from $O(nd)$ to $O(\min (n,d))$. This reveals a striking contrast between the sphere and the ball: when $n=O(1)$, the sphere admits an $O(1)$ query algorithm, whereas the ball requires $\exp (\Omega (d))$.