On Adaptive Distance Estimation

Yeshwanth Cherapanamjeri, Jelani Nelson

Abstract

This paper introduces a novel randomized data structure for Approximate Distance Estimation (ADE) that remains accurate even when queries are chosen adaptively by an adversary. By utilizing an ensemble of sketches and a median-based sampling technique, the authors achieve nearly optimal memory and query time while closing a major security loophole present in traditional dimensionality reduction methods.

The Challenge of Adaptive Queries

In numerous machine learning applications—such as nearest neighbor search or kernel regression—systems must estimate the distance between a query point $q$ and a large dataset $X = \{x_1, \dots, x_n\}$. Exact computation requires $O(nd)$ time, which is prohibitively slow for massive datasets. To accelerate computation, researchers typically rely on randomized linear sketching (e.g., the Johnson-Lindenstrauss lemma), which projects high-dimensional data into a much smaller space.

However, these standard methods suffer from a critical "Monte Carlo" flaw: they only guarantee correctness if the query $q$ is chosen independently of the random sketch. In modern adversarial settings, an attacker might choose a sequence of queries $q_1, q_2, \dots$ where each subsequent query depends on the answers provided to previous ones. This "adaptivity" can leak information about the internal random seed of the data structure, eventually allowing the adversary to craft a query that forces the system to output wildly incorrect distances.

Proposed Methodology

To counter this vulnerability, the authors propose a generic meta-algorithm that transforms non-adaptive data structures into robust, adaptive ones. The approach relies on three core components:

  1. Ensemble Sketching: Instead of creating one large sketch, the system constructs an ensemble of $l$ independent, smaller sketches (utilizing $p$-stable distributions for $\ell_p$ norms).
  2. Median-of-Means Sampling: When a query $q$ arrives, the data structure does not evaluate all $l$ sketches. Instead, it randomly samples a small subset of $r \approx \log n$ sketches, computes distance estimates from each, and returns the median of those estimates.
Algorithm 2: Process Query
  1. The "Rep" Property: The core theoretical contribution is proving that if the system maintains enough independent sketches ($l \approx d$), then for any possible query in the entire space, the vast majority of those sketches will be accurate. Because the majority are "good," a random sample combined with a median operation will almost certainly yield a correct answer, regardless of how the adversary attempts to manipulate the system.

Experimental Setup and Key Results

Because the primary contributions are theoretical, the authors evaluate their method using synthetic adversarial attacks rather than standard large-scale benchmarks. They designed a specific attack on a small database and used a sequence of random inputs to probe a standard Johnson-Lindenstrauss sketch, accumulating enough information to construct a single adaptive query that breaks the sketch's accuracy.

Key Findings: * Empirical Robustness: In their experiments, a standard sketch fails (reported distances drop drastically) after only a few hundred adaptive queries. In contrast, the proposed adaptive method maintains stable, accurate distance estimates throughout the entire adversarial test. * Query Speedup: The query time is $\tilde{O}(\epsilon^{-2}(n + d))$, which is significantly faster than the naive linear scan $O(nd)$ when $n$ and $d$ are large. * Near-Optimal Space: The memory consumption is $\tilde{O}((n + d)d/\epsilon^2)$. The authors prove this is nearly optimal for any data structure providing these robust guarantees.

Limitations and Future Directions

While highly robust, the method has limitations regarding pre-processing. The main bottleneck is the time required to build the data structure, which scales as $O(nd^2/\epsilon^2)$. Although the authors suggest this can be improved using fast rectangular matrix multiplication, it remains superlinear and potentially expensive for massive datasets.

A major open question is whether it is possible to achieve these same adaptive guarantees with a data structure that can be built in nearly linear time ($O(nd)$). Additionally, while this work focuses on $\ell_p$ norms, exploring how this ensemble approach translates to other machine learning primitives—such as inner products or frequency estimation—remains a promising direction for future research.

Summary updated

Abstract

We provide a static data structure for distance estimation which supports {\it adaptive} queries. Concretely, given a dataset $X = \{x_i\}_{i = 1}^n$ of $n$ points in $\mathbb{R}^d$ and $0 < p \leq 2$, we construct a randomized data structure with low memory consumption and query time which, when later given any query point $q \in \mathbb{R}^d$, outputs a $(1+\varepsilon)$-approximation of $\|q - x_i\|_p$ with high probability for all $i\in[n]$. The main novelty is our data structure's correctness guarantee holds even when the sequence of queries can be chosen adaptively: an adversary is allowed to choose the $j$th query point $q_j$ in a way that depends on the answers reported by the data structure for $q_1,\ldots,q_{j-1}$. Previous randomized Monte Carlo methods do not provide error guarantees in the setting of adaptively chosen queries. Our memory consumption is $\tilde O(nd/\varepsilon^2)$, slightly more than the $O(nd)$ required to store $X$ in memory explicitly, but with the benefit that our time to answer queries is only $\tilde O(\varepsilon^{-2}(n + d))$, much faster than the naive $\Theta(nd)$ time obtained from a linear scan in the case of $n$ and $d$ very large. Here $\tilde O$ hides $\log(nd/\varepsilon)$ factors. We discuss applications to nearest neighbor search and nonparametric estimation. Our method is simple and likely to applicable to other domains: we describe a generic approach for transforming randomized Monte Carlo data structures which do not support adaptive queries to ones that do, and show that for the problem at hand it can be applied to standard nonadaptive solutions to $\ell_p$ norm estimation with negligible overhead in query time and a factor $d$ overhead in memory.
BibTeX
@inproceedings{cherapanamjeri2020adaptive,
  author = {Yeshwanth Cherapanamjeri and Jelani Nelson},
  title = {{On Adaptive Distance Estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=6KDq-LBSpuB},
}
Figure