Research map / Learning theory and algorithms / Prediction and decision losses

Distribution-Specific Agnostic Conditional Classification With Halfspaces

ICLR 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Data attribution and recourse · 0 citations (OpenAlex)

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.

Studies agnostic conditional (selective) classification with sparse linear classifiers and homogeneous halfspace selectors under Gaussian marginals, giving a polynomial-time O(sqrt(opt)) PAC algorithm via projected SGD on a ReLU surrogate, and a cryptographic hardness result showing additive-error approximation is as hard as agnostic halfspace learning.

Problem

Agnostic conditional classification: learning a classifier and a selector (subset defined by a halfspace with population in [a,b]) that minimize error conditioned on the selected subset, under adversarial label noise and Gaussian marginals.

Approach

Reduce one-sided conditional classification for each candidate classifier to a one-sided agnostic linear problem, and find a near-optimal homogeneous halfspace selector by projected SGD on a ReLU surrogate loss, whose approximate stationary points are provably near-optimal under Gaussian marginals; combined with robust list learning for sparse classifiers.

Key results

• Algorithm achieves conditional classification error O(sqrt(opt)) with O(d/epsilon^6) examples and runtime O(d|C|/epsilon^6) for finite classes under standard normal marginals.
• Extends to sparse linear classifiers with poly(d,1/epsilon,1/delta) samples and runtime for constant sparsity.
• Under sub-exponential cLWE assumption, conditional classification with general halfspaces has no d^{O(1/(eps sqrt(log d))^alpha)} time algorithm achieving additive error eps for eps >= c/sqrt(d log d) and eps <= 1/log^gamma d.

Surprising findings

• Conditional classification with general halfspaces may be strictly harder than agnostic classification in multiplicative form.

Limitations

• Selectors restricted to homogeneous halfspaces, which can only select half the data and limit the advantage of conditional classification.
• Requires standard normal marginals, which are unrealistic for real data.
• O(sqrt(opt)) error guarantee appears suboptimal.

Experimental setup

Metrics: conditional classification error

Baselines: agnostic halfspace learning hardness results

Builds on: agnostic linear classification approximation schemes robust list learning of sparse linear classifiers continuous LWE hardness assumption

Closest papers by meaning

• Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.87)
• Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.85)
• Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate (NeurIPS 2026 · similarity 0.85)
• On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.85)
• Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals (NeurIPS 2026 · similarity 0.84)
• Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.84)