Learning Partition Trees for Nearest Neighbor Search

• URL: http://arxiv.org/abs/2607.09909v1
• Date: Fri, 10 Jul 2026 18:59:31 GMT
• Title: Learning Partition Trees for Nearest Neighbor Search
• Abstract summary: We study nearest neighbor search from the perspective of data-driven algorithm design.<n>We focus on the class of balanced halfspace trees.<n>We show that without distributional assumptions, finding the optimal balanced halfspace is NP-hard.
• Score: 5.425161484130288
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset $P \subset \mathbb{R}^d$ of size $n$ and sample access to a query distribution over $\mathbb{R}^d$, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving $o(nd)$ query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over $\mathbb{R}^d \times \mathbb{R}^d$ and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an $α$ fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree $\tilde{O}(1/\varepsilon^2)$ that cuts at most an $O(\sqrt{α+\varepsilon})$ fraction.

Related papers

• Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals [5.7652356955571085]
  Given i.i.d. labeled samples from an unknown distribution over $mathbbRd times pm 1$ whose marginal on $mathbbRd$ is Gaussian, the goal is to output a hypothesis from a target class $mathcalF$ whose 0-1 loss is within $$ of that of the best classifier in $mathcalF$.<n>Our algorithm runs in time $dO(K2 log (1/)/2) + (K/)O(K
  arXiv  Detail & Related papers  (2026-05-26T19:07:06Z)
• Reliable Learning of Halfspaces under Gaussian Marginals [34.64644162448095]
  We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. Our main positive result is a new algorithm for reliable learning of Gaussian halfspaces on $mathbbRd$ with sample and computational complexity.
  arXiv  Detail & Related papers  (2024-11-18T02:13:11Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  We study the problem of high-dimensional sparse mean estimation in the presence of an $epsilon$-fraction of adversarial outliers. Our algorithms follow the Sum-of-Squares based, to algorithms approach.
  arXiv  Detail & Related papers  (2022-06-07T16:49:54Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Point Location and Active Learning: Learning Halfspaces Almost Optimally [24.80812483480747]
  Given a finite set $X subset mathbbRd$ and a binary linear $c: mathbbRd to 0,1$, how many queries of the form $c(x)$ are required to learn the label of every point in $X$? We provide the first nearly optimal solution, a randomized linear decision tree of depth $tildeO(dlog(|X|))$, improving on the previous best of $tildeO(dlog(|X
  arXiv  Detail & Related papers  (2020-04-23T18:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.