Penalized Estimation in Additive Regression
with High-Dimensional Data
Zhiqiang Tan1 & Cun-Hui Zhang

1

arXiv:1704.07229v1 [] 24 Apr 2017

April 25, 2017

Abstract.

Additive regression provides an extension of linear regression by modeling the

signal of a response as a sum of functions of covariates of relatively low complexity. We study
penalized estimation in high-dimensional nonparametric additive regression where functional
semi-norms are used to induce smoothness of component functions and the empirical L2 norm
is used to induce sparsity. The functional semi-norms can be of Sobolev or bounded variation
types and are allowed to be different amongst individual component functions. We establish
new oracle inequalities for the predictive performance of such methods under three simple
technical conditions: a sub-gaussian condition on the noise, a compatibility condition on the
design and the functional classes under consideration, and an entropy condition on the functional classes. For random designs, the sample compatibility condition can be replaced by its
population version under an additional condition to ensure suitable convergence of empirical
norms. In homogeneous settings where the complexities of the component functions are of the
same order, our results provide a spectrum of explicit convergence rates, from the so-called
slow rate without requiring the compatibility condition to the fast rate under the hard sparsity
or certain Lq sparsity to allow many small components in the true regression function. These
results significantly broadens and sharpens existing ones in the literature.
Key words and phrases.

Additive model; Bounded variation space; ANOVA model; High-

dimensional data; Metric entropy; Penalized estimation; Reproducing kernel Hilbert space;
Sobolev space; Total variation; Trend filtering.

1

Department of Statistics & Biostatistics, Rutgers University. Address: 110 Frelinghuysen Road, Piscataway,

NJ 08854. E-mail: ztan@stat.rutgers.edu, czhang@stat.rutgers.edu. The research of Z. Tan was supported in
part by PCORI grant ME-1511-32740. The research of C.-H. Zhang was supported in part by NSF grants
DMS-1513378, IIS-1250985, and IIS-1407939.

1

Introduction

Additive regression is an extension of linear regression where the signal of a response can
be written as a sum of functions of covariates of relatively low complexity. Let (Yi , Xi ),
i = 1, . . . , n, be a set of n independent (possibly non-identically distributed) observations,
where Yi ∈ R is a response variable and Xi ∈ Rd is a covariate (or design) vector. Consider an

additive regression model, Yi = g ∗ (Xi ) + εi with
g∗ (x) =

Pp

j=1

gj∗ (x(j) ),

(1)

where εi is a noise with mean 0 given Xi , x(j) is a vector composed of a small subset of the
components of x ∈ Rd , and gj∗ belongs to a certain functional class Gj . That is, g ∗ (x) lies in
P
the space of additive functions G = { pj=1 gj (x(j) ) : gj ∈ Gj , j = 1, . . . , p}. A function g ∈ G
Pp
(j)
may admit the decomposition g(x) =
j=1 gj (x ) for multiple choices of (g1 , . . . , gp ). In

what follows, such choices are considered equivalent but a favorite decomposition can be used
to evaluate properties of the components of g ∈ G.

In a classical setting (e.g., Stone 1985), each gj∗ is a univariate function and x(j) is the jth

component of x ∈ [0, 1]d , so that p = d. We take a broad view of additive regression and our
(j)

analysis will accommodate the general setting where gj∗ can be multivariate with Xi

being a

block of covariates, possibly overlapping across different j as in functional ANOVA (e.g., Gu
2002). However, most concrete examples will be given in the classical setting.
Additive modeling has been well studied in the setting where the number of components
p is fixed. See Hastie & Tibshirani (1990) and references therein. Recently, building upon
related works in penalized linear regression, there have been considerable progresses in the
development of theory and methods for sparse additive regression in high-dimensional settings
where p can be of greater order than the sample size n but the number of significant components
is still smaller than n. See, for example, Lin & Zhang (2006), Meier et al. (2009), Ravikumar
et al. (2009), Huang et al. (2010), Koltchinskii & Yuan (2010), Raskutti et al. (2012), Suzuki
& Sugiyama (2013), Petersen et al. (2016), and Yuan & Zhou (2016).
In this article, we study a penalized estimator ĝ with a specific associated decomposition
P
ĝ = pj=1 ĝj defined as a minimizer of a penalized loss
kY − gk2n /2 +

over g ∈ G and decompositions g =

Pp

Pp

j=1

j=1 gj ,

ρnj kgj kF,j + λnj kgj kn



where (λnj , ρnj ) are tuning parameters, k · kn is
1

the empirical L2 norm based on the data points, e.g. kY − gk2n = n−1

Pn

i=1 {Yi

− g(Xi )}2 , and

kgj kF,j is a semi-norm describing the complexity of gj ∈ Gj . For simplicity, the association of
(j)

kgj kn and kgj kF,j with Xi

is typically suppressed.

In the above penalty function, the primary role of the empirical norm k · kn is to induce
sparsity, whereas the primary role of the functional semi-norm k · kF,j is to induce smoothness
R 1 (m)
of the estimated regression function. For example, kgj kF,j = { 0 (gj )2 dz}1/2 when Gj is the
(m)

L2 -Sobolev space W2m on [0, 1], where gj

denotes the mth derivative of gj .

We consider both fixed and random designs and establish oracle inequalities for the predictive performance of ĝ under three simple technical conditions: a sub-gaussian condition on
noises, a compatibility condition on the design and the functional classes Gj , and an entropy
condition on Gj . The compatibility condition is similar to the restricted eigenvalue condition
used in analysis of Lasso, and for random designs, the empirical compatibility condition can be
replaced by its population version under an additional condition to ensue suitable convergence
of empirical norms. For the Sobolev and bounded variation classes, the entropy condition on
Gj follows from standard results in the literature (e.g., Lorentz et al. 1996).
The implications of our oracle inequalities can be highlighted in the classical homogeneous
(j)

setting where Xi

is the jth component of Xi and Gj = G0 for all j, where G0 is either an

Lr -Sobolev space Wrm or a bounded variation space V m of univariate functions on [0, 1], where

r ≥ 1 and m ≥ 1 are shape and smoothness indices of the space, and r = 1 for V m . In
this setting, it is natural to set (λnj , ρnj ) = (λn , ρn ) for all j. Consider random designs, and
suppose that for some choice of (g1∗ , . . . , gp∗ ) satisfying (1),
p
X
j=1

where kf k2Q = n−1

Pn

i=1 E{f

kgj∗ kF,j
2 (X )}
i

p
X

≤ C1 MF ,

j=1

kgj∗ kqQ ≤ C1q Mq ,

(2)

for a function f (x), C1 > 0 is a scaling constant depending

only on the moments of εi , and 0 ≤ q ≤ 1, Mq > 0 and MF > 0 are allowed to depend on

(n, p). In the case of hard sparsity, q = 0, M0 = #{j : gj∗ 6= 0}. As a summary, the following
result can be easily deduced from Proposition 3, 5, and 7.
Let β0 = 1/m and define
o
n
−1
1−q
wn∗ (q) = max n 2+β0 (1−q) , (log(p)/n) 2 ,


−1
−(1−q)β0
−1/2
∗
2+β0 (1−q)
4
,n
(log(p)/n)
γn (q) = min n
.
2

For simplicity, we restrict to the case where 1 ≤ r ≤ 2. For rm > 1, we assume that the
(j)

(j)

average marginal density of (X1 , . . . , Xn ) are uniformly bounded away from 0 and, if q 6= 1,
also uniformly bounded from above for all j = 1, . . . , p. The assumption of marginal densities
bounded from above, as well as the restriction 1 ≤ r ≤ 2, can be relaxed under slightly different
technical conditions (see Propositions 3, 4, and 6). For r = m = 1, neither the lower bound
nor the upper bound of marginal densities need to be assumed.
Proposition 1. Let G0 be a Sobolev space Wrm with 1 ≤ r ≤ 2 and m ≥ 1 or a bounded

variation space V m with r = 1 and m ≥ 1. Suppose that the noises are sub-gaussian and
√
log(p) = o(n). Let τ0 = 1/(2m + 1 − 2/r), Γn = 1 for rm > 1 and Γn = log n for r = m = 1.

(i) Let q = 1 and λn = ρn = A0 {log(p)/n}1/2 for a sufficiently large constant A0 . If p → ∞,

then
o
n
p
kĝ − g∗ k2Q = Op (1)C12 (MF2 + M12 ) n−1/2 Γn + log(p)/n .

(3)

(ii) Let q = 0, λn = A0 [γn∗ (0) + {log(p)/n}1/2 ] and ρn = λn wn∗ (0). Suppose that
n

wn∗ (0)−τ0

p

o
log(np)/n (1 + MF + M0 ) = o(1)

(4)

and a population compatibility condition (Assumption 5) holds. Then,
n −1
o2
p
kĝ − g∗ k2Q = Op (1)C12 (MF + M0 ) n 2+β0 + log(p)/n .

(5)

(iii) Let 0 < q < 1, λn = A0 [γn∗ (q) + {log(p)/n}1/2 ] and ρn = λn wn∗ (q). Suppose that
n

wn∗ (q)−τ0 (log(np)/n)

1−q
2

o

(1 + MF + Mq ) = O(1)

and a population compatibility condition (Assumption 7) holds. Then,
n
o2−q
p
−1
kĝ − g∗ k2Q = Op (1)C12 (MF + Mq ) n 2+β0 (1−q) + log(p)/n
.

(6)

There are several important features achieved by the foregoing result, distinct from existing
results. First, our results are established for additive regression with Sobolev spaces of general shape and bounded variation spaces. An important innovation in our proofs involves a
delicate application of maximal inequalities based on the metric entropy of a particular choice
of bounded subsets of G0 (see Lemma 1). All previous results seem to be limited to the L2 Sobolev spaces or similar reproducing kernel Hilbert spaces, except for Petersen et al. (2016),
who studied additive regression with the bounded variation space V 1 and obtained the rate
3

{log(np)/n}1/2 for in-sample prediction under assumption (2) with q = 1. In contrast, our

analysis in the case of q = 1 yields the sharper, yet standard, rate {log(p)/n}1/2 for in-sample
prediction (see Proposition 3), whereas {log(np)/n}1/2 for out-of-sample prediction by (3).

Second, the restricted parameter set (2) represents an L1 ball in k · kF semi-norm (inducing
smoothness) but an Lq ball in k · kQ norm (inducing sparsity) for the component functions
(g1∗ , . . . , gp∗ ). That is, the parameter set (2) decouples conditions for sparsity and smoothness

in additive regression: it can encourage sparsity at different levels 0 ≤ q ≤ 1 while enforcing
smoothness only to a limited extent. Accordingly, our result leads to a spectrum of convergence
rates, which are easily seen to slow down as q increases from 0 to 1, corresponding to weaker
sparsity assumptions. While most of previous results are obtained under exact sparsity (q =
0), Yuan & Zhou (2016) studied additive regression with reproducing kernel Hilbert spaces
Pp
∗ q
under an Lq ball in the Hilbert norm k · kH :
j=1 kgj kH ≤ Mq . This parameter set induces

smoothness and sparsity simultaneously and is in general more restrictive than (2). As a
result, the minimax rate of estimation obtained by Yuan & Zhou (2016), based on constrained
least squares with known Mq instead of penalized estimation, is faster than (6), in the form
n−2/(2+β0 ) + {log(p)/n}(2−q)/2 , unless q = 0 or 1.

Third, in the case of q = 1, our result (3) shows that the rate {log(p)/n}1/2 , with an

additional {log(n)/n}1/2 term for the bounded variation space V 1 , can be achieved via penalized

estimation without requiring a compatibility condition. This generalizes a slow-rate result for
constrained least-squares (instead of penalization) with known (M1 , MF ) in additive regression
with the Sobolev Hilbert space in Ravikumar et al. (2009). Both are related to earlier results
for linear regression (Greenhstein & Ritov 2004; Bunea et al. 2007).
Finally, compared with previous results giving the same rate of convergence (5) under exact
sparsity (q = 0) for Hilbert spaces, our results are stronger in requiring much weaker technical
conditions. The penalized estimation procedures in Koltchinskii & Yuan (2010) and Raskutti
et al. (2012), while minimizing a similar criterion as Kn (g), involve additional constraints:
Koltchinskii & Yuan (2010) assumed that the sup-norm of possible g∗ is bounded by a known
constant, where as Raskutti et al. (2012) assumed maxj kgj kH is bounded by a known constant.
(1)

(p)

Moreover, Raskutti et al. (2012) assumed that the covariates (Xi , . . . , Xi ) are independent
of each other. These restrictions were relaxed in Suzuki & Sugiyama (2013), but only explicitly
under the assumption that the noises εi are uniformly bounded by a constant. Moreover, our
rate condition (4) about the sizes of (M0 , MF ) is much weaker than in Suzuki & Sugiyama
4

(2013), due to improved analysis of convergence of empirical norms and the more careful
choices (λn , ρn ). For example, if (M0 , MF ) are bounded, then condition (4) holds whenever
log(p)/n = o(1) for Sobolev Hilbert spaces, but the condition previously required amounts to
log(p)n−1/2 = o(1). Finally, the seemingly faster rate in Suzuki & Sugiyama (2013) can be
deduced from our results when (λn , ρn ) is allowed to depend on (M0 , MF ). See Remarks 8 and
14–16 for relevant discussion.
The rest of the article is organized as follows. Section 2 gives a review of univariate functional
classes and entropies. Section 3 presents general results for fixed designs (Section 3.1) and
random designs (Section 3.2), and then provides specific results with Sobolev and bounded
variation spaces (Section 3.4) after a study of convergence of empirical norms (Section 3.3).
Section 4 concludes with a discussion. For space limitation, all proofs are collected in Section S1
and technical tools are stated in Section S2 of the Supplementary Material.

2

Functional classes and entropies

As a building block of additive regression, we discuss two broad choices for the function space Gj
and the associated semi-norm kgj kF,j in the context of univariate regression. For concreteness,
we consider a fixed function space, say G1 , although our discussion is applicable to Gj for j =
R1
1, . . . , p. For r ≥ 1, the Lr norm of a function f on [0, 1] is defined as kf kLr = { 0 |f (z)|r dz}1/r .

Example 1 (Sobolev spaces). For r ≥ 1 and m ≥ 1, let Wrm = Wrm ([0, 1]) be the Sobolev
(m−1)

space of all functions, g1 : [0, 1] → R, such that g1
(m)

(m)

kg1 kWrm = kg1 kLr + kg1 kLr is finite, where g1

is absolutely continuous and the norm

denotes the mth (weak) derivative of g1 . To
(m)

describe the smoothness, a semi-norm kg1 kF,1 = kg1 kLr is often used for g1 ∈ Wrm .

In the statistical literature, a major example of Sobolev spaces is W2m = {g1 : kg1 kL2 +

(m)

kg1 kL2 < ∞}, which is a reproducing kernel Hilbert space (e.g., Gu 2002). Consider a
univariate regression model
(1)

Yi = g1 (Xi ) + εi ,

i = 1, . . . , n.

(7)

The Sobolev space W2m is known to lead to polynomial smoothing splines through penalized
estimation: there exists a unique solution, in the form of a spline of order (2m − 1), when

minimizing over g1 ∈ W2m the following criterion
n
o2
1 Xn
(1)
Yi − g1 (Xi ) + ρn1 kg1 kF,1 .
2n
i=1

5

(8)

This solution can be made equivalent to the standard derivation of smoothing splines, where the
penalty in (8) is ρ′n1 kg1 k2F,1 for a different tuning parameter ρ′n1 . Particularly, cubic smoothing
splines are obtained with the choice m = 2.
Example 2 (Bounded variation spaces). For a function f on [0, 1], the total variation (TV)
of f is defined as
TV(f ) = sup

( k
X
i=1

)

|f (zi ) − f (zi−1 )| : z0 < z1 < . . . < zk is any partition of [0, 1] .

If f is differentiable, then TV(f ) =

R1
0

|f (1) (z)| dz. For m ≥ 1, let V m = V m ([0, 1]) be the
(m−2)

bounded variation space that consists of all functions, g1 : [0, 1] → R, such that g1
m ≥ 2, is absolutely continuous and the norm kg1 kV m = kg1 kL1 +

g1 ∈ V m , the semi-norm kg1 kF,1 =

(m−1)
TV(g1
)

(m−1)
TV(g1
)

, if

is finite. For

is often used to describe smoothness. The

bounded variation space V m includes as a strict subset the Sobolev space W1m , where the
(m−1)

semi-norms also agree: TV(g1

(m)

) = kg1 kL1 for g1 ∈ W1m .

For univariate regression (7) with bounded variation spaces, TV semi-norms can be used
as penalties in (8) for penalized estimation. This leads to a class of TV splines, which are
shown to adapt well to spatial inhomogeneous smoothness (Mammen & van de Geer 1997).
For m = 1 or 2, a minimizer of (8) over g1 ∈ V m can always be chosen as a spline of order m,
(1)

with the knots in the set of design points {Xi

: i = 1, . . . , n}. But, as a complication, this is

in general not true for m ≥ 3.
Recently, there is another smoothing method related to TV splines, called trend filtering
(1)

(Kim et al. 2009), where (8) is minimized over all possible values {g1 (Xi ) : i = 1, . . . , n}
with kg1 kF,1 replaced by L1 norm of mth-order differences of these values. This method is
equivalent to TV splines only for m = 1 or 2. But when the design points are evenly spaced,
it achieves the minimax rate of convergence over functions of bounded variation for general
m ≥ 1, similarly as TV splines (Tibshirani 2014).
The complexity of a functional class can be described by its metric entropy, which plays
an important role in the study of empirical processes (van der Vaart & Wellner 1996). For a
subset F in a metric space F endowed with norm k · k, the covering number N (δ, F, k · k) is
defined as the smallest number of balls of radius δ in the k·k-metric needed to cover F, i.e., the
smallest value of N such that there exist f1 , . . . , fN ∈ F , satisfying minj=1,...,N kf − fj k ≤ δ
for any f ∈ F. The entropy of (F, k · k) is defined as H(δ, F, k · k) = log N (δ, F, k · k).
6

For analysis of regression models, our approach involves using entropies of functional classes
(1)

for empirical norms based on design points, for example, {Xi

: i = 1, . . . , n} for subsets of G1 .
P
(1)
One type of such norms is the empirical L2 norm, kg1 kn = {n−1 ni=1 g12 (Xi )}1/2 . Another
(1)

is the empirical supremum norm, kg1 kn,∞ = maxi=1,...,n g1 (Xi ). If F is the unit ball in

the Sobolev space Wrm or the bounded variation space V m on [0, 1], the general picture is

H(δ, F, k · k) . δ−1/m for commonly used norms. See Section S2.5 for more.

3

Main results

As in Section 1, consider the estimator
Kn (g) = kY − gk2n /2 + A0 Rn (g),

ĝ = argming∈G Kn (g),
where A0 > 1 is a constant, G = {g =
Rn (g) =

p
X
j=1

for any decomposition g =

Pp

Pp

j=1 gj

(9)

: gj ∈ Gj } and the penalty is of the form

p 

X
ρnj kgj kF,j + λnj kgj kn
Rnj (gj ) =
j=1

j=1 gj

with gj ∈ Gj , with certain functional penalties kfj kF,j and

the empirical L2 penalty kfj kn . Here the regularization parameters (λnj , ρnj ) are of the form
ρnj = λnj wnj ,

n

λnj = C1 γnj +

p

o

log(p/ǫ)/n ,

where C1 > 0 is a noise level depending only on parameters in Assumption 1 below, 0 < ǫ < 1
is a tail probability for the validity of error bounds, 0 < wnj ≤ 1 is a rate parameter, and
γnj = n−1/2 ψnj (wnj )/wnj

(10)

for a function ψnj (·) depending on the entropy of the unit ball of the space Gj under the
associated functional penalty. See Assumption 2 or 4 below.
Before theoretical analysis, we briefly comment on computation of ĝ. By standard properties
of norms and semi-norms, the objective function Kn (g) is convex in g. Moreover, there are
at least two situations where the infinitely-dimensional problem of minimizing Kn (g) can be
reduced to a finite-dimensional one. First, if each class Gj is a reproducing kernel Hilbert space
P
such as W2m , then a solution ĝ = pj=1 ĝj can be obtained such that each ĝj is a smoothing
(j)

spline with knots in the design points {Xi

: i = 1, . . . , n} (e.g., Meier et al. 2009). Second, by

the following proposition, the optimization problem can be also reduced to a finite-dimensional
7

one when each class Gj is the bounded variation space V 1 or V 2 . As a result, the algorithm in
Petersen et al. (2016) can be directly used to find ĝ when all classes (G1 , . . . , Gp ) are V 1 .

Proposition 2. Suppose that the functional class Gj is V m for some 1 ≤ j ≤ p and m = 1
P
or 2. Then a solution ĝ = pj=1 ĝj can be chosen such that ĝj is piecewise constant with jump
(j)

points only in {Xi

: i = 1, . . . , n} if m = 1, or ĝj is continuous and piecewise linear with
(j)

break points only in {Xi

: i = 1, . . . , n} if m = 2.

By Example 2, it can be challenging to compute ĝ when some classes Gj are V m with m ≥ 3.
However, this issue may be tackled using trend filtering (Kim et al. 2009) as an approximation.

3.1

Fixed designs

For fixed designs, the covariates (X1 , . . . , Xn ) are fixed as observed, whereas (ε1 , . . . , εn ) and
hence (Y1 , . . . , Yn ) are independent random variables. The responses are to be predicted when
new observations are drawn with covariates from the sample (X1 , . . . , Xn ). The predictive
performance of ĝ is measured by kĝ − g ∗ k2n .
Consider the following three assumptions. First, we assume sub-gaussian tails for the noises.
This condition can be relaxed, but with increasing technical complexity and possible modification of the estimators, which we will not pursue here.
Assumption 1 (Sub-gaussian noises). Assume that the noises (ε1 , . . . , εn ) are mutually independent and uniformly sub-Gaussian: For some constants D0 > 0 and D1 > 0,
max D0 E exp(ε2i /D0 ) ≤ D1 .

i=1,...,n

We will also impose this assumption for random designs with the interpretation that the above
probability and expectation are taken conditionally on (X1 , . . . , Xn ).
Second, we impose an entropy condition which describes the relationship between the function ψnj (·) in the definition of γnj and the complexity of bounded subsets in Gj . Although
entropy conditions are widely used to analyze nonparametric regression (e.g., Section 10.1, van
de Geer 2000), the subset Gj (δ) in our entropy condition below is carefully aligned with the
penalty Rnj (gj ) = λnj (wnj kgj kF,j + kgj kn ). This leads to a delicate use of maximal inequalities so as to relax and in some cased remove some restrictions in previous studies of additive
models. See Lemma 1 in the Supplement and Raskutti et al. (2012, Lemma 1).
8

Assumption 2 (Entropy condition for fixed designs). For j = 1, . . . , p, let Gj (δ) = {fj ∈ Gj :
kfj kF,j + kfj kn /δ ≤ 1} and ψnj (δ) be an upper bound of the entropy integral as follows:
Z δ
H 1/2 (u, Gj (δ), k · kn ) du, 0 < δ ≤ 1.
(11)
ψnj (δ) ≥
0

(j)

In general, Gj (δ) and the entropy H(·, Gj (δ), k · kn ) may depend on the design points {Xi }.
The third assumption is a compatibility condition, which resembles the restricted eigenvalue
condition used in high-dimensional analysis of Lasso in linear regression (Bickel et al. 2009).
Similar compatibility conditions were used by Meier et al. (2009) and Koltchinskii & Yuan
(2010) in their analysis of penalized estimation in high-dimensional additive regression.
Assumption 3 (Empirical compatibility condition). For certain subset S ⊂ {1, 2, . . . , p} and
constants κ0 > 0 and ξ0 > 1, assume that


2 
X
X
λnj kfj kn  ≤ 
κ20 
λ2nj  kf k2n
j∈S

j∈S

for any functions {fj ∈ Gj : j = 1, . . . , p} and f =
p
X
j=1

λnj wnj kfj kF,j +

X

j∈S c

Pp

j=1 fj

∈ G satisfying

λnj kfj kn ≤ ξ0

X
j∈S

λnj kfj kn .

Remark 1. The subset S can be different from {1 ≤ j ≤ p : gj∗ 6= 0}. In fact, S is arbitrary
in the sense that a larger S leads to a smaller compatibility coefficient κ0 which appears as a
factor in the denominator of the “noise” term in the prediction error bound below, whereas a
smaller S leads to a larger “bias” term. Assumption 3 is automatically satisfied for the choice
S = ∅. In this case, it is possible to take ξ0 = ∞ and any κ0 > 0, provided that we treat
summation over an empty set as 0 and ∞ × 0 as 0.
Our main result for fixed designs is an oracle inequality stated in Theorem 1 below, where
P
ḡ = pj=1 ḡj ∈ G as an estimation target is an additive function but the true regression function
g∗ may not be additive. Denote as a penalized prediction loss
Dn (ĝ, ḡ) =

1
1
kĝ − g∗ k2n + kĝ − ḡk2n + (A0 − 1)Rn (ĝ − ḡ).
2
2

For a subset S ⊂ {1, 2, . . . , p}, write as a bias term for the target ḡ

P
P
1
p
λ
kḡ
k
ρ
kḡ
k
+
∆n (ḡ, S) = kḡ − g∗ k2n + 2A0
j∈S c nj j n .
j=1 nj j F,j
2
The bias term is small when ḡ is smooth and sparse and predicts g ∗ well.

9

Theorem 1. Suppose that Assumptions 1, 2, and 3 hold. Then for any A0 > (ξ0 + 1)/(ξ0 − 1),
we have with probability at least 1 − ǫ,
Dn (ĝ, ḡ) ≤ ξ1−1 ∆n (ḡ, S) + 2ξ22 κ−2
0

P


2
λ
j∈S nj .

(12)

where ξ1 = 1 − 2A0 /{(ξ0 + 1)(A0 − 1)} ∈ (0, 1] and ξ2 = (ξ0 + 1)(A0 − 1).
Remark 2. As seen from our proofs, Theorem 1 and subsequent corollaries are directly ap(j)

plicable to functional ANOVA modeling, where each function gj may depend on Xi , a block
of covariates, and the variable blocks are allowed to overlap across different j. The entropy
associated with the functional class Gj need to be determined accordingly.
Remark 3. Using ideas from Bellec and Tsybakov (2016), it is possible to refine the oracle
inequality for ĝ, such that the scaling parameter ǫ is fixed, for example, ǫ = 1/2 in the definition
of ĝ in (9), but at any level 0 < ǫ̃ < 1, (12) holds with probability 1 − ǫ̃ when an additional
term of the form log(1/ǫ̃)/n on the right-hand side.
Taking S = ∅ and ξ0 = ∞ leads to the following corollary, which explicitly does not require
the compatibility condition (Assumption 3).
Corollary 1. Suppose that Assumptions 1 and 2 hold. Then for any A0 > 1, we have with
probability at least 1 − ǫ,
1
Dn (ĝ, ḡ) ≤ ∆n (ḡ, ∅) = kḡ − g∗ k2n + 2A0 Rn (ḡ).
2

(13)

The following result can be derived from Theorem 1 through the choice S = {1 ≤ j ≤ p :
kḡj kn > C0 λnj } for some constant C0 > 0.
Corollary 2. Suppose that Assumptions 1, 2, and 3 hold with S = {1 ≤ j ≤ p : kḡj kn >
C0 λnj } for some constant C0 > 0. Then for any 0 ≤ q ≤ 1 and A0 > (ξ0 + 1)/(ξ0 − 1), we
have with probability at least 1 − ǫ,


p 


X
q
Dn (ĝ, ḡ) ≤ O(1) kḡ − g ∗ k2n +
ρnj kḡj kF,j + λ2−q
nj kḡj kn  ,

j=1

where O(1) depends only on (q, A0 , C0 , ξ0 , κ0 ).

It is instructive to examine the implications of Corollary 2 in a homogenous situation where
for some constants B0 > 0 and 0 < β0 < 2,
Z δ
H 1/2 (u, Gj (δ), k · kn ) du ≤ B0 δ1−β0 /2 ,
max
j=1,...,p 0

10

0 < δ ≤ 1.

(14)

That is, we assume ψnj (δ) = B0 δ1−β0 /2 in (11). For j = 1, . . . , p, let
wnj = wn (q) = {γn (q)}1−q ,

2
2+β0 (1−q)

γnj = γn (q) = B0

−1

n 2+β0 (1−q) ,

(15)

1−q
which are determined by balancing the two rates ρnj = λ2−q
nj , that is, wnj = λnj , along with the
P
P
−β /2
definition γnj = B0 n−1/2 wnj 0 by (10). For g = pj=1 gj ∈ G, denote kgkF,1 = pj=1 kgj kF,j
P
and kgkn,q = pj=1 kgj kqn . For simplicity, we also assume that g∗ is an additive function and

set ḡ = g ∗ for Corollary 3.

Corollary 3. Assume that (1) holds and kg∗ kF,1 ≤ C1 MF and kg∗ kn,q ≤ C1q Mq for 0 ≤ q ≤ 1,
Mq > 0, and MF > 0, possibly depending on (n, p). In addition, suppose that (14) and (15)
hold, and Assumptions 1 and 3 are satisifed with S = {1 ≤ j ≤ p : kgj∗ kn > C0 λnj } for some
constant C0 > 0. If 0 < wn (q) ≤ 1 for sufficiently large n, then for any A0 > (ξ0 + 1)/(ξ0 − 1),
we have with probability at least 1 − ǫ,
Dn (ĝ, g∗ ) = kĝ − g ∗ k2n + (A0 − 1)Rn (ĝ − g∗ )
n
o2−q
p
≤ O(1)C12 (MF + Mq ) γn (q) + log(p/ǫ)/n
,

(16)

where O(1) depends only on (q, A0 , C0 , ξ0 , κ0 ).

Remark 4. There are several interesting features in the convergence rate (16). First, (16)
presents a spectrum of convergence rates in the form
n

−1

n 2+β0 (1−q) +

p

log(p)/n

o2−q

,

which are easily shown to become slower as q increases from 0 to 1, that is, the exponent
(2 − q)/{2 + β0 (1 − q)} is decreasing in q for 0 < β0 < 2. The rate (16) gives the slow rate
−2

{log(p)/n}1/2 for q = 1, or the fast rate n 2+β0 + log(p)/n for q = 0, as previously obtained

for additive regression with reproducing kernel Hilbert spaces. We defer to Section 3.4 the
comparison with existing results in random designs. Second, the rate (16) is in general at least
as fast as
n −1
o2−q
p
n 2+β0 + log(p)/n
.

Therefore, weaker sparsity (larger q) leads to a slower rate of convergence, but not as slow
−2

as the fast rate {n 2+β0 + log(p)/n} raised to the power of (2 − q)/2. This is in contrast
with previous results on penalized estimation over Lq sparsity balls, for example, the rate
{k/n + log(p)/n}(2−q)/2 obtained for group Lasso estimation in linear regression (Neghaban
11

et al. 2012), where k is the group size. Third, the rate (16) is in general not as fast as the
following rate (unless q = 0 or 1)
−2

n 2+β0 + {log(p)/n}(2−q)/2 ,
which was obtained by Yuan & Zhou (2016) using constrained least squares for additive
regression with reproducing kernel Hilbert spaces under an Lq ball in the Hilbert norm:
Pp
∗ q
j=1 kgj kH ≤ Mq . This difference can be explained by the fact that an Lq ball in k · kH

norm is more restrictive than in k · kn or k · kQ norm for our results.

3.2

Random designs

For random designs, prediction of the responses can be sought when new observations are randomly drawn with covariates from the distributions of (X1 , . . . , Xn ), instead of within the sample (X1 , . . . , Xn ) as in Section 3.1. For such out-of-sample prediction, the performance of ĝ is
P
measured by kĝ−g ∗ k2Q , where k·kQ denotes the theoretical norm: kf k2Q = n−1 ni=1 E{f 2 (Xi )}
for a function f (x).

Consider the following two extensions of Assumptions 2 and 3, such that dependency on
the empirical norm k · kn and hence on (X1 , . . . , Xn ) are removed.
Assumption 4 (Entropy condition for random designs). For some constant 0 < η0 < 1 and
j = 1, . . . , p, let ψnj (δ) be an upper bound of the entropy integral, independent of the realizations
(j)

{Xi

: i = 1, . . . , n}, as follows:
ψnj (δ) ≥

Z

δ
0

H ∗1/2 ((1 − η0 )u, Gj∗ (δ), k · kn ) du,

0 < δ ≤ 1,

(17)

where Gj∗ (δ) = {fj ∈ Gj : kfj kF,j + kfj kQ /δ ≤ 1} and
H ∗ (u, Gj∗ (δ), k · kn ) =

sup
(j)
(j)
(X1 ,...,Xn )

H(u, Gj∗ (δ), k · kn ).

Assumption 5 (Theoretical compatibility condition). For some subset S ⊂ {1, 2, . . . , p} and

constants κ∗0 > 0 and ξ0∗ > 1, assume that for any functions {fj ∈ Gj : j = 1, . . . , p} and
P
f = pj=1 fj ∈ G, if
p
X
j=1

λnj wnj kfj kF,j +

X

j∈S c

λnj kfj kQ ≤ ξ0∗

12

X
j∈S

λnj kfj kQ ,

(18)

then



κ∗2
0

X
j∈S

2



X
λnj kfj kQ  ≤ 
λ2nj  kf k2Q .

(19)

j∈S

Remark 5. Similarly as in Remark 1 about the empirical compatibility condition, Assumption 5 is also automatically satisfied for the choice S = ∅, in which case it is possible to take

ξ0∗ = ∞ and any κ∗0 > 0.

To tackle random designs, our approach relies on establishing appropriate convergence of
empirical norms k · kn to k · kQ uniformly over the space of additive functions G, similarly as
in Meier et al. (2009) and Koltchinskii & Yuan (2010). For clarity, we postulate the following
assumption on the rate of such convergence to develop general analysis of ĝ. We will study
convergence of empirical norms specifically for Sobolev and bounded variation spaces in Section 3.3, and then provide corresponding results on the performance of ĝ in Section 3.4. For
P
g = pj=1 gj ∈ G, denote
Rn∗ (g)

=

p
X
j=1

∗
Rnj
(gj ),

∗
Rnj
(gj ) = λnj (wnj kgj kF,j + kgj kQ ),

as the population version of the penalty Rn (g), with kgj kQ in place of kgj kn .
Assumption 6 (Convergence of empirical norms). Assume that




kgk2n − kgk2Q
P sup
>
φ
≤ π,
n
 g∈G

Rn∗2 (g)

(20)

where 0 < π < 1 and φn > 0 such that for sufficiently large n, one or both of the following
conditions are valid.
(i) φn (maxj=1,...,p λ2nj ) ≤ η02 , where η0 is from Assumption 4.
(ii) For some constant 0 ≤ η1 < 1, we have



φn (ξ0∗ + 1)2 κ∗−2
0

X
j∈S



λ2nj  ≤ η12 ,

(21)

where S is the subset of {1, 2, . . . , p} used in Assumption 5.

Our main result, Theorem 2, gives an oracle inequality for random designs, where the predicP
tive performance of ĝ is compared with that of an arbitrary additive function ḡ = pj=1 ḡj ∈ G,
13

but the true regression function g ∗ may not be additive, similarly as in Theorem 1 for fixed
designs. For a subset S ⊂ {1, 2, . . . , p}, denote


1
∆∗n (ḡ, S) = kḡ − g ∗ k2n + 2A0 (1 − η0 ) 
2

p
X
j=1

ρnj kḡj kF,j +

X

j∈S c



λnj kḡj kQ  ,

which, unlike ∆n (ḡ, S), involves kḡj kQ and η0 from Assumptions 4 and 6(i).

Theorem 2. Suppose that Assumptions 1, 4, 5 and 6(i)–(ii) hold with 0 < η0 < (ξ0∗ − 1)/(ξ0∗ +
1). Let A(ξ0∗ , η0 ) = {ξ0∗ + 1 + η0 (ξ0∗ + 1)}/{ξ0∗ − 1 − η0 (ξ0∗ + 1)} > (1 + η0 )/(1 − η0 ). Then for

any A0 > A(ξ0∗ , η0 ), we have with probability at least 1 − ǫ − π,

1
1
kĝ − g ∗ k2n + kĝ − ḡk2n + (1 − η1 )A1 Rn∗ (ĝ − ḡ)
2
2


X

λ2nj  ,
≤ ξ1∗−1 ∆∗n (ḡ, S) + 2ξ2∗2 κ∗−2
0

(22)

j∈S

where A1 = (A0 − 1) − η0 (A0 + 1) > 0, ξ1∗ = 1 − 2A0 /{(ξ0∗ + 1)A1 } ∈ (0, 1] and ξ2∗ = (ξ0∗ + 1)A1 .
Moreover, we have with probability at least 1 − ǫ − π,
1
1
kĝ − g ∗ k2n + kĝ − ḡk2Q + A2 Rn∗ (ĝ − ḡ)
2
2

X
φn
∗

≤ ξ3∗−1 ∆∗n (ḡ, S) + 2ξ4∗2 κ∗−2
λ2nj  +
ξ ∗−2 ∆∗2
n (ḡ, g , S),
0
2A1 A2 3

Dn∗ (ĝ, ḡ) :=

(23)

j∈S

where A2 = A1 /(1 − η12 ), ξ3∗ = ξ1∗ (1 − η12 ), and ξ4∗ = ξ2∗ /(1 − η12 ).

Remark 6. Similarly as in Remark 2, we emphasize that Theorem 2 and subsequent corollaries
are also applicable to functional ANOVA modeling (e.g., Gu 2002). For example, consider
model (1) studied in Yang & Tokdar (2015), where each gj∗ is assumed to depend only on d0

of a total of d covariates and lie in a Hölder space with smoothness level α0 . Then p = dd0 ,

and the entropy condition (27) holds with β0 = d0 /α0 . Under certain additional conditions,
Corollary 6 with q = 0 shows that penalized estimation studied here achieves a convergence
−2

−2

rate M0 n 2+β0 + M0 log(p)/n under exact sparsity of size M0 , where n 2+β0 is the rate for
estimation of a single regression function in the Hölder class in dimension d0 with smoothness
β0−1 , and log(p)/n ≍ d0 log(d/d0 )/n is the term associated with handling p regressors. This
result agrees with the minimax rate derived in Yang & Tokdar (2015), but can be applied when
more general functional classes are used such as multi-dimensional Sobolev spaces. In addition,
14

Yang & Todkar (2015) considered adaptive Bayes estimators which are nearly minimax with
some extra logarithmic factor in n.
Taking S = ∅, ξ0∗ = ∞, and η1 = 0 leads to the following corollary, which explicitly
does not require the theoretical compatibility condition (Assumption 5) or the rate condition,
Assumption 6(ii), for convergence of empirical norms.
Corollary 4. Suppose that Assumptions 1, 4, and 6(i) hold. Then for any A0 > (1 + η0 )/(1 −
η0 ), we have with probability at least 1 − ǫ − π,
1
1
kĝ − g∗ k2n + kĝ − ḡk2n + A1 Rn∗ (ĝ − ḡ)
2
2
1
∗
≤ ∆n (ḡ, ∅) = λ2n0 + kḡ − g∗ k2n + 2A0 Rn∗ (ḡ).
2

(24)

Moreover, we have with probability at least 1 − ǫ − π,
1
1
kĝ − g∗ k2n + kĝ − ḡk2Q + A1 Rn∗ (ĝ − ḡ)
2
2
φn ∗2
∗
≤ ∆n (ḡ, ∅) +
∆ (ḡ, ∅).
2A21 n

(25)

The preceding results deal with both in-sample and out-of-sample prediction. For space limitation, except in Proposition 3, we hereafter focus on the more challenging out-of-sample prediction. Under some rate condition about φn in (20), the additional term involving φn ∆∗2
n (ḡ, S)
can be absorbed into the first term, as shown in the following corollary. Two possible scenarios
are accommodated. On one hand, taking ḡ = g ∗ directly gives high-probability bounds on the
prediction error kĝ − g∗ k2Q provided that g∗ is additive, that is, model (1) is correctly specified.
On the other hand, the error kĝ − g ∗ k2Q can also be bounded, albeit in probability, in terms of
an arbitrary additive function ḡ ∈ G, while allowing g ∗ to be non-additive.

Corollary 5. Suppose that the conditions of Theorem 2 hold with S = {1 ≤ j ≤ p : kḡj kQ >
C0∗ λnj } for some constant C0∗ > 0, and (20) holds with φn > 0 also satisfying


p
X
X
φn 
ρnj kḡj kF,j +
λnj kḡj kQ  ≤ η2 ,

(26)

j∈S c

j=1

for some constant η2 > 0. Then for any 0 ≤ q ≤ 1 and A0 > A(ξ0∗ , η0 ), we have with probability
at least 1 − ǫ − π,

p 

X
2−q
ρnj kḡj kF,j + λnj
kḡj kqQ
Dn∗ (ĝ, ḡ) ≤ {O(1) + φn kḡ − g ∗ k2n } kḡ − g ∗ k2n +
,





j=1

15

where O(1) depends only on (q, A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 , η1 , η2 ). In addition, suppose that φn kḡ − g∗ k2Q
is bounded by a constant and ǫ = ǫ(n, p) tends to 0 in the definition of ĝ in (9). Then for any
0 ≤ q ≤ 1, we have


p 

X
q
kĝ − g∗ k2Q ≤ Op (1) kḡ − g ∗ k2Q +
ρnj kḡj kF,j + λ2−q
nj kḡj kQ  .




j=1

Similarly as Corollary 3, it is useful to deduce the following result in a homogeneous situation
where for some constants B0∗ > 0 and 0 < β0 < 2,
Z δ
H ∗1/2 ((1 − η0 )u, Gj∗ (δ), k · kn ) du ≤ B0∗ δ1−β0 /2 ,
max
j=1,...,p 0

0 < δ ≤ 1.

(27)

That is, we assume ψnj (δ) = B0∗ δ1−β0 /2 in (17). For j = 1, . . . , p, let
wnj = wn∗ (q) = max{γn (q)1−q , νn1−q },

(28)

γnj = γn∗ (q) = min{γn (q), B0∗ n−1/2 νn−(1−q)β0 /2 },

(29)

where νn = {log(p/ǫ)/n}1/2 , and wn (q) = γn (q)1−q and
2

−1

−1

γn (q) = B0∗ 2+β0 (1−q) n 2+β0 (1−q) ≍ n 2+β0 (1−q)
are determined from the relationship (10), that is, γn (q) = B0∗ n−1/2 wn (q)−β0 /2 . The reason
why (wn∗ (q), γn∗ (q)) are used instead of the simpler choices (wn (q), γn (q)) is that the rate condition (30) needed below would become stronger if γn∗ (q) were replaced by γn (q). The rate
of convergence, however, remains the same even if γn∗ (q) is substituted for γn (q) in (31). See
P
P
Remark 16 for further discussion. For g = pj=1 gj ∈ G, denote kgkF,1 = pj=1 kgj kF,j and
P
kgkQ,q = pj=1 kgj kqQ .
Corollary 6. Assume that (1) holds and kg∗ kF,1 ≤ C1 MF and kg ∗ kQ,q ≤ C1q Mq for 0 ≤ q ≤ 1,

Mq > 0, and MF > 0, possibly depending on (n, p). In addition, suppose that (27), (28),
and (29) hold, Assumptions 1, 5, and 6(i) are satisfied with 0 < η0 < (ξ0∗ − 1)/(ξ0∗ + 1) and

S = {1 ≤ j ≤ p : kgj∗ kQ > C0∗ λnj } for some constant C0∗ > 0, and (20) holds with φn > 0
satisfying
o2−q
n
p
= o(1).
φn C12 (MF + Mq ) γn∗ (q) + log(p/ǫ)/n

(30)

Then for sufficiently large n, depending on (MF , Mq ) only through the convergence rate in (30),
and any A0 > A(ξ0∗ , η0 ), we have with probability at least 1 − ǫ − π,
o2−q
n
p
Dn∗ (ĝ, g∗ ) ≤ O(1)C12 (MF + Mq ) γn (q) + log(p/ǫ)/n
,
16

(31)

where O(1) depends only on (q, A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 ).
In the case of q 6= 0, Corollary 6 can be improved by relaxing the rate condition (30) but
requiring the following compatibility condition, which is seemingly stronger than Assumption 5,
and also more aligned with those used in related works on additive regression (Meier et al. 2009;
Koltchinskii & Yuan 2010).
Assumption 7 (Monotone compatibility condition). For some subset S ⊂ {1, 2, . . . , p} and

constants κ∗0 > 0 and ξ0∗ > 1, assume that for any functions {fj ∈ Gj : j = 1, . . . , p} and
P
f = pj=1 fj ∈ G, if (18) holds then
κ∗2
0

X
j∈S

kfj k2Q ≤ kf k2Q .

(32)

Remark 7. By the Cauchy–Schwartz inequality, (32) implies (19), and hence Asssumption 7
is stronger than Assumption 5. However, there is a monotonicity in S for the validity of
Assumption 7 with (32) used. In fact, for any subset S ′ ⊂ S and any functions {fj′ ∈ Gj : j =
P
1, . . . , p} and f ′ = pj=1 fj′ ∈ G, if
p
X
j=1

λnj wnj kfj′ kF,j +

X

j∈S ′c

λnj kfj′ kQ ≤ ξ0∗

X

j∈S ′

λnj kfj′ kQ ,

then (18) holds with fj = fj′ , j = 1, . . . , p, and hence, via (32), implies
kf ′ k2Q ≥ κ∗2
0

X
j∈S

kfj′ k2Q ≥ κ∗2
0

X

j∈S ′

kfj′ k2Q .

Therefore, if Assumption 7 holds for a subset S, then it also holds for any subset S ′ ⊂ S with

the same constants (ξ0∗ , κ∗ ).

Corollary 7. Suppose that the conditions of Corollary 6 are satisfied with 0 < q ≤ 1 (excluding
q = 0), Assumption 7 holds instead of Assumption 5, and the following condition holds instead
of (30),
o2−q
n
p
≤ η3 ,
φn C12 (MF + Mq ) γn∗ (q) + log(p/ǫ)/n

(33)

for some constant η3 > 0. If 0 < wn∗ (q) ≤ 1 for sufficiently large n, then for any A0 >
A(ξ0∗ , η0 ), inequality (31) holds with probability at least 1 − ǫ − π, where O(1) depends only on

(q, A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 , η3 ).

17

To demonstrate the flexibility of our approach and compare with related results, notably
Suzuki & Sugiyama (2013), we provide another result in the context of Corolloary 6 with
(wnj , γnj ) allowed to depend on (MF , Mq ), in contrast with the choices (28)–(29) independent
of (MF , Mq ). For j = 1, . . . , p, let
wnj = wn† (q) = max{wn′ (q), νn1−q (Mq /MF )},

(34)

γnj = γn† (q) = min{γn′ (q), B0∗ n−1/2 νn−(1−q)β0 /2 (Mq /MF )−β0 /2 },

(35)

2

−β0

−1

where wn′ (q) = γn′ (q)1−q (Mq /MF ) and γn′ (q) = B0∗ 2+β0 (1−q) n 2+β0 (1−q) (Mq /MF ) 2+β0 (1−q) are determined along with the relationship γn′ (q) = B0∗ n−1/2 wn′ (q)−β0 /2 by (10). These choices are
picked to balance the two rates: λn wn MF and λn2−q Mq , where wn and λn denote the common
values of wnj and λnj for j = 1, . . . , p.
Corollary 8. Suppose that the conditions of Corollary 6 are satisfied except that (wnj , γnj )
are defined by (34)–(35), and the following condition holds instead of (30),
n
o2−q
p
φn C12 Mq γn† (q) + log(p/ǫ)/n
= o(1).

(36)

Then for sufficiently large n, depending on (MF , Mq ) only through the convergence rate in (36),
and any A0 > A(ξ0∗ , η0 ), we have with probability at least 1 − ǫ − π,
(
Dn∗ (ĝ, g ∗ ) ≤ O(1)C12

2−β0
2+β0 (1−q)

Mq

(2−q)β0
2+β0 (1−q)

MF

n

−(2−q)
2+β0 (1−q)

+ Mq νn2−q

)

,

(37)

where O(1) depends only on (q, B0∗ , A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 ).
Remark 8. In the special case of q = 0 (exact sparsity), the convergence rate (37) reduces to
2−β0
2+β0

M0

2β0
2+β0

MF

−2

n 2+β0 + M0 νn2 . The same rate was obtained in Suzuki & Sugiyama (2013) under
p
X
j=1

kgj∗ k0Q

≤ M0 ,

p
X
j=1

kgj∗ kH ≤ MF ≤ cM0 ,

(38)

with a constant c for additive regression with reproducing kernel Hilbert spaces, where kgj∗ kH
is the Hilbert norm. As one of their main points, this rate was argued to be faster than
−2

(M0 + MF )n 2+β0 + M0 νn2 , that is, the rate (31) with q = 0 under (38). Our analysis sheds
new light on the relationship between the rates (31) and (37): their difference mainly lies in
whether the tuning parameters (wnj , γnj ) are chosen independently of (MF , M0 ) or depending
on (MF , M0 ).
18

3.3

Convergence of empirical norms

We provide two explicit results on the convergence of empirical norms as needed for Assumption 6. These results can also be useful for other applications.
Our first result, Theorem 3, is applicable (but not limited) to Sobolev and bounded variation
spaces in general. For clarity, we postulate another entropy condition, similar to Assumption 4
but with the empirical supremum norms.
Assumption 8 (Entropy condition in supremum norms). For j = 1, . . . , p, let ψnj,∞ (·, δ) be
(j)

an upper envelope of the entropy integral, independent of the realizations {Xi

: i = 1, . . . , n},

as follows:
ψnj,∞(z, δ) ≥

Z

0

z

H ∗1/2 (u/2, Gj∗ (δ), k · kn,∞ ) du,

z > 0, 0 < δ ≤ 1,

where Gj∗ (δ) = {fj ∈ Gj : kfj kF,j + kfj kQ /δ ≤ 1} as in Assumption 4 and
H ∗ (u, Gj∗ (δ), k · kn,∞ ) =

sup
(j)
(j)
(X1 ,...,Xn )

H(u, Gj∗ (δ), k · kn,∞ ).

We also make use of the following two conditions about metric entropies and sup-norms.
Suppose that for j = 1, . . . , p, ψnj (δ) and ψnj,∞ (z, δ) in Assumptions 4 and 8 are in the
polynomial forms
ψnj (δ) = Bnj δ1−βj /2 ,

0 < δ ≤ 1,

ψnj,∞ (z, δ) = Bnj,∞z 1−βj /2 ,

(39)

z > 0, 0 < δ ≤ 1,

(40)

where 0 < βj < 2 is a constant, and Bnj > 0 and Bnj,∞ > 0 are constants, possibly depending
on n. Denote Γn = maxj=1,...,p (Bnj,∞ /Bnj ). In addition, suppose that for j = 1, . . . , p,
kgj k∞ ≤ (C4,j /2) kgj kF,j + kgj kQ

τj

1−τj

kgj kQ

,

gj ∈ Gj ,

(41)

where C4,j ≥ 1 and 0 < τj ≤ (2/βj − 1)−1 are constants. Let γnj = n−1/2 ψnj (wnj )/wnj =
−β /2

n−1/2 Bnj wnj j

−τ

by (10) and γ̃nj = n−1/2 wnj j for j = 1, . . . , p. As a function of wnj , the

quantity γ̃nj in general differs from γnj even up to a multiplicative constant unless τj = βj /2
as in the case where Gj is an L2 -Sobolev space; see (43) below.
Theorem 3. Suppose that Assumptions 4 and 8 hold with ψnj (δ) and ψnj,∞(z, δ) in the forms
(39) and (40), and condition (41) holds. In addition, suppose that for sufficiently large n,
19

1−βj /2

γnj ≤ wnj ≤ 1 and Γn γnj

≤ 1 for j = 1, . . . , p. Then for any 0 < ǫ′ < 1 (for example,

ǫ′ = ǫ), inequality (20) holds with π = ǫ′ 2 and φn > 0 such that

β
τ /2
γ̃nj wnjp+1 j
γnj
1/2
max
φn = O(1) n Γn max
j
j λnj
λnj
p
2 log(p/ǫ′ ) 
γ̃nj
log(p/ǫ′ )
γ̃nj
+ max
max
+ max
,
j λnj
j
j
λnj
λ2nj

(42)

where βp+1 = minj=1,...,p βj , and O(1) depends only on (C2 , C3 ) from Lemmas 13 and 14 and
C4 = maxj=1,...,p C4,j from condition (41).
To facilitate justification of conditions (39), (40), and (41), consider the following assumption on the marginal densities of the covariates, as commonly imposed when handling random
designs (e.g., Stone 1982).
Assumption 9 (Non-vanishing marginal densities). For j = 1, . . . , p, denote by qj (x(j) ) the
(j)

(j)

average marginal density function of (X1 , . . . , Xn ), that is, the density function associated
P
(j)
with the probability measure n−1 ni=1 QX (j) , where QX (j) is the marginal distribution of Xi .
i

i

For some constant 0 < ̺0 ≤ 1, assume that qj (x(j) ) is bounded from below by ̺0 simultaneously
for j = 1, . . . , p.
Remark 9. Conditions (39), (40), and (41) are satisfied under Assumption 9, when each Gj
m

is a Sobolev space Wrj j for rj ≥ 1 and mj ≥ 1, or a bounded variation space V mj for rj = 1
and mj ≥ 1, on [0, 1]. Let βj = 1/mj . First, (41) is implied by the interpolation inequalities
for Sobolev spaces (Nirenberg 1966) with
τj = (2/βj + 1 − 2/rj )−1

(43)

∗
and C4,j = ̺−1
0 C4 (mj , rj ) as stated in Lemma 21 of the Supplement. Moreover, if fj ∈ Gj (δ)

with 0 < δ ≤ 1, then kfj kF,j ≤ 1 and kfj kQ ≤ δ, and hence kfj kLrj ≤ kfj k∞ ≤ C4,j by
(41). By rescaling the entropy estimates for Sobolev and bounded variation spaces (Lorentz
et al. 1996) as in Lemmas 19 and 20 of the Supplement, Assumptions 4 and 8 are satisfied
such that (39) and (40) hold with Bnj independent of n, and Bnj,∞ = O(1)Bnj if rj > βj or
Bnj,∞ = O(log1/2 (n))Bnj if rj = βj = 1.
Remark 10. Assumption 9 is not needed for justification of (39), (40), and (41), when each
class Gj is W11 or V 1 on [0, 1], that is, rj = mj = 1. In this case, condition (41) directly holds
with τj = 1, because kgj k∞ ≤ TV(gj ) + kgj kQ . Then (39) and (40) easily follow from the
entropy estimates in Lemmas 19 and 20.
20

Our second result provides a sharper rate than in Theorem 3, applicable (but not limited)
to Sobolev and bounded variation spaces, provided that the following conditions hold. For
P∞
gj ∈ Gj , assume that gj (·) can be written as
ℓ=1 θjℓ ujℓ (·) for certain coefficients θjℓ and

basis functions ujℓ (·) on a set Ω. In addition, for certain positive constants C5,1 , C5,2 , C5,3 ,
0 < τj < 1, and 0 < wnj ≤ 1, assume that for all 1 ≤ j ≤ p,
sup

P k

max
k≥1

Pℓj0

2
ℓ=1 ujℓ (x)/k

P

: x ∈ Ω, k ≥ ℓj0 ≤ C5,1 ,

2 1/τj
ℓj,k−1 <ℓ≤ℓjk θjℓ ℓjk

2 −2
ℓ=1 θjℓ wnj

(44)

−1
≤ C5,2 (kgj kF,j + wnj
kgj kQ )2 ,

(45)

−1
kgj kQ )2 ,
≤ C5,2 (kgj kF,j + wnj

(46)

with ℓjk = ⌈(2k /wnj )2τj ⌉ for k ≥ 0 and ℓj,−1 = 0, and for all 1 ≤ j ≤ p and k ≥ 0,
n P
P
2
= 1 ≤ C5,3 .
sup k ℓj,k−1 <ℓ≤ℓjk θjℓ ujℓ k2Q : ℓj,k−1 <ℓ≤ℓjk θjℓ

(47)

Theorem 4. Suppose that (44), (45), (46) and (47) hold as above, and maxj=1,...,p {e2/(1−τj ) +
−τ

2wnj j } ≤ n. Then for any 0 < ǫ′ < 1 (for example, ǫ′ = ǫ), inequality (20) holds with π = ǫ′ 2
and φn > 0 such that
(

γ̃nj
φn = O(1) max
max
j (1 − τj )λnj
j

p

2 log(np/ǫ′ )
γ̃nj
log(np/ǫ′ )
+ max
j
λnj
(1 − τj )2 λ2nj

)

,

−τ

where γ̃nj = n−1/2 wnj j and O(1) depends only on {C5,1 , C5,2 , C5,3 }.
m

Remark 11. Let Gj be a Sobolev space Wrj j with rj ≥ 1, mj ≥ 1, and (rj ∧ 2)mj > 1 or a

bounded variation space V mj with rj = 1 and mj > 1 (excluding mj = 1) on [0, 1]. Condition

(44) holds for commonly used Fourier, wavelet and spline bases in L2 . For any L2 orthonormal
bases {ujℓ , ℓ ≥ 1}, condition (46) follows from Assumption 9 when C5,2 ≥ ̺−1
0 , and condition
(47) is also satisfied under an additional assumption that the average marginal density of
(j)

{Xi

: i = 1, . . . , n} is bounded from above by C5,3 for all j. In the proof of Proposition 5

we verify (44) and (45) for suitable wavelet bases with τj = 1/{2mj + 1 − 2/(rj ∧ 2)}, which
m

j
satisfies τj < 1 because (rj ∧ 2)mj > 1. In fact, Gj is allowed to be a Besov space Brj ,∞
, which

m

contains Wrj j for rj ≥ 1 and V mj for rj = 1 (e.g., DeVore & Lorentz 1993).

Remark 12. The convergence rate of φn in Theorem 4 is no slower than (42) in Theorem 3
if 1 ≤ rj ≤ 2 and (1 − τj )−1 {log(n)/n}1/2 = O(γ̃nj ), the latter of which is valid whenever τj
−τ /2

is bounded away from 1 and γ̃nj = n−1/2 wnj j

21

is of a slower polynomial order than n−1/2 .

However, Theorem 4 requires an additional side condition (47) along with the requirement of
τj < 1, which excludes for example the bounded variation space V 1 on [0, 1]. See Equations
(52) and (53) for implications of these rates when used in Assumption 6.

3.4

Results with Sobolev and bounded variation spaces

We combine the results in Section 3.2 and 3.3 (with ǫ′ = ǫ) to deduce a number of concrete
results on the performance of ĝ. For simplicity, consider a fully homogeneous situation where
each class Gj is a Sobolev space Wrm0 0 for some constants r0 ≥ 1 and m0 ≥ 1 or a bounded

variation space V m0 for r0 = 1 and m0 ≥ 1 on [0, 1]. Let β0 = 1/m0 . By Remark 9, if

r0 > β0 , then Assumptions 4 and 8 are satisfied such that ψnj (δ) = B0∗ δ1−β0 /2 and ψnj,∞ (z, δ) =
O(1)B0∗ z 1−β0 /2 for z > 0 and 0 < δ ≤ 1 under Assumption 9 (non-vanishing marginal densities),

where B0∗ > 0 is a constant depending on ̺0 among others. On the other hand, by Remark 10,

if r0 = β0 = 1, then Assumptions 4 and 8 are satisfied such that ψnj (δ) = B0∗ δ1/2 and
ψnj,∞ (z, δ) = O(log1/2 (n))B0∗ z 1/2 for z > 0 and 0 < δ ≤ 1, even when Assumption 9 does not
hold. That is, Γn in Theorem 3 reduces to
Γn = O(1) if r0 > β0 or O(log1/2 (n)) if r0 = β0 = 1.
We present our results in three cases, where the underlying function g ∗ =

(48)
Pp

∗
j=1 gj

is assumed

to satisfy (2) with q = 1, q = 0, or 0 < q < 1. As discussed in Section 1, the parameter set (2)
decouples sparsity and smoothness, inducing sparsity at different levels through an Lq ball in
k · kQ norm for 0 ≤ q ≤ 1, while only enforcing smoothness through an L1 ball in k · kF norm

on the components (g1∗ , . . . , gp∗ ).

The first result deals with the case q = 1 for the parameter set (2).
Proposition 3. Assume that (1) holds and kg ∗ kF,1 ≤ C1 MF and kg ∗ kQ,1 ≤ C1 M1 for MF > 0
and M1 > 0, possibly depending on (n, p). Let wnj = 1 and γnj = γn∗ (1) ≍ n−1/2 by (28)–(29).

Suppose that Assumptions 1 and 9 hold, and log(p/ǫ) = o(n). Then for sufficiently large n,
independently of (MF , M1 ), and any A0 > (1 + η0 )/(1 − η0 ), we have with probability at least
1 − 2ǫ,
p
kĝ − g ∗ k2n + A1 Rn∗ (ĝ − g ∗ ) ≤ O(1)C12 (MF + M1 ) log(p/ǫ)/n,

22

where O(1) depends only on (B0∗ , A0 , η0 , ̺0 ). Moreover, we have
1
kĝ − g∗ k2Q + A1 Rn∗ (ĝ − g ∗ )
2
n
o
p
≤ O(1)C12 (MF2 + M12 ) n−1/2 Γn + log(p/ǫ)/n ,

with probability at least 1 − 2ǫ, where Γn is from (48) and O(1) depends only on (B0∗ , A0 , η0 , ̺0 )
and (C2 , C3 , C4 ) as in Theorem 3. If r0 = β0 = 1, then the results are valid even when
Assumption 9 and hence ̺0 are removed.
Remark 13 (Comparison with existing results). Proposition 3 leads to the slow rate {log(p)/n}1/2
under L1 -ball sparsity in k·kQ norm, as previously obtained for additive regression with Sobolev
Hilbert spaces in Ravikumar et al. (2009), except in the case where r0 = β0 = 1, that is, each
class Gj is W11 or V 1 . In the latter case, Proposition 3 shows that the convergence rate is

{log(np)/n}1/2 for out-of-sample prediction, but remains {log(p)/n}1/2 for in-sample predic-

tion. Previously, only the slower rate, {log(np)/n}1/2 , was obtained for in-sample prediction

in additive regression with the bounded variation space V 1 by Petersen et al. (2016).
The second result deals with the case q = 0 for the parameter set (2).

Proposition 4. Assume that (1) holds and kg∗ kF,1 ≤ C1 MF and kg∗ kQ,0 ≤ M0 for MF > 0
and M0 > 0, possibly depending on (n, p). By (28)–(29), let
(

1/2 )
−1
2
log(p/ǫ)
,
wnj = wn∗ (0) = max B0∗ 2+β0 n 2+β0 ,
n


− β 0 


4
−1
2
log(p/ǫ)
γnj = γn∗ (0) = min B0∗ 2+β0 n 2+β0 , B0∗ n−1/2
.


n

Suppose that Assumptions 1, 5, and 9 hold with 0 < η0 < (ξ0∗ − 1)/(ξ0∗ + 1) and S = {1 ≤ j ≤

p : kgj∗ kQ > C0∗ λnj } for some constant C0∗ > 0, and
n

Γn wn∗ (0)−(1−β0 /2)τ0 γn∗ (0) + wn∗ (0)−τ0

p

o
log(p/ǫ)/n (1 + MF + M0 ) = o(1),

(49)

where τ0 = 1/(2/β0 + 1 − 2/r0 ). Then for sufficiently large n, depending on (MF , M0 ) only
through the convergence rate in (49), and any A0 > A(ξ0∗ , η0 ), we have

n −1
o2
p
Dn∗ (ĝ, g∗ ) ≤ O(1)C12 (MF + M0 ) n 2+β0 + log(p/ǫ)/n ,

(50)

with probability at least 1 − 2ǫ, where O(1) depends only on (B0∗ , A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 , ̺0 ). If
r0 = β0 = 1, then the results are valid even when Assumption 9 and hence ̺0 are removed.
23

Condition (49) is based on Theorem 3 for convergence of empirical norms. By Remark 12,
a weaker condition can be obtained using Theorem 4 when 1 ≤ r0 ≤ 2 and τ0 < 1 (that is,
r0 > β0 ). It is interesting to note that (49) reduces to (51) below in the case r0 = β0 = 1.
Proposition 5. Proposition 4 is also valid with (49) replaced by the weaker condition
o
n
p
wn∗ (0)−τ0 log(np/ǫ)/n (1 + MF + M0 ) = o(1),
(j)

(51)
(j)

in the case where 1 ≤ r0 ≤ 2, r0 > β0 , and the average marginal density of (X1 , . . . , Xn ) is

bounded from above for all j.
Remark 14 (Comparison with existing results). Propositions 4 and 5 yield the fast rate
−2

n 2+β0 + log(p)/n under L0 -ball sparsity in k · kQ norm. Previously, the same rate was obtained
for high-dimensional additive regression only with reproducing kernel Hilbert spaces (including
the Sobolev space W2m ) by Koltchinskii & Yuan (2010) and Raskutti et al. (2012), but under
more restrictive conditions. They studied hybrid penalized estimation procedures, which involve additional constraints such that the Hilbert norms of (g1 , . . . , gp ) are bounded by known
constants when minimizing a penalized criterion. Moreover, Koltchinskii & Yuan (2010) assumed a constant bound on the sup-norm of possible g∗ , whereas Raskutti et al. (2012) assumed
(1)

(p)

the independence of the covariates (Xi , . . . , Xi ) for each i. These restrictions were relaxed
in subsequent work by Suzuki & Sugiyama (2013), but only explicitly under the assumption
that the noises εi are uniformly bounded by a constant. Moreover, our condition (49) is much
weaker than related ones in Suzuki & Sugiyama (2013), as discussed in Remarks 15 and 16
below. See also Remark 8 for a discussion about the relationship between our results and the
seemingly faster rate in Suzuki & Sugiyama (2013).
Remark 15. To justify Assumptions 6(i)–(ii) on convergence of empirical norms, our rate
condition (49) is much weaker than previous ones used. If each class Gj is a Sobolev Hilbert
space (r0 = 2), then τ0 = β0 /2 and (49) becomes
o
n
p
2
n1/2 wn∗ (0)β0 /4 γn∗ (0)2 + γn∗ (0) log(p/ǫ) (1 + MF + M0 ) = o(1).

(52)

Moreover, by Proposition 5, condition (49) can be weakened to (51), that is,
p
γn∗ (0) log(np/ǫ)(1 + MF + M0 ) = o(1),

(53)
(j)

(j)

under an additional condition that the average marginal density of (X1 , . . . , Xn ) is bounded
from above for all j. Either condition (52) or (53) is much weaker than those in related analysis
24

with reproducing kernel Hilbert spaces. In fact, techniques based on the contraction inequality
(Ledoux & Talagrand 1991) as used in Meier et al. (2009) and Koltchinskii & Yuan (2010),
lead to a rate condition such as
n1/2 {γn2 (0) + νn2 }(1 + MF + M0 ) = o(1),
2

(54)

−1

where γn (0) = B0∗ 2+β0 n 2+β0 and νn = {log(p/ǫ)/n}1/2 . This amounts to condition (6) assumed
in Suzuki & Sugiyama (2013), in addition to the requirement n−1/2 (log p) ≤ 1. But condition

(54) is even stronger than the following condition:
o
n
2
n1/2 γn (0)2+β0 /4 + γn (0)νn (1 + MF + M0 ) = o(1),

(55)

2

because Γn γn (0)2+β0 /4 + γn (0)νn ≪ γn2 (0) + νn2 if either γn (0) ≫ νn or γn (0) ≪ νn . Condition
(55) implies (52) and (53), as we explain in the next remark.
Remark 16. Our rate condition (49) is in general weaker than the corresponding condition
with (wn∗ (0), γn∗ (0)) replaced by (wn (0), γn (0)), that is,
o
n
Γn γn (0)1−(1−β0 /2)τ0 + γn (0)−τ0 νn (1 + MF + M0 ) = o(1),

(56)

This demonstrates the advantage of using the more careful choices (wn∗ (0), γn∗ (0)) and also
explains why (55) implies (52) in Remark 15. In fact, if γn (0) ≥ νn then (49) and (56) are

identical to each other. On the other hand, if γn (0) < νn , then wn∗ (0) = νn > γn (0) and
wn∗ (0)−(1−β0 /2)τ0 γn∗ (0) = B0∗ n−1/2 wn∗ (0)−(1−β0 /2)τ0 −β0 /2 < γn (0)1−(1−β0 /2)τ0 . This also shows
that if γn (0) ≪ νn , then (49) is much weaker than (56). For illustration, if r0 = 2 and
hence τ0 = β0 /2, then (56) or equivalently (55) requires at least γn (0)−β0 /2 νn = o(1), that is,
−2

(log p)n 2+β0 = o(1), and (54) requires at least n1/2 νn2 = o(1), that is, log(p)n−1/2 = o(1). In
contrast, the corresponding requirement for (49), wn∗ (0)−β0 /2 νn = o(1), is automatically valid
as long as νn = o(1), that is, log(p)n−1 = o(1).
The following result deals with the case 0 < q < 1 for the parameter set (2).
Proposition 6. Assume that (1) holds and kg∗ kF,1 ≤ C1 MF and kg∗ kQ,q ≤ C1q Mq for 0 <

q < 1, Mq > 0, and MF > 0, possibly depending on (n, p). Let wnj = wn∗ (q) and γnj = γn∗ (q)

by (28)–(29). Suppose that Assumptions 1, 7, and 9 hold with 0 < η0 < (ξ0∗ − 1)/(ξ0∗ + 1) and
S = {1 ≤ j ≤ p : kgj∗ kQ > C0∗ λnj } for some constant C0∗ > 0, log(p/ǫ) = o(n), and
n

o
Γn wn∗ (q)−(1−β0 /2)τ0 γn∗ (q)1−q + wn∗ (q)−τ0 νn1−q (1 + MF + Mq ) ≤ η4 ,
25

(57)

for some constant η4 > 0, where νn = {log(p/ǫ)/n}1/2 . Then for sufficiently large n, independently of (MF , Mq ), and any A0 > A(ξ0∗ , η0 ), we have

n
o2−q
p
−1
Dn∗ (ĝ, g ∗ ) ≤ O(1)C12 (MF + Mq ) n 2+β0 (1−q) + log(p/ǫ)/n
,

with probability at least 1 − 2ǫ, where O(1) depends only on (q, B0∗ , A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 , ̺0 , η4 ) and
(C2 , C3 , C4 ) as in Theorem 3. If r0 = β0 = 1, then the results are valid even when Assumption 9
and hence ̺0 are removed.
Similarly as in Propositions 4 and 5, condition (57) can be weakened as follows when
1 ≤ r0 ≤ 2 and τ0 < 1 (that is, r0 > β0 ). It should also be noted that (57) is equivalent to

(58) below (with different η4 in the two equations) in the case r0 = β0 = 1, because γn∗ (q) with

q < 1 is of a slower polynomial order than n−1/2 and hence {log(n)/n}1/2 γn∗ (q)−1 = o(1).
Proposition 7. Proposition 6 is also valid with (49) replaced by the weaker condition
n

o
wn∗ (q)−τ0 (log(np/ǫ)/n)(1−q)/2 (1 + MF + M0 ) ≤ η4 ,

(58)

for some constant η4 > 0, in the case where 1 ≤ r0 ≤ 2, r0 > β0 , and the average marginal
(j)

(j)

density of (X1 , . . . , Xn ) is bounded from above for all j.
Remark 17. Propositions 6 and 7 yield, under Lq -ball sparsity in k · kQ norm, a convergence
rate interpolating the slow and fast rates smoothly from q = 1 to q = 0, similarly as in fixed
designs (Section 3.1). However, the rate condition (57) involved does always exhibit a smooth
transition to those for the slow and fast rates. In the extreme case q = 1, condition (57) with
q = 1 cannot be satisfied when M1 is unbounded or when M1 is bounded but Γn is unbounded
with r0 = β0 = 1. In contrast, Proposition 3 allows for unbounded M1 and the case r0 = β0 = 1.
This difference is caused by the need to justify Assumption 6(ii) with q 6= 1. In the extreme
case q = 0, condition (57) with q = 0 also differ drastically from (49) in Proposition 4. As seen
from the proof of Corollary 7, this difference arises because Assumption 6(ii) can be justified
by exploiting the fact that z q → ∞ as z → ∞ for q > 0 (but not q = 0).
For illustration, Table 1 gives the convergence rates from Propositions 3–6 in the simple
situation where (MF , Mq ) are bounded from above, independently of (n, p). The rate conditions
(49) and (57) are easily seen to hold in all cases except that (49) is not satisfied for q = 0
when r0 = β0 = 1 but νn 6= o(γn (0)). In this case, we show in the following result that the

convergence rate {γn (0) + νn }2 can still be achieved, but with the tuning parameters (wnj , γnj )
26

Table 1: Convergence rates for out-of-sample prediction under parameter set (2) with (MF , Mq )
bounded from above
r0 > β0
0≤q≤1
scale
adaptive
rate

yes
{γn (q) + νn }2−q
−1

r0 = β0 = 1
q=1

0<q<1

yes
p
log(n)/n + νn

yes

q=0
νn = o(γn (0))

otherwise

yes

no

{γn (q) + νn }2−q

Note: γn (q) ≍ n 2+β0 (1−q) and νn = {log(p/ǫ)/n}1/2 . Scale-adaptiveness means the convergence rate is
achieved with (wnj , γnj ) chosen independently of (MF , Mq ).

chosen suitably depending on the upper bound of (MF , Mq ). This is in contrast with the other
cases in Table 1 where the convergence rates are achieved by our penalized estimators in a
scale-adaptive manner: (wnj , γnj ) = (wn∗ (q), γn∗ (q)) are chosen independently of (MF , Mq ) or
their upper bound.
Proposition 8. Assume that r0 = β0 = 1, and MF and M0 are bounded from above by a
constant M > 0. Suppose that the conditions of Proposition 4 are satisfied except with (49)
and Assumption 9 removed, and Assumption 7 holds instead of Assumption 5. Let ĝ ′ be the
−β0 /2 ∗
γn (0)

′ = K
′
estimator with (wnj , γnj ) replaced by wnj
= K0 wn∗ (0) and γnj
0

for K0 > 0.

Then K0 can be chosen, depending on M but independently of (n, p), such that for sufficiently
large n, depending on M , and any A0 > A(ξ0∗ , η0 ), we have
n −1
o2
p
Dn∗ (ĝ ′ , g ∗ ) ≤ O(1)C12 (MF + M0 ) n 2+β0 + + log(p/ǫ)/n ,

with probability at least 1 − 2ǫ, where O(1) depends only on (M , B0∗ , A∗0 , C0∗ , ξ0∗ , κ∗0 , η0 ) and
(C2 , C3 , C4 ) as in Theorem 3.

4

Discussion

For additive regression with high-dimensional data, we have established new convergence results on the predictive performance of penalized estimation when each component function can
be a Sobolev space or a bounded variation space. A number of open problems remain to be
fully investigated. First, our results provide minimax upper bounds for estimation when the
27

component functions are restricted within an L1 ball in k · kF,j semi-norm and an Lq ball in
k · kQ norm. It is desirable to study whether these rates would match minimax lower bounds.
Second, while the penalized estimators have been shown under certain conditions to be adaptive to the sizes of L1 (k · kF ) and Lq (k · kQ ) balls for fixed q, we are currently investigating
adaptive estimation over such balls with varying q simultaneously. Finally, it is interesting to
study variable selection and inference about component functions for high-dimensional additive
regression, in addition to predictive performance studied here.

References
Bellec, P.C. and Tsybakov, A.B. (2016) Bounds on the prediction error of penalized least
squares estimators with convex penalty. Festschrift in Honor of Valentin Konakov, to
appear.
Bickel, P., Ritov, Y., and Tsybakov, A.B. (2009) Simultaneous analysis of Lasso and Dantzig
selector, Annals of Statistics, 37, 1705–1732.
Bunea, F., Tsybakov, A.B., and Wegkamp, M. (2007) Sparsity oracle inequalities for the
Lasso, Electronic Journal of Statistics, 1, 169–194.
DeVore, R. A. and Lorentz, G.G. (1993) Constructive Approximation, Springer: New York,
NY.
Greenshtein, E. and Ritov, Y. (2004) Persistency in high-dimensional linear predictor selection
and the virtue of over-parametrization, Bernoulli 10, 971–988.
Gu, C. (2002) Smoothing Spline ANOVA Models, Springer: New York, NY.
Hastie, T. and Tibshirani, R. (1990) Generalized Additive Models, Chapman & Hall: New
York, NY.
Huang, J., Horowitz, J.L., and Wei, P. (2010) Variable selection in nonparametric additive
models, Annals of Statistics, 38, 2282–2313.
Kim, S.-J., Koh, K., Boyd, S., and Gorinevsky, D. (2009) ℓ1 trend filtering, SIAM Review 51,
339–360.
Koltchinskii, V. and Yuan, M. (2010) Sparsity in multiple kernel learning, Annals of Statistics,
38, 3660–3695.
28

Ledoux, M. and Talagrand, M. (1991) Probability in Banach Spaces: Isoperimetry and Processes, Springer: Berlin.
Lin, Y. and Zhang, H.H. (2006) Component selection and smoothing in multivariate nonparametric regression, Annals of Statistics, 34, 2272–2297
Lorentz, G.G., Golitschek, M.v. and Makovoz, Y. (1996) Constructive Approximation: Advanced Problems, Springer: New York, NY.
Mammen, E. and van de Geer, S. (1997) Locally adaptive regression splines, Annals of Statistics, 25, 387–413.
Meier, L., van de Geer, S., and Buhlmann, P. (2009) High-dimensional additive modeling,
Annals of Statistics, 37, 3779–3821.
Negahban, S.N., Ravikumar, P., Wainwright, M.J., and Yu, B. (2012) A unified framework
for high-dimensional analysis of M-estimators with decomposable regularizers, Statistical
Science, 27, 538–557.
Nirenberg, L. (1966) An extended interpolation inequality, Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, 20, 733–737.
Petersen, A., Witten, D., and Simon, N. (2016) Fused Lasso additive model, Journal of
Computational and Graphical Statistics, 25, 1005–1025.
Raskutti, G., Wainwright, M.J., and Yu, B. (2012) Minimax-optimal rates for sparse additive models over kernel classes via convex programming, Journal of Machine Learning
Research 13, 389–427.
Ravikumar, P., Liu, H., Lafferty, J., and Wasserman, L. (2009) SPAM: Sparse additive models,
Journal of the Royal Statistical Society, Series B, 71, 1009–1030.
Stone, C.J. (1982) Optimal global rates of convergence for nonparametric regression. Annals
of Statistics, 10, 1040–1053.
Stone, C.J. (1985) Additive regression and other nonparametric models. Annals of Statistics,
13, 689–705.

29

Suzuki, T. and Sugiyama, M. (2013) Fast learning rate of multiple kernel learning: Trade-off
between sparsity and smoothness, Annals of Statistics, 41, 1381–1405.
Tibshirani, R.J. (2014) Adaptive piecewise polynomial estimation via trend filtering, Annals
of Statistics, 42, 285–323.
van de Geer, S. (2000) Empirical Processes in M-Estimation, Cambridge University Press.
van der Vaart, A.W. and Wellner, J. (1996) Weak Convergence and Empirical Processes,
Springer: New York, NY.
Yuan, M. and Zhou, D.-X. (2016) Minimax optimal rates of estimation in high dimensional
additive models, Annals of Statistics, 44, 2564–2593.
Yang, Y. and Tokdar, S.T. (2015) Minimax-optimal nonparametric regression in high dimensions, Annals of Statistics, 43, 652–674.

30

Supplementary Material for “Penalized Estimation in
Additive Regression with High-Dimensional Data”
Zhiqiang Tan & Cun-Hui Zhang

S1

Proofs

S1.1

Proof of Proposition 2
(1)

(1)

Without loss of generality, assume that k = 1 and 0 ≤ X1 < . . . < Xn ≤ 1.
P
Consider the case m = 1. For any g = pj=1 gj with g1 ∈ V 1 , define g̃1 as a piecewise
(1)

(1)

(1)

(1)

(1)

constant function: g̃1 (z) = g1 (X1 ) for 0 ≤ z < X2 , g̃1 (z) = g1 (Xi ) for Xi ≤ z < Xi+1 ,
P
(1)
(1)
i = 2, . . . , n − 1, and g̃1 (z) = g1 (Xn ) for Xn ≤ z ≤ 1. Let g̃ = g̃1 + pj=2 gj . Then

g̃(Xi ) = g(Xi ) for i = 1, . . . , n, but TV(g̃1 ) ≤ TV(g1 ) and hence Rn (g̃) ≤ Rn (g), which implies
the desired result for m = 1.
Consider the case m = 2. For any g =
(1)

Pp

j=1 gj

(1)

with g1 ∈ V 2 , define g̃1 such that g̃1 (Xi ) =
(1)

(1)

(1)

g1 (Xi ), i = 1, . . . , n, and g̃1 (z) is linear in the intervals [0, X2 ], [Xi , Xi+1 ], i = 2, . . . , n −
Pn−1
(1)
(1)
2, and [Xn−1 , 1]. Then TV(g̃1 ) =
i=1 |bi+1 − bi |, where bi is the slope of g̃1 between
(1)

(1)

(1)

(1)

[Xi , Xi+1 ]. On the other hand, by the mean-value theorem, there exists zi ∈ [Xi , Xi+1 ] such
P
Pn−1
(1)
(1)
that g1 (zi ) = bi for i = 1, . . . , n − 1. Then TV(g1 ) ≥ i=1
|bi+1 − bi |. Let g̃ = g̃1 + pj=2 gj .
Then g̃(Xi ) = g(Xi ) for i = 1, . . . , n, but Rn (g̃) ≤ Rn (g), which implies the desired result for

m = 2.

S1.2

Proofs of Theorem 1 and corollaries

We split the proof of Theorem 1 and Corollary 1 into five lemmas. The first one provides a
probability inequality controlling the magnitude of hε, hj in , in terms of the semi-norm khj kF,j
and the norm khj kn for all hj ∈ Gj with a single j.
Lemma 1. For fixed j ∈ {1, . . . , p}, let
Anj = ∪hj ∈Gj {|hε, hj in |/C1 > γnj,twnj khj kF,j + γnj,tkhj kn } ,
where γnj,t = γnj +

p

t/n for t > 0, γnj = n−1/2 ψnj (wnj )/wnj , and wnj ∈ (0, 1]. Under

Assumptions 1 and 2, we have
P (Anj ) ≤ exp(−t).
1

Proof. In the event Anj , we renormalize hj by letting fj = hj /(khj kF,j + khj kn /wnj ). Then
kfj kF,j + kfj kn /wnj = 1 and hence fj ∈ Gj (wnj ). By Lemma 12 with F1 = Gj (wnj ) and
δ = wnj , we have for t > 0,
(
P (Anj ) ≤ P
=P

(

sup

fj ∈Gj (wnj )

sup

fj ∈Gj (wnj )

|hε, fj in |/C1 > γnj,t wnj

)

|hε, fj in |/C1 > n−1/2 ψnj (wnj ) + wnj

p

)

t/n

≤ exp(−t).


By Lemma 1 and the union bound, we obtain a probability inequality controlling the magnitude of hε, hj in for hj ∈ Gj simultaneously over j = 1, . . . , p.
Lemma 2. For each j ∈ {1, . . . , p}, let
Anj = ∪hj ∈Gj {|hε, hj in | > λnj wnj khj kF,j + λnj khj kn } ,
where λnj /C1 = γnj + {log(p/ǫ)/n}1/2 . Under Assumptions 1 and 2, we have
P (∪pj=1 Anj ) ≤ ǫ.
Proof. By Lemma 1 with t = log(p/ǫ), we have for j = 1, . . . , p,
P (Anj ) ≤ exp(−t) =

ǫ
.
p

Applying the union bound yields the desired inequality.



If g ∗ ∈ G, then Kn (ĝ) ≤ Kn (g∗ ) directly gives the basic inequality:
1
kĝ − g ∗ k2n + A0 Rn (ĝ) ≤ hε, ĝ − g ∗ in + A0 Rn (g∗ ).
2

(S1)

By exploiting the convexity of the regularizer Rn (·), we provide a refinement of the basic
inequality (S1), which relates the estimation error of ĝ to that of any additive function ḡ ∈ G
and the corresponding regularization Rn (ḡ).
Lemma 3. The fact that ĝ is a minimizer of Kn (g) implies that for any function ḡ(x) =
Pp
(j)
j=1 ḡj (x ) ∈ G,
1
1
kĝ − g ∗ k2n + kĝ − ḡk2n + A0 Rn (ĝ)
2
2
1
≤ kḡ − g ∗ k2n + hε, ĝ − ḡin + A0 Rn (ḡ).
2
2

(S2)

Proof. For any t ∈ (0, 1], the fact that Kn (ĝ) ≤ Kn ((1 − t)ĝ + tḡ) implies

t2
kĝ − ḡk2n + Rn (ĝ) ≤ hY − ((1 − t)ĝ + tḡ), t(ĝ − ḡ)in + Rn ((1 − t)ĝ + tḡ)
2
≤ hy − ((1 − t)ĝ + tḡ), t(ĝ − ḡ)in + (1 − t)Rn (ĝ) + tRn (ḡ),

by similar calculation leading to the basic inequality (S1) and by the convexity of Rn (·):
Rn ((1 − t)ĝ + tḡ) ≤ (1 − t)Rn (ĝ) + tRn (ḡ). Using Y = g∗ + ε, simple manipulation of the
preceding inequality shows that for any t ∈ (0, 1],
t
hĝ − g∗ , ĝ − ḡin − kĝ − ḡk2n + Rn (ĝ) ≤ hε, ĝ − ḡin + Rn (ḡ),
2
which reduces to
1
1−t
1
kĝ − g ∗ k2n +
kĝ − ḡk2n + Rn (ĝ) ≤ kḡ − g∗ k2n + hε, ĝ − ḡin + Rn (ḡ)
2
2
2
by the fact that 2hĝ − g∗ , ĝ − ḡin = kĝ − g ∗ k2n + kĝ − ḡk2n − kḡ − g∗ k2n . Letting t ց 0 yields the
desired inequality (S2).



From Lemma 3, we obtain an upper bound of the estimation error of ĝ when the magnitudes
of hε, ĝj − ḡj in , j = 1, . . . , p, are controlled by Lemma 2.
Lemma 4. Let An = ∪pj=1 Anj with hj = ĝj − ḡj in Lemma 2. In the event Acn , we have for
any subset S ⊂ {1, 2, . . . , p},
1
1
kĝ − g ∗ k2n + kĝ − ḡk2n + (A0 − 1)Rn (ĝ − ḡ)
2
2
X
λnj kĝj − ḡj kn ,
≤ ∆n (ḡ, S) + 2A0
j∈S

where


p
X
X
1
∆n (ḡ, S) = kḡ − g∗ k2n + 2A0 
ρnj kḡj kF,j +
λnj kḡj kn  .
2
c
j=1

j∈S

Proof. By the refined basic inequality (S2), we have in the event Acn ,
1
1
kĝ − g ∗ k2n + kĝ − ḡk2n + A0 Rn (ĝ)
2
2
1
∗ 2
≤ kḡ − g kn + Rn (ĝ − ḡ) + A0 Rn (ḡ).
2
Applying to the preceding inequality the triangle inequalities,
kĝj kF,j ≥ kĝj − ḡj kF,j − kḡj kF,j ,

j = 1, . . . , p,

kĝj kn ≥ kĝj − ḡj kn − kḡj kn ,

j ∈ S c,

kĝj kn ≥ kḡj kn − kĝj − ḡj kn ,

j ∈ S,

3

(S3)

and rearranging the result leads directly to (S3).



Taking S = ∅ in (S3) yields (13) in Corollary 1. In general, we derive implications of (S3)
by invoking the compatibility condition (Assumption 3).
Lemma 5. Suppose that Assumption 3 holds. If A0 > (ξ0 + 1)/(ξ0 − 1), then (S3) implies
(12) in Theorem 1.
Proof. For the subset S used in Assumption 3, write
1
1
Zn = kĝ − g ∗ k2n + kĝ − ḡk2n ,
2
2
p
X
X
ρnj kĝj − ḡj kF,j +
λnj kĝj − ḡj kn ,
Tn1 =

Tn2 =

j∈S c

j=1

X
j∈S

λnj kĝj − ḡj kn .

Inequality (S3) can be expressed as
Zn + (A0 − 1)(Tn1 + Tn2 ) ≤ ∆n (ḡ, S) + 2A0 Tn2 ,
which leads to two possible cases: either
ξ1 {Zn + (A0 − 1)(Tn1 + Tn2 )} ≤ ∆n (ḡ, S),

(S4)

or (1 − ξ1 ){Zn + (A0 − 1)(Tn1 + Tn2 )} ≤ 2A0 Tn2 , that is,
Zn + (A0 − 1)(Tn1 + Tn2 ) ≤

2A0
Tn2 = (ξ0 + 1)(A0 − 1)Tn2 = ξ2 Tn2 ,
1 − ξ1

(S5)

where ξ1 = 1 − 2A0 /{(ξ0 + 1)(A0 − 1)} ∈ (0, 1] because A0 > (ξ0 + 1)/(ξ0 − 1). If (S5) holds,
then Tn1 ≤ ξ0 Tn2 , which, by Assumption 3 with fj = ĝj − ḡj , implies
Tn2


1/2
X

λ2nj  kĝ − ḡkn .
≤ κ−1
0

(S6)

j∈S

Combining (S5) and (S6) and using kĝ − ḡk2n /2 ≤ Zn yields


X

λ2nj  .
Zn + (A0 − 1)(Tn1 + Tn2 ) ≤ 2ξ22 κ−2
0

(S7)

j∈S

Therefore, inequality (S3), through (S4) and (S7), implies




Zn + (A0 − 1)(Tn1 + Tn2 ) ≤ ξ1−1 ∆n (ḡ, S) + 2ξ22 κ−2
0
4

X
j∈S



λ2nj  .


Finally, combining Lemmas 2, 4 and 5 completes the proof of Theorem 1.
P
λ2nj and j∈S c λnj kḡj kn
Pp
2−q
q
> C0 λnj }. First, because
j=1 λnj kḡj kn ≥

Proof of Corollary 2. The result follows from upper bounds of
by the definition S = {1 ≤ j ≤ p : kḡj kn
P
2−q
+ q q
j∈S λnj (C0 ) λnj , we have
X

λ2nj

j∈S

≤

(C0+ )−q

p
X
j=1

P

j∈S

2−q
λnj
kḡj kqn ,

(S8)

where for z ≥ 0, (z + )q = z q if q > 0 or = 1 if q = 0. Second, because
Pp
1−q kḡ kq , we have
j n
j=1 λnj (C0 λnj )
X

j∈S c

λnj kḡj kn ≤ C01−q

p
X
j=1

P

j∈S c

2−q
λnj
kḡj kqn .

λnj kḡj kn ≤

(S9)

Inserting (S8) and (S9) into (12) yields the desired inequality.



Proof of Corollary 3. The result follows directly from Corollary 2, because λ2−q
=
nj
C12−q {γn (q) + νn }2−q and ρnj = C1 {γn (q) + νn }γn1−q (q) ≤ C1 {γn (q) + νn }2−q , where νn =
{log(p/ǫ)/n}1/2 .

S1.3



Proofs of Theorem 2 and corollaries

Write hj = ĝj − ḡj and h = ĝ − ḡ and, for the subset S used in Assumption 5,
1
1
Zn = kĝ − g ∗ k2n + khk2n ,
2
2
p
X
X
∗
ρnj khj kF,j +
λnj khj kQ ,
Tn1
=

∗
Tn2
=

j∈S c

j=1

X
j∈S

λnj khj kQ .

∗ and T ∗ are
Compared with the definitions in Section S1.2, Zn is the same as before, and Tn1
n2

similar to Tn1 and Tn2 , but with khj kQ used instead of khj kn .
Let
Ωn1 =




sup
 g∈G

kgk2n − kgk2Q
Rn∗2 (g)

≤ φn




.



Then P (Ωn1 ) ≥ 1 − π. In the event Ωn1 , we have by Assumption 6(i),
max sup

j=1,...,p gj ∈Gj

|kgj kn − kgj kQ |
≤ λn,p+1 φn1/2 ≤ η0 .
wnj kgj kF,j + kgj kQ
5

(S10)

By direct calculation, (S10) implies that if kgj kF,j + kgj kn /wnj ≤ 1 then kgj kF,j + kgj kQ /wnj ≤

(1 − η0 )−1 and hence (S10) implies that

H(u, Gj (wnj ), k · kn ) ≤ H((1 − η0 )u, Gj∗ (wnj ), k · kn ),
and ψnj (wnj ) satisfying (17) also satisfies (11) for δ = wnj . Let Ωn2 = Acn in Lemma 4. Then
conditionally on X1:n = (X1 , . . . , Xn ) for which Ωn1 occurs, we have P (Ωn2 |X1:n ) ≥ 1 − ǫ by
Lemma 2. Therefore, P (Ωn1 ∩ Ωn2 ) ≥ (1 − ǫ)(1 − π) ≥ 1 − ǫ − π.
In the event Ωn2 , recall that (S3) holds, that is,
Zn + (A0 − 1)Rn (h) ≤ ∆n (ḡ, S) + 2A0

X
j∈S

λnj khj kn .

(S11)

In the event Ωn1 ∩ Ωn2 , simple manipulation of (S11) using (S10) shows that
Zn + A1 Rn∗ (h) ≤ ∆∗n (ḡ, S) + 2A0

X
j∈S

λnj khj kQ ,

(S12)

where A1 = (A0 − 1) − η0 (A0 + 1) > 0 because A0 > (1 + η0 )/(1 − η0 ). In the following, we
restrict to the event Ωn1 ∩ Ωn2 with probability at least 1 − ǫ − π.
Proof of Corollary 4. Taking S = ∅ in (S12) yields (24), that is,
Zn + A1 Rn∗ (h) ≤ ∆∗n (ḡ, g∗ , ∅).
−2 ∗2
∗
∗
2
2
∗2
2
∗
As a result, Rn∗ (h) ≤ A−1
1 ∆n (ḡ, g , ∅) and hence khkQ ≤ khkn +φn Rn (h) ≤ khkn +φn A1 ∆n (ḡ, g , ∅).

Inequality (25) then follows from (24).



Proof of Theorem 2. Inequality (S12) can be expressed as
∗
∗
∗
Zn + A1 (Tn1
+ Tn2
) ≤ ∆∗n (ḡ, g ∗ , S) + 2A0 Tn2
,

which leads to two possible cases: either
∗
∗
ξ1∗ {Zn + A1 (Tn1
+ Tn2
)} ≤ ∆∗n (ḡ, S),

(S13)

∗ + T ∗ )} ≤ 2A T ∗ , that is,
or (1 − ξ1∗ ){Zn + A1 (Tn1
0 n2
n2
∗
∗
Zn + A1 (Tn1
+ Tn2
)≤

2A0 ∗
∗
∗
T = (ξ0∗ + 1)A1 Tn2
= ξ2∗ Tn2
,
1 − ξ1∗ n2

(S14)

where ξ1∗ = 1 − 2A0 /{(ξ0∗ + 1)A1 } ∈ (0, 1] because A0 > {ξ0∗ + 1 + η0 (ξ0∗ + 1)}/{ξ0∗ − 1 −
∗ ≤ ξ ∗ T ∗ , which, by the theoretical compatibility condition
η0 (ξ0∗ + 1)}. If (S14) holds, then Tn1
0 n2

6

(Assumption 5) with fj = ĝj − ḡj , implies

1/2
X
∗

λ2nj  khkQ
Tn2
≤ κ∗−1
0

(S15)

j∈S


1/2
n
o
X
∗
∗

λ2nj 
≤ κ∗−1
khkn + φ1/2
n (Tn1 + Tn2 )
0

(S16)

j∈S

P
2
2 2
By Assumption 6(ii), we have φn ξ2∗2 κ∗−2
0 ( j∈S λnj ) ≤ η1 A1 . Combining this fact, (S14) and
(S16) and simple manipulation yields

1/2

X
∗
∗
λ2nj  khkn ,
Zn + (1 − η1 )A1 (Tn1
+ Tn2
) ≤ ξ2∗ κ0∗−1 
j∈S

which, by the fact that khk2n /2 ≤ Zn , implies



∗
∗

Zn + (1 − η1 )A1 (Tn1
+ Tn2
) ≤ 2ξ2∗2 κ∗−2
0

X
j∈S



λ2nj  .

(S17)

Therefore, inequality (S12), through (S13) and (S17), implies (22):



∗
∗

Zn + (1 − η1 )A1 (Tn1
+ Tn2
) ≤ ξ1∗−1 ∆∗n (ḡ, S) + 2ξ2∗2 κ∗−2
0

X
j∈S



λ2nj  .

To demonstrate (23), we return to the two possible cases, (S13) or (S14). On one hand, if
∗ + T ∗ ) is also bounded from above by the right hand side
(S13) holds, then A1 Rn∗ (h) = A1 (Tn1
n2

of (S13) and hence
khk2Q ≤ khk2n + φn Rn∗2 (h) ≤ khk2n +

φn ∗−2 ∗2
ξ ∆n (ḡ, g∗ , S).
A21 1

(S18)

Simple manipulation of (S13) using (S18) yields
1
φn ∗−2 ∗2
1
∗
∗
kĝ − g∗ k2n + khk2Q + A1 (Tn1
+ Tn2
) ≤ ξ1∗−1 ∆∗n (ḡ, S) +
ξ ∆n (ḡ, g ∗ , S).
2
2
2A21 1
On the other hand, combining (S14) and (S15) yields

∗
∗

Zn + A1 (Tn1
+ Tn2
) ≤ ξ2∗ κ∗−1
0

X
j∈S

1/2

λ2nj 

khkQ .

(S19)

(S20)

∗ + T ∗ ) is also bounded from above by the right hand side of
As a result, A1 Rn∗ (h) = A1 (Tn1
n2

(S20) and hence by Assumption 6(ii),
khk2Q ≤ khk2n + φn Rn∗2 (h)


X
1
φ
n

λ2nj  khk2Q ≤ khk2n + η12 khk2Q .
≤ khk2n + 2 ξ2∗2 κ∗−2
0
2
A1
j∈S

7

(S21)

Simple manipulation of (S20) using (S21) yields
1
1−
kĝ − g ∗ k2n +
2
2

η12

1/2

X
∗
∗

λ2nj  khkQ ,
khk2Q + A1 (Tn1
+ Tn2
) ≤ ξ2∗ κ∗−1
0
j∈S

which, when squared on both sides, implies
− η12

1
1
kĝ − g ∗ k2n +
2
2

∗
∗
khk2Q + A1 (Tn1
+ Tn2
)≤

2
1 − η12



X

λ2nj  .
ξ2∗2 κ∗−2
0

(S22)

j∈S

Therefore, inequality (S12), through (S19) and (S22), implies

1 − η12
1
∗
∗
kĝ − g∗ k2n +
khk2Q + A1 (Tn1
+ Tn2
)
2
2


X
2
φn ∗−2 ∗2

≤ ξ1∗−1 ∆∗n (ḡ, S) +
λ2nj  +
ξ2∗2 κ∗−2
ξ1 ∆n (ḡ, g ∗ , S),
0
2
2
1 − η1
2A1
j∈S

which yields (23) after divided by 1 − η12 on both sides.



Proof of Corollary 5. We use the following upper bounds, obtained from (S8) and (S9)
with S = {1 ≤ j ≤ p : kḡj k > C0∗ λnj },
X
j∈S

λ2nj

≤

(C0∗+ )−q

p
X
j=1

q
λ2−q
nj kḡj kQ ,

(S23)

and
X

j∈S c

λnj kḡj kQ ≤ C0∗1−q

p
X
j=1

q
λ2−q
nj kḡj kQ .

(S24)

Equations (21) and (26) together imply φn ∆∗n (ḡ, , S) = O(1) + φn kḡ − g∗ k2n /2. Inserting this

into (23) and applying (S23) and (S24) yields the high-probability result about Dn∗ (ĝ, ḡ). The
in-probability result follows by combining the facts that ǫ → 0, kḡ − g∗ k2n = Op (1)kḡ − g∗ k2Q by

the Markov inequality, and kĝ − g ∗ k2Q ≤ 2(kĝ − ḡk2Q + kḡ − g ∗ k2Q ) by the triangle inequality. 
Proof of Corollary 6. First, we show
wn∗ (q) ≤ {γn∗ (q) + νn }1−q .

(S25)

In fact, if γn (q) ≥ νn , then γn∗ (q) = γn (q) and wn∗ (q) = γn (q)1−q ≤ {γn∗ (q) + νn }1−q . If

γn (q) < νn , then wn∗ (q) = νn1−q ≤ {γn∗ (q) + νn }1−q . By (S23), (S24), and (S25), inequality (30)

implies that for any constants 0 < η1 < 1 and η2 > 0, (21) and (26) are satisfied for sufficiently
2−q
large n. The desired result follows from Corollary 5 with ḡ = g ∗ , because λ2−q
{γn∗ (q) +
nj = C1

8

νn }2−q ≤ C12−q {γn (q)+ νn }2−q and, by (S25), ρnj = C1 wn∗ (q){γn∗ (q)+ νn } ≤ C1 {γn (q)+ νn }2−q .

Proof of Corollary 7. For a constant 0 < η1 < 1, we choose and fix C0∗ ′ ≥ C0∗ sufficiently
large, depending on q > 0, such that
∗′ q 2
(ξ0∗ + 1)2 κ∗−2
0 η3 ≤ (C0 ) η1 .

Let S ′ = {1 ≤ j ≤ p : kgj∗ kQ > C0∗ ′ λnj }. Then (21) is satisfied with S replaced by S ′ , due
to (33), (S23), and the definition λnj = C1 {γn∗ (q) + νn }. Similarly, (26) is satisfied with S

replaced by S ′ for η2 = M q + (C0∗ ′ )1−q M q , by (S24) and simple manipulation. By Remark 7,
Assumption 7 implies Assumption 5 and remains valid when S is replaced by S ′ ⊂ S. The
desired result follows from Corollary 5 with ḡ = g ∗ .



Proof of Corollary 8. The proof is similar to that of Corollary 6. First, we show
wn† (q)MF ≤ {γn† (q) + νn }1−q Mq .

(S26)

In fact, if γn′ (q) ≥ νn , then γn† (q) = γn′ (q) and wn† (q)MF = γn′ (q)1−q Mq ≤ {γn† (q) + νn }1−q Mq .
If γn (q) < νn , then wn† (q)MF = νn1−q Mq ≤ {γn† (q) + νn }1−q Mq . Then (36) implies that for

any constants 0 < η1 < 1 and η2 > 0, (21) and (26) are satisfied for sufficiently large n.
2−q
†
The desired result follows from Corollary 5 with ḡ = g ∗ , because λ2−q
nj Mq = C1 {γn (q) +

νn }2−q Mq ≤ C12−q {γn′ (q) + νn }2−q Mq and, by (S26), ρnj MF = C1 wn† (q){γn† (q) + νn }MF ≤
C1 {γn′ (q) + νn }2−q Mq .

S1.4



Proof of Theorem 3

We split the proof into three lemmas. First, we provide maximal inequalities on convergence
of empirical inner products in functional classes with polynomial entropies.
Lemma 6. Let F1 and F2 be two functional classes such that
sup kfj kQ ≤ δj ,

fj ∈Fj

sup kfj k∞ ≤ bj ,

j = 1, 2.

fj ∈Fj

Suppose that for some 0 < βj < 2 and Bnj,∞ > 0, condition (S45) holds with
ψn,∞ (z, Fj ) = Bnj,∞ z 1−βj /2 ,

9

j = 1, 2.

(S27)

Then we have
(
E

sup

f1 ∈F1 ,f2 ∈F2

|hf1 , f2 in − hf1 , f2 iQ | /C2

)





2C2 ψn,∞ (b1 , F1 ) 1−β1 /2
2C2 ψn,∞ (b2 , F2 ) β1 /2 ψn,∞ (b2 , F1 )
√
√
√
≤ 2 δ1 +
δ2 +
n
n
n

1−β2 /2 
β2 /2
2C2 ψn,∞ (b2 , F2 )
ψn,∞ (b1 , F2 )
2C2 ψn,∞ (b1 , F1 )
√
√
√
+ 2 δ2 +
.
δ1 +
n
n
n

(S28)

Moreover, we have for any t > 0,
sup
f1 ∈F1 ,f2 ∈F2

≤E

(

|hf1 , f2 in − hf1 , f2 iQ | /C3

sup

f1 ∈F1 ,f2 ∈F2

)

|hf1 , f2 in − hf1 , f2 iQ |

+ δ1 b2

r

t
t
+ b1 b2 ,
n
n

(S29)

with probability at least 1 − e−t .
Proof. For any function f1 , f1′ ∈ F1 and f2 , f2′ ∈ F2 , we have by triangle inequalities,
kf1 f2 − f1′ f2′ kn ≤ δ̂2 kf1 − f1′ kn,∞ + δ̂1 kf2 − f2′ kn,∞ .
As a result, we have for u > 0,
H(u, F1 × F2 , k · kn ) ≤ H{u/(2δ̂2 ), F1 , k · kn,∞ } + H{u/(2δ̂1 ), F2 , k · kn,∞ },

(S30)

where F1 × F2 = {f1 f2 : f1 ∈ F1 , f2 ∈ F2 }.
By symmetrization inequality (van der Vaart & Wellner 1996),
)
(
(
E

sup

f1 ∈F1 ,f2 ∈F2

|hf1 , f2 in − hf1 , f2 iQ |

≤ 2E

sup

f1 ∈F1 ,f2 ∈F2

)

|hσ, f1 f2 in | .

Let δ̂12 = supf1 ∈F1 ,f2 ∈F2 kf1 f2 kn ≤ min(δ̂1 b2 , δ̂2 b1 ). By Dudley’s inequality (Lemma 13) conditionally on X1:n = (X1 , . . . , Xn ), we have
)
(
E

sup

f1 ∈F1 ,f2 ∈F2

|hσ, f1 f2 in | X1:n

/C2 ≤ E

(Z

δ̂12
0

H 1/2 (u, F1 × F2 , k · kn ) du X1:n

)

.

Taking expectations over X1:n , we have by (S30), (S45), and definition of H ∗ (),
)
(
E

sup

f1 ∈F1 ,f2 ∈F2

≤E

"Z

δ̂1 b2
0

|hf1 , f2 in − hf1 , f2 iQ | /C2

H ∗1/2 {u/(2δ̂2 ), F1 , k · kn,∞ } du +

Z

δ̂2 b1

0

h
i
≤ E δ̂2 ψn,∞ (δ̂1 b2 /δ̂2 , F1 ) + δ̂1 ψn,∞ (δ̂2 b1 /δ̂1 , F2 ) .
10

H ∗1/2 {u/(2δ̂1 ), F2 , k · kn,∞ } du

#
(S31)

By (S27) and the Hölder inequality, we have
n
o


1−β /2
β /2 1−β /2
E δ̂2 ψn,∞ (δ̂1 b2 /δ̂2 , F1 ) ≤ Bn1,∞ b2 1 E δ̂2 1 δ̂1 1
1−β1 /2

≤ Bn1,∞ b2

1−β1 /2

E β1 /2 (δ̂2 )E 1−β1 /2 (δ̂1 ) ≤ Bn1,∞ b2

E β1 /4 (δ̂22 )E (2−β1 )/4 (δ̂12 ),

and similarly
n
o
1−β /2
E δ̂1 ψn,∞ (δ̂2 b1 /δ̂1 , F2 ) ≤ Bn2,∞ b1 2 E β2 /4 (δ̂12 )E (2−β2 )/4 (δ̂22 ).
Then inequality (S28) follows from (S31) and Lemma 16. Moreover, inequality (S29) follows
from Talagrand’s inequality (Lemma 14) because kf1 f2 kQ ≤ δ1 b2 and kf1 f2 k∞ ≤ b1 b2 for
f1 ∈ F1 and f2 ∈ F2 .



By application of Lemma 6, we obtain the following result on uniform convergence of empirical inner products under conditions (39), (40), and (41).
Lemma 7. Suppose the conditions of Theorem 3 are satisfied for j = 1, 2 and p = 2. Let
Fj = Gj∗ (wnj ) for j = 1, 2. Then we have
(
E

sup

f1 ∈F1 ,f2 ∈F2

|hf1 , f2 in − hf1 , f2 iQ | /C2

)



β τ /2
β τ /2
≤ 2(1 + 2C2 C4 )C4 n1/2 Γn wn1 wn2 γn1 γ̃n2 wn21 2 + γn2 γ̃n1 wn12 1
.

−τ

where 0 < τj ≤ (2/βj −1)−1 and C4 = maxj=1,2 C4,j from condition (41), and γ̃nj = n−1/2 wnj j .
Moreover, we have for any t > 0,
sup
f1 ∈F1 ,f2 ∈F2

≤E

(

|hf1 , f2 in − hf1 , f2 iQ | /C3

sup

f1 ∈F1 ,f2 ∈F2

)

|hf1 , f2 in − hf1 , f2 iQ |



+ wn1 wn2 C4 t1/2 γ̃n2 + C42 tγ̃n1 γ̃n2 ,

with probability at least 1 − e−t .
Proof. For fj ∈ Fj with wnj ≤ 1, we have kfj kF,j ≤ 1 and kfj kQ ≤ wnj , and hence
1−τj

kfj k∞ ≤ C4 wnj

by (41). Let ψn,∞ (·, Fj ) = ψnj,∞ (·, wnj ) from (40), that is, in the form (S27)
1−τ

such that (S45) is satisfied. We apply Lemma 7 with δj = wnj and bj = C4 wnj j . By simple
manipulation, we have
1−τ

n−1/2 ψn,∞ (bj , Fj ) = n−1/2 ψnj,∞ (C4 wnj j , wnj )
−β /2

1−(1−βj /2)τj

≤ C4 Bnj,∞n−1/2 wnj j wnj

11

1−βj /2

≤ C4 Γn γnj wnj

≤ C4 wnj ,

where C4 ≥ 1 is used in the second step, Bnj,∞ ≤ Γn Bnj and (1 − βj /2)τj ≤ βj /2 in the
−β /2

third step, and γnj ≤ wnj and Γn γnj wnj j
inequality (S28) yields
(
E

sup

f1 ∈F1 ,f2 ∈F2

1−βj /2

≤ Γn γnj

|hf1 , f2 in − hf1 , f2 iQ | /C2
1−β1 /2

≤ 2(1 + 2C2 C4 )n−1/2 wn1

≤ 1 in the fourth step. Therefore,
)

β /2

1−τ2
wn21 ψn1,∞ (C4 wn2
, wn1 )

1−β2 /2

+ 2(1 + 2C2 C4 )n−1/2 wn2

1−β1 /2

≤ 2(1 + 2C2 C4 )C4 n−1/2 wn1

β /2

1−τ1
wn12 ψn2,∞ (C4 wn1
, wn2 )

1−β2 /2

+ 2(1 + 2C2 C4 )C4 n−1/2 wn2

−τ +β1 τ2 /2

Bn1,∞ wn2 wn2 2

−τ +β2 τ1 /2

Bn2,∞ wn1 wn1 1

,

which leads to the first desired inequality because Bnj,∞ ≤ Γn Bnj . Moreover, simple manipulation gives
δ1 b2
b1 b2

r

t
1−τ2
= C4 wn1 wn2
n

r

t
= C4 t1/2 wn1 wn2 γ̃n2 ,
n

t
1−τ1 1−τ2 t
= C42 wn1
wn2
= C42 twn1 γ̃n1 wn2 γ̃n2 .
n
n

The second desired inequality follows from (S29).



The following result concludes the proof of Theorem 3.
Lemma 8. In the setting of Theorem 3, let
βp+1 τj /2

γ̃nj wnj
γnj
max
φn = 4C2 C3 (1 + 2C2 C4 )C4 n Γn max
j
j λnj
λnj
p
2 log(p/ǫ′ )
′
√
γ̃nj
log(p/ǫ )
γ̃nj
+ 2C3 C4 max
max
+ 2C3 C42 max
,
j λnj
j
j
λnj
λ2nj
1/2

−τ

where γ̃nj = n−1/2 wnj j and βp+1 = minj=1,...,p βj . Then




kgk2n − kgk2Q
2
>
φ
≤ ǫ′ .
P sup
n
∗2

 g∈G
Rn (g)

∗ (g ) = kg k
∗
Proof. For j = 1, . . . , p, let rnj
j
j F,j + kgj kQ /wnj and fj = gj /rj (gj ). Then kfj kF,j +
P
kfj kQ /wnj = 1 and hence fj ∈ Gj∗ (wnj ). By the decomposition kgk2n = j,k hgj , gk in , kgk2Q =
P
j,k hgj , gk iQ , and the triangle inequality, we have

kgk2n − kgk2Q ≤

=

X
j,k

X
j,k

|hgj , gk in − hgj , gk iQ |

∗
∗
(gk ) |hfj , fk in − hfj , fk iQ | .
rnj
(gj )rnk

12

Because R∗2 (g) =



sup
P

⊂

(

g=

P

∗
∗
j,k rnj (gj )rnk (gk )wnj λnj wnk λnk ,

kgk2n − kgk2Q
R∗2 (g)

p
j=1 gj

[
j,k

> φn





sup

fj ∈G ∗ (wnj ),fk ∈G ∗ (wnk )

=
g=

we have

[

Pp

j=1

gj

n

o
kgk2n − kgk2Q > φn R∗2 (g)

|hfj , fk in − hfj , fk iQ | > φn wnj λnj wnk λnk

)

By Lemma 7 with F1 = Gj∗ (wnj ), F2 = Gk∗ (wnk ), and t = log(p2 /ǫ′ 2 ), we have with probability
no greater than ǫ′ 2 /p2 ,
sup
fj ∈G ∗ (wnj ),fk ∈G ∗ (wnk )

|hfj , fk in − hfj , fk iQ | /C3

> 4C2 (1 + 2C2 C4 )C4 n1/2 Γn Wn wnj γnj wnk γnk
q
2
1/2
+ C4 n Vn wnj wnk γnk log(p2 /ǫ′ 2 )/n + C42 Vn2 log(p2 /ǫ′ )wnj γnj wnk γnk .
Therefore, we have by the definition of φn ,
P

sup
fj ∈G ∗ (wnj ),fk ∈G ∗ (wnk )

|hfj , fk in − hfj , fk iQ | > φn wnj λnj wnk λnk

The desired result follows from the union bound.

S1.5

!

≤

ǫ′ 2
.
p2


Proofs of Propositions 3, 4, 6, and 8

Denote wnj = wn,p+1 and γnj = γn,p+1 for j = 1, . . . , p. By direct calculation, (42) implies
that for any 0 ≤ q ≤ 1,

n

2−q
1−q
φn (γn,p+1 + νn )2−q ≤ O(1) n1/2 Γn Wn γn,p+1
+ n1/2 Vn min γn,p+1 νn1−q , γn,p+1
νn
o

2−q
2
(S32)
+ nVn2 min γn,p+1
νn2−q , γn,p+1
νn2 ,
where
β /2−τ

0
0
Vn = wn,p+1
,

β /2−τ0 +β0 τ0 /2

0
Wn = wn,p+1

.

(S33)

We verify that the technical conditions hold as needed for Theorem 3, with wnj = wn∗ (q)
and γnj = γn∗ (q) for 0 ≤ q ≤ 1. First, we verify γnj ≤ wnj for sufficiently large n. It suffices

to show that γn∗ (q) ≤ wn∗ (q) whenever γn (q) ≤ 1 and νn ≤ 1. In fact, if γn (q) ≥ νn , then

wn∗ (q) = γn (q)1−q and γn∗ (q) = γn (q) ≤ γn (q)1−q provided γn (q) ≤ 1. If γn (q) < νn , then
−(1−q)β0 /2

wn∗ (q) = νn1−q and γn∗ (q) = B0∗ n−1/2 νn

≤ νn ≤ νn1−q provided νn ≤ 1. Moreover, we

13

have Γn γn∗ (q)1−β0 /2 ≤ 1 for sufficiently large n, because Γn is no greater than O(log1/2 (n)) and

γn∗ (q)1−β0 /2 ≤ γn (q)1−β0 /2 decreases polynomially in n−1 for 0 < β0 < 2.

Proof of Proposition 3. For wnj = 1 and γnj = γn∗ (1) ≍ n−1/2 , inequality (S32) with
q = 0 and νn = o(1) gives
o
n
φn {γn∗ (1) + νn }2 ≤ O(1) n1/2 Γn γn∗2 (1) + n1/2 γn∗ (1)νn + nγn∗2 (1)νn2


= O(1) n−1/2 Γn + νn ,

Assumption 6(i) holds because Γn is no greater than O(log1/2 (n)). Inserting the above inequality into (25) in Corollary 4 yields the out-of-sample prediction result. The in-sample prediction
result follows directly from Corollary 4.



Proof of Proposition 4. For γnj = γn∗ (0), inequality (S32) with q = 0 gives
o
n
φn {γn∗ (0) + νn }2 ≤ O(1) n1/2 Γn Wn γn∗2 (0) + n1/2 Vn γn∗ (0)νn + nVn2 γn∗2 (0)νn2 .

(S34)

By (S33) and γn∗ (0) = B0∗ n−1/2 wn∗ (0)−β0 /2 , simple manipulation gives
n1/2 Vn γn∗ (0)νn = B0∗ wn∗ (0)−τ0 νn ,

(S35)

n1/2 Wn γn∗ (0)2 = B0∗ wn∗ (0)−(1−β0 /2)τ0 γn∗ (0).
Then (49) and (S34) directly imply that Assumption 6(i) holds for sufficiently large n and also
(30) holds. The desired result follows from Corollary 6 with q = 0.



Proof of Proposition 6. For γnj = γn∗ (q), inequality (S32) with q = 0 gives
o
n
φn {γn∗ (q) + νn }2 ≤ O(1) n1/2 Γn Wn γn∗2 (q) + n1/2 Vn γn∗ (q)νn + nVn2 γn∗2 (q)νn2 .

(S36)

By (S33) and γn∗ (q) = B0∗ n−1/2 wn∗ (q)−β0 /2 , simple manipulation gives
n1/2 Vn γn∗ (q)νn1−q = B0∗ wn∗ (q)−τ0 νn1−q ,

n1/2 Wn γn∗ (q)2−q = B0∗ wn∗ (q)−(1−β0 /2)τ0 γn∗ (q)1−q .
Then (57) and (S36) imply that Assumption 6(i) holds for sufficiently large n, along with the
fact that νn = o(1), γn (q) = o(1), and q > 0. Moreover, (57) and (S32) with γnj = γn∗ (q)
directly yield (33). The desired result follows from Corollary 7.
Proof of Proposition 8.



′
, Vn′ , Wn′ , etc., the corresponding quanDenote by γn,p+1

′ , γ ′ ). By (S33) and (S35) with τ = 1, we have n1/2 V ′ γ ′
tities based on (wnj
0
n n,p+1 νn =
nj

14

K0−1 (n1/2 Vn γn,p+1 νn ) and n1/2 Vn γn,p+1 νn = B0∗ min{νn γn−1 (0), 1} ≤ B0∗ . Moreover, we have
n1/2 Γn Wn′ γ ′ 2n,p+1 = o(1) for a constant K0 , because Wn′ = 1, Γn is no greater than O(log1/2 (n)),

and n1/2 γn2 (0) decreases polynomially in n−1 . For a constant 0 < η1 < 1, we choose and fix
K0 ≥ 1 sufficiently large, depending on M but independently of (n, p), such that Assump-

′ , γ ′ ), for sufficiently large n, due
tions 6(i)–(ii) are satisfied, with (wnj , γnj ) replaced by (wnj
nj
′ + ν ). Moreover, by (S25), ρ′ = λ′ w ′ ≤
to (S23), (S34), and the definition λ′nj = C1 (γnj
n
nj
nj nj
1−β0 /2

K0

1−β0 /2

λnj wnj ≤ K0

C1 {γn∗ (0)+νn }2 , which together with (S24) implies that (26) is satisβ /2

fied for some constant η2 > 0. Assumption 7 is also satisfied with C0∗ replaced by C0∗′ = C0∗ K0 0

and S replaced by {1 ≤ j ≤ p : kgj∗ kQ > C0∗′ λ′nj } ⊂ S for K0 ≥ 1 due to monotonicity in S for

′ , γ ′ ) because
the validity of Assumption 7 by Remark 7, and with (wnj , γnj ) replaced by (wnj
nj
′ ≥w
(18) after the modification implies (18) itself, with wnj
nj for K0 ≥ 1 and λnj constant in

j. The desired result follows from Corollary 5 with ḡ = g ∗ .

S1.6



Proof of Theorem 4

We use the non-commutative Bernstein inequality (Lemma 15) to prove Theorem 4. Suppose
that (X1 , . . . , Xn ) are independent variables in a set Ω. First, consider finite-dimensional
functional classes Fj with elements of the form
fj (x) = uTj (x)θj ,

∀ θj ∈ Rdj , j = 1, 2,

(S37)

where uj (x) is a vector of basis functions from Ω to Rdj , and θj is a coefficient vector. Let

Uj = {uj (X1 ), . . . , uj (Xn )}T , and Σjj ′ = E UjT Uj ′ /n ∈ Rdj ×dj′ . The population inner product

is hfj , fj′ iQ = θjT Σjj ′ θj ′ , j, j ′ = 1, 2. The difference between the sample and population inner
products can be written as
sup

fj , fj ′

kθj k=kθj ′ k=1

n

− fj , fj ′

Q

=

sup
kθj k=kθj ′ k=1

|θjT (UjT Uj ′ /n − Σjj ′ )θj′ |

= kUjT Uj ′ /n − Σjj ′ kS .
Lemma 9. Let fj be as in (S37). Assume that for a constant C5,1 ,
sup kuj (x)k2 ≤ C5,1 ℓj ,

x∈Ω

∀j = 1, 2.

Then for all t > 0,
kUjT Uj ′ /n − Σjj ′ kS >

q

r

(ℓj kΣj ′ j ′ kS ) ∨ (ℓj ′ kΣjj kS )

with probability at least 1 − (dj + dj ′ )e−t .
15

p
2C5,1 t
4t
+ C5,1 ℓj ℓj ′
n
3n

Let Mi = uj (Xi )uTj ′ (Xi ) − E{uj (Xi )uTj ′ (Xi )}. Because uj (Xi )uTj ′ (Xi ) is of rank
p
p
1, kMi kS ≤ 2 supx∈Ω {kuj (x)kkuTj ′ (x)k} ≤ 2C5,1 ℓj ℓj ′ . Hence we set s0 = 2C5,1 ℓj ℓj ′ in

Proof.

Lemma 15. Similarly, Wcol ≤ C5,1 ℓj ′ kΣjj kS because

E(Mi MiT ) ≤ E{uj (Xi )uTj ′ (Xi )uj ′ (Xi )uTj (Xi )} ≤ C5,1 ℓj ′ E{uj (Xi )uTj (Xi )},
and Wrow ≤ C5,1 ℓj kΣj ′ j ′ kS . Thus, (S44) gives the desired result.



Now consider functional classes Fj such that fj ∈ Fj admits an expansion
fj (·) =

∞
X

θjℓ ujℓ (·),

ℓ=1

where {ujℓ (·) : ℓ = 1, 2, . . .} are basis functions and {θjℓ : ℓ = 1, 2, . . .} are the associated
coefficients.
Lemma 10. Let 0 < τj < 1, 0 < wnj ≤ 1 and
n
P
P
2
≤ k−1/τj ∀ k ≥ (1/wnj )2τj ,
Bj = fj : k/4<ℓ≤k θjℓ
0≤ℓ1/τj w 2

nj

2
≤ wnj
θ2
<1 j,ℓ+1

o

Suppose that (44) and (47) hold with certain positive constants C5,1 , C5,3 . Then, for a certain
constant C5,4 depending on {C5,1 , C5,3 } only,
sup
fj ∈Bj ,fj ′ ∈Bj ′

hfj , fj ′ in − hfj , fj ′ iQ

q
h
−τ ′
−τ ′
−τ
−τ
≤ C5,4 wnj wnj ′ (µj wnj j + µj ′ wnj ′j )
µj + µj ′ + log(wnj j + wnj ′j ) + t /n
i

−τ ′
−τ ′
−τ
−τ
+ µj + µj ′ + log(wnj j + wnj ′j ) + t (µj wnj j )(µj ′ wnj ′j )/n

with at least probability 1 − e−t for all t > 0, where µj = 1/(1 − τj ).

Proof. Let ℓjk = ⌈(2k /wnj )2τj ⌉. We group the basis and coefficients as follows:
uj,Gjk (x) = (ujℓ (x), ℓ ∈ Gjk )T ,

θj,Gjk = (θjℓ , ℓ ∈ Gjk )T ,

k = 0, 1, . . .

where Gj0 = {1, . . . , ℓj0 } of size |Gj0 | = ℓj0 and Gjk = {ℓj,k−1 + 1, . . . , ℓjk } of size |Gjk | =

ℓjk − ℓj,k−1 ≤ (2k /wnj )2τj for k ≥ 1. Define θ̃j , a rescaled version of θj , by
−1
θj,Gjk .
θ̃j,Gjk = (θ̃jℓ , ℓ ∈ Gjk ) = 2k wnj

It follows directly from (45) and (46) that
kθ̃j,Gj,0 k2 ≤ 1,

−1/(2τj )

kθ̃j,Gjk krj ≤ (2k /wnj )/ℓjk
16

≤ 1 ∀ k ≥ 1, ∀ fj ∈ Bj .

Let Ujk = {uj,Gjk (X1 ), . . . , uj,Gjk (Xn )}T ∈ Rn×|Gjk | . We have
sup
fj ∈Bj ,fj ′ ∈Bj ′

=

hfj , fj ′ in − hfj , fj ′ iL2

sup
fj ∈Bj ,fj ′ ∈Bj ′

≤

max

k=0 ℓ=0

∞
∞ X
X



T
T
T
′
′
θj,G
U
U
/n
−
E
U
U
/n
θj ′ ,Gj′ ,ℓ
jk j ,ℓ
jk j ,ℓ
jk
T



T
T
Uj ′ ,ℓ /n
Uj ′ ,ℓ /n − E Ujk
Ujk

θ̃j,Gjk
k=0 ℓ=0
∞
∞ X
T
X
Uj ′ ,ℓ /n
Ujk

kθ̃j k∨kθ̃j ′ k≤1

≤ wnj wnj ′

∞ X
∞
X

k=0 ℓ=0

−1 ℓ −1
2k wnj
2 wnj ′

T
Uj ′ ,ℓ /n
− E Ujk

2k 2ℓ



θ̃j ′ ,Gj′ ,ℓ

.

(S38)

S

Let ak = 1/{(k + 1)(k + 2)}. By (44), supx∈Ω kuj,Gjk (x)k2 ≤ supx∈Ω

Pℓjk

2
ℓ=1 ujℓ (x)

≤ C5,1 ℓjk for

T
Ujk /nkS ≤ C5,3 . Because |Gjk | ≤ ℓj,k , it follows from Lemma 9 that
k ≥ 0. By (47), kEUjk
T
T
Uj ′ ,ℓ /nkS
Uj ′ ,ℓ /n − E Ujk
kUjk
q
log(ℓjk + ℓj ′ ,ℓ ) − log(ak aℓ ) + t 2C5,1 C5,3 (ℓjk ∨ ℓj ′ ,ℓ )/n
≤
p

+ log(ℓjk + ℓj ′ ,ℓ ) − log(ak aℓ ) + t (4/3)C5,1 ℓjk ℓj ′ ,ℓ /n

(S39)

with probability at least 1 − ak aℓ e−t for any fixed k ≥ 0 and ℓ ≥ 0. By the union bound and
P
the fact that ∞
k=0 ak = 1, inequality (S39) holds simultaneously for all k ≥ 0 and ℓ ≥ 0 with
probability at least 1 − e−t . Because ℓjk = ⌈(2k /wnj )2τj ⌉, we rewrite (S39) as

T
T
kUjk
Uj ′ ,ℓ /n − E Ujk
Uj ′ ,ℓ /nkS
q
h
−τ ′
−τ ′
−τ
−τ
k + ℓ + log(wnj j + wnj ′j ) + t /n
≤C5,4 (2τj k wnj j + 2τj′ ℓ wnj ′j )
i

−τ ′
−τ ′
−τ
−τ
+ k + ℓ + log(wnj j + wnj ′j ) + t (2τj k wnj j )(2τj′ ℓ wnj ′j )/n .

where C5,4 is a constant depending only on {C5,1 , C5,3 }. For any α ≥ 0,

P∞

k=0 k

(S40)
α 2−k(1−τj )

≤

Cα µα+1
, where Cα is a numerical constant and µj = 1/(1 − τj ). Using this fact and inserting
j
(S40) into (S38) yields the desired result.



Finally, the following result concludes the proof of Theorem 4.
Lemma 11. In the setting of Theorem 4, let
)
(
p
2
2 log(np/ǫ′ )µ2j γ̃nj
2 log(np/ǫ′ )
µj γ̃nj
max
+ max
,
φn = C5,2 C5,4 max
j
j
j
λnj
λnj
λ2nj

17

−τ

where γ̃nj = n−1/2 wnj j , µj = 1/(1−τj )−1 , and C5,4 is a constant depending only on {C5,1 , C5,3 }
as in Lemma 10. Then
P




sup
 g∈G

kgk2n − kgk2Q

Proof. Recall that ℓjk = ⌈(2k /wnj )2τj ⌉. For gj =
2
rnj
(gj )

X
ℓj0

=

> φn

Rn∗2 (g)

2
2
θjℓ
/wnj

ℓ=1



∨



P∞





ℓ=1 θjℓ ujℓ ,

max
k≥1

2

≤ ǫ′ .

X

define rnj (gj ) by
2 1/τj
θjℓ
ℓjk

ℓj,k−1 <ℓ≤ℓjk



.

Let fj = gj /rnj (gj ) and µj = 1/(1 − τj ). Then fj ∈ Bj as in Lemma 10 and
kgk2n
=

−

p X
p
X
j=1

Because

Pp

i=1 wnj λnj rnj (gj )




sup
 g∈G
⊂

[

j,j ′

kgk2Q

j ′ =1

≤

Rn∗2 (g)
sup

fj ∈Bj ,fj ′ ∈Bj ′

j=1 j ′ =1

hgj , gj ′ in − hgj , gj ′ iQ

rnj (gj )rnj ′ (gj ′ ) hfj , fj ′ in − hfj , fj ′ iQ .
1/2
j=1 C5,2 λnj (wnj kgj kF,j

Pp

kgk2n − kgk2Q
(

≤

p X
p
X

> φn

1/2

+ kgj kQ ) = C5,2 Rn∗ (g) by (45),





−1
φn wnj λnj wnj ′ λnj ′
|hfj , fk in − hfj , fk iQ | > C5,2

)

.

(S41)

−τ

By Lemma 10 with t = log(p2 /ǫ′ 2 ) and e2µj + 2wnj j ≤ n, we have
sup
fj ∈Bj ,fj ′ ∈Bj ′

hfj , fj ′ in − hfj , fj ′ iQ

q
h
−τ ′
−τ ′
−τ
−τ
≤ C5,4 wnj wnj ′ (µj wnj j + µj ′ wnj ′j )
µj + µj ′ + log(wnj j + wnj ′j ) + log(p2 /ǫ′ 2 ) /n
i

−τ ′
−τ ′
−τ
−τ
2
+ µj + µj ′ + log(wnj j + wnj ′j ) + log(p2 /ǫ′ ) (µj wnj j )(µj ′ wnj ′j )/n
n
o
−τ ′
−τ ′ p
−τ
−τ
≤ C5,4 wnj wnj ′ (µj wnj j + µj ′ wnj ′j ) 2 log(np/ǫ′ )/n + 2 log(p/ǫ′ )(µj wnj j )(µj ′ wnj ′j )/n ,

with probability at least 1 − ǫ′ 2 /p2 . By the definition of φn , we have
(
P

sup

fj ∈Bj ,fj ′ ∈Bj ′

hfj , fj ′ in − hfj , fj ′ iQ ≤

−1
C5,2
φn wnj wnj ′ λnj λnj ′

The conclusion follows from the union bound using (S41).

18

)

≥1−

ǫ′ 2
.
p2


S1.7

Proof of Proposition 5

Here we verify explicitly conditions of Theorem 4 for Sobolev spaces Wrmi i and bounded varia-

tion spaces V mi with ri = 1 on [0, 1] in the case of τj < 1, where τi = 1/(2mi +1−2/(ri ∧2)). Be-

cause conditions (44), (45), (46) and (47) depend on (mj , rj ) only through τj , we assume with(j)

out loss of generality 1 ≤ rj ≤ 2. When the average marginal density of {Xi

: i = 1, . . . , n}

is uniformly bounded away from 0 and ∞, the norms kgj kQ and kgj kL2 are equivalent, so that
condition (46) and (47) hold for any L2 -orthonormal bases {ujℓ : ℓ ≥ 1}. Let u0 (x) be a mother
R
R
wavelet with m vanishing moments, e.g., u0 (x) = 0 for |x| > c0 , u20 (x)dx = 1, xm u0 (x)dx =
√
0 for m = 0, . . . , maxj mj , and {u0,kℓ (x) = 2k u0 (2k (x − j)) : ℓ = 1, . . . , 2k , k = 0, 1, . . .} is
L2 -orthonormal. We shall identify {ujℓ : ℓ ≥ 1} as {u0,11 , u0,21 , u0,22 , u0,31 , . . .}. Because
#{ℓ : u0,kℓ (x) 6= 0} ≤ 2c0 k ∀x,
2k+1
X−1

k

u2jℓ (x)

=

ℓ=1

ℓ=2k

cause u0 has

u20,kℓ (x) ≤ 2c0 2k ku0 k∞ , ∀x,

P∞ P2k
(−m)
(x)
ℓ=1 θjkℓ u0,kℓ (x). Define u0
ℓ=1 θjℓ ujℓ (x) =
k=0
R
(m)
(−m+1)
(−m)
x
(x) = −∞ u0
(t)dt, and gj (x) = (d/dx)m gj (x). Beintegral of u0 , u0
R (m)
(m)
vanishing moments, u0 (x)dx = 0 for m = 0, . . . , maxj mj , so that u0 (x) = 0

so that (44) holds. Suppose gj (x) =
as the m-th

2
X

P∞

for |x| > c0 . Due to the orthonormality of the basis functions, for 1 ≤ ℓ ≤ 2k , we have
Z
Z
(m )
2mj k θjkℓ = 2mj k gj (x)u0,kℓ (x)dx = (−1)m gj j (x)u0,mj kℓ (x)dx
with u0,mkℓ (x) =
k −1
2X

mj k

2

θjℓ

rj

ℓ=2k−1

√

(−m)

2k u0

≤

k −1
2X

ℓ=2k−1

(2k (x − j)). By the Hölder inequality,

Z

(mj )

gj

(mj ) rj

≤ gj

Lr j

(x)

rj

u0,mj kℓ (x)

rj (1−2(1−/rj ))

dx u0,mj kℓ

(mj ) rj (1−2(1−/rj )) (k/2)rj (1−2(1−/rj ))

2c0 u0

2

∞

rj (2(1−1/rj ))
L2

(mj )

u0

L2

2rj (2(1−1/rj )) .

Because 2mj k−(k/2)(1−2(1−/rj )) = 2k(mj +1/2−1/rj ) = 2k/(2τj ) and 1 ≤ rj ≤ 2, we have
k −1
 2X

ℓ=2k−1

2
2k/τj θjℓ

1/2

≤

k −1
 2X

k/(2τj )

2

ℓ=2k−1

1/(2τj )

Because ℓjk

1/rj
(mj ) 2/rj −1

(mj )

≤ gj

θjℓ

rj

Lr j

(2c0 )1/rj u0

∞

(mj ) 2−2/rj

u0

L2

.

≥ 2k /wnj and ℓjk ≤ 1 + 22τj ℓj,k−1 with τj < 1, we have ℓjk ≤ 4ℓj,k−1 , so that

{ℓj,k−1 + 1, . . . , ℓj,k } involves at most three resolution levels. Thus, condition (45) follows from
19

the above inequality. For the bounded variation class, we have
Z
Z
(m −1)
mj k
mj k
m
2
θjkℓ = 2
gj (x)u0,kℓ (x)dx = (−1)
u0,mj kℓ (x)dgj j (x),
so that (45) follows from the same proof with rj = 1.

S2
S2.1

Technical tools
Sub-gaussian maximal inequalities

The following maximal inequality can be obtained from van de Geer (2000, Corollary 8.3), or
directly derived using Dudley’s inequality for sub-gaussian variables and Chernoff’s tail bound
(see Proposition 9.2, Bellec et al. 2016).
Lemma 12. For δ > 0, let F1 be a functional class such that supf1 ∈F1 kf1 kn ≤ δ, and
Z δ
H 1/2 (u, F1 , k · kn ) du.
(S42)
ψn (δ, F1 ) ≥
0

Let (ε1 , . . . , εn ) be independent variables. Under Assumption 1, we have for any t > 0,
)
(
p
−1/2
ψn (δ, F1 ) + δ t/n ≤ exp(−t),
P sup |hε, f1 in |/C1 > n
f1 ∈F1

where C1 = C1 (D0 , D1 ) > 0 is a constant, depending only on (D0 , D1 ).

S2.2

Dudley and Talagrand inequalities

The following inequalities are due to Dudley (1967) and Talagrand (1996).
Lemma 13. For δ > 0, let F1 be a functional class such that supf1 ∈F1 kf1 kn ≤ δ and (S42)
holds. Let (σ1 , . . . , σn ) be independent Rademacher variables, that is, P (σi = 1) = P (σi =
−1) = 1/2. Then for a universal constant C2 > 0,
)
(
E

sup |hσ, f1 in |/C2

f1 ∈F1

≤ n−1/2 ψ(δ, F1 ).

Lemma 14. For δ > 0 and b > 0, let (X1 , . . . , Xn ) be independent variables, and F be a
functional class such that supf ∈F kf kQ ≤ δ and supf ∈F kf k∞ ≤ b. Define
n

Zn = sup
f ∈F

1X
{f (Xi ) − Ef (Xi )} .
n
i=1

Then for a universal constant C3 > 0, we have
)
(
r
t
t
≤ exp(−t),
+b
P Zn /C3 > E(Zn ) + δ
n
n
20

t > 0.

S2.3

Non-commutative Bernstein inequality

We state the non-commutative Bernstein inequality (Troop, 2011) as follows.
Lemma 15. Let {Mi : i = 1, . . . , n} be independent random matrices in Rd1 ×d2 such that
E(Mi ) = 0 and P {kMi kS ≤ s0 } = 1, i = 1, . . . , n, for a constant s0 > 0, where k · kS denotes
P
P
the spectrum norm of a matrix. Let Σcol = ni=1 E(Mi MiT )/n and Σrow = ni=1 E(MiT Mi )/n.
Then, for all t > 0,

n
1X
P
Mi
n
i=1

>t
S



≤ (d1 + d2 ) exp




−nt2 /2
.
kΣcol kS ∨ kΣrow kS + s0 t/3

Consequently, for all t > 0,


n
p
p
1X
Mi > kΣcol kS ∨ kΣrow kS 2t/n + (s0 /3)2t/n ≤ (d1 + d2 )e−t .
P
n
S

(S43)

(S44)

i=1

S2.4

Convergence of empirical norms

For δ > 0 and b > 0, let F1 be a functional class such that
sup kf1 kQ ≤ δ,

f1 ∈F1

sup kf1 k∞ ≤ b,

f1 ∈F1

and let ψn,∞ (·, F1 ) be an upper envelope of the entropy integral:
Z z
H ∗ 1/2 (u/2, F1 , k · kn,∞ ) du,
ψn,∞ (z, F1 ) ≥

z > 0,

(S45)

0

where H ∗ (u, F1 , k · kn,∞ ) = sup(X (1) ,...,X (1) ) H(u, F1 , k · kn,∞ ). Let δ̂ = supf1 ∈F1 kf1 kn . The
1

n

following result can be obtained from Guedon et al. (2007) and, in its present form, van de
Geer (2014), Theorem 2.1.
Lemma 16. For the universal constant C2 in Lemma 13, we have
)
(
2
(b, F1 )
2δC2 ψn,∞ (b, F1 ) 4C22 ψn,∞
2
2
√
E sup kf1 kn − kf1 kQ ≤
.
+
n
n
f1 ∈F1
Moreover, we have
q

S2.5

E(δ̂2 ) ≤ δ +

2C2 ψn,∞ (b, F1 )
√
.
n

Metric entropies
m

For r ≥ 1 and m > 0 (possibly non-integral), let W r = {f : kf kLr + kf (m) kLr ≤ 1}. The
following result is taken from Theorem 5.2, Birman & Solomjak (1967).
21

Lemma 17. If rm > 1 and 1 ≤ q ≤ ∞, then
m

H(u, W r , k · kLq ) ≤ B1 u−1/m ,

u > 0,

where B1 = B1 (m, r) > 0 is a constant depending only on (m, r). If rm ≤ 1 and 1 ≤ q <
r/(1 − rm), then
m

H(u, W r , k · kLq ) ≤ B2 u−1/m ,

u > 0,

where B2 = B2 (m, r, q) > 0 is a constant depending only on (m, r, q).
For m ≥ 1, let V

m

= {f : kf kL1 + TV(f (m−1) ) ≤ 1}. The following result can be obtained

from Theorem 15.6.1, Lorentz et al. (1996), on the metric entropy of the ball {f : kf kLr +
[f ]Lip(m,Lr ) ≤ 1}, where [f ]Lip(m,Lr ) is a semi-norm in the Lipschitz space Lip(m, Lr ). By
Theorem 9.9.3, DeVore & Lorentz (1993), the space Lip(m, L1 ) is equivalent to V m , with

the semi-norm [f ]Lip(m,Lr ) equal to TV(f ), up to suitable modification of function values at
1

(countable) discontinuity points. However, it should be noted that the entropy of V endowed
with the norm k · kL∞ is infinite.
Lemma 18. If m ≥ 2 and 1 ≤ q ≤ ∞, then
m

H(u, V , k · kLq ) ≤ B3 u−1/m ,

u > 0,

where B3 = B3 (m) > 0 is a constant depending only on m. If 1 ≤ q < ∞, then
1

H(u, V , k · kLq ) ≤ B4 u−1 ,

u > 0,

where B4 = B4 (r) > 0 is a constant depending only on r.
By the continuity of functions in Wrm for m ≥ 1 and V m for m ≥ 2, the maximum entropies
of these spaces in k · kn,∞ and k · kn norms over all possible design points can be derived from
Lemmas 17 and 18.
Lemma 19. If rm > 1, then for B1 = B1 (m, r),
m

m

H ∗ (u, W r , k · kn ) ≤ H ∗ (u, W r , k · kn,∞ ) ≤ B1 u−1/m ,
m

u > 0,

m

and hence (S42) and (S45) hold with ψn (z, W r ) ≍ ψn,∞ (z, W r ) ≍ z 1−1/(2m) . If m ≥ 2, then
for B3 = B3 (m),
m

m

H ∗ (u, V , k · kn ) ≤ H ∗ (u, V , k · kn,∞ ) ≤ B3 u−1/m ,
m

m

u > 0,

and hence (S42) and (S45) hold with ψn (z, V ) ≍ ψn,∞ (z, V ) ≍ z 1−1/(2m) .
22

1

The maximum entropies of V over all possible design points can be obtained from Section
5, Mammen (1991) for the norm k · kn and Lemma 2.2, van de Geer (2000) for the norm
k · kn,∞ . In fact, the proof of van de Geer shows that for F the class of nondecreasing functions

f : [0, 1] → [0, 1], H ∗ (u, F, k · kn,∞ ) ≤ n log(n + u−1 ) if u ≤ n−1 or ≤ u−1 log(n + u−1 ) if

u > n−1 . But if u ≤ n−1 , then n log(n + u−1 ) ≤ n(log n + n−1 u−1 ) ≤ (1 + log n)u−1 . If

u > n−1 , then u−1 log(n + u−1 ) ≤ u−1 log(2n). Combining the two cases gives the stated result
1

1

about H ∗ (u, V , k · kn,∞ ), because each function in V can be expressed as a difference two
nondecreasing functions.
Lemma 20. For a universal constant B5 > 0, we have
1

1

H ∗ (u, W 1 , k · kn ) ≤ H ∗ (u, V , k · kn ) ≤ B5 u−1 ,
1

u > 0,

1

and hence (S42) holds with ψn (z, W 1 ) ≍ ψn (z, V ) ≍ z 1/2 . Moreover, for a universal constant
B6 > 0, we have
1

1

H ∗ (u, W 1 , k · kn,∞ ) ≤ H ∗ (u, V , k · kn,∞ ) ≤ B6
1

1 + log n
,
u

u > 0,

1

and hence (S45) holds with ψn,∞ (z, W 1 ) ≍ ψn,∞ (z, V ) ≍ (1 + log n)1/2 (z/2)1/2 .

S2.6

Interpolation inequalities

The following inequality (S46) can be derived from the Gagliardo-Nirenberg inequality for
Sobolev spaces (Theorem 1, Nirenberg 1966). Inequality (S47) can be shown by approximating
f ∈ V m by functions in W1m .
Lemma 21. For r ≥ 1 and m ≥ 1, we have for any f ∈ Wrm ,
oτ
n
kf k∞ ≤ (C4 /2) kf (m) kLr + kf kL2 kf k1−τ
L2 ,

(S46)

where τ = (2m + 1 − 2/r)−1 ≤ 1 and C4 = C4 (m, r) ≥ 1 is a constant depending only on (m, r).
In addition, we have for any f ∈ V m ,

oτ
n
kf k∞ ≤ (C4 /2) TV(f (m−1) ) + kf kL2 kf k1−τ
L2 .

(S47)

From this result, kf k∞ can be bounded in terms of kf kL2 and kf (m) kLr or TV(f (m−1) )

in a convenient manner. For f ∈ Wrm and 0 < δ ≤ 1, if kf kL2 ≤ δ and kf (m) kLr ≤ 1,

then kf k∞ ≤ C4 δ1−1/(2m+1−2/r) . Similarly, for f ∈ V m and 0 < δ ≤ 1, if kf kL2 ≤ δ and

TV(f (m−1) ) ≤ 1, then kf k∞ ≤ C4 δ1−1/(2m−1) .

23

References
Bellec, P.C., Lecue, G., Tsybakov, A.B. (2016) Slope meets Lasso: Improved oracle bounds
and optimality, arXiv:1605.08651.
Birman, M.S. and Solomjak, M.Z. (1967) Piecewise-polynomial approximations of functions
of the classes Wpα , Mathematics of the USSR–Sbornik, 2, 295–317.
Dudley, R.M. (1967) The sizes of compact subsets of Hilbert space and continuity of Gaussian
processes, Journal of Functional Analysis, 1, 290–330.
Guedon, O., Mendelson, S., Pajor, A., and Tomczak-Jaegermann, N. (2007) Subspaces and
orthogonal decompositions generated by bounded orthogonal systems, Positivity, 11,
269–283.
Mammen, E. (1991) Nonparametric regression under qualitative smoothness assumptions,
Annals of Statistics, 19, 741–759.
Talagrand, M. (1996) New concentration inequalities in product spaces. Inventiones Mathematicae 126, 505–563.
Tropp, J.A. (2011) Freedman’s inequality for matrix martingales, Electronic Communications
in Probability, 16, 262–270.
van de Geer, S. (2014) On the uniform convergence of empirical norms and inner products,
with application to causal inference, Electronic Journal of Statistics, 8, 543–574.

24

