Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms
Authors: Sijia Zhou
Yunwen Lei
Ata Kaban
Venue: NeurIPS 2023 poster (2023)
Keywords: PAC-Bayesian Bounds
Uniform Stability
Generalization Analysis
TL;DR: We develop sharper generalization bounds for uniformly stable randomized algorithms in a PAC-Bayesian framework.

Abstract: We give sharper bounds for uniformly stable randomized algorithms in a PAC-Bayesian framework, which improve the existing results by up to a factor of $\sqrt{n}$ (ignoring a log factor), where $n$ is the sample size. The key idea is to bound the moment generating function of the generalization gap using concentration of weakly dependent random variables due to Bousquet et al (2020). We introduce an assumption of sub-exponential stability parameter, which allows a general treatment that we instantiate in two applications: stochastic gradient descent and randomized coordinate descent. Our results eliminate the requirement of strong convexity from previous results, and hold for non-smooth convex problems.

Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms
Sijia Zhou'
Yunwen Lei Ata Kabán'
School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom Department of Mathematics, The University of Hong Kong, Pokfulam, Hong Kong, China sx2115@student, bham. ac uk leiyw@hku. .kk a. k.baan@bhaam. ackuk
Abstract
We give sharper bounds for uniformly stable randomized algorithms in PAC- Bayesian framework, which improve the existing results by up to a factor of vn (ignoring a log factor), where n is the sample size. The key idea is to bound the moment generating function of the generalization gap using concentration weakly dependent random variables due to Bousquet al (2020). We introduce an assumption of sub-exponential stability parameter, which allows a general treatment that we instantiate in two applications: stochastic gradient descent and randomized coordinate descent. Our results eliminate the requirement of strong convexity from previous results, and hold for moo-smooth convex problems.
1 Introduction
Stochastic optimization methods are the workhorses of many modern machine learning problems. A lot of progress has been made in reducing optimization errors with less training time in stochastic settings [6. 21, 41, 46, 64]. One such method is stochastic gradient descent (SGD), which builds a stochastic gradient estimator iteratively based on randomly sampled example to approximate the gradient for the next iteration. SGD appealing for large-scale data analysis due its cheap computational cost, simplicity and efficiency.
Obtaining models that generalize well is the goal in machine learning and undertake theoretical analysis of this problem. The generalization behavior model can be quantified by the excess risk, which decomposes into two components: the optimization error and the generalization error (or generalization gap). In this paper, we focus on the analysis of the generalization error of stochastic optimization methods. We combine two useful approaches to bound the generalization error, that is algorithmic stability [7, 16] and PAC-Bayes bounds [9, 26, 34, 53]. Our hope is to retain the benefits of both approaches derive powerful generalization bounds better understand the behavior of stochastic optimization methods.
Seminal work by Bousquet et al. [7] provided generalization bounds for uniformly stable algorithms in the deterministic case. Sharper generalization bounds were obtained via moment bound on the generalization gap and a concentration inequality of weakly dependent random variables [8, 18]. Extending stability-based bounds to randomized algorithms is challenge. In [16], where the stability- based bounds for the randomized algorithms were considered, the results hold for fixed distributions. To give bounds uniformly for all distributions, we need to turn to PAC-Bayes analysis. A recent work analyzed stable algorithms in the PAC-Bayee framework and derived generalization bounds that hold for any distribution [32]. However, a comparison between [8] and [32] reveals that the error convergence rate in the randomized case [32] is much slower than that for the deterministic case [8]. In more detail, it was shown that --uniformll stable (33 is decreasing w.r.t. n, where n is the sample
Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

size) and deterministic algorithms would imply generalization bounds of order -(1/v [8. 18I. while PAC-Bayes bounds of order O(1/ /n,3) were developed for randomized algorithms [32]. In [32], the randomness comes from the sampling of hyperparameters such as the index of examples chosen in SGD, and the PAC-Bayes bounds hold for any posterior distribution which may depend on the dataset. It is clear that the PAC-Bayes bounds can be slower than those in [8, 18] by factor of yn, which motivates a natural question: can we develop PAC-Bayes bounds for randomized algorithms which match the rate of deterministic algorithms?
This paper explores the above question. We provide sharper PAC-Bayes bounds that hold for uniformly stable randomized algorithms. We adapt moment bound [8] previously used for stable algorithms in deterministic cases and extend it to the PAC- PAC-Bayesian framework, to give bounds that hold for randomized predictors. The PAC-Bayes framework is based on the work of [32]. However, we take a different analysis strategy to control the change in hyperparameters, which is based on an assumption of sub-exponential stability parameter. This general assumption allows us to bound the moment generating function (MGF) of the generalization gap within a high probability domain where our assumption holds (see Appendix A.2). Furthermore, we prove that this assumption holds for both SGD and randomized coordinate descent (RCD). We then illustrate the advantage of our results over existing bounds.
Regarding the convergence rate, our main result improves on the existing PAC-Bayes bounds [32] by a factor of /n (ignoring a log factor). This improvement holds under weaker conditions under which convergence is not guaranteed in [32]. Our primary technical tool is moment bound, which we extend to randomized learning algorithms in the PAC-Bayes framework. This allows our bounds to hold for all possible posteriors, not just fixed ones [16] or deterministic algorithms [8, 18). We need to introduce novel techniques to handle the randomness of the hyperparameter, which is challenge in the PAC-Bayes analysis (details will be given in Section 3.2).
Regarding assumptions, our result holds without the requirement of hyperparameter stability in previous work [32]. Instead, we introduce new assumption on the sub-exponential behavior of uniform stability by viewing the uniform stability as function of the random hyperparameter. Interestingly, suffices to study the aub-exponential behavior of uniform stability under the prior distribution, which makes the sub-exponential assumption easy to check.
We show that the uniform stability of SGD and RCD have mixture of aub-Gaussian and sub- exponential tails that satisfy this assumption. Thus, we remove the strong convexity assumption in the existing analysis of SGD [32] and extend the result non-smooth problems. Our result also applies to RCD, where the randomness arises from the selected coordinates.
The remainder of the paper is organized as follows. We discuss the basics PAC-Bayes and stability analysis in Section 2. We present our main results in Section 3, and apply it to SGD and RCD in Section 4. We survey the related work stability and PAC- MAC-Bayesian analysis in Section 5, and conclude the paper in Section 6.
Preliminaries
We first introduce some notations. Let X' and y denote the input and output space respectively and let Z XX x y' We are given set of training examples of size n, S = {=1 (v1, 3/ .., 2n, (I yn)] drawn independently and identically distributed (i.i.d.) from an unknown distribution D on 2. We hope to learn a predictor from a class of hypotheses H to predict unseen new data drawn from D. Let W denote the weight space, W C IRd, and θ denote a hyperparameter space. A deterministic learning algorithm A : 2" x θ - H maps the training examples to hypothesis hw E H determined by w E W. The quality of a hypothesis is measured by a loss function, l: H x Z - [0, M).
The goal of any learning algorithm is to produce a predictor that generalizes well. That means that the learned predictor applied on previously unseen input data from the marginal of D should have a small expected loss. For any 0 E O the risk of a predictor returned by the algorithm A is a random variable as a function of S, defined as
R ()) = E (==
(2.1)
We use Ō to hide logarithti factors.
2

---

Since D is unknown, we have no access to the true risk. Instead, the empirical risk is often used as an approximation
" 7 Σ (()())))
Rs(A(S;0)
(2.2)
We are interested in how well the empirical risk can estimate the risk. The difference between them is the generalization gap G(S;0) 2 R(A(S;0) Rs(A(S:0)). We can upper bound the risk by bounding this difference.
2.1 PAC-Bayes basics
We are interested in randomized algorithms, such as stochastic gradient descent (SGD) and random- ized coordinate descent (RCD). In such algorithms, there is in-built random sampling mechanism that we can think of as random hyperparameter. In other words, a randomized algorithm may be viewed as a deterministic algorithm with hyperparameters that follow distribution. Therefore. for the analysis that follows, we will explicitly define distributions on O. There has been lot of interest in SGD because is often used train model and its randomness comes from independent sampling of training instances to estimate gradient directions. In this case, the hyperparameters @ E θ form random sequence training point from S. Here [n] denotes (1.....n..
(f..... rr), where every 0g E [n], for E [T], an i.i.d. index of
Any distribution over the hyperparameter space O induces distribution over the predictors (or weights since we often consider parametric models). In the PAC-Bayes methodology. the common approach is define a prior distribution on the domain of the weights [13, 22, 34, 53]. However, in the context of randomized algorithms of the kind mentioned above it is more natural to exploit the randomness already present through distribution on the domain of the hyperparameters.
Hence, we will conduct MMC-Bayesian analysis by focusing on the randomness of the hyperparameters. Let IP be any prior distribution the hyperparameter domain O chosen before seeing the training data. Given a randomized algorithm, we will only need to prove a condition for the prior on O and in return our generalization guarantees will hold with high probability for all posteriors Q on O. In particular, we can assume simple uniform distribution as a prior for SGD, i.e. SGD with uniform sampling, and derive bounds for data-dependent non-uniform sampling [49, 56, 66). For example, SGD with importance sampling [66] shows better results than uniform sampling, and there are efforts to learn good sampling distributions [32] in line of research towards self-certified learning algorithms [13, 44].
The quality of predictor learned by algorithm A from the training sample S, is defined the expected risk w.r. the BCyBa posterior Q as
R(S, Q E [R(A(S:0))
(2.3)
a~Q
Its empirical counterpart, the expected empirical risk w.r.t Qss
Rs (S, Q
E
[Rs (A(S:A)))))
(2.4)
f~
In special cases this expectation can be computed analytically; most often it is approximated either by Monte Carlo sampling by analytical upper bounds.
PAC-Bayes bounds aim to estimate R(S, Q) in terms of (s S, Q) and the divergence between IP and Q. A key ingredient that PAC-Bayes bounds rest upon is change of measure inequality, also known as variational formula. For completeness this is given in Appendix (Lemma A.3).
2.2 Algorithmic stability basics
Another relatively recent framework for generalization analysis is based on the concept of algorithmic stability [7]. The key concept in this framework quantifies how sensitive a learning algorithm is to small perturbations of the training data. There are several notions of algorithmic stability, and the one we use in our work is the following uniform stability [7]. We denote S S' if they are neighboring datasets, i.c., S and S differ by at most single example.
3

---

Definition 1 (Uniform Stability), For any 9, an algorithm A A(S;0) is Sg Bg-uniformly stable w.I.t loss function e if S' z", Vz 2,
-
Bg.
(2.5)
Recall that A is a randomized algorithm whose randomness is exclusively due to random draw of 0. Hence, given a fixed instance of the algorithm becomes a deterministic algorithm. This simple observation helps reduce the problem from randomized learning to deterministic learning. Based on this observation, the next section presents sharper generalization bounds for randomized algorithms in comparison previous results [32].
3
Main Results
First we introduce a sub-exponential assumption on the stability parameter. This will allow to make some key innovations: 1) We will able to remove one of the assumptions required by [32, Theorem 2] (hyperparameter stability) and only require uniform stability. 2) we will state result in more general terms, and instantiate it to specific algorithms such as SGD and RCD.
Assumption 1 (Sub-exponentiall stability). Let P be fixed probability distribution Q = IT O2- We say that a randomized algorithm with random hyperparameters ~ IP satisfies sub-exponential stability if, for any fixed instance of it satisfies fg--unfform stability w.r.t. loss function E, and there exists c E I such that for any 8 E (0, 1/nj, with probability at least 1 - over draws of 0 ~ P.
30 < 1e + c clog(1//4
(3.1)
In other words, this assumption says that the deviation of [8 from its mean roughly has sub- exponential tail. We will show that c is dominated by [B~ in typical stochastic optimization algorithms such as SGD and RCD.
Note that in the above assumption, the probability is made w.r.t. 0 ~ P. which a prior distribution independent of S. We can choose IP to be uniform distribution. In this case, will show that SGD satisfies this assumption under mild conditions on the loss functions with very small [B>e[[8] and c.
Recall that for any fixed instance of 0, the trained model of the learning algorithm A on data set S with hyperparameters is deterministic predictor. Our proof strategy for our main result below is to first fix f. and apply a recent technique of obtaining sharp bounds [8] to the resulting deterministic algorithm. After that, we deal with the randomness of
In Theorem 1 we give our main result. This bound is useful when we have small [ø-r[30] and c. We will see two examples
Section We denote B 2 B' if there exists universal constant ei > such that B 2 ei B'. We use B $ B' if there exists a universal constant > 0 such that B S C2 B'. We use B x B' if B' S B. The proof is given in Appendix A.2.
Theorem 1 (Generalization of sub-exponentially stable randomized algorithms). Consider a learning
algorithm A(S;)) 0) that satisfies Assumption I w.r.f. P and e S [o-e(Bo). Assume (((S;;), 2) E [0, M. Then for any 81 E 10,1) the following inequality holds with probability at least 51 uniformly for all Q
Ee-2 - & (Dia, (Dxa.(Q/))))oo((//))) max (Earr log n, Vn
where (Q] means the KL divergence between P and Q i.e. D (QIIP) = Es~
log 200) P())
To apply Theorem 1, we only need to check the sub-exponential assumption w.r.t. the prior P. Then, we use the PAC-Bayesian analysis to transfer this stability assumption w.r.t. the specific IP to a bound holding for all posterior distributions.
3.1 Comparison
Next, we compare our result (Theorem 1) with the previous generalization bounds on randomized algorithms due to [32] and observe the advantages that our approach offers.

---

To blend the stability into the PAC-Bayes framework, where hyperparameters follow a distribu- tion, [32] defined the following new hyperparameter stability assumption for learning algorithms (Definition 2) and obtained the stability-based PAC-Bayes bound given in Theorem 2.
Definition 2 (Hyperparameter Stability). A learning algorithm A has uniform hyperparameter stability Se w.r.t. the loss function E, if
sup (((A(S:0),)) (0000))))==(((()())))))))))))))) ((A(S: (', Se, SE2" 6.
sup sup
(3.2)
where DH v)
Tw # og] is the Hamming distance and T[-] denotes the indicator function, i.e, [[ = if the event E holds and O otherwise.
Σ
Observe that, uniform stability (Definition 1) concerns the stability of an algorithm with respect to a change in the training set. In contrast, the above Definition 2 requires stability w.r.t. change in the hyperparameters. Moreover, the approach in [32] requires stability w.r.t. both the loss function and the hyperparameters to derive the following PAC-Bayes bound.
Theorem 2 (Theorem 2 of [32]). Let A be randomized learning algorithm and ((A(S;)) 2) M. Assume is 3g-uniformly stable w.r.l. loss functions, and Be- Deg-uniformly stable w.rl. hyper-
paramters. Consider the prior IP as a fixed probability distribution defined on θ I θ. Then for any n 2 1, T 2 1, and E (0, 1), the following inequality holds with probability at least 1 over draws of data set, S ~ D for every posterior Q on O
Ex-o -s(A)))))) & V (1ooo/////////////EEOEAA-C (MM++1E00:=33)))///---111
We now compare our bound (Theorem 1) with the bound above (Theorem 2).
In terms of the rate, our bound in Theorem improves the previous result of Theorem 2 by up to a factor of / (up to poly-logarithmic factors when the divergence is polylogarithmic in n [32]). To see this, consider the case where in both Theorem I and Theorem 2, the term that contains the stability parameter dominates over the KL term. Then, in Theorem I, for Bg Bo-uniformly stable randomized algorithms, we have
E ((A(S:)) - Rs(A(S;0)) = max (3)))- 2) DKL ( (Q(IP).
In contrast, Theorem 2 in [32] gives
Ee~o [(AA(S:)) Rs (s(A(S)))) = =Ō 0VVnBeer130)
(3.3)
is clear that, the case when Ō D( it with ((E))==(B)) we improved (3.3) by up to factor of vn (ignoring a log term). The prior IP can be selected freely if is independent of S. The posterior Q can depend on the data, Indeed, a strength of the PAC-Bayesian analysis is that it applies to any Q and therefore it allows to choose distribution Q in a data-dependent manner. The posterior Q can be optimized to control the divergence between P and Q. Therefore, we typically have small KL divergence.
dominates the KL divergence then having replaced
Observe also that, in Theorem 1, when Eg S O(n our generalization bound is Ö(n ((n-)).. while (3.3) implies a vacuous bound (11) so generalization is not guaranteed. Furthermore, our bounds require Eg<r [8e] X 1/ to get almost optimal rates Õ(1/ (n). As a comparison, the results in Eq. (3.3) require stronger condition Eg-r [3u] 1/n and ße S 1/T to get the rate O /n).
In the unlikely case when the KI. divergence the dominating term, for example, DKL. (Q[IPP Z (n), then Theorem 2 achieves better result. But in this circumstance, both Theorems and 2 require 8g < O(n #) to converge at rate of O(n }), which we believe this be also rather uncommon.
In terms of assumptions, we eliminate the hyperparameter stability assumption in [32] at the price of an additional sub-exponential tail assumption on the uniform stability parameter. We will prove later in Section 4 that this general assumption holds for more stochastic optimization methods and even for non-smooth problems. In conclusion, we achieve better results under weaker conditions.
5

---

3.2 Proof sketch and challenge in the analysis
We begin by noting that é is applied to the output of A(S; which depends on the training data and the hyperparameters. Therefore, ()) could be sensitive to changes in both the dataset and the hyperparameters. To address this issue, Theorem 2 assumes hyperparameter stability, which requires small changes in ((A(S; f)) when the hyperparameters are perturbed.
In contrast to the previous method, adopt different strategy for controlling changes in 0. Our So a random variable w.r.t. 0. We assume a sub-exponential concentration behavior of 3g to control its deviation (Assumption 1). This allows us control [8 without necessitating hyperparameter stability. Based on this assumption, our proof proceeds by bounding the MGF of the generalization gap. A key challenge handle the randomness of 3g. More precisely, for any temporarily fixed 0 has been shown that (SS; 0) is a mixture of sub-Gaussian and sub-exponential random variables when only considering the randomness of S [8]. Then a bound of Es (exp(((SS À S 1/ Se (by Eq. (A.5) on sub- uub-exponential random variables). This constraint makes it challenging since we need to choose an appropriate À and control the associated Eg (exp(AG(S; 0)] (the random constraint makes the selection of X difficult). Our key idea to address this problem is to control the MGF of another function H 2 -> IR defined follows
requires an assumption
R R(A(S:)) - Rs(A()))) if E S2g- otherwise,
(S;0)) = 0
where Assumption 1 holds everywhere on f2g, which is subset of ④ with probability measure at least 1 - 8. This definition of H has two benefits.
First, (S; is equal to G(S;0) () with high probability. Therefore, a high-probability bound on H would imply a high-probable probbabibbbb bound on G.
Second, H is convenient to control. For any 0 E θ \Ωg, the MGF satisfies Es (cx)(AH((: 1. For any 9 E Szg. the term Eg [cxp(XHHHH() (S; can be controlled under an assumption À S 1/Eg-p due to the definition of Ω2 which relates 3o with its expectation. A key difference is that the random 3g is replaced by Eg-r|88 in the constraint of X, which allows us to choose deterministic À uniformly for all 0. A further expectation w.r.t. 0 would imply a bound on Es: (S:o(exp(AHH(:)))))) 0))], which is needed in the PAC-Bayes analysis.
Finally, we manipulate this MGF bound in the PAC-Bayes framework by the variational formula (Lemma A.3), building upon the framework of [32].
3.3 Bounds in Expectation
Our previous analysis gives high- gigh-probability bounds. In this subsection, we give PAC-Bayes bounds in expectation. In this case. we no longer need an assumption on the concentration behavior of Be around its expectation. The proof is given in Appendix A.3.
Theorem 3. Consider any Bg Be-uniformly stable algorithm A and M-bounded loss t. For any distribution Q, we have
(2M + 16 [36]
EgEa R(A(S:0) - (s((A())))] & (((0))))))((((())((0 (x²(Q)P)+1) +1)
(3.4)
Remark 1. Under the same assumption, it was shown in Theorem 1 in [32] that
$ 12ME [Bo]
2M2
EgEa~ (R(A(S:)) Rs(A(S;0)) < (QIIP) +1
(3.5)
n
Therefore, our analysis gives bound of the order 0(1/VT + (Ea-r $), while Eq. (3.5)
gives bound (1/v/n (Bg- #). It is known that [B~>[188 can be much smaller than Ep-e [3]] For example, for SGD with iterations and IP being the uniform distribution, it was shown Eg [3] = O(zt//)) and [ = Orz2t/n) if the loss function is convex and smooth [27]. In the typical setting with 1 0 /t) and x n (in this setting SGD achieves optimal rates), we have Ea-p[3g] (l/vnn) and Eg [35] O(1/n). In this case, our analysis gives PAC-Bayes bounds of the order O(1/ while Eq. (3.5) gives PAC-Bayes bounds of the order (LLnn)). Therefore, analysis implies much better PAC-Bayes bounds than that in [32].

---

4 Applications
We apply our general results to derive PAC-Bayes bounds for two optimization algorithms: Stochastic Gradient Descent (SGD) and Randomized Coordinate Descent (RCD). To this aim, we introduce some necessary definitions. Let || 2l2 denote the Euclidean norm.
Definition 3 (Lipschitz continuity). We say loss function {(;22 is I-Lipschitz if for any E W and 2 E 2, we have [[V&(;;>) 2) 2) Σ L. This implies that for any W1, W2 E W,
|e ([W1:2) ((w2;2) 2)) S L wella-
(4.1)
Definition 4 (Convexity). Let 0. We say loss function f(:: z) is k-strongly convex if for any W1, W2 E W and E 2, we have
((wi=)= 2 ((w2)2) (Vl(w2;=), W1 w2) + - R w2ll3.
2 [|l]
(4.2)
We say the loss function é is convex if the above inequality holds with O. Definition 5 (Smoothness). Let 2 O. We say loss function ((: 2) is a-smooth if for any W1, W2 E W and & E Z, we have
VV((11:2 Vé(
(W( 2)12 S al|w w2ll2.
(4.3)
For the applications, we only need to verify the sub-exponential stability of the algorithm w.r.t. the prior sampling P., which is often chosen to be simple such as the uniform distribution.
4.1 Applications to Stochastic Gradient Descent
SGD is one the most popular algorithms to solve optimization problems in machine learning due to its simplicity and efficiency. The basic idea is to build stochastic gradient based randomly selected example, which is used to update iterates. Here we consider SGD with a general sampling scheme, where the random index follows from general distribution. This general SGD has already been considered in the literature to improve the efficiency of SGD with uniform sampling, including importance sampling [66] and Markov chain sampling [54, 58, 63].
Definition 6 (SGD with general sampling). Let W1 be an initial point. Let I' be probability measure over [n]] and S = {a....., žn) } be a training dataset. Let (d1,.... iz)) be drawn according to P. At the t-th iteration, SGD with sampling scheme P updates the model by
W++1
V((we;
(4.4)
where {mh} a positive step-size sequence. If is the uniform distribution, then we call it SGD with uniform sampling (SGDU).
Now we apply Theorem 1 to develop PAC-Bayes bounds for SGD applied to convex problems, covering both smooth and non-smooth cases. We will show that SGD enjoy sub-exponential stability.
4.1.1 Smooth case
In the following lemma to be proved in Appendix II.1.1, we give stability bounds for SGDU and show it satisfies Assumption 1. Recall that the indicator function [[-] is defined in Definition 2.
Lemma 4 (Stability bound). Let S and S' be neighboring datasets. Suppose for all E Z the loss function is convex, a-smooth and L-Lipschitz. Let [we), { (w]) be the sequence produced by SGDU on S and S' respectively with ni S 2/ax Then SGDU with iterations and the hyperparumeter 0 is 39 un-uniformly stable with
BB 2T, max kE(n)
Σ ny T = k:).
If nh = 1), then any 8 E (0, 1), with probability at least - 8 we have
3 < Eg- [Ba] 4L' (t/m)²) log(1/8).
That is, Assumption I holds with 4L3m + (t/n))) w.r.t. P.
7

---

We can combine the above lemma with Theorem to obtain PAC-Bayes bounds for SGD, whose proof is given in Appendix II.1.1. An interesting property is that generalization bounds for SGD with general sampling can be derived based on the stability analysis for SGD with the uniform sampling. We always let IP denote a uniform prior on θ.
Corollary 5 (Generalization bound). Assume E is M-bounded, L-Lipschitz, convex and a-smooth. For uniform distribution IP, every n E N+ and 5 E (0, 1), with probability at least 1 over draws of data set, S ~ . all posterior sampling distribution Q on [n]", SGD with ry S 2/ satisfies
Bg (R(((S))) - (R((A(S:))) 2 [QKL(QIP) log()))) max { (L (1 (T/n)
log(n)) (LT/)))
logn,
M vn
Based on [20, 27], which studied the trade-off between optimization and stability, the recommended choices of parameters are x n and 17 x 1/VT to get a SGD iterate with good generalization behavior. In this setting, the above corollary implies a PAC-Bayes bound Ö(1/ (R)
London [32] gave PAC-Bayes bounds for SGD under strong convexity and smoothness assumptions.
Corollary 6 (Corollary in [32]). Suppose l M -bounded. Let the objective function be ss-strongly convex, L-Lipschitz and a-smooth. Then, for uniform distribution IP and any ō E (0, 1), with probability at least 1 - over draws of a data set, S DD,, SGD with T3t = (xi + a)- and any posterior sampling distribution Q on [n]² satisfies
E [R(A(S;0) Rss (s(S:()))) & V (DKL(QIP)) (M+
(M
L R2T
+
We now compare Corollary 5 and Corollary 6. First, Corollary 6 requires strong convexity assumption, which is removed in our analysis. Second, our analysis implies PAC-Bayes bounds of the order Ó(1/ /n), while Corollary implics bounds of order (LL(VVix)) The strong convexity parameter is often very small in both theoretical and empirical analysis. For example, the existing generalization analysis of regularization schemes suggests O(n $ get an optimal bound (Section 3 in [55]), for which Corollary 6 implies a vacuous bound. By contrast, our bound 0(1/V)) is optimal up to log factor.
Remark 2.
Remark 3. Our uniform stability (Definition 1) is slightly different from the uniform stability 83 := s sup= Ee- [e)Ap( 0), 2) ((A(S';)) 0), =)] in [32] in the sense of taking expectation in different places. The expectation of 0 ~ IP is taken outside sup in our case and inside sup in 8z [32]. However, we often have similar upper bounds for [[3e] and 8z. Consider SGD for smooth, Lipschitz and convex problems as example. It is shown in [20] that 8z 21, Et= m//n, while we can show E[Se] - L'"log n Ei-1 Ma/n (the proof of Lemma 4) These two upper bounds are the same order up logarithmic factor. Furthermore, lower bounds were established in [65] (Theorem
1) where 8z 4 Σ Et=1 m//n, which match the existing upper bounds up to constant factor. This shows that 32 and E [3)] are of similar order.
4.1.2 Non-smooth case
The following lemma shows that SGDU applied to non-smooth problems enjoys the nub-exponential stability. The proof follows the analysis Section 4.2 in [29] and is given in Appendix 1I.1.2.
Lemma 7 (Stability bound). Let S and S' be neighboring datasets. Suppose for all Z the loss function is convex and L-Lisschitz. Let {w:), [w(} be the sequence produced by SGDU on S and S' respectively with fixed step sizes. Then SGDU with t iterations and the hyperparameter 0 is 39 3g-uniformly stable with 3g 22/eL2 n (VT + maxke[m] probability at least - 8 we have
E/= =k). For any ö E (0, 1), with
30 < Ee-r Bo] + A/ AeeeLLL + (t/n)*) log(1/6).
That is, Assumption holds with c 1 + (t/n)=) w.r.t. IP.
Based on the above lemma, we derive the following corollary for the PAC-Bayes bounds of SGD in non-smooth problems.
8

---

Corollary 8 (Generalization bound), Assume is M -bouded, L-Lipschitz and convex. For any 8 E (0, 1), with probability least 1 6 over draws of a data set. S ~ D", for all posterior sampling distribution Q on [n]", SGD with T iterations and = 1 satisfies
"=""forr
BB-0 [R(A(S: 0)) Rss (s(AAS)))) x
(DKI, + log 2) max [ T/n (1 (T/n)a) log n) log n, Vn
M
Remark 4. If we choose 7j T and T n², then Corollary gives the PAC-Bayes bounds of order ((1/vn). This choice of parameters was suggested in Theorem 7 in [27]. This gives the 0(1/V)) optimization bounds to get optimal trade-off between stability and optimization for non- smooth problems. The analysis in [32] cannot imply PAC-Bayes bounds for non-smooth problems.
4.2 Applications to Randomized Coordinate Descent
In this subsection, we consider RCD; this has not been studied in the PAC- AAC-Bayesian literature. RCD is an efficient optimization algorithm that randomly chooses coordinate update at each iteration [37]. Here we consider RCD with general sampling scheme, i.e. the coordinate to update follows a general distribution. This scheme has been studied before in the optimization context [1, 66).
Definition 7 (RCD with general sampling). Let W1 be an initial point. Let IP be a probability measure over (d] and S = {=1,-... 2n } be training dataset. Let (41...., (rr) be drawn according to P. At the t-th iteration, RCD with sampling scheme P updates the model by
Wt+1 Wt ?/ v Rig (We)c...
(4.5)
where {ne) } is step-size sequence, e, the i-th coordinate vector in Rd and Vig is the derivative of g w.r.t. the i-th coordinate. If IP is the uniform distribution, then we call it RCD with uniform sampling (RCDU).
Before giving the generalization bound for RCD, we first introduce coordinate-wise smoothness. Definition 8 ([37)). A differentiable function g W > IR has coordinate Lipschitz continuous gradients with parameter à > 0, if for all À E R. w E W.iC [d],
g(w (w + Xe,) S g (w) + X .g(w) + 2x2/2.
In Lemma 9, to be proved in Appendix B.2, we develop stability bounds for RCDU with convex and smooth loss functions. In particular, we show the stability follows a sub-exponential distribution.
Lemma 9 (Stability bound). Let S and S' be neighboring datasets. Suppose for all E Z the loss function is convex, a-smooth, L-Lipschitz and has coordinate-wise Lipschitz continuous gradients with parameter à O. Let {we). (w'} be the sequence produced by RCDU on S and S' respectively with The & 2/a. Then RCD with iterations is Bo Bo-uniformly stable with
B. = L
max TU kE[n)
V, ((W5:t)) - Vi
(4.6)
j=1
where V[((w;))] S L1 Furthermore, n. = n, then any 8 (0, the following inequality holds with probability at least 1 1-8 over O ~ P (the uniform distribution over (i1,...,, .4) : : E [d]}
2L
TT. n log(1/5) V
V
321
Bg I
nd +
n
Remark 5. Stability bounds of the order ((nt/(nd)) were developed for RCD in [62] (Theorem 2). Their stability bounds hold in expectation. In contrast, we develop pigb-probability stability bounds of the order ( nt
nd + :).
We plug the above bounds into Theorem 1, and derive the following PAC-Bayes bounds for RCD. Corollary 10 (Generalization bound). Let the assumptions in Corollary hold. We further assume that the gradient is coordinate-wist Lipschitz continuous. When TP is the uniform distribution, for any 6 E (0, 1), with probability at least 8 over draws of S DD", for all posterior sampling distributions Q on [d]T. RCD with the hyperparameter 0 and fixed step sizes nj S. 2/a satisfies
M
Ea~ R(A(S))) 0) Rs(A(S;0)) & (QII(QIIP) + log(1/6)) max
log n. Vn
nd

---

According to the above corollary, we can derive PAC-Bayes bounds of the order ((1/vn) if T= (dd/n) n and 1 = (1). These choices of parameters were suggested in Theorem 7 in [62] to balance optimization and stability for RCD.
5 Related Work
Related work on stability The analysis of the generalization error through algorithmic stability is based on the landmark work of [7]. Generalization bounds via stability algorithm-speccifcc and have been applied to regularization algorithms, such as SVM regression and classification [7, 11, 16, 52]. Pioneering work on stability analysis of SGD was introduced in [20], which motivated much subsequent stability analyses of randomized iterative algorithms [10, 24, 25, 31, 38, 45]. The smoothness assumption in [20] was removed in more recent stability analyses [3, 27] of SGD. Stability bounds showing the benefit of low training errors on generalization were also developed for convex [27, 39, 50J. nonconvex [28] and overparameterized models [12, 47, 59]. In recent works, stronger high-probability bounds via uniform stability have been developed. Some breakthroughs have narrowed down the difference between the risk and the empirical risk, leading to faster convergence rates with high probability [8, 17, 18].
Related work on PAC-Bayes bounds The PAC-Bayes theory of generalization dates back to works by [53] and [34] and further improved by [9, 26] and others. PAC-Bayes bounds are upper bounds on the generalization error of randomized learning algorithms, given in terms of data-dependent quantities that we can compute: the empirical error, and a quantity to measure the divergence between the PAC-Bayesian prior and posterior distributions, such as Kullback-Leible (KL) divergence or the Rényi divergence [4]. The framework was later extended to allow learning the prior from the data, resulting in tighter bounds [2. 14, 15, 35, 42, 48]. The sensitivity of learning algorithms to small perturbations in the weights can be analyzed through the properties of a distribution of predictors, which may lead to regularity and improve the generalization bounds [5]. By evaluating the algorithmic stability all possible outputs, stability of learning algorithms and PAC-Bayes bounds can be combined [32, 33, 35, 36, 40, 48, 57] and applied to randomized learning algorithms such as SGD and SGLD [30, 32, 35, 36]. For PAC-Bayes bounds, usually, the randomness is induced by a distribution on the parameters of a model. In [32], the authors isolated the randomness to view the randomized learning algorithm as deterministie, with hyperparameters following the distribution instead.
6 Conclusions
Under an assumption of sub-exponential stability parameter, we derive sharper stability-based PAC-Bayes bounds for randomized learning algorithms by utilizing a moment bound. We show that the sub-exponential stability assumption holds for SGD and RCD, for which we develop PAC- Bayes bounds as corollaries. Our results remove the need for the requirements of strong convexity. hyperparameter stability, and even smoothness in previous results.
Limitations. Future work of interest includes exploring other optimization methods that meet the sub-exponential assumption. It would also be interesting study the quality of bounds obtainable when placing the PAC-Bayes prior on the parameters of a model (as in the classic approach) versus the hyperparametrs of the optimiser of the model (as in this work). Another interesting research direction is to further improve the bound by including additional assumptions, As noted in [23], for the deterministic case, the bounds can be / /n-times faster under Bernstein condition between expectation and variance of loss functions.
Acknowledgements. The authors grateful to the anonymous reviewers for their thoughtful comments and constructive suggestions. The work of Yunwen Lei is partially supported by the Research Grants Council of Hong Kong [Project No. 22303723]. The work of Sijia Zhou is funded by CSC and UoB scholarship. AK acknowledges funding by EPSRC Fellowship grant EP/P004245/1.
References
[1] Z. Allen-Zhu, Z. Qu, P. Richtárik, and Y. Yuan. Even faster accelerated coordinate descent using non- uniform sampling. In International Conference on Machine Learning, pages PMLR, 2016.
10

---

[2] A. Ambroladze, E. Parrado-Hernúndez, and J. Shawe-Taylor Tighter pac-bayes bounds. Advances in Neural Information Processing Systems, 19, 2006.
[3 R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
[4] L. Bégin, P. Germain, F. Laviolette, and J.-F. Roy. Pac-bayesian bounds based on the rényi divergence. In Artificial Intelligence and Statistics, pages 435-444, 444.. PMLR, 2016.
[5] C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra. Weight uncertainty in neural network. In Machine Learning, pages 1613-1622. PMLR, 2015,
International Conference
[6] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning, SIAM Review, 60(2)2233 311, 2018.
[7] O. Bousquet and A. Elissceff. Stability and generalization. Journal of Machine Learning Research, 2
(Mar):499- 526, 2002.
[8] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626, 626, 2020.
[9] O. Catoni. A pac-bayesian approach to adaptive classificatiin. preprint, 840, 2003.
[10] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 744-753, 2018.
[11] J. Chen, H. Chen, X. Jiang, B. Gu, W. Li, T. Gong, and F. Zheng. On the stability and generalization of triplet learning. arXiv preprint arXiv:2302.0981 2023.
[12] P. Deora, R. Ghaderi, H. Taheri, and C. Thrampoulidis. On the optimization and generalization of
multi-hcar attention. 2023.
[13] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint orXiv:/703: 1008, 2017.
[14] G. K. Dziugaite and D. M. Roy. Data-dependent pac-bayes priors via differential privacy. In Advances in Neural Information Processing Systems, volume 31, 2018.
[15] G. K. Driugaite, K. Hsu, W. Gharbich, G. Arpino, and D. Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pages 604-612. PMLR, 2021.
[16] A. Elisseeff. T. Evgeniou, and M. Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79. 2005.
[17] V. Feldman and J. Vondrak. Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems, pages 9747-9757, 2018.
[18] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279, 2019.
[19] D. A. Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[20] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent.
In International Conference on Machine Learning, pages 1225-1234, 2016.
[21] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323, 2013.
[22] A. Kabán. Fractional norm regularization: Learning with very few relevant features. IEEE Transactions on Neural Networks and Learning Systems, 24(6):953-933, 2013.
[23] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate o(//r). Advances in Neural Information Processing Systems, 34, 2021.
[24] T. Koren, R. Livni, Y. Mansour, and U. Sherman. Benign underfitting of stochastic gradient descent. In Advances in Neural Information Processing Systems, 2022.
[25] I. Kuzborskij and C. I Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2820-2829, 2018
[26] J. Langford and R. Schapire. Tutorial on practical prediction theory for classification. Journal of Machine Learning Research, 6(3), 2005.
[27] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819, 2020.
[28] Y. Lei and Y. Ying. Sharper generalization bounds for learning with gradient-lominated objective functions. In International Conference on Learning Representations, 2021.
[29] Y. Lei. M. Liu, and Y. Ying. Generalization guarantee of sgd for pairwise learning. Advances in Neural
Information Processing Systems. 34:21216-211 -22288 2021.
[30] J. Li, X. Luo, and M. Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. International Conference on Learning Representations, 2020.
[31] J. Lin, R. Camoriano, and L. Rosasco. Generalization properties and implicit regularization for multiple passes SGM. In International Conference on Machine Learning, pages 2340-2346 2016.
11

---

[32] B. London. A PAC-bayesian analysis of randomized learning with application to stochastic gradient descent. In Advonces in Neural Information Processing Systems, pages 2931-2940, 2017.
[33] B. London, B. Huang. and L. Getoor. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1):7808-7852 2016.
[34] D. A. McAllester. Some pac- bayyasiaa theorems. Machine Learning. 37(3):355- 363, 1999.
[35] W. Mou, L. Wang. X. Zhai, and K. Zheng. Generalization bounds of sgld for non-convex learning: Two
theoretical viewpoints. In Conference on Learning Theory, pages 605 638, 2018.
[36] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. nnarmation-thcoreiie gencralization bounds for sgid via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
[37] Y. Nesterow. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal
Optimization, 22(2):341-362, 2012.
[38] K. Nikolakakis, F. Haddadpour, D. Kalogerias, and A. Karbasi. Black-box generalization: Stability of zeroth-order learning. Advances in Neural Information Processing Systems, 11:31525-3144) 2022. [39] K. E. Nikolakakis, F. Haddadpour, A. Karbasi, and D. S. Kalogerias. Beyond lipschitz: sharp generalization and excess risk bounds for full-batch gd. arXiv preprint ar XrX:::2004, 1 12446, 2022.
[40] L. Oneto. M. Donini, M. Pontil, and J. Shawe-Taylor, Randomized learning and generalization of fair and private classifiers: From pac-bayes to stability and differential privacy. Neurocomputing, 416:231-243, 2020.
[41] F. Orabona. Simultaneous model selection and optimization through parameter-free stochastic learning. In Advances in Neural Information Processing Systems, pages 1 1116-1 124, 2014.
[42] E. Parrado-Hernándzz, A. Ambroladze, J. Shawe-Taylo and S. Sun. Pac-bayes bounds with data dependent priors. The Journal of Machine Learning Research, (35573357333 2012.
[43] M. Pérez-Ortiz, O. Rivasplata, B. Gucdj. M. Gleeson, J. Zhang. J. Shawe-Taylor, M. Bober, and J. Kittler. Learning pac-bayes priors for probabilistic neural networks. arXiv preprint arXiv:2109.108: 10304, 2021.
[44] M. Pérez-Ortiz, O. Rivasplata, J. Shawe-Taylor, and C. Szepesvári. Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22, 2021.
[45] A. Raj, I.. Zhu, M. Gurbuzhalaban, and U. Simsekli. Algorithmic stability of heavy-tailed sgd with general loss functions. In International Conference on Machine Learning, pages
2023.
[46] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning, pages 449-456, 2012.
[47] D. Richards and I. Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. Advances in Neural Information Processing Systems, 34, 2021.
[48] O. Rivasplata, E. Parrado-Ieernnndez. J. S. Shawe-Taylor, S. Sun, and C. Szepesvári. Pac-bayes bounds for stable algorithms with instance-dependent priors. In Advances in Neural Information Processing Systems, pages 9214 9224, 2018
[49] F. Salehi. L. E. Celis, and P. Thiran. Stochastic optimization with bandit sampling. arXiv preprint 2017.
arXiv:1708.0255
[50] M. Schliserman and T. Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In Conference on Learning Theory, pages 3380-3394. PMLR, 2022.
[51] S. Shwlav-SSwartz and S. Ben-David. Understanding machine learning: From theory to algorithums. Cambridge university press, 2014.
[52] S. Shalev-Shwatzz, O. Shamir, N. Srebro, and K. Sridharan. Learnaillity. stability and uniformm convergence. Journal of Machine Learning Research, 11(Oct):2635 2670, 2010.
[53] J. Shawe-Taylor and R. C. Williamson. A pac analysis of bayesian estimator. In Proceedings of the Tenth Annual Conference on Computational Learning Theory, pages 2 9, 1997.
[54] S. Smale and D.-X. Zhou. Online learning with markov sampling. Analysis and Applications, 7(01): 87-113, 2009.
[55] K. Sridharan, S. Shalev-Shwartz, and N. Srebro. Fast rates for regularized objectives. In Advances in Neural Information Processing Systems, pages 1555-1552, 2009.
[56] S. U. Stich, A. Raj. and M. Jaggi. Safe adaptive importance sampling. Advances in Neural Information Processing Systems, 30, 2017.
[57] S. Sun, M. Yu, J. Shawe-Taylor and L. Mao. Stability- based pac-bayes analysis for multi-view learning algorithms. Information Fusion, 86:76-92, 2022.
[58] T. Sun, Y. Sun, and W. Yin. On markov chain gradient descent. Advances in Neural Information Processing Systems, 31, 2018
[59] H. Taheri and C. Thrampoulidis. Generalization and stability of interpolating neural networks with minimal width. arXiv preprint arXiv:2302.09255 2023.
[60] R. Van Handel. Probability in high dimension. Lecture Notes (Princeton University), 2014.
12

---

[61] R. Vershynin. High-dimensionul probability: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.
[62] P. Wang, L. Wu, and Y. Lei. Stability and generalization for randomized coordinate descent. In International Artificial Intelligence, pages 3104-3110, 2021.
Joint Conference
[63] P. Wang. Y. Lei, Y. Ying. and D.-X. Zhou. Stability and generalization for markov chain stochastic gradient methods. In Advances Neural Information Processing Systems, pages 37735-37745 2022.
[64] B. Woodworth, K. K. Patel, S. Stich, Z. Dai, B. Bullins, B. Mcmahan, O. Shamir, and N. Srebro. Is local sgd better than minibatch sgd? In International Conference Machine Learning, pages
PMI.R, 2020.
[65] Y. Zhang. W. Zhang. S. Bald, V. Pingali, C. Chen, and M. Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty Artificial Intelligence, pages 2364 2373. PMLR, 2022.
[66] P. Zhao and T. Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In International Conference Machine Learning, pages 1-9, 2015.
13


Reviews:
[{"review_id": "FxoTJl0Ptr", "reviewer": "Reviewer_ZHyT", "summary": "In this paper, the authors extend the work of London [29] and prove PAC-Bayesian generalization bounds for uniformly stable algorithms. Compared to [29], the present work removes some required assumptions in the work of [29], such as the hyperparameter stability. To do so, they required a new assumption called \"Sub-exponential stability\" and proved Theorem 1 based on this new assumption. They further instantiate their theorem for stochastic gradient descent and randomized coordinate descent.", "questions": "_Major comments_:  \n\n- **l173**: In the current form of Theorem 2, I could not compare it with Theorem 2 of [29]. Indeed, for me, in [29], their bound includes the term $\\beta_{\\mathcal{Z}}$ while you have instead $\\mathbb{E}\\_{\\theta\\sim\\mathbb{P}}[\\beta\\_\\theta]$. Indeed, by looking at the two definitions, i.e. your Definition 1 and one in [29], the expectation over $\\mathbb{P}$ is not in the same place.  \n- **l179-181**: I am confused with your $\\widetilde{O}(\\cdot)$ notation and your discussion below.\nIndeed, your discussion involves the KL divergence, but it is hidden in the two equations. Hence, the discussion is hard to understand in this current form.  \n- **l270**: In [29], $R\\_S$ does not have to be necessarily $\\gamma$-strongly convex and $\\alpha$-smooth. Indeed, they consider another function (called $F$ in their notations) to be minimized.  \n\n_Minor comments_:  \n\n- **l152**: I would have expected to have $M$ in the bound since you introduced the notation in the statement of the theorem.  \n- **l494**: You cite the wrong Theorem in [8]; you cite an old version of the paper. By the way, the constants are improved in the new version of the theorem.  \n- **l512**: Since [55] is a book, can you cite the section or the theorem of the Lemma for readability?  \n\n_Typos_:  \n\n- **l154**: There is \"..\" at the end of the sentence.  \n- **In Appendix B**: there is some \"$-$\" that are in fact \"$+$\".", "limitations": "I do not see any potential negative societal impact of their work since it is theoretical.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The hyperparameter stability assumption is not required in the present analysis.\n- The strong convexity assumption in the SGD applications is removed compared to the analysis of [29].\n- To the best of my knowledge, this is the first time that Randomized Coordinate Descent is studied in the literature.", "weaknesses": "- I find the $\\lesssim$ and the $\\widetilde{O}$ notations sometimes confusing (see the comments below).\n- The statements of the theorems of [29] do not seem to be correctly restated.\n- There are no experiment evaluations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions.\n\n**Q1**. L173: In your Definition 1 and one in [29], the expectation over $\\mathbb{p}$ is not in the same place.\n\n**A:** Thanks for the careful reading and indicating this. $\\mathbb{E}[\\beta_\\theta]$ in our submission is different from $\\beta_{\\mathcal{Z}}$ in [29] in the sense of taking expectation in different places: expectation is outside $\\sup$ in $\\mathbb{E}[\\beta_\\theta]$, and inside $\\sup$ in $\\beta_{\\mathcal{Z}}$. However, we often have similar upper bounds for $\\beta_{\\mathcal{Z}}$ and $\\mathbb{E}[\\beta_\\theta]$. Consider SGD for smooth, Lipschitz and convex problems as an example. The paper [19] shows $\\beta_{\\mathcal{Z}}\\leq 2L^2\\sum_{k=1}^t\\eta_k/n$, while we show $\\mathbb{E}[\\beta_\\theta]\\leq 2L^2\\sum_{k=1}^t\\eta_k/n$ in the proof of Lemma 3. These two upper bounds are the same. Furthermore, lower bounds were established in [R1, Thm 1]: $\\beta_{\\mathcal{Z}}\\geq \\frac{L}{2}\\sum_{k=1}^t\\eta_k/n$, which match the existing upper bounds up to a constant factor. This shows that $\\beta_{\\mathcal{Z}}$ and $\\mathbb{E}[\\beta_\\theta]$ are of the same order.  Also, the analysis in [29] involves $\\beta_{\\Theta}$ which takes supremum over $\\theta,z,S$. We remove this term by introducing the sub-exponential condition. Here the expectation is taken with respect to $\\theta\\sim\\mathbb{P}$ in $\\mathbb{E}[\\beta_\\theta]$.\n\n**Q2**. L179-181: I am confused with your $\\widetilde{O}$ notation and your discussion below. Indeed, your discussion involves the KL divergence, but it is hidden in the two equations. Hence, the discussion is hard to understand in this current form.\n\n**A:** Thanks for indicating this. We will add the term $D_{\\text{KL}}(\\mathbb{Q}\\|\\mathbb{P})$ in the equations and revise it as follows: we show\n\n   $$\\mathbb{E}\\_{\\theta\\sim\\mathbb{Q}} \\big [R(A(S;\\theta))-R_S(A(S;\\theta))\\big] =  \\widetilde{O}\\big(\\mathbb{E}\\_{\\theta\\sim\\mathbb{P}}[\\beta_\\theta]+ \n   n^{-\\frac{1}{2}}\\big)D_{\\text{KL}}(\\mathbb{Q}\\|\\mathbb{P}),$$\n\n  while the analysis in [29] shows\n\n  $$\\mathbb{E}\\_{\\theta\\sim\\mathbb{Q}} \\big [R(A(S;\\theta))-R_S(A(S;\\theta))\\big] = \\widetilde{O}\\big(\\sqrt{n}\\mathbb{E}\\_{\\theta\\sim\\mathbb{P}}[\\beta_\\theta] + \\sqrt{T} \\beta_\\Theta\\big)D^{\\frac{1}{2}}_{\\text{KL}}(\\mathbb{Q}\\|\\mathbb{P}).$$\n\n  Then, if the KL divergence is dominated by the stability parameter, our bound can be sharper up to a factor of $\\sqrt{n}$.\n\n  **Q3**.  L270: In [29], $R_S$ does not have to be necessarily strongly convex and smooth. Indeed, they consider another function (called $F$ in their notations) to be minimized.\n\n   **A:** The analysis in [29] requires the objective function $F$ to be strongly convex, Lipschitz and smooth, which, as you indicated, may not be $R_S$. As a comparison, we do not require the objective function to be strongly convex, and therefore our analysis can apply to SGD to minimize $R_S$ directly. We will clarify this confusion by modifying the statement of Corollary 5 (Corollary 1 in [29]).\n\n**Q4**. L152: I would have expected to have $M$ in the bound since you introduced the notation in the statement of the theorem.\n\n**A:**  Yes, the bound depends on $M$. We showed the dependency on $M$ in the proof of Theorem 1 (Appendix A.1, Line 550), and absorbed it in the $\\lesssim$ notation in the statement of Theorem 1. We will state them clearly in Theorem 1.\n\n  **Q5**.  L494: You cite an old version of the paper [8].\n\n **A:** Thanks for indicating this. We will cite the new version and modify the constants.\n\n **Q6**.  L512: Can you cite the section or the theorem of the Lemma for readability?\n\n **A:** Thank you for the suggestion. We agree. We refer to Prop. 2.5.2 and Prop. 2.7.1 in [55]. We will mention it clearly in the revision.\n\n **Q7**. Some Typos.\n\n **A:** Thank you for spotting the typos. We will fix them in the revision.\n\n[R1]: Stability of SGD: Tightness Analysis and Improved Bounds. Zhang et al. UAI, 2022."}, {"review_id": "rnvvzKp9IN", "reviewer": "Reviewer_V6pn", "summary": "In this paper, the authors study PAC-Bayesian bounds on the generalization error of uniformly stable algorithms. They consider algorithms in which the randomness comes from a particular hyperparameter $\\theta$, e.g., stochastic gradient descent (SGD), in which the randomness comes from selecting the indices used to determine which samples are utilized in the gradients. This way, they consider algorithms that are stable for every choice of the hyperparamter $\\theta$, but they allow different degrees of stability $\\beta\\_\\theta$ for every parameter. They only require that the stability parameter is at least exponentially close to its mean under some prior distribution $\\mathbb{P}$, that is $\\beta\\_\\theta \\leq \\mathbb{E}\\_{\\vartheta \\sim \\mathbb{P}} [\\beta\\_\\vartheta] + \\tilde{b} \\log(1/\\delta)$ with probability $1 - \\beta$ over the draws of $\\theta$ (sub-exponential condition).\n\nIn this setup, they obtain generic PAC Bayes bounds that scale linearly with the KL divergence between a posterior over the parameters $\\mathbb{Q}$ and the prior $\\mathbb{P}$. These bounds have the same rate as the bounds from Bousquet, Klochkov, and Zhivotovskiy [8, Corollary 8] when the parameters are deterministic. Moreover, compared to the PAC-Bayes bounds from London [29, Theorem 2], they substitute the parameter uniform stability by the sub-exponential condition, which is weaker, and their bound still has a better rate.\n\nIn terms of applications:\n* They show that SGD with a Lipschitz, convex, and smooth loss is stable for all parameters $\\theta$ selecting the indices to determine which samples are utilized in the gradients, and that that the parameters satisfy the sub-exponential condition for a uniform prior distribution. This way, they can obtain a generalization bound with rate $\\tilde{O}(1/\\sqrt{n})$, improving upon London's bounds [9] that require strong convexity and potentially have a worse rate.\n* They show that the smoothness assumption can be lifted and there are still choices of the learning rate and number of iterations under which the rate is $\\tilde{O}(1/\\sqrt{n})$.\n* They show that randomized coordinate descent (RCD) with a Lipschitz, convex, smooth, and coordinate-Lipschitz loss is also stable for all parameters $\\theta$ used to select the coordinate where the gradient is taken, and  that the parameters satisfy the sub-exponential condition for a uniform prior distribution. This way, they obtain bounds of a similar order to Wang, Wu, and Lei [56] that hold with high probability instead than in expectation.", "questions": "* I don't understand how you go from the equation after line 593 to the equation after line 540.\n* Could you elaborate on more cases in Remark 2? From what I see, in Remark 2 using the standard $T \\in \\Theta(n)$ and a small learning rate $\\eta \\in O(1/\\sqrt{n})$ yields a reasonable rate of $\\tilde{O}(1/\\sqrt{n})$ as well.  \n\nRepeating here some of the questions in the weaknesses:\n* After line 538 shouldn't it be 36 instead of 72?\n* After line 538, where did the multiplicative factor of 2 in the second exponential?\n* It seems you forgot a + 3 on the right-hand side of equation 547. This should also appear in the general statement of the theorem as $(D\\_{\\mathrm{KL}}(\\mathbb{Q} \\Vert \\mathbb{P}) + \\log \\frac{1}{\\delta} + 3)$. Shouldn't it? ", "limitations": "The authors discuss some of the limitations throughout the text and in the conclusion.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In terms of originality, the main source of originality is the consideration of per hyper-parameter uniform stability + a sub-exponential condition in the stability parameter. The analysis employed for finding the bound for a fixed hyper-parameter is very similar to Bousquet, Klochkov, and Zhivotovskiy [8], but the consideration of a sub-exponential condition on the stability parameter and the introduction of said condition to find generic bounds is novel.\n\nSimilarly, the proofs to show that SGD and RCD are stable with a sub-exponential stability parameter are based on common analyses in the field + standard concentration arguments. However, combining them into this setting is also new as far as I know.\n\nIn general, the idea of introducing a prior and a posterior over the parameters did not seem very relevant in the beginning, as many times the hyper-parameters distribution is independent of the data and one can always have $\\mathbb{Q} = \\mathbb{P}$ with a zero divergence. However, it appeared to be quite clever afterwards since one only needs to prove the sub-exponential condition for the prior and see how far the actual distribution is from that.\n\nThe results seem significant since the control of the sampling is often a drawback in many analyses of SGD and its variants, that have very specific forms of sampling. Also, some of the results obtained are already as good as previous results in the literature when reduced to their setting, or more general, or better.", "weaknesses": "I believe that some things could be clarified. For instance what I mentioned in the strengths about the introduction of a prior and a posterior. Some commentary about that would be helpful. At least for readers like me, who may be wondering why would one introduce this seemingly artificial distribution over the hyper-parameters.\n\nAlso, it would be good to clarify that in Corollaries 4,7, and 9 the prior $\\mathbb{P}$ must be the uniform distribution. Similarly, it would be easier for the reader if in Definition 7 you would use the same letter used fro priors throughout, i.e. $\\mathbb{P}$.\n\nSometimes in the text and in the appendices, references are cited without the specific place where one should look. This difficults the reader experience. For instance, For Lemma A.2 only [55] is mentioned, when it refers to a combination of Propositions 2.5.2 and 2.7.1. I hope the authors go back to their text and look at their citations and try to specify better where the reader should look.\n\nIn Lemma A.1, the authors seem to use the version v1 of the paper [8] in the arxiv. They may want to look at Theorem 4 in the latest version (and the version actually published). They will see that the constants are improved: $3 \\sqrt{2}$ is actually $4$ and $\\sqrt{6}$ is actually $\\sqrt{2}$. \n\nLemma A.3 is not the Donsker-Varadhan formula. The Donsker-Varadhan formula deals with the supremum of the functions $h$ appearing in their equation, finding a dual equivalence. The shown theorem is the Gibbs variational principle (see e.g. Lemma 4.10 of [A]).\n\nThere seem to be some mistakes in the constants in the proof of Theorem 1. Not very important as they seem to be solvable:\n* After line 538 shouldn't it be 36 instead of 72?\n* After line 538, where did the multiplicative factor of 2 in the second exponential?\n* It seems you forgot a + 3 in the right hand side of equation 547. This should also appear in the general statement of the theorem as $(D\\_{\\mathrm{KL}}(\\mathbb{Q} \\Vert \\mathbb{P}) + \\log \\frac{1}{\\delta} + 3)$. Shouldn't it? \n\n**Additional References**\n\nRamon van Handel. \"Probability in High Dimension\". APC 550 Lecture Notes. Princeton University. 2016.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions.\n\n  **Q1**.  It would be better to clarify why would one introduce this seemingly artificial distribution over the hyper-parameters.\n\n   **A:** Thanks for the suggestion. We will add more discussions on the distribution of the hyper-parameters. In particular, we will emphasize that it allows us to build a PAC-Bayesian bound holding for any arbitrary posterior distribution, which allows us to learn a posterior distribution to minimize the bound and draw a hyperparameter from this posterior distribution for the implementation of the algorithm.\n\n  **Q2**.  It would be good to clarify that in Corollaries 4,7, and 9 the prior must be the uniform distribution.\n\n   **A:** We agree, and will follow your suggestion to mention it clearly in the revision.\n\n  **Q3**.  Sometimes in the text and in the appendices, references are cited without the specific place where one should look. For instance, For Lemma A.2 only [55] is mentioned, when it refers to a combination of Propositions 2.5.2 and 2.7.1.\n\n   **A:** Thank you for indicating this and checking the reference. Yes, Lemma A.2 is a combination of Propositions 2.5.2 and 2.7.1 in [55].  We will mention the specific result when citing a result in a book in the revision.\n\n  **Q4**.  In Lemma A.1, the authors seem to use the version v1 of the paper [8] in the arxiv.\n\n   **A:** Yes, you are right. We will use the improved constants in the new version. Thanks for indicating this.\n\n  **Q5**. Lemma A.3 is not the Donsker-Varadhan formula. The shown theorem is the Gibbs variational principle (see e.g. Lemma 4.10 of [A]).\n\n   **A:** Thank you for indicating this. We will modify it and update the reference in the revision.\n\n  **Q6**. I don't understand how you go from the equation after line 539 to the equation after line 540.\n\n   **A:** Thank you for checking the details. The r.h.s. of the inequality after line 539 is of the form $\\exp(a) \\cdot (\\exp(b) +\\exp(c)) +\\delta$, where $a,b,c>0$ are some terms indicated in the inequality.\n\n  Then, we actually use the following inequality to get the equation after line 540\n\n  $$\\exp(a) \\cdot (\\exp(b) +\\exp(c)) +\\delta\\leq \\exp(a+1/2) \\cdot (\\exp(b) +\\exp(c)).$$\n\n  This is equivalent to\n\n  $$\\delta \\leq (\\exp(b) +\\exp(c))\\exp(a)\\big(\\sqrt{e}-1\\big).$$\n\n  This holds directly since $\\delta<1,\\exp(b)+\\exp(c)\\geq2$ and $\\sqrt{e}-1\\geq1/2$. We will give more details in the revision.\n\n **Q7**.  Could you elaborate on more cases in Remark 2?\n\n   **A:** Thank you for the comment. If we choose $T=\\Theta(n)$, then the bound would be of the order $O(\\eta\\sqrt{n}\n   +1/\\sqrt{n})$ (ignoring KL divergence and log factors). Then $\\eta$ should be of order $O(1/n)$ to get the generalization bound $O(1/\\sqrt{n})$. In this case, the $\\eta=O(1/T)$ would be too small to get a good decay of optimization error.\n\n **Q8**.  Line 538: coefficient should be $36$ instead of $72$?\n\n   **A:** Thanks for checking the details. Yes, it should be $36$ instead of $72$. We will modify it.\n\n  **Q9**. Line 538, where did the multiplicative factor of 2 in the second exponential?\n\n   **A:** Thanks for the careful reading. We want to bound $\\mathbb{E}\\exp(2\\lambda X_2)$ and therefore should apply Eq (A.12) with $\\lambda$ replaced by $2\\lambda$.\n\n  **Q10**. Line 547, it seems you forgot $a + 3$ in the right hand side of equation 547.\n\n   **A:** Thank you for careful reading. Yes, there should have $+3$ in the proof and we absorbed it in the big $O$ notation in the statement of Theorem 1. We will modify it in the revised version. \n"}, {"review_id": "7mkq27Ve82", "reviewer": "Reviewer_qrJQ", "summary": "The work aims to provide stronger generalization guarantees for stochastic algorithms through the analysis of stability and PAC-Bayes. Such algorithms include SGD and RCD. The work uses a milder assumption in the analysis under the same problem setting as [29]. The results can be extended beyond strong convexity from previous results and hold for non-smooth convex problems.", "questions": "1. Although it’s a similar setting as [29], it’s unclear why you need PAC-Bayes analysis to guarantee all distributions Q over the hyperparameter space. It doesn’t seem like you are trying to learn some good distributions Q of randomized rule. As far as I can see, you are interested in providing a generalization guarantee for some fixed distribution, regardless of how arbitrary it is. Therefore, isn’t it enough to have results for a fixed distribution like in [15]?\n\n2. I feel there is something missing in the results related to assumption 1. It looks like assumption 1 is a characterization of a randomized algorithm A defined by some distribution P. And it essentially says all deterministic algorithms defined by \\theta in the support of P are nice in the sense of being \\beta_\\theta-uniform stable. Also, the distribution P itself is nice in the sense that the \\beta_\\theta from such P is w.h.p. not too far from the mean with some parameter \\tilde b.\n\na) Is the stability constant \\tilde b in assumption 1 a function of the distribution P? \n\nb) It’s perhaps better to say, in line 136, that it’s uniform stable “w.r.t. a loss function \\ell” since it makes little sense to talk about stability without mentioning the loss. Also, the \\ell\\in[0,M] assumption in line 152 should perhaps be associated with the stability conditions in assumption 1 rather than be put independently.\n\nc) Again, assumption 1 is a characterization of some A defined by some P. Hence, it’s not clear what it means by “a learning algorithm A that satisfies Assumption 1” (in line 152) without mentioning the associated distribution. Also, it’s most likely that other distributions Q won’t follow the same sub-exp stability constant \\tilde b as P (the formula in theorem 1).\n\n3. Do you have any idea why Theorem 1 doesn’t depend on the loss range M? It is neither in the bound nor in the stability constant \\beta_\\theta in your example in Lemma 3.\n\n4. In Lemma 3, the SGDU is explicitly associated with a distribution P=uniform. It’s not clear to me why this randomized algorithm is \\beta_\\theta uniformly stable, which only depends on some specific \\theta.", "limitations": "There were quite some fast-rate results in PAC-Bayes analysis in other applications. There are also some fast-rate analyses for the algorithms addressed in the work but with stronger assumptions on losses. However, due to the “max” function in theorem 1, the results here cannot go beyond O(1/sqrt(n)) convergence rate. Whether a fast rate is possible here can be an interesting question.", "rating": 4, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "If the results are correct, they are tighter than a previous work [29] in the same problem setting. Also, they require milder assumptions (uniform stability and sub-exp stability), whereas [29] requires some stability w.r.t. the changes of the data and the hyperparameters. Therefore, although they build from the setting in [29], they require different analysis techniques.", "weaknesses": "The significance of the results is not very clear. Please see more details in Question 1.\n\nThe soundness of the results is not clear. Please see more details in the next section from point 2 and beyond.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions.\n\n  **Q1**. It is unclear why you need PAC-Bayes analysis to guarantee all distributions $\\mathbb{Q}$. Isn't it enough to consider a fixed distribution like in [15]?\n\n   **A:** Thank you for the intuitive question. Since the PAC-Bayes bound holds uniformly for any posterior $\\mathbb{Q}$, we are allowed to select the best $\\mathbb{Q}$ that minimises (or approximately minimises) the bound, despite it depends on the training set. In other words we can learn $\\mathbb{Q}$ from the data by minimising the bound, i.e. select a distribution $\\mathbb{Q}$ that balances the trade off between minimizing empirical error and reducing the KL divergence between the prior and posterior. Indeed [29] demonstrates an algorithm that learns $\\mathbb{Q}$ by approximately minimising the PAC-Bayes bound. The algorithm associated with our work is the same as there, our contribution is an improved analysis / convergence rate. Namely, it suffices to study uniform stability under the prior distribution and we have the flexibility to choose any posterior distribution. This can not be achieved in [15], as that requires the choice of $\\mathbb{Q}$ to be made before seeing the data.\n\n  **Q2**.  I feel something missing in results related to Assumption 1, which is a characterization of $A$ and says all deterministic algorithms are $\\beta_\\theta$-uniformly stable. Also, $\\beta_\\theta$ is not far from the mean.\n\n **A:** Thank you for the comment. In Assumption 1 we consider a randomized algorithm $A$ with a random hyperparameter $\\theta\\sim\\mathbb{P}$. For each $\\theta$, we have a deterministic algorithm. For $\\theta \\sim \\mathbb{P}$ we can estimate the uniform stability $\\beta_\\theta$ of the algorithm defined in Definition 1, which is a function of random $\\theta$. In Assumption 1, we assume $\\beta_\\theta$ concentrates around its expectation w.h.p., under the distribution $\\mathbb{P}$. Take SGD with $T$ iterations as an example. Then we have $\\theta=(i_1,\\ldots,i_T)$ and we derive an upper bound of $\\beta_\\theta$ as a function of random $(i_1,\\ldots,i_T)$. With concentration inequality, we then show that $\\beta_\\theta\\leq \\mathbb{E}[\\beta_\\theta]+O(\\eta(1+t/n))$ w.h.p. in Lemma 3, where the expectation is $\\theta\\sim\\mathbb{P}$. A crucial point is that in our PAC-Bayesian analysis, we only need to check the stability for any fixed $\\mathbb{P}$. Therefore, we can choose $\\mathbb{P}$ to be simple, e.g., the uniform distribution over $\\{(i_1,\\ldots,i_T)\\}$ in the case of SGD. We will add more discussions in the revision.\n\n  **Q3**.  Is the stability constant $\\tilde b$ a function of $\\mathbb{P}$?\n\n   **A:** Yes. Since the assumption is made w.r.t. $\\mathbb{P}$, the term $\\tilde{b}$ depends on $\\mathbb{P}$. For SGD, we give an explicit form of $\\tilde{b}$ in Lemma 3 when $\\mathbb{P}$ is a uniform distribution.\n\n  **Q4**.  It makes little sense to say stability without mentioning loss. $\\ell\\in[0,M]$ should be associated with Assumption 1.\n\n   **A:** Yes, the stability depends on the loss function. To avoid confusion and for brevity, we will emphasize that we always mean stability w.r.t. $\\ell$ when mentioning stability. We do not associate $\\ell\\in[0,M]$ with Assumption 1 since stability may not depend on $M$. For example, in Lemma 3 we show Assumption 1 holds without dependency on $M$, which is consistent with existing stability bounds [19].\n\n  **Q5**.  \"a learning algorithm that satisfies Assumption 1\" is not clear without mentioning distribution. Other distributions $\\mathbb{Q}$ won't follow the same sub-exp stability.\n\n   **A:** Thanks for the comment. When we mention Assumption 1 we always mean Assumption w.r.t. $\\mathbb{P}$. The underlying reason is that our analysis only requires Assumption 1 to hold for any fixed $\\mathbb{P}$. We do not need to check Assumption 1 for the posterior distribution $\\mathbb{Q}$. Indeed, we use PAC-Bayesian analysis to transfer the stability for the particular $\\mathbb{P}$ to get results holding for any posterior distribution $\\mathbb{Q}$. To avoid confusion, we will emphasize in the revision that we always mean the prior distribution $\\mathbb{P}$ when mentioning Assumption 1.\n\n  **Q6**. Do you have any idea why Theorem 1 doesn't depend on the loss range $M$? It is neither in the bound nor in the stability constant $\\beta_\\theta$ in your example in Lemma 3.\n\n   **A:** Theorem 1 actually depends on $M$. We showed the dependency on $M$ in the proof (Line 550), and absorbed it in the $\\lesssim$ notation in Theorem 1. We will state them clearly in the revision. $\\beta_\\theta$ may not depend on $M$. Instead, it depends on $L$ [19], and we include this dependency in Lemma 3.\n\n  **Q7**.  In Lemma 3, the SGDU is explicitly associated with a distribution $\\mathbb{P}=\\text{uniform}$. It is not clear to me why this randomized algorithm is $\\beta_\\theta$ uniformly stable.\n\n   **A:** Thank you for the comment. We give proof for the uniform stability of SGDU in both smooth and nonsmooth cases from line 568 to line 585 and from line 590 to line 605. A strength of our result is that we only need to check the sub-exponential condition of the stability for any prior distribution $\\mathbb{P}$. Then we use PAC-Bayesian analysis to transfer the stability for the particular $\\mathbb{P}$ to get results holding for any posterior distribution $\\mathbb{Q}$. For SGD with $T$ iterations, the randomness comes from the sampling of index $\\theta=(i_1,\\ldots,i_T)$. For each $\\theta$, we get a deterministic algorithm. Therefore, for $\\theta \\sim \\mathbb{P}$, we can estimate the uniform stability by using the convexity, Lispchitz and smoothness assumption, following the idea of existing stability analysis of SGD [19]. This stability bound for SGD with the hyperparameter $\\theta$ depends on $\\theta=(i_1,\\ldots,i_T)$. Since $\\theta$ is a random hyperparameter, we further use concentration inequality to show that $\\beta_\\theta$ is a sub-exponential random variable."}, {"review_id": "H4oEegKRrd", "reviewer": "Reviewer_qzEi", "summary": "This paper gave an improved PAC-Bayes bound for uniformly stable randomized algorithms. It introduced new assumptions and proof techniques. The paper also applied the general theorem to concrete applications (SGD and RCD) and got better or novel PAC-Bayes bound for these two algorithms. ", "questions": "1. In line 79, it says \"given the parameter $w\\in W$\", what does this mean? Shouldn't the algorithm output $w$ instead of given $w$? Or do you mean \"given the parameter class $W$\"?\n2. In line 183-185 you claimed that the benefit of PAC-Bayes bound is that the prior and posterior can be selected and posterior parameters can be optimized? I understand the prior can be selected freely but isn't the posterior depends on $S$ and the algorithm? This part may need more explanation.\n3. If my understanding is correct, in both of your applications (SGD and RCD), even in the generalized version, the sampling distribution is still a fixed distribution across all iterations. Can you extend your result to algorithms where the sampling distribution could be different in every iteration or even depend on the history?\n", "limitations": "The authors addressed the limitation of their paper properly.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The general PAC-Bayes bound improvement in this paper is good. Although the improvement doesn't always hold, it is sharper in most cases and can be up to $\\sqrt{n}$, which is significant. This result seems to be quite non-trivial.\n2. The authors introduced new assumptions and proof techniques. The newly introduced assumption of sub-exponential stability is interesting and provided a new perspective compared to the previous assumption. The new proof technique is innovative and could be studied and used on proving other problems.\n3. The paper gave concrete applications to the general theorem, which shows the power of such bound. The bound for SGD is sharper and requires no strong convexity and the bound for RCD is completely novel. These results are nice contributions.\n4. The paper is well-written. As someone who doesn't know much about PAC-Bayes, reading the paper doesn't take too much effort. Sufficient background information is given, definitions are clearly and maths are rigorous. Contributions and novelty of the paper is highlighted properly.", "weaknesses": "1. One thing I find confusing is that the prior and posterior are over the hyperparameters but not on the hypothesis class, while usually in the PAC-Bayes framework the prior and the posterior are defined over the hypothesis class. This part should be clarified, I think more background or explanation is needed.\n2. The use of the word \"parameter\" and \"hyperparameter\" is a bit confusing because the meanings seem to be different from its usual meaning. Actually the parameter class $W$ barely shows in the paper and I think it is basically equivalent to $H$ here. From my understanding, \"hyperparameter\" here is just the random seed of the algorithm, but usually it means something like the step size. Maybe changing the names could make it better.\n3. A very tiny typo: line 101 should be \"parameters\" instead of \"parameter\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions.\n\n  **Q1**.  The prior and posterior are over the hyperparameters but not on the hypothesis class.\n\n   **A:** Thanks for the suggestion. We build on the idea of [29] to consider the prior and posterior on the hyperparameters instead of that on the hypothesis class. In the context of randomized algorithms, it is more natural to handle the randomness through the distribution on the hyperparameters as compared to hypothesis. Then, we can learn a good posterior distribution and draw a hyperparameter from this posterior distribution for the implementation of an algorithm. Another benefit is that the posterior distribution on the hyperparameters is usually simple, while the associated distribution on hypothesis can be very complicated. For example, the paper [R1] designs an importance sampling strategy for SGD, where at each iteration the index is drawn from a non-uniform distribution on $\\{1,2,\\ldots,n\\}$. While this posterior distribution on hyperparameters is simple, the resulting distribution of models produced by SGD can be very complicated. We will give more background in the revised version.\n\n  **Q2**.  The use of the word \"parameter\" and \"hyperparameter\" is a bit confusing.\n\n   **A:** Thanks for indicating this. We agree that this may cause confusion, and will clarify as follows. As in [29] we use the term ''hyperparameters'' to mean random seeds. In particular, we will use \"weights\" to mean $\\mathbf{w}$. We will emphasize that  hyperparameters mean the random seeds of the algorithm in our setting, as in [29].\n\n  **Q3**.  What is the meaning of \"given the parameter $\\mathbf{w}\\in W$\"?\n\n   **A:** Thanks for indicating this. We wanted to mean $h_{\\mathbf{w}}$ is determined by $\\mathbf{w}\\in W$. We will modify it as ''maps the training examples to a hypothesis $h_{\\mathbf{w}}\\in\\mathcal{H}$ determined by $\\mathbf{w}\\in W$''.\n\n  **Q4**.  I understand the prior can be selected freely but isn't the posterior depends on data and the algorithm? This part may need more explanation.\n\n   **A:** Thanks for the suggestion. Yes, the prior can be selected freely if it is independent of the data $S$. The posterior can depend on the data $S$. Indeed, a strength of the PAC-Bayesian analysis is that it applies to any posterior distribution. The posterior distribution can even depend on the data, and therefore it allows to choose a distribution $\\mathbb{Q}$ in a data-dependent manner. For example, [R2,R3] and [29] trained data-dependent posterior distributions to minimize the bounds. We will add more explanations in the revised version.\n\n\n  **Q5**.  For both SGD and RCD, the sampling distribution is still a fixed distribution across all iterations. Can you extend your result to algorithms where the sampling distribution could be different in every iteration or even depend on the history?\n\n   **A:** Yes, while we only consider the uniform distribution in checking the sub-exponential condition for SGD and RCD, our results apply to any posterior distributions. The sampling distribution of the algorithm can be different in very iteration or even depend on the histroy. Indeed, the posterior distribution $\\mathbb{Q}$ is the distribution of the indices $\\theta=(i_1,\\ldots,i_T)$, where $i_t$ is drawn from a sampling distribution at the $t$th iteration. The only requirement is to compute the KL divergence between $\\mathbb{p}$ and $\\mathbb{Q}$. A strength of the combining stability and PAC-Bayesian together is that it only needs to verify the stability for the prior distribution $\\mathbb{P}$. Indeed, we only need to study stability for the prior distribution, and then use the idea of PAC-Bayesian analysis to transfer this result to any posterior distribution. Therefore, we choose the simple uniform distribution as the prior and check whether SGD and RCD satisfy Assumption 1 (measured under the prior distribution). We will clarify this in the revised version.\n\n\n[R1] P. Zhao and T. Zhang. Stochastic Optimization with Importance Sampling, ICML, 2015.\n\n[R2] M. Perez-Ortiz, O. Rivasplata, J. Shawe-Taylor, and C. Szepesvari. Tighter risk certificates for neural networks, Journal of Machine Learning Research, 2021.\n\n[R3] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprint arXiv:1703.11008, 2017."}]

Author rebuttal:

Meta-review: The work is a rigorous contribution to the PAC-Bayesian analysis of randomized learning algorithms. The clever introduction of a "sub-exponential assumption on the stability parameter" allows for an improvement in the previous result of London (2017). Other researchers might subsequently build on this rigorous analysis to further improve theoretical guarantees and "self-certified" learning algorithms.

The reviewers ask for many clarifications and provide suggestions during the discussion period. It is important that the authors incorporate these in the camera-ready of the paper.
Decision: Accept (poster)