Understanding Machine Learning: From Theory to Algorithms

170 Convex Learning Problems

the set of all Turing machines. Define the loss function as follows. For every

Turing machineT∈Z, let`(0,T) = 1 ifThalts on the input 0 and`(0,T) = 0

ifTdoesn’t halt on the input 0. Similarly, let`(1,T) = 0 ifThalts on the

input 0 and`(1,T) = 1 ifTdoesn’t halt on the input 0. Finally, forh∈(0,1),

let`(h,T) =h`(0,T) + (1−h)`(1,T).

1. Show that the resulting learning problem is convex-Lipschitz-bounded.


2. Show that no computable algorithm can learn the problem.