Understanding Machine Learning: From Theory to Algorithms

13.7 Exercises 183

4.Strong Convexity with Respect to General Norms:
Throughout the section we used the` 2 norm. In this exercise we generalize
some of the results to general norms. Let‖·‖be some arbitrary norm, and letf
be a strongly convex function with respect to this norm (see Definition 13.4).

1. Show that items 2–3 of Lemma 13.5 hold for every norm.
   2.(*)Give an example of a norm for which item 1 of Lemma 13.5 does not
   hold.


2. LetR(w) be a function that is (2λ)-strongly convex with respect to some
   norm‖·‖. LetAbe an RLM rule with respect toR, namely,

A(S) = argmin

w

(LS(w) +R(w)).

Assume that for everyz, the loss function`(·,z) isρ-Lipschitz with respect

to the same norm, namely,

∀z,∀w,v, `(w,z)−`(v,z)≤ρ‖w−v‖.

Prove thatAis on-average-replace-one-stable with rate^2 ρ

2

λm.

4.(*)Letq∈(1,2) and consider the`q-norm

‖w‖q=

(d

∑

i=1

|wi|q

) 1 /q

.

It can be shown (see, for example, Shalev-Shwartz (2007)) that the function

R(w) =

1

2(q−1)

‖w‖^2 q

is 1-strongly convex with respect to‖w‖q. Show that ifq=log(log(d)d−) 1 then

R(w) is

(

1

3 log(d)

)

-strongly convex with respect to the` 1 norm overRd.