We study a variant of nonuniform PAC learning, where the constants in the learning rate may depend on the marginal distribution, and devise a trichotomy of possible rates.

When can learning be implemented as a computer program? We answer this question for the theoretical model of universal online learning.