Research map / Learning theory and algorithms / Sample complexity
Noise-Tolerant Interactive Learning Using Pairwise Comparisons
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a pairwise comparison oracle alongside the labeling oracle | A2-ADGAC · Tsybakov noise, generic class | label complexity | Helped |
| add a pairwise comparison oracle alongside the labeling oracle | A2-ADGAC · Adversarial noise nu=O(eps), generic class | label complexity: ˜O(dθ) -> ˜O(1) | Helped |
| add a pairwise comparison oracle alongside the labeling oracle | Margin-ADGAC · Massart noise, halfspaces | label complexity: ˜O(d) -> ˜O(1) | Helped |
| add a pairwise comparison oracle alongside the labeling oracle | Margin-ADGAC · Adversarial noise, halfspaces | label complexity: ˜O(d2) -> ˜O(1) | Helped |
| replace batch sampling with ADGAC in active learning | Margin-ADGAC · Adversarial noise, halfspaces | total query complexity: ˜O(d2) -> ˜O(d) | Helped |
| use comparisons to learn halfspaces under Massart noise efficiently | Margin-ADGAC · Massart noise, halfspaces | total query complexity | No clear effect |
| add comparison oracle under Tsybakov noise | A2-ADGAC · Tsybakov noise, generic class | total query complexity | Helped |
| add comparison oracle under Tsybakov noise | Margin-ADGAC · Tsybakov noise, halfspaces | total query complexity | Helped |
| add comparison oracle under adversarial noise, generic class | A2-ADGAC · Adversarial noise, generic class | total query complexity | No clear effect |
Closest papers by meaning
- A General Framework for Robust Interactive Learning (NeurIPS 2017 · similarity 0.86)
- Don’t Label Twice: Quantity Beats Quality when Comparing Binary Classifiers on a Budget (ICML 2024 · similarity 0.85)
- Active Learning From Positive and Unlabeled Examples (NeurIPS 2026 · similarity 0.84)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.84)
- Information-theoretic Limits of Online Classification with Noisy Labels (NeurIPS 2024 · similarity 0.83)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.83)
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.