# On Margin-Based Cluster Recovery with Oracle Queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 45 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Approximate Correlation Clustering Using Same-Cluster Queries](https://mlsanity.com/paper/1712.06865/) (2017)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Approximate Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1704.01862/) (2017)
- [Semisupervised Clustering by Queries and Locally Encodable Source Coding](https://mlsanity.com/paper/1904.00507/) (2019)
- [Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering](https://mlsanity.com/paper/1803.00926/) (2018)
- [The VC-dimension of k-vertex d-polytopes](https://mlsanity.com/paper/2004.04841/) (2020)
- [Centerpoints: A link between optimization and convex geometry](https://mlsanity.com/paper/1511.08609/) (2015)
- [Fault-Tolerant Entity Resolution with the Crowd](https://mlsanity.com/paper/1512.00537/) (2015)
- [Flattening a Hierarchical Clustering through Active Learning](https://mlsanity.com/paper/1906.09458/) (2019)

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

- [Active Learning of Classifiers with Label and Seed Queries](https://mlsanity.com/paper/2209.03996/) (2022)
- [Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle](https://mlsanity.com/paper/2305.13402/) (2023)

## Abstract (arXiv)

We study an active cluster recovery problem where, given a set of n points and an oracle answering queries like "are these two points in the same cluster?", the task is to recover exactly all clusters using as few queries as possible. We begin by introducing a simple but general notion of margin between clusters that captures, as special cases, the margins used in previous work, the classic SVM margin, and standard notions of stability for center-based clusterings. Then, under our margin assumptions we design algorithms that, in a variety of settings, recover all clusters exactly using only O(log n) queries. For the Euclidean case, ℝm, we give an algorithm that recovers arbitrary convex clusters, in polynomial time, and with a number of queries that is lower than the best existing algorithm by Theta(mm) factors. For general pseudometric spaces, where clusters might not be convex or might not have any notion of shape, we give an algorithm that achieves the O(log n) query bound, and is provably near-optimal as a function of the packing number of the space. Finally, for clusterings realized by binary concept classes, we give a combinatorial characterization of recoverability with O(log n) queries, and we show that, for many concept classes in Euclidean spaces, this characterization is equivalent to our margin condition. Our results show a deep connection between cluster margins and active cluster recoverability.