Research map / Label-efficient and robust learning / Test-time adaptation
Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
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 the first provably efficient TDS (testable learning with distribution shift) algorithms for regression with neural networks, via a kernel-based spectral tester (bounded, hypercontractive training marginals) and a uniform-polynomial-approximation moment-matching tester (strictly subexponential marginals).
Problem
Learning neural networks in the regression setting with distribution shift, where the learner must either reject or output a hypothesis with provably near-optimal test error without any assumptions on the test distribution.
Approach
Extends TDS learning from classification to nonconvex real-valued regression. It builds a data-dependent reference feature map from train and test samples, uses a multiplicative spectral test on fresh verification samples to certify transfer of error, and for unbounded training marginals replaces sandwiching with uniform polynomial approximation plus moment matching.
Key results
- For bounded, hypercontractive training marginals, one hidden-layer sigmoid networks admit TDS regression in poly(d, M, 1/epsilon) time.
- For strictly subexponential training marginals, arbitrary Lipschitz-activation networks of constant depth are TDS-learnable in time poly(d^s, 1/epsilon, log(1/delta)^l) with s depending on the approximation degree.
- Single ReLU under bounded hypercontractive marginals is TDS-learnable in poly(d, M) time for epsilon < 1/log d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the proposed TDS learning algorithm to one hidden-layer sigmoid networks under bounded training distributions | One hidden-layer Sigmoid Net · TDS regression, bounded training distributions | runtime: \mathrm{poly}(d,M,1/\epsilon) | Helped |
| Apply the proposed TDS learning algorithm to a single ReLU under bounded training distributions | Single ReLU · TDS regression, bounded training distributions | runtime: \mathrm{poly}(d,M)\cdot 2^{O(1/\epsilon)} | Helped |
| Apply the proposed TDS learning algorithm to sigmoid networks under bounded training distributions | Sigmoid Nets · TDS regression, bounded training distributions | runtime: \mathrm{poly}(d,M) \cdot 2^{O\left((\log(1/\epsilon))^{t-1}\right)} | Helped |
| Apply the proposed TDS learning algorithm to 1-Lipschitz networks under bounded training distributions | 1-Lipschitz Nets · TDS regression, bounded training distributions | runtime: \mathrm{poly}(d,M) \cdot 2^{\tilde{O}(k\sqrt{k}2^{t-1}/\epsilon)} | Helped |
Surprising findings
- A bound on some constant-degree moment of the test labels is necessary for TDS regression, not just the training labels.
Limitations
- Subexponential case runtime is quasi-polynomial in d (d^{poly(k log(M/eps))}), not fully polynomial.
- Requires hypercontractivity of the training marginal, and bounded labels or a bounded moment of test labels.
Experimental setup
Metrics: test error bound relative to opt + lambda running time
Baselines: Kernel-based agnostic learning of ReLU/sigmoid nets (no distribution shift) prior TDS classification algorithms (sandwiching-based)
Builds on: TDS learning (Klivans et al., 2024) kernel-based agnostic learning of neural networks sandwiching polynomial TDS learning testable agnostic learning
Closest papers by meaning
- Efficient Discrepancy Testing for Learning with Distribution Shift (NeurIPS 2024 · similarity 0.91)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.90)
- Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization (NeurIPS 2024 · similarity 0.87)
- Iterative Chow Filtering for Learning with Distribution Shift (NeurIPS 2026 · similarity 0.85)
- Domain-wise Data Acquisition to Improve Performance under Distribution Shift (ICML 2024 · similarity 0.85)
- On Statistical Learning Theory for Distributional Inputs (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.