Task 4

Let \(X\) be a finite set of some finite size \(k\). Let \(A\) be a learner that on a sample \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) outputs a function \(A(S)\) such that:

 If \(x=x_i\) for some \(i \in \{1, \ldots, m\}\) then \(A(S)(x)= y_i\),
 
 If \(x \notin \{x_1, \ldots, x_m\}\), then \(A(S)(x)\) is picked randomly with probability \(1/2\) for each label in \(\{0,1\}\). 

Given a function \(f: X \to \{0,1\}\), define a probability distribution \((U,f)\) over \(X \times \{0,1\}\) by assigning probability \(1/k\) to any pair \((x, f(x))\) and probability 0 to any \((x,y) \notin \{(x, f(x)): x \in X\}\).

Show that for every \(f: X \to \{0,1\}\) and \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\),

\[L_{(U,f)}(A(S)) -L_S(A(S)) \geq \frac{(k-m)}{2k}.\]

[Total 7 marks]