Measure-theoretically rigorous treatment of statistical learning theory My main source on statistical learning theory has been Shwartz/Ben-David. This is a good book but it's a little vague from a measure-theoretic point of view. For example, in the definition of PAC learnability (Definition 3.1), learning happens with respect to "every distribution over $X$", $X$ being the input domain, which is just a set. No measure-space structure is mentioned for $X$, and in particular it's not clear if "every distribution" means all possible measurable-space structures on $X$, or just one specific sigma-algebra.
For another example, the idea of a learning algorithm as something mapping training sets to hypothesis functions has no measurability assumptions on it, yet it requires at least some, since we want to write down expressions like "probability (with respect to the random training set) that the test error of the returned hypothesis is less than $\epsilon$", which implies the test error is a measurable random variable.
I also looked at Vapnik, who seems to generally work with density functions, not abstract measure spaces.
Is there a measure-theoretic treatment of this type of material, either as a book or a series of articles?
 A: I will try to explain systematically, so apologies for going over things you probably already know.
To construct a probability space, $\Omega$, we first choose some elementary subsets/events appropriate to the situation; for example, in a coin toss the events might be heads and tails. We then define a probability measure, $\mathbb{P}$, on these events. Finally, a sigma-algebra, $\Sigma,$ is generated by admitting the subsets/events resulting from all possible complementation, (countable) union and intersection.  Not all of the events will always be practically relevant, but it doesn't hurt that they exist.
While we can largely work on intuition in a simple example such as "heads or tails", to scale the approach we define a function $X:\Omega\mapsto\mathbb{R}$ which assigns a single value to each of these events. For example, $\mathbb{P}(heads)=1$ and $\mathbb{P}(tails)=0$, with the induced sigma-algebra additionally consisting of the empty set and the event $\{heads, tails\}$ (i.e. $\Omega$ itself). $X$ is, of course, called a random variable.
To define events on the entire real line we take $X$ to be the identity function. The elementary events can, for example, be those of the form $\{(-\infty,a)\}:a\in\mathbb{R}$. These generate the Borel sigma-algebra.  It would be endlessly tedious to assign probabilities for each of these elementary events, but we don't need to, since the structure can be induced indirectly (see below).
Now, the events $\{\omega\in\Omega:X(\omega)\in(-\infty,a),a\in\mathbb{R}\}$ exist in $\Sigma$, and $X$ is consequently a $\Sigma$-measurable function. The $\omega$ references tend to be omitted, which results in a reference to events $\{X\in(-\infty,a):a\in\mathbb{R}\}$.
I hope this addresses your question regarding what sigma-algebra a random variable tends to be defined on.  There are a few loose ends, though. Let's call $F:\mathbb{R}\mapsto[0,1]:F(a)=\mathbb{P}(X<a)$ the distribution function of $X$. Let's take a function that is monotonic, approaches 0 as $a\rightarrow-\infty$, approaches 1 as $a\rightarrow\infty$, and is right-continuous. The Skorokhod Representation Theorem establishes that any such function can be uniquely associated with a random variable possessing this distribution function. This means we can avoid worrying about elementary events when it is more convenient to specify a probability space based on its distribution function instead.
The last thing that might be unclear is why we use integration with respect to the Lebesgue measure, $\lambda$, to obtain probabilities from the density functions pertaining to continuous distributions. This comes from the Radon-Nikodym Theorem.  So long as $\Sigma$ is the Borel sigma-algebra and, for $A\in\Sigma$, $\lambda(A)=0\Rightarrow\mathbb{P}(A)=0$ (i.e. $\mathbb{P}$ is absolutely continuous with respect to $\lambda$), there exists a Radon-Nikodym derivative $f$ - the density function - whose integrals with respect to $\lambda$ over the Borel sets $A\in\Sigma$ return the values $\{\mathbb{P}(A):A\in\Sigma\}$.
Discrete distributions like the "heads" and "tails" example do not generate the Borel sigma-algebra, which is why they don't have density functions defined with respect to the Lebesgue measure. Of course, one could set up an alternative system based on the counting measure that would work for suitable discrete distributions. In fact, this gives rise to the probability mass function in cases where absolute continuity of the discrete probability measure with respect to the counting measure applies.
In his Statistical Learning Theory (1998), Vapnik presents the measure-theoretic framework for probability work from page 59, although it's necessarily rather abridged.
