Abstract
Bateni et al. (2024) recently introduced the weak-strong distance oracle model to study clustering problems in settings with limited distance information. Given query access to the strong-oracle and weak-oracle in this model, the authors design approximation algorithms for $k$-means and $k$-center clustering problems. In this work, we design algorithms with improved guarantees for both problems. One of our main contributions is showing that the $k$-means++ algorithm can be adapted to the weak-strong oracle model using only a small number of strong-oracle queries, which is the critical resource. Specifically, our $k$-means++ based algorithm gives a constant approximation for $k$-means and uses $O(k^2 \log^2{n})$ strong-oracle queries, improving upon the previous $O(k^2 \log^4 n \log^2 \log n)$ requirement. For the $k$-center problem, we provide a ball-carving based $6(1 + \epsilon)$-approximation algorithm using $O(k^3 \log^2{n} \log{\frac{\log{n}}{\epsilon}})$ strong-oracle queries, an improvement over the previous $14(1 + \epsilon)$-approximation. Empirical evaluations on real-world datasets demonstrate that our algorithms significantly outperform existing methods.
Introduction
Standard clustering algorithms, such as $k$-means, typically assume full access to an exact distance matrix between all $n$ points. However, in many real-world applications—ranging from crowdsourcing to complex biological simulations—obtaining exact distances is computationally expensive or slow.
To address this, the weak-strong oracle model was introduced:
- Strong Oracle (SO): Provides exact distances but is highly expensive (limited budget).
- Weak Oracle (WO): Provides distances that are correct with probability $1-\delta$, but may return arbitrary values otherwise. It is cheap and allows for many queries.
The fundamental challenge is to find high-quality clustering solutions while minimizing the number of expensive Strong Oracle queries.
Methodology
Our approach bridges the gap between unreliable "weak" data and the need for precision through three core innovations:
1. The Median-of-Distances Trick
To mitigate noise from the Weak Oracle, we employ a robust estimation technique. To estimate the distance between points $x$ and $y$, we query the WO for distances between $x$ and a small set of points in a "ball" around $y$. By taking the median of these values, we obtain a robust estimator. As long as the WO is correct more than half the time ($\delta < 1/2$), the median converges to the true distance.
2. Adapting $k$-means++
The $k$-means++ algorithm is the standard for cluster initialization but relies on $D^2$-sampling. We demonstrate that by using our median-based distance estimates, we can simulate $k$-means++ while only requiring a small number of SO queries to "settle" clusters. A cluster is considered settled once enough centers have been sampled within it to make distance estimates reliable.
3. Ball-Carving for $k$-center
For the $k$-center problem, which seeks to minimize the maximum distance from any point to its nearest center, we utilize a "ball-carving" strategy. We iteratively select centers and remove (carve out) all points within a specific estimated radius, ensuring a tighter approximation than previous methods.
Key Results
Our algorithms provide significant theoretical improvements in both approximation factors and query complexity compared to the state-of-the-art results by Bateni et al. (2024).
As shown in the table above, our $k$-means algorithm reduces the logarithmic factors in the strong-oracle query complexity. For $k$-center, we improve the approximation guarantee from 14 to 6 while maintaining efficient query counts.
Empirical Evaluation
We evaluated our algorithms on synthetic datasets (Stochastic Block Model) and the MNIST dataset ($n=60,000$). On MNIST, our algorithms required 61% to 99% fewer strong queries than the previous state-of-the-art to achieve comparable or superior clustering costs. This demonstrates that our theoretical improvements translate directly into practical efficiency gains in real-world scenarios.
Conclusion
By leveraging the robustness of the median and adapting standard clustering heuristics like $k$-means++, we have developed more efficient algorithms for clustering under distance uncertainty. Future work includes exploring models with correlated noise and establishing absolute lower bounds for strong-oracle queries in these settings.
Summary updated