Understanding Machine Learning: From Theory to Algorithms

13.3 Tikhonov Regularization as a Stabilizer 175

definition13.4 (Strongly Convex Functions) A functionfisλ-strongly con-
vex if for allw,uandα∈(0,1) we have

f(αw+ (1−α)u)≤αf(w) + (1−α)f(u)−λ

2

α(1−α)‖w−u‖^2.

Clearly, every convex function is 0-strongly convex. An illustration of strong
convexity is given in the following figure.

f(w)

f(u)

w

αw+ (1−α)u

u

≥λ 2 α(1−α)‖u−w‖^2

The following lemma implies that the objective of RLM is (2λ)-strongly con-
vex. In addition, it underscores an important property of strong convexity.

lemma13.5

1. The functionf(w) =λ‖w‖^2 is 2 λ-strongly convex.


2. Iffisλ-strongly convex andgis convex, thenf+gisλ-strongly convex.


3. Iffisλ-strongly convex anduis a minimizer off, then, for anyw,

f(w)−f(u)≥λ

2

‖w−u‖^2.

Proof The first two points follow directly from the definition. To prove the last
point, we divide the definition of strong convexity byαand rearrange terms to
get that

f(u+α(w−u))−f(u)

α

≤f(w)−f(u)−

λ

2

(1−α)‖w−u‖^2.

Taking the limitα→0 we obtain that the right-hand side converges tof(w)−
f(u)−λ 2 ‖w−u‖^2. On the other hand, the left-hand side becomes the derivative
of the functiong(α) =f(u+α(w−u)) atα= 0. Sinceuis a minimizer off,
it follows thatα= 0 is a minimizer ofg, and therefore the left-hand side of the
preceding goes to zero in the limitα→0, which concludes our proof.

We now turn to prove that RLM is stable. LetS= (z 1 ,...,zm) be a training
set, letz′be an additional example, and letS(i)= (z 1 ,...,zi− 1 ,z′,zi+1,...,zm).
LetAbe the RLM rule, namely,

A(S) = argmin

w

(

LS(w) +λ‖w‖^2

)

.