A Sketching Method for Finding the Closest Point on a Convex Hull

Roozbeh YousefzadeharXiv 2021 · arXiv

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.

Algorithm 1: Finding the point on the convex hull of a dataset closest to a query point.

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

Abstract

We develop a sketching algorithm to find the point on the convex hull of a dataset, closest to a query point outside it. Studying the convex hull of datasets can provide useful information about their geometric structure and their distribution. Many machine learning datasets have large number of samples with large number of features, but exact algorithms in computational geometry are usually not designed for such setting. Alternatively, the problem can be formulated as a linear least-squares problem with linear constraints. However, solving the problem using standard optimization algorithms can be very expensive for large datasets. Our algorithm uses a sketching procedure to exploit the structure of the data and unburden the optimization process from irrelevant points. This involves breaking the data into pieces and gradually putting the pieces back together, while improving the optimal solution using a gradient project method that can rapidly change its active set of constraints. Our method eventually leads to the optimal solution of our convex problem faster than off-the-shelf algorithms.
BibTeX
@misc{yousefzadeh2021sketching,
  author = {Roozbeh Yousefzadeh},
  title = {{A Sketching Method for Finding the Closest Point on a Convex Hull}},
  year = {2021},
  eprint = {2102.10502},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.10502},
}
Figure