Clustering with Weak Distance Oracles

Clustering is a fundamental task in unsupervised learning, serving as a core tool for data mining and exploratory data analysis. Classical $k$-clustering objectives such as $k$-median and $k$-means formalize this task, but typically assume access to exact pairwise distances. This assumption is increasingly unrealistic in modern applications where distances are estimated through proxy embedding models, learned similarity functions, human feedback, or other low-cost procedures that may be noisy. We study $k$-clustering in an unknown metric space where the algorithm has access only to a weak distance oracle: for each pair of objects, the oracle returns the true distance with probability of $1/2+\varepsilon$ , where $\varepsilon$ is a constant, and otherwise may return an arbitrary corrupted value. We present randomized algorithms that, given a metric space with $n$ vertices and a parameter $k$, use only weak distance-oracle queries to compute a set of representative centers together with a mapping from every input object to one of these centers, such that the total mapping cost is within a constant factor of the optimal $k$-clustering cost. Our first algorithm returns $O(k\cdot\mathsf{polylog}(n))$ centers using $O(n\cdot k\cdot \mathsf{polylog}(n))$ weak-oracle queries and runs in quasi-polynomial time. We also give a polynomial-time algorithm that returns $O(k^2\cdot\mathsf{polylog}(n))$ centers using $O(n\cdot k\cdot \mathsf{polylog}(n))$ weak-oracle queries. Preliminary experiments for $k$-means clustering show that our approach remains close to the optimum under substantial oracle noise, while noise-oblivious baselines degrade sharply.