# How to Design Robust Algorithms using Noisy Comparison Oracle

arXiv: https://arxiv.org/abs/2105.05782 · HTML: https://mlsanity.com/paper/2105.05782/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 85 references that are in the map.
- First posted on arXiv 12 May 2021.

## Builds on (most cited first, 27 of 27)

- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Metric Learning for Individual Fairness](https://mlsanity.com/paper/1906.00250/) (2019)
- [TaxoGen: Unsupervised Topic Taxonomy Construction by Adaptive Term Embedding and Clustering](https://mlsanity.com/paper/1812.09551/) (2018)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces](https://mlsanity.com/paper/1804.06829/) (2018)
- [Clustering - What Both Theoreticians and Practitioners are Doing Wrong](https://mlsanity.com/paper/1805.08838/) (2018)
- [Query K-means Clustering and the Double Dixie Cup Problem](https://mlsanity.com/paper/1806.05938/) (2018)
- [Approximate Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1704.01862/) (2017)
- [Foundations of Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/1811.00928/) (2018)
- [Correlation Clustering with Adaptive Similarity Queries](https://mlsanity.com/paper/1905.11902/) (2019)
- [Parallel Algorithms for Select and Partition with Noisy Comparisons](https://mlsanity.com/paper/1603.04941/) (2016)
- [Crowdsourced correlation clustering with relative distance comparisons](https://mlsanity.com/paper/1709.08459/) (2017)
- [Comparison Based Learning from Weak Oracles](https://mlsanity.com/paper/1802.06942/) (2018)
- [Learning Nearest Neighbor Graphs from Noisy Distance Samples](https://mlsanity.com/paper/1905.13267/) (2019)
- [Relaxed Oracles for Semi-Supervised Clustering](https://mlsanity.com/paper/1711.07433/) (2017)
- [Sorting and Selection with Imprecise Comparisons](https://mlsanity.com/paper/1501.02911/) (2015)
- [Semi-Supervised Active Clustering with Weak Oracles](https://mlsanity.com/paper/1709.03202/) (2017)
- [Sorting with Recurrent Comparison Errors](https://mlsanity.com/paper/1709.07249/) (2017)
- [Skyline Computation with Noisy Comparisons](https://mlsanity.com/paper/1710.02058/) (2017)
- [Optimal Sorting with Persistent Comparison Errors](https://mlsanity.com/paper/1804.07575/) (2018)

## Built on by (most cited first, 4 of 4)

- [A Revenue Function for Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/2211.16459/) (2022)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)

## Abstract (arXiv)

Metric based comparison operations such as finding maximum, nearest and farthest neighbor are fundamental to studying various clustering techniques such as k-center clustering and agglomerative hierarchical clustering. These techniques crucially rely on accurate estimation of pairwise distance between records. However, computing exact features of the records, and their pairwise distances is often challenging, and sometimes not possible. We circumvent this challenge by leveraging weak supervision in the form of a comparison oracle that compares the relative distance between the queried points such as `Is point u closer to v or w closer to x?'. However, it is possible that some queries are easier to answer than others using a comparison oracle. We capture this by introducing two different noise models called adversarial and probabilistic noise. In this paper, we study various problems that include finding maximum, nearest/farthest neighbor search under these noise models. Building upon the techniques we develop for these comparison operations, we give robust algorithms for k-center clustering and agglomerative hierarchical clustering. We prove that our algorithms achieve good approximation guarantees with a high probability and analyze their query complexity. We evaluate the effectiveness and efficiency of our techniques empirically on various real-world datasets.