In an ML problem as specified in Section 5.1, we use f  to denote the model obtained from the ERM procedure in Eq. (5.6):

f  = arg min f 2H Remp¹ f jDNº, and we use ˆ f to denote the best possible model in the model space H, that is:

ˆ f = arg min f 2H R¹ f º

We further assume the unknown target function is denoted as ¯ f . By definition, we have R¹ ¯ f º = 0 and Remp¹ ¯ f jDNº = 0.We can define several types of errors in ML as follows:

I Generalization error Eg:

Eg =

R¹ f º ???? Remp¹ f  jDNº

I Estimation error Ee:

Ee =

R¹ f º ???? R¹ ˆ f º

I Approximation error Ea:

Ea =

R¹ ˆ f º ???? R¹ ¯ f º

= R¹ ˆ f º

Use words to explain the physical meanings of these errors.

Section 5.3 showed that Eg  B¹N,Hº, where B¹N,Hº is the generalization bound defined in Eq. (5.10). In this exercise, prove the following properties:

a. R¹ f º  Ee + Ea

b. Remp¹ f  jDNº  Eg + Ee + Ea

c. Ee  2
B¹N,Hº