Research map / Learning theory and algorithms / Sample complexity

Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning halfspaces under noise

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first attribute-efficient (O(s^2 log^5 d) samples) PAC learner for s-sparse halfspaces tolerating a constant malicious noise rate, under margin and mixture-of-logconcaves assumptions, via sparsity-constrained soft outlier removal and hinge loss minimization.

Problem

PAC learning of s-sparse halfspaces with malicious noise at a constant rate, requiring sample complexity polynomial in s and log d.

Approach

Extends the margin plus mixture-of-logconcaves robust learning framework to sparse settings by solving a hinge loss minimization over an L2 and L1 constrained set, with a semidefinite soft outlier removal step, a KKT-based gradient analysis handling both constraints, and function-class (L_infinity) covering instead of geometric covering.

Key results

• Learns an s-sparse halfspace with O(s^2 log^5 d log^2(1/(epsilon delta))) samples under a constant malicious noise rate eta_0 <= 1/2^28 (theoretical result).
• Gives an information-theoretic lower bound Omega(s(log(1/epsilon)+log(d/s))) for the noiseless case under the same assumptions.
• Claims near-optimality: the O(s^2) dependence matches an SQ-based lower bound for computationally efficient learners up to log factors.

Surprising findings

• Constant malicious noise rate is tolerated, unlike prior attribute-efficient methods limited to noise O(epsilon).

Limitations

• Requires a constant-noise threshold eta_0 that is very small (1/2^28) in the analysis.
• Requires margin and mixture-of-logconcaves assumptions and k <= 64 components.
• Optimal s^2 dependence is only supported by evidence, not an information-theoretic lower bound.

Experimental setup

Metrics: sample complexity error rate

Baselines: Prior margin-based surrogate loss methods for malicious noise (dense pancake fra Attribute-efficient learners with noise rate O(epsilon)

Builds on: Diakonikolas et al. margin plus logconcave robust halfspace learning framework Hanneke-style dense pancake condition semidefinite relaxation for sparse variance

Closest papers by meaning

• A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.89)
• Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.88)
• Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.87)
• Robust learning of halfspaces under log-concave marginals (NeurIPS 2025 · similarity 0.85)
• Distribution-Specific Agnostic Conditional Classification With Halfspaces (ICLR 2025 · similarity 0.85)
• Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.85)