Agnostic kind of nonuniform learnability
Structural risk minimization is an algorithm that can nonuniform learn nonuniform learnable classes.
What about the algorithm: Check the size of the training set, , and see what is the largest in the collection such that guarantees generalization gap smaller than . Then just do ERM with that ? Would that work for nonuniform learnability?