Research map / Learning theory and algorithms / Sample complexity
Efficient Discrepancy Testing for Learning with Distribution Shift
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 provably efficient testers for localized discrepancy distance (Chow matching, cylindrical grids, boundary proximity), yielding improved, universal, and fully polynomial test-time TDS learners for several concept classes.
Problem
Testing discrepancy distance between train and test distributions is hard in general because it requires enumerating a whole concept class, which blocks efficient guarantees for learning under distribution shift (TDS learning).
Approach
Replace global discrepancy with localized discrepancy measured relative to a fixed candidate classifier, and show efficient testers for it: low-degree Chow-parameter matching under L1 sandwiching, cylindrical grid tests on subspaces, and boundary-proximity tests for halfspace intersections. Decoupling training from testing lets the test phase be fully polynomial.
Key results
- Chow matching tester gives L1-sandwiching implies TDS learning with error lambda+opt_train+epsilon, yielding the first TDS learner for AC0 with exponential improvement in runtime.
- Universal TDS learner for balanced intersections of k halfspaces with fully polynomial test time poly(d,k,1/eps) and training poly(d) exp(O(k^5/eps)).
- Realizable TDS learner for eps-balanced convex subspace juntas with poly(d) (k/eps)^{O(k)} testing time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use L1 rather than L2 sandwiching for TDS learning | TDS learning for concept classes with low sandwiching degree · General concept classes | error guarantee: O(λ) -> λ+opt_train+O(ε) | Helped |
| Use L1 rather than L2 sandwiching | TDS learning for constant-depth circuits · Depth-t AC0 formulas | runtime: d^{\sqrt{s}\cdot O( \log({s}/{\eps}))^{O(t)}} -> d^{ O(\log({s}/{\eps}))^{O(t)}} | Helped |
| Use the proposed learner instead of the prior state-of-the-art | TDS learning of balanced intersections of halfspaces · Intersections of k halfspaces | testing runtime: d^{O(\log(k/\eps))}+\poly(d)(k/\eps)^{O(k^2)} -> \poly(d,k,1/\eps) | Helped |
| Make the intersection learner universal over structured test distributions | TDS learning of balanced intersections of halfspaces · Intersections of k halfspaces | testing runtime: d^{O(\log(k/\eps))}+\poly(d)(k/\eps)^{O(k^2)} -> \poly(d,k,1/\eps) | Helped |
| Trade universality for the non-universal tester | TDS learning of balanced intersections of halfspaces · Intersections of k halfspaces | testing runtime: \poly(d,k,1/\eps) -> (dk)^{O(\log(1/\eps))} | Mixed |
Limitations
- Universal learners pay exponential cost in training runtime
- Some results require balanced concepts and Gaussian or uniform training marginals
Experimental setup
Metrics: sample complexity time complexity test error bound
Baselines: Klivans et al. 2023 L2-sandwiching TDS learner previous state-of-the-art halfspace intersection TDS learner
Builds on: TDS learning (Klivans et al. 2023) testable agnostic learning discrepancy distance
Closest papers by meaning
- Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees (ICLR 2025 · similarity 0.91)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.89)
- On $f$-Divergence Principled Domain Adaptation: An Improved Framework (NeurIPS 2024 · similarity 0.86)
- Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach (NeurIPS 2024 · similarity 0.85)
- Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.85)
- Iterative Chow Filtering for Learning with Distribution Shift (NeurIPS 2026 · 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.