Fabien Lauer

Uniform Risk Bounds for Learning with Dependent Data Sequences

This paper extends standard results from learning theory with independent data to sequences of dependent data. Contrary to most of the literature, we do not rely on mixing arguments or sequential measures of complexity and derive uniform risk bounds with classical proof patterns and capacity measures. In particular, we show that the standard classification risk bounds based on the VC-dimension hold in the exact same form for dependent data, and further provide Rademacher complexity-based bounds, that remain unchanged compared to the standard results for the identically and independently distributed case. Finally, we show how to apply these results in the context of scenario-based optimization in order to compute the sample complexity of random programs with dependent constraints.

Introduction

Statistical learning theory offers probabilistic guarantees on the accuracy of models learned from data. Most of these results assume that the data come from a realization of a sample of independent and identically distributed (i.i.d.) random variables, which allows one to build the theory upon standard concentration arguments. However, this assumption is often unrealistic as dependent data are ubiquitous in real-world applications, such as signal processing, speech recognition, biological sequence annotation [START_REF] Baldi | Bioinformatics: the Machine Learning Approach[END_REF], dynamical system identification [START_REF] Ljung | System Identification: Theory for the User[END_REF], or even handwritten character recognition where the images collected for training come from a string of letters forming a meaningful text.

This paper extends several classical results to sequences of dependent data, such as risk bounds based on the Vapnik-Chervonenkis (VC) dimension or the Rademacher complexity. In particular, we focus on uniform risk bounds that are more suitable for nonconvex loss functions difficult to minimize in practice.

As a motivating application, we also consider the consequences of these results in the framework of scenario-based optimization for solving uncertain optimization problems. Here, robust solutions are those that typically satisfy an infinite number of constraints: one for each value of the uncertain parameter of the problem. Scenario-based optimization computes instead probably approximately correct solutions by sampling the set of uncertainties and solving the problem with a finite number of constraints. In this context, the computing complexity is directly related to the number of sampled constraints and it is thus of primary importance to compute the sample complexity of the corresponding random program, i.e., the smallest sample size for which we can guarantee with a high confidence that the probability of violation of the constraint is low.

Related work

Dependence between training instances typically occur for machine learning in the context of ranking problems, where the training algorithms deal with overlapping pairs of input data. In this setting, prior work on generalization bounds [START_REF] Usunier | Generalization error bounds for classifiers trained with interdependent data[END_REF][START_REF] Ralaivola | Entropy-based concentration inequalities for dependent variables[END_REF] relied on a decomposition of the training sample into independent subsamples for which concentration could be applied by following the graph-coloring scheme of [START_REF] Janson | Large deviations for sums of partly dependent random variables[END_REF].

The literature also contains numerous results that do not assume that such a decomposition is possible, e.g., when a single training instance depends on all the others as is common when handling time-series or sequential data. In that case, the general approach is to measure the degree of dependence between the data points with a mixing coefficient [START_REF] Bradley | Basic properties of strong mixing conditions. a survey and some open questions[END_REF] and assume that this coefficient tends to zero sufficiently quickly to allow for the derivation of meaningful bounds. Works in this line include that of [START_REF] Meir | Nonparametric time series prediction through adaptive model selection[END_REF]; [START_REF] Steinwart | Fast learning from non-i.i.d. observations[END_REF]; Mohri andRostamizadeh (2009, 2010) and rely on technical arguments inherited from [START_REF] Yu | Rates of convergence for empirical processes of stationary mixing sequences[END_REF]. Though the obtained risk bounds share most of their structure with their counterpart for i.i.d. data, they also involve the mixing coefficient, which slightly degrades the convergence and remains difficult to determine or estimate in practice. Note that a connection between the mixing and graph-coloring arguments is discussed in [START_REF] Ralaivola | Chromatic PAC-Bayes bounds for non-iid data: Applications to ranking and stationary β-mixing processes[END_REF].

Other approaches based on Rademacher complexities include that of [START_REF] Rakhlin | Sequential complexities and uniform martingale laws of large numbers[END_REF], which can also deal with non-stationary sequences [START_REF] Kuznetsov | Learning theory and algorithms for forecasting non-stationary time series[END_REF], but involves complex computations with tree processes and decoupling techniques from de la [START_REF] De La Peña | Decoupling: From Dependence to Independence[END_REF]. Also, these works consider a different form of the risk (a conditional forecasting risk) and rely on sequential counterparts of standard capacity measures.

A more recent line of research developped by [START_REF] Simchowitz | Learning without mixing: Towards a sharp analysis of linear system identification[END_REF]; [START_REF] Faradonbeh | Finite time identification in unstable linear systems[END_REF] relies on techniques from [START_REF] Mendelson | Learning without concentration[END_REF][START_REF] Mendelson | Learning without concentration for general loss functions[END_REF] to bypass the need for mixing arguments. However, these results apply only to the empirical risk minimizer (the orthogonal least-squares estimator is considered in [START_REF] Simchowitz | Learning without mixing: Towards a sharp analysis of linear system identification[END_REF]; [START_REF] Faradonbeh | Finite time identification in unstable linear systems[END_REF]). Thus, they do not provide uniform risk bounds that apply to any model in a given class, which is critical for applications with nonconvex loss functions where the empirical risk minimizer remains elusive (such as unsupervised learning or hybrid dynamical system identification [START_REF] Lauer | Hybrid System Identification: Theory and Algorithms for Learning Switching Models[END_REF]).

Regarding our motivating application, i.e., scenario-based optimization, we can distinguish two main lines of research. The first, developed for instance in [START_REF] Alamo | Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems[END_REF]; [START_REF] Lauer | Margin theory for the scenario-based approach to robust optimization in high dimension[END_REF], builds upon learning theory to derive bounds on the probability of violation and sample complexities. The second, pioneered by [START_REF] Campi | The exact feasibility of randomized solutions of uncertain convex programs[END_REF]; [START_REF] Calafiore | Random convex programs[END_REF], relies instead on convex analysis arguments that lead to tighter bounds for the specific case of convex optimization. A number of works also tried to extend the latter to various forms of nonconvex programs [START_REF] Esfahani | Performance bounds for the scenario approach and an extension to a class of non-convex programs[END_REF][START_REF] Campi | A general scenario theory for nonconvex optimization and decision making[END_REF]. However, all these works, either based on learning theory or convex analysis, assume that the scenarios are sampled independently, which could be problematic for certain applications, as, e.g., the one of [START_REF] Wang | Data-driven feedback stabilization of switched linear systems with probabilistic stability guarantees[END_REF].

Contribution

We show that many standard results from learning theory, such as classification VC bounds and Rademacher complexity-based bounds, apply without any modification to dependent data. In addition, we derive these results with proofs that follow the standard patterns and rely on the classical capacity measures, which stands in contrast to the approach of [START_REF] Rakhlin | Sequential complexities and uniform martingale laws of large numbers[END_REF] which requires additional arguments and more complex computations with sequential complexities. In comparison with other works from the literature, we obtain uniform risk bounds that do not introduce additional terms or mixing coefficients and that are thus more widely applicable than those of [START_REF] Simchowitz | Learning without mixing: Towards a sharp analysis of linear system identification[END_REF][START_REF] Faradonbeh | Finite time identification in unstable linear systems[END_REF] and tighter than those of, e.g., [START_REF] Mohri | Rademacher complexity bounds for non-iid processes[END_REF].

Technically, our results rely on a simple construction of the ghost sample that enjoys the necessary properties, and, for Rademacher complexity-based bounds, a concentration inequality adapted to dependent variables by following [START_REF] Van De Geer | On Hoeffding's inequality for dependent random variables[END_REF]. Specifically, these allow us to prove the following claims along the different sections of the paper.

• The standard classification risk bounds of [START_REF] Vapnik | Statistical Learning Theory[END_REF] that are based on the VC-dimension hold in the exact same form for non-i.i.d. training sequences. Interestingly, no new concentration result is required for the proof (Sect. 3).

• With an additional stationarity assumption, similar conclusions hold for VC relative deviation bounds and classification risk bounds with fast rates, thus generalizing the results of [START_REF] Vapnik | Statistical Learning Theory[END_REF]; [START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF] (Sect. 3.1).

• Extending the results above to deal with regression problems poses no difficulty in the non-i.i.d. context (Sect. 3.2).

• When the Rademacher complexity can be bounded in terms of the marginal distributions of the data, Rademacher complexity-based bounds identical to the ones for the standard i.i.d. case hold for dependent data. This is true in particular for linear and kernel machines, thus generalizing the results of [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF] (Sect. 4).

• Using the chaining method, standard risk bounds based on uniform covering numbers or the fat-shattering dimension are shown to hold also for .

• In the framework of robust optimization, the sample complexities of random programs derived in [START_REF] Alamo | Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems[END_REF]; [START_REF] Lauer | Margin theory for the scenario-based approach to robust optimization in high dimension[END_REF] for independent scenarios also hold with dependent scenarios (Sect. 5).

Finally, the main drawback of our approach is that it does not allow the derivation of data-dependent bounds, i.e., risk bounds in which the complexity term is evaluated with respect to the available training sample. Datadependent bounds may be tighter than worst-case or average estimates. How-ever, this improvement remains limited in many standard cases. In addition, keeping in mind our motivation stemming from the field of scenario-based optimization, we note that data-dependent bounds are irrelevant for computing sample complexity estimates.

Preliminaries

This section presents the general learning framework with dependent data sequences and the basic tools needed to derive our main results.

Learning framework

Let (A i ) 0≤i≤n denote a filtration and

Z n = (Z i ) 1≤i≤n a sequence of random variables Z i = (X i , Y i ) ∈ X × Y = Z adapted to (A i ) 1≤i≤n
,1 without any other assumption. Given a model class F of functions from X → Y and a bounded loss function : Y2 → [0, B], we consider learning a model f ∈ F from such a training sequence Z n and aim at the estimation of its risk,

L n (f ) = 1 n n i=1 E (f (X i ), Y i ), (1)
where E denotes the expectation, by its empirical risk

Ln (f ) = 1 n n i=1 (f (X i ), Y i ).
(2)

Note that for stationary sequences, the Z i variables are identically distributed and the risk (1) merely boils down to the standard learning risk E (f (X 1 ), Y 1 ), also considered for sequential data, e.g., in [START_REF] Mohri | Rademacher complexity bounds for non-iid processes[END_REF].

For non-stationary sequences, the risk in (1) does not really assess the ability of the model to predict future values of Y i , since these need not share the same distribution with the Y i 's in (1). However, it remains a valuable quantity for other applications, such as vector quantization or clustering problems, where, after the obvious reformulation of the loss as : X 2 → [0, B], the risk in (1) stands for the distortion or the clustering risk and evaluates how well the model approximates the distribution of the training sample.

Regarding prediction problems, note that the risk (1) differs from the conditional risk 1 n

n i=1 E [ (f (X i ), Y i ) | A i-1 ] (3)
studied, e.g., in [START_REF] Kuznetsov | Learning theory and algorithms for forecasting non-stationary time series[END_REF]; [START_REF] Rakhlin | Sequential complexities and uniform martingale laws of large numbers[END_REF]. The conditional risk (3) only measures the ability of the model to predict the (immediate) future of the training sequence, which is particularly well-suited for time-series forecasting problems. However, it is not suitable for applications such as dynamical system identification where the model is learned from training data offline, and then applied to predict the output of the system that might have been reset in the meantime. In other words, the conditional risk (3) refers only to the sample path of the random process used for training, whereas the risk in (1) averages over all sample paths.

Basic tools

Most results in statistical learning theory rely on concentration arguments, which are easily available for samples of independent variables. While we will see in Sect. 3 that these are sufficient to extend some standard risk bounds to dependent sequences, others will require a concentration inequality for samples of dependent variables. It is stated here as a specification of the results in [START_REF] Van De Geer | On Hoeffding's inequality for dependent random variables[END_REF]. The detailed proof can be found in Appendix A for completeness.

Theorem 1 (Bounded difference inequality for sequences of dependent variables). Let (Z i ) 1≤i≤n denote a sequence of random variables (not necessarily stationary) taking values in Z and g be a real-valued function of Z 1 , ..., Z n such that it is A n -measurable and

sup (z j ) 1≤j≤n ∈Z n z ∈Z |g(z 1 , . . . , z i , . . . , z n ) -g(z 1 , . . . , z , . . . , z n )| ≤ c i , i = 1, . . . , n.
Then, for any > 0,

P {g(Z 1 , . . . , Z n ) -Eg(Z 1 , . . . , Z n ) > } ≤ exp -2 2 n i=1 c 2 i .
Note that Theorem 1 provides the exact same result as McDiarmid's inequality for i.i.d. variables [START_REF] Mcdiarmid | On the method of bounded differences[END_REF], with the same exponential rate.

We also recall a famous result from [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], in its original form for independent variables, which is all we will require in the sequel.

Theorem 2 (Hoeffding's inequality). Let (W i ) 1≤i≤n denote a sequence of independent random variables satisfying W i ∈ [a i , b i ]. Then, for any > 0,

P 1 n n i=1 W i - 1 n n i=1 EW i > ≤ exp -2n 2 2 n i=1 (b i -a i ) 2 .

Classification risk bounds based on the VC-dimension

We first discuss how to derive the standard VC classification risk bounds for dependent data. The first ingredient of such bounds is a symmetrization lemma, which in turn requires two things: a concentration inequality and a ghost sample. In the classical scenario where the training sample Z n is made of independent copies of some random variable Z, the ghost sample Z n can merely be taken as an independent copy of Z n . Then, standard concentration inequalities apply to this sample of i.i.d. variables Z i .

In the case of a sequence of dependent variables, we instead build the ghost sample with variables Z i taken as independent copies of the variables Z i . Thus, we obtain a sample Z n of independent variables that is also independent of Z n and with each Z i ∼ Z i (the notation A ∼ B indicates that the two random variables A and B share the same distribution). Note however that the resulting ghost sample Z n need not share the same joint distribution with Z n as in the classical i.i.d. scenario. But, a careful look at the proof of the standard symmetrization lemma of [START_REF] Vapnik | Statistical Learning Theory[END_REF] shows that this is not needed for symmetrization to hold. In addition, in this proof, the concentration inequality is only applied to the ghost sample, not the training sample. Since our ghost sample is made of independent variables by construction, we have the following (detailed proof in App. B).

Lemma 1 (Symmetrization). Let Z n denote a sequence of possibly dependent variables and consider the ghost sample Z n = (Z i ) 1≤i≤n with each

Z i = (X i , Y i ) built as an independent copy of Z i = (X i , Y i ). Then, for any such that n 2 ≥ 2B 2 , P sup f ∈F L n (f ) -Ln (f ) ≥ ≤ 2P sup f ∈F L n (f ) -Ln (f ) ≥ 2 , where L n (f ) = 1 n n i=1 (f (X i ), Y i ).
Equipped with this tool, classification risk bounds based on the zero-one loss2 (ŷ, y) = 1 ŷ =y (4) can be obtained in terms of the growth function Π F (n) of the class F that can be bounded by the VC-dimension d V C .

Definition 1 (Growth function). For a set F of classifiers f : X → Y with a discrete set Y of finite cardinality, its growth function is the largest cardinality of the set of classifications produced by its classifiers over all sets x n = (x i ) 1≤i≤n of n points:

Π F (n) = sup xn∈X n |{(f (x 1 ), . . . , f (x n )) : f ∈ F}|. Definition 2 (VC-dimension). The Vapnik-Chervonenkis (VC) dimension d V C of a set F of binary classifiers f : X → Y, |Y| = 2, is the largest number of points n such that Π F (n) = 2 n .
More precisely, it is a remarkable fact that no new concentration result is needed to derive a risk bound for dependent data from Lemma 1. The trick is that, by introducing independent Rademacher variables and conditioning, we only require concentration with respect to these variables rather than for the samples themselves. Therefore, the classical Hoeffding inequality of Theorem 2 applies and the proof of the next result (given in Appendix C) only requires that the quantity

1 f (X i ) =Y i -1 f (X i ) =Y i is a symmetric random variable, which is ensured by the fact that (X i , Y i ) is an independent copy of (X i , Y i ).
Theorem 3 (Basic VC risk bound for dependent data). Let F be a set of classifiers f : X → {-1, +1} with VC-dimension d V C and denote the classification loss (4). Then, for any δ ∈ (0, 1), with probability at least 1 -δ,

∀f ∈ F, L n (f ) ≤ Ln (f ) + 2 2 log Π F (2n) + log 2 δ n ≤ Ln (f ) + 2 2 d V C log 2en d V C + log 2 δ n .
Note that Theorem 3 applies to dependent training sequences Z n and provides the exact same result as Vapnik (1998) did for the i.i.d. case.

Example 1 (Linear classification). Consider the set of linear classifiers, [START_REF] Vapnik | Statistical Learning Theory[END_REF]. For all d ≥ 3, Theorem 3 then yields for n = 100 000 that, with 95% probability, the risk of any classifier f ∈ F can be estimated from its empirical risk on the training sample of dependent instances with accuracy no less than 0.031 √ d + 1 + 0.015.

F = {f : f (x) = sign( w, x + b), w ∈ R d , b ∈ R}, of VC-dimension d V C = d + 1 (

Relative deviation bounds

Risk bounds with a faster convergence rate close to O(1/n) instead of O(1/ √ n) can be derived from relative deviation bounds of the form

P sup f ∈F L n (f ) -Ln (f ) L n (f ) ≥ ≤ A exp(-nC),
for some constants A and C. In turn, obtaining such results requires a different form of symmetrization, associated to a concentration argument.

The detailed proof of the corresponding symmetrization given in [START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF] shows that independence is used at only two different places. It is first required between data points to apply a binomial tail bound, but only on the ghost sample. Then, the fact that the training sample is independent of the ghost sample is used.

Considering now a construction of the ghost sample as in Theorem 1, we directly obtain the required indepedence: Z n is independent of Z n and all Z i in the ghost sample are independent of each other. This leads to the following generalization of the result of [START_REF] Vapnik | Statistical Learning Theory[END_REF]; [START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF] to stationary sequences of training data (the detailed proof can be found in Appendix D for completeness). Note that stationarity, which is required for the binomial tail bound, is a reasonable assumption for a prediction task as considered here.

Lemma 2 (Symmetrization for relative deviations). Let Z n = (Z i ) 1≤i≤n denote a stationary sequence of possibly dependent variables and consider the ghost sample

Z n = (Z i ) 1≤i≤n with each Z i = (X i , Y i ) built as an independent copy of Z i = (X i , Y i ).
Let denote the classification loss (4). Then, for any such that n 2 > 1,

P sup f ∈F L n (f ) -Ln (f ) L n (f ) ≥ ≤ 4P    sup f ∈F L n (f ) -Ln (f ) ( Ln (f ) + L n (f ) + 1 n )/2 ≥ 2    , where L n (f ) = 1 n n i=1 1 f (X i ) =Y i .
As for Theorem 3, we can derive a fast-rate risk bound from Lemma 2 using only standard concentration arguments, i.e., by following the proof of [START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF] and introducing independent Rademacher variables, and the symmetry of 1 f (X i ) =Y i -1 f (X i ) =Y i ensured by our ghost sample construction (detailed proof given in App. E).

Theorem 4 (General VC risk bound for dependent data). Let F be a class of classifiers f : X → {-1, +1} with VC-dimension d V C and denote the classification loss (4). Let Z n = (Z i ) 1≤i≤n denote a stationary sequence of possibly dependent variables. Then, for any δ ∈ (0, 1), with probability at least

1 -δ, ∀f ∈ F, L n (f ) ≤ Ln (f ) + 2 Ln (f ) log Π F (2n) + log 4 δ n + 4 log Π F (2n) + log 4 δ n ≤ Ln (f ) + 2 Ln (f ) d V C log 2en d V C + log 4 δ n + 4 d V C log 2en d V C + log 4 δ n .
Here again, the bounds of Theorem 4 provide the same guarantees as the classical results of [START_REF] Vapnik | Statistical Learning Theory[END_REF]; [START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF], while holding more generally for dependent data. In particular, for classifiers achieving a small empirical error Ln (f ), these are tighter than the ones of Theorem 3, with a convergence rate in O(1/n) in the optimistic scenario where a perfect fit of the data can be ensured.

Finally, we note that the fast-rate and margin-based risk bounds provided in [START_REF] Cortes | Relative deviation margin bounds[END_REF] and that involve covering numbers instead of the growth function can also be proved to hold for dependent data using similar arguments as above. However, we refrain from giving the details and will instead consider margin classifiers when discussing Rademacher complexity-based bounds in Sect. 4.

Regression bounds

When : Y 2 → [0, B] is a regression loss bounded by B, the VC theory for classification applies thanks to Inequality (5.11) in [START_REF] Vapnik | Statistical Learning Theory[END_REF]:

P sup f ∈F L n (f ) -Ln (f ) > ≤ P sup f ∈F ,β∈(0,B) L(f ) -Ln (f ) > B , (5)
where L(f ) and Ln (f ) are defined as in ( 1)-( 2) with the classification loss

˜ (f (X i ), Y i ) = 1 (f (X i ),Y i )-β≥0
. Interestingly, it can be checked that Inequality (5) holds irrespective of the independence of the Z i . Thus, the classification bounds above can be applied to its right-hand side with the VC-dimension of a function class that has one additional parameter β ∈ (0, B), and this yields bounds on the regression risk of models learned from dependent data sequences.

Example 2 (VC bound for linear system identification). Consider a regression problem with data generated by a linear dynamical system as y i = θ, x i + ν i with a random noise term ν i and x i = (y i-1 , . . . , y i-d ). In this case, the data collected from a single trajectory of the system clearly cannot be assumed to be i.i.d., but the results above still yield performance guarantees. Specifically, for the squared loss (ŷ, y) = (ŷ -y) 2 and a class of linear models

F = {f : f (x) = w, x , w ∈ R d } over X ⊂ R d
, the VC-dimension of the set of functions 1 (f (x),y)-β≥0 induced by F × (0, B) can be computed as follows.

Let φ be the function that maps x ∈ X into a vector of all the d 2 monomials of degree 2 over the components of x: φ i+(j-1)d (x) = x i x j , i = 1, . . . , d, j = 1, . . . , d. Let z = (x, y) and ψ(z) = (φ(x), yx, y 2 ). Then, for any f ∈ F and β ∈ (0, B),

(f (x), y) -β = ( w, x -y) 2 -β = ( w, x ) 2 -2 w, yx + y 2 -β,
which is a quadratic function of z but a linear function of ψ(z). Therefore, the VC-dimension of the set of functions 1 (f (x),y)-β≥0 cannot be larger than the VC-dimension of the set of linear classifiers of R d 2 +d+1 to which all the ψ(z) belong, i.e., d V C ≤ d 2 + d + 2. Thus, Inequality (5) ensures with Theorem 3 that, with probability at least 1 -δ,

∀f ∈ F, L n (f ) ≤ Ln (f ) + 2B 2 (d 2 + d + 2) log 2en d 2 +d+2 + log 2 δ n .

Rademacher complexity-based bounds

We now consider the derivation of risk bounds based on Rademacher complexities instead of VC-dimensions. This also relies on a symmetrization step, which we conduct using a ghost sample defined as in Section 3. In addition, we will also require a bounded difference inequality for dependent variables, which we established in Theorem 1.

Let us first define the relevant capacity measures.

Definition 3 (Rademacher complexities). Let T n = (T i ) 1,≤i≤n be a sequence of (not necessarily independent nor identically distributed) random variables T i ∈ T and σ n = (σ i ) 1≤i≤n an i.i.d. sequence of uniformly distributed σ i ∈ {-1, +1}. Let F be a class of real-valued functions over T . The empirical Rademacher complexity of F given T n is

RT n (F) = E sup f ∈F 1 n n i=1 σ i f (T i ) T n and the Rademacher complexity of F is R T n (F) = E RT n (F) = E sup f ∈F 1 n n i=1 σ i f (T i ).
Note that we keep the subscript T n in the notation of the Rademacher complexity to emphasize that its definition depends on the distribution of T n . For a sequence of values t n = (t i ) 1≤i≤n ∈ T n , we will also occasionally write Rtn (F) with a lowercase t n in the subscript to refer to the value of the empirical Rademacher complexity computed given T n = t n .

We can now state the first result of this section (proved in App. F).

Theorem 5 (Rademacher complexity-based bound). Let Z n denote a sequence of possibly dependent variables and consider the ghost sample

Z n = (Z i ) 1≤i≤n with each Z i = (X i , Y i ) built as an independent copy of Z i = (X i , Y i ). Let : Y × Y → [0, B]
be a loss function. Then, for any δ ∈ (0, 1), with probability at least 1 -δ,

∀f ∈ F, L n (f ) ≤ Ln (f ) + R Zn (L) + R Z n (L) + B log 1 δ 2n ,
where

L = { f : f (z) = (f (x), y), f ∈ F}, and R Z n (L) is the Rademacher complexity of L defined over the ghost sample Z n instead of Z n .
The main difference with classical Rademacher complexity-based bounds of, e.g., [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF], is due to the possibility of having different joint distributions for Z n and Z n , which prevents us from collapsing R Zn (L) + R Z n (L) into 2R Zn (L). In particular, this compromises the possibility to obtain data-dependent bounds based on the empirical Rademacher complexities, since the ghost sample is not really available to compute RZ n (L).

However, even in the standard i.i.d. case where we can perform such a simplification, it is common practice to upper bound the Rademacher complexity by its empirical version in a worst-case manner, which we reproduce here:

R Zn (L) ≤ sup zn∈Z n Rzn (L) and R Z n (L) ≤ sup zn∈X n Rzn (L).
Therefore, we can obtain a risk bound that does not depend on the ghost sample anymore, and which coincides with common bounds for the i.i.d. case:

Corollary 1. For any δ ∈ (0, 1), with probability at least 1 -δ,

∀f ∈ F, L n (f ) ≤ Ln (f ) + 2 sup zn∈Z n Rzn (L) + B log 1 δ 2n .
Example 3 (Linear and kernel regression). Consider the squared loss, (ŷ, y) = (y -ŷ) 2 , computed from a bounded output Y ∈ [-M, M ] and a clipped prediction ŷ = min(M, max(-M, ŷ)) given by a linear model ŷ

= f (x) from F lin = {f : f (x) = w, x , w ≤ Λ}. Then, standard computations (detailed in App. G) yield sup zn∈Z n Rzn (L) ≤ 4M Λ sup x∈X x √ n , (6)
which can only be improved in data-dependent bounds through the substitution of n i=1 X i 2 /n for sup x∈X x . If we now consider F as the ball of radius Λ in the Reproducing Kernel Hilbert Space (RKHS) H induced by the Gaussian kernel, K(x, x ) = exp(-x -x /2σ 2 ), we have instead

sup zn∈Z n Rzn (L) ≤ 4M Λ √ n ,
which is exactly what the corresponding data-dependent bound would give in an i.i.d. setting.

Instead of relying on worst-case estimates, another possibility is to use an upper bound on the Rademacher complexity expressed in terms of the marginal distributions of the variables Z i , which coincide with those of the Z i . Theorem 6. Let Z n denote a sequence of possibly dependent variables

Z i = (X i , Y i ) ∈ X × Y. For a bounded loss function : Y × Y → [0, B] and a class F of functions from X to Y, let L = { f : f (z) = (f (x), y), f ∈ F}. If R Zn (L) ≤ R n (L) (7)
with an upper bound R n (L) on the Rademacher complexity of L expressed in terms of the marginal distributions of the Z i 's, then, for any δ ∈ (0, 1), with probability at least 1 -δ,

∀f ∈ F, L n (f ) ≤ Ln (f ) + 2R n (L) + B log 1 δ 2n .
Proof. Since R n (L) only involves the marginal distributions of the Z i , which are identical to the ones of the Z i by construction of the ghost sample in Theorem 5, the bound in (7) also implies R Z n (L) ≤ R n (L). Then, both Rademacher complexities in the bound of Theorem 5 can be upper bounded by R n (L), which yields the desired result.

Example 4 (Linear and kernel regression-continued). Consider again the squared loss with the class F lin for linear regression. Then, the classically used upper bound on the Rademacher complexity is precisely of a form suitable for Theorem 6:

R Zn (L) ≤ 4M Λ n i=1 E X i 2 n = R n (L),
and, since

X i ∼ X i , R Z n (L) ≤ 4M Λ n i=1 E X i 2 n = 4M Λ n i=1 E X i 2 n = R n (L).
Thus, we obtain that, with probability at least 1 -δ,

∀f ∈ F lin , L n (f ) ≤ Ln (f ) + 8M Λ n i=1 E X i 2 n + 4M 2 log 1 δ 2n ,
which coincides with the standard result for linear regression with i.i.d. data.

In addition, similar results can also be derived for classes of kernel models with E X i 2 replaced by EK(X i , X i ), which only depends on the marginal distribution of X i .

Example 5 (Margin classifiers). Binary margin classifiers are classifiers that implement f (x) = sign(g(x)) with a real-valued function g ∈ G. For those, the piecewise linear margin loss function is usually considered: for a margin γ > 0, γ (g(x), y) = min{γ, max{0, (1 -yg(x))/γ}. Then, the contraction principle [START_REF] Ledoux | Probability in Banach Spaces: Isoperimetry and Processes[END_REF] yields R Zn (L) ≤ R Zn (G)/γ and an upper bound on R Zn (G) in terms of the marginal distributions also leads to a bound on R Zn (L) suitable for Theorem 6. For linear classifiers, G = {g : g(x) = w, x , w ≤ Λ}, we can use the bound of Example 4 to obtain

R n (L) = Λ n i=1 E X i 2 γn ,
and a bound on the probability of misclassification via

P (f (X) = Y ) = E1 f (X) =Y ≤ E γ (g(X), Y ) = L n (f )
, where L n (f ) is bounded by Theorem 6.

Of course, similar results hold for kernel machines by exchanging E X i 2 with EK(X i , X i ).

Theorem 6 applies also more broadly to other nonconvex loss functions for which the contraction principle does not apply as directly as in Example 5. Note that, for such losses, the empirical risk minimizer remains most often elusive and the obtention of uniform risk bounds is critical to allow for their application to the model returned by a training algorithm.

Example 6 (Vector quantization). Consider the problem of vector quantization in X ⊂ H for some Hilbert space H as discussed in [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF]; [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF], where one aims at finding a collection f = (f k ) 1≤k≤C ∈ H C of C codepoints f k that can well approximate the observations of X i ∈ X . The framework of Sect. 2.1 can be modified in the obvious manner to account for this setting by letting Z i = X i and computing the loss from

X 2 → [0, B] in- stead of Y 2 → [0, B].
For nearest neighbors quantizers, the error of the model f is computed by the loss function

(f, x) = min k∈{1,...,C} x -f k 2 ,
and the risk (1) is the so-called distortion of f . Risk bounds in this setting were derived for the i.i.d. scenario via the Rademacher complexity in [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF]; [START_REF] Lauer | Risk bounds for learning multiple components with permutation-invariant losses[END_REF], and their computations led to bounds in terms of the marginals. For instance, for

F = F C 0 , F 0 = {f 0 ∈ H : f 0 H ≤ Λ}, we have R Xn (L) ≤ 2CΛ n i=1 E X i 2 n + CΛ 2 √ n = R n (L)
and therefore a risk bound that applies in the non-i.i.d. setting via Theorem 6.

Other examples, such as in switching regression or subspace clustering (Lauer, 2020a,b), can be found and lead to the same conclusion: in all these settings, common bounds on the Rademacher complexity is expressed in terms of the marginal distributions, and can thus be used verbatim to produce risk bounds with dependent data. For switching regression, this leads to guarantees on the accuracy of models in switched system identification [START_REF] Lauer | Hybrid System Identification: Theory and Algorithms for Learning Switching Models[END_REF] that are tighter than those derived in [START_REF] Massucci | A statistical learning perspective on switched linear system identification[END_REF] with mixing arguments.

More generally, Theorem 6 can be compared with the results of [START_REF] Mohri | Rademacher complexity bounds for non-iid processes[END_REF] that provide generic risk bounds based on Rademacher complexities and mixing arguments, used for instance by [START_REF] Massucci | A statistical learning perspective on switched linear system identification[END_REF]. For a training sequence Z n generated by a β-mixing process of mixing coefficient β(a) that measures the degree of dependence between data points separated by a time steps (see [START_REF] Bradley | Basic properties of strong mixing conditions. a survey and some open questions[END_REF] for proper definitions of these terms), and in a setting otherwise similar to Theorem 6, [START_REF] Mohri | Rademacher complexity bounds for non-iid processes[END_REF] provides the bound:

∀f ∈ F, L n (f ) ≤ Ln (f ) + 2R µ (L) + B log 1 δ-4(µ-1)β(a) 2µ , (8)
where a and µ are positive integers such that n = 2aµ, and δ must satisfy δ > 4(µ -1)β(a). Theorem 6 offers several advantages over the mixing bound (8).

First, the mixing bound involves the so-called "effective sample size" µ = n/2a < n instead of n itself, which makes it less tight, even when focusing only on the complexity term of the bound and R µ (L) that is computed on a subset of µ points. Second, it is only applicable with values of the confidence index δ larger than a quantity that grows with µ, which prevents us from reaching the "practical certainty" of δ ≈ 10 -9 that is often needed in applications such as scenario-based optimization. Finally, the last term of (8) involves the mixing coefficient β(a) that is often unknown and difficult to estimate from the data itself (see [START_REF] Mcdonald | Estimating beta-mixing coefficients via histograms[END_REF] for a discussion of this topic).

Chaining and covering numbers

Chaining [START_REF] Talagrand | Upper and Lower Bounds for Stochastic Processes[END_REF]) is a generic method for estimating the empirical Rademacher complexity of a function class from its covering numbers, defined in terms of an empirical pseudo-metric.

Definition 4 (Pseudo-metric). Given a sequence t n ∈ T n , d 2,tn is the empirical pseudo-metric over the set of functions from T to R defined by

d 2,tn (f, f ) = 1 n n i=1 |f (t i ) -f (t i )| 2 1 2
.

Definition 5 (Covering numbers). Given a class F of functions of T → R and a pseudo-metric ρ, the covering number N ( , F, ρ) at scale of F for the distance ρ is the smallest cardinality of the proper -net H ⊆ F of F such that ∀f ∈ F, ρ(f, H) < . Uniform covering numbers are defined for the pseudo-metric of Definition 4 by

N 2 ( , F, n) = sup tn∈T n N ( , F, d 2,tn ).
Theorem 7 (Chaining). Let F be a real-valued function class over T and, for any t n ∈ T n , let D F = sup (f,f )∈F 2 d 2,tn (f, f ) denote its diameter. Then, for any integer N > 0,

Rtn (F) ≤ D F 2 N + 6D F N j=1 2 -j log N (D F 2 -j , F, d 2,tn ) n .
As we have seen in the examples above, the Rademacher complexity of the loss class L can usually be bounded in terms of the one of the function class F via contraction arguments that merely introduce a factor L ϕ .3 Thus, if we let C(X n , F) denote the bound on the empirical Rademacher complexity of F given by Theorem 7, then after taking expectation and using Jensen's inequality, we obtain

R Zn (L) ≤ L ϕ EC(X n , F) = L ϕ D F 2 N + 6L ϕ D F N j=1 2 -j log EN (D F 2 -j , F, d 2,Zn ) n , (9)
and a bound on the Rademacher complexity given in terms of expected covering numbers. This bound thus depends on the distribution of Z n and would differ on the ghost sample Z n . However, in many cases, the covering numbers are merely bounded by their uniform (worst-case) counterpart, i.e.,

EN (D F 2 -j , F, d 2,Xn ) ≤ sup xn∈X n N (D F 2 -j , F, d 2,xn ) = N 2 (D F 2 -j , F, n),
which are themselves bounded in terms of the fat-shattering dimension (see, e.g., [START_REF] Alon | Scalesensitive dimensions, uniform convergence, and learnability[END_REF]; [START_REF] Mendelson | Rademacher averages and phase transitions in Glivenko-Cantelli classes[END_REF]; [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF]).

Then, the resulting bound,

R n (F) = L ϕ D F 2 N + 6L ϕ D F N j=1 2 -j log N 2 (D F 2 -j , F, n) n ,
on the Rademacher complexity on the training sample applies similarly to the one on the ghost sample, R Z n (F), and this leads, with Theorem 6, to the same result one would have obtained under an i.i.d. assumption.

In addition, if one is reluctant to use the uniform (worst-case) covering numbers, many bounds in the literature on the expected covering numbers are given in terms of the marginal distributions.

For instance, in the multi-category classification setting, [START_REF] Bartlett | Spectrally-normalized margin bounds for neural networks[END_REF] derived a covering numbers bound for a class L of margin loss functions induced by a class of spectrally-regularized deep neural networks, which is of the form

log N ( , L, d 2,Zn ) ≤ A n i=1 X i 2 2 .
This directly yields a bound on the expected log covering numbers that could be used in ( 9) and that is expressed in terms of the marginal distributions, and thus is valid for both the training and the ghost samples.4

Application to scenario-based optimization

A robust optimization program can typically be written as

min θ∈Θ J(θ) (10) s.t. f (x, θ) ≤ 0, ∀x ∈ X ,
with an infinite number of constraints induced by the set X that accounts for the uncertainties in the parameters of the problem. Scenario-based optimization computes solutions to (10) with probabilistic guarantees of feasibility by solving random programs of the form

θ ∈ argmin θ∈Θ J(θ) (11) s.t. f (X i , θ) ≤ 0, i = 1, . . . , n,
where the uncertainties are sampled in order to yield a finite number of constraints. Note that in order to avoid confusion, we kept the notations of the rest of the paper and denote the random quantity as X and the optimization variable as θ (instead of x as is usually done in the robust optimization literature). Here, X n = (X i ) 1≤i≤n is a random sample of "scenarios" X i ∈ X and Θ is a general and deterministic feasible set (think of Θ = R d for instance).

The two critical issues in scenario-based optimization are to estimate the probability of violation of the computed solution,

L n ( θ) = P {f (X 1 , θ) > 0},
where we assume stationarity of X n , and the number of scenarios one should sample to guarantee a certain reliability, i.e., the sample complexity of (11), defined for given , δ ∈ (0, 1) as the smallest n such that

P {L n ( θ) > } ≤ δ (12)
holds.

For independent scenarios, [START_REF] Alamo | Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems[END_REF] proposed upper bounds on the probability of violation and sample complexity estimates based on the VC-dimension of the set of indicator functions

I = {I θ ∈ {0, 1} X : I θ (x) = 1 f (x,θ)>0 , θ ∈ Θ}. ( 13
)
Random programs for which the VC-dimension cannot be bounded can be handled with other results from [START_REF] Lauer | Margin theory for the scenario-based approach to robust optimization in high dimension[END_REF] that are instead based on the Rademacher complexity of the class of margin loss functions,

L γ,Θ = { θ ∈ [0, 1] X : θ (x) = min{1, max{0, 1 + f (x, θ)/γ}}, θ ∈ Θ}, ( 14
)
for a margin γ > 0.

We generalize these results to the case of dependent scenarios below.

Sample complexity of random programs with dependent scenarios and finite VC-dimension

We now consider the case of dependent scenarios, i.e., when X n is a sample of dependent variables. Building on the results of Section 3, we obtain the following sample complexity, which we only state for the zero-error case that is rather standard in the framework of scenario optimization.

Theorem 8. Let X n denote a stationary sequence of random variables of values in X n . Let d V C denote the VC-dimension of the set (13). Assume that, for any x n ∈ X n , the random program (11) is feasible and that an algorithm computes a feasible point θ. Then, for any δ ∈ (0, 1), with probability at least 1 -δ,

P {f (X 1 , θ) > 0} ≤ 4 log Π I (2n) + log 4 δ n ≤ 4d V C log( 2en d V C ) + log 4 δ n ,
and, for any ∈ (0, 1), δ ∈ (0, 1), the sample complexity of ( 11) is no more than

n( , δ) = 5 d V C log 40 + log 4 δ .
Proof. Theorem 4 can be reformulated for the loss (θ, x) = 1 f (x,θ)>0 where f ∈ F is identified with θ ∈ Θ and the growth function and VC-dimension of F are replaced by those of I (13). This yields the bound on the probability of violation above under the assumption that θ is a feasible point for (11), i.e., Ln ( θ) = 0. Then, (12) holds as soon as

4 log Π I (2n) + log 4 δ n ≤ ,
which is implied by

4 2en d V C d V C exp(-n /4) ≤ δ.
Using Theorem 6 in [START_REF] Alamo | Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems[END_REF], this can be ensured by setting

n ≥ inf µ>1 4 µ µ -1 log 4 δ + d V C log 8µ ,
in which the suboptimal choice µ = 5 suffices to conclude.

Here, Theorem 8 yields the same guarantees as [START_REF] Alamo | Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems[END_REF] for scenario optimization, but applies more broadly to dependent scenarios.

Margin-based sample complexity of pseudolinear random programs

For random programs with infinite (or merely too large) VC-dimension, we instead follow the margin-based approach of [START_REF] Lauer | Margin theory for the scenario-based approach to robust optimization in high dimension[END_REF] which, given a margin parameter γ > 0, implements the following random program instead of (11):

θ ∈ argmin θ∈Θ J(θ) (15) s.t. f (X i , θ) ≤ -γ, i = 1, . . . , n.
More specifically, we focus here on problems in which the constraint function is of the form f (x, θ) = max k∈{1,...,C}

f k (x, θ) (16)
for a collection of C functions

f k (x, θ) = ψ k (x) φ k (θ) + η k (x), k = 1, . . . , C, (17)
based on functions

ψ k : X → R n k , φ k : Θ → R n k and η k : X → R. 5
Then, combining the contraction principle (with Lipschitz constant 1/γ) and Theorem 2 in Lauer ( 2023) yields

R Xn (L γ,Θ ) ≤ R n (L γ,Θ ) = 1 γ C k=1 τ k Λ k √ n , ( 18
)
where L γ,Θ is as in ( 14), τ k = sup x∈X ψ k (x) , and Λ k = sup θ∈Θ φ k (θ) .

Note that this bound holds similarly for any ghost sample X n ∈ X n , which leads to the following.

Theorem 9. Let X n denote a stationary sequence of random variables of values in X n . Let τ k = sup x∈X ψ k (x) and Λ k = sup θ∈Θ φ k (θ) . Fix the margin parameter γ > 0 and assume that, for any x n ∈ X n , the random program (15) is feasible and that an algorithm computes a feasible point θ satisfying the margin condition f (x i , θi ) < -γ, i = 1, . . . , n. Then, for any δ ∈ (0, 1), with probability at least 1 -δ,

P {f (X, θ) > 0} ≤ 2 γ C k=1 τ k Λ k √ n + log 1 δ 2n ,
and, for any ∈ (0, 1), δ ∈ (0, 1), the sample complexity of (11) is no more than

n( , δ) = 1 2 2 γ C k=1 τ k Λ k + log 1 δ 2 .
Proof. Apply Theorem 5 to the loss class ( 14) and use ( 18) to bound the two Rademacher complexities. Then, the bound on the probability of violation follows from the feasibility of θ, that ensures that Ln ( θ) computed with the margin loss γ (θ, x) = min{1, max{0, 1 + f (x, θ)/γ}} is zero, and the fact that

P {f (X, θ) > 0} ≤ P {f (X, θ) > -γ} = L n ( θ).
Then, (12) holds as soon as

2 γ C k=1 τ k Λ k √ n + log 1 δ 2n ≤ ,
which is ensured whenever n ≥ n( , δ).

Again, the proposed method yields with Theorem 9 the same guarantees as [START_REF] Lauer | Margin theory for the scenario-based approach to robust optimization in high dimension[END_REF] for scenario optimization, but in a more general setting that allows the sampling of dependent scenarios.

Conclusions

This paper explored the possible extensions of standard risk bounds to dependent data. This resulted in a number of uniform risk bounds applicable to a wide range of problems. Compared with other approaches from the literature for deriving uniform bounds without assuming independence, the proposed method provides tighter bounds and does not rely on a mixing condition difficult to verify in practice.

Yet, one drawback of the proposed approach is the lack of data-dependent counterparts of the bounds. However, as seen on a number of examples, data-dependent bounds do not offer improved guarantees in several classical cases. In addition, regarding the motivating application of scenario-based optimization, where the focus is on the sample complexity, data-dependent bounds are irrelevant. In this context, we showed that standard results so far limited to the i.i.d. case also hold with dependent scenarios. This provides the basis for a refined analysis of several problems in control theory such as that of [START_REF] Wang | Data-driven feedback stabilization of switched linear systems with probabilistic stability guarantees[END_REF], and the basic tool for investigating new sampling strategies in robust optimization.

Another open issue arises in scenario-based optimization, where the standard bounds for convex random programs [START_REF] Campi | The exact feasibility of randomized solutions of uncertain convex programs[END_REF][START_REF] Calafiore | Random convex programs[END_REF] heavily rely on a binomial tail bound and independence. As these follow a proof scheme rather different than that of learning theory bounds, the current work does not allow their extension to dependent scenarios, which would allow for a straightforward strengthening of the results of [START_REF] Wang | Data-driven feedback stabilization of switched linear systems with probabilistic stability guarantees[END_REF].

A Proof of Theorem 1

Let (W i ) 1≤i≤n be a random sequence adapted to (A i ), i.e., a sequence of real-valued A i -measurable random variables. Recall that an A i-1 -measurable variable is said to be predictable. Define

S n = n i=1 W i .
We will first state a few intermediate results on generic variables W i that are necessary for the proof of Theorem 1.

Lemma 3 (Hoeffding's lemma, slightly extended). For predictable random variables

L i ≤ W i ≤ U i with E[W i | A i-1 ] = 0, E[e βW i | A i-1 ] ≤ e β 2 (U i -L i ) 2 /8 .
Proof. Replace the constant bounds by L i , U i and the expectation by the conditional expectation in the standard proof of [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]: by convexity of the exponential,

e βW i ≤ U i -W i U i -L i e βL i + W i -L i U i -L i e βU i and E[e βW i | A i-1 ] ≤ E U i -W i U i -L i e βL i A i-1 + E W i -L i U i -L i e βU i A i-1 .
Then, use the fact that the L i and U i are predictable and

E[W i | A i-1 ] = 0: E[e βW i | A i-1 ] ≤ U i -E[W i | A i-1 ] U i -L i e βL i + E[W i | A i-1 ] -L i U i -L i e βU i = U i U i -L i e βL i + -L i U i -L i e βU i = e h(β(U i -L i )) with h(u) = uL i /(U i -L i ) + log(1 + L i [(1 -e u )/(U i -L i )]
). By computing derivatives and the Taylor expansion, we know that h(u) ≤ u 2 /8, which completes the proof.

Lemma 4 (Lemma 2.4 in van De Geer ( 2007)

). Assume E[W i | A i-1 ] = 0 and L i ≤ W i ≤ U i with L i and U i that are predictable (i.e., A i-1 -measurable).
For any β > 0, the sequence of random variables

ζ n (β) = exp βS n -β 2 n i=1 (U i -L i ) 2 /8 , n = 1, 2, . . . , is a supermartingale, i.e., E[ζ n (β) | A n-1 ] ≤ ζ n-1 (β).
Proof.

E[ζ n (β) | A n-1 ] = E exp β n i=1 (W i -β(U i -L i ) 2 /8) | A n-1 = E exp β(W n -β(U n -L n ) 2 /8) n-1 i=1 exp β(W i -β(U i -L i ) 2 /8) | A n-1
Here, the assumed predictability of L i , U i implies that, for any function

f , ∀i ≤ n -1, E[f (W i , L i , U i ) | A n-1 ] = f (W i , L i , U i ). Thus, E[ζ n (β) | A n-1 ] = n-1 i=1 exp β(W i -β(U i -L i ) 2 /8) × E exp β(W n -β(U n -L n ) 2 /8) | A n-1 ≤ n-1 i=1 exp β(W i -β(U i -L i ) 2 /8) = exp β n-1 i=1 (W i -β(U i -L i ) 2 /8) = ζ n-1 (β),
where we used Lemma 3 for the inequality.

Theorem 10 (Hoeffding inequality for sums-simplified version of Theorem 2.5 in [START_REF] Van De Geer | On Hoeffding's inequality for dependent random variables[END_REF] with fixed n). Assume that L i ≤ W i ≤ U i for predictable random variables L i and U i , i.e., they are A i-1 -measurable. Also assume that E[W i | A i-1 ] = 0. Then, for any t > 0 and c > 0,

P S n ≥ t and n i=1 (U i -L i ) 2 ≤ c 2 ≤ exp(-2t 2 /c 2 ).
Proof. By Lemma 4, ζ n (β) is a supermartingale. Thus, for any n,

Eζ n (β) = EE[ζ n (β) | A n-1 ] ≤ Eζ n-1 (β)
and, by induction,

Eζ n (β) ≤ Eζ 1 (β) = E exp(βS 1 -β 2 (U 1 -L 1 ) 2 /8) = E exp(βW 1 -β 2 (U 1 -L 1 ) 2 /8) = E[exp(βW 1 -β 2 (U 1 -L 1 ) 2 /8) | A 0 ] (since A 0 = ∅) ≤ 1,
where we used Lemma 3 for the last inequality. Now consider the event

A = S n > t and n i=1 (U i -L i ) 2 ≤ c 2 . Then, since ζ n (β)1 A ≤ ζ n (β), E[ζ n (β)1 A ] ≤ E[ζ n (β)] ≤ 1.
But on A, we have

ζ n (β) = exp βS n -β 2 n i=1 (U i -L i ) 2 /8 ≥ exp(βt -β 2 c 2 /8), so that E[ζ n (β)1 A ] ≥ E[exp(βt -β 2 c 2 /8)1 A ] = exp(βt -β 2 c 2 /8)E[1 A ] = exp(βt -β 2 c 2 /8)P (A).
Thus,

P (A) ≤ 1 exp(βt -β 2 c 2 /8) = exp(-βt + β 2 c 2 /8).
Now set β = 4t/c 2 , this yields

P (A) ≤ exp(-4t 2 /c 2 + 16t 2 /8c 2 ) = exp(-2t 2 /c 2 ).
Now, we are ready to state the proof of Theorem 1.

Let us define the random variables G = g(Z 1 , . . . , Z n ) and

W i = E[G | A i ]- E[G | A i-1 ]. Then, g(Z 1 , . . . , Z n ) -Eg(Z 1 , . . . , Z n ) = G -EG = E[G | A n ] -E[G | A 0 ] = n i=1 E[G | A i ] -E[G | A i-1 ] = n i=1 W i .
Therefore, the theorem is just an application of Theorem 10 to S n = n i=1 W i , after checking that

E[W i | A i-1 ] = E [ E[G | A i ] | A i-1 ] -E [ E[G | A i-1 ] | A i-1 ] = E[G | A i-1 ] -E[G | A i-1 ] = 0
(due to the tower property, since A i-1 ⊂ A i ). Actually, to apply Theorem 10, we also need predictable (A i-1 -measurable) bounds on W i . First note that

L i = inf z E [g(Z 1 , . . . , Z i-1 , z, Z i+1 , . . . , Z n ) | A i ]
and

U i = sup z E [g(Z 1 , . . . , Z i-1 , z, Z i+1 , . . . , Z n ) | A i ]
are A i-1 -measurable (since Z i is replaced by an arbitrary z in their definition) and satisfy

L i ≤ E[G | A i ] ≤ U i ,
while the bounded difference assumption ensures that U i -L i ≤ c i . So, since

W i = E[G | A i ] -E[G | A i-1 ],
we have the following predictable bounds:

Li = L i -E[G | A i-1 ] ≤ W i ≤ U i -E[G | A i ] = Ũi
with Ũi -Li ≤ c i . Thus, with c 2 = n i=1 c 2 i , n i=1 ( Ũi -Li ) 2 ≤ c 2 always holds and, by Theorem 10: for any t > 0,

P (S n > t) = P S n > t and n i=1 ( Ũi -Li ) 2 ≤ c 2 ≤ exp(-2t 2 /c 2 ).
Recalling that S n = g(Z 1 , . . . , Z n ) -Eg(Z 1 , . . . , Z n ) and choosing t = completes the proof.

B Proof of Lemma 1

Define the events

A(f ) = L n (f ) -Ln (f ) ≥ , A = sup f ∈F L n (f ) -Ln (f ) ≥ B(f ) = L n (f ) -Ln (f ) ≥ 2 , B = sup f ∈F L n (f ) -Ln (f ) ≥ 2 .
Let f * ∈ F denote the function that depends solely on Z n and such that6

L n (f * ) -Ln (f * ) = sup f ∈F L n (f ) -Ln (f ).
Then, since f * ∈ F, we have

P (B) ≥ P {B(f * )}.
For any real numbers a, b, c,

(c -a) ≥ ∧ (b -c) ≥ - 2 ⇒ b -a ≥ 2 ,
and thus

P (b -a ≥ /2) ≥ P (c -a ≥ , b -c ≥ -/2).
Applied with a = Ln (f * ), b = L n (f * ) and c = L n (f * ), this gives:

P {B(f * )} ≥ P L n (f * ) -Ln (f * ) ≥ , L n (f * ) -L n (f * ) ≥ - 2 = P A(f * ), L n (f * ) -L n (f * ) ≥ - 2 = E1 A(f * ) 1 L n (f * )-Ln(f * )≥ - 2 = EE 1 A(f * ) 1 L n (f * )-Ln(f * )≥ - 2 Z n = E1 A(f * ) E 1 L n (f * )-Ln(f * )≥ - 2 Z n = E1 A(f * ) P L n (f * ) -L n (f * ) ≥ - 2 Z n .
The probability in the latter can be bounded as

P L n (f * ) -L n (f * ) ≥ - 2 Z n = P L n (f * ) -L n (f * ) ≤ 2 Z n + P L n (f * ) -L n (f * ) > 2 Z n ≥ P L n (f * ) -L n (f * ) ≤ 2 Z n ≥ 1 -P L n (f * ) -L n (f * ) > 2 Z n ≥ 1 2 ,
where the last inequality is obtained from (a conditional form of) Bienaymé-Chebyshev's inequality applied to the random variable L n (f * ) whose expectation is L n (f * ) by construction of the ghost sample (Z i ∼ Z i ):

E L n (f * ) = 1 n n i=1 E (f * (X i ), Y i ) = 1 n n i=1 E (f * (X i ), Y i ) = L n (f * ).
Note that we can apply this inequality here since given Z n , f * is fixed and independent of Z n . Moreover, by the independence of Z n and Z n :

E ( L n (f * ) -L n (f * )) 2 | Z n ≤ sup f ∈F E ( L n (f ) -L n (f )) 2 = sup f ∈F V ar L n (f ) = 1 n 2 sup f ∈F n i=1 V ar (f (X i ), Y i ) ≤ B 2 4n ,
where the two last lines are due to the independence of the Z i and the fact that, for any f , (f

(X i ), Y i ) ∈ [0, B]. Thus, P L n (f * ) -L n (f * ) ≥ 2 Z n ≤ 4E ( L n (f * ) -L n (f * )) 2 | Z n 2 ≤ B 2 n 2 ≤ 1 2 ,
since, by assumption, n 2 > 2B 2 . Therefore, we have shown that

P (B) ≥ P {B(f * )} ≥ 1 2 E1 A(f * ) = 1 2 P {A(f * )} = 1 2 P (A)
and this concludes the proof.

C Proof of Theorem 3

We will prove that

P sup f ∈F L n (f ) -Ln (f ) ≥ ≤ 2Π F (2n) exp(-n 2 /8), (19)
which implies the first inequality of Theorem 3 if we let δ = 2Π F (2n) exp(-n 2 /8) and solve this equation for . The second inequality is then obtained by bounding the growth function by the VC-dimension with Sauer's lemma [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF], as usual.

By Lemma 1, we only have to bound the deviation between the empirical risk on the training sample and the one on the ghost sample. Let σ n = (σ i ) 1≤i≤n denote a sequence of independent Rademacher variables uniformly distributed in {+1, -1}. Then, this random quantity,

D = L n (f ) -Ln (f ) = 1 n n i=1 1 f (X i ) =Y i -1 f (X i ) =Y i , is identically distributed to D = 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ),
since (X i , Y i ) and (X i , Y i ) are independent and identically distributed, which makes (1 f (X i ) =Y i -1 f (X i ) =Y i ) a symmetric random variable whose distribution remains unchanged after multiplication by a random sign σ i . Thus,

P sup f ∈F L n (f ) -Ln (f ) > 2 = E1 sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) > 2 = E E 1 sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) > 2 Z n , Z n = E P σ n : sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) > 2 Z n , Z n = E P D n : sup f ∈F 1 n n i=1 D i > 2 Z n , Z n ,
where we let

D n = (D i ) 1≤i≤n and D i = σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ).
For any fixed f and Z n , Z n , the conditional expectation of these variables is zero:

E[D i | Z n , Z n ] = (1 f (X i ) =Y i -1 f (X i ) =Y i )Eσ i = 0.
Thus, by applying Hoeffding inequality (Theorem 2) on the sequence of independent variables D n , we obtain

P 1 n n i=1 D i > 2 Z n , Z n ≤ exp -n 2 2 2 n i=1 c 2 i , where c i = b i -a i with a i ≤ D i ≤ b i and a i = -1, b i = 1. This gives c 2 i = 4 and ∀f ∈ F, P 1 n n i=1 D i > 2 Z n , Z n ≤ exp -n 2 8 . Therefore, with F XnX n = {(f (X 1 ), . . . , f (X n ), f (X 1 ), . . . , f (X n )) : f ∈ F}, by the union bound, P D n : sup f ∈F 1 n n i=1 D i > 2 Z n , Z n ≤ |F XnX n | exp -n 2 2
and the conclusion stems from Lemma 1 and Definition 1.

D Proof of Lemma 2

The proof follows the lines of that of Lemma 2 in [START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF] and makes use of the following.

Lemma 5 (Theorem 1 in [START_REF] Greenberg | Tight lower bound on the probability of a binomial exceeding its expectation[END_REF]). For any positive integer m and any probability p such that p > 1/m, let X be a random variable distributed according to the binomial distribution with m trials and probability of success of each trial p. Then, EX = mp and

P (X ≥ EX) > 1 4 .
Moreover, given Z n , f * is fixed and if L n (f * ) > 2 , then under the assumption n > 1, L n (f ) > 1/n. Then, by stationarity and the construction of the ghost sample, the Z i are i.i.d., which makes the quantity

n L n (f * ) = n i=1 1 f * (X i ) =Y i
distributed according to a binomial distribution with m = n trials and probability of success p

= P (f * (X i ) = Y i ) = P (f * (X i ) = Y i ) = L n (f * ) > 1/m. Thus, by Lemma 5, P {B(f * ) | Z n } > 1/4 and, in the case L n (f * ) > 2 , P {C(f * )} ≥ E1 A(f * ) /4 and P {A(f * )} ≤ 4P {C(f * )}. In the other case, if L n (f * ) ≤ 2 , then A(f * ) cannot hold and P {A(f * )} = 0 ≤ 4P {C(f * )}.
So, in any case:

P sup f ∈F L n (f ) -Ln (f ) L n (f ) ≥ = P {A(f * )} ≤ 4P {C(f * )} ≤ 4P    sup f ∈F L n (f ) -Ln (f ) ( Ln (f ) + L n (f ) + 1 n )/2 >    ,
where the first equality is due to the choice of f * and the last inequality is due to f * ∈ F.

E Proof of Theorem 4

We proceed as in the proof of Theorem 3 (see App. C) with a sequence σ n = (σ i ) 1≤i≤n of independent Rademacher variables uniformly distributed in {+1, -1} and by taking advantage of the symmetry of the (1 f (

X i ) =Y i - 1 f (X i ) =Y i ): P    sup f ∈F L n (f ) -Ln (f ) ( Ln (f ) + L n (f ) + 1 n )/2 >    = E1    sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) ( Ln (f ) + L n (f ) + 1 n )/2 >    = E E   1    sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) ( Ln (f ) + L n (f ) + 1 n )/2 >    Z n , Z n   = E P    σ n : sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) ( Ln (f ) + L n (f ) + 1 n )/2 > Z n , Z n    = E P D n : sup f ∈F 1 n n i=1 D i > Z n , Z n ,
where we let D n = (D i ) 1≤i≤n and D i =

σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) ( Ln(f )+ L n (f )+ 1 n )/2
. Since Eσ i = 0, for any fixed f and Z n , Z n , we have E[D i | Z n , Z n ] = 0. Thus, by applying Hoeffding inequality (Theorem 2) on the sequence of independent variables D n , we obtain

P 1 n n i=1 D i > Z n , Z n ≤ exp -2n 2 2 n i=1 c 2 i
, where c i = b i -a i with a i ≤ D i ≤ b i . In particular, we have

a i = -|1 f (X i ) =Y i -1 f (X i ) =Y i | ( Ln (f ) + L n (f ) + 1 n )/2 = -|1 f (X i ) =Y i -1 f (X i ) =Y i | 1 n (1 + n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i )/2 = -|1 f (X i ) =Y i -1 f (X i ) =Y i | √ 2n 1 + n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i
and, similarly:

b i = |1 f (X i ) =Y i -1 f (X i ) =Y i | √ 2n 1 + n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i , which gives
c 2 i =   2|1 f (X i ) =Y i -1 f (X i ) =Y i | √ 2n 1 + n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i   2 = 8n(1 f (X i ) =Y i -1 f (X i ) =Y i ) 1 + n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i ≤ 8n(1 f (X i ) =Y i -1 f (X i ) =Y i ) 2 n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i and n i=1 c 2 i ≤ 8n n i=1 (1 f (X i ) =Y i -1 f (X i ) =Y i ) 2 n i=1 1 f (X i ) =Y i + 1 f (X i ) =Y i ≤ 8n,
where the last inequality is due to

(1 f (X i ) =Y i -1 f (X i ) =Y i ) 2 = 1 2 f (X i ) =Y i + 1 2 f (X i ) =Y i -21 f (X i ) =Y i 1 f (X i ) =Y i ≤ 1 f (X i ) =Y i + 1 f (X i ) =Y i .
Thus, for any f ∈ F,

P    σ n : 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) ( Ln (f ) + L n (f ) + 1 n )/2 > Z n , Z n    ≤ exp -n 2 4
and, with F XnX n = {(f (X 1 ), . . . , f (X n ), f (X 1 ), . . . , f (X n )) : f ∈ F}, by the union bound,

P    σ n : sup f ∈F 1 n n i=1 σ i (1 f (X i ) =Y i -1 f (X i ) =Y i ) ( Ln (f ) + L n (f ) + 1 n )/2 > Z n , Z n    ≤ |F XnX n | exp -n 2 4 .
Gathering it all and using Lemma 2:

P sup f ∈F L(f ) -Ln (f ) L(f ) > ≤ 4P    sup f ∈F L n (f ) -Ln (f ) ( Ln (f ) + L n (f ) + 1 n )/2 >    ≤ 4E|F XnX n | exp -n 2 4 ≤ 4Π F (2n) exp -n 2 4 .
By setting δ = 4Π F (2n) exp(-n 2 /4), we obtain that, with probability at least 1 -δ, in which the growth function Π F (2n) can be bounded in terms of the VCdimension d V C by Sauer's lemma [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF].

F Proof of Theorem 5

We will show that, with probability at least 1 -δ,

sup f ∈F L n (f ) -Ln (f ) ≤ R Zn (L) + R Z n (L) + B log 1 δ 2n .
Let us first rewrite, with a slight abuse of notation, the loss as (Z i ) = (f (X i ), Y i ). Then, we apply a bounded difference inequality to

g(Z 1 , . . . , Z n ) = sup f ∈F L n (f ) -Ln (f ) .
If (Z i ) ∈ [0, B], then the bounded difference condition with c i = B/n is satisfied and we can apply Theorem 1. By setting δ = exp(-2t 2 / n i=1 c 2 i ) = exp(-2nt 2 /B 2 ), and thus t = B log(1/δ)/2n, we get that, with probability at least 1 -δ,

sup f ∈F L n (f ) -Ln (f ) ≤ E sup f ∈F L n (f ) -Ln (f ) + B log 1 δ 2n . ( 20
)
Then, introduce the ghost sample Z n and use its independence with Z n and Z i ∼ Z i to write

E 1 n n i=1 (Z i ) Z n = E 1 n n i=1 (Z i ) = 1 n n i=1 E (Z i ) = L n (f ),
and thus

E sup f ∈F L n (f ) -Ln (f ) = E sup f ∈F E 1 n n i=1 (Z i ) Z n - 1 n n i=1 (Z i ) = E sup f ∈F E 1 n n i=1 (Z i ) - 1 n n i=1 (Z i ) Z n ≤ EE sup f ∈F 1 n n i=1 (Z i ) -(Z i ) Z n = E sup f ∈F 1 n n i=1 (Z i ) -(Z i ) ,
where we used Jensen's inequality in the third line.

Then, we can introduce Rademacher variables as follows. As in the proof of Theorem 3, the variables ( (Z i ) -(Z i )) are symmetric by construction of the ghost sample that ensures that Z i ∼ Z i and Z i is independent of Z i . Thus, for any σ n = (σ i ) 1≤i≤n ∈ {-1, +1} n chosen independently of Z i and Z i , we can replace them by σ i ( (Z i ) -(Z i )) without changing the resulting expectation. Furthermore, averaging over all the 2 n sequences of σ i does not change the result either. This leads to

E sup f ∈F 1 n n i=1 (Z i ) -(Z i ) = E sup f ∈F 1 n n i=1 σ i (Z i ) -(Z i ) ≤ E sup f ∈F 1 n n i=1 σ i (Z i ) + E sup f ∈F 1 n n i=1 -σ i (Z i ) = E sup f ∈F 1 n n i=1 σ i (Z i ) + E sup f ∈F 1 n n i=1 σ i (Z i ) = R n (L) + R n (L),
where we used σ i ∼ -σ i in the third line. Together with (20), this completes the proof.

G Proof of (6)

For any z n ∈ Z n , by the contraction principle [START_REF] Ledoux | Probability in Banach Spaces: Isoperimetry and Processes[END_REF], we have Rzn (L) ≤ 4M Rxn (F). Then, the computations of [START_REF] Bartlett | Rademacher and Gaussian complexities: Risk bounds and structural results[END_REF] give

Rxn (F) ≤ Λ n i=1 X i 2 n ≤ Λ sup x∈X x √ n
for linear models. For kernel models, the norms X i are replaced by K(X i , •) = K(X i , X i ), which is 1 for the Gaussian kernel.

  A ≤ B √ A + C ⇒ A ≤ B 2 + B √ C + C yields L(f ) ≤ Ln (f ) + L(f )2 log Π F (2n) + log 4

A filtration is a sequence of increasing σ-algebras ∅ = A 0 ⊂ A 1 ⊂ A

⊂ • • • ⊂ A n and a sequence of random variables is adapted to it if each Z i is A i -measurable.

With the loss (4), the risk (1) is just the probability of misclassification P (f (X) = Y ) for stationary sequences.

The factor L ϕ is the Lipschitz constant of the univariate function ϕ used to compute the loss (f (x), y) = ϕ(u), where u is for instance yg(x) for margin classification or f (x) -y for regression.

Note that when formulating (9), we could have applied Jensen's inequality only to the square root and express the bound in terms of expected log coverging numbers.

The results actually hold for a more general form of composition in (16), as detailed in[START_REF] Lauer | Margin theory for the scenario-based approach to robust optimization in high dimension[END_REF].

In case this is not possible, choose f * as the function for which the difference is η-close to the supremum and take the limit η → 0 to conclude as in[START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF].

In case this is not possible, choose f * as the function for which the ratio is η-close to the supremum and take the limit η → 0 to conclude as in[START_REF] Cortes | Relative deviation learning bounds and generalization with unbounded loss functions[END_REF].

For any f ∈ F, consider the events

Then

To see this, first note that

which also implies < L n (f ). Then, also note that, for all a, b > 0, the function

is increasing in a and decreasing in b (the derivatives are positive and negative). Thus,

, where, on B(f ),

(because < L n (f )). Since we assume n 2 > 1 and thus 2 > 1/n, we have

Now, let f * ∈ F denote the function that depends solely on Z n and such that 7

L n (f * ) -Ln (f * )

Then, by the discussion above,