Algorithmic stability of stochastic training — Examples

Let $n,T,d\ge 1$, $L,\beta >0$, and let $(\mathsf{X},{\mathrm{\Sigma }}_X)$, $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$, and $(\mathsf{A},{\mathrm{\Sigma }}_A)$ be measurable spaces. Let $P$ be a probability measure on $\mathsf{X}\times \mathsf{Y}$, let $\mathrm{\ell }:\mathsf{A}\times \mathsf{Y}\to [0,+\mathrm{\infty })$ be measurable, and let $f_w:\mathsf{X}\to \mathsf{A}$ be measurable for every $w\in {\mathbb{R}}^d$. For $z=(x,y)$ put $g(w,z)=\mathrm{\ell }(f_w(x),y)$ and assume $g$ and ${\mathrm{\nabla }}_{w}g$ are jointly measurable. For every $z$, assume $g(\cdot ,z)$ is totally differentiable and convex, its gradient is $\beta$-Lipschitz, and its values satisfy $\mathrm{\mid }g(w,z)-g(v,z)\mathrm{\mid }\le L\mathrm{\parallel }w-v{\mathrm{\parallel }}_2$. Let $S=(Z_1,\dots ,Z_n)$ be IID with law $P$, and define $R_P(f_w)=\int g(w,z)P(dz)$ and ${\widehat{R}}_S(f_w)=n^{-1}{\sum }_{i=1}^{n}g(w,Z_i)$. Let $I_1,\dots ,I_T$ be independent of $S$ with $\mathbb{P}(I_t=i)=1\mathrm{/}n$ for each $t,i$; dependence across times is allowed. From fixed $w_0\in {\mathbb{R}}^d$, run $w_t=w_{t-1}-{\alpha }_t{\mathrm{\nabla }}_{w}g(w_{t-1},Z_{I_t})$ and assume the resulting loss and risk maps are measurable and integrable. For the constant schedule ${\alpha }_t=1\mathrm{/}\beta$, the stability and absolute expected-generalization upper bound is $2L^{2}T\mathrm{/}(\beta n)$, which is linear in $T$ as a bound. This is an upper-bound calculation, not a lower bound on the actual stability or generalization gap.

Expected generalization of convex stochastic gradient training supplies the convex SGD stability and expected-gap bound.

Hardt, Recht, and Singer, arXiv-version Theorem 3.8 (conference Theorem 3.7): full arXiv paper.

For each $r\in \{1,2\}$, let $({\mathsf{X}}_r,{\mathrm{\Sigma }}_{X_r})$, $({\mathsf{Y}}_r,{\mathrm{\Sigma }}_{Y_r})$, and $({\mathsf{A}}_r,{\mathrm{\Sigma }}_{A_r})$ be measurable spaces, let $P_r$ be a probability measure on ${\mathsf{X}}_r\times {\mathsf{Y}}_r$, let ${\mathrm{\ell }}_r:{\mathsf{A}}_r\times {\mathsf{Y}}_r\to [0,+\mathrm{\infty })$ be measurable, and let $f_w^{(r)}:{\mathsf{X}}_r\to {\mathsf{A}}_r$ be measurable for $w\in {\mathbb{R}}^d$, where $d\ge 1$. Put $g_r(w,(x,y))={\mathrm{\ell }}_r(f_w^{(r)}(x),y)$ and assume $g_r$ and ${\mathrm{\nabla }}_w{g}_r$ are jointly measurable. Let $n=1000$, $T=100$, let $S_r=(Z_1^{(r)},\dots ,Z_n^{(r)})$ be IID with law $P_r$, and define $R_{P_r}(f_w^{(r)})=\int g_r(w,z)P_r(dz)$ and ${\widehat{R}}_{S_r}(f_w^{(r)})=n^{-1}{\sum }_{i=1}^n{g}_r(w,Z_i^{(r)})$. For each regime, let $I_1^{(r)},\dots ,I_T^{(r)}$ be independent of $S_r$ with $\mathbb{P}(I_t^{(r)}=i)=1\mathrm{/}n$ for every $t,i$; dependence between times is allowed. Start from fixed $w_0^{(r)}\in {\mathbb{R}}^d$ and use $w_t^{(r)}=w_{t-1}^{(r)}-{\alpha }_t^{(r)}{\mathrm{\nabla }}_w{g}_r(w_{t-1}^{(r)},Z_{I_t^{(r)}}^{(r)})$. In regime $r=1$, assume each $g_1(\cdot ,z)$ is totally differentiable and convex, has $1$-Lipschitz gradient, and is $1$-Lipschitz in values; use ${\alpha }_t^{(1)}=1$. In regime $r=2$, assume each $g_2(\cdot ,z)$ is totally differentiable, takes values in $[0,1]$, has $1$-Lipschitz gradient and is $1$-Lipschitz in values, with no convexity assumption; use ${\alpha }_t^{(2)}=1\mathrm{/}t$. Assume the displayed output risk variables are measurable and integrable. The convex theorem's stability and absolute expected-generalization upper bound is $1\mathrm{/}5$. The nonconvex theorem's upper bound is $20\sqrt{2}\mathrm{/}999$. This comparison concerns only these theorem certificates under their distinct loss hypotheses, not the actual stability or generalization gaps of arbitrary training problems.

Expected generalization of convex stochastic gradient training supplies the convex bound.

Expected generalization of nonconvex stochastic gradient training supplies the nonconvex bound.

Hardt, Recht, and Singer, arXiv-version Theorems 3.8 and 3.12 (conference Theorems 3.7 and 3.8): full arXiv paper.

Let the instance space be $\{\ast \}$ with its full sigma-algebra, let the label and action spaces be $\mathbb{R}$ with their Borel sigma-algebras, take $P$ to be the point mass at $0$, use predictors $f_w(\ast )=w$, and use loss $\mathrm{\ell }(u,y)=\frac{1}{2}(u-y{)}^2$. For $w,y\in \mathbb{R}$, write $g(w,(\ast ,y))=\mathrm{\ell }(f_w(\ast ),y)=\frac{1}{2}(w-y{)}^2$. For sample size $n=1$, start at $w_0=0$, use $I_1=1$ and ${\alpha }_1=1\mathrm{/}2$, and set $w_1=w_0-{\alpha }_1{\mathrm{\partial }}_{w}g(w_0,Z_{I_1})$. For every $a\in \mathbb{R}$, compare the neighboring samples $S_a=((\ast ,a))$ and $S_0=((\ast ,0))$ at test observation $z_0=(\ast ,0)$. Their output losses differ by $a^2\mathrm{/}8$. Since $a$ is arbitrary, this procedure has no finite uniform replacement stability coefficient. The loss is convex and its gradient is $1$-Lipschitz but its values are not globally Lipschitz in $w$, so this example lies outside the convex SGD theorem's hypotheses and is not a counterexample to that theorem.

Uniform stability for randomized learning rules defines the finite replacement-stability requirement.

Expected generalization of convex stochastic gradient training requires global Lipschitzness of the per-example loss.

Hardt, Recht, and Singer, arXiv-version Theorem 3.8 (conference Theorem 3.7): full arXiv paper.