Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization
This addresses the challenge of out-of-distribution generalization for machine learning systems, offering theoretical guarantees, but it is incremental as it builds on existing ERM frameworks.
The paper tackles the problem of learning under distribution shifts where train and test distributions are related by transformation maps, establishing learning rules with algorithmic reductions to ERM and providing sample complexity upper bounds in terms of VC dimension.
Learning with identical train and test distributions has been extensively investigated both practically and theoretically. Much remains to be understood, however, in statistical learning under distribution shifts. This paper focuses on a distribution shift setting where train and test distributions can be related by classes of (data) transformation maps. We initiate a theoretical study for this framework, investigating learning scenarios where the target class of transformations is either known or unknown. We establish learning rules and algorithmic reductions to Empirical Risk Minimization (ERM), accompanied with learning guarantees. We obtain upper bounds on the sample complexity in terms of the VC dimension of the class composing predictors with transformations, which we show in many cases is not much larger than the VC dimension of the class of predictors. We highlight that the learning rules we derive offer a game-theoretic viewpoint on distribution shift: a learner searching for predictors and an adversary searching for transformation maps to respectively minimize and maximize the worst-case loss.