Prove the following generalization of Lemma 17.3. Assume that |K(x)| ≤ 1 for all x ∈ R, and suppose that K has total variation V <>
N1(, Fk, Xn 1 ) ≤ 3k 4b(b + ) 2e(b + ) k+1 6eV (b + ) 4k(d2+d+2)
Hint: Since K is of bounded variation it can be written as the difference of two monotone decreasing functions: K = K1 − K2 (see Figure 17.5). Let G be the collection of functions [x−c] T A[x−c] parametrized by c ∈ Rd and the nonnegative definite matrix A. Also, let FCi = {Ki(g(·)) : g ∈ G} (i = 1, 2) and let F = {K(g(·)) : g ∈ G}. By Lemma 16.4 for the covering number of sums of families of functions, we have
N1(, F, Xn 1 ) ≤ N1(/2, FC1, Xn 1 )N1(/2, FC2, Xn 1 )
because F⊂{f1−f2 : f1 ∈ FC1, f2 ∈ FC2}. Since G spans a (d2+d+1)-dimensional v ector space, by Lemma 9.5 the collection of sets
G+ = {{(x, t) : g(x) − t ≥ 0} : g ∈ G}
has VC dimension VG+ ≤ d2 + d + 2. Since Ki is monotone, it follows from Lemma 16.3 that VFC+ i ≤ d2 + d + 2, where the families of sets FC+ i are defined just as G+ with FCi in place of G. Let V1 and V2 be the total variations of K1 and K2, respectively. Then V = V1 + V2 and 0 ≤ Ki(x) + αi ≤ Vi, x ∈ R (i = 1, 2) for suitably chosen constants α1 and α2. Lemma 9.4 implies 0 ≤ f(x) ≤ B for all f ∈ F and x, thus
N1(, F, Xn 1 ) ≤ 3 2eB log 3eB VF+ ≤ 3 3eB 2VF+ .
Show that this implies that
N1(, F, Xn 1 ) ≤ 9 3eV 4(d2+d+2) .
Mimic the rest of the proof of Lemma 17.3 to obtain the conclusion.