Given a <hypothesis class> $\mathcal H$ and a <loss function> $\ell$, its loss class is the <function class>
$$
\mathcal F=\{z\mapsto\ell(h,z):h\in\mathcal H\}.
$$
It lets properties of a learning problem be studied through the random fluctuations of the losses themselves.


Loss class

{c}
{wiki}

For <independent and identically distributed random variables> $Z_1,\ldots,Z_n$ and independent <Rademacher random variable>[Rademacher signs] $\varepsilon_1,\ldots,\varepsilon_n$, the Rademacher complexity of a <function class> $\mathcal F$ is
$$
\mathcal R_n(\mathcal F)
=\mathbb E_{Z,\varepsilon}\left[
\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n\varepsilon_i f(Z_i)
\right].
$$
It measures how strongly the class can correlate with independent random signs on a random sample.


Rademacher complexity

{c}

For an <independent and identically distributed random variables>[i.i.d. sample] and an integrable <function class> $\mathcal F$,
$$
\mathbb E\sup_{f\in\mathcal F}
\frac1n\sum_{i=1}^n\bigl(f(Z_i)-\mathbb Ef(Z_i)\bigr)
\leq2\mathcal R_n(\mathcal F).
$$
Introduce an independent ghost sample, replace each expectation by its ghost-sample average using <Jensen inequality>, and then multiply each paired difference by an independent <Rademacher random variable>[Rademacher sign]. Splitting the resulting supremum into its two sample contributions gives the factor two.


Rademacher symmetrization inequality

= Map
{synonym}

A function class is a <set> whose elements are functions, usually sharing a common domain and codomain.


Codex @codex  0

 Incoming links: Function class