Research map / Learning theory and algorithms / Sample complexity
The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
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.
Introduces iterative polynomial filtering to remove outliers, enabling efficient learning under bounded contamination (nasty noise) via low-degree approximators and under heavy additive contamination via sandwiching approximators, plus tolerant testable learning for log-concave halfspace functions.
Problem
Supervised binary classification when training data is adversarially contaminated in both covariates and labels (bounded contamination or heavy additive contamination), and tolerant testable learning under distribution shift.
Approach
A general iterative polynomial filtering algorithm that removes outliers while preserving expectations of any low-degree polynomial whose absolute expectation under a hypercontractive target is small; followed by L1 polynomial regression on the filtered set. Heavy contamination is handled by tuning the filter's selectivity R proportional to the contamination ratio Q.
Key results
- Bounded contamination learning of any hypercontractive-approximable class achieves error 2*eta+eps, e.g., first efficient algorithm for halfspaces under Gaussian with eta-bounded contamination at error 2eta+eps.
- Heavy additive contamination learning (Q-heavy) achieves error Q*OPT+eps for classes with sandwiching degree, e.g., intersections of k halfspaces in time d^{O~(Q^2 k^6/eps^4)}.
- First efficient tolerant testable learner for functions of halfspaces under any fixed log-concave distribution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use iterative polynomial filtering followed by polynomial regression, rather than the prior bounded-contamination method | Learning intersections of k halfspaces · Bounded contamination; Gaussian or uniform | error: 4\eta + \eps -> 2\eta + \eps | Helped |
| use iterative polynomial filtering followed by polynomial regression | Learning depth-t, size-s circuits · Bounded contamination; uniform | runtime: d^{O(\log s)^{O(t)} \log 1/\eps} -> d^{O(\log s)^{t-1} \log 1/\eps} | Helped |
| use low-degree approximating polynomials with iterative filtering for bounded contamination | Concept classes with low-degree approximators · Bounded contamination | error: 2\eta + \eps | Helped |
| use sandwiching approximators with iterative filtering | Concept classes with low-degree sandwiching polynomials · Heavy contamination | error: Q\cdot \opttotal + \eps | Helped |
| replace low-degree sandwiching approximators with ordinary low-degree approximators | Learning with heavy contamination · Monotone functions | sample complexity | Hurt |
Surprising findings
- Monotone functions require exponentially many samples (2^{Omega(d)}) for heavy contamination, separating it from bounded contamination.
Limitations
- Heavy contamination bounds are exponential in Q for many classes; monotone functions require exponential samples.
- Requires sandwiching or L1/L2 approximation degree with hypercontractive, efficiently samplable target marginal; distribution-specific only.
- Bounded contamination error 2eta+eps relies on approximation at eps^4 rather than eps^2, giving worse eps dependence than agnostic learning.
Experimental setup
Metrics: classification error under clean distribution sample complexity runtime
Baselines: agnostic learning via L1 polynomial regression Diakonikolas et al. bounded contamination PTF results tolerant testable learning with L2 sandwiching
Builds on: iterative filtering for distribution shift L1 polynomial regression (Kalai et al.) sandwiching approximators testable learning
Closest papers by meaning
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.87)
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.86)
- Robust Conformal Outlier Detection under Contaminated Reference Data (ICML 2025 · similarity 0.86)
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.85)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.85)
- Robustly Learning Single-Index Models via Alignment Sharpness (ICML 2024 · similarity 0.85)
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.