Bandit-Based Monte Carlo Optimization for Nearest Neighbors
Preprint
Abstract
The celebrated Monte Carlo method estimates an expensive-to-compute quantity by random sampling. Bandit-based Monte Carlo optimization is a general technique for computing the minimum of many such expensive-to-compute quantities by adaptive random sampling. The technique converts an optimization problem into a statistical estimation problem which is then solved via multi-armed bandits. We apply this technique to solve the problem of high-dimensional $k$-nearest neighbors, developing an algorithm which we prove is able to identify exact nearest neighbors with high probability. We show that under regularity assumptions on a dataset of $n$ points in $d$-dimensional space, the complexity of our algorithm scales logarithmically with the dimension of the data as $O\left((n+d)\log^2 \left(\frac{nd}{\delta}\right)\right)$ for error probability $\delta$, rather than linearly as in exact computation requiring $O(nd)$. We corroborate our theoretical results with numerical simulations, showing that our algorithm outperforms both exact computation and state-of-the-art algorithms such as kGraph, NGT, and LSH on real datasets.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Query Complexity of k-NN based Mode Estimation2021
- Randomized near-neighbor graphs, giant components and applications in data scienceJournal of Applied Probability, 2020
- Billion-Scale Similarity Search with GPUsIEEE Transactions on Big Data, 2019
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest NeighborsSIAM Journal on Computing, 2009
- Hessian eigenmaps: Locally linear embedding techniques for high-dimensional dataProceedings of the National Academy of Sciences, 2003
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal OptimizationDiscrete Event Dynamic Systems, 2000
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982