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.
79,585 characters · 11 sections · 55 citation commands
Maximal Inequalities for Empirical Processes under General Mixing Conditions
\thispagestyle{empty}
\setcounter{page}{1}
Maximal inequalities serve as a fundamental cornerstone in empirical processes theory, playing a pivotal role in deriving crucial results, including but not limited to the functional central limit theorem and strong approximations.
This paper provides a maximal inequality for $f \mapsto G_{n}[f] : = n^{-1/2} \sum_{i=1}^{n} f(X_{i}) - E_{P}[f(X_{i})]$ of the form
for some quantity $\Gamma$ to be specified below, and where the data $(X_{i})_{i=-\infty}^{\infty}$ is a stationary process drawn from a probability $P$ which satisfies some general mixing conditions to be described below.
There is a large body of work deriving maximal inequalities and their derivatives such as the functional CLT for dependent data under mixing conditions; cf. doukhan1987principes,arcones1994central,andrews1994introduction,yu1994rates,DMR1995,billingsley2013convergence, and dedecker2002maximal and rio2017asymptotic for reviews. Closest to this paper is the important work in DMR1995 wherein the authors establish a functional invariance principle in the sense of Donsker for absolutely regular empirical processes, where the constant $\Gamma$ is proportional to a measure of complexity of the class $\mathcal{F}$. To the best of our knowledge, this and all other existing results in this literature are derived under restrictions on the decay of mixing coefficients, e.g. $\sum_{k=1}^{\infty} \beta(k) < \infty$ (DMR1995), or $k^{\frac{p}{p-2}} (\log k )^{2 \frac{p-1}{p-2}} \beta(k) = o(1)$ for some $p >2$ (arcones1994central) where $\beta$ is the $\beta$-mixing coefficient used in DMR1995.
These results leave open the question of what type of maximal inequality one can obtain in contexts where the mixing coefficients do not satisfy these conditions. Many processes do not satisfy them, either because the data exhibits long-range dependency or long-memory and this feature is modeled using slowly decaying dependence structure, e.g. see asadi2014stationary in the context of Markov processes; or the data is described by a so-called infinite memory chain (see doukhan2008weakly); or simply because the $\beta$-mixing coefficients decay at a slow polynomial rate (see CCLJOE10), or not at all (see andrews1984non). More generally, there is the open question of how do the mixing properties affect the concentration rate and the constant $\Gamma$ of the maximal inequality (ref). This paper provides insights into these questions.
Unfortunately, the approach utilized in DMR1995 and related papers cannot be applied to establish maximal inequalities when the aforementioned restrictions on the mixing coefficients do not hold. One of the cornerstones of this approach relies on insights that can be traced back to Dudley in the 1960s (dudley_sizes_1967) for Gaussian processes. Dudley's work states that the “natural" topology to measure the complexity of the class of functions $\mathcal{F}$ is related to the variation of the stochastic process. In DMR1995, the authors use this insight to construct a “natural" norm, which turns out to depend on the $\beta$-mixing coefficients. Unfortunately, without restrictions on the mixing coefficients, this approach is not feasible because this norm may not even be well-defined.
In view of this, the current paper proposes a new proof technique which employs a family of norms, rather than just one, to measure the complexity of the class $\mathcal{F}$. To accommodate this new feature, we introduce a new measure of complexity inspired by Talagrand's measure (talagrand2005,talagrand2014) that allows for a family of norms.
The family of norms proposed in the proof is linked to the dependence structure, which is captured by suitably chosen mixing coefficients. Papers such as arcones1994central,DMR1995 use $\beta$-mixing while some other papers use stronger concepts such as $\phi$-mixing (see ibragimov2012gaussian). In this paper, however, we use the weaker notions of $\tau$-mixing introduced by dedecker2004coupling,dedecker2005new and $\alpha$-mixing (cf. rio2017asymptotic). The $\tau$-mixing coefficients not only are typically weaker than the $\beta$-mixing ones, thereby encompassing a wider class of stochastic processes (see dedecker2004coupling,dedecker2005new and examples below), but they are also adaptive to the size of the class of functions $\mathcal{F}$ --- a property not enjoyed by standard mixing coefficients.
The main result in the paper shows that the $L^{1}$ norm of $\sup_{f, f_{0} \in \mathcal{F}} |G_{n}[f-f_{0}]|$ is bounded (up to constants) by the aforementioned complexity measure. Under IID (or $m$-dependent data), the bound corresponds, up to constants, to that in Talagrand's Generic Chaining approach (talagrand2014 e.g. Theorem 4.5.16). For general mixing data, when a summability condition, similar to the one in DMR1995 holds, our bound replicates (up to constants), and in some cases improves upon, the results in the literature. When the summability restriction does not hold --- i.e., the mixing coefficients do not decay quickly to zero --- a bound of the form (ref) remains valid. However, in this case, the quantity $\Gamma$ is comprised not only of the complexity measure, as in the standard case, but also of a scaling factor that depends on the mixing properties and the sample size. This last novel result implies that the concentration rate is not root-n, as in the standard case, but slower and is a function of the mixing rate.
The remainder of the paper is organized as follows. Section (ref) presents the maximal $L^{1}$-inequality results and Section (ref) presents the proofs. Some technical lemmas and proofs are relegated to the Appendix.
This section aims to establish an upper bound for $\left \Vert \sup_{f , f_{0} \in \mathcal{F}} | G_{n}[f-f_{0}] | \right \Vert_{L^{1}(P)}$, where $\mathcal{F}$ is a class of functions bounded in $L^{2}(P) \cap L^{\infty}$.\footnote{As per talagrand2014, the quantity $\left \Vert \sup_{f , f_{0} \in \mathcal{F}} | G_{n}[f-f_{0}] | \right \Vert_{L^{1}(P)}$ is defined as $\sup \{ \left \Vert \sup_{f , f_{0} \in \mathcal{M}} | G_{n}[f-f_{0}] | \right \Vert_{L^{1}(P)} \colon \mathcal{M} \subseteq \mathcal{F}~\text{finite} \}$ to sidestep measurability issues.} We now outline an informal roadmap for the proof to identify key components and motivate subsequent formal definitions.
The first step of the proof involves constructing a “chain" between $f$ and $f_{0}$ denoted as $f - f_{0} = \sum_{k=1}^{\infty} \Delta_{k} f$, where each link, $\Delta_{k}f$, belongs to a class with finite cardinality. As a consequence of this chain, the empirical process is decomposed as $G_{n}[f] = \sum_{k=1}^{\infty} G_{n}[\Delta_{k} f ]$.
For each link of the chain (indexed by $k \in \mathbb{N}$), the second step of the proof couples the empirical process $f \mapsto G_{n}[\Delta_{k} f ]$ with $f \mapsto G^{\ast}_{n}[\Delta_{k} f] : = n^{-1/2} \sum_{i=1}^{n}{ \Delta_{k} f(X^{\ast}_{i}) - E_{P}[ \Delta_{k} f(X^{\ast}) ]}$, where $(X_{i})_{i=-\infty}^{\infty}$ and $(X^{\ast}_{i})_{i=-\infty}^{\infty}$ have joint probability denoted by $\mathbb{P}$; and the latter process is such that $(U^{\ast}_{2j}(q_{k}))_{j=0}^{\infty}$ form an independent sequence and $(U^{\ast}_{2j+1}(q_{k}))_{j=0}^{\infty}$ form another independent sequence, where each block is given by $U^{\ast}_{i}(q_{k}) : =(X^{\ast}_{q_{k}i+1},...,X^{\ast}_{q_{k}i+q_{k}})$ and has the same distribution as its counterpart in the $(X_{i})_{i=-\infty}^{\infty}$ process --- $q_{k} \in \mathbb{N}$ will be chosen below.\footnote{In this informal presentation it is implicitly assumed that $n/q_{k}$ is an integer; we relax this assumption in the general theory.} Existence of such process is established by the results in dedecker2006inequalities which are presented in Appendix (ref) for completeness. Henceforth, we refer to $f \mapsto G^{\ast}_{n}[f]$ as a block-independent empirical process. This coupling yields
where the $L^{1}$-norm of the second term on the right-hand side is controlled by our measure of dependence defined below.
The final step of the proof involves bounding the term $\left \Vert \sup_{f \in \mathcal{F}} | \sum_{k=1}^{\infty} G^{\ast}_{n}[ \Delta_{k} f ] | \right \Vert_{L^{1}(P)}$. To achieve this, we employ Talagrand's generic chaining insights (cf. talagrand2014). However, it is crucial to adjust the measure of complexity to accommodate the link-specific length of the block, given by $q_{k}$. As mentioned in the introduction, the reason why the block length influences the topology employed to gauge complexity comes from the realization that the “natural" distance used in complexity computations stems from the stochastic process's variability. Due to the dependence structure of $f \mapsto G^{\ast}_{n}[f]$, the variability is measured by $\sigma_{2}(f,q_{k}) : = \sqrt{E_{P} \left[ \left( q^{-1/2}_{k} \sum_{i=1}^{q_{k}} f(X_{i}) - E_{P} [ f(X) ] \right)^{2} \right] }$, where $q_{k}$ is the parameter regulating the length of the blocks. Therefore, the “natural" notion of distance may differ for each link in the chain. To accommodate for this feature we introduce a novel measure of complexity.
From this brief description of the proof one can see the two key ingredients: First, a measure of dependence, which quantifies the error of approximating the original process with a block-independent one. Second, a measure of complexity that can accommodate a family of norms. Below we formally define these two quantities, we explain the need to work with a family of norms as opposed to just one as in the rest of the literature, and we then present the main result.
\paragraph{Measure of Dependence.} Let $P$ be the probability distribution of the stationary process $(X_{i})_{i=-\infty}^{\infty}$, $P_{X}$ denotes the marginal distribution of $X_{i}$ where $X_{i} \in \mathbb{X}$ for some Polish space $\mathbb{X}$, and $P(.\mid \mathcal{M}_{j}^{l})$ denotes the conditional probability distribution given $\mathcal{M}_{j}^{l}$ for any $-\infty \leq j \leq l \leq \infty$, where $\mathcal{M}_{j}^{l}$ is the $\sigma$-algebra generated by $(X_{j},\ldots,X_{l})$.
The measure that quantifies the dependence structure of the data for any $\mathcal{B} \subseteq cone \mathcal{F}$ is given by\footnote{For any set $A \subseteq L^{2}(P)$, $cone A : = \{ \lambda a \colon a \in A~and~\lambda \geq 0 \}$.} (cf. dedecker2006inequalities,dedecker2004coupling,dedecker2005new)
where the supremum is taken over all future blocks of at most $q$ elements with starting time $t_1 \ge 1$, and
with $\Lambda( \mathbb{X}^{l} , d_{l,\mathcal B} )$ is the class of Lipschitz (with constant 1) functions over $\mathbb{X}^{l}$ with respect to $(x_{1:l},y_{1:l}) \mapsto d_{l,\mathcal B}(x_{1:l},y_{1:l}) : = \sum_{m=1}^{l} \sup_{f \in \mathcal{B}} |f(x_{m}) - f(y_{m})|$.\footnote{The element $x_{1:l}$ denotes the vector $(x_{1},...,x_{l})$ for any $l \in \mathbb{N}$.}
The quantity $\tau_{\mathcal B}(q)$, introduced in dedecker2006inequalities,dedecker2004coupling,dedecker2005new, measures the largest average per-coordinate dependence between the distant past (up to time $-q$) and the future --- measured by any future block of length at most $q$. The dependence is quantified in a Kantorovich--Wasserstein sense using the class of $1$-Lipschitz functions on $\mathbb X^{l}$ with respect to the block metric generated by $\mathcal B$. We defer a more detailed discussion of its properties and its relation to other mixing coefficients, such as $\beta$-mixing, to below. For present purposes, we simply note that this notion of dependence --- unlike $\beta$-mixing --- can be tailored to the function class under consideration, as we do next.
Let
where $B \mathcal{B} : = \{ f \in cone \mathcal{B} \colon ||f||_{L^{\infty}} \leq 1 \}$ for any set $\mathcal{B} \subseteq \mathcal{F}$, and $\alpha$ is the strong mixing coefficient (e.g. see rio2017asymptotic)
where $BL$ is the class of bounded (by 1) measurable functions. Henceforth, we extend $\theta(.)$ to the positive reals as a cadlag function --- to ease the notational burden we still use $\theta$ to denote this extension.
We say the process is $z$-mixing if $\lim_{q \rightarrow \infty} z(q) = 0$ with $z \in \{\theta,\tau,\alpha\}$. The quantity $\theta $ is the relevant quantity for measuring dependence as both $\tau(q)$ and $\alpha(q)$ are used in the proof. The first one controls the error of coupling the original empirical process with a block-independent one; see Lemma (ref) in Appendix (ref). On the other hand, as shown in the proof of Lemma (ref) in Appendix (ref), the second mixing coefficient, $\alpha$, is used to control the variance of the block-independent empirical process given by $\sigma^{2}_{2}(f,q) = E_{P} \left[ \left( q^{-1/2} \sum_{i=1}^{q} f(X_{i}) - E_{P} [ f(X) ] \right)^{2} \right] $.
In previous work (cf. DMR1995,yu1994rates) the two dependence measures, $\tau$ and $\alpha$, were subsumed by the $\beta$-mixing coefficient, $\beta(q) : = \beta(\mathcal{M}_{-\infty}^{-q}, \mathcal{M}_{0}^{+\infty}) $, where $\mathcal{M}_{0}^{\infty}$ is the $\sigma$-algebra generated by the “future" $(X_{0},X_{1},...)$ and $\beta$ is the defined as in VolRoz1959. The distinction between this $\beta$-mixing coefficient and $\tau$ is twofold. First, $\beta$-mixing compares the distance past $\sigma$-algebra and entire future $\sigma$-algebra, whereas $\tau(q)$ only measures dependence between the distant past $\sigma$-algebra and finite future blocks. Second, and more importantly, $\beta$-mixing is defined through total variation (i.e., supremum over the class $BL$), while $\tau$ relies on a weaker Kantorovich-type metric restricting attention to the class of $1$-Lipschitz functions generated by $B\mathcal F$. So, for any $q \in \mathbb{N}$, $\tau(q)$ is smaller (up to a constant) than $\beta(q)$ --- Lemma (ref) in the Appendix (ref) formally shows this.
This class of 1-Lipschitz functions generated by $B\mathcal F$ will be equal to $BL$ when $\mathcal{F}$ is sufficiently rich so that $d_{\mathcal{F}}(x,y)= 1 \{x \ne y \}$; for instance, if $\mathcal{F}$ is the class of indicators over the half-line. In many applications, however, it is common for $\mathcal{F}$ to have smoothness restrictions of some sort. These restrictions imply that the class of $1$-Lipschitz functions generated by $B\mathcal F$ will be much smaller than $BL$, so that dependence conditions based on $\beta$-mixing may be unnecessarily restrictive. For instance, if functions in $\mathcal{F}$ are Lipschitz with respect to some distance $\rho$, our $\tau$-coefficient is bounded by that in dedecker2006inequalities,dedecker2004coupling as the next lemma shows.
This connection is useful because the literature on $\tau$-dependence (cf dedecker2004coupling,dedecker2005new) provides many examples of processes that are $\tau$-mixing even though they fail to be $\beta$-mixing --- even cases where the $\tau$-mixing coefficients vanish at exponential rate; one such case is discussed in Example (ref) below.
\paragraph{Measure of Complexity. } We present a new measure of complexity which we dub Talagrand's complexity measure as it is inspired by Talagrand's Generic Chaining theory (see talagrand1996, talagrand2005, talagrand2014).
For any $r > 0$ and $\mathcal{B} \subseteq \mathcal{F}$, we say $\mathcal{T}^{\infty} : = (\mathcal{T}_{l})_{l \in \mathbb{N}_{0}}$ is an admissible partition sequence of order $r$ for $\mathcal{B}$, if $\mathcal{T}^{\infty}$ is an increasing sequence of partitions of $\mathcal{B}$ with $card \mathcal{T}_{l} \leq 2^{2^{l/r}}$ and $card \mathcal{T}_{0} = 1$.\footnote{By increasing we mean that any set in $\mathcal{T}_{l+1}$ is included in a set in $\mathcal{T}_{l}$.} Let $\mathbf{T}_{r}(\mathcal{B})$ denote the set of all admissible partition sequences of order $r$ for $\mathcal{B}$. For any $f \in \mathcal{B}$ and $l \in \mathbb{N}_{0}$, let $T(f,\mathcal{T}_{l})$ be the (only) set in $\mathcal{T}_{l}$ containing $f$ and let $x \mapsto D(f,\mathcal{T}_{l})(x) : = \sup_{f_{1},f_{2} \in T(f,\mathcal{T}_{l})} |f_{1}(x) - f_{2}(x)|$ be the “diameter" of such set.
Talagrand's complexity measure is defined by
The main difference with the expression in definition 2.2.19 and the expression in p. 32 in talagrand2014 is the usage of a different (quasi)-norm, $d_{l}$, for each different partition $\mathcal{T}_{l}$. For reference, when specializing to one norm (as opposed to a family), this definition with $r=1$ is analogous to that in talagrand2014. The order $r$ (and the index $p$) provide flexibility and allow us to majorize the measure of complexity by the standard Dudley's metric entropy --- see Lemma (ref) in Appendix (ref).
\paragraph{Notion of distance.} We now introduce the notion of distance, captured by a family of norms. The “natural" notion of distance to compute the complexity arises from the Berenstein inequality (see Lemma (ref) below), which works with the boundedness and the variability of the stochastic process. As argued above the relevant process is the block empirical process $f \mapsto G^{\ast}_{n}[f]$, and due to its dependence structure the variability is given by $\sigma_{2}(f,q)$, where $q$ is the parameter regulating the length of the blocks. Motivated by this observation and Theorem 1.1 in rio2017asymptotic, we introduce the following norms
where
with $u \mapsto Q_{f}(u) : = \inf \{ s \mid H_{f}(s) \leq u \}$ being the quantile function of $|f|$ with $s \mapsto H_{f}(s) : = P(|f(X)| > s)$.
\paragraph{Choice of block length.} Most of the literature derives maximal inequalities of the type studied here under the assumption that $\beta$ mixing coefficients decay “fast enough" to zero --- $\sum_{i=1}^{\infty} \beta(i) < \infty$ or stronger. Under this assumption, for any $q$, $||f||_{2,q}$ is majorized (up to constants) by $ \sqrt{\int_{0}^{1} \beta^{-1}(u) Q^{2}_{f}(u) du}$, which is a well-defined norm and can be combined with known metric entropies --- to our knowledge, such approach was first proposed in DMR1995 for constructing bracketing entropies using $\beta$-mixing coefficient. If $\sum_{i=1}^{\infty} \beta(i)$ is not finite, however, the above proposal becomes infeasible since $\beta^{-1}$ is not integrable and thus the previous norm is not even be well-defined. Consequently, the strategy of proof proposed by DMR1995 and related papers cannot be followed.
In order to sidestep this issue, we use a different strategy of proof which relies on directly using $||.||_{2,q}$, as it is always well-defined for any finite $q$, and working with a sequence of block lengths, $(\mathbf{q}_{n}(k))_{k=0}^{\infty}$, given by
where $\mathcal{Q}_{n} : = \{ m \in \mathbb{N} \colon m \leq n \}$.
\paragraph{Main Result.} We are now in position to state the maximal inequality result.
Unlike classical maximal inequalities, which typically assume independence or fast-mixing dependence (e.g., summable $\beta$-mixing coefficients), this result is valid for arbitrarily slow mixing rates. The bound consists of two complexity measures $\gamma_{1,b}$ and $\gamma_{2,a}$, the first one involving the sup norm and the second one involving an $L^{2}$-norm. This feature is analogous to the results in Theorem 4.5.16 in talagrand2014 for IID data. The key difference lies on the norms being defined relative to a “mixing-adjusted" family of norms, making the bound adaptive to different dependence structures.\footnote{If the quantities in the RHS are infinite the inequality is trivially true, so, henceforth we assume that are finite. We provide examples wherein this holds below and in Remark (ref) in Appendix (ref).}
In what follows, we present a few remarks and corollaries designed to shed light on the scope of the theorem, how to use it, its relationship with existing literature, and the role of the dependence structure.
Henceforth, let $x \mapsto \bar{\tau}(x) : = \tau(x)/x$, and $\bar{\tau}^{-1}$ its generalized inverse. We adopt the following convention: $\mathbb{L}$ represents an universal constant and $\mathbb{L}_{x}$ represents an universal constant with the exception that can depend on a parameter “x" --- e.g., in Theorem (ref), $\mathbb{L}_{a,b}$ is an universal constant that only depends on $(a,b)$. The constants $\mathbb{L}_{x}$ can take different values at different instances, and are used to simplify the exposition. The derivations in the proofs contain the exact values behind these constants.
We begin with a refinement of the previous theorem that provides an upper bound that separates the dependence structure from the geometric one. Although this bound is looser than the one in the theorem, it is perhaps more practical and easier to compute in applications. Henceforth, for any $q \in \mathbb{N}$ and any $r \in [1,+\infty]$, let $ \Theta_{r}(q) : = \sqrt{ 1 + ( \int_{0}^{1} | \min\{ \alpha^{-1}(u), q \} |^{\frac{r}{r-1}} du )^{\frac{r-1}{r}} } $ for $r \in (1,+\infty)$, $\Theta_{1}(q) : = \sqrt{1+q} $ for $r=1$, and $\Theta_{\infty}(q) : = \sqrt{1 + \int_{0}^{1} | \min\{ \alpha^{-1}(u), q \} | du } $ for $r=+\infty$.
This result is obtained by showing that, for any $q \in \mathbb{N}$,
and it provides insight into the role of the mixing structure and the complexity of $\mathcal{F}$. The influence of the mixing structure is reflected in the scaling factors $\frac{\bar{\tau}^{-1}(1/n)}{\sqrt{n}}$ and $\Theta_{r}(\bar{\tau}^{-1}(1/n))$, which depend on the behavior of $\tau$ through $\bar{\tau}^{-1}$ and on $\alpha$ through $\Theta_{r}$. The complexity of $\mathcal{F}$ is captured by $\gamma_{1,b}$ and $\gamma_{2,a}$. These quantities, introduced in Talagrand's work, are independent of the dependence structure and benefit from numerous established upper bounds that we can leverage.
For instance, by Lemma (ref) in Appendix (ref),
for any $r \in [1,\infty]$, where $e_{l,b}(\mathcal{F},||\cdot||_{L^{r}(P)}) := \inf_{S \subseteq \mathcal{F}, card S \leq 2^{2^{l/b}}} \sup_{t \in \mathcal{F}} \min_{s \in S} ||t - s||_{L^{r}(P)}$ denotes the entropy number, and $N(u,\mathcal{F},||\cdot||_{L^{r}(P)})$ is the covering number for radius $u$.\footnote{For convenience, the entropy number is defined using a cardinality of $2^{2^{l/b}}$ instead of the conventional $2^{l/b}$.} Expression (ref) is particularly useful as it relies on a well-known and extensively studied quantity: the entropy numbers. It can also be improved; for instance, when $\mathcal{F}$ exhibits certain convexity properties, this bound can be further improved by utilizing the results from VanHandel2018,VanHandel2018b.
This case is presented just to illustrate our bound relative to the literature and the effect of dependence in maximal inequalities. Suppose $(X_{i})_{i}$ is such that, for any $i \in \mathbb{N}$, $X_{i} = \Phi(Z_{i+1},...,Z_{i+m})$ where $(Z_{i})_{i}$ is an IID process. This process is $m$-dependent and so $\theta(q) = 0$ for any $q \geq m$. Therefore, by choosing $\mathbf{q}=m$, it follows that $f \mapsto ||f||^{2}_{2,m} = \sum_{i=0}^{m} \int_{0}^{0.5\theta(i)} Q^{2}_{f}(u) du \leq m \int_{0}^{1} Q^{2}_{f}(u) du = m ||f||^{2}_{L^{2}(P)}$. Hence, by Theorem (ref)
For the IID case of $m=1$, this bound coincides (up to constants) with known bounds in the literature; cf. Proposition 9.2 in talagrand2014.
For a general $m>1$, however, the IID bound is scaled up by a factor of $m$ thereby reflecting the fact that in this type of processes, without additional knowledge on the function $\Phi$, is as if the sample size is $n/m$ as opposed to $n$. This matters for applications as it is common practice in statistics to employ an asymptotic approach, wherein $n$ divergences and constants are ignored. This practice will lead to the conclusion that the bound coincides with the IID one, as $m$ is merely constant, but the theorem illustrates that, even with this simple dependence structure, such a conclusion can be misleading. For instance, even for moderate dependence --- e.g., $m$ equal 4 or 5 --- the actual bound corresponds to more than twice the IID bound, or alternatively, corresponds to an IID bound but with less than 25 percent of the sample size.
This feature, whereby the dependence structure results in a scaling of the IID bound, is canonical, appearing in more general processes as shown below. Moreover, the nature of the scaling --- whether is constant or diverging with the sample size --- depends on how fast mixing occurs.
In this case, the norm $f \mapsto |||f|||_{2,\theta } : = \sqrt{\int_{0}^{1} (1 + \theta^{-1}(u) ) Q^{2}_{f}(u) du }$ is well-defined as $\theta$ is integrable (cf. DMR1995). Moreover, it turns out that $||f||_{2,q} \leq |||f|||_{2,\theta } $ (this is formally shown in the proof of the proposition below). Hence, Theorem (ref) implies the following result.
This case of “fast mixing" has been studied in the literature (cf. DMR1995 Theorem 1), but Proposition (ref) offer extensions in two directions. First, by virtue of the generic chaining theory, it provides a tighter bound than existing results which use Dudley's metric entropy or Ossiander's bracketing entropy. Second, and perhaps more importantly, it imposes weaker restrictions on the mixing structure of the data because it relies on the $\theta$-mixing coefficients as oppose to the $\beta$-mixing ones, thus extending maximal inequalities to a wider class of stochastic processes --- Example (ref) illustrates this point.
In this section we discuss the case of “slow mixing" --- defined by $\min\{ \sum_{q} \alpha(q) , \sum_{q} \tau(q)\} = \infty$ ---, which, to our knowledge, has not been studied before in the literature. Intuitively, in this case there is a “phase-transition" because the scaling parameter due to the mixing structure is no longer constant, rather, it diverges with the sample size due to the slow mixing. That is, while the bound preserves the standard structure of a scaling factor and a measure of complexity, now the scaling factor is divergent with the sample size.
To formalize this intuition, one can use Corollary (ref), but a more succinct refinement can be obtained for $r=1$ if $\mathcal{F}$ is separable under $L^{2}(P)$ norm (a rather mild condition for many applications). Henceforth, let $\varphi : = (\varphi_{l})_{l}$ be the orthonormal basis, so that any $f$ in $\mathcal{F}$ can be cast as $\langle \pi(f) , \varphi \rangle_{\ell^{2}}$ for some $\pi(f) \in \Pi(\mathcal{F}) \subseteq \ell^{2}$ where $\Pi(\mathcal{F})$ summarizes additional summability restrictions on the coefficients that $\mathcal{F}$ may induce through its smoothness properties.
At first glance, Proposition (ref) might seem a surprising result as it majorizes the expectation of the supremum of an slowly $\theta$-mixing empirical process with a seemingly unrelated quantity: the expectation of the supremum of a Gaussian process, scaled by $\bar{\tau}^{-1}(1/n)$. However, the result stems from (a) a careful control of the mixing structure and geometry of $\mathcal{F}$, presented in Corollary (ref), and (b) the celebrated majorizing measure theorem (e.g. talagrand2014 Theorem 2.4.1).\footnote{The results and technique in Proposition (ref) is not confined to slow $\theta$-mixing processes, it can also be obtained for the fast $\theta$-mixing case.}
This result presents a relatively easy to use tool to bound $ \left \Vert \sup_{f,f_{0} \in \mathcal{F}} | G_{n}[f - f_{0}] | \right \Vert_{L^{1}(P)} $: Computing $\bar{\tau}^{-1}(1/n)$ for a given $\tau$ is trivial, and bounds for the supremum of the Gaussian process has been extensively studied in the literature; e.g. One can use Dudley's metric entropy, or the results in talagrand2014 or VanHandel2018, or simply bounded using H\"{o}lder inequality. In addition, it has the interesting property that it does not depend on the $\alpha$-mixing coefficients, only on the $\tau$-mixing ones, thus, presenting itself as a useful bound even if the process is not $\alpha$-mixing. This simplicity, however, may come at the cost of yielding slower rates of convergence than those implied by Corollary (ref).
The next example illustrates these points and also establish new Glivenko-Cantelli type results over Sobolev classes under slow mixing processes. The key takeaway is that, in this case, the concentration rate is slower than $\sqrt{n}$, revealing a fundamental limitation of classical methods in this setting.
For the proof of this theorem it is useful to expand the notion of admissible partition sequence for $\mathcal{F}$ to a sequence of partitions $\mathcal{T}^{\infty}(c,d) : = (\mathcal{T}_{l}(c,d))_{l \in \mathbb{N}_{0}}$ which is increasing and $card \mathcal{T}_{0}(c,d) =1$ and $card \mathcal{T}_{l}(c,d) \leq 2^{d 2^{l/c}}$ where $c > 0$ and $d >0$. The parameter $c$ is the order --- indeed when $d=1$, $\mathcal{T}_{l}(c) : = \mathcal{T}_{l}(c,1)$ coincides with the one in the definition (ref) ---, $d$ is an extra parameter that is convenient for establishing this proof. We call $(c,d)$ the order tuple of partition $\mathcal{T}^{\infty}(c,d)$.
For any order tuple $c,d>0$ and any admissible partition sequence for $\mathcal{F}$ given by $\mathcal{T}^{\infty}(c,d): = (\mathcal{T}_{k}(c,d))_{k \in \mathbb{N}_{0}}$, we construct a “chain" from any $f$ to $f_{0}$ as follows. For any $k \in \mathbb{N}_{0}$, let $\pi_{k}f$ be an element of $T(f,\mathcal{T}_{k}(c,d))$, where $T(f,\mathcal{T}_{k}(c,d))$ is the (unique) set in $\mathcal{T}_{k}(c,d)$ containing $f$. Setting $\pi_{0}f = f_{0}$, it follows that
The following Lemma is the basis of the proof of Theorem (ref) and could be of independent interest as it gives a more primitive (albeit more cumbersome) bound than of the theorem; its proof is relegated to section (ref).
For any $f \in \mathcal{F}$ and any $k \in \mathbb{N}_{0}$, let $\pi_{k}f$ be an element of $T(f,\mathcal{T}_{k})$, where $T(f,\mathcal{T}_{k})$ is the (unique) set in $\mathcal{T}_{k}$ containing $f$.\footnote{To ease the notational burden, we leave the dependence of the partition on the order tuple $c,d$ implicit.} Let $\Pi_{k} \mathcal{F}$ be the subset of $\mathcal{F}$ of all such elements --- $\pi_{k}$ has the property that $\pi_{k}f = \pi_{k}f'$ for all $f' \in T(f,\mathcal{T}_{k})$, thus $card \Pi_{k} \mathcal{F} \leq 2^{d 2^{k/c}}$. Henceforth, for any $l \in \mathbb{N}$, let $\Delta_{l} \mathcal{F} : = \{ g - g_{-1} \colon g \in \Pi_{l} \mathcal{F}~and~g_{-1} \in \Pi_{l-1} \mathcal{F} \}$, and $B \Delta_{l} \mathcal{F} : = \{ g \in cone \Delta_{l} \mathcal{F} \colon ||g||_{L^{\infty}} \leq 1 \}$.
By setting $\pi_{0}f = f_{0}$, the following chain is constructed
and so
The goal is to couple the process $f \mapsto G_{n}[\Delta_{l}f]$ with a block-independent one. However, since $n/q$ may not be an integer, we need to decompose the process as follows
where $J(n,q)$ is the floor of $n/q$, i.e., $J(n,q) : = \max\{ x \in \mathbb{N} \colon x \leq n/q \}$. This expression decomposes $G_{n}[f]$ into a “reminder" part and a first part that can be “coupled" with the block-independent process. The reminder term satisfies
because $0 \leq n-J(n,q)q \leq q$.
For any $n,q,l \in \mathbb{N}$, the process $f \mapsto G_{J(n,q)q}[\Delta_{l}f] $ will be coupled with a block-independent process constructed using $(X^{\ast}_{i})_{i \in \mathbb{N}}$ given by\footnote{Throughout this section we use a double sub-index to denote the block-independent process --- $f \mapsto G^{\ast}_{n,q}[f]$ as opposed to just $f \mapsto G^{\ast}_{n}[f]$. This is to stress the dependence of the process on the length of the block $q$.}
The existence and construction of process $(X^{\ast}_{i})_{i=-\infty}^{\infty}$ follow from known results and are relegated to Appendix (ref). The process is such that the blocks $U^{\ast}_{j}(q) : =(X^{\ast}_{qj+1},...,X^{\ast}_{qj+q})$ have the same distribution as $U_{j}(q) : = (X_{qj+1},...,X_{qj+q})$ for each $j$, and $(U^{\ast}_{2j}(q))_{j=0}^{\infty}$ form an independent sequence and $(U^{\ast}_{2j+1}(q))_{j=0}^{\infty}$ form another independent sequence.
Henceforth, let $\underline{n}(l) : = J(n,\mathbf{q}(l)) \mathbf{q}(l)$ for any $l \in \mathbb{N}_{0}$. Then, by equations (ref) - (ref), and the triangle inequality, it follows that
($\mathbb{P}$ denotes the joint probability measure over the original process and the block-independent one.)
We now bound the first term in the RHS in expression (ref), $ \sup_{f \in \mathcal{F}} | \sum_{l=1}^{\infty} \sqrt{\frac{ \underline{n}(l) }{n}} G^{\ast}_{\underline{n}(l),\mathbf{q}(l)}[\Delta_{l} f] | $. To do this, we employ an extension of the generic chaining approach proposed by Talagrand (cf. see talagrand2014). One condition needed for this approach (cf. talagrand2014 expression 1.4) is a Bernstein-type inequality for $ G^{\ast}_{\underline{n}(l),\mathbf{q}(l)}[\Delta_{l} f]$ which is verified in the following lemma
We are now in a position to establish an exponential tail inequality for $\sup_{f \in \mathcal{F}} \left| \sum_{l=1}^{\infty} \sqrt{\frac{ \underline{n}(l) }{n}} G^{\ast}_{\underline{n}(l),\mathbf{q}(l)}[\Delta_{l} f] \right|$.
From this previous lemma we can derive an expectation bound:
By plugging in the bound in Lemma (ref) in expression (ref) one obtains
Since $(\ell(l))^{2} \geq 1$, the last term in the RHS --- the “reminder" term of the coupling --- is bounded by $ \sup_{f \in \mathcal{F} } \sum_{l=1}^{\infty} \frac{\mathbf{q}(l)}{\sqrt{n}} ||\Delta_{l}f||_{L^{\infty}} \leq \sup_{f \in \mathcal{F} } \sum_{l=1}^{\infty} ||\Delta_{l}f||_{L^{\infty}} \frac{\mathbf{q}(l)}{\sqrt{n}} (\ell(l))^{2} $, which is dominated by the first term in the RHS. Thus,
We now bound the second term in the RHS. By the condition in the lemma, $||\Delta_{l}f||_{L^{\infty}} \leq e(l)$ for any $f \in \mathcal{F}$ and any $l \in \mathbb{N}$. So,
By Lemma (ref) --- in which $\underline{n}(l)$ plays the role of $n$, $\mathcal{B} = B \Delta_{l} \mathcal{F}$, and $q = \mathbf{q}(l)$ --- the norm in the last term can be bounded by $\sqrt{\underline{n}(l) } \tau_{B \Delta _{l} \mathcal{F}} (\mathbf{q}(l))$, thereby obtaining
This result and expression (ref) imply that, for any $n \in \mathbb{N}$, any order tuple $c,d \geq 1$, any admissible partition sequence for $\mathcal{F}$, $\mathcal{T}^{\infty}(c,d)$, any real-valued sequence $(e(l))_{l \in \mathbb{N}_{0}}$, any $\mathbf{q} : \mathbb{N}_{0} \rightarrow \mathcal{Q}_{n}$, and any $\ell : \mathbb{N}_{0} \rightarrow \mathbb{R}_{+}$ such that $\sup_{f \in \mathcal{F}} ||\Delta_{l} f ||_{L^{\infty}} \leq e(l)$ and $d 2^{l/c} \leq \ell(l)^{2} $ for all $l \in \mathbb{N}$, it follows that
with $\mathbb{M}_{2} : = 1 + 12 \left( 2 \sum_{l=0}^{\infty} 2^{ 2d 2^{l/c} } e^{- 2\ell(l)^{2} } \right) \geq 1 + \mathbb{M}$.
We now establish that $ \tau_{B \Delta_{l} \mathcal{F}}(.) \leq 2 \tau_{B \mathcal{F}}(.) = 2 \tau(.)$ for any $l \in \mathbb{N}$. The last equality follows from the definition of $\tau$ in expression (ref) --- recall that for any set $S$, $BS : = \{ f \in cone S \colon ||f||_{L^{\infty}} \leq 1 \}$. Hence, we only need to show the inequality. To do this, we show that $ \tau_{B \Delta_{l} \mathcal{F}}(.) \leq 2 \tau_{B \Pi_{l} \mathcal{F} }(.) \leq 2\tau_{B \mathcal{F}}(.) $ where, recall, $\Pi_{l} \mathcal{F} : = \{ \pi_{l}f \colon f \in \mathcal{F} \}$. Since $B \mapsto \tau_{B}$ is non-decreasing (with respect to the set inclusion partial ordering; see Lemma (ref)) and $\Pi_{l} \mathcal{F} \subseteq \mathcal{F}$, the last inequality follows. To show the first one, suppose, $\Lambda(\Delta_{l} \mathcal{F}) \subseteq \Lambda(2 \Pi_{l}\mathcal{F})$, then, by the definition of $\tau$, $\tau_{\Delta_{l} \mathcal{F}} \leq \tau_{2 \Pi_{l} \mathcal{F}} \leq 2\tau_{\Pi_{l} \mathcal{F}}$, so the desired inequality follows. We now show $\Lambda(\Delta_{l} \mathcal{F}) \subseteq \Lambda(2 \Pi_{l}\mathcal{F})$. Take any $g \in \Lambda(\Delta_{l} \mathcal{F})$, it follows that $|g(x)-g(y)| \leq \sup_{h \in \Delta_{l} \mathcal{F}} |h(x)-h(y)|$. Since $h$ has to be of the form $f_{l}-f_{-l}$ for $f_{l},f_{-l}$ in $\Pi_{l}\mathcal{F}$, it follows that $|g(x)-g(y)| \leq \sup_{h \in 2 \Pi_{l}\mathcal{F}} |h(x)-h(y)|$. Hence $g \in \Lambda(2 \Pi_{l}\mathcal{F})$.
Therefore,
Thus, the desired result follows because $\sum_{l=0}^{\infty} 2^{ 2d 2^{l/c} } e^{- 2\ell(l)^{2} } \leq \sum_{l=0}^{\infty} e^{- m d 2^{l/c}}$ where $m : = 2(1-\ln 2) \geq 1/2$.