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 E_P (h) is probably approximately equal to sup{E_P (h) : h in F}. This Expectation Maximization (EMX) problem captures many well studied learning problems; in fact, it is equivalent to Vapnik’s general setting of learning. We focus on the case where the functions in F are Boolean, which generalize classification problems. We study the interaction between the statistical sample complexity of F and its combinatorial structure. In particular we explore the a existence of a “VC-dimension-like” parameter that captures learnability in this setting. 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). This result implies 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. The talk is based on joint work with Pavel Hrubeˇs, Shay Moran, Amir Shpilka, and Amir Yehudayoff