Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems

Stochastic optimization has found wide applications in minimizing objective functions in machine learning, which motivates a lot of theoretical studies to understand its practical success. Most of existing studies focus on the convergence of optimization errors, while the generalization analysis of stochastic optimization is much lagging behind. This is especially the case for nonconvex and nonsmooth problems often encountered in practice. In this paper, we initialize a systematic stability and generalization analysis of stochastic optimization on nonconvex and nonsmooth problems. We introduce novel algorithmic stability measures and establish their quantitative connection on the gap between population gradients and empirical gradients, which is then further extended to study the gap between the Moreau envelope of the empirical risk and that of the population risk. To our knowledge, these quantitative connection between stability and generalization in terms of either gradients or Moreau envelopes have not been studied in the literature. We introduce a class of sampling-determined algorithms, for which we develop bounds for three stability measures. Finally, we apply these discussions to derive error bounds for stochastic gradient descent and its adaptive variant, where we show how to achieve an implicit regularization by tuning the step sizes and the number of iterations.


Yunwen Lei
Abstract-Stochastic optimization has found wide applications in minimizing objective functions in machine learning, which motivates a lot of theoretical studies to understand its practical success. Most of existing studies focus on the convergence of optimization errors, while the generalization analysis of stochastic optimization is much lagging behind. This is especially the case for nonconvex and nonsmooth problems often encountered in practice. In this paper, we initialize a systematic stability and generalization analysis of stochastic optimization on nonconvex and nonsmooth problems. We introduce novel algorithmic stability measures and establish their quantitative connection on the gap between population gradients and empirical gradients, which is then further extended to study the gap between the Moreau envelope of the empirical risk and that of the population risk. To our knowledge, these quantitative connection between stability and generalization in terms of either gradients or Moreau envelopes have not been studied in the literature. We introduce a class of sampling-determined algorithms, for which we develop bounds for three stability measures. Finally, we apply these discussions to derive error bounds for stochastic gradient descent and its adaptive variant, where we show how to achieve an implicit regularization by tuning the step sizes and the number of iterations.
Index Terms-Algorithmic Stability, Learning Theory, Stochastic Optimization

I. INTRODUCTION
S TOCHASTIC optimization has become the workhorse behind many successful applications of machine learning (ML) [1,2]. The basic idea is to introduce randomness into the design of optimization algorithms to speed up the learning process by using the sum structure of objective functions in ML. A representative algorithm is the stochastic gradient descent (SGD). As an iterative algorithm, SGD first randomly selects a single example from a training dataset to build a stochastic gradient, and then moves along the negative direction of this stochastic gradient to get the next iterate. Due to its cheap computation cost and simplicity, SGD is especially interesting to solve large-scale and complex learning problems. In the last decade, SGD has been improved in various directions from the viewpoint of Nesterov acceleration [3], variance reduction [4][5][6][7][8] and adaptive learning rates [9][10][11].
Motivated by the increasing popularity, researchers have studied the theoretical behavior of stochastic optimization. Depending on the property of objective functions, one can measure the progress of optimization in terms of different Yunwen Lei is with the School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom (e-mail: y.lei@bham.ac.uk). performance metrics. For strongly convex problems, one can use the distance between the output model and the best model as the performance measure since there is only a unique minimizer [2,12]. For convex problems, one can develop convergence rates in terms of functional suboptimality gap since there may exist several models with the same global function value [1]. For nonconvex and smooth problems, one can measure the performance through the magnitude of gradients since an algorithm is only guaranteed to find a local minimum [13]. The performance metric becomes more tricky for nonconvex and nonsmooth problems [14,15]. For an objective function ψ, neither the functional suboptimality gap ψ(w t )−inf ψ(w), nor the stationarity measure, dist(0, ∂ψ(w t )), necessarily decay to zero along the optimization process [14]. Here w t denotes an iterate of the algorithm, ∂ψ(w t ) denotes the subdifferential and dist denotes the Euclidean distance function. Recently, Davis and Drusvyatskiy [14] proposed to use the Moreau envelope ψ λ (w) = inf v ψ(v) + 1 2λ v − w 2 2 as a useful potential function to study stochastic optimization for weakly convex problems. An intuitive understanding is that a small gradient ∇ψ λ (w t ) 2 implies that w t is near some point that is nearly stationary for the problem min w ψ(w), which motivates the use of the performance measure ∇ψ λ (w t ) 2 for weakly convex problems. Weakly convex problems form an importance class of nonconvex and nonsmooth problems, with instantiations in various application domains such as phase retrieval, robust principal component analysis, covariance matrix estimation and sparse dictionary learning [14].
Most of existing studies focus on the convergence behavior of stochastic optimization algorithms from the perspective of optimization, i.e., how the trained model would behave on training examples. However, in ML we are more interested in the prediction behavior from the perspective of learning [16], i.e., how these models would behave on testing examples, which is much less studied for stochastic optimization. The gap between training and testing is a central topic in statistical learning theory (SLT). There are two major approaches to study the generalization gap: a uniform convergence approach based on the complexity analysis of hypothesis spaces [17] and an algorithmic stability approach based on the sensitivity analysis of algorithms [18] (for simplicity we always mean algorithmic stability when mentioning stability). Uniform convergence analysis applies to nonconvex problems, which, however, often leads to a square-root dependency on the dimensionality and therefore unfavorable for highdimensional learning problems [19]. Stability analysis can yield dimension-free bounds, which, however, often requires strong assumptions on loss functions such as convexity or smoothness. For example, most of the algorithmic stability analysis of stochastic optimization requires a convexity and a smoothness assumption [20][21][22]. The smoothness assumption is removed in the recent study [23,24]. In particular, the paper [24] develops matching lower bounds for convex and nonsmooth problems. For nonconvex problems, one typically requires a Polyak-Lojasiewicz (PL) condition to get nontrivial error bounds of SGD [25][26][27]. In the general nonconvex case, the stability analysis of SGD requires very small step sizes to get meaningful stability bounds [20,21], for which one cannot get meaningful optimization error bounds within reasonable computations. The strong assumption restricts the application domain of stability analysis for nonconvex and nonsmooth problems, which are often encountered in practice. To our knowledge, there is no stability analysis of stochastic optimization for problems that are simultaneously nonconvex and nonsmooth without restrictive assumptions such as the PL condition.
In this paper, we initialize the stability and generalization analysis of stochastic optimization for weakly convex problems, where the objective functions are nonconvex and nonsmooth. As a runner up, we first consider convex and nonsmooth problems, then nonconvex and smooth problems, and finally move onto weakly convex problems. As indicated before, we require to use different metrics to measure the generalization performance, which also asks for different stability measures as well as a different connection between stability and generalization. Our contributions are summarized as follows.
(a) We introduce a novel stability measure called uniform stability in gradients, and establish its quantitative relationship to the generalization measured by gradients for smooth problems. In particular, we show that the gap between population and empirical gradients can be bounded by our stability measure plus O(1/ √ n), where n is the sample size.
(b) We consider a specific class of nonconvex and nonsmooth problems called weakly convex problems, for which we measure the performance of trained models by Moreau envelopes. We develop, to our best knowledge, the first connection between argument stability and the generalization gap measured by Moreau envelopes. (c) We introduce the concept of sampling-determined algorithms, for which we establish stability bounds in terms of either function values, gradients or arguments. (d) We apply our results to SGD and its adaptive variant. For nonconvex and smooth problems, we develop the first stability-based risk bounds without the PL condition. We also develop the first risk bounds in terms of Moreau envelops for weakly convex problems. Furthermore, we develop differential private SGD for weakly convex problems and study its utility in generalization.
The paper is organized as follows. We present the related work in Section II, and introduce the problem setup in Section III. We discuss general stability and generalization bounds in Section IV, which are applied to specific algorithms in Section V. We present the proofs on connecting stability and generalization in Section VI, and put other proofs in the supplementary material. We conclude the paper in Section VII.

II. RELATED WORK
In this section, we review the related work on generalization analysis. We will focus on two approach: the algorithmic stability approach and the uniform convergence approach. Algorithmic Stability. We first review the related work on algorithmic stability. Algorithmic stability is a fundamental concept in SLT to measure the sensitivity of an algorithm up to a perturbation of the training dataset, which is closely related to learnability [28,29]. There are various algorithmic stability concepts. Some stability concepts measure the sensitivity in terms of function values, e.g., uniform stability [18], hypothesis stability [18,30], Bayes stability [31], locally elastic stability [32] and on-average stability [21,28], while others measure the sensitivity in terms of output models, e.g., argument stability [33] and on-average argument stability [23]. A most widely used stability concept is the uniform stability [18], which can imply almost optimal generalization bounds with high probability [19,34,35]. The celebrated connection between stability and generalization motivates the discussions of stability for many specific algorithms, including regularization algorithms [18], stochastic optimization algorithms [20,21,25,27,36,37], iterative hard thresholding [38], structured prediction [39], meta learning [40], transfer learning [21], multi-task learning [41], learning with graphdependent data [42], hyperparameter optimization [43] and adversarial training [44]. In particular, the influential work gives the first stability analysis of SGD applied to convex and smooth problems [20]. The smoothness assumption is removed in the recent study [23,24], and a tighter lower bound on the stability of SGD was developed [24]. Uniform Convergence. The trained models have a bias toward training datasets, which motivates the generalization analysis by the uniform convergence approach to study the difference between training and testing over the whole hypothesis space. Initially, the uniform convergence was mainly studied in terms of function values [17], which, however, is not appropriate to stochastic optimization with nonconvex loss functions. The underlying reason is that an algorithm can only guarantee to find a local minimizer (one cannot get convergence rate of training errors to the that of the best model). Then, the uniform convergence of function values fail to show the convergence of testing errors to that of the best model. Instead, one has to turn to other performance measures such as the gradients of risks for smooth problems [13] and the gradients of Moreau envelope for weakly convex problems [14]. In particular, Ghadimi and Lan [13] gave the first nonasymptotical convergence rate of the gradient norm. Motivated by this observation, the uniform convergence for gradients have been recently studied [15,[45][46][47]. The work [45] initialized the discussion on the uniform convergence of gradients by characterizing the complexity of function spaces with covering numbers, which was extended to the uniform convergence in terms of Rademacher complexities [46]. These discussions are devoted to control the uniform deviation between gradients of empirical and population risks under a smoothness condition. For nonsmooth problems, the gradients are not well defined since the functions may not be differentiable. This problem was recently addressed by considering the gradients of Moreau envelope of empirical/population risks [15], which are appropriate stationary measures for weakly convex problems. Specifically, the uniform deviation of gradients for the Moreau envelope between empirical and population risks was studied based on covering numbers [15].
Other than the above two approaches, there are also interesting discussions on generalization analysis by using tools in integral operators [48][49][50] and information theory [51].

III. PROBLEM SETUP
Let ρ be a probability measure defined on a sample space Z := X × Y, from which a dataset S = {z 1 , . . . , z n } are independently drawn. Based on S, we wish to build a model h : X → Y for prediction. We consider a parametric learning setting where the model can be determined by a parameter w in a parameter space W ⊂ R d . The performance of a model w on a single example z can be quantified by a loss function f : W × Z → R + . The training and testing behavior of w then can be measured by the empirical risk F S (w) and the population risk F (w) defined by where E Z denotes the expectation w.r.t. Z. Let w * = arg min w∈W F (w) be the model with the minimal population risk in W. Let A be a randomized learning algorithm and A(S) be the output model when applying A to the dataset S. In this paper, we are interested in the quality of A(S) in prediction under different performance measures. We require necessary definitions on Lipschitz continuity, smoothness and convexity. Let · 2 denote the Euclidean norm and ∇g(w) denote a subgradient of g at w. If g is differentiable then ∇g(w) becomes the gradient of g at w.
We say g is ρ-weakly-convex if w → g(w)+ ρ 2 w 2 2 is convex, and ρ-strongly Weakly convex functions are widespread in applications with a common source being the composite function class: g(w) := h(c(w)), where h : R m → R is convex and G-Lipschitz and c : R d → R m has β-Lipschitz continuous Jacobians [14]. We will use error decomposition to study the generalization behavior of learning models. Depending on the property of learning tasks, we will introduce different error decompositions.
For convex learning problems, a learning algorithm can be guaranteed to produce a model with a small empirical error. Therefore, we quantify the behavior of a model by the associated population risk. A standard approach to studying the population risk is to decompose it into two error terms [52] where we have used E S,A [F S (w * )] = F (w * ) since w * is independent of A and S. We refer to the term F (A(S)) − F S (A(S)) in (III.1) as the generalization error since it is related to the generalization from the training behavior to testing behavior. The second term F S (A(S)) − F S (w * ) is called the optimization error since it quantifies how well the algorithm minimizes the empirical risk. We will apply stability analysis to study the generalization error, and tools in optimization theory to study the optimization error.
For nonconvex and smooth learning problems, a learning algorithm can only be guaranteed to produce an approximate stationary point, i.e., a point w with a small ∇F S (w) 2 . In this case, the population risk is not a reasonable quality measure since there may be many local minimizers with different risks. As an alternative, we use the population gradient norm as the performance measure. We use the following error decomposition We call the first term ∇F (w)−∇F S (w) 2 the generalization error for smooth problems, and ∇F S (w) 2 the optimization error (empirical gradient norm). We will introduce a novel stability concept as well as its connection to generalization to study the generalization error for nonconvex problems. The optimization error is well studied in the literature [13]. For weakly convex learning problems, we cannot measure the quality of a model by gradients since the function may not be differentiable. An elegant performance measure is in terms of the Moreau envelope.

A. Connecting Stability and Generalization
As a fundamental concept in SLT, algorithmic stability measures the insensitiveness on the behavior of an algorithm under a perturbation of a single example. The uniform stability and uniform argument stability were discussed in the literature [18]. To tackle the performance measure in terms of gradient norms for nonconvex learning problems, we introduce a novel uniform stability in gradients. We say S, S ′ are neighboring datasets if they differ by at most a single example.
Definition 3 (Uniform Stability). Let A be a randomized algorithm. We say A is ǫ-uniformly-stable in function values if for all neighboring datasets S, S ′ , we have We say A is ǫ-uniformly-argument-stable if for all neighboring datasets S, S ′ , we have We say A is ǫ-uniformly-stable in gradients if for all neighboring datasets S, S ′ , we have Remark 1. The motivation of introducing the gradient-based stability is to use it to study the generalization performance for nonconvex problems. For nonconvex problems, an optimization algorithm generally only finds a local minimizer, and therefore one cannot use the function value to measure the convergence (the local minimizer the algorithm finds may be far away from the global minimizer and therefore the convergence in function values do not make much sense).
In this case, one often studies the convergence of ∇F S in the optimization community [13]. To use this convergence to study the behavior of A(S) in prediction, we need to address ∇F (A(S)) − ∇F S (A(S)) 2 , which, as we will see, can be achieved by stability in gradients. In summary, the stability on gradients allows us to incorporate the existing optimization error bounds to study the prediction performance as measured by ∇F (A(S)) 2 .
The connection between uniform stability in function values and generalization is given in the following lemma [20,28]. We give the proof in Section VI-A for completeness.

Lemma 1 (Generalization via Stability in Function Values). Let
Our first result is a connection between generalization and stability in gradients. This result cannot be derived by using the standard arguments in the literature [20,28] since one can not exchange the summation operator and norm. We will give more explanations in the proof, which is given in Section VI-A.

Theorem 2 (Generalization via Stability in Gradients). Let
A be ǫ-uniformly-stable in gradients. Assume for any z, the function f (w; z) is differentiable. Then is the variance of ∇f (A(S); Z) as a function of the random variable Z.

Remark 2.
Note the left-hand side of Eq. (IV.4) can be addressed by the uniform convergence of gradients sup w∈W ∇F (w) − ∇F S (w) 2 , which was established in terms of covering numbers [45] and Rademacher complexities [46]. These bounds generally involve a square-root dependency on the dimensionality of W. As a comparison, Theorem 2 considers the convergence of empirical gradients to population gradients at the particular model A(S). Therefore, it implies dimension-free generalization bounds which would be effective for high-dimensional learning problems.
Our second result is a connection between the uniform argument-stability and generalization measured by the Moreau envelope for weakly convex problems. Theorem 3 shows that the difference between empirical and population gradients of the Moreau envelope at A(S) can be bounded by the uniform argument stability of A. With this result, we can transfer the existing bound on ∇F S 2 to ∇F 2 on the performance of models for prediction. The proof of Theorem 3 is totally different from that of Theorem 2. The proof is given in Section VI-B.

Theorem 3 (Generalization via Uniform Argument Stability).
Let A be ǫ-argument stable. Assume for any z, the function f (w; z) is G-Lipschitz continuous. Assume for any S, the function F S is ρ-weakly-convex and F is ρ-weakly-convex. Then Remark 3. For ρ-weakly convex f , the uniform convergence sup w∈W ∇F S,1/(2ρ) (w) − ∇F 1/(2ρ) (w) 2 was studied in terms of the covering number of W [15], which generally involves a square-root dependency on the dimensionality. For example, if W is a ball in R d , then the following result was established [15] sup (IV.6) The underlying reason to consider a uniform convergence is noting the dependency of A(S) in Eq. (IV.5) on S. We address this dependency by giving a bound in terms of the argument stability of A. Theorem 3 yields dimension-free bounds since it only considers the convergence of ∇F S,1/(2ρ) to ∇F 1/(2ρ) at the particular output model A(S). It shows how the argument stability of A would affect the convergence rate.
Finally, we give a high-probability bound on the generalization gap measured by the Moreau envelope. The proof is given in Section VI-B.
Theorem 4 (High-probability Bound via Uniform Argument Stability). Let A be ǫ-argument stable almost surely, i.e., Assume for any S, the function F S is ρ-weakly-convex and F is ρ-weakly-convex. For any δ ∈ (0, 1), the following inequality holds with probability at least 1 − δ .

B. Stability Bounds
We now consider a class of randomized algorithms called sampling-determined algorithms for our stability analysis. We say a randomized algorithm A is symmetric if its output is independent on the order of the elements in the training set.
Definition 4 (Sampling-determined Algorithm). Let A be a randomized algorithm which randomly chooses an index sequence I(A) = {i t } to build stochastic gradients. We say a symmetric algorithm A is sampling-determined if the output model is determined by An important property of sampling-determined algorithms is that these algorithms will produce the same model when applied to two neighboring datasets if the differing example is not selected in the algorithm. For example, if two neighboring datasets differ by the first example and the index 1 is not selected by the algorithm, then the algorithm would produce the same model when applied to these two neighboring datasets. This property is critical for us to study the stability. The class of sampling-determined algorithms include several famous randomized algorithms. Below, we give some representative algorithms. The first algorithm is the SGD, which is a most simple and most popular stochastic optimization algorithm.
Let Π W (w) denote the projection of w onto W. Note W can be R d and in this case there is no projection.
Definition 5 (Stochastic Gradient Descent). Let w 1 = 0 ∈ R d be an initial point and {η t } t be a sequence of positive step sizes. SGD updates models by where ∇f (w t , z it ) denotes a subgradient of f w.r.t. the first argument and i t is independently drawn from the uniform distribution over [n] := {1, 2, . . . , n}.
The second algorithm is an adaptive variant of SGD, which introduces a sequence {b 2 t } to store the accumulated gradient norm square [9,53,54]. We then set the step size as the reciprocal of b t multiplied by a parameter η [54]. This algorithm has a nice advantage of being able to adapt the level of stochastic noise of the problem, and can achieve robust convergence without the need to fine-tune stepsize schedule.
is not selected in the implementation of A. Therefore, both SGD and AdaGrad-Norm are sampling-determined algorithms and It is also clear from the definition that Adam is a sampling-determined algorithm.
Remark 5. There are also some randomized algorithms that are not sampling-determined. A notable example is the stochastic variance reduction gradient (SVRG) [4]. Note that SVRG is implemented in epochs, for each of which we need to compute the full gradient at a reference point. Therefore, SVRG will produce different models when applied to neighboring datasets even if the differing example is not selected to compute a stochastic gradient. One can also check that other variance reduction algorithms are not sampling-determined, including stochastic dual coordinate ascent [55], stochastic average gradient [5] and SAGA [6].
The following theorem to be proved in Section B (supplementary material) establishes the uniform stability bounds for sampling-determined algorithms. It shows that the uniform stability of a sampling-determined algorithm A can be bounded by the probability of an index not selected in I(A). We consider stability in function values (Part (a)), stability in gradients (Part (b)) and stability in arguments (Part (c)). The proof is motivated by the arguments in Hardt et al. [20].
Theorem 5. Let A be a sampling-determined algorithm and S, S ′ be neighboring datasets.
We can derive the following corollary by tackling the probability Pr{n ∈ I(A)}. The proof is given in Section B.
Corollary 6. Let A be either SGD or AdaGrad-Norm with T iterations and S, S ′ be neighboring datasets.
Remark 6. Since we consider symmetric algorithms, the condition n ∈ I(A) can be replaced by i ∈ I(A) for any i ∈ [n]. Both Theorem 5 and Corollary 6 require boundedness assumptions on either function values, gradients and arguments, which hold immediately if we impose a projection operator on A(S). Note we do not require a projection for each iterate. A projection for A(S) suffices for our analysis.

V. APPLICATIONS TO STOCHASTIC OPTIMIZATION
In this section, we apply our general stability results to several stochastic optimization algorithms. We use the notation Recall that n is the sample size and T is the iteration number.

A. Stochastic Gradient Descent
We first apply our general results on stability bounds to derive risk bounds for SGD. We will consider different problem settings: convex and smooth cases, nonconvex and smooth cases, and weakly convex cases. All the proofs in this subsection can be found in Section C (supplementary material). Convex and Nonsmooth Problems. In the following proposition, we show that SGD applied to convex and nonsmooth problems can imply the excess population risk bounds O(n − 1 3 ) with O(n Recall that w * is a minimizer of the population risk F and we assume w * 2 is finite.
Remark 7. We compare Proposition 7 with existing results. The excess risk bounds of SGD without smoothness assumptions were established as follows [23,24] . As a comparison, our analysis implies the bounds O((G w * 2 + B)n − 1 3 ). However, the bound (V.2) requires O(n 2 ) iterations to achieve this optimal risk bounds, which is computationally expensive. As a comparison, our analysis requires O(n , the existing analysis [23,24] requires to run SGD with O(n gives the complexity requirement T = n 4 3 , which is larger than the iteration complexity n 2 3 G w * 2 /B as suggested in Proposition 7. Note we require an assumption sup z E A [f (A(S); z)|n ∈ I(A)] ≤ B in Proposition 7, which is not required in [23,24]. The discussion in [24] requires a Lipschitz assumption and imply high-probability bounds, while we require the assumption E[ ∇f (w t ; z it ) 2 2 ] ≤ G 2 and derive bounds in expectation. Furthermore, a tight lower bound on the stability is developed in [24].
Excess risk bounds of the order O(G w * 2 n − 1 3 log n) were also established for SGD based on the uniform convergence approach [56]. Their discussions consider kernel methods and would imply dimension-dependent bounds if applied to general nonlinear models. As a comparison, our stability analysis always yields dimension-free bounds.
Nonconvex and Smooth Problems. We now consider the performance of SGD for nonconvex and smooth problems. In the remainder, we always let r be randomly selected from the uniform distribution over [T ]. We show that SGD with O(n 2 3 ) iterations can achieve the population gradient bound E S,A,r ∇F (w r ) 2 = O(n − 1 6 ). Again, this result shows that considering generalization does not bring additional computation requirement since SGD with T ≍ n 2 3 iterations is only guaranteed to achieve empirical gradient bounds . That is, with n 2 3 iterations, our population gradient bounds match the existing empirical gradient bounds.

Proposition 8 (Nonconvex and Smooth Case
Remark 8. We compare our bounds with the existing results. For nonconvex, smooth and Lipschitz loss functions, the uniform stability bound of the order O(n −1 T Lc Lc+1 ) was established for SGD with step size η t ≤ c/t [20]. While this stability analysis gives nontrivial bounds on the generalization gap, the proposed step size is small to enjoy a good decay of optimization errors. Indeed, with this step size one can only derive optimization error bounds E S,A,r ∇F S (w r ) 2 = O(1/ log T ). One cannot trade-off the generalization bounds O(n −1 T Lc Lc+1 ) and optimization error bounds O(1/ log T ) for a non-vacuous population gradient bound. Indeed, to get a non-vacuous bound, one requires T = O(n Lc+1 Lc ). However, in this case the optimization error bounds become O(1/ log n), which are very slow. As a comparison, our discussion suggests a step size η t ≍ n − 1 3 for a significantly better population risk bound O(n − 1 6 ). We should mention that the discussion in [20] considers the stability in function values, while we consider stability in gradients. High probability bounds on a weighted average of ∇F (w t ) 2 2 were developed in [47]. Their discussions use a uniform convergence approach and therefore admits a square-root dependency on the dimensionality. As a comparison, Proposition 8 yields dimension-free bounds for population gradients.
We can further improve the population gradient bounds under a strong growth condition (SGC), which connects the rates at which the stochastic gradients shrink relative to the full gradient [57].
The following proposition shows that the learning performance improves under the SGC condition. Weakly Convex Problems. Finally, we consider weakly convex problems. Note we impose a bounded subgradient assumption E[ ∇f (w t ; z it ) 2 2 ] ≤ G 2 as in Davis and Drusvyatskiy [14]. In the appendix E, we will relax this assumption ] + B 2 for some B 1 , B 2 > 0 and derive the corresponding convergence rates of SGD. To our knowledge, this convergence analysis under the relaxed condition is new for SGD with weakly convex problems.
Proposition 10 (Weakly-convex Case). Let {w t } t be produced by (IV.7) with η t = η and A(S) = w r . Assume ). It would be interesting to further improve the risk bound here.
Population risk bounds of gradient descent were recently studied for weakly convex problems [58]. Their discussions require the weak convexity parameter to be sufficiently small for meaningful generalization. As a comparison, our discussion does not require this assumption. Furthermore, their discussions consider smooth problems with Lipshictz continuous Hessians and focus on gradient descent [58], while our discussions apply to SGD with nonsmooth problems.

B. AdaGrad-Norm
We now turn to the generalization analysis of AdaGrad-Norm. Proposition 11 presents the risk bounds in terms of function values for convex and nonsmooth problems, while Proposition 12 presents the risk bounds in terms of gradients for nonconvex and smooth problems. Note that these bounds match the corresponding results for SGD (w.r.t. n) in Section V-A up to a logarithmic factor. All the proofs are given in Section D (supplementary material).

Proposition 11 (Convex and Nonsmooth Case). Let {w
If T ≍ n Remark 10. Generalization behavior of adaptive gradient descent was recently studied by Zhou et al. [59]. They considered minibatch adaptive algorithms with a sufficiently large batch size, while the algorithms we consider here use only a single example to compute a stochastic gradient and is therefore more computationally efficient. Their analysis is based on a connection between generalization and differential privacy, and requires to add noise to achieve differential privacy. This in turn leads to a dimension-dependent bound. As a comparison, we do not require to introduce noise in algorithms and our bounds are dimension-free.

C. Differentially Private SGD
In this section, we use our stability analysis to develop a differentially private SGD with generalization guarantee for weakly-convex problems, which is useful to handle data with sensitive information [60]. We first introduce the definition of differential privacy, which is a well-accepted mathematical definition of privacy.
Definition 8 (Differential Privacy). Let ǫ > 0 and δ ∈ (0, 1). A randomized mechanism A provides (ǫ, δ)-differential privacy (DP) if for any two neighboring datasets S and S ′ and any set E in the range of A there holds Our basic idea to develop differentially private algorithms is to inject noise in the learning process to mask the influence of any single datapoint. In particular, at the t-th iteration we randomly sample a noise b t from a Gaussian distribution with a variance σ 2 I d and build a new stochastic gradient as ∇f (w t ; z it ) + b t . Then we move along the negative direction of this stochastic gradient as follows where β is a parameter and We refer to our algorithm as DP-SGD and summarize the implementation in Algorithm 1. Proposition 13 shows that Algorithm 1 achieves the (ǫ, δ)-privacy guarantee, while Proposition 14 gets the utility guarantee as measured by ∇F (w r ) 2 . The proofs are given in Section F.
Proposition 14 (Utility guarantee). Let ǫ > 0 and δ ∈ (0, 1). Assume for any z, the function w → f (w; z) is G-Lipschitz and F S is ρ-weakly convex. Let {w t } t be produced by Algorithm 1 with η t = η and A(S) = w r . Assume

A. Proof of Theorem 2
In this section, we prove the connection between generalization and uniform stability measured by gradients. For brevity, we use E[·] to denote E S,A [·]. Before proving Theorem 2, we first present the proof of Lemma 1. This result is known in the literature [20,21] and we give the proof for completeness and for showing that these arguments cannot be used to prove Theorem 2.
Proof of Lemma 1. Let S ′ = {z ′ 1 , . . . , z ′ n } be drawn independently from ρ. For any i ∈ [n], define S (i) = {z 1 , . . . , z i−1 , z ′ i , z i+1 , . . . , z n }. According to the symmetry between z i and z ′ i we have where the last identity holds since A(S (i) ) is independent of z i . It then follows that The proof is completed.
An essential argument in proving Lemma 1 is to use the identity E S,A [F (A(S))] = 1 n n i=1 E S,A [f (A(S (i) ); z i )]. However, one can only get where the summation is outside of · 2 . As a comparison, for ∇F S (A(S)) 2 = 1 n n i=1 ∇f (A(S); z i ) 2 , the summation is inside the norm. Since we cannot exchange the norm and the summation, we cannot use the argument in the proof of Lemma 1 to prove Theorem 2. Intuition. We use an error decomposition in [34] to handle this. Our intuitive idea is to show that where ξ i is a sequence of mean-zero variables satisfying E[ ξ i , ξ j ] ≤ 4ǫ 2 for any i = j. Then one can show that Proof of Theorem 2. Let S, S ′ and S (i) be defined as in the proof of Lemma 1. We have the following error decomposition where we have used E Z [∇f (A(S); Z)] = ∇F (A(S)). It then follows that where we introduce ξ i as a function of S as follows Note S and S (i) differ by a single example. By the assumption on stability, we further get (VI.1) Due to the symmetry between Z and z i , one can see that (VI.2) That is, S j is formed by replacing the j-th element of S with z ′′ j , while S (i) j is formed by replacing the j-th element of S (i) with z ′′ j . If i = j, then where the second identity holds since ξ i (S j ) is independent of z j and the last identity follows from E zj ξ j (S)] = 0 due to (VI.2). In a similar way, one can show the following inequalities for i = j As a combination of the above identities we have (i = j) where we have used ab ≤ 1 2 (a 2 + b 2 ). According to the definition of ξ i (S) and ξ i (S j ) we know the following identity It then follows from the elementary inequality (a + b) 2 ≤ 2(a 2 + b 2 ) and the Jensen's inequality that Since S (i) and S (i) j differ by one example, it follows from the definition of stability that In a similar way, one can show that We can plug the above two inequalities back into (VI.3) and derive the following inequality if i = j Furthermore, according to the definition of ξ i (S) and Jensen inequality we know where we have used the symmetry between z i and z ′ i (z ′ i has the same distribution of Z). It then follows that We can plug the above inequality back into (VI.1) and get The proof is completed.

B. Proofs of Theorem 3 and Theorem 4
In this section, we provide the proof of Theorem 3 and Theorem 4. Intuition. Before giving the detailed proof, we first sketch the intuition. For any S, define According to the definition of F S,1/(2ρ) and F 1/(2ρ) , we know (VI.6) It remains to control w S − w S 2 . According to the definition of w S , we know Let A be ǫ-uniformly argument stable. We then show that the algorithm defined in Eq. (VI.4) is O(ǫ + 1/(nρ))-uniformly stable, and the algorithm defined in Eq. (VI.5) is O(ǫ)uniformly stable. It then follows from the connection between generalization and stability that We then can replace F S in Eq. (VI.7) by F to get Furthermore, the weak-convexity and the optimality ofw S show that the left-hand side of the above inequality is larger .
We now give details. We first introduce two lemmas. Lemma 15 shows the argument stability of the algorithm S → Prox FS /(2ρ) (A(S)) via the argument stability of A. For any g : W → R, let ∂g(w) denote the subdifferential of g at w.
Lemma 15. Let A be an algorithm. Assume for any S, the function F S is ρ-weakly-convex. For any S, let w S be defined in Eq. (VI.4) and assume sup z ∇f (w S ; z) 2 ≤ G. Let S and S ′ be neighboring datasets. Then Proof. Without loss of generality, we assume S and S ′ differ by the last element, i.e., S = {z 1 , . . . , z n } and S = {z 1 , . . . , z n−1 , z ′ n }. Since F S is ρ-weakly convex, we know According to the first-order optimality condition we know where we have used the addition property of subdifferential and the definition of F S , F ′ S . We can plug the above two expressions into Eq (VI.8) and get It then follows from the Lipschitz continuity that The stated bound then follows. The proof is completed.
Remark 11. By the ρ-strong convexity of w → F S (w) + ρ w − A(S) 2 2 , we know It then follows that w S − A(S) 2 2 ≤ 2FS (A(S)) 3ρ . Therefore, if A(S) has a finite norm then w S also has a finite norm.
The following lemma connects the argument stability of the algorithm S → Prox F/(2ρ) (A(S)) via that of A. Lemma 16. Let A be an algorithm and F be ρ-weakly-convex. For any S, letw S be defined in Eq. (VI.5). Let S and S ′ be neighboring datasets. Then Proof. By the weak convexity of F we know According to the first-order optimality condition we know As a combination of the above three inequalities, we get It then follows from the Lipschitz continuity that The stated inequality then follows directly.
Proof of Theorem 3. For any S, define w S andw S according to Eq. (VI.4) and Eq. (VI.5), respectively. According to Lemma 16 and the Lipschitz continuity assumption (A is ǫargument stable), we know that the algorithm defined by (VI.5) is 2Gǫ-uniformly stable in function values. It then follows from Lemma 1 that According to Lemma 15, we know that the algorithm defined by (VI.4) is ( 2G 2 nρ + 2Gǫ)-uniformly stable. It then follows from Lemma 1 that It then follows that Furthermore, according to the definition of w S we know and therefore it follows from (VI.9) that We can combine (VI.10) and the above inequality together, and derive According to the ρ-strong convexity of v → F (v) + ρ v − A(S) 2 2 (this strong convexity follows from the weak convexity of F ) and the definition ofw S as a minimizer, we know We can combine the above two inequalities together and derive It then follows that It then follows from Eq. (VI.6) that The proof is completed.

VII. CONCLUSIONS
We provide a systematic study on the stability and generalization analysis of stochastic optimization for problems that can be either nonconvex or nonsmooth. We consider three stability measures: the stability by function values, the stability by gradients and the stability by arguments, which are used to study convex and nonsmooth problems, nonconvex and smooth problems, and weakly convex problems, respectively. We develop connection between stability and generalization gap measured by gradients for either the population risks or the Moreau envelopes. We then develop bounds for these stability measures for a class of sampling-determined algorithms. As a combination of these stability bounds and the connection between stability and generalization, we develop error bounds for SGD and AdaGrad-Norm, with the performance measured by either functional suboptimality, stationarity by gradients or stationarity by Moreau envelopes. It is interesting to investigate whether our error bounds can be further improved. It is also very interesting to develop lower bounds for learning with weakly convex problems.

A. PROOF OF THEOREM 4
In this section, we prove the high probability bounds. To this aim, we first introduce an useful lemma.
Lemma A.1 (Bousquet et al. 34). Let A be an ǫ-uniformly stable algorithm. Assume f (A(S); z) ≤ R almost surely. Then for any δ ∈ (0, 1) with probability at least 1 − δ we have Proof of Theorem 4. For any S, define w S andw S according to Eq. (VI.4) and Eq. (VI.5), respectively. According to Lemma 16 and the Lipschitz continuity assumption, we know that the algorithm defined by (VI.5) is 2Gǫ-uniformly stable in function values. The following inequality then follows from Lemma A.1 with probability at least 1 − δ/2 According to Lemma 15, we know that the algorithm defined by (VI.4) is 2G 2 nρ + 2Gǫ -uniformly stable. The following inequality then follows from Lemma A.1 with probability at least 1 − δ/2

It then follows that
Furthermore, according to the definition of w S and (A.1) we know We can combine (A) and the above inequality together, and derive the following inequality with probability at least 1 − δ According to the ρ-strong convexity of v → F (v) + ρ v − A(S) 2 2 and the definition ofw S , we know the following inequality We can combine the above two inequalities together and derive the following inequalities with probability at least 1 − δ ρ 2 w S −w S 2 2 = O G 2 (nρ) −1 + Gǫ log(n) log(1/δ) + n −1 log(1/δ) and therefore w S −w S 2 = O Gn − 1 2 ρ −1 + Gǫ/ρ log(n) log(1/δ) + n −1 ρ −2 log(1/δ) 1 4 .
The stated bound then follows from Eq. (VI.6). The proof is completed.

B. PROOFS ON UNIFORM STABILITY BOUNDS
In this section, we present the proofs on the uniform stability bounds of sampling-determined algorithms. Our proof follows the idea in Hardt et al. [20]. It then follows that where we have used the assumption E A [ ∇f (A(S); z)|n ∈ I(A) 2 2 ] ≤ G 2 for any S. Finally, we consider Part (c). It is clear where we have used the assumption E A [ A(S) 2 |n ∈ I(A)] ≤ R for any S. The proof is completed.
Proof of Corollary 6. We consider only SGD (the arguments of AdaGrad-Norm are the same). It is clear that It is clear that the algorithm A is sampling-determined, and therefore one can apply Theorem 5 to derive the stated bounds. The proof is completed.

C. PROOFS ON STOCHASTIC GRADIENT DESCENT
The following lemma establishes the optimization error bounds of SGD. Part (a) is a standard result in optimization. Part (b) is due to Ghadimi and Lan [13], Part (c) is due to Vaswani et al. [57] and Part (d) is due to Davis and Drusvyatskiy [14]. (a) If F S is convex, then for all t ∈ N and w (c) Assume for all z, the function w → f (w; z) is L-smooth and SGC holds with the parameter ρ.
Proof of Proposition 7. According to Lemma C.1, Part (a), we have the following optimization error bounds Furthermore, by Corollary 6, Part (a), we have the following stability bounds where {w ′ t } is a sequence of iterates produced by SGD based on a neighboring dataset S ′ . This together with Lemma 1 on the connection between uniform stability and generalization further implies We can plug the above generalization error and optimization error bounds into (III.1), and derive (V.1).
follows directly from the choice of η and T . The proof is completed.
Proof of Proposition 8. According to Lemma C.1, Part (b), we have the following optimization error bounds It is clear that A is sampling-determined and one can apply Corollary 6, Part (b) to show the following uniform stability bounds where {w ′ t } is a sequence of iterates produced by SGD based on a neighboring dataset S ′ . This together with (III.2) and the connection between uniform stability and generalization established in Theorem 2 gives We can plug the optimization error bounds (C.2) into the above bound, and get We can choose T ≍ n Proof of Proposition 9. Analogous to the proof of Proposition 8, we have Furthermore, Lemma C.1, Part (c) implies We can combine the above two bounds together and get Therefore, we can choose T ≍ √ Lρn/G and get E ∇F (w r ) 2 = O((LρG 2 /n) 1 4 ). The proof is completed.
Proof of Proposition 10. According to Lemma C.1, Part (d), we have the following optimization error bounds We can apply Corollary 6, Part (c) to show the following argument stability bounds This together with (III.3) and the connection between argument stability and generalization established in Theorem 3 gives We can plug the optimization error bounds (C.2) into the above bound, and get We can choose T ≍ n The following lemma establishes the convergence rates of AdaGrad-Norm. Part (a) is for convex and nonsmooth problems, while Part (b) is for nonconvex and smooth problems. We give a simple proof of Part (a), while the proof of Part (b) can be found in Ward et al. [54].
Lemma D.1 (Optimization Error Bound for AdaGrad-Norm). Let {w t } be the sequence produced by AdaGrad-Norm. (a) Let F S be convex. Assume w 2 ≤ R for all w ∈ W. Then the following bound holds for all w ∈ W where r follows from the uniform distribution over [T ].
Proof. Denote η t = η/b t , then (IV.8) can be written as w t+1 = Π W (w t − η t ∇f (w t ; z it )). It then follows that Re-arranging the above gives We take conditional expectation w.r.t. z it over both sides and get It then follows from the convexity of F S that We can take an expectation followed with a summation of the above inequality from t = 1 to t = T , and get where we have used the following inequality in the last step It then follows from the convexity of F S that The stated bound then follows.
Proof of Proposition 11. Analogous to the proof of Proposition 7, we have the following generalization error bound Lemma D.1, Part (a), implies the following optimization error bound We can plug the above two inequalities back into (III.1) and get One can derive the stated bound by setting T ≍ n 2 3 . The proof is completed.
Proof of Proposition 12. Analogous to the Proof of Proposition 8, we have the following generalization error bound Lemma D.1, Part (b), implies the following optimization error bound We can combine the above two inequalities together and get One can choose T ≍ n 2 3 to get the stated bound. The proof is completed.

E. CONVERGENCE RATES WITH RELAXED BOUNDED GRADIENT ASSUMPTIONS
In this section, we study the convergence rates of SGD for solving weakly convex problems. The existing convergence analysis requires a bounded subgradient assumption as E it [ ∇f (w t ; z it ) 2 2 ] ≤ G 2 for some G > 0 [14]. We aim to relax this assumption to a more general assumption as where B 1 , B 2 ≥ 0 are two constants. This assumption implies that the gradients can be bounded in terms of function values, which has been considered in the literature [1].
Let {w t } t be produced by the algorithm A defined by (IV.7) and Eq. (E.1) holds for all t ∈ N. If F S is ρ-weakly convex, then Proof. For any t ∈ N, denoteŵ t = Prox FS ,1/(2ρ) (w t ). According to the definition of Moreau envelope and the definition of w t , we know where in the last second step we have used Eq. (E.1) and in the last inequality we have used the weak convexity of F S . By the weak convexity of F S , we know the function w → F S (w) + ρ w − v 2 2 is ρ-strongly convex. This together with the definition ofŵ t implies It then follows that This together with the assumption η t ≤ 1/B 1 implies . We can plug the above inequality back into Eq. (E.3) and derive where we have used Eq. (E.4) and the following inequality in the last step It then follows from Eq. (E.5) that E A F S,1/2ρ (w t+1 ) ≤ 1 + ρB 1 η 2 t E A F S,1/2ρ (w t ) + ρη 2 t B 2 and therefore (1 + a ≤ exp(a)) E A F S,1/2ρ (w t+1 ) ≤ We can plug the above inequality back into Eq. (E.5) and get The above inequality can be reformulated as We can take a summation of the above inequality from t = 1 to t = T and get According to the definition ofŵ t , we know ∇F S,1/2ρ (w t ) = 2ρ(w t −ŵ t ). It then follows that This gives the bound (E.2). The proof is completed.

F. PROOFS ON DIFFERENTIALLY PRIVATE SGD
In this section, we prove privacy and utility guarantee for DP-SGD. To this aim, we first study the Rényi differential privacy, and then transform it to (ǫ, δ)-DP.
Definition 9. For λ > 1, ρ > 0, a randomized mechanism A satisfies (λ, ρ)-Rényi differential privacy (RDP) if for all neighboring datasets S and S ′ we have where P A(S) (w) and P A(S ′ ) (w) are the density of A(S) and A(S ′ ), respectively.
The following lemma shows the RDP of an adaptive composition of several mechanisms. The following lemma shows the connection between DP and RDP.
We are now ready to prove the privacy and utility guarantee.
Proof of Proposition 13. Consider the mechanism A t = M t + b t , where M t (z) = ∇f (w t ; z). Since f is G-Lipschitz continuous, we know sup z,z ′ ∇f (w t ; z) − ∇f (w t ; z ′ ) 2 ≤ ∆ := 2G and therefore the ℓ 2 sensitivity of M t is 2G. Note Adding noise does not affect the stability analysis [24], we then use Eq. (C.3) to get For our choice of β, we have where we have used β ≤ 1/2 established in the proof of Proposition 13. If we choose η ≍ 1/((G + √ dσ) √ ρT ) and use Eq.