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

Tolerant Algorithms for Learning with Arbitrary Covariate Shift

NeurIPS 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Distributionally robust optimization · 1 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.

Gives dimension-efficient PQ learners and the first tolerant TDS and tolerant testable agnostic learners for halfspaces, intersections of halfspaces, decision trees and formulas under Gaussian/hypercube training marginals, via a spectral outlier-removal procedure with a dimension-free moment bound.

Problem

Learning under arbitrary covariate distribution shift with abstention: PQ learning (selective classification with adversarial test shift) and TDS learning (reject whole test set), where prior algorithms are computationally hard or reject tiny shifts.

Approach

Replace low-degree moment matching with a low-degree spectral boundedness condition, enabled by L2-sandwiching polynomials, and enforce it via an iterative spectral outlier-removal filter that handles arbitrarily large outlier fractions and gives a degree-independent second-moment bound with a potential-function iteration bound.

Key results

• PQ learning of general halfspaces under Gaussian marginal in time poly(d^{log(1/eps)}) with error and rejection rate eps.
• Tolerant TDS learning of halfspaces with runtime d^{O~(1/eps^2)} tolerating TV distance O(eps).
• Outlier removal gives error O(lambda)+2theta+eps for tolerant TDS learning, versus sqrt(lambda) for PQ in agnostic setting.

Surprising findings

• Low-degree moment-matching tests can reject distributions with total variation o(eps) from the reference, motivating tolerant tests.

Limitations

• Results hold only for limited training marginals (Gaussian, uniform on hypercube, log-concave-type tame distributions).
• Agnostic PQ error is sqrt(lambda), which is necessarily high for PQ.
• Completeness only for test marginals close to the training marginal, not to a wider class of distributions.

Experimental setup

Metrics: test error rejection rate runtime

Baselines: Klivans et al. 2023 TDS learner Goel et al. 2020 PQ learning Kalai et al. 2023 nasty noise learners

Builds on: PQ learning TDS learning nasty noise outlier removal L2 sandwiching

Closest papers by meaning

• Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees (ICLR 2025 · similarity 0.90)
• Efficient Discrepancy Testing for Learning with Distribution Shift (NeurIPS 2024 · similarity 0.89)
• Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization (NeurIPS 2024 · similarity 0.87)
• Sufficient Invariant Learning for Distribution Shift (CVPR 2025 · similarity 0.87)
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination (NeurIPS 2025 · similarity 0.87)
• Iterative Chow Filtering for Learning with Distribution Shift (NeurIPS 2026 · similarity 0.86)