Learnable function class

In statistical learning theory, a learnable function class is a set of functions for which an algorithm can be devised to asymptotically minimize the expected risk, uniformly over all probability distributions. The concept of learnable classes are closely related to regularization in machine learning, and provides large sample justifications for certain learning algorithms.

Definition

Background

Let [math]\displaystyle{ \Omega = \mathcal{X} \times \mathcal{Y} = \{(x, y)\} }[/math] be the sample space, where [math]\displaystyle{ y }[/math] are the labels and [math]\displaystyle{ x }[/math] are the covariates (predictors). [math]\displaystyle{ \mathcal{F} = \{ f: \mathcal{X} \mapsto \mathcal{Y} \} }[/math] is a collection of mappings (functions) under consideration to link [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math]. [math]\displaystyle{ L: \mathcal{Y} \times \mathcal{Y} \mapsto \mathbb{R} }[/math] is a pre-given loss function (usually non-negative). Given a probability distribution [math]\displaystyle{ P(x, y) }[/math] on [math]\displaystyle{ \Omega }[/math], define the expected risk [math]\displaystyle{ I_P( f ) }[/math] to be:

[math]\displaystyle{ I_P (f) = \int L( f(x), y ) d P( x, y ) }[/math]

The general goal in statistical learning is to find the function in [math]\displaystyle{ \mathcal{F} }[/math] that minimizes the expected risk. That is, to find solutions to the following problem:

[math]\displaystyle{ \hat{f} = \arg \min_{f \in \mathcal{F}} I_P (f) }[/math]

But in practice the distribution [math]\displaystyle{ P }[/math] is unknown, and any learning task can only be based on finite samples. Thus we seek instead to find an algorithm that asymptotically minimizes the empirical risk, i.e., to find a sequence of functions [math]\displaystyle{ \{\hat{f}_n\}_{n=1}^\infty }[/math] that satisfies

[math]\displaystyle{ \lim_{n \rightarrow \infty} \mathbb{P}( I_P (\hat{f}_n) - \inf_{f \in \mathcal{F}}I_P( f ) \gt \epsilon ) = 0 }[/math]

One usual algorithm to find such a sequence is through empirical risk minimization.

Learnable function class

We can make the condition given in the above equation stronger by requiring that the convergence is uniform for all probability distributions. That is:

[math]\displaystyle{ \lim_{n \rightarrow \infty} \sup_P \mathbb{P}( I_P (\hat{f}_n) - \inf_{f \in \mathcal{F}}I_P( f ) \gt \epsilon ) = 0 }[/math]

(1)

The intuition behind the more strict requirement is as such: the rate at which sequence [math]\displaystyle{ \{\hat{f}_n\} }[/math] converges to the minimizer of the expected risk can be very different for different [math]\displaystyle{ P(x, y) }[/math]. Because in real world the true distribution [math]\displaystyle{ P }[/math] is always unknown, we would want to select a sequence that performs well under all cases.

However, by the no free lunch theorem, such a sequence that satisfies (1) does not exist if [math]\displaystyle{ \mathcal{F} }[/math] is too complex. This means we need to be careful and not allow too "many" functions in [math]\displaystyle{ \mathcal{F} }[/math] if we want (1) to be a meaningful requirement. Specifically, function classes that ensure the existence of a sequence [math]\displaystyle{ \{\hat{f}_n\} }[/math] that satisfies (1) are known as learnable classes.

It is worth noting that at least for supervised classification and regression problems, if a function class is learnable, then the empirical risk minimization automatically satisfies (1). Thus in these settings not only do we know that the problem posed by (1) is solvable, we also immediately have an algorithm that gives the solution.

Interpretations

If the true relationship between [math]\displaystyle{ y }[/math] and [math]\displaystyle{ x }[/math] is [math]\displaystyle{ y \sim f^*(x) }[/math], then by selecting the appropriate loss function, [math]\displaystyle{ f^* }[/math] can always be expressed as the minimizer of the expected loss across all possible functions. That is,

[math]\displaystyle{ f^* = \arg\min_{f \in \mathcal{F}^*} I_P( f ) }[/math]

Here we let [math]\displaystyle{ \mathcal{F}^* }[/math] be the collection of all possible functions mapping [math]\displaystyle{ \mathcal{X} }[/math] onto [math]\displaystyle{ \mathcal{Y} }[/math]. [math]\displaystyle{ f^* }[/math] can be interpreted as the actual data generating mechanism. However, the no free lunch theorem tells us that in practice, with finite samples we cannot hope to search for the expected risk minimizer over [math]\displaystyle{ \mathcal{F}^* }[/math]. Thus we often consider a subset of [math]\displaystyle{ \mathcal{F}^* }[/math], [math]\displaystyle{ \mathcal{F} }[/math], to carry out searches on. By doing so, we risk that [math]\displaystyle{ f^* }[/math] might not be an element of [math]\displaystyle{ \mathcal{F} }[/math]. This tradeoff can be mathematically expressed as

[math]\displaystyle{ I_P (\hat{f}_n) - \inf_{f \in \mathcal{F}^*}I_P( f ) = \underbrace{I_P (\hat{f}_n) - \inf_{f \in \mathcal{F}}I_P( f )}_{(a)} + \underbrace{\inf_{f \in \mathcal{F}}I_P( f ) - \inf_{f \in \mathcal{F}^*}I_P( f )}_{(b)} }[/math]

(2)

In the above decomposition, part [math]\displaystyle{ (b) }[/math] does not depend on the data and is non-stochastic. It describes how far away our assumptions ([math]\displaystyle{ \mathcal{F} }[/math]) are from the truth ([math]\displaystyle{ \mathcal{F}^* }[/math]). [math]\displaystyle{ (b) }[/math] will be strictly greater than 0 if we make assumptions that are too strong ([math]\displaystyle{ \mathcal{F} }[/math] too small). On the other hand, failing to put enough restrictions on [math]\displaystyle{ \mathcal{F} }[/math] will cause it to be not learnable, and part [math]\displaystyle{ (a) }[/math] will not stochastically converge to 0. This is the well-known overfitting problem in statistics and machine learning literature.

Example: Tikhonov regularization

A good example where learnable classes are used is the so-called Tikhonov regularization in reproducing kernel Hilbert space (RKHS). Specifically, let [math]\displaystyle{ \mathcal{F^*} }[/math] be an RKHS, and [math]\displaystyle{ ||\cdot||_2 }[/math] be the norm on [math]\displaystyle{ \mathcal{F^*} }[/math] given by its inner product. It is shown in that [math]\displaystyle{ \mathcal{F} = \{f: ||f||_2 \leq \gamma \} }[/math] is a learnable class for any finite, positive [math]\displaystyle{ \gamma }[/math]. The empirical minimization algorithm to the dual form of this problem is

[math]\displaystyle{ \arg\min_{f \in \mathcal{F}^*} \left\{ \sum_{i = 1}^n L( f(x_i), y_i) + \lambda ||f||_2 \right\} }[/math]

This was first introduced by Tikhonov to solve ill-posed problems. Many statistical learning algorithms can be expressed in such a form (for example, the well-known ridge regression).

The tradeoff between [math]\displaystyle{ (a) }[/math] and [math]\displaystyle{ (b) }[/math] in (2) is geometrically more intuitive with Tikhonov regularization in RKHS. We can consider a sequence of [math]\displaystyle{ \{\mathcal{F}_\gamma\} }[/math], which are essentially balls in [math]\displaystyle{ \mathcal{F^*} }[/math] with centers at 0. As [math]\displaystyle{ \gamma }[/math] gets larger, [math]\displaystyle{ \mathcal{F}_\gamma }[/math] gets closer to the entire space, and [math]\displaystyle{ (b) }[/math] is likely to become smaller. However we will also suffer smaller convergence rates in [math]\displaystyle{ (a) }[/math]. The way to choose an optimal [math]\displaystyle{ \gamma }[/math] in finite sample settings is usually through cross-validation.

Relationship to empirical process theory

Part [math]\displaystyle{ (a) }[/math] in (2) is closely linked to empirical process theory in statistics, where the empirical risk [math]\displaystyle{ \{\sum_{i=1}^n L( y_i, f(x_i) ), f \in \mathcal{F}\} }[/math] are known as empirical processes. In this field, the function class [math]\displaystyle{ \mathcal{F} }[/math] that satisfies the stochastic convergence

[math]\displaystyle{ \sup_P \mathbb{E} \sup_{f \in \mathcal{F}} | \sum_{i=1}^n L( y_i, f(x_i) ) - I_P(f) | = 0 }[/math]

(3)

are known as uniform Glivenko–Cantelli classes. It has been shown that under certain regularity conditions, learnable classes and uniformly Glivenko-Cantelli classes are equivalent. Interplay between [math]\displaystyle{ (a) }[/math] and [math]\displaystyle{ (b) }[/math] in statistics literature is often known as the bias-variance tradeoff.

However, note that in the authors gave an example of stochastic convex optimization for General Setting of Learning where learnability is not equivalent with uniform convergence.