let be convex function and let be random variable use the subgradient definition of convexity to prove jensen' inequalityjensen' inequality (xh(ex( using jensen' inequalityshow that the kullback-leibler divergence between probability densities and is always positivethat ise ln ( (xwhere vapnikchernovenkis bound the purpose of this exercise is to prove the following vapnik-chernovenkis boundfor any finite class (containing only finite number |gof possible functionsand general bounded loss functionl loss uthe expected statistical error is bounded from above according to( ln( | | `(gtn `( ( note how this bound conveniently does not depend on the distribution of the training set tn (which is typically unknown)but only on the complexity ( cardinalityof the class we can break up the proof of ( into the following four parts(afor general function class gtraining set risk function `and training loss ` we haveby definition`(gg `(gand ` (ggt ` (gfor all show that `(ggt `(gg sup |` ( `( )` (gg `(gg )gg where we used the notation sup (supremumfor the least upper bound since ` (ge`( )we obtainafter taking expectations on both sides of the inequality abovee `(ggt `(gg sup |` ( `( )gg hoeffding' inequality (bif is zero-mean random variable taking values in the interval [lu]then the following hoeffding' inequality states that the moment generating function satisfies ( ) exp tx ( prove this result by using the fact that the line segment joining points (lexp(tl)and (uexp(tu)bounds the convex function exp(txfor [lu]that isetx etl - - etu - - [lu(clet zn be (possibly dependent and non-identically distributedzero-mean random variables with moment generating functions that satisfy exp(tzk exp( / for all and some parameter use jensen' inequality ( to prove that for any