Generalization bounds for mixing processes via delayed online-to-PAC conversions

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:36:57

Abstract: We study the generalization error of statistical learning algorithms in a non-i.i.d. setting, where the training data is sampled from a stationary mixing process. 
We develop an analytic framework for this scenario based on a reduction to online learning with delayed feedback. In particular, we show that the existence of an online learning algorithm with bounded regret (against a fixed statistical learning algorithm in a specially constructed game of online learning with delayed feedback) implies low generalization error of said statistical learning method even if the data sequence is sampled from a mixing time series. The rates demonstrate a trade-off between the amount of delay in the online learning game and the degree of dependence between consecutive data points, with near-optimal rates recovered in a number of well-studied settings when the delay is tuned appropriately as a function of the mixing time of the process.

Main paper: 
 introduction: 
 In machine learning, generalization denotes the ability of a model to infer patterns from a datasetof training examples and apply them to analyze previously unseen data (Shalev-Shwartz and Ben-David, 2014) . The gap in accuracy between the model's predictions on new data and those on the training set is usually referred to as generalization error. Providing upper bounds on this quantity is a central goal in statistical learning theory. Classically, bounds based on notions of complexity (e.g., VC dimension and Rademacher complexity) for the model's hypothesis space were used to provide uniform worst-case guarantees (see Bousquet et al., 2004; Vapnik, 2013; Shalev-Shwartz and Ben-David, 2014) . However, results of this kind are often too loose to be applied to the most common machine learning over-parameterised models, such as deep neural networks (Zhang et al., 2021) . As a consequence, several approaches have been proposed to obtain algorithm-dependent generalization bounds, which can adapt to the problem and be much tighter in practice than their uniform counterparts. Often, the underlying idea is that if the algorithm's output does not have a too strong dependence on the specific input dataset used for the training, then the model should not be prone to overfitting, and so generalize well. Examples of results that build onto these ideas are stability bounds, information-theoretic bounds, and PAC-Bayesian bounds (see, e.g., Bousquet and Elisseeff, 2002; Russo and Zou, 2020; Hellström et al., 2023; Alquier, 2024) .Most results in the literature focus on the i.i.d. setting, where the training dataset is made of independent draws from some underlying data distribution. However, for several applications, this assumption is far from realistic. For instance, it excludes the case where observations received by the learner have some inherent temporal dependence, as it is the case for stock prices, daily energy consumption, or sensor data from physical environments (Ariyo et al., 2014; Takeda et al., 2016) . This calls for the development of theory for addressing non-i.i.d. data. A common approach in the extant literature is to consider a class of non-i.i.d. data-generating processes usually referred to as stationary β-mixing or φ-mixing processes. This assumption, together with a "blocking" trick introduced by Yu (1994) , has led to a few results in the literature: Meir (2000) , Mohri and Rostamizadeh (2008) , Shalizi and Kontorovich (2013) , and Wolfer and Kontorovich (2019) provided uniform worst-case generalization bounds, Steinwart and Christmann (2009) and Agarwal and Duchi (2012) discussed excess risk bound (comparing the algorithm's output with the best possible hypothesis), while Mohri and Rostamizadeh (2010) gave bounds based on a stability analysis (in the sense of Bousquet and Elisseeff, 2002) .Here, we propose propose results for the non-i.i.d. setting in the form of PAC-Bayesian bounds (Guedj, 2019; Alquier, 2024) : high probability upper bounds on the expected generalization error of randomized learning algorithms. We achieve this by combining the "blocking" argument by Yu (1994) to manage the concentration of sums of correlated random variables, with the recent online-to-PAC conversion technique recently proposed by Lugosi and Neu (2023) . Using their framework we show a new way to obtain generalization bounds for stationary dependent processes that satisfy a certain "short-memory" property (intuitively meaning that data points that are closer in time are more heavily dependent on each other). Our assumption slightly differs from β-mixing in the sense that we only need it to hold for a specific class of bounded loss functions. Among other results, this allows us to prove PAC-Bayesian generalization bounds for mixing processes. This complements previous work on such bounds that have only considered mild relaxations of the i.i.d. condition such as assuming that the data has a martingale structure (see, e.g., Seldin et al., 2012; Chugg et al., 2023; Haddouche and Guedj, 2023) . Notable exceptions are the works of Alquier and Wintenberger (2012 ), Alquier et al. (2013 ), and Eringis et al. (2022 , 2024) , who provided generalization bounds for a sequential prediction setting where both the data-generating process and the hypothesis class used for prediction are stable dynamical systems. Their results are proved under some very specific conditions on these systems, and their guarantees involve unspecified problem-dependent constants that may be large. In contrast, our bounds hold under general, simple-to-verify conditions and feature explicit constants.The rest of the paper is organized as follows. In Section 2 we properly define the generalization error of a statistical learning algorithm for both i.i.d. and non-i.i.d. cases, and state our main assumption on the data dependence. Our main contribution lies in Section 3, where after recalling the results for the i.i.d. setting we show how to adapt this to stationary mixing processes. In Section 4 we provide concrete results of the bounds we can obtain through the online-to-PAC conversion. Finally in Section 5 we extend our results to the setting where the hypothesis class itself may consist of dynamical systems.Notation. For a distribution over hypotheses P ∈ ∆ W and bounded function f : W → R we write ⟨P, f ⟩ to refer to the expectation ofE W ∼P [f (W )]. We denote D KL (P ||Q) = E X∼P ln P (X) Q(X)to refer to the Kullback-Leibler divergence. We use ||.|| to denote a norm on the Banach space Q of the finite signed measures, and ||.|| * the corresponding dual norm on the dual space Q * of measurable functions f on W such that ||f || * = sup Q∈Q:||Q||≤1 ⟨Q, f ⟩. 
preliminaries: 
 The classical statistical learning framework usually considers a dataset S n = (Z 1 , ..., Z n ), made of n i.i.d. elements drawn from a distribution µ over a measurable instance space Z. Often, one can think of each Z i as a feature-label pair (X i , Y i ). Furthermore, we are given a measurable class W of hypotheses and a loss function ℓ : W ×Z → R + , with ℓ(w, z) measuring the quality of the hypothesis w ∈ W on the data instance z ∈ Z. For any given hypothesis w ∈ W, two key objects of interest arethe training error L(w, S n ) = 1 n n i=1 ℓ(w, Z i ) and the test error L(w) = E Z ′ ∼µ [ℓ(w, Z ′ )],where the random element Z ′ has the same distribution as Z i and is independent of S n .A learning algorithm A : Z n → W maps the training sample to an hypothesis in W. More generally, we will focus on randomized learning algorithms, returning a probability distribution P Wn|Sn ∈ ∆ W over W, conditionally on S n (deterministic algorithms can be recovered as special cases, whose the outputs are Dirac distributions). The ultimate goal of the learner is to minimize the test error. Yet, this quantity cannot be computed without knowledge of the data generating distribution µ. In practice, one typically relies on the training error in order to gauge the quality of the algorithm. For an algorithm A :S n → P Wn|Sn , we define the generalization error as the expected gap between training and test error:Gen(A, S n ) = E L(W n ) -L(W n , S n ) S n .The expectation in the above expression integrates over the randomness in the output of the algorithm W n ∼ P Wn|Sn , conditionally on the sample S n . We remark that the test error is not equal to the mean of the training error, due to the dependence of W n on the training data.We extend the previous setting by considering the case where the data have an intrinsic temporally ordered structure, and come in the form of a stationary process (Z t ) t∈N * ∼ ν. Formally, we assume that the joint marginal distribution of any block (Z t , Z t-1 , . . . , Z t-i ) is the same as the distribution of (Z t+j , Z t+j-1 , . . . , Z t+j-i ) for any t, i and j, but the data points are not necessarily independent of each other. In particular, the marginal distribution of Z t is constant and is denoted by µ. Thus, it is natural to continue to use the definition of the test loss and generalization error given above, although with the understanding that µ now refers to the marginal distribution of an independent copy of Z 1 , a sample point from a stationary non-i.i.d. process. We remark here that other notions of the test loss may also be considered, and the framework that we propose can be extended to most natural definitions with little work (but potentially large notational overhead). In Section 5, we provide such an extension for a more general setting where the hypotheses themselves are allowed to have memory and the process may not be as strongly stationary as our assumption above requires.In order to obtain generalization results we need to have some control on how strong the dependencies between different datapoints are allowed to be. To this regard, we consider the following assumption.Assumption 1. There exists a non-increasing sequence (ϕ d ) d∈N * of non-negative real numbers such that, for all w ∈ W and all t ∈ N * :E L(w) -ℓ(w, Z t ) F t-d ≤ ϕ d , where L(w) = E Z ′ ∼µ [ℓ(w, Z ′ )],with Z ′ being independent on the process (Z t ) t∈N * and having as distribution the stationary marginal µ of the Z t .The intuition behind this assumption is that the loss associated with the observations Z t becomes almost independent of the past after d steps, enabling us to treat each sequence of the form (Z t , Z t+d , . . . , Z t+(n-t)d ) as an approximately i.i.d. sequence. Note that this assumption differs from the usual β-mixing assumption which requires the distribution of Z t |F t-d to be close to the marginal distribution µ for all t, in terms of total variation distance. Our assumption is somewhat weaker in the sense that it only requires the expected losses under these distributions to be close, and only a one-sided inequality is required. It is easy to verify that our assumption is satisfied if the process is β-mixing in the usual sense and the losses are bounded in [0, 1]. 
proving generalization bounds via online learning: 
 Online learning focuses on algorithms that aim to improve performance incrementally as new information becomes available, often without any underlying assumption on how data are generated.The online learner's performance is typically measured leveraging the idea of regret. This involves introducing a cost function for the problem and defining the regret as the difference between the cumulative cost of the online learner and that of a fixed comparator. We refer to the monographs Cesa-Bianchi and Lugosi, 2006 and Orabona, 2019 for comprehensive overviews on online learning and regret analysis. Recently, Lugosi and Neu (2023) established a connection between upper bounds on the regret and generalization bounds, showing that the existence of a strategy with a bounded regret in a specially designed online game translates into a generalization bound, via a technique dubbed online-to-PAC conversion. Their focus is on the i.i.d. setting, where the training dataset is made of independent draws. Here, we show that this framework can naturally be extended beyond the i.i.d. assumption.In what follows, we briefly review the setup of Lugosi and Neu (2023) in Section 3.1 and then describe our new extension of their model to the non-i.i.d. case in Section 3.2. In particular, we prove a high-probability bound for the generalization error of any statistical learning algorithm learnt with a stationary mixing process verifying Assumption 1.3.1 Online-to-PAC conversions for i.i.d. data Lugosi and Neu (2023) have recently established a framework to obtain generalization bounds via a reduction to online learning. Their technique allows to recover several classic PAC-Bayesian results, and provide a range of generalizations thereof. The main idea of Lugosi and Neu (2023) is to introduce an online learning game called the generalization game, where the following steps are repeated for a sequence of rounds t = 1, 2, . . . , n:• the online learner picks a distribution P t ∈ ∆ W ;• the adversary selects the cost function c t : w → ℓ(w, Z t ) -L(w);• the online learner incurs the cost ⟨P t , c t ⟩ = E W ∼Pt [c t (W )];• Z t is revealed to the learner.The learner can adopt any strategy to pick P t , but they can only rely on past knowledge to make their prediction. Explicitly, if F t denotes the sigma-algebra generated by Z 1 , ..., Z t , then P t has to be F t-1 -measurable. We also emphasize that in this setup the online learner is allowed to know the loss function ℓ and the distribution µ of the data points Z t , and therefore by revealing the value of Z t , the online learner may compute the entire cost function c t .We define the regret of the online learner against the possibly data-dependent comparator P * ∈ ∆ W as Regret(P * ) = n t=1 ⟨P t -P * , c t ⟩. Now,EQUATIONThe first of these terms correspond to the regret of the online learner against a fixed comparator strategy that picks P Wn|Sn at each step. The second term is a martingale and can be bounded in high probability with standard concentration tools. Indeed, since P t is chosen before Z t is revealed, one can easily check that E[⟨P t , c t ⟩|F t-1 ] = 0. Thus, to prove a bound on the generalization error of the statistical learning algorithm, it is enough to find an online learning algorithm with bounded regret against P Wn|Sn in the generalization game.As a concrete application of the above, the following generalization bound is obtained when picking the classic exponential weighted average (EWA) algorithm (Vovk, 1990; Littlestone and Warmuth, 1994; Freund and Schapire, 1997) as online strategy, and plugging its regret bound into (1).Theorem 2 (Corollary 6 in Lugosi and Neu, 2023) . Suppose that ℓ(w, z) ∈ [0, 1] for all w, z. Then, for any P 1 ∈ ∆ W and η > 0, with probability at least 1 -δ on the draw of S n , uniformly on every learning algorithm A : S n → P Wn|Sn , we haveGen(A, S n ) ≤ D KL (P Wn|Sn ||P 1 ) ηn + η 2 + 2 log 1 δ n .Proof. We can bound each term of (1) separately. A data-dependent bound for the regret term is obtained via a direct application of the regret analysis of EWA which brings the termD KL (P Wn |Sn ||P1) ηn + η 2 (see Appendix B.1). The term 2 log( 1 δ )n results from bounding the martingale M n via an application of Hoeffding-Azuma inequality.Note that the first term in the above bound is data-dependent due to the presence of P Wn|Sn , and thus optimizing it requires a data-dependent choice of η, which is not allowed by Theorem 2. However, via a union bound argument it is possible to get a bound in the formGen(A, S n ) = O D KL (P Wn|Sn ||P 1 ) n + 1 n log log n δ ,For the details, we refer to the proof of Corollary 5 of Lugosi and Neu (2023) , which recovers a classical PAC-Bayes bound of McAllester (1998).In what follows, we will drop the i.i.d. assumption for the data, and instead consider non-i.i.d. sequences satisfying Assumption 1. For this setting we define the following variant of the generalization game.Definition 1 (Generalization game with delay). The generalization game with delay d ∈ N * is an online learning game where the following steps are repeated for a sequence of rounds t = 1, ..., n:• the online learner picks a distribution P t ∈ ∆ W ;• the adversary selects the cost function c t : w → ℓ(w, Z t ) -L(w);• the online learner incurs the cost⟨P t , c t ⟩ = E W ∼Pt [c t (W )]; • if t ≥ d, Z t-d+1 (and thus c t-d+1) is revealed to the learner.The main difference between our version of the generalization game and the standard one of Lugosi and Neu (2023) is the introduction of a delay on the online learning algorithm's decisions. Specifically, we will force the online learner to only take information into account up to time t -d when picking their action P t . Clearly, setting d = 1 recovers the original version of the generalization game with no delay.It is easy to see that the regret decomposition of Theorem 1 still remains valid in the current setting.The purpose of introducing the delay is to be able to make sure that the termM n = -1 n n t=1 ⟨P t , c t ⟩is small. The lemma below states that the increments of M n behave similarly to a martingaledifference sequence, thanks to the introduction of the delay.Lemma 1. Fix d ∈ [[1, n]].Under assumption 1, it holds for all t ∈ [[1, n]]:E[⟨-P t , c t ⟩|F t-d ] ≤ ϕ d .where P t and c t are defined as in 1.Proof. Proposition 1 (Bound in expectation). Consider (Z t ) t∈N * satisfying Assumption 1 and suppose there exists a d-delayed online learning algorithm with regret bounded by Regret d,n (P * ) against any comparator P * . Then, the expected generalization of A is bounded asSince P t is F t-d -measurable we have E[⟨-P t , c t ⟩|F t-d ] = ⟨P t , E[-c t |F t-d ]⟩ ≤ ϕ d ,E [Gen(A, S n )] ≤ E Regret d,n (P Wn|Sn ) n + ϕ d . Proof. By Theorem 1, it holds that E[Gen(A, S n )] = E[Regret d,n (P Wn |Sn )] n + E[M n ],where the regret is for a strategy P t in the delayed generalization game. Hence, by Lemma 1E[M n ] = E - 1 n n t=1 ⟨P t , c t ⟩ = 1 n n t=1 E[⟨-P t , c t ⟩] = 1 n n t=1 E [E[⟨-P t , c t ⟩|F t-d ]] ≤ ϕ d ,which proves the claim.The above result holds in expectation over the training sample. We now provide a high-probability guarantee on the generalization error.Theorem 3 (Bound in probability). Assume that (Z t ) t∈N * satisfies Assumption 1 and consider a d-delayed online learning algorithm with regret bounded by R d,n (P * ) against any comparator P * .Then, for any δ > 0, it holds with probability 1 -δ on the draw of S n , uniformly for all A,Gen(A, S n ) ≤ R d,n (P Wn|Sn ) n + ϕ d + 2d log d δ n .The proof of this claim follows directly from combining the decomposition of Theorem 1 with a standard concentration result for mixing processes that we state below. n] ] and consider (Z t ) t∈N * satisfying Assumption 1. Consider the generalization game of Definition 1. Then, for any δ > 0, the following bound is satisfied with probability at least 1 -δ:Lemma 2. Fix d ∈ [[1,M n ≤ ϕ d + 2d log d δ n .The proof is based on a classic "blocking" technique due to Yu (1994) . For the sake of completeness, we provide a proof in Appendix A.2.4 New generalization bounds for non-i.i.d. dataThe dependence on the delay d for the bounds that we presented in the previous section is non-trivial.Indeed, if on the one hand increasing the delay will reduce the magnitude of ϕ d , on the other hand the regret of the online learner will grow with d. There is hence a trade-off between these two terms appearing in our bounds. In what follows, we derive some concrete generalization bounds from Theorem 3, under a number of different choices of the online learning algorithm. For concreteness, we will consider two types of mixing assumptions, but stress that the approach can be applied to any process that satisfies Assumption 1. 
regret bounds for delayed online learning: 
 From Theorem 3, we can obtain a generalization bound using our framework if we have a regret bound for a delayed online algorithm. This is a well-known problem in the area of online learning (see, e.g., Weinberger and Ordentlich, 2002; Joulani et al., 2013) . In the following, we will leverage the following simple trick that allows us to extend the regret bounds of any online learning algorithm to its delayed counterpart, provided that the regret bound respects some specific assumptions.Lemma 3 (Weinberger and Ordentlich, 2002) . Consider any online algorithm whose regret satisfies The proof idea is closely related to the blocking trick of Yu (1994) , with an algorithmic construction that runs one instance of the base method for each index i = 1, 2, . . . , d, with the i-th instance being responsible for the regret in rounds i, i + d, i + 2d, . . . (more details are provided in Appendix B.3).For most of the regret bounds that we consider, the function R takes the formR(n) = O( √ n), sothat the first term in the generalization bound is typically of order d/n. Since this term matches the bound on M n in Lemma 2, in this case the final generalization bound behaves effectively as if the sample size was n/d instead of n.The following definition gives two concrete examples of mixing processes that satisfy Assumption 1 with different choices of ϕ d , and are commonly considered in the related literature (see, e.g., Mohri and Rostamizadeh, 2010, Levin and Peres, 2017) .Definition 2. We say that a stationary process (Z t ) t∈N * satisfying Assumption 1 is:• geometrically mixing, if ϕ d = Ce -d τ , for some positive τ and C;• algebraically mixing, if ϕ d = Cd -r , for some positive r and C.Instantiating the bound of Theorem 3 to these two cases yields the following two corollaries.Corollary 1. Assume (Z t ) t∈N * is a geometrically mixing process with constants τ, C > 0. Consider a d-delayed online learning algorithm with regret bounded by R d,n (P * ) for all comparators P * .Then, setting d = ⌈τ log n⌉, for any δ > 0, with probability at least 1 -δ we have that, uniformly for any algorithm A,Gen(A, S n ) ≤ R d,n (P Wn|Sn ) n + C n + 2 (τ log n + 1) log τ log n+1 δ n .Up to a term linear in τ and some logarithmic factors, the above states that under the geometric mixing the same rates are achievable as in the i.i.d. setting. Roughly speaking, this amounts to saying that the effective sample size is a factor τ smaller than the original number of samples n, as long as generalization is concerned.Corollary 2. Assume (Z t ) t∈N * is an algebraic mixing process with constants r, C > 0. Consider a d-delayed online learning algorithm with regret bounded by R d,n (P * ) against any comparator 1+2r) , for any δ > 0, with probability at least 1 -δ we have that, uniformly for any algorithm A, 1+2r) .P * . Then, setting d = C 2 n 1/(Gen(A, S n ) ≤ R d,n (P Wn|Sn ) n + C 1 + log(d/δ) n -2r 2(This result suggests that the rates achievable for algebraically mixing processes are qualitatively much slower than what one can get for i.i.d. or geometrically mixing data sequences (although the rates do eventually approach 1/ √ n as r goes to infinity).We start our discussion on possible online strategies by focusing on the classic exponential weighted average (EWA) algorithm (Vovk, 1990; Littlestone and Warmuth, 1994; Freund and Schapire, 1997) .We fix a data-free prior P 1 ∈ ∆ W and a learning rate parameter η > 0. We consider the updatesP t+1 = arg min P ∈∆ W ⟨P, c t ⟩ + 1 η D KL (P ||P t ) ,Combining the standard regret bound of EWA (see Appendix B.1) with Lemma 3 and Corollary 1 yields the result that follows.Corollary 3. Suppose that (Z t ) t∈N * is a geometric mixing process with constants τ, C > 0. Suppose that ℓ(w, z) ∈ [0, 1] for all w, z. Then, for any P 1 ∈ ∆ W and any δ > 0, with probability at least 1 -δ, uniformly on any learning algorithm A we haveGen(A, S n ) ≤ D KL (P * ||P 1 )(τ log n + 1) ηn + η 2 + C n + 2 (τ log n + 1) log τ log n+1 δ n .This results suggests that when considering geometric mixing processes, by applying a union bound over a well-chosen range of η we recover the PAC-Bayes bound of McAllester (1998) up to a O( √ τ log n) factor. A similar result can be derived from Corollary 2 for algebraically mixing processes, leading to a bound typically scaling as n -2r/(2(1+2r)) .In this subsection we extend the common class of online learning algorithms known as follow the regularized leader (FTRL, see e.g., Abernethy and Rakhlin, 2009; Orabona, 2019) to the problem of learning with delay. FTRL algorithms are defined using a convex regularization function h : ∆ W → R. We restrict ourselves to the set of proper, lower semi-continuous and α-strongly convex functions with respect to a norm ||.|| (and its respective dual norm ||.|| * ) defined on the set of signed finite measures on W (see Appendix B.2 for more details). The online procedure (without delay) of the FTRL algorithm is as follows:P t+1 = arg min P ∈∆ W t s=1 ⟨P, c s ⟩ + 1 η h(P ) .The existence of the minimum is guaranteed by the compactness of ∆ W under ∥•∥, and its uniqueness is ensured by the strong convexity of h. Combining the analysis of FTRL (see Appendix B.2) with Lemma 3 and Corollary 1 yields the following result.Corollary 4. Suppose that (Z t ) t∈N * is a geometric mixing process with constants τ, C > 0. Suppose that ℓ(w, z) ∈ [0, 1] for all w, z. Assume there exists B > 0 such that for all t, ||c t || * ≤ B. Then, for any P 1 ∈ ∆ W , for any δ > 0 with probability at least 1 -δ on the draw of S n , uniformly for all A,Gen(A, S n ) ≤ (h(P * ) -h(P 1 )) (τ log n + 1) ηn + ηB 2 2α + C n + 2 (τ log n + 1) log τ log n+1 δ n .This generalization bound is similar to the bound of Theorem 9 of Lugosi and Neu (2023) up to a O( √ τ log n) factor, when applying a union-bound argument over an appropriate grid of learning-rates η. In particular, this result recovers PAC-Bayesian bounds like those of Corollary 3 when choosing h = D KL (•∥P 1 ). We refer to Section 3.2 in Lugosi and Neu (2023) for more discussion on such bounds. As before, a similar result can be stated for algebraically mixing processes, with the leading terms approaching zero at rate of n -2r/2(1+2r) instead of n -1/2 . 
generalization bounds for dynamic hypotheses: 
 Finally, inspired by the works of Eringis et al. (2022 Eringis et al. ( , 2024)) , we extend our framework to accommodate loss functions ℓ that rely not only on the last data point Z t , but on the entire data sequence Z t = (Z t , Z t-1 , . . . , Z 1 ). Formally, we will consider loss functions of the form ℓ : W × Z * → R + 1 and write ℓ(w, z t ) to denote the loss associated with hypothesis w ∈ W on sequence z t ∈ Z t . This consideration extends the learning problem to class of dynamical predictors such as Kalman filters, autoregressive models, or recurrent neural networks (RNNs), broadly used in time-series forecasting (Ariyo et al., 2014; Takeda et al., 2016) . Specifically, if we think of z t = (x t , y t ) as a data-pair of context and observation, in time-series prediction we usually not only rely on the context x t but also on the past sequence of contexts and observations (x t-1 , y t-1 , . . . , x 1 , y 1 ). As an example, consider ℓ(w, z t , . . . , z 1 ) = 1 2 (y t -h w (x t , z t-1 , . . . , z 1 )) 2 where h ∈ H is a function class parameterized by W. For this type of loss function a natural definition of the test error is:L(w) = lim n→∞ E[ℓ(w, Z ′ t , Z ′ t-1 , ..., Z ′ t-n )],whereZ ′ t = (Z ′ t , Z ′ t-1 , . . .) is a semi-infinite random sequence drawn from the same stationary process that has generated the data Z t . We consider the following assumption.Assumption 2. For a given process (Z t ) t∈Z with joint-distribution ν over Z Z and same marginals µ over Z, there exists a non-increasing sequence (ϕ d ) d∈N * of non-negative real numbers such that the following holds for all w ∈ W, for all t ∈ N * :E ℓ(w, Z t , . . . , Z 1 ) -L(w) F t-d ≤ ϕ d .This is a generalization of Assumption 1 in the sense that taking ℓ(w, Z t , . . . , Z 1 ) = ℓ(w, Z t ) simply amounts to requiring the same mixing condition as before. For our online-to-PAC conversion we consider the same framework as in Definition 1, except that now the cost function is defined asc t : w → ℓ(w, Z t , . . . , Z 1 ) -L(w) .Then it easy to check that result of Lemma 2 still holds for this specific cost, and we can thus extend all the results of Section 4. For concreteness, we state the following adaptation of Theorem 3 below.Theorem 4. Assume (Z t ) t∈Z which satisfies Assumption 2 and consider a d-delayed online learning algorithm with regret bounded by R d,n (P * ) against any comparator P * . Then, for any δ > 0, it holds with probability 1 -δ:Gen(A, S n ) ≤ R d,n (P Wn|Sn ) n + ϕ d + 2d log d δ n .To see that Assumption 2 can be verified and the resulting bounds can be meaningfully applied, consider the following concrete assumptions about the hypothesis class, the loss function, and the data generating process. The first assumption says that for any given hypothesis, the influence of past data points on the associated loss vanishes with time (i.e., the hypothesis forgets the old data points at a controlled rate).Assumption 3. There exists a decreasing sequence (B d ) d∈N * of non-negative real numbers such that for any two sequences z t = (z t , . . . , z i ) and z ′ t = (z ′ t , . . . , z ′ j ) of possibly different lengths thatsatisfy z k = z ′ k for all k ∈ t, . . . , t -d + 1, we have |ℓ(w, z t ) -ℓ(w, z ′ t )| ≤ B d , for all w ∈ W.This condition can be verified for stable dynamical systems like autoregressive models, certain classes of RNNs, or sequential predictors that have bounded memory by design (see Eringis et al., 2022 Eringis et al., , 2024)) . The next assumption is a refinement of Assumption 1, adapted to the case where the loss function acts on blocks of d data points z t-d+1:t = (z t , z t-1 , . . . , z t-d+1 ).Assumption 4. Let Z t = (Z t , . . . , Z 1 ) be a sequence of data points and letZ ′ t = (Z ′ t , . . . , Z ′ 0 , . . . )be an independent copy of the same process. Then, there exists a decreasing sequence (β d ) d∈N * non-negative real numbers such that the following is satisfied for all hypotheses w ∈ W and alld ∈ N * : E ℓ(w, Z ′ t-d+1:t ) -ℓ(w, Z t-d+1:t ) F t-2d ≤ β d .This assumption can be verified whenever the loss function is bounded and the joint distribution of the data block Z t-d+1:t satisfies a β-mixing assumption. In more detail, this latter condition amounts to requiring that the conditional distribution of each data block given a block that trails d steps behind is close to the marginal distribution in total variation distance, up to an additive term of β d . The following proposition shows that these two simple conditions together imply that Assumption 2 holds, and that thus the bound of Theorem 4 can be meaningfully instantiated for bounded-memory hypothesis classes deployed on mixing processes.Proposition 2. Suppose that the loss function satisfies Assumption 3 and the data distribution satisfies Assumption 4. Then Assumption 2 is satisfied withϕ d = 2B d/2 + β d/2 . 
conclusion: 
 We have developed a general framework for deriving generalization bounds for non-i.i.d. processes under a general mixing assumption, via an extension of the online-to-PAC-conversion framework of Lugosi and Neu (2023) . Among other results, this approach has allowed us to prove PAC-Bayesian generalization bounds for such data in a clean and transparent way, and even study classes of dynamic hypotheses under a simple bounded-memory condition. These results provide a clean and tight alternative to the results of (Alquier and Wintenberger, 2012; Eringis et al., 2022) . The generality of our approach further demonstrates the power of the Online-to-PAC scheme of Lugosi and Neu (2023) , and in particular our results provide further evidence that this framework is particularly promising for developing techniques for generalization in non-i.i.d. settings. We hope that flexibility of our framework will find further uses and enables more rapid progress in the area.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: The paper does not include experiments requiring code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: The paper does not include experiments requiring code.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: The paper does not include experiments requiring code.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The contribution is mainly theoretical so we do not discuss these issues in the paper.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: the paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 The proof of Theorem 1Let (P t ) n t=1 ∈ ∆ n W be the predictions of an online learner playing the generalization game. ThenGen(A, S n ) = 1 n n t=1 E[ℓ t (W n ) -L(W n )|S n ] = - 1 n n t=1 E[c t (W n )|S n ] = - 1 n n t=1 ⟨P Wn|Sn , c t ⟩ = 1 n n t=1 ⟨P t -P Wn|Sn , c t ⟩ - 1 n n t=1 ⟨P t , c t ⟩ = Regret n (P Wn|Sn ) n + M n .Assume n = Kd for simplicity:M n = - 1 n n t=1 ⟨P t , c t ⟩ = 1 dK d i=1 K t=1 ⟨-P i+d(t-1) , c i+d(t-1) ⟩We denote X (i) t= ⟨-P i+d(t-1) , c i+d(t-1) ⟩ and we want to bound in high-probability the term1 K K t=1 X (i) t . Let also denote F (i) t = F i+d(t-1) . Then for i ∈ [[1, d]], we can write using Chernoff's technique that for all λ > 0 it holds:P 1 K K t=1 X (i) t ≥ u ≤ E e λ K K t=1 X (i) t e λu ≤ E e λ K K-1 t=1 X (i) t E e λ K X (i) K F (i) K-1 e -λu .Now remark that:E e λ K X (i) K F (i) K-1 = E e λ K (X (i) K -E[X (i) K |F (i) K-1 ]) F (i) K-1 e λ K E[X (i) K |F (i) K-1 ] . If we denote Z = X (i) K -E[X (i) K |F (i) K-1 ] then |Z| ≤ 2 and E[Z|F (i) K-1 ] = 0 so via Hoeffding's lemma: E[e λ K Z ] ≤ e λ 22K 2 . Now by construction of the P t and because of Lemma 1 it follows that for all i, E[X(i) K |F (i) K-1 ] ≤ ϕ d .Repeating the same reasoning for each term of the sum yields:P 1 K K t=1 X (i) t ≥ u ≤ e λ 2 2K e λϕ d e -λu .Optimzing with λ = K(u -ϕ d ) and taking δ = e -K(u-ϕ) 2 2 it finally holds for any δ > 0, with probability 1 -δ d :1 K K t=1 X (i) t ≤ ϕ d + 2 log d δ K .Thus applying a union bound we have with probability 1 -δ:M n ≤ ϕ d + 2 log d δ K ,which concludes the proof.Suppose without loss of generality that d is even and define d ′ = d/2. For the proof, let Z ′ n be a semi-infinite sequence drawn independently from the same process as Z n . Then, we haveL(w) = lim n→∞ E[ℓ(w, Z ′ t , Z ′ t-1 , ..., Z ′ t-n )] ≤ E[ℓ(w, Z ′ t , Z ′ t-1 , . . . , Z ′ t-d ′ )] + B d ′ ≤ E [ ℓ(w, Z t , Z t-1 , . . . , Z t-d ′ )| F t-2d ′ ] + B d ′ + β d ′ ≤ E [ ℓ(w, Z t , Z t-1 , . . . , Z t-d ′ , . . . , Z 1 )| F t-2d ′ ] + 2B d ′ + β d ′ ≤ E [ ℓ(w, Z t , Z t-1 , . . . , Z 1 )| F t-2d ′ ] + 2B d ′ + β d ′ ,where we used Assumption 3 in the first inequality, Assumption 4 in the second one, and Assumption 3 again in the last step. This proves the statement.Recalling EWA updates we have:P t+1 = arg min P ∈∆ W ⟨P, c t ⟩ + 1 η D KL (P ||P t ) ,where η > 0 is a learning-rate parameter. The minimizer can be shown to exist and satisfies:dP t+1 dP t (w) = e -ηct(w) W e -ηct(w ′ ) dP t (w ′ ), and the following result holds.Proposition 3. For any prior P 1 ∈ ∆ W and any comparator P * ∈ ∆ W the regret of EWA simultaneously satisfies for η > 0:Regret(P * ) ≤ D KL (P * ||P 1 ) η + η 2 n t=1 ||c t || 2 ∞ .We refer the reader to Appendix A.1 of Lugosi and Neu (2023) for a complete proof of the result above.We say that h is α-strongly convex if the following inequality is satisfied for all P, P ′ ∈ ∆ W and all λ ∈ [0, 1]:h(λP + (1 -λ)P ′ ) ≤ λh(P ) + (1 -λ)h(P ′ ) - αλ(1 -λ) 2 ||P -P ′ || 2 .Recalling the FTRL updates:P t+1 = arg min P ∈∆ W t s=1 ⟨P, c s ⟩ + 1 η h(P ) ,the following results holds.Proposition 4. For any prior P 1 ∈ ∆ W and any comparator P * ∈ ∆ W the regret of FTRL simultaneously satisfies for η > 0:Regretn (P * ) ≤ h(P * ) -h(P 1 ) η + η 2α n t=1 ||c t || 2 * .We refer the reader to Appendix A.3 of Lugosi and Neu (2023) for a complete proof of the results above.B.3 Details about the reduction of Weinberger and Ordentlich (2002) For concretenes we formally present how to turn any online learning algorithm into its delayed version.For sake of convenience, assume n = Kd. We denote c(i) t = c i+d(t-1) (for instance c(1) 1 = c 1 is the cost revealed at time d + 1). Then we create d instances of horizon time K of the online learning as follows, for i = 1, . . . , d:• We initializeP (i) 1 = P 0 ,• for each block i of length K we update for t = 1, . . . , K:P (i) t+1 = OL update (c (i) s ) t s=1 .Here OL update refers to the update function of the online learning algorithm we consider which can possibly depend of the whole history of cost functions (e.g., in the case of the FTRL update).• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.Here, Z * denotes the disjoint union Z * = ⊔ t∈N Z t . 


Decision: The authors consider the important problem of developing generalization bounds for stationary mixing processes. This paper uses the recent notion of online-to-PAC conversion, with small modification, together with regret bounds/techniques for online learning with delayed feedback, in order to derive these generalization bounds. This decision is difficult. On the one hand, simplicity of a paper should not be viewed as a bad thing. On the other hand, this work seems premature in that it is not clear how the new generalization error bounds shown here go beyond what was previously known; it feels like the authors simply need to expose a "killer application" to make this work significant.

On the technical side, the present paper simply joins online-to-PAC conversion (i.e., the generalization game) and online learning with delayed feedback. The combination looks straightforward. Various results are presented in the paper, but from my close look I could not identify which results of the authors required technical novelty. The power of the paper comes from previous results on online-to-PAC conversion and previous, well-known-and-understood results from online learning with delayed feedback. As such, the paper feels almost like an application of known results (although, potentially with a nice payoff). Moreover, the authors themselves, in their author response, did not claim technical novelty (multiple reviewers had asked about this).

However, even if new technical tools have not been developed, the paper may still have sufficient merit to be accepted if the results themselves (the new generalization error bounds) are significant. Unfortunately, it is here that the story becomes murky; at this time, for the reasons explained below, I believe the paper is not ready to be accepted.

A first major issue (which was raised in different ways by some reviewers) is the question of how the authors’ Assumption 1 (here, I imagine the case of "geometrically mixing") compares to the assumption of $\beta$-mixing from earlier work; see, e.g., the cited work of Mohri and Rostamizadeh (2008). The authors appear to claim their assumption is weaker in the case of bounded losses since their assumption is at the loss level and one-sided. However, are there actual, non-contrived scenarios of interest where the authors’ assumption truly is weaker? A detailed assumption comparison is in order where, in particular, the authors point out, in some setting of interest, how their new results advance upon what was previously known (here, I mean the new bounds themselves, rather than the proof techniques).

Next, during the discussion period, the authors mentioned that their results improve upon the work of Mohri and Rostamizadeh (2008) in that the authors obtain PAC-Bayesian bounds. However, PAC-Bayesian bounds have previously been shown for beta-mixing processes. See the work of Ralaivola et al. (2010), specifically, Theorem 19. I understand that there are different flavors/forms of PAC-Bayesian bounds, but certainly the authors should be able to engage in a comparison between their bound (Corollaries 3 or 4) and the result of Ralaivola et al. The authors should also see if there are any later works on PAC-Bayesian bounds for non-i.i.d. data.

Finally, the part of the paper that may have the most promise to showcase the authors techniques may well be Section 5, on dynamic hypotheses. Unfortunately, it is unclear how we should view the new results of the authors in light of previous work. There were some brief comments in the Introduction section, which I thought foreshadowed a richer discussion in Section 5. However, Section 5 lacks discussion comparing the authors' results to previous work. In particular, are there applications of interest where the authors results are better than what was previously known? Here, a comparison to the recent works of Eringis et al. and the less-recent works involving Alquier and Wintenberger (/Alquier, Li, Wintenberger) is necessary. For example, for the settings where Eringis et al.'s results also apply, do the authors obtain better results? Next, are there meaningful settings that the authors can handle that cannot be handled by the results of Eringis et al.?
Based on the writing in the Introduction, I feel that the authors know how to do this comparison. Yet, this important comparison was left out of paper.

Overall, I am optimistic that the simplicity/elegance of the authors’ approach should allow them to clearly show a theoretical advance (in terms of their bounds) over previous results. However, adding the detailed discussion with prior results will take some work, and having this context is critical during the review process. Therefore, I cannot argue for this paper to be accepted at this time.

### References

Ralaivola, L., Szafranski, M. and Stempfel, G., 2010. Chromatic PAC-Bayes bounds for non-iid data: Applications to ranking and stationary β-mixing processes. The Journal of Machine Learning Research, 11, pp.1927-1956.

Reviews: review: paper_summary: paper_summary: This paper provides a framework for proving generalization bounds for non-i.i.d. data sequences, building upon a recent framework introduced by Lugosi and Neu (2023) that reduces PAC to online learning. This technique recovers some known PAC Bayesian bounds for non-i.i.d. scenarios and various other implications.

The original framework by Lugosi and Neu (2023) introduced an online learning "generalization game", where the regret of the online learning algorithm can be translated into a generalization bound in the offline setting. This framework has been shown to recover some important generalization bounds with a clean analysis.

In this paper, the generalization game is extended to a game where the learner gets to see the observation with delay (where there's no delay we are back to the original framework). The regret of the online learner in this game can again be translated into a generalization bound. When the delay is large, it increases the regret of the online learner (one term in the generalization bound) but decreases the term determined by the property of "how much the sequence is non-i.i.d.".
Online learning with delays has been studied extensively, and so "off-the-shelf" algorithms and regret bounds can be used to derive/recover generalization bounds.

One nice application of the technique is that it allows the analysis of stationary mixing processes that have been studied extensively (the assumption on the non-i.i.d. sequences is weaker than known mixing assumptions). Another interesting application is to popular dynamic predictions such as autoregressive models and RNNs.
strength_weakness: strength_weakness: The paper heavily builds on the framework of Lugosi and Neu (2023). This is not a weakness, but my question is: besides extending the online game to accommodate delays and using ideas from the online learning literature, what are the technical challenges/contributions in this paper?

Another question - do you know if the paper by Lugosi and Neu (2023) was already published? I'm asking since I didn't go over the proofs in this paper.
questions: questions: See above.
limitations: limitations: Limitations are properly addressed.
paper_summary: paper_summary: The paper focuses on learning from non-i.i.d data. Specifically, the authors develop a framework that derives generalization guarantees through a reduction to an online learning game with delays, where achieving low regret translates to low generalization error. They present specific bounds when using EWA and FTRL as the online learning algorithms. Additionally, the framework is extended to accommodate dynamic hypotheses.
strength_weakness: strength_weakness: While I did not go over the entire details, I did not find any major weaknesses.  
- A small typo is line 43: "..we propose propose.. "
questions: questions: Could the authors provide their perspective on potential future directions and limitations of their framework?
limitations: limitations: N/A
paper_summary: paper_summary: This paper extends the Lugosi-Neu(2023) framework for upper bounding the generalization error of statistical learning algorithms to the non-i.i.d. setting, by considering that the training samples are drawn from a suitably mixing stochastic process. They show that the existence of a delayed online learner with bounded regret in the Online-to-Batch game of Lugosi-Neu(2023) against an offline learner implies that the offline learner has low generalization error even when trained on data drawn from a mixing stochastic process. The authors also investigate settings such as FTRL and MWU under this model.
strength_weakness: strength_weakness: The techniques seem to be largely an amalgamation of several papers which have refined the "blocking technique" in various settings, and the key observation that the introduction of delay in online games lead to the online cost being a sum of martingale difference sequences, which essentially allows them to use proof techniques of Lugosi-Neu(2003). 

The delayed online learning setting is new to me, and I am not sure how to evaluate its significance versus the standard online learning setting. In fact, it seems like getting similar bounds w.r.t. the standard online setting would involve significant more technical novelty, compared to the current setting. 

The stochastic process also seems to be quite well-behaved in comparison to previous works in the literature such as Mohri and Rostamizadeh (2011), who give generalization bounds (in the pure offline setting) under stochastic processes with weaker notions of convergence.

The authors mention that the results hold for a specific class of bounded loss functions, but I could not find specific details regarding this point afterwards in the paper.
questions: questions: 1. Can the authors comment on the delayed learning setup vs the normal online setup of Lugosi-Neu (2003)? Given that this is a central construct essential to the proof idea, I strongly believe that the discussion section should some attention to this question.
2. Is it possible to get high probability bounds for the generalization error when the offline learner is trained on $\beta$-mixing processes as defined in Yu (1994), Meir (2000), Mohri and Rostamizadeh (2008), etc.?
3. Is it possible to get similar results for a more general family of loss functions (for example Lipschitz loss functions)?
limitations: limitations: The discussions of limitations in the current work is limited, and lacks discussion as to why certain choices were made (or overlooked).
paper_summary: paper_summary: This paper studies the generalization error of statistical learning in a non-i.i.d setting, where the training data distribution could have temporal dependency. They develop a framework that reduces the generalization error in this case into the regret of an online learning problem with delayed feedback. Then, they present a series of instantiations of their results with different online learning algorithms and assumptions on the data generation process.
strength_weakness: strength_weakness: 1. The proposed framework seems to be a straightforward extension of that in the i.i.d setting. Technical novelty of this work seems limited.
2. The instantiation of the framework given in this paper is still very high level and abstract (for example, the algorithm considered is the general follow the leader algorithm). It would be beneficial to have some specific instantiations and show that if the obtained results are comparable to the existing ones, similar to what has been done in Lugosi and Neu (2023).
questions: questions: 1. typo in Line 43: double "propose"
2. Assuming that the data is $\beta$-mixing, how is your results compare to previous work? Does your result improve over existing ones?
3. Is the framework applicable when the online learning algorithm is under the online mirror descent framework?
limitations: limitations: Nothing necessary stands out.
paper_summary: paper_summary: The authors establish generalization error bounds for non-iid data based on the online-to-PAC conversion.
In particular, the authors extend the online-to-PAC conversion techinique to non-iid settings utilizing the online learning with delayed feedback. In the paper, the authors illustrate

1. a method of non-iid online-to-PAC conversion,
2. a method of converting online learning algorithms to their delayed counterparts,
3. the resulting non-iid generalization bounds combining 1. and 2., and
4. an extension of 1. to dynamic hypothesis learning.
strength_weakness: strength_weakness: - Notable logical gap: Lemma 3 only gives a regret bound **independent** of $P^*$, but it seems Corollaries 3 and 4 need $P^*$-dependent regret bound. I believe this is fixable, but still, need some fix.
- More discussion on related work: Are there any results previously not known, but can be proved with the proposed method?
questions: questions: - Can you show instantiations of Theorem 4 using EWA and FTRL (as in Corollaries 3 and 4)?
limitations: limitations: Limitations are not explicitly discussed.

Comments: comment: Thanks for your response. 
I will keep my positive score.
Thank you for the rebuttal. I am mostly satisfied with the responses. I will be maintaining my current positive rating. 

As an aside, I would urge the authors to add an exposition on the delayed setting due to importance of the technique in this paper. It might be well-studied (as the authors have claimed) but I do not think it is well-established to the point of being self-explanatory.
Thanks for the rebuttal.
I confirm my concerns/questions are all addressed adequately.