Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
49,244 characters · 6 sections · 31 citation commands
Concentration Inequalities for Suprema of Empirical Processes with Dependent Data via Generic Chaining with Applications to Statistical Learning
\symbolfootnote[0]{\\ $^{\dag}$ Department of Economics and Business, Universitat Pompeu Fabra and Barcelona SE;\\ e-mail: [email removed], [email removed], [email removed].\\ $^*$ Corresponding author. \\ We have benefited from discussions with Gabor Lugosi.\\ Christian Brownlees acknowledges support from the Spanish Ministry of Science and Technology (Grant MTM2012-37195); the Ayudas Fundaci\'on BBVA Proyectos de Investigación Cient\`ifica en Matemáticas 2021; the Spanish Ministry of Economy and Competitiveness through the Severo Ochoa Programme for Centres of Excellence in R&D (SEV-2011-0075).}
\doublespace
Bounds for the suprema of stochastic processes have numerous applications in statistics, econometrics, and machine learning. A powerful and general technique used to obtain such bounds is generic chaining. Classical chaining consists of bounding the supremum of a stochastic process by constructing a sequence of increasingly fine partitions of the index set and appropriately controlling the process’ increments across the different partitions. Generic chaining refines classical chaining by optimizing over the admissible sequences of partitions, typically leading to sharper bounds. This technique was pioneered by Michel Talagrand, who was awarded the Abel Prize in 2024 in part for this key contribution to the theory of stochastic processes. Talagrand2005, Vandervaart and Boucheron provide, among others, a comprehensive treatment of this topic.
A classic application of generic chaining consists in obtaining concentration inequalities for the suprema of empirical processes. The majority of applications in the literature, however, rely on the assumption that the underlying data are independent and identically distributed. This is not appealing for applications in econometrics, where it is often more realistic to assume that the data exhibit dependence. This paper establishes a novel general concentration inequality for suprema of empirical processes with dependent data. We do so by combining the generic chaining argument Talagrand2005 with a coupling argument to deal with the dependence MerlevedePeligrad2002. We demonstrate the usefulness of our result by obtaining non-asymptotic predictive performance guarantees for empirical risk minimization in statistical learning problems.
We begin by introducing a general concentration result for the supremum of an empirical process with dependent data. We consider a (possibly nonlinear) function that depends on a random vector and a parameter belonging to some parameter space. We then study the empirical process indexed by the parameter which is given by the average of the functions over a sequence of dependent random vectors. The dependence structure of the sequence is characterized using the notion of $\beta$-mixing Doukhan:1994. Our main theorem is based on two high-level assumptions: an increment condition and a coupling condition. These two conditions allow us to develop, respectively, the generic chaining and the coupling arguments required to establish the main claim of the theorem. The increment condition states that the sub-Weibull quasi-norm of the difference of the function evaluated in two parameter values, for the same random vector, is bounded by their distance. The coupling condition states that the expected supremum (over the parameter space) of the absolute difference of the function evaluated in two random vectors, for the same parameter, is bounded by the $L_r$-norm of their distance. This condition enables the use of a coupling lemma MerlevedePeligrad2002, which allows us to approximate the sequence of dependent random vectors with an i.i.d. sequence of random vectors with the same marginal distribution.
Our main theorem establishes a general concentration inequality for the supremum of empirical processes with dependent data, extending classical i.i.d. results. The bound on the supremum of the empirical process depends on the so called Talagrand's functional, which captures the complexity of the parameter space, and on a coupling correction term accounting for the approximation error introduced when replacing the sequence of dependent random vectors with an independent copy. The bounds is governed by a key quantity that we refer to as the effective sample size. When observations are dependent, each additional observation provides less incremental information compared to the i.i.d. case, and the effective sample size quantifies this loss of information due to dependence.
We apply our concentration result to study the properties of empirical risk minimization. Empirical risk minimization is a classic principle in statistical learning theory to choose a prediction rule for forecasting. It consists of choosing the prediction rule that minimizes the average loss over the observed data, which is called the empirical risk. A central problem in statistical learning theory is to understand the predictive performance of the empirical risk minimizer (ERM). Using our results, we derive predictive performance guarantees for the ERM for nonlinear regression with dependent data. In particular, we establishes a non-asymptotic oracle inequality for the ERM under mild conditions on the regression model. The result implies that the predictive performance of the ERM approaches the best attainable performance at a rate that matches the so-called “classical” convergence rate of empirical risk minimization Devroye:Gyorfi:Lugosi:1996 once the sample size is replaced by the effective sample size. As a special illustration of the general framework, we obtain predictive performance guarantees for a single-layer neural network model. Overall, our results show that empirical risk minimzaton with dependent data attains a prediction accuracy comparable to that in the i.i.d. setting for a wide range of nonlinear regression models.
This paper is related to different strands of the literature. First it is related to the literature on generic chaining. In addition to the works we have already cited, additional important references on chaining and generic chaining include pollard1984convergence, vandegeer2000 and Kosorok. Introductory exposition on chaining and generic chaining is provided by Wainwright_2019 and Vershynin, among others. Second, this work is related to the literature on empirical risk minimization with dependent data. Contributions in this literature include Jiang:Tanner:2010, Brownlees:Gudmundsson:2021 and Brownlees:LlorensTerrazas:2021.
The rest of the paper is outlined as follows. Section (ref) introduces the basic framework, the assumptions and the main theorem of this paper. Section (ref) applies the main theorem in the context of statistical learning to obtain non-asymptotic prediction performance guarantees for empirical risk minimization for a fairly large class of nonlinear regression models and, as a special case, single-layer neural network. Section (ref) outlines the proof of the main theorem. Concluding remarks follow in Section (ref). Additional proofs and results are collected in Appendix (ref).
Let \( \{ g_{\bm \theta} : \bm \theta \in \Theta \} \) be a class of real-valued functions defined on \( \mathcal Z \subset \mathbb R^d \) indexed by $\bm \theta \in \Theta$. Let $\{ \bm Z_t \}$ be a dependent sequence of random vectors where $\bm Z_t$ takes values in $\mathcal Z$ for each $t$. Our main objective consists in controlling the supremum of the empirical process associated with the average of the functions $g_{\bm \theta}$ based on the a sequence $\{ \bm Z_1, \ldots, \bm Z_T \}$, that is \[ \sup_{\bm \theta \in \Theta} \left| {1\over T} \sum_{t=1}^T g_{\bm \theta}(\bm Z_t) - \mathbb E(g_{\bm \theta}(\bm Z_t)) \right| ~. \] In what follows we refer to $T$ as the sample size. Such a problem arises frequently in statistics, econometrics and machine learning. In the following section, we will show how controlling the supremum of the empirical process is key to obtain prediction performance guarantees in statistical learning problems.
Our concentration result relies on two high level assumptions that we present below. Before stating the first of these two assumptions we need to introduce the notion of a sub-Weibull random variable of order $\alpha$, for some $\alpha > 0$ WongTewari:2020. Let $\psi_\alpha(x) = \exp(x^\alpha) - 1$ for some $\alpha>0$ and define the quasi-norm of a random variable $X$ as
We refer to $\| \cdot \|_{\psi_\alpha}$ as the sub-Weibull($\alpha$) quasi-norm, and we say that a random variable $X$ is sub-Weibull($\alpha$) if $\| X \|_{\psi_\alpha} < \infty$. We recall that the special cases $\alpha = 2$ and $\alpha = 1$ correspond, respectively, to the familiar notions of sub-Gaussian and sub-exponential random variables. Additional details and properties of sub-Weibull($\alpha$) random variables are provided in Appendix (ref).
(ref) implies that the increments of the empirical process exhibit sub-Weibull-type behaviour. This is a standard type of condition required to develop the chaining argument. We remark that we state (ref) for demeaned random variables for convenience. It follows from the basic properties of sub-Weibull random variables that if $X$ is sub-Weibull of order $\alpha$ then $X - \mathbb E(X)$ is also sub-Weibull of order $\alpha$ (Proposition (ref)).
(ref) implies that the expected absolute difference between the empirical processes associated with two copies of the sequence $\{ \bm Z_t \}$ can be bounded by the average $L_r$-norm of the distance between the random vectors in the two sequences. We also remark that the requirement that $(\mathcal Z,d_{\mathcal Z})$ is a Polish space is a technical condition required to apply a coupling result and that it is typically straightforward to verify. This is a key condition required to develop the coupling argument.
Before stating our main concentration result, we introduce two key concepts: Talagrand's functional and the absolute regularity coefficients.
Talagrand's functional is a measure of complexity of a class of functions Talagrand2005. We say that a sequence of partition $\{ \mathcal A_k \}_{k\geq 0}$ of $\Theta$ is admissible if the sequence is increasing\footnote{An increasing sequence of partitions means that every set of $\mathcal A_{k+1}$ is included in a set of $\mathcal A_k$.} and it is such that $| \mathcal A_k | \leq 2^{2^k}$ for $k=0,1,\ldots$. For any $\bm \theta \in \Theta$, denote by $A_k(\bm \theta)$ the unique element of $\mathcal A_k$ that contains $\bm \theta$. Let $\Delta(A)$ denote the diameter of the set $A \subset \Theta$ associated with the distance $d_\Theta$. Finally, for $\alpha>0$ Talagrand's functional $\gamma_\alpha$ is defined as \[ \gamma_\alpha(\Theta) = \inf_{\mathcal A_k} \sup_{\bm \theta \in \Theta} \sum_{k\geq 0} 2^{k/\alpha} \Delta( A_k(\bm \theta) ) ~, \] where the infimum is taken over all admissible sequences. It follows from standard arguments (Proposition (ref)) that \[ \gamma_\alpha(\Theta) \leq \log (2)^{1/\alpha} \left(1 - \frac{1}{2^{1/\alpha}}\right) \int_{0}^{\Delta(\Theta)} \big(\log \mathcal{N}(\Theta,\varepsilon)\big)^{1/\alpha} \, d\varepsilon ~, \] where $\mathcal{N}(\Theta, \varepsilon)$ denotes the covering number of $\Theta$ at scale $\varepsilon > 0$.
The absolute regularity coefficients, also known as $\beta$-mixing coefficients, measure the degree of dependence among the coordinates of the process $\{ \bm Z_t \}$ Doukhan:1994. Let $\mathcal{F}_{-\infty}^t$ and $\mathcal{F}_{t+l}^{\infty}$ be the $\sigma$-algebras generated by $\lbrace \bm Z_s: -\infty \leq s \leq t\rbrace$ and $\lbrace \bm Z_s: t + l \leq s \leq \infty\rbrace$ respectively. The $\beta$-mixing coefficient of order $l$, for $l\geq 0$, is defined as
where the inner supremum in the definition is taken over all pairs of partitions $\mathcal U = \{ U_1, \ldots, U_I \}$ and $\mathcal V = \{ V_1, \ldots, V_J \}$ of the sample space such that $U_i \in \mathcal{F}_{-\infty}^t$ and $V_j \in \mathcal{F}_{t+l}^{\infty}$ for all $i,j$.
Finally, we can state our main theorem.
A few remarks on Theorem (ref) are in order. To simplify the discussion it is useful to introduce a special version of the theorem. Our result implies that for any $n \in \{ 1 , \ldots , T \}$ and any $\varepsilon\geq 2$ the inequality
holds at most with probability \(13 (T/n)\exp( - \varepsilon ) \), where $C_\alpha$ is the same constant that appears in the statement of the theorem. This is obtained by choosing $\varepsilon_1 = \varepsilon$ and $\varepsilon_2 = \beta^{s/(r(r+s))}\left( \left\lfloor{T \over n+1}\right\rfloor \right) \exp( \varepsilon)$.
First, it is important to emphasize that the bound on the supremum of the empirical process is controlled by the variable $n$, which may be interpreted as the effective sample size. Intuitively, when observations are dependent the incremental information provided by an additional observation is in some sense smaller in comparison to the i.i.d. case and the variable $n$ captures the loss of information due to dependence.
Second, the supremum of the empirical process is bounded by three terms. The first two terms depend, respectively, on the Talagrand's functionals $\gamma_2(\Theta)$ and $\gamma_\alpha(\Theta)$, which capture the complexity of the parameter space $\Theta$. When \( \alpha \geq 2 \) the first term dominates and we recover the classic sub-Gaussian concentration rate, with the effective sample size \( n \) playing the role typically held by the (actual) sample size \( T \) in the i.i.d. setting. On the contrary, when $\alpha<2$, the second term dominates, leading to a slower concentration rate, which is still controlled by the effective sample size $n$. The third term depends on the $\beta$-mixing coefficients and may be interpreted as a correction term arising from the fact that the sequence of random vectors is dependent rather than independent. It is important to highlight that the choice of effective sample size $n$ entails a trade-off (assuming that the $\beta$-mixing coefficients are decaying). The first two terms that depend on Talagrand's functional are small when the effective sample size is large. On the contrary the third term that depends on the $\beta$-mixing coefficients is small when the effective sample size is also small.c
Third, the probability bound of the inequality is the classic exponential-type bound that is typically associated with analogous concentration results for i.i.d. data multiplied by the factor $T/n$. The factor $T/n$ may be interpreted as a correction factor capturing the error arising from the fact that the sequence of random vectors is dependent rather than independent.
Fourth, the dimensionality of the parameter space affects the inequality through Talagrand's functional. In general, the larger the dimensionality of the parameter space the larger is Talagrand's functional. The dimensionality of the data affects the inequality through the constant $C_Z$. In what follows, we shall see how these constants simplify in the context of specific applications of our result.
Fifth, it is important to highlight that the generic chaining proof requires the empirical process to be separable, in the sense of the definition of Boucheron. In line with many authors, we assume throughout that these requirements are satisfied.
Last, we conclude with a few minor remarks on a number of additional aspects of theorem. We note that the theorem holds for any $T$, unlike results stated in the literature, which are often stated to hold for an unspecified and sufficiently large $T$ Jiang:Tanner:2010,Brownlees:Gudmundsson:2021,Brownlees:LlorensTerrazas:2021. All the constants in the theorem can be recovered from the proofs in the appendix of the paper. We do not provide explicit expressions in the text to avoid burdening exposition. The theorem does not assume any specific rate of decay of the $\beta$-mixing coefficients. However, meaningful applications of the theorem require that the $\beta$-mixing coefficient decay at suitable rate. Finally, applications of the theorem also require to set appropriately some of the variables in the theorem. We shall illustrate these choices in the application to statistical learning problems in the next section.
Consider the stationary time series $\{ (Y_t,\bm X_t')' \}$ where $Y_t$ takes values in $\mathcal Y \subset \mathbb R$ and $\bm X_t$ takes values in $\mathcal X \subset \mathbb R^d$, with both $\mathcal Y$ and $\mathcal X$ assumed to be closed sets. We are interested in forecasting the prediction target $Y_t$ on the basis of the vector of predictors $\bm X_t$. The forecasts for the prediction target $Y_t$ are obtained from the class of prediction rules \( f_{\bm \theta} : \mathcal X \rightarrow \mathcal Y \) indexed by $\bm \theta \in \Theta$. The square loss is used to measure prediction accuracy \[ L( Y_t, f_{\bm \theta}(\bm X_t) ) := ( Y_t - f_{\bm \theta}(\bm X_t) )^2 ~. \] A standard problem in statistical learning consists is devising an algorithm to choose an accurate prediction rule $f_{\bm \theta}$ on the basis of a sample of observations $\mathcal D = \{ (Y_1,\bm X_1')', \ldots, (Y_T,\bm X_T')' \}$. One of the natural principles used to tackle this challenge is empirical risk minimization. This principle consists in choosing the $\bm \theta$ that minimizes the empirical risk, that is \[ \hat{\bm \theta} \in \arg \min_{\bm \theta \in \Theta} R_T(\bm \theta) \text{ where } R_T(\bm \theta) := {1\over T}\sum_{t=1}^T ( Y_t - f_{\bm \theta}(\bm X_t) )^2 ~. \] If more than one $\bm \theta$ achieves the minimum we may pick one arbitrarily. We call $\hat {\bm \theta}$ the empirical risk minimizer (ERM).
The accuracy of the ERM is measured by its conditional risk defined as
where $(Y,\bm X')'$ denotes a draw form the stationary distribution of the time series $\{ (Y_t,\bm X_t')' \}$, and is assumed to be independent of the sample $\mathcal D$. The performance measure in (ref) can be interpreted as the risk of the ERM obtained from the “training sample” $\mathcal D$ over the “validation observation” $(Y,\bm X')'$. This performance measure allows us to keep our analysis close to the bulk of contributions in the learning theory literature (which typically focus on the analysis of i.i.d. data) and facilitates comparisons. We remark that Brownlees:Gudmundsson:2021 and Brownlees:LlorensTerrazas:2021 consider alternative performance measures such as the conditional out-of-sample average risk of the ERM, which has a more attractive interpretation for time series applications. It turns out that these alternative measures lead to essentially the same theoretical analysis, at the expense of introducing additional notation. Therefore, we focus on the performance measure defined in (ref) for clarity.
A classic objective of statistical learning theory is to obtain a bound on the performance of the ERM relative to the optimal risk that can be achieved within the given class of prediction rules. Define \( R(\bm \theta) := \mathbb E\left( ( Y_t - f_{\bm \theta}(\bm X_t) )^2\right) \). Our aim is to find a pair $(B_T(\Theta),\delta_T)$ such that
holds at least with probability $1-\delta_T$ for all (sufficiently large) $T$. In general, inequalities such as (ref) provide non-asymptotic guarantees on the performance of the ERM. Additionally, when we have that $B_T(\Theta) \rightarrow 0$ and $\delta_T \rightarrow 0$ as $T\rightarrow \infty$ the inequality in (ref) is referred to as an oracle inequality, meaning that that the ERM asymptotically performs as well as the best prediction rule in the class (when it exists).
Theorem (ref) can be used to obtain performance bounds for empirical risk minimization. We begin by recalling the basic inequality Devroye:Gyorfi:Lugosi:1996 stating that \[ | R( \hat{\bm \theta} ) - \inf_{\bm \theta \in \theta} R(\bm \theta) | \leq 2 \sup_{\bm \theta \in \Theta} \left| R_T(\bm \theta) - R(\bm \theta ) \right| ~. \]
Let $\bm Z_t = (Y_t,\bm X_t')'$ that takes values in $\mathcal Z = \mathcal Y \times \mathcal X$ and define $g_{\bm \theta}(\bm Z_t) = ( Y_t - f(\bm X_t,\bm \theta) )^2$. Then, we have \[ \sup_{\bm \theta \in \Theta} \left| R_T(\bm \theta) - R(\bm \theta ) \right| = \sup_{\bm\theta\in\Theta}\left|{1 \over T} \sum_{t=1}^T g_{\bm \theta}(\bm Z_t) - \mathbb E(g_{\bm \theta}(\bm Z_t)) \right| ~. \] Thus an application of Theorem (ref) leads to the result of interest.
In order to apply Theorem (ref), we assume that a number of high-level conditions hold. These conditions play the same role as (ref) and (ref) in the previous section, but are reformulated to fit the present framework. In Section (ref) we verify that these conditions are satisfied, for example, by a single-layer neural network model.
Notice that in condition (ref) we have that the bound on the sub-Gaussian norms of $\sup_{\theta \in \Theta} f_{\bm \theta}(\bm X_t)$ and $f_{\bm \theta_1}(\bm X_t) - f_{\bm \theta_2}(\bm X_t)$ do not depend on dimension of $\bm X_t$.\footnote{This is satisfied, for example, when $f_{\bm \theta}(\bm X_t)=\bm X_t'\bm \theta$ and $\bm X_t$ is a sub-Gaussian vector. In this case for condition (ref).$(i)$ we have that \[ \| \bm X_t'(\bm \theta_1-\bm \theta_2) \|_{\psi_2} = \left\| \bm X_t'{(\bm \theta_1 - \bm \theta_2) \over \| \bm \theta_1 - \bm \theta_2 \|_2} \| \bm \theta_1 - \bm \theta_2 \|_2 \right\|_{\psi_2} \leq \| \bm X_t \|_{\psi_2} \| \bm \theta_1 - \bm \theta_2 \|_2 ~. \] }
A number of remarks on the proposition are in order. First, the proposition implies that in our framework the ERM is consistent for prediction in the sense that $| R( \hat{\bm \theta} ) - \inf_{\bm \theta \in \theta} R(\bm \theta) | \stackrel{p}{\rightarrow} 0$. Second, it is insightful to provide a simplified expression for the main claim of the proposition. When $T$ is sufficiently large and assuming that the dimensionality of the parameter space and of the data is fixed we have that there is a positive constant $C$ such that \[ R( \hat{\bm \theta} ) \leq \inf_{\bm \theta \in \theta} R(\bm \theta) + C \sqrt{ \log(n) \over n } \] holds at least with probability \( 1-13 n^{-1} \). We recall that the rate of convergence $\sqrt{\log(n)/n}$ is typically referred to as the classical rate of convergence of empirical risk minimization in the learning literature with i.i.d. data Devroye:Gyorfi:Lugosi:1996. Thus, our results recovers the classical rate of converge once we replace the sample size $T$ with the effective sample size $n$. We highlight that the proposition relies on fairly weak conditions on the sequence of mixing coefficients. In particular, it requires (a sufficiently fast rate of) polynomial decay as opposed to several contributions in the literature which typically assume geometric decay Jiang:Tanner:2010,Brownlees:Gudmundsson:2021,Brownlees:LlorensTerrazas:2021. It is worth noting that the faster the rate of decay of the mixing coefficients (as captured by a larger value of $\zeta$), the smaller the discrepancy between $n$ and $T$ (as reflected by a value of $\eta$ closer to unity).
It is instructive to apply Proposition (ref) to a specific class of regression models in order to illustrate more concretely the implications of our results. In this section, we derive learning rates for a class of neural network models, specifically the single-layer perceptron for regression Hastieetal:2009. We note that neural network models are typically trained using back-propagation algorithms rather than empirical risk minimization. Nevertheless, analyzing ERM remains valuable, as it offers theoretical benchmarks for understanding the predictive performance that can be expected to be achieved for this class of models.
The single-layer perceptron for regression may be defined as follows. We start by defining a set of $K$ derived predictors called hidden units $H_{k\,t}$ for $k=1,\ldots,K$, which are nonlinear transformations of the original set of predictors. These are given by
where $\bm w_k$, $k=1,\ldots,K$, is a set of weight vectors and $\sigma : \mathbb R \rightarrow \mathbb R$ is the so-called activation function. Classic choices for $\sigma$ include the rectified linear unit (ReLU) function $\sigma(x)=\max\{0,x\}$ or the sigmoid function $\sigma(x)=1/(1+e^{-x})$. We assume that $Y_t$ is subGaussian with subGaussian norm $\| \bm Y_t \|_{\psi_2} = \sigma_Y$, and that $\bm X_t$ is subGaussian with subGaussian norm $\| \bm X_t \|_{\psi_2} = \sigma_X $. Moreover, we assume that the activation function is sub-differentiable with a bounded first sub-derivative and that $\sigma(0)=0$. Forecasts for the target variable $Y_t$ are then obtained by combining the hidden units
where $\psi_1,\ldots,\psi_K$ are additional weights. Putting together (ref) and (ref), we get that the class of prediction rules in the single-layer perceptron for regression is given by
with $\bm \theta = (\bm w_1',\ldots,\bm w_K',\psi_1,\ldots,\psi_K)' \in \mathbb R^p$ with $p=Kd+K$. We further assume that $\bm \theta$ belongs to the set $\Theta$ that is compact.
The following corrollary specializes Proposition (ref) for the single-layer perceptron for regression.
In this section we detail the proof of Theorem (ref). To simplify exposition throughout this section we use $g_{\bm\theta}(\bm Z_t)$ to denote $g_{\bm\theta}(\bm Z_t) - \mathbb E(g_{\bm\theta}(\bm Z_t))$.
First, we introduce a coupling result MerlevedePeligrad2002 that is key to the proof.
Our proof strategy is built upon Proposition (ref). Let $M$ be a natural number such that $T/(n+1) < M \leq T/n$. Consider the extension of the sequence of vectors $\{\bm Z_1, \ldots, \bm Z_T \}$ given by $\{ \bm z, \bm Z_1, \ldots, \bm Z_T , \bm z, \bm z, \ldots \}$ where $\bm z$ denotes an arbitrary element in $\mathcal Z$ (which is deterministic). Define $\bm W_{i,j} = \bm Z_{i M +j}$ for $i\in \{0,\ldots,n\}$ and $j\in \{0,\ldots,M-1\}$. For each $j \in \{0,\ldots,M-1\}$ consider the sequence $\{ \bm W^*_{0,j} , \ldots , \bm W^*_{n,j}\}$ constructed from $\{ \bm W_{0,j} , \ldots , \bm W_{n,j}\}$ using Proposition (ref). Then we have
Note that the second equality follows from the fact that $g_{\bm\theta}(\bm W_{i,j},\bm\theta)=0$ when $\bm W_{i,j}=\bm z$. Furthermore, we have that
where $\bm \theta_0$ is defined (ref).$(ii)$. Then, for any $\varepsilon', \varepsilon'_1, \varepsilon'_2, \varepsilon'_3 \geq 0$ such that $\varepsilon' = \varepsilon'_1 + \varepsilon'_2 + \varepsilon_3'$ we have that
Our objective is to find appropriate bounds for the three terms in (ref).
We begin with the first term in (ref). We introduce a concentration result for sub-Weibull random variables that is based on KuchibhotlaChakrabortty2022 and results by Latala1997.
We remark that the explict expressions for the constants $C'_\alpha$ and $C''_\alpha$ can be deduced in the proof of the proposition.
We note that (ref).$(ii)$ and Proposition (ref) imply that for any $j \in \{ 0, \ldots, M-1 \}$ we have that
Notice that in this result we are using the fact that the random variable $g_{\bm\theta}(\bm W^*_{i,j})$ is degenerate at zero when $\bm W^*_{i,j} = \bm z$ and that in this case we have that $\| g_{\bm\theta}(\bm W^*_{i,j}) \|_{\psi_\alpha} < C_{\Theta}$.
We continue with the second term in (ref). (ref).$(i)$ and Proposition (ref) imply that for any $j \in \{ 0, \ldots, M-1 \}$, any $\bm \theta_1, \bm \theta_2 \in \Theta$ and any $\varepsilon\geq 0$ we have that
In other words, the empirical process satisfies a sub-Weibull increment-type condition. Such a property allows us to develop a generic chaining argument to control its supremum and, hence to control the second term in (ref).
We outline here the basic strategy of the generic chaining proof. We are interested in establishing a high-probability bound for \[ \sup_{\bm\theta\in\Theta}|X_{\bm\theta}-X_{\bm\theta_0}| ~. \] To simplify exposition, here we assume that $\Theta$ is finite Talagrand2005.\footnote{We remark that Proposition (ref) does not rely on this assumption and allows $\Theta$ to be uncountable.} We begin by constructing a sequence of subsets of $\Theta$ denoted by $\{ \Theta_k \}_{k\geq 0}^K$ such that $\bm \theta_0 \in \Theta_0$ and $\Theta = \Theta_K$. The sequence of subsets is carefully constructed and may be interpreted as a sequence of progressively finer approximations of $\Theta$, in the sense that any $\bm \theta$ can be more accurately approximated by an element in $\Theta_k$ as $k$ increases. Let $\pi_k(\bm \theta) = \arg \min_{ s \in \Theta_k} d_\Theta(s,\bm \theta) $ denote the closest element of the set $\Theta_k$ to $\bm \theta$. Then, by constructing a telescoping sum and applying the triangle inequality we get that \[ \sup_{\bm\theta\in\Theta}|X_{\bm\theta}-X_{\bm\theta_0}|\leq \sup_{\bm\theta\in\Theta}\sum_{k\geq 1}^K|X_{\pi_k(\bm\theta)}-X_{\pi_{k-1}(\bm\theta)}| ~. \] Next, for any \(\varepsilon \geq 0\), define the event \(\Omega(\varepsilon)\) as \[ \left\{ \text{ for all } k \in \{ 1 , \ldots , K \}, \text{ for any } \bm\theta_1,\bm\theta_2\in \Theta_k,~ |X_{\bm \theta_1}-X_{\bm\theta_2}| \leq c_k(\varepsilon) d_\Theta(\bm\theta_1,\bm\theta_2) ~\right\} ~, \] where $c_k = a2^{(k+1)/2} \sqrt\varepsilon + b2^{(k+1)/\alpha}\varepsilon^{1/\alpha}$. It can be shown that, under the sub-Weibull increment condition, the event $\Omega^c(\varepsilon)$ is realized with probability at most $2\exp(-\varepsilon)$ for any $\varepsilon\geq 2$. Then, assuming that the \(\Omega(\varepsilon)\) is realized we have that
The final upper bound follows from straightforward computations by studying the properties of the summation in the last display.
Condition (ref).$(i)$, Proposition (ref) and Proposition (ref) imply that for any $j \in \{ 0, \ldots, M-1 \}$ and any $\varepsilon'_2 \geq 2$ we have that
We conclude with the third term in (ref). (ref) and Proposition (ref) imply that for any $j \in \{ 0, \ldots, M-1 \}$, some ${\bm w} \in \mathcal Z$ and some $s>0$ we have that
The claim of the theorem then follows from (ref), (ref), (ref) and (ref) after setting $\varepsilon_1' = \varepsilon_2'$ and redefining $\varepsilon_1 = \varepsilon_1'$ and $\varepsilon_2 = C_{\mathcal Z} \varepsilon_3'$.
We conclude this section with an auxiliary proposition that provides an upper bound for Talagrand's functional in terms of a generalised version of Dudley's entropy integral. This result allows to simplify the bounds of the empirical process implied by our main theorem in the applications.
This paper establishes a concentration inequality for the suprema of the empirical processes with dependent data. The concentration inequality is established by developing an argument based on generic chaining combined with a coupling strategy. We apply our result to study the properties of statistical learning procedures. Specifically, we derive non-asymptotic predictive performance guarantees for empirical risk minimization for nonlinear regression. We show that empirical risk minimization achieves the classical convergence rate that can be obtained in i.i.d. setting after replacing the sample size with what we call in this work the effective sample size, a notion of sample size that reflects the loss of information due to the dependence with respect to the i.i.d. case. Our result encompasses a broad class of nonlinear regression models, including a single-layer neural network models, and offers theoretical guarantees for widely used statistical learning procedures in dependent data environments.