Research map / Learning theory and algorithms / Sample complexity

Iterative Chow Filtering for Learning with Distribution Shift

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Learning halfspaces under noise · 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.

Shows that L1 sandwiching suffices for efficient PQ learning via a new Iterative Chow Filtering procedure, yielding the first quasipolynomial-time PQ learner for DNFs under uniform marginals.

Problem

Efficient PQ learning under distribution shift (learner may abstain on out-of-distribution test points) was previously only possible via L2 sandwiching, which gives poor bounds for classes such as DNFs and constant-depth circuits.

Approach

Replace L2 sandwiching with the weaker L1 sandwiching and introduce Iterative Chow Filtering, which iteratively removes test points where Chow-type (classifier-weighted) polynomial expectations under the test distribution exceed R times those under the training distribution, enabling a multiplicative Chow-transfer error bound.

Key results

• First quasipolynomial-time PQ learner for DNFs under the uniform distribution, runtime d^{O(log^2 s)} versus prior d^{Otilde(sqrt s)}.
• Constant-depth circuits of size s and depth t: runtime d^{(log s)^{O(t)}} versus prior d^{sqrt(s)(log s)^{O(t)}}.
• Degree-2 PTFs under uniform marginal: poly(d) runtime versus prior 2^{O(d)}; constant-degree PTFs under Gaussian: poly(d) versus prior 2^{poly(d)}.

Surprising findings

• Requiring additive Chow matching between a selected test distribution and training distribution is impossible in general, motivating the multiplicative Chow-transfer lemma.

Limitations

• Relies on existence of L1 sandwiching polynomials under a hypercontractive training distribution.
• Unclear whether sandwiching conditions are necessary for efficient PQ learning.
• Unclear whether error bounds can be improved in other special cases.

Experimental setup

Metrics: runtime sample complexity selective error rejection rate

Baselines: Goel et al. L2 sandwiching PQ learner

Builds on: PQ learning (Goldwasser et al.) TDS learning (Klivans et al.) Iterative Polynomial Filtering L2 sandwiching PQ learning (Goel et al.) L1 regression (Kalai et al.)

Closest papers by meaning

• Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.86)
• Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees (ICLR 2025 · similarity 0.85)
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination (NeurIPS 2025 · similarity 0.85)
• Efficient Discrepancy Testing for Learning with Distribution Shift (NeurIPS 2024 · similarity 0.85)
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.84)
• Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.84)