Algorithmic stability and hypothesis complexity

Introduction

The notion of algorithmic stability has been an important tool in deriving theoretical guarantees of the generalization abilities of learning algorithms. Various notions of stability have been introduced and have been exploited to derive generalization bounds. For some examples, Mukherjee et al. 2006 proved that a statistical form of leave-one-out stability is a sufficient and necessary condition for the generalization and learnability of empirical risk minimization learning algorithms; Shalev-Shwartz et al. 2010 defined a weaker notion, the so-called “on-average-replace-one-example stability”, and showed that this condition is both sufficient and necessary for the generalization and learnability of a general learning setting.

In this paper we study learning algorithms that select a hypothesis (i.e., a function used for prediction) from a certain fixed class of functions belonging to a separable Banach space. We introduce a notion of argument stability which measures the impact of changing a single training example on the hypothesis selected by the learning algorithm. This notion of stability is stronger than uniform algorithmic stability of Bousquet & Elisseeff 2002 that is only concerned about the change in the loss but not the hypothesis itself. However, as we will show, the new notion is still quite natural and holds for a variety of learning algorithms. On the other hand, it allows one to exploit martingale inequalities (Boucheron et al. 2013) in the Banach space of the hypotheses. Indeed, the performance bounds we derive for stable algorithms depend on characteristics related to the martingale type of the Banach space.

Generalization bounds typically depend on the complexity of a class of hypotheses that can be chosen by the learning algorithm. Exploiting the local estimates of the complexity of the predefined hypothesis class is a promising way to obtain sharp bounds. Building on martingale inequalities in the Banach space of the hypotheses, we define a subset of the predefined hypothesis class, whose elements will (or will have a high probability to) be output by a learning algorithm, as the algorithmic hypothesis class, and study the complexity of the algorithmic hypothesis class of argument-stable learning algorithms. We show that, if the hypotheses belong to a Hilbert space, the upper bound of the Rademacher complexity of the algorithmic hypothesis class will converge at a fast rate of order $O(1/n)$, where $n$ is the sample size.

The rest of the paper is organized as follows. Section 2 introduces the mathematical framework and the proposed notion of algorithmic stability. Section 3 presents the main results of this study, namely the generalization bounds in terms of argument stability. Section 4 specializes the results to some learning algorithms, including empirical risk minimization and stochastic gradient descent. Section 5 concludes the paper.

Algorithmic Stability and Hypothesis Class

We consider the classical statistical learning problem, where the value of a real random variable $Y$ is to be predicted based on the observation of an another random variable $X$. Let $S$ be a training sample of $n$ i.i.d. pairs of random variables $Z_{1}=(X_{1},Y_{1}),\ldots,Z_{n}=(X_{n},Y_{n})$ drawn from a fixed distribution $P$ on a set $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ is the so-called feature space. A learning algorithm $\mathcal{A}:S\in\mathcal{Z}^{n}\mapsto h_{S}\in H$ is a mapping from $\mathcal{Z}^{n}$ to a hypothesis class $H$ that we assume to be a subset of a separable Banach space $(\mathfrak{B},\|\cdot\|)$. We focus on linear prediction problems, that is, when $h(x)$ is a linear functional of $x$. We write $h(x)=\langle h,x\rangle$. In other words, we assume that the feature space $\mathcal{X}$ is the algebraic dual of the Banach space $\mathfrak{B}$. We denote the norm in $\mathcal{X}$ by $\|\cdot\|_{*}$. The output $h_{S}$ of the learning algorithm is a hypothesis used for predicting the value for $Y$.

An important special case is when $\mathfrak{B}$ is a Hilbert space. In that case we may assume that $\mathcal{X}=\mathfrak{B}$ and that $\langle h,x\rangle$ is the inner product in $\mathfrak{B}$.

For the output $h_{S}$ of a learning algorithm $\mathcal{A}$, the generalization error is defined as

The notion of algorithmic stability was proposed to measure the changes of outputs of a learning algorithm when the input is changed. Various ways have been introduced to measure algorithmic stability. Here we recall the notion of uniform stability defined by Bousquet & Elisseeff 2002 for comparison purposes. This notion of stability relies on the altered sample $S^{i}=\{Z_{1},\ldots,Z_{i-1},Z^{\prime}_{i},Z_{i+1},\ldots,Z_{n}\}$, the sample $S$ with the $i$-th example being replaced by an independent copy of $Z_{i}$.

We propose the following, similar, notion that “acts” on the hypotheses directly, as opposed to the losses.

A learning algorithm $\mathcal{A}$ is $\alpha(n)$-uniformly argument stable if for all $i\in\{1,\ldots,n\}$,

holds for all $z\in\mathcal{Z}$ and $h,h^{\prime}\in H$.

Additionally assuming that $\|X\|_{*}$ is bounded by some $B>0$ with probability one, it is easy to see that an $\alpha(n)$-uniformly argument stable learning algorithm is uniformly stable with $\beta(n)=LB\alpha(n)$, since

However, the reverse implication need not necessarily hold and hence uniform argument stability is a stronger notion.

The relationship between argument stability and generalization performance hinges on a property of the Banach space $\mathfrak{B}$ that is closely related to the martingale type of the space—see Pisier 2011 for a comprehensive account. For concreteness we assume that the Banach space $\mathfrak{B}$ is $(2,D)$-smooth (or of martingale type 2) for some $D>0$. This means that for all $h,h^{\prime}\in\mathfrak{B}$,

Note that Hilbert spaces are $(2,1)$-smooth. The property we need is described in the following result of (Pinelis 1994):

Let $D_{1},\ldots,D_{n}$ be a martingale difference sequence taking values in a separable $(2,D)$-smooth Banach space $\mathfrak{B}$. Then for any $\epsilon>0$,

where $c$ is a constant satisfying that $\sum_{t=1}^{\infty}\|D_{t}\|_{\infty}^{2}\leq c^{2}$ (and $\|D_{t}\|_{\infty}$ is the essential supremum of the random variable $\|D_{t}\|$).

Our arguments extend, in a straightforward manner, to more general Banach spaces whenever exponential tail inequalities for bounded martingale sequences similar to Proposition 1 are available. We stay with the assumption of $(2,D)$-smoothness for convenience and because it applies to the perhaps most important special case when $\mathfrak{B}$ is a Hilbert space. We refer to Rakhlin & Sridharan 2015 for more information of martingale inequalities of this kind.

Let the Banach space $\mathfrak{B}$ be $(2,D)$-smooth. If a learning algorithm $\mathcal{A}$ is $\alpha(n)$-uniformly argument stable, then, for any $\delta>0$,

for $\delta=2\exp\left(-\frac{\epsilon^{2}}{2D^{2}}\right)$. ∎

Algorithmic Rademacher Complexity and Generalization Bound

For a sample size $n$ and confidence parameter $\delta>0$, let $r=r(n,\delta)=D\alpha(n)\sqrt{2n\log(2/\delta)}$ and define the algorithmic hypothesis class of a stable learning algorithm by

Note that, by Lemma 1, $h_{S}\in B_{r}$ with probability at least $1-\delta$.

We bound the generalization error (1) in terms of the Rademacher complexity (Bartlett & Mendelson 2003) of the algorithmic hypothesis class. The Rademacher complexity of a hypothesis class $H$ on the feature space $\mathcal{X}$ is defined as

where $\sigma_{1},\ldots,\sigma_{n}$ are i.i.d. Rademacher variables that are uniformly distributed in $\{-1,+1\}$.

The next theorem shows how the Rademacher complexity of the algorithmic hypothesis class can be bounded. The bound depends on the type of the feature space $\mathcal{X}$. Recall that the Banach space $(\mathcal{X},\|\cdot\|_{*})$ is of type $p\geq 1$ if there exists a constant $C_{p}$ such that for all $x_{1},\ldots,x_{n}\in\mathcal{X}$,

In the important special case when $\mathcal{X}$ is a Hilbert space, the space is of type $2$ with constant $C_{2}=1$.

Assume that $\mathfrak{B}$ is a $(2,D)$-smooth Banach space and that its dual $\mathcal{X}$ is of type $p$. Suppose that the marginal distribution of the $X_{i}$ is such that $\|X_{i}\|_{*}\leq B$ with probability one, for some $B>0$. If a learning algorithm is $\alpha(n)$-uniformly argument stable, then the Rademacher complexity of the algorithmic hypothesis class $B_{r}$ on the feature space satisfies

In particular, when $\mathfrak{B}$ is a Hilbert space, the bound simplifies to

The theorem above may be easily used to bound the performance of an $\alpha(n)$-uniformly argument stable learning algorithm. For simplicity, we state the result for Hilbert spaces only. The extension to $(2,D)$-smooth Banach spaces with a type-$p$ dual is straightforward.

Note first that, by Lemma 1, with probability at least $1-\delta$,

On the other hand, by the boundedness of the loss function, and the bounded differences inequality, with probability at least $1-\delta$,

Note that the order of magnitude of $\alpha(n)$ of many stable algorithms is of order $O(1/n)$. For the notion of uniform stability, such bounds appear in Lugosi & Pawlak 1994; Bousquet & Elisseeff 2002; Wibisono et al. 2009; Hardt et al. 2015; Liu et al. 2017. As we will show in the examples below, many of these learning algorithms even have uniform argument stability of order $O(1/n)$. In such cases the bound of Corollary 1 is essentially equivalent of the earlier results cited above. The bound is dominated by the term $M\sqrt{\frac{\log(1/\delta)}{2n}}$ present by using the bounded differences inequality. Fluctuations of the order of $O(n^{-1/2})$ are often inevitable, especially when $R(h_{S})$ is not typically small. When small risk is reasonable to expect, one may use more advanced concentration inequalities with second-moment information, at the price of replacing the generalization error by the so-called “deformed” generalization error $R(h_{S})-\frac{a}{a-1}R_{S}(h_{S})$ where $a>1$. The next theorem derives such a bound, relying on techniques developed by Bartlett et al. 2005. This result improves essentially on earlier stability-based bounds.

The proof of Theorem 2 relies on techniques developed by Bartlett et al. 2005. In particular, we make use of the following result.

(Bartlett et al. 2005, Theorem 2.1). Let $F$ be a class of functions that map $\mathcal{X}$ into $[0,M]$. Assume that there is some $\rho>0$ such that for every $f\in F$, $\text{var}(f(X))\leq\rho$. Then, with probability at least $1-\delta$, we have

To prove the theorem, we also need to introduce the following auxiliary lemma.

For any $r>0$ and $a>1$, if $V_{r}\leq r/a$ then every $h\in B_{r}$ satisfies

First, we introduce an inequality to build the connection between algorithmic stability and hypothesis complexity. According to Lemma 1, for any $a>1$ and $\delta>0$, with probability at least $1-\delta$, we have

which means that there exists an $r^{*}\leq\frac{2Ma^{2}\log(1/\delta)}{n}+8a\mathfrak{R}(\mathcal{G}_{r})+\frac{4}{3}\frac{2aM\log(1/\delta)}{n}$ such that $V_{r^{*}}\leq r^{*}/a$ holds. According to Lemma 2, for any $h\in B_{r}$, with probability at least $1-\delta$, we have

By elementary properties of the Rademacher complexity (see, e.g., Bartlett & Mendelson 2003), $H^{\prime}\subseteq H$ implies $\mathfrak{R}(H^{\prime})\leq\mathfrak{R}(H)$. Then, with probability at least $1-\delta$, we have

The proof of Theorem 2 is complete by combining the above inequality with inequality (2), the Talagrand Contraction Lemma, and Theorem 1. ∎

In the next section, we specialize the above results to some learning algorithms by proving their uniform argument stability.

Applications

Various learning algorithms have been proved to possess some kind of stability. We refer the reader to (Devroye & Wagner 1979; Lugosi & Pawlak 1994; Bousquet & Elisseeff 2002; Zhang 2003; Wibisono et al. 2009; Hardt et al. 2015; Liu et al. 2017) for such examples, including stochastic gradient descent methods, empirical risk minimization, and non-parametric learning algorithms such as $k$-nearest neighbor rules and kernel regression.

Regularized empirical risk minimization has been known to be uniformly stable (Bousquet & Elisseeff 2002). Here we consider regularized empirical risk minimization (RERM) algorithms of the following form. The empirical risk (or the objective function) of RERM is formulated as

By exploiting their results, we show that stable RERM algorithms have strong generalization properties.

Assume that $\mathfrak{B}$ is a separable Hilbert space. Suppose that the marginal distribution of the $X_{i}$ is such that $\|X_{i}\|_{*}\leq B$ with probability one, for some $B>0$ and that the loss function is convex in $h$, bounded by $M$ and $L$-Lipschitz. Suppose that for some constants $C$ and $\xi>1$, the penalty function $N(h)$ satisfies

Then, for any $\delta>0$, and $a>1$, if $h_{S}$ is the output of RERM, with probability at least $1-2\delta$, we have

Specifically, when $N(h)=\|h\|^{2}$, (3) holds with $\xi=2$ and $C=\frac{1}{2}\left(\frac{M}{\lambda}\right)^{\frac{1}{2}}$.

The proof of Theorem 3 relies on the following result implied by Wibisono et al. 2009.

Assume the conditions of Theorem 3. Then the RERM learning algorithm is $\beta(n)$-uniformly stable with

and is $\alpha(n)$-uniformly argument stable with

Specifically, when $N(h)=\|h\|_{p}^{p}$ and $1<p\leq 2$, the condition 3 on the penalty function holds with $\xi=2$ and $C=\frac{1}{4}p(p-1)\left(\frac{M}{\lambda}\right)^{\frac{p-1}{p}}$, where $\|h\|_{p}^{p}=\sum_{r}|h_{r}|^{p}$ and $r$ is the index for the dimensionality.

Theorem 3 follows by combining Theorem 2 and Proposition 3. ∎

2 Stochastic Gradient Descent

Stochastic gradient descent (SGD) is one of the most widely used optimization methods in machine learning. Hardt et al. 2015 showed that parametric models trained by SGD methods are uniformly stable. Their results apply to both convex and non-convex learning problems and provide insights for why SGD performs well in practice, in particular, for deep learning algorithms.

where $\nabla_{x}f(x)$ denotes the derivative of $f(x)$ with respect to $x$ and $s>0$.

While the above result only applies to $L$-Lipschitz loss functions as defined in Definition 3, it does explain some generalization properties of layer-wise training of neural networks by stochastic gradient descent. In this once-common training scheme (see, e.g., Bengio et al. 2007), one freezes the parameters of the network before/after a certain layer and performs SGD for this single layer. It is easy to see that, as long as the activation function and the loss function (connected with the network) are Lipschitz-continuous in their inputs, the overall loss can easily satisfy the continuous conditions of Theorem 4. This implies that the parameters in each layer may generalize well in a certain sense if SGD is employed with an early stop.

The proof of Theorem 4 follows immediately from Theorem 2, combined with the following result implied by Hardt et al. 2015 (which is a collection of the results of Theorems 3.8, 3.9, and 3.12 therein).

Conclusion

Our study leaves some open problems and allows several possible extensions. First, the algorithmic hypothesis class defined in this study depends mainly on the property of learning algorithms but little on the data distribution. It would be interesting to investigate a way to define an algorithmic hypothesis class by considering both the algorithmic property and the data distribution. Second, it would be interesting to explore if there are some algorithmic properties other than stability that could result in a small algorithmic hypothesis class.

Acknowledgments

Liu and Tao were partially supported by Australian Research Council Projects FT-130101457, DP-140102164, LP-150100671. Lugosi was partially supported by the Spanish Ministry of Economy and Competitiveness, Grant MTM2015-67304-P, and FEDER, EU. Neu was partially supported by the UPFellows Fellowship (Marie Curie COFUND program 600387).

References