  We consider the following statistical estimation problem: given a family F of
real valued functions over some domain X and an i.i.d. sample drawn from an
unknown distribution P over X, find h in F such that the expectation of h
w.r.t. P is probably approximately equal to the supremum over expectations on
members of F. This Expectation Maximization (EMX) problem captures many well
studied learning problems; in fact, it is equivalent to Vapnik's general
setting of learning.
  Surprisingly, we show that the EMX learnability, as well as the learning
rates of some basic class F, depend on the cardinality of the continuum and is
therefore independent of the set theory ZFC axioms (that are widely accepted as
a formalization of the notion of a mathematical proof).
  We focus on the case where the functions in F are Boolean, which generalizes
classification problems. We study the interaction between the statistical
sample complexity of F and its combinatorial structure. We introduce a new
version of sample compression schemes and show that it characterizes EMX
learnability for a wide family of classes. However, we show that for the class
of finite subsets of the real line, the existence of such compression schemes
is independent of set theory. We conclude that the learnability of that class
with respect to the family of probability distributions of countable support is
independent of the set theory ZFC axioms.
  We also explore the existence of a "VC-dimension-like" parameter that
captures learnability in this setting. Our results imply that that there exist
no "finitary" combinatorial parameter that characterizes EMX learnability in a
way similar to the VC-dimension based characterization of binary valued
classification problems.
