Sharper Bounds for Uniformly Stable Algorithms with Stationary Mixing Process
Authors: Shi Fu
Yunwen Lei
Qiong Cao
Xinmei Tian
Dacheng Tao
Venue: ICLR 2023 poster (2023)
Keywords: Algorithmic Stability
Non-I.I.D. Learning
Generalization Error
Learning Theory

Abstract:   Generalization analysis of learning algorithms often builds on a critical assumption that training examples are independently and identically distributed, which is often violated in practical problems such as time series prediction. In this paper, we use algorithmic stability to study the generalization performance of learning algorithms with $\psi$-mixing data, where the dependency between observations weakens over time. We show uniformly stable algorithms guarantee high-probability generalization bounds of the order $O(1/\sqrt{n})$ (within a logarithmic factor), where $n$ is the sample size. We apply our general result to specific algorithms including regularization schemes, stochastic gradient descent and localized iterative regularization, and develop excess population risk bounds for learning with $\psi$-mixing data. Our analysis builds on a novel moment bound for weakly-dependent random variables on a $\varphi$-mixing sequence and a novel error decomposition of generalization error.

Published as a conference paper at ICLR 2023
SHARPER BOUNDS FOR UNIFORMLY STABLE ALGO- RITHMS WITH STATIONARY MIXING PROCESSES
Shi Fu' Yunwen L Qiong C Xinmei Tian'
Dacheng T
1 University of Science and Technology of China, Hefei, China
2 DDepartment of Mathematics, Hong Kong Baptist University, Hong Kong, China
3 JD Explore Academy, JD.com, Beijing, China
*School of Computer Science, University of Sydney, Sydney, Australia
ABSTRACT
Generalization analysis of learning algorithms often builds on critical assumption that training examples are independently and identically distributed, which is often violated in practical problems such as time series prediction. In this paper, we use algorithmic stability to study the generalization performance of learning algorithms with e--mixing data, where the dependency between observations weakens over time. We show uniformly stable algorithms guarantee high-probabillty generaliza- tion bounds of the order O(1 (T) (within a logarithmic factor), where n is the sample size. We apply our general result to specific algorithms including regular- ization schemes, stochastic gradient descent and localized iterative regularization, and develop excess population risk bounds for learning with ei-mixing data. Our analysis builds on novel moment bound for weakly-dependent random variables on a j--mixing sequence and novel error decomposition of generalization error.
INTRODUCTION
Generalization gap refers to the discrepancy between training and testing, which a quantity of central importance in statistical learning theory (SLT) (Shalev-Shwartz & Ben-David 2014). A
popular approach to controlling the generalization gap is to bound it by the uniform convergence
between training and testing errors over a function space (Bartlett & Mendelson 2002). which
leads to bounds depending on the complexity of function spaces, such as VC dimension (Vapnik) 2013), covering number (Cucker & Zhou 2007) and Rademacher complexity (Bartlett & Mendelson
2002). These complexity-based bounds do not exploit the property of a learning algorithm and
would generally admit a square-root dependency on the dimension (Feldman 2016). which are not favorable for large-scale problems. To incorporate the property of a learning algorithm and remove the dependency on dimension, concept of algorithmic stability has been introduced into SLT (Bousquet& & Elisseeff 2002). Intuitively speaking, algorithmic stability measures how a small perturbation of the training dataset would affect the output model of learning algorithm, which has close connection to several key properties such as learnability (Shalev-Shwartz et al. 2010). robustness and privacy (Bassily et al. 2020).
Recent research has witnessed an increasing interest in leveraging stability to study the generalization behavior of various algorithms, such as stochastic gradient descent (Hardt et al., 2016), structured prediction (London et al., 2016), meta learning (Maurer 2005) and transfer learning (Kuzborskij) & Lampert 2018). Most of these discussions are based on a critical assumption that the training examples are independently and identically distributed (i.i.d.). This assumption is often violated in practical applications. For example, the i.i.d. assumption is too restrictive in time series pre- diction [Vidyasagar 2013). The prices of the same stock different days may have temporal dependence. These phenomena motivate several analyses to derive meaningful bounds for learning problems with observations drawn from non-i.i.d. process (Yu 1994 Vidyasagar 2013).
A widely used relaxation of the i.i.d. assumption is to assume the observations are drawn from
mixing process Yu 1994 Meir
2000 Lozano et al. 2005 Vidyasagar 2013), where the dependency
"The work was done when Shi Fu an intern JD Explore Academy Corresponning authors

---

Published as a conference paper at ICLR 2023
between two observations is quantified by mixing coefficient as function of the discrepancy of the associated two indices. These mixing coefficients decay either as polynomial function or exponential function of the discrepancy (Vidyasagar 2013). Several mixing processes have been introduced into the literature, including the (3-mixing, g--mixing and z--mixing processes YYu 1994 Meir 2000, Lozano et al., (005). Within this formulation, various generalization bounds have been developed to show how the dependency among observations would affect the learning process. Interestingly, these discussions imply a concept called "effective size" which plays a similar role of the sample size in the i..dd scenario Yu 1994, Kuznetsov & Mohri 2017).
As in the i.i.d. case, most generalization analyses in the non-i.i.d. case focus on complexity-basee bounds (Meir) 2000, Yu 1994; Kuznetsov & Mohri (017). There are few stability analyses of learning algorithms
the non-i.i.d. cases. An exception the work in Mohri Rostamizadeh (2010), which, to our knowledge, gives the first systematic analysis on the stability and generalization in non-i.i.d. case. The authors developed high-probability generalization bounds for learning with stationary e--mixig and 9-mixing sequences, which are then applied to general kernel regularization- based bounds. Due to the agorrthm--ppccffe nature, these bounds are preferable to complexity-based bounds if the associated hypothesis space has very large complexity.
However, the stability analysis (Mohri & Rostamizadehi 2010) only implics sub-optimal general- ization bounds. Indeed, for 3-uniformly stable algorithms, the high-probability bounds in Mohri & Rostamizadehi (2010) are of the order of O(vn, + A VT). where n is the sample size and A. term depending on the decay rate of mixing coefficients. For learning with X-strongly convex problems, the uniform stability parameter is of the order O ((1/(nA)) (Bousquet& & Elisseeff 2002) and therefore the bounds in Mohri & Rostamizadeh (2010) become OTT[(ynA) + A./ Vn.. A & Ben-David, (214)) and then the bounds further become O + An/Vn), which cannot imply the optimal bounds O(1/vz) even if A, = 0(1) For learning with i..d. data, recent breakthroughs (Feldman Vondrak (2019] Bousquet al. 2020) in stability analysis show that B-uniformly stable algorithms enjoy generalization bounds develop generalization bounds of the order ((1/vn) for uniformly stable algorithms applied to mixing process?
typical choice of À is X RJ n for a > 0
of the order ((1/vn This motivates natural question:
This paper provides an affirmative answer to the above question. Our contributions are listed below.
We develop a moment bound for weakly dependent random variables defined on a ip-mixing sequence. We show our bound matches the existing moment bounds for i.i.d. random variables up to a logarithmic factor. As a byproduct, we develop a Marcinkeewiez-yygmudd inequality for a s--mixin sequence, which may be interesting in its own right.
2. We develop high-probaten probability bounds of order Ö(L/vn for uniformly stable algorithms for learning with t (--mixing sequences (our results actually require assumptions on yp -mixing coefficients which weaker than assumptions on ti-mxiig coefficients). We achieve this by introducing a different and mean-zero random
decomposition of generalization errors to make sure we get variables, which is more challenging than the i.i.d. case. Our results recover the existing bounds within a constant factor in the i.i.d. case.
3. We apply our general bound some specific algorithms to show the effectiveness of our results, including kernel regularization schemes, stochastic gradient descent (SGD) and iterative localization.
The paper is organized as follows. We present the related work in Section We develop concentration incqualities for e-mixing data in Section aand present general stability- bounds in Section 4 We apply our general result to specific algorithms in Section [5] We conclude the paper in Section 6
2 RELATED WORK
In this section, we discuss the related work. We first discuss the related work on algorithmic stability and then the related work on learning with dependent data.
Algorithmic stability. Algorithmic stability measures how the replacement/nemoval of a single (or a few) example would affect the output model, which is an important concept in SLT (Bousquet & Elisseeff 2002). A nice property of algorithmic stability is that it only considers the behavior of the
"We use Ô to hide logarithmic factors
2

---

Published as a conference paper at ICLR 2023
output model and therefore can imply sppacit-iiddeeendett generalization bounds. An important stability measure called uniform stability was introduced in an influential work (Bousquet & Elisseeff 2002), which was used to study the generalization behavior of regularization schemes. This uniform stability was extended to the setting of randomized algorithms (Hlisseeff et al. 2005), which was further used to study the generalization guarantee of SGD (Hardt et al. 2016). To better exploit the training examples for better generalization bounds, a relaxation of uniform stability called on-average stability has been introduced (Shalev-Shwartz et al., 2010). In particular, the on-average stability was shown to be equivalent to learnability (Shalev- SSwarrzz et al.] 2010) and was used to derive data-dependent error bounds (Kuzborskij & Lampent 2018 Lei & Ying 2020 Zhou et al. 202T Li et al. 2020, Nikolakakis et 2022). The smoothness assumption for stability analysis of SGD was removed in the papers (Lei Ying 2020; [Bassily et al., 2020). For nonconvex problems, stability and generalization of learning algorithms that converge to global optima were studied for gradient-dominated problems (Charles & Papailiopoulos 2018 Lei & Ying 202T). While most discussions focus on upper bounds on the stability, recent work also develops lower bounds on the stability of SGD (Bassily et al., 2020 Amir et al.] [022]. While most stability analyses imply optimal bounds in expectation, the recent study shows that uniform stability
imply almost optimal bounds with high probability (Feldman & Vondrak 2019; [oouquet et al., 2020; Klochkov & Zhivotovskiy
202T Yuan & Li 2022 Li & Liu| 2022). Algorithmic stability has found wide applications in various learning problems, including transfer learning (Kuzborskij & Lampert 2018). meta- meta-learming (Maurer 2005). structured prediction (London et al. 2016), hyperparameter optimization (Bao al. [021)
neural networks (Richards & Kuzborskij] 2021) and adversarial training (Xing et al. 2021).
Learning with dependent data. For learning with dependent data, one generally assumes that the data are drawn from stationary and mixing sequences with the dependence between observations diminishing appropriately over time (Doukhan 1994| |Smale& & Zhou] (209).. Initially, generalization
bounds were established via a uniform convergence approach based on complexity measures of function classes, such as VC dimension Yuu 1994), covering numbers (Meir) 2000) and Rademacher complexity (Mohri & Rostamizadeh 2008). Based on a localization idea and self bounding loss
functions, Steinwart & Christmann (2009) developed fast learning rates for regularized algorithms with geometrically a-mixing data. Ralaivola et al.] (20TO) and Alluier et al. (2013) established
convergence rates under the assumption of stationary and weak dependence. While most discussions focus on stationary sequence, Kuznetsov & Mohri (2017) used Rademacher complexity to study learning bounds with non-stationary ş-mixing and 3-mixing sequences. The first stability analysis of learning with mixing sequences was given in the paper (Mohri & Rostamizadeh 2010). The stability approach also used to study online learning with dependent data (Agarwal & Duchi 2013) and
learning with graph-dependent data (Zhang et al. 2019). SGD with Markov sampling has also been recently studied (Sun et al. 2018 Wang et 2022).
3 CONCENTRATION INEQUALITIES FOR -MXIING SEQUENCES
We consider learning problems with a sequence of dependent observations. We assume the depen- dency between observations decays with their gap. There several concepts to quantify the de- pendency relationship within a stationary sequence such as 3-mixing, --mmxxig and ti-mixing (Mohri & Rostamizadeh 2010 Yu 1994). We focus on the --mixxng and vi-mixing sequences in this paper. Let Z [Z, -= do be a stationary sequence of random variables. For any i.j e N, let of denote the alaggerra generated by the random variables Za i < k S j.
Definition 1 (e--Mixing Sequence). For any k E N. the ---mixigg coefficient of Z is defined as sup
<(k)= n.A.
|Pr(A| - Pr(A))
Z is said be mp-mixing if (kk) + 0 as k 2o. It is said to be algebraically ---mixing (with degree r >> 0) if there exists a real number Po > 0 such that (k) I 4o//k" for all k, exponentially mixing (with degree r) if there exist real numbers yo, 1 such that sp(k) S so exp(-ppkk)) for all k. Definition (gi-Mixing Sequence (Bradley 2007)). For any l E N. the t--mixing coefficient of the
stochastic process Z is defined as (bk)
sup n. n+4 BE
Z is said to be mimixng if (A+) - 0 as k 0o. It is said to be algebraically simixing (with degree r > 0) if there exists a real number t/ > 0 such that (k) I wo/k for all k, exponentially mixing (with degree r) if there exist real numbers tho 4/1 such that (k) S v/o exp((1/kk for all k.
3

---

Published as a conference paper at ICLR 2023
We will use mi-mixig give bound on the stability analysis version of y' e'-mixing in Lemma 3. Intuitively speaking, ((k)) and (k) measure the dependency of an event on those happened units of time ahead. By the definition, we know that dl-mixing is stronger than the p-mixing. Below we provide examples of ço-mixing and mi-mixing sequences in Kesten & O'Brien 1976).
We first consider random variables V,, Un and Sn for (2. P), which are independent of each other and have the following distributions: for all n E Z, P(V, n i) Bi, i 0, 1 and 0 Bo < 30 + B1 1; P(U,, k) - pt 2 0, 0, 1, and
Z defined the probability space
Ex=o Pk- = 1; P(S,- - j] - 75. J = 0, 1, 2 and 0 < 70 < 70 + 71 < 70 + =
Example (Example of g-mixing sequence), Let {fr. k 2 1] be a non-increasing sequence such that fi S 1, fx + as k + oe and 2 log(11 - [(+1) 2 log(1 ft] + log(1 - fk+2) for (k: ʃa < 1}.
For any 0 < e < 2 we define 8 = e, B1 = 1 - e. Define {pm) 3 by
Σ k=0
n-1
(1 - fn) (1 f
if fn < if fn 1.
Pk
0
Note that pt = (1 - (1-
fx) fk+1) 11 2 for {k : fu < 1] since
2 logg(1 - fk+1) 2 log(1 - fa) + log(1 - 2242). Xnt = Un + 1 Vn + W., where Wn, = Vn-Un.
Then (X., n E }) is a y-mixing sequence with (1 - f S {k() S Sk.
Next we provide an example of t-mixing sequence.
Example 2 (Example of vi-mixing sequence). Let {gk, k > 13 be a sequence such that gi 92 < 9k + 9k+2. k = 1,2, ... For any E (0, 1), Let 72 = e,
9: + 0 as k + 0o and 2g
To 7/ (1 e), Bu 51
_. Define {pm} by
2.
Po = 0, Pk = gk 29k+1 + 9k+2, 1,,2, 1.2.....
Note that pk 2 0 for k = 0, 1, 1,... Let Un, Vn and Sn, be as before. Let Zn = Spllss or 1] +
Vn- (h.-..[ss.-2 where is the indicator function. Finally we define X,, = Vn + 2Zn. Then (Xn,, n E
}} is d-mmiiig sequence with c(1 + +) e)''g gb S (k)) I exp [e(1 -e) - gk - 1.
To develop error bounds for learning with çe-mixing sequences, we first develop concentration inequalities for j--mxxig sequences. In the following theorem to be proved in Section [ we derive tail bound for the summation of dependent random variables in terms of the tail behavior of each individual random variable. Let A,,
2 Ex= (kk). The Ly-norm of a real-valued random variable Z is denoted by /|2ppp == (E])ZT") $, .p21. 1.
Theorem 1. Let X1.... Xn, be a finite contiguous subsequence from a s--mixing sequence. Let Z, be a function of X; with B[Z,] = 0 and [ > 2) s 2 2xxp(=22 Then for any 2 we have
Z < (9 + log(n))pAn, 2nb.
Remark 1. Theorem ji an extension of Mareinkiewiez-Zyggmue inequality for independent random variables to ş--mixing sequences. Indeed, if Z, are i.i.d., it was shown Σ Zellp O(pvnb) (Ren & Liang 200T). We show how the mixing behavior would affect the concentration by including A, in our bound. In particular, if Z; independent then A,, 1 and in this case, our result inequality up to a logarithmic factor. Note A, = (1) for algebraical e-mixing with and exponential -p-mixing sequences (Mohri & Rostamizadeh 2010).
matches the Marcinkiewicz-Zyggma
Under the assumption Σx= so (k) < co, it was shown
Σ Z, S C. (C
(EL 12 Xuejun et al. 2010 This bound requires an assumption involving Σ go (k).
which is larger than Σk= (ok) in A. since &à (k) 2 <(k). For example, if (p(k) Ok--)) then
Ek=1 (kk) = Olog n) while >i= &p (k) = O(y)). Moreover, the bound in Xuejun et al. 2010) involves Cp which is not explicitly stated. As comparison, our bound involves all explicit constants.
Remark 2. Our basic idea to prove Theorem is to apply McDiarmid inequality (Lemma A.I to
Lipschitz function defined on a ---mixing sequence. If we define ('(X,..... ...).....)..__......... = "n= Z, one cannot guarantee the Lipschitz continuity of & due the unboundedness of Z,. Our novelty is to
4

---

Published as a conference paper at ICLR 2023
define Z, = Z, where [[j is indicator function and ( The boundedness of Zi implies the (2c)-Lipschitz continuity of and therefore we can apply the McDiarmid inequality study its decay rate of Q. Furthermore, the assumption Pr[IZ; E} S 2 exp((===/0 shows that and 4 are equal with a high probability. We then combine these two observations together to derive a high-probability bound for Φ', which further leads bound the Ly-norm of &' by the equivalence between high-probability bound and the Ly norm bound.
Based on Theorem T we develop a moment bound for Lipschitz functions (W.r.. the Hamming distance) defined mixing sequences. The following theorem is extension of result in the ii.d. case (Bousquet et al. 2020) to the case with mixing sequences. This result plays major role in developing genera lizaionn bounds for learning with mixing sequences. The first assumption is conditional boundedness assumption which is standard for concentration inequalities. The second assumption implies that the 9: is of mean zero conditioned on any fixed [n]. which is stronger than E[g:] 0 since the conditional expectation holds for any fixed [m]])[]- The last assumption implies that gi is insensitive to the change of any single example, which implies that 9s is concentrated around its expectation by McDiarmid's inequality. Our proof follows from the framework in Bousquet et al. (2020), which is given in Section B
Theorem 2 (Concentration Inequality for u--Mixing Sequence). Let 7 ., Ze be a finite contiguous subsequence from sp-mixing sequence. Denote 7 = 171.... } Let 01 a In be some functions 9: : Z" + I such that the following holds for any E [n]]
Exiaat [g. 2:1l S M almost surely,
Ez, (o: Z Ma) a.s.,
gi 3-Lipschitz w.r.t the Hamming distance.
Then for any 2 1 we have (k = =logg n
n
k-1
S 3MA, V 2pn 2*
_ (9 1)
g:
Remark 3. If the sequence is i.i.d., the following bound was developed (Bousquet et al. 2020)
Σ
gi
3M + 12v6pn3 log, n.
(3.1)
Our bound recovers the existing result in the i.i.d. case. Note A, for any n and then Theorem P
implies Σn 9: I 3M /2m (p logg [n] which matches Eq. 3.1 up to logarithmic
factor. This is the first extension of the result in Bousquet al. (2020) to e-mixing setting.
We follow the framework in Bousquet et al. 2020)) to prove Theorem 2 The difference is to replace the Marcinkiewicz--yygmmni inequality for i.i.d. random variables by Theorem for sp-mixing random
variables. The basic idea to use the representation Σn= 9: Σ Elg. Z EE Σ (g)
), where gi is the expectation of conditioned on some random variables and l is an integer depending on n.. We then use a McDiarmid inequality and the conditional boundedness of Efg, [2] to control Σn [y), and use Theorem |
to control Ek=1 Ei= (gl - -)
STABILITY AND GENERALIZATION
Let Z = X ) be sample space, where X' C IRd is input space and y is an output space. We consider supervised learning problems where 5 = {. 2n
= {x1, ,/),..., (In, yn)) is contiguous subsequence from mi-mixing sequence. Based on S, wish to find model h X + V We consider parametric models where the model is determined by a parameter w in a parameter space W. The performance of model on single example can be measured by loss function f(w 2). The empirical risk and population risk are then defined by
1 n
Fs(w)
n Σ
f(w; 2:) and F(w) = E. [f[s(w;: 2)],
(4.1)
5

---

Published as a conference paper at ICLR 2023
which measure the behavior of w training examples and test examples, respectively. Here the test point 2 is assumed to be dependent on S (i.e., 2 is assumed to follow immediately after the sample S). which is the most realistic setting considered in Mohri & Rostamizadeh (2010). We refer to the discrepancy between training and testing as the generalization gap F F(w) (ww In machine learning, we often apply an algorithm get model with small training error. Meanwhile, we wish the output model also admits a small generalization gap to enjoy good generalization to test data. In this paper, we are interested in developing generalization error bounds that decay zero as the sample size goes to infinity. Our basic tool is the algorithmic stability, which measures the sensitivity of the output up to the perturbation of single example. Various concepts of stability have been introduced in the literature. In this paper, we focus on the uniform stability which is arguably the most widely used algorithmic stability. We use Ws to mean the output model we apply an algorithm A to the dataset S. Note we omit the dependency of the notation on A, which should be clear from the context. We say two sets are neighboring datasets if they differ by one example.
Definition 3 (Uniform Stability (Bousquet & Elisseeff 2002)). A randomized algorithm A is uniformly stable if for all neighboring datasets S, 5 E 2 we have sup=
S e.
Our stability analysis requires different mixing coefficient defined follows
(1k))
sup
[Pr(znIA B) - Pr(zz)/-
(4.2)
n,AEo" xe ..,, Eag BEo
is clear that ('(k) 2 (kk). The following lemma controls (k()) in terms of the t--mixig coefficients. According to the following lemma, one can show that if (k) = O(k then (k)
O(k-)). If (1:) = O(exp( k²))")) then s'(k) = ((ex((-0/)
Lemma 3. Lei Z = [2,) be drawn from ti-mixing distribution and assume (kk) < 1. Then
x max {
(1 + (xa)) 1- (k)
1, (1 (1)))
1 + (A)
To apply Theorem to learning with mixing sequences, we need to introduce sequence of functions
Ii satisfying the conditions in Theorem 2 and relate them to the generalization gap. Let 2/ (resp. z(") be drawn from the same distribution of 2;, i.e., the conditional distribution of 2/ (resp. 2(")
given 21...,, 74 :i.,...., Zn is the same as that of z; given E1,..., 2; Zi+11.... Zn. Let S.. {z1,...; Zi b- 1, Ri, Zi4841, hn i.e., we remove 26 points around z4. For any i E [n)] 1- 1, 2/1 2itb
let Sh.6 (21,....
b.. We then define the following random variables
9, = E E [f( 2/)] s: =:]] Vi E [m].
(4.3)
The following lemma to be proved in Section C givee generalization bounds in terms of stability and Ex= 9r- We will use sf (b) in Theorem 5 and all corollaries in Section 5. The underlying reason is that we need to remove 2b points around to get Si,, for the application of Theorem 2 An upper bound [F(ws) - -E (
requires to use (b(b).
Lemma 4. Let S be drawn from a mimixing distribution. Let b E {O.....n) denote the number of last points removed in S, i.e., S. = {21,..., Zn-b). Let ws denote the hypothesis trained on S. If the algorithm A is B-uniformly stable and the loss function is bounded by M > O, then the following inequality holds with 9i defined in Eq. 4.3)
22
|n(((ws)- - -Fs(ws)) s (36 + 1)8 + +M)(((()) + (b6) +
Σ 9
We can apply Theorem 2 to control the term Σi= Ii and derive the following generalization bounds
in terms of mixing coefficients
Theorem 5 (General Mixing Stability Bound). Let ws denote the hypothesis returned by a B- uniformly stable algorithm trained on a sample S drawn from a ti-mixing stationary distribution. Let M denote the uniform bound of the loss function. Then for any b E (0....,n} and any 8 E (0, 1), the following inequality holds with probability at least 1- (k [log, m))
[(ws)) Fs(ws)) s <2(3b 1)33 + M(((b) + ((b))
2 (og(og/))/)))) 2l0g(e/8)
k-1
+ 3eMM,,
+
Σ 1=0
(9 + 1)43.
n
6

---

Published as a conference paper at ICLR 2023
Remark 4. For co-mixing sequences, the following probabiibyii bounds were developed (Mohri & Rostamizadeh, 2010)
F(ws) P's (ws)) - (Vooo (ii)
- =n
(4.4)
As comparison, our generalization bound in Theorem 5
becomes
[F(w)) Fs((s))))
0 (('(b) + An Vn + 3(b+ + A log" log((1/))) (4.5)
log(1/6)
Eq. 4.5) improves Eq. (4.4) as follows: (1) we replace /nip(b) with (b);; (2) we replace VnbbA,
with 8(b + A log" n). The above two terms save a factor of n. Meanwhile it should be also mentioned that our bounds involve ş², while the bounds in Mohri & Rostamizadeh (2010) involve
3. We now compare these two bounds under assumptions of op in three cases (results in Mohri & Rostamizadeh 2010) hold for çe-mixing coefficients and also hold for p'-mixing coefficients).
3 n log( log(1/))), which matches existing stability-based bounds (Bousquet et al. 2020) up to logarithmic factor. As a comparison, Eq. becomes F(ws) (s( O log (1g5()
In the i.i.d. case, 44. becomes ((ws) (ws) O(y n log (g/((L//) 1/0)
1,3 (5 1/vn)).
2. We now consider al algebraically mixing sequences, i... (k()) S Pok with > 1. In this case, know A,, (1) (Mohri & Rostamizadehi 2010). If we choose b bx -ー in Eq. 445) we get 3b x b-d f-1x and therefore (we denote = there are absolute constants e and Cg such that 0 < B B.)
F(ws)) - Fs(ws)) = + v log(10) + + logg n log(1/6))
(4.6)
As comparison, the optimal choice b = 9 मो. in Eq.
4.4 4.4
implies
IF(ws) Fs(ws)] 0 Tog( 1
3 +n + #))
(4.7)
It is clear our bound replaces र in Eq. 4.7 by उ + Blog" log 18). which is smaller.
3. Finally, we consider exponential mixing sequences, i..., (k) < 90 exp -1 p2kkk)) k"). which imply
A. =11).. If we fix b [log* (1/3)1, we know exp(- < 63 = 0(3 log (1/8)) and
(FWs)) Fs(ws) O
V nn-nnn Vnnnnnoo(11 log(1/5) Blog* n log(1/8) 6) + 3 log (1/B)).
(4.8)
As a comparison, Eq. (4.4) implies |Fww)) - Fs( (ws) = (Vlog(( (1))(1/))( ()) VnB log (1/3) vn. 1/vz)). It is clear that our analysis removes a factor of v in front of the stability parameter B.
Remark 5. The analysis in the mixing case is more challenging than that in the i.i.d. case. The analysis in Boussuet al. (2020) introduces 9. E. f [[W 2() f(wg( where is independently drawn from the stationary distribution and St {21, {=1...., -: 2/. 2i+1,..., 2.)) While Ez, [o.] = 0 in the i.i.d. case, we cannot guarantee Ex, [ = 0 in the mixing case due to the dependency between 24 and 2, (j き i). In this way, one cannot apply Theorem 2 to 9, in the mixing case. We use much more complicated decomposition of the generalization error in terms of gi in Eq. (4.3), which of mean zero in the mixing case. In this process, we introduce concepts such as Sib. S% to fully exploit the stability and mixing property. It should be mentioned that S,,,, St have been introduced in Mohri & Rostamizadehi (2010). However, the aim is different. These concepts are used in Mohri & Rostamizadeh (2010) to get bounds in expectation for &(S) = F(ws) g) (s(ws) via a lemma in Yu (1994) for 3-mixing sequence, where the concentration of ((S) around its expectation can be directly studied via the McDiarmid inequality for e--mixing sequence. As a comparison, our aim is to replace the sequence 9 = E.y.,, [f z) f fW x]] (with non-zero conditional mean) by the sequence Ji in Eq. (4.3) with zero conditional mean, which is then controlled by our new concentration inequality for -o-mixing sequences (Theorem 2).
APPLICATIONS
We now present applications of Theorem 5 to several algorithms, including the kernel regularization algorithm, SGD and localized iterative regularization. Let A be an algorithm which outputs a model (S) after observing the dataset S. We are interested in the excess population risk of model
7

---

Published as a conference paper at ICLR 2023
A(S) defined by F(A(S)) F(w"). which measures the performance of the output model A(S) as compared to the best model w arg min F F(w). An efficient approach to this aim is based on the following error dccomposition [Bousquet & Bottou 2008)
F(A(S)) - F(w") F(A(S)) Fs(A(S)) Fs(A(S)) - Fs(w") F=(s"s)w F(w"), (5.1)
where we refer to F(A(S)) Fs(A(S)) as the generalization gap and (s(A(S)) Fs(w") as the optimization error. The last term (ww We will apply stability analysis to control the generalization gap, and tools in optimization theory to control the optimization error. To this aim, we give some necessary definitions. The Lipschitz condition means the gradient is bounded, and the smoothness means the gradient is Lipschitz continuous. Examples of Lipschitz loss functions include the hinge loss, logistic loss and absolute loss. Examples of Lipschitz and smooth loss functions include the logistic loss and Huber loss.
) - F(w") " is easy to control since w" is independent of
Definition& 4 (Lipschitz, smoothness and convexity). Let y > 0 and 2 O. Let f W x 2 + IR
We say f is L-Lipschitz continuous if [f(w; f(w': =)] - -|| - w'll for any w, w',
We say I is y-smooth if [V](w;=) - ([(' - 7// -- w/ll for any w, w', 2.
We say f' is g-strongly convex if =(w::)=/(w< for any w, w', We say f' is convex if it is u-stronggy convex with μ 0.
v/(w':=)) 2 -lww-w1l
5.1 KERNEL REGULARIZATION SCHEMES
We first consider kernel regularization schemes with convex and Lipschitz loss functions. Let K : X x X' + R be a Mercer kernel (i.e., is symmetric and positive definite) and W be the associated reproducing kernel Hilbert space with the norm || ||.. We consider the following model
W S,A = arg min {Fs(w) + 11 WEW
(5.2)
where À >> 0 is regularization parameter to tradeoff the data-fitting term F's and the regularizer [[w]] IIk The following corollary gives high- probabbbbyyyl excess population risk bounds on kernel regularization. The proof is given in Section D.I
(.2) when trained on a sample S drawn from ii-mixing stationary distribution. Assume f is convex, L-Lipschitz and bounded by M > O. Then, with probability at least 1 - 5, the following excess risk bound holds (k: = [log2 n
Corollary 6. Let w.,x denote the hypothesis returned by Eq.
F(WS.A) - F(w")= = -0(
An Lon' log (1/8)
b
Ei= IA 1og(1/6) nd
+b)(() n
A||ww" l
Vn
Remark 6. We now instantiate the above bounds under special mixing sequences. We first consider the algebraically mixing sequence, i.e., (kk(k) S pok with r > In this case, analysis similar to Remark 4 implies the following bound with an appropriate choice of b
F(ws,)) - F(w") o (n log (1/8) + (nA) मं. + log" 1og(1/8) + >/|
nd
If ||w" ||x O()), then we choose A = 1/ and get
((Wsx))F(ww)) 0(1 log (1/8) + スलना log" n log(1/6))
We now consider the exponential mixing case, i.e., (k(k) S exp (-p)k²). In this case, analysis similar to Remark implies
F(ws) - Fs( (ws)) log
log" log (n)) log (n)) + +N/lw* 1
If //w || (1). then we can choose X = t/ derive
[F(ws) - Fs(ws)) = 0(" 1 (Vlog(1/8) + log" n (og(1/)) log (n)))
5.2 STOCHASTIC GRADIENT DESCENT
We apply our generalization bounds to SGD with convex and smooth loss functions, which has wide applications in training complex models in the big-data due to its simplicity and efficiency.
8

---

Published as a conference paper at ICLR 2023
Definition 5 (Stochastic Gradient Descent). Let wi 0 R be initial point and (ne be a sequence of positive step sizes. SGD updates models by W = w; Th f(w: 2,), where f(W,,, 2;,) denotes gradient of f w.r.t the first argument and & is independently drawn from the uniform distribution over [x] ..).
We assume the algorithm produces Wg = 7 E.= w,, which is an average of SGD iterates. We first present the generalization error bounds. The proofs are given in Section D.2
Corollary 7 (Generalization bound). Assume that the loss function f(;22) is y-smooth, convex, I--iipchitzz and bounded by M > 0 for every 2. Suppose that we run SGD with step sizes qe I min(2/7, n) for T steps sample S drawn from th-mixing stationary distribution. Then, with probability al least 1 we have (k [log2 n))
k-1
108(1/0)
F(ws) - Fs(ws) = (nblog((1/)) +1
Σ 1 log (1/8)+ + An
1=0
As a corollary, we develop the following excess risk bounds. Corollary 8 (Excess risk bound). Assume that the loss function (1; is 7-smooth, convex, L.- Lipschitz and bounded by M >> for every z. Suppose that we run SGD with step sizes the = 1) X 1/vT for T x n steps on a sample S drawn from a th-mixing stationary distribution. Then, with probability least 8 we have (k- loggn]
k-1 I4 log (16))MM)))) An log (n/0)
F(ws)-F(w")) bo=bblo(116614)
vn
5.3 ITERATIVE LOCALIZED ALGORITHM
We now turn to convex and non-smooth problems. this case, SGD requires very small step size to enjoy good stability, which however would affect the optimization process. Indeed, tradeoff between generalization and optimization requires running SGD with O(n²) iterations, which not computationally efficient (Lei & Ying 2020 Bassily et al.. 2020). To speed up the algorithm, we consider an iterative localization scheme (Algorithm) iss deferred to Section D.3). which was introduced in Feldman al. (2020). The basic idea of Algorithm iis to implement the optimization in epochs. At each epoch, Algorithm Soaihhmmuuulll builds an objective function with a regularizer depending on the output of the previous epoch, which is solved by SGD with T, iterations and learning rates (m))
The following corollary gives error bounds for Algorithm [ The proof is given in Section D.3
Corollary 9. Assume that the loss function 2(;;2) is convex, L--Lipschizz and bounded by M > 0 for every 2. We run Algorithm [ on sample St, i E [m]] drawn from a th-mixing stationary distribution. If we choose n then, with probability at least 1 -
O nn= log nAn log (n/5)+bn +M log nup' (b)+n
Σ IA log (ng))
I=0
where k = [loge 12). Moreover, Algorithm requires only O(n lo gradient computations to achieve this generalization bound.
CONCLUSIONS
With high probability, we develop the first stability- generalization bounds of the order Õ(1/ Vn) for learning with mixing sequence. We apply our results to several specific algorithms such as regularization schemes, SGD and localized iterative regularization. Our analysis relies on new moment bound for weakly-dependent random variables defined mixing sequence.
Our generalization bounds involve s' s'-mixing coefficients, which are larger than the s--mixing coefficients. It would be very interesting to investigate whether these o'-mixing coefficients can be replaced by ip-mixing coefficients. We guess p'-mixing would be more similar to ç-mixing than qi-mixing since both ip- and y coeefffices measure the difference between conditional probability and a probability (i.e., of the form [Pr(A Pr(A)) ). As comparison, gi-mixing considers the difference between and the ratio of probabilities (i.e. of the form 1 Pr(A B))Pr(()Pr(BB))

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work is supported by the Major Science and Technology Innovation 2030 "New Generation Artificial Intelligence" key project (No. 2021ZD0111700 NSFC No. 62222117 and National Social Science Found of China "Research on Virtual Reality Media Narrative " (Grant No. &ZD326), The work was done when Yunwen Lei was at the School of Computer Science, University of Birmingham.
REFERENCES
Alekh Agarwal and John C. Duchi. The generalization ability of online algorithms for dependent data. IEEE Trunsactions on Information Theory, 59(1)553-5887 2013.
Pierre Alquier, Xiaoyin Li, and Olivier Wintenberger. Prediction of time series by statistical learning: general losses and fast rates. Dependence Modeling, 1:65-93, 2013.
Idan Amir, Tomer Koren, and Roi Livni. Sgd generalizes better than gd (and regularization doesn't tt help). Conference on Learning Theory, pp. 63-92. PMLR, 2021.
Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. Advances in Neural Information Processing Systems, 34, 2021.
Peter Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses, Advances in Neural Information Processing Systems, 33, 2020.
Olivier Bousquet and Léon Bottou. The tradeoffs of large scale learning. In Advances in Neural Information Processing Systems, pp. 161-168, 2008.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy, Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626, 2020.
Richard C Bradley. Introduction strong mixing conditions. Kendrick press, 2007.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that
converge to global optima. In International Conference Machine Learning, pp. 744-753, 2018.
Felipe Cucker and Ding-Xuan Zhou. Learning Theory: Approximation Theory Viewpoint. Cam- bridge University Press, 2007.
P. Doukhan. Mixing: Properties and examples. Lecture notes in statistics. New York: Springer, 1994.
Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. In Advances Neural Information Processing Systems, pp. 3576-3584, 2016.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference Learning Theory, pp. 1270-1279, 2019.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439 449, 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
10

---

Published as a conference paper at ICLR 2023
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high-probabille bounds for strongly-convex stochastic gradient descent. arXiv preprint 1eXiv:1909.00800 2019.
Harry Kesten and George L. O'Brien. Examples of mixing sequences. Duke Mathematical Journal, 43:405-415, 1976.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with conver- gence rate O(1/n). In Advances in Neural Information Processing Systems, 2021.
Leonid Aryeh Kontorovich and Kavita Ramanan. Concentration inequalities for dependent random variables via the martingale method. The Annals of Probubility, 36(6):2126-2158, 2008
IIja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning, pp. 2820-2829, 2018.
Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for son-sttaionary mixing processes. Machine Learning, 106(1):93-117, 2017.
Yunwen Lei and Ke Tang. Stochastic composite mirror descent: Optimal bounds with high probabili- ties. In Advance in Neural Information Processing Systems, pp. 1524-1534, 2018.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819, 2020.
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient-dominated objective functions. International Conference on Learning Representations, 2021.
Jian Li, Xuanyuan I Luo, and Mingda Qiao. On generalization enror bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
Shaojie Li and Yong Liu. High probability generalization bounds with fast rates for minimax problems. In International Conference on Learning Representations, 2022.
Ben London, Bert Huang, and Lise Getoor. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1):7808-759, 2016.
Aurélie Lozano, Sanjeev Kulkarni, and Robert Schapire. Convergence and consistency of regularized boosting algorithms with stationary b-mixing observations. Advances in neural information processing systems, 18, 2005.
Andreas Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 6 (Jun):967-994, 2005.
Ron Meir. Nonparametric time series prediction through adaptive model selection. Machine learning, 39:5-34,70 2000.
Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-i.i.d processes. In Advances in Neural Information Processing Systems, volume 21, 2008.
Mehryar Mohri and Afshin Rostamizadeh. Stability bounds for stationary --mmxing and B-mixing processes. Journal of Machine Learning Research, 1 11(2), 2010.
Konstantinos Nikolakakis, Farzin Haddadpour, Amin Karbasi, and Dionysios S Kalogerias. Be- yond lipschitz: Sharp generalization and excess risk bounds for full-batch gd. arXiv preprint arXiv:2204. 12446, 2022.
Liva Ralaivola, Marie Szafranski, and Guillaume Stempfel. Chromatic pac-bayes bounds for non-iid data: Applications to ranking and stationary 3-mixing processes. Journal of Machine Learning Research, 11 11:1927-1956, 2010.
Yao-Feng Ren and Han- Han-Ying Liang. On the best constant in marcinkiewicz prreinkkewicz-zzymuudd inequality. Statistics & probability letters, 53(3):227-233, 2001.

---

Published as a conference paper at ICLR 2023
Dominic Richards and Ilja Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. Advances Neural Information Processing Systems, 34, 2021.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shai Shalev-Shwarzz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11:2635-26700 2010.
Steve Smale and Bhng-Xuan Zhou. Online learning with markov sampling. Analysis and Applications, 7(01):87-113, 2009.
Ingo Steinwart and Andreas Christmann. Fast learning from non-iid observations. In Advances in Neural Information Processing Systems, pp. 1768-1776, 2009.
Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. Advances in Neural Information Processing Systems, 31:9918-9999 2018.
Vladimir Vapnik. The nature of statistical learning theory. Springer, 2013.
Mathukumalli Vidyasagar. Learning and generalisation: with applications to neural networks. Springer Science & Business Media, 2013.
Martin J Wainwright. High-dimensiont statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Puyu Wang, Yunwen Lei, Yiming Ying, and Dung-Xuan Zhou Stability and generalization for markov chain stochastic gradient methods. In Advances in Neural Information Processing Systems, 2022.
Yue Xing, Qifan Song. and Guang Cheng. On the algorithmic stability of adversarial training. Advances in Neural Information Processing Systems, 34, 2021.
Wang Xuejun, Hu Shuhe, Yang Wenzhi, and Shen Yan. On complete convergence for weighted sums of ç--mixing random variables. Journal of Inequalities and Applications, 2010:1-13, 2010.
Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pp. 94-116, 1994.
Xiao-Tong Yuan and Ping Li. Boosting the confidence of generalization for Lz-stable randomized learning algorithms, arXiv preprint arXiv:2206.0388 033834 2022.
Rui Ray Zhang, Xingwu Liu, Yuyi Wang. and Liwei Wang. Mcdiarmid-type inequalities for graph- dependent variables and stability bounds. Advances in Neural Information Processing Systems, 32, 2019.
Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error of SGD in nonconvex optimization. Machine Learning, pp. 1-31, 2021.
A PROOF OF THEOREM
In this section, we prove Theorem ! To this aim, introduce several lemmas. The following lemma is McDiarmid inequality for stable functions defined on mixing sequences (Kontorovich & Ramanan 2008).
Lemma A.1. Let T 2" +
be measurable function that is c-Lipschitz w.r.t. the Hamming distance for some e > O, and let Zi,..., Ln be random variables distributed according a sp-mixing distribution. Then for any > 0 the following inequality holds
Pr (Z Zn) El ZnD1l 2 2c] < exp nT=
-22
Furthermore, any 8 E (0, 1) the following inequality holds with probability at least 1 - 6
| Z1. Zn) - E[4(Z,,.... .n)] cAn /
v2
12

---

Published as a conference paper at ICLR 2023
The following lemma shows the equivalence of tails and moments (Bousquet al. 2020). Lemma A.2. Let Y be a random variable. for any E (0, 1), with probability at least 1 -
Y S avlog(e/0) + blog(e/6),
then for any p it holds that
|||pp S 33pp + 9pb.
|||| S ypa + pb for any p 2 1, then for any (0,1) we have with probability at least 1
Y s e e (a//ool( blog(e/0))
Proof of Theorem 7 Let number to be fixed later and define
Z. Z,1 2, Vi [n]],
where 1H- is the indicator function (1 the argument is true and otherwise). Define ((1,...., X₂) = Ei= Z, First we show the Lipschitz continuity of w.r.t. the Hamming dis- tance. Suppose change X1 by X2 and keep other X,. Define Zi...., Zn similarly to Zi...., Zn but as functions of X X2,,. ......... Xn. Since Zj is a function of X, (i.e., once we know X, we know
Zj), we know Z, Z for all 1. Then
x,,) (X X x = 11 + +... + - -
= 7 S 2c.
According to Lemma A.1 with 2e we derive the following inequality with probability at least 1 - (e 2)
Σ
Z
c 2m (neog(2e/((e 2)8)).
(A.1)
1=1
According the assumption Pr Zz
-E),,, we know with probability at least 2) S eexp( (exp(=E//b))
1 - (6((en)
Z / /llo(en//))
(A.2)
We fix /llogeen/), We now assume that Eq. (A.T) and Eq. (A.2) hold for E [n]. which happen with probability at least 1 - 8. Under this event, we have Z, Z; and (for simplicity we assume n 2 2/(e 2))
72
Σ 2
Σ Z
A. 2nd (óg( logee 2)0)) VnnbA, log(en/6).
The following inequality then holds with probability at least -
Σ Z - 2nbb,, log(n) s lole/nooge//)),
1=1
According to Lemma A.2
for any 2 1 it holds that
Σ 7 VnbA, log(n) s 9pv 2nbAn
f=1
The stated bound follows directly. The proof is completed.
B PROOF OF THEOREM 2
We follow the framework in Bousquet al. (2020) to prove Theorem
Proof of Theorem 2 Without loss of generality, we assume = 2*. Consider sequence of partitions
Bo,... By with Be = (1,2,...,22* ,2,). We then obtain B, from B by splitting each subset in B into two equal parts. In this way, we get
Bo ((1) (2). ... (2 B ((1,2), (3, ()..4)....... ..... (2t 1,2 ... BB {[n])-
13

---

Published as a conference paper at ICLR 2023
For each i E [n]] and [ = 0, 1, ..... k, denote by (i) B, the only set from Bi that contains i. In particular, (i) = {i} and B (i) = [n|]
For each i E [r]] and each 0, 1, ................................ k. introduce the random variables
9 g Z [m] (a())) = E gi Z,, [nn
That is, we condition on Z; and all the variables that are not in the same set as Z; in the partition B, One can check that o. 9i and "²¹ Elgi Z,). We can write telescopic sum for each [n]]
R-1
= L Zd
+
Σ 1=0
(s)
gi g(
It then follows from the triangle inequality that
k-1
12
Σ
9i
Elg. 2.1
Σ
Σ
(o)
91
1+1
(B.1)
i=1
Since [[/1: S M, one can check that (
7. = =i=1
Flg: Z7] is 2M-Lippchitz w.r.t.
the Hamming distance. Furthermore, we have [E [9: [4,
0. Now we can apply Lemma A. with
2M to derive the following inequality with at least 1 -
11111111| & MA. v 2n (2g()))).
1=1
It then follows from Lemma A.2 that
E Elg |, 3M A, 2pm.
(B.2)
i=1
According to the definition of g/, one can see that
Ez E [99] g. 1+1
Furthermore, according to our assumption we know of as a function of Zy.j E (i)((I)B(( satisfies the B-Lipschitz continuity w.r.t. the Hamming distance. Therefore, one apply Lemma A.1 with e = 3 and = of to derive the following inequality with (there are 2 random variables)
Pr(lot of 11 2) I 2 2exp (- 32. 22A
22
(B.3)
where the probability is w.r.t. Z B (i))
Let us consider the sum Eiert nc (g) 1-1 for any B' E Bj Note Z = gf - 9: 1+1 is function of
Z, [.). We now condition on Zin and then Z is a function of Z, According to Eq. (B.3).
we can apply Theorem with b = 2/-1 1--1 B² A2 to derive the following inequality
E |1|
> BEB
Col
o ) Man < (9 + log( B /)
2 B
22 B'
(9+ + 1)pp 22132 -9 1)p2' BA
We now take integration w.r.t. jjj, B and get
Σ Cof of 1
< (9 3A3.
SEB
According to the triangle inequality, we further get
Σ (g) of I| <
Σ
Σ
(o) 9 1+1
< 2 (99 -99 1)2"
iE(n]
B'ES
iEB!
where we have used the fact that
[B]] = 2 1, It follows that
n
Σ (of of |1,
/ S 2 p/3
(9 + 1)
1=0
1=0
We can plug Eq. (B.2) and the above inequality back into Eq.
to derive
Σ
S 3MA,, /2pm + 2 23
(9 1)43.
91
1=1
1=0
The proof is completed.
14

---

Published as a conference paper at ICLR 2023
C PROOF OF THEOREM! 5
To prove Theorem 5 we require the following lemma to control the difference between two test errors: with the test example drawn from the mixing sequence and one with the test example drawn from the independent stationary distribution. Let S. { be the sequence by removing the last b points of S.
Lemma C.1 (Mohri & Rostamizadehi 2010). Ler F (ws) = Ez if (ws: 2) [) denote the expectation
in the dependent case (ie., depends on S) and F (ws,) = E5 [ʃ (ws,; 2) denole the expectation
where the test points are assumed independent of the training data (i.e., 2 is independent of S). If A is 8- 3-uniformly stable and f(w; 2) E [0, M. then the following inequality holds for any b > 0
[ 3)] E3 (f
8] S 63 Mcp(b).
Let z/ (resp. = be drawn from the same distribution of 2,. i.e., the condi- tional distribution of z/ (resp. 2/") given 21...., R1-1; 2++1...., 2n is the same as that of 2 given 21..... 2/-1- 24 Zn- Let S.,6 {E1,.... 2-b-1 1: Ris 254b+1,.... 2n-b). For any i [n], let
Proof of Lemma 4
6 81- b- 1, 2
bn We have the following decomposition
Σ (Bey (/(W 5 (WS::
Σ
(Bey [S(Ws, R.g ([(s :(()
Egg Egg [f ;244 /( [1]]
Eyg [/(wst (Wss.ii)))
According to the definition of B-uniform stability know
E [f([[[(w]) [f(Ws,.32 - f(ws..: 2))
s 2,8 +
Σ 1=1
E.g E [f(s,, - (wss,,2)))|
1=1
(C.I)
For any i E [n]. introduce
9: = E2 [Eg [f(wst :24")] [=w)s=((ss
Then, we have
Σ
E u [f S 24'1 f f(Ws..i :1) $ 2,n
Σ
9
(C.2)
im
According to Lemma C.1 we know
F(ws) Ez S $3bB + Mb)().
By the definition of s we know
Ef Bs E)] s (b).
Furthermore, the definition of stability implies
[f(ws..i 24) - f(w x4] & 363.
We combine the above three inequalities together and derive
Σ F(ws) - E.; If 24 4')]1
Σ [((Ws, f(ws:2)) -WWs::))) < (6b3 + My((b) + (b)(
i=1
Combining the above inequality and Eq. C.Il
we obtain
|n(F(w)) - Fs(w)))
[B,) f(ws,si z)) +
Σ
F(ws) - (.ssl((ws..i +
Σ 1=1
f(ws,si&) - ((ws:2))
12
+ 2 Mpp(() +
Σ
94|
The proof is completed.
15

---

Published as a conference paper at ICLR 2023
Proof of Theorem
Recall the definition of 9s.
9i Reg [ sw z\) s(
Since 2; and x follow from the same distribution, we know
[ 0.
One can check other assumptions in Theorem also hold. Therefore, one can apply Theorem 2 to derive the following inequality with probability at least 1 - ò
A-1
ΣΣ
S 3MA. v 2pm + 2 pg
Σ (9
+1)
2=1
1=0
where flog2 n]. According Lemma A.2 we further get the following inequality with probability at least 1 -
Σ 91 3M 2n logl(() +
Σ
(9 + 1) log(e/0))
(C.3)
According to Lemma
we know
(nF(Ws)) Fs(ws)) - (6b 1 2)m3 (( + M +
- gil-
==1
We can combine the above inequality with Eq. at least 1
C.3 derive the following inequality with probability
n ((F(ws)= Es(ws)) S Se(3M S3 logle// + 2 2++1
8 Σ (9 1) log(e/0))
t-
+ (6b 2)m3 + m(Mp(b) Mb)(
The proof is completed.
D PROOF OF APPLICATIONS
D.1 PROOF OF COROLLARY
To prove Corollary we require the following lemma on the uniform stability of kernel regulariza- tion (Bousquet Elisseefi 2002).
Lemma D.1 (Bousquet & Elisseeff 2002). Let the loss function f be L-Lipschitz and convex. Let the algorithm A be defined in 5.2 Then A is B-uniformly stable with 3 < An'
Proof of Corollary 6 Let be the algorithm which returns Ws.x- By Lemma D.I
we know A is derive the
8-uniformly stable, where 8 < _
Ex Plugging the above inequality into Theorem 5
following inequality with probability at least 8
2(3b + 1)T.2 + Myp(b) + My'(b)
(((ws.) Fs((sx))
nd
+ M log(e/0) + 2eL k-1
Σ (9 + 1) log(e/5).
nd
1=0
By Lemma A.1 we have the following inequality with probability at least 1 1-6 5
Fs(w") - (((w")F[(w")) = o An log (1/8).
Vn
Furthermore, we have the following error decomposition
F(Ws,x) - F(w") ll
=F(Ws,>) Fs (s.)) Fs(ws.)) Fs(ww) + > A//wa..lll 1 < F((Ws,)) F's (w...) (ss""" F(w") + A/|ww*|] [|] where we have used the definition of ws.x- We can combine the above three inequalities together to derive the stated bound. The proof is completed.
Al/w*|1 1 + w Fs(w") F(w*)
[
16

---

Published as a conference paper at ICLR 2023
D.2 PROOF OF COROLLARY 7 AND COROLLARY g
First, we prove the stability bound for convex loss minimization via SGD. Then, we apply the stability bound and Theorem to the generalization bound. To develop high-probability bounds, need to introduce a concentration inequality (Wainwright, 2019).
Lemma D.2 (Chernoff's s Bound), Let X1...., .., X2 be independent random variables taking values Ej=1x X3 and μ = [[ Then for any > 0 with probability at least 1 exp (- u8² /2 + 6)) we have X (1 + 8)p. Furthermore, for any (0, 1) with probability at least - 5 we have
in {0, 1}. Let X
X & μ + log(1/6) + 22 log(1/6).
Proof of Corollary 7 Let S and S' be samples of size differing in only single example. Consider the gradient updates WI..... WT and wi.... w/ induced by running SGD on sample $ and S¹. We now suppose S and S differ by the first example and apply the Lipschitz condition on f(;2) to get
(wr3 (whri a)1 S L [6r],
(D.1)
where 67 1|w w/ll. Observe that at step t, with probability 1/n, the example selected by SGD is the same in both S and S'. The convexity and y-smoothness imply that (Hardt et al. 2016
(VS((, vS(w, - w) 2
=)1?
(D.2)
i # 1. by & 2/7 we know
We+1 - w'+1ll
|w/-- w/ll? 21T (V 2.)) Vf(W', 24) we
w() (ww))) VV ff(w 24,11
Ww w/ll2 2TT
'r [V[[(w, - V/(W1.
|we w/ll?.
(D.3)
With probability 1/ 1/n, the example selected is different, i.e. i, Then, by the triangle equality and
Eq. D.3
| W'+zal
||; 1/6 V. z4.) (w'- - V 24) IV - Vf(W(,+))1
(D.4)
< ||: - w'll + 21/L.
Combining the above two cases, we can conclude that for every t,
|W-1 w/+1|| < |w, -w'll + 2n, LI
(D.5)
where denotes the indicator function. Solving recursive inequality gives,
W - - s 2L Σ
21
[i I 2Lm Σ
(D.6)
1=1
1==1
We can apply Lemma D.2 with X I/ix /4 t/n to get the following inequality with probability
at least 1
I|==1] S t/n log(1/0) + 22t log(1/6).
Therefore, with probability at least there holds
[w++1 -w'+n < 2Ln(t/n log(1/5) +
log(1/))) -
By the convexity of the norm || ||. we get the following inequality with probability least 1
l|w w < (T log(1/5) + /2Tn log(1/5)).
Plugging the inequality back into Eq. DD.I. we obtain that, with probability at least
|f (w) (w's;=)) & (T/n (1/) 22Tn-1logl log(1/)))
(D.7)
17

---

Published as a conference paper at ICLR 2023
We combine Eq. (.7) and Theorem to obtain the following inequality with probability at least
1
(n(F(ws) - Fs(ws))
(D.8)
$ 44LL2n ( 1) 22T log(2/6)) 3eM A / log(2e/8)
k-1
Σ (9 (9+1) log( 2
2e
+ 4n 4nLn n
+
nM +
By the choice of T n,, we can get
k-1 = (0000///eooo///HH////000////1111 (1/6
Σ 14
1=0
The proof is completed.
To prove excess risk bounds, require the following high-probability bound optimization error. Notice that optimization error analysis does not depend on the mixing property of the dataset since the randomness taken with respect the random indices.
Lemma D.3 (Optimization Error (Lei & Tang 2018)). Assume that the loss function f(+;2) is convex and L-Lipschitz for every Suppose that run SGD with step sizes T7, n /T then with probability at least
8 we have
Fs(ws) inf Fs O(T log (T/6)).
Proof of Corollary 8
By Corollary
7 we know with probability at least 8 that
Σ 1n log (1/6) + M + Any log(1/6) 1/5)
[F(w)) Fs [w(s)))
O
nb lyblo((1/0) +
By Lemma A.1
we have the following inequality with probability least 1
Fs(w") - F(w") o( An log (1/0))
Vn
Lemma D.3 shows the following inequality with probability least 1 8
Fs(ws) inf Fs (s(w) = O log (T/))).
We plug the above three inequalities back into Eq. probability least 38
5.1 and derive the following inequality with
F(ws) F(w*) -0
blog ( +
00 -
Σ
k-1
1 log2 (1/0)
1=0
An log (1/6) + log (n/o) vn
+ Myp((b) +
The proof is completed.
D.3 PROOF OF COROLLARY
In this section, we present the proof on the stability of the iterative localization technique. To this aim, first present Algorithm
18

---

Published as a conference paper at ICLR 2023
Algorithm 1: Iterative Localized Algorithm
Input: initial point Wo 0, parameter > 0, m for i 1,2,.... ..... m72 do
2 log2 n)
7:m & E 3. 7t 1+1 set T; = n, V 2
draw a sample S, of size n from the mixing distribution
apply SGD with T; iterations and step size T to minimize the following problem and get w;
Fs, (w)
Σ f(w;2) 12
+
||w
w:-1ll?
7
SES;
end
Then we move to generalization bound for Corollary 9 definitions for proof. For any i, let
To this aim, We need to introduce some
w, arg min Fs; (w),
(D.9)
where Fs, is defined in Algorithm
Lemma D.4 (Optimization Error Bound). Suppose that the function + f(w; 2) is ju-strongly convex (with respect to || I]) and L-Lipschitz. Let {weht be produced by SGD on sample S and step
size = 2/(2 (u(( - 1)) to minimize (s((w) = +/ Ei f(w; 2.). Set w/ = (Eimi / /
Then, any d E (0, 1), with probability at least 1
Es (w:) Fs(w) =
The proof of Lemma D.4 can be found in Harvey al. 2019). According Algorithm | w, is the output by SGD with πソ = (t 1) to minimize Fs, (w), with the iterates weighted as Lemma D.4 The following lemma establishes the bound of Euclidean distance of w, and w..
Lemma D.5. Suppose that the function w - f(w; 2) is L-Lipschitz and p-strongly convex. For
any 8 (0, 1), the following inequality holds with probability at least 8
l| will = (Vira log (1/6)).
Proof. From Algorithm I we know that F's, is A; 2/ (ran) -stonnly convex. According to Lemma D.4 the following inequality holds with probability at least 1 -
Fs. (w;) Fs. (w,) = (log(1/5)/ (TAA.) = O (log(1 ( (n2a)).
It then follows from the definition of w; and the strong convexity that
A || wall Fs, (w:) Fs. (w.) = O (log(1/6)/ (nd.))
2
and therefore
lW will 2 (1og(1//)) (1/6))(11))) = (n log(1/6))
The proof is completed.
Lemma D.6 (Bousquet & Elisseeff 2002). Suppose the function W + E takes a structure f= E + T, where Ł: W x Z + IR and r W + R. Assume for all we have (V((w; < L. Suppose Fs n 5 E f(; 2,) is p-strongly convex and define as A(S) arg min Fs(w).
Then A is ny
1L2 -uniformly stable.
Lemma D.7. Assume for any 2, w + f(w; 2) is L-Lipschitz. Let w; be defined in Eq. probability least 88 (2m) we have the following inequality uniformly for any w
D.9
With
8/
(((.)-F.(w) = 0(
An log (2m/6)
b%
+M) 7/8 k-- 14,, (og(2m// (2m/6) [0)] 2 w w. 112
Vn
2
2
7.70
where & [log n2].
19

---

Published as a conference paper at ICLR 2023
Proof. For any define
1 7:
((w)=EE.ffve
w| w
and w arg minw (w). where we assume is independently drawn from the stationary distribu- tion of mixing sequence. Let A, be the algorithm outputting the minimizer of Fs., We know Fs. is A; (//7an)-stroone convex. Then analysis similar to irrollary@mmllee the stated inequality with probability at least 6/(m).. The proof is completed.
Based on the above lemmas, we now turn to proving Corollary 9
Proof of Corollary g Let Wo w and w, be defined by Eq. (.9). We can decompose F(Wm)
F(w*) by
F(wm) F(w")((>))))) (F(w.)-
- + F(wm)- P(Wm).
(D.10)
Since f is lipschitz, Lemma D.5 implies the following inequality with probability at least 1-5/(2m)
F(w m F( S L Wm winll O(vir log (1/5)).
(D.11)
Furthermore, we can apply Lemma D.7 with w w,-1 to derive the following inequality with probability least 1 - (2mm
(( = 0 A, log (2m/8)
by M Σ
k-1
1a log (2m/ 2 W/ - w.- 112
Vn
2
722
1=0
The following incquality then holds with probability at least - 6/2
(F(w)) F(W:-1))
An log (2m/d)
Σ 1A log(2m/5) + | wi-1l13
+ by + Mb)(b)) + 7
Vn
t=1
t=0
By Lemma
D.5
we further get the following inequality with probability at least 8
m
(F(w)) F(w
An log (2m/6) + by + Mbp((b) +
k-1
IA (lgg(mm/)) + m² log(1 (1/8)
V2
7/
i=1
m
+ by Myp((b) + 74 An log (2m/6)
k-1
Σ
o
Σ
A log(2m/0) + 71- log (1/8)
Vn
1=0
o mnn logt (2m/5)
k-1
+ by + mM)'(() + Σ 1=0
14 log(2m/6) + 1 log((11))
Vn
where in the last two steps we have used 7, = 7/2 We can plug the above inequality and Eq. (DIIT back into Eq. (D.10) and derive the following inequality with probability 1 1-8
F(Wm) - ((Wm)=F(w")) = o( mA, log (2m/5) + by + mM) + + Σ
ia log (2g(2m/5)
Vn
1=0
Vnyn log (1/6).
This gives the stated bound. The proof is completed.
20

---

Published as a conference paper at ICLR 2023
E PROOF OF LEMMA 3
Proof of Lemma 3 For simplicity, we only consider discrete random variables. Let A E R2- B E ahe and Zny 2 on According to the definition of mixing sequence, know
Pr(A[B) Pr(A)
1 (bk) S
(kk) + 1.
(E.1)
By Eq. EE.
we know
Pr(Zn; A) Pr Pn, A,
Pr(Za| A,
Pr(A, B) Σ. Pr(z, A,
P((A)PP(ZZZAAAP((IAAAAAA. Z.)
Σ. PT(A))P((())PP((((IAA))) Pr(2:1A)PP((1AA4...)
E. P((4A)))(B))))))
Pr(Za]4)Pr(BIIA) Z,)
Σ, ((K))))(((())++))))(()))))))
Pr(B) + (B)Pr((B
Pr(2))A)P((B)11=(())) Pr(Z, A)(1 (()))
Pr(B) ((K))
(+)(
(1
++((k)
It then follows that
(10)(116(B))))) Pr(Z.) = Pr(Zn) 1+
(1 - (()))2
1).
B)( - Pr(Z.)) >
1 2/(k)
In similar way, one can show
Pr(Z, - Pr(ZZ) < Pr(Z.) (1 (1+
(k))
The proof is completed by combining the above two inequalities together.
21


Reviews:
[{"review_id": "rCRPoV8tku", "reviewer": "Reviewer_HM4R", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves stability-based generalization bounds under the assumption that the data is drawn from a mixing sequence (rather than assuming that the data is i.i.d.). The bounds improve upon previous results by a factor which is the square root of the sample size.", "summary_of_the_review": "Although the paper does not motivate the mixing setting well with examples, overall I believe that the contribution is solid and hence I recommend acceptance.", "strength_and_weaknesses": "The paper makes a good contribution to learning theory, with improved results over prior literature.\n\nThe main weakness is that the paper provides no examples of mixing sequences (beyond the trivial i.i.d. case), which makes it difficult to understand the relevance of the work. Please provide such examples (if the authors did not do so out of a lack of space, then they can cut down on the elaboration of the various consequences in the algebraic and exponentially mixing cases in Section 5, since these are straightforward corollaries of the stated results).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nlvARJ2RI_L", "reviewer": "Reviewer_Ue97", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study generalization bounds in parametrized supervised learning when training (and test) data are not i.i.d. This setting is more realistic than the typical independence assumptions made in statistical learning theory for problems like time series (or say a Markov chain), where it is expected that the $t$-th sample depends on the prior position (observed examples). Following a long line of work on learning from non-i.i.d data, the authors consider the setting of “mixing processes,” where the dependence between samples is controlled by some mixing coefficient that decays to 0 between the $t$-th and $(t+i)$-th examples as $i$ goes to infinity. Roughly, the authors show that any uniformly stable algorithm has near optimal generalization bounds under strong assumptions on the decay of dependence across time.\n\nIn slightly greater detail, the authors consider two main settings called $\\phi$-mixing and $\\psi$-mixing respectively, where roughly:\n\n$$\\phi(k) = \\sup_{A,B}\\left|Pr(A|B) - Pr(A)\\right|, \\quad \\quad \\psi(k) = \\sup_{A,B}\\left|\\frac{Pr(A \\cap B)}{Pr(A)Pr(B)} - 1\\right|,$$\n\nWhere A and B are events k time steps apart, and $\\psi$-mixing is a stronger assumption than $\\phi$-mixing\n\nThe authors start by proving new concentration inequalities for $phi$-mixing sequences, showing that the sum of any family of $n$ mean-0, sub-gaussian variables $\\{Z_i\\}$ that are functions of random variables $\\{X_i\\}$ drawn from a $\\phi$-mixing process have bounded p-norm (matching the classical Marcinkiewicz-Zygmun inequality for the i.i.d setting up to log factors and the mixing coefficient). A similar result is shown for bounded mean, Lipshitz, coordinate-wise 0-mean variables, generalizing a result in the i.i.d setting of Bousquet, Klochkov, and Zhivotovskiy (COLT 2020).\n\nUsing these newly developed concentration inequalities, the authors generalize the optimal stability-based generalization bounds of [BKZ20] to the non-i.i.d setting (an algorithm is said to be stable if changing a single training example does not significantly shift the output value on any point). In particular, the authors show a high probability generalization bound of roughly:\n\n$$|F(w_S)-F_S(w_S)| \\leq \\tilde{O}(n^{-1/2})$$\n\nwhere $F$ is a bounded loss function and $w_S$ is the (parametrized) output of a uniformly stable algorithm on sample $S$, under the assumption that the data distribution is $\\psi$-mixing for $\\psi(k) \\leq 1/k^r$ for some $r>1$ (i.e. where dependence decays at a super-linear rate). To the authors’ knowledge, this is the first such result known to achieve optimal generalization rates for non-i.i.d data.\n\nFinally, the authors apply this result to a few popular learning paradigms, Kernel Regularization Schemes, SGD, and Feldman, Koren, and Talwar’s recent iterative localized algorithm to give generalization bounds of the form \n\n$$|F_S(w_S)-F(w^*)| \\leq \\tilde{O}(n^{-1/2})$$,\n\nUnder various standard assumptions (e.g. Lipshitz, smoothness, strong convexity), where $w^*$ is the minimizer of $F$.", "summary_of_the_review": "The authors study an interesting setting in statistical learning theory (generalization bounds under non-i.i.d data), and prove optimal bounds under strong decay of dependence across samples. On content alone the work is (in my opinion) above the bar for ICLR, but due to significant issues in presentation I cannot recommend acceptance in its current form.", "strength_and_weaknesses": "Studying learning settings where data is non-i.i.d is a natural and important problem, especially given that the vast majority of statistical learning theory is built for the i.i.d setting while one frequently expects dependencies to occur in practice. This work is (to my knowledge), the first to show that one can recover near-optimal generalization rates that don’t depend on classical complexity measures (VC, Rademacher, etc). The main concentration inequality for $\\phi$-mixing random variables also seems to be of independent interest. At a technical level, the work draws heavily from [BKZ20] and Mohri and Rostamizadeh (JMLR 2010), and the main observation seems to be that one can combine their techniques (the former giving optimal bounds in the i.i.d setting, the latter sub-optimal for $\\phi$-mixing) by making a stronger assumption on the mixing process ($\\psi$-mixing). Realizing this requires some effort and ties together several disparate works.\n\nOn the other hand, there are several serious issues in the presentation of the results. First and foremost, the authors claim as one of (if not the) main selling point that their generalization results improve over Mohri and Rostamizadeh by a factor of $\\sqrt{n}$, and are optimal. From what I can tell, this is not true. The authors make their improvement in large part via a stronger assumption on the decay of dependence in the mixing process, so the result is incomparable to prior work in this vein. I find the introduction to be fairly misleading in this sense, and largely due to this fact do not think I can recommend the work in its current form for publication in ICLR. There are a number of other presentation issues as well. A number of crucial definitions are not properly explained (e.g. distribution of the test examples), several of the theorem/lemma statements are confusing as written (what does “Let b ∈ {0, . . . , n} denote the number of last removed in S” mean?), and the stronger dependence assumption is never motivated (how much stronger is $\\psi$-mixing than $\\phi$-mixing? Is this a reasonable assumption?). \n\nMinor comments:\n\n1. “Note $\\Delta_n = O(1)$ for algebraical φ-mixing” Do you mean for $r>1$?\n\n2. I suggest writing bounds in asymptotic notation in the intro/beginning for readability\n\n3. It’d be nice to motivate the conditions in Thm 2 beside just being what you need for the analysis.\n\n4. There are many other grammatical/typographical issues throughout", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "hnYcbeaU9U", "reviewer": "Reviewer_uJFn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper uses the notion of \"algorithmic stability\" to study the\ngeneralization performance of learning algorithms that train on data drawn from\na $\\varphi$-mixing sequence. The authors give new high-probability guarantees\nfor uniformly stable algorithms that improve on previous state-of-the-art\nresults by a factor of $O(\\sqrt{n})$ [Mohri-Rostamizadeh, JMLR 2010]. They then\napply their general mixing stability bound (Theorem 5) to a few special cases\nfor polynomially-bounded and exponentially-bounded $\\varphi'(k)$-sequences: \nkernel regularization schemes, SGD, and an iterative localization algorithm.", "summary_of_the_review": "This is a good paper that could be accepted to ICLR. The target audience is\nprobably better suited for COLT since this work solely focuses on\ngeneralization bounds for $\\varphi$-mixing sequences (a method for quantifying\ndecay of correlation), but the results are of likely of interest to a broader\ncrowd.", "strength_and_weaknesses": "**Strengths:**\n- There is good precedent for studying generalization bounds via stability for i.i.d. data:\n  * Feldman--Vondrak, COLT 2019\n  * Bousquet--Klochkov--Zhivotovskiy, COLT 2020\n  * Klochkov--Zhivotovskiy, NeurIPS 2021\n- Previous work on stability bounds for $\\varphi$-mixing sequences are limited but important:\n  * Mohri--Rostamizadeh, JMLR 2010\n- The main contributions of this work are sufficiently technical, but also\n  adaptations of different previous works for $\\varphi$-mixing setting:\n  * The moment bound for weakly dependent random variables (Theorem 1) extends\n    [Ren--Liang, Statistics and Probability Letters 2001].\n  * The concentration inequality for $\\varphi$-mixing sequences (Theorem 2)\n    builds on [Bousquet--Klochkov--Zhivotovskiy, COLT 2020].\n  * The general uniformly-mixing stability bound (Theorem 5) is applied to\n    several useful instances (e.g., SGD).\n\n**Weaknesses:**\n- Theorem 5 and all of the corollaries in Section 5 use\n  $\\varphi'(b)$, which in turn is a function of $\\psi(k)$. The paper should\n  more explicit about this --- it doesn't seem like the authors draw any\n  attention to it. They do, however, note that ``$\\psi$-mixing is stronger\n  than $\\varphi$-mixing'', so this should be reconciled since the final\n  bounds are not solely a function of $\\varphi(k)$.\n- It would be helpful to mention soon after Definition 2 that we will use\n  $\\psi$-mixing to give a bound on the stability analysis version of\n  $\\varphi'$-mixing in Lemma 3. Otherwise, it's not clear why Definition 2 is\n  relevant, and then Lemma 3 is somewhat surprising in that the bound isn't\n  given in terms of $\\varphi(k)$.\n\n**Suggestions:**\n- [page 2] Typo: \"general bound\" --> \"generalization bound\"\n- [page 4] Clarification: In Theorem 1 we say $X_1, \\dots, X_n$ are\n  $\\varphi$-mixing distributions, but the definition for $\\varphi$-mixing is\n  given in terms of an infinite sequence of random variables. These ideas could\n  be better connected. We can say something similar about Theorem 2.\n- [page 5] Suggestion: Discuss the distribution from which $z$ is drawn in more\n  detail. You say that $z$ depends on $S$, but can you comment more about\n  what kind of assumptions are reasonable or previously studied?\n- [page 9] Typo: The equation in Corollary 9 should end with a comma, not a period.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "bwdwhqrkHK", "reviewer": "Reviewer_2VCS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the generalization performance of learning algorithms in a non iid setting, via the lens of algorithmic stability. The assumption made on the data is that it is generated by a mixing process ($\\phi$ mixing or $\\psi$ mixing) which formally quantifies how the level of dependency between two observations decays as a function of the gap between their indices. The paper derives moment bounds for weakly dependent random variables, which leads to a generalization of the Marcinkiewicz-Zygmund inequality (for iid random variables) to the non iid setting for mixing sequences. Then following the ideas in (Bousquet et al., 2020), they derive high probability bounds on the generalization error for uniformly stable learning algorithms trained on a sample drawn from a mixing process, with bounded loss functions. Applications of this bound are shown for several settings such as kernel regularization, stochastic gradient descent and iterative localized optimization algorithms.", "summary_of_the_review": "The paper is very well written. The problem setup, related work, and the setting considered is explained clearly, and the exposition of the technical results are also clean. I think this is a decent result and is a natural extension of the recent advancements made in the context of high probability bounds for the iid setting to the non iid setup. The bounds improve that of (Mohri & Rostamizadeh, 2010) by a factor of $\\sqrt{n}$ up to log factors, and this is made possible by heavily relying on the proof steps of (Bosquet et al. 2020), which leads to Theorem 2. The Marcinkiewicz-Zygmund type inequality developed in Theorem 1 is a useful tool although it seems to follow quite readily from the Mcdiarmid inequality in Lemma A.1 (Kontorovich and Ramanan, 2008).  ", "strength_and_weaknesses": "Pros: The paper has the following strengths.\n\n• Very well written paper with a clear exposition that explains the problem setup, main contributions, related work, and the technical ideas cleanly.\n\n• The high probability generalization error bounds for learning algorithms trained on non iid data generated from a mixing sequence is a solid addition to the literature, and novel to my knowledge. It improves the existing bound of (Mohri & Rostamizadeh, 2010) by a $\\sqrt{n}$ factor.  \n\nCons: The paper has the following weaknesses.\n\n• Theorems 1 and 2 are the main technical tools used for deriving the main results. However, the proof of Theorem 2 essentially follows the telescoping argument of (Bousquet et al. 2020) with little changes. And the proof of Theorem 1 follows readily from Lemma A.1 (as mentioned above), so there does not seem to be much technical novelty in the analysis.\n\n• I think it would be helpful for the reader if some discussion on the proof steps can be provided within the main text, especially for Theorems 1 and 2 as these are the main technical tools needed for deriving the main results.  At the moment, no such discussion exists regarding the proof steps. \n\nFurther comments:\n\n•  In Remark 4 in the fourth line, should it be “we cannot guarantee $\\mathbb{E}[\\tilde{g}_i] = 0$…”?\n\n• Theorem 5 is for loss functions which are uniformly bounded by M. It would be helpful to clarify in the text how the conditions required within the corollaries in Section 5 handle this boundedness condition. For example, in the proof of Corollary 6, it is not clear to me from the proof where M disappears?\n\n• In the statement of Corollary 6, I think f should be stated to be convex? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YatQEtLwd8", "reviewer": "Reviewer_enwM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper develops generalisation bounds for stable learning procedures trained on a $\\psi$-mixing (dependent) stochastic process. The key contribution here is an extension of a recent line of work on generalisation analysis of stable methods on i.i.d. data. Much like in the i.i.d. case, the result is stability bounds that improve in $\\sqrt{n}$ factors found in prior analysis of the same. \n\nThe extension follows two steps, both of which are mixing versions of the approach of Bousquet et al. [BKZ] - first, the authors derive a MacDiarmid type tail bound for sums of functions of $\\varphi$-mixing processes along the lines of Theorem 4 of [BKZ]. Next this with a one-point ghost replacement trick is used to derive stability bounds along the lines of Lemma 7 of [BKZ]. The main novelty lies in this second part - to handle the dependence of the stream, the authors extend this technique to control the generalisation error in terms of the risks of a model trained with a replaced $i$th sample along with removing $2b$ samples around $i$. The value of $b$ serves as an (analytical) tradeoff (roughly speaking, between the loss of samples and the decorrelation engendered by removing samples). This part is strongly reminiscent of the work of Mohri and Rostamizadeh [MR].\n\nThe paper concludes with applications of the bounds derived to methods previously established to be stable, illustrating the utility of the bounds found.", "summary_of_the_review": "I think this is an interesting paper, but have reservations for its appearance in this venue, and would additionally like a clearer description of how specific technical aspects of the argument interact with the prior work. On the whole, I lean towards recommending acceptance.\n\nN.B. - I would have given a score of 7 if available as an option, but it's not. The score of 6 rather than 8 reflects the fact that I do have reservations about the venue, but I'm open to changing this upon discussion.", "strength_and_weaknesses": "I think this paper is quite timely, and interesting. The extension of the recent iid stability breakthroughs to mixing processes was just waiting to happen, and the submission does a fine job of delivering on this. I think the paper also does a good job at characterising the existing work, and in treating a technically involved subject in a simple way. The proofs are, to my reading, correct, although I have not checked every detail.\n\nThere's perhaps two points of weakness to consider:\n\n- To an extent, these methods at a high level look like an integration of [BKZ] and [MR]. While the authors briefly discuss the differences from [BKZ] in the proof technique (the evacuating $b$), this difference appears to be present already in [MR]. I think a clear discussion of the specific challenges thrown by the integration of these two lines, and of the specific novelty relative to these will strengthen the paper.\n\n- The paper is very theoretical, which somewhat clashes with the flavour of this conference. While certainly most large ML conferences do have a space for theoretical work, ICLR tends to lie more strongly on the empirically driven side of things. It is thus worth considering how appropriate this paper is for the venue.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JLBOt4PZm-", "reviewer": "Reviewer_PGse", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of deriving generalization bounds for weakly dependent data using algorithmic stability. It builds on previous work by Mohri & Rostamizadeh (2010) which derived the first generalization bounds for this setup. This paper claim to improve on these bounds by a factor of sqrt(n). To derive these bounds, the paper develops some new moment bounds for sums and Lipschitz functions of weakly dependent random variables. Finally, the paper applies the new generalization bounds to analyze a few algorithms including kernel regularization and SGD.", "summary_of_the_review": "Overall, the paper appears to be a good contribution to generalization theory, though I have some concerns regarding the contribution and significance.", "strength_and_weaknesses": "Strengths:\n\n1. The paper has significant contributions to the understanding of generalization and algorithmic stability for the case of weakly-dependent data. For e.g. it obtains bounds which match the best known bounds for i.i.d. data in some cases if the dependence among the variables is weak enough.\n2. The paper introduces some interesting concentration bounds for sums and Lipschitz functions of weakly dependent random variables, which could possibly have wider applications.\n\nWeaknesses:\n\n1. I think the message, presentation, and perhaps the bounds in the paper as well need to be distilled more to make the contribution clearer. For e.g. how do the concentration bounds in Thm 1 and 2 compare with prior work? The bounds seem interesting, but I'm not sure of the improvement here. Similarly, I'm not fully sure of the improvement in Thm 5. If the sequence is exponentially $\\varphi$-mixing (or algebraically $\\varphi$-mixing with a large enough degree) then the $\\sqrt{n}\\varphi(b)$ term should be negligible, and the improvement is mainly in the other $\\sqrt{n}b \\beta \\Delta_n$ term. This term could potentially be significant, but I'd like to see some specific algorithmic examples where it leads to a better downstream bound. For e.g., it would be good if the authors commented on the difference between their bounds and previous work for kernel regularizations and SGD. On a related note, I'm not sure I fully understand the claim on page 2 that Mohri & Rostamizadeh (2010) get a worse than 1/sqrt(n) bound for strongly-convex problems, why should I think of $\\lambda$ as not being constant (or a very small polynomial) here? Seeing some concrete examples of how the theory leads to better bounds for well-studied algorithms would make the significance of the contributions much clearer.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster