This blog is about the basic of machine learning theory, including probably approximately correct (PAC), generalization bound on finite (PAC learnable) and infinite space (Rademacher complexity, growth function, VC-dimension), referenced the excellent machine learning lecture notes at Tsinghua University by Mingsheng Long.
We know the components of learning, we need a hypothesis space , a learning algorithm……But what things can be learned efficiently, under which condition? And are these learning guaranteed?
From statistical machine learning view, there is a latent data generating distribution $D_{x\times y}$, all training and testing samples are generated from this distribution. So when we learn a model on training set $D_{x\times y}$, this will not work for another distribution $D^{'}_{x\times y}$.
As we all know, learning is not fitting. So what is the truth of learning?
Here lies a trade-off between performance and model complexity :

When we do the training , we get empirical error on the known dataset
$h$ is the hypothesis, $D_n$ is the dataset’s distribution
$$ \hat{\epsilon}{D_n}(h)=\frac{1}{n}\sum{i=1}^{n}l(h(x_i),y_i) $$
The final goal of training is to get the smallest expected error:
$$ \epsilon_{D_n}(h)=E_{(x,y)\sim D_{(x,y)}}l(h(x),y) $$