Research map / Learning theory and algorithms / Sample complexity
Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization
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.
Theoretical study of OOD generalization where train and test distributions are related by classes of data transformations; gives ERM-based learning rules, VC-based sample complexity bounds, and algorithmic reductions to ERM with a small synthetic experiment.
Problem
Learning predictors that perform uniformly well across distributions obtained by transforming a source distribution by a known or unknown class of data transformation maps, under covariate shift with unchanged labels.
Approach
Describes distribution shift as a transformation class T applied to the source distribution D, and bounds sample complexity via the VC dimension of the composed class H∘T; gives min-max ERM learning rules, a multiplicative-weights reduction to ERM for the agnostic case with finite T, and a relaxed "as many transformations as possible" objective.
Key results
- Upper bound: worst-case ERM over H∘T learns with sample complexity O((vc(H∘T)+log(1/δ))/ε²); for linear transformations vc(H∘T) ≤ vc(H).
- Multiplicative-weights reduction using only an ERM oracle achieves OPT_∞+ε for finite T with R=O(ln|T|/ε²) rounds.
- Basic experiment on Boolean functions: heuristic permutation-augmented SGD is compared against standard SGD with a two-layer 512-unit network (reported results not quantified in text).
Surprising findings
- The worst-case-optimal proper learning rule can have sample complexity Ω(vc(H∘T)), which can be much larger than vc(H), showing a gap from VC dimension of H alone.
Limitations
- Reductions require finite transformation class T; infinite T can fail with ERM oracle only.
- Proper learning rules incur sample complexity lower bounded by vc(H∘T), potentially much larger than vc(H).
- Min-max learning rules are not implemented with neural parameterizations; experiments are small and heuristic.
Experimental setup
Datasets: synthetic Boolean hypercube data (parity and majority-of-subparities functions)
Benchmarks: synthetic Boolean hypercube learning (parity, majority-of-subparities)
Metrics: test error
Baselines: standard mini-batch SGD
Builds on: distributionally robust optimization multi-distribution learning invariant risk minimization adversarially robust learning
Closest papers by meaning
- Distribution Shift Is Key to Learning Invariant Prediction (AAAI 2026 · similarity 0.89)
- Robust Generalization despite Distribution Shift via Minimum Discriminating Information (NeurIPS 2021 · similarity 0.88)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.87)
- Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees (ICLR 2025 · similarity 0.87)
- Towards Robust Out-of-Distribution Generalization Bounds via Sharpness (ICLR 2024 · similarity 0.86)
- Sufficient Invariant Learning for Distribution Shift (CVPR 2025 · similarity 0.86)
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.