Noname manuscript

Prediction Error Bounds for
Linear Regression With the TREX

arXiv:1801.01394v1 [] 4 Jan 2018

Jacob Bien · Irina Gaynanova ·
Johannes Lederer∗ · Christian Müller

Received: date / Accepted: date

Abstract The TREX is a recently introduced approach to sparse linear regression. In contrast to most well-known approaches to penalized regression,
the TREX can be formulated without the use of tuning parameters. In this
paper, we establish the first known prediction error bounds for the TREX.
Additionally, we introduce extensions of the TREX to a more general class of
penalties, and we provide a bound on the prediction error in this generalized
setting. These results deepen the understanding of TREX from a theoretical
perspective and provide new insights into penalized regression in general.
Keywords TREX · high-dimensional regression · tuning parameters · oracle
inequalities
Mathematics Subject Classification (2000) 62J07

1 Introduction
The high dimensionality of contemporary datasets has fueled extensive work
in developing and studying penalized estimators, such as the LASSO [45],
SCAD [23], and MCP [49]. However, the performance of each of these estimators depends on one or more tuning parameters that can be difficult to calibrate. In particular, among the many different approaches to the calibration
of tuning parameters, only very few are equipped with theoretical guarantees.
The TREX [35] is a recently proposed approach to sparse regression that
attempts to sidestep this calibration issue by avoiding tuning parameters altogether. Numerical studies have suggested that it may be a competitive basis
∗ Johannes

Lederer
Departments of Statistics and Biostatistics
University of Washington
Box 354322
Seattle, WA 98195-4322
E-mail: ledererj@uw.edu

2

Bien, Gaynanova, Lederer, Müller

for high-dimensional linear regression and graph estimation [35]. Moreover,
the TREX fits within the knockoff framework of [5], leading to theoretical
bounds for false discovery rates [8]. On the other hand, the TREX has not
yet been equipped with any oracle inequalities, which form the foundation of
high-dimensional theories.
In this paper, we make two contributions.
– We develop the first prediction error bounds for linear regression with the
TREX.
– We extend the TREX to a class of more general penalties.
These results represent a first step toward a complete theoretical treatment
of the TREX approach. In addition, the results highlight the role of tuning
parameters in high-dimensional regression in general. For example, while most
results in the literature make statements about an estimator assuming an
oracle could choose the tuning parameter, the prediction error bounds we
present pertain to the TREX as it would actually be used by a practitioner.
Finally, despite its non-convex objective function, recent work has shown that
the TREX can be efficiently globally optimized using machinery from convex
optimization [8]. This property plays a key role in closing a practical gap that
would otherwise be present in any theoretical results that are based on the
global minimizer.
The rest of the paper is organized as follows. In the remainder of this section, we specify the framework and mention further literature. In Section 2, we
review the TREX approach. In Section 3, we present the theoretical guarantees. In Section 4, we formulate an extension of the TREX to arbitrary norm
penalties and show how the theory presented earlier generalizes to this context. In Section 5, we conclude with a discussion. The proofs are deferred to
the Appendix.

Framework and Notation
We consider linear regression models of the form
Y = Xβ ∗ + ε,

(1)

where Y ∈ Rn is a response vector, X ∈ Rn×p a design matrix, and ε ∈ Rn
a noise vector. We allow in particular for high-dimensional settings, where
p rivals or exceeds n, and general distributions of the noise ε that do not
need to be known to the statistician. Typical targets in this framework are β ∗
(estimation), the support of β ∗ (variable selection), or Xβ ∗ (prediction). In
this study, we focus on prediction.
Pl
Throughout the manuscript, we use the norms kvk1 := i=1 |vi |, kvk2 :=
Pl
( i=1 vi2 )1/2 , and kvk∞ := maxi∈{1,...,l} |vi | for vectors v ∈ Rl , l ∈ {1, 2, . . . }.

Prediction Error Bounds for Linear Regression With the TREX

3

Related Literature
While this work is focused exclusively on the TREX, for completeness, we
mention some alternative approaches to tuning parameter calibration. Calibration schemes for the LASSO have been introduced and studied in various
papers, including [15,16,17,29,39,42,43]. A LASSO-type algorithm with variable selection guarantees was introduced in [37]. The square-root LASSO [6],
described in the next section, and similarly the scaled LASSO [44] are aimed
at avoiding the calibration to the noise variance. A version of the square-root
LASSO with a group penalty was formulated in [11].

2 A Brief Review of the TREX Approach
The TREX was motivated by a reformulation and extension of the square-root
LASSO approach. Following the line of arguments in [35], we first review the
LASSO estimator [45] defined as
o
n
β̃(λ) ∈ arg min kY − Xβk22 + 2λkβk1

(λ > 0).

(2)

β∈Rp

It is well-understood that tuning parameters of the form
λ = hkX ⊤ εk∞ = hσkX ⊤ ζk∞ ,
where h > 0 is a constant, and where we factor out the standard deviation of
the noise σ (that is, ζ := ε/σ) for illustration purposes, can be theoretically
sound—see [10] and references therein. Indeed, these choices for λ follow from
oracle inequalities for the LASSO (see the next section). In practice, however,
the corresponding calibration of λ can be challenging, because hσkX ⊤ ζk∞ is
a random quantity that depends on several aspects of the model, including
the design matrix X and the in practice unknown standard deviation of the
noise σ and noise vector ζ.
The square-root LASSO [6] is designed to obviate the need for calibration
with respect to the standard deviation of the noise. As described in [35], one
can write the square-root LASSO as
(
)
kY − Xβk22
β̄(γ) ∈ arg min
(γ > 0) ,
(3)
+ γkβk1
kY −Xβk
β∈Rp

√
n

2

which highlights
the view of this as the LASSO with a scaling factor of
√
kY − Xβk2 / n. This factor acts as an inherent estimator of the standard
deviation of the noise σ and therefore makes further calibration of σ unnecessary. A suitable theoretical form of γ is (see, for example, [6])
γ = hkX ⊤ζk∞

4

Bien, Gaynanova, Lederer, Müller

for constants h > 0. Note that hkX ⊤ ζk∞ is still a random quantity that
depends on the typically unknown ζ, so that γ is still subject to a tuning
scheme.
The motivation for the TREX is to automatically calibrate all model parameters. The key idea is to estimate the entire quantity σkX ⊤ ζk∞ rather
than σ alone. Thus, in line with the discussion above, σkX ⊤ ζk∞ is mimicked
by kX ⊤ (Y − Xβ)k∞ , leading to the estimator
β̂ ∈ arg min
β∈Rp

n

o
kY − Xβk22
,
+
kβk
1
ckX ⊤ (Y − Xβ)k∞

(4)

where c ∈ (0, 2) is a constant. The value c = 1/2 is used in the original
TREX proposal [35]. With this setting, TREX is a single, tuning-free estimator. Similar to the bootstrap LASSO [3], the TREX can be equipped with
bootstrapping techniques for variable ranking [35] or used for graphical model
learning using node-wise regression [34].
An initial practical challenge regarding the TREX estimator was the nonconvexity of the underlying objective function in (4). While first approaches
to minimizing the TREX objective function relied on fast heuristic approximation schemes [35], it was shown in [8] that the globally optimal solution of
the TREX objective can be found in polynomial time via convex optimization
techniques. This was achieved by stating the problem in (4) as an equivalent minimization problem over 2p convex sub-problems. These sub-problems
can be solved via second-order cone programming [8] or proximal algorithms
thanks to the existence of efficient proximity operators [18]. In the n > p
setting, availability of the globally optimal solution and the different convex
sub-problem solutions led to provable guarantees on false discovery rates of the
TREX [8] by extending the knock-off filter framework originally introduced in
[5]. Other theoretical guarantees for the TREX have, thus far, remained elusive.

3 Theoretical Guarantees for the TREX
Here, we derive novel theoretical guarantees for sparse linear regression with
the TREX. We focus on guarantees on the prediction loss kX β̂ − Xβ ∗ k22 /n,
which is an important step toward a complete understanding of the theoretical
properties of the TREX. We use the LASSO as a point of reference, since it
is the most well-known and well-studied approach for sparse linear regression.
For ease of exposition, we consider fixed design matrices
X that are normal√
ized such that each column has Euclidean norm n. We also do not impose
restrictions on the noise distribution; in particular, we allow the entries of the
noise vector to be correlated, the noise vector ε and the design matrix X to
be correlated, and we allow for heavy-tailed noise distributions. The proofs of
our results are deferred to the Appendix.

Prediction Error Bounds for Linear Regression With the TREX

5

3.1 Review of Bounds for LASSO-type Estimators
For the LASSO estimator defined in (2), two types of prediction bounds are
known in the literature. The first type is termed a “fast-rate bound.” A standard representative invokes the compatibility condition
√
skXηk2
(5)
for all η ∈ Rp such that kηS c k1 ≤ 3kηS k1 ,
ν≤ √
nkηS k1

where ν > 0 is a constant, S := supp(β ∗ ) is the support of β ∗ (the index
set of the non-zero entries of β ∗ ), S c the complement of S, and s := |S| the
sparsity level. The compatibility condition ensures that the correlations in the
design matrix X are small. Under this assumption, the prediction loss can be
bounded as follows, cf. [10, Theorem 6.1].

Lemma 1 If λ ≥ 2kX ⊤εk∞ and the compatibility condition (5) is met for a
constant ν > 0, the prediction loss of the LASSO satisfies
kX β̃(λ) − Xβ ∗ k22
16sλ2
≤ 2 2.
n
ν n
Similar bounds for the lasso can be found in [7,12,13,14,19,20,21,22,25,26,40,
41]. Note that we have adopted
the normalization 1/n of the prediction error
√
throughout, relating to the n-normalization of the columns of X. If one would
know the true support of β ∗ , then a least-squares on this support would have
expected prediction loss sσ 2 /n. The above result states that the lasso can—
under the given assumptions—achieve the same rate up to constants and an
“entropy” factor encapsulated in λ2 . Indeed, if λ = 2kX ⊤εk∞ , we recover the
rate sσ 2 /n up to the constant 16/ν 2 and the entropy factor kX ⊤ εk2∞ /(σ 2 n).
Given a distribution, one can bound the latter factor in probability by using
maximal inequalities, see [9,24,46] or more recently [27,33,47]. In the case of
i.i.d. Gaussian noise, for example, we find that the factor can be bounded by
h log p with a sufficiently large constant h.
Such bounds can also be derived for the square-root LASSO and other
penalized regression methods. For example, using the techniques in [6], one
can derive (under some minor additional conditions) that there are constants
h, h′ > 0 such that if γ ≥ hkX ⊤ ζk∞ , the prediction loss of the square-root
LASSO in (3) satisfies
kX β̄(γ) − Xβ ∗ k22
h′ sσ 2 γ 2
.
≤
n
ν 2 n2
The same bound (except for slightly different assumptions and constants) holds
also for LASSO-LinSelect [4], for example. We refer the reader to [29, Proposition 4.2 and 4.3] for detailed prediction bounds for the square-root LASSO
and LASSO-LinSelect.
The second type of bound is termed a “slow-rate bound.” In strong contrast
to the “fast-rate bounds,” these bounds provide guarantees on the prediction
error without assuming weakly correlated X. The standard representative for
this type of bound is as follows [31,32,38,41].

6

Bien, Gaynanova, Lederer, Müller

Lemma 2 If λ ≥ kX ⊤εk∞ , the prediction loss of the LASSO satisfies the
following bound:
4λkβ ∗ k1
kX β̃(λ) − Xβ ∗ k22
≤
.
n
n
The term “slow-rate” comes from the fact
√ that the representative above provides rates typically not faster than 1/ n (as compared to 1/n above). Indeed, if again λ = 2kX ⊤ εk∞ and if the noise
√ is again i.i.d.
√ Gaussian, standard
maximal inequalities yield the bound hσ log pkβ ∗ k1 / n for a constant h > 0.
However, there are three main reason for why a superficial comparison of rates
is not sufficient and the term “slow-rate” is misleading: First, the assumptions
on X needed for “fast-rate bounds” (such as the compatibility condition invoked above) can typically not be verified in practice, because they involve
quantities (such as the support of β ∗ ) that are unknown; “slow-rate bounds,”
in contrast, hold for any X. Second, fast “slow-rate bounds” (with rate close
to 1/n) can be derived in some settings [19], and the constants in “fast-rate”
√
bounds can be unfavorably large, masking the 1/n rate. Third, the rate 1/ n
cannot be improved altogether unless further assumptions are imposed [19,
Proposition 4 on Page 561]. Refined versions of both types of bound and more
exhaustive comparisons can be found in [19,28,30,36,50].
Similarly for the square-root LASSO, if γ = hkX ⊤ ζk∞ for a suitable h > 0,
then the prediction loss satisfies the following bound:
kX β̄(γ) − Xβ ∗ k22
h′ σγkβ ∗ k1
≤
n
n
for a constant h′ > 0. We refer to [36] for details and further references.
A major limitation of both types of result is the condition on the tuning parameter λ. As indicated in Lemmas 1 and 2, the tuning parameter
(i) needs to be large enough to satisfy the given assumptions but (ii) small
enough to provide sharp bounds. Since kX ⊤ εk∞ (and equivalently kX ⊤ ζk∞ in
the square-root LASSO case) are unknown in practice, one tries to establish
a trade-off by using a data-dependent tuning parameter λ̃ ≡ λ̃(Y, X) when
it comes to applications. Plugging this data-dependent tuning parameter in
Lemmas 1 and 2 yields the following.
Corollary 1 If λ̃ ≥ 2kX ⊤ εk∞ and the compatibility condition (5) is met for
a constant ν > 0, the prediction loss of the LASSO satisfies
16sλ̃2
kX β̃(λ̃) − Xβ ∗ k22
≤ 2 2.
n
ν n
Corollary 2 If λ̃ ≥ kX ⊤ εk∞ , the prediction loss of the LASSO satisfies
kX β̃(λ̃) − Xβ ∗ k22
4λ̃kβ ∗ k1
≤
.
n
n

Prediction Error Bounds for Linear Regression With the TREX

7

These bounds now hinge on guarantees for λ̃(Y, X). In particular, for such
bounds to hold, one would need to guarantee that λ̃(Y, X) ≥ 2kX ⊤ εk∞ ; however, standard data-based calibration schemes such as cross-validation, BIC,
and AIC, lack such results. To our knowledge, there are neither results showing
that λ̃ is sufficiently large to satisfy the given assumptions, nor that λ̃ is sufficiently small to provide reasonable bounds. In this sense, the above guarantees
are of academic value only.
3.2 Bounds for the TREX
In this section, we derive two types of prediction bounds for the TREX. The
first bound (Theorem 1) expresses the TREX’s prediction error in terms of
the LASSO’s prediction error, whereas the second bound (Theorem 2) stands
on its own.
Functions of the form kX ⊤ (Y − X·)k∞ are well-known in LASSO settings,
since the LASSO KKT conditions specify that λ = kX ⊤ (Y − X β̃(λ)k∞ as
long as β̃(λ) 6= 0 (and more generally specify that kX ⊤ (Y − X β̃(λ))k∞ ≤ λ).
We state the TREX bounds in terms of the corresponding quantity, which we
denote as
û ≡ û(Y, X) := kX ⊤ (Y − X β̂)k∞ .
(6)
First, we establish a direct connection between the prediction performance
of the TREX and the LASSO under the following assumption.
Assumption 1 The regression vector β ∗ is sufficiently small such that
kβ ∗ k1 ≤

kεk22
.
16kX ⊤εk∞

In the case of i.i.d. Gaussian noise, this assumption
p can be loosely interpreted
as saying that kβ ∗ k1 should be bounded by σ n/ log p, which holds in the
standard high-dimensional limit in which (log p)/n → 0. This assumption
might look unusual, but recall that the classical “slow-rate bounds” for the
LASSO have a similar assumption implicit in their formulation. In Lemma 2,
for example,p
under i.i.d. Gaussian noise and optimal tuning, the prediction
bound is hσ (logp
p)/nkβ ∗ k1 for a constant h, which is a non-trivial bound
∗
only if kβ k1 ≪ σ n/ log p.

Theorem 1 Let Assumption 1 be fulfilled and let λ̃ := max{2û, 8kX ⊤εk∞ /c},
where c ∈ (0, 2) and û is defined in (6). If û ≤ kX ⊤ Y k∞ /2, then the prediction
loss of the TREX satisfies
kX β̂ − Xβ ∗ k22
3kX β̃(λ̃) − Xβ ∗ k22
7kX ⊤εk∞ kβ̃(λ̃) − β ∗ k1
≤
+
.
n
4n
2n
The quantity û from (6) plays a similar role for the TREX as the data-driven
tuning parameter λ̃ plays for the LASSO. The main feature of Theorem 1,
however, is that it allows for any value û ≤ kX ⊤ Y k∞ . Indeed, the tuning

8

Bien, Gaynanova, Lederer, Müller

parameter λ̃ is lower bounded by 8kX ⊤ εk∞ /c, irrespective of the value of û,
which ensures that the condition λ & kX ⊤ εk∞ on the tuning parameter λ in
standard results for the LASSO, such as Corollaries 1 and 2, is always fulfilled.
Therefore, Theorem 1 in conjunction with the known results for LASSO, provides a concrete bound for the prediction loss kX β̂ − Xβ ∗ k22 /n of the TREX.
Specifically, if the LASSO satisfies the compatibility condition and û is of the
same order as kX ⊤ εk∞ , the above bound implies the “fast-rate” sσ 2 (log p)/n
up to constants and an entropy factor as before. The following corollary highlights these aspects once more.
Corollary 3 Let Assumption 1 be fulfilled, and let λ̃ := max{2û, 8kX ⊤εk∞ /c},
where û is defined in (6). If û ≤ kX ⊤ Y k∞ /2, then the prediction loss of the
TREX satisfies
12sλ̃2
kX β̂ − Xβ ∗ k22
≤ 2 2,
n
ν n
where s is the sparsity level of β ∗ , and ν is the compatibility constant from (5).
This corollary clearly resembles Corollary 1 for the LASSO, yet a significant
distinction is that for the LASSO result to be applicable, one would also need
a result showing that the data-driven choice of the tuning parameter exceeds
2kX ⊤εk∞ . By contrast, Corollary 3 holds for the TREX estimator exactly as
it would be used in practice. Whether Corollary 3 represents a tight bound for
the prediction error of the TREX is another matter: when 2û ≤ 8kX ⊤εk∞ /c,
the bound behaves like the bound in Corollary 1 with the best choice of λ̃;
when instead 2û > 8kX ⊤εk∞ /c, the bound is not necessarily tight. We discuss
this in more detail further below.
Next, we bound the prediction loss of the TREX directly. Specifically, we
are interested in deriving a so-called “slow-rate bound,” which allows for potentially large correlations in X (see discussion in Section 3.1). To derive this
bound, we use a different assumption.
Assumption 2 The regression vector β ∗ is sufficiently large such that

2 ⊤
kX ⊤ Xβ ∗ k∞ ≥ 1 +
kX εk∞ .
c
Note that this assumption implies kX ⊤ Y k∞ ≥ 2kX ⊤εk∞ /c via the triangle inequality. In the orthogonal case, in which X ⊤ X = n In , it holds that
kX ⊤ Xβ ∗ k∞ = nkβ ∗ k∞ ; more generally, under the ℓ∞ -restricted eigenvalue
condition [17, Equation (7) on Page 6], it holds that kX ⊤ Xβ ∗ k∞ ≥ gnkβ ∗ k∞
for some constant g. Then, in the case of i.i.d. Gaussian noise, a sufficient
conp
dition for Assumption 2 is that kβ ∗ k∞ of larger order in n than σ (log p)/n.
The assumption can, therefore, be interpreted as a condition on the minimal
signal strength, and would naturally hold in the standard high-dimensional
limit of (log p)/n → 0.

Prediction Error Bounds for Linear Regression With the TREX

9

Theorem 2 Let Assumption 2 be fulfilled, and let û be as in (6). If û ≤
kX ⊤ Y k∞ , then the prediction loss of the TREX satisfies


2kX ⊤ εk∞ + max û, 2kX ⊤εk∞ /c kβ ∗ k1
kX β̂ − Xβ ∗ k22
≤
.
n
n
This result is closely related to Corollary 2. In particular, since Corollary 2
requires λ̃ ≥ kX ⊤ εk∞ , the right-hand sides in the bounds of Theorem 2 and
of Corollary 2 resemble each other closely1 . The
√ rates in both results are,
as discussed, “slow-rates” of order at least 1/ n. The major difference between the two results are the assumptions on λ̃ and û: While the assumption
λ̃ ≥ kX ⊤ εk∞ depends on quantities that are unknown in practice, the assumption û ≤ kX ⊤ Y k∞ depends on the data only. This means that in practice, one
can check if û satisfies the requirements. Alternatively, one can add the convex constraint kX ⊤ (Y − Xβ)k∞ ≤ kX ⊤ Y k∞ directly into the optimization
procedure of the TREX, which automatically ensures—without changing the
proofs—that û ≤ kX ⊤Y k∞ . Having verifiable assumptions is an advantage
of Theorem 2 over Corollary 2; however, a price paid is that the bound in
Theorem 2 may be large if û ≫ kX ⊤εk∞ . Note finally that as both results are
oracle inequalities, the bounds themselves are not known in practice.
We now discuss the conditions imposed by Assumptions 1 and 2. While
each of the derived prediction bounds relies on only one of these assumptions,
it is of interest to see whether these assumptions can hold at the same time.
Note that for standard noise distributions, it holds that kεk22√is of order n,
and classical entropy bounds ensure that kX ⊤ εk∞ is of order σ n log p (recall
the normalization of X). Moreover, for near-orthogonal design (in the sense of
the ℓ∞ -restricted eigenvalue, for example), it holds that kX ⊤Xβ ∗ k∞ is lower
bounded by nkβ ∗ k∞ upp
to constants. As such, at a high level, p
Assumptions 1
and 2 together imply σ (log p)/n/f ≤ kβ ∗ k∞ ≤ kβ ∗ k1 ≤ f σ n/ log p for a
constant f , which are mild conditions on the signal β ∗ when n is sufficiently
large. For small n, however, the constants in Assumptions 1 and 2 become
relevant and can be too large. Conditions with smaller constants can be found
in the Appendix, and we expect that the constants can be further decreased.
However, the key point is that the restrictions imposed on the model are very
mild if n is reasonably large relative to log p. Still, an open conceptual question
is whether it is possible to develop theories (for any estimator!) that do without
assumptions on the signal strength altogether.
A more stringent limitation of the above inequalities is the dependence
on û. Since tight upper bounds for û are currently lacking, it is not clear if
the inequalities provide an optimal control of the prediction errors. However,
we argue that our results still improve the existing theory for sparse linear
regression substantially. We first note that known LASSO prediction bounds
do not involve estimated quantities only because these bounds do not address
tuning parameter calibration altogether. When the LASSO is combined with
1 The right-hand side in Corollary 2 has a minimal magnitude of 4kX ⊤ εk kβ ∗ k /n, while
∞
1
the right-hand side in Theorem 2 has a minimal magnitude of (2 + 2/c)kX ⊤ εk∞ kβ ∗ k1 /n.

10

Bien, Gaynanova, Lederer, Müller

a calibration scheme, the bounds do in fact involve estimated tuning parameters (see Corollaries 3 and 4) that have eluded any statistical analysis so far.
Our bounds for the TREX provide a better control because they involve the
maximum of û and the optimal bound, thus providing a lower bound on the
relevant quantities.
Similar comments apply to the comparison of our TREX theory with the
theories of the square-root LASSO/scaled LASSO and LASSO-LinSelect: since
the three latter methods all invoke (functions of) the normalized noise ζ in
their tuning schemes, they require additional calibration unless (the distribution of) ζ is known. However, when sharp tail bounds for (the appropriate functions of) ζ are known, these methods are currently equipped with
more comprehensive theories than what is presented here (and in the LASSOliterature), and unlike the results here, they then also allow for bounds in
probability [29, Proposition 4.2 and 4.3].
As for calibration schemes, we mention cross-validation as the most popular
one. Standard k-fold cross-validation can provide unbiased estimation of a
prediction risk [1, Page 57]. However, this hinges on i.i.d. data and the risk is in
out-of-sample prediction (as compared to the in-sample prediction considered
here) for a sample size smaller than n (since cross-validation involves data
splitting). A comprehensive overview of cross-validation theory can be found
in [1], further ideas in [2] and others. Nevertheless, there are currently no
non-asymptotic guarantees for LASSO-type estimators calibrated by k-fold
cross-validation.
In summary, the presented prediction bounds for the TREX avoid the problem of “too small” tuning parameters that is present for LASSO-type bounds
(see Section 3.1). Thus, the TREX prediction bounds provide an advancement over the theory for the LASSO (and similarly, the square-root LASSO,
the scaled LASSO, MCP, and other penalized methods) combined with crossvalidation, information criteria, or other standard means for tuning parameter
selection. However, the inequalities do not solve the problem of “too large”
tuning parameters, yet. Being able to bound û in terms of kX ⊤ εk∞ , for example, would allow us to extend our results in this direction. Thus, our results
provide a not yet complete but certainly improved theoretical framework for
sparse linear regression.

4 Generalizations to General Norm Penalties
The ℓ1 -norm in the penalty of the LASSO and the TREX reflects the assumption that the regression vector is sparse. However, many applications
involve more complex structures for β ∗ . In this section, we discuss generalizations of the TREX objective function to general norm penalities. For this, we
consider general norms Ω on Rp with corresponding dual norms defined by
Ω ∗ (η) := sup{η ⊤ β : Ω(β) ≤ 1}. A generalized version of the TREX can then

Prediction Error Bounds for Linear Regression With the TREX

11

be formulated as
minp

β∈R




kY − Xβk22
+
Ω(β)
,
cΩ ∗ (X ⊤ (Y − Xβ))

(7)

assuming that a minimum
P exists. An example is the group TREX that uses the
norm penalty Ω(β) := G∈G wG kβG k2 for a given partition G of {1, . . . , p}
and given weights w1 , . . . , w|G| > 0. Explicitly, we define the group TREX as
(
)
X
kY − Xβk22
min
+
wG kβG k2 .
⊤ (Y − Xβ)k /w }
β∈Rp
c maxG∈G {kXG
2
G
G∈G
The group TREX is the TREX analog to the well-known group LASSO [48]
and group square-root LASSO [11]. In the special case in which all groups are
of size one, that is, G = {1, . . . , p}, the group TREX reduces to a weighted
version of the standard TREX problem:




2
X
kY − Xβk2
wj |βj | .
minp
+
⊤

β∈R  c maxj∈{1,...,p} {|Xj (Y − Xβ)|/wj }
j∈{1,...,p}

The weighting can be further extended to allow for completely unpenalized coordinates. Unpenalized predictors arise commonly in practice when one wants
to allow for an intercept or has prior knowledge that certain predictors should
be included in the fitted model. To incorporate unpenalized predictors in the
TREX, we denote the set of indices corresponding to the unpenalized predictors by U ⊆ {1, . . . , p} and the complementary set by P := {1, . . . , p} \ U.
Let us, with some abuse of notation, denote the generalized TREX by β̂. The
unpenalized predictors are determined by forcing the estimator β̂ to satisfy
XU⊤ (Y − X β̂) = 0.

The subscript indicates that only the columns of a matrix (or the entries of
a vector) in the corresponding set are considered. In the special case of an
intercept, where U = {1} and x1 = (1, . . . , 1)⊤ , this reads
(1, . . . , 1)⊤ (Y − X β̂) = 0.
This is the identical constraint for the standard LASSO with intercept. More
generally, (4) implies
β̂U = (XU⊤ XU )+ XU⊤ (Y − XP β̂P ),
where (XU⊤ XU )+ is a generalized inverse of XU⊤ XU . Incorporating this constraint in the TREX criterion yields the estimator


kMU (Y − XP βP )k22
β̂P := min
+ Ω(βP )
cΩ ∗ (XP⊤ MU (Y − XP βP ))
βP ∈R|P|
(8)
β̂U := (XU⊤ XU )+ XU⊤ (Y − XP β̂P ),

12

Bien, Gaynanova, Lederer, Müller

where MU := (I −XU (XU⊤ XU )+ XU⊤ ) is the projection on the orthogonal complement of the span of the columns with indices in U. Note that the estimator (8) simplifies to the least-squares estimator if U = {1, . . . , p} and simplifies
to (7) for U = ∅. More generally, β̂P can be considered as a (generalized)
TREX on the output not explained by a least-squares of Y on XU . Indeed, if
the columns with indices in U are orthogonal to the columns with indices in
P, the estimator (8) simplifies to


kMU Y − XP βP k22
+
Ω(β
)
β̂P := min
P
cΩ ∗ (XP⊤ (MU Y − XP βP ))
βP ∈R|P|
β̂U := (XU⊤ XU )+ XU⊤ Y.

In this case, the generalized TREX combines the TREX on (MU Y, XP ) and
least-squares estimation on (Y, XU ). Theorem 2 can be extended in this generalized setting.
Assumption 3 The regression vector β ∗ is sufficiently large such that


2
Ω ∗ (X ⊤ Xβ ∗ ) ≥ 1 +
Ω ∗ (X ⊤ ε).
c
Theorem 3 Let Assumption 3 be fulfilled and define û := Ω ∗ (X ⊤ (Y − X β̂)).
If û ≤ Ω ∗ (X ⊤ Y ), then the prediction loss of TREX satisfies


2Ω ∗ (X ⊤ ε) + max û, 2c Ω ∗ (X ⊤ ε) Ω(β ∗ )
kX β̂ − Xβ ∗ k22
≤
.
n
n
The bound depends on the size of the vectors X ⊤ ε and X ⊤ (Y − X β̂) as
measured by the dual norm Ω ∗ . In the special case that Ω(β) = kβk1 , Ω ∗
is simply the ℓ∞ -norm, and this theorem reduces to Theorem 2. We refer to
Appendix B for the proof details.
5 Discussion
In this paper, we have provided the first prediction error bounds for the TREX
and for a newly proposed generalization of the TREX. Our theoretical guarantees resemble known bounds for the LASSO. However, there is an important
practical difference. The LASSO results hold only if an oracle could guarantee that a sufficiently large tuning parameter has been chosen (in practice,
one uses a data-dependent calibration scheme for which such guarantees of a
sufficiently large tuning parameter are not available). By contrast, our TREX
results do not have such a requirement and therefore pertain to the precise
version of the estimator that is used in practice.
We envision future research in different directions. First, it would be desirable to derive sharp upper bounds for the quantity û. This would lead
to a complete set of guarantees for high-dimensional prediction with finitely
many samples. For this, one might also explore potential connections with the

Prediction Error Bounds for Linear Regression With the TREX

13

Dantzig selector [14], in which the quantity kX ⊤ (Y − Xβ)k∞ is controlled explicitly. Moreover, it would be of interest to study the choice of the constant c
further. Numerical results in [35,8] indicate that the fixed choice c = 1/2
works in a variety of settings. While the presented theory covers all values of
c ∈ (0, 2), it is, however, conceivable that a data-dependent choice of c may
further improve the accuracy of the TREX. Finally, it would be interesting to
extend our theoretical results to tasks beyond prediction, such as estimation
and support recovery.
Acknowledgements We sincerely thank the editor and the reviewers for their insightful
comments.

References
1. Arlot, S., Celisse, A.: A survey of cross-validation procedures for model selection. Statistics Surveys 4, 40–79 (2010)
2. Arlot, S., Celisse, A.: Segmentation of the mean of heteroscedastic data via crossvalidation. Statistics and Computing 21(4), 613–632 (2011)
3. Bach, F.: Bolasso: Model Consistent Lasso Estimation Through the Bootstrap. In:
Proceedings of the 25th International Conference on Machine Learning, pp. 33–40 (2008)
4. Baraud, Y., Giraud, C., Huet, S.: Gaussian model selection with an unknown variance.
Ann. Statist. 37(2), 630–672 (2009)
5. Barber, R., Candès, E.: Controlling the False Discovery Rate via Knockoffs. Ann.
Statist. 43(5), 2055–2085 (2015)
6. Belloni, A., Chernozhukov, V., Wang, L.: Square-root lasso: pivotal recovery of sparse
signals via conic programming. Biometrika 98(4), 791–806 (2011)
7. Bickel, P., Ritov, Y., Tsybakov, A.: Simultaneous analysis of lasso and Dantzig selector.
Ann. Statist. 37(4), 1705–1732 (2009)
8. Bien, J., Gaynanova, I., Lederer, J., Müller, C.: Non-convex global minimization and
false discovery rate control for the TREX. to appear in J. Comput. Graph. Statist
(2017)
9. Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic
Theory of Independence. Oxford University Press (2013)
10. Bühlmann, P., van de Geer, S.: Statistics for high-dimensional data: Methods, theory
and applications. Springer (2011)
11. Bunea, F., Lederer, J., She, Y.: The Group Square-Root Lasso: Theoretical Properties
and Fast Algorithms. IEEE Trans. Inform. Theory 60(2), 1313–1325 (2014)
12. Bunea, F., Tsybakov, A., Wegkamp, M.: Aggregation and sparsity via ℓ1 -penalized least
squares. In: Proceedings of 19th Annual Conference on Learning Theory, pp. 379–391
(2006)
13. Candès, E., Plan, Y.: Near-ideal model selection by ℓ1 minimization. Ann. Statist. 37(5)
(2009)
14. Candes, E., Tao, T.: The Dantzig selector: Statistical estimation when p is much larger
than n. Ann. Statist. 35(6), 2313–2351 (2007)
15. Chatterjee, S., Jafarov, J.: Prediction error of cross-validated lasso. arXiv:1502.06291
(2015)
16. Chételat, D., Lederer, J., Salmon, J.: Optimal two-step prediction in regression. Electron. J. Stat. 11(1), 2519–2546 (2017)
17. Chichignoud, M., Lederer, J., Wainwright, M.: A practical scheme and fast algorithm
to tune the lasso with optimality guarantees. J. Mach. Learn. Res. 17, 1–20 (2016)
18. Combettes, P., Müller, C.: Perspective functions: Proximal calculus and applications in
high-dimensional statistics. J. Math. Anal. Appl. 457(2) (2016)

14

Bien, Gaynanova, Lederer, Müller

19. Dalalyan, A., Hebiri, M., Lederer, J.: On the Prediction Performance of the Lasso.
Bernoulli 23(1), 552–581 (2017)
20. Dalalyan, A., Tsybakov, A.: Aggregation by exponential weighting and sharp oracle
inequalities. In: Proceedings of 19th Annual Conference on Learning Theory, pp. 97–
111 (2007)
21. Dalalyan, A., Tsybakov, A.: Mirror averaging with sparsity priors. Bernoulli 18(3),
914–944 (2012)
22. Dalalyan, A., Tsybakov, A.: Sparse regression learning by aggregation and langevin
monte-carlo. J. Comput. System Sci. 78(5), 1423–1443 (2012)
23. Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle
properties. J. Amer. Statist. Assoc. 96(456), 1348–1360 (2001)
24. van de Geer, S.: Empirical Processes in M-estimation, vol. 6. Cambridge University
Press (2000)
25. van de Geer, S.: The deterministic Lasso. In JSM proceedings (2007)
26. van de Geer, S., Bühlmann, P.: On the conditions used to prove oracle results for the
Lasso. Electron. J. Stat. 3, 1360–1392 (2009)
27. van de Geer, S., Lederer, J.: The Bernstein-Orlicz norm and deviation inequalities.
Probab. Theory Related Fields 157(1–2), 225–250 (2013)
28. van de Geer, S., Lederer, J.: The Lasso, correlated design, and improved oracle inequalities. IMS Collections 9, 303–316 (2013)
29. Giraud, C., Huet, S., Verzelen, N.: High-dimensional regression with unknown variance.
Statist. Sci. 27(4), 500–518 (2012)
30. Hebiri, M., Lederer, J.: How correlations influence Lasso prediction. IEEE Trans. Inform.
Theory 59(3), 1846–1854 (2013)
31. Huang, C., Cheang, G., Barron, A.: Risk of Penalized Least Squares, Greedy Selection
and L1 penalization for flexible function libraries (2008). Manuscript
32. Koltchinskii, V., Lounici, K., Tsybakov, A.: Nuclear-norm penalization and optimal
rates for noisy low-rank matrix completion. Ann. Statist. 39(5), 2302–2329 (2011)
33. Lederer, J., van de Geer, S.: New concentration inequalities for empirical processes.
Bernoulli 20(4) (2014)
34. Lederer, J., Müller, C.: Topology adaptive graph estimation in high dimensions.
arXiv:1410.7279 (2014)
35. Lederer, J., Müller, C.: Don’t fall for tuning parameters: Tuning-free variable selection in
high dimensions with the TREX. In: Proceedings of the Twenty-Ninth AAAI Conference
on Artificial Intelligence (2015)
36. Lederer, J., Yu, L., Gaynanova, I.: Oracle inequalities for high-dimensional prediction.
arXiv:1608.00624 (2016)
37. Lim, N., Lederer, J.: Efficient feature selection with large and high-dimensional data.
arXiv:1609.07195 (2016)
38. Massart, P., Meynet, C.: The Lasso as an ℓ1 -ball model selection procedure. Electron.
J. Stat. 5, 669–687 (2011)
39. Meinshausen, N., Bühlmann, P.: Stability selection. J. R. Stat. Soc. Ser. B 72(4),
417–473 (2010)
40. Raskutti, G., Wainwright, M., Yu, B.: Restricted eigenvalue properties for correlated
Gaussian designs. J. Mach. Learn. Res. 11, 2241–2259 (2010)
41. Rigollet, P., Tsybakov, A.: Exponential Screening and optimal rates of sparse estimation.
Ann. Statist. 39(2), 731–771 (2011)
42. Sabourin, J., Valdar, W., Nobel, A.: A permutation approach for selecting the penalty
parameter in penalized model selection. Biometrics 71(4), 1185–1194 (2015)
43. Shah, R., Samworth, R.: Variable selection with error control: another look at stability
selection. J. Roy. Statist. Soc. Ser. B 75(1), 55–80 (2013)
44. Sun, T., Zhang, C.H.: Scaled sparse linear regression. Biometrika 99(4), 879–898 (2012)
45. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc.
Ser. B 58(1), 267–288 (1996)
46. van der Vaart, A., Wellner, J.: Weak Convergence and Empirical Processes. Springer
(1996)
47. Wellner, J.: The Bennett-Orlicz norm. Sankhya A 79(2), 355–383 (2017)
48. Yuan, M., Lin, Y.: Model selection and estimation in regression with grouped variables.
J. Roy. Statist. Soc. Ser. B 68(1), 49–67 (2006)

Prediction Error Bounds for Linear Regression With the TREX

15

49. Zhang, C.: Nearly unbiased variable selection under minimax concave penalty. Ann.
Statist. 38(2), 894–942 (2010)
50. Zhuang, R., Lederer, J.: Maximum regularized likelihood estimators: A general prediction theory and applications. arXiv:1710.02950 (2017)

A Proof of a Generalization of Theorem 1
We first consider a generalization of Assumption 1.
Assumption 4 The signal β ∗ is sufficiently small such that for some κ1 > 1 and κ2 > 2
with 1/κ1 + 2/κ2 < 1,
kβ ∗ k1 ≤

1
4



1−

1
2
−
κ1
κ2



kεk22
.
kX ⊤ εk∞

As a first step toward the proof of Theorem 1, we show that any TREX solution has larger
ℓ1 -norm than any lasso solution with tuning parameter λ = û.
Lemma 3 Any TREX solution (4) satisfies
kβ̂k1 ≥ kβ̃(û)k1 ,
where β̃ û is any lasso solution as in (2) with tuning parameter λ = û.
Proof (of Lemma 3) If β̃(û) = 0, the statement holds trivially. Now for β̃(û) 6= 0, the KKT
conditions for LASSO imply that
kX ⊤ (Y − X β̃(û))k∞ = û.
Together with the definition of β̂, this yields
kY − X β̂k22 + cûkβ̂k1 ≤ kY − X β̃(û)k22 + cûkβ̃(û)k1 .
On the other hand, the definition of the LASSO implies
kY − X β̃(û)k22 + 2ûkβ̃(û)k1 ≤ kY − X β̂k22 + 2ûkβ̂k1 .
Combining these two displays gives us
(c − 2)ûkβ̂k1 ≤ (c − 2)ûkβ̃(û)k1 .
The claim follows now from c < 2.
We are now ready to prove a generalization of Theorem 1.
Theorem 4 Let Assumption 4 be fulfilled, and let λ̃ := max{κ1 û,
any û ≤ kX ⊤ Y k∞ /κ1 , the prediction loss of the TREX satisfies
kX β̂ − Xβ ∗ k22 ≤



1
2
+
κ1
κ2



kX β̃(λ̃) − Xβ ∗ k22 +



2+

4
2
+
κ1
κ2



Theorem 1 follows from Theorem 4 by setting κ1 = 2, and κ2 = 8.

κ2
kX ⊤ εk∞ }.
c

Then, for

kX ⊤ εk∞ kβ̃(λ̃) − β ∗ k1 .

16

Bien, Gaynanova, Lederer, Müller

Proof (of Theorem 4) Assume first β̃(λ̃) = 0. Then, since û ≤ kX ⊤ Y k∞ /κ1 , the definition
of the TREX implies
kY − X β̂k22 + cûkβ̂k1 ≤ kY k22 /κ1 = kY − X β̃(λ̃)k22 /κ1 .
Assume now β̃(λ̃) 6= 0. In view of the KKT conditions for LASSO, β̃(λ̃) fulfills
κ2
kX ⊤ εk∞ } ≥ κ1 û.
kX ⊤ (Y − X β̃(λ̃))k∞ = λ̃ = max{κ1 û,
c
The definition of the TREX therefore yields
kY − X β̂k22 + cûkβ̂k1 ≤

kY − X β̃(λ̃)k22
+ cûkβ̃(λ̃)k1 .
κ1

We now observe that since κ1 > 1 by assumption, we have λ̃ ≥ û, and one can verify easily
that this implies kβ̃(û)k1 ≥ kβ̃(λ̃)k1 . At the same time, Lemma 3 ensures kβ̂k1 ≥ kβ̃ û k1 .
Thus, cûkβ̂k1 ≥ cûkβ̃(λ̃)k1 and, therefore, we find again
kY − X β̂k22 ≤

kY − X β̃(λ̃)k22
.
κ1

Invoking the model, this results in
κ1 kX β̂ − Xβ ∗ k22
≤ (1 − κ1 ) kεk22 + 2ε⊤ (Xβ ∗ − X β̃(λ̃)) + 2ε⊤ (X β̂ − Xβ ∗ ) + kX β̃(λ̃) − Xβ ∗ k22 .
We can now use Hölder’s inequality and the triangle inequality to deduce
kX β̂ − Xβ ∗ k22


2kX ⊤ εk∞ kβ ∗ − β̃(λ̃)k1
1 − κ1
kεk22 +
≤
κ1
κ1
+ 2kX ⊤ εk∞ kβ̂k1 + 2kX ⊤ εk∞ kβ ∗ k1 +
≤



1 − κ1
κ1



kX β̃(λ̃) − Xβ ∗ k22
κ1

2kX ⊤ εk∞ kβ ∗ − β̃(λ̃)k1
κ1
!
kY − X β̂k22
kX β̃(λ̃) − Xβ ∗ k22
.
+ kβ̂k1 + 2kX ⊤ εk∞ kβ ∗ k1 +
cû
κ1

kεk22 +

+ 2kX ⊤ εk∞

Next, we observe that by the definition of our estimator β̂ and of λ̃,
kY − X β̂k22
kY − X β̃(λ̃)k22
kY − X β̃(λ̃)k22
+ kβ̃(λ̃)k1 .
+ kβ̂k1 ≤
+ kβ̃(λ̃)k1 ≤
cû
κ2 kX ⊤ εk∞
cλ̃
Combining these two displays and using the model assumption then gives
kX β̂ − Xβ ∗ k22


1 − κ1
2kX ⊤ εk∞ kβ ∗ − β̃(λ̃)k1
≤
kεk22 +
κ1
κ1
!
2
kX β̃(λ̃) − Xβ ∗ k22
kY − X β̃(λ̃)k2
+
k
β̃(
λ̃)k
+ 2kX ⊤ εk∞ kβ ∗ k1 +
+ 2kX ⊤ εk∞
1
κ2 kX ⊤ εk∞
κ1


1 − κ1
2
2kX ⊤ εk∞ kβ ∗ − β̃(λ̃)k1
=
+
kεk22 +
κ1
κ2
κ1
!
⊤
∗
2ε X(β − β̃(λ̃))
+ 2kX ⊤ εk∞
+
k
β̃(
λ̃)k
+ 2kX ⊤ εk∞ kβ ∗ k1
1
κ2 kX ⊤ εk∞


2
1
+
kX β̃(λ̃) − Xβ ∗ k22 .
+
κ1
κ2

Prediction Error Bounds for Linear Regression With the TREX

17

We can now use Hölder’s inequality and rearrange the terms to get
kX β̂ − Xβ ∗ k22




2
2
1
1 − κ1
+
+
kεk22 +
2kX ⊤ εk∞ kβ ∗ − β̃(λ̃)k1
≤
κ1
κ2
κ1
κ2


1
2
+ 2kX ⊤ εk∞ kβ̃(λ̃)k1 + 2kX ⊤ εk∞ kβ ∗ k1 +
+
kX β̃(λ̃) − Xβ ∗ k22 .
κ1
κ2
The last step is to use Assumption 4, which ensures
kβ ∗ k1 ≤



1
1
1
−
−
4
4κ1
2κ2



kεk22
kX ⊤ εk∞

and, therefore,
4kX ⊤ εk∞ kβ ∗ k1 ≤
The above display therefore yields



κ1 − 1
2
−
κ1
κ2



kεk22 .




1
2
+
2kX ⊤ εk∞ kβ ∗ − β̃(λ̃)k1
κ1
κ2


2
1
+
kX β̃(λ̃) − Xβ ∗ k22 .
+ 2kX ⊤ εk∞ kβ̃(λ̃)k1 + 2kX ⊤ εk∞ kβ ∗ k1 +
κ1
κ2

kX β̂ − Xβ ∗ k22 ≤ −4kX ⊤ εk∞ kβ ∗ k1 +

Using the triangle inequality, we finally obtain




2
4
2
1
+
+
kX ⊤ εk∞ kβ̃(λ̃) − β ∗ k1 +
kX β̃(λ̃) − Xβ ∗ k22
kX β̂ − Xβ ∗ k22 ≤ 2 +
κ1
κ2
κ1
κ2
as desired.
Corollary 4 Let Assumption 4 be fulfilled, and let λ̃ := max{κ1 û,
more, let κ1 , κ2 > 0 be such that

κ2
kX ⊤ εk∞ }.
c

Further-

1
κ1
1
+
≤ .
κ2
κ2 + 2κ1
c
Then for any û ≤ kX ⊤ Y k∞ /κ1 , the prediction loss of TREX satisfies
kX β̂ − Xβ ∗ k22 ≤



2
1
+
κ1
κ2



16sλ̃2
,
ν2n

where ν is the compatibility constant defined in (5).
Corollary 3 follows from Corollary 4 by setting κ1 = 2, and κ2 = 8, which satisfy the
requirement for any c ∈ (0, 2).
Proof (of Corollary 4) Using Theorem 4 and the definition of λ̃, the TREX prediction loss
satisfies




2
4
1
2
+
+
kX β̂ − Xβ ∗ k22 ≤
kX β̃(λ̃) − Xβ ∗ k22 + 2 +
kX ⊤ εk∞ kβ̃(λ̃) − β ∗ k1
κ1
κ2
κ1
κ2





2
c
2κ1 κ2
1
+
λ̃kβ̃(λ̃) − β ∗ k1 .
kX β̃(λ̃) − Xβ ∗ k22 + 2 +
≤
κ1
κ2
κ2 + 2κ1 κ2
On the other hand, the LASSO estimator β̃(λ̃) satisfies [10, Theorem 6.1]
kX β̃(λ̃) − Xβ ∗ k22 + 2λ̃kβ̃(λ̃) − β ∗ k1 ≤

16sλ̃2
.
ν2n

18

Bien, Gaynanova, Lederer, Müller

Since by assumption


2+

2κ1 κ2
κ2 + 2κ1



c
≤ 2,
κ2

the LASSO bound implies
kX β̂ − Xβ ∗ k22 ≤



1
2
+
κ1
κ2



16sλ̃2
ν2n

as desired.

B Proof of a Generalization of Theorem 2
We consider a generalization of the TREX according to
β̂ ∈ arg min




kY − Xβk22
+
Ω(β)
,
cΩ ∗ (X ⊤ (Y − Xβ))

where Ω is a norm on Rp , Ω ∗ (η) := sup{η⊤ β : Ω(β) ≤ 1} is the dual of Ω, 0 < c < 2, and
the minimum is taken over all β ∈ Rp . We also set û := Ω ∗ (X ⊤ (Y − X β̂)) with some abuse
of notation. The corresponding generalization of Assumption 2 then reads as follows.
Assumption 5 The regression vector β ∗ is sufficiently large such that
Ω ∗ (X ⊤ Xβ ∗ ) ≥



1+

2
c



Ω ∗ (X ⊤ ε).

We now prove a generalization of Theorem 2.
Theorem 5 Let Assumption 5 be fulfilled. If û ≤ Ω ∗ (X ⊤ Y ), then the prediction loss of
TREX satisfies


2Ω ∗ (X ⊤ ε) + max û, 2c Ω ∗ (X ⊤ ε) Ω(β ∗ )
kX β̂ − Xβ ∗ k22
≤
.
n
n
Theorem 2 follows from Theorem 5 by setting Ω(·) := k · k1 .
Proof (of Theorem 5) The definition of the estimator implies
kY k22
kY − X β̂k22
+ Ω(β̂) ≤
,
c · û
c · Ω ∗ (X ⊤ Y )
which yields together with the model assumptions
kX β̂ − Xβ ∗ k22 + kεk22 + 2ε⊤ (Xβ ∗ − X β̂) + cûΩ(β̂)


û
≤ ∗ ⊤
kεk22 + kXβ ∗ k22 + 2ε⊤ Xβ ∗ .
Ω (X Y )
Rearranging the terms and Hölder’s inequality in the form of 2ε⊤ X β̂ ≤ 2Ω ∗ (X ⊤ ε)Ω(β̂)
and kXβ ∗ k22 = β ∗⊤ X ⊤ Xβ ∗ ≤ Ω ∗ (X ⊤ Xβ ∗ )Ω(β ∗ ) then gives
kX β̂ − Xβ ∗ k22 ≤



û
Ω ∗ (X ⊤ Y

)


− 1 kεk22 + (2Ω ∗ (X ⊤ ε) − cû)Ω(β̂)

ûΩ ∗ (X ⊤ Xβ ∗ )Ω(β ∗ )
+
+2
Ω ∗ (X ⊤ Y )




û
−
1
2ε⊤ Xβ ∗ .
Ω ∗ (X ⊤ Y )

(9)

Prediction Error Bounds for Linear Regression With the TREX

19

Case 1: We first consider the case 2Ω ∗ (X ⊤ ε) ≤ cû.
For this, we first note that û ≤ Ω ∗ (X ⊤ Y ) by assumption. Using this and 2Ω ∗ (X ⊤ ε) ≤ cû
allows us to remove the first two terms on the right hand side of Inequality (9) so that
ûΩ ∗ (X ⊤ Xβ ∗ )Ω(β ∗ )
+
Ω ∗ (X ⊤ Y )

kX β̂ − Xβ ∗ k22 ≤




û
−
1
2ε⊤ Xβ ∗ .
Ω ∗ (X ⊤ Y )

Since 2ε⊤ Xβ ∗ ≤ 2Ω ∗ (X ⊤ ε)Ω(β ∗ ) due to Hölder’s Inequality, and since û ≤ Ω ∗ (X ⊤ Y )
by definition of our estimator, we therefore obtain from the above display and the model
assumptions


ûΩ ∗ (X ⊤ Xβ ∗ )Ω(β ∗ )
û
2Ω ∗ (X ⊤ ε)Ω(β ∗ )
+
1
−
Ω ∗ (X ⊤ Y )
Ω ∗ (X ⊤ Y )

 ∗ ⊤
Ω (X Xβ ∗ ) − 2Ω ∗ (X ⊤ ε)
Ω(β ∗ )
= 2Ω ∗ (X ⊤ ε)Ω(β ∗ ) + û
Ω ∗ (X ⊤ Y )
 ∗ ⊤

Ω (X Xβ ∗ ) − 2Ω ∗ (X ⊤ ε)
= 2Ω ∗ (X ⊤ ε)Ω(β ∗ ) + û
Ω(β ∗ ).
Ω ∗ (X ⊤ Xβ ∗ + X ⊤ ε)

kX β̂ − Xβ ∗ k22 ≤

Next, we note that the triangle inequality gives
Ω ∗ (X ⊤ Xβ ∗ + X ⊤ ε) ≥ Ω ∗ (X ⊤ Xβ ∗ ) − Ω ∗ (X ⊤ ε).
Plugging this in the previous display finally yields
kX β̂ − Xβ ∗ k22 ≤ 2Ω ∗ (X ⊤ ε)Ω(β ∗ ) + ûΩ(β ∗ ),
which concludes the proof for Case 1.
Case 2: We now consider the case 2Ω ∗ (X ⊤ ε) ≥ cû.
Similarly as before, we start with the definition of the estimator, which yields in particular
Ω(β̂) ≤

kY k22
.
c · Ω ∗ (X ⊤ Y )

Invoking the model assumptions and Hölder’s inequality then gives
Ω(β̂) ≤

1
cΩ ∗ (X ⊤ Y



kεk22 + kXβ ∗ k22 + 2ε⊤ Xβ ∗



)


1
kεk22 + Ω ∗ (X ⊤ Xβ ∗ )Ω(β ∗ ) + 2ε⊤ Xβ ∗ .
≤
cΩ ∗ (X ⊤ Y )

We can now plug this into Inequality (9) to obtain



û
−
1
kεk22
Ω ∗ (X ⊤ Y )


1
kεk22 + Ω ∗ (X ⊤ Xβ ∗ )Ω(β ∗ ) + 2ε⊤ Xβ ∗
+ (2Ω ∗ (X ⊤ ε) − cû) ∗ ⊤
cΩ (X Y )


û
ûΩ ∗ (X ⊤ Xβ ∗ )Ω(β ∗ )
+
− 1 2ε⊤ Xβ ∗ .
+
∗
⊤
∗
⊤
Ω (X Y )
Ω (X Y )

kX β̂ − Xβ ∗ k22 ≤

We can now rearrange the terms to get
kX β̂ − Xβ ∗ k22 ≤


+




2Ω ∗ (X ⊤ ε)
2Ω ∗ (X ⊤ ε)
2
−
1
kεk
+
−
1
2ε⊤ Xβ ∗
2
cΩ ∗ (X ⊤ Y )
cΩ ∗ (X ⊤ Y )
2Ω ∗ (X ⊤ ε) ∗ ⊤
Ω (X Xβ ∗ )Ω(β ∗ ).
cΩ ∗ (X ⊤ Y )

20

Bien, Gaynanova, Lederer, Müller

We now observe that Assumption 5 implies via the triangle inequality and the model assumptions that
2Ω ∗ (X ⊤ ε)
.
Ω ∗ (X ⊤ Y ) ≥
c
Using this, Hölder’s inequality, and the triangle inequality, we then find
kX β̂ − Xβ ∗ k22


2Ω ∗ (X ⊤ ε)
≤ 1−
2Ω ∗ (X ⊤ ε)Ω(β ∗ )
cΩ ∗ (X ⊤ Y )
+ 2Ω ∗ (X ⊤ ε)Ω(β ∗ )/c +

2Ω ∗ (X ⊤ ε) ∗ ⊤
Ω (X ε)Ω(β ∗ )
cΩ ∗ (X ⊤ Y )

=2Ω ∗ (X ⊤ ε)Ω(β ∗ ) + 2Ω ∗ (X ⊤ ε)Ω(β ∗ )/c −

2Ω ∗ (X ⊤ ε) ∗ ⊤
Ω (X ε)Ω(β ∗ )
cΩ ∗ (X ⊤ Y )

≤(2 + 2/c)Ω ∗ (X ⊤ ε)Ω(β ∗ ).
This concludes the proof for Case 2 and, therefore, the proof of Theorem 5.

