Decidability of Sample Complexity of PAC Learning in finite setting
  In this short note we observe that the sample complexity of PAC machine
learning of various concepts, including learning the maximum (EMX), can be
exactly determined when the support of the probability measures considered as
models satisfies an a-priori bound. This result contrasts with the recently
discovered undecidability of EMX within ZFC for finitely supported
probabilities (with no a priori bound). Unfortunately, the decision procedure
is at present, at least doubly exponential in the number of points times the
uniform bound on the support size.
