Page 158 - Understanding Machine Learning

Regularization and Stability
140

On the other hand, we can write

E[L S (A(S))] = E [ (A(S),z i )].
S S,i

Combining the two equations we conclude our proof.

When the right-hand side of Equation (13.6)issmall, we say that A is a sta-
ble algorithm – changing a single example in the training set does not lead to a
significant change. Formally,

Definition 13.3 (On-Average-Replace-One-Stable). Let
: N → R be a monotoni-
cally decreasing function. We say that a learning algorithm A is on-average-replace-
one-stable with rate
(m) if for every distribution D

(i)
E [ (A(S ,z i )) − (A(S),z i )] ≤
(m).

(S,z )∼D m+1 ,i∼U(m)
Theorem 13.2 tells us that a learning algorithm does not overfit if and only if
it is on-average-replace-one-stable. Of course, a learning algorithm that does not
overfit is not necessarily a good learning algorithm – take, for example, an algo-
rithm A that always outputs the same hypothesis. A useful algorithm should find
a hypothesis that on one hand fits the training set (i.e., has a low empirical risk)
and on the other hand does not overfit. Or, in light of Theorem 13.2, the algorithm
should both fit the training set and at the same time be stable. As we shall see, the
parameter λ of the RLM rule balances between fitting the training set and being
stable.

13.3 TIKHONOV REGULARIZATION AS A STABILIZER
In the previous section we saw that stable rules do not overfit. In this section we
2
show that applying the RLM rule with Tikhonov regularization, λ w , leads to a
stable algorithm. We will assume that the loss function is convex and that it is either
Lipschitz or smooth.
The main property of the Tikhonov regularization that we rely on is that it makes
the objective of RLM strongly convex, as defined in the following.

Definition 13.4 (Strongly Convex Functions). A function f is λ-strongly convex if
for all w, u,and α ∈ (0, 1) we have

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

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