On the Non-Asymptotic Properties of Regularized
M-estimators
Demian Pouzo∗

arXiv:1512.06290v3 [math.ST] 21 Oct 2016

Dept. of Economics, UC Berkeley
October 24, 2016

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.

1

Introduction

Regularized M-estimators are ubiquitous in econometrics and statistics. They appear in several models, ranging from semi-/non-parametric models such as semi-/nonparametric regressions and semi-/non-parametric likelihood models, to high-dimensional
regression models, just to name a few.1 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/sievesbased estimators (e.g. [29], [28], [27] and [49]), Kernel-based estimators (e.g. Nadaraya
and Watson estimators) and penalized estimators (e.g. [48], and [25] and references
therein) — which include LASSO and Ridge regressions in high-dimensional models
(e.g. [56] 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 Kernelbased estimators or the scale of the penalization in penalized-based estimators.
∗

Contact: 530 Evans Hall # 3880, Berkeley CA 94720. E-mail: dpouzo[at]econ.berkeley.edu. I
would like to thank Noureddine El-Karoui, Nacho Esponda, Bryan Graham, Michael Jansson, Pat
Kline, Elena Manresa, Anna Mikusheva, Jim Powell, Andres Rodriguez-Clare and Andres Santos for
their comments. All errors are mine.
1
See [8] for references and discussion.

1

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 β-mixing (or
regular mixing) conditions.2 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. [50, 26]). 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-/nonparametric problems, relies on asymptotic theory. In this paper we take another route
and we, instead, establish non-asymptotic results. An appealing feature of this approach
is that it allows us to understand the incidence of tuning parameters on the properties
of the estimator for a given sample size, and also, how this depends on the underlying
data structure, namely its dependence structure. Overall, our results provide a more
accurate description of the estimator’s behavior than the standard asymptotic ones,
and even extend them in some settings.
In order to assess the behavior of our estimator, we focus on the so-called concentration properties. That is, we provide non-asymptotic bounds for the probability that
our estimator is within a certain ball of the identified parameter. We characterize how
the sample size, the tuning parameters and the dependence structure affect the radius
of this ball. This radius, called the concentration rate, should be thought as analogous
to the convergence rate in asymptotic theory. We think that studying concentration
properties are a necessary and important first step for assessing the finite sample behavior of regularized estimators, and also constitute the foundation for establishing the
asymptotic results of consistency and convergence rates.
The concentration rate is comprised of two familiar terms: a “variance” term
and a “(squared) bias” term. The behavior of the former term depends on (i) how
“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 β-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 “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
“large or complex” the parameter set is; we quantify this by defining a new measure
of complexity inspired by Talagrand’s Generic Chaining approach ([51]). 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 ([52],[53]) our measure of
complexity is bounded above by the one based on metric-entropies ([24]); i.e., one can
2

See [10] for references and discussions of mixing processes.

2

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.3
Second, we show that the effect of the dependence structure of the data on the
concentration rate can be summarized by a re-scaling of the number of observations.
That is, we show that “variance” term (or rather a bound of it) is analogous to the one
obtained in the i.i.d. data case, but with a modified (smaller) sample size, instead of
the actual sample size. We call this the effective number of observations. In order to
fix ideas, consider a very simple linear regression model with k covariates and with mdependent data.4 p
For the case of i.i.d. data, it is not hard to show that the “variance”
term is of order k/n where n is the number of observations in the sample.
p With
m-dependent data, however, we show that the “variance” term is of order mk/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 nonasymptotic results. For m fixed, the previous discussion implies that, asymptotically,
the effective and actual number of observations coincide, and thus the “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 β-mixing
coefficients decay “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. [18] and [16]).
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”
β-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 β-mixing
structure, the natural topology for determining the size/complexity of the parameter
set is given by a family of norms, each depending on the mixing structure. This is in
contrast to the cases of i.i.d data or “fast-decaying” β-mixing coefficients where a single
norm is used (cf. [23] and [18]).
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 ([36]) and is an adaptation to Mestimation of the one first proposed by [41]. The motivation for this method is as follows.
3

In [42], we show that our measure is also a lower bound for bracketing-entropies ([40]).
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.
4

3

In many cases choosing the tuning parameter to balance the “(squared) bias” and the
“variance” terms yields good convergence rates, even achieving min-max convergence
rates (see [3] 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 “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 ([47],[1]) both of which can be delicate in general frameworks with
time-dependent data.
Related Literature. Conceptually our general setup is based on the excellent
reviews by [8] and [37]. The construction of our estimator is based on [17] PSMD
estimator (adapted to M-estimation) and [13].
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 [56] book for
a thorough review of the literature and an extensive treatment of LASSO ([54]) and
similar models. In econometrics, we refer the reader to [7] 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 [39] 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 [11] about “assumptionless” consistency
of the LASSO.
Second, we contribute to the vast literature of non-/semi-parametric models. We
refer the reader to [43] and [13] 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. [37] offers a nice review of non-asymptotic results but for i.i.d
data. From these papers, closest to ours are [18] and [16] who derive asymptotic results
(both convergence rate and inference) for sieve and penalized M estimators respectively,
for β-mixing decay of the order O(q −̟ ) with ̟ > 2. They rely on L2 bracketing entropy to measure the complexity or size of the parameter set. [65] 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 [53] for a recent book treatment. To our knowledge this approach has not been used before in M-estimation problems, with the notable exception
of [55]. The idea that the notion of distance used to construct the complexity measure depends on the mixing structure was first pointed out by [23] in the context of
central limit results and under the assumption of sufficiently fast decaying β-mixing
coefficients.5 This last assumption ensures that a single norm suffices to construct a
Ossiander’s bracket entropy integral (see [40]), which the authors used as their measure
of complexity. However, if the assumption is dropped — i.e., the β-mixing coefficients
decay slowly — then their norm, and thus their approach, does not work as stated.
5

See their paper and our Section 4.1 for a precise statement regarding the rate of decay.

4

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 [41], 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 [14] uses a similar
method for choosing the tuning parameter under the L∞ norm for the non-parametric
IV model under i.i.d. data. [31] proposes an alternative way of choosing the tuning
parameter for the same model but under the L2 norm and
palso under i.i.d. assumption;
2
his procedure attains the optimal L -norm rate up to a log(n). Finally, we refer the
reader to [37] for a review of model selection in this setup.
Roadmap. Section 2 presents some illustrative examples. Section 3 defines the
data structure, the M-estimation model (subsection 3.2) and the regularized M-estimator
(subsection 3.3). Section 4 presents the concentration result for the regularized Mestimator and a discussion; it introduces the notion of effective number of observations and establishes bounds for our measure of complexity (subsection 4.2). Section
5 proposes the method for choosing the tuning parameters. Section 6 presents some
numerical simulations. All proofs are gathered in the Appendix.
Notation. For a generic Polish space X the associated σ-algebra is the Borel σalgebra. All functions that we define from X are taken to be Borel measurable. For
any set A ⊆ X and distance function d, d(x, A) ≡ inf x′ ∈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 P below). For any probability measure P , EP [.]
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 P. For any
function f from X to Y, x 7→ f (x) denotes the function and x1 7→ f (x1 , x2 ) is used
when viewing f as a function of x1 , keeping x2 fixed. For two real-valued sequences
(xn )n and (yn )n , xn - yn ( xn % yn ) means that there exists a finite universal constant,
C ≥ 1, such that xn ≤ Cyn ( Cxn ≥ yn ); xn ≍ yn means that both xn - yn and
xn % yn hold. For any given real-valued sequence, (xk )k , xk ↓ a denotes that (a) the
sequence is decreasing and (b) its limit is a; ↑ is defined analogously. Finally, N denotes
{..., −1, 0, 1, ...}, N = {1, 2, 3, ...} and N0 = N ∪ {0}.

2

Illustrative Examples

The following example presents a high-dimensional quantile regression (HD-QR) model.
Quantile regression ([33]) 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 ([6], [32], [60], [64]) 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 [11]). 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.6
6

Related models are also [19] who studied a non-parametric version for dependent data; [63] who
studied kernel estimation of conditional quantiles for dependent data; and [35] who studied a parametric
quantile auto-regression model.

5

Example 2.1 (HD-QR). Let Yi = XiT θ∗ + Ui with E[1{Ui ≤ 0}|Xi ] = τ for some
τ ∈ (0, 1) and i ∈ {1, ..., n}, where θ∗ ∈ Θ = Rd and d ∈ 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 (·|X) (the true conditional cdf) admits a
continuously differentiable pdf (with respect to Lebesgue) f (·|X), and E[|X|] < ∞,
E[|Y |] < ∞, emin (E[XX T ]) > 0 and Eπ0 ≡ E[|emax (XX T )|π0 ] < ∞ for some π0 > 2.7
The parameter of interest can be viewed as solving θ∗ = arg minθ∈Θ EP [φ(Z, θ)]
with Z = (X, Y ) and loss function (z, θ) 7→ φ(z, θ) ≡ (y − xT θ)(τ − 1{y − xT θ ≤ 0});
now and throughout the paper, 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
νk (Pn ) = arg min EPn [φ(Z, θ)] + λk P en(θ)
θ∈Θ

P
where Pn is the empirical distribution, n−1 ni=1 δZi ; λk ≥ 0 is the tuning parameter ;
and P en : Θ → R+ is a penalization function. We present two widely used examples of
penalization function: The ℓ1 -norm and the weighted ℓ2 -norm.
The P en = ||.||ℓ1 Case. By applying our result to this setting, we obtain the
following concentration property (proved in Proposition D.1 in the Appendix D): For
any (k, n) and any u > 0, with probability higher than 1 − G0 /u
p
(1)
|| Wk (νk (Pn ) − θ∗ )||ℓ2 ≤uK max{1, 21/π0 Eπ0 }
s





 tr{W −1 } log(2d) 1/4 q
 p
k
× min
,
Mn,k /λk + λk ||θ∗ ||ℓ1  ,


n(β)
n(β)
where Mn,k = EPn [φ(Z, θ∗ )] + λk ||θ∗ ||ℓ1 ; G0 and K are universal constants that do not
depend on θ∗ or P and are specified below; and Wk ≡ E[dk (X)XX T ] with dk (X) ≡
inf θ∈{θ : ||θ||ℓ1 ≤max{Mn,k ,E[Mn,k ]}/λk } f (X T θ | X). Finally, the quantity n(β) ∈ N is the
so-called effective number of observations and is one of the key quantities in our results;
it is defined in Theorem 4.2 below and discussed further in Section 4.1.3. Informally,
the effective number of observations summarizes the effect of the β-mixing structure on
the concentration property of the regularized estimator. For instance, for i.i.d. data,
n(β) = n, but for richer dependence structures, it follows that n(β) < n; moreover for
8
β-mixing coefficients decaying “slowly”
√ to zero, it follows that n(β)/np→ 0. T
The notion of distance we use, || Wk (·)||ℓ2 , is akin to the MSE, || E[XX ](·)||ℓ2 ,
which is routinely used in high-dimensional linear regression models. The discrepancy
— the term dk — arises because for quantile regression the loss function φ 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 linear regression models.
In √
expression 1, the right hand side term inside the parenthesis consists of the sum
and vanishes as
of a “ variance” and “bias” term. The latter term is quite intuitive
√
λk → 0. We now present some remarks for the, more involved, “ variance” term.
First consider the case where d << n(β). In this case no regularization
q is needed so
we set λk = 0, and the LHS of expression 1 becomes uK max{1, 21/π0 Eπ0 }
7

8

emax (A) and emin (A) are the maximum and minimum eigenvalue of matrix A.
The exact characterization of “slow” decay is presented in Section 4.1.3.

6

tr{Wk−1 }/n(β).

Our results deliver the standard bound for finite (low) dimensional regression problems
with n(β) playing the role of n.9 As pointed out before, for i.i.d. data n(β) = n,
but for other dependence structures, n(β) < 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(β) case, the concentration property reduces to: with probability higher than 1 − G0 /u,
p
|| Wk (νk (Pn ) − θ∗ )||ℓ2 ≤uK max{1, 21/π0 Eπ0 }
!


p
log(2d) 1/4 q
×
Mn,k /λk + λk ||θ∗ ||ℓ1 .
(2)
n(β)
Remark 2.1. We did not impose that Θ ⊆ {θ | ||θ||ℓ1 ≤ K} for some K > 0. By
Remark OA.3.2 in the Online Appendix OA.3, imposing this additional condition —
which is quite standard, see e.g. [11], [56] and references therein — delivers:
)
(
1/4
p
√
log(2d)
|| Wk (νk (Pn ) − θ∗ )||ℓ2 ≤ u2K max{1, 21/π0 Eπ0 }
K
n(β)
with probability higher than 1 − G0 /u, and for λk ≤



log(2d)
n(β)

1/2

.△

For the case of i.i.d data, the result in Remark 2.1 agrees (possibly up to constants)
with those obtained by [11], [4] and [56] among others, for the Linear Regression case
with ℓ1 penalty. The reason for the power 1/4 in log(2d)/n(β) (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(β)}), display 2 and Remark 2.1 extend the “assumptionless” (nomenclature in [11]) 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 β-mixing processes.
Moreover, as opposed to [11], our results do not impose Gaussianity of the residual of
the regression. The reason for this stems from our complexity measure, defined in Definition 4.1. By exploiting the results by [53], Proposition 4.5 in Section 4.2 shows that,
essentially, our measure of complexity
is bounded above by the expectation
of suprema
h
i
Pd
of Gaussian processes; i.e., E supθ∈{θ∈Θ : ||θ|| 1 ≤Mn,k /λk } | j=1 ζj θj | with ζj ∼ N (0, 1).
ℓ

M

≤
So, by applying Hölder inequality one obtains the bound E[max1≤k≤d |ζk |] λn,k
k
p
Mn,k
log(2d) λk (see Lemma OA.3.1 and also [12] Lemma A.2), which is precisely the
term in the “variance term” in expression 2. This point illustrates the usefulness of our
measure of complexity, vis-a-vis, say, Dudley’s entropy. A final comment about the set
{θ ∈ Θ : ||θ||ℓ1 ≤ Mn,k /λk } is in order. Since our estimator minimizes the regularized
criterion function it belongs to {θ ∈ Θ : ||θ||ℓ1 ≤ Mn,k /λk }. Thus, this set, rather than
Θ is the relevant parameter set.
The P en = || · ||2ℓ2 (p) Case. We now apply our results to the case where P en =
P
|| · ||2ℓ2 (p) with ||.||2ℓ2 (p) = dj=1 |θj |2 pj and pj = j m for m ≥ 0. The point of this section
9

p

For comparison, in the linear regression case, the term

tr{E[XX T ]−1 }/n(β).

7

q
tr{Wk−1 }/n(β), becomes the standard

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 D.2 in Appendix D): For any (n, k) and any u > 0,


s
−1/m
q
p
, d}
min{λk
Bk 
|| Wk (νk (Pn ) − θ∗ )||ℓ2 ≤ uK max{1, 21/π0 Eπ0 }  λk ||θ∗ ||2ℓ2 (p) +
n(β)



with probability higher than 1 − G0 /u, where Bk ≡
+ 1 emin2(Wk ) .
√ q d
If d << n(β), then the “variance” term can be majorized by Bk n(β)
. But
r
emin (Wk )
2(m−1)

1/m

−1/m

if d >> n(β), there exists a possibly tighter upper bound given by

Bk

λk
n(β)

. By

choosing λk to balance the “variance” and “(squared) bias” terms, it follows that
1
m
p
− m
m+1
|| Wk (νk (Pn ) − θ∗ )||ℓ2 ≤ uK max{1, 21/π0 Eπ0 }n(β) 2(m+1) ||θ∗ ||ℓm+1
B
,
2 (p) k

and λk = (||θ∗ ||2ℓ2 (p) Bk /n(β))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 ℓ2 (p)-balls;
e.g. [61] Ch. 7. Unfortunately, choosing λk to balance the variance-bias trade-off is
typically infeasible since the bias term depends on unknown quantities such as θ∗ . In
section 5 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 ℓ1 case applies in this
case, with the caveat that now the influence of d in the “variance term” is capped by
− m
−1/m
. Consequently, the concentration rate, n(β) 2(m+1) , does not diverge as d → ∞.
λk
Similar result holds for sequences (pj )j that diverges faster than j m for m > 1, but the
situation is different for pj = j m with m ∈ [0, 1] as the next result illustrates for the
case m = 0 (proved in Proposition D.2): For λk ≤ d/(2tr{Wk−1 }),


s
−1
q
p
2tr{Wk }
.
|| Wk (νk (Pn ) − θ∗ )||ℓ2 ≤ uK max{1, 21/π0 Eπ0 }  λk ||θ∗ ||2ℓ2 (p) +
n(β)
with probability higher than 1 − G0 /u. △

Other examples, such as Non-parametric regression also falls into our framework.
Example 2.2 (Non-Parametric Linear Regression). Let Yi = θ∗ (Xi )+Ui with EP [Ui |Xi ] =
0 for i ∈ {1, .., n} where θ∗ ∈ Θ and Θ is some convex subset of L2 = L2 (Lebesgue).
Our results allow for the regressors to contain lagged values of Y ; e.g. [18] for more
examples. In this case, Z = (X, Y ) and the loss function (z, θ) 7→ φ(z, θ) = (y − θ(x))2 ,
and θ∗ = arg minθ∈Θ EP [φ(Z, θ)].
It is well-known that the estimation problem is ill-posed and needs to be regularized;
see [8]. A common regularized estimator is given by νk (Pn ) = τk (Pn )T ψ(·), where
τk (Pn ) = arg min n
τ ∈Rk

−1

n
X
(Yi − τ T ψ(Xi ))2 + λk P en(τ )
i=1

8

and ψ = (ψ1 , ..., ψk )T being some basis functions for L2 and P en is a convex.10 △
The following example is designed to provide an overview of the main results derived below, in Section 4. 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.
Example 2.3 (A Simple Linear Regression Model). Consider the linear
P regression
model Yi = xTi θ∗ + Ui for i ∈ {1, √
..., n}, xi ∈ Rd non-random with n−1 ni=1 xi xTi =
I, d < n and maxi ||xi ||ℓ2 ≤ K0 d, and ||θ∗ ||ℓ2 < K2 ; (Ui )i with E[U ] = 0 and
E[|Ui |2 ] < ∞. Finally, we assume that (Ui )i is µ0 -block independent, i.e., for any
j ′ µ0 +µ0
0 +µ0
11
j, j ′ ∈ {0, ..., n/µ0 − 1}, (Ui )jµ
and (Ui )i=j
′ µ +1 are independent.
i=jµ
+1
0
0
P
In this case ν(Pn ) = n−1 ni=1 xi Yi . The natural notion of distance for studying concentration properties is the ℓ2 norm, Therefore, obtaining concentration results in
P this problem, boils down to finding concentration results for ||ν(Pn ) − θ∗ ||ℓ2 =
||n−1 ni=1 xi Ui ||ℓ2 . Straightforward calculations imply that, for any u > 0,
!
n

X
X
√ 
−1
xi,l Ui | ≥ u .
(3)
P |n
P ||ν(Pn ) − θ∗ ||ℓ2 ≥ du ≤
1≤l≤d

i=1

The P
previous display suggests that it suffices to study the concentration properties
n
−1
of n
i=1 xi,l Ui 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 3.2. Due to the level
of generality, however, we cannot exploit closed form solution of the estimator; as a
consequence, we need to control uniformly the centered (regularized) criterion function
(see Theorem 4.3 in Section 4.1.1 below). It is here that the complexity of the parameter
set arises as an important element in our results. In Section 4 we define the Measure
of Complexity and in Section 4.2 we provide further discussions and results.12
P
√ P
−1/2 Pjµ0 +µ0
We can cast |n−1 ni=1 xi,l Ui | as |n−1 µ0 Jj=0 ∆j,l | with ∆j,l = µ0
i=jµ0 +1 xi,l Ui
and J = n/µ0 − 1. Since (Ui )i is µ0 -block independent, this decomposition implies that
(∆j,l )Jj=0 are independent from each other. Using this fact, and decomposing xl U into
bounded and unbounded parts, we invoke Bernstein (e.g. [57] Lemma 2.2.9) and Markov
inequalities to establish the following bound (proved in Proposition D.3 in Appendix
D):13 For any n ∈ N, µ0 ≤ n and l = 1, ..., d, for any t ≥ 1
v
"
u
r !
2 #
n
u
X
4
µ
|∆|
0
≤ tEP
xi,l Ui | ≥ t
P |n−1
.
√
n
t
µ0
i=1

We observe that given the dependence structure, the correct order for the variance
E[(∆l )2 ] is in fact µ0 , which also appears scaling the sample size. This observation
10

Due to space constraints, we refer the reader to the Arxiv version [42] for a full-treatment of this
example.
11
For simplicity, we set µ0 such that n/µ0 − 1 ∈ N. Also, in the Online Appendix OA.2 we develop
the MA(µ0 ) case (another µ0 -dependent process)
and argue that the results remain the same.
√
12
In this simple example, the scaling d can be viewed as a measure of the complexity of the
parameter space.
13
The appendix also contains a discussion about alternative bounds.

9

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 effective number of observations is
given by n/µ0 . This proposition and expression 3, imply that
q the estimator satisfies a

d
concentration property with a concentration rate given by n/µ
and a concentration
0
s

2 
|∆|
4d
√
bound given by u 7→ u EP
, i.e., for any n and any u ≥ 1,
µ0

P ||ν(Pn ) − θ∗ ||ℓ2 ≥

s

d
u
n/µ0

!

v
"
u
2 #
4d u
|∆|
tEP
≤
.
√
u
µ0

(4)

At the core of the proof of our main theorem, Theorem 4.1 below, there is also Bernstein inequality (see Lemma B.7 in Appendix B.4), and the idea of approximating the
original data with independent blocks. There are, however, some key differences with
the calculations leading to expression 4. First, in this simple application, the approximation by independent block is exact, but for more general dependent structures an
approximation error arises (see Lemma B.4 in Appendix B.4 and the discussion in Section 3). Second, while we also decompose φ into a “bounded” part and a “unbounded”
part, we use more sophisticated arguments based on the results in [23] that only use
L1 -norm bounds (see Lemmas B.3 and B.6 in Appendix B.4). 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 4.3). 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 4.1 for its role on the concentration
rate). △

3

The Model and the Regularized Estimator

We now introduce the data structure, define the model and the regularized estimator.

3.1

The Data

Let ω ≡ (..., Z−1 , Z0 , Z1 , ...) with Z ∈ Z ⊆ R|Z| for some |Z| ∈ N finite. Let Ω = (Z)N
n be the σ-algebra generated by Z
be the sample space. Let Zm
m:n = (Zm , ..., Zn ) for any
m ≤ n. Let P be the true probability over (Ω, Borel). We assume that P belongs to a
class of stationary and β-mixing (or absolutely regular) probabilities, i.e., there exists
t , Z +∞ ) ≤ β(q) for
a function β : R+ → R such that limq→∞ β(q) = 0 and supt β(Z−∞
t+q
all q ∈ N0 where


 X

1
β(U , V) = sup
|P(Uj ∩ Vj ) − P(Uj )P(Vj )|
(5)


2
i∈I,j∈J

where the “sup” is taken over all pairs of partitions (Ui )i∈I and (Vi )i∈I on Ω such that
Ui ∈ U and Vi ∈ V, and U and V are σ-algebras; see [58] and [23] p. 397. For technical
reasons, we also require β to be cadlag and non-increasing.

10

The results in the paper hinge on well-known coupling results for β-mixing processes;
in particular, following [65], in our proofs we use the following fact:14 For any q ∈ N, let
∗
∗
(Zi∗ )i∈N0 be independent of (Zi )i∈N0 and such that: (1) Ui∗ (q) ≡ (Ziq+1
, ..., Ziq+q
) has
the same distribution as Ui (q) ≡ (Ziq+1 , ..., Ziq+q ) for any i = 0, 1, ...; (2) The sequence
∗ (q))
∗
∗
(U2i
i≥0 is i.i.d. and so is (U2i+1 (q))i≥0 ; and (3) P(Ui (q) 6= Ui (q)) ≤ β(q) for any
∗
i = 0, 1, .... where P is the product measure of P and P — the probability distribution
∗ , Z ∗ , Z ∗ , ...); see [22] pp. 144-152 and [38] Theorem 2.9 and references
of ω ∗ ≡ (..., Z−1
1
0
therein.

3.2

The Model

Consider a Banach space (Θ, ||.||Θ ) and some subset P of the space of Borel probability
measures over Ω that are stationary and β-mixing, and P ∈ P. Our interest is the
estimation of a parameter θ∗ ∈ Θ such that for some given criterion function Q :
P ∪ D × Θ → R+ (where D the set of discretely supported distributions)15
Q(θ∗ , P) ≤ Q(θ, P), ∀θ ∈ Θ.
I.e., the parameter of interest, θ∗ , is characterized as the minimizer of the criterion function at P over Θ. We focus on M-estimation problems, wherein Q(θ, P ) = EP [φ(Z, θ)]
for a given loss function φ : Z × Θ → R such that {φ(·, θ) : θ ∈ Θ} ⊆ L1 (P).
Let ν : P → 2Θ be the parameter mapping where
ν(P ) = arg min Q(θ, P ), ∀P ∈ P
θ∈Θ

(6)

and ν(P ) be the identified parameter (set) at P . Clearly, if ν(P) is non-empty, θ∗ ∈
ν(P). In Appendix A we present a low-level condition that ensures the non-emptiness
of ν(P).16 Henceforth, Q(ν(P), P) should be understood as Q(θ, P) for some (any)
θ ∈ ν(P). Our analysis admits the identified parameter set, ν(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 ν(P).
In this general setup, it is well-known that the mapping ν 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 [8] and references therein. Therefore, we need to regularize
the problem.

3.3

The Regularized Estimator and Concentration Properties

Our goal is to study the concentration properties of the class of regularize M-estimators.
We now define these concepts.
The Regularized M-estimator. In the spirit of [8], we define a regularized estimator as a sequence of set-valued functionsPν = (νk )k∈N with νk : P ∪ D → 2Θ such
that νk (Pn ) is a singleton, where Pn ≡ n−1 ni=1 δZi is the empirical distribution.
14

See also [18].
The reason for including 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.
16
The condition essentially restricts the lower-contour sets of Q(., P) to be compact under some
topology, not necessarily the one induced by ||.||Θ .
15

11

Remark 3.1. The regularized estimator needs only to be constructed at Pn , but is
convenient to define it at P too, and interpret this quantity as the “regularized parameter” (the precise definition is given below). Abusing terminology, we also call the
sequence evaluated at Pn , (νk (Pn ))n,k , a regularized estimator. △
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.
Definition 3.1. A regularization structure is a tuple h{λk , Θk , }∞
k=1 , P eni such that
1. (Penalization parameter) For each k ∈ N, λk > 0 and λk ↓ 0.

2. (Sieve Spaces) For each k ∈ N, Θk ⊆ Rk is non-empty, τ -closed and ∪k Θk is
τ -dense in Θ.17
3. (Penalization function) P en : Θ → R+ is τ -continuous.

For each k ∈ N, let Qk = Q + λk P en be the Regularized Criterion Function, and

Definition 3.2 (Regularized Estimator). Given a regularization structure h{λk , Θk , }∞
k=1 , P eni
and a positive real-valued sequence (ηn )n such that ηn → 0, the regularized M-estimator
(νk (Pn ))n,k is given by
νk (Pn ) ∈ Θk and Qk (νk (Pn ), Pn ) ≤ inf Qk (θ, Pn ) + ηn , a.s. − P
θ∈Θk

for all (n, k) ∈ N2 .

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 highdimensional models, or sieve/series and penalization for semi-/non-parametric models.
The Regularized Parameter Set. For any k ∈ N, let
νk (P) = arg min Qk (θ, P)
θ∈Θk

(7)

be the regularized parameter (set).18 As in the case of the identified parameter, our
analysis goes through even if νk (P) is not a singleton. Henceforth, Qk (νk (P), P) should
be understood as Qk (θ, P) for some (any) θ ∈ νk (P).
Finally, we formally define the concentration property for a regularized estimator.

Concentration Property. Let r = (rn,k )n,k∈N2 with rn,k : Ω → R+ and g : R+ →
[0, 1].
Definition 3.3 (Concentration Property). Given a parameter mapping ν, a regularized
estimator ν, (r, g)-concentrates around ν(P) under d : Θ2 → R+ if, for all u > 0 and
all (n, k),
P (d(νk (Pn ), ν(P)) ≥ urn,k (ω)) ≤ g(u).

(8)

We call r the concentration rate and g the concentration bound.
That is, if a regularized estimator satisfies the concentration property with parameters (r, g), with probability higher than 1 − g(u), the estimator is within a urn,k neighborhood (under d) of the identified set ν(P). In cases where limu→∞ g(u) = 0 and
rn,k(n) → 0 as n → ∞ a.s.-P for some n 7→ k(n), this property implies the asymptotic
convergence (under d) at rate (rn,k(n) )n to the identified set ν(P).
17
18

τ is some topology, not necessarily equal to the one induced by ||.||Θ .
Lemma A.2 in the Appendix A provides sufficient conditions to show that νk (P) is non-empty.

12

4

Main results

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.
UnlessQotherwise stated, we restrict our attention to q ∈ Qn = {m ∈ N : n/m ∈ N}
i
and n = υi=1 pm
for some some υ ∈ N, (mi )υi=1 ∈ Nυ0 and (pi )υi=1 consecutive primes.
i
This restriction is not crucial for our results and can be relaxed, but it simplifies the
exposition and technical derivations. The choice of Qn ensure that when constructing
the blocks described in Section 3 with length q ∈ Qn , the number of blocks is an
integer.19 The restriction over n is simply to ensure that Qn is “rich enough” and
its elements are not too far apart; see Online Appendix OA.1 for a more thorough
discussion.
Notion of distance and the Bias Term. For all θ ∈ Θ, let20
p
δP (θ, ν(P)) = Q(θ, P) − Q(ν(P), P).

As illustrated in Section 4.1.1 below, the proof for the concentration results amounts to
studying the behavior of the criterion function. Hence, in this context, δP presents itself
as the natural choice to measure distance over Θ 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 ℓp or Lp norms.
For instance, in the HD-QR example 2.1, we argue
√ that a natural
√
distance is || Wk (·)||ℓ2 , which has the property that δP (·, ν(P)) ≥ || Wk (· − ν(P))||ℓ2 .
In Proposition 4.1 below we generalize this idea and provide concentration results for
general metrics.
For any k ∈ N, let
Bk (P) ≡ Qk (νk (P), P) − Q(ν(P), P)
be the “bias term” under the metric induced by δP . It reflects the two sources of the
“bias”: The fact that our estimator is constructed over Θk (and not Θ) and also the
fact that we add a penalization term when λk > 0.21
Measure of Complexity. The measure of complexity is inspired by Talagrand’s
Generic Chaining results (see [51], [52] and [53]), but to our knowledge the exact construction is new.
For any A ⊆ Θ, let F(A) = {f : Z → R | ∃θ ∈ A, f (.) = φ(., θ) − φ(., νk (P))}.22
For any A ⊆ Θ, let (Tl )l∈N0 be an increasing sequence of partitions (of F(A)) such
l
that card(Tl ) ≤ 22 and T0 = F(A). That is, each Tl consists of a partition of F(A)
l
with (at most) 22 elements. We call such sequence an admissible sequence; we denote
the set of all such sequences as T. For any f ∈ F(A) and l ∈ N0 , there is only one
set in Tl that contains f ; we call it T (f, Tl ). Finally, for any z ∈ Z, let S(f, Tl )(z) =
supf1 ,f2 ∈T (f,Tl ) |f1 (z) − f2 (z)|.
19

For instance, this fact simplifies the decompositions in Lemma B.7 in the Appendix.
Note that δP (·, P) is well-defined because Q(θ, P) ≥ Q(ν(P), P) for all θ ∈ Θ.
21
Lemma A.3 in Appendix A provides conditions to ensure that the bias vanishes as k diverges.
22
We are abusing notation by writing φ(., νk (P)). If νk (P) is a set, φ(., νk (P)) is defined as φ
evaluated at one element of the set and fix it throughout the following arguments.
20

13

Definition 4.1 (Complexity Measure). For any set A ⊆ Θ and a family of quasinorms, {dl : F(Θ) → R+ }l∈N0 , let
γ(A, (dl )l∈N0 ) =

∞
√ X
2l/2 dl (S(f, Tl ))
2
sup

inf

(Tl )l∈N0 ∈T f ∈F (A)

(9)

l=0

be the Complexity Measure of set A under the family (dl )l∈N0 .
We relegate a discussion of its properties to Section 4.2. As explained below in
Section 4.1, the fact that the complexity depends on a family of distances — as opposed
to only one norm/distance
— is important for our analysis. The relevant family of norms

is given by ||.||qn,k k∈N where, for any n and k ∈ N0 ,
0

qn,k = min{s ∈ Qn | 0.5β(s)n ≤ s2k+1 },

(10)

where for each (n, k), qn,k acts as the parameter q controlling the bound of the coupling
results in Section 3. And for any f ∈ F(Θ) and q ∈ N, let
||f ||2q

=2

Z

1
0

µq (u)Q2f (u)du,

(11)

where Qf is the quantile function of |f | and23
u 7→ µq (u) =

q
X
i=0

1{u≤0.5β(i)} ∈ {0, ..., 1 + q}.

(12)

Observe that the dependence structure enters the definition of the norm ||.||q through
R1
µq . In particular, note that ||f ||2L2 (P) = 0 Q2f (u)du, so if q 7→ µq were constant, then
||.||q is proportional to ||.||L2 (P) . However, for general β-mixing processes, µq is not
constant and acts as a weight function for the quantile Qf .
Finally, for any A ⊆ Θ and any n, let
γn (A) = γ(A, (||.||qn,k )k ).
Abusing terminology, we call γn (A) the Complexity Measure of set A given n.
We now define the “variance term” of the concentration rate. For any k ∈ N and
any M ≥ 0, let Θk (M ) ≡ {θ ∈ Θk : λk P en(θ) ≤ M }, and let ω 7→ Mn,k (ω) ≡
Qk (θk , Pn ) + ηn for some (any) θk ∈ Θk . It follows that our estimator belongs to
Θk (Mn,k (ω)) a.s.-P, and thus this is the relevant set over which we do our analysis.
For any s > 0, let
Hn,k (ω)(s) ≡

γn (In,k (ω)(s))
√
+ ηn , a.s. − P
n

where In,k (ω)(s) ≡ {θ ∈ Θk (Mn,k (ω)) | s ≥ δk,P (θ, νk (P)) ≥ 0.5s} and 24
p
δk,P (θ, νk (P)) ≡ Qk (θ, P) − Qk (νk (P), P), ∀θ ∈ Θk , k ∈ N.
23

24

That is, for any u ≥ 0, Qf (u) = inf{s | Hf (s) ≤ u} with Hf (s) = P(|f (Z)| > s).
Observe that δk,P (θ, νk (P )) ≥ 0 for all θ ∈ Θk .

14

(13)

That is, γn (In,k (ω)(s)) measures the complexity of an “δk,P -strip” of Θk (Mn,k (ω)). For
any (n, k), the “variance term” is given by


Hn,k (ω)(sx)
Vn,k (ω) = min s > 0 | s ≥ 5 max
, a.s. − P.
(14)
x≥1
sx
Concentration result. Let ̺ = {̺n,k : Ω → R+ }n,k such that for any (n, k)
p
̺n,k (ω) = Vn,k (ω) + Bk (P), a.s. − P.
(15)

√

This sequence is the concentration rate of our estimator. Let G0 = 3 pυ (8.1) + 2 × 8 ,
and for any u ≥ G0 , let g0 (u) = G0 u−1 , and g0 (u) = 1 for u ∈ [0, G0 ).25 We now establish a concentration property for our regularized M-estimator. We note that this result
is obtained without assumptions, other than ν(P) 6= {∅}.
Theorem 4.1. Suppose ν(P) 6= {∅}. Then, the regularized M-estimator (defined in
definition 3.2) (̺, g0 )-concentrates at ν(P) under δP . That is, for all (n, k) and u > 0
P (δP (νk (Pn ), ν(P)) ≥ u̺n,k (ω)) ≤ g0 (u).

(16)

Proof. See Appendix B.1.
Before discussing its implications, we derive an upper bound on ||.||qn,k which introduces a key component of the variance term (and hence, of the concentration rate),
the so-called effective number of observations. It follows that for any q ∈ N and any
r > 2,26

√ Z
|| · ||q ≤ 2

1

0

|µq (u)|

r
r−2

du

 r−2
2r

|| · ||Lr (P) .

(17)

Since ||.||Lr (P) does not depend on the mixing structure, in order to understand
how
affects concentration rates, it suffices to study the sequence
 the mixing structure
 r−2 
R1
r
2r
r−2 du
. Using this observation, the next Theorem provides
0 |µqn,k (u)|
n,k

bounds for the “variance term” of the concentration rate.
Theorem 4.2. For any r > 2 and any n, k,



Vn,k (ω) ≤ min s > 0 | s ≥ 5 max

x≥1


γ(In,k (ω)(sx),21/r ||.||Lr (P) )

√

n(β)

sx

where

n

n(β) =
21−2/r
Proof. See Appendix B.2.
25
26

R

r
1
r−2 du
0 |µqn,0 (u)|


+ ηn 




 r−2 .
r

The constant follows from the bounds that appear in the Propositions in the Appendix B.1.
This is proven in Lemma OA.4.1 in the Online Appendix OA.4.

15

(18)

We call n(β) the effective number of observations. The Theorem indicates that
is the effective number of observations — rather than n — the right measure of the
sample size in the variance term of the concentration rate. It also illustrates how the
dependence structure affects the concentration rate: By scaling the sample size through
 r−2
 R
R1
r
r
2
1
. Moreover, by inspection of 0 |µqn,0 (u)| r−2 du, we
the term 2 0 |µqn,0 (u)| r−2 du

can see that the integrability of µqn,0 — which in turn relates to the one of β −1 ; see
equation 12 — plays an important role; we relegate a more thorough discussion of this
and the effective number of observations to section 4.1.3.
Concentration Property under general metric. The next proposition establishes the concentration property for a general metric ̟; to do so, it is paramount to
quantify the relationship between δk,P and the desired metric ̟.
Assumption 4.1. For any ǫ > 0, k ∈ N and M > 0,
inf

θ∈Θk (M )\νk

(P)ǫ

δk,P (θ, νk (P))
≥ ̟ k (M, ǫ).
̟(θ, νk (P))

(19)

where νk (P)ǫ = {θ ∈ Θk (M ) | inf θ0 ∈νk (P) ̟(θ, θ0 ) < ǫ}, and ̟ k : R2+ → R++ .
Let ̺
˜ = (˜
̺n,k )n,k , where, for any (n, k), ̺˜n,k (ω) = Ṽn,k (ω) + ̟(νk (P), ν(P)), with
o
n

p

γn (I˜n,k (ω)(sx))/ n(β) + ηn 
Ṽn,k (ω) = min s > 0 | s ≥ 5 max
(20)


x≥1
xs(̟k (Mn,k (ω), 0.5xs))2

and I˜n,k (ω)(s) = {θ ∈ Θk (Mn,k (ω)) | s ≥ ̟(θ, νk (P)) ≥ 0.5s}.

Proposition 4.1. Suppose ν(P) 6= {∅}. Let ̟ be a metric over Θ such that Assump˜ g0 )tion 4.1 holds. Then, the regularized M-estimator (defined in definition 3.2) (̺,
concentrates at ν(P) under ̟.
Proof. See Appendix B.3.
Condition 19 is akin to the identifiable uniqueness condition (e.g. see [62]) and to
measures of ill-posedness in the context of ill-posed inverse problems (see [17]). The
condition quantifies how well the regularized criterion separates points (away from
ν(P)) in the metric space (Θ, ̟). The main difference with the results in the Theorem
4.1 is the scaling by ̟k in the variance term. Ideally ̟k (M, ǫ) ≥ c > 0 for all k, M, ǫ,
so in this case Ṽn,k is proportional to Vn,k for any (n, k). There could be cases, however,
where lim supk→∞ ̟k (M, ǫ) = 0, thus implying that Ṽn,k /Vn,k will diverge.
L1 non-asymptotic bound. Theorem 4.1 implies, under additional integrability
restrictions, an L1 non-asymptotic bound for our estimator.
Proposition 4.2. Suppose that ν(P) 6= {∅}, and also that for any (n, k), there exists
a decreasing bounded function ϕn,k : R+ → R+ , such that


δP (νk (Pn ), ν(P)) δP (νk (Pn ), ν(P))
EP
1{
≥ A} ≤ ϕn,k (A), ∀A > 0.
̺k,n (ω)
̺k,n (ω)
i
h
(Pn ),ν(P))
≤ inf A≥1 {ϕn,k (A) + 1 + G0 ln(A)} for any n, k.
Then EP δP (νk̺k,n
(ω)
16

Proof. See Appendix B.3.
A function ϕn,k always exist if

δP (νk (Pn ),ν(P))
̺k,n (ω)

is in L1 (P). So we view the assump-

n ),ν(P))
.
tion in the proposition as a way of quantifying the tail behavior of δP (νk̺(P
k,n (·)
For instance, if supθ∈Θk δP (θ, ν(P)) ≤ Dk < ∞ and ̺ is non-random, we choose

Dk log(1+Dk )
ϕn,k (A) = 1{A ≤ Dk /̺n,k } ̺n,k
log(1+A̺n,k ) and obtain EP [δP (νk (Pn ), ν(P))] ≤ ̺k,n (1 +
G0 log(2Dk ) + G0 log(1/̺k,n )) for any (n, k).

4.1
4.1.1

Discussion about Theorem 4.1 and Theorem 4.2
Heuristics

Informally, the proof of Theorem 4.1 can be divided into two main parts. The first
part relies on “Wald’s approach” ([59]) and is fairly standard in this setting p
(e.g., see
[18]). It hinges on first noting that δP (νk (Pn ), ν(P)) ≤ δk,P (νk (Pn ), νk (P)) + Bk (P),
so it is sufficient to show that {δk,P (νk (Pn ), νk (P)) ≥ uVn,k (ω)} has probability lower
than g0 (u). In order to do this we “slice” this set into strips of the form In,k,l ≡
{2l uVn,k (ω) ≥ δk,P (νk (Pn ), νk (P)) ≥ 2l−1 uVn,k (ω)} for l = 1, 2, .... After some tedious
calculations
it follows that it suffices to control uniformly the process θ 7→ Ln (θ) =
Pn
−1
n
i=1 {φ(Zi , θ) − EP [φ(Z, θ))]} over In,k,l . The second part of the proof essentially
consists of showing that the set
(
)
ω:

sup |Ln (θ) − Ln (νk (P))| ≥ 2l uVn,k (ω)

θ∈In,k,l

occurs with probability less than 2−l g0 (u), and it is shown here:
Theorem 4.3. Let A ⊆ Θ. Then, for all (n, k) and all u ≥ 0,


γn (A)
≤ g0 (u).
P sup |Ln (θ) − Ln (νk (P))| ≥ u √
n
θ∈A

(21)

Proof. See Appendix B.4.
By our definition of
of the theorem can be thought directly in terms
 F, the statement
Pn
γn√(A)
−1
of f ∈ F(A), i.e., P supf ∈F (A) |n
≤ g0 (u). The
i=1 f (Zi ) − E[f (Z)]| ≥ u
n
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 basedP
on bracketing (see [57]
Ch. 2.5), we decompose any f ∈ F(A) (and consequently n−1 ni=1 f (Zi ) − E[f (Z)])
into several parts (see Lemma B.3 in the Appendix B.4); essentially, we decompose f
into “bounded” parts and “unbounded” parts. Second, we use Bernstein inequality for
β-mixing (see Lemma B.7 in the Appendix B.4) and the ideas in [53] to control the
“bounded” parts uniformly, and we use a L1 bound for the “unbounded” parts (see
Lemma B.6 in the Appendix B.4).
4.1.2

On the family of Norms (||.||qn,k )k .

Our measure of complexity, γn , suggests that the appropriate notion of distance to
measure the complexity of Θ is given by a family of norms — as opposed to only one

17

norm — with each norm depending on the mixing structure. We now discuss these two
features.
It follows from Lemma B.5(3) in Appendix B.4 that for all q ∈ N
√ Z 1 −1
β (2u)Q2f (u)du, ∀f ∈ F(Θ).
||f ||q ≤ ||f ||2,β ≡ 2
0

R1
(recall that Qf is the quantile function of |f |, see 12). In the case where 0 β −1 (2u)du
is finite, the RHS of the previous display provides a well-defined norm for F(Θ) which
was first proposed by [23] (henceforth, DMR) for constructing
entropies.
√ Pbracketing
l/2 ||S(f, T )||
Moreover, it is easy to see that γn (A) ≤ inf (Tl )l ∈T supf ∈F (A) 2 ∞
2
l 2,β .
l=0
R 1 −1
This indicates that when 0 β (2u)du is finite, we can use the norm proposed in DMR
R1
to construct our measure of complexity for the “variance term”. If 0 β −1 (2u)du is
not finite, however, the above proposal becomes infeasible since ||.||2,β may not even be
well-defined, and thus cannot be used to construct the measure of complexity; we need
an alternative way of measuring distance. Since ||.||q is always well-defined for any q,
we rely on a family of norms to describe the complexity measure.27
4.1.3

On the Effective Number of Observations.

In order to shed some light on the behavior of n(β), we provide bounds for two widely
use canonical mixing structures.
Proposition 4.3. Let m0 > 0. Then, for any n, q ∈ Qn and r > 2,28

1. If β(q) = 1{q < m−1
0 }, then
n
n
.
−1 ≤ n(β) ≤
min{1 + [n/4], 1 + m0 }
min{1 + n/4, m−1
0 }

And, if β(q) = (1 + q)−m0 ,
2. With m0 >

r
r−2 ,

then
n

3. With m0 =


1+

h

n
4



m0 (r−2)
m0 (r−2)−r

r
r−2 ,


h
m0 log 1 +

4. With m0 <




then

n

n
4

r
r−2 ,

1
m0 +1

then

where A1 =

i

n
0
i r−(r−2)m
r

1
m0 +1

1
2

n
n
o.
max (2−m0 )(r−2)/r , 1

(r−2)/r ≤ n(β) ≤

 m1 ≤ n(β) ≤
+1 0

A0

≤ n(β) ≤

r−m0 (r−2)

n
4



1
m0 +1



+

2m0


1+


n
4

1
m0 +1

and A0 =



0
 r−(r−2)m
r−2

r
r−m0 (r−2)

−2

 r−2
r

r
−m0
r−2

! r−2

0

r

.

27
The fact that ||.||q is alwaysR well-defined for any q follows from Lemma B.5 in Appendix B.4, which
1
shows that ||.||q is bounded by 0 min{β −1 (2u), q}Q2f (u)du
28
The element [x] is the smallest upper bound for x in Qn .

18

 m1 .

n

 r−(r−2)m0  2−m0 m0 (r−2)  r−2
r
r

n

 
1
1
m
log
0
2
2 1+

A1

Proof. See Appendix B.3.
Remark 4.1. Our result for the m−1
0 -dependent case (Case 1) formalizes the intuition
that if observations are m−1
-dependent
(and we do not have any additional information
0
regarding their behavior), then is as if we only had (up to constants) n/m−1
0 observations
for computing the estimator. Asymptotically, for m0 fixed, our result implies that
n(β) ≍ n and thus the concentration rate for this case is 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.29 For instance, if m−1
is comparable to the number of
0
observations, the effective number of observations can be small, ultimately yielding a
larger value for the concentration rate. △
Remark 4.2. Case 2 is analogous to Case 1 and has been widely used in the literature
(e.g. DMR, [30], [18] and [45] among others) and many stationary processes have been
shown to be β-mixing with decay faster than Case 2.30 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(β) ≍ n/ log(n) whereas for case 4
1−

r−(r−2)m0

r(m0 +1)
n(β) ≍ n
. Perhaps surprisingly, even in this last case n(β) → ∞ as n → ∞,
for any pair (r, m0 ), but it can be at a very slow rate (e.g., the case m0 ≈ 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.31 △

Remark
key difference between cases 1-2 and 3-4 is that for the former
R 1 4.3. The
r
two 0 (β −1 (u)) r−2 du is finite, whereas for the latter two it is not. Intuitively, if
R 1 −1
r
(u)) r−2 du is finite, then it turns out that µq in display 17 is bounded above
0 (β
by a constant (not depending on q) and thus it suffices to study the complexity measure under a single norm, ||.||Lr (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 [18] and [16]. △

4.2

Upper Bounds for our Measure of Complexity

Given the result in Theorem 4.2 a key object to bound the variance term is γ(·, ||.||Lr (P) ).
We now provide bounds in terms of the more standard metric entropy-based measure
of complexity ([24]). We also link our measure of complexity to the Generic Chaining
one ([53] and references therein), thereby providing “easy” to compute bounds based
on maximal inequalities for Gaussian processes.
We impose the following Lipschitz restriction on φ.
Assumption 4.2. There exists a pseudo-distance d : Θ2 → R+ such that for any
M ≥ 0 and k ∈ N, there exists a Ck,M : Z → R such that:
(1) For all θ1 , θ2 ∈ Θk (M ), |φ(z, θ1 ) − φ(z, θ2 )| ≤ Ck,M (z)d(θ1 , θ2 ), a.s. − P.
(2) There exists a r > 2 such that for all k ∈ N and M > 0, ||Ck,M ||Lr (P) ∈ [0, ∞).
29
For comparison, for the i.i.d. case (m0 = 1) our results show that 0.5n ≤ n(β) ≤ n for any n. I.e.,
the lower bound is “loose” by a factor of 2.
30
E.g. [13] for a general review, and [5] and [20] for results for Markov Copula models.
31
See [15] for examples of processes with slow polynomial decay in the β-mixing coefficients.

19

For instance, this assumptions is fulfilled in the HD-QR model (example 2.1) with
r = π0 , d = ||.||ℓ2 and Ck,M (z) = (1 + τ )emax (xxT ). The next proposition establishes
an upper bound for γ.
Proposition 4.4. Suppose assumption 4.2 holds. Then: For any M ≥ 0, any k ∈ N
and any A ⊆ Θk (M ),
γ(A, ||.||Lr (P) ) ≤

√

2||Ck,M ||Lr (P)

inf

sup

(Sk )k ∈S θ∈A

∞
X
l=0

2l/2 Diam(T (θ, Sl ), d)

where S is the set of admissible sequences over A.32
Proof. See Appendix C.
P
k/2 Diam(T (θ, S ), d) is exactly Talagrand’s
The expression inf (Sk )k ∈S supθ∈A ∞
k
k=0 2
d.
By
the calculations in [53] pp
Generic Chaining bound ([53]), applied to AR under
∞p
21-24, this expression is bounded above by 0
log N (e, A, d)de; thus showing that
our measure of complexity is sharper than Dudley’s entropy bound. In fact, as argued
in [53] Sec. 2.3, for certain sets of Rk the difference can even diverge with k.
The case where d is induced by ||.||ℓ2 (b) deserves an special mention due to the work
by Talagrand (e.g. [53] and references therein). Let, ζj ∼ N (0, 1) for j = 1, ..., k, and
for any k ∈ N and A ⊆ Θk


k
X
p
Γk (A) ≡ E sup
(22)
ζ j bj θ j  .
θ∈A j=1

The next Proposition is a direct corollary of Proposition 4.4 and [53] Theorem 2.4.1.

Proposition 4.5. Suppose assumption 4.2 holds with d induced by ||.||ℓ2 (b) . Then:
There exists a L ≥ 0 such that, for any M ≥ 0, any A ⊆ Θk (M ) and any k ∈ N,
√
γ(A, ||.||Lr (P) ) ≤ 2L||Ck,M ||Lr (P) Γk (A)
(23)
Proof. See Appendix C.33
The proposition establishes an upper bound for our measure of complexity of A (in
particular A = In,k (ω)(s) or A = I˜n,k (ω)(s) defined in Proposition 4.1) in terms of the
expectation of the supremum of a Gaussian process. This quantity, Γk (A), is a fairly
simple object and relatively easy to bound. A general strategy to bound Γk (A) consists
of using Hölder inequality to obtain Γk (A) ≤ E[||ζ||ℓq1 ] supθ∈A ||b · θ||ℓq2 with 1/q1 +
1/q2 = 1. The choice of q2 is dictated by the geometric properties of A under ||b · .||ℓq2 ,
and bounding E[||ζ||ℓq1 ] usually involves elementary operations since ζ are independent
Gaussian. In the Online Appendix OA.3 we formalize this approach and provide bounds
when the penalty P en is constructed using ℓq -norms. These observations illustrate
what we consider an additional advantage of our measure of complexity over the more
standard ones.
32
33

For any set X and pseudo-distance d, Diam(X, d) = supx1 ,x2 ∈X d(x1 , x2 ).
The L comes from [53] Theorem 2.4.1, and is universal; it does not depend on n, k nor on P.

20

4.3

Linear Regression Model (Example 2.3) cont.

It is instructive to compare the results we obtained in the simple linear regression
model in Example 2.3, with those obtained by applying our general method, which
cannot exploit the explicit
Pn solutionTof 2the OLS estimator.
−1
n
Since
i=1 (y − xi θ) (recall that (xi )i=1 are fixed, not random) and
Pn φ(z,Tθ) = n
−1
n
i=1 xi xi = I, it can be shown that Assumption 4.2 holds with hCk,M (z) = 2(|y| + i
P
K2 ) , r = 2 and d = ||.||ℓ2 , So, by Proposition 4.5, γ(A, ||.||L2 ) ≤ K1 E supθ∈A dk=1 ζj θj ,
√
for any A ⊆ Θ with K1 ≡ 2L2(E[|Y |2 ] + K2 ). In particular, for A = {θ ∈ Θ | ||θ −
θ∗ ||ℓ2 ≤ s} for any s√> 0, by Cauchy-Schwartz inequality, it follows that γ(A, ||.||L2 ) ≤
n 34
K1 sE [||ζ||ℓ2 ] = K1 s d. Also, by Proposition 4.3(1) (with m−1
0 = µ0 ), n(β) ≥ 2 µ0 .
q
d
Therefore, by expressions 13 and 14, it follows that Vn,k ≤ 2K1 n/µ
, and thus Theo0
rem 4.1 implies that
s
!
d
≤ G0 2K1 u−1 .
P ||ν(Pn ) − θ∗ ||ℓ2 ≥ u
n/µ0
The only difference between this expression and 4 is the constant in the concentration
bound.

5

Choice of Regularization Parameters

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 [41]. The salient feature of this method is that it does not use any
knowledge of the “bias” term; it is solely based on the “variance term”.
Unfortunately, Theorem 4.1 cannot be used to establish concentration results for the
aforementioned method, since, δP depends on P (which is unknown).35 Hence, we rely
on Proposition 4.1 which establishes concentration results for a metric ̟ (e.g., a Banach
norm over Θ) and Ṽn,k (see expression 20). For reasons that will become apparent in
the proof of Theorem 5.1, we require Ṽn,k to be increasing
p as a function of k, or at least
find an upper bound that it is. Abusing notation, let Bk (P) = ̟(νk (P), ν(P)).
Assumption 5.1. (i) For each (k, n) ∈ N2 let Ṽk (Pn ) be such that Ṽk (Pn ) ≥ VṼn,k (ω),
k 7→ Ṽk (Pn ) non-decreasing and V ≥ 1; (ii) k 7→ Bk (P) is decreasing.

Part (i) is a high level assumption which seems easy to obtain; we postpone its
discussion to the Appendix E. Part (ii) ensures monotonicity of the “bias” term, which
is convenient for the proof and can be somewhat relaxed.
Let K = {ki ∈ N | 0 < k0 < ... < k|K| } for some |K| < ∞, be the set from which the
researcher selects the tuning parameter. This set is allowed to change with n. Let
p
I(Pn , P) ≡ {k ∈ K | Ṽk (Pn ) ≥ Bk (P)}.
(24)
We assume K to be such that P(I(Pn , P) 6= {∅}) = 1; this assumption is quite mild
since k 7→ Ṽk (Pn ) is nondecreasing and lim supk→∞ Bk (P) = 0. Finally, we define the

34
Formally, this data structure is not stationary, but still sufficiently well-behaved to apply our
theorems; in particular, q 7→ β(q) = 1{q ≤ µ0 } according to our definition in Section 3.
35
Vn,k depends on P through δk,P (., νk (P)).

21

ideal tuning parameter as

36

kI (Pn , P) = arg

min

k∈I(Pn ,P)

Ṽk (Pn ).

The next lemma establishes that the (infeasible) estimator (νkI (Pn ,P) (Pn ))n satisfies
the concentration property at ν(P) under ̟, with rate (ṼkI (Pn ,P) (Pn ))n and bound
u 7→ g0 (0.5u/V).
Lemma 5.1. Suppose Assumptions 4.1 and 5.1 hold and ν(P) 6= {∅}. Then,
P(̟(νkI (Pn ,P) (Pn ), ν(P)) ≥ 2VuṼkI (Pn ,P) (Pn )) ≤ g0 (u), ∀n and u > 0.
Proof. See Appendix E.
We now construct the “feasible” tuning parameter. For any s ∈ R+
Fs (Pn ) ≡ {k ∈ K | ̟(νk (Pn ), νk′ (Pn )) ≤ 4sṼk′ (Pn ), ∀k′ ∈ K such that k ′ ≥ k},
be the test set. For any s > 0, the feasible tuning parameter is given by
ksF (Pn ) = arg

min

k∈Fs (Pn )

Ṽk (Pn ).

(25)

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′ ≥ k and Proposition 4.1, it follows
that, with probability higher than
p
1 − g0 (s), ̟(νk (Pn ), νk′ (Pn )) - s2{Ṽk′ (Pn ) + Bk (P)}. Hence, the “extra” restriction
imposed by the test set is to focus, roughly speaking, attention to k ∈ K for which the
“(squared) bias” term is dominated by the “variance” term; i.e., Bk (P) - Ṽk2 (Pn ) ≤
Ṽk2′ (Pn ). Since I(Pn , 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.
Theorem 5.1. Suppose Assumptions 4.1 and 5.1 hold and ν(P) 6= {∅}. Also, suppose
that for some s ∈ R+ , P (Fs (Pn ) 6= {∅}) = 1. Then, for all n
P(̟(νksF (Pn ) (Pn ), ν(P)) ≥ s6VṼkI (Pn ,P) (Pn )) ≤ 2|K|g0 (s).
Proof. See Appendix E.
The theorem essentially states that the concentration rate of the estimator νksF (Pn ) (Pn )
is of the same order as the one corresponding to the ideal tuning parameter. That is, by
minimizing the “variance term” over the test set, one can construct an estimator which
performance — measured by the concentration rate — is no worse (up to constants)
than the one obtained by the ideal choice which uses knowledge of the “bias” term to
balance the “bias” and “variance” terms of the concentration rate.
On the |K| factor. The concentration function in the theorem is scaled by the
complexity of the set K, |K|. Although it might not be surprising that the complexity
of the set K affects the concentration bound, it still deserves some discussion, especially
since it played no role in Lemma 5.1.
36

If there are several minimizer; we take the largest one.

22

The
we need to ensure
o that the set ∩k∈K En (u, k) ≡
n reason for this scaling arises because

p
∩k∈K ω ∈ Ω | ̟(νk (Pn ), ν(P)) < u Ṽk (Pn ) + Bk (P) has high probability. Proposition 4.1 states that for each k, P(En (u, k)) ≥ 1 − g0 (u), so by means of a crude union
bound we obtain a lower bound 1 − |K|g0 (u) for P(∩k∈K En (u, k)); we refer the reader
to the Online Appendix E.1 for a formalization of this discussion.37
Implications of the Theorem. The theorem provides “̟-confidence-bands”
in the sense that, for a given confidence level α ∈ (0, 1), by choosing s such that
2|K|g0 (s) = α, the theorem implies that


P ̟(νksF (Pn ) (Pn ), ν(P)) ≤ s6VṼkI (Pn ,P) (Pn ) ≥ 1 − α.

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 K to grow with the sample size — and moreover, its rate of convergence coincides
with that of the ideal estimator.
Proposition 5.1. Suppose all assumptions of Theorem 5.1 hold. Then
̟(νksF

n

(Pn ) (Pn ), ν(P))

ṼkI (Pn ,P) (Pn )

= OP (sn ), ∀ (sn )n such that |K|g0 (sn ) → 0.

Proof. See Appendix E.
So consistency of our estimator with the feasible tuning parameter is obtained provided that sn ṼkI (Pn ,P) (Pn ) = oP (1).38
Heuristics. The proof is rather straightforward, albeit somewhat lengthy. The
idea is to bound ̟(νksF (Pn ) (Pn ), ν(P)) by bounding ̟(νksF (Pn ) (Pn ), νkI (Pn ,P) (Pn )) and
̟(νkI (Pn ,P) (Pn ), ν(P)). The latter term was bounded in Lemma 5.1, 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, kI (Pn , P) belongs to the test set.
Thus, by construction of ksF (Pn ), ṼksF (Pn ) (Pn ) ≤ ṼkI (Pn ,P) (Pn ). Since k 7→ Ṽk (Pn )
is non-decreasing, it must hold that kI (Pn , P) ≥ ksF (Pn ). However, by construction of ksF (Pn ) and the fact that kI (Pn , P) belongs to the test set, it follows that
̟(νksF (Pn ) (Pn ), νkI (Pn ,P) (Pn )) - ṼkI (Pn ,P) (Pn ) with high probability.
We illustrate how the choice of tuning parameter works in the HD-QR example.
Example 5.1 (HD-QR (cont.)). We study the case with d >> n(β). Here, choosing
k amounts to choosing λk ; hence we index the relevant quantities directly by λ. The
metric ̟ = ||.||ℓ2 and ̟k (M, ǫ) = emin (Wk ) and we assume mink emin (Wk ) ≡ ̟ ∈
(0, 1].
37

In [41] it is (implicitly) assumed that the sets En (u, k) occur with probability one; thus in their
results the complexity of K plays no role.
38
For the case where |K| is uniformly bounded, it suffices to impose that maxk∈K Ṽk (Pn ) = oP (1).
This condition is rather mild and rules pathological cases where k 7→ Ṽk (Pn ) behaves like a “traveling
wave”. E.g. Ṽk (Pn ) = 1{k ≥ K(n)} for a diverging K(.). In this case, it could happen that kI (Pn , P) =
K(n); hence ṼkI (Pn ,P) (Pn ) = 1 and thus we cannot establish consistency. If the cardinality of K grows
the condition states that is cannot grow too fast relative to 1/ maxk Ṽk (Pn ).

23

For P en(.) = ||.||ℓ1 , Assumption 5.1 is satisfied with Ṽλ (Pn ) =




log(2d) 1/4
n(β)

q

n−1

Pn

i=1

φ(Zi ,0)

λ

and V = V1 ≡ ̟ −1 K max{1, 21/π0 Eπ0 }. For P en(.) = ||.||ℓ2 (p) (with m > 0), Assumpr
 1−m

−1/m
2m
λk
̟
}. Finally,
and V = V1 max{1, 2(m−1)
tion 5.1 is satisfied with Ṽλ (Pn ) = 2 n(β)

the test set can be written directly in term of λ as

Ls (Pn ) ≡ {λ ∈ L | ||νλ (Pn ) − νλ′ (Pn )||ℓ2 ≤ 4sṼλ′ (Pn ), ∀λ′ ≤ λ}
where L is a grid in R++ . So, λkF (Pn ) amounts to choosing the largest λ in Ls (Pn ).
The next proposition establishes the “ideal” concentration rate, which, by Theorem
5.1, coincides (up to constants) with the one obtained by our feasible choice.
Proposition 5.2. Suppose and 0 ∈ Θ. Then:
(1) If P en = ||.||ℓ1 , then ṼλkI (P

n

(Pn ) ≤ (0.5̟)−1
,P)

(2) If P en = ||.||ℓ2 (p) , then ṼλkI (P

n ,P)




log(2d) 1/8
n(β)

m
− 2(m+1)

(Pn ) ≤ n(β)

||θ∗ ||ℓ1 n−1

1
m+1
2
ℓ (p)

||θ∗ ||

.

Pn

1/4

i=1 φ(Zi , 0)

Proof. See Appendix E.39
The rate for (1) is very slow. This follows from the fact that we do not impose
sparsity nor compatibility-type conditions (e.g. [56]), nor bounded parameter set (e.g.
[11]). 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 ℓ2 (p) balls ([61] Ch. 7). △

6

Numerical Simulations

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.

6.1

The effective number of observations

P
We study the following simple regression model with m-dependent data: Yi = dj=1 θ∗ (j)Xj,i +
0.5Ui for i = 1, ...., n and θ∗ (j) = j −0.5 for j = 1, ..., d. The data (Xi , Ui )ni=1 is constructed as follows: Let q = n/m, (X1,j )qj=1 and (U1,j )qj=1 be independent standard
Gaussian, and (X2,i )ni=1 and (U2,i )ni=1 be independent standard Gaussian, finally
Ul+(j−1)m = U1,j + 0.01U2,l+(j−1)m , and Xl+(j−1)m = X1,j + 0.01X2,l+(j−1)m
for all j = 1, ..., q and l = 1, ..., m. It is clear that (Yi , Xi )ni=1 are m-block i.i.d., and, as
pointed in Example 2.3, m-dependent.
P
Let (z, θ) 7→ φ(z, θ) = ρj (y − dl=1 θ(l)xl ) for j = 1, 2, with t 7→ ρ1 (t) = 0.5|t| and
t 7→ ρ2 (t) = t2 . 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 λk = 0 for all k ∈ N.
39

The assumption 0 ∈ Θ is only to get more tractable expressions. See the proof for an explanation.

24

.

We perform M C = 2, 000 Monte Carlo repetitions. For each (n, m), and j = 1, 2
(indexing the type of regression), we report the expectation of δP (νk (Pn ), θ0 ),
µj (n, m) ≡ EP [δP (νk (Pn ), θ0 )] .
√ q
For this case, ̺n,k = Cj m n3 where (Cj )j=1,2 are universal constants. Thus
p n 
√ q 
Proposition 4.2 predicts that µj (n, m) ≤ Cj m n3 C′j + G0 log
, for some
3m

universal constant C′j . Essentially, our theory predicts an upper bound for the growth
√
of m 7→ µj (n, m) of the order of m.
In Tables 6.1 and 6.1 we report µ1 (n, m) and µ2 (n, m) resp. for different values
of (n, m).40 In the tables, “actual” stands for the actual value of µj (n, m) stemming
from the numerical simulations. The “predicted” value for any m > 1, is constructed
√
as m × µ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.41
For comparison, the “standard” asymptotic results predict that µj (n, m) has a convergence rate of order n−1 , independently of the value of m. Tables 6.1 and 6.1 show
that our results provide a sharper description of the behavior of the estimator. Moreover, for small sample sizes such as n = 50, one might feel that asymptotic results are
not even applicable.

n = 50

Actual
Predicted

n = 100

Actual
Predicted

n = 250

Actual
Predicted

n = 1000

Actual
Predicted

m=1
11.88
m=1
6.184
m=1
4.021
m=1
1.986

m=2
16.95
16.81
m=2
8.896
8.745
m=5
8.992
8.991
m = 10
6.318
6.282

m=4
12.62
12.37
m = 10
13.08
12.72
m = 20
9.171
8.890

m = 40
12.68
12.56

m = 100
21.24
19.86

Table 1: Values of 100 × µ1 (n, m) for different values of (n, m).
Overall, the numerical simulations seem to suggest that our upper bound provides
an accurate description of the size of µ for both models. Notably, it does so for values
of n which one could find to be too low to apply asymptotic results.
40

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(β) = 25. For n = 1000 we add the case
n(β) = 10 for further comparison.
41
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.

25

n = 50

Actual
Predicted

n = 100

Actual
Predicted

n = 250

Actual
Predicted

n = 1000

Actual
Predicted

m=1
8.931

m=2
12.97
12.63
m=2
11.53
11.48
m=5
11.77
11.37
m = 10
8.228
8.045

m=1
8.122
m=1
5.078
m=1
2.544

m=4
17.25
16.24
m = 10
17.07
16.07
m = 20
11.65
11.38

m = 40
17.24
16.09

m = 100
22.07
22.44

Table 2: Values of 100 × µ2 (n, m) for different values of (n, m).

6.2

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: Yi =
θ∗ (Wi ) + 0.5Ui for i = 1, ...., n and θ∗ (w) = 2 cos(w) + w for any w ∈ [−6, 6]. The
Xi
and the data (Xi , Ui )ni=1 is constructed in
sequence (Wi )ni=1 is such that Wi = 6 1+|X
i|
the same way as in the previous design (except that the X’s P
are now in R).
We consider a sieve-based estimator with Θk = {f : f = kj=1 θj qj , θj ∈ R, ∀j =
1, ..., k} for two distinct basis functions (qj )j : (a) A polynomial basis and (b) a PSpline basis with 3 equally spaced knots. The second case is of particular interest
because assumption 5.1(ii) may not hold here. We set λk = 0, so the regularization
parameter is k ∈ K where K = {3, ..., 8}. We consider M C = 2, 500.
It is easy to show that in this case, ̟ is induced by the L2q
(P) norm. Therefore, the
P
k
I
= || kj=1 νk (j)qj −
ideal tuning parameter, kn , is proportional to the solution of n/m
−1
E[q k (W )θ∗ (W )] with q k (w) =
θ∗ ||L2 (P) where (νk (1), ..., νk (k))T = E[(q k (W ))(q k (W ))T ]
(q1 (w), ..., qk (w))T . The feasible tuning parameter, knF , is chosen as the minimal k inside
s
q
k′
¯
¯ ′
, ∀k′ ∈ K s.t. k′ ≥ k}
{k ∈ K : (θ̂k,k − θ̂k′ )T Mk′ (θ̂k,k′ − θ̂k′ ) ≤ 4sn
n/m
−1 Pn k
where sn was chosen as 0.5 log(n/m) and for any k θ̂k ≡ Qk QTk
i=1 q (Wi )Yi with
′
¯ ′
k
k
k
Qk = (q (W1 ), ..., q (Wn )), and θ̂k,k = (θ̂k , 0, ..., 0) ∈ R , finally Mk = E[(q k (W ))(q k (W ))T ].
Proposition 5.1 states that rn ≡

√

F

n||(θ̂kF )T q kn −θ∗ ||L2 (P)

√

n

Is
mkn
n

is bounded in probability; so in

order to gauge the behavior of rn we report its MC quantiles for different values of n.
Tables 6.2 and 6.2 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 5.1. 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, knI < knF .
26

n(β)
quant0.1 (rn )

100
0.151

300
0.101

500
0.097

1000
0.092

2000
0.091

3000
0.094

500=3000/6
0.091

quant0.5 (rn )

0.247

0.156

0.147

0.134

0.125

0.125

0.144

quant0.9 (rn )

0.388

0.228

0.206

0.185

0.170

0.166

0.204

knI

5

7

7

7

7

7

7

knF

7

7

7

7

7

7

7

VknI

0.224

0.153

0.118

0.084

0.059

0.048

0.118

VknF

0.264

0.153

0.118

0.084

0.059

0.048

0.118

Table 3: Parameter choice for P-Splines basis.
n
quant0.1 (rn )

100
0.417

300
0.471

500
0.558

1000
0.696

2000
0.896

3000
1.031

500=3000/6
0.555

quant0.5 (rn )

0.464

0.492

0.573

0.705

0.902

1.036

0.571

quant0.9 (rn )

0.550

0.527

0.599

0.723

0.913

1.045

0.597

knI

5

7

7

7

7

7

7

knF

5

5

5

5

5

5

5

VknI

0.224

0.153

0.118

0.084

0.059

0.048

0.118

VknF

0.224

0.130

0.100

0.071

0.050

0.041

0.100

Table 4: Parameter choice for Polynomial basis.

References
[1] S. Arlot and A. Celisse. A survey of cross-validation procedures for model selection. Statistics Surveys, 4:40–79, 2010.
[2] A. Banerjee, X. Guo, and H. Wang. On the optimality of conditional expectation as a
bregman predictor. Information Theory, IEEE Transactions on, 51(7):2664–2669, 2005.
[3] A. Barron, L. Birgé, and P. Massart. Risk bounds for model selection via penalization.
Probability Theory and Related Fields, 113(3):301–413, 1999.
[4] P. L. Bartlett, S. Mendelson, and J. Neeman. ℓ1 -regularized linear regression: persistence
and oracle inequalities. Probability Theory and Related Fields, 154(1-2):193–224, 2012.
[5] B. Beare. Copulas and temporal dependence. Econometrica, 78(1):395–410, 2010.
[6] A. Belloni and V. Chernozhukov. L1-Penalized Quantile Regression in High-Dimensional
Sparse Models. The Annals of Statistics, 39(1):82–130, 2011.
[7] A. Belloni, V. Chernozhukov, and C. Hansen. Inference for High-Dimensional Sparse
Econometric Models. ArXiv e-prints 1201.0220, 2011.
[8] P. Bickel and B. Li. Regularization in statistics. TEST, 15(2):271–344, 2006.
[9] R. Blundell, X. Chen, and D. Kristensen. Semi-nonparametric iv estimation of shapeinvariant engel curves. Econometrica, 75(6):1613–1669, 2007.
[10] R. C. Bradley. Basic properties of strong mixing conditions. a survey and some open
questions. Probability surveys, 2(2):107–144, 2005.
[11] S. Chatterjee. Assumptionless consistency of the Lasso. ArXiv e-prints 1303.5817, 2013.
[12] S. Chatterjee and J. Jafarov. Prediction error of cross-validated Lasso. ArXiv e-prints
1502.06291, 2015.

27

[13] X. Chen. Penalized sieve estimation and inference of seminonparametric dynamic models:
A selective review. In D. Acemoglu, M. Arellano, and E. Dekel, editors, Advances in
Economics and Econometrics, volume 3, pages 485–544. Cambridge University Press, 2013.
[14] X. Chen and T. M. Christensen. Optimal Sup-norm Rates, Adaptivity and Inference in
Nonparametric Instrumental Variables Estimation. ArXiv e-prints 1508.03365, 2015.
[15] X. Chen, L. P. Hansen, and M. Carrasco. Nonlinearity and temporal dependence. Journal
of Econometrics, 155:155–169, 2010.
[16] X. Chen and Z. Liao. Asymptotic properties of penalized m estimators with time series
observations. In X. Chen and N. R. Swanson, editors, Recent Advances and Future Directions in Causality, Prediction, and Specification Analysis, pages 97–120. Springer New
York, 2013.
[17] X. Chen and D. Pouzo. Estimation of nonparametric conditional moment models with
possibly nonsmooth generalized residuals. Econometrica, 80(1):277–321, 2012.
[18] X. Chen and X. Shen. Sieve extremum estimates for weakly dependent data. Econometrica,
66(2):289–314, 1998.
[19] X. Chen and H. White. Improved rates and asymptotic normality for nonparametric neural
network estimators. Information Theory, IEEE Transactions on, 45(2):682–691, 1999.
[20] X. Chen, W. W. Wu, and Y. Yi. Efficient estimation of copula-based semiparametric
markov models. The Annals of Statistics, 37(6B):4214–4253, 2009.
[21] F. D. Côté, I. N. Psaromiligkos, and W. J. Gross. A Chernoff-type Lower Bound for the
Gaussian Q-function. ArXiv e-prints 1202.6483, 2012.
[22] J. Dedecker and S. Louhichi. Maximal inequalities and empirical central limit theorems.
In H. Dehling, T. Mikosch, and M. Sorensen, editors, Empirical Process Techniques for
Dependent Data, pages 137–159. Birkhäuser Boston, 2002.
[23] P. Doukhan, P. Massart, and E. Rio. Invariance principles for absolutely regular empirical
processes. Annales de l’institut Henri Poincar (B) Probabilits et Statistiques, 31(2):393–
427, 1995.
[24] R. M. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian
processes. J. Functional Analysis, 1:290–330, 1967.
[25] P.P.B. Eggermont and V.N. LaRiccia.
Springer, 2001.

Maximum Penalized Likelihood Estimation.

[26] J. Fan, J. Lv, and L. Qi. Sparse high-dimensional models in economics. Annual Review of
Economics, 3(1):291–317, 2011.
[27] R. Gallant and D. W. Nychka. Semi-nonparametric maximum likelihood estimation.
Econometrica, 55(2):363–390, 1987.
[28] S. Geman and C.-R. Hwang. Nonparametric maximum likelihood estimation by the method
of sieves. The Annals of Statistics, 10(2):401–414, 06 1982.
[29] U. Grenander. Abstract Inference. Wiley, 1981.
[30] B. E. Hansen. Inference when a nuisance parameter is not identified under the null hypothesis. Econometrica, 64(2):413–430, 1996.
[31] J. L. Horowitz. Adaptive nonparametric instrumental variables estimation: Empirical
choice of the regularization parameter. Journal of Econometrics, 180(2):158 – 173, 2014.
[32] R. Koenker. Quantile regression for longitudinal data. Journal of Multivariate Analysis,
91(1):74–89, 2004.
[33] R. Koenker and G. Bassett Jr. Regression quantiles. Econometrica, pages 33–50, 1978.

28

[34] R. Koenker and K. F. Hallock. Quantile regression. Journal of Economic Perspectives,
15(4):143–146, 2001.
[35] R. Koenker and Z. Xiao. Quantile autoregression. Journal of the American Statistical
Association, 101(475):980–990, 2006.
[36] O. V. Lepskii. On a problem of adaptive estimation in gaussian white noise. Theory of
Probability & Its Applications, 35(3):454–466, 1991.
[37] P. Massart. Concentration inequalities and model selection, volume 6. Springer, 2007.
[38] F. Merlevede and M. Peligrad. On the coupling of dependent random variables and applications. In H. Dehling, T. Mikosch, and M. Sorensen, editors, Empirical Process Techniques
for Dependent Data, pages 171–193. Birkhäuser Boston, 2002.
[39] S. N. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu. A unified framework for highdimensional analysis of m-estimators with decomposable regularizers. Statistical Science,
27(4):538–557, 11 2012.
[40] M. Ossiander. A central limit theorem under metric entropy with L2 bracketing. The
Annals of Probability, 15(3):897–919, 07 1987.
[41] S. Pereverzev and E. Schock. On the adaptive selection of the parameter in regularization
of ill-posed problems. SIAM Journal on Numerical Analysis, 43(5):2060–2076, 2006.
[42] D. Pouzo. On the Non-Asymptotic Properties of Regularized M-estimators. ArXiv e-prints
1512.06290, 2015.
[43] J. L. Powell. Chapter 41 estimation of semiparametric models. In Handbook of Econometrics, volume 4, pages 2443 – 2521. Elsevier, 1994.
[44] E. Rio. Covariance inequalities for strongly mixing processes. Annales de l’institut Henri
Poincar (B) Probabilits et Statistiques, 29(4):587–597, 1993.
[45] E. Rio. Inequalities and limit theorems for weakly dependent sequences. Lecture, 2013.
[46] R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970.
[47] J. Shao. An asymptotic theory for linear model selection. Statistica Sinica, 7(2):221–264,
1997.
[48] X. Shen. On methods of sieves and penalization. The Annals of Statistics, 25(6):2555–2591,
12 1997.
[49] X. Shen and W. H. Wong. Convergence rate of sieve estimates. The Annals of Statistics,
22(2):580–615, 06 1994.
[50] S. Song and P. J. Bickel. Large Vector Auto Regressions. ArXiv e-prints 1106.3915, 2011.
[51] M. Talagrand. Majorizing measures: the generic chaining. The Annals of Probability,
24(3):1049–1103, 07 1996.
[52] M. Talagrand. The Generic Chaining. Springer Monographs in Mathematics. SpringerVerlag, 2005.
[53] M. Talagrand. Upper and Lower Bounds for Stochastic Processes. A Series of Modern
Surveys in Mathematics. springer-Verlag, 2014.
[54] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal
Statistical Society. Series B (Methodological), 58(1):267–288, 1996.
[55] S. van de Geer. Generic chaining and the ℓ1 -penalty. Journal of Statistical Planning and
Inference, 143(6):1001 – 1012, 2013.
[56] S. van de Geer and P. Bülmann. Statistics for High-Dimensional Data. Springer series in
Statistics. Springer, 2011.

29

[57] A.W. van der Vaart and J. Wellner. Weak Convergence and Empirical Processes with
Applications to Statistics. Springer-Verlag New York, 1996.
[58] V. A. Volkonskii and Yu. A. Rozanov. Some limit theorems for random functions. i. Theory
of Probability & Its Applications, 4(2):178–197, 1959.
[59] A. Wald. Note on the consistency of the maximum likelihood estimate. The Annals of
Mathematical Statistics, 20(4):595–601, 12 1949.
[60] L. Wang, Y. Wu, and R. Li. Quantile regression for analyzing heterogeneity in ultra-high
dimension. Journal of the American Statistical Association, 107(497):214–222, 2012.
[61] L. Wasserman. All of Nonparametric Statistics. Springer New York, 2006.
[62] H. White and J. Wooldridge. Some results on sieve estimation with dependent observations.
In W.A. Barnett, J. Powell, and G. Tauchen, editors, Non-parametric and Semi-parametric
Methods in Econometrics and Statistics, pages 459–493. Cambridge University Press, 1991.
[63] W. B. Wu, K. Yu, and G. Mitra. Kernel conditional quantile estimation for stationary
processes with application to conditional value-at-risk. Journal of Financial Econometrics,
6(2):253–270, 2008.
[64] Y. Wu and Y. Liu. Variable selection in quantile regression. Statistica Sinica, pages 801–
817, 2009.
[65] B. Yu. Rates of convergence for empirical processes of stationary mixing sequences. The
Annals of Probability, 22(1):94–116, 1994.
[66] E. Zeidler. Nonlinear Functional Analysis and its Applications, volume III. Springer-Verlag,
1985.

30

Appendix
A

On the Properties of the Parameter Set, Regularized
Parameter Set and “Bias” term

The next assumption is sufficient for ν(P) being non-empty. Let τ be a topology over Θ
which might differ from the one induced by ||.||Θ ; it coincides with the one in the Definition of
Regularization structure.
Assumption A.1. There exists M0 > inf θ∈Θ Q(θ, P), such that {θ ∈ Θ | Q(θ, P) ≤ M } is
τ -compact for all M ≤ M0 .
Assumption A.1 is relatively weak, especially because the topology τ can be weaker than the
one induced by ||.||Θ ; see [17] for a discussion in the context of semi-/non-parametric estimation.
Lemma A.1. Suppose assumption A.1 holds. Then, ν(P) is non-empty.
Proof of Lemma A.1 . Let Θ(M0 ) = {θ ∈ Θ | Q(θ, P) ≤ M0 }. The set is τ -compact and since
M0 > inf θ∈Θ Q(θ, P), Θ(M0 ) is non-empty. Consider arg minθ∈Θ(M0 ) Q(θ, P). By assumption,
Q(·, P) : Θ(M0 ) ⊆ Θ → R is τ lower semi-continuous relative to Θ(M0 ) (see Definition 38.5
in [66]). By Theorem 38.B in [66], arg minθ∈Θ(M0 ) Q(θ, P) is non-empty. This establishes the
desired result since any θ outside Θ(M0 ) will yield a strictly large value than minθ∈Θ(M0 ) Q(θ, P).
The next lemma establishes existence of the regularized parameter set.
Lemma A.2. Suppose assumption A.1 holds. Then, for any k ∈ N, νk (P) is non-empty.
Proof of Lemma A.2 . From the definition of a regularization structure and assumption A.1,
Qk is τ - lower-semicompact. Since Θk is closed, {θ ∈ Θk : Qk (θ, P) ≤ M } is τ -compact for all
M ≤ M0 . The proof follows along the same lines of the one in Lemma A.1.
The next Lemma provides sufficient conditions to ensure that the “bias” term vanishes.
Lemma A.3. Suppose assumption A.1 holds. Then, if Q(·, P) is u.s.c. under the τ -topology,
then limk→∞ Bk (P) = 0.
Q
Q
A.3. Suppose Q(·, P) is u.s.c. Let ( k ν(P))k be such that k ν(P) ∈ Θk for
Proof of LemmaQ
condition 2
each k ∈ N and k ν(P) converges to ν(P) under τ . Such sequence exists because
Q
in the definition of regularization structure. Moreover,
Q
(ν
(P),
P)
≤
Q
(
ν(P),
P) for all
k k
k
k
Q
k ∈ N. It is enough to show that the limit of Qk ( k ν(P), P) vanishes.
A.1 and the condition of u.s.c., Q(·, P) is continuous under τ and thus
Under assumption
Q
limk→∞ Q( k ν(P), P) = Q(ν(P), P). By conditionQ3 in the definition of regularization structure, P en is τ -continuous
and thus limk→∞ P en( k ν(P), P) = P en(ν(P)) < ∞ and thus
Q
limk→∞ λk P en( k ν(P), P) = 0.

Remark A.1. If, in addition, Θk ↑. Then k 7→ Bk (P) is non-increasing. To show this, take
k1 ≤ k2 . Then, since k 7→ λk is non-increasing, it follows that Qk2 (., P) ≤ Qk1 (., P). Moreover,
Θk1 ⊆ Θk2 , then since νk (P) is a minimizer, Qk2 (νk2 (P), P) ≤ Qk1 (νk1 (P), P). △

B

Proofs of Results in Section 4

Following [53] p. 13, for any metric space T , stochastic process (Xt )t∈T and A ⊆ T , we define
supt∈A Xt as


sup Xt = sup sup Xt ; F ⊆ A, F f inite .
t∈A

t∈F

31

B.1

Proof of Theorem 4.1

Proof of Theorem 4.1. Throughout the proof, fix a (n, k). We divide the proof into several
steps. We note that for u ∈ [0, G0 ] the bound is trivial, so we focus on u ≥ G0 ≥ 1.
Step 1. It follows that
|δP (θ, ν(P))|2 ≤ |δk,P (θ, νk (P))|2 + Bk (P).
Therefore



p
p
P (δP (θ, ν(P)) ≥ u̺n,k (ω)) ≤ P δk,P (θ, ν(P)) + Bk (P) ≥ u Vn,k (ω) + Bk (P) .

Thus, for any u ≥ 1, it suffices to show that P (δk,P (θ, ν(P)) ≥ uVn,k (ω)) ≤ g0 (u).
In order to do this, note that
P (δk,P (νk (Pn ), νk (P)) ≥ uVn,k (ω))
∞
X

≤
P 2l uVn,k (ω) ≥ δk,P (νk (Pn ), νk (P)) ≥ 2l−1 uVn,k (ω)
l=1

≡

∞
X

Pn,k (l).

l=1

We now bound Pn,k (l) for each l ∈ {1, 2, ...}.
Step 2. Let Mn,k (ω) = Qk (θk , Pn ) + ηn for some θk ∈ Θk . Let, for any r > 0,
In,k (ω)(r) ≡ {θ ∈ Θk (Mn,k (ω)) | r ≥ δk,P (θ, νk (P)) ≥ 0.5r},
and On,k (ω)(r) ≡ Θk (Mn,k (ω)) \ In,k (ω)(r). Observe that these are random sets. By definition,
Qk (νk (Pn ), Pn ) ≤ Qk (θk , Pn )+ηn , and thus νk (Pn ) ∈ Θk (Mn,k (ω)). Observe that Θk (Mn,k (ω))
is also a random set. We also note that νk (Pn ) ∈ {θ ∈ Θk : Q(θ, Pn ) ≤ Mn,k (ω)} (which is also
a random set). We will
Pnuse this set and Θk (Mn,k (ω)) interchangeably.
Let Ln (θ) ≡ n−1 i=1 φ(Zi , θ) − EP [φ(Z, θ)]. Observe that


Pn,k (l) = P
inf
Qk (θ, Pn ) ≤
inf
Qk (θ, Pn ) + ηn ,
θ∈In,k (ω)(2l uVn,k (ω))

θ∈On,k (ω)(2l uVn,k (ω))

and that νk (P) ⊆ On,k (ω)(2l uVn,k (ω)). And also that, for any r > 0,
inf

Qk (θ, Pn ) − Qk (νk (P), Pn )

inf

{Qk (θ, P) − Qk (νk (P), P) + Ln (θ) − Ln (νk (P))}

inf

Qk (θ, P) − Qk (νk (P), P) −

θ∈In,k (ω)(r)

=
≥

42

θ∈In,k (ω)(r)
θ∈In,k (ω)(r)

sup
θ∈In,k (ω)(r)

|Ln (θ) − Ln (νk (P))|.

Thus, taking r = 2l uVn,k (ω), it follows that

Pn,k (l) ≤P
inf
Qk (θ, P) − Qk (νk (P), P)
θ∈In,k (ω)(2l uVn,k (ω))
!
≤

42

sup

θ∈In,k (ω)(2l uVn,k (ω))

|Ln (θ) − Ln (νk (P))| + ηn

.

If νk (P) is a set, to construct Ln (.) at νk (P), we take one element, which we still denote as νk (P).

32

Step 3. Note that (δk,P (θ, νk (P)))2 = Qk (θ, P) − Qk (νk (P), P) for any θ ∈ Θk . Thus by
the previous step
!
Pn,k (l) ≤P (2l−1 uVn,k (ω))2 ≤

sup

θ∈In,k (ω)(2l uVn,k (ω))

≤P (2l−1 uVn,k (ω))2 ≤ (2l u)γn,k (2l u) + ηn
+P

sup
θ∈In,k (ω)(2l uVn,k (ω))

|Ln (θ) − Ln (νk (P))| + ηn



sup

θ∈In,k (ω)(2l uVn,k (ω))

l

!

l

l

!

|Ln (θ) − Ln (νk (P))| ≥ (2 u)γn,k (2 u)



≤P (2l−1 uVn,k (ω))2 ≤ (2l u) γn,k (2l u) + ηn
+P

l

|Ln (θ) − Ln (νk (P))| ≥ (2 u)γn,k (2 u)

√
where γn,k (2l u) ≡ γn (In,k (ω)(2l uVn,k (ω)))/ n; the last line√follows since u ≥ 1.
For any r > 0, recall that Hn,k (ω)(r) ≡ γn (In,k (ω)(r))/ n + ηn . By definition


Hn,k (ω)(rx)
2
Vn,k (ω) = min r > 0 | r ≥ 5 max
,
x≥1
x
H

(ω)(V

(ω)x)

H

(ω)(V

(ω)2l u)

thus (Vn,k (ω))2 > 4 maxx≥1 n,k x n,k
≥ 4 n,k 2ln,k
(because x is maximal and
u
l
l−1 2
2 u ≥ 1). Multiplying at both sides by (2 u) , this result implies
Pn,k (l) ≤ P

l

sup
θ∈In,k (ω)(2l uVn,k (ω))

l

!

|Ln (θ) − Ln (νk (P))| ≥ (2 u)γn,k (2 u) .

By theorem 4.3 with A ≡ In,k (ω)(2l uVn,k (ω)), the RHS is less than g0 (2l u).
Step 4. By Step 1-3 it follows that
P (δP (θ, ν(P)) ≥ u̺n,k (ω)) ≤

B.2

∞
X

g0 (2l u) = G0 u−1

l=1

∞
X
l=1

2−l ≤ G0 u−1 .

Proof of Theorem 4.2

Proof of Theorem 4.2. Fix any r > 2. Suppose that, for any s > 0,
Hn,k (ω)(s) ≤

γ(In,k (ω)(s), 21/r ||.||Lr (P) )
p
+ ηn .
n(β)



Then, Vn,k (ω) ≤ min s > 0 | s ≥ 5 maxx≥1


γ(In,k (ω)(sx),21/r ||.||Lr (P) )

√

n(β)

sx



+ηn 

. To show this, sup-



pose the minimum in the RHS is attained (if not, the proof follows by using subsequences); denote it as v. We show the result by means of contradiction. That is, suppose that Vn,k (ω) > v.
γ(In,k (ω)(vx),21/r ||.||Lr (P) )

√

n(β)

+ηn

H

(ω)(vx)

We know that v ≥ maxx≥1
≥ maxx≥1 n,k vx
. But this contravx
dicts that Vn,k (ω) is minimal.
Therefore, we need to establish the first display. By definition, for any k = 0, 1, 2, ..., the
k+1
quantity qn,k is the minimal q ∈ Qn such that 0.5 β(q)
≤ 2 n . Since q 7→ β(q)/q is nonq
R1
R1
r
r
increasing, it follows that qn,k ≤ qn,0 . Consequently 0 |µqn,k (u)| r−2 du ≤ 0 |µqn,0 (u)| r−2 du.

33

R
 r−2
r
2r
1
Hence, by display 17, ||.||qn,k ≤ 2(r−2)/(2r) 0 |µqn,0 (u)| r−2 du
21/r || · ||Lr (P) for any k =
0, 1, 2, ....
This implies that for any k = 0, 1, 2, ... and any f ,
||S(f, Tk )||qn,k

√
≤ 2

Z

1

|µqn,0 (u)|

0

r
r−2

du

 r−2
2r

||S(f, Tk )||Lr (P) .

By our definition of γn : For any A ⊆ Θ,
√ X k/2
√
2
γn (A) ≤ 2 inf sup 2
k

√
= 2

Z

1

√
= 2

Z

1

0

=2

1

0

|µqn,0 (u)|

du

 r−2
2r

|µqn,0 (u)| r−2 du

 r−2
2r

|µqn,0 (u)|

0

Z

(r−2)/(2r)

r
r−2

r

Z

0

1

|µqn,0 (u)|

r
r−2

r
r−2

du

 r−2
2r

||S(f, Tk )||Lr (P)

√ X k/2
2 ||S(f, Tk )||Lr (P)
inf sup 2
k

γ(A, ||.||Lr (P) )

du

 r−2
2r

γ(A, 21/r ||.||Lr (P) ).

Hence, by setting A = In,k (ω)(s), the result follows from the definition of Hn,k .

B.3

Proof of Proposition 4.2, Proposition 4.1 and Proposition 4.3

Proof of Proposition 4.1. The proof is analogous to the one of Theorem 4.1, so we only present
a sketch highlighting the discrepancies. Recall that ̟(·, νk (P)) = inf θ0 ∈νk (P) ̟(·, θ0 ).
As in the proof of Theorem 4.1, it suffices to show, for any l = 1, 2, ...,


P 2l uṼn,k (ω) ≥ ̟(νk (Pn ), νk (P)) ≥ 2l−1 uṼn,k (ω) ≤ g0 (2l u)
foru ≥ 1. The RHS is bounded by

P inf θ∈In,k (ω)(2l uṼn,k (ω)) Qk (θ, Pn ) ≤ inf θ∈Θn,k (Mn,k )\In,k (ω)(2l uṼn,k (ω)) Qk (θ, Pn ) . Our goal is

to bound this quantity by g0 (2l u). We note that here, for any r > 0 In,k (ω)(r) = {θ ∈
Θk (Mn,k (ω)) | r ≥ ̟(θ, νk (P)) ≥ 0.5r} ⊆ {θ ∈ Θk (Mn,k (ω)) | ̟(θ, νk (P)) ≥ 0.5r}. So by
assumption 4.1, for any r > 0
Qk (θ, P) − Qk (νk (P), P) ≥ ̟(θ, νk (P))2 (̟k (Mn,k (ω), 0.5r))2 ≥ (0.5r)2 (̟k (Mn,k (ω), 0.5r))2
for any θ ∈ In,k (ω)(r). Taking, r = 2l uṼn,k (ω), it follows that



P (2l−1 uVn,k (ω)̟k (Mn,k (ω), 2l−1 uṼn,k (ω)))2 ≤ 2l u γn,k (2l u) + ηn
!

γn,k (2l u) + ηn
2
.
⇐⇒ P (Ṽn,k (ω)) ≤ 4
2l u(̟k (Mn,k (ω), 2l−1 uṼn,k (ω)))2
n
Since Ṽn,k (ω) = min r > 0 : r2 ≥ 5 maxx≥1

{γn,k (x)+ηn }
x(̟ k (Mn,k (ω),0.5xr))2

o

, it follows that Ṽn,k (ω)2 >

{γn,k (2 u)+ηn }
{γ
(x)+ηn }
4 maxx≥1 x(̟ (M n,k
≥ 4 2l u(̟ (M (ω),2l−1 uṼ (ω)))2 . Thus, the probability in
2
n,k (ω),0.5xṼn,k (ω)))
n,k
n,k
k
k
the previous display is zero.
By using this observation and analogous algebra to the one in the proof of Theorem 4.1, it
follows
that in order to achieve our goal if suffices to bound 

P supθ∈In,k (ω)(2l uṼn,k (ω)) |Ln (θ) − Ln (νk (P))| ≥ 2l uγn,k (2l u) by g0 (2l u). Its steps are identical to those in the proof of Theorem 4.1 and thus omitted.

34

l

Proof of Proposition 4.2. Let πn,k (ω) =
A ≥ 1,

δP (νk (Pn ),ν(P))
̺k,n (ω)

for any ω ∈ Ω. Observe that, for any

EP [πn,k (ω)] =EP [πn,k (ω)1{πn,k (ω) ≥ A}] + EP [πn,k (ω)1{πn,k (ω) ≤ A}] .
By assumption, the first term in the RHS, is bounded above by ϕn,k (A). Regarding the second
term, by Theorem 4.1, it follows that

Z 1 
δP (νk (Pn ), ν(P))
≥ t dt
EP [πn,k (ω)1{πn,k (ω) ≤ A}] ≤
P
̺k,n (ω)
0

Z A 
δP (νk (Pn ), ν(P))
+
P
≥ t dt
̺k,n (ω)
1
Z A
≤1 +
g0 (t)dt = 1 + G0 ln(A).
1

Since A ≥ 1 is arbitrary, we can choose the minimal value.
(r−2)/(2r)
√ R 1
r
, for any r > 2. The next lemma
In what follows let Br (q) = 2 0 |µq (u)| r−2
solves for q 7→ Br (q) for different cases of β.
Lemma B.1. Let m0 > 0. For any n, any q ∈ Qn and any r > 2, the following hold:
1. If β(q) = 1{q < m−1
0 }, then
q
min{1 + q, 1 + m−1
0 },
q
and Br (q) ≥ 21/r min{1 + q, m−1
0 }.

Br (q) ≤ 21/r

2. If β(q) = (1 + q)−m0 with m0 >

r
r−2 ,

Br (q) ≤ 2

then
m0
r
m0 − r−2

1/r

!(r−2)/(2r)

and
Br (q) ≥ 21/r 2−m0
3. If β(q) = (1 + q)−m0 with m0 =

r
r−2 ,

then

 r−2
2r

.

1

Br (q) ≤ 21/r (m0 log(1 + q) + 1) 2m0 ,
and
√
1
Br (q) ≥ 21/r 0.5 (m0 log(1 + 0.5q) + 2m0 ) 2m0
4. If β(q) = (1 + q)−m0 with m0 <
Br (q) ≤ 2

1/r

r
r−2 ,

then

r
r−2
r
r−2

− m0

!(r−2)/(2r)

(1 + q)

r−(r−2)m0
2r

and
Br (q) ≥ 21/r

2−m0 m0
r
r−2 − m0

! r−2
2r

35

r

((1 + 0.5q) r−2 −m0 − 1)

r−2
2r

Proof. See the Online Appendix OA.4.
Proof of Proposition 4.3. Given our definition of n(β) and our notation, it suffices to provide
upper and lower bounds on Br (q). Throughout the proof, r is fixed to an arbitrary value r > 2.
(1) Note that qn,0 is such that β(qn,0 )/qn,0 ≤ n4 . Recall that for any x ∈ R+ , [x] is the
smallest element, s in Qn such that s ≥ x.
Observe that β(qn,0 )/qn,0 ≤ 1/qn,0 , so any value of qn,0 ≥ 0.25n will satisfy the restriction β(qn,0 )/qn,0 ≤ n4 . Thus, qn,0 = [0.25n]. Therefore, by Lemma B.1(1), Br (qn,0 ) ≤
q
n
21/r min{1 + [0.25n], 1 + m−1
0 }. Therefore, n(β) ≥ min{1+[0.25n],1+m−1 } . Also, Br (qn,0 ) ≥
0
q
−1
n
n
1/r
min{1 + [0.25n], m0 }, and thus n(β) ≤ 22/r min{1+[0.25n],m−1 } ≤ min{1+0.25n,m
2
−1 .
}
0

0

(2) It is easy to see that by Lemma B.1(2), a bound for Br (q) does not depend on q and
thus the result holds with n(β) ≥  m (r−2)n (r−2)/r . The lower bound for Br (q) in Lemma
0
m0 (r−2)−r

n
(2−m0 )(r−2)/r

B.1(2) implies that n(β) ≤

h

.

Br (qn,0 ) ≤ 2

1/r




n 1/(m0 +1)
4

i

1/(m0 +1)
and also that qn,0 ≥ n4
− 1. To
h 
i
n 1/(m0 +1)
−(m0 +1)
show this note that β(q)/q ≤ q
. If qn,0 >
, then by definition of the
4

1/(m
+1)
0
operator [.] there exists a s ∈ Qn such that qn,0 > s ≥ n4
. Thus n4 > s−(1+m0 ) ≥
β(s)/s. But this contradicts the fact that qn,0 is minimal in Qn such that β(s)/s ≤ n4 . Clearly,
1/(m0 +1)
− 1.
(qn,0 )−(m0 +1) ≤ n4 and thus qn,0 ≥ n4
Thus, by Lemma B.1(3),
(3) We first establish that qn,0 ≤

 2m1
  1 
0
n m0 +1
)+1
m0 log(1 +
,
4

and
Br (qn,0 ) ≥ 2

1/r



 2m1
 n  m 1+1 
√
0
0
m0
+2
0.5 m0 log 0.5 + 0.5
,
4

These inequalities imply that
n
 m1
 1 i
0
n m0 +1
)
+
1
4
n
and n(β) ≤
 m1 .


 1 
0
0.5 m0 log 0.5 + 0.5 n4 m0 +1 + 2m0
n(β) ≥ 
h
m0 log(1 +

(4) We can obtain the same bound for qn,0 as in point (3), so by Lemma B.1(4),
Br (qn,0 ) ≤ 2

1/r

0 
(r−2)/(2r)

  1  r−(r−2)m
2r
r
n m0 +1
,
1+
4
r − m0 (r − 2)

and
Br (qn,0 ) ≥ 2

1/r

! r−2
r

(r−2)/(2r)
2r  −m
−m0
 n  m 1+1  r−2
2 0 m0 (r − 2)
0
0.5(1 +
)
−1
4
r − m0 (r − 2)

The result follows from analogous calculations to those in step (3).

36

B.4

Proof of Theorem 4.3

To simplify notation P
we use F to denote F (A). For any (Zi )i = ω ∈ Ω and any f ∈
n
−1
∗
∗
F , let
L
(f
)
=
n
∈ Ω, let L∗n (f ) =
n
i=1 f (Zi ) − EP [f (Z)], and for any (Zi )i = ω
Pn
∗
−1
∗
n
i=1 f (Zi ) − EP∗ [f (Z)]. Recall that the Z ’s were constructed in Section 3.
Observe that the following equivalence holds: For any f ∈ F and its corresponding θ, i.e.,
f = φ(., θ) − φ(., νk (P)), it follows that
Ln (f ) = Ln (θ) − Ln (νk (P)).

(26)

(Recall that φ(., νk (P)) is defined as φ evaluated at some element of νk (P) which is chosen a
priori).
Hence, in order to establish the expression in Theorem 4.3 it suffices to show
!
γn (A)
≤ g0 (u).
(27)
P sup |Ln (f )| ≥ u √
n
f ∈F
In order to show this we need some lemmas (the proofs are relegated to the Online Appendix
OA.5).
For each k, given a partition Tk , let πk (f ) a point in T (f, Tk ) with π0 (f ) = 0 (recall that
T0 = {F } and 0 ∈ F ). Let ∆k f ≡ πk (f ) − πk−1 (f ) and Ξk (f ) = −f + πk (f ).
The next lemma is essentially the first part of the Chaining argument in the proof of the
CLT for empirical processes, see [57] Ch. 2.5.
Lemma B.2. For any admissible partition sequence of F , (Tn )n , any f ∈ F , any (vk )k with
vk : F → RZ , and any (ak )k with ak ≥ 0,
f=

∞
X

k=1

∆k f 1{m(f )≥k∩|vk (f )|≤ak } −

− Ξ0 (f )1m(f )=0 ,

∞
X

k=1

Ξk−1 (f )1{m(f )=k∩|vk (f )|>ak }

where m(f ) = min{j | |vj (f )| > aj }.
Proof. See the Online Appendix OA.5.
Observe that ∆k f = Ξk (f ) − Ξk−1 (f ) and
|Ξk (f )| = |πk (f ) − f | ≤ S(f, Tk ), ∀k, f

(28)

since both f and πk (f ) are in T (f, Tk ).
The next lemma, uses the decomposition in Lemma B.2 to provide an upper bound for the
LHS of display 27.
Lemma B.3. For any admissible partition sequence of F , (Tn )n , any (vk )k with vk : F → RZ ,
any (ak )k with ak ≥ 0, the following holds: For all Γ = Γ1 + Γ2 + Γ3 with Γl ≥ 0, all u ≥ 0,
and all n ∈ N,
!
!
2
∞
X
X
l
(29)
P sup |Ln (f )| ≥ uΓ ≤
P sup |Ln (
gk (f ))| ≥ uΓl
f ∈F

l=1

+P

f ∈F

k=1

sup |Ln (Ξ0 (f )1{m(f )=0} )| ≥ uΓ3

f ∈F

with, z 7→ gk1 (f )(z) ≡ ∆k (f )(z)1{m(f,z)≥k∩|vk (f )(z)|≤ak } and
z 7→ gk2 (f )(z) ≡ Ξk−1 (f )(z)1{m(f,z)=k∩|vk (f )(z)|>ak } .
Proof. See the Online Appendix OA.5.

37

!

(30)

We use the previous lemmas with the following choices for (vk (f ))k and (ak )k : For any
(n, k) ∈ N2
bn,k (f, Tk )
vk (f ) =S(f, Tk ), and an,k (f, Tk ) =
qn,k
√
nδ(f, Tk )
with bn,k (f, Tk ) =B0 √
,
2k+1
and δ(f, Tk ) =||S(f, Tk )||qn,k , and B0 = pυ .

(31)
(32)
(33)

Recall that pυ defines (among other things) the possible values of n; see Online Appendix OA.1
for details. To simplify the notation, most of the time we use: Sk (f ), ak and bk to denote
S(f, Tk ), an,k (f, Tk ) and bn,k (f, Tk ) resp. We also use qk instead of qn,k .
Set
 γ (A)

γn (A)
n
√
Γ1 = EC0 + 4B0 + 23/2
≡ E1 √
n
n
!
2

γn (A)
γn (A)
2
√
C0 + 4B0 + 23/2
≡ E2 √
Γ2 = E
15
e
n
n
γn (A)
γn (A)
Γ3 =4 √
≡ E3 √
n
n
∞
X
j−1
8
(2/e33 )2
and E = × B0 ,
with C0 =
3
j=1
in the Lemma B.3. In order to proof the Theorem, we claim that it suffices to show that: For
all u ≥ 33, 43
!
∞
X
P sup |Ln (
gkl (f ))| ≥ uΓl ≤ 1/u, f or l = 1, 2
f ∈F

k=1

and
P

sup |Ln (Ξ0 (f )1{m(f )=0} )| ≥ uΓ3

f ∈F

!

≤ 1/u.

Because, if this is the case, then by Lemma B.3, it follows that
γn (A)
P sup |Ln (f )| ≥ u (E1 + E2 + E3 ) √
n
f ∈F

!

≤ 3/u,

which implies, for any u ≥ 33 (which implies that it holds for any u ≥ 0.5G0 ),
!
γn (A)
3
P sup |Ln (f )| ≥ u √
≤ (E1 + E2 + E3 ) = g0 (u).
n
u
f ∈F
After tedious algebra and noting that B0 = pυ and C0 < 0.00001, it follows that
√
E1 + E2 + E3 < pυ (8.1) + 28

(34)

and thus G0 > 3(E1 + E2 + E3 ).
Therefore, in order to establish the desired result, we need to prove the following propositions
43
The logic behind 33 is as follows. It holds that G0 > 3(E1 + E2 + E3 ), and thus G0 > 3(8B0 +
21+3/2 + 22 ) > 3 × 23 (1 + 2−0.5 + 2−1 ) > 3 × 23.5 > 33. Since we only care about u ≥ G0 and also
G0 > 33, it suffices to show the propositions below for u > 33.

38

 1
P
1
Proposition B.1. For all n, P supf ∈F |Ln ( ∞
k=1 gk (f ))| ≥ uΓ1 ≤ u , for all u ≥ 33.

P∞
Proposition B.2. For all n, P supf ∈F |Ln ( k=1 gk2 (f ))| ≥ uΓ2 ≤ u1 , for all u ≥ 33.

Proposition B.3. For all n, P supf ∈F |Ln (Ξ0 (f )1{m(f )=0} )| ≥ uΓ3 ≤ u1 , for all u ≥ 33.

Remark B.1. The constants in (Γl )l=1,2,3 essentially arise from Bernstein inequality (see the
proof of Lemma B.7) and Lemma B.6. △

B.4.1

Proofs of Propositions B.1, B.2 and B.3

We first establish the proof of Proposition B.2. Recall that z 7→ gk2 (f )(z) ≡ Ξk−1 (f )(z)1{m(f,z)=k∩|vk (f )(z)|>ak } .
The proof proceeds in several steps: gk2 (f ) is majorized by h2k (f ) = Sk−1 (f )1{m(f )=k∩|vk (f )|>ak }
which requires some re-centering by the expectation. We then use Lemmas B.4 (see below) and
Lemma B.7 (see below) to bound the centered part (this is done in Step 1) and Lemma B.6 (see
below) to bound the expectation part (this is done in Step 2). The proofs of Propositions B.1
and B.3 are slight modifications of this one. For the former, we essentially use the methodology
in Step 1 of the proof of Proposition B.2 and for the latter we essentially use the methodology
in Step 2 of the same proof.
The next lemma is a simple adaptation of the results in [23] p. 408.
Lemma B.4. Let g ∈ B ≡ {f ∈ F : ||f ||L∞ ≤ a} for some a > 0. Then, for all n


√
√
EP sup n|Ln (g) − L∗n (g)| ≤ 2 naβ(q).
g∈B

Proof. See the Online Appendix OA.5.
Pq The next lemma establishes some useful properties of ||.||q and µq . Recall that u 7→ µq =
i=0 1{u ≤ 0.5β(i)} and (u, f ) 7→ Qf (u) = inf{s | P(|f (Z)| > s) ≤ u}. The function
β −1 : [0, 1] → R+ is defined as β −1 (u) = min{s | β(s) ≤ u} — since β is right-continuous, the
min exists.
Lemma B.5. The following assertions hold:
(1) For all q ∈ N and f, g ∈ F such that |f | ≤ |g|, then ||f ||q ≤ ||g||q .
(2) For all u ∈ [0, 1], q 7→ µq (u) is non-increasing.
(3) For all u ∈ [0,1] and q ∈ N, µq (u) ≤ min{β −1 (2u)
+ 1, q + 1} and for all a ≥ 0,

R1
R1
a
−1
a
a
(µ
(u))
du
≤
0.5
(β
(v)
+
1)
dv
+
(q
+
1)
β(q)
.
q
0
β(q)
R1
−1
(4) For all u ∈ [0, 1] and q ∈ N, µq (u) ≥ min{β
(2u), q + 1} and for all a ≥ 0, 0 (µq (u))a du ≥

R1
0.5 β(q+1) (β −1 (v))a dv + (q + 1)a β(q + 1) .
Proof. See the Online Appendix OA.5.

The next lemma controls the L1 norm for f 1{f >b/qn,k } .

√
√
Lemma B.6. For all n, k and f ∈ F , let b = B0 n||f ||qn,k / 2k+1 and (qn,k )n,k as defined in
equation 10. Then
||f 1{f >b/qn,k } ||L1 ≤

√ ||f ||qn,k √
2 √
2k+1 .
n

Proof. See the Online Appendix OA.5.
The following Bernstein exponential inequality result is needed to bound “the bounded
part” of Ln (g), for any g ∈ F .

39

Lemma B.7. For any (n,√k) ∈ N2 , any q ≤ n and any b > 0 and g ∈ F such that ||g||L∞ ≤ bk−1
√
with bk−1 = B0 q −1 nb/ 2k and b ≥ ||g||q , it follows that

√
√
P∗
n|Ln (g)| ≥ u 2k bE ≤ 2 exp{−u2k }
for any u ≥ 1 and with E =

8
3

× B0 .

Proof. See the Online Appendix OA.5.
Proof of Proposition B.2. By the Markov inequality
!


P∞
∞
X
EP supf ∈F |Ln ( k=1 gk2 (f ))|
2
.
P sup |Ln (
gk (f ))| ≥ uΓ2 ≤
uΓ2
f ∈F

(35)

k=1

i
h
P∞
Thus is sufficient to show that EP supf ∈F (A) |Ln ( k=1 gk2 (f ))| ≤ Γ2 .

Let h2k (f ) =

Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } . By display 28, |Ξk−1 (f )| ≤ Sk−1 (f ) and thus |gk2 (f )| ≤ h2k (f )
and moreover,
sup |

∞
X

f ∈F (A) k=1

Ln (gk2 (f ))| ≤ sup |

∞
X

f ∈F (A) k=1
∞
X

n−1

n
X
i=1

n
X

(gk2 (f )(Zi ))| + sup |

n−1

≤ sup |

Ln (h2k (f ))| +

f ∈F (A) k=1

i=1

f ∈F (A) k=1
∞
X

EP [(gk2 (f )(Z))]|

(h2k (f )(Zi ))| + sup |

≤ sup |

f ∈F (A) k=1
∞
X

∞
X

EP [(h2k (f )(Z))]|
f ∈F (A) k=1
∞
X
2 sup
|EP [h2k (f )(Z)]|.
(36)
f ∈F (A) k=1

In the following steps we provide an upper bound for the expectation of the two terms in
the RHS.
Step 1. We show that
#
"
#
"
∞
∞
X
X
2
Ln (Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } )|
Ln (hk (f ))| =EP sup |
EP sup |
f ∈F (A) k=1

f ∈F (A) k=1

γn (A)
≤(C0 E + 4B0 )C0 √ .
n

Since for any z, such that m(f )(z) = k, it follows that |vk−1 (f )| = Sk−1
√ (f ) ≤ ak−1 and
−1 √
thus ||Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } ||L∞ ≤ ak−1 = B0 qk−1
n||Sk−1 (f )||qk−1 / 2k and
||Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } ||qk−1 ≤ ||Sk−1 (f )||qk−1 (by Lemma B.5(1)).
By Lemma B.4 (with h2k (f ) and ak−1 playing the role of g and a in the lemma)
"
"
#
#
∞
∞
X
X
√
√
2
∗
2
sup
EP sup
n|Ln (
hk (f ))| ≤EP∗
n|Ln (
hk (f ))|
f ∈F (A)

k=1

f ∈F (A)

k=1
#
∞
∞
X
X
√
∗
2
2
n|Ln (
hk (f )) − Ln (
hk (f ))|
+ EP sup
f ∈F (A)
k=1
k=1
"
#
∞
∞
X
X
√
√
∗
2
sup
≤EP∗
n|Ln (
hk (f ))| + 2
ak−1 β(qk−1 ) n.
f ∈F (A)
k=1
k=1

"

40

Moreover,
∞
X

∞
X
√
B0 ||Sk−1 (f )||qk−1 nβ(qk−1 )
√
ak−1 β(qk−1 ) n =
qk−1
2k
k=1
k=1

≤2B0
=2B0

∞
X
||Sk−1 (f )||qk−1 k
√
2
2k
k=1

∞ √
X
2k ||Sk−1 (f )||qk−1
k=1

where the first line follows from the definition of ak−1 and second line follows from the definition
of qk . Hence
"
"
#
#
∞
∞
∞ √
X
X
X
√
√
2
2
∗
∗
EP sup
sup
hk (f ))| ≤ EP
hk (f ))| + 4B0
n|Ln (
n|Ln (
2k ||Sk−1 (f )||qk−1 .
f ∈F (A)

f ∈F (A)

k=1

k=1

k=1

We now bound the first term in the RHS.
P∞ √
Recall that γn (A) = inf (Tn )n ∈T supf ∈F (A) j=1 2j ||Sj−1 (f )||qj−1 and let

n
o
√
√
Ωn (u) = ω ∗ ∈ Ω | ∀f ∀j, nL∗n (h2j (f )) ≤ uE 2j ||Sj−1 (f )||qj−1 .



P∞
√
(E is as in Lemma B.7). Note that P∗ supf ∈F (A) | nL∗n ( k=1 h2k (f ))| ≥ uEγn (F ) ≤ P∗ (Ω \ Ωn (u)).


√
√
And P∗ (Ω \ Ωn (u)) = P∗ ∃f ∃j, nL∗n (h2j (f )) ≥ uE 2j ||Sj−1 (f )||qj−1 .
By Lemma B.7 with q = qk−1 , g = h2k (f ), bk−1 = ak−1 and b = ||Sk−1 (f )||qk−1 (for these
choices is true that ||h2k (f )||L∞ ≤ bk−1 = ak−1 and ||h2k (f )||qk−1 ≤ b = ||Sk−1 (f )||qk−1 ), we
obtain that for all f and all j,

√
√
n|L∗n (h2j (f ))| ≥ u 2j ||Sj−1 (f )||qj−1 E ≤ 2 exp{−u2j }.
P∗



We also note that card g = h2k (f ), with f ∈ F (A) = card ({g = Sk−1 (f ), with f ∈ F (A)}).
Since Sk−1 (f ) = Sk−1 (f ′ ) for all f, f ′ in the same set of Tk−1 , card ({g = Sk−1 (f ), with f ∈ F (A)}) =
k−1
card(Tk−1 ) ≤ 22 .
Therefore
!
∞
√ ∗ X
2
∗
hk (f ))| ≥ uEγn (F ) ≤ P∗ (Ω \ Ωn (u))
sup | nLn (
P
f ∈F (A)

≤

∞ card(T
Xj−1 )
X
j=1
∞
X

≤2

j=1

l=1

k=1

√

√
P∗
n|L∗n (h2j (f ))| ≥ u 2j ||Sj−1 (f )||qj−1 (E)


card(Tj−1 ) exp −u2j .

Since u2j = u(2 + 2j−1 ) ≥ 2u + 332j−1 for u ≥ 33, it follows that
!
∞
∞
X
X

√
card(Tj−1 ) exp −332j−1
h2k (f ))| ≥ uEγn (F ) ≤2e−2u
P∗ sup | nL∗n (
f ∈F

j=1

k=1

j−1

2
∞ 
X
2
−2u
≤2e
e33
j=1

41

.

Let C0 =
EP∗

"

P∞

j=1

 j−1
2 2
e33

< 0.00001. Hence

# Z
∞
X
√
n|L∗n (
h2k (f ))| =
sup

f ∈F (A)

∞

!
∞
√ ∗ X
sup | nLn (
h2k (f ))| ≥ u du

P∗

f ∈F

0

k=1

=Eγn (A)

∞

Z

k=1

∗

P

0

=Eγn (A)C0

Z

∞

sup |

√

f ∈F

∞
X
nL∗n (
h2k (f ))|
k=1

!

≥ Eγn (F )t dt

2e−2t dt

0

=Eγn (A)C0 .
Therefore,
"

#
∞
∞ √
X
X
√
2
n|Ln (
hk (f ))| ≤ C0 Eγn (A) + 4B0
2k ||S(f, Tk−1 )||qk−1 ,
sup

EP

f ∈F (A)

k=1

k=1

since the (Tk−1 )k in the second term of the RHS is arbitrary, it follows that the RHS is bounded
above by (C0 E + 4B0 )γn (F ).44
Step 2. We now show that
sup

∞
X

|EP [h2k (f )(Z)]| = sup

f ∈F (A) k=1

∞
X

f ∈F (A) k=1

γn (A)
|EP [Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } ]| ≤ 23/2 √ .
n

For any z, such that m(f )(z) = k, it follows that |vk−1 (f )(z)| ≤ ak−1 and since |vk (f )| =
Sk (f ) for all k, in turn it follows that
qk−1 Sk−1 (f )(z) ≤

bk−1
bk−1
bk−1
bk ≤
qk Sk (f )(z) ≤
qk−1 Sk (f )(z).
bk
bk
bk

Where the inequalities follow because for any fix n, qk−1 ≥ qk , and also because m(f )(z) = k
b
implies Sk (f )(z) > ak . Therefore, Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } ≤ k−1
bk Sk (f )1{m(f )=k∩Sk (f )>ak } .
By Lemma B.6 with b = bn,k (f, Tk )
bk−1
||Sk (f )1{m(f )=k∩Sk (f )>ak } ||L1
bk
bk−1
≤
||Sk (f )1{Sk (f )>ak } ||L1
bk
r
bk−1 √
2k+1
2
≤
||Sk (f )||qk .
bk
n

EP [Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } ] ≤

Therefore,
sup

∞
X

f ∈F (A) k=1

√
|EP [Sk−1 (f )1{m(f )=k∩|vk (f )|>ak } ]| ≤ 2

r

∞

X√
bk−1
1
||Sk (f )||qk .
sup
2k+1
n f ∈F
bk
k=1

√
P∞
P
2k+1 ||Sk−1 (f )||qk−1
k+1 bk−1 ||S (f )||
Note that bk−1
, then ∞
k
qk =
k=1
k=1 2
bk =
||Sk (f )||qk
bk
2k
Finally, since the implied partition defining Sk−1 (f ) is arbitrary, it follows that
q

k+1
2√
||Sk−1 (f )||qk−1 .
2k

∞
∞ √
X
X
√
2k+1
√ ||Sk−1 (f )||qk−1 = 23/2 sup
2 sup
2k ||Sk−1 (f )||qk−1 ≤ 23/2 γn (A).
k
2
f ∈F (A) k=1
f ∈F (A) k=1
44

Formally, it should be (4 + ǫ)B0 for any ǫ > 0, but we omit this term.

42

Step 3. By display 35 - 36, Step 1 and Step 2 it follows that
∞
X
sup |Ln (
gk2 (f ))| ≥ uΓ2

P

f ∈F (A)

k=1

!

≤

+ 23/2 γn√(A)
(EC0 + 4B0 ) γn√(A)
n
n
uΓ2

γn (A) EC0 + 4B0 + 23/2
=u−1 √
Γ2
n

and by definition of Γ2 the RHS equals u−1 and the desired result follows.
Remark B.2. As shown in the previous proof and discussed in Section 4.2, a crucial difference
between our chaining and, say, the one in [57] Ch. 2.5 is that the latter basically bounds
the size of each link in the chain uniformly for all f , whereas we allow the size (measured by
||S(f, Tl )||qn,l ) to vary with each f . △
Proof of Proposition B.1. Recall that z 7→ gk1 (f )(z) ≡ ∆k (f )(z)1{m(f,z)≥k∩|vk (f )(z)|≤ak } . The
proof is analogous to that of Proposition B.2 so we only present a sketch. By the Markov
inequality
i
h
P∞
!
∞
EP supf ∈F (A) |Ln ( k=1 gk1 (f ))|
X
.
P
sup |Ln (
gk1 (f ))| ≥ uΓ1 ≤
uΓ1
f ∈F (A)
k=1

√
−1 √
It follows that ||gk1 (f )||L∞ ≤ ak = B0 qn,k
n||S(f, Tk )||qn,k / 2k+1 and, by lemma B.5(1),
||gk1 (f )||qn,k ≤ ||∆k (f )||qn,k ≤ ||S(f, Tk )||qn,k . By following the same steps in Step 1 of the proof
of proposition B.2,
"
#
"
#
∞
∞
∞
X
X
X
√
sup |L∗n (
gk1 (f ))| + 2
ak β(qn,k ) n.
gk1 (f ))| ≤ EP∗
EP sup |Ln (
f ∈F (A)

f ∈F (A)

k=1

k=1

k=1

We now bound the first term in the RHS. For this, we first show that
!

2
∞
X
2
∗
1
−2u
∗
sup |Ln (
gk (f ))| ≥ uEγn (A) ≤ 2e
C0 .
P
e15
f ∈F (A)
k=1

In order to do this we proceed as in Step 1 of the proof of proposition B.2. By invoking Lemma
B.7 with q = qn,k , g = gk1 (f ), bk−1 = ak and b = ||S(f, Tk )||qn,k it follows, for any j and f :
!
√
√
sup
P∗
n|L∗n (gj1 (f ))| ≥ u 2j+1 ||S(f, Tj )||qn,j (E) ≤ exp{−u2j+1 }.
f ∈F (A)

Therefore, by analogous calculations to those in the proof of Proposition B.2, it follows that
P∗

1
!
):f ∈F (A)})
∞
∞ card({gj (f
X
X
X
∗
1
exp{−u2j+1 }.
gk (f ))| ≥ uEγn (A) ≤
sup | nLn (

√

f ∈F (A)

j=1

k=1

l=1

The cardinality of {gj1 (f ) : f ∈ F (A)} is no larger than card({πj (f ) : f ∈ F (A)})×card({πj−1 (f ) :
j

f ∈ F (A)}) ≤ 22
P∗

+2j−1

, thus — since u ≥ 33 and 2j ≥ 2 for all j ≥ 1, u2j ≥ u2 + 15 × 2j —
!
∞
∞
X

√ ∗ X
j
j−1
1
sup | nLn (
22 +2 exp −15 × 2j+1
gk (f ))| ≥ uEγn (A) ≤2e−2u

f ∈F (A)

j=1

k=1

j+1

≤2e

43

−2u

2
∞ 
X
2
e15
j=1

= 2e

−2u



2
e15

2

C0 ,

because 2j−1 + 2j ≤ 2j+1 .
Therefore, by following the steps in step 1 of the proof of proposition B.2
"
# 
2
∞
X
2
γn (A)
∗
1
sup |Ln (
gk (f ))| ≤
EP∗
C0 E √ .
15
e
n
f ∈F (A)
k=1

Also
∞
X

k=1

∞ √
X
√
2k+1 ||S(f, Tk )||qk ,
ak β(qk ) n ≤ 2B0
k=1

√
P
with γn (A) = inf (Tl )l ∈T supf ∈F (A) ∞
2j+1 ||S(f, Tj )||qj . Finally, since the partition implied
j=0
P∞ √ k+1
by the term k=1h 2
||S(f, Tk )||qk is arbitrary,
bound the term
by γn (A).
i we
 can


P∞ 1
γn (A)
2 2
Therefore EP supf ∈F (A) |Ln ( k=1 gk (f ))| ≤ e15 C0 E + 6B0 √n .
Proof of Proposition B.3. By the Markov inequality and analogous calculations to those in the
Proof of Proposition B.2, it suffices to show
"
#
EP

sup |Ln (S0 (f )1{m(f )=0} )| ≤ 23/2 n−1/2 γn (A)

(37)

f ∈F (A)

and
sup EP [S0 (f )1{m(f )=0} ] ≤ 21/2 n−1/2 γn (A)

(38)

f ∈F (A)

We now
establish equation 38. The fact that m(f ) = 0 implies that S0 (f ) > a0 =
√
nδ0 / 2
B0 q0 . Thus, by Lemma B.6 with f (in the lemma) equal to S0 (f ) and noting that
b = bn,0 (f, T0 ) satisfies the condition, it follows that
√

EP [S0 (f )1{m(f )=0} ] =||S0 (f )1{S0 (f )>a0 } ||L1
r
√
2
≤ 2
||S0 (f )||q0 .
n
√
Clearly, the RHS is bounded above by n−1/2 2γn (F ).
In order to establish equation 37. We first note that T (f, T0 ) = F (A) and thus z 7→
S0 (f )(z) = supf1 ,f2 ∈T (f,T0 ) |f1 (z) − f2 (z)| = supf1 ,f2 ∈F |f1 (z) − f2 (z)| which does not depend
on f ; we denote this function as z 7→ σ0 (z). Consequently supf ∈F (A) |Ln (S0 (f )1S0 (f )>a0 )| =
|Ln (σ0 1σ0 >a0 )|. Thus
#
"
EP

sup |Ln (S0 (f )1S0 (f )>a0 )| ≤ EP [|Ln (σ0 1σ0 >a0 )|] ≤ 2||σ0 1σ0 >a0 ||L1 .

f ∈F (A)

q
√ q
By Lemma B.6 with f = σ0 , 2||σ0 1σ0 >a0 ||L1 ≤ 2 2 n2 ||σ0 ||q0 = 23/2 n2 ||S0 (f )||q0 . The

desired result follows since the last term is clearly bounded by 23/2 n−1/2 γn (A).

C

Proofs of Proposition 4.4 and Proposition 4.5

Proof of Proposition 4.4. Let
γ̄(A, d) =

inf

sup

(Sl )l ∈S θ∈A

∞
X
l=0

2l/2 Diam(T (θ, Sl ), d),

44

where S is the set of sequences of partitions of A, (Sl )l∈N0 , such that S0 = {A} and card(Sl ) ≤
√
l
22 . We show that γ(A, ||.||Lr (P) ) ≤ 2||Ck,M ||Lr (P) γ̄(A, d).
Consider the following mapping Φ : Θ → F (Θ) with Φ(θ) = φ(., θ). By construction this
mapping it 1-to-1 and onto. Let θf = Φ−1 (f ). Moreover, given any partition T = {T1 , ..., TN }
over F (A), we can generate an induced partition over A, T̄ = {T̄1 , ..., T̄N }, such that T̄i =
Φ−1 (Ti ) = {θ ∈ A | ∃f ∈ Ti , s.t. φ(., θ) = f } for all i = 1, ..., N .45 It also holds that any
partition over A, T̄ = {T̄1 , ..., T̄N }, has an associated partition over F (A), with sets of the form
{f | ∃θ ∈ T̄i , s.t. f = Φ(θ) − Φ(νk (P))}.
Therefore, under assumption 4.2, for any f ∈ F (A), and l ∈ N
sup
f1 ,f2 ∈T (f,Tl )

|f1 (z) − f2 (z)| ≤

sup
θ1 ,θ2 ∈T (θf ,T̄l )

|Ck,M (z)| × d(θ1 , θ2 )

=|Ck,M (z)|Diam(T (θf , T̄l ), d), a.s. − P
where T (θf , T̄l ) is the (only) set of the partition T̄l that contains θf . Therefore, ||S(f, Tl )||Lr (P) ≤
||Ck,M ||Lr (P) Diam(T (θf , T̄l ), d).
It thus follows that for any admissible sequence (Tl )l over F (A),
∞
X
l=0

2l/2 ||S(f, Tl )||Lr (P) ≤ ||Ck,M ||Lr (P)

∞
X
l=0

2l/2 Diam(T (θf , T̄l ), d).

Taking the supremum over f and the infimum over partitions, the desired result follows.
Proof of Proposition 4.5. Let
θ 7→ Xθ ≡
with ζj (θ) = bj ζj θj . Observe that
θ2 ||ℓ2 (b) . Thus, by [53] Theorem 2.4.1,

k
X

ζj (θ)

j=1

qP
p
k
2
E[(Xθ1 − Xθ2 )2 ] =
j=1 bj (θ1,j − θ2,j ) = ||θ1 −

γ̄(A, || · ||ℓ2 (b) ) ≤ LΓk (A),
√
and by Proposition 4.4, γ(A, ||.||Lr (P) ) ≤ 2L||Ck,M ||Lr (P) Γk (A).

D

Proofs for Results in Section 2

In order to show this proposition we need the following results; The proofs of all supplementary
lemmas are relegated to the Online Appendix OA.6.
Lemma D.1. The function EP [φ(Z, ·)] is convex, continuous and twice-continuously differentiable, and coercive.46
Proof. See the Online Appendix OA.6.
Remark D.1. The boundedness assumption of the eigenvalues of E[XX T ] is to ensure the
finiteness of constants affecting the concentration rate. The restriction on the minimal eigenvalue is needed to establish coerciveness. If Θ is compact, then this restriction is not needed.
△
Lemma D.2. Assumption 4.2 holds with d induced by ||.||ℓ2 (b) with bj = 1 for all j, r = π0 ,
and Ck,M (z) = (1 + τ )emax (xxT ) for any k ∈ N, z and M > 0.
45

Clearly T̄j ∩T̄k = {∅} otherwise there exists a θ such that φ(., θ) = f = f ′ for f 6= f ′ , and ∪N
i=1 T̄i = A
N
because otherwise there exists a θ such that φ(., θ) ∈ F(A)\{f | ∃θ ∈ ∪N
i=1 T̄i , s.t. φ(., θ) = f } = ∪i=1 Ti ,
but this is a contradiction to the fact that T is a partition.
46
We say a function f is coercive if for all M ∈ R, {θ ∈ Θ | f (θ) ≤ M } is bounded.

45

The following lemma is a simple application of the Mean value theorem and results [46] Ch.
23 (summarized in Lemma OA.6.1 in the Online Appendix OA.6).
Lemma D.3. Suppose that θ 7→ Q(θ, P) is convex and twice continuously differentiable and
P en is convex, νk (P) ⊂ int(Θk ) and Θk ⊆ Rk convex. For all θ ∈ Θk and θ0,k ∈ νk (P),
Qk (θ, P) − Qk (νk (P), P) ≥0.5

Z

0

1

d2 Q(θ0,k + t(θ − θ0,k ), P)
[θ − θ0,k , θ − θ0,k ]dt
dθT dθ

+ λk (P en(θ) − P en(θ0,k ) − µT (θ − θ0,k ))
for some µ ∈ ∂(P en(θ0,k )) such that

dQ(θ0,k ,P)
[θ
dθ T

− θ0,k ] + λk µT (θ − θ0,k ) = 0.

Proof. See the Online Appendix OA.6.
d2 Q(θ

+t(θ ′ −θ

),P)

0,k
0,k
[θ′ −
Remark D.2. (1) Lemma D.3 necessarily implies that for any θ′ ∈ νk (P),
dθ T dθ
′
′
T ′
θ0,k , θ − θ0,k ] = 0 for any t ∈ [0, 1] and P en(θ ) − P en(θ0,k ) − µ (θ − θ0,k ) = 0 for all
dQ(θ0,k ,P) ′
[θ − θ0,k ] + λk µT (θ′ − θ0,k ) = 0.
µ ∈ ∂(P en(θ0,k )) such that
dθ T
(2) The assumption νk (P) ⊂ int(Θk ) is to avoid dealing with boundary issues; it can be
relaxed following the standard results. △

Recall that In,k (ω)(r) ≡ {θ ∈ Θk (Mn,k ) : r ≥ δk,P (θ, νk (P)) ≥ 0.5r}. Let Jn,k (ω)(r) ≡
{θ ∈ Θk (Mn,k ) : r ≥ δk,P (θ, νk (P))}. Clearly, In,k (ω)(r) ⊆ Jn,k (ω)(r) and Jn,k (ω)(.) is nondecreasing.
Γ (I
(ω)(rx))
Γ (J
(ω)(rx))
Let SI (C) ≡ {r > 0 | r ≥ C maxx≥1 k n,krx
} and SJ (C) ≡ {r > 0 | r ≥ C maxx≥1 k n,krx
},
and rI (C) = inf r∈SI (C) r and rJ (C) = inf r∈SJ (C) r.
Lemma D.4. The following are true:
(1) rI (.) and rJ (.) are non-decreasing.
(2) rI ≤ rJ .
(3) rJ (C) ≤ CrJ (1) and rI (C) ≤ CrI (1) for any C ≥ 1.
(4) For any (n, k) ∈ N2 , if for all r > 0, Γk (Jn,k (ω)(r)) ≤p
min{rΛn,k (ω), Bn,k (ω)} a.s.-P,
for some Λn,k (ω) and Bn,k (ω). Then rJ (C) ≤ min{CΛn,k (ω), CBn,k (ω)}.
Proof. See the Online Appendix OA.6.

Recall that Mn,k = EPn [φ(Z, θ∗ )] + λk ||θ∗ ||ℓ1 ; and Wk ≡ E[dk (X)XX T ] with dk (X) ≡
inf θ∈{θ : ||θ||ℓ1 ≤max{Mn,k ,E[Mn,k ]}/λk } f (X T θ | X).
Proposition D.1. For any (k, n) and any u > 0, with probability higher than 1 − G0 /u:
1/2

(39)
||Wk (νk (Pn ) − θ∗ )||ℓ2 ≤uK max{1, 21/π0 Eπ0 }

s




 p
 tr{W −1 } log(2d) 1/4 q
k
Mn,k /λk + λk ||θ∗ ||ℓ1  ,
× min
,


n(β)
n(β)

√
where K ≡ max{1, 210L(1 + τ )}.

q
Proof of Proposition D.1. Throughout the proof, let || · ||2 ≡ EP [dk (X)||X T (·)||2ℓ2 ]. Note
that this notion of distance is defined conditional on the data ω because dk (x) depends on ω
through Mn,k ; throughout this dependence is left implicit. Also, let Kπ0 ≡ 21/2+1/π0 5L(1 +
τ )||emax (XX T )||Lπ0 .
Lemma D.1 implies assumption A.1 under the Euclidean topology, thus, by Lemma A.1,
ν(P) is non-empty, given by ν(P) = {θ ∈ Θ | E[X(F (X T θ|X) − τ )] = 0}. Also, by Lemma
A.2, νk (P) is non-empty and also convex.

46

By Lemma D.2, θ 7→ φ(z, θ) satisfies assumption 4.2 with r = π0 and Ck,M (z) ≡ (1 +
τ )emax (xxT ). This fact, Theorem 4.2 (with ηn = 0) and Proposition 4.5, imply
)
(
Γk (In,k (ω)(sx))
K π0
.
max
Vn,k ≤ min s > 0 | s ≥ p
sx
n(β) x≥1

So we now bound Γk (In,k (ω)(sx)). Let A1 ≡ {τ ∈ Θ : ||τ ||ℓ1 ≤ Mn,k /λk } and A0 ≡ {τ ∈
Θ : ||τ ||ℓ1 ≤ Qk (θ∗ , P)/λk }.
By Lemma D.3 with θ0,k being the minimum ||.||ℓ1 -element of νk (P), and the fact that
d2 Q(θ,P)
2
= E[f (X T θ|X)XX T ], it follows that for any θ ∈ A1 ∪ A0 , δk,P
(θ, νk (P)) is bounded
dθ 2
R
1
T
T
T
below by 0.5(θ − νk (P)) 0 E[f (X θ(t)|X)XX ]dt(θ − θ0,k ) with θ(t) = θ0,k + t(θ − θ0,k ).
Moreover, for any v ∈ Θ,
Z 1
Z 1
T
T
T
v
E[f (X θ(t)|X)XX ]dtv =
E[f (X T θ(t)|X)v T XX T v]dt
0

0

≥E[

inf

θ∈A0 ∪A1

f (X T θ|X)v T XX T v]

=v T E[dk (X)XX T ]v
where the second line because θ, νk (P) are in A1 ∪ A0 and thus, so is θ(t). Finally, note that
A1 ∪ A0 ≡ {θ ∈ Θ : ||θ||ℓ1 ≤ max{EPn [φ(Z, θ∗ )], EP [φ(Z, θ∗ )]}/λk + ||θ∗ ||ℓ1 }. Thus
√
δk,P (θ, νk (P)) ≥ 0.5||θ − θ0,k ||2 .
(this implies that νk (P) is in fact a singleton).
√
0.5||θ − νk (P)||2 ≤ s}. This
Therefore, for any s > 0, hIn,k (ω)(s) ⊆ A(s) ≡ {θ
∈
Θ
:
i
Pd
imply that Γk (In,k (ω)(s)) ≤ E supτ ∈A(s) | k=1 ζk θk | (see display 22 for the definition of Γk ).
Moreover, by Hölder inequality
"
# q
d
q
p
X
√


−1
T
T
τ Wk τ ≤ tr{Wk−1 } 2s
E sup |
ζk θk | ≤ E ζ Wk ζ sup
τ ∈A(s)

τ ∈A(s) k=1

p
τ T Wk τ = ||τ ||2 and (ii) ζ are independent with zero
√
tr{Wk−1 } 2s.

where the second line follows because
q(i)
mean. Therefore, Γk (In,k (ω)(s)) ≤
On the other hand,
"
E

sup |

τ ∈A1

d
X

k=1

#

ζk θk | ≤E[||ζ||ℓ∞ ] sup ||τ ||ℓ1
τ ∈A1

p
≤ log(2d)Mn,k /λk

p
where the second line follows from Lemma OA.3.1. Hence, Γk (In,k (ω)(s)) ≤ log(2d)Mn,k /λk .
Since both bounds are valid, for any s > 0
q

p
−1
Γk (In,k (ω)(s)) ≤ min
2tr{Wk }s, log(2d)Mn,k /λk .

It is easy to see that the same bound holds for Γk (Jq
n,k (ω)(s)), with Jn,k defined as in Lemma
p
D.4. Therefore, by Lemma D.4(4) with Λn,k (ω) ≡ 2tr{Wk−1 }, Bn,k (ω) ≡ log(2d)Mn,k /λk
p
and C ≡ Kπ0 / n(β), it follows that


s
1/4 q



2tr{Wk−1 } p
log(2d)
(40)
, K π0
Vn,k (ω) ≤ min Kπ0
Mn,k /λk .


n(β)
n(β)

47

Regarding the bias term, it follows that
Bk (P)2 ≤ Q(θ∗ , P) + λk ||θ∗ ||ℓ1 − Q(θ∗ , P) = λk ||θ∗ ||ℓ1 .
By analogous arguments to those above, for any θ ∈ A0 ∪ A1 ,
√
δP (θ, ν(P)) = δP (θ, θ∗ ) ≥ 0.5||θ − θ∗ ||2 .
(note that tθ + (1 − t)θ∗ ∈ A0 ∪ A1 ).
Hence, display 40 and Theorem 4.1 imply that

s



 p
 tr{W −1 }  log(2d) 1/4 q
k
P ||νk (Pn ) − ν(P)||2 ≤ Ce min
Mn,k /λk + λk ||θ∗ ||ℓ1 
,


n(β)
n(β)

≥1 − C0 /u,

where Ce ≡ 21/2 max{1, 2Kπ0 }.
√
It is easy to see that Ce is bounded above by max{1,
21/π0 ||emax (XX T )||Lπ0 } max{1, 210L(1+
√
τ )} and thus the result follows with K ≡ max{1, 210L(1 + τ )}.
Proposition D.2. Let pj = j m for any j ∈ N. Then: For any u > 0 and any (n, k):
(1) For m > 1


s
−1/m
q
min{λk
, d} 
1/2
Bk
||Wk (νk (Pn ) − θ∗ )||ℓ2 ≤ uK max{1, 21/π0 Eπ0 }  λk ||θ∗ ||2ℓ2 (p) +
n(β)
with probability higher than 1 − g0 (u), where Bk ≡
(2) For m ∈ [0, 1]
1/2

||Wk (νk (Pn ) − θ∗ )||ℓ2



emin (Wk )
2(m−1)

1/m

+1



2
emin (Wk ) .



s
−1
−1 d1−m
q
,
2tr{W
}}
min{λ
k
k 1−m

≤ uK max{1, 21/π0 Eπ0 }  λk ||θ∗ ||2ℓ2 (p) +
n(β)

with probability higher than 1 − g0 (u).

Proof of Proposition D.2. (1) The proof is analogous to the one for Proposition D.1, and thus
we need to provide a bound for Γk which allow us to use Lemma D.4(4).
Let A ≡ {θ ∈ Θ : ||θ||2ℓ2 (p) ≤ max{Mn,k , E[Mn,k ]}/λk }.
First note that, for any θ ∈ A , by Lemma D.3 and analogous calculations to those in proof
of Proposition D.1
q
δk,P (θ, νk (P)) ≥ 0.5||θ − νk (P)||22 + λk ||θ − νk (P)||2ℓ2 (p)

p
1/2
where ||.||22 = E[||Wk (·)||2ℓ2 ]. One can write the RHS as ||θ−νk (P)||Ak ≡ (θ − νk (P))T Ak (θ − νk (P))
with Ak ≡ 0.5Wk + λk diag{1, 2m, ..., dm }.
Therefore, In,k (ω)(s) ⊆ A(s) ≡ {θ ∈ Θ : ||θ − νk (P)||Ak ≤ s}. Hence Γk (In,k (ω)(s)) ≤
P
E[supτ ∈A(s) | dj=1 ζj θj |]. By letting a ≡ (ζj )dj=1 and b(θ) ≡ (θj )dj=1 , then by Cauchy-Swarhz,
E[ sup |

d
X

τ ∈A(s) j=1

−1/2

ζj θj |] = E[ sup |aT b(τ )|] ≤E[ sup ||Ak
τ ∈A(s)

τ ∈A(s)

v
u d
uX −1
≤st
A [j, j]
k

j=1

48

a||ℓ2 ||b(τ )||Ak ]

where the last line follows from the fact that a are independent normal and A−1
k [j, j] denotes
the (j, j) element of A−1
.
For
any
a
∈
{1,
...,
d},
k
d
X
j=1

A−1
k [j, j] ≤
≤

a
X

2(Wk [j, j])−1 + λ−1
k

X

j −m

2(Wk [j, j])−1 + λ−1
k

Z

x−m dx

j>a

j=1

a
X
j=1



=2a sup a−1
1≤a≤d



≤2a sup a−1
1≤a≤d

a
X
j=1

a
X
j=1

d

a



(Wk [j, j])−1  + λ−1
k


(Wk [j, j])−1  + λ−1
k

1
(a−m+1 − d−m+1 )
m−1
1
a−m+1
m−1



 1 1/m
Pa
−1/m
m−1
, the previLet avgk ≡ sup1≤a≤d a−1 j=1 (Wk [j, j])−1 . By choosing a = λk
2avgk
ous display shows that

47

E[ sup |

d
X

τ ∈A(s) j=1

v
u
u −1/m
ζj θj |] ≤ stλk



1
m−1

1/m

1−1/m

(2avgk )

!

.

 1 1/m
−1/m
m−1
), then an always valid bound is
If the choice of a exceeds d (i.e., if d ≤ λk
2avgk
q
√
Pd
given by E[supτ ∈A(s) | j=1 ζj θj |] ≤ s 2tr{Wk−1 } ≤ s 2davgk .
Therefore, we proved that
v
!1/m
u
1
u
−1/m
m−1
t
, d}2avgk .
Γk (In,k (ω)(s)) ≤ s min{λk
2avgk

By Theorem 4.2 (with ηn = 0), the fact that θ 7→ φ(z, θ) satisfies Assumption 4.2 with
r = π0 and Ck,M (z) ≡ (1 + τ )emax (xxT ) (see Lemma D.2) and Proposition 4.5, it follows that
(
)
K π0
Γk (In,k (ω)(sx))
Vn,k ≤ min s > 0 | s ≥ p
.
max
sx
n(β) x≥1

So the bound for Γk readily implies that
v
u
K π0 u
tmin{λ−1/m
Vn,k ≤ p
k
n(β)

1
m−1

2avgk

!1/m

, d}2avgk ,

where Kπ0 is defined in the proof of Proposition D.1.
Finally, note that, for any v ∈ Rd , v T Wk v ≥ v T vemin (Wk ). Thus, avgk ≤ emin (Wk )−1 .
Thus, the desired result follows by simple algebra (see the last part of the proof of Proposition
D.1).
Pd
(2) For the case with m ∈ [0, 1], as before, an always valid bound is given by E[supτ ∈A(s) | j=1 ζj θj |] ≤
q
s 2tr{Wk−1 }. In addition,
d
X
j=1

47

−1
A−1
k [j, j] ≤λk

d
X
j=1

j −m ≤ λk−1

d1−m
,
1−m
−1/m

More precisely, a is chosen as the integer approximation of λk

for the sake of presentation.

49



1
m−1

2avgk

1/m

, but we omit this

and the bound follows.
Proposition D.3. For any n ∈ N, µ0 ≤ n and l = 1, ..., d, for any t ≥ 1
v
"
u
r !
2 #
n
X
u
4
µ
|∆|
0
≤ tEP
xi,l Ui | ≥ t
P |n−1
.
√
n
t
µ0
i=1

Remark D.3. As pointed out in the proof below, one can obtain a better bound of order
t−2 × log(t2 ) by refining the arguments in the proof. The goal here is not to obtain the best
possible bound but to present a proof that resembles the technique of proof we used in the
paper. Also, even when comparing our method to the sharper bound of order t−2 × log(t2 ), it is
worth to point out that our method cannot exploit the explicit solution of the OLS estimator,
and is designed for general β-mixing processes. △
Proof of Proposition D.3. So as to ease the notational burden, we omit the subscript l from
√
√
∆j,l . For any K1 > 0, let ∆L
µ0 K1 K0 } and ∆U
µ0 K1 K0 }.
j ≡ ∆j 1{|∆j | ≤
j ≡ ∆j 1{|∆j | ≥
L
U
By construction E[∆j ] = E[∆j ] + E[∆j ] = 0 and thus
n

−1

√ X
√ X
J
J
µ0
µ0
L
¯
∆j +
∆¯U
xi,l Ui =
j ,
n
n
j=0
j=0
i=1

n
X

where ∆¯zj ≡ ∆zj − E[∆zj ] for z ∈ {L, U }. Therefore, for any u > 0,




!
√ X
√ X
n
J
J
X
µ
µ
0
0
¯L | ≥ 0.5u + P |
¯U | ≥ 0.5u
xi,l Ui | ≥ u ≤P |
P |n−1
∆
∆
j
j
n
n
i=1
j=0
j=0
≡T erm1 (u) + T erm2 (u).

We now bound the T erm1 (u) (using Bernstein inequality) and T erm2 (u) (using Markov inequality).
√
By Bernstein inequality and the fact that |∆L
j | ≤ K 1 K 0 µ0 ,


)
(
√ X
J
µ0
0.5u2 n2 µ−1
L
0
¯


P
∆ ≥ u ≤ exp − PJ
−1/2 1/2
n j=0 j
E[(∆¯L )2 ] + u nµ
µ K0 K1
j=0

3

0

0

for all u > 0. Hence, since J + 1 = n/µ0 ,


)
(
√ X
J
2 2 −1
µ0
0.5u
n
µ
L
0
¯j ≥ u ≤ exp − P
∆
P
J
u
¯L 2
n
j=0 E[(∆ ) ] + 3 nK0 K1
j=0
(
)
0.5u2
= exp − (J+1)
µ0 n2 E[(∆¯L )2 ] + u3 µn0 K0 K1


0.5u2
= exp − 1
E[(∆¯L )2 ] + u3 µn0 K0 K1
 n

0.5u2
≤ exp − 1
u µ0
2
n E[(∆) ] + 3 n K0 K1
where the last line follows from the fact that E[(∆¯L )2 ] ≤ E[(∆L )2 ] ≤ E[(∆)2 ].
If E[(∆)2 ] ≥ u3 µ0 K0 K1 , then for any u > 0,




√ X
J
µ0
u2

∆¯L
≥
u
≤
exp
−
P
n j=0 j
4 n1 E[(∆)2 ]

50

iff, for all t > 0


√ X
J
p
p
√
µ0
2 µ0
2 −1/2 t ≤ exp {−t} , if
E[(∆)2 ] ≥ t √ K0 K1 .
∆¯L
P
j ≥ 2 E[(∆) ]n
n j=0
3 n
Else, if E[(∆)2 ] ≤ u3 µ0 K0 K1 , then for any u > 0,




√ X
J
µ0
u
L
¯


∆ ≥ u ≤ exp − 4 µ0
P
n j=0 j
3 n K0 K1

iff, for all t > 0


√ X
J
p
µ0
µ
4
2 µ0
0
∆¯L
K0 K1 t ≤ exp {−t} , if E[(∆)2 ] ≤ t √ K0 K1 .
P
j ≥
n j=0
3 n
3 n
When t ≥ 1 it follows that,

p
p
√ p
4 µ0
2 µ0
2 µ0
K0 K1 t1{ E[(∆)2 ] ≤ t √ K0 K1 }
2 E[(∆)2 ]n−1/2 t1{ E[(∆)2 ] ≥ t √ K0 K1 } +
3 n
3 n
3 n
s
s
s
!
r
r
r
r
µ0
E[(∆)2 ]
E[(∆)2 ]
µ0
E[(∆)2 ]
µ0
2
2
4 µ0
≤
1{
≥ t
≤ t
t 2
K0 K1 } +
K0 K1 1{
K0 K1 }
n
µ0
µ0
3
n
3 n
µ0
3
n
)
( s
r
r
µ0
E[(∆)2 ] 8 µ0
,
≤
t max 4
K0 K1 .
n
µ0
3 n
Therefore, for any t ≥ 1,







√ X
J


µ0
t
L
¯


 .
 q
∆j ≥ t ≤ exp −
T erm1 (2t) = P
p µ0


n j=0
E[(∆)2 ] 8 p µ0



, 3 n K0 K1 
n max 4
µ0


√ P

µ
J
Regarding T erm2 (2u) = P | n 0 j=0 ∆¯U
|
≥
u
. By the Markov Inequality, it follows
j
that for any u > 0




√
J
X
µ0 /n
|∆|
2
√
U 
¯

|∆j | ≤ EP √ 1{|∆|/ µ0 ≥ K0 K1 }
T erm2 (2u) ≤
EP
u
u
µ0
j=0
and applying Markov inequality again, it follows that T erm2 (2u) ≤
Therefore, by a simple change of variables

P |n−1

n
X
i=1

xi,l Ui | ≥ 2s

r

µ0
n

!






2
uK0 K1 EP



|∆|
√
µ0

2 






s
 q

−
p µ0


2]
E[(∆)

8
 max 4

, 3 n K0 K1 
µ0
"
2 #
r
|∆|
2
n
.
EP
+
√
µ0 sK0 K1
µ0

≤ exp

51

.

Choosing K1 so that K0 K1 =

P |n−1

n
X
i=1

xi,l Ui | ≥ 2s

q

r

n
µ0

µ0
n

q

!

E[(∆)2 ]
,
µ0

it follows that















v
"
u
2 #
|∆|
s
2u
t
≤ exp − s
+
EP
√

2  

s
µ0


|∆|




 4 EP √µ0


v
"
u
2 #
|∆|
4u
t
EP
.
≤
√
s
µ0

Remark D.4. K1 was chosen to optimize the RHS bound; if one allows K1 to depend on s we
obtain a better bound of order s−2 × log(s2 ) as opposed to s−1 obtained now. △

E

Proofs for Results in Section 5

Proof of Lemma 5.1. The result follows from Proposition 4.1, the definition of I(Pn , P) and
assumption 5.1.
Proof of Proposition 5.1. We need to show that for any ǫ > 0, there exists a M (ǫ) and N (ǫ)
such that
P(̟(νksFn (Pn ) (Pn ), ν(P)) ≥ M (ǫ)sn ṼkI (Pn ,P) ) ≤ ǫ
for all n ≥ N (ǫ).
By theorem 5.1, it follows that
P(̟(νksFn (Pn ) (Pn ), ν(P)) ≥ sn 6VṼkI (Pn ,P) ) ≤ |K|g0 (sn )
for all n ∈ N. By assumption, |K|g0 (sn ) → 0, so for any ǫ > 0, there exists a N (ǫ) such that
|K|g0 (sn ) < ǫ for any n ≥ N (ǫ). So the result follows by setting M (ǫ) = 6.
Proof of Theorem 5.1. Henceforth, we simply write ksF and k I instead of ksF (Pn ) and k I (Pn , P).
Also, we prove the statement for V = 1 so as to simplify further the notation; from general
V ≥ 1 the proof is the same, but simply replacing Ṽk by VṼk . Also, recall that s > 0 is fixed.
We first define sets we use throughout the proof:
An,s ≡{ω ∈ Ω | k I ≥ ksF }

Bn (s) ≡{ω ∈ Ω | ̟(νksF (Pn ), ν(P)) > s6ṼkI (Pn )}
Cn (s) ≡{ω ∈ Ω | ̟(νkI (Pn ), ν(P)) < 2sṼkI (Pn )}

Dn (s) ≡{ω ∈ Ω | ̟(νksF (Pn ), ν(P)) ≤ ̟(νksF (Pn ), νkI (Pn ))
+ 2sṼkI (Pn )}


p
En (s, k) ≡{ω ∈ Ω | ̟(νk (Pn ), ν(P)) < s Ṽk (Pn ) + Bk (P) }

and En (s) = ∩k∈K En (s, k). In this notation,
P we want to show that P(Bn (s)) ≤ 2|K|g0 (s).
By Proposition 4.1, P(Ω \ En (s)) ≤ k∈K P(Ω \ En (s, k)) ≤ |K|g0 (s). Also, by Lemma 5.1,
P(Ω \ Cn (s)) is bounded by g0 (s) ≤ |K|g0 (s).
Thus, it suffices to show
P(En (s) ∩ Cn (s) ∩ Bn (s)) = 0.

52

(41)

Henceforth, let Fn (s) ≡ En (s) ∩ Cn (s) ∩ Bn (s). It suffices to show
P(Fn (s) ∩ Dn (s)) + P({Ω \ Dn (s)} ∩ Fn (s)) = 0.

(42)

We first show that En (s) ∩ Cn (s) ⊆ {ω ∈ Ω | k I ∈ Fs (Pn )}. First note that k I ∈ K by
construction. If ω ∈ En (s) ∩ Cn (s), then for all k ≥ k I ,
̟(νkI (Pn ), νk (Pn )) ≤ (̟(νkI (Pn ), ν(P)) + ̟(νk (Pn ), ν(P)))
n
o
p
≤s 2ṼkI (Pn ) + Ṽk (Pn ) + Bk (P)
n
o
≤s 4Ṽk (Pn )

where the first line follows from
the third line follows because, since k ≥ k I ,
p
p triangle inequality;
then Ṽk (Pn ) ≥ ṼkI (Pn ) ≥ BkI (P) ≥ Bk (P) (note that under assumption 5.1(ii), k 7→
Bk (P) is non-increasing). Thus k I ∈ Fs (Pn ).
For any ω ∈ Cn (s) it follows that
̟(νksF (Pn ), ν(P)) ≤̟(νksF (Pn ), νkI (Pn )) + ̟(νkI (Pn ), ν(P))
<̟(νksF (Pn ), νkI (Pn )) + 2sṼkI (Pn ).

(43)
(44)

But this means that ω ∈ Dn (s) and thus P({Ω \ Dn (s)} ∩ Fn (s)) = 0. Therefore, from display
42 it remains to show that P(Fn (s) ∩ Dn (s)) = 0. For this, observe that
P(Fn (s) ∩ Dn (s)) ≤ P(Fn (s) ∩ An,s ∩ Dn (s)) + P(Fn (s) ∩ {Ω \ An,s } ∩ Dn (s)).

(45)

Regarding the first expression in the RHS, note that when k I ≥ ksF , by definition of Fs (Pn )
and the fact that k I ∈ K, it follows that
̟(νksF (Pn ), νkI (Pn )) ≤ 4sṼkI (Pn ),
and thus,
̟(νksF (Pn ), ν(P)) ≤̟(νksF (Pn ), νkI (Pn )) + ̟(νkI (Pn ), ν(P))
≤4sṼkI (Pn ) + ̟(νkI (Pn ), ν(P))
=6sṼkI (Pn )

where the second line follows from the fact that ω ∈ Cn (s). But this contradicts the inequality
in the definition of Bn (s), thus P(Dn (s) ∩ An,s ∩ Fn (s)) = 0.
Therefore, it only remains to show that the second term in display 45 is zero. In this case
k I < ksF . This implies that ṼkI (Pn ) ≤ ṼksF (Pn ). However, since k I ∈ Fs (Pn ), it also follows
that ṼkI (Pn ) ≥ ṼksF (Pn ). Hence ṼkI (Pn ) = ṼksF (Pn ). Therefore,
q
q
ṼksF (Pn ) + BksF (P) =ṼkI (Pn ) + BksF (P)
p
≤ṼkI (Pn ) + BkI (P), because k I < ksF
≤2ṼkI (Pn ).

Hence, by the fact that ω ∈ En (s), it follows that ̟(νksF (Pn ), ν(P)) ≤ 2sṼkI (Pn ). But this
contradicts ω ∈ Bn (s).
Proof of Proposition 5.2. Under our assumption ||.||2 ≥ ̟||.||ℓ2 . So, by our calculations in
Example 2.1, it follows, for P en = ||.||ℓ1 ,
 v

n
 u

X
p
u −1
||νk (Pn ) − θ∗ ||ℓ2 ≤ uV1 An tλk n−1
φ(Zi , 0) + λk ||θ∗ ||ℓ1


i=1

53

with An ≡ (log 2d/n(β))1/4 with probability higher than 1 − g0(u). Similarly, for P en = ||.||ℓ2 (p)
s

 λ−1/m q

k
+ λk ||θ∗ ||2ℓ2 (p) .
||νk (Pn ) − θ∗ ||ℓ2 ≤ uV2


n(β)

Pn
The fact that the RHS has n−1 i=1 φ(Zi , 0) is valid because 0 ∈ Θ. This simplifies the
expressions, in case 0 ∈
/ Θ any other element of Θ would work.
−1/m
Pn
λk
2
−1
2
By choosing λk so as A2n λ−1
k n
i=1 φ(Zi , 0) = λk ||θ∗ ||ℓ1 and n(β) = λk ||θ∗ ||ℓ2 (p) , resp.,
one obtains the “infeasible choice” of tuning parameter.
This choice imply, for P en = ||.||ℓ1 ,
(
)
n
X
p
p
1/4
−1
||νk (Pn ) − θ∗ ||ℓ2 ≤ uV1
φ(Zi , 0))
An (n
||θ∗ ||ℓ1
i=1

and, for P en = ||.||ℓ2 (p)
||νk (Pn ) − θ∗ ||

ℓ2



1
m
− 2(m+1)
m+1
||θ∗ ||ℓ2 (p) ,
≤ uV2 n

with probability higher than 1 − g0 (u). Similarly,

E.1

Discussion of Assumption 5.1 and |K|

The monotonicity assumption in k 7→ Ṽk (Pn ) is quite mild. For instance, we need k 7→ Mn,k
to be non-decreasing and k 7→ ̟k to be non-increasing at least for k ≥ k0 for some k0 ∈ N.
Regarding the former, this property follows simply by noting that there exists a θ0 such that:
(i) θ0 ∈ Θk0 for some k0 and (ii) P en(θ0 ) is finite; and thus one can set θk = θ0 for all k ≥ k0
(and arbitrarily elsewhere); such that choice exists because P en is finite in Θk for any k < ∞.
Since ̟k is a lower bound, imposing that is non-increasing can always be achieved by taking
the ̟k to be the “worst” bound among ̟j for j ≤ k.
The following corollary formalizes the discussion on the |K| factor of Theorem 5.1. It shows
that conditioning on the set En (s) there is no |K| present on the concentration bound.
Corollary E.1. Under the same assumptions of Theorem 5.1,
P(̟(νksF (Pn ) (Pn ), ν(P)) ≥ s6VṼkI (Pn ,P) (Pn ) | En (s)) ≤ g0 (s)
with En (s) = ∩k∈K En (s, k) and


p
En (s, k) ≡ {ω ∈ Ω | ̟(νk (Pn ), ν(P)) < s Ṽk (Pn ) + Bk (P) }.

This corollary also shows that if one has a better bound for P(∩k∈K En (., k)) then one can
improve on the overall bound of Theorem 5.1. For instance, this will be the case if there exists
a u ≥ 0 such that P(En (s, k)) = 1 for each k ∈ K and all n large.

54

Online Appendix
OA.1

Some observations about our choices of n and Qn

Qυ
υ
υ
υ
i
Let N ≡ {m : m = i=1 pm
i , some (mi )i=1 ∈ N0 } for some υ ∈ N and (pi )i=1 consecutive
prime. Our restrictions
imply that n ∈ N . It is well-known that any n ∈ N admits a prime
Q
factorization ei=1 pei i where (pi , ei )ei=1 and e depend on n. Our restriction on n imposes that
e and (pi )i do not depend on n. Specifically, we guarantee that pe (the highest prime) is fixed.
The assumption that the primes are consecutive is just for simplicity.
For instance, for υ = 2, then n ∈ {1, 2, 4, 8, 16, ..., 2m, ...}, and for υ = 3, then n ∈
{1, 2, 3, 4, 6, 8, 9, 12, ..., 2m13m2 , ...}. Note that once we fixed υ certain values of n are not admissible, say, if υ = 3 then neither n = 7 or n = 11 (or any prime larger than 3) are valid choices
of n.
These restrictions in n ensure that consecutive elements of Qn are not “too far apart”.
Formally, let D[n] the set of divisors of n, then
Lemma OA.1.1. For any n ∈ N and a ∈ D[n], a > 1. Then there exists a a′ ∈ D[n] such
that a′ < a and pυ a′ ≥ a.
Qυ
Proof. If a ∈ D[n], then it must be that a = i=1 pfi i for some integers (fi )i such that fi ≤ mi .
Let l be the first i ∈ {1, ..., υ} such that fi ≥ 1 (such l exists because a > 1). Consider
Qe
a′ = plfl −1 i=l+1 pfi i . Clearly a′ < a and pv a′ ≥ pl a′ = a. Moreover, an′ = pl na which is an
integer because a ∈ D[n]. Therefore a′ ∈ D[n].
This lemma shows how the choice of υ and (pi )υi=1 affect the “separation” in D[n]. For
instance, for υ = 2, 2a′ ≥ a for any a′ ≤ a in D[n]. But if υ = 7, then the case n = 7 or n = 14
are such that 7a′ ≥ a.
We note that Qn = D[n], so the previous lemma readily applies to elements in Qn . In
Lemma B.6 we use this result to establish the bound for the L1 norm.

OA.2

A Simple Linear Regression Model: MA structure

The setup is the same as that of Example 2.3 but with the difference that Ui = εi − θ1 εi−1 −
... − θq εi−q with (εi )i being an i.i.d. sequence of mean zero bounded random variables, and
q ≡ µ0 ∈ N. It is well known
P that (Ui )i is a q-dependent sequence.
We now study n−1 ni=1 xi,l Ui and how to decompose it into i.i.d. blocks. Henceforth,
we omit the l subscript. Consider B0 = (x1 U1 , ...., xq Uq ), B1 = (x1+q U1+q , ...., x2q U2q ),...,
Bj = (xjq+1 Ujq+1 , ...., xjq+q Ujq+q ),.... As usual, we assume that (q, n) are such that there
exists a J ∈ N such that J(q + 1) = n.
We now show that the sequence (B2j )j=0,... is an independent sequence. Fix a k ∈ {0, ...}
and take U2kq+q (the last random component of B2k ) and compare it with U2(k+1)q+1 (the first
random component of B2(k+1) ). By construction, U2kq+q is measurable with respect to the
σ-algebra generated by ε2kq+q , ε2kq+q−1 , ..., ε2kq+q−q . Similarly, U2(k+1)q+1 is measurable with
respect to the σ-algebra generated by ε2(k+1)q+1 , ε2(k+1)q+1−1 , ..., ε2(k+1)q+1−q . Observe that
ε2(k+1)q+1−q = ε2kq+2q+1−q = ε2kq+q+1 . That is, the “oldest” innovation of the first element of
B2(k+1) is ε2kq+q+1 and is independent from the “latest” innovation of the last element of B2k ,
which is ε2kq+q . So U2(k+1)q+1 and U2kq+q are independent. This implies that any other two
elements of B2k and B2(k+1) are independent too.
Analogously, we can show that (B2j+1 )j=0,... is an independent sequence. Consequently, we
Pn
√ P[(J+1)/2]−1
√ P[J/2]
∆2j+1
can decomposed n−1 i=1 xi Ui into two summands n−1 q j=0 ∆2j and n−1 q j=0
P
jq+q
with ∆j = q −1/2 i=jq+1 xi Ui . This is the same decomposition we did in the proof of Lemma

1

B.7 but with the caveat that in this case — due to the particular MA structure — there is no
need to invoke another dataset given by Z ∗ .



Pn
√ P[J/2]
Hence, in order to bound P |n−1 i=1 xi Ui | ≥ u it suffices to bound P |n−1 q j=0 ∆2j | ≥ u


√ P[(J+1)/2]−1
and P |n−1 q j=0
∆2j+1 | ≥ u . For each of these terms the proofs proceed in the
same fashion as that of Proposition D.3 and it is thus omitted.

OA.3

Bounds for the Suprema of Gaussian Processes

OA.3.1

Upper Bounds for Γk (In,k (ω)(r))

From the Proposition 4.5 (and Theorem 4.2), we see that the relevant notion of complexity of
Θk (Mn,k ) (or rather In,k (ω)) is the expectation of the supremum of Gaussian process of the
form presented in display 22. In this section we provided
Pk some insights so as to further control
this quantity when P en is of the form || · ||aℓa (p) ≡ j=1 pj |θj |a for a ≥ 1 and (pj )j positive
real-valued non-decreasing sequence.48
ideas is as follows: By exploiting Gaussianity and the linearity of the process θ 7→
Pk The p
ζ
bj θj , it turns out that one can get good bounds on Γk (In,k (ω)(r)) under distances
j=1 j
of the form ||θ||aℓa (p) ; see Lemmas OA.3.1 - OA.3.4. Since δk,P (·, νk (P)) will (in principle) not
coincide with Banach norms, e.g., || · ||ℓa (p) , we need to control the relative behavior between
these distances.
P
Assumption OA.3.1. P en(θ) = kj=1 pj |θj |a for a ≥ 1 and (pj )j positive real-valued nondecreasing sequence.
Remark OA.3.1. It is straightforward to extend the results below to cases where one ”mixesand-matches” ℓp norms, e.g. P en(.) = ||.||aℓa + ||.||bℓb for some a, b ≥ 1. △
For some vk (P) ∈ νk (P), and for any A ⊆ Θk and any a′ ∈ N and p′ = (p′j )kj=1 ∈ Rk+ , let
Ξk (a′ , p′ , A) ≡ sup

||θ − vk (P)||ℓa′ (p′ )

θ∈A

δk,P (θ, νk (P))

.

Also, let for any p = (pj )kj=1 ∈ Rk+
 Pk p

bj

j=1


 a−1


a
1
a
Pk
a
a−1
− a−1
0.5 a−1
p
(E[|ζ1 | a−1 ]) a
b
Ck,a (p) =
j
j=1 j


q

√


max1≤j≤k bj p−2
log 2k
j

a=∞
a ∈ (1, ∞)
a=1

Proposition OA.3.1. Suppose Assumption OA.3.1 holds. Then, for any (n, k) ∈ N2 , 1 ≤
a′ , a ≤ ∞, (p′ , p) ∈ R2k
+ , and r > 0,
(

1/a0 )
Mn,k
′
′ ′
Γk (In,k (ω)(r)) ≤ min Ck,a′ (p )Ξk (a , p , In,k (ω)(r))r, Ck,a (p)
,
λk
a.s.-P, with a0 = a if a < ∞ and a0 = 1 if a = ∞.
Toh prove the PropositioniOA.3.1 we need the next lemma, which provides an upper bound
p
Pk
for E supτ ∈A j=1 ζj bj τj , where (bj )j is a positive real-valued sequence (the proof of this

Lemma is relegated to the end of the section).
48

For a = ∞, ||θ||aℓa (p) = max1≤j≤k |θj |, for any θ ∈ Θk .

2

Lemma OA.3.1. For any A ⊆ Θk , any (pj )j real-valued positive sequence, any k ∈ N, and
any q ∈ N ∪ {∞}.


k
X
p
ζj bj τj  ≤ Ck,q (p) sup ||τ ||ℓq (p) .
E  sup
(46)
τ ∈A j=1

τ ∈A

Proof of Proposition OA.3.1. The proof relies on Lemma OA.3.1. We first note that






k
k
k
X
X
X
p
p
p
ζj bj θj  =E sup
E sup
ζj bj θj  − E 
ζj bj vk,j (P)
θ∈A j=1

θ∈A j=1



=E sup

k
X

θ∈A j=1

because E
Thus

hP
k

j=1 ζj

j=1


p
ζj bj {θj − vk,j (P)}

i P
 p 
p
k
bj vk,j (P) = j=1 E ζj bj vk,j (P) = 0.


Γk (In,k (ω)(r)) = E 

k
X

sup

θ∈In,k (ω)(r) j=1


p
ζj bj {θj − vk,j (P)} .

We note that In,k (ω)(r) ⊆ {θ | δk,P (θ, vk (P)) ≤ r} ⊆ {θ |
fore,

Γk (In,k (ω)(r)) ≤ rΞk (a′ , p′ , In,k (ω)(r))E 

||θ−vk (P)||ℓa′ (p′ )

Ξk (a′ ,p′ ,In,k (ω)(r))

sup

k
X

θ∈||θ−vk (P)||ℓa′ (p′ ) ≤1 j=1

≤ r}. There-


p
ζj bj {θj − vk,j (P)} .

By invoking Lemma OA.3.1 with τ = θ − vk (P), p′ acting as p and a′ = q in the Lemma
and A = {θ ∈ Θ | ||θ − vk (P)||ℓa′ (p′ ) ≤ 1}, it follows that one possible upper bound is given by
Γk (In,k (ω)(r)) ≤ Ck,a′ (p′ )Ξk (a′ , p′ , In,k (ω)(r))r.
Another possible upper bound is directly given by
Γk (In,k (ω)(r)) ≤Γk (Θk (Mn,k ))
≤Ck,a (p)

||θ||ℓa (p)

sup

θ∈Θk (Mn,k )

1/a0

≤Ck,a (p) (Mn,k /λk )

where the first line follows from definition of In,k (ω)(r) ⊆ Θk (Mn,k ); the second follows by
Lemma OA.3.1 with τ = θ, q = a and A = Θk (Mn,k ); and the last follows from the fact that,
under Assumption OA.3.1, P en(θ) = ||θ||aℓa (p) ≤ M/λk for all θ ∈ Θk (M ).
Since both upper bounds are valid, we take the minimum of both and the desired result
follows.
Remark OA.3.2. In cases where there exists a finite constant M such that supθ∈Θ ||θ||ℓa (p) ≤
M , then the proposition can be easily adapted to accommodate this case and yield sharper
bounds, of the type:
n
o
1/a
Γk (In,k (ω)(r)) ≤ min Ck,a′ (p′ )Ξk (a′ , p′ , In,k (ω)(r))r, Ck,a (p) (M ) 0 .
△

3

We conclude the section with a few remarks regarding Ξk (a′ , p′ , In,k (ω)(r)). The quantity
Ξk (a′ , p′ , In,k (ω)(r)) measures the discrepancy between δk,P , which is the “natural” distance
for the criterion function, and a Banach norm ||.||ℓa′ (p′ ) . The problem is that there could
exist elements of Θk (Mn,k ) for which the former distance is small, but the latter is not. In
a non-/semi-parametric conditional moment context, this quantity is analogous to the (sieve)
measure of ill-posedness (see [9] and [17]) and in high-dimensional problems with sparsity is
related (although not the same) to the so-called compatibility constant (see [56] and references
therein).
2
Lower bound for δk,P

OA.3.2

2
The next assumption provides a lower bound for δk,P
which is natural in settings where Q(·, P)
is convex and twice continuously differentiable, and P en is convex.

Assumption OA.3.2. P en is convex and there exists a real valued non-negative sequence
(en,k )n,k such that: For all (n, k) ∈ N2 ,
2
δk,P
(θ, νk (P)) ≥ en,k ||θ − νk (P)||2ℓ2 + λk ∆(θ, νk (P)), ∀θ ∈ Θk (Mn,k ),

where 0 ≤ ∆(θ, νk (P)) ≤ P en(θ) − P en(νk (P)) − µT (θ − νk (P)) for all µ ∈ ∂P en(νk (P)).
When P en is differentiable, ∆ can be taken to be the Bergman divergence (see [2] and
reference therein). For P en = ||.||ℓ1 one can simply take ∆ = 0 whereas for P en = ||.||2ℓ2 (p) one
can take ∆ = ||.||2ℓ2 (p) .
Under this assumption,
Ξk (a′ , p′ , In,k (ω)(r)) ≤Ξk (a′ , p′ , Θk (Mn,k ))
≤

OA.3.3

sup
θ∈Θk (Mn,k )

(47)
||θ − νk (P)||ℓa′ (p′ )

q
.
en,k ||θ − νk (P)||2ℓ2 + λk ∆(θ, νk (P))

(48)

On the Bounds of Lemma OA.3.1

The next Lemma shows that for certain sets A, the bounds of Lemma OA.3.1 are sharp for any
q < ∞, up to universal constants; for q = ∞ we loose a k −1 which in some cases — non-/semiparametric models — it could diverge. In particular, this lemma extends the results in [53] Ch.
2 to more general sets than ellipsoids.
Lemma OA.3.2. For A = {τ ∈ Rk | ||τ ||ℓq (p) ≤ M 1/q }:
(1) For q = ∞


k
X
p
ζj bj τj  ≥ sup ||τ ||ℓ∞ k −1 Ck,q (p)
E  sup
τ ∈A j=1

(49)

τ ∈A

(2) For q ∈ (1, ∞)



E  sup

k
X

τ ∈A j=1

with K =



1
L+1

 q−1
q


p
ζj bj τj  ≥ KCk,q (p) sup ||τ ||ℓq (p)

(50)

τ ∈A

q

q
q
2 2(q−1) Γ( 2(q−1)
).
< 1 and L = 2 q−1

(3) For q = 1


q
k
X
p
−1
−1
ζj bj τj  ≥ ( max b−0.5
E  sup
p
)
(1
−
e
)
c−1
j
2 log c1 k sup ||τ ||ℓ1 (p)
j
τ ∈A j=1

1≤j≤k

τ ∈A

4

(51)

OA.3.4

Proofs of Lemmas OA.3.1 and OA.3.2

Throughout this section, let ζj ∼ iid − N (0, 1) for any j = 1, 2, .... Recall that || · ||qℓq (p) =
P
q
j pj | · | for any q ∈ N ∪ {∞} and pj ∈ R+ for each j = 1, 2, .... In what follows, fix any (pj )j
real-valued positive sequence, any k ∈ N, and any q ∈ N ∪ {∞}.
The proof of Lemma OA.3.1 requires the following results. The right inequality in the first
lemma is a minor modification of Lemma A.2 in [12] (their proofs are relegated to the end of
the section).
Lemma OA.3.3. Let ζj ∼ i.i.d.N (0, 1) and (pj )j a positive real valued sequence. Then


q
p
−1
log
c
k
≤
E
max
|p
ζ
|
≤ ( min pj )−1 0.5 log 2k.
( max pj )−1 (1 − e−1 ) c−1
1
j
2
j
1≤j≤k

1≤j≤k

1≤j≤k

with

e(π+2)
4

c1 ≡

−1

r

π+2
π

!

c2 ≡ 1
Lemma OA.3.4. Let ζ = (ζ1 , ..., ζk ) with ζj ∼ i.i.d.N (0, 1) and (pj )j a positive real valued
sequence. Then, for any q ≥ 1,


E[|ζ1 |] 

k
X
j=1

1/q



≤ E ||ζ||ℓq (p)

pj 

Proof of Lemma OA.3.1. Let ξj ≡ ζj
(1)-(2) By Holder inequality
Γk (A) ≤E[sup

k
X

τ ∈A j=1






≤E  sup 
τ ∈A



p
bj for all j.
−1/q2

|pj

k
X

−q1 /q2

pj

j=1

1/q2

ξj pj

1/q

k
X
≤ (E[|ζ1 |q ])1/q 
pj 
j=1

(τj )|]
1/q1 

|ξj |q1 



k
X
j=1

1/q2 

pj |τj |q2 


1/q2

k
i
h
X
pj |τj |q2 
= sup 
E ||ζ||ℓq1 (b0.5q1 ·p−q1 /q2 )
τ ∈A

j=1

for any qi ≥ 1 and q1−1 + q2−1 = 1. By lemma OA.3.4 (the p in the lemma is taken to be
b0.5q1 · p−q1 /q2 in this proof),


Γk (A) ≤ sup ||τ ||ℓq2 (p) (E[|ζ1 |q1 ])1/q1 
τ ∈A

k
X
j=1

1/q1

1 −q1 /q2 
pj
b0.5q
j

.

The result (2) follows by setting q2 = q. The result (1) follows from setting pj = 1 and noting
that q1 = 1 and ||τ ||ℓq2 (p) = ||τ ||ℓ∞ , so


k
X
;
b0.5
Γk (A) ≤ sup ||τ ||ℓ∞ (E[|ζ1 |]) 
j
τ ∈A

j=1

and the fact that E[|ζ1 |] = 1 for standard Gaussian.

5

(3) Note that
Γk (A) ≤ E[sup

k
X

τ ∈A j=1

−1
p−1
j ξj pj τj ] ≤ E[ max |pj ξj |] sup ||τ ||ℓ1 (p) .
1≤j≤k

θ∈A

By lemma OA.3.3 (the p in the lemma is taken to be b0.5 · p−1 in this proof),
r
p
−1
E[ max |pj ξj |] ≤
max bj p−2
0.5 log 2k.
j
1≤j≤k

1≤j≤k

p
Pk
Proof of Lemma OA.3.2. Let ξj ≡ bj ζj . Let Xk (A) ≡ supτ ∈A j=1 ξj τj for any realization
of (ζ1 , ..., ζk ). Therefore, it suffices to show that
E [Xk (A)] ≥ KCk,q (p)M 1/q .

(52)

We begin by noting a fact that we use throughout the proof: For any realization ζP
and for any
k
τ ∈ A, by taking tj = τj sign(ξj ) (which also belongs to A) it follows that Xk (A) ≥ j=1 τj |ξj |.
Pk
The Case q = ∞: From the fact above Xk (A) ≥ j=1 τj |ξj | for any τ ∈ A. For any given
τ ′ ∈ A, choose τ such that τ1 = max1≤l≤k |τl′ | and τj = 0 for all j 6= 1. Clearly (1) τ ∈ A
√
P
and (2) Xk (A) ≥ kj=1 τj |ξj | ≥ |ζ1 | b1 max1≤l≤k |τl′ |. By taking expectations and repeating
Pk p
the process for j = 2, etc, it follows that Xk (A) ≥ k −1 j=1 bj × max1≤l≤k |τl′ |. The desired
result thus follows from taking the supremum over all τ ′ ∈ A.
The Case q ∈ (1, ∞):

Step 1. We now show that
E[(Xk (A))

q
q−1

] ≥(M )



1
q−1

E 

k
X

|ξj |

j=1

q
q−1



− 1
pj q−1 

k
iX
h
q
1
0.5 q
− 1
bj q−1 pj q−1 .
=(M ) q−1 E |ζ1 | q−1
j=1

By the fact at the beginning Xk (A) ≥
Let

Pk

j=1 τj |ξj |

1

τj = M

1/q

Note that

q
j=1 pj τj

=M

and so τ ∈ A. Also, note that
k
X
j=1

1

|pj |− q−1 |ξj | q−1

, ∀j = 1, ..., k.
q
Pk
1
( j=1 |pj |− q−1 |ξj | q−1 )1/q
−

Pk

for any τ ∈ A.

Pk

j=1

pj Pk

j=1

τj |ξj | =M 1/q
=M

pj

1/q

k
X
j=1

k
X

q
q−1

|pj

q

|ξj | q−1

− 1
| q−1

|ξj

q
| q−1

=M

Pk

|pj |
j=1 Pk

1

1

|pj |− q−1 |ξj |1+ q−1

q
Pk
1
( j=1 |pj |− q−1 |ξj | q−1 )1/q
1

q

|pj |− q−1 |ξj | q−1

q
Pk
1
( j=1 |pj |− q−1 |ξj | q−1 )1/q
 q−1

q
k
X
q
1
− q−1
1/q 
|ξj | q−1 
|pj |
=M
.

j=1

j=1

6

−

1
q−1

q

|ξj | q−1

− 1
q−1
j=1 pj

q

|ξj | q−1

=M

Hence
E[(Xk (A))
and the results follows.

q
q−1



] ≥ E M

1
q−1




k
X
j=1

|pj |

1
− q−1

|ξj |

q
q−1




Step 2. We show that:
q

q

E[(Xk (A) − E[Xk (A)]) q−1 ] ≤ L (E[Xk (A)]) q−1 ,
for L =

q

q
q
2(q−1) Γ(
q−1 2
2(q−1) )

> 1. We do this by showing that
q

q

E[(|Xk (A) − E[Xk (A)]|) q−1 ] ≤ L (σ) q−1 ,
with σ =

q
Pk
supτ ∈A (E[ j=1 ξj τj ])2 ; and that

v
v
u
u
k
k
X
X
u
u
t
2
ξj τj ]) ≤ t sup
bj τj2 ≤ E[Xk (A)].
σ = sup (E[
τ ∈A

(53)

τ ∈A j=1

j=1

To establish the first display, note that
"
 q # Z ∞ 

q−1
|Xk (A) − E[Xk (A)]| q−1
E
=
Pr |Xk (A) − E[Xk (A)]| ≥ σt q dt
σ
0
q−1
Z ∞
Z ∞
q−1
(σt q )2
}dt = 2
exp{−0.5t2 q }dt
≤2
exp{−0.5
2
σ
0
0
Z ∞
q
q
q
−1
2 2(q−1)
exp{−w}w 2(q−1) −1 dw
=2
q−1
0
q
q
q
−1
2(q−1)
Γ(
2
)
=2
q−1
2(q − 1)
where the second line follow from lemma 2.4.7 in [53]; the third follows by change of variables
q
> 0 ).
(observe that 2(q−1)
To establish display 53, we start by showing that: for any τ ∈ A, there exists a τ ′ ∈ A such
that
v
u k
k
X
uX
p ′
2
t
bj τj .
bj τj ≤
j=1

j=1

Pk p
By taking τ ′ = |τ | (note that since τ ∈ A, |τ | ∈ A), it follows that ( j=1 bj τj′ )2 =
p
P
P
( kj=1 bj |τj |)2 ≥ kj=1 bj |τj |2 . Therefore
v
u
k
k
X
X
u
p
bj τj2 ≤ sup
bj τj .
σ = t sup
τ ∈A j=1

τ ∈A j=1

By the fact at the beginning of the proof: Xk (A) ≥
E[Xk (A)] ≥

k
X
j=1

τj E[|ξ1 |] =

Step 3. We now show our desired result.

7

Pk

j=1 τj |ξj |

k
X
p
bj τj .
j=1

and thus

By step 2, and the fact that ||a − b||Lr ≥ |||a||Lr − ||b||Lr | for r ≥ 1 by Minkowski inequality,
it follows that
q

q

E[(Xk (A)) q−1 ] ≤ (L + 1) (E[Xk (A)]) q−1 .
By step 1,
k
iX
h
q
q
1
0.5 q
− 1
bj q−1 pj q−1 ≤ (L + 1) (E[Xk (A)]) q−1 ,
(M ) q−1 E |ζ1 | q−1
j=1

or
 q−1
q
k
iX
h
q
1
q
q−1
0.5 q−1
− q−1

bj
(M ) E |ζ1 | q−1
pj
≤ (L + 1) q E[Xk (A)],
1
q



j=1

Pk
The Case q = 1: As it was shown at the beginning of the proof, Xk (A) ≥ j=1 |ξj |τj for
any τ ∈ A. In particular, fix any j = 1, ..., k, let τj = p−1
j M and τl = 0 for all l 6= j, it follows
that ||τ ||ℓ1 (p) = M and thus is in A. Also Xk (A) ≥ |ξj |p−1
j M . Since this construction holds for
any j = 1, .., k, by taking the maximum over j and applying expectations it follows that
p
E[Xk (A)] ≥ E[ max | bj p−1
j ζj |]M.
1≤j≤k

The result thus follows from Lemma OA.3.3 (the lower bound).

OA.3.4.1

Proofs of Supplementary Lemmas

Proof of Lemma OA.3.3. We now establish the right inequality. Note that for any λ > 0,




−1
−1
E max |p−1
ζ
|
=λ
E
log
exp{λ
max
|p
ζ
|}
j
j
j
j
1≤j≤k
1≤j≤k


≤λ−1 log E exp{λ max |p−1
ζ
|}
(by Jensen inequality)
j
j
1≤j≤k


X

≤λ−1 log E 
exp{λ|p−1
j ζj |}
1≤j≤k

−1

=λ

log

X

1≤j≤k
−1

≤λ

log 2

X





−1
E exp{λp−1
j ζj }1{ζj > 0} + E exp{−λpj ζj }1{ζj < 0}

1≤j≤k

=λ−1 log 2

X

1≤j≤k



E exp{λp−1
j ζj } (by symmetry of ζ)

exp{0.5λ2 p−2
j } (by Gaussianity of ζ)

=λ−1 log 2k + λ−1 log k −1

k
X
j=1

exp{0.5λ2 p−2
j }

≤λ−1 log 2k + λ−1 log max exp{0.5λ2 pj−2 }
1≤j≤k

−1

=λ

log 2k + 0.5λ max p−2
j .
1≤j≤k


 q
√
−1
−1/2
2
log
2k,
it
follows
that
E
max
p
ζ
≤ max1≤j≤k p−2
Letting λ = (max1≤j≤k p−2
)
1≤j≤k
j
j
j 0.5 log 2k.
j
q
−1
−1
Clearly max1≤j≤k p−2
.
j = max1≤j≤k pj = (min1≤j≤k pj )

8

We now establish the left inequality. Let Yk ≡ max1≤j≤k pj−1 ζj . Note that, for any a ≥ 0,




−1
−1
−1
E max |pj ζj | ≥E max |pj ζj | max |pj ζj | ≥ a Pr{ max |p−1
j ζj | ≥ a}
1≤j≤k

1≤j≤k

1≤j≤k

≥a Pr{ max

1≤j≤k

|pj−1 ζj |

1≤j≤k

≥ a} = a Pr{Yk ≥ a}.

Clearly it suffices to (lower) bound a Pr{Yk ≥ a}. Observe that
Y
Pr{Yk ≥ a} =1 −
Pr{ζ1 < apj }
1≤j≤k

≥1 − (Φ(a max pj ))k ,
1≤j≤k

because Pr{ζ1 < apj } ≤ Pr{ζ1 < a max1≤j≤k pj }.

By Theorem 2.1 in [21] it follows that 1−Φ(x) ≥ c1 exp{−c2 x2 } with c1 =
and c2 = κ2 for any κ ≥ 1 (in particular, we use κ = 2). Thus



−1

e((π(κ−1)+2))
2κ

q

κ−1
π (π(κ

Φ(a max pj ) ≤ 1 − c1 exp{−c2 (a max pj )2 }.
1≤j≤k

1≤j≤k

Thus


2

k

E [Yk ] ≥ a 1 − (1 − c1 exp{−c2 (a max pj ) })
taking a = (max1≤j≤k pj )−1

q

1≤j≤k



log c1 k
c2 ,

it follows that
r
log c1 k
−1
E [Yk ] ≥ ( max pj )
(1 − (1 − k −1 )k ).
1≤j≤k
c2

The function k 7→ (1−k −1)k is increasing an bounded by e−1 and thus the desired result follows.
Proof of Lemma OA.3.4.


E ||ζ||ℓq (p)




1/q 
k
X


pj |ζj |q  
=E 
j=1


1/q
k
X
≤
pj E [|ζj |q ]
(by Jensen inequality)
j=1



=(E [|ζ1 |q ])1/q 

Also,

k
X
j=1

1/q

pj 


1/q 
k
X




pj |ζj |q  
E ||ζ||ℓq (p) =E 

.

j=1



≥

k
X
j=1

1/q

pj 


=E [|ζ1 |] 

k
X
j=1


k
X
pj
E
P

k
j=1

j=1

1/q

pj 

.

9

pj



|ζj | (by Jensen inequality)


− 1) + 2)

OA.4

Proofs of Supplementary Lemmas in Appendix B.3

Recall that Br (q) =

(r−2)/(2r)
√ R 1
r
, for any r > 2.
2 0 |µq (u)| r−2

Lemma OA.4.1. For any r > 2, any f ∈ F (Θ), ||f ||q ≤ Br (q)||f ||Lr (P) for all q ∈ N, with
!!(r−2)/(2r)
Z 1
√
r
r
−1
Br (q) ≤ 2 0.5
(β (u) + 1) r−2 du + (q + 1) r−2 β(q)

49

β(q)

and
Br (q) ≥

√

2 0.5

Z

1

(β

−1

(u))

r
r−2

du + (q + 1)

r
r−2

!!(r−2)/(2r)

β(1 + q)

β(1+q)

R1
Proof of Lemma OA.4.1. By definition ||f ||2q = 2 0 µq (u)Qf (u)2 du. By Cauchy-Swarchz inequality
Z 1
1/q Z 1
1/p
Z 1
2
q
2p
µq (u)Qf (u)du ≤
|µq (u)|
|Qf (u)|
0

0

0

with 1/q + 1/p = 1. Letting p = r/2, it follows that
(r−2)/r Z
Z 1
Z 1
r
2
r−2
2
µq (u)Qf (u)du ≤2
|µq (u)|
0

0

0

=2

Z

0

1

1

|µq (u)|

r
r−2

(r−2)/r

The final bounds follow from Lemma B.5(3)(4) with a =

|Qf (u)|

r

2/r

||f ||2Lr (P) .
r
r−2 .

Proof of Lemma B.1. Throughout the proof, we use the upper and lower bounds of Br (q) provided by Lemma OA.4.1.
(1) For this case, β −1 (u) = m−1
0 . And thus
√
 r−2
r−2
r
r
2r
r−2 (1 − 1{q < m−1 }) + (q + 1) r−2 1{q < m−1 }
.
Br (q) ≤ 0.5 2r 2 (m−1
0
0
0 + 1)
q
√
So, after simple algebra it follows that Br (q) ≤ (0.5)(r−2)/(2r) 2 min{1 + q, 1 + m−1
0 }.
Also,
 r−2
r−2 √
r
r
2r
r−2 (1 − 1{1 + q < m−1 }) + (1 + q) r−2 1{1 + q < m−1 }
.
Br (q) ≥ 0.5 2r 2 (m−1
0
0
0 )
q
√
√
r−2 √
2r
So Br (q) ≤ (0.5)(r−2)/(2r) 2 min{1 + q, m−1
2 = 21−(r−2)/r =
0 }. Note also that 0.5

21/r .

The upper bound for cases (2) and (4): For all these cases β −1 (u) = (u)−1/m0 − 1, so
!(r−2)/(2r)
Z
1

Br (q) ≤21/r

−m

(u)

r
0 (r−2)

r

du + (1 + q) r−2 (1 + q)−m0

β(q)

r

=2

1/r

=2

1/r

r
1 − (1 + q) (r−2) −m0
+ (1 + q) r−2 −m0
r
1 − m0 (r−2)

1
m0 −

r
r−2


m0 −

!(r−2)/(2r)

r
r
(1 + q) r−2 −m0
r−2

49

!(r−2)/(2r)

.

Recall that the function β −1 : [0, 1] → R+ is defined as β −1 (u) = min{s | β(s) ≤ u} — since β is
right-continuous, the min exists —.

10

For case (2) m0 >

r
r−2 ,

For the case (4), m0 <
q)

r−(r−2)m0
2r

so an upper bound for the RHS in the display is 21/r
r
r−2 ,



m0
r
m0 − r−2

so an upper bound for the RHS in the display is 21/r

.



(r−2)/(2r)

r
r−2

r
r−2 −m0

.
(r−2)/(2r)

The upper bound for case (3): For this case
1

Z

Br (q) ≤ 21/r

(u)−1 du + 1

β(q)

!(r−2)/(2r)

(r−2)/(2r)

= 21/r (m0 log(1 + q) + 1)

.

The lower bound for cases (2) and (4): We first observe that for any 0 ≤ u ≤ β(1) = 2−m0 ,
then u−1/m0 ≥ 2. Therefore ((u)−1/m0 − 1) ≥ 0.5(u)−1/m0 for all 0 ≤ u ≤ β(1) = 2−m0 . Hence
Br (q) ≥2

1/r

1

Z

β(1)

(u

−1/m0

β(1+q)

≥21/r
≥2

Z

1/r

β(1+q)

0.5

r
r−2

− 1)

(u−1/m0 − 1)

Z

β(1)

u

−m

r
r−2

r
r−2

du + (1 + q)

du + (1 + q)

r
0 (r−2)

r
r−2

r
r−2

du + (1 + q)

−m0

(2 + q)

! r−2
2r

(2 + q)−m0

! r−2
2r

r
r−2

−m0

(2 + q)

β(1+q)

=21/r

=21/r

! r−2
2r


r
r
r
m0
2 r−2 −m0 − (2 + q) r−2 −m0 + (1 + q) r−2 (2 + q)−m0
0.5
r
m0 − r−2
!! r−2
r

 r−2
2r
r
r
1
+
q
m
2−m0 m0
0
r−2 −m0
r−2
+
(2
+
q)
−
0.5
r
r
m0 − r−2
2+q
m0 − r−2
r
r−2

For case (2), m0 >

2

1/r

=2

1/r

≥2

1/r

=21/r

r
r−2 ,

then

1+q
2+q

≥ 0.5 and thus the RHS is bounded below by

r
r
2−m0 m0
r−2 −m0 0.5 r−2
r + (2 + q)
m0 − r−2
r
2−m0 m0
r−2 −m0
r − (2 + q)
m0 − r−2

r

2− r−2 r−2
m0 −
r

r
2− r−2 r−2

r
2−m0 m0
r−2 −m0
r − (2)
m0 − r−2
 r−2
2−m0 2r .

m0 −

11

m0
1−
r
m0 − r−2
!! r−2
2r
r

r
r−2

r
r−2

!! r−2
2r

!! r−2
2r

! r−2
2r

(1+

For case (4), m0 <

r
r−2 ,

2

1/r

=21/r

=21/r

≥21/r

by similar arguments, a lower bound is given by
r
2−m0 m0
r−2 −m0
r + (2 + q)
m0 − r−2

r

r
2− r−2 r−2

−m0 +

r
2−m0 m0
r−2 −m0
r + (1 + 0.5q)
m0 − r−2

r
r−2

!! r−2
2r

r
2m0 r−2

−m0 +
! r−2
2r

r
r−2

!! r−2
2r

r
2−m0 m0
((1 + 0.5q) r−2 −m0 − 1)
r
−
m
0
r−2
! r−2
2r
r
2−m0 m0
((1 + 0.5q) r−2 −m0 − 1)
.
r
r−2 − m0

The lower bound for cases (3): By analogous calculations

Br (q) ≥2

1/r

0.5

r
r−2

Z

β(1)

u

−1

du + (1 + q)

r
r−2

−m0

(2 + q)

β(1+q)

! r−2
2r

 r−2
r
=21/r 0.5 r−2 m0 (log(2 + q) − log(2)) + 1 2r
 r−2
√ 
r−2
2r
=21/r 0.5 m0 log(1 + 0.5q) + 2 r
.

OA.5

Proofs of Supplementary Lemmas in Appendix B.4

Proof of Lemma B.2. Recall that ∆k f ≡ πk (f ) − πk−1 (f ), Ξk = −f + πk (f ), and
m(f )(z) = min{k | |vk (f )(z)| > ak }, ∀z ∈ Z.

(54)

Observe that ∆k f = Ξk (f ) − Ξk−1 (f ) and by definition π0 (f ) = 0. Thus, for all z, f (z) =

12

−π0 (f )(z)+π1 (f )(z)+f (z)−π1 (f )(z) = ∆1 (f )(z)+f (z)−π1 (f )(z). Continuing in this fashion,
f (z) =
=
=
=

∞
X

k=1
∞
X

k=1
∞
X

k=1
∞
X
k=1

∆k f (z)
∆k f (z)1m(f )(z)≥k +
∆k f (z)1m(f )(z)≥k +

∞
X

k=1
∞
X
k=1

∆k f (z)1m(f )(z)<k
(Ξk (f ) − Ξk−1 (f )))(z)1m(f )(z)<k

∆k f (z)1m(f )(z)≥k − Ξ0 (f )(z){1m(f )(z)<1} − Ξ1 (f )(z){1m(f )(z)<2 − 1m(f )(z)<1 }

− Ξ2 (f )(z){1m(f )(z)<3 − 1m(f )(z)<2 } − ...
∞
X
=
∆k f (z)1m(f )(z)≥k − Ξ0 (f )(z){1m(f )(z)<1} − Ξ1 (f )(z){1m(f )(z)=1 }
k=1

− Ξ2 (f )(z){1m(f )(z)=2 } − ...
∞
∞
X
X
=
∆k f (z)1m(f )(z)≥k −
Ξk (f )(z)1m(f )(z)=k

=

k=1
∞
X

k=1

k=0

∆k f (z)1m(f )(z)≥k −

∞
X

k=1

Ξk (f )(z)1m(f )(z)=k − Ξ0 (f )(z)1m(f )(z)=0 ,

where the third line follows because 1m(f )(z)<k+1 − 1m(f )(z)<k = 1m(f )(z)=k and 1m(f )(z)<1 =
1m(f )(z)=0 .
P∞
P∞Observe that 1{m(f )(z)≥k∩|vk f (z)|>ak }P=∞1{m(f )(z)=k∩|vk f (z)|>ak } . And thus k=1 ∆k f (z)1m(f )(z)≥k =
k=1 ∆k f (z)1{m(f )(z)≥k∩|vk f (z)|≤ak } +
k=1 ∆k f (z)1{m(f )(z)=k∩|vk f (z)|>ak } . Therefore
f (z) =

∞
X

∆k f (z)1{m(f )(z)≥k∩|vk f (z)|≤ak } +

k=1
∞
X

−

k=1

∞
X

k=1

Ξk (f )(z)1{m(f )(z)=k∩|vk f (z)|>ak } −

− Ξ0 (f )(z)1{m(f )(z)=0} ,

∆k f (z)1{m(f )(z)=k∩|vk f (z)|>ak }
∞
X

k=1

Ξk (f )(z)1{m(f )(z)=k∩|vk f (z)|≤ak }

Since
∞
X

k=1

∆k f (z)1{m(f )(z)=k∩|vk (f )(z)|>ak } =

∞
X

k=1

Ξk f (z)1{m(f )(z)=k∩|vk f (z)|>ak } −

∞
X

k=1

Ξk−1 f (z)1{m(f )(z)=k∩|vk f (z)|>ak } ,

it follows that
∞
X

∆k f (z)1{m(f )(z)=k∩|vk (f )(z)|>ak } −

k=1
∞
X

=−

k=1

∞
X

k=1

Ξk (f )(z)1{m(f )(z)=k∩|vk (f )(z)|>ak }

Ξk−1 f (z)1{m(f )(z)=k∩|vk (f )(z)|>ak } .

Therefore
f (z) =

∞
X

∆k f (z)1{m(f )(z)≥k∩|vk (f )(z)|≤ak } −

k=1
∞
X

−

k=0

∞
X

k=1

Ξk−1 (f )(z)1{m(f )(z)=k∩|vk (f )(z)|>ak }

Ξk (f )(z)1{m(f )(z)=k∩|vk (f )(z)|≤ak } − Ξ0 (f )(z)1{m(f )(z)=0} .

13

Finally, m(f )(z) = k implies that |vk (f )(z)| > ak and thus 1{m(f )(z)=k∩|vk (f )(z)|≤ak } =

0.

Proof of Lemma B.3. Let gk1 (f )(z) ≡ ∆k f (z)1{m(f,z)≥k∩|vk (f )(z)|≤ak } and
gk2 (f )(z) ≡ (I − πk−1 )(f )(z)1{m(f,z)=k∩|vk (f )(z)|>ak } . By lemma B.2,
Ln (f ) =

∞
X

k=1

∞


 X
Ln gk2 (f ) − Ln Ξ0 (f )1{m(f )=0} .
Ln gk1 (f ) +

(55)

k=1

Let for all l = 1, 2,
Ωln (u) = {ω ∈ Ω | ∀f ∈ F (A), |

∞
X


Ln gkl (f ) | ≤ uΓl }.

(56)


Ln Ξ0 (f )1{m(f )=0} | ≤ uΓ3 }.

(57)

k=1

and
Ω3n (u) = {ω ∈ Ω | ∀f ∈ F (A), |

∞
X

k=1

It follows that
!

sup |Ln (f )| ≥ u(Γ1 + Γ2 + Γ3 )

P

f ∈F (A)

≤

3
X
l=1


P Ω \ Ωln (u) .


Pn
Proof of Lemma B.4. Note that |Ln (g) − L∗n (g)| ≤ an−1 i=1 1Zi 6=Zi∗ + P(Zi 6= Zi∗ ) for any


P
√
g ∈ B. Therefore EP supg∈B n|Ln (g) − L∗n (g)| ≤ 2an−1/2 ni=1 P(Zi 6= Zi∗ ).
By our definition of Zi∗ and Zi , P(Zi 6= Zi∗ ) ≤ P(Ui (q) 6= Ui∗ (q)) ≤ β(q).
Proof of Lemma B.5. (1) Since |f | ≤ |g|, it is clear that Hf ≤ Hg and by construction of Q.
the result follows.
(2) Trivial.
(3) Recall that t 7→ β(t) ∈ [0, 1] is cadlag and non-increasing. Let β −1 (u) = min{s | β(s) ≤
u} for u ∈ [0, 1] and β −1 (u) = 0 for u > 1. It is easy to see that µq (u) = min{j(2u), 1 + q}
where j(u) = min{s ∈ N0 | u > β(s)}.
We claim that β −1 (u) ≥ j(u) − 1. By definition of j(u), u ≤ β(j(u) − 1) and by definition of
−1
β (u), β(β −1 (u)) ≤ u; thus β(β −1 (u)) ≤ β(j(u) − 1). Since β(.) is non-increasing, this implies
that β −1 (u) ≥ j(u) − 1.
Therefore, µq (u) ≤ min{β −1 (2u) + 1, q + 1}. And thus, for any a ≥ 0
Z

0

1

(µq (u))a du ≤
≤

Z

1

0

Z

min{(β −1 (2u) + 1)a , (q + 1)a }du

1

(β −1 (2u) + 1)a du + (q + 1)a 0.5β(q)

0.5β(q)
Z 2

=0.5

(β −1 (v) + 1)a dv + (q + 1)a 0.5β(q)

β(q)

=0.5

Z

1

(β

−1

a

a

!

(v) + 1) dv + (q + 1) β(q)

β(q)

14

(since β −1 (u) = 0, f or u > 1).

(4) We first show that β −1 (u) ≤ j(u). Suppose not, i.e., β −1 (u) > j(u). By definition of
j(u), u > β(j(u)). But this violates the property that β −1 (u) is the minimum over all s such
that β(s) ≤ u. Therefore, µq (u) ≥ min{β −1 (2u), q + 1} and thus
Z

0

1

a

(µq (u)) du ≥
=

Z

1

(min{β −1 (2u), q + 1})a du

0

Z

1

(β −1 (2u), 1)a du + (q + 1)a 0.5β(1 + q)

0.5β(q+1)
Z 2

=0.5

(β −1 (v))a dv + (q + 1)a 0.5β(1 + q)

β(q+1)

Z

=0.5

1

(β

−1

a

a

!

(v)) dv + (q + 1) β(1 + q) .

β(q+1)

Proof of Lemma B.6. We divide the proof into several steps.
Rǫ

Qf (t)dt for any ǫ ∈ [0, 1).50 For any q, by definiqR
√
u
tion of ||.||q and the fact that u 7→ Qf (u) is non-increasing, ||f ||q ≥ 2 supu≤t Qf (u) 0 µq (v)dv
Step 1. Note that ||f 1{f >Qf (ǫ)} ||L1 ≤

for all t ∈ [0, 1). Therefore Qf (u) ≤

0

||f ||q
√ √R u
µq (v)dv
2
0

||f 1{f >Qf (ǫ)} ||L1 ≤ ||f ||q

Z

for all u < 1. Hence, for any ǫ ∈ [0, 1),

ǫ

0

1
dt.
√ qR t
2 0 µq (v)dv

Let ǫk = n−1 q n,k 2k+1 where q n,k is maximal element of Qn lower than qn,k . We note that

ǫk is less than 1 by the definition of qn,k and the fact that β(.) ≤ 1. Clearly, if
then
Z ǫk
1
dt.
||f 1{f >bk /qn,k } ||L1 ≤ ||f ||qn,k
√ qR t
0
2 0 µqn,k (v)dv
Step 2. We now establish that in fact
to show that

bk
qn,k

Since ǫk = n

||f ||
≥ √µ (ǫq

−1

qn,k

q n,k 2

k+1

k )ǫk

bk
qn,k

.

bk
qn,k

≥ Qf (ǫk ),

(58)

≥ Qf (ǫk ). Since µq is non-increasing, if suffices

,
qn,k

µqn,k (ǫk ) = µqn,k (n

−1

(q n,k )2

k+1

)=

X
i=0

1{n−1 (q

n,k

)2k+1 ≤0.5β(i)} .

By definition of qn,k , n−1 q n,k 2k+1 < 0.5β(q n,k ). Since β(.) is non-increasing, this implies that
Pqn,k
n−1 q n,k 2k+1 < 0.5β(i) for all i = 0, ..., q n,k and thus µqn,k (ǫk ) = i=0
1{n−1 q 2k+1 ≤0.5β(i)} ≥
n,k
q n,k . This implies that
r
q
√
n
µqn,k (ǫk )ǫk ≥ q n,k n−1/2 2k+1 = ǫk
.
2k+1
Qυ
i
for some integers (mi )i , it
Since qn,k ∈ Qn and n is restricted to be of the form i=1 pm
i
follows by Lemma OA.1.1 in Appendix OA.1, that qn,k ≤ pυ q n,k .
50

The case for ǫ = 0 comes from the fact that for f ∈ F ⊆ L1 , the RHS is zero since Qf (0) = ∞.

15

Hence qn,k ≤ pυ nǫk /2k+1 , and thus, from the previous display it follows that

since bk
||f ||qn,k .

r
r
n
2k+1
2k+1
1 q
1
µqn,k (ǫk )ǫk ≥
ǫk
=
,
k+1
qn,k
pυ nǫk
2
pυ
n
√
√
= B0 n||f ||qn,k / 2k+1 and B0 = pυ , it readily follows that

bk
qn,k

p
µqn,k (ǫk )ǫk ≥

Step 3. By step 1-2 we have

||f 1{f >bk /qn,k } ||L1 ≤

R ǫk
0

||f ||qn,k
√
2

ǫk

0

1
qR
t
0

dt.

(59)

µqn,k (v)dv

Rt
Since u 7→ µq (u) is non-increasing, t 7→ t−1 0 µqn,k (v)dv is also non-increasing and thus
q
q
R ǫk −1/2
R
ǫ
ǫk
1
qR
R ǫk
t
dt. Thus the RHS
dt = 0 k R t µ t (v)dv t−1/2 dt ≤
t
(v)dv 0
µ
0

µqn,k (v)dv

0

qn,k

0

q
||f ||q
is bounded above by √2n,k R ǫk µ ǫk (v)dv
qn,k
0
qR ǫ ǫk
√ ǫk
.
Therefore,
≤
k µ
ǫk µqn,k (ǫk )
(v)dv
q
0

Z

R ǫk

1
√
dt
t

0

qn,k

√
= 2||f ||qn,k qR ǫk
0

ǫk

µqn,k (v)dv

. By Step 2,

n,k

||f 1{f >bk /qn,k } ||L1 ≤

√

2||f ||qn,k

r

ǫk
.
µqn,k (ǫk )

r −1
q
√
n q n,k 2k+1
By the calculations in Step 2, µq ǫk(ǫk ) ≤
= n−1/2 2k+1 . We thus conclude
q
n,k
n,k
√
√
that ||f 1{f >bk /qn,k } ||L1 ≤ 2||f ||qn,k n−1/2 2k+1 as desired.
Proof of Lemma B.7. We note that since q ∈ Qn , J is an integer equal to n/q − 1. Throughout,
Pqj+q
we use J = J(q, n) = n/q − 1. Let f 7→ δj (ω ∗ )(f ) = q −1/2 i=qj+1 {f (Zi∗ ) − EP∗ [f (Z ∗ )]} for
any j = 0, 1, 2, .... Then, it follows that for any f ∈ F ,
L∗n (f )

=n

−1

n
X

f¯(Zi∗ ) = n−1

jq+q
J
X
X

√
f¯(Zi∗ ) = n−1 q

j=0 i=jq+1

i=1

J
X

δj (ω ∗ )(f )

j=0

∗
∗
where δj (ω ∗ )(f ) is measurable with respect to Uj∗ (q) = (Zqj+1
, ..., Zqj+q
).
PJ
P[J/2]
P[(J+1)/2]−1
a2j+1 , then
Note that, for any sequence (aj )j , j=0 aj = j=0 a2j + j=0



[(J+1)/2]−1
[J/2]
X
X
√ ∗
√
nLn (f ) = n−1/2 q 
{δ2j+1 (ω ∗ )(f )} .
{δ2j (ω ∗ )(f )} +

51

(60)

j=0

j=0

Observe that for any t > 0,

√
P nL∗n (f ) ≥ t


[J/2]
X
√
≤P n−1/2 q
{δ2j (ω ∗ )(f )} ≥ 0.5t
j=0



51

√
+ P n−1/2 q

[(J+1)/2]−1

X



{δ2j+1 (ω ∗ )(f )} ≥ 0.5t .

j=0

Here, [a] = max{n ∈ N : n ≤ a}.

16

(61)

Thus, it suffices to bound each term in the RHS separately.
∗
∗
By the conditions in Section 3, (U2j
(q))j≥0 are i.i.d. (so are (U2j+1
(q))j≥0 ). Moreover,
∗
they have the same distribution as (U2j (q))j≥0 (also (U2j+1 (q))j≥0 has the same distribution
as (U2j+1 (q))j≥0 ). Thus, we can replace EP∗ [.] by EP [.] in the definition of δj (ω ∗ )(f ).
√
It is easy to see that for any f ∈ F , ||δj (ω ∗ )(f )||L∞ ≤ q2||f ||L∞ . Moreover, by [44]
Corollary 1.2 and Lemma 1.2, for any f ∈ F ,
EP∗ [(δ0 (ω ∗ )(f ))2 ] =EP [(δ0 (ω)(f ))2 ]
=V arP (f (Z0 )) + 2

q
X

(1 − k/q)CovP (f (Z0 ), f (Zk ))

k=1

≤4

q
X
1

≤4

Z

1

≤4

Z

1

=4

Z

(1 − k/q)

k=0

0

0

0

q
X

k=0
q
X

k=0

Z

0

αk

Q2f (u)du
!

(1 − k/q)1{u ≤ 0.5β(k)} Q2f (u)du
!

1{u ≤ 0.5β(k)} Q2f (u)du

µq (u)Q2f (u)du = 2||f ||2q

where (αk )k are the strong mixing coefficients and the second line follows because αk ≤ 0.5β(k)
(e.g. see [44]).
Remark OA.5.1. By setting β(0) = 2, for the i.i.d. case — wherein β(q) = 0 for any q > 0
R1
— the display implies that EP∗ [(δ0 (ω ∗ )(f ))2 ] ≤ 4 0 1{u ≤ 1}Q2f (u)du = 4||f ||2L2 . Thus, our
approach looses a factor of 4 for the simple i.i.d. case. Hence, in situations where i.i.d.-ness is
imposed one could obtain better constants in this lemma. △
By Bernstein inequality (see [57] Lemma 2.2.9), it follows that


(
)
r [J/2]
−1
2
X
q
0.5q
nu
P∗ 
{δ2j (ω ∗ )(g)} ≥ u ≤ exp − P[J/2]
p
√
1
∗
2
n j=0
nq −1 u2 q||g||L∞
j=0 EP∗ [(δ2j (ω )(g)) ] + 3
)
(
0.5q −1 nu2
= exp − P[J/2]
2√
∗
2
j=0 EP∗ [(δ2j (ω )(g)) ] + 3 nu||g||L∞
(
)
0.5nq −1 u2
= exp −
√
(0.5J + 1)2||g||2q + 32 nu||g||L∞
(
)
0.5u2
≤ exp −
2||g||2q + 32 u √qn ||g||L∞




2
u

≤ exp − 
 4 b2 + 1 u √q ||g|| ∞ 
3

n

L

where the second line follows from the fact that EP∗ [(δ2j (ω ∗ )(g))2 ] = EP∗ [(δ0 (ω ∗ )(g))2 ] (stationarity) and our previous observations; the third line follows from simple algebra and the fact
that J − 1 = nq and n/q ≥ 1; the last one from ||g||q ≤ b.
If b2 ≥ 31 u √qn ||g||L∞ , then


r [J/2]


X
u2
q
{δ2j (ω ∗ )(g)} ≥ u ≤ exp − 2
P∗ 
n j=0
8b

17

so


P∗ 

r


[J/2]
√

q X
{δ2j (ω ∗ )(g)} ≥ t 8b ≤ exp −t2
n j=0

Otherwise, if b2 < 31 u √qn ||g||L∞ , then


so

P∗ 


P∗ 

r

r


(
)
[J/2]
q X
u
∗

{δ2j (ω )(g)} ≥ u ≤ exp − 8 q
√
n j=0
∞
3 n ||g||L


X

8 q
q
{δ2j (ω ∗ )(g)} ≥ t2 √ ||g||L∞  ≤ exp −t2 .
n j=0
3 n
[J/2]

√
We are interested in t = u2k/2 for any u ≥ 1. Note also that ||g||L∞ ≤ B0 q −1 nb √1 k .
2
Hence
√
1 q
1 q
8 q
t2 √ ||g||L∞ 1{t √ ||g||L∞ > b2 } + 8tb1{t √ ||g||L∞ < b2 }
3 n
3 n
3 n
√
8B0 k/2
1 q
1 q
≤u2
2 b1{t √ ||g||L∞ > b2 } + 8u2k/2 b1{t √ ||g||L∞ < b2 }
3
3 n
3 n


√
1 q
8B0
1 q
≤u2 b2k/2
1{t √ ||g||L∞ > b2 } + 81{t √ ||g||L∞ < b2 }
3
3 n
3 n
8B
0
≤u2 b2k/2
,
3
√
where the third line follows since u ≥ 1 and since B0 ≥ 2, 8B0 /3 ≥ 16/3 ≥ 8.
Therefore,


r [J/2]
X

8B
q
0
{δ2j (ω ∗ )(g)} ≥ u2 2k/2 b
≤ exp −u2 2k .
P∗ 
n j=0
3
The same result holds for
desired result follows.

OA.6

P[(J+1)/2]−1
j=0

{δ2j+1 (ω ∗ )(g)}. And thus, by equation 61, the

Proofs of Supplementary Lemmas in Appendix D

Proof of Lemma D.1. Convexity: It is well-known (e.g. [34]) that θ 7→ Q(θ, P) = EP [φ(Z, θ)]
is convex.
R XT θ
Continuity: Note that Q(θ, P) = τ EP [Y − X T θ] − EP [ −∞ (y − X T θ)F (dy|X)] = τ EP [Y −
R XT θ
X T θ] − EP [ −∞ yf (y|X)dy] + EP [X T θF (X T θ|X)].
Clearly θ 7→ EP [X]T θ is continuous. Also θ 7→ F (X T θ|X) is continuous a.s. and by the
dominated convergence theorem (DCT), θ 7→ EP [F (X T θ|X)X] is too. Since y 7→ yf (y|X) is inR XT θ
R XT θ
R∞
tegrable a.s.; θ 7→ −∞ yf (y|X)dy is continuous a.s. Clearly, | −∞ yf (y|X)dy| ≤ −∞ |y|f (y|X)dy ≡
R XT θ
H(X) and EP [H(X)] = EP [|Y |] < ∞ and thus by the DCT, θ 7→ EP [ −∞ yf (y|X)dy] is continuous.

18

Coercivity: We now show that: For all M > 0, {θ ∈ Θ | EP [φ(Z, θ)] ≤ M } is bounded. For
this, suppose that : For all (θn )n such that θn ∈ Θ and limn→∞ ||θn ||ℓ2 = ∞, then
P({X : lim |X T θn | = ∞}) > 0.

(62)

n→∞

(We show this at the end of the proof).
We do the proof by contradiction, that is: Suppose there exists a M0 > 0 such that S(M0 ) ≡
{θ ∈ Θ | EP [φ(Z, θ)] ≤ M0 } is unbounded. That is, there exists a sequence (θn )n such that
θn ∈ S(M0 ) and limn→∞ ||θn ||ℓ2 = ∞. Take A the set of X’s such that limn→∞ |X T θn | = ∞;
this set has positive probability by 62. Moreover, for any x in such set (y − xT θn ) → ±∞
a.s., and thus φ(z, θ) → ∞ a.s. That is, the set {Z | φ(Z, θn ) → ∞} has positive measure,
thus implying by Fatou’s lemma that EP [φ(Z, θn )] → ∞. But this contradicts the fact that
θn ∈ S(M0 ).
We now show display 62. The idea is that if it does not hold, then the two or more
components of X are linearly dependent. Take any (θn )n in Θ, note that
|X T θn |
|X T θn |
] = lim E[
] ≤ emax (E[XX T ])
n→∞ ||θn ||ℓ2
n→∞
||θn ||ℓ2

EP [ lim
T

θn |
T
because |X
||θn ||ℓ2 ≤ emax (XX ) is integrable.
Also note that

|X T θn |
] ≥ emin (E[XX T ]) > 0.
n→∞ ||θn ||ℓ2

EP [ lim

Letting e ≡ emin (E[XX T ]) and by the fact that E[X] ≤ a + E[X|X > a] Pr(X > a) for any
random variable X and any a > 0, it follows that by setting a = 0.5e,
|X T θn |
|X T θn |
|X T θn |
| lim
> 0.5e]P( lim
> 0.5e)
n→∞ ||θn ||ℓ2
n→∞ ||θn ||ℓ2
n→∞ ||θn ||ℓ2
2

|X T θn |
|X T θn |
−1
]P( lim
> 0.5e)
≤(0.5e) EP [ lim
n→∞ ||θn ||ℓ2
n→∞ ||θn ||ℓ2
|X T θn |2
|X T θn |
=(0.5e)−1 EP [ lim
]P( lim
> 0.5e)
2
n→∞ ||θn || 2
n→∞ ||θn ||ℓ2
ℓ

0.5e ≤EP [ lim

=(0.5e)−1 lim EP [
n→∞

|X T θn |
|X T θn |2
]P( lim
> 0.5e),
2
n→∞ ||θn ||ℓ2
||θn ||ℓ2

where the last line follows from the DCT and the fact that
T

2

|X T θn |2
||θn ||22
ℓ

≤ emax (XX T ), which it is

θn |
] ≤ emax (E[XX T ]) < ∞ the display above
integrable as argued above. Since limn→∞ E[ |X
||θn ||2
ℓ2

T

θn |
implies that P(limn→∞ |X
||θn ||ℓ2 > 0.5e) > 0.
Since this result holds for any sequence and e > 0, this implies display 62.

Continuous Differentiability: We now show that θ 7→ EP [φ(Z, θ)] is twice-continuously
differentiable. Clearly θ 7→ EP [X]T θ is twice-continuously differentiable. Also, since θ 7→
R xT θ
T
−∞ yf (y|x)dy is continuously differentiable (since θ 7→ x θ is continuously differentiable and
R R xT θ
y 7→ yf (y|x) are continuous), then θ 7→
yf (y|x)dyP(dx) is continuously differentiable
−∞
T
T
with derivative equal to x θf (x θ|x) which is also continuously differentiable under our asR R xT θ
sumptions. Finally, θ 7→ θT x −∞ f (y|x)dyP(dx) is too by similar arguments.
Proof of Lemma D.2. For part (1), observe that for any u1 ≤ u2

|u1 − u2 |

|u1 | ≤ −u1 + u2 = |u1 − u2 |
|u1 1{u1 ≤ 0} − u2 1{u2 ≤ 0}| =

0

19

if u1 ≤ u2 ≤ 0
if u1 ≤ 0 ≤ u2
if 0 ≤ u1 ≤ u2

Thus,
|φ(z, θ1 ) − φ(z, θ2 )| ≤|xT (θ1 − θ2 )|(1 + τ )
q
≤(1 + τ ) (θ1 − θ2 )T xxT (θ1 − θ2 )

(63)
(64)

T

≤(1 + τ )emax (xx )||θ1 − θ2 ||ℓ2 .

(65)

Assumption 4.2(2) holds with r = π0 by our assumptions in Example 2.1.
Let ∂f (x0 ) be the set of sub-gradients of function f at x0 .
Lemma OA.6.1. Let f : Rd → R and g : Rd → R where f is convex and twice continuously
differentiable and g is convex. Let h = f + ag for a ≥ 0. Then:
(1)
∂h(x0 ) = {u ∈ Rd | u =

df (x0 )
+ av, with v ∈ ∂g(x0 )}
dx

for any x0 ∈ Rd .
(2) x0 is a minimizer of h iff 0 ∈ ∂h(x0 ).
Proof. Both f and ag are proper functions (see [46] p. 24). The domain of f and g coincide (and
so does its relative interior see [46] p. 44). By Theorem 23.8 in [46], ∂h(x0 ) = ∂f (x0 )+∂ag(x0 ) =
(x0 )
∂f (x0 ) + a∂g(x0 ). Since f is differentiable, ∂f (x0 ) = { dfdx
}.
By Theorem 23.5 in [46] 0 ∈ ∂h(x0 ) iff −h(x0 ) achieves its supremum.
Proof of Lemma D.3. By lemma D.1 Qk (·, P) is twice continuously differentiable, and thus
Qk (θ, P) − Qk (θ0,k , P) =

=

dQ(θ0,k , P)
[θ − θ0,k ]
dθT
Z 1 2
d Q(θ0,k + t(θ − θ0,k ), P)
+ 0.5
[θ − θ0,k , θ − θ0,k ]
dθT dθ
0
+ λk (P en(θ) − P en(θ0,k ))

dQ(θ0,k , P)
[θ − θ0,k ] + λk µT (θ − θ0,k )
dθT
Z 1 2
d Q(θ0,k + t(θ − θ0,k ), P)
+ 0.5
[θ − θ0,k , θ − θ0,k ]dt
dθT dθ
0
+ λk (P en(θ) − P en(θ0,k ) − µT (θ − θ0,k ))

where µ ∈ ∂(P en(θ0,k )) (is well defined since P en is convex; see Lemma OA.6.1). Hence
P en(θ) − P en(θ0,k ) − µT (θ − θ0,k ) ≥ 0. Also, θ0,k is a minimizer of Qk (·, P) and θ 7→ Q(θ, P)
is convex and continuously differentiable (see Lemma D.1) and P en is convex. Thus by lemma
dQ(θ0,k ,P)
[θ − θ0,k ] + λk µT (θ − θ0,k ) = 0.
OA.6.1, one can choose µ such that
dθ T
Proof of Lemma D.4. (1) Suppose not, then there exists a C1 > C2 but rI (C1 ) < rI (C2 ).
By definition of rI (C1 ) there exists a sequence (rI,m (C1 ))m such that rI,m (C1 ) ∈ SI (C1 ) and
rI,m (C1 ) → rI (C1 ). Hence, for sufficiently large m, rI,m (C1 ) < rI (C2 ).
Γ (I
(ω)(rI (C1 )x))
Γ (I
(ω)(r
(C1 )x))
< C1 maxx≥1 k n,krI (C1 )x
,
Thus, it must hold that rI,m (C1 ) < C2 maxx≥1 k n,krI,m (CI,m
1 )x
but this is a contradiction to the fact that rI,m (C1 ) ∈ S(C1 ). An analogous results holds for
rJ .
(2) Suppose not. Then there exists a C such that rI (C) > rJ (C), but then, it must
Γ (I
(ω)(r (C)x))
hold that rJ (C) < C maxx≥1 k n,krJ (C)xJ
(or for a subsequence converging to rJ (C)).
Since In,k (ω)(r) ⊆ Jn,k (ω)(r), by definition of Γk , rJ (C) < C maxx≥1
contradiction to the fact that rJ (C) (or a subsequence) belongs to SJ (C).

20

Γk (Jn,k (ω)(rJ (C)x))
;
rJ (C)x

a

(3) Suppose not. Then there exists a C such that rJ (C) > CrJ (1). By definition of
rJ (1) there exists a sequence (rJ,m (1))m such that rJ,m (1) ∈ SJ (1) and rJ,m (1) → rJ (1).
That is, for sufficiently large m, rJ (C) > CrJ,m (1). Thus, it must hold that CrJ,m (1) <
Γ (J
(ω)(CrJ,m (1)x))
C maxx≥1 k n,kCrJ,m (1)x
. However
rJ,m (1) ≥ max
x≥1

Γk (Jn,k (ω)(rJ,m (1)x′ ))
Γk (Jn,k (ω)(rJ,m (1)x))
≥
rJ,m (1)x
rJ,m (1)x′

for any x′ ≥ 1. In particular x′ = zC where z ≥ 1 is such that
Γ (J
(ω)(rJ,m (1)Cx))
.
maxx≥1 k n,krJ,m (1)Cx

Γk (Jn,k (ω)(rJ,m (1)Cz))
rJ,m (1)Cz

=

′

Since C ≥ 1, x ≥ 1 is a valid choice. Thus

CrJ,m (1) ≥ C max
x≥1

Γk (Jn,k (ω)(rJ,m (1)Cx))
;
rJ,m (1)Cx

a contradiction to the fact that rJ (C) is minimal. An analogous results holds for rI .
(4) By using the same arguments as in (2), rJ (C) ≤ inf r∈TJ (C) r with TJ (C) ≡ {r > 0 | r ≥
min{xrΛn,k (ω),Bn,k (ω)}
B
(ω)
max{xrΛn,k (ω),Bn,k (ω)}
}. Clearly,
≤ min{Λn,k (ω), n,kr }. By
C maxx≥1
xr
xr
applying the arguments in (2) again, it follows that rJ (C) is less or equal than
Bn,k (ω)
}}.
r
p
p
p
Consider t∗ = min{CΛn,k (ω), CBn,k (ω)}. If CΛn,k (ω) > CBn,k (ω), then t∗ = CBn,k (ω)
min{r > 0 | r ≥ C min{Λn,k (ω),

and

t∗ = min{CΛn,k (ω),

If CΛn,k (ω) <

q
CBn,k (ω)}

Bn,k (ω)
Bn,k (ω)
=C min{Λn,k (ω), p
}.
} = C min{Λn,k (ω),
t∗
CBn,k (ω)
p
CBn,k (ω), t∗ = CΛn,k (ω), and

C min{Λn,k (ω),

Bn,k (ω)
Bn,k (ω)
} = min{CΛn,k (ω),
}
t∗
Λn,k (ω)
Bn,k (ω)
=CΛn,k (ω) min{1,
}
C(Λn,k (ω))2
=CΛn,k (ω) = t∗ ,

because

Bn,k (ω)
C(Λn,k (ω))2

> 1. Thus t∗ belongs to r ≥ C min{Λn,k (ω),

21

Bn,k (ω)
},
r

and thus rJ (C) ≤ t∗ .

