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
- The functionf(w) =λ‖w‖^2 is 2 λ-strongly convex.
- Iffisλ-strongly convex andgis convex, thenf+gisλ-strongly convex.
- 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