Sublinear time algorithms for greedy selection in high dimensions

Qi Chen, Kai Liu, Ruilong Yao, Hu DingUAI 2022 · OpenReview

Introduction

Greedy selection is a fundamental technique in machine learning and computational geometry, used extensively for tasks such as $k$-center clustering, active learning, and core-set construction. The standard approach for these problems involves iteratively selecting the "best" next candidate based on a specific criterion—for instance, the point furthest from the current set of selections. However, as datasets grow into the millions of points ($n$) and thousands of dimensions ($d$), the traditional $O(nkd)$ complexity of these algorithms becomes a significant computational bottleneck. This paper presents a framework for randomized greedy selection that achieves sublinear time complexity, where the runtime is effectively independent of the total number of data points $n$.

In $k$-center clustering, the goal is to find $k$ points (centers) such that the maximum distance from any data point to its nearest center is minimized. The classic 2-approximation algorithm, Gonzalez’s algorithm, starts with an arbitrary point and iteratively adds the point furthest from the current set of centers. While mathematically elegant and robust, it requires a full pass over the dataset in every iteration. In high-dimensional spaces, this linear dependence on $n$ prevents real-time processing and limits scalability for massive datasets.

Proposed Methodology

The authors propose a randomized framework that replaces exhaustive searches with clever sampling strategies, ensuring that the selection process remains efficient without sacrificing theoretical guarantees.

1. Sublinear $k$-Center (Algorithm 1)

Instead of scanning all $n$ points to find the absolute furthest neighbor, the algorithm samples a small subset $Q$ of points uniformly at random. By picking the furthest point within $Q$ rather than the entire set, the complexity is reduced. The authors prove that with a sample size of approximately $O(\frac{k}{\epsilon} \log \frac{k}{\eta})$, the resulting centers will cover $(1-\epsilon)n$ points within a radius comparable to the original greedy algorithm. Crucially, this sample size does not depend on $n$.

2. Stratified Sampling and the Stopping Oracle

In many practical scenarios, the number of clusters $k$ is unknown, and the goal is instead to meet a target covering radius $r_0$. To address this, the authors introduce a stratified approach (Algorithm 2) that runs in phases, gradually increasing the sample size. To determine when to stop without looking at the full dataset, they employ a "Stopping Oracle" based on Chernoff bounds. This oracle estimates the fraction of points still uncovered, allowing the algorithm to terminate as soon as the target radius is likely achieved for the bulk of the data.

3. Convex Hull Approximation

The framework extends to high-dimensional convex hull approximation. Since calculating the exact distance to a convex hull is computationally expensive (often requiring quadratic programming), the authors integrate Gilbert’s algorithm. This allows for the efficient identification of approximate furthest points relative to the convex hull, maintaining sublinear performance even in complex geometric tasks.

Experimental Evaluation

The algorithms were tested on two primary computer vision benchmarks:

  • CIFAR-10: 60,000 images (3,072-dimensional vectors).
  • MNIST: 60,000 images (784-dimensional). To test extreme scalability, the authors created an augmented version of MNIST with 360,000 points by adding Gaussian noise to copies of the original digits.

Key Insights and Results

Efficiency and Speed

The sublinear algorithms demonstrated significant speedups over Gonzalez’s algorithm. On CIFAR-10, Algorithm 1 outperformed both the vanilla greedy approach and standard streaming baselines. The total time complexity for $k$-center was reduced to $\tilde{O}(k^3 d / \epsilon)$, a massive improvement when $n \gg k^2$.

The "Outlier Trap"

One of the most surprising findings was that randomized sampling sometimes yielded better results than exhaustive greedy selection. Standard greedy algorithms are highly sensitive to outliers—they will always pick the single most distant point, even if it is noise. Random sampling is more likely to pick a point representing the "bulk" of a distant cluster, leading to a more representative set of centers and a faster reduction in the covering radius.

Dimensionality Independence

The required sample size for the $k$-center algorithm is independent of the dimensionality $d$. This makes the approach uniquely suited for high-dimensional or even infinite-dimensional problems, such as those encountered in kernel methods, where $d$ is effectively the size of the Hilbert space.

Conclusion and Future Work

This research proves that for many greedy selection problems, we do not need to see all the data to make high-quality decisions. While the theoretical guarantees apply to a $(1-\epsilon)$ fraction of the data, empirical results show the algorithms perform well across the entire set. Future work may involve "beyond worst-case analysis" to further explain why these randomized approaches avoid the outlier sensitivity inherent in traditional greedy methods, and exploring the optimal tuning of the error tolerance $\epsilon$ and success probability $\eta$ for specific industrial applications.

Summary updated

Abstract

Greedy selection is a widely used idea for solving many machine learning problems. But greedy selection algorithms often have high complexities and thus may be prohibitive for large-scale data. In ...
BibTeX
@inproceedings{chen2022sublinear,
  author = {Qi Chen and Kai Liu and Ruilong Yao and Hu Ding},
  title = {{Sublinear time algorithms for greedy selection in high dimensions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=pgDbw-THbQ5},
}
Figure