Metraipolis › archive › dc_871bcbf79e4e

Learning Nearest-Neighbor Maps from Adaptive Queries — arXiv:2608.07352

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.07352
License (as archived): CC0-1.0
Archived: 2026-10-23T15:11:04.397Z
SHA-256 of the archived text: 51a56d38bcd819dcf4970c6ca4fe1dafb94c7ee251f48070517c1e9b644b2bbf
Stable URL of this page: https://metraipolis.com/documento/dc_871bcbf79e4e

How to cite

Learning Nearest-Neighbor Maps from Adaptive Queries — arXiv:2608.07352 — arXiv (en), https://arxiv.org/abs/2608.07352 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_871bcbf79e4e (Metraipolis archive dc_871bcbf79e4e, sha256 51a56d38bcd819dcf4970c6ca4fe1dafb94c7ee251f48070517c1e9b644b2bbf)

BibTeX

@misc{dc871bcbf79e4e,
  title = {Learning Nearest-Neighbor Maps from Adaptive Queries — arXiv:2608.07352},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.07352},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_871bcbf79e4e; sha256 51a56d38bcd819dcf4970c6ca4fe1dafb94c7ee251f48070517c1e9b644b2bbf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07352. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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,\| \cdot\|)$ 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))$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2608.07352 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-23T15:08:55.961Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).