Research map / Learning theory and algorithms / Sample complexity
How to Query an Oracle? Efficient Strategies to Label Data
Farshad Lahouti, Victoria Kostina, Babak Hassibi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| increase query size k in the basic scheme (kIC) with uniform classes | Algorithm 1 · Uniform classes, analysis | query rate: N/(2(k-1)) queries/sample | Improved |
| increase query size k in the randomized batch scheme with uniform classes | Algorithm 2 · Uniform classes, analysis | query rate: 2N/(k(k-1)) queries/sample | Improved |
| use batch Algorithm 2 instead of basic Algorithm 1 at small k | kIC labeling · Uniform classes, analysis | query rate: only surpasses Algorithm 1 for k>=4 | Hurt |
| use adaptive greedy Algorithm 3 with 3IC instead of Algorithms 1 and 2 | kIC labeling · Uniform classes, N=10 | query rate: reduces the query rate by more than 40% | Improved |
| nonuniform class distribution with one large class instead of uniform | Algorithm 2 · 3IC, N=5 classes, L=100000 | query rate: rate ratio of Algorithm 1 to Algorithm 2 is (k-1)+0.5N*eps versus 0.25k for uniform | Improved |
| go from pairwise (2IC) to triplet (3IC) query for human annotators | Stanford Dogs labeling by volunteers · Stanford Dogs (300 images, 6 breeds) | time per query: almost 50% higher time for 3IC with three times more comparisons | Mixed |
| use k=N+1=7 direct labeling query with constant class representatives | Algorithm 1 · Stanford Dogs (300 images, 6 breeds) | processing time | No clear effect |
Closest papers by meaning
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.84)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.83)
- Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.83)
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.83)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.83)
- Towards Establishing Guaranteed Error for Learned Database Operations (ICLR 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.
