ATheoryofPACLearnabilityunderTransformation Invariances

Third, weintroduce acomplexitymeasure (seeDefinition 5)thatcharacterizes theoptimal sample complexity of learning in settings (ii) and (iii) above, and we give optimal algorithms for these settings. Finally,wealso provide adaptivelearning algorithms that interpolate between settings (i) and (ii), i.e., whenh is partiallyinvariant.