Research map / Learning theory and algorithms / Clustering
Optimal Algorithms for Learning Partitions with Faulty Oracles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives query-optimal algorithms for recovering a hidden partition with same-cluster queries when up to ℓ answers may be faulty, matching lower bounds via a Rényi-Ulam correlation-clustering game analysis.
Problem
Exactly recovering a hidden k-partition of an n-element set using same-cluster (\"are u and v in the same group?\") queries when up to ℓ answers from the oracle may be wrong (non-persistent errors), with the goal of minimizing query complexity.
Approach
Algorithms that build cliques of negative answers (certifying false negatives) and repeat positive-answer queries until a count threshold (certifying true positives), with a Rényi-Ulam / chip-liar game linked to correlation clustering that yields matching lower bounds; false negatives and false positives have asymmetric cost, (n-k)ℓ_yes versus k²ℓ_no.
Key results
- Algorithm for weighted ℓ-PL in k-known setting uses O(RS_k(n,k) + (n−k)ℓ_yes + k²ℓ_no) queries, matched by lower bounds Ω(max{RS, ℓ_yes(n−k), ℓ_no k²}).
- For the ℓ-PL problem in the k-known setting, query complexity is Θ(RS_k(n,k) + (n−k)ℓ + k²ℓ).
- In the k-unknown setting, an upper bound O(RS_u(n,k) + (n−k)max{ℓ_yes,ℓ_no} + k²ℓ_no) is given, matching lower bounds except for the weighted case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow up to ℓ false-negative answers instead of no errors | Partition learning with known k · k-known | query complexity: RSk(n, k) -> Θ(RSk(n, k) + k2ℓ) | Mixed |
| Allow up to ℓ false-positive answers instead of no errors | Partition learning with known k · k-known | query complexity: RSk(n, k) -> Θ(RSk(n, k) + (n − k)ℓ) | Mixed |
| Allow up to ℓ errors of either type | Partition learning with known k · k-known | query complexity: RSk(n, k) -> Θ(RSk(n, k) + (n − k)ℓ + k2ℓ) | Hurt |
| Allow up to ℓ false-negative answers instead of no errors | Partition learning with unknown k · k-unknown | query complexity: RSu(n, k) -> Θ(RSu(n, k) + (n − k)ℓ + k2ℓ) | Hurt |
| Allow up to ℓ false-positive answers instead of no errors | Partition learning with unknown k · k-unknown | query complexity: RSu(n, k) -> Θ(RSu(n, k) + (n − k)ℓ) | Hurt |
| Allow up to ℓ errors of either type | Partition learning with unknown k · k-unknown | query complexity: RSu(n, k) -> Θ(RSu(n, k) + (n − k)ℓ + k2ℓ) | Hurt |
| Use false-positive tolerance ℓyes and false-negative tolerance ℓno | Weighted ℓ-PL algorithm · k-known | query complexity: (n − k)ℓyes + k2ℓno | Mixed |
| Use false-positive tolerance ℓyes and false-negative tolerance ℓno | Weighted ℓ-PL algorithm · k-unknown | query complexity: (n − k) max{ℓyes, ℓno} + k2ℓno | Mixed |
Surprising findings
- False negatives and false positives have asymmetric query costs: false positives cost a factor of n−k per error while false negatives cost k² per error.
Limitations
- Only worst-case adversarial error model; results do not directly apply to stochastic errors exceeding tolerance ℓ.
- Weighted ℓ-PL in k-unknown setting has a gap between upper and lower bounds.
- Only same-cluster queries considered, not triangle or other query models.
Experimental setup
Metrics: query complexity
Baselines: Reyzin and Srivastava algorithm Liu and Mukherjee lower bound
Builds on: Reyzin and Srivastava same-cluster algorithm Liu and Mukherjee query lower bounds Rényi-Ulam liar games correlation clustering
Closest papers by meaning
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.87)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.85)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.85)
- Clustering Items through Bandit Feedback: Finding the Right Feature out of Many (ICML 2025 · similarity 0.85)
- Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.85)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.