9.3 Alternative multi-class boosting algorithm. Consider the objective function G dened for any sample S = ((x1; y1); : : : ; (xm; ym)) 2 (X  Y)m and =

(1; : : : ; n) 2 Rn, n  1, by G() =

Xm i=1 e????1 k

Pk l=1 yi[l]fn(xi;l) =

Xm i=1 e????1 k

Pk l=1 yi[l]

Pn t=1 tht(xi;l): (9.25)

Use the convexity of the exponential function to compare G with the objective function F dening AdaBoost.MH. Show that G is a convex function upper bounding the multi-label multi-class error. Discuss the properties of G and derive an algorithm dened by the application of coordinate descent to G. Give theoretical guarantees for the performance of the algorithm and analyze its running-time complexity when using boosting stumps.