Improved Algorithms for Clustering with Noisy Distance Oracles

Pinki Pradhan, Anup Bhattacharya, Ragesh Jaiswal

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).

Comparison of approximation guarantees and query complexities for k-means and k-center clustering.

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

Abstract

Bateni et al. has 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 the weak-strong oracle model, the authors design approximation algorithms for $k$-means and $k$-center clustering problems. In this work, we design algorithms with improved guarantees for $k$-means and $k$-center clustering problems in the weak-strong oracle model. The $k$-means++ algorithm is routinely used to solve $k$-means in settings where complete distance information is available. One of the main contributions of this work is to show that $k$-means++ algorithm can be adapted to work in the weak-strong oracle model using only a small number of strong-oracle queries, which is the critical resource in this model. In particular, our $k$-means++ based algorithm gives a constant approximation for $k$-means and uses $O(k^2 \log^2{n})$ strong-oracle queries. This improves on the algorithm of Bateni et al. that uses $O(k^2 \log^4n \log^2 \log n)$ strong-oracle queries for a constant factor approximation of $k$-means. For the $k$-center problem, we give a simple ball-carving based $6(1 + ε)$-approximation algorithm that uses $O(k^3 \log^2{n} \log{\frac{\log{n}}ε})$ strong-oracle queries. This is an improvement over the $14(1 + ε)$-approximation algorithm of Bateni et al. that uses $O(k^2 \log^4{n} \log^2{\frac{\log{n}}ε})$ strong-oracle queries. To show the effectiveness of our algorithms, we perform empirical evaluations on real-world datasets and show that our algorithms significantly outperform the algorithms of Bateni et al.
BibTeX
@inproceedings{pradhan2026improved,
  author = {Pinki Pradhan and Anup Bhattacharya and Ragesh Jaiswal},
  title = {{Improved Algorithms for Clustering with Noisy Distance Oracles}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=6lFHvZzieB},
}
Figure