Adversarially Robust Approximate Furthest Neighbor

We work in the adaptive query model, where one is given a point set $P \subset \mathbb{R}^d$ and seeks to construct a data structure that can answer correctly and efficiently a sequence of adaptive queries. In this model, an adversary observes the answers returned by the data structure to previous queries $q_1, \ldots, q_{i-1}$ and, based on this information, chooses the next query point $q_i$. This setting captures strong forms of adaptivity that naturally arise in modern machine learning pipelines, and rules out many classical randomized techniques that assume oblivious queries. Our focus is the problem of furthest neighbor search in this adaptive setting, a fundamental problem in several learning tasks, including diversity maximization, outlier and anomaly detection, adversarial example generation, and more. We present the first adversarially robust data structure for $c$-approximate furthest neighbor queries that achieves query time $\tilde{O}(n^{1/c^2} + d)$. This matches the query time of the seminal result by Indyk [SODA'03] for $c$-approximate furthest neighbor in the oblivious setting, and significantly improves upon the $\tilde{O}(n + d)$ query time achieved by using the adaptive distance estimation framework of Cherapanamjeri and Nelson [NeurIPS'20].