Research map / Learning theory and algorithms / Prediction and decision losses
A General Framework for Robust Interactive Learning
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 |
|---|---|---|---|
| Use the graph-based median-query strategy instead of swapping only the reported adjacent pair | Interactive ranking with adjacent-transposition feedback · Ranking | equivalence queries: Θ(n^2) -> O(n log n) | Helped |
| Use graph-based interactive learning with correct feedback | Ranking with adjacent-transposition feedback · Ranking | equivalence queries: at most log n! ≤ n log n | Helped |
| Allow feedback to be correct with probability p > 1/2 and use multiplicative-weights likelihood updates | Graph-based interactive learning · Ranking with adjacent-transposition feedback | equivalence queries in expectation: \frac{(1 - \delta)}{1 - \Entr{p}} n \log n + o(n \log n) + O(\log^2(1/delta)) | Helped |
| Use weighted insertion-sort graph edges to represent feedback moving an item ahead of a block | Interactive ranking · Ranking with insertion-sort feedback | equivalence queries: at most log n! ≤ n log n | Helped |
| Use the graph framework for clustering with merge and split feedback | Interactive clustering · Clustering with at most M candidate clusters and k target clusters | queries: O(k log M) | Helped |
| Use unrestricted candidate clusterings rather than restricting the cluster class | Graph-based interactive clustering · Clustering with correct feedback | queries: Θ(n log n) | Hurt |
| Use arbitrary-swap feedback with the proposed graph framework | Interactive ranking · Ranking with arbitrary-swap feedback | graph-framework applicability: c < n | Hurt |
| Require an approximate sampling oracle for likelihood-weighted candidate models | Efficient implementation of the noisy-feedback algorithm · Interactive ranking | computational feasibility: 1 - \Delta | Hurt |
Closest papers by meaning
- Robust Offline Active Learning on Graphs (NeurIPS 2024 · similarity 0.84)
- Provably Efficient Interactive-Grounded Learning with Personalized Reward (NeurIPS 2024 · similarity 0.84)
- Order-Robust Class Incremental Learning: Graph-Driven Dynamic Similarity Grouping (CVPR 2025 · similarity 0.83)
- Probably Approximately Precision and Recall Learning (NeurIPS 2025 · similarity 0.82)
- Interactive Deep Clustering via Value Mining (NeurIPS 2024 · similarity 0.82)
- Sampling for Beyond-Worst-Case Online Ranking (AAAI 2024 · similarity 0.82)
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.