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.
111,041 characters · 17 sections · 112 citation commands
On the Non-Asymptotic Properties of Regularized M-estimators
Regularized M-estimators are ubiquitous in econometrics and statistics. They appear in several models, ranging from semi-/non-parametric models such as semi-/non-parametric regressions and semi-/non-parametric likelihood models, to high-dimensional regression models, just to name a few.\footnote{See Bickel-Li-TEST06 for references and discussion.} In these models, the standard M-estimator might be ill-defined or ill-behaved so a regularized version of the M-estimator is needed. A few examples of these estimators which are widely used by practitioners are: series/sieves-based estimators (e.g. Grenander1981, GemanHwang1982, GallantNychka1987 and shen1994), Kernel-based estimators (e.g. Nadaraya and Watson estimators) and penalized estimators (e.g. shen1997, and EggLaRic2001 and references therein) --- which include LASSO and Ridge regressions in high-dimensional models (e.g. VdG-Buhlmann11 and references therein).
Even though regularization methods are a powerful tool to study otherwise ill-posed problems, they rely on tuning parameters that ought to be chosen by the researcher. E.g., the number of terms in the series/sieves estimators, the bandwidth in the Kernel-based estimators or the scale of the penalization in penalized-based estimators.
Our goal is to propose an unifying framework that encompasses, among others, the aforementioned models and allow us to study the effect of these tuning parameters on the behavior of the estimator, how this effect changes with the number of observations and also with the time-dependence structure in the data. Moreover, we provide a data-driven method to choose the tuning parameters. Our framework allows for (potentially) infinite-dimensional parameters which are identified by minimization of a criterion function, and also for dependence in the data --- quantified using $\beta$-mixing (or regular mixing) conditions.\footnote{See Bradley2005 for references and discussions of mixing processes.} By focusing on time-dependent data we extend the scope of high-dimensional models to many applications in fields like economics and finance, where time-dependent data is ubiquitous (e.g. SongBickel2011, FanLvQi2011). Also, from a conceptual point of view, time-dependent data provides a good laboratory to study departures from the standard setup of i.i.d. observations.
The standard approach for handling tuning parameters, especially in semi-/non-parametric problems, relies on asymptotic theory. In this paper we take another route and we, instead, establish non-asymptotic results. An appealing feature of this approach is that it allows us to understand the incidence of tuning parameters on the properties of the estimator for a given sample size, and also, how this depends on the underlying data structure, namely its dependence structure. Overall, our results provide a more accurate description of the estimator's behavior than the standard asymptotic ones, and even extend them in some settings.
In order to assess the behavior of our estimator, we focus on the so-called concentration properties. That is, we provide non-asymptotic bounds for the probability that our estimator is within a certain ball of the identified parameter. We characterize how the sample size, the tuning parameters and the dependence structure affect the radius of this ball. This radius, called the concentration rate, should be thought as analogous to the convergence rate in asymptotic theory. We think that studying concentration properties are a necessary and important first step for assessing the finite sample behavior of regularized estimators, and also constitute the foundation for establishing the asymptotic results of consistency and convergence rates.
The concentration rate is comprised of two familiar terms: a \textquotedblleft variance" term and a \textquotedblleft (squared) bias" term. The behavior of the former term depends on (i) how \textquotedblleft large/complex” the underlying parameter set is, and on (ii) the so-called effective sample size. For i.i.d. data, the quantity in (ii) is simply the number of observations; for dependent data, however, it can be strictly (even asymptotically) smaller than the number of observations. The effective sample size depends on the dependence structure, quantified by the $\beta$-mixing condition, and captures the intuition that high dependence in the data reduces the information of each observation. Regarding the quantity in (i), one contribution of this paper is to propose a, to our knowledge, novel measure of complexity of the parameter set.
More precisely, we first show that the behavior of the \textquotedblleft variance" term is governed almost entirely by the behavior of the supremum of the scaled (regularized) criterion function over the parameter set. The behavior of this quantity in turn depends on how \textquotedblleft large or complex” the parameter set is; we quantify this by defining a new measure of complexity inspired by Talagrand's Generic Chaining approach (talagrand1996). In fact, if the loss function is Lipschitz, our measure of complexity is proportional to Talagrand's Generic Chaining bound. Therefore, by Talagrand's results (talagrand2005,talagrand2014) our measure of complexity is bounded above by the one based on metric-entropies (Dudley-1967); i.e., one can do no worse with our measure than with the more standard one used in the literature. Moreover, in some cases, our measure is also bounded above by the expectation of the supremum of a Gaussian process, which is fairly “easy" to bound object.\footnote{In 2015arXivDemian, we show that our measure is also a lower bound for bracketing-entropies (ossiander1987).}
Second, we show that the effect of the dependence structure of the data on the concentration rate can be summarized by a re-scaling of the number of observations. That is, we show that “variance" term (or rather a bound of it) is analogous to the one obtained in the i.i.d. data case, but with a modified (smaller) sample size, instead of the actual sample size. We call this the effective number of observations. In order to fix ideas, consider a very simple linear regression model with $k$ covariates and with $m$-dependent data.\footnote{That is, an observation at time $t$ is independent for all observations at time $t-m$, $t-m-1$, etc. However, it can be correlated with observations at time $t-1$,...,$t-m+1$.} For the case of i.i.d. data, it is not hard to show that the \textquotedblleft variance" term is of order $\sqrt{k /n }$ where $n$ is the number of observations in the sample. With $m$-dependent data, however, we show that the \textquotedblleft variance" term is of order $\sqrt{m k /n }$. I.e., is as if we only had $n/m$ observations for computing the estimator, as opposed to the original $n$; $n/m$ is our effective number of observations for this case. Intuitively, this loss reflects the fact that, without any further restrictions on the correlation within the “window" of m-observations, is as if we can only use $n/m$ observations.
This example serves to illustrate another point regarding the usefulness of non-asymptotic results. For $m$ fixed, the previous discussion implies that, asymptotically, the effective and actual number of observations coincide, and thus the \textquotedblleft variance" term (and ultimately the concentration rate) is asymptotically the same as the one for the i.i.d. case. However, in finite samples, when $m$ is comparable to the number of observations, the effective number of observations can be small, ultimately yielding a concentration rate that can be slower than the one for the i.i.d. case and the one predicted by the asymptotic theory. We provide numerical simulations that allow us to quantify this point in a regression setting.
The aforementioned observation holds more generally, for cases where the $\beta$-mixing coefficients decay \textquotedblleft fast enough” to zero (the exact rate is established in the paper). This result is consistent with the existing asymptotic results which show that the convergence rates for this case coincide with those for the i.i.d. case (e.g. CS-1998 and ChenLiao2013). Our non-asymptotic approach thus offers a sharper characterization of the role of dependency than the one provided by the asymptotic approach. On the other hand, to our knowledge, there are no general asymptotic results for the case of “slow-decaying" $\beta$-mixing coefficients. Here, we provide non-asymptotic concentration results, and show that in this case, the concentration rates are slower than in the i.i.d. case, even asymptotically. This result thus extends existing asymptotic results to situations where the dependency in the data decays “slowly”.
Finally, on a more technical point, our derivations show that under general $\beta$-mixing structure, the natural topology for determining the size/complexity of the parameter set is given by a family of norms, each depending on the mixing structure. This is in contrast to the cases of i.i.d data or “fast-decaying" $\beta$-mixing coefficients where a single norm is used (cf. DMR1995 and CS-1998).
We conclude with an application of our concentration result to the problem of selection of the tuning parameter. We provide a data-driven method for choosing the tuning parameter, which relates to Lepskii's method (Lepskii1991) and is an adaptation to M-estimation of the one first proposed by PereverzevSchock2006. The motivation for this method is as follows. In many cases choosing the tuning parameter to balance the \textquotedblleft (squared) bias" and the \textquotedblleft variance" terms yields good convergence rates, even achieving min-max convergence rates (see Barron1999 and refences therein). This method, however, requires knowing the “bias" term which is typically unknown to the practitioner. By exploiting our concentration results, we show that our method yields (up to constants) the same concentration rate as the aforementioned choice, but with the salient feature that it does not rely on any knowledge of the \textquotedblleft bias" term. We thus view our method as a viable alternative to Cross Validation methods which require data splitting and restrictions on the shape of the loss function (shao1997,arlot2010) both of which can be delicate in general frameworks with time-dependent data.
Related Literature. Conceptually our general setup is based on the excellent reviews by Bickel-Li-TEST06 and massart2007. The construction of our estimator is based on CP-2012 PSMD estimator (adapted to M-estimation) and Chen2013.
We build on and contribute to several strands of literature. First, we contribute to the extensive branch of high dimensional models; we refer the reader to VdG-Buhlmann11 book for a thorough review of the literature and an extensive treatment of LASSO (Tibshirani1996) and similar models. In econometrics, we refer the reader to BCH2013 review article for discussions and applications. Our paper is aligned with many papers in this literature in terms of the non-asymptotic nature of our results, however, the vast majority of these papers only derive results under i.i.d. data. In this framework, closest to ours is the paper by NRWY2012 who derives non-asymptotic results for M-estimators under (a stronger) set of assumptions (the so-called decomposability assumption and strong convexity-type assumptions). While we view our results as complementary to theirs, we try to derive the non-asymptotic results under “minimal" assumptions; in this sense, our approach throughout the paper relates to the work by Chatterjee2013 about “assumptionless" consistency of the LASSO.
Second, we contribute to the vast literature of non-/semi-parametric models. We refer the reader to Powell1994 and Chen2013 for excellent reviews; the latter focusing on time dependent data. As opposed to high-dimensional models, in this branch there are many paper studying the behavior of estimators under time dependent data; however, most of these results are asymptotic. massart2007 offers a nice review of non-asymptotic results but for i.i.d data. From these papers, closest to ours are CS-1998 and ChenLiao2013 who derive asymptotic results (both convergence rate and inference) for sieve and penalized M estimators respectively, for $\beta$-mixing decay of the order $O(q^{-\varpi})$ with $\varpi > 2$. They rely on $L^{2}$ bracketing entropy to measure the complexity or size of the parameter set. YU1994 establishes rates of convergence empirical processes for time dependent data; we employ the coupling technique in the paper to derive exponential bounds.
Third, our results about the complexity measure build on Talagrand's Generic Chaining approach; see talagrand2014 for a recent book treatment. To our knowledge this approach has not been used before in M-estimation problems, with the notable exception of vandeGeer2013. The idea that the notion of distance used to construct the complexity measure depends on the mixing structure was first pointed out by DMR1995 in the context of central limit results and under the assumption of sufficiently fast decaying $\beta$-mixing coefficients.\footnote{See their paper and our Section (ref) for a precise statement regarding the rate of decay.} This last assumption ensures that a single norm suffices to construct a Ossiander's bracket entropy integral (see ossiander1987), which the authors used as their measure of complexity. However, if the assumption is dropped --- i.e., the $\beta$-mixing coefficients decay slowly --- then their norm, and thus their approach, does not work as stated. Our results, propose a natural extension of their insight by allowing a family of norms to describe the relevant notion of distance used to construct the measure of complexity.
Fourth, the approach for choosing the tuning parameter is an adaptation of the method proposed in PereverzevSchock2006, developed for an ill-posed inverse problem with known linear operator and measurement error in the data and thus being not directly amenable for our purposes. In statistical/econometrics applications, the paper by ChenTim2015 uses a similar method for choosing the tuning parameter under the $L^{\infty}$ norm for the non-parametric IV model under i.i.d. data. Horowitz2014 proposes an alternative way of choosing the tuning parameter for the same model but under the $L^{2}$ norm and also under i.i.d. assumption; his procedure attains the optimal $L^{2}$-norm rate up to a $\sqrt{\log(n)}$. Finally, we refer the reader to massart2007 for a review of model selection in this setup.
Roadmap. Section (ref) presents some illustrative examples. Section (ref) defines the data structure, the M-estimation model (subsection (ref)) and the regularized M-estimator (subsection (ref)). Section (ref) presents the concentration result for the regularized M-estimator and a discussion; it introduces the notion of effective number of observations and establishes bounds for our measure of complexity (subsection (ref)). Section (ref) proposes the method for choosing the tuning parameters. Section (ref) presents some numerical simulations. All proofs are gathered in the Appendix.
Notation. For a generic Polish space $\mathbb{X}$ the associated $\sigma$-algebra is the Borel $\sigma$-algebra. All functions that we define from $\mathbb{X}$ are taken to be Borel measurable. For any set $A \subseteq \mathbb{X}$ and distance function $d$, $d(x,A) \equiv \inf_{x' \in A} d(x,x')$. All statements involving measurable functions are taken to hold almost surely with respect to the true probability (which we denote as $\mathbf{P}$ below). For any probability measure $P$, $E_{P}[.]$ denotes the expectation with respect to $P$; sometimes we omit the dependence, in this cases the expectation is taken with respect to the true probability measure $\mathbf{P}$. For any function $f$ from $\mathbb{X}$ to $\mathbb{Y}$, $x \mapsto f(x)$ denotes the function and $x_{1} \mapsto f(x_{1},x_{2})$ is used when viewing $f$ as a function of $x_{1}$, keeping $x_{2}$ fixed. For two real-valued sequences $(x_{n})_{n}$ and $(y_{n})_{n}$, $x_{n} \precsim y_{n}$ ( $x_{n} \succsim y_{n}$) means that there exists a finite universal constant, $C \geq 1$, such that $x_{n} \leq C y_{n}$ ( $C x_{n} \geq y_{n}$); $x_{n} \asymp y_{n}$ means that both $x_{n} \precsim y_{n}$ and $x_{n} \succsim y_{n}$ hold. For any given real-valued sequence, $(x_{k})_{k}$, $x_{k} \downarrow a$ denotes that (a) the sequence is decreasing and (b) its limit is $a$; $\uparrow$ is defined analogously. Finally, $\mathbf{N}$ denotes $\{...,-1,0,1,...\}$, $\mathbb{N} = \{ 1,2,3,...\}$ and $\mathbb{N}_{0} = \mathbb{N} \cup \{ 0 \}$.
The following example presents a high-dimensional quantile regression (HD-QR) model. Quantile regression (koenker1978regression) is a widely used statistical method that provides an alternative to linear regressions models by capturing the heterogeneous impact of regressors on different parts of the distribution. Recently, many papers (BelloniChern2011, koenker2004quantile, wang2012quantile, wu2009variable) extend the original framework to high-dimensional settings. Here, we extend it further to allow for dependent data, and also derive the results without imposing sparsity (akin to Chatterjee2013). By doing this, we hope our results extend the scope of HD-QR models to cover applications in finance and economics, where time-series data is ubiquitious.\footnote{Related models are also CW1999 who studied a non-parametric version for dependent data; Wu2008 who studied kernel estimation of conditional quantiles for dependent data; and KoenkerXiao2006 who studied a parametric quantile auto-regression model.}
Other examples, such as Non-parametric regression also falls into our framework.
The following example is designed to provide an overview of the main results derived below, in Section (ref). In particular, the example showcases the key arguments behind the main theorems, and also highlights the role of the so-called effective number of observations. To keep the setup as simple as possible, we abstract from any regularization.
We now introduce the data structure, define the model and the regularized estimator.
Let $\omega \equiv (...,Z_{-1},Z_{0},Z_{1},...)$ with $Z \in \mathbb{Z} \subseteq \mathbb{R}^{|\mathbb{Z}|}$ for some $|\mathbb{Z}| \in \mathbb{N}$ finite. Let $\Omega = (\mathbb{Z})^{\mathbf{N}}$ be the sample space. Let $\mathcal{Z}_{m}^{n}$ be the $\sigma$-algebra generated by $Z_{m:n} = (Z_{m},...,Z_{n})$ for any $m \leq n$. Let $\mathbf{P}$ be the true probability over $(\Omega,Borel)$. We assume that $ \mathbf{P}$ belongs to a class of stationary and $\beta$-mixing (or absolutely regular) probabilities, i.e., there exists a function $\beta : \mathbb{R}_{+} \rightarrow \mathbb{R}$ such that $\lim_{q \rightarrow \infty} \beta(q) =0$ and $\sup_{t} \boldsymbol{\beta}(\mathcal{Z}^{t}_{-\infty},\mathcal{Z}_{t+q}^{+\infty}) \leq \beta(q)$ for all $q \in \mathbb{N}_{0}$ where
where the \textquotedblleft sup" is taken over all pairs of partitions $(U_{i})_{i\in I}$ and $(V_{i})_{i\in I}$ on $\Omega$ such that $U_{i} \in \mathcal{U}$ and $V_{i} \in \mathcal{V}$, and $\mathcal{U}$ and $\mathcal{V}$ are $\sigma$-algebras; see VolRoz1959 and DMR1995 p. 397. For technical reasons, we also require $\beta$ to be cadlag and non-increasing.
The results in the paper hinge on well-known coupling results for $\beta$-mixing processes; in particular, following YU1994, in our proofs we use the following fact:\footnote{See also CS-1998.} For any $q \in \mathbb{N}$, let $(Z^{\ast}_{i})_{i \in \mathbb{N}_{0}}$ be independent of $(Z_{i})_{i \in \mathbb{N}_{0}}$ and such that: (1) $U^{\ast}_{i}(q) \equiv (Z^{\ast}_{iq+1},...,Z^{\ast}_{iq+q})$ has the same distribution as $U_{i}(q) \equiv (Z_{iq+1},...,Z_{iq+q})$ for any $i=0,1,...$; (2) The sequence $(U^{\ast}_{2i}(q))_{i\geq 0}$ is i.i.d. and so is $(U^{\ast}_{2i+1}(q))_{i \geq 0}$; and (3) $\mathbb{P}(U^{\ast}_{i}(q) \ne U_{i}(q) ) \leq \beta(q)$ for any $i=0,1,...$. where $\mathbb{P}$ is the product measure of $\mathbf{P}$ and $\mathbf{P}^{\ast}$ --- the probability distribution of $\omega^{\ast} \equiv (...,Z^{\ast}_{-1},Z^{\ast}_{0},Z^{\ast}_{1},...)$; see DL2002 pp. 144-152 and MP2002 Theorem 2.9 and references therein.
Consider a Banach space $(\Theta,||.||_{\Theta})$ and some subset $\mathcal{P}$ of the space of Borel probability measures over $\Omega$ that are stationary and $\beta$-mixing, and $\mathbf{P} \in \mathcal{P}$. Our interest is the estimation of a parameter $\theta_{\ast} \in \Theta$ such that for some given criterion function $Q : \mathcal{P} \cup \mathcal{D} \times \Theta \rightarrow \mathbb{R}_{+}$ (where $\mathcal{D}$ the set of discretely supported distributions)\footnote{The reason for including $\mathcal{D}$ in the domain of $Q$ is to ensure that, for our estimator, $Q$ is well-defined once it is evaluated in the empirical distribution. We could relax this assumption by generalizing the definition of regularized M-estimator below.}
I.e., the parameter of interest, $\theta_{\ast}$, is characterized as the minimizer of the criterion function at $\mathbf{P}$ over $\Theta$. We focus on M-estimation problems, wherein $Q(\theta,P)=E_{P}[\phi(Z,\theta)]$ for a given loss function $\phi : \mathbb{Z} \times \Theta \rightarrow \mathbb{R}$ such that $\{ \phi (\cdot,\theta) \colon \theta \in \Theta \} \subseteq L^{1}(\mathbf{P})$.
Let $\nu : \mathcal{P} \rightarrow 2^{\Theta}$ be the parameter mapping where
and $\nu(P)$ be the identified parameter (set) at $P$. Clearly, if $\nu(\mathbf{P})$ is non-empty, $\theta_{\ast} \in \nu(\mathbf{P})$. In Appendix (ref) we present a low-level condition that ensures the non-emptiness of $\nu(\mathbf{P})$.\footnote{The condition essentially restricts the lower-contour sets of $Q(.,\mathbf{P})$ to be compact under some topology, not necessarily the one induced by $||.||_{\Theta}$.} Henceforth, $Q(\nu(\mathbf{P}),\mathbf{P})$ should be understood as $Q(\theta,\mathbf{P})$ for some (any) $\theta \in \nu(\mathbf{P})$. Our analysis admits the identified parameter set, $\nu(\mathbf{P})$, to be a non-trivial set; i.e., the criterion may not identify the parameter of interest. In this case, our results would be about concentration at the whole identified set $\nu(\mathbf{P})$.
In this general setup, it is well-known that the mapping $\nu$ may be ill-defined or even if it is well-defined, it could be ill-behaved (e.g., discontinuous) once evaluated in the empirical distribution; see Bickel-Li-TEST06 and references therein. Therefore, we need to regularize the problem.
Our goal is to study the concentration properties of the class of regularize M-estimators. We now define these concepts.
The Regularized M-estimator. In the spirit of Bickel-Li-TEST06, we define a regularized estimator as a sequence of set-valued functions $\boldsymbol{\nu} = (\nu_{k})_{k \in \mathbb{N}}$ with $\nu_{k} : \mathcal{P} \cup \mathcal{D} \rightarrow 2^{\Theta}$ such that $\nu_{k}(P_{n})$ is a singleton, where $P_{n} \equiv n^{-1} \sum_{i=1}^{n} \delta_{Z_{i}}$ is the empirical distribution.
To define a regularized M-estimator, we need the following definition of regularization structure. This definition also clarifies the role of $k$ in the definition of regularized estimator.
For each $k \in \mathbb{N}$, let $Q_{k} = Q + \lambda_{k} Pen$ be the Regularized Criterion Function, and
As illustrated in the examples, this definition is quite general and encompasses many widely used estimators; e.g. such as Penalization-based LASSO or Ridge in high-dimensional models, or sieve/series and penalization for semi-/non-parametric models.
The Regularized Parameter Set. For any $k \in \mathbb{N}$, let
be the regularized parameter (set).\footnote{Lemma (ref) in the Appendix (ref) provides sufficient conditions to show that $\nu_{k}(\mathbf{P})$ is non-empty.} As in the case of the identified parameter, our analysis goes through even if $\nu_{k}(\mathbf{P})$ is not a singleton. Henceforth, $Q_{k}(\nu_{k}(\mathbf{P}),\mathbf{P})$ should be understood as $Q_{k}(\theta,\mathbf{P})$ for some (any) $\theta \in \nu_{k}(\mathbf{P})$.
Finally, we formally define the concentration property for a regularized estimator.
Concentration Property. Let $\mathbf{r} = (r_{n,k})_{n,k \in \mathbb{N}^{2}}$ with $r_{n,k} : \Omega \rightarrow \mathbb{R}_{+}$ and $g : \mathbb{R}_{+} \rightarrow [0,1]$.
That is, if a regularized estimator satisfies the concentration property with parameters $(\mathbf{r},g)$, with probability higher than $1-g(u)$, the estimator is within a $u r_{n,k}$-neighborhood (under $d$) of the identified set $\nu(\mathbf{P})$. In cases where $\lim_{u \rightarrow \infty} g(u) = 0$ and $r_{n,k(n)} \rightarrow 0$ as $n \rightarrow \infty$ a.s.-$\mathbf{P}$ for some $n \mapsto k(n)$, this property implies the asymptotic convergence (under $d$) at rate $(r_{n,k(n)})_{n}$ to the identified set $\nu(\mathbf{P})$.
We now present the main theorem of the paper which establishes a concentration property for our regularized M-estimator. We first define some necessary concepts to construct the “bias" term and the “variance" term of the concentration rate. In particular, for the latter term we need to define a notion of complexity of the parameter space.
Unless otherwise stated, we restrict our attention to $q \in \mathcal{Q}_{n} = \{ m \in \mathbb{N} \colon n/m \in \mathbb{N} \}$ and $n = \prod_{i=1}^{\upsilon} p_{i}^{m_{i}}$ for some some $\upsilon \in \mathbb{N}$, $(m_{i})_{i=1}^{\upsilon} \in \mathbb{N}_{0}^{\upsilon}$ and $(p_{i})_{i=1}^{\upsilon}$ consecutive primes. This restriction is not crucial for our results and can be relaxed, but it simplifies the exposition and technical derivations. The choice of $\mathcal{Q}_{n}$ ensure that when constructing the blocks described in Section (ref) with length $q \in \mathcal{Q}_{n}$, the number of blocks is an integer.\footnote{For instance, this fact simplifies the decompositions in Lemma (ref) in the Appendix.} The restriction over $n$ is simply to ensure that $\mathcal{Q}_{n}$ is “rich enough" and its elements are not too far apart; see Online Appendix (ref) for a more thorough discussion.
Notion of distance and the Bias Term. For all $\theta \in \Theta$, let\footnote{Note that $\delta_{\mathbf{P}}(\cdot,\mathbf{P})$ is well-defined because $Q(\theta,\mathbf{P}) \geq Q(\nu(\mathbf{P}),\mathbf{P})$ for all $\theta \in \Theta$.}
As illustrated in Section (ref) below, the proof for the concentration results amounts to studying the behavior of the criterion function. Hence, in this context, $\delta_{\mathbf{P}}$ presents itself as the natural choice to measure distance over $\Theta$ and, loosely speaking, can be viewed as a generalization of the root mean square error. This observation notwithstanding, the relevant notion of distance ultimately depends on the application at hand, and in many instances one would like a concentration property under more standard metrics such as $\ell^{p}$ or $L^{p}$ norms. For instance, in the HD-QR example (ref), we argue that a natural distance is $||\sqrt{W_{k}}(\cdot)||_{\ell^{2}}$, which has the property that $\delta_{\mathbf{P}}(\cdot,\nu(\mathbf{P})) \geq ||\sqrt{W_{k}}(\cdot - \nu(\mathbf{P}))||_{\ell^{2}}$. In Proposition (ref) below we generalize this idea and provide concentration results for general metrics.
For any $k \in \mathbb{N}$, let
be the \textquotedblleft bias term" under the metric induced by $\delta_{\mathbf{P}}$. It reflects the two sources of the \textquotedblleft bias": The fact that our estimator is constructed over $\Theta_{k}$ (and not $\Theta$) and also the fact that we add a penalization term when $\lambda_{k}>0$.\footnote{Lemma (ref) in Appendix (ref) provides conditions to ensure that the bias vanishes as $k$ diverges.}
Measure of Complexity. The measure of complexity is inspired by Talagrand's Generic Chaining results (see talagrand1996, talagrand2005 and talagrand2014), but to our knowledge the exact construction is new.
For any $A \subseteq \Theta$, let $\mathcal{F}(A) = \{ f : \mathbb{Z} \rightarrow \mathbb{R} \mid \exists \theta \in A,~f(.) = \phi(.,\theta)-\phi(.,\nu_{k}(\mathbf{P})) \}$.\footnote{We are abusing notation by writing $\phi(.,\nu_{k}(\mathbf{P}))$. If $\nu_{k}(\mathbf{P})$ is a set, $\phi(.,\nu_{k}(\mathbf{P}))$ is defined as $\phi$ evaluated at one element of the set and fix it throughout the following arguments.} For any $A \subseteq \Theta$, let $(\mathcal{T}_{l})_{l \in \mathbb{N}_{0}}$ be an increasing sequence of partitions (of $\mathcal{F}(A)$) such that $card(\mathcal{T}_{l}) \leq 2^{2^{l}}$ and $\mathcal{T}_{0} = \mathcal{F}(A)$. That is, each $\mathcal{T}_{l}$ consists of a partition of $\mathcal{F}(A)$ with (at most) $2^{2^{l}}$ elements. We call such sequence an admissible sequence; we denote the set of all such sequences as $\mathbf{T}$. For any $f \in \mathcal{F}(A)$ and $l \in \mathbb{N}_{0}$, there is only one set in $\mathcal{T}_{l}$ that contains $f$; we call it $T(f,\mathcal{T}_{l})$. Finally, for any $z \in \mathbb{Z}$, let $S(f,\mathcal{T}_{l})(z) = \sup_{f_{1},f_{2} \in T(f,\mathcal{T}_{l})} |f_{1}(z) - f_{2}(z)|$.
We relegate a discussion of its properties to Section (ref). As explained below in Section (ref), the fact that the complexity depends on a family of distances --- as opposed to only one norm/distance --- is important for our analysis. The relevant family of norms is given by $\left( ||.||_{q_{n,k}} \right)_{k \in \mathbb{N}_{0}}$ where, for any $n$ and $k \in \mathbb{N}_{0}$,
where for each $(n,k)$, $q_{n,k}$ acts as the parameter $q$ controlling the bound of the coupling results in Section (ref). And for any $f \in \mathcal{F}(\Theta)$ and $q \in \mathbb{N}$, let
where $Q_{f}$ is the quantile function of $|f|$ and\footnote{That is, for any $u \geq 0$, $Q_{f}(u) = \inf \{ s \mid H_{f}(s) \leq u \}$ with $H_{f}(s) = \mathbf{P}(|f(Z)| > s)$.}
Observe that the dependence structure enters the definition of the norm $||.||_{q}$ through $\mu_{q}$. In particular, note that $||f||^{2}_{L^{2}(\mathbf{P})} = \int_{0}^{1} Q^{2}_{f}(u) du$, so if $q \mapsto \mu_{q}$ were constant, then $||.||_{q}$ is proportional to $||.||_{L^{2}(\mathbf{P})}$. However, for general $\beta$-mixing processes, $\mu_{q}$ is not constant and acts as a weight function for the quantile $Q_{f}$.
Finally, for any $A \subseteq \Theta$ and any $n$, let
Abusing terminology, we call $\gamma_{n}(A)$ the Complexity Measure of set $A$ given $n$.
We now define the \textquotedblleft variance term" of the concentration rate. For any $k \in \mathbb{N}$ and any $M \geq 0$, let $\Theta_{k}(M) \equiv \{ \theta \in \Theta_{k} : \lambda_{k} Pen(\theta) \leq M \}$, and let $\omega \mapsto M_{n,k}(\omega) \equiv Q_{k}(\theta_{k},P_{n}) + \eta_{n}$ for some (any) $\theta_{k} \in \Theta_{k}$. It follows that our estimator belongs to $\Theta_{k}(M_{n,k}(\omega))$ a.s.-$\mathbf{P}$, and thus this is the relevant set over which we do our analysis.
For any $s > 0$, let
where $I_{n,k}(\omega)(s) \equiv \{ \theta \in \Theta_{k}(M_{n,k}(\omega)) \mid s \geq \delta_{k,\mathbf{P}}(\theta, \nu_{k}(\mathbf{P})) \geq 0.5 s \} $ and \footnote{Observe that $\delta_{k,\mathbf{P}}(\theta,\nu_{k}(P)) \geq 0$ for all $\theta \in \Theta_{k}$.}
That is, $\gamma_{n}( I_{n,k}( \omega )(s))$ measures the complexity of an “$\delta_{k,\mathbf{P}}$-strip” of $\Theta_{k}(M_{n,k}(\omega))$. For any $(n,k)$, the “variance term” is given by
Concentration result. Let $\boldsymbol{\varrho} = \{ \varrho_{n,k} : \Omega \rightarrow \mathbb{R}_{+} \}_{n,k}$ such that for any $(n,k)$
This sequence is the concentration rate of our estimator. Let $\mathbb{G}_{0} = 3 \left( p_{\upsilon} \left( 8.1 \right) + \sqrt{2} \times 8 \right)$, and for any $u \geq \mathbb{G}_{0}$, let $g_{0}(u) = \mathbb{G}_{0} u^{-1} $, and $g_{0}(u) = 1$ for $ u \in [0,\mathbb{G}_{0})$.\footnote{The constant follows from the bounds that appear in the Propositions in the Appendix (ref).} We now establish a concentration property for our regularized M-estimator. We note that this result is obtained without assumptions, other than $\nu(\mathbf{P}) \ne \{ \emptyset \}$.
Before discussing its implications, we derive an upper bound on $||.||_{q_{n,k}}$ which introduces a key component of the variance term (and hence, of the concentration rate), the so-called effective number of observations. It follows that for any $q \in \mathbb{N}$ and any $r>2$,\footnote{This is proven in Lemma (ref) in the Online Appendix (ref).}
Since $||.||_{L^{r}(\mathbf{P})}$ does not depend on the mixing structure, in order to understand how the mixing structure affects concentration rates, it suffices to study the sequence $\left\{ \left( \int_{0}^{1} |\mu_{q_{n,k}}(u)|^{\frac{r}{r-2}} du\right)^{\frac{r-2}{2r}} \right\}_{n,k}$. Using this observation, the next Theorem provides bounds for the \textquotedblleft variance term" of the concentration rate.
We call $n(\beta)$ the effective number of observations. The Theorem indicates that is the effective number of observations --- rather than $n$ --- the right measure of the sample size in the variance term of the concentration rate. It also illustrates how the dependence structure affects the concentration rate: By scaling the sample size through the term $\left(2\int_{0}^{1} |\mu_{q_{n,0}}(u)|^{\frac{r}{r-2}} du \right)^{\frac{r-2}{2}} $. Moreover, by inspection of $\int_{0}^{1} |\mu_{q_{n,0}}(u)|^{\frac{r}{r-2}} du$, we can see that the integrability of $\mu_{q_{n,0}}$ --- which in turn relates to the one of $\beta^{-1}$; see equation (ref) --- plays an important role; we relegate a more thorough discussion of this and the effective number of observations to section (ref).
Concentration Property under general metric. The next proposition establishes the concentration property for a general metric $\varpi$; to do so, it is paramount to quantify the relationship between $\delta_{k,\mathbf{P}}$ and the desired metric $\varpi$.
Let $\boldsymbol{\tilde{\varrho}} = (\tilde{\varrho}_{n,k})_{n,k}$, where, for any $(n,k)$, $\tilde{\varrho}_{n,k}(\omega) = \tilde{V}_{n,k}(\omega) + \varpi(\nu_{k}(\mathbf{P}),\nu(\mathbf{P}))$, with
and $ \tilde{I}_{n,k}(\omega)(s) = \{ \theta \in \Theta_{k}(M_{n,k}(\omega)) \mid s \geq \varpi(\theta, \nu_{k}(\mathbf{P}) ) \geq 0.5 s \} $.
Condition (ref) is akin to the identifiable uniqueness condition (e.g. see WW1991) and to measures of ill-posedness in the context of ill-posed inverse problems (see CP-2012). The condition quantifies how well the regularized criterion separates points (away from $\nu(\mathbf{P})$) in the metric space $(\Theta,\varpi)$. The main difference with the results in the Theorem (ref) is the scaling by $\underline{\varpi}_{k}$ in the variance term. Ideally $\underline{\varpi}_{k}(M,\epsilon) \geq c >0$ for all $k,M,\epsilon$, so in this case $\tilde{V}_{n,k}$ is proportional to $V_{n,k}$ for any $(n,k)$. There could be cases, however, where $\limsup_{k\rightarrow \infty} \underline{\varpi}_{k}(M,\epsilon) = 0$, thus implying that $\tilde{V}_{n,k}/V_{n,k}$ will diverge.
$L^{1}$ non-asymptotic bound. Theorem (ref) implies, under additional integrability restrictions, an $L^{1}$ non-asymptotic bound for our estimator.
A function $\varphi_{n,k}$ always exist if $\frac{\delta_{\mathbf{P}}(\nu_{k}(P_{n}),\nu(\mathbf{P}))}{\varrho_{k,n}(\omega)}$ is in $L^{1}(\mathbf{P})$. So we view the assumption in the proposition as a way of quantifying the tail behavior of $\frac{\delta_{\mathbf{P}}(\nu_{k}(P_{n}),\nu(\mathbf{P}))}{\varrho_{k,n}(\cdot)}$. For instance, if $\sup_{\theta \in \Theta_{k} } \delta_{\mathbf{P}}(\theta,\nu(\mathbf{P})) \leq D_{k} < \infty$ and $\boldsymbol{\varrho}$ is non-random, we choose $\varphi_{n,k}(A) = 1\{ A \leq D_{k}/\varrho_{n,k} \}\frac{D_{k} \log (1+D_{k})}{\varrho_{n,k}\log (1 + A \varrho_{n,k})} $ and obtain $E_{\mathbf{P}} \left[\delta_{\mathbf{P}}(\nu_{k}(P_{n}),\nu(\mathbf{P})) \right] \leq \varrho_{k,n} (1+\mathbb{G}_{0} \log (2D_{k}) + \mathbb{G}_{0} \log (1/\varrho_{k,n}))$ for any $(n,k)$.
Informally, the proof of Theorem (ref) can be divided into two main parts. The first part relies on “Wald's approach" (wald1949) and is fairly standard in this setting (e.g., see CS-1998). It hinges on first noting that $\delta_{\mathbf{P}} \left( \nu_{k}(P_{n}), \nu(\mathbf{P}) \right) \leq \delta_{k,\mathbf{P}} \left( \nu_{k}(P_{n}), \nu_{k}(\mathbf{P}) \right) + \sqrt{B_{k}(\mathbf{P})}$, so it is sufficient to show that $\{\delta_{k,\mathbf{P}} \left( \nu_{k}(P_{n}), \nu_{k}(\mathbf{P}) \right) \geq u V_{n,k}(\omega)\}$ has probability lower than $g_{0}(u)$. In order to do this we \textquotedblleft slice" this set into strips of the form $I_{n,k,l} \equiv \{ 2^{l} u V_{n,k}(\omega) \geq \delta_{k,\mathbf{P}} \left( \nu_{k}(P_{n}), \nu_{k}(\mathbf{P}) \right) \geq 2^{l-1} u V_{n,k}(\omega)\}$ for $l=1,2,...$. After some tedious calculations it follows that it suffices to control uniformly the process $\theta \mapsto \mathcal{L}_{n}(\theta) = n^{-1}\sum_{i=1}^{n} \{\phi(Z_{i},\theta) - E_{\mathbf{P}}[\phi(Z,\theta))]\}$ over $I_{n,k,l}$. The second part of the proof essentially consists of showing that the set
occurs with probability less than $2^{-l}g_{0}(u)$, and it is shown here:
By our definition of $\mathcal{F}$, the statement of the theorem can be thought directly in terms of $f \in \mathcal{F}(A)$, i.e., $\mathbf{P} \left( \sup_{f \in \mathcal{F}(A)} |n^{-1} \sum_{i=1}^{n} f(Z_{i}) - E[f(Z)] | \geq u \frac{\gamma_{n}(A)}{\sqrt{n}} \right) \leq g_{0}(u)$. The proof of this statement relies on two main insights. First, by using a chaining argument akin to that in the proof of the CLT for empirical processes based on bracketing (see VdV-W1996 Ch. 2.5), we decompose any $f \in \mathcal{F}(A)$ (and consequently $n^{-1} \sum_{i=1}^{n} f(Z_{i}) - E[f(Z)]$) into several parts (see Lemma (ref) in the Appendix (ref)); essentially, we decompose $f$ into “bounded" parts and “unbounded" parts. Second, we use Bernstein inequality for $\beta$-mixing (see Lemma (ref) in the Appendix (ref)) and the ideas in talagrand2014 to control the “bounded" parts uniformly, and we use a $L^{1}$ bound for the “unbounded" parts (see Lemma (ref) in the Appendix (ref)).
Our measure of complexity, $\gamma_{n}$, suggests that the appropriate notion of distance to measure the complexity of $\Theta$ is given by a family of norms --- as opposed to only one norm --- with each norm depending on the mixing structure. We now discuss these two features.
It follows from Lemma (ref)(3) in Appendix (ref) that for all $q \in \mathbb{N}$
(recall that $Q_{f}$ is the quantile function of $|f|$, see (ref)). In the case where $\int_{0}^{1} \beta^{-1}(2u)du $ is finite, the RHS of the previous display provides a well-defined norm for $\mathcal{F}(\Theta)$ which was first proposed by DMR1995 (henceforth, DMR) for constructing bracketing entropies. Moreover, it is easy to see that $\gamma_{n}(A) \leq \inf_{(\mathcal{T}_{l})_{l} \in \mathbf{T}} \sup_{f \in \mathcal{F}(A)} \sqrt{2} \sum_{l=0}^{\infty} 2^{l/2} ||S(f,\mathcal{T}_{l})||_{2,\beta}$. This indicates that when $\int_{0}^{1} \beta^{-1}(2u)du $ is finite, we can use the norm proposed in DMR to construct our measure of complexity for the \textquotedblleft variance term". If $\int_{0}^{1} \beta^{-1}(2u)du$ is not finite, however, the above proposal becomes infeasible since $||.||_{2,\beta}$ may not even be well-defined, and thus cannot be used to construct the measure of complexity; we need an alternative way of measuring distance. Since $||.||_{q}$ is always well-defined for any $q$, we rely on a family of norms to describe the complexity measure.\footnote{ The fact that $||.||_{q}$ is always well-defined for any $q$ follows from Lemma (ref) in Appendix (ref), which shows that $||.||_{q}$ is bounded by $\int_{0}^{1} \min\{ \beta^{-1}(2u) ,q \} Q^{2}_{f}(u) du$}
In order to shed some light on the behavior of $n(\beta)$, we provide bounds for two widely use canonical mixing structures.
Given the result in Theorem (ref) a key object to bound the variance term is $\gamma(\cdot,||.||_{L^{r}(\mathbf{P})})$. We now provide bounds in terms of the more standard metric entropy-based measure of complexity (Dudley-1967). We also link our measure of complexity to the Generic Chaining one (talagrand2014 and references therein), thereby providing “easy" to compute bounds based on maximal inequalities for Gaussian processes.
We impose the following Lipschitz restriction on $\phi$.
For instance, this assumptions is fulfilled in the HD-QR model (example (ref)) with $r=\pi_{0}$, $\mathbf{d}=||.||_{\ell^{2}}$ and $\mathbb{C}_{k,M}(z) = (1+\tau)e_{max}(xx^{T})$. The next proposition establishes an upper bound for $\gamma$.
The expression $ \inf_{(\mathcal{S}_{k})_{k} \in \mathbf{S}} \sup_{\theta \in A}\sum_{k=0}^{\infty} 2^{k/2} Diam (T(\theta,\mathcal{S}_{k}),\mathbf{d})$ is exactly Talagrand's Generic Chaining bound (talagrand2014), applied to $A$ under $\mathbf{d}$. By the calculations in talagrand2014 pp 21-24, this expression is bounded above by $\int_{0}^{\infty} \sqrt{\log N(e,A,\mathbf{d})}de $; thus showing that our measure of complexity is sharper than Dudley's entropy bound. In fact, as argued in talagrand2014 Sec. 2.3, for certain sets of $\mathbb{R}^{k}$ the difference can even diverge with $k$.
The case where $\mathbf{d}$ is induced by $||.||_{\ell^{2}(b)}$ deserves an special mention due to the work by Talagrand (e.g. talagrand2014 and references therein). Let, $\zeta_{j} \sim N(0,1)$ for $j=1,...,k$, and for any $k \in \mathbb{N}$ and $A \subseteq \Theta_{k}$
The next Proposition is a direct corollary of Proposition (ref) and talagrand2014 Theorem 2.4.1.
The proposition establishes an upper bound for our measure of complexity of $A$ (in particular $A = I_{n,k}(\omega)(s)$ or $A = \tilde{I}_{n,k}(\omega)(s)$ defined in Proposition (ref)) in terms of the expectation of the supremum of a Gaussian process. This quantity, $\Gamma_{k}(A)$, is a fairly simple object and relatively easy to bound. A general strategy to bound $\Gamma_{k}(A)$ consists of using H\"older inequality to obtain $\Gamma_{k}(A) \leq E[||\zeta||_{\ell^{q_{1}}}] \sup_{\theta \in A} ||b \cdot \theta||_{\ell^{q_{2}}}$ with $1/q_{1} + 1/q_{2} = 1$. The choice of $q_{2}$ is dictated by the geometric properties of $A$ under $|| b \cdot .||_{\ell^{q_{2}}}$, and bounding $E[||\zeta||_{\ell^{q_{1}}}]$ usually involves elementary operations since $\zeta$ are independent Gaussian. In the Online Appendix (ref) we formalize this approach and provide bounds when the penalty $Pen$ is constructed using $\ell^{q}$-norms. These observations illustrate what we consider an additional advantage of our measure of complexity over the more standard ones.
It is instructive to compare the results we obtained in the simple linear regression model in Example (ref), with those obtained by applying our general method, which cannot exploit the explicit solution of the OLS estimator.
Since $\phi(z,\theta) = n^{-1} \sum_{i=1}^{n} (y - x_{i}^{T} \theta)^{2}$ (recall that $(x_{i})_{i=1}^{n}$ are fixed, not random) and $n^{-1} \sum_{i=1}^{n} x_{i} x_{i}^{T} = I$, it can be shown that Assumption (ref) holds with $\mathbb{C}_{k,M}(z) = 2(|y| + K_{2})$ , $r=2$ and $\mathbf{d} = ||.||_{\ell^{2}}$, So, by Proposition (ref), $\gamma(A,||.||_{L^{2}}) \leq \mathbb{K}_{1} E \left[ \sup_{\theta \in A} \sum_{k=1}^{d} \zeta_{j} \theta_{j} \right] $, for any $A \subseteq \Theta$ with $\mathbb{K}_{1} \equiv \sqrt{2} L 2(E[|Y|^{2}] + K_{2})$. In particular, for $A=\{ \theta \in \Theta \mid ||\theta - \theta_{\ast} ||_{\ell^{2}} \leq s \}$ for any $s>0$, by Cauchy-Schwartz inequality, it follows that $\gamma(A,||.||_{L^{2}}) \leq \mathbb{K}_{1}s E \left[ ||\zeta ||_{\ell^{2}} \right] = \mathbb{K}_{1} s \sqrt{d}$. Also, by Proposition (ref)(1) (with $m^{-1}_{0} = \mu_{0}$ ), $n(\beta) \geq 2 \frac{n}{\mu_{0}}$.\footnote{Formally, this data structure is not stationary, but still sufficiently well-behaved to apply our theorems; in particular, $q \mapsto \beta(q) = 1\{ q \leq \mu_{0} \}$ according to our definition in Section (ref).} Therefore, by expressions (ref) and (ref), it follows that $V_{n,k} \leq 2 \mathbb{K}_{1} \sqrt{\frac{d}{n/\mu_{0}}} $, and thus Theorem (ref) implies that
The only difference between this expression and (ref) is the constant in the concentration bound.
We apply our concentration results to construct a data-driven method for choosing the tuning parameter. This method is an adaptation to regularized M-estimation of the one proposed in PereverzevSchock2006. The salient feature of this method is that it does not use any knowledge of the \textquotedblleft bias" term; it is solely based on the \textquotedblleft variance term".
Unfortunately, Theorem (ref) cannot be used to establish concentration results for the aforementioned method, since, $\delta_{\mathbf{P}}$ depends on $\mathbf{P}$ (which is unknown).\footnote{$V_{n,k}$ depends on $\mathbf{P}$ through $\delta_{k,\mathbf{P}}(.,\nu_{k}(\mathbf{P}))$.} Hence, we rely on Proposition (ref) which establishes concentration results for a metric $\varpi$ (e.g., a Banach norm over $\Theta$) and $\tilde{V}_{n,k}$ (see expression (ref)). For reasons that will become apparent in the proof of Theorem (ref), we require $\tilde{V}_{n,k}$ to be increasing as a function of $k$, or at least find an upper bound that it is. Abusing notation, let $\sqrt{B_{k}(\mathbf{P})} = \varpi (\nu_{k}(\mathbf{P}),\nu(\mathbf{P}))$.
Part (i) is a high level assumption which seems easy to obtain; we postpone its discussion to the Appendix (ref). Part (ii) ensures monotonicity of the “bias" term, which is convenient for the proof and can be somewhat relaxed.
Let $\mathcal{K} = \{ k_{i} \in \mathbb{N} \mid 0 < k_{0} < ... < k_{|\mathcal{K}|} \}$ for some $|\mathcal{K}| < \infty$, be the set from which the researcher selects the tuning parameter. This set is allowed to change with $n$. Let
We assume $\mathcal{K}$ to be such that $\mathbf{P}(\mathcal{I}(P_{n},\mathbf{P}) \ne \{ \emptyset \}) = 1$; this assumption is quite mild since $k \mapsto \tilde{V}_{k}(P_{n})$ is nondecreasing and $ \limsup_{k \rightarrow \infty} B_{k}(\mathbf{P}) = 0$. Finally, we define the ideal tuning parameter as \footnote{If there are several minimizer; we take the largest one.}
The next lemma establishes that the (infeasible) estimator $(\nu_{k^{I}(P_{n},\mathbf{P})}(P_{n}) )_{n}$ satisfies the concentration property at $\nu(\mathbf{P})$ under $\varpi$, with rate $(\tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n}) )_{n}$ and bound $u \mapsto g_{0}(0.5u/\mathbb{V})$.
We now construct the \textquotedblleft feasible" tuning parameter. For any $s \in \mathbb{R}_+$
be the test set. For any $s>0$, the feasible tuning parameter is given by
The test set is random and known to the researcher since it depends only on known quantities. The motivation for its construction is as follows. By the triangle inequality, the fact that $k' \geq k$ and Proposition (ref), it follows that, with probability higher than $1-g_{0}(s)$, $\varpi (\nu_{k}(P_{n}) , \nu_{k'}(P_{n})) \precsim s 2 \{ \tilde{V}_{k'}(P_{n}) + \sqrt{B_{k}(\mathbf{P})} \} $. Hence, the “extra" restriction imposed by the test set is to focus, roughly speaking, attention to $k \in \mathcal{K}$ for which the “(squared) bias" term is dominated by the “variance" term; i.e., $B_{k}(\mathbf{P}) \precsim \tilde{V}^{2}_{k}(P_{n}) \leq \tilde{V}^{2}_{k'}(P_{n}) $. Since $\mathcal{I}(P_{n},\mathbf{P})$ imposes a similar restriction; one would expect that minimizing the variance over the test set would yield similar results to those given by the ideal tuning parameter. This is the idea behind the following theorem.
The theorem essentially states that the concentration rate of the estimator $\nu_{k^{F}_{s}(P_{n})}(P_{n})$ is of the same order as the one corresponding to the ideal tuning parameter. That is, by minimizing the \textquotedblleft variance term" over the test set, one can construct an estimator which performance --- measured by the concentration rate --- is no worse (up to constants) than the one obtained by the ideal choice which uses knowledge of the “bias" term to balance the “bias" and “variance" terms of the concentration rate.
On the $|\mathcal{K}|$ factor. The concentration function in the theorem is scaled by the complexity of the set $\mathcal{K}$, $|\mathcal{K}|$. Although it might not be surprising that the complexity of the set $\mathcal{K}$ affects the concentration bound, it still deserves some discussion, especially since it played no role in Lemma (ref).
The reason for this scaling arises because we need to ensure that the set $\cap_{k \in \mathcal{K}} E_{n}(u,k) \equiv \cap_{k \in \mathcal{K}} \left\{ \omega \in \Omega \mid \varpi (\nu_{k}(P_{n}) , \nu(\mathbf{P}) ) < u \left( \tilde{V}_{k}(P_{n}) + \sqrt{B_{k}(\mathbf{P})} \right) \right\}$ has high probability. Proposition (ref) states that for each $k$, $\mathbf{P}(E_{n}(u,k)) \geq 1 - g_{0}(u)$, so by means of a crude union bound we obtain a lower bound $1-|\mathcal{K}| g_{0}(u)$ for $\mathbf{P}(\cap_{k \in \mathcal{K}} E_{n}(u,k))$; we refer the reader to the Online Appendix (ref) for a formalization of this discussion.\footnote{In PereverzevSchock2006 it is (implicitly) assumed that the sets $E_{n}(u,k)$ occur with probability one; thus in their results the complexity of $\mathcal{K}$ plays no role.}
Implications of the Theorem. The theorem provides “$\varpi$-confidence-bands" in the sense that, for a given confidence level $\alpha \in (0,1)$, by choosing $s$ such that $2 | \mathcal{K} | g_{0}(s) = \alpha$, the theorem implies that
As the next proposition shows, another implication of the Theorem is that our choice of tuning parameter yields a consistent estimator --- even allowing for the complexity of $\mathcal{K}$ to grow with the sample size --- and moreover, its rate of convergence coincides with that of the ideal estimator.
So consistency of our estimator with the feasible tuning parameter is obtained provided that $s_{n} \tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n})= o_{\mathbf{P}}(1)$.\footnote{For the case where $|\mathcal{K}|$ is uniformly bounded, it suffices to impose that $\max_{k \in \mathcal{K}} \tilde{V}_{k}(P_{n}) = o_{\mathbf{P}}(1)$. This condition is rather mild and rules pathological cases where $k \mapsto \tilde{V}_{k}(P_{n})$ behaves like a \textquotedblleft traveling wave”. E.g. $\tilde{V}_{k}(P_{n}) = 1\{ k \geq K(n) \}$ for a diverging $K(.)$. In this case, it could happen that $k^{I}(P_{n},\mathbf{P}) = K(n)$; hence $\tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n}) = 1$ and thus we cannot establish consistency. If the cardinality of $\mathcal{K}$ grows the condition states that is cannot grow too fast relative to $1/\max_{k} \tilde{V}_{k}(P_{n})$.}
Heuristics. The proof is rather straightforward, albeit somewhat lengthy. The idea is to bound $\varpi (\nu_{k^{F}_{s}(P_{n})}(P_{n}) , \nu(\mathbf{P}) ) $ by bounding $\varpi (\nu_{k^{F}_{s}(P_{n})}(P_{n}) , \nu_{k^{I}(P_{n},\mathbf{P})}(P_{n}) ) $ and $\varpi (\nu_{k^{I}(P_{n},\mathbf{P})}(P_{n}) , \nu(\mathbf{P}) ) $. The latter term was bounded in Lemma (ref), so it only remains to show that the former term is (up to constants) of the same order. To do this, the key step is that, with high probability, $k^{I}(P_{n},\mathbf{P})$ belongs to the test set. Thus, by construction of $k^{F}_{s}(P_{n})$, $\tilde{V}_{k^{F}_{s}(P_{n})}(P_{n}) \leq \tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n})$. Since $k \mapsto \tilde{V}_{k}(P_{n}) $ is non-decreasing, it must hold that $k^{I}(P_{n},\mathbf{P}) \geq k^{F}_{s}(P_{n})$. However, by construction of $k^{F}_{s}(P_{n})$ and the fact that $k^{I}(P_{n},\mathbf{P})$ belongs to the test set, it follows that $\varpi (\nu_{k^{F}_{s}(P_{n})}(P_{n}) , \nu_{k^{I}(P_{n},\mathbf{P})}(P_{n})) \precsim \tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n}) $ with high probability.
We illustrate how the choice of tuning parameter works in the HD-QR example.
We now present numerical simulations to further illustrate the role of the effective number of observations and also the behavior of our choice of tuning parameters.
We study the following simple regression model with $m$-dependent data: $Y_{i} = \sum_{j=1}^{d} \theta_{\ast}(j) X_{j,i} + 0.5 U_{i}$ for $i=1,....,n$ and $\theta_{\ast}(j) = j^{-0.5}$ for $j=1,...,d$. The data $(X_{i},U_{i})_{i=1}^{n}$ is constructed as follows: Let $q=n/m$, $(X_{1,j})_{j=1}^{q}$ and $(U_{1,j})_{j=1}^{q}$ be independent standard Gaussian, and $(X_{2,i})_{i=1}^{n}$ and $(U_{2,i})_{i=1}^{n}$ be independent standard Gaussian, finally
for all $j=1,...,q$ and $l=1,...,m$. It is clear that $(Y_{i},X_{i})_{i=1}^{n}$ are $m$-block i.i.d., and, as pointed in Example (ref), $m$-dependent.
Let $(z,\theta) \mapsto \phi (z,\theta) = \rho_{j}(y - \sum_{l=1}^{d} \theta(l) x_{l})$ for $j=1,2$, with $t \mapsto \rho_{1}(t) = 0.5|t|$ and $t \mapsto \rho_{2}(t) = t^{2}$. We want to assess how sharp our upper bounds are and, in particular, assess the role of the effective number of observations. To this end, we abstract from other features of the setup and set $d = 3$ and $\lambda_{k} = 0$ for all $k \in \mathbb{N}$.
We perform $MC=2,000$ Monte Carlo repetitions. For each $(n,m)$, and $j=1,2$ (indexing the type of regression), we report the expectation of $ \delta_{\mathbf{P}} (\nu_{k}(P_{n}),\theta_{0}) $,
For this case, $\varrho_{n,k} = \mathbb{C}_{j} \sqrt{m} \sqrt{\frac{3}{n}} $ where $(\mathbb{C}_{j})_{j=1,2}$ are universal constants. Thus Proposition (ref) predicts that $\mu_{j}(n,m) \leq \mathbb{C}_{j} \sqrt{m} \sqrt{\frac{3}{n}} \left( \mathbb{C}'_{j} + \mathbb{G}_{0} \log \left( \sqrt{\frac{n}{3 m}} \right) \right) $, for some universal constant $\mathbb{C}'_{j}$. Essentially, our theory predicts an upper bound for the growth of $m \mapsto \mu_{j}(n,m)$ of the order of $\sqrt{m}$.
In Tables (ref) and (ref) we report $\mu_{1}(n,m)$ and $\mu_{2}(n,m)$ resp. for different values of $(n,m)$.\footnote{Because each row has a different value of $n$, the values of $m$ also differ. For all $n$ except $n=1000$, the right most number in each row corresponds to the case of $n(\beta) = 25$. For $n=1000$ we add the case $n(\beta) = 10$ for further comparison.} In the tables, “actual" stands for the actual value of $\mu_{j}(n,m)$ stemming from the numerical simulations. The “predicted" value for any $m>1$, is constructed as $\sqrt{m} \times \mu_{j}(n,1)$ for each $j=1,2$. The discrepancy between the “predicted" and the “actual" value gauges how sharp our bound is and ultimately, how good of a description of the estimator our theory provides. For all cases, even for fairly small sample sizes (e.g., $n=50$ or $n=100$), the “predicted" value seems to be a remarkably good approximation of the actual quantity, for both mean and median regressions; except perhaps the case $(n,m)=(1000,100)$ for the median regression case.\footnote{In most $(n,m)$ cases, the predicted value is below the actual value, but in these cases the discrepancy is very small and attributed to numerical randomness in the Monte Carlo simulations.}
For comparison, the \textquotedblleft standard" asymptotic results predict that $\mu_{j}(n,m)$ has a convergence rate of order $n^{-1}$, independently of the value of $m$. Tables (ref) and (ref) show that our results provide a sharper description of the behavior of the estimator. Moreover, for small sample sizes such as $n=50$, one might feel that asymptotic results are not even applicable.
Overall, the numerical simulations seem to suggest that our upper bound provides an accurate description of the size of $\mu$ for both models. Notably, it does so for values of $n$ which one could find to be too low to apply asymptotic results.
In order to study the performance of our method for choosing the tuning parameter, we study the following non-parametric regression model with $m$-dependent data: $Y_{i} = \theta_{\ast}(W_{i}) + 0.5 U_{i}$ for $i=1,....,n$ and $\theta_{\ast}(w) = 2 \cos(w) + w$ for any $w \in [-6,6]$. The sequence $(W_{i})_{i=1}^{n}$ is such that $W_{i} = 6 \frac{X_{i}}{1 + |X_{i}|} $ and the data $(X_{i},U_{i})_{i=1}^{n}$ is constructed in the same way as in the previous design (except that the $X$'s are now in $\mathbb{R}$).
We consider a sieve-based estimator with $\Theta_{k} = \{ f \colon f = \sum_{j=1}^{k} \theta_{j} q_{j},~\theta_{j} \in \mathbb{R},~\forall j =1,...,k \}$ for two distinct basis functions $(q_{j})_{j}$: (a) A polynomial basis and (b) a P-Spline basis with 3 equally spaced knots. The second case is of particular interest because assumption (ref)(ii) may not hold here. We set $\lambda_{k} = 0$, so the regularization parameter is $k \in \mathcal{K}$ where $\mathcal{K} = \{ 3,...,8\}$. We consider $MC=2,500$.
It is easy to show that in this case, $\varpi$ is induced by the $L^{2}(\mathbf{P})$ norm. Therefore, the ideal tuning parameter, $k^{I}_{n}$, is proportional to the solution of $\sqrt{\frac{k}{n/m}} = || \sum_{j=1}^{k} \nu_{k}(j) q_{j} - \theta_{\ast}||_{L^{2}(\mathbf{P})}$ where $(\nu_{k}(1),...,\nu_{k}(k))^{T} = \left( E[(q^{k}(W)) (q^{k}(W))^{T}] \right)^{-1} E[q^{k}(W) \theta_{\ast}(W)]$ with $q^{k}(w) = (q_{1}(w),...,q_{k}(w))^{T}$. The feasible tuning parameter, $k^{F}_{n}$, is chosen as the minimal $k$ inside
where $s_{n}$ was chosen as $0.5 \log(n/m)$ and for any $k$ $\hat{\theta}_{k} \equiv \left( Q_{k} Q^{T}_{k} \right)^{-1} \sum_{i=1}^{n} q^{k}(W_{i}) Y_{i}$ with $Q_{k} = (q^{k}(W_{1}),...,q^{k}(W_{n}))$, and $\bar{\hat{\theta}}_{k,k'} = (\hat{\theta}_{k},0,...,0) \in \mathbb{R}^{k'} $, finally $M_{k} = E[(q^{k}(W)) (q^{k}(W))^{T}]$. Proposition (ref) states that $r_{n} \equiv \frac{\sqrt{n} || (\hat{\theta}_{k^{F}_{n}})^{T} q^{k^{F}_{n}} - \theta_{\ast}||_{L^{2}(\mathbf{P})} }{\sqrt{m k^{I}_{n}} s_{n} }$ is bounded in probability; so in order to gauge the behavior of $r_{n}$ we report its MC quantiles for different values of $n$.
Tables (ref) and (ref) presents the results for P-splines and Polynomial basis, resp.. Even though there is a positive trend for the quantiles in Polynomial case, the values are well below $6$, the scaling constant in Theorem (ref). For all columns except the last one, we set $m=1$; for the last column we set $m=6$ so the effective number of observations is $500$. The results show that with $m=6$ the behavior is closer to $n=500$ than it is to $n=3,000$ (as would have been predicted by asymptotic theory). Finally, even in cases where ideal and feasible tuning parameters differ, the corresponding “variance" terms are close. Interestingly, for P-splines the ideal and feasible choices happen to coincide (except for $n=100$); for this last case, $k^{I}_{n} < k^{F}_{n}$.