Generalization Error Bounds on Deep Learning with Markov Datasets
Authors: Lan V. Truong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Generalization Errors
Deep Learning
Bayesian Deep Learning

Abstract: In this paper, we derive upper bounds on generalization errors for deep neural networks with Markov datasets. These bounds are developed based on Koltchinskii and Panchenko's approach for bounding the generalization error of combined classifiers with i.i.d. datasets. The development of new symmetrization inequalities in high-dimensional probability for Markov chains is a key element in our extension, where the spectral gap of the infinitesimal generator of the Markov chain plays a key parameter in these inequalities. We also propose a simple method to convert these bounds and other similar ones in traditional deep learning and machine learning to Bayesian counterparts for both i.i.d. and Markov datasets. Extensions to $m$-order homogeneous Markov chains such as AR and ARMA models and mixtures of several Markov data services are given.

Generalization Error Bounds on Deep Learning with Markov Datasets
Lan V. Truong
Department of Engineering University of Cambridge Cambridge, CB2 1P% 1t4070cam. ac
Abstract
In this paper, we derive upper bounds on generalization errors for deep neural networks with Markov datasets. These bounds are developed based on Koltchinskii and Panchenko's 's approach for bounding the generalization етгоr of combined classifiers with i.i.d. datasets. The development of new symmetrization inequalities in high-dimensional probability for Markov chains is key element in our extension, where the absolute spectral gap of the infinitesimal generator of the Markov chain plays key parameter in these inequalities. We also propose simple method to convert these bounds and other similar ones traditional deep learning and machine learning to Bayesian counterparts for both i.i.d. and Markov datasets. Extensions to m-order homogeneous Markov chains such as AR and ARMA models and mixtures of several Markov data services are given.
Introduction
In statistical learning theory, understanding generalization for neural networks is among the most challenging tasks. The standard approach to this problem was developed by Vapnik [1] and it is based on bounding the difference between the prediction error and the training error. These bounds are expressed in terms of the so called VC-dimension of the class. However, these bounds are very loose when the VC-dimension of the class can be very large, or even infinite. In 1998, several authors 2 3 suggested another class of upper bounds on generalization error that are expressed in terms of the empirical distribution of the margin of the predictor (the classifir)). Later, Koltchinskii and Panchenko proposed new probabilistic upper bounds on generalization error of the combination of many complex classifiers such as deep neural networks. These bounds were developed based on the general results the theory of Gaussian, Rademacher, and empirical processes in terms of general functions of the margins, satisfying a Lipschitz condition. They improved previously known bounds on generalization error of convex combination of classifiers.
In the context of supervised classification, PAC-Bayesian bounds have proved to be the tightest (5 Several recent works have focused on gradient descent based PAC-Bayesiar algorithms, aiming to minimise generalisation bound for stochastic classifiers 1 Most of these studies use a surrogate loss avoid dealing with the zero-gradient of the misclassification loss. Several authors used other methods to estimate of the misclassification eтror with non-zero gradient by proposing new training algorithms to evaluate the optimal output distribution PAC- MCC-Baysiinn bounds analytically [3] Recently, there have been some interesting works which use information-thhoreee approach to find PAC-bounds on generalization errors for machine learning 14 15 and deep learning [16].
*Use footnote for providing further information about author (webpage, alternative address) not for acknowledging funding agencies.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

All of the mentioee bounds are derived based on the assumption that the dataset is generated by an i.i.d. process with unknown distribution. However, in many applications in machine learning such as speech, handwriting, gesture recognition, and bio-informatics, the samples of data are usually correlated. Some of these datasets are time-series ones with stationary distributions such as samples via MCMC, finite-state random walks, or random walks on graph. In this work, we develop some upper bounds on generalization errors for deep neural networks with Markov or hidden Markov datasets. Our bounds are derived based on the same approach as Koltchinskii and Panchenko [4. To deal with the Markov structure of the datasets, we need to develop some new techniques in this work. The development of new symmetrization inequalities in nigh-dimensional probability for Markov chains is a key element in our extension, where the absolute spectral gap of the infinitesimal generator also apply our
of the Markov chain plays results to m-order Markov chains such as AR and ARMA models and mixtures of Markov chains. Finally, simple method to convert all our bounds for traditional deep learning counterparts for Bayesian deep learning is given. Our method can be applied to convert other similar bounds for i.i.d. datasets in the research literature well. Bayesian deep learning was introduced by (20] [1]]. The key distinguishable property of a Bayesian approach is marginalization, rather than using a single
key parameter in these inequalities. Furthermore,
setting of weights in (traditional) deep learning [22]
Bayesian marginalization can particularly improve the accuracy and calibration of modern deep neural networks, which are typically underspecified by the data, and can represent many compelling but different solutions. Analysis of machine learning algorithms for Markov and Hidden Markov datasets already appeared in research literature 17.19. In practice, some real-world time-series datasets are not stationary Markov chains. However, we can approximate time-series datasets by stationary Markov chains in many applications. There also some other methods of approximating non-stationary Markov chains by stationary ones via MA and ARMA models in the statistical research literature. The i.i.d. dataset is a special case of the Markov dataset with stationary distribution.
2 Preliminaries
2.1
Mathematical Backgrounds
1os Let Markov chain [== on state space S with transition kernel Q(1, dy) and the initial state
X1 ~ V, where S is Polish space in R. In this paper, we consider the Markov chains which are irreducible and positive-recurrent, so the existence of stationary distribution is guaranteed. An irreducible and recurrent Markov chain on an infinite state-space is called Harris chain (23] A Markov chain is called reversible if the following detailed balance condition satisfied:
Tt (dx))((a, dy) x (dy) dx),
Yx, E S.
(1)
Define
d(t) = sup drv (Q' =ES
Smix(() == min ft: d(t) S E)
(2)
and
2 =2-E) 2 1- tmix := tmixe (1/4)
Tmin == inf
fmix oses1
(3)
Let (2(T)) be the Hilbert space of complex valued measurable functions on S that square integrable w.r.t. π. We endow L2(T) with inner product (f, g) == = f dr, and norm [| := (f 1/2 Let
Ex, be the associated averaging operator defined by (Ea)(z, v) (()), Yx, y E S. and
A = 1 - Ex
(4)
where ([b))))()) = ma /B Q can be viewed as a linear operator (infinites- imal generator) on (T()), denoted by Q, defined as (z))(z) == (Q)x,)((), and the reversibility is equivalent to the self-adjointness of Q. The operator Q acts on measures on the left, creating measure PaQ, that is, for every measurable subset A of S. pQ(A) == fres Q(x, A))(dz). For a Markov chain with stationary distribution म,, we define the spectrum of the chain as
S₂ = (5 E C: (5I- - Q) is not invertible on L2(T)}
(5)

---

It is known that À = 1- - 24 where
supllel S2, 11,
if eigenvalue has multiplicity 1. otherwise
is the the absolute spectral gap of the Markov chain. The absolute spectral gap be bounded by the mixing time mix of the Markov chain by the following expression:
(;-11) log 2 S mmix S
log(4/m.)
(6)
where T, = msnges ue is the minimum stationary probability, which is positive if Q+ > (entry-
wise positive) for some 2 1. See [25] for more detailed discussions. In [25] 26 the authors provided algorithms to estimate fmix and y from a single trajectory.
Define
M2 = { u.
(
du
di < 00
where || 22 is the standard La norm in the Hilbert space of complex valued measurable functions on S.
2.2 Problem settings
In this paper, we consider a uniformly bounded class of functions: F: { if: - R} such that sup
| Il S . for some finite constant M.
Define the probability measure P(A) SA =(x)dr, for any measurable set A S. In addition, let Pa be the empirical measure based the sample (2,, .xn), i.e., Pa 20-15x, We also denote Pf = Is fdP and Paf == I's fdPa. Then, we have
Pf / f()))(x)dr and Paf f(X)).
1
(8)
On the Banach space of uniformly bounded functions F, define an infinity norm: ||||= = sup [Y) Let
Gz(F) =
(9)
where {g:}] is sequence of i..d. standard normal variables. independent of (X.). We will call n + ()) the Gaussian complexity function of the class F.
Similarly, we define
xx. 1
R (x(F) :-
(10)
and
p2 = n Σ EXxx
(11)
where {e;} a sequence i. Rademacher (taking values +1 and -1 with probability 1/2 each) random variables, independent of (X+). We will call n + (F(F) the Rademacher complexity function of the class F.
For times-series datasets in machine learning, we can assume that feature vectors are generated by a Markov chain {x with stochastic matrix Q, and of labels. Furthermore, Q is irreducible and recurrent some finite set S. An i..d. sequence of
the corresponding sequence

---

feature vectors can be considered as special Markov chain where Q(z, x') only depends on z'. In the supervised learning. the sequence of labels (Y, joc can be considered as being generated by Hidden Markov Model (HMM), where the emission probability PY,,x, (y/(r) g(r, y) for all n 2 1 and 9 S x y + Rt. It is easy to see that {(X,, Yn) is Markov chain with the transition probability
[n. P X,Y,, (Tn+1 Un+ Ln. Vn) = (In, In+ (( ;
(12)
Let Q(11, 11, 22, 122 (2 (22 12) for all I1, 32 E S and 31,32 E V. which is the S == x y. Then, it is not hard to
transition probability of the Markov chain {(X,, Yn) ]= that {(x,, Y,, )m) is irreducible and recurrent S, so it has stationary distribution, say it. The associated following probability measure is defined as
P(A) := / (2z ydddy,
(13)
Jsxy
and the empirical distribution Pn. based on the observations {(x,, )==1
Pn
Nx.
(14)
2.3 Contributions
In this paper, we aim to develop a set of novel upper bounds on the generalization errors for deep neural networks with Markov dataset. More specially, target is to find relationship between Pf and faf which holds for all f E JF in terms of Gaussian and Rademacher complexities. Our main contributions include:
We develop general bounds on generalization errors for machine learning (and deep learning) Markov datasets.
Since the dataset is non-i.i.d., the standard symmetrization inequalities in high- sigh-dimensional probability can not be applied. In this work, we extend some symmetrization inequalities for i.i.d. random processes to Markov ones.
We propose a new method to convert all the bounds for machine learning (and deep learning)
models to Bayesian settings.
Extensions to m-order homogeneous Markov chains such as AR and ARMA models and mixtures several Markov services are given.
3 Main Results
3.1 Probabilistic Bounds for General Function Classes
In this section, develop probabilistic bounds for general function classes in terms of Gaussian and Rademacher complexities.
First. prove the following key lemma,, which is extension of the symmetrization inequality for i.idd. sequences (for example, (27]) to a new version for Markov sequences { with the stationary distribution and the initial distribution E M2z
Lemma 1. Let F be class of functions which are uniformly bounded by M. For all n E define
2M
64M2
du
An
=
n(1
X)
+
n² - 2)2
dm
(15)
2
M
An
1Tmin Wogin Vro +
(16)
2n
Then, the following holds:
1
E
[
11
A, <E|[pP,
- pl| 2E [| + An
(17)
2

---

where
1 Σ exf( 2=1
Palls == sup
(18)
JEF
The proof of this lemma can be found in Appendix A the supplement material. Compared with the i.i.d. case, the symmetrization inequality for Markov chain in Lemma [ are different in two perspectives: (1) The expectation IE| [I] [P ||]]] is now is under the joint distributions
Markov chain and Rademacher random variables and (2) The term A, appears in both lower and upper bounds to compensate for the difference between the initial distribution v and the stationary distribution of the Markov chair Later, will that A,, represents the effects of data structures the generalization errors in deep learning.
By applying Lemma ! the following theorem can be proved. See detailed proof in Appendix C in the supplement material.
Theorem 2. Denote by
2
64
dv
BR =
+
(19)
n(1
X)
(1
X)2
dm
2
Let ip be a non-increasing function such that (p(x)
2 1 (-000.0] (x) for all x E R. For any t > 0.
8L(p))
P 3 E P(f 50}
>
inf 6E(0,1)
Pass
+
(F(
8
x²
+ (t + v log log, 28
Tmin
+ Bn
exp(-211
(20)
n
3
and
2L(x) 2
P 3f F: P(f S >
inf
P.
8 +
(T(
6E(0,1)
+ (t+ + v log log, 26 20-1)
Tmin
+ vn
+ Bn )) S 3
exp(-22"
(21)
n
Since B, = O(1V/n). Theorem 2 shows that with high probability, the generalization error can be bounded by Rademacher or Gaussian complexity functions plus an O(1/vTi) term, where n is the length of the training This fact also happens in i.i.d. among samples in Markov chain, the constant in O(L/vn) term is larger than the i.idd. case.
4. However, because the dependency
It follows, in particular, in the example of the voting methods of combining classifiers (2). from Theorem we achieve the following PAC-bound:
8C
V(H) n
PV s 0) < inf 6E(0,1)
Pa.i so
8
B, +
(v] log
?
/ log log, 20 20-1)
VV
Tiin
(22)
3a
with probability least (PAC-Bayes bound), where V(H) the VC-dimension of the class H
and C' is some positive constant.
3.2 Bounding the generalization error in deep neural networks
In this section, we consider the same example as 4 Section 6]. However, we assume that feature vectors in the dataset are generated by a Markov chain instead of an i.i.d. process. Let H be the class of uniformly bounded functions f S + R. H is called the class base functions.
"This difference causes a burn-in in time 28 which is the time between the initial and first time that the Markov
chain is stationary.
5

---

Consider a feed-forward neural network with layers of neurons V = ff V3 where Vi {v. The neurons U, and Uo called the input and the output neurons, respectively. To define the network, we will assign the labels to the neurons the following way. Each of the base neurons is labelled by function from the base class H. Each neuron of the j-th layer Vj. where labelled by a vector w == (Wi, W2, Here, will be called the vector of weights of the neuron.
1, is Wm) E R" where m the number of inputs of the neuron.
Given a Borel function from R into [-1, 1] (for example, sigmoid function) and a vector w = (wi, W2,"
Wmm) E R where = [H| + 1, let
No.00 R + R, No (u1, 02, 1. Um == or
Wyuj)
(23)
Let o. : 1 be functions from into [-1, 1], satisfying the Lipschitz conditions
- [oy(u)-oy(o)
- Ly uajuuou o/. u, E R.
(24)
The neural network works can be formed as the following. The input neuron inputs an instance r E S. base neuron computes the value of the base function on this instance and outputs the value through its output edges. A neuron in the j-th layer (j 2 1) computes and outputs through its output edges the value No,,0(U5, U2,- (m) (where U1 " .... Um are the values of the inputs of the neuron). The network outputs the value (ax (of function it computes) through the output edge.
We denote by N₁ the set of such networks. We call N₁ the class of feed-forward neural networks with base H and layers of neurons (and with sigmoid o,). Let No == UJ=NN Define Ho == H. and then recursively
Hj = { No No (h1, hm): 2 0, h4 E Hi-1, B UH--I-
(25)
Denote Ho == U,. Hy. Clearly, Hos includes all the functions computable by feed-forward neural networks with base H.
Let {by} } be a sequence of positive numbers. We also define recursively classes of functions com- putable by feed-forwart neural networks with restrictions on the weights of neurons:
Hb,bi, bo,,b,,,bbb bb) = No b2,.... hm) : 2
h E (01, b2, by-1), w R." //el11 bj 1 ,bj-1), (26)
where ||ll| denotes the 1-norm of the vector w. Clearly,
Hox U H4 ... .b)): bi b., ,, < to0
(27)
Denote by H. the class of measurable functions f S x - R. where y is the alphabet of labels. H is introduced for real machine learning applications where we need to work with new Markov chain generated from both feature vectors and their labels {(X,, Y,) instead of the feature-based Markov chain [x, See Subsection 2.2 for detailed discussions. For binary classification,
H : (f f E H), where f(z,y) vz))). Let to be function such that sxx) > ((-o<,oj())) for all x E RR and y satisfies the Lipschitz condition with constant L(p)) Then, the following is direct application of Theorem 2
Theorem 3. For any t 2 0 and for all 1 1 1,
Prpp { + 2 2
P 3f H(b,, b2. .b)) PIJ < 0)
inf SE(0.1) I]
II (2L,b, (H)
< 2²
+ (1+ Vlog log, 28 26-1) where Bn is defined in
Finin + Bn
(xp(-211)
(28)
3
19

---

Remark 4. Pff - 0} represents the probability of mis-classification in the deep neural network.
Proof. Let Hl H(bi, b2, b1). As the proof of 4 Theorem 13). it holds that
G, - II
(2L5 + (H..
(29)
==1
Hence, 288
direct application of Theorem and 29
Now, given neural network f E Noo. let
I(f) min 2 1: f Eg))
(30)
For any number & such that 1 < k < ((f). let (f( be the set of all neurons of layer & in the neural network which represented by f. Denote by
W&(f) := max wEVi(f)
||w(()) ||
bk:
k 1,2,..,,,1 .(f)
(31)
where w() is the coefficient-vector associated with the neuron u in this layer. Define
1(f) A II (AL (4L,
K0
Ta()) = Σ log(2 log, W&()),
(32)
where > 0 is the number such that ((a) < 3/2, ç being the Riemann reta-function: ((a)
Ek=1 k o Then, by using Theorem 3 with by - ao and the same arguments as 4 Proof of Theorem 14], we obtain the following result. See Section 1.3 in the supplement material for more detailed derivations.
Theorem 5. For any t 2 and all 2 1,
2 2V2TL(0)
2 Vn
H Pl 00 >
inf 8E(0,1)
Pasp 8
AJ)G,( +
8
+(I+Ta00) Vlog logg 28-1
Tiin
Bu
1)
s - 2((a)) exp (-2(2), (33)
x²
n
where Bn is defined in (I
3.3 Generalization Error Bounds on Bayesian Deep Learning
For Bayesian machine learning and deep learning, F= {s S W - R]. where S is the state space of the Markov chain and W is the domain (random) coefficients. We assume that and W are Polish spaces on R. which include both discrete sets and R. For example, in binary classification, f(X, W' = sgn( ( X + b) where the feature and the coefficient W are random vectors with specific prior distributions. In practice, the distribution of W is known which depends our design method, and the distribution of X unknown. For example, W is assumed to be Gaussian in Bayesian deep neural networks 22..
Since all the bounds on Subsections 3.1 and 3.2 hold for any function f in F at each fixed vector W = hence, they can be directly applied to Bayesian settings where W is random. However, these bounds are not expected to be tight enough since we don't use the prior distribution of W when deriving them. In the following, we use another approach to derive new (and tighter) bounds for Bayesian deep learning and machine learning from all the bounds in Subsections and For illustration purposes, we only derive new bound. Other bounds can be derived in similar fashion. We assume that Wi, W2, ... W,, are i.i.d. random variables as in [22].
Let
1
Pr =
8x..W
(34)
2m

---

and define new probability measure P on S x W such that
P(A) / F(z, w)dxdw,
(35)
for all (Borel) set A on S x W. Here, ñ is the stationary distribution of the irreducible Markov process {(X,, w, with stochastic matrix Q == {Q(z, Pw (w)):/(ww)kr)) (o) In addition, define two new (averaging) linear functionals:
Pa( = 1 Σ / (dd n 1=1
(36)
and
P()) (())= J 1 f(x, w)r(2, W)dd
(37)
In practice, the prior distribution of W is known, so we can estimate P. (f) based on the training
set {(X1, Yi), (X2, Y2),... (Xn, Y, which is a Markov chain on X x y (cf. Section 2.2 The following result can proved.
Theorem 6. Let up be a sequence of finccton such that (p(x) 2 ((-00,0)(). For any
8T((P)
P Af
>
inf
P
+
6E(0.1)
+ (t+ + llg logg 28
Trin
+ Bn
π²
exp(-2t")
(38)
3
and
p Bf F PTF S 50} >
inf 6E(0.1)
Prop
1
1
+
21(g)
2T
Gx(F)
+
2
0
8
V
π²
(1 + v log logg 20-11
Tmin
+ Bn
s
exp (-21²).
(39)
Proof. Let W1, W2. Wn, be an n samples of W ~ Pw on W (or samples of some set of random coefficients). For simplicity, we assume that (W, les 1 is an i.i.d. sequence. Then, it obvious that f(Xn, 1a forms Markov chain with probability transition probability
(In, Wxi Tn+1: Wx+1) P(Xn+1 In+1, Wn+1 Wnt1|Xn Zn, W., wn) = Q( Tn+1 Pi (w
(40)
(41)
From Theorem 2 it holds that
P EF PUSO}>
inf 6E(0.1)
Puss
f 8L(p))
(F)
+ (t + log log, 25-1)
IV
Tmin
B,
< n
exp(-2t²)
(42)
This means that with probability at least
x²
exp((22t? it holds that 3
PV < 0}
<
inf
{
8L(P)
(n( + (++ Vlog log, 20-1) )
Tiin
Bu
(43)
sE(0.1]
8
From it holds that with probability at least
- 2² 3
1 2
f(X,, Wi)
+ 8L(P) R, (F)
Pff <0 < inf 6E(0.1)
Σ
4
i=1
+ (t Vlog log, 25-1)
V
Tmin
+ Bn
(44)
8

---

From 44
with probability at least 1 -
x²
3 (exp(-213) it holds that
1
f(x;,W3
Wi)
8L(P)
Bw
P(f S 0} S Ew
inf 6E(U,1]
Σ
(F)
n im
8
8
+ (1 + Vlog logg 26
28-1) v
Twin
Bn
(45)
n
1 Σ Ew 10
[(X,,
]
8L(p)
inf 60(0.1]
+
(F)
8
+ (++ Vlog logz 26-1)
Tiin
Bn
(46)
n
From 46 we obtain
(38) Similarly, we can achieve
(39
4
Extension to High-Order Markov Chains
In this subsection, we extend our results in previous sections to m-order homogeneous Markov chain. The main idea convert m-order homogeneous Markov chains 1-order homogeneous Markov chain and use our results in previous sections to bound the generalization error. We start with the following simple example.
Example 7. [m-order moving average process without noise] Consider the following m m-order Markov chain
m
X
a
E E
(47)
1=1
Let Yv = (x
XxJ=.
Then, from
47
obtain Yx41 GYs Vk E z
where
a1
am
am
G
0
1
0
0
(48)
is clear that (Y,) is an order-1 Markoy chain. Hence, instead of directly working with the m-order Markov chain [Xn)m we can find upper bound for the Markov chain {Yn 1x
To derive generalization error bounds for the Markov chain [= we can use the following arguments. For all f F and (Ia, Tktl,' .. 3k4mm-1) 1), by setting f( 2k41, (x4mm-))) f(xx) where f : 8 + R. we obtain
1 " TE
n n
10000 10()) 50.
(49)
Hence, by applying all the results for 1-order Markov chain [Y we obtain corresponding upper bounds for the sequence of m-order Markov chain
{Xn)
100
This approach can extended to more general Markov chain. See Section 4 in the Supplementary Material for details.
5 Conclusions
In this paper, we derive upper bounds on generalization errors for machine learning and deep neural networks based on a new assumption that the dataset has Markov or hidden Markov structure. We also propose a new method to convert all these bounds to Bayesian deep learning and machine learning. Extension to m--oreer Markov chains and a mixture of Markov chains are also given. An interesting future research topic to develop some new algorithms to evaluate performance of these bounds on real Markov datasets.

---

References
[1] V. N. Vapnik. Statistical Learning Theory. Wiley, New York, 1998.
[2] Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651 1686, 1998.
[3] Peter Bartlett and John Shawe-Taylor Generalization Performance of Support Vector Machines and Other Pattern Classifiers, page 43-54. MIT Press, 1999.
[4] V. Koltchinskii and D. Panchenko. Empirical Margin Distributions and Bounding the General- ization Error of Combined Classifiers. The Annals of Stafistics, 30(1):1 -50, 2002.
[5] J. Langford and J. Shawe-Taylor. PAC-Bayes and Margins. In Advances of Neural Information Processing Systems (NIPS), 2003.
[6] D. A. McAllester. Pac-hayesian stochastic model selection. Machine Learning, 51, 2004.
[7] E. Purrado-Hem"" Hern'andez A. Ambroladze and J. ShaweTaylor. Tighter PAC-Bayes bounds. In NIPS, 2007.
[8] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Uncertainty in Artificial Intelligence (UAT), 2017.
[9] M. Austern R. P. Adams W. Zhou, V. Veitch and P. Orbanz. Non-vacuous generalization bounds the imagenet scale: PAC-Bayesiaa compression approach. In The International Conference on Learning Representations (ICLR), 2019.
[10] F. Biggs and B. Guedj. Differentiable PAC-Bayer objectives with partially aggregated neural networks. Entropy, 23, 2021.
[11] A. McAllester. Some PAC-Bayesian theorems. In Conference on Learning Theory (COLT), 1998.
[12] Eugenio Clerico, George Deligiannidis, and Amaud Doucet. Wide stochastic networks: Gaus- sian limit and PACBayesian training. Arxiv: 2106.09798, 2021.
[13] Eugenio Clerico, George Deligiannidis, and Arnaud Doucet. Conditional Gaussian PAC-Bayes. Arxiv: 2110.1188 2021.
[14] A. Xu and M. Raginsky. Information-theowe analysis of generalization capability of learning algorithms. Advances of Neural Information Processing Systems (NIPS), 2017.
[15] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via Rényi-f-divergences and maximal leakage. IEEE Transactions on Information Theory, 67)8): 4986-5004, 2021.
[16] D. Jakubovitz, R. Giryes, and M. R. D. Rodrigues. Generalization Error in Deep Learning. Arxiv: 1808.01174 30, 2018.
[17] John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. Ergodic mirror descent. 2011 49th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 701-706, 2011.
[18] Gang Wang, Bingcong Li, and Georgios B. Giannakis. A multistep Ιyaрunov approach for finite-time analysis of biased stochastic approximation. ArXiv, abs/1909.042999 99999999999999999 2019.
[19] Lan V. Truong. On linear model with markov signal priors. In AISTATS, 2022.
[20] David J.C. MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, United States, 1992.
10

---

[21] David J. C. Mackay. Probable networks and plausible predictions a review of practical bayesian methods for supervised neural networks. Network: Computation In Neural Systems, 6:469-505, 1995.
[22] A. G. Wilson and P. Izmailov. Bayesian deep learning and probabilistic perspective of model construction. Proc. 37th ICML. Morgan Kaufmann, 2020.
[23] Pekka Tuominen and Richard L. Tweedie. Markov Chains with Continuous Components. Proceedings of the London Mathematical Society, 53-38(11:89-111 01 1979.
[24] Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20(79):1 - 32, 2015.
[25] G. Wolfer and A. Kontorovich. Estimating the mixing time of ergodic markov chains. In 32nd Annual Conference on Learning Theory, 2019.
[26] R. Combes and M. Touati. Computationally efficient estimation the spectral gap markov chain. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3:1 -2,, 2019.
[27] A. W. Van Der Vaart and Wellner. Weak convergence and Empirical Processes. Springer, New York, 1996.
[28] D. Rudolf. Explicit error bounds for Markov chain Monte Carlo. Arxiv: 1108. 3200, 2011.


Reviews:
[{"review_id": "gQyrgGvFoXD", "reviewer": "Reviewer_XGoR", "summary": "This paper develops an empirical process theory for irreducible reversible Markov Chains with applications to statistical learning theory for non i.i.d. sampling. It adopts an ambitious and historically faithful approach, following the classic [1] quite closely and generalizing most of their results to the non i.i.d. case.\n\nIn very simple terms, the most basic idea relevant to both this paper and to [2] is that empirical averages of functions will converge to their population versions, where the latter are defined in terms of the stationary distribution of the background Markov chain process, as a result of the convergence of the samples to this stationary distribution. \n\nHowever, the results are of course finite sample and in particular, also apply before approaching the stationary distribution and perfectly quantify the convergence. The proofs usually follow the proofs of [1] quite closely, but must also invoke in passing some powerful results  from [2,3,4,5]. Most notably this includes Lemma 22 from the sup., i.e. Theorem 3.41 from [3], which quantifies the convergence of the background Markov process to the stationary distribution (which constitutes one more source of \"failure\"), as well as the Markov Hoeffding's lemma (lemma 23, page 27) from [2,6]\n\nThe work is composed of the main paper and a supplementary in two parts since the latter contains an appendix. The 2-part supplementary is reasonably self-contained and there is little need to read the main paper in too much detail. \n In my opinion, one of the main results of the paper is Theorem 5 in the supplementary, which provides a uniform high probability bound on the difference between P(f_n\\leq 0) and P(f\\leq 0) where f_n is an empirical average of f and the bound is uniform over f running in an arbitrary function class. The bound naturally involves the Rademacher complexity of the function class in question. In the main paper and much of the rest of the \"main supplementary\", the results are expressed in a more general but harder-to-parse form (which can nonetheless be easily translated to theorems of the form of this Theorem 5. ) \n\nThe above result can be directly applied to obtain generalization bounds for classification problems via the classic lemma in statistical learning theory, for an arbitrary method, as long as one can bound the complexity of the underlying function class. However, \"the main supplementary\" goes much further and (in section 2.3) establishes tighter results on the convergence of the empirical processes not just in distribution but in terms of Lévy distance. The work also provides applications of the results to convex combinations of classifiers and to neural networks, all of which mirroring [1]. The application to Neural Networks is reasonably high-level (could theoretically be applied to other methods such as deep kernels for instance), and features the complexity of the one-layer set of basis functions without computing it. \n\nFinally, there are sections with an extension of the results to the case of higher-order Markov chains and to Bayesian deep learning for good measure. \n\n\n\n\n\n=======================================\nReferences:\n\n\n[1] V. Koltchinskii and D. Pachenko. \"Empirical margin distributions and bounding the generalization error of combined classifiers\", Annals of stats 2002. \n\n[2] Jianqing Fan, Bai Jiang, Qiang Sun. \"Hoeffding's inequality for general Markov chains and applications to statistical learning.\", JMLR 2021\n\n[3] Daniel Paulin. \"Concentration inequalities for Markov chains by Marton Couplings and spectral methods\", electronic journal of Probability 2015. \n\n[4] Ledoux and Talagrand. Probability in Banach spaces. \n\n[5] D. Rudolf. Explicit error bounds for Markov chain Monte Carlo. (arxiv 2011)//Explicit error bounds for lazy reversible Markov chain Monte Carlo,  Journal of Complexity 2009. \n\n[6] Shravas Rao. A Hoeffding inequality for Markov Chains.  Electronic communications in Probability 2019. \n\n\n", "questions": "In this section, I list both \"questions\" and the most significant doubts/mistakes I have about the actual mathematics of the paper.  In the \"limitations\" section I list comparatively minor issues. (This should hopefully make it easier for the authors to prioritize their work during the rebuttal)\n\n\n1. QUESTION: In Lemma 26 (main supplementary), your constants are explicit, whereas the equivalent result (Theorem 5 on page 16 of [1]) involves a nonexplicit constant. It would thus appear that your result is tighter even in the i.i.d. case. Is that the case and can you explain what made this possible? \n\n\n2. PRESUMED ERROR: Lemma 22 page 25 is cited from 11, theorem 3.41, which is on page 60 and originally involves a parameter \"p\". The value of p which yields the result as cited is p=4, but then the constant next to M^2 should be 128 instead of 64, to account for the additional factor $\\frac{p}{p-2}=2$. Of course this also influences several theorem statements throughout all three parts of the submission, including the definition of \"A_n\" wherever it appears, equation (18) in the main text, etc.  \n\n\n\n3.  QUESTION/ PRESUMED ERROR: I think there are a couple of issues with the proof of Lemma 7 (from page 5) on page 39. It doesn't seem that the statement is correctly proved with the current order between the classifiers. It looks like there is a single proof which works for an arbitrary value of y, but that is not enough to put y inside the high probability statement (unless a suitable union bound and limiting argument were applied). In addition, the proof is a bit sloppy on lines 636-638: It would seem that equation (400) holds \"for any y\" (which should replace the \"for any t\" from line 636), and that it shouldn't involve the term $\\frac{4t}{\\sqrt{n}}$, which instead comes from equation (394). It is after this (at equation (401)) that the quantifier is slipped back into the high probability statement without proof. \n\n3.2 (Minor) For the ease of the reader I would also recommend adding that equation (214) is on page 25, or better, restructure the proof of Lemma 1 so that equation (214) becomes a separate lemma, which it seems to deserve to be. \n\n\n4. MISSING PROOF (confirm solution below): The proof of Theorem 5 (page 4 of the main sup.) is not complete at all. Note that first of all, the theorem makes use of the notation \"\\gamma_{ps}\", which has not been introduced in the paper. It turns out (see equation (3.3) of [3]) that this refers to the \"pseudo spectral gap\". Applying the results from Theorem 3 as dictated in the proof here does not yield equation (17) but instead a different equation with the term 4M\\exp(...) replaced by something similar to the quantity \"A_n\". I believe that the correct way to reach theorem 5 is by using the Bernstein-type inequality from page 13 of [3] instead of Lemma 22 in dealing with the \"burn-in\" part of failure estimation. \n\n\n\n\n5. QUESTION: Do you think it is possible to obtain simpler results of a more \"classic SLT\" flavor (with expectation instead of probability, and generalization bounds involving margins), analogous to the treatment of [7], by using only the symmetrization parts of the present paper and using a McDiarmid type inequality? If so, has it been done and where is the \"Markov McDiarmid inequality\" in the literature? \n\n5.2 Have you tried just starting with the Hoeffding type lemma from the closely related work [2], applying a union bound (which should reach a finite class result already) and then using classic covering number arguments to obtain a result in terms of Theorem 10.1 in [8]?\n\n\n\n\n=======================================\nReferences:\n\n[1] V. Koltchinskii and D. Pachenko. \"Empirical margin distributions and bounding the generalization error of combined classifiers\", Annals of stats 2002. \n\n[2] Jianqing Fan, Bai Jiang, Qiang Sun. \"Hoeffding's inequality for general Markov chains and applications to statistical learning.\", JMLR 2021\n\n[3] Daniel Paulin. \"Concentration inequalities for Markov chains by Marton Couplings and spectral methods\", electronic journal of Probability 2015. \n\n[4] Ledoux and Talagrand. Probability in Banach spaces. \n\n[5] D. Rudolf. Explicit error bounds for Markov chain Monte Carlo. (arxiv 2011)//Explicit error bounds for lazy reversible Markov chain Monte Carlo,  Journal of Complexity 2009. \n\n[6] Shravas Rao. A Hoeffding inequality for Markov Chains.  Electronic communications in Probability 2019. \n\n[7] Bartlett and Mendelson. \"Rademacher and Gaussian Complexities: Risk Bounds and Structural Results\" 2002. \n\n[8] Anthony and Bartlett. Neural Network Learning: Theoretical foundations. 1999. \n", "limitations": "For actual limitations, see the above questions.  See more minor issues below. \n \n\n\n==============Minor problems with notation=============\n\n\nMAIN:\n\nEquation (4) of the main paper (page 2): the mixing time is not defined (see def 1.3 on page 4 of [2]). \nLine 72: \\gamma_{ps} is not defined.  See (4.5) in [9], or middle of page 2 in [2]. \nLines 74 to 76 are a little bit sloppy: the condition \"\\nu\\ll \\pi$ should be in equation (5) inside the brackets rather than before the equation, \\nu and v shouldn't be used interchangeably and a clash with the running variable measure in eq (5) and the initial distribution \\nu should be avoided. Later in the equation after line 76, it is the initial distribution that is meant by \\nu/ v. There is also an actual constant \"v\" in Theorem 6 (sup) which should ideally not clash either. \n\nLine 105 when you claim that the MC (X_n,Y_n) is irreducible and recurrent, I guess some more conditions are required, including the assumption that the original MC is recurrent and irreducible (which I agree is implied) and the fact that g(x,y) \\neq 0 for all (x,y). Sounds like this condition should creep up in a lot of other main theorems in some form of other as well. \n\nEquation (19), at the bottom of page 4 (line 130). P_0 is not defined! This is definitely unpleasant for the reader. I guess P_0 refers to the Rademacher or gaussian complexity, from the rest of the context.  It appears in technical appendices for the first time in equation (221) page 26 as far as I am concerned.\n\nEquation (49), top of page 9: I think there is a constant \"c\" missing after \\pi^2 before the exponential. \n\nSUP\n\nLemma 19 and its proof (pages 18 and 19): there is some inconsistency between the originally introduced notation where bold version of epsilon, X and Y refer to the vector of the first n instances of the corresponding variables and the later notation. In the proof there is some notation of the type \\epsilon^1_n for the first n instances of \\epsilon (and similar notation for X and Y). This should be introduced. \n\nequation (154), line 414 page 20: there is some inconsistency in the use of comas in the indices which define the transition probabilities. \ncf. also equations (157, 159 and 160)\n\nI would mention Jensen's inequality to aid the reader at line 463 top of page 26. \n\n\n\nline 500 page 29: I really dislike it when authors \"prove\" a statement with \"by [Reference]\" as a mere justification. You could write \" By a Slepian type Lemma  (c.f. the middle of page 7 in [1] or [4]m pp 76-77), ... \" Or even better, write the used result in a separate Lemma. \n\n\n\n=========minor typos========\n\nMAIN: \n\nEquation (10) should have a period instead of a comma. \nline 78 \"homogeneousness\" should be \"homogeneous\"\nLine 145 (p 5) \"because the dependency\" =>\"because of the dependency\" \nLine 149 (p5) \"Let \\mathcal{H} be a the\" ===> see the section 2.5 page 8 of the sup which corresponds to this section and is better written than in the main. \n162 (p5) should be \"for example, THE sigmoid function)\n146 \"constant is larger than IN  the i.i.d. case\" \n165 \"Neural networks can\" (not \"networks works can\")\n214 (p 8) \"we only derive a new bound. Other bounds can be derived in a similar fashion\" \n==> \" We only derive one bound:  equation (45). The other bounds in this paper (such as eq. (46)) can be derived in a similar fashion\" \n\n227 \"associated\" is repeated \n\n\n\nSUP\n\n\n125: \"especially, ...\" => \"In particular, ...\"\nFootnote at the bottom of page 27: \"...change of measure is appeared in...\"==> \"\"...change of measure appeared in...\"\n\n499 \"and g is standard normal independent\" ===> \"  \"and g is A standard normal independent\"\n\nLine 549 \"replacing u=... to (294)\"  ===> \"substituting u=... into equation (294)...\" \n\n\n\nLemma 26 page 37 lines 612-613: Improve sentence structure. \n\n\n\n=======================================\nReferences:\n\n\n[1] V. Koltchinskii and D. Pachenko. \"Empirical margin distributions and bounding the generalization error of combined classifiers\", Annals of stats 2002. \n\n[2] Jianqing Fan, Bai Jiang, Qiang Sun. \"Hoeffding's inequality for general Markov chains and applications to statistical learning.\", JMLR 2021\n\n[3] Daniel Paulin. \"Concentration inequalities for Markov chains by Marton Couplings and spectral methods\", electronic journal of Probability 2015. \n\n[4] Ledoux and Talagrand. Probability in Banach spaces. \n\n[5] D. Rudolf. Explicit error bounds for Markov chain Monte Carlo. (arxiv 2011)//Explicit error bounds for lazy reversible Markov chain Monte Carlo,  Journal of Complexity 2009. \n\n[6] Shravas Rao. A Hoeffding inequality for Markov Chains.  Electronic communications in Probability 2019. \n\n[7] Bartlett and Mendelson. \"Rademacher and Gaussian Complexities: Risk Bounds and Structural Results\" 2002. \n\n[8] Anthony and Bartlett. Neural Network Learning: Theoretical foundations. 1999. \n\n[9] Wolfer and Kontorovich. Estimating the mixing time of ergodic Markov chains. 2019 COLT. \n\n\n\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a very solid, very high-quality paper overall. \n\nStrengths: \n1. The breadth of the results and the systematic approach to the treatment. A lot is covered and it represents a lot of work for the authors that required extreme proficiency with difficult topics. The results are as strong as possible and very general. \n2. Applicability: this is a highly fundamental problem and the potential for further research (mostly on specific models) is great. This paper will get cited. \n\n\nWeaknesses: \n\n1. The readability and presentation could definitely be improved. Several results are just there in the supplementary without any proper explanation of the context. I am thinking of sections 2.2 and 2.3 in the main supplementary in particular. There is nothing about what the results mean.  In addition, the actual main paper is useless without the supplementary unless one is completely familiar with the complex baroque and overly general style of [1]. \n2. There are notations that are not properly introduced (see \"questions\"), making readability more problematic. Reader friendliness is, therefore, a definite issue. There are also parts of proofs that follow [1] very closely without disclosing the corresponding result despite it having the potential to make it easier for the reader.  \n3. I believe there are two MINOR ERRORS, including one with the numerical constants involved in several theorems (see \"questions\" section), and the proof of what is pretty much the main theorem is far from complete.\n4. (Very slight) It is a lot of abominable bookkeeping but I couldn't spot a truly original proof technique (not that this should be grounds for rejection of course). \n\n\nRegarding 1 and 2, I think it would be helpful to have a graph of dependencies between the sections,  and a table with equivalents from the literature.  Here is a tentative, non exhaustive list of correspondences:\n\nTheorem 5 (p 4) = Theorem 4 in [1], page 12. \nTheorem 6 (p4) = Theorem 5 in [1]\nTheorem 10 (p6) = THeorem 7 page 24 of [1]\nTheorem 3 (proof on page 29) = Theorem 2 in [1]\nLemma 26 p37: cf. Theorem 5 page 16 of [1]\n\n\n\n\n\n=======================================\nReferences:\n\n\n[1] V. Koltchinskii and D. Pachenko. \"Empirical margin distributions and bounding the generalization error of combined classifiers\", Annals of stats 2002. \n\n[2] Jianqing Fan, Bai Jiang, Qiang Sun. \"Hoeffding's inequality for general Markov chains and applications to statistical learning.\", JMLR 2021\n\n[3] Daniel Paulin. \"Concentration inequalities for Markov chains by Marton Couplings and spectral methods\", electronic journal of Probability 2015. \n\n[4] Ledoux and Talagrand. Probability in Banach spaces. \n\n[5] D. Rudolf. Explicit error bounds for Markov chain Monte Carlo. (arxiv 2011)//Explicit error bounds for lazy reversible Markov chain Monte Carlo,  Journal of Complexity 2009. \n\n[6] Shravas Rao. A Hoeffding inequality for Markov Chains.  Electronic communications in Probability 2019. \n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_tkSpIYazJV", "reviewer": "Reviewer_pV3G", "summary": "The submission extends Rademacher and Gaussian complexity generalization bounds from iid data to Markov Chains. The resulting bounds for neural networks are also provided and then extended to Bayesian neural networks. Extensions to m-order Markov Chains and mixtures of Markov chains are given in the appendix.", "questions": "See the previous section", "limitations": "See the weaknesses section", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have read other papers and worked on theory of Markov Chains but still had a hard time following and verifying the results. I am voting for rejection but this is a low-confidence review as I might have misunderstood the terminology and notation. The techniques appear general and, if correct, could help for extending results other than Rademacher complexity to Markov Chains. The current manuscript is however hard to follow and it will benefit from reorganization and other revisions that I will elaborate on below.\n\n1. In line 74, what does $\\nu << \\pi$ mean for start distribution $\\nu$ and stationary distribution $\\pi$? If this is a comparison, how are these distributions compared? In Eq (5) below it, what is $dv/d\\pi$? $v$ is not defined. If this is $\\nu$, does this mean that the start distribution is a function of the stationary distribution?\n\n2. I think the paper should shift its focus from neural networks to a general machine learning model. The title and introduction emphasize the generalization bound on deep learning yet the main result (Theorem 2) is for a general model. The extension to deep learning (Theorem 3) is in fact a corollary of the previous theorem. In the iid setting there is a vast literature on measures of complexity special to neural networks which the authors can follow-up on if they want to focus on deep learning. A good starting point is [1] although there has been a substantial amount of work after this review.\n\n3. One of the paper's main contributions is extensions beyond simple Markov Chain models (Section 4). This section has only one paragraph in the main paper and all the results are moved to the appendix. The required space for bringing these results in the main paper can be freed up by making some of the short Equations (7) up to (17) in Section 2 inline and reducing the whitespace.\n\n4. There are other techniques e.g. [2] and Section 3 in [3] for extending results from iid to Markov Chain using mixing time. While this previous work is not about Rademacher complexity and generalization I wonder in what ways the underlying techniques are similar or different from the submission.\n\nMinor comments:\n\n(i) I suggest defining \"Polish space\" in line 55 and g* in line 60 \n\n(ii) The formulation of neural network in Section 3.2 is a bit confusing. See [1] for an example of a more standard notation.\n\n\n[1] Behnam Neyshabur, \"Implicit Regularization in Deep Learning.\" PhD thesis, 2017\n\n[2] Duchi, John C., et al. \"Ergodic mirror descent.\" SIAM Journal on Optimization (2012)\n\n[3] Wang, Gang, Bingcong Li, and Georgios B. Giannakis. \"A multistep Lyapunov approach for finite-time analysis of biased stochastic approximation.\" arXiv (2019).\n\n-------------------------------------------------------\nUpdate after discussions:\n\nThanks for the clarifications. I could go through the main result and its proof in the appendix after these clarifications and changed my vote to accept. The initial score was tentative.\n\nI still strongly believe the paper should assume less about the reader's background in this part of measure theory. Perhaps the current definitions are adequate for a paper in a statistics journal, but a large part of NeurIPS audience whose research is related to generalization and can benefit from this result will have trouble following this paper. Even more fundamental measure theoretic concepts are often named or fully defined in machine learning papers. This is something that can be fixed in camera-ready and I do not want to lower my score because of it but it worries me that the initial rebuttal (before update) insisted on not incorporating this change and no revision has been submitted so far.\n\nThe stationary assumption is fine to me although I do share reviewer MmSs's concern about organization.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ES9Xoyi3tJu", "reviewer": "Reviewer_MmSs", "summary": "This work uses recent high dimensional symmetrization inequalities to extend existing i.i.d. generalization bound approaches to prove new generalization error bounds for machine learning on Markov datasets. An approach is proposed to extend generalization bounds to Bayesian settings. ", "questions": "none", "limitations": "While the authors motivate the problem by observing that many real world datasets consist of time series data instead of i.i.d. samples, the results are severely limited by assuming stationarity of the Markov chain. In fact, to my knowledge, none of the motivating applications listed in the introduction typically statisfy this property. I would have liked to see a better and more complete motivation for considering stationary Markov chains from the machine learning literature.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper addresses generalization bounds in the setting where data is generated by a Markov chain, a setting which to my knowledge has not previously been treated in the literature.\n\nWeaknesses: \nStationary assumption: While the authors motivate the problem by observing that many real world datasets consist of time series data instead of i.i.d. samples, the results are severely limited by assuming stationarity of the Markov chain. In fact, to my knowledge, none of the motivating applications listed in the introduction typically statisfy this property. I would have liked to see a better and more complete motivation for considering stationary Markov chains from the machine learning literature.\n\nPresentation:\nSection 4 appears to be unfinished, without even a theorem statement - the way it points to a corresponding vastly expanded section in the supplement is troubling as it appears to be an attempt to bypass the main paper page limit. Given the higher-order results are critical to the contribution of the paper, Section 3 should have been greatly condensed so Section 4 could be expanded and fit the page limit. Furthermore, the supplement is not written as such, it almost looks as if that is the real main paper and the \"main paper\" is just a haphazard and inefficient extraction of portions of it - see the many sections that are present in both almost verbatim. The supplement should instead be essentially a collection of appendices well-tied to the main paper. \n\nMinor: \nLine 15: [27] is a book, not \"seminar papers\"\n\nLine 47 should be clarified: [29] did not \"introduce Bayesian deep learning\", see citations in [29] for instance.\n\nLine 156: Presumably there are l layers of neurons, not \"V\".\n\n---------------------------------------\nEdit after rebuttal: Unfortunately the authors do not acknowledge my significant concerns with the presentation and in general do not promise or implement any changes to the paper. I cannot recommend acceptance of this work as-is.\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept