Statistical Learning Theory 14 NTK and Kernels A The Singular Value Decomposition

Chapter 15 Stability

We’ve argued that it’s important to consider algorithm-specific bounds: sometimes $\mathcal{H}$ is too big for uniform convergence, but $\mathcal{A}$ still learns well. This is true both for deep learning and for, say, kernel ridge regression with a universal kernel,

\operatorname*{arg\,min}_{h\in\mathcal{F}}L_{S}^{\mathit{sq}}(h)+\frac{\lambda% }{2}\lVert h\rVert_{\mathcal{F}}^{2}.

This algorithm could feasibly return any

h\in\mathcal{F}

,¹¹1Consider a

{\mathcal{D}}

where

y\mid x=h^{*}(x)

, the distribution on

x

is “sufficiently broad,” and

\lambda\to 0

m\to\infty

. If this kernel is also continuous,

h^{*}

is the unique minimizer of

L_{\mathcal{D}}

, and checking the details in some asymptotic analysis will give us that

\hat{h}_{S}\to h^{*}

. and so a typical uniform convergence analysis will have to use

\mathcal{H}=\mathcal{F}

. But we know that the VC dimension and Rademacher complexity of

\mathcal{F}

are both infinite for a universal kernel, so a uniform convergence analysis won’t tell us anything useful.

We can generalize this setting a bit to regularized loss minimization (RLM):

\operatorname*{arg\,min}_{h\in\mathcal{H}}L_{S}(h)+\lambda R(h).

(RLM)

(Kernel ridge regression uses square loss, with

\mathcal{H}

the RKHS

\mathcal{F}

, and

R(h)=\frac{1}{2}\lVert h\rVert_{\mathcal{F}}^{2}

. We’ll use the factor of 1/2 because it makes

R

1-strongly convex, as in proposition C.9.)

We’ve appealed before to a connection between RLM and constrained ERM:

\operatorname*{arg\,min}_{h\in\mathcal{H}:R(h)\leq B}L_{S}(h).

The two problems are Lagrange dual to each other: for any

\lambda

, there is some

B

such that the solutions agree, and vice versa. But converting between

\lambda

and

B

generally requires actually solving the problem, (RLM) is typically easier computationally, and it’s usually easier to choose a good

\lambda

than to choose a good

B

. So, we’d like to come up with a direct analysis of (RLM) for its own sake, in addition to developing techniques that will help with other analyses.

Randomized algorithms

Our analyses of ERM applied to any empirical risk minimizer, so exactly what the algorithm did didn’t really matter. When we’re dealing with specific algorithms, though, it’s important to note that these algorithms might be randomized: for instance, stochastic gradient descent sees points in a random order, and might start at a random location.

Notationally, we’ll use $\mathcal{A}(S)$ to denote the potentially random result of the algorithm on a set $S$ : even for a fixed $S$ , the result could be a random variable. Something like $\operatorname*{\mathbb{E}}_{\mathcal{A}}\ell(\mathcal{A}(S),z)$ will denote the mean of the loss on a fixed $z$ when training on a fixed $S$ . We’ll always assume that this randomness is independent of $S$ (other than its size): for instance, this will be the random seed that determines that pattern in which we access the $z_{i}$ . If $\mathcal{A}$ is deterministic, it’s just a point-mass distribution.

15.1 Definitions of Stability

The general intuition we’re going to use is algorithmic stability: if two training sets $S$ and $S^{\prime}$ are “similar,” then $\mathcal{A}(S)$ and $\mathcal{A}(S^{\prime})$ will also be “similar.” Then $\mathcal{A}$ doesn’t “depend too much” on the particular sample set, and so it’s likely to not really overfit too much. (Defining “similar” in different ways will yield different notions of stability.)

In (RLM), the regularizer $R(h)$ “stabilizes” the algorithm. For instance, if you run linear regression on “multicollinear” data (where the $n\times d$ data matrix isn’t full rank), there are multiple possible solutions: the algorithm isn’t stable. But if you add the regularizer $\lambda\lVert w\rVert^{2}$ , then there’s always a unique solution that doesn’t depend too much on any one input point.

We’ll use the following notation for changing single sample points:

\text{If }S=(z_{1},\dots,z_{m}),\text{ then }S^{(i\leftarrow z^{\prime})}=(z_{% 1},\dots,z_{i-1},z^{\prime},z_{i+1},\dots,z_{m}).

Now, notice the following basically-trivial result:

Proposition 15.1.

For any distribution

{\mathcal{D}}

and learning algorithm

\mathcal{A}

\operatorname*{\mathbb{E}}_{S\sim{\mathcal{D}}^{m},\,\mathcal{A}}[L_{\mathcal{% D}}(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))]=\operatorname*{\mathbb{E}}_{\begin{% subarray}{c}S\sim{\mathcal{D}}^{m},\,z^{\prime}\sim{\mathcal{D}}\\ i\sim\operatorname{Unif}([m]),\,\mathcal{A}\end{subarray}}\left[\ell(\mathcal{% A}(S^{(i\leftarrow z^{\prime})}),z_{i})-\ell(\mathcal{A}(S),z_{i})\right].

On the right-hand side, the first loss term is the generalization loss, since

\mathcal{A}(S^{(i\leftarrow z^{\prime})})

doesn’t train on

z_{i}

. The second one is the training error, since

\mathcal{A}(S)

does train on

z_{i}

Proof.

Splitting up the expectation, the second term has

\operatorname*{\mathbb{E}}_{\begin{subarray}{c}S\sim{\mathcal{D}}^{m}\\ i\sim\operatorname{Unif}([m]),\,\mathcal{A}\end{subarray}}\left[\ell(\mathcal{% A}(S),z_{i})\right]=\operatorname*{\mathbb{E}}_{S\sim{\mathcal{D}}^{m},\,% \mathcal{A}}\left[\frac{1}{m}\sum_{i=1}^{m}\ell(\mathcal{A}(S),z_{i})\right]=% \operatorname*{\mathbb{E}}_{S\sim{\mathcal{D}}^{m},\,\mathcal{A}}\left[L_{S}(% \mathcal{A}(S))\right].

The first is

\operatorname*{\mathbb{E}}_{\begin{subarray}{c}S\sim{\mathcal{D}}^{m},\,z^{% \prime}\sim{\mathcal{D}}\\ i\sim\operatorname{Unif}([m]),\,\mathcal{A}\end{subarray}}\left[\ell(\mathcal{% A}(S^{(i\leftarrow z^{\prime})}),z_{i})\right]=\operatorname*{\mathbb{E}}_{% \begin{subarray}{c}S\sim{\mathcal{D}}^{m},\,z^{\prime}\sim{\mathcal{D}}\\ i\sim\operatorname{Unif}([m]),\,\mathcal{A}\end{subarray}}\left[\ell(\mathcal{% A}(S),z^{\prime})\right]=\operatorname*{\mathbb{E}}_{S\sim{\mathcal{D}}^{m},\,% \mathcal{A}}L_{\mathcal{D}}(\mathcal{A}(S)),

where we switched the names of the iid variables

z_{i}

and

z^{\prime}

in the first equality. ∎

This motivates what is basically the weakest useful notion of stability:

Definition 15.2.

$\mathcal{A}$ is $\varepsilon(m)$ -on-average-replace-one stable if for all ${\mathcal{D}}$ ,

\operatorname*{\mathbb{E}}_{\begin{subarray}{c}S\sim{\mathcal{D}}^{m},\,z^{% \prime}\sim{\mathcal{D}}\\ i\sim\operatorname{Unif}([m]),\,\mathcal{A}\end{subarray}}\left[\ell(\mathcal{% A}(S^{(i\leftarrow z^{\prime})}),z_{i})-\ell(\mathcal{A}(S),z_{i})\right]\leq% \varepsilon(m).

We say an algorithm is on-average-replace-one stable if

\lim_{m\to\infty}\varepsilon(m)=0

for all

{\mathcal{D}}

Thus, an $\varepsilon(m)$ -on-average-replace-one stable algorithm will have small average-case generalization gap $L_{\mathcal{D}}(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))$ : it won’t overfit much, on average. Like for uniform convergence, there are bad stable algorithms: consider $\mathcal{A}$ that always returns $x\mapsto 0$ regardless of $S$ . But a stable algorithm that also usually fits its training data, one with small $\operatorname*{\mathbb{E}}_{S}L_{S}(\mathcal{A}(S))$ , will have small $\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))$ . This is the notion studied by Chapter 13 of [SB14]; also see [SSS+10].

Notice that since proposition 15.1 is an equality, any algorithm where

\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))

is always close to

\operatorname*{\mathbb{E}}_{S}L_{S}(\mathcal{A}(S))

will necessarily be on-average replace-one stable; this is what I meant by it being the weakest notion. There’s also a more commonly considered but much stronger notion of stability:

Definition 15.3.

²²2[BE02] defined

\beta

as the change from removing the

i

th element, which implies this one with a factor of

2

difference; [EEP05] extended to random algorithms. This version (without the 2) is called strongly-uniform-replace-one stable by [SSS+10].

A learning algorithm $\mathcal{A}$ is $\beta(m)$ -uniformly stable if for all $m\geq 1$ ,

\sup_{\begin{subarray}{c}S\in\mathcal{Z}^{m},\,i\in[m]\\ z,z^{\prime}\in\mathcal{Z}\end{subarray}}\lvert\operatorname*{\mathbb{E}}_{% \mathcal{A}}\ell(\mathcal{A}(S^{(i\leftarrow z^{\prime})}),z)-\operatorname*{% \mathbb{E}}_{\mathcal{A}}\ell(\mathcal{A}(S),z)\rvert\leq\beta(m).

We say an algorithm is uniformly stable if

\lim_{m\to\infty}\beta(m)=0

That is, changing one point in any training set gives you a hypothesis that looks almost the same for any test point.

If you know differential privacy, this might seem familiar: it turns out that an

(\varepsilon,\delta)

-differentially private algorithm with loss

\ell\in[0,1]

(e^{\varepsilon}-1+\delta)

-uniformly stable ([WLF16], Lemma 23).

\mathcal{A}

\beta(m)

-uniformly stable, it’s

\varepsilon(m)

-on-average-replace-one stable, just by plugging in the definitions. But the converse is not true. (There are also in-between notions; see [BE02, SSS+10].)

If we do have uniform stability, though, we can get stronger bounds:

Theorem 15.4 ([BE02], basically).

Suppose that $\ell(h,z)\in[a,b]$ almost surely. Let $\mathcal{A}$ be $\beta(m)$ -uniformly stable. Then, with probability at least $1-\delta$ over the choice of training points $S\sim{\mathcal{D}}^{m}$ ,

\operatorname*{\mathbb{E}}_{\mathcal{A}}[L_{\mathcal{D}}(\mathcal{A}(S))-L_{S}% (\mathcal{A}(S))]\leq\beta(m)+\left(2m\beta(m)+b-a\right)\sqrt{\frac{1}{2m}% \log\frac{1}{\delta}}.

The best case for this bound is when

\beta(m)=\operatorname{\mathcal{O}}(1/m)

, in which case you get a usual

\operatorname{\mathcal{O}}(1/\sqrt{m})

rate. That turns out to be often the case.

Proof.

We’ll apply McDiarmid’s inequality (theorem 5.6) to the function

f(S)=\operatorname*{\mathbb{E}}_{\mathcal{A}}[L_{\mathcal{D}}(\mathcal{A}(S))-% L_{S}(\mathcal{A}(S))]

Since

\beta(m)

-uniformly stable algorithms are

\varepsilon(m)

-on-average-replace-one stable, proposition 15.1 implies that

\operatorname*{\mathbb{E}}_{S}f(S)\leq\beta(m)

For brevity, write

\hat{h}_{S}

for

\mathcal{A}(S)

, and

S^{i}

for

S^{(i\leftarrow z^{\prime})}

. Then we have directly that

\lvert\operatorname*{\mathbb{E}}_{\mathcal{A}}L_{\mathcal{D}}(\hat{h}_{S^{i}})% -\operatorname*{\mathbb{E}}_{\mathcal{A}}L_{\mathcal{D}}(\hat{h}_{S})\rvert% \leq\operatorname*{\mathbb{E}}_{z\sim{\mathcal{D}}}\lvert\operatorname*{% \mathbb{E}}_{\mathcal{A}}\ell(\hat{h}_{S^{i}},z)-\operatorname*{\mathbb{E}}_{% \mathcal{A}}\ell(\hat{h}_{S},z)\rvert\leq\beta(m).

L_{S}

is slightly more complicated, since one evaluation point changes too:

	$\displaystyle\lvert\operatorname{\mathbb{E}}_{\mathcal{A}}L_{S^{i}}(\hat{h}_{% S^{i}})-\operatorname{\mathbb{E}}_{\mathcal{A}}L_{S}(\hat{h}_{S})\rvert$	$\displaystyle\leq\frac{1}{m}\sum_{j\neq i}\lvert\operatorname{\mathbb{E}}_{% \mathcal{A}}\ell(\hat{h}_{S^{i}},z_{j})-\operatorname{\mathbb{E}}_{\mathcal{A% }}\ell(\hat{h}_{S},z_{j})\rvert+\frac{1}{m}\lvert\operatorname{\mathbb{E}}_{% \mathcal{A}}\ell(\hat{h}_{S^{i}},z^{\prime})-\operatorname{\mathbb{E}}_{% \mathcal{A}}\ell(\hat{h}_{S},z_{i})\rvert$
		$\displaystyle\leq\frac{1}{m}\sum_{j\neq i}\beta(m)+\frac{1}{m}(b-a)=\frac{m-1}% {m}\beta(m)+\frac{b-a}{m}$
		$\displaystyle\leq\beta(m)+\frac{b-a}{m}.$

Thus

f

satisfies the bounded differences condition of McDiarmid with

c_{i}=2\beta(m)+\frac{b-a}{m}

. Combining with

\operatorname*{\mathbb{E}}_{S}f(S)\leq\beta(m)

gives the desired result. ∎

In fact, even stronger rates have been shown recently, with more complex techniques; ³³3I don’t know whether their results hold for random

\mathcal{A}

or not. [BKZ20] showed for deterministic

\mathcal{A}

that, with probability at least

1-\delta

over the choice of

S

L_{\mathcal{D}}(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))\leq\text{const}\left(% \beta(m)\log(m)\log\frac{1}{\delta}+\frac{b-a}{\sqrt{m}}\sqrt{\log\frac{1}{% \delta}}\right)

(15.1)

by simplifying and improving techniques of [FV18, FV19] inspired by techniques from differential privacy. This shows a

\tilde{\operatorname{\mathcal{O}}}_{p}(1/\sqrt{m})

rate as long as

\beta(m)=\tilde{\operatorname{\mathcal{O}}}(1/\sqrt{m})

, much weaker than the

\tilde{\operatorname{\mathcal{O}}}(1/m)

required by theorem 15.4.

15.2 Convex RLM

Recall regularized loss minimization (RLM), and suppose

h\mapsto\ell(h,z)

is convex for each

z

, ⁴⁴4If it’s strongly convex with some different

m

, just scale it and inversely scale

\lambda

. and

R(h)

is 1-strongly convex. Then

f_{S}(h)=L_{S}(h)+\lambda R(h)

, the sum of a convex function and a

\lambda

-strongly convex function, is

\lambda

-strongly convex. Let

\mathcal{A}(S)

denote

\operatorname*{arg\,min}_{h\in\mathcal{H}}f_{S}(h)

; since

f_{S}

is strongly convex, it has a unique minimizer.

Now, notice that for any $h\in\mathcal{H}$ , we have that

f_{S}(h)=f_{S^{(i\leftarrow z^{\prime})}}(h)-\frac{1}{m}\ell(h,z^{\prime})+% \frac{1}{m}\ell(h,z_{i}).

Thus for any

h,g\in\mathcal{H}

f_{S}(h)-f_{S}(g)=f_{S^{(i\leftarrow z^{\prime})}}(h)-f_{S^{(i\leftarrow z^{% \prime})}}(g)+\frac{\ell(h,z_{i})-\ell(g,z_{i})}{m}+\frac{\ell(g,z^{\prime})-% \ell(h,z^{\prime})}{m}.

Plugging in

h=\hat{h}^{i}=\mathcal{A}(S^{(i\leftarrow z^{\prime})})

and

g=\hat{h}=\mathcal{A}(S)

, since

\hat{h}^{i}

minimizes

f_{S^{(i\leftarrow z^{\prime})}}

, we get that

f_{S}(\hat{h}^{i})-f_{S}(\hat{h})\leq\frac{\ell(\hat{h}^{i},z_{i})-\ell(\hat{h% },z_{i})}{m}+\frac{\ell(\hat{h},z^{\prime})-\ell(\hat{h}^{i},z^{\prime})}{m}.

Noting also that

\nabla f_{S}(\hat{h})=0

, proposition C.3 implies that

f_{S}(\hat{h}^{i})-f_{S}(\hat{h})\geq\tfrac{1}{2}\lambda\lVert\hat{h}^{i}-\hat% {h}\rVert^{2}

. Thus we’ve shown that

\frac{\lambda}{2}\lVert\hat{h}^{i}-\hat{h}\rVert^{2}\leq\frac{\ell(\hat{h}^{i}% ,z_{i})-\ell(\hat{h},z_{i})}{m}+\frac{\ell(\hat{h},z^{\prime})-\ell(\hat{h}^{i% },z^{\prime})}{m}.

(15.2)

15.2.1 Lipschitz loss

If we further assume that

h\mapsto\ell(h,z)

\rho

-Lipschitz for each

z

, i.e.

\lvert\ell(h,z)-\ell(h^{\prime},z)\rvert\leq\rho\lVert h-h^{\prime}\rVert

for all

z

, then (15.2) yields that

\frac{\lambda}{2}\lVert\hat{h}^{i}-\hat{h}\rVert^{2}\leq\frac{2\rho}{m}\lVert% \hat{h}^{i}-\hat{h}\rVert,

and hence

\lVert\hat{h}^{i}-\hat{h}\rVert\leq\frac{4\rho}{\lambda m}.

Using the Lipschitz property again,

\lvert\ell(\hat{h}^{i},z)-\ell(\hat{h},z)\rvert\leq\rho\lVert\hat{h}^{i}-\hat{% h}\rVert\leq\frac{4\rho^{2}}{\lambda m}

for any

z

, and so we’ve shown

\frac{4\rho^{2}}{\lambda m}

-uniform stability. Plugging into theorem 15.4, we’ve shown the following result.

Proposition 15.5.

Suppose that

h\mapsto\ell(h,z)

\rho

-Lipschitz and convex for each

z\in\mathcal{Z}

. Let

h\mapsto\lambda R(h)

\lambda

-strongly convex. Then the RLM algorithm

\mathcal{A}

of (RLM) is

4\rho^{2}/(\lambda m)

-uniformly stable, and hence

\operatorname*{\mathbb{E}}_{S\sim{\mathcal{D}}^{m}}[L_{\mathcal{D}}(\mathcal{A% }(S))-L_{S}(\mathcal{A}(S))]\leq\frac{4\rho^{2}}{\lambda m}.

If we further have that

\ell(h,z)\in[a,b]

for all

h

and

{\mathcal{D}}

-almost all

z

, (RLM) satisfies that, with probability at least

1-\delta

over the choice of

S\sim{\mathcal{D}}^{m}

L_{\mathcal{D}}(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))\leq\frac{4\rho^{2}}{% \lambda m}+\left(\frac{8\rho^{2}}{\lambda}+b-a\right)\sqrt{\frac{1}{2m}\log% \frac{1}{\delta}}.

15.2.2 Smooth, nonnegative loss

It’s possible, though messier, to show a similar result for nonnegative

\beta

-smooth functions (those with

\beta

-Lipschitz gradients, as in definition 11.1): in the end, if you also assume that

\lambda\geq 2\beta/m

, you get (see [SB14, Section 13.3.2]) that

\operatorname*{\mathbb{E}}_{S,z^{\prime}}\left[L_{S}(\mathcal{A}(S^{(i% \leftarrow z^{\prime})}))-L_{S}(\mathcal{A}(S))\right]\leq\frac{48\beta}{% \lambda m}\operatorname*{\mathbb{E}}_{S}[L_{S}(\mathcal{A}(S))].

R

is nonnegative and there is some

h_{0}

with

R(h_{0})=0

, e.g. the zero predictor when

R(h)=\lVert h\rVert^{2}

, and we also have that

\ell(h_{0},z)\leq b

, say because the loss is always less than

b

, then we know that

L_{S}(\mathcal{A}(S))\leq L_{S}(\mathcal{A}(S))+\lambda R(\mathcal{A}(S))\leq L% _{S}(h_{0})+\lambda R(h_{0})\leq b,

in which case we can upper-bound

\operatorname*{\mathbb{E}}_{S}L_{S}(\mathcal{A}(S))

b

15.3 Fitting-Stability Trade-Off

Proposition 15.5 shows that $L_{\mathcal{D}}(\mathcal{A}(S))$ is closer to $L_{S}(\mathcal{A}(S))$ as $\lambda$ grows. But $L_{S}(\mathcal{A}(S))$ will also get worse for bigger $\lambda$ , since $\mathcal{A}$ cares more and more about having “simpler” $h$ than minimizing $L_{S}$ . How can we find the best $\lambda$ to trade off between them?

For any fixed $h^{*}$ , if $R$ is nonnegative and $1$ -strongly convex, we have that

L_{S}(\mathcal{A}(S))\leq L_{S}(\mathcal{A}(S))+\lambda R(h)\leq L_{S}(h^{*})+% \lambda R(h^{*}),

and hence

\operatorname*{\mathbb{E}}_{S}L_{S}(\mathcal{A}(S))\leq L_{\mathcal{D}}(h^{*})% +\lambda R(h^{*}).

(15.3)

15.3.1 Expected loss

So, using (15.3) and propositions 15.1 and 15.5,

	$\displaystyle\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))$	$\displaystyle\leq L_{\mathcal{D}}(h^{})+\lambda R(h^{})+\operatorname*{% \mathbb{E}}_{S}[L_{\mathcal{D}}(\mathcal{A}(S))-L_{S}(\mathcal{A}(S))]$
		$\displaystyle\leq L_{\mathcal{D}}(h^{})+\lambda R(h^{})+\frac{4\rho^{2}}{% \lambda m}$		(15.4)

if the loss is convex and

\rho

-Lipschitz, and

R

is nonnegative and

1

-strongly convex.

We now have two routes we can take from this bound.

Choosing $\lambda$

Because our canonical regularizer is $R(h)=\frac{1}{2}\lVert h\rVert^{2}$ , let’s compare our result to any $h^{*}$ satisfying $R(h^{*})\leq\frac{1}{2}B^{2}$ . We then have

\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))\leq L_{\mathcal{% D}}(h^{*})+\frac{1}{2}\lambda B^{2}+\frac{4\rho^{2}}{\lambda m}.

(15.5)

Using that

\alpha x+\beta/x

is minimized at

x=\sqrt{\beta/\alpha}

with value

2\sqrt{\alpha\beta}

, we can minimize this bound by picking

\lambda=\frac{\rho}{B}\sqrt{\frac{8}{m}}

to get

\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))\leq\inf_{h^{*}:R% (h^{*})\leq\frac{1}{2}B^{2}}L_{\mathcal{D}}(h^{*})+\rho B\sqrt{\frac{8}{m}}.

Definition 15.6.

A learning problem is convex, $\rho$ -Lipschitz, $B$ -bounded ⁵⁵5 The class of problems is also sometimes described in terms of Bregman divergences; see e.g. Chapter 14 of [MRT18]. if the hypothesis set

\mathcal{H}

is convex, bounded as

R(h)\leq\frac{1}{2}B^{2}

for all

h\in\mathcal{H}

for some strongly convex function

R

, and the loss functions

h\mapsto\ell(h,z)

are convex and

\rho

-Lipschitz for each

z\in\mathcal{Z}

Regularized loss minimization can therefore learn (in the sense of expected loss) any convex-Lipschitz-bounded learning problem. (Section 12.2.1 of [SB14] gives examples of problems which are not learnable if they’re convex but not Lipschitz and/or not bounded.)

You can do a similar thing for the case where the loss is nonnegative and smooth instead of Lipschitz ([SB14], Corollaries 13.10 and 13.11).

Fixing $\lambda$

Instead of fixing some $B$ and picking $\lambda$ accordingly, we can instead ask: what happens if we run the algorithm with any particular choice of $\lambda$ ? We minimized (15.5) in terms of $\lambda$ , but it’s equivalent to take $\lambda$ as given and minimize the bound in terms of $B$ , in which case we find $B=\frac{\rho}{\lambda}\sqrt{\frac{8}{m}}$ and

\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))\leq\inf_{h^{*}:R% (h^{*})\leq\frac{1}{2}\left(\frac{\rho}{\lambda}\sqrt{\frac{8}{m}}\right)^{2}}% L_{\mathcal{D}}(h^{*})+\frac{8\rho^{2}}{\lambda m}.

This is exactly the same analysis, but tells us what happens with different choices of

\lambda

: for instance, if we pick a constant

\lambda

m

grows, then we only compete with simpler and simpler hypotheses as we see more data (not ideal).

We need $\frac{1}{\lambda m}\to 0$ for the second term to go to zero, i.e. we need $\lambda=\omega(1/m)$ . If we also want to eventually compete with any possible predictor, we need $\frac{1}{\lambda\sqrt{m}}\to\infty$ , i.e. $\lambda=o(1/\sqrt{m})$ . Thus, consider picking $\lambda\propto m^{-\gamma}$ for any $\gamma\in(1/2,1)$ : the second term becomes $\operatorname{\mathcal{O}}(m^{\gamma-1})$ .

Note that this means boundedness isn’t actually required for learnability: convexity and Lipschitzness of the loss is enough. With boundedness, however, we know that

\inf_{h*:R(h^{*})\leq\frac{1}{2}\left(\frac{\rho}{\lambda}\sqrt{\frac{8}{m}}% \right)^{2}}L_{\mathcal{D}}(h^{*})

will become exactly

\inf_{h^{*}\in\mathcal{H}}L_{\mathcal{D}}(h^{*})

for

m

bigger than some threshold. Without boundedness, it might be that

\inf_{h^{*}\in\mathcal{H}}L_{\mathcal{D}}(h^{*})

is not actually achieved, only approached as

R(h^{*})\to\infty

; this is actually the case for logistic regression of separable data. To get a final bound, then, we would need to know the rate at which

\inf_{h*:R(h^{*})\leq\frac{1}{2}\left(\frac{\rho}{\lambda}\sqrt{\frac{8}{m}}% \right)^{2}}L_{\mathcal{D}}(h^{*})

approaches its asymptote as

m

grows.

15.3.2 High-probability bound

To get high-probability bounds, also assume that $\ell\in[a,b]$ .

We showed in the proof of theorem 15.4 that

L_{\mathcal{D}}(\mathcal{A}(S))

satisfies bounded differences with

c_{i}=\beta(m)

. We then have that

L_{\mathcal{D}}(\mathcal{A}(S))

is close to

\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D}}(\mathcal{A}(S))

, which we just upper-bounded; we don’t actually need to apply theorem 15.4 directly, and doing so wouldn’t be any tighter. This tells us that

L_{\mathcal{D}}(\mathcal{A}(S))\leq\operatorname*{\mathbb{E}}_{S}L_{\mathcal{D% }}(\mathcal{A}(S))+\frac{4\rho^{2}}{\lambda m}\sqrt{\frac{m}{2}\log\frac{1}{% \delta}},

and plugging in (15.5) gives for any fixed

h^{*}

, it holds with probability at least

1-\delta

that

L_{\mathcal{D}}(\mathcal{A}(S))\leq L_{\mathcal{D}}(h^{*})+\lambda R(h^{*})+% \frac{4\rho^{2}}{\lambda m}+\frac{4\rho^{2}}{\lambda\sqrt{m}}\sqrt{\frac{1}{2}% \log\frac{1}{\delta}}.

(15.6)

We can see that the choice

\lambda\propto 1/\sqrt{m}

, which was optimal in the average-case analysis of section 15.3.1, will now give us a constant upper bound. That’s no good. The problematic term is

\beta(m)\sqrt{m}

, the same as in theorem 15.4, but using

\lambda\propto 1/\sqrt{m}

means that

\beta(m)=\operatorname{\mathcal{O}}(\frac{1}{\lambda m})

becomes

\operatorname{\mathcal{O}}(1/\sqrt{m})

We’ll thus need a larger

\lambda

. Assuming

R(h^{*})\leq\frac{1}{2}B^{2}

, we can minimize (15.6) when

\lambda=\sqrt{\frac{2}{B^{2}}\cdot 4\rho^{2}\left(\frac{1}{m}+\sqrt{\frac{1}{2% m}\log\frac{1}{\delta}}\right)}=\frac{\rho}{B}\sqrt{8\left(\frac{1}{m}+\sqrt{% \frac{1}{2m}\log\frac{1}{\delta}}\right)},

giving a bound of

L_{\mathcal{D}}(\mathcal{A}(S))-L_{\mathcal{D}}(h^{*})\leq B\rho\sqrt{8\left(% \frac{1}{m}+\sqrt{\frac{1}{2m}\log\frac{1}{\delta}}\right)}.

Notice that this upper bound on the suboptimality is bigger than

B\rho\left(\frac{32}{m}\log\frac{1}{\delta}\right)^{1/4}

; that

m^{-1/4}

rate is much slower than the

m^{-1/2}

rate for the mean!

Using the sharper bound of (15.1) instead gives a much better result:

L_{\mathcal{D}}(\mathcal{A}(S))-L_{\mathcal{D}}(h^{*})=\operatorname{\mathcal{% O}}\left(\lambda B^{2}+\frac{\rho^{2}}{\lambda m}+\frac{\rho^{2}}{\lambda m}% \log m\log\frac{1}{\delta}+\frac{b-a}{\sqrt{m}}\sqrt{\log\frac{1}{\delta}}% \right).

This upper bound is minimized by

\lambda=\Theta\left(\frac{\rho}{B}\sqrt{\frac{1+\log m\log\frac{1}{\delta}}{m}% }\right)=\tilde{\Theta}\left(\frac{\rho}{B\sqrt{m}}\right)

, giving

L_{\mathcal{D}}(\mathcal{A}(S))-L_{\mathcal{D}}(h^{*})=\operatorname{\mathcal{% O}}\left(B\rho\sqrt{\frac{1+\log m\log\frac{1}{\delta}}{m}}+\frac{b-a}{\sqrt{m% }}\sqrt{\log\frac{1}{\delta}}\right)=\tilde{\operatorname{\mathcal{O}}}_{p}% \left(\frac{\max(B\rho,b-a)}{\sqrt{m}}\right).

This is a far more satisfying final bound, and notice that the choice of

\lambda

is similar (up to log factors) to the case from section 15.3.1 where we only analyzed the mean.

Either of these analyses shows that convex-Lipschitz-bounded learning problems are also learnable by RLM with high probability.

A similar, but messier, analysis should also work for the case of a nonnegative $\beta$ -smooth loss.

15.4 More

Other algorithms than RLM are also stable. The theory originated out of analyses of “local learning rules” like $k$ -nearest neighbour, which are on-average-replace-one stable (and “hypothesis stable”) but not uniformly stable. You can also show that (stochastic) gradient descent is uniformly stable for convex problems, and even get some results in non-convex settings ([HRS15, FV19]). And, as mentioned, any differentially private algorithm is automatically uniformly stable (with the randomized variant).

Stability is also very useful for analyzing cross-validation, especially leave-one-out cross-validation, which is discussed by many of the papers here ([BE02, SSS+10]).

[SSS+10] also have thorough accounting of when stability is necessary, or not, to be able to learn different kinds of problems, and [WLF16] a similar accounting of the relationship to privacy.

Chapter 15 Stability

Randomized algorithms

15.1 Definitions of Stability

Proposition 15.1.

Proof.

Definition 15.2.

Definition 15.3.

Theorem 15.4 ([BE02], basically).

Proof.

15.2 Convex RLM

15.2.1 Lipschitz loss

Proposition 15.5.

15.2.2 Smooth, nonnegative loss

15.3 Fitting-Stability Trade-Off

15.3.1 Expected loss

Choosing λ

Definition 15.6.

Fixing λ

15.3.2 High-probability bound

15.4 More

Choosing $\lambda$

Fixing $\lambda$