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$.
The Problem: The Cost of Exhaustive Search
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