Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent

Introduction

Stochastic gradient descent (SGD) has become the workhorse behind many machine learning problems. As an iterative algorithm, SGD updates the model sequentially upon receiving a new datum with a cheap per-iteration cost, making it amenable for big data analysis. There is a plethora of theoretical work on its convergence analysis as an optimization algorithm [e.g. 11, 55, 40, 34, 21, 46].

Concurrently, there are a considerable amount of work with focus on its generalization analysis . For instance, using the tool of integral operator the work studied the excess generalization error of SGD with the least squares loss, i.e. the difference between the true risk of SGD iterates and the best possible risk. An advantage of this approach is its ability to capture the regularity of regression functions and the capacity of hypothesis spaces. The results were further extended in Lin et al. , Lei & Tang based on tools of empirical processes which are able to deal with general convex functions even without a smoothness assumption. The idea is to bound the complexity of SGD iterates in a controllable manner, and apply concentration inequalities in empirical processes to control the uniform deviation between population risks and empirical risks over a ball to which the SGD iterates belong.

Recently, in the seminal work the authors studied the generalization bounds of SGD via algorithmic stability for convex, strongly convex and non-convex problems. This motivates several appealing work on some weaker stability measures of SGD that still suffice for guaranteeing generalization . An advantage of this stability approach is that it considers only the particular model produced by the algorithm, and can imply generalization bounds independent of the dimensionality.

However, the existing stability analysis of SGD is established under the strong assumptions on the loss function such as the boundedness of the gradient and strong smoothness. Such assumptions are very restrictive which are not satisfied in many standard contexts. For example, the bounded gradient assumption does not hold for the simple least-squares regression, where the model parameter belongs to an unbounded domain. The strong smoothness assumption does not hold for the popular support vector machine. Furthermore, the analysis in the strongly convex case requires strong convexity of each loss function which is not true for many problems such as the important problem of least squares regression.

In this paper, we provide a fine-grained analysis of stability and generalization for SGD. Our new results remove the bounded gradient assumption for differentiable loss functions and remove the strong smoothness assumptions for Lipschitz continuous loss functions, and therefore broaden the impact of the algorithmic stability approach for generalization analysis of SGD. In summary, our main contributions are listed as follows.

$\bullet$ Firstly, we study stability and generalization for SGD by removing the existing bounded gradient assumptions. The key is an introduction of a novel stability measure called on-average model stability, whose connection to generalization is established by using the smoothness of loss functions able to capture the low risks of output models for better generalization. An advantage of on-average model stability is that the corresponding bounds involve a weighted sum of empirical risks instead of the uniform Lipschitz constant. The weighted sum of empirical risks can be bounded via tools in analyzing optimization errors, which implies a key message that optimization is beneficial to generalization. Furthermore, our stability analysis allows us to develop generalization bounds depending on the risk of the best model. In particular, we have established fast generalization bounds $O(1/n)$ for the setting of low noises, where $n$ is the sample size. To our best knowledge, this is the first fast generalization bound of SGD based on stability approach in a low-noise setting.

$\bullet$ Secondly, we consider loss functions with their (sub)gradients satisfying the Hölder continuity which is a much weaker condition than the strong smoothness in the literature. Although stability decreases by weakening the smoothness assumption, optimal generalization bounds can be surprisingly achieved by balancing computation and stability. In particular, we show that optimal generalization bounds can be achieved for the hinge loss by running SGD with $O(n^{2})$ iterations. Fast learning rates are further derived in the low-noise case.

$\bullet$ Thirdly, we study learning problems with (strongly) convex objectives but non-convex individual loss functions. The nonconvexity of loss functions makes the corresponding gradient update no longer non-expansive, and therefore the arguments in Hardt et al. do not apply. We bypass this obstacle by developing a novel quadratic inequality of the stability using only the convexity of the objective, which shows that this relaxation affects neither generalization nor computation.

The paper is structured as follows. We discuss the related work in Section 2 and formulate the problem in Section 3. The stability and generalization for learning with convex loss functions is presented in Section 4. In Sections 5 and 6, we consider problems with relaxed convexity and relaxed strong convexity, respectively. We conclude the paper in Section 7.

Related Work

In this section, we discuss related work on algorithmic stability, stability of stochastic optimization algorithms and generalization error of SGD.

Algorithmic Stability. The study of stability can be dated back to Rogers & Wagner . A modern framework of quantifying generalization via stability was established in the paper , where a concept of uniform stability was introduced and studied for empirical risk minimization (ERM) in the strongly convex setting. This framework was then extended to study randomized learning algorithms , transfer learning and privacy-preserving learning , etc. The interplay between various notions of stability, learnability and consistency was further studied . The power of stability analysis is especially reflected by its ability in deriving optimal generalization bounds in expectation . Very recently, almost optimal high-probability generalization bounds were established via the stability approach . In addition to the notion of uniform stability mentioned above, various other notions of stability were recently introduced, including uniform argument stability and hypothesis set stability .

Stability of Stochastic Optimization Algorithms. In the seminal paper , the co-coercivity of gradients was used to study the uniform stability of SGD in convex, strongly convex and non-convex problems. The uniform stability was relaxed to a weaker notion of on-average stability , for which the corresponding bounds of SGD can capture the impact of the risk at the initial point and the variance of stochastic gradients . For non-convex learning problems satisfying either a gradient dominance or a quadratic growth condition, pointwise-hypothesis stabilities were studied for a class of learning algorithms that converge to global optima , which relaxes and extends the uniform stability of ERM under strongly convex objectives . A fundamental stability and convergence trade-off of iterative optimization algorithms was recently established, where it was shown that a faster converging algorithm can not be too stable, and vice versa . This together with some uniform stability bounds for several first-order algorithms established there, immediately implies new convergence lower bounds for the corresponding algorithms. Algorithmic stability was also established for stochastic gradient Langevin dynamics with non-convex objectives and SGD implemented in a stagewise manner .

Generalization Analysis of SGD. A framework to study the generalization performance of large-scale stochastic optimization algorithms was established in Bousquet & Bottou , where three factors influencing generalization behavior were identified as optimization errors, estimation errors and approximation errors. Uniform stability was used to establish generalization bounds $O(1/\sqrt{n})$ in expectation for SGD for convex and strongly smooth cases . For convex and nonsmooth learning problems, generalization bounds $O(n^{-\frac{1}{3}})$ were established based on the uniform convergence principle . An interesting observation is that an implicit regularization can be achieved without an explicit regularizer by tuning either the number of passes or the step sizes . For the specific least squares loss, optimal excess generalization error bounds (up to a logarithmic factor) were established for SGD based on the integral operator approach . The above mentioned generalization results are in the form of expectation. High-probability bounds were established based on either an uniform-convergence approach or an algorithmic stability approach . A novel combination of PAC-Bayes and algorithmic stability was used to study the generalization behavior of SGD, a promising property of which is its applications to all posterior distributions of algorithms’ random hyperparameters .

Problem Formulation

We are interested in studying the excess generalization error $F(A(S))-F(\mathbf{w}^{*})$, where $\mathbf{w}^{*}\in\arg\min_{\mathbf{w}\in\Omega}F(\mathbf{w})$ is the one with the best prediction performance over $\Omega$. It can be decomposed as

The first term is called the estimation error due to the approximation of the unknown probability measure $\rho$ based on sampling. The second term is called the optimization error induced by running an optimization algorithm to minimize the empirical objective, which can be addressed by tools in optimization theory. A popular approach to control estimation errors is to consider the stability of the algorithm, for which a widely used stability measure is the uniform stability .

A stochastic algorithm $A$ is $\epsilon$-uniformly stable if for all training datasets $S,\widetilde{S}\in\mathcal{Z}^{n}$ that differ by at most one example, we have

The celebrated relationship between generalization and uniform stability is established in the following lemma .

Let $A$ be $\epsilon$-uniformly stable. Then

where $\partial f(\mathbf{w}_{t},z_{i_{t}})$ denotes a subgradient of $f$ w.r.t. the first argument and $i_{t}$ is independently drawn from the uniform distribution over $\{1,\ldots,n\}$.

Stability with Convexity

An essential assumption to establish the uniform stability of SGD is the uniform Lipschitz continuity (boundedness of gradients) of loss functions as follows .

We assume $\|\partial f(\mathbf{w};z)\|_{2}\leq G$ for all $\mathbf{w}\in\Omega$ and $z\in\mathcal{Z}$.

In this section, we will remove the boundedness assumption on the gradients for differentiable loss functions, and establish stability and generalization only under the assumption where loss functions have Hölder continuous (sub)gradients–a condition much weaker than the strong smoothness . Note that the loss functions can be non-differentiable if $\alpha=0$.

If (4.2) holds with $\alpha=1$, then $f$ is smooth as defined by (4.1). If (4.2) holds with $\alpha=0$, then this amounts to saying that $f$ is Lipschitz continuous as considered in Assumption 1. Examples of loss functions satisfying Definition 3 include the $q$-norm hinge loss f(\mathbf{w};z)=\big{(}\max(0,1\!-\!y\langle\mathbf{w},x\rangle)\big{)}^{q} for classification and the $q$-th power absolute distance loss $f(\mathbf{w};z)=|y\!-\!\langle\mathbf{w},x\rangle|^{q}$ for regression , whose (sub)gradients are $(q\!-\!1,C)$-Hölder continuous for some $C>0$ if $q\in$. If $q=1$, we get the hinge loss and absolute distance loss with wide applications in machine learning and statistics.

The key to remove the bounded gradient assumption and the strong smoothness assumption is the introduction of a novel stability measure which we refer to as the on-average model stability. We use the term “on-average model stability” to differentiate it from on-average stability in Kearns & Ron , Shalev-Shwartz et al. as we measure stability on model parameters $\mathbf{w}$ instead of function values. Intuitively, on-average model stability measures the on-average sensitivity of models by traversing the perturbation of each single coordinate.

Let $S,\widetilde{S}$ and $S^{(i)}$ be constructed as Definition 4. Let $\gamma>0$.

If for any $z$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative and $L$-smooth, then

If for any $z$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $\mathbf{w}\mapsto\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in$, then

2 Strongly smooth case

To justify the effectiveness of the on-average model stability, we first consider its application to learning with smooth loss functions. We first study stability and then generalization.

Assume for all $z\in\mathcal{Z}$, the map $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $L$-smooth. Let $S,\widetilde{S}$ and $S^{(i)}$ be constructed as Definition 4. Let $\{\mathbf{w}_{t}\}$ and $\{\mathbf{w}_{t}^{(i)}\}$ be produced by (3.3) with $\eta_{t}\leq 2/L$ based on $S$ and $S^{(i)}$, respectively. Then for any $p>0$ we have

The stability bounds in Theorem 3 can be extended to the non-convex case. Specifically, let assumptions of Theorem 3, except the convexity of $\mathbf{w}\mapsto f(\mathbf{w};z)$, hold. Then for any $p>0$ one gets (see Proposition C.3)

This result improves the recurrence relationship in Hardt et al. for uniform stability by replacing the uniform Lipschitz constant with empirical risks.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $L$-smooth. Let $\{\mathbf{w}_{t}\}$ be produced by (3.3) with nonincreasing step sizes satisfying $\eta_{t}\leq 1/(2L)$. If $\gamma\geq 1$, then

where \mathbf{w}_{T}^{(1)}=\big{(}\sum_{t=1}^{T}\eta_{t}\mathbf{w}_{t}\big{)}/\sum_{t=1}^{T}\eta_{t}.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $L$-smooth.

Let $\{\mathbf{w}_{t}\}$ be produced by (3.3) with $\eta_{t}=c/\sqrt{T}\leq 1/(2L)$ for a constant $c>0$. If $T\asymp n$, then

Let $\{\mathbf{w}_{t}\}$ be produced by (3.3) with $\eta_{t}=\eta_{1}\leq 1/(2L)$. If $F(\mathbf{w}^{*})=0$ and $T\asymp n$, then

We compare here our results with some fast bounds for SGD. Some fast convergence rates of SGD were recently derived for SGD under low noise conditions or growth conditions relating stochastic gradients to full gradients . The discussions there mainly focused on optimization errors, which are measured w.r.t. the iteration number $t$. As a comparison, our fast rates measured by $n$ are developed for generalization errors of SGD (Part (b) of Corollary 5), for which we need to trade-off optimization errors and estimation errors by stopping at an appropriate iteration number. Fast generalization bounds are also established for the specific least squares based on an integral operator approach . However, these discussions heavily depend on the structure of the square loss and require capacity assumptions in terms of the decay rate of eigenvalues for the associated integral operator. As a comparison, we consider general loss functions and do not impose a capacity assumption.

3 Non-smooth case

As a further application, we apply our on-average model stability to learning with non-smooth loss functions, which have not been studied in the literature.

Stability bounds. The following theorem to be proved in Appendix D.1 establishes stability bounds. As compared to (4.4), the stability bound below involves an additional term $O(\sum_{j=1}^{t}\eta_{j}^{\frac{2}{1-\alpha}})$, which is the cost we pay by relaxing the smoothness condition to a Hölder continuity of (sub)gradients. It is worth mentioning that our stability bounds apply to non-differentiable loss functions including the popular hinge loss.

Assume for all $z\in\mathcal{Z}$, the map $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in[0,1)$. Let $S,\widetilde{S}$ and $S^{(i)}$ be constructed in Definition 4. Let $\{\mathbf{w}_{t}\}$ and $\{\mathbf{w}_{t}^{(i)}\}$ be produced by (3.3) based on $S$ and $S^{(i)}$, respectively. Then

Generalization bounds. We now present generalization bounds for learning by loss functions with Hölder continuous (sub)gradients, which are specific instantiations of a general result (Proposition D.4) stated and proved in Appendix D.2.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex, and $\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in[0,1)$. Let $\{\mathbf{w}_{t}\}_{t}$ be given by (3.3) with $\eta_{t}=cT^{-\theta},\theta\in,c>0$.

Although relaxing smoothness affects stability by introducing $O(\sum_{j=1}^{t}\eta_{j}^{\frac{2}{1-\alpha}})$ in the stability bound, we achieve a generalization bound similar to the smooth case with a similar computation cost if $\alpha\geq 1/2$. For $\alpha<1/2$, a minimax optimal generalization bound $O(n^{-\frac{1}{2}})$ can be also achieved with more computation cost as $T\asymp n^{\frac{2-\alpha}{1+\alpha}}$. In particular, if $\alpha=0$ we develop the optimal generalization bounds $O(n^{-\frac{1}{2}})$ for SGD with $T\asymp n^{2}$ iterations. To our best knowledge, this gives the first generalization bounds for SGD with non-smooth loss functions (e.g., hinge loss) based on stability analysis. Analogous to the smooth case, we can derive generalization bounds better than $O(n^{-\frac{1}{2}})$ in the case with low noises. To our best knowledge, this is the first optimistic generalization bound for SGD with non-smooth loss functions.

We can extend our discussion to ERM. If $F_{S}$ is $\sigma$-strongly convex and $\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous, we can apply the on-average model stability to show (see Proposition D.6)

Stability with Relaxed Convexity

We now turn to stability and generalization of SGD for learning problems where the empirical objective $F_{S}$ is convex but each loss function $f(\mathbf{w};z)$ may be non-convex. For simplicity, we impose Assumption 1 here and use the arguments based on the uniform stability. The proofs of Theorem 8 and Theorem 9 are given in Appendix E.1.

The derivation of uniform stability bounds in Hardt et al. is based on the non-expansiveness of the operator $\mathbf{w}\mapsto\mathbf{w}-\partial f(\mathbf{w};z)$, which requires the convexity of $\mathbf{w}\mapsto f(\mathbf{w};z)$ for all $z$. Theorem 8 relaxes this convexity condition to a milder convexity condition on $F_{S}$. If $\sum_{j=1}^{\infty}\eta_{j}^{2}<\infty$, the stability bounds in Theorem 8 become $O(n^{-1}\sum_{j=1}^{t}\eta_{j}+n^{-\frac{1}{2}})$ since $C_{t}<\infty$.

As shown below, minimax optimal generalization bounds can be achieved for step sizes $\eta_{t}=\eta_{1}t^{-\theta}$ for all $\theta\in(1/2,1)$ as well as the step sizes $\eta_{t}\asymp 1/\sqrt{T}$ with $T\asymp n$.

Let Assumption 1 hold. Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is $L$-smooth. Let $\{\mathbf{w}_{t}\}_{t}$ be produced by (3.3). Suppose for all $S$, $F_{S}$ is convex.

If $\eta_{t}=\eta_{1}t^{-\theta},\theta\in(1/2,1)$, then

Example: AUC Maximization. We now consider a specific example of AUC (Area under ROC curve) maximization where the objective function is convex but each loss function may be non-convex. As a widely used method in imbalanced classification ($\mathcal{Y}=\{+1,-1\}$), AUC maximization was often formulated as a pairwise learning problem where the corresponding loss function involves a pair of training examples . Recently, AUC maximization algorithms updating models with a single example per iteration were developed . Specifically, AUC maximization with the square loss can be formulated as the minimization of the following objective function

An interesting property is that (5.2) involves only a single example $z$. This observation allows Natole et al. to develop a stochastic algorithm as (3.3) to solve (5.1). However, for each $z$, the function $z\mapsto f(\mathbf{w};z)$ is non-convex since the associated Hessian matrix may not be positively definite. It is clear that its expectation $F$ is convex.

Stability with Relaxed Strong Convexity

Finally, we consider learning problems with strongly convex empirical objectives but possibly non-convex loss functions. Theorem 10 provides stability bounds, while the minimax optimal generalization bounds $O(1/(\sigma n))$ are presented in Theorem 11. The proofs are given in Appendix F.

Let Assumptions in Theorem 8 hold. Suppose for all $S\subset\mathcal{Z}$, $F_{S}$ is $\sigma_{S}$-strongly convex. Then, there exists a constant $t_{0}$ such that for SGD with $\eta_{t}=2/((t+t_{0})\sigma_{S})$ we have

Let Assumption 1 hold. Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is $L$-smooth. Suppose for all $S\subset\mathcal{Z}$, $F_{S}$ is $\sigma_{S}$-strongly convex. Then, there exists some $t_{0}$ such that for SGD with $\eta_{t}=2/((t+t_{0})\sigma_{S})$ and $T\asymp n$ we have

where \mathbf{w}_{T}^{(2)}=\big{(}\sum_{t=1}^{T}(t+t_{0}-1)\mathbf{w}_{t}\big{)}/\sum_{t=1}^{T}(t+t_{0}-1).

2 Application: least squares regression

As we will see in the proof, Theorem 10 holds if only the following local strong convexity holds, i.e.,

Therefore, we can apply Theorem 10 with $\widetilde{S}=\bar{S}$ and $\sigma_{S}=\sigma_{S}^{\prime}$ to derive (note $\partial F_{S}(\mathbf{w})=C_{S}\mathbf{w}-\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}$)

Conclusions

In this paper, we study stability and generalization of SGD by removing the bounded gradient assumptions, and relaxing the smoothness assumption and the convexity requirement of each loss function in the existing analysis. We introduce a novel on-average model stability able to capture the risks of SGD iterates, which implies fast generalization bounds in the low-noise case and stability bounds for learning with even non-smooth loss functions. For all considered problems, we show that our stability bounds can imply minimax optimal generalization bounds by balancing optimization and estimation errors. We apply our results to practical learning problems to justify the superiority of our approach over the existing stability analysis. Our results can be extended to stochastic proximal gradient descent, high-probability bounds and SGD without replacement (details are given in Appendix G). In the future, it would be interesting to study stability bounds for other stochastic optimization algorithms, e.g., Nesterov’s accelerated variants of SGD .

Acknowledgement

The work of Y. Lei is supported by the National Natural Science Foundation of China (Grant Nos. 61806091, 11771012) and the Alexander von Humboldt Foundation. The work of Y. Ying is supported by the National Science Foundation (NSF) under Grant No. #1816227.

Appendix A Optimization Error Bounds

For a full picture of generalization errors, we need to address the optimization errors. This is achieved by the following lemma. Parts (a) and (b) consider the convex and strongly convex empirical objectives, respectively (we make no assumptions on the convexity of each $f(\cdot,z)$). Note in Parts (c) and (d), we do not make a bounded gradient assumption. As an alternative, we require convexity of $f(\cdot;z)$ for all $z$. An appealing property of Parts (c) and (d) is that it involves $O(\sum_{j=1}^{t}\eta_{j}^{2}F_{S}(\mathbf{w}))$ instead of $O(\sum_{j=1}^{t}\eta_{j}^{2})$, which is a requirement for developing fast rates in the case with low noises.

Our discussion on optimization errors requires to use a self-bounding property for functions with Hölder continuous (sub)gradients, which means that gradients can be controlled by function values. The case $\alpha=1$ was established in Srebro et al. . The case $\alpha\in(0,1)$ was established in Ying & Zhou . The case $\alpha=0$ follows directly from Definition 3. Define

Assume for all $z\in\mathcal{Z}$, the map $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, and $\mathbf{w}\mapsto\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in$. Then for $c_{\alpha,1}$ defined as (A.1) we have

where \mathbf{w}_{t}^{(1)}=\big{(}\sum_{j=1}^{t}\eta_{j}\mathbf{w}_{j}\big{)}/\sum_{j=1}^{t}\eta_{j}.

where \mathbf{w}_{t}^{(2)}=\big{(}\sum_{j=1}^{t}(j+t_{0}-1)\mathbf{w}_{j}\big{)}/\sum_{j=1}^{t}(j+t_{0}-1).

Parts (a) and (b) can be found in the literature . We only prove Parts (c) and (d). We first prove Part (c). The projection operator $\Pi_{\Omega}$ is non-expansive, i.e.,

By the SGD update (3.3), (A.3), convexity and Lemma A.1, we know

where the last inequality is due to $\eta_{t}\leq 1/(2L)$. It then follows that

Multiplying both sides by $\eta_{t}$ and using the assumption $\eta_{t+1}\leq\eta_{t}$, we know

Taking a summation of the above inequality gives ($\mathbf{w}_{1}=0$)

Taking an expectation w.r.t. $A$ gives (note $\mathbf{w}_{j}$ is independent of $i_{j}$)

On the other hand, taking an expectation w.r.t. $i_{t}$ over both sides of (A.4) shows

Taking an expectation on both sides followed with a summation, we get

where the last step is due to (A.5). The proof is complete since $\mathbf{w}$ is independent of $A$.

We now prove Part (d). Analogous to (A.4), one can show for loss functions with Hölder continuous (sub)gradients (Lemma A.1)

we know (notice the following inequality holds trivially if $\alpha=0$)

Combining the above two inequalities together, we get

Multiplying both sides by $\eta_{t}$ and using $\eta_{t+1}\leq\eta_{t}$, we derive

Taking a summation of the above inequality gives

According to the Jensen’s inequality and the concavity of $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$, we know

where in the last step we have used (A.8). Taking an expectation on both sides of (A.6), we know

Taking a summation of the above inequality gives

where we have used (A.9) and the concavity of $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$ in the last step. The proof is complete by noting the independence between $\mathbf{w}$ and $A$. ∎

Appendix B Proofs on Generalization by On-average Model Stability

To prove Theorem 2, we introduce an useful inequality for $L$-smooth functions $\mathbf{w}\mapsto f(\mathbf{w};z)$

where the last identity holds since $A(S^{(i)})$ is independent of $z_{i}$. Under Assumption 1, it is then clear that

We now prove Part (b). According to (B.1) due to the $L$-smoothness of $f$ and (B.2), we know

According to the Schwartz’s inequality we know

where the last inequality is due to the self-bounding property of smooth functions (Lemma A.1). Combining the above two inequalities together, we derive

The stated inequality in Part (b) then follows directly by noting $\frac{1}{n}\sum_{i=1}^{n}f(A(S);z_{i})=F_{S}(A(S))$.

Finally, we consider Part (c). By (B.2) and the convexity of $f$, we know

By the Schwartz’s inequality and Lemma A.1 we know

Combining the above two inequalities together, we get

Since $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$ is concave and $z_{i}$ is independent of $A(S^{(i)})$, we know

A combination of the above two inequalities then gives the stated bound in Part (c). The proof is complete. ∎

Appendix C Proof on Learning without Bounded Gradients: Strongly Smooth Case

A key property on establishing the stability of SGD is the non-expansiveness of the gradient-update operator established in the following lemma.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is convex and $L$-smooth. Then for $\eta\leq 2/L$ we know

Based on Lemma C.1, we establish stability bounds of models for SGD applied to two sets differing by a single example.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $L$-smooth. Let $S,\widetilde{S}$ and $S^{(i)}$ be constructed as Definition 4. Let $\{\mathbf{w}_{t}\}$ and $\{\mathbf{w}_{t}^{(i)}\}$ be produced by (3.3) with $\eta_{t}\leq 2/L$ based on $S$ and $S^{(i)}$, respectively. Then for any $p>0$ we have

If $i_{t}\neq i$, we know the updates of $\mathbf{w}_{t+1}$ and $\mathbf{w}_{t+1}^{(i)}$ are based on stochastic gradients calculated with the same example $z_{i_{t}}$. By Lemma C.1 we then get

where the second inequality follows from the sub-additivity of $\|\cdot\|_{2}$ and the last inequality is due to Lemma A.1 on the self-bounding property of smooth functions.

We first prove Eq. (C.1). Since $i_{t}$ is drawn from the uniform distribution over $\{1,\ldots,n\}$, we can combine Eqs. (C.3) and (C.5) to derive

Taking a summation of the above inequality and using $\mathbf{w}_{1}=\mathbf{w}_{1}^{(i)}$ then give (C.1).

We now turn to (C.2). For the case $i_{t}=i$, it follows from (C.4) and the standard inequality $(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ that

where the last inequality is due to Lemma A.1. Combining (C.3), the above inequality together and noticing the distribution of $i_{t}$, we derive

Multiplying both sides by $(1+p/n)^{-(t+1)}$ yields that

Taking a summation of the above inequality and using $\mathbf{w}_{1}=\mathbf{w}_{1}^{(i)}$, we get

We first prove (4.3). According to Lemma C.2 (Eq. (C.1)), we know

It then follows from the concavity of the square-root function and the Jensen’s inequality that

We now turn to (4.4). It follows from Lemma C.2 (Eq. (C.2)) that

Let Assumptions of Theorem 3 hold except that we do not require the convexity of $\mathbf{w}\mapsto f(\mathbf{w};z)$. Then for any $p>0$ we have

If $i_{t}\neq i$, then by the $L$-smoothness of $f$ we know

If $i_{t}=i$, then analogous to (C.7), one can get

By the uniform distribution of $i_{t}\in\{1,2,\ldots,n\}$ we can combine the above inequality and (C.9) to derive

C.2 Generalization bounds

We now prove generalization bounds for SGD.

According to Part (c) of Lemma A.2 with $\mathbf{w}=\mathbf{w}^{*}$, we know the following inequality

Let $A(S)$ be the $(t+1)$-th iterate of SGD applied to the dataset $S$. We plug (4.4) into Part (b) of Theorem 2, and derive

We can plug (A.5) with $\mathbf{w}=\mathbf{w}^{*}$ into the above inequality, and derive

Multiplying both sides by $\eta_{t+1}$ followed with a summation gives

Putting (C.10) into the above inequality then gives

The stated inequality then follows from Jensen’s inequality. The proof is complete. ∎

We first prove Part (a). For the chosen step size, we know

The stated bound (4.5) then follows from Theorem 4, $\gamma=\sqrt{n}$ and (C.11).

We now prove Part (b). The stated bound (4.6) then follows from Theorem 4, $F(\mathbf{w}^{*})=0$ and $\gamma=1$. The proof is complete. ∎

Appendix D Proof on Learning without Bounded Gradients: Non-smooth Case

Theorem 6 is a direct application of the following general stability bounds with $p=n/t$. Therefore, it suffices to prove Theorem D.1.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex and $\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in[0,1)$. Let $S,\widetilde{S}$ and $S^{(i)}$ be constructed as Definition 4 and $c_{\alpha,3}=\frac{\sqrt{1-\alpha}}{\sqrt{1+\alpha}}(2^{-\alpha}L)^{\frac{1}{1-\alpha}}$. Let $\mathbf{w}_{t}$ and $\mathbf{w}_{t}^{(i)}$ be the $t$-th iterate produced by (3.3) based on $S$ and $S^{(i)}$, respectively. Then for any $p>0$ we have

We require several lemmas to prove Theorem D.1. The following lemma establishes the co-coercivity of gradients for convex functions with Hölder continuous (sub)gradients. The case $\alpha=1$ can be found in Nesterov . The case $\alpha\in(0,1)$ can be found in Ying & Zhou . The case $\alpha=0$ follows directly from the convexity of $f$.

The following lemma controls the expansive behavior of the operator $\mathbf{w}\mapsto\mathbf{w}-\eta\partial f(\mathbf{w};z)$ for convex $f$ with Hölder continuous (sub)gradients.

We first consider the case $\alpha=0$. In this case, it follows from Definition 3 and Lemma D.2 with $\alpha=0$ that

We now consider the case $\alpha>0$. According to Lemma D.2, we know

where we have used Young’s inequality (A.7). Plugging the above inequality back into (D.3), we derive

Combining the above two cases together, we get the stated bound with the definition of $c_{\alpha,3}$ given in Theorem D.1. The proof is complete. ∎

For the case $i_{t}\neq i$, it follows from Lemma D.3 that

If $i_{t}=i$, by (C.4) and the standard inequality $(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$, we get

Combining the above two inequalities together, using the self-bounding property (Lemma A.1) and noticing the distribution of $i_{t}$, we derive

Multiplying both sides by $(1+p/n)^{-(t+1)}$ gives

Taking a summation of the above inequality and using $\mathbf{w}_{1}=\mathbf{w}_{1}^{(i)}$, we derive

It then follows from the concavity of the function $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$ and the Jensen’s inequality that

The stated inequality then follows from the definition of $F_{S}$. The proof is complete. ∎

D.2 Generalization errors

Theorem 7 can be considered as an instantiation of the following proposition on generalization error bounds with specific choices of $\gamma,T$ and $\theta$. In this subsection, we first give the proof of Theorem 7 based on Proposition D.4, and then turn to the proof of Proposition D.4.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex, and $\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in[0,1)$. Let $\{\mathbf{w}_{t}\}_{t}$ be produced by (3.3) with step sizes $\eta_{t}=cT^{-\theta},\theta\in$ satisfying $\theta\geq(1-\alpha)/2$. Then for all $T$ satisfying $n=O(T)$ and any $\gamma>0$ we have

It can be checked that $\theta$ considered in Parts (a)-(c) satisfy $\theta\geq(1-\alpha)/2$. Therefore Proposition D.4 holds. If $\gamma=\sqrt{n}$, then by Proposition D.4 we know

We first prove Part (a). Since $\alpha\geq 1/2$, $\theta=1/2$ and $T\asymp n$, it follows from (D.4) that

where we have used $\frac{3}{2}-\frac{1}{1-\alpha}\leq-\frac{1}{2}$ due to $\alpha\geq 1/2$. This shows Part (a).

We now prove Part (b). Since $\alpha<1/2$, $T\asymp n^{\frac{2-\alpha}{1+\alpha}}$ and $\theta=\frac{3-3\alpha}{2(2-\alpha)}\geq 1/2$ in (D.4), the following inequalities hold

where we have used $(3\alpha-3)/(1+\alpha)\leq-1$ due to $\alpha<1/2$. Furthermore, since $\theta\geq 1/2$ and $\alpha<1/2$ we know $\frac{\alpha\theta-\theta-2\alpha}{1+\alpha}\leq-\frac{1}{2}$ and $T\asymp n^{\frac{2-\alpha}{1+\alpha}}\geq n$. Therefore $T^{\frac{\alpha\theta-\theta-2\alpha}{1+\alpha}}=O(T^{-\frac{1}{2}})=O(n^{-\frac{1}{2}})$. Plugging the above inequalities into (D.4) gives the stated bound in Part (b).

We now turn to Part (c). Since $F(\mathbf{w}^{*})=0$, Proposition D.4 reduces to

With $\gamma=nT^{\theta-1}$, we further get

For the choice $T=n^{\frac{2}{1+\alpha}}$ and $\theta=\frac{3-\alpha^{2}-2\alpha}{4}$, we know $1-\theta=(1+\alpha)^{2}/4$ and therefore

Plugging the above inequalities into (D.5) gives the stated bound in Part (c). The proof is complete. ∎

To prove Proposition D.4, we first introduce an useful lemma to address some involved series.

Assume for all $z\in\mathcal{Z}$, the function $\mathbf{w}\mapsto f(\mathbf{w};z)$ is nonnegative, convex, and $\partial f(\mathbf{w};z)$ is $(\alpha,L)$-Hölder continuous with $\alpha\in[0,1)$. Let $\{\mathbf{w}_{t}\}_{t}$ be produced by (3.3) with step sizes $\eta_{t}=cT^{-\theta},\theta\in$ satisfying $\theta\geq\frac{1-\alpha}{2}$. Then

We first prove (D.6). For the step size sequence $\eta_{t}=cT^{-\theta}$, we have

where we have used the subadditivity of $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$, the identity

in the second step and $\theta\geq(1-\alpha)/2$ in the third step (the third term is dominated by the first term). This shows (D.6).

We now consider (D.7). Taking an expectation over both sides of (A.8) with $\mathbf{w}=\mathbf{w}^{*}$, we get

According to the Jensen’s inequality and the concavity of $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$, we know

where we have used (D.6) in the last step. This shows (D.7).

Finally, we show (D.8). Since we consider step sizes $\eta_{t}=cT^{-\theta}$, it follows from (D.7) that

This proves (D.8) and finishes the proof. ∎

Our idea is to address separately the above estimation error and optimization error.

We first address estimation errors. Plugging (D.1) back into Theorem 2 (Part (c)) with $A(S)=\mathbf{w}_{t+1}$, we derive

By the concavity and sub-additivity of $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$, we know

Solving the above inequality of $\delta_{t+1}$ gives the following inequality for all $t\leq T$

It then follows from the definition of $\delta_{t}$ that (note $n=O(T)$)

By $\eta_{t}=cT^{-\theta}$, (D.7) and (D.8), we further get

We now consider optimization errors. By Lemma A.2 (Part (d) with $\mathbf{w}=\mathbf{w}^{*}$) and the concavity of $x\mapsto x^{\frac{2\alpha}{1+\alpha}}$, we know

where we have used (D.6) in the last step.

Plugging the above optimization error bound and the estimation error bound (D.10) back into the error decomposition (D.9), we finally derive the following generalization error bounds

The stated inequality then follows from the convexity of $F$. The proof is complete. ∎

D.3 Empirical Risk Minimization with Strongly Convex Objectives

Let $\widetilde{S}$ and $S^{(i)},i=1,\ldots,n$, be constructed as Definition 4. Due to the $\sigma$-strong convexity of $F_{S^{(i)}}$ and $\partial F_{S^{(i)}}(A(S^{(i)}))=0$ (necessity condition for the optimality of $A(S^{(i)})$), we know

Taking a summation of the above inequality yields

According to the definition of $S^{(i)}$, we know

Taking an expectation and dividing both sides by $n^{2}$ give ($A(S)$ is independent of $\widetilde{S}$)

Plugging the above identity and (D.12) back into (D.11) gives

We can now apply Part (c) of Theorem 2 to show the following inequality for all $\gamma>0$ (notice $A$ is a deterministic algorithm)

from which we can derive the stated inequality. The proof is complete. ∎

Appendix E Proofs on Stability with Relaxed Convexity

The event $i_{t}=1$ happens with probability $1/n$, and in this case

Plugging (E.3) and the above inequality back into (E.2), we derive

To prove Theorem 9, we require a basic result on series.

We have the following elementary inequalities.

If $\theta\in(0,1)$, then $(t^{1-\theta}-1)/(1-\theta)\leq\sum_{k=1}^{t}k^{-\theta}\leq t^{1-\theta}/(1-\theta)$;

If $\theta>1$, then $\sum_{k=1}^{t}k^{-\theta}\leq\frac{\theta}{\theta-1}$.

For the step sizes considered in both Part (a) and Part (b), one can check that $\sum_{t=1}^{T}\eta_{t}^{2}$ can be upper bounded by a constant independent of $T$. Therefore, $C_{t}<C$ for all $t=1,\ldots,T$ and a universal constant $C$. We can apply Lemma A.2 (Part (a)) on optimization errors to get

For the step sizes $\eta_{t}=\eta_{1}t^{-\theta}$ with $\theta\in(1/2,1)$, we can apply Lemma E.1 to show

Part (b) follows by plugging (C.11) into (E.7). The proof is complete. ∎

Appendix F Proofs on Stability with Relaxed Strong Convexity

Due to the $\sigma_{S}$-strong convexity of $F_{S}$, we can analyze analogously to (E.4) to derive

Therefore, analogous to the derivation of (E.5) we can derive

We find $t_{0}\geq 4L^{2}/\sigma_{S}^{2}$. Then $\eta_{t}\leq\sigma_{S}/(2L^{2})$ and it follows that

Multiplying both sides by $(t+t_{0})(t+t_{0}-1)$ yields

The stated bound then follows from the elementary inequality $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$. The proof is complete. ∎

It then follows from (3.1) and Part (a) of Theorem 2 that

The stated bound holds since $T\asymp n$. The proof is complete. ∎

Let $S=\{z_{1},\ldots,z_{n}\}$ and $C_{S}=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}$. Then the range of $C_{S}$ is the linear span of $\{x_{1},\ldots,x_{n}\}$.

It suffices to show that the kernel of $C_{S}$ is the orthogonal complement of $V=\text{span}\{x_{1},\ldots,x_{n}\}$ (we denote $\text{span}\{x_{1},\ldots,x_{n}\}$ the linear span of $x_{1},\ldots,x_{n}$). Indeed, for any $x$ in the kernel of $C_{S}$, we know $C_{S}x=0$ and therefore $x^{\top}C_{S}x=\frac{1}{n}\sum_{i=1}^{n}(x_{i}^{\top}x)^{2}=0$, from which we know that $x$ must be orthogonal to $V$. Furthermore, for any $x$ orthogonal to $V$, it is clear that $C_{S}x=0$, i.e., $x$ belongs to the kernel of $C_{S}$. The proof is complete. ∎

Appendix G Extensions

In this section, we present some extensions of our analyses. We consider three extensions: extension to stochastic proximal gradient descent, extension to high probability analysis and extension to SGD without replacement.

G.2 Stability bounds with high probabilities

We can also extend our stability bounds stated in expectation to high-probability bounds, which would be helpful to understand the fluctuation of SGD w.r.t. different realization of random indices.

High-probability generalization bounds can be derived by combining the above stability bounds and the recent result on relating generalization and stability in a high-probability analysis .

To prove Proposition G.1, we need to introduce a special concentration inequality called Chernoff’s fs bound for a summation of independent Bernoulli random variables .

Combining the above two cases together, we derive

Taking a summation of the above inequality then yields

Therefore, for the step size $\eta_{j}=ct^{-\theta},j=1,\ldots,t$, we know

G.3 SGD without replacement

where $\{\eta_{t}^{k}\}$ is the step size sequence. We set $\mathbf{w}^{k+1}_{1}=\mathbf{w}^{k}_{n+1}$, i.e., each epoch starts with the last iterate of the previous epoch. The following proposition establishes stability bounds for SGD without replacement when applied to loss functions with Hölder continuous (sub)gradients.

Taking a summation of the above inequality from $t=1$ to $n$ gives

Let $i^{k}$ be the unique $t\in\{1,\ldots,n\}$ such that $i_{t}^{k}=1$. Since $\mathbf{w}^{k+1}_{1}=\mathbf{w}^{k}_{n+1}$, we derive

Since we draw $(i^{k}_{1},\ldots,i^{k}_{n})$ from the uniform distribution of all permutations, $i^{k}$ takes an equal probability to each $1,\ldots,n$. Therefore, we can take expectations over $A$ to derive

We can take a summation of the above inequality from $k=1$ to $K$ to derive the stated bound. The proof is complete. ∎

References