The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
111,041 characters
On the Non-Asymptotic Properties of Regularized M-estimators
\maketitle
\begin{abstract}
We propose a general framework for regularization in M-estimation problems under time dependent (absolutely regular-mixing) data which encompasses many of the existing estimators. We derive non-asymptotic concentration bounds for the regularized M-estimator. Our results exhibit a variance-bias trade-off, with the variance term being governed by a novel measure of the complexity of the parameter set. We also show that the mixing structure affect the variance term by scaling the number of observations; depending on the decay rate of the mixing coefficients, this scaling can even affect the asymptotic behavior. Finally, we propose a data-driven method for choosing the tuning parameters of the regularized estimator which yield the same (up to constants) concentration bound as one that optimally balances the (squared) bias and variance terms. We illustrate the results with several canonical examples.
\end{abstract}
\section{Introduction}
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 \cite{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. \cite{Grenander1981}, \cite{GemanHwang1982}, \cite{GallantNychka1987} and \cite{shen1994}), Kernel-based estimators (e.g. Nadaraya and Watson estimators) and penalized estimators (e.g. \cite{shen1997}, and \cite{EggLaRic2001} and references therein) --- which include LASSO and Ridge regressions in high-dimensional models (e.g. \cite{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 \cite{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. \cite{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 \emph{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 (\cite{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 (\cite{talagrand2005},\cite{talagrand2014}) our measure of complexity is bounded above by the one based on metric-entropies (\cite{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 \cite{2015arXivDemian}, we show that our measure is also a lower bound for bracketing-entropies (\cite{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 \emph{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. \cite{CS-1998} and \cite{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 \emph{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. \cite{DMR1995} and \cite{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 (\cite{Lepskii1991}) and is an adaptation to M-estimation of the one first proposed by \cite{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 \cite{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 (\cite{shao1997},\cite{arlot2010}) both of which can be delicate in general frameworks with time-dependent data.
\medskip
\textbf{Related Literature.} Conceptually our general setup is based on the excellent reviews by \cite{Bickel-Li-TEST06} and \cite{massart2007}. The construction of our estimator is based on \cite{CP-2012} PSMD estimator (adapted to M-estimation) and \cite{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 \cite{VdG-Buhlmann11} book for a thorough review of the literature and an extensive treatment of LASSO (\cite{Tibshirani1996}) and similar models. In econometrics, we refer the reader to \cite{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 \cite{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 \cite{Chatterjee2013} about ``assumptionless" consistency of the LASSO.
Second, we contribute to the vast literature of non-/semi-parametric models. We refer the reader to \cite{Powell1994} and \cite{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. \cite{massart2007} offers a nice review of non-asymptotic results but for i.i.d data. From these papers, closest to ours are \cite{CS-1998} and \cite{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. \cite{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 \cite{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 \cite{vandeGeer2013}.
The idea that the notion of distance used to construct the complexity measure depends on the mixing structure was first pointed out by \cite{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{sec:discussion} 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 \cite{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 \cite{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 \cite{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. \cite{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 \cite{massart2007} for a review of model selection in this setup.
\medskip
\textbf{Roadmap.} Section \ref{sec:examples} presents some illustrative examples. Section \ref{sec:prem} defines the data structure, the M-estimation model (subsection \ref{sec:model}) and the regularized M-estimator (subsection \ref{sec:reg}). Section \ref{sec:main} 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{sec:MoC-bound}). Section \ref{sec:choice} proposes the method for choosing the tuning parameters. Section \ref{sec:simul} presents some numerical simulations. All proofs are gathered in the Appendix.
\medskip
\textbf{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 \}$.
\section{Illustrative Examples}
\label{sec:examples}
The following example presents a high-dimensional quantile regression (HD-QR) model. Quantile regression (\cite{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 (\cite{BelloniChern2011}, \cite{koenker2004quantile}, \cite{wang2012quantile}, \cite{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 \cite{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 \cite{CW1999} who studied a non-parametric version for dependent data; \cite{Wu2008} who studied kernel estimation of conditional quantiles for dependent data; and \cite{KoenkerXiao2006} who studied a parametric quantile auto-regression model.}
\medskip
\begin{example}[HD-QR] \label{exa:HD-QR}
Let $Y_{i} = X^{T}_{i}\theta_{\ast} + U_{i}$ with $E[1\{U_{i} \leq 0 \}|X_{i} ] = \tau $ for some $\tau \in (0,1)$ and $i \in \{1,...,n\}$, where $\theta_{\ast} \in \Theta = \mathbb{R}^{d}$ and $d \in \mathbb{N}$ is fixed (albeit might be much greater than $n$). The regressors $X$ could include previous lags of $Y$ as well as other (lagged) variables.
We assume that $F(\cdot|X)$ (the true conditional cdf) admits a continuously differentiable pdf (with respect to Lebesgue) $f(\cdot|X)$,
and $E[|X|] <\infty$, $E[|Y|] <\infty$, $e_{min}(E[XX^{T}])>0$ and $\mathbb{E}_{\pi_{0}} \equiv E[|e_{max}(XX^{T})|^{\pi_{0}}] < \infty$ for some $\pi_{0} > 2$.\footnote{$e_{max}(A)$ and $e_{min}(A)$ are the maximum and minimum eigenvalue of matrix $A$.}
The parameter of interest can be viewed as solving $\theta_{\ast} = \arg\min_{\theta \in \Theta} E_{\mathbf{P}}[\phi(Z,\theta)]$ with $Z=(X,Y)$ and \emph{loss function} $(z,\theta) \mapsto \phi(z,\theta) \equiv (y-x^{T}\theta)(\tau - 1\{ y - x^{T}\theta \leq 0 \})$; now and throughout the paper, $\mathbf{P}$ denotes the true probability distribution. In this model, since $d$ could be much larger than $n$, the standard plug-in estimator may fail to be well-defined and thus the problem needs to be regularized. A widely used regularized M-estimator is given by
\begin{align*}
\nu_{k}(P_{n}) = \arg\min_{\theta \in \Theta} E_{P_{n}}[\phi(Z,\theta)] + \lambda_{k} Pen(\theta)
\end{align*}
where $P_{n}$ is the empirical distribution, $n^{-1} \sum_{i=1}^{n} \delta_{Z_{i}}$; $\lambda_{k} \geq 0 $ is the \emph{tuning parameter}; and $Pen: \Theta \rightarrow \mathbb{R}_{+}$ is a \emph{penalization function}. We present two widely used examples of penalization function: The $\ell^{1}$-norm and the weighted $\ell^{2}$-norm.
\smallskip
\textbf{The $Pen=||.||_{\ell^{1}}$ Case.} By applying our result to this setting, we obtain the following \emph{concentration property} (proved in Proposition \ref{pro:HD-QR-L1-new} in the Appendix \ref{app:examples}): For any $(k,n)$ and any $u >0$, with probability higher than $1-\mathbb{G}_{0}/u$
\begin{align} \label{eqn:HD-QR-l1-CR}
||\sqrt{W_{k}}(\nu_{k}(P_{n}) - \theta_{\ast}) ||_{\ell^{2}} \leq & u \mathbb{K} \max\{ 1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}}\} \\ \notag
& \times \left( \min \left\{ \sqrt{\frac{tr\{ W^{-1}_{k} \}}{n(\beta)}} , \left( \frac{\log (2 d)} {n(\beta)}\right)^{1/4} \sqrt{M_{n,k}/\lambda_{k}} \right\} + \sqrt{\lambda_{k}||\theta_{\ast}||_{\ell^{1}}} \right),
\end{align}
where $M_{n,k} = E_{P_{n}}[\phi(Z,\theta_{\ast})] + \lambda_{k} ||\theta_{\ast}||_{\ell^{1}}$; $\mathbb{G}_{0}$ and $\mathbb{K}$ are universal constants that do not depend on $\theta_{\ast}$ or $\mathbf{P}$ and are specified below; and $W_{k} \equiv E[\underline{d}_{k}(X) XX^{T}]$ with $ \underline{d}_{k}(X) \equiv \inf_{\theta \in \{\theta \colon ||\theta||_{\ell^{1}} \leq \max\{M_{n,k},E[M_{n,k}]\}/\lambda_{k} \}} f(X^{T}\theta \mid X) $. Finally, the quantity $n(\beta) \in \mathbb{N}$ is the so-called \emph{effective number of observations} and is one of the key quantities in our results; it is defined in Theorem \ref{thm:effe-n} below and discussed further in Section \ref{sec:effe-n}. Informally, the effective number of observations summarizes the effect of the $\beta$-mixing structure on the concentration property of the regularized estimator. For instance, for i.i.d. data, $n(\beta) = n$, but for richer dependence structures, it follows that $n(\beta) < n$; moreover for $\beta$-mixing coefficients decaying ``slowly" to zero, it follows that $n(\beta)/n \rightarrow 0$.\footnote{The exact characterization of ``slow" decay is presented in Section \ref{sec:effe-n}.}
The notion of distance we use, $ ||\sqrt{W_{k}} (\cdot) ||_{\ell^{2}}$, is akin to the MSE, $||\sqrt{E[XX^{T}]}(\cdot) ||_{\ell^{2}}$, which is routinely used in high-dimensional linear regression models. The discrepancy --- the term $\underline{d}_{k}$ --- arises because for quantile regression the loss function $\phi$ is different to the quadratic one. We thus view our notion of distance as a natural generalization to the one typically used in high-dimensional \emph{linear} regression models.
In expression \ref{eqn:HD-QR-l1-CR}, the right hand side term inside the parenthesis consists of the sum of a ``$\sqrt{variance}$" and ``bias" term. The latter term is quite intuitive and vanishes as $\lambda_{k} \rightarrow 0$. We now present some remarks for the, more involved, ``$\sqrt{variance}$" term.
First consider the case where $d << n(\beta)$. In this case no regularization is needed so we set $\lambda_{k}=0$, and the LHS of expression \ref{eqn:HD-QR-l1-CR} becomes $u \mathbb{K} \max\{ 1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}}\} \sqrt{tr\{ W^{-1}_{k} \}/n(\beta)}$. Our results deliver the standard bound for finite (low) dimensional regression problems with $n(\beta)$ playing the role of $n$.\footnote{For comparison, in the linear regression case, the term $\sqrt{tr\{ W^{-1}_{k} \}/n(\beta)}$, becomes the standard $\sqrt{tr\{ E[XX^{T}]^{-1} \}/n(\beta)}$.
} As pointed out before, for i.i.d. data $n(\beta)=n$, but for other dependence structures, $n(\beta)<n$ and thus the concentration rates are slower than that for the i.i.d. case. This remark illustrates the role that the effective number of observations plays in summarizing the effect of dependence structure on the concentration rates.
Second, for the $d >> n(\beta)$ case, the concentration property reduces to: with probability higher than $1-\mathbb{G}_{0}/u$,
\begin{align} \notag
||\sqrt{W_{k}}(\nu_{k}(P_{n}) - \theta_{\ast}) ||_{\ell^{2}} \leq & u \mathbb{K} \max\{ 1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}}\} \\ \label{eqn:HD-QR-LASSO-1}
& \times \left( \left( \frac{\log (2 d)} {n(\beta)}\right)^{1/4} \sqrt{M_{n,k}/\lambda_{k}} + \sqrt{\lambda_{k}||\theta_{\ast}||_{\ell^{1}}} \right).
\end{align}
\begin{remark}\label{rem:rate-LASSO}
We did not impose that $\Theta \subseteq \{ \theta \mid ||\theta||_{\ell^{1}} \leq K \}$ for some $K>0$. By Remark \ref{rem:Gamma-bound} in the Online Appendix \ref{app:sup-Gau}, imposing this additional condition --- which is quite standard, see e.g. \cite{Chatterjee2013}, \cite{VdG-Buhlmann11} and references therein --- delivers:
\begin{align*}
||\sqrt{W_{k}} ( \nu_{k}(P_{n}) - \theta_{\ast}) ||_{\ell^{2}} \leq u 2\mathbb{K} \max\{1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}} \} \left\{ \left( \frac{\log (2 d) }{n(\beta)} \right)^{1/4} \sqrt{K} \right\}
\end{align*}
with probability higher than $1-\mathbb{G}_{0}/u$, and for $\lambda_{k} \leq \left( \frac{\log (2 d) }{n(\beta)} \right)^{1/2}$.
$\triangle$
\end{remark}
For the case of i.i.d data, the result in Remark \ref{rem:rate-LASSO} agrees (possibly up to constants) with those obtained by \cite{Chatterjee2013}, \cite{Bartlett-Mendelson-Neeman-2012} and \cite{VdG-Buhlmann11} among others, for the Linear Regression case with $\ell^{1}$ penalty. The reason for the power $1/4$ in $\log (2d)/n(\beta)$ (as opposed to, say, power of $1/2$) follows from the fact that neither sparsity nor compatibility-type conditions is assumed. In fact, a notable feature of these results is that were obtained under almost no assumptions. If $d = o (\exp\{ n(\beta) \})$, display \ref{eqn:HD-QR-LASSO-1} and Remark \ref{rem:rate-LASSO} extend the ``assumptionless" (nomenclature in \cite{Chatterjee2013}) consistency results in the aforementioned papers to a wider class of regression models and more general data structure. In particular, we allow for Quantile regression models and general $\beta$-mixing processes.
Moreover, as opposed to \cite{Chatterjee2013}, our results do not impose Gaussianity of the residual of the regression. The reason for this stems from our complexity measure, defined in Definition \ref{def:MoC}. By exploiting the results by \cite{talagrand2014}, Proposition \ref{pro:M-rate1} in Section \ref{sec:Dudley-bound} shows that, essentially, our measure of complexity is bounded \emph{above} by the expectation of suprema of Gaussian processes; i.e., $E \left[ \sup_{ \theta \in \{ \theta \in \Theta \colon ||\theta||_{\ell^{1}} \leq M_{n,k}/\lambda_{k} \}} |\sum_{j=1}^{d} \zeta_{j} \theta_{j}| \right]$ with $\zeta_{j} \sim N(0,1)$. So, by applying H\"{o}lder inequality one obtains the bound $E[\max_{1 \leq k \leq d} |\zeta_{k}| ] \frac{M_{n,k}}{\lambda_{k}} \leq \sqrt{\log (2 d)} \frac{M_{n,k}}{\lambda_{k}}$ (see Lemma \ref{lem:M-rate1b} and also \cite{Chatterjee-Jafarov-2015} Lemma A.2), which is precisely the term in the ``variance term" in expression \ref{eqn:HD-QR-LASSO-1}. This point illustrates the usefulness of our measure of complexity, vis-a-vis, say, Dudley's entropy. A final comment about the set $\{ \theta \in \Theta \colon ||\theta||_{\ell^{1}} \leq M_{n,k}/\lambda_{k} \}$ is in order. Since our estimator minimizes the regularized criterion function it belongs to $\{ \theta \in \Theta \colon ||\theta||_{\ell^{1}} \leq M_{n,k}/\lambda_{k} \}$. Thus, this set, rather than $\Theta$ is the relevant parameter set.
\smallskip
\textbf{The $Pen = ||\cdot||^{2}_{\ell^{2}(p)}$ Case.} We now apply our results to the case where $Pen=||\cdot||^{2}_{\ell^{2}(p)}$ with $||.||^{2}_{\ell^{2}(p)} = \sum_{j=1}^{d} |\theta_{j}|^{2} p_{j}$ and $p_{j} = j^{m}$ for $m \geq 0$. The point of this section is to illustrate how the choice of penalty function affects the measure of complexity of the parameter set and the bias term (but, essentially, nothing else).
For $m>1$, our theory delivers the following concentration property (proved in Proposition \ref{pro:HD-QR-L2m-CR} in Appendix \ref{app:examples}): For any $(n,k)$ and any $u>0$,
\begin{align*}
& || \sqrt{W_{k}}(\nu_{k}(P_{n}) - \theta_{\ast}) ||_{\ell^{2}} \leq u \mathbb{K} \max\{1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}} \} \left( \sqrt{ \lambda_{k} ||\theta_{\ast}||^{2}_{\ell^{2}(p)} } + \sqrt{ \frac{ \min \{ \lambda^{-1/m}_{k} , d \} } {n(\beta)} \mathbb{B}_{k} } \right)
\end{align*}
with probability higher than $1-\mathbb{G}_{0}/u$, where $\mathbb{B}_{k} \equiv \left( \left( \frac{e_{min}(W_{k})}{2(m-1)} \right)^{1/m} + 1 \right) \frac{2}{ e_{min}(W_{k})}$.
If $d << n(\beta)$, then the ``variance" term can be majorized by $\sqrt{\mathbb{B}_{k}} \sqrt{ \frac{ d }{n(\beta)}} $. But if $d>>n(\beta)$, there exists a possibly tighter upper bound given by $\sqrt{\mathbb{B}_{k} \frac{ \lambda_{k}^{-1/m}}{n(\beta)}}$. By choosing $\lambda_{k}$ to balance the ``variance" and ``(squared) bias" terms, it follows that
\begin{align*}
||\sqrt{W_{k}}(\nu_{k}(P_{n}) - \theta_{\ast})||_{\ell^{2}} \leq u \mathbb{K} \max\{1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}} \} n(\beta)^{-\frac{m}{2(m+1)}} ||\theta_{\ast}||^{\frac{1}{m+1}}_{\ell^{2}(p)} \mathbb{B}_{k}^{\frac{m}{m+1}} ,
\end{align*}
and $\lambda_{k} = (||\theta_{\ast}||^{2}_{\ell^{2}(p)} \mathbb{B}_{k}/n(\beta))^{m/(m+1)}$. The rate, $n^{-0.5m/(m+1)}$, coincides (up to constants) with the min-max rate obtained for a normal means model over $\ell^{2}(p)$-balls; e.g. \cite{Wasserman2006} Ch. 7. Unfortunately, choosing $\lambda_{k}$ to balance the variance-bias trade-off is typically infeasible since the bias term depends on unknown quantities such as $\theta_{\ast}$. In section \ref{sec:choice} we address this issue by proposing a data-driven method that achieves the same concentration property (up to constants).
The same remarks about ``assumptionless" consistency in the $\ell^{1}$ case applies in this case, with the caveat that now the influence of $d$ in the ``variance term" is capped by $\lambda_{k}^{-1/m}$. Consequently, the concentration rate, $n(\beta)^{-\frac{m}{2(m+1)}}$, does not diverge as $d \rightarrow \infty$. Similar result holds for sequences $(p_{j})_{j}$ that diverges faster than $j^{m}$ for $m >1$, but the situation is different for $p_{j} = j^{m}$ with $m \in [0,1]$ as the next result illustrates for the case $m=0$ (proved in Proposition \ref{pro:HD-QR-L2m-CR}): For $\lambda_{k} \leq d/(2 tr\{ W_{k}^{-1} \}) $,
\begin{align*}
& || \sqrt{W_{k}}(\nu_{k}(P_{n}) - \theta_{\ast}) ||_{\ell^{2}} \leq u \mathbb{K} \max\{1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}} \} \left( \sqrt{ \lambda_{k} ||\theta_{\ast}||^{2}_{\ell^{2}(p)} } + \sqrt{ \frac{ 2 tr\{ W_{k}^{-1} \} } {n(\beta)} } \right).
\end{align*}
with probability higher than $1-\mathbb{G}_{0}/u$. $\triangle$
\end{example}
Other examples, such as Non-parametric regression also falls into our framework.
\begin{example}[Non-Parametric Linear Regression]\label{exa:NP-LR1}
Let $Y_{i} = \theta_{\ast}(X_{i}) + U_{i}$ with $E_{\mathbf{P}}[U_{i}|X_{i} ] = 0 $ for $i \in \{1,..,n\}$ where $\theta_{\ast} \in \Theta $ and $\Theta$ is some convex subset of $L^{2} = L^{2}(Lebesgue)$. Our results allow for the regressors to contain lagged values of $Y$; e.g. \cite{CS-1998} for more examples. In this case, $Z=(X,Y)$ and the loss function $(z,\theta) \mapsto \phi(z,\theta) = (y - \theta(x))^{2}$, and $\theta_{\ast} = \arg\min_{\theta \in \Theta} E_{\mathbf{P}}[\phi(Z,\theta)]$.
It is well-known that the estimation problem is ill-posed and needs to be regularized; see \cite{Bickel-Li-TEST06}. A common regularized estimator is given by $\nu_{k}(P_{n}) = \tau_{k}(P_{n})^{T}\psi(\cdot )$, where
\begin{align*}
\tau_{k}(P_{n}) = \arg\min_{\tau \in \mathbb{R}^{k}} n^{-1} \sum_{i=1}^{n} (Y_{i}- \tau^{T} \psi(X_{i}))^{2} + \lambda_{k} Pen(\tau)
\end{align*}
and $\psi = (\psi_{1},...,\psi_{k})^{T}$ being some basis functions for $L^{2}$ and $Pen$ is a convex.\footnote{Due to space constraints, we refer the reader to the Arxiv version \cite{2015arXivDemian} for a full-treatment of this example.} $\triangle$
\end{example}
The following example is designed to provide an overview of the main results derived below, in Section \ref{sec:main}. 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.
\begin{example}[A Simple Linear Regression Model]\label{exa:OLS-q}
Consider the linear regression model $Y_{i} = x^{T}_{i} \theta_{\ast} + U_{i}$ for $i\in \{ 1,...,n\}$, $x_{i} \in \mathbb{R}^{d}$ non-random with $n^{-1} \sum_{i=1}^{n} x_{i} x^{T}_{i} = I$, $ d < n$ and $\max_{i} ||x_{i}||_{\ell^{2}} \leq K_{0} \sqrt{d} $, and $||\theta_{\ast}||_{\ell^{2}} < K_{2}$; $(U_{i})_{i}$ with $E[U]=0$ and $E[|U_{i}|^{2}] < \infty$. Finally, we assume that $(U_{i})_{i}$ is $\mu_{0}$-block independent, i.e., for any $j,j' \in \{ 0,...,n/\mu_{0}-1\}$, $(U_{i})_{i=j\mu_{0}+1}^{j\mu_{0}+\mu_{0}} $ and $(U_{i})_{i=j'\mu_{0}+1}^{j'\mu_{0}+\mu_{0}} $ are independent.\footnote{For simplicity, we set $\mu_{0}$ such that $n/\mu_{0} -1 \in \mathbb{N}$. Also, in the Online Appendix \ref{app:OLS-q-MA} we develop the MA($\mu_{0}$) case (another $\mu_{0}$-dependent process) and argue that the results remain the same.}
In this case $\nu(P_{n}) = n^{-1} \sum_{i=1}^{n} x_{i} Y_{i} $.
The natural notion of distance for studying concentration properties is the $\ell^{2}$ norm,
Therefore, obtaining concentration results in this problem, boils down to finding concentration results for $||\nu(P_{n}) - \theta_{\ast} ||_{\ell^{2}} = || n^{-1} \sum_{i=1}^{n} x_{i} U_{i} ||_{\ell^{2}}$. Straightforward calculations imply that, for any $u>0$,
\begin{align}\label{eqn:OLS-q}
\mathbf{P} \left( ||\nu(P_{n}) - \theta_{\ast} ||_{\ell^{2}} \geq \sqrt{d} u \right) \leq \sum_{1 \leq l \leq d }\mathbf{P} \left( | n^{-1} \sum_{i=1}^{n} x_{i,l} U_{i} | \geq u \right).
\end{align}
The previous display suggests that it suffices to study the concentration properties of $\left| n^{-1} \sum_{i=1}^{n} x_{i,l} U_{i} \right|$ for any $l=1,...,d$. In our general approach it is also the case that for obtaining concentration properties we need to bound an average, namely a centered version of the (regularized) criterion function defined in \ref{def:reg}. Due to the level of generality, however, we cannot exploit closed form solution of the estimator; as a consequence, we need to control \emph{uniformly} the centered (regularized) criterion function (see Theorem \ref{thm:gbrack} in Section \ref{sec:heur} below). It is here that the complexity of the parameter set arises as an important element in our results. In Section \ref{sec:main} we define the \emph{Measure of Complexity} and in Section \ref{sec:MoC-bound} we provide further discussions and results.\footnote{In this simple example, the scaling $\sqrt{d}$ can be viewed as a measure of the complexity of the parameter space.}
We can cast $|n^{-1} \sum_{i=1}^{n} x_{i,l} U_{i} |$ as $|n^{-1} \sqrt{\mu_{0}} \sum_{j=0}^{J} \varDelta_{j,l} |$ with $ \varDelta_{j,l} =\mu_{0}^{-1/2}\sum_{i=j\mu_{0}+1}^{j\mu_{0}+\mu_{0}} x_{i,l} U_{i} $ and $J=n/\mu_{0}-1$. Since $(U_{i})_{i}$ is $\mu_{0}$-block independent, this decomposition implies that $(\varDelta_{j,l})_{j=0}^{J}$ are independent from each other. Using this fact, and decomposing $x_{l}U$ into bounded and unbounded parts, we invoke Bernstein (e.g. \cite{VdV-W1996} Lemma 2.2.9) and Markov inequalities to establish the following bound (proved in Proposition \ref{pro:OLS-q} in Appendix \ref{app:examples}):\footnote{The appendix also contains a discussion about alternative bounds.} For any $n \in \mathbb{N}$, $\mu_{0}\leq n$ and $l = 1,...,d$, for any $t \geq 1$
\begin{align*}
\mathbf{P} \left( |n^{-1} \sum_{i=1}^{n} x_{i,l} U_{i} | \geq t \sqrt{\frac{\mu_{0}}{n}} \right) \leq \frac{4}{t} \sqrt{E_{\mathbf{P}} \left[ \left(\frac{|\varDelta|}{\sqrt{\mu_{0}}} \right)^{2} \right]}.
\end{align*}
We observe that given the dependence structure, the correct order for the variance $E[(\varDelta_{l})^{2}]$ is in fact $\mu_{0}$, which also appears scaling the sample size. This observation illustrates, in a simplistic way, a key feature of our general results: The dependence structure affects the variance part in Bernstein inequality, and, in turn, the concentration rate of the estimator. So, in this case, the \emph{effective number of observations} is given by $n/\mu_{0}$.
This proposition and expression \ref{eqn:OLS-q}, imply that the estimator satisfies a concentration property with a \emph{concentration rate} given by $\sqrt{\frac{d}{n/\mu_{0}}}$ and a \emph{concentration bound} given by $u \mapsto \frac{4d}{u} \sqrt{E_{\mathbf{P}} \left[ \left(\frac{|\varDelta|}{\sqrt{\mu_{0}}} \right)^{2} \right]} $, i.e., for any $n$ and any $u \geq 1$,
\begin{align}\label{eqn:toy-concen}
\mathbf{P} \left( || \nu(P_{n}) - \theta_{\ast} ||_{\ell^{2}} \geq \sqrt{\frac{d}{n/\mu_{0}}} u \right) \leq \frac{4d}{u} \sqrt{E_{\mathbf{P}} \left[ \left(\frac{|\varDelta|}{\sqrt{\mu_{0}}} \right)^{2} \right]}.
\end{align}
At the core of the proof of our main theorem, Theorem \ref{thm:concen-main} below, there is also Bernstein inequality (see Lemma \ref{lem:bere} in Appendix \ref{app:gbrack}), and the idea of approximating the original data with independent blocks. There are, however, some key differences with the calculations leading to expression \ref{eqn:toy-concen}. First, in this simple application, the approximation by independent block is exact, but for more general dependent structures an approximation error arises (see Lemma \ref{lem:beta-bdd} in Appendix \ref{app:gbrack} and the discussion in Section \ref{sec:prem}). Second, while we also decompose $\phi$ into a ``bounded" part and a ``unbounded" part, we use more sophisticated arguments based on the results in \cite{DMR1995} that only use $L^{1}$-norm bounds (see Lemmas \ref{lem:decom-L} and \ref{lem:L1-bdd} in Appendix \ref{app:gbrack}). Both differences, however, only affect the constant in the concentration bound, not the concentration rate nor the geometric decay of the bound; in particular, our constant does not depend on $d$ (see Section \ref{sec:OLS-simple}). Finally, by abstracting from regularization, this example only illustrates the behavior of the ``variance" term in the concentration rate, ignoring the (more straightforward) ``bias" term (see Theorem \ref{thm:concen-main} for its role on the concentration rate). $\triangle$
\end{example}
\section{The Model and the Regularized Estimator}\label{sec:prem}
We now introduce the data structure, define the model and the regularized estimator.
\subsection{The Data}
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
\begin{align}
\boldsymbol{\beta}(\mathcal{U},\mathcal{V}) = \frac{1}{2} \sup \left\{ \sum_{i\in I,j \in J} \left| \mathbf{P}(U_{j} \cap V_{j} ) - \mathbf{P}(U_{j}) \mathbf{P}( V_{j} ) \right| \right\}
\end{align}
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 \cite{VolRoz1959} and \cite{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 \cite{YU1994}, in our proofs we use the following fact:\footnote{See also \cite{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 \cite{DL2002} pp. 144-152 and \cite{MP2002} Theorem 2.9 and references therein.
\subsection{The Model}
\label{sec:model}
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 \emph{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.}
\begin{align*}
Q(\theta_{\ast},\mathbf{P}) \leq Q(\theta,\mathbf{P}),~\forall \theta \in \Theta.
\end{align*}
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 \emph{M-estimation} problems, wherein $Q(\theta,P)=E_{P}[\phi(Z,\theta)]$ for a given \emph{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 \emph{parameter mapping} where
\begin{align}
\nu(P) = \arg\min_{\theta \in \Theta} Q(\theta,P),~\forall P \in \mathcal{P}
\end{align}
and $\nu(P)$ be the \emph{identified parameter (set)} at $P$. Clearly, if $\nu(\mathbf{P})$ is non-empty, $\theta_{\ast} \in \nu(\mathbf{P})$. In Appendix \ref{app:prelim} 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 \cite{Bickel-Li-TEST06} and references therein. Therefore, we need to regularize the problem.
\subsection{The Regularized Estimator and Concentration Properties}
\label{sec:reg}
Our goal is to study the concentration properties of the class of regularize M-estimators. We now define these concepts.
\medskip
\textbf{The Regularized M-estimator.} In the spirit of \cite{Bickel-Li-TEST06}, we define a \emph{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.
\begin{remark}
The regularized estimator needs only to be constructed at $P_{n}$, but is convenient to define it at $\mathbf{P}$ too, and interpret this quantity as the \textquotedblleft regularized parameter" (the precise definition is given below). Abusing terminology, we also call the sequence evaluated at $P_{n}$, $(\nu_{k}(P_{n}))_{n,k}$, a regularized estimator. $\triangle$
\end{remark}
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.
\begin{definition}
A \emph{regularization structure} is a tuple $\langle \{ \lambda_{k}, \Theta_{k}, \}_{k=1}^{\infty}, Pen \rangle $ such that \begin{enumerate}
\item (Penalization parameter) For each $k \in \mathbb{N}$, $\lambda_{k} > 0$ and $\lambda_{k} \downarrow 0$.
\item (Sieve Spaces) For each $k \in \mathbb{N}$, $\Theta_{k} \subseteq \mathbb{R}^{k}$ is non-empty, $\tau$-closed and $\cup_{k} \Theta_{k}$ is $\tau$-dense in $\Theta$.\footnote{$\tau$ is some topology, not necessarily equal to the one induced by $||.||_{\Theta}$.}
\item (Penalization function) $Pen : \Theta \rightarrow \mathbb{R}_{+}$ is $\tau$-continuous.
\end{enumerate}
\end{definition}
For each $k \in \mathbb{N}$, let $Q_{k} = Q + \lambda_{k} Pen$ be the \emph{Regularized Criterion Function}, and
\begin{definition}[Regularized Estimator]
\label{def:reg}
Given a regularization structure $\langle \{ \lambda_{k}, \Theta_{k}, \}_{k=1}^{\infty},Pen \rangle$ and a positive real-valued sequence $(\eta_{n})_{n}$ such that $\eta_{n} \rightarrow 0$, the \emph{regularized M-estimator} $(\nu_{k}(P_{n}))_{n,k}$ is given by
\begin{align*}
\nu_{k}(P_{n}) \in \Theta_{k}~and~Q_{k}(\nu_{k}(P_{n}),P_{n}) \leq \inf_{\theta \in \Theta_{k}} Q_{k}(\theta,P_{n}) + \eta_{n},~a.s.-\mathbf{P}
\end{align*}
for all $(n,k) \in \mathbb{N}^{2}$.
\end{definition}
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.
\medskip
\textbf{The Regularized Parameter Set.} For any $k \in \mathbb{N}$, let
\begin{align}
\nu_{k}(\mathbf{P}) = \arg\min_{\theta \in \Theta_{k}} Q_{k}(\theta,\mathbf{P})
\end{align}
be the \emph{regularized parameter (set)}.\footnote{Lemma \ref{lem:reg-min} in the Appendix \ref{app:prelim} 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})$.
\medskip
Finally, we formally define the concentration property for a regularized estimator.
\medskip
\textbf{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]$.
\begin{definition}[Concentration Property]\label{def:concen}
Given a parameter mapping $\nu$, a regularized estimator $\boldsymbol{\nu}$, $(\boldsymbol{r},g)$-concentrates around $\nu(\mathbf{P})$ under $d : \Theta^{2} \rightarrow \mathbb{R}_{+}$ if, for all $u>0$ and all $(n,k)$,
\begin{align}
\mathbf{P} \left( d(\nu_{k}(P_{n}),\nu(\mathbf{P})) \geq u r_{n,k}(\omega) \right) \leq g(u).
\end{align}
We call $\mathbf{r}$ the \emph{concentration rate} and $g$ the \emph{concentration bound}.
\end{definition}
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})$.
\section{Main results}
\label{sec:main}
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{sec:prem} 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{lem:bere} 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{app:domN} for a more thorough discussion.
\medskip
\textbf{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$.}
\begin{align*}
\delta_{\mathbf{P}}(\theta,\nu(\mathbf{P})) = \sqrt{ Q(\theta,\mathbf{P}) - Q(\nu(\mathbf{P}),\mathbf{P})}.
\end{align*}
As illustrated in Section \ref{sec:heur} 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{exa:HD-QR}, 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{pro:concen-w} below we generalize this idea and provide concentration results for general metrics.
For any $k \in \mathbb{N}$, let
\begin{align*}
B_{k}(\mathbf{P}) \equiv Q_{k}(\nu_{k}(\mathbf{P}) , \mathbf{P}) - Q(\nu(\mathbf{P}) , \mathbf{P})
\end{align*}
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{lem:Bias-incr} in Appendix \ref{app:prelim} provides conditions to ensure that the bias vanishes as $k$ diverges.}
\medskip
\textbf{Measure of Complexity.} The measure of complexity is inspired by Talagrand's Generic Chaining results (see \cite{talagrand1996}, \cite{talagrand2005} and \cite{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 \emph{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)|$.
\begin{definition}[Complexity Measure]\label{def:MoC}
For any set $A \subseteq \Theta$ and a family of quasi-norms, $\{ d_{l} :
\mathcal{F}(\Theta) \rightarrow \mathbb{R}_{+} \}_{l \in \mathbb{N}_{0}}$, let
\begin{align}
\gamma(A,(d_{l})_{l \in \mathbb{N}_{0}}) = \inf_{(\mathcal{T}_{l})_{l\in \mathbb{N}_{0}} \in \mathbf{T}} \sup_{f \in \mathcal{F}(A)} \sqrt{2} \sum_{l=0}^{\infty} 2^{l/2} d_{l}(S(f,\mathcal{T}_{l}))
\end{align}
be the \emph{Complexity Measure of set $A$ under the family $(d_{l})_{l \in \mathbb{N}_{0} }$}.
\end{definition}
We relegate a discussion of its properties to Section \ref{sec:MoC-bound}.
As explained below in Section \ref{sec:discussion}, the fact that the complexity depends on a \emph{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}$,
\begin{align}\label{eqn:qk}
q_{n,k} = & \min \{ s \in \mathcal{Q}_{n} \mid 0.5 \beta(s) n \leq s 2^{k+1} \},
\end{align}
where for each $(n,k)$, $q_{n,k}$ acts as the parameter $q$ controlling the bound of the coupling results in Section \ref{sec:prem}.
And for any $f \in \mathcal{F}(\Theta)$ and $q \in \mathbb{N}$, let
\begin{align}
||f||^{2}_{q} = 2\int_{0}^{1} \mu_{q}(u) Q^{2}_{f}(u) du,
\end{align}
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)$.}
\begin{align}
\label{eqn:muq}
u \mapsto \mu_{q}(u) = \sum_{i=0}^{q} 1_{\{ u \leq 0.5 \beta(i) \}} \in \{0,...,1+q\}.
\end{align}
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
\begin{align*}
\gamma_{n}(A) = \gamma(A,(||.||_{q_{n,k}})_{k}).
\end{align*}
Abusing terminology, we call $\gamma_{n}(A)$ the \emph{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
\begin{align}\label{eqn:H}
H_{n,k}(\omega)(s) \equiv \frac{\gamma_{n}( I_{n,k}( \omega )(s))}{\sqrt{n}} + \eta_{n},~a.s.-\mathbf{P}
\end{align}
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}$.}
\begin{align*}
\delta_{k,\mathbf{P}}(\theta,\nu_{k}(\mathbf{P})) \equiv \sqrt{Q_{k}(\theta,\mathbf{P}) - Q_{k}(\nu_{k}(\mathbf{P}),\mathbf{P})},~\forall \theta \in \Theta_{k},~k\in \mathbb{N}.
\end{align*}
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
\begin{align}\label{eqn:V-H}
V_{n,k}(\omega) = \min \left\{ s > 0 \mid s \geq 5 \max_{x \geq 1} \frac{H_{n,k}(\omega)(sx)}{sx} \right\},~a.s.-\mathbf{P} .
\end{align}
\medskip
\textbf{Concentration result.} Let $\boldsymbol{\varrho} = \{ \varrho_{n,k} : \Omega \rightarrow \mathbb{R}_{+} \}_{n,k}$ such that for any $(n,k)$
\begin{align}
\varrho_{n,k}(\omega) = V_{n,k}(\omega)+ \sqrt{B_{k}(\mathbf{P})},~a.s.-\mathbf{P}.
\end{align}
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{app:concen-main}.} 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 \}$.
\begin{theorem}
\label{thm:concen-main}
Suppose $\nu(\mathbf{P}) \ne \{ \emptyset \}$. Then, the regularized M-estimator (defined in definition \ref{def:reg}) $(\boldsymbol{\varrho},g_{0})$-concentrates at $\nu(\mathbf{P})$ under $\delta_{\mathbf{P}}$. That is, for all $(n,k)$ and $u >0$
\begin{align}\label{eqn:main-1}
\mathbf{P} \left( \delta_{\mathbf{P}} \left( \nu_{k}(P_{n}), \nu(\mathbf{P}) \right) \geq u \varrho_{n,k}(\omega) \right) \leq g_{0}(u).
\end{align}
\end{theorem}
\begin{proof}
See Appendix \ref{app:concen-main}.
\end{proof}
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 \emph{effective number of observations}.
It follows that for any $q \in \mathbb{N}$ and any $r>2$,\footnote{This is proven in Lemma \ref{lem:bound-normq} in the Online Appendix \ref{app:supp-lem-bound-H}.}
\begin{align}\label{eqn:qnorm-bound}
||\cdot ||_{q} \leq \sqrt{2} \left( \int_{0}^{1} |\mu_{q}(u)|^{\frac{r}{r-2}} du \right)^{\frac{r-2}{2r}} ||\cdot ||_{L^{r}(\mathbf{P})}.
\end{align}
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.
\begin{theorem}
\label{thm:effe-n}
For any $ r > 2$ and any $n,k$,
\begin{align*}
V_{n,k}(\omega) \leq \min \left\{ s > 0 \mid s \geq 5 \max_{x \geq 1} \frac{\frac{\gamma(I_{n,k}(\omega)(sx),2^{1/r} ||.||_{L^{r}(\mathbf{P})})}{\sqrt{n(\beta)}} + \eta_{n}}{sx} \right\}
\end{align*}
where \begin{align}
n(\beta) = \frac{n}{2^{1-2/r} \left( \int_{0}^{1} |\mu_{q_{n,0}}(u)|^{\frac{r}{r-2}} du\right)^{\frac{r-2}{r}}}.
\end{align}
\end{theorem}
\begin{proof}
See Appendix \ref{app:effe-n}.
\end{proof}
We call $n(\beta)$ the \emph{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{eqn:muq} --- plays an important role; we relegate a more thorough discussion of this and the effective number of observations to section \ref{sec:effe-n}.
\medskip
\textbf{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$.
\begin{assumption}\label{ass:IU}
For any $\epsilon>0$, $k \in \mathbb{N}$ and $M>0$,
\begin{align}\label{eqn:IU}
\inf_{\theta \in \Theta_{k}(M) \setminus \nu_{k}(\mathbf{P})^{\epsilon} } \frac{\delta_{k,\mathbf{P}} (\theta, \nu_{k}(\mathbf{P})) }{\varpi(\theta , \nu_{k}(\mathbf{P}) )} \geq \underline{\varpi}_{k}(M,\epsilon).
\end{align}
where $\nu_{k}(\mathbf{P})^{\epsilon} = \{ \theta \in \Theta_{k}(M) \mid \inf_{\theta_{0} \in \nu_{k}(\mathbf{P})} \varpi(\theta,\theta_{0}) < \epsilon \}$, and $\underline{\varpi}_{k}: \mathbb{R}^{2}_{+} \rightarrow \mathbb{R}_{++}$.
\end{assumption}
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
\begin{align}\label{eqn:V-concen-w}
\tilde{V}_{n,k}(\omega) = \min \left\{ s > 0 \mid s \geq 5 \max_{x \geq 1} \frac{\left\{ \gamma_{n}( \tilde{I}_{n,k}(\omega)(s x) )/\sqrt{n(\beta)} + \eta_{n} \right\} }{x s ( \underline{\varpi}_{k}(M_{n,k}(\omega), 0.5 x s) )^{2} } \right\}
\end{align}
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 \} $.
\begin{proposition}\label{pro:concen-w}
Suppose $\nu(\mathbf{P}) \ne \{ \emptyset\}$. Let $\varpi$ be a metric over $\Theta$ such that Assumption \ref{ass:IU} holds. Then, the regularized M-estimator (defined in definition \ref{def:reg}) $(\boldsymbol{\tilde{\varrho}},g_{0})$-concentrates at $\nu(\mathbf{P})$ under $\varpi$.
\end{proposition}
\begin{proof}
See Appendix \ref{app:concen-w}.
\end{proof}
Condition \ref{eqn:IU} is akin to the identifiable uniqueness condition (e.g. see \cite{WW1991}) and to measures of ill-posedness in the context of ill-posed inverse problems (see \cite{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{thm:concen-main} 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.
\medskip
\textbf{$L^{1}$ non-asymptotic bound.} Theorem \ref{thm:concen-main} implies, under additional integrability restrictions, an $L^{1}$ non-asymptotic bound for our estimator.
\begin{proposition}
\label{pro:L1-rate}
Suppose that $\nu(\mathbf{P}) \ne \{ \emptyset\}$, and also that for any $(n,k)$, there exists a decreasing bounded function $\varphi_{n,k} : \mathbb{R}_{+} \rightarrow \mathbb{R}_{+}$, such that
\begin{align*}
E_{\mathbf{P}} \left[ \frac{\delta_{\mathbf{P}}(\nu_{k}(P_{n}),\nu(\mathbf{P}))}{\varrho_{k,n}(\omega)} 1\{ \frac{\delta_{\mathbf{P}}(\nu_{k}(P_{n}),\nu(\mathbf{P}))}{\varrho_{k,n}(\omega)} \geq A \} \right] \leq \varphi_{n,k}(A),~\forall A>0.
\end{align*}
Then $ E_{\mathbf{P}} \left[ \frac{\delta_{\mathbf{P}}(\nu_{k}(P_{n}),\nu(\mathbf{P}))}{\varrho_{k,n}(\omega)} \right] \leq \inf_{A \geq 1} \{\varphi_{n,k}(A) + 1 + \mathbb{G}_{0} \ln (A)\}$
for any $n,k$.
\end{proposition}
\begin{proof}
See Appendix \ref{app:concen-w}.
\end{proof}
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)$.
\subsection{Discussion about Theorem \ref{thm:concen-main} and Theorem \ref{thm:effe-n} }
\label{sec:discussion}
\subsubsection{Heuristics}
\label{sec:heur}
Informally, the proof of Theorem \ref{thm:concen-main} can be divided into two main parts. The first part relies on ``Wald's approach" (\cite{wald1949}) and is fairly standard in this setting (e.g., see \cite{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 \emph{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
\begin{align*}
\left\{ \omega \colon \sup_{\theta \in I_{n,k,l}} |\mathcal{L}_{n}(\theta) - \mathcal{L}_{n}(\nu_{k}(\mathbf{P})) | \geq 2^{l} u V_{n,k}(\omega) \right\}
\end{align*} occurs with probability less than $2^{-l}g_{0}(u)$, and it is shown here:
\begin{theorem}
\label{thm:gbrack}
Let $A \subseteq \Theta$. Then, for all $(n,k)$ and all $u \geq 0$,
\begin{align}
\mathbf{P} \left( \sup_{\theta \in A} |\mathcal{L}_{n}(\theta) - \mathcal{L}_{n}(\nu_{k}(\mathbf{P})) | \geq u \frac{\gamma_{n}(A)}{\sqrt{n}} \right) \leq g_{0}(u).
\end{align}
\end{theorem}
\begin{proof}
See Appendix \ref{app:gbrack}.
\end{proof}
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 \cite{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{lem:decom-L} in the Appendix \ref{app:gbrack}); essentially, we decompose $f$ into ``bounded" parts and ``unbounded" parts. Second, we use Bernstein inequality for $\beta$-mixing (see Lemma \ref{lem:bere} in the Appendix \ref{app:gbrack}) and the ideas in \cite{talagrand2014} to control the ``bounded" parts \emph{uniformly}, and we use a $L^{1}$ bound for the ``unbounded" parts (see Lemma \ref{lem:L1-bdd} in the Appendix \ref{app:gbrack}).
\subsubsection{On the family of Norms $(||.||_{q_{n,k}})_{k}$.}
\label{sec:family}
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{lem:q-norm}(3) in Appendix \ref{app:gbrack} that for all $q \in \mathbb{N}$
\begin{align*}
||f||_{q} \leq ||f||_{2,\beta} \equiv \sqrt{2} \int_{0}^{1} \beta^{-1}(2u) Q^{2}_{f}(u) du,~\forall f \in \mathcal{F}(\Theta).
\end{align*}
(recall that $Q_{f}$ is the quantile function of $|f|$, see \ref{eqn:muq}). 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 \cite{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 \emph{family} of norms to describe the complexity measure.\footnote{ The fact that $||.||_{q}$ is always well-defined for any $q$ follows from Lemma \ref{lem:q-norm} in Appendix \ref{app:gbrack}, which shows that $||.||_{q}$ is bounded by $\int_{0}^{1} \min\{ \beta^{-1}(2u) ,q \} Q^{2}_{f}(u) du$}
\subsubsection{On the Effective Number of Observations.}
\label{sec:effe-n}
In order to shed some light on the behavior of $n(\beta)$, we provide bounds for two widely use canonical mixing structures.
\begin{proposition}
\label{pro:bound-H}
Let $m_{0} > 0$. Then, for any $n$, $q \in \mathcal{Q}_{n}$ and $r>2$,\footnote{The element $[x]$ is the smallest upper bound for $x$ in $\mathcal{Q}_{n}$.}
\begin{enumerate}
\item If $\beta(q) = 1\{ q < m^{-1}_{0} \}$, then
\begin{align*}
\frac{n}{ \min\{ 1 + [n/4] , 1 + m_{0}^{-1} \} } \leq n(\beta) \leq \frac{n}{ \min\{ 1 + n/4 , m_{0}^{-1} \} }.
\end{align*}
\end{enumerate}
And, if $\beta(q) = (1+q)^{-m_{0}}$,
\begin{enumerate}
\item[2.] With $m_{0} > \frac{r}{r-2}$, then\begin{align*}
\frac{n}{\left(\frac{m_{0}(r-2)}{m_{0}(r-2) - r} \right)^{(r-2)/r}} \leq n(\beta) \leq \frac{n}{ \max \left\{ \left(2^{-m_{0}} \right)^{(r-2)/r} , 1 \right\}}.
\end{align*}
\item[3.] With $m_{0} = \frac{r}{r-2}$, then\begin{align*}
\frac{n}{ \left( m_{0} \log \left( 1 + \left[ \left( \frac{n}{4} \right)^{\frac{1}{m_{0}+1}} \right] \right) + 1 \right)^{\frac{1}{m_{0}}}} \leq n(\beta) \leq \frac{n}{\frac{1}{2} \left( m_{0} \log \left( \frac{1}{2} \left( 1 + \left( \frac{n}{4} \right)^{\frac{1}{m_{0}+1}} \right) \right) + 2^{m_{0}} \right)^{\frac{1}{m_{0}}}}.
\end{align*}
\item[4.] With $m_{0} < \frac{r}{r-2}$, then \begin{align*}
\frac{n}{ \left( 1 + \left[ \left( \frac{n}{4} \right)^{\frac{1}{m_{0}+1}} \right] \right)^{\frac{r - (r-2)m_{0}}{r}} A_{0} } \leq n(\beta) \leq \frac{n}{ \left( \left( 1 + \left( \frac{n}{4} \right)^{\frac{1}{m_{0}+1}} \right)^{\frac{r- (r-2)m_{0}}{r-2}} - 2^{\frac{r}{r-2} - m_{0}} \right)^{\frac{r-2}{r}} A_{1} }
\end{align*}
where $A_{1} = \left( \frac{1}{2} \right)^{\frac{r-(r-2)m_{0}}{r}} \left( \frac{2^{-m_{0}} m_{0}(r-2)}{r - m_{0}(r-2)} \right)^{\frac{r-2}{r}}$ and $A_{0} = \left( \frac{r}{r-m_{0}(r-2)} \right)^{\frac{r-2}{r}}$.
\end{enumerate}
\end{proposition}
\begin{proof}
See Appendix \ref{app:sec-main-prop}.
\end{proof}
\begin{remark}
Our result for the $m^{-1}_{0}$-dependent case (Case 1) formalizes the intuition that if observations are $m^{-1}_{0}$-dependent (and we do not have any additional information regarding their behavior), then is as if we only had (up to constants) $n/m^{-1}_{0}$ observations for computing the estimator. Asymptotically, for $m_{0}$ fixed, our result implies that $n(\beta) \asymp n$ and thus the concentration rate for this case is \emph{asymptotically} the same as the one for the i.i.d. case. Our results, however, provide a more nuanced view by studying the finite sample behavior.\footnote{For comparison, for the i.i.d. case ($m_{0}=1$) our results show that $0.5 n \leq n(\beta) \leq n$ for any $n$. I.e., the lower bound is ``loose" by a factor of 2.} For instance, if $m_{0}^{-1}$ is comparable to the number of observations, the effective number of observations can be small, ultimately yielding a larger value for the concentration rate. $\triangle$
\end{remark}
\begin{remark}
Case 2 is analogous to Case 1 and has been widely used in the literature (e.g. DMR, \cite{Hansen96}, \cite{CS-1998} and \cite{Rio2013} among others) and many stationary processes have been shown to be $\beta$-mixing with decay faster than Case 2.\footnote{E.g. \cite{Chen2013} for a general review, and \cite{Beare2010} and \cite{CWY2009} for results for Markov Copula models.} Cases 3 and 4 are different, because, even asymptotically the effective number of observations differs from the actual number of observations. Roughly, for case 3 $n(\beta) \asymp n/\log(n)$ whereas for case 4 $n(\beta) \asymp n^{1-\frac{r-(r-2)m_{0}}{r(m_{0}+1)}}$. Perhaps surprisingly, even in this last case $n(\beta) \rightarrow \infty$ as $n \rightarrow \infty$, for any pair $(r,m_{0})$, but it can be at a very slow rate (e.g., the case $m_{0} \approx 0$). Cases 3 and 4, although not as widely used as Case 2, could be of interest since they allow for slowly decaying dependence structure and thus could be used as alternatives for modeling long-range dependency or long-memory.\footnote{See \cite{CCLJOE10} for examples of processes with slow polynomial decay in the $\beta$-mixing coefficients.} $\triangle$
\end{remark}
\begin{remark}
The key difference between cases 1-2 and 3-4 is that for the former two $\int_{0}^{1} (\beta^{-1}(u))^{\frac{r}{r-2}} du $ is finite, whereas for the latter two it is not. Intuitively, if $\int_{0}^{1} (\beta^{-1}(u))^{\frac{r}{r-2}} du $ is finite, then it turns out that $\mu_{q}$ in display \ref{eqn:qnorm-bound} is bounded above by a constant (not depending on $q$) and thus it suffices to study the complexity measure under a single norm, $||.||_{L^{r}(\mathbf{P})}$. Moreover, in this case, the mixing structure has no (asymptotic) incidence on the convergence rate; this observation is consistent with the asymptotic results in \cite{CS-1998} and \cite{ChenLiao2013}. $\triangle$
\end{remark}
\subsection{Upper Bounds for our Measure of Complexity}
\label{sec:MoC-bound}
Given the result in Theorem \ref{thm:effe-n} 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 (\cite{Dudley-1967}). We also link our measure of complexity to the Generic Chaining one (\cite{talagrand2014} and references therein), thereby providing ``easy" to compute bounds based on maximal inequalities for Gaussian processes.
\label{sec:Dudley-bound}
We impose the following Lipschitz restriction on $\phi$.
\begin{assumption}\label{ass:Lip-phi}
There exists a pseudo-distance $\mathbf{d} : \Theta^{2} \rightarrow \mathbb{R}_{+}$ such that for any $M \geq 0$ and $k \in \mathbb{N}$, there exists a $\mathbb{C}_{k,M} : \mathbb{Z} \rightarrow \mathbb{R}$ such that:
(1) For all $\theta_{1}, \theta_{2} \in \Theta_{k}(M)$, $ |\phi(z,\theta_{1}) - \phi(z,\theta_{2})| \leq \mathbb{C}_{k,M}(z) \mathbf{d}(\theta_{1},\theta_{2}),~a.s.-\mathbf{P}$.
(2) There exists a $r>2$ such that for all $k \in \mathbb{N}$ and $M>0$, $||\mathbb{C}_{k,M}||_{L^{r}(\mathbf{P})} \in [0,\infty)$.
\end{assumption}
For instance, this assumptions is fulfilled in the HD-QR model (example \ref{exa:HD-QR}) 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$.
\begin{proposition}
\label{pro:bound-GC}
Suppose assumption \ref{ass:Lip-phi} holds. Then: For any $M\geq 0$, any $k \in \mathbb{N}$ and any $A \subseteq \Theta_{k}(M)$,
\begin{align*}
\gamma(A,||.||_{L^{r}(\mathbf{P})}) \leq \sqrt{2} ||\mathbb{C}_{k,M}||_{L^{r}(\mathbf{P})} \inf_{(\mathcal{S}_{k})_{k} \in \mathbf{S}} \sup_{\theta \in A}\sum_{l=0}^{\infty} 2^{l/2} Diam (T(\theta,\mathcal{S}_{l}),\mathbf{d})
\end{align*}
where $\mathbf{S}$ is the set of admissible sequences over $A$.\footnote{For any set $X$ and pseudo-distance $d$, $Diam(X,d) = \sup_{x_{1},x_{2} \in X} d(x_{1},x_{2})$.}
\end{proposition}
\begin{proof}
See Appendix \ref{app:Dudley-bound}.
\end{proof}
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
(\cite{talagrand2014}),
applied to $A$ under $\mathbf{d}$. By the calculations in \cite{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 \cite{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. \cite{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}$
\begin{align}\label{eqn:Gauss}
\Gamma_{k}(A) \equiv E\left[\sup_{\theta \in A} \sum_{j=1}^{k} \zeta_{j} \sqrt{b_{j}} \theta_{j} \right].
\end{align}
The next Proposition is a direct corollary of Proposition \ref{pro:bound-GC} and \cite{talagrand2014} Theorem 2.4.1.
\begin{proposition}
\label{pro:M-rate1}
Suppose assumption \ref{ass:Lip-phi} holds with $\mathbf{d}$ induced by $||.||_{\ell^{2}(b)}$. Then: There exists a $L\geq 0$ such that, for any $M\geq 0$, any $A \subseteq \Theta_{k}(M)$ and any $k \in \mathbb{N}$,
\begin{align}
\gamma(A,||.||_{L^{r}(\mathbf{P})}) \leq \sqrt{2} L ||\mathbb{C}_{k,M}||_{L^{r}(\mathbf{P})} \Gamma_{k}(A)
\end{align}
\end{proposition}
\begin{proof}
See Appendix \ref{app:Dudley-bound}.\footnote{The $L$ comes from \cite{talagrand2014} Theorem 2.4.1, and is universal; it does not depend on $n$, $k$ nor on $\mathbf{P}$. }
\end{proof}
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{pro:concen-w}) 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{app:sup-Gau} 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.
\subsection{Linear Regression Model (Example \ref{exa:OLS-q}) cont.}
\label{sec:OLS-simple}
It is instructive to compare the results we obtained in the simple linear regression model in Example \ref{exa:OLS-q}, 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{ass:Lip-phi} holds with $\mathbb{C}_{k,M}(z) = 2(|y| + K_{2})$ , $r=2$ and $\mathbf{d} = ||.||_{\ell^{2}}$,
So, by Proposition \ref{pro:M-rate1}, $\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{pro:bound-H}(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{sec:prem}.} Therefore, by expressions \ref{eqn:H} and \ref{eqn:V-H}, it follows that $V_{n,k} \leq 2 \mathbb{K}_{1} \sqrt{\frac{d}{n/\mu_{0}}} $, and thus Theorem \ref{thm:concen-main} implies that
\begin{align*}
\mathbf{P} \left( ||\nu(P_{n}) - \theta_{\ast}||_{\ell^{2}} \geq u \sqrt{\frac{d}{n/\mu_{0}}} \right) \leq
\mathbb{G}_{0} 2\mathbb{K}_{1} u^{-1}.
\end{align*}
The only difference between this expression and \ref{eqn:toy-concen} is the constant in the concentration bound.
\section{Choice of Regularization Parameters}
\label{sec:choice}
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 \cite{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{thm:concen-main} 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{pro:concen-w} which establishes concentration results for a metric $\varpi$ (e.g., a Banach norm over $\Theta$) and $\tilde{V}_{n,k}$ (see expression \ref{eqn:V-concen-w}). For reasons that will become apparent in the proof of Theorem \ref{thm:k-fea}, 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}))$.
\begin{assumption}
\label{ass:V-bdd}
(i) For each $(k,n) \in \mathbb{N}^{2}$ let $\tilde{V}_{k}(P_{n})$ be such that $\tilde{V}_{k}(P_{n}) \geq \mathbb{V} \tilde{V}_{n,k}(\omega)$, $k \mapsto \tilde{V}_{k}(P_{n})$ non-decreasing and $\mathbb{V} \geq 1$; (ii) $k \mapsto B_{k}(\mathbf{P})$ is decreasing.
\end{assumption}
Part (i) is a high level assumption which seems easy to obtain; we postpone its discussion to the Appendix \ref{app:choice}. 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
\begin{align}
\mathcal{I}(P_{n},\mathbf{P}) \equiv \{ k \in \mathcal{K} \mid \tilde{V}_{k}(P_{n}) \geq \sqrt{B_{k}(\mathbf{P})} \} .
\end{align}
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 \emph{ideal tuning parameter} as \footnote{If there are several minimizer; we take the largest one.}
\begin{align*}
k^{I}(P_{n},\mathbf{P}) = \arg \min_{k \in \mathcal{I}(P_{n},\mathbf{P})} \tilde{V}_{k}(P_{n}).
\end{align*}
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})$.
\begin{lemma}
\label{lem:k-inf}
Suppose Assumptions \ref{ass:IU} and \ref{ass:V-bdd} hold and $\nu(\mathbf{P}) \ne \{\emptyset\}$. Then,
\begin{align*}
\mathbf{P}( \varpi (\nu_{k^{I}(P_{n},\mathbf{P})}(P_{n}) , \nu(\mathbf{P}) ) \geq 2 \mathbb{V} u \tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n}) ) \leq g_{0}(u),~\forall n~and~u>0.
\end{align*}
\end{lemma}
\begin{proof}
See Appendix \ref{app:choice}.
\end{proof}
We now construct the \textquotedblleft feasible" tuning parameter. For any $s \in \mathbb{R}_+$
\begin{align*}
\mathcal{F}_{s}(P_{n}) \equiv \{ k \in \mathcal{K} \mid \varpi (\nu_{k}(P_{n}) , \nu_{k'}(P_{n})) \leq 4 s \tilde{V}_{k'}(P_{n}) ,~\forall k' \in \mathcal{K}~such~that~k' \geq k \},
\end{align*}
be the \emph{test set}. For any $s>0$, the \emph{feasible tuning parameter} is given by
\begin{align}
k_{s}^{F}(P_{n}) = \arg \min_{k \in \mathcal{F}_{s}(P_{n})} \tilde{V}_{k}(P_{n}).
\end{align}
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{pro:concen-w}, 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.
\begin{theorem}
\label{thm:k-fea}
Suppose Assumptions \ref{ass:IU} and \ref{ass:V-bdd} hold and $\nu(\mathbf{P}) \ne \{\emptyset\}$. Also, suppose that for some $s \in \mathbb{R}_{+}$, $ \mathbf{P} \left( \mathcal{F}_{s}(P_{n}) \ne \{ \emptyset \} \right) = 1$. Then, for all $n$
\begin{align*}
\mathbf{P}( \varpi (\nu_{k^{F}_{s}(P_{n})}(P_{n}) , \nu(\mathbf{P}) ) \geq s 6 \mathbb{V} \tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n}) ) \leq 2 | \mathcal{K} | g_{0}(s) .
\end{align*}
\end{theorem}
\begin{proof}
See Appendix \ref{app:choice}.
\end{proof}
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.
\medskip
\textbf{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{lem:k-inf}.
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{pro:concen-w} states that for \emph{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{sec:discuss-V-bdd} for a formalization of this discussion.\footnote{In \cite{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.}
\medskip
\textbf{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
\begin{align*}
\mathbf{P} \left( \varpi (\nu_{k^{F}_{s}(P_{n})}(P_{n}) , \nu(\mathbf{P}) ) \leq s 6 \mathbb{V} \tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n}) \right) \geq 1- \alpha.
\end{align*}
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.
\begin{proposition}
\label{pro:choicek-asym}
Suppose all assumptions of Theorem \ref{thm:k-fea} hold. Then
\begin{align*}
\frac{\varpi (\nu_{k_{s_{n}}^{F}(P_{n})}(P_{n}) , \nu(\mathbf{P}))}{\tilde{V}_{k^{I}(P_{n},\mathbf{P})}(P_{n})} = O_{\mathbf{P}}(s_{n}),~\forall~(s_{n})_{n}~such~that~|\mathcal{K}| g_{0}(s_{n}) \rightarrow 0.
\end{align*}
\end{proposition}
\begin{proof}
See Appendix \ref{app:choice}.
\end{proof}
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})$.}
\medskip
\textbf{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{lem:k-inf}, 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.
\medskip
We illustrate how the choice of tuning parameter works in the HD-QR example.
\begin{example}[HD-QR (cont.)]
We study the case with $d >> n(\beta)$. Here, choosing $k$ amounts to choosing $\lambda_{k}$; hence we index the relevant quantities directly by $\lambda$. The metric $\varpi = ||.||_{\ell^{2}}$ and $\underline{\varpi}_{k}(M,\epsilon) = e_{min}(W_{k})$ and we assume $\min_{k} e_{min}(W_{k}) \equiv \underline{\varpi} \in (0,1]$.
For $Pen(.) = ||.||_{\ell^{1}}$, Assumption \ref{ass:V-bdd} is satisfied with $\tilde{V}_{\lambda}(P_{n}) = \left(\frac{\log (2 d)}{n(\beta)} \right)^{1/4} \sqrt{ \frac{ n^{-1}\sum_{i=1}^{n} \phi(Z_{i},0)} { \lambda} }$ and $\mathbb{V} = \mathbb{V}_{1} \equiv \underline{\varpi}^{-1}\mathbb{K} \max\{1, 2^{1/\pi_{0}} \mathbb{E}_{\pi_{0}} \}$. For $Pen(.) = ||.||_{\ell^{2}(p)}$ (with $m>0$), Assumption \ref{ass:V-bdd} is satisfied with $\tilde{V}_{\lambda}(P_{n}) = 2 \sqrt{\frac{\lambda_{k}^{-1/m}}{n(\beta)} } $ and $\mathbb{V} = \mathbb{V}_{1} \max\{ 1, \left(\frac{\underline{\varpi}}{2(m-1)} \right)^{\frac{1-m}{2m}} \}$. Finally, the test set can be written directly in term of $\lambda$ as
\begin{align*}
\mathcal{L}_{s}(P_{n}) \equiv \{ \lambda \in \mathcal{L} \mid ||\nu_{\lambda}(P_{n}) - \nu_{\lambda'}(P_{n}) ||_{\ell^{2}} \leq 4 s \tilde{V}_{\lambda'}(P_{n}) ,~\forall \lambda' \leq \lambda \}
\end{align*} where $\mathcal{L}$ is a grid in $\mathbb{R}_{++}$. So, $\lambda_{k^{F}(P_{n})}$ amounts to choosing the largest $\lambda$ in $\mathcal{L}_{s}(P_{n})$.
The next proposition establishes the ``ideal" concentration rate, which, by Theorem \ref{thm:k-fea}, coincides (up to constants) with the one obtained by our feasible choice.
\begin{proposition}
\label{pro:LASSO-choice}
Suppose and $0 \in \Theta$. Then:
(1) If $Pen = ||.||_{\ell^{1}}$, then $\tilde{V}_{\lambda_{k^{I}(P_{n},\mathbf{P})}}(P_{n}) \leq (0.5 \underline{\varpi} )^{-1} \left(\frac{\log (2 d)}{n(\beta)} \right)^{1/8} \left( ||\theta_{\ast}||_{\ell^{1}} n^{-1}\sum_{i=1}^{n} \phi(Z_{i},0) \right)^{1/4}$.
(2) If $Pen = ||.||_{\ell^{2}(p)}$, then $\tilde{V}_{\lambda_{k^{I}(P_{n},\mathbf{P})}}(P_{n}) \leq n(\beta)^{-\frac{m}{2(m+1)}} ||\theta_{\ast}||_{\ell^{2}(p)}^{\frac{1}{m+1}} $.
\end{proposition}
\begin{proof}
See Appendix \ref{app:choice}.\footnote{The assumption $0 \in \Theta$ is only to get more tractable expressions. See the proof for an explanation.}
\end{proof}
The rate for (1) is very slow. This follows from the fact that we do not impose sparsity nor compatibility-type conditions (e.g. \cite{VdG-Buhlmann11}), nor bounded parameter set (e.g. \cite{Chatterjee2013}). In fact, we think it is rather surprising that consistency can be achieved without any of these assumptions and still allowing for large number of parameters relative to the (effective) sample size. The rate for (2) coincides with the min-max rate for Normal Means models on $\ell^{2}(p)$ balls (\cite{Wasserman2006} Ch. 7). $\triangle$
\end{example}
\section{Numerical Simulations}
\label{sec:simul}
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.
\subsection{The effective number of observations}
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
\begin{align*}
U_{l+(j-1)m} = U_{1,j} + 0.01 U_{2,l+(j-1)m},~and~X_{l+(j-1)m} = X_{1,j} + 0.01 X_{2,l+(j-1)m}
\end{align*}
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{exa:OLS-q}, $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}) $,
\begin{align*}
\mu_{j}(n,m) \equiv E_{\mathbf{P}} \left[ \delta_{\mathbf{P}} (\nu_{k}(P_{n}),\theta_{0}) \right].
\end{align*}
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{pro:L1-rate} 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{tab:median} and \ref{tab:mean} 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{tab:median} and \ref{tab:mean} 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 \emph{asymptotic} results are not even applicable.
\begin{table}[ht]
\centering
{\footnotesize{
\label{multiprogram}
\begin{tabular}{c|c|c||c|c|c|c} \hline \hline
& & $m=1$ & $m=2$ & & &\\ \hline
\multirow{ 2}{*}{$n=50$} & Actual & 11.88 & 16.95 &
& & \\
& Predicted & & 16.81 & & &\\ \hline\hline
& & $m=1$ & $m=2$ & $m=4$ & & \\ \hline
\multirow{ 2}{*}{$n=100$} & Actual & 6.184 & 8.896 & 12.62 & & \\
& Predicted & & 8.745 & 12.37 & & \\ \hline\hline
& & $m=1$ & $m=5$ & $m=10$ & & \\ \hline
\multirow{ 2}{*}{$n=250$} & Actual & 4.021 & 8.992 & 13.08 &
& \\
& Predicted & & 8.991 & 12.72 & & \\ \hline\hline
& & $m=1$ & $m=10$ & $m=20$ & $m=40$ & $m=100$ \\ \hline
\multirow{ 2}{*}{$n=1000$} & Actual & 1.986 & 6.318 & 9.171 & 12.68 & 21.24 \\
& Predicted & & 6.282 & 8.890 & 12.56 & 19.86 \\ \hline\hline
\end{tabular}
\caption{Values of $100 \times \mu_{1}(n,m)$ for different values of $(n,m)$.}
}}
\label{tab:median}
\end{table}
\begin{table}[ht]
\centering
{\footnotesize{
\label{multiprogram}
\begin{tabular}{c|c|c||c|c|c|c} \hline \hline
& & $m=1$ & $m=2$ & & & \\ \hline
\multirow{ 2}{*}{$n=50$} & Actual & 8.931 & 12.97 & & & \\
& Predicted & & 12.63 & & & \\ \hline\hline
& & $m=1$ & $m=2$ & $m=4$ & & \\ \hline
\multirow{ 2}{*}{$n=100$} & Actual & 8.122 & 11.53 & 17.25 & &\\
& Predicted & & 11.48 & 16.24 & & \\ \hline\hline
& & $m=1$ & $m=5$ & $m=10$ & & \\ \hline
\multirow{ 2}{*}{$n=250$} & Actual & 5.078 & 11.77 & 17.07
& & \\
& Predicted & & 11.37 & 16.07 & & \\ \hline\hline
& & $m=1$ & $m=10$ & $m=20$ & $m=40$ & $m=100$ \\ \hline
\multirow{ 2}{*}{$n=1000$} & Actual & 2.544 & 8.228 & 11.65 & 17.24 & 22.07 \\
& Predicted & & 8.045 & 11.38 & 16.09 & 22.44 \\ \hline\hline
\end{tabular}
\caption{Values of $100 \times \mu_{2}(n,m)$ for different values of $(n,m)$.}
}}
\label{tab:mean}
\end{table}
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.
\subsection{The choice of tuning parameter}
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{ass:V-bdd}(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
\begin{align*}
\{ k \in \mathcal{K} \colon \sqrt{(\bar{\hat{\theta}}_{k,k'} - \hat{\theta}_{k'})^{T} M_{k'} (\bar{\hat{\theta}}_{k,k'} - \hat{\theta}_{k'})} \leq 4 s_{n} \sqrt{\frac{k'}{n/m}},~\forall k' \in \mathcal{K}~s.t.~k' \geq k \}
\end{align*}
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{pro:choicek-asym} 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{tab:choice-psp} and \ref{tab:choice-pol} 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{thm:k-fea}. 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}$.
\begin{table}[ht]
\centering
{\footnotesize{
\begin{tabular}{c|cccccc|c} \hline \hline
$n(\beta)$ & 100 & 300 & 500 & 1000 & 2000 & 3000 & 500=3000/6 \\ \hline
$quant_{0.1}(r_{n})$ & 0.151 & 0.101 & 0.097 & 0.092 & 0.091 & 0.094 & 0.091 \\[1ex]
$quant_{0.5}(r_{n})$ & 0.247 & 0.156 & 0.147 & 0.134 & 0.125 & 0.125 & 0.144 \\[1ex]
$quant_{0.9}(r_{n})$ & 0.388 & 0.228 & 0.206 & 0.185 & 0.170 & 0.166 & 0.204 \\ [1ex]
$k^{I}_{n}$ & 5 & 7 & 7 & 7 & 7 & 7 & 7 \\[1ex]
$k^{F}_{n}$ & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ [1ex]
$V_{k^{I}_{n}}$ & 0.224 & 0.153 & 0.118 & 0.084 & 0.059 & 0.048 & 0.118 \\ [1ex]
$V_{k^{F}_{n}}$ & 0.264 & 0.153 & 0.118 & 0.084 & 0.059 & 0.048 & 0.118 \\ [1ex]
\hline \hline
\end{tabular}
\caption{Parameter choice for P-Splines basis.}
}}
\label{tab:choice-psp}
\end{table}
\begin{table}[ht]
\centering
{\footnotesize{
\begin{tabular}{c|cccccc|c} \hline \hline
n & 100 & 300 & 500 & 1000 & 2000 & 3000 & 500=3000/6 \\ \hline
$quant_{0.1}(r_{n})$ & 0.417 & 0.471 & 0.558 & 0.696 & 0.896 & 1.031 & 0.555 \\[1ex]
$quant_{0.5}(r_{n})$ & 0.464 & 0.492 & 0.573 & 0.705 & 0.902 & 1.036 & 0.571 \\[1ex]
$quant_{0.9}(r_{n})$ & 0.550 & 0.527 & 0.599 & 0.723 & 0.913 & 1.045 & 0.597\\ [1ex]
$k^{I}_{n}$ & 5 & 7 & 7 & 7 & 7 & 7 & 7 \\[1ex]
$k^{F}_{n}$ & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ [1ex]
$V_{k^{I}_{n}}$ & 0.224 & 0.153 & 0.118 & 0.084 & 0.059 & 0.048 & 0.118 \\ [1ex]
$V_{k^{F}_{n}}$ & 0.224 & 0.130 & 0.100 & 0.071 & 0.050 & 0.041 & 0.100 \\ [1ex]
\hline \hline
\end{tabular}
\caption{Parameter choice for Polynomial basis.}
}}
\label{tab:choice-pol}
\end{table}
\small
\bibliographystyle{plain}
\bibliography{myref}
\newpage