Research map / Learning theory and algorithms / Sample complexity
Efficient active learning of sparse halfspaces with arbitrary bounded noise
Chicheng Zhang, Jie Shen, Pranjal Awasthi
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 the proposed active algorithm instead of the prior efficient sparse-halfspace approach | Active learning of sparse halfspaces under bounded noise · Isotropic log-concave distributions | label complexity | Improved |
| Use a noise-aware update that also updates on correctly predicted labels | Online mirror descent refinement · Bounded-noise halfspace learning | noise tolerance | Improved |
| Sample examples from a band around the current classifier | Online mirror descent refinement · Isotropic log-concave distributions | label complexity | Improved |
| Use sparsity-inducing online mirror descent regularization | Proposed active learning algorithm · Sparse halfspaces | label complexity | Improved |
| Initialize by averaging labeled examples, hard-thresholding, then refining | Proposed active learning algorithm · Sparse halfspaces | label complexity | Mixed |
| Replace the noise-aware update with the negative Perceptron update | Online mirror descent refinement · Bounded-noise halfspace learning | bounded-noise tolerance | Hurt |
Closest papers by meaning
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.91)
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.88)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.87)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.87)
- Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.86)
- Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate (NeurIPS 2026 · similarity 0.86)
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.
