A Sketching Method for Finding the Closest Point on a Convex Hull
This addresses a computational bottleneck for machine learning applications dealing with large, high-dimensional datasets, though it appears incremental as it builds on existing optimization techniques.
The paper tackles the problem of efficiently finding the closest point on the convex hull of a large dataset to an external query point, which is computationally expensive with exact or standard optimization methods. It introduces a sketching algorithm that breaks the data into pieces and uses a gradient project method to achieve faster convergence to the optimal solution compared to off-the-shelf algorithms.
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.