Abstract
Finding the closest point on a convex hull to an external query point is a fundamental problem in machine learning, particularly for tasks like out-of-distribution detection and model generalization. However, traditional computational geometry and standard optimization solvers often fail when faced with high-dimensional datasets containing millions of samples. This paper proposes a "sketching" algorithm that exploits the inherent sparsity of the geometric solution. By iteratively building the solution using sorted data partitions and a gradient projection strategy, the method significantly reduces the computational burden compared to off-the-shelf solvers.
Introduction
In modern machine learning, understanding the geometric structure of data is crucial. One powerful way to characterize a dataset is through its convex hull—the smallest convex set containing all datapoints. Determining the proximity of a new query point $q$ to this hull can help identify whether the sample is an outlier or part of the training distribution.
Despite its utility, finding the closest point on a convex hull is computationally intensive in high dimensions ($d$) with large sample sizes ($n$). While the problem can be framed as a constrained linear least-squares optimization, standard solvers struggle with the massive number of constraints when every datapoint is treated as a potential component of the solution.
The Sketching Algorithm
The proposed method addresses these challenges by combining a Sketching Method with a Gradient Projection optimization strategy. The core insight is that the optimal solution is typically highly sparse; even in a dataset of 60,000 points, the closest point on the hull might be defined by a combination of only a few dozen points.
The algorithm proceeds by first sorting the dataset $\mathcal{D}$ based on Euclidean distance to the query point $q$. It then partitions the data into $\eta$ subsets. The optimization begins with the subset closest to $q$, creating an initial "sketch" of the convex hull. As subsequent partitions are added, the algorithm uses the previous solution as a "warm start," updating only if new points offer a closer approximation. Within each iteration, a gradient projection method is employed to handle constraints (weights must sum to 1 and be non-negative), quickly identifying which points can be ignored.
Key Insights
Sparsity as a Computational Advantage
In high-dimensional spaces, most points are irrelevant to the specific geometric relationship between a query point and the hull. By prioritizing points closest to the query and ignoring irrelevant ones early, the sketching method avoids the overhead of managing a full set of constraints.
Sketching via Data Partitioning
Unlike traditional sketching in machine learning, which often involves random projections for dimensionality reduction, "sketching" here refers to data partitioning. This strategy breaks the data into manageable pieces, allowing the optimizer to build the solution incrementally.
Primal vs. Dual Formulations
The paper notes that while the primal solution (the weights of the points) is sparse, the Lagrange multipliers in the dual form are often non-sparse. This makes the dual form computationally more expensive to solve, justifying the focus on the primal gradient projection method.
Discussion and Future Work
While the theoretical framework is robust, several areas remain for future exploration. The current method requires sorting and partitioning relative to each specific query point $q$, which may become a bottleneck if thousands of queries are processed. Additionally, the sensitivity of the algorithm to the number of partitions ($\eta$) warrants further empirical study.
Future research could involve benchmarking this approach against established solvers like Gurobi or MOSEK on standard datasets. Furthermore, analyzing the specific points that constitute the "closest" convex combination may provide deeper insights into the internal structure of high-dimensional datasets and the nature of outliers.
Summary updated