When does the optimal model exist in learning theory?

Question

In the context of learning theory, we usually have: data $(x,y)\sim P(x,y)$, with $x\in\mathcal{X}\subseteq\mathbb{R}^d$ and $y\in\mathcal{Y}\subseteq\mathbb{R}^k$, a hypothesis class $\mathcal{F}\subseteq\Omega$, where $\Omega$ is the set of measurable functions $\mathcal{X}\rightarrow\mathcal{Y}$ and a loss function $\ell:\mathbb{R}^k\times\mathbb{R}^k\to\mathbb{R}_+$. Also, we define the functional $R$, the risk, such that $R(f)=\mathbb{E}_{xy}[\ell(y,f(x))]$

A Bayes model $f^*$ is defined as any function in $\Omega$ such that $\forall f\in\Omega$: $R(f^*)\leq R(f)$

A "best in class" $f^*_{F}$ is defined as any function in $\mathcal{F}$ such that $\forall f\in\mathcal{F}$: $R(f^*_F)\leq R(f)$

Given the random variable $D\sim P(x,y)^n$, define $R_{emp}(f; D)=\frac{1}{N}\sum_{i=1}^N\ell(y_i,f(x_i))$. Now, an empirical risk minimiser $f_{erm}$ is defined as any function in $\mathcal{F}$ such that $\forall f\in\mathcal{F}$: $R_{emp}(f_{erm})\leq R_{emp}(f)$.

My question is: what are the conditions needed to guarantee the existence of these functions? I'm not interested in the uniqueness. If one of these conditions is the continuity of $\ell$, do these quantities exist also for the $0/1$ loss?

Answer 1

Existence of minimizers is studied in the context of calculus of variations. There is quite some theory about it. The so called "direct method" goes as follows

• Choose a topology on the hypothesis space.
• Show that the hypothesis space is compact in that topology (or show that there is compact set in the hypothesis space in which any minimizer has to be, e.g. by considering level sets of the objective).
• Show that the objective is lower semi continuous in that topology.

The choice of the topology is often crucial and not obvious. Sometimes there is natural choice (e.g. if the hypothesis space is contained in a reproducing kernel Hilbert space) but then this may not work and one needs to look for a different topology.