Papers › Bandit-Based Monte Carlo Optimization for Nearest Neighbors
Bandit-Based Monte Carlo Optimization for Nearest Neighbors
Vivek Bagaria, Tavor Z. Baharav, Govinda M. Kamath, David N. Tse
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((n+d)log² (nd/δ)) for error probability δ, 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.
In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
For agents, on Syntology's MCP service (how to connect):
get_citation_path(paper_1="1805.08321", paper_2="…")with another paper's arXiv id or titleget_concepts_for_paper(arxiv_id="1805.08321")
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections