Research map / Learning theory and algorithms / Sample complexity
Near-Optimal Active Learning of Halfspaces via Query Synthesis in the Noisy Setting
Lin Chen, Hamed Hassani, Amin Karbasi
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 |
|---|---|---|---|
| Use dimension coupling instead of prior methods | Synthetic halfspace learning, noiseless setting · Noiseless synthetic halfspace queries | estimation error | Improved |
| Use dimension coupling instead of prior methods | Synthetic halfspace learning, noisy setting · Noisy synthetic halfspace queries | estimation error: around two orders of magnitude smaller | Improved |
| Use dimension coupling instead of repetitive querying | Synthetic halfspace learning · Noisy synthetic halfspace queries, ρ=0.2, d=1000 | estimation error: three orders of magnitude smaller | Improved |
| Use dimension coupling instead of repetitive querying | Synthetic halfspace learning · Noisy synthetic halfspace queries | execution time | Hurt |
| Use dimension coupling instead of random sampling, uncertainty sampling, or query-by-committee | Synthetic halfspace learning · Noisy synthetic halfspace queries | execution time: around 100 times faster | Improved |
| Use dimension coupling instead of version-space ellipsoid search | Synthetic halfspace learning · Noisy synthetic halfspace queries | estimation error | Improved |
| Combine two-dimensional subproblems through dimension coupling | Dimension Coupling (DC) · Noisy synthetic halfspace queries | estimation error: 5 ε (d-1) | Improved |
Closest papers by meaning
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.86)
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.86)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.85)
- Improved Active Learning via Dependent Leverage Score Sampling (ICLR 2024 · similarity 0.84)
- Robust Regression of General ReLUs with Queries (NeurIPS 2025 · similarity 0.84)
- Querying Easily Flip-flopped Samples for Deep Active Learning (ICLR 2024 · 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.
