Abstract
Learning with identical train and test distributions has been extensivelyinvestigated both practically and theoretically. Much remains to be understood,however, in statistical learning under distribution shifts. This paper focuseson a distribution shift setting where train and test distributions can berelated by classes of (data) transformation maps. We initiate a theoreticalstudy for this framework, investigating learning scenarios where the targetclass of transformations is either known or unknown. We establish learningrules and algorithmic reductions to Empirical Risk Minimization (ERM),accompanied with learning guarantees. We obtain upper bounds on the samplecomplexity in terms of the VC dimension of the class composing predictors withtransformations, which we show in many cases is not much larger than the VCdimension of the class of predictors. We highlight that the learning rules wederive offer a game-theoretic viewpoint on distribution shift: a learnersearching for predictors and an adversary searching for transformation maps torespectively minimize and maximize the worst-case loss.