Submitted to the Annals of Statistics
arXiv: 1607.01434

arXiv:1607.01434v3 [] 26 Jul 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE
FUNCTION COMBINATIONS INCLUDING NEURAL
NETWORKS
By Jason M. Klusowski and Andrew R. Barron
Yale University
Let f ⋆ be a function on Rd satisfying a spectral norm condition.
1/4
For various noise settings, we show that Ekfˆ − f ⋆ k2 ≤ vf ⋆ logn d
,
where n is the sample size and fˆ is either a penalized least squares
estimator or a greedily obtained version of such using linear combinations of ramp, sinusoidal, sigmoidal or other bounded Lipschitz ridge
functions. Our risk bound is effective even when the dimension d is
much larger than the available sample size. For settings where the dimension is larger than the square root of the sample size this quantity

1/2
is seen to improve the more familiar risk bound of vf ⋆ d log(n/d)
,
n
also investigated here.

1. Introduction. Functions f ⋆ in Rd are approximated using linear combinations of ridge functions with one layer of nonlinearities. These approximations are employed via functions of the form
(1.1)

fm (x) = fm (x, ζ) =

m
X
k=1

ck φ(ak · x + bk ),

which is parameterized by the vector ζ, consisting of ak in Rd , and bk , ck
in R for k = 1, . . . , m, where m ≥ 1 is the number of nonlinear terms.
The functions φ are allowed to be quite general. For example, they can be
bounded and Lipschitz, polynomials with certain controls on their degrees,
or bounded with jump discontinuities. It is useful to view the representation
(1.1) as
X
(1.2)
βh h(x),
h∈H

Primary 62J02, 62G08; secondary 68T05
Keywords and phrases: Nonparametric regression; nonlinear regression; neural networks; penalization; machine learning; high dimensional data analysis; learning theory;
generalization error; supervised learning; greedy algorithms; big data

1
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

2

where H is a library of candidate basis or activation functions of the form
h(x) = φ(θh · x) and the βh are non-negative, where all but finitely many
are zero.
We can reduce (1.1) to (1.2) as follows. Suppose the library is symmetric
H = −H and contains the zero function. Without loss of generality, we
may assume that the ck are non-negative by replacing the associated φ with
φ sgnck , that by assumption also belongs to H. One can assume the internal
parameters ak · x + bk take the form θk · x by appending a one to x and bk
to ak . Note that now x and θk are (d + 1)-dimensional.
Suppose P is an arbitrary probability measure on [−1, 1]d . Let
R k · k be the
L2 (P ) norm induced by the inner product h·, ·i. Define vf ⋆ ,s = Rd kωks1 f˜(ω)dω,
for s ≥ 0.R If f ⋆ has a bounded domain in [−1, 1]d and a Fourier representation
f ⋆ (x) = Rd eiω·x f˜(ω)dω with vf ⋆ ,1 < +∞, it is possible to use approximating functions of the form (1.1) with a single activation function φ. Such
activation functions φ can be be general bounded monotone functions.
The following result from [2] provides a useful starting point for approximating general functions f ⋆ by linear combinations of such objects. Suppose vf ⋆ ,1
is finite. Then by [2], there exists an artificial neural network of the form
(1.1) with φ(x) = sgn(x) with kak k1 = 1 and |bk | ≤ 1 such that
kf ⋆ − fm k2 ≤

4vf2 ⋆ ,1
m

.

If φ has right at left limits −1 and +1, respectively, the fact that φ(τ x) →
sgn(x) as τ → +∞ allows one to use somewhat arbitrary activation functions
as basis elements. It is natural to impose a restriction on the size of the
internal parameters and to also enjoy a certain degree of smoothness not
offered by step functions. Thus we consider the result in [10], which allows
one to approximate f ⋆ by linear combinations of ramp ridge functions (also
known as first order ridge splines or hinging hyper-planes) (x · α − t)+ =
max{0, x · α − t}, with kαk1 = 1, |t| ≤ 1. These functions are continuous and
Lipschitz. In the supplementary material Supplement A we refine a result
from [10]. For an arbitrary target function f ⋆ with vf ⋆ ,2 finite, there exists
an approximation of the form (1.1) activated by ridge ramp functions with
kak k = 1 and |bk | ≤ 1 such that
⋆

2

kf − fm k ≤

16vf2 ⋆ ,2
m

.

The supplement also discusses refinements of these approximation bounds
and how one can reach similar conclusions with second order splines having
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

3

bounded internal parameters. The Lipschitz property of the ramp functions
yields smaller covering numbers and thus improved rates over that which
can be obtained using step functions. We define the set
Hramp = {x 7→ ±(α · x − t)+ : kαk1 = 1, |t| ≤ 1}.
We then set Framp to be the linear span of Hramp . In general, for a symmetric
collection of dictionary elements H = −H containing the zero function, we
let F = FH be the linear span of H. The variation vf = kf kH of f with
respect to H (or the atomic norm of f with respect to H) is defined by
(
)
X
+
lim inf kβk1 : fδ =
,
βh h and kfδ − f k ≤ δ, βh ∈ R
δ↓0 fδ ∈F

h∈H

P

where kβk1 = h∈H βh . For functions in F
PH , this variation picks out the
smallest kβk1 among representations f = h∈H βh h. For functions in the
L2 (P ) closure of the linear span of H, the variation is the smallest limit
of such ℓ1 norms among functions approaching the target. The subspace of
functions with kf kH finite is denoted L1,H .
R
Note that the condition Rd kωk21 |f˜(ω)|dω < +∞ ensures that f ⋆ belongs to
L1,Hramp and kf ⋆ kHramp ≤ vf ⋆ ,2 . Functions with moderate variation are particularly closely approximated. Nevertheless, even when kf ⋆ kH is infinite, we
express the trade-offs in approximation accuracy for consistently estimating
functions in the closure of the linear span of H.
In what follows, we assume h has L∞ norm at most one, h is Lipschitz
with Lipschitz constant at most one, and the internal parameters have ℓ1
norm at most Λ. This control on the size of the internal parameters will be
featured prominently throughout. In the case of ramp activation functions,
we are content with the assumption Λ = 2. Note that if one restricts the
size of the domain and internal parameters (say, to handle polynomials), the
functions h are still bounded and Lipschitz but with possibly considerably
worse constants.
Suppose data {(Xi , Yi )}ni=1 are independently drawn from the distribution of
(X, Y ). To produce predictions of the real-valued response Y from its input
X, the target regression function f ⋆ (x) = E[Y |X = x] is to be estimated.
The function f ⋆ is assumed to be bounded in magnitude by a positive constant B. We assume the noise ǫ = Y − f ⋆ (X) has moments (conditioned
on X) that satisfy a Bernstein condition with parameter η > 0. That is, we
assume
1
k = 3, 4, . . . ,
E(|ǫ|k |X) ≤ k!η k−2 V(ǫ|X),
2
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

4

where V(ǫ|X) ≤ σ 2 . This assumption is equivalent to requiring that E(e|ǫ|/ν |X)
is uniformly bounded in X for some ν > 0. A stricter assumption is that
2
E(e|ǫ| /ν |X) is uniformly bounded in X, which corresponds to an error distribution with sub-Gaussian tails. These two noise settings will give rise to
different risk bounds, as we will see.
The input design X is assumed to be a d-dimensional vector with subGaussian coordinates. This condition implies that kXk2∞ is on average bounded
by a constant multiple of log d. We will see that in our framework, estimators of f ⋆ are functions of training and test data. If one seeks to describe
the error of an estimator for f ⋆ evaluated at a new set of random points distributed according to P , the estimator is allowed to depend on the test data
and the sub-Gaussian coordinates can be shown to affect the rates below
only by a logarithmic factor in d. This paper will focus only on the ability of
an estimator to generalize to a new data set. For ease of analysis, we assume
that X is contained in the hyper-cube [−1, 1]d , i.e. the supremum norm of
X is at most one. No assumption is made about whether the coordinates of
X are independent.
Because f ⋆ is bounded in magnitude by B, it is useful to truncate an estimator fˆ at a level Bn at least B. Depending on the nature of the√noise ǫ,
we will see that Bn will need to be at least B plus a term of order log n or
log n. We define the truncation operator T that acts on function f in F by
T f = min{|f |, Bn }sgnf . Associated with the truncation operator is a tail
quantity
n
X
(|Yi |2 − Bn2 )I{|Yi | > Bn }
Tn = 2
i=1

that appears in the following analysis. Lemma 9 describes the finite sample
behavior of ETn .

The empirical mean squared
error of a function f as a candidate fit to the
P
observed data is (1/n) ni=1 (Yi − f (Xi ))2 . Given the collection of functions
F, a penalty penn (f ), f ∈ F, and data, a penalized least squares estimator
fˆ arises by optimizing or approximately optimizing
(1/n)

n
X
i=1

(Yi − f (Xi ))2 + penn (f )/n.

Our method of risk analysis proceeds as follows. Given a collection F of
candidate functions, we show that there is a countable approximating set F̃
of representations f˜, variable-distortion, variable-complexity cover of F, and
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

5

a complexity function Ln (f˜), with the property that for each f in F, there is
an f˜ in F̃ such that penn (f ) is not less than a constant multiple of γn Ln (f˜)+
∆n (f, f˜), where γn is a constant (depending on B, Bn , σ 2 , and η) and
∆n (f, f˜) is given as a suitable empirical measure of distortion (based on sums
of squared errors). The variable-distortion, variable-complexity terminology
has its origins in [6], [7], and [12]. The task is to determine penalties such
that an estimator fˆ approximately achieving the minimum of kY − f k2n +
penn (f )/n satisfies
(1.3)

EkT fˆ − f ⋆ k2 ≤ c inf {kf − f ⋆ k2 + Epenn (f )/n + EAf },
f ∈F

for some universal c > 1 and positive quantity Af that decays as n grows.
The quantity
inf {kf − f ⋆ k2 + Epenn (f )/n + EAf }.
f ∈F

is an index of resolvability of f ⋆ by functions F with sample size n. We shall
take particular advantage of such risk bounds in the case that penn (f ) does
not depend on X. Our restriction of X to [−1, 1]d is one way to allow the
construction of such penalties.
The following table expresses the heart of our results, expressing valid penalties providing such risk bounds for moderate and high-dimensional situations.
Noise ǫ

λn &

sub-Gaussian / sub-exponential



2
γn
log(d+1)

penn (f )/n &
1/4

n
1/3
γn log(d+1)
n
1/2+1/(2(d+3))

dγn log(n/d+1)
n



zero
sub-Gaussian / sub-exponential

vf λn
(vf )4/3 λn
vf λn

Table 1: Penalties for Theorem 2
The results we wish to highlight are contained in the first two rows of Table
1. The penalties as stated are valid up to modest universal constants and
negligible terms that do not depend on the candidate fit. The quantity γn
is of order log2 n in the sub-exponential noise case, order log n in the subGaussian noise case and of constant order in the zero noise case. This γn (as
defined in Lemma 9) depends on the variance bound σ 2 , Bernstein parameter
η, the upper bound B of kf ⋆ kH , and the noise tail level Bn of the indicated
order.

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

6

When f ⋆ belongs to L1,H , a resulting valid risk bound is a constant multiple
4/3
of kf ⋆ kH λn or kf ⋆ kH λn , according to the indicated cases. In this way the
λn expression provides a rate of convergence.
The classical risk bounds for mean squared error, involving d/n to some
power, are only useful when the sample size is much larger than the dimension. Here, in contrast, in the first two lines of Table 1, we see the dependence
on dimension is logarithmic, permitting much smaller sample sizes. The price
we pay for the smaller dependence on dimension is a deteriorated rate with
exponent 1/4 in general and 1/3 under a no noise assumption. The rates in
last row improve upon the familiar exponent of 1/2 to 1/2 + 1/(2(d + 3)).
Note that when d is large, this enhancement in the exponent is negligible.
√
The rate in the first row is better than the third approximately for d > n,
the second is better than the third row approximately for d > n1/3 , and
both of these first two rows have risk tending to zero as long as d < eo(n) .
For functions in L1,Hramp , an upper bound of ((d/n) log(n/d))1/2 for the
squared error loss is obtained in [3]. Using the truncated penalized ℓ1 least
squares estimator (1.3), we obtain an improved rate of order
((dγn /n) log(n/d))1/2+1/(2(d+3)) , where γn is logarithmic in n, using techniques that originate in [15] and [14], with some corrections here. A slightly
better rate with the d + 3 replaced by d + 1 in the denominator of the exponent can be achieved through more technical means, that we choose not
to put in the present paper to keep the length under control.
In an upcoming paper, the authors intend to show that this rate is almost
optimal in the Gaussian noise, uniform design setting, since we provide minimax rates between (1/n)1/2+1/(d+2) and (d/n)1/2+1/2(d+1) for functions in
L1,Hramp . Compare this with [20], where the mini-max L2 risk for functions
in L1,Hstep (i.e. function approximated by linear combinations of step ridge
functions) is determined to be between
(1/n)1/2+1/(2(d+1)) (log n)−(1+1/d)(1+2/d)(1+2/d)(2+1/d) and (log n/n)1/2+1/(2(2d+1)) .
These quantities have the attractive feature that the rate does not deteriorate as the dimension grows. However, they are only useful provided d/n
is small. In high dimensional settings, the available sample size might not
be large enough to ensure this condition. These results are all based on obtaining covering numbers for the library {x 7→ φ(θ · x) : kθk1 ≤ Λ}. If φ
satisfies a Lipschitz condition, these numbers are equivalent to ℓ1 covering
numbers of the internal parameters or of the Euclidean inner product of the
data and the internal parameters. The factor of d multiplying the reciprocal
of the sample size is produced from the order d log(Λ/ǫ) log cardinality of
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

7

the standard covering of the library {θ : kθk1 ≤ Λ}. What enables us to circumvent this polynomial dependence on d is to use an alternative cover of
{x 7→ x·θ : kθk1 ≤ Λ} that has log cardinality of order (Λ/ǫ)2 log(d+1). Misclassification errors for neural networks with bounded internal parameters
have been analyzed in [9] and [18].
In this paper we bound the mean squared error of function estimation, extending the results of [3], [4], [20], [15], [8], [7], [18], [11], [1], [21], [17].
2. Greedy Algorithm. The main difficulty with constructing an estimator that satisfies (1.3) is that it involves a dm-dimensional optimization.
Here, we outline a greedy approach that reduces the problem to performing m d-dimensional optimizations. This construction is based on the ℓ1 penalized greedy pursuit (LPGP) in [15], with the modification that the
penalty can be a convex function of the candidate function complexity.
Greedy strategies for approximating functions in the closure of the linear
span of a subset of a Hilbert space has its origins in [16] and and many of
its statistical implications were studied in [8] and [15].
Let f ⋆ be a function, not necessarily in F. Initialize f0 = 0. For m =
1, 2, . . . , iteratively, given the terms of fm−1 as h1 , . . . , hm−1 and the coefficients of it as β1,m−1
P
Pm, . . . , βm−1,m−1 , we proceed as follows. Let fm (x) =
m
β
h
(x)
=
j,m
j
j=1
j=1 βj,m φ(θhj · x), with the term hm in H chosen to
come within a constant factor c ≥ 1 of the maximum inner product with the
residual f ⋆ − fm−1 ; that is
hhm , f ⋆ − fm−1 i ≥

1
sup hh, f ⋆ − fm−1 i.
c h∈H

Define fm (x) = (1 − αm )fm−1 (x) + βm,m hm (x). Associated P
with this repm
resentation of fm is the ℓ1 norm of its coefficients vm =
j=1 |βj,m | =
(1 − αm )vm−1 + βm,m . The coefficients αm and βm,m are chosen so that
≤

inf

kf ⋆ − (1 − αm )fm−1 − βm,m hm k2 + w(vm )

α∈[0,1], β∈R+

[kf ⋆ − (1 − α)fm−1 − βhm k2 + w((1 − α)vm−1 + β)],

where w : R → R is a real-valued non-negative convex function. In the empirical setting, with Ri = Yi − fm−1 (Xi ), the high-dimensional optimization
task is to find θm such that
n

n

i=1

i=1

1X
1
1X
Ri φ(θm · Xi ) ≥
sup
Ri φ(θ · Xi )
n
c kθk1 ≤Λ n
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

8

One appealing aspect of the slight sub-optimality of θm is that it permits the
use of adaptive annealing techniques developed by the authors in a forthcomingPpaper [5]. The algorithm samples from a distribution proportional
n
1
to et( n i=1 Ri φ(θ·Xi )) p0P
(θ) which has, for t sufficiently large, a mean that is
1
1
at least c supkθk1 ≤Λ n ni=1 Ri φ(θ · Xi ).

Theorem 1. If fm is chosen according to the greedy scheme described
previously, then


4bf
⋆
2
⋆
2
kf − fm k + w(vm ) ≤ inf kf − f k + w(cvf ) +
,
f ∈F
m
where bf = c2 vf2 + 2vf kf ⋆ k(c + 1) − kf k2 . Furthermore,

inf inf

f ∈F δ>0

kf ⋆ − fm k2 + w(vm ) ≤
)
−1 (c + 1)2 v 2
4(1
+
δ)δ
f
,
(1 + δ)kf ⋆ − f k2 + w(cvf ) +
m

(

and hence with δ =

2(c+1)vf
√ ,
kf ⋆ −f k m

kf ⋆ − fm k2 + w(vm ) ≤ inf

f ∈F

(

2(c + 1)vf
√
kf ⋆ − f k +
m

2

Proof. Fix any f in the linear span F, with the form
non-negative βh .

)

+ w(cvf ) .

P

h∈H βh h,

with

em = kf ⋆ − fm k2 − kf ⋆ − f k2 + w(vm ).
Then from the definition of αm and βm,m ,
em = kf ⋆ − (1 − αm )fm−1 − βm,m hm k2 − kf ⋆ − f k2 +
w((1 − αm )vm−1 + βm,m )

≤ kf ⋆ − (1 − αm )fm−1 − αm cvf hm k2 − kf ⋆ − f k2 +
⋆

w((1 − αm )vm−1 + αm cvf )

≤ kf − (1 − αm )fm−1 − αm cvf hm k2 − kf ⋆ − f k2 +
(1 − αm )w(vm−1 ) + αm w(cvf ),

where the last line follows from the convexity of w. Now kf ⋆ −(1−αm )fm−1 −
αm cvf hm k2 is equal to k(1−αm )(f ⋆ −fm−1 )+αm(f ⋆ −chm vf )k2 . Expanding
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

9

this quantity leads to
kf ⋆ − (1 − αm )fm−1 − αm cvf hm k2 = (1 − αm )2 kf ⋆ − fm−1 k2

− 2αm (1 − αm )hf ⋆ − fm−1 , chm vf − f ⋆ i
+ α2m kf ⋆ − chm vf k2 .

Next we add (1 − αm )w(vm−1 ) + αm w(cvf ) − kf ⋆ − f k2 to this expression
to obtain
em ≤ (1 − αm )em−1 + α2m [kf ⋆ − chm vf k2 − kf ⋆ − f k2 ] + αm w(cvf )
− 2αm (1 − αm )hf ⋆ − fm−1 , chm vf − f i

+ αm (1 − αm )[2hf ⋆ − fm−1 , f ⋆ − f i − kf ⋆ − fm−1 k2 − kf ⋆ − f k2 ],

which is further upper bounded by
em ≤ (1 − αm )em−1 + α2m [kf ⋆ − chm vf k2 − kf ⋆ − f k2 ] + αm w(cvf )
− 2αm (1 − αm )hf ⋆ − fm−1 , chm vf − f i

− αm (1 − αm )(kf ⋆ − fm−1 k − kf ⋆ − f k)2 ,
Consider a random variable that equals h with probability βh /vf having
mean f . Since a maximum is at least an average, the choice of hm implies
that hf ⋆ − fm−1 , chm vf i is at least hf ⋆ − fm−1 , f i. This shows that em is
no less than (1 − αm )em−1 + α2m [kf ⋆ − chm vf k2 − kf ⋆ − f k2 ] + αm w(cvf ).
Expanding the squares in kf ⋆ − chm vf k2 − kf ⋆ − f k2 and using the CauchySchwarz inequality yields the bound kchm vf k2 + 2kf ⋆ k(kf − chm vf k)− kf k2 .
Since khm k ≤ 1 and kf k ≤ vf , we find that kf ⋆ − chm vf k2 − kf ⋆ − f k2 is at
most bf = c2 vf2 + 2vf kf ⋆ k(c + 1) − kf k2 . Hence we have shown that
e1 ≤ bf + w(cvf )
and
em ≤ (1 − αm )em−1 + α2m bf + αm w(cvf ).
Choose αm = 2/(m + 1), m ≥ 2 and use an inductive argument to establish the claim. The second statement in the theorem follows from similar
arguments upon consideration of
em = kf ⋆ − fm k2 − (1 + δ)kf ⋆ − f k2 + w(vm ),
together with the inequality a2 − (1 + δ)b2 ≤ (1 + δ)δ−1 (a − b)2 .

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

10

3. Risk bounds. Here we state our main theorem.
Theorem 2. Let f ⋆ be a real-valued function on [−1, 1]d with finite variation vf ⋆ with respect to the library H = {h(x) = φ(θh · x)}. We further
assume that φ is Lipschitz function with kφk∞ ≤ 1 and kθh k ≤ Λ. In the
case that f ⋆ belongs to L1,Hramp , φ is a ramp function with Λ = 2. If fˆ is
chosen to satisfy
)
( n
n
X
1
1X
(Yi − fˆ(Xi ))2 + penn (fˆ)/n ≤ inf
(Yi − f (Xi ))2 + penn (f )/n ,
f ∈F
n
n
i=1

i=1

then for the truncated estimator T fˆ and for penn (f ) depending on vf as
specified below, the risk has the resolvability bound
EkT fˆ − f ⋆ k2 ≤ 2(τ + 1) inf {kf − f ⋆ k2 + Epenn (f )/n},
f ∈F

The penalty divided by sample size penn (f )/n is at least
16vf



γn Bn2 Λ2 log(d + 1)
n

1/4

+8



γn Bn2 Λ2 log(d + 1)
n

1/2

+

Tn
n

and
60vf Λ






1 dγn log(n/d + 1) 1/2+1/2(d+3)
dγn log(n/d + 1) 1/2+1/2(d+3)
+ 2
n
Λ
n

1/2+3/2(d+3)
dγn log(n/d + 1)
dγn log(n/d + 1) Tn
+
+
+
,
n
n
n

when d is small compared to n. In the no noise setting, penn (f )/n is at least
4/3

16vf



γn Λ2 log(d + 1)
n

1/3

4/3

+ 4(vf

+ 1)



γn Λ2 log(d + 1)
n

2/3

,

Here γn = (2τ )−1 (1 + δ1 /2)(1 + 2/δ1 )(B + Bn )2 + 2(1 + 1/δ2 )σ 2 + 2(B + Bn )η
and τ = (1 + δ1 )(1 + δ2 ) for some δ1 > 0 and δ2 > 0. Accordingly, if f ⋆
belongs to L1,H , EkT fˆ − f ⋆ k2 is not more than a constant multiple of the
above penalties with vf replaced by kf ⋆ kH .
If fˆm is the LPGP estimator from the previous section, then by Theorem 1,
)
( n
n
X
4b
1
1X
f
,
(Yi − fˆm(Xi ))2 +w(vfˆm ) ≤ inf
(Yi − f (Xi ))2 + w(cvf ) +
f ∈F
n
n
m
i=1

i=1

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

11

where bf is the empirical version of the same quantity in Theorem 1 and
hence the risk has the resolvability bound
EkT fˆ − f ⋆ k2 ≤ 2(τ + 1) inf {kf − f ⋆ k2 + Epenn (cf )/n + 4Ebf /m},
f ∈F

for a penalty, convex in vf , penn (f ) = nw(vf ) as before. If m is chosen
√
to be of order between n and n so as to make the computational effects
negligible, the previously described L2 (P ) rates for estimating f ⋆ in L1,H via
the truncated estimator T fˆm are attainable under the appropriate penalties.
As we have said, where we have d + 3 in the denominator in the exponent, it
is possible to improve it to a d + 1. Such improvements are due to improved
covers for the complexity evaluation. These refinements also hold for the
LPGP estimator, although the number of iterations m needs to be of slightly
higher order than before.
One can also extend these results to include penalties that depend on the
number of terms m in an m-term greedy approximation fˆm to f ⋆ . We take
fˆm to be an m term fit from an LPGP algorithm and choose m̂ among all
m ∈ M (i.e. M = {1, . . . , n}) to minimize
n

1X
(Yi − fˆm (Xi ))2 + penn (fˆm , m)/n.
n
i=1

This approach enables the use of a data-based stopping criterion for the
greedy algorithm. For more details on these adaptive methods, we refer the
reader to [15]. The resolvability risk bound allows also for interpolation rates
between L2 and L1,H refining the results of [8] and in accordance with the
best balance between error of approximation and penalty.
The target f ⋆ is not necessarily in F. To each f in F, there corresponds a
function ρ, which assigns to (X, Y ) the relative loss
ρ(X, Y ) = ρf (X, Y ) = (Y − f (X))2 − (Y − f ⋆ (X))2 .
Let X ′ be an independent copy of the training data X used for testing the
efficacy of a fit fˆ based on X, Y . The relative empirical
loss with respect to
1 Pn
⋆
the training data is denoted by Pn (f ||f ) = n i=1
Pρ(Xi , Yi ) and that with
respect to the independent copy is Pn′ (f ||f ⋆ ) = n1 ni=1 ρ(Xi′ , Yi ). We define
the
empirical squared error by on the training
and test data by Dn (f, f˜) =
P
n
1 Pn
1
2
′
′
˜
˜
˜ ′ 2
i=1 (f (Xi ) − f (Xi )) and Dn (f, f ) = n
i=1 (f (Xi ) − f (Xi )) for all
n
f, f˜ in F. Using the relationship Y = f ⋆ (X) + ǫ, we note that ρ(X, Y ) can
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

12

also be written as (f (X) − f ⋆ (X))2 − 2ǫ(f (X) − f ⋆ (X)) = g 2 (X) − 2ǫg(X),
where g(x) = P
f (x) − f ⋆ (x). Hence we have the relationship Pn (f ||f ⋆ ) =
2
⋆
Dn (f, f ) − n ni=1 ǫi g(Xi ).

The relative empirical loss Pn′ (f ||f ⋆ ) is an unbiased estimate of the risk
Ekfˆ−f ⋆ k2 . Since ǫi has mean zero conditioned on Xi , the mean of Pn′ (f ||f ⋆ )
with respect to X ′ and Y is Ekfˆ−f ⋆ k2 . Such a quantity captures how well the
fit fˆ based on the training data generalizes to a new set of observations. The
goal is to control the empirical discrepancy Pn′ (f ||f ⋆ ) − cPn (f ||f ⋆ ) between
the loss on the future data and the loss on the training data for a constant
τ > 1. Toward this end, we seek a positive quantity penn (f ) to satisfy

E sup Pn′ (f ||f ⋆ ) − τ Pn (f ||f ⋆ ) − τ penn (f )/n ≤ 0,
f ∈F

Once such an inequality holds, the data-based choice fˆ in F yields
EPn′ (fˆ||f ⋆ ) ≤ τ E[Pn (fˆ||f ⋆ ) + penn (f )/n].

If fˆ satisfies
(3.1)
)
( n
n
ˆ)
X
pen
(
f
pen
(f
)
1
1X
n
n
≤ inf
+ Af ,
(Yi −fˆ(Xi ))2 +
(Yi − f (Xi ))2 +
f ∈F
n
n
n
n
i=1

i=1

for some positive quantity Af that decays to zero as the sample size grows,
we see that
EPn′ (fˆ||f ⋆ ) ≤ τ inf E[Pn (f ||f ⋆ ) + penn (f )/n + Af ].
f ∈F

Using EPn′ (fˆ||f ⋆ ) = Ekfˆ − f ⋆ k2 and EPn (f ||f ⋆ ) = kf − f ⋆ k2 , the above
expression is seen to be
Ekfˆ − f ⋆ k2 ≤ τ inf {kf − f ⋆ k2 + Epenn (f )/n + EAf }.
f ∈F

For the purposes of proving results in the case when F is uncountable, it
is useful to consider complexities Ln (f˜) for f˜ in a countable subset F̃ of F
P
˜
satisfying f˜∈F̃ e−γn Ln (f ) ≤ 1 for some γn > 0 and such that

sup Pn′ (f ||f ⋆ ) − τ Pn (f ||f ⋆ ) − τ penn (f )/n
f ∈F

(3.2)

n
o
≤ sup Pn′ (f˜||f ⋆ ) − τ Pn (f˜||f ⋆ ) − τ γn Ln (f˜)/n ,
f˜∈F̃

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

13

with
n
o
E sup Pn′ (f˜||f ⋆ ) − τ Pn (f˜||f ⋆ ) − τ γn Ln (f˜)/n ≤ 0.
f˜∈F̃

The condition in (3.2) is equivalent to requiring that
sup inf {∆n (f, f˜) + γn Ln (f˜) − penn (f )} ≤ 0,

f ∈F f˜∈F̃

where
∆n (f, f˜) = n[Pn (f˜||f ⋆ ) − Pn (f ||f ⋆ )] − (n/τ )[Pn′ (f˜||f ⋆ ) − Pn′ (f ||f ⋆ )].
If we truncate the penalized least squares estimator fˆ at a certain level Bn ,
for EkT fˆ − f ⋆ k2 to maintain the resolvability bound τ inf f ∈F {kf − f ⋆ k2 +
Epenn (f )/n + EAf }, we require that
sup inf {∆n (f, f˜) + γn Ln (f˜) − penn (f )} ≤ 0,

f ∈F f˜∈F̃

where
∆n (f, f˜) = n[Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ )] − (n/τ )[Pn′ (T f˜||f ⋆ ) − Pn′ (T f ||f ⋆ )].
Rather than working with the relative empirical loss Pn′ (T f ||f ⋆ ), we prefer
to work with
Dn′ (T f, f ⋆ ). These two quantities are related to each other,
1 Pn
provided n i=1 ǫi g(Xi′ ) is small and they are exactly equal in the no noise
case. Hence we would like to determine penalties that ensure

E sup Dn′ (T f, f ⋆ ) − τ Pn (f ||f ⋆ ) − τ penn (f )/n ≤ 0.
f ∈F

Suppose we require that

E sup {τ1−1 Dn′ (T f, f ⋆ ) − τ τ2 Pn (f ||f ⋆ )−
f ∈F

τ τ2 penn (f )/n} ≤ 0,
for some τ1 , τ2 ≥ 1. This further inflates the resulting risk bound by (1 +
τ1 )(1 + τ2 ) so that the factor τ is replaced with τ τ1 τ2 in (3). However, it
enables us to create countable covers F̃ with smaller errors in approximating
functions from F. To see this, suppose the countable cover F̃ satisfies

sup τ1−1 Dn′ (T f, f ⋆ ) − τ τ2 Pn (f ||f ⋆ ) − τ τ2 penn (f )/n
f ∈F

n
o
≤ sup Dn′ (T f˜, f ⋆ ) − τ Pn (T f˜||f ⋆ ) − τ γn Ln (f˜)/n ,
f˜∈F̃

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

14

or equivalently that
sup inf

f ∈F f˜∈F̃




γn
˜
˜
∆n (f, f ) + Ln (f ) − penn (f ) ≤ 0,
τ2

where
∆n (f, f˜) = n[τ2−1 Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ )]+

nτ −1 τ2−1 [τ1−1 Dn′ (T f, f ⋆ ) − Dn′ (T f˜, f ⋆ )].

There are two cases to consider for bounding ∆n (f, f˜). In the noise case, we
1
(b − a)2
set τ2 = 1 and τ1 = 1/τ + 1. Using the inequality, τ −1 a2 − b2 ≤ τ −1
√
√ 2
that can be derived from (a/ τ − b τ ) ≥ 0, we can upper bound the
difference τ1−1 Dn′ (T f, f ⋆ ) − Dn′ (T f˜, f ⋆ ) by
˜
(τ1 − 1)−1 Dn′ (T f, T f).
This quantity does not involve f ⋆ , which is desirable for the proceeding
analysis. Hence ∆n (f, f˜) is not greater than
n[Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜)].
and thus we seek a penalty penn (f ) that is at least
γn Ln (f˜) + n[Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜)].
An estimator fˆ satisfying (3.1) with penality penn (f ) that is at least
γn Ln (f˜) + n[Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜)].
satisfies the risk bound
EkT fˆ − f ⋆ k2 ≤ (τ + 1) inf {kf − f ⋆ k2 + Epenn (f )/n + EAf }.
f ∈F

In the no noise case, we set both τ1 and τ2 to be strictly greater than one.
We can bound the difference
τ2−1 Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) = τ2−1 Dn (T f˜, f ⋆ ) − Dn (f, f ⋆ )
≤ τ −1 Dn (f˜, f ⋆ ) − Dn (f, f ⋆ )
2

by (τ2 − 1)−1 Dn (f˜, f ) so that ∆n (f, f˜) has the bound
n(τ2 − 1)−1 Dn (f˜, f ) + nτ −1 τ2−1 (τ1 − 1)−1 Dn′ (f, f˜).
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

15

If we set τ2 = 2 and τ1 = 1/τ + 1, we find that ∆n (f, f˜) is no less than
n[Dn (f˜, f ) + Dn′ (f, f˜)].
An estimator fˆ satisfying (3.1) with penality penn (f ) that is at least
γn Ln (f˜) + n[Dn (f˜, f ) + Dn′ (f, f˜)].
satisfies the risk bound
EkT fˆ − f ⋆ k2 ≤ 2(τ + 1) inf {kf − f ⋆ k2 + Epenn (f )/n + EAf }.
f ∈F

By bounding the distortion in this way, we eliminate some error in approximating f by f˜ that arises from analyzing Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) and
Dn (T f˜, f ⋆ ) − Dn (T f, f ⋆ ).
Suppose F̃ is a countable collection of functions that satisfies
n
o
E sup Dn′ (T f˜, f ⋆ ) − τ Pn (f˜||f ⋆ ) − τ γn Ln (f˜) ≤ 0.

Theorem 3.

f˜∈F̃

If penn (f ) is at least
γn Ln (f˜) + n[Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜)].
or

γn Ln (f˜) + n[Dn (f˜, f ) + Dn′ (f, f˜)]

corresponding to the noise or no noise setting, then the truncated estimator
T fˆ with fˆ satisfying (3.1) has the resolvability bound
EkT fˆ − f ⋆ k2 ≤ 2(τ + 1) inf {kf − f ⋆ k2 + Epenn (f )/n + EAf }.
f ∈F

Recall that g is equal to f − f ⋆ . In this way, there is a one to one correspondence between f and g. To simplify notation, we sometimes write Dn (f, f ⋆ )
as Dn (g) and Dn′ (f, f ⋆ ) as Dn′ (g). Moreover, assume an analogous notation
holds for the relative loss functions Pn (f ||f ⋆ ) and P ′ (f ||f ⋆ ) and complexities
Ln (f ).
Theorem 4. If F is a countable collection of functions
in magP bounded
−Ln (f ) ≤ 1,
nitude by Bn and Ln (f ) satisfies the Kraft inequality
e
f ∈F
then

E sup Dn′ (f ||f ⋆ ) − τ Pn (f ||f ⋆ ) − τ γn Ln (f )/n ≤ 0,
f ∈F

where τ = (1 + δ1 )(1 + δ2 ) and γn = (2τ )−1 (1 + δ1 /2)(1 + 2/δ1 )(B + Bn )2 +
2(1 + 1/δ2 )σ 2 + 2(B + Bn )η.

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

16

Proof. Let s2 (g) be as in Lemma 1. Since g2 is non-negative, s2 (g) ≤
Dn′ (g2 ) + Dn (g2 ). Moreover, since |f | ≤ Bn and |f ⋆ | ≤ B, it follows that
s2 (g) ≤ (B + Bn )2 (Dn′ (g) + Dn (g)). Let γ1 = A1 (B + Bn )2 /2 with A1 to be
specified later. By Lemma 1, we have
n
o
γ1
E sup (1 − 1/A1 )Dn′ (g) − (1 + 1/A1 )Dn (g) − L(g)
(3.3)
n
g∈G


1 2
γ1
′
≤ E sup Dn (g) − Dn (g) − L(g) −
(3.4)
s (g) ≤ 0
n
2γ1
g∈G
By Lemma 2, we also know that
( n
)
γ2
1
1X
ǫi g(Xi ) − L(g) −
Dn (g) ≤ 0,
(3.5)
E sup
n
n
A2 n
g∈G
i=1

where γ2 = A2 σ 2 /2 + (B + Bn )η. Adding the expression in (3.3) to 2a > 0
times the expression in (3.5) and collecting terms, we find
P that 1 + 1/A1 +
2a/A2 should be equal to a in order for Dn (g) and n1 ni=1 ǫi g(Xi ) to be
added together to produce Pn (g). Thus we find that
n
o
γn
E sup (1 − 1/A1 )Dn′ (g) − a(Pn (g) + L(g)) ≤ 0,
n
g∈G
where γn = γ1 /a + 2γ2 . Choosing A1 = 1 + 2/δ1 , A2 = 2(1 + 1/δ2 ), and
τ = (1 + δ1 )(1 + δ2 ), we find that a = τ (1 − 1/A1 ). Dividing the resulting
expression by 1 − 1/A1 produces

E sup Dn′ (g) − τ Pn (g) − τ γn L(g)/n ≤ 0.
g∈G

In general, the penalty should not depend on the unknown test data X ′ .
However if one seeks to describe the error of a fit fˆ trained with the data
(X, Y ) at new data points X ′ , a penalty that depends on X ′ is natural and
fits in with the standard trans-inductive setting in machine learning [13].
Since we have been assuming that the input design X is contained in a cube
with side length at most one, the dependence on X ′ of the penalties as shown
in the following lemmata can be ignored.
When we speak of empirical L2 covers of H, we mean with respect to the
empirical measure of X ∪ X ′ on both the training and test data. That is,
empirical L2 covers of H are with respect to the squared norm [D(h, h̃) +
D ′ (h, h̃)]/2.
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

17

P
Theorem 5. Let f = h βh h. Let H̃1 be an empirical L2 ǫ1 -net for H of
cardinality M1 . Let H̃2 be an empirical L2 ǫ2 -net for H of cardinality M2 .
Suppose these empirical covers do not depend on the underlying
data. There
M2 +M1 +m0 
such that for
exists a subset F̃ of F with cardinality at most
M1 +m0
v ≥ vf and ṽ = v(1 + M1 /m0 )
Tn
2ṽ 2 ǫ21 ṽ 2 M1
+
,
+ 8Bn ṽǫ2 +
Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜) ≤
2
m0
n
2m0
for some f˜ in F̃. Alternatively, there exists a subset F̃ of F with cardinality
0
at most M2m+m
such that
0
2vvf
Tn
+ 8Bn vǫ2 +
,
Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜) ≤
m0
n
and in the case of no noise with Bn ≥ B
4vvf
Dn (f˜, f ) + Dn′ (f, f˜) ≤
+ 4v 2 ǫ22
m0
for some f˜ in F̃ .
Proof. The proof is an immediate consequence of Lemma 4.
According to Theorems 3 and 4, a valid penalty is at least
γn Ln (f˜) + n[Pn (T f˜||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜)],
P
−Ln (f˜) ≤ 1. The
where f˜ belongs to a countable set F̃ satisfying
f˜∈F̃ e
constant γn is as prescribed in Theorem
4. By Theorem 5, there is a set F̃
M2 +M1 +m0 
such that for all f with vf ≤ v, there
with cardinality at most
M1 +m0
⋆
˜
˜
is a f in F̃ such that Pn (T f ||f ) − Pn (f ||f ⋆ ) + Dn′ (T f, T f˜) is bounded by
2ṽ 2 ǫ21 ṽ 2 M1
Tn
.
+
+ 8Bn ṽǫ2 +
2
m0
n
2m0

1 +m0
is bounded by (M1 +
Using the fact that the logarithm of M2M+M
+m
1
0
m0 ) log(e(M2 /M1 + 1)), a valid penalty divided by sample size is at least
(3.6)

Tn
γn
2ṽ 2 ǫ21 ṽ 2 M1
+ 8Bn ṽǫ2 +
(M1 + m0 ) log(e(M2 /M1 + 1)) +
+
.
2
n
m0
n
2m0

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

18


0
such that
Alternatively, there is a set F̃ with cardinality at most M2m+m
0
⋆
˜
˜
for all f with vf ≤ v, there is a f in F̃ such that Pn (T f ||f ) − Pn (f ||f ⋆ ) +
˜ is bounded by
Dn′ (T f, T f)
2vvf
Tn
+ 8Bn vǫ2 +
m0
n
and hence a valid penalty divided by sample size is at least
(3.7)

γn m0 log M2 2vvf
Tn
+
+ 8Bn vǫ2 +
.
n
m0
n

In the no noise case, a valid penalty divided by sample size is at least
(3.8)

γn m0 log M2 4vvf
+
+ 4v 2 ǫ22 .
n
m0

We now discuss how m0 , ǫ1 , and ǫ2 should be chosen to produce penalties
that yield optimal risk properties for T fˆ.
4. Risk bounds in high dimensions.
4.1. Noise case. By Lemma 6, an empirical L2 ǫ2 -cover of H has cardi2 
2 
2) ⌉
2) ⌉
is bounded by
. The logarithm of 2d+⌈(Λ/ǫ
nality less than 2d+⌈(Λ/ǫ
⌈(Λ/ǫ2 )2 ⌉
⌈(Λ/ǫ2 )2 ⌉
2
4(Λ/ǫ2 ) log(d + 1).
Continuing from the expression (3.7), we find that penn (f )/n is at least
4γn m0 (Λ/ǫ2 )2 log(d + 1) 2vvf
Tn
+
+ 8Bn vǫ2 +
.
n
m0
n
1/2

vv nǫ22
, we see that penn (f )/n
Choosing m0 to be the ceiling of 2γn Λ2 flog(d+1)
must be at least

1/2
vvf γn Λ2 log(d + 1)
Tn
8γn Λ2 log(d + 1)
+ 8Bn vǫ2 +
+8
.
2
2
n
nǫ2
nǫ2


2 log(d+1) 1/4
so that penn (f )/n must
Finally, we set v = vf and ǫ2 = γn Λ nB
2
n
be at least


1/4
1/2
γn Bn2 Λ2 log(d + 1)
γn Bn2 Λ2 log(d + 1)
Tn
16vf
.
+8
+
n
n
n
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

19

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

We see that the main term in the penalty divided by sample size is
1/4

γn Bn2 Λ2 log(d + 1)
.
16vf
n
4.2. No noise case. Continuing from the expression (3.8), we find that
penn (f )/n is at least
4γn m0 (Λ/ǫ2 )2 log(d + 1) 4vvf
+
+ 4v 2 ǫ22 .
n
m0
1/2

Choosing m0 to be the ceiling of
must be at least



vvf nǫ22 (τ +1)2
γn Λ2 log(d+1)(τ +2)

4γn Λ2 log(d + 1)
+8
nǫ22



vvf γn Λ2 log(d + 1)
nǫ22

Finally, we set v = vf and ǫ2 =
penn (f )/n must be at least
4/3
16vf



γn Λ2 log(d + 1)
n

1/3

+



, we see that penn (f )/n

1/2

+ 4v 2 ǫ22 .


4(τ +2)/(τ +1)2 γn Λ2 log(d+1) 1/6
2
nv

4/3
4(vf

+ 1)



γn Λ2 log(d + 1)
n

so that

2/3

,

where we used the fact that v 2/3 ≤ v 4/3 + 1. We see that the main term in
the penalty divided by sample size is
1/3

2
4/3 γn Λ log(d + 1)
.
16vf
n
4.3. Combining the noise and no noise cases. As the previous sections
show, there are differences in the risk bounds depending on the nature of
the noise. These bounds only incorporate information about the presence of
noise, without regard to the degree of variability. Ideally one would prefer
to have a bound that interpolates between these two situations and recovers the no noise case exactly when the variability is zero. We can establish
the validity of a penalty divided by sample size that is at least a constant
multiple of
!1/3
!1/4
vf4 Λ2 γn log(d + 1)
vf4 Λ2 γn log(d + 1)
√
+ σ
.
(4.1)
n
n
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

20

plus negligible terms that do not depend on the candidate fit. Note that
this penalty is a convex function of vf and hence the setting of Theorem 1
applies. For a proof of the above form of the penalty, we refer the reader to
the supplement Supplement A.
5. Risk bounds with improved exponents for moderate dimensions. Continuing from the expression (3.6), we find that penn (f )/n is at
least
γn
Tn
2ṽ 2 ǫ21 ṽ 2 M1
+ 8Bn ṽǫ2 +
(M1 + m0 ) log(e(M2 /M1 + 1)) +
+
.
2
n
m0
n
2m0
Note that we can bound Bn2 by γn by choosing δ1 and δ2 appropriately. For
the precise definition of γn , see Theorem 4. The strategy for optimization is
to first consider the terms
2ṽ 2 ǫ21
√
γn
m0 log(e(M2 /M1 + 1)) +
+ 8 γn ṽǫ2 .
n
m0

(5.1)

After m0 , M1 , and M2 have been selected, we then check that
ṽ 2 M1
γn
M1 log(e(M2 /M1 + 1)) +
n
2m20

(5.2)

is relatively negligible. Choosing m0 to be the ceiling of
we see that (5.1) is at most
γn
log(e(M2 /M1 + 1)) + 4
n





1/2
2ṽ2 nǫ21
,
γn log(e(M2 /M1 +1))

ṽ 2 γn ǫ21 log(e(M2 /M1 + 1))
n

1/2

√
+ 8 γn ṽǫ2 .

Note that an empirical L2 ǫ-cover of H has cardinality between (Λ/ǫ)d and
(2Λ/ǫ + 1)d ≤ (3Λ/ǫ)d whenever ǫ ≤ Λ. Thus M2 /M1 ≤ (3ǫ1 /ǫ2 )d whenever
ǫ2 ≤ Λ and hence
log(e(M2 /M1 + 1)) ≤ 1 + (d/2) log(9ǫ21 /ǫ22 + 1) ≤ d log(9ǫ21 /ǫ22 + 1),
whenever ǫ21 ≥ ǫ22 (e − 1)/9. These inequalities imply that (5.1) is at most
dγn log(9ǫ21 /ǫ22 + 1)
+4
n



ṽ 2 ǫ21 dγn log(9ǫ21 /ǫ22 + 1)
n

Next, set
ǫ22 =

1/2

√
+ 8 γn ṽǫ2 .

9dǫ21
.
n

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

21

This means that the assumption ǫ21 ≥ ǫ22 (e − 1)/9 is valid provided d ≤
n/(e − 1). Thus (5.1) is at most
r
dγn log(n/d + 1)
dγn log(n/d + 1)
+ 20ǫ1 ṽ
.
n
n
Next, we add in the terms from (5.2). The selections of m0 and ǫ1 make
(5.2) at most
M1 dγn log(n/d + 1) M1 dγn log(n/d + 1)
+
n
nǫ21
Since M1 ≤ (3Λ/ǫ1 )d whenever ǫ1 ≤ Λ, we find that (5.2) is at most
(3Λ)d dγn log(n/d + 1) (3Λ)d dγn log(n/d + 1)
+
nǫd1
nǫd+2
1
1/2(d+3)

. Choosing ṽ = vf , we see that a valid
Let ǫ1 = 3Λ dγn log(n/d+1)
n
penalty divided by sample size is at least

60vf Λ






1 dγn log(n/d + 1) 1/2+1/2(d+3)
dγn log(n/d + 1) 1/2+1/2(d+3)
+ 2
n
Λ
n
1/2+3/2(d+3)

dγn log(n/d + 1) Tn
dγn log(n/d + 1)
+
+
.
+
n
n
n

Note that for the form of the above penalty to be valid, we need dγn log(n/d)
n
to be small enough to ensure that ǫ1 and ǫ2 are both less than Λ.
v 2 M1
4m20

from the bound in Lemma
P
5 at the expense of a larger set F̃ . For example, let (1/m0 ) m
k=1 bk hk , kbk ≥
vf be as in the first part of Lemma 4. Note that the vector
(b1 , . . . , bm )′ /kbk1 belongs to the ℓ1 unit ball. This space has an ǫ-covering
number of order (1/ǫ)m0 +M1 and thus the collection of representors F̃ is of
order


m0 +M1 M2 + M1 + m0
(1/ǫ2 )
.
M1 + m0

Remark.

It is possible to remove the term

This new cover can be used to yield even tighter bounds than those presented
in Table 1. However, the analysis is more technical and we omit it here. We
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

22

will however say that slightly improved rates of order vf ⋆
are possible.

d
n

log


n 1/2+1/(2(d+1))
d

6. Proofs of the lemmata. An important aspect of the above covers F̃
is that they P
only depend on the data (X, X ′ ) through kXk2∞ +kX ′ k2∞ , where
1
2
kXk∞ = n ni=1 kXi k2∞ . Since the coordinates of X and X ′ are restricted
to belong to [−1, 1]d , the penalties and quantities satisfying Kraft’s inequality do not depend on X and X ′ . This is an important implication for the
following empirical process theory. On the other hand, using the fact that
kXk2∞ +kX ′ k2∞ is symmetric in the coordinates of X and X ′ and has a mean
that is at most logarithmic in d, the following bounds can be adapted to handle covers F̃ that depend on the training and test data without imposing
sup-norm controls.
Lemma 1. Let (X, X ′ ) = (X1 , . . . , Xn , X1′ , . . . , Xn′ ), where X ′ is an independent copy of the data X and where (X1 , . . . , Xn ) are component-wise
independent but not necessarily identicallyPdistributed. A countable function
class G and complexities L(g) satisfying g∈G e−L(g) ≤ 1 are given. Then
for arbitrary positive γ,


1 2
γ
s (g) ≤ 0,
(6.1)
E sup Dn′ (g) − Dn (g) − L(g) −
n
2γ
g∈G
where s2 (g) =

1
n

Pn

i=1 (g

2 (X )
i

− g2 (Xi′ ))2 .

Proof. Let Z = (Z1 , . . . , Zn ) be a sequence of independent centered Bernoulli
random variables with success probability 1/2. Since Xi and Xi′ are identically distributed, g2 (Xi ) − g2 (Xi′ ) is a symmetric random variable and hence
sign changes do not affect the expectation in (6.1). Thus the right hand side
of the inequality in (6.1) is equal to
( n
)
1X
γ
1
EZ,X,X ′ sup
Zi (g2 (Xi ) − g2 (Xi′ )) − L(g) −
s2 (g) .
n
n
2γ
g∈G
i=1

Using the identity x = λ log(x/λ) with λ = γ/n, conditioning on X and X ′ ,
and applying Jensen’s inequality to move EZ inside the logarithm, we have

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

23

that
)
n
γ
1
1X
Zi (g 2 (Xi ) − g 2 (Xi′ )) − L(g) −
s2 (g)
EZ sup
n
n
2γ
g∈G
i=1
( n
)
X
1
γ
n
≤ log EZ sup exp
Zi (g 2 (Xi ) − g 2 (Xi′ )) − L(g) − 2 s2 (g) .
n
γ
2γ
g∈G
(

i=1

Replacing the supremum with the sum and using the linearity of expectation,
the above expression is not more than
( n
)
X
1X
γ
n 2
2
2
′
log
EZ exp
Zi (g (Xi ) − g (Xi )) − L(g) − 2 s (g)
n
γ
2γ
i=1
g∈G
( n
)


X
1X
n 2
γ
2
2
′
exp −L(g) − 2 s (g) EZ exp
Zi (g (Xi ) − g (Xi )) .
= log
n
2γ
γ
i=1

g∈G

Next, note that by the independence of Z1 , . . . , Zn ,
( n
)


n
Y
1X
1
2
2
′
2
2
′
EZi exp
Zi (g (Xi ) − g (Xi )) .
Zi (g (Xi ) − g (Xi )) =
EZ exp
γ
γ
i=1
i=1
n
o
2
Using the inequality ex +e−x ≤ 2ex /2 , each EZi exp γ1 Zi (g 2 (Xi ) − g 2 (Xi′ ))
o
n
is not more than exp 2γ1 2 (g2 (Xi ) − g 2 (Xi′ ))2 . Whence
( n
)


1X
n 2
2
2
′
EZ exp
Zi (g (Xi ) − g (Xi )) ≤ exp
s (g) .
γ
2γ 2
i=1

The claim follows from the fact that

γ
n

log

P

g∈G

e−L(g) ≤ 0.

Lemma 2. Let ǫ = (ǫ1 , . . . , ǫn ) be conditionally independent random variables given {Xi }ni=1 , with conditional mean zero, satisfying Bernstein’s moment condition with parameter η > 0. A countable class G and complexities
L(g) satisfying
X
e−L(g) ≤ 1
g∈G

are given. Assume a bound K, such that |g(x)| ≤ K for all g in G. Then
)
( n
n
γ
1 X 2
1X
ǫi g(Xi ) − L(g) −
g (Xi ) ≤ 0.
E sup
n
n
An
g∈G
i=1

i=1

where A is an arbitrary constant and γ = Aσ 2 /2 + Kh.
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

24

Proof. Using the identity x = λ log(x/λ) with λ = γ/n, conditioning on
X, and applying Jensen’s inequality to move Eǫ inside the logarithm, we
have that
( n
)
n
1X
γ
1 X 2
Eǫ|X sup
ǫi g(Xi ) − L(g) −
g (Xi )
n
n
An
g∈G
i=1
i=1
( n
)
n
1X
γ
1 X 2
≤ log Eǫ|X sup exp
ǫi g(Xi ) − L(g) −
g (Xi ) .
n
γ
γA
g∈G
i=1

i=1

Replacing the supremum with the sum and using the linearity of expectation,
the above expression is not more than
( n
)
n
X
1X
γ
1 X 2
ǫi g(Xi ) − L(g) −
g (Xi )
log
Eǫ|X exp
n
γ
γA
i=1
i=1
g∈G
( n
)
)
(
n
X
1X
γ
1 X 2
= log
exp −L(g) −
g (Xi ) Eǫ|X exp
ǫi g(Xi ) .
n
γA
γ
i=1

g∈G

i=1

Next, note that by the independence of ǫ1 , . . . , ǫn conditional on X,
( n
)


n
Y
1X
1
Eǫi |Xi exp
ǫi g(Xi ) =
ǫi g(Xi ) .
Eǫ|X exp
γ
γ
i=1

i=1

o
o
n 2 2
g (Xi )
.
By Lemma 7, each Eǫi |Xi exp γ1 ǫi g(Xi ) is not more than exp 2γσ2 (1−ηK/γ)
Whence
( n
)
 2 Pn

2
σ
1X
i=1 g (Xi )
Eǫ|X exp
ǫi g(Xi ) ≤ exp
γ
2γ 2 (1 − ηK/γ)
i=1
)
(
n
1 X 2
g (Xi ) ,
= exp
γA
n

i=1

where the last line followsPfrom the definition of γ. The proof is finished
after observing that nγ log g∈G e−L(g) ≤ 0.
P
Lemma 3. For f = Ph βh h and f0 in F, there is a choice of h1 , . . . , hm
in H with fm = (v/m) m
k=1 hk , v ≥ vf such that
kfm − f0 k2 − kf0 − f k2 ≤

vvf
.
m

Moreover, the same bound holds for any convex combination of kfm − f0 k2 −
kf0 − f k2 and ρ2 (fm , f ), where ρ is a possibly different Hilbert space norm.
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

25

Proof. Let H be a random variable that equals hv with probability βh /v
and zero with probability 1 − vf /v. Let H1 , . . . ,P
Hm be a random sample
m
1
from the distribution defining H. Then H = m
j=1 Hj has mean f and
2
2
furthermore the mean of kfm − f0 k − kf0 − f k is the mean is kf − Hk2 .
This quantity is seen to be bounded by vvf /m. As a consequence of the
bound holding
P on average, there exists a2 realization 2of fm of H (having
form (v/m) m
k=1 hk ) such that kfm − f0 k − kf0 − f k is also bounded by
V vf /m.
The next lemma is an extension of a technique used in [19] to improve the
L2 error of an m-term approximation of a function in L1,H . The idea is
essentially stratified sampling with proportional allocation used in survey
sampling as a means of variance reduction. In the following, we use the
notation k · k to denote a generic Hilbert space norm.
Lemma 4. Let H̃ be an L2 ǫ1 -net of H with cardinality M1 . For f =
P
and f0 in F, there is a choice of h1 , . . . , hm in H with fm =
h βh hP
(1/m0 ) m
k=1 bk hk , m ≤ m0 + M1 and kbk1 ≥ vf such that
kf0 − fm k2 − kf0 − f k2 ≤

vvf ǫ21
.
m0

Moreover, there is an equally weighted linear combination fm = (v/m0 )
v ≥ vf , m ≤ m0 + M1 such that
kf0 − fm k2 − kf0 − f k2 ≤

Pm

k=1 hk ,

v 2 ǫ21 (1 + M1 /m0 ) v 2 M1
+
.
m0
4m20

The same bound holds for any convex combination of kfm − f0 k2 − kf0 − f k2
and ρ2 (fm , f ), where ρ is a possibly different Hilbert space norm.
Proof. Suppose the elements of H̃ are h̃1 , . . . , h̃M1 . Consider the M1 sets
H̃j = {h ∈ H : kh − h̃j k2 ≤ ǫ21 },
S
j = 1, . . . , M1 . By working instead with disjoint sets H̃j \ 1≤i≤j−1 H̃i (H̃0 =
∅) that are contained in H̃j and whose union is H, we may assume
that the
P
H̃j form a partition of H. Let M = m0 + M1 and vj =
h∈H̃j βh . To
obtain the first conclusion, define a random variable Hj to equal hvj with
probability βh /vj for all h ∈ H̃j . let H1,j , . . . , Hnj ,j be a random sample
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

26

m
l
vj M
, where V = vM
of size Nj =
V
m0 and v ≥ vf , from the distribution
P
defining Hj . Note that the Nj sum to at most M . Define gj = h∈H̃j βh h
P 1 1 P Nj
and f = M
j=1 Nj
k=1 Hk,j . Note that the mean of f is f . This means the

expectation
kf0 − f k2 − kf0 − f k2 is the expectation of kf − f k2 , which is
PMof
1
equal to j=1 EkHj − gj k2 /Nj . Now EkHj − gj k2 /Nj is further bounded by
(V /M )

X

h∈H̃j

βh inf kh − hj k2 ≤ (V /M )
hj

X

h∈H̃j

βh kh − h̃j k2 ≤

vj vǫ21
.
m0

The above fact was established by noting that the mean of a real-valued
random variable minimizes its average squared distance from any point hj .
Summing over 1 ≤ j ≤ M1 produces the claim. Since this bound
Pholds on
average, there exists a realization fm of f (having form (1/m0 ) m
k=1 bk hk
with kbk1 ≥ vf ) such that kf0 − fm k2 − kf0 − f k2 is also bounded by

vvf ǫ21
m0 .

For the second conclusion, we
inj a similar
fashion. Suppose nj is a
m
k
l proceed
vj M
vj M
and V
with respective probabilities
random variable that equals V
v M

chosen to make its average equal to jV . Furthermore, assume n1 , . . . , nM1
V
V
nj . Since Vj ≤ vj + M
, the Vj sum to
are independent. Define Vj = M
at most V . Let Hj be a random variable that equals hvj with probability
βh /vj for all h ∈ H̃j . For each j and conditional on nj , let H1,j , . . . , Hnj ,j
be a random sample of size Nj = nj + I{nj = 0} from the distribution
P
defining Hj . Note that the Nj sum to at most M . Define gj = h∈H̃j βh h
P 1 1 P Nj
and f = M
j=1 Nj
k=1 Hk,j . Note that the conditional mean of H given
PM 1
N1 , . . . , NM1 is g =
j=1 (Vj /vj )gj and hence the mean of f is f . This
2
2
of kf −f k2 ,
means the expectation
PM1of kf0 −fk −kf0 −f2k is the expectation
2
which is equal to j=1 EkHj − (Vj /vj )gj k /Nj + Ekf − gk by the law of
total variance. Now EkHj − (Vj /vj )gj k2 /Nj is further bounded by
(V /M )2 (nj /vj )

X

h∈H̃j

βh inf kh − hj k2 ≤
hj

v 2 M ǫ21
.
m20

The above fact was established by noting that the mean of a real-valued
random variable minimizes its average squared distance from any point hj .
Next, note that by the independence of the coordinates of v1 , . . . , vM1 and

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

27

the fact that Vj has mean vj ,
M1
M1
X
X
2
2
(kgj k2 /vj2 )V(nj ).
(vj /vj − 1)gj k = (V /M )
Ekf − gk = Ek
2

j=1

j=1

Finally, observe that kgj k2 ≤ vj2 and V(nj ) ≤ 1/4 (a random variable whose
range is contained in an interval of length one has variance bounded by
2M
1
1/4). This shows that Ekf − gk2 ≤ v4m
2 . Since this bound holds on average,
0
P
there exists a realization fm of f (having form (v/m0 ) m
k=1 hk ) such that
kf0 − fm k2 − kf0 − f k2 is also bounded by

v2 ǫ21 (1+M1 /m0 )
m0

+

v 2 M1
.
4m20

Lemma 5. Let y = {yi }ni=1 be a sequence of real numbers and let x =
{xi }ni=1 and x′ = {x′i }ni=1 be sequences d-dimensional vectors. Let H̃1 be an
2
empirical L2 ǫ1 -net for H with cardinality M
P1 and H̃2 be an empirical L
ǫ2 -net for H with cardinality M2 . For P
f = h βh h in F, there is a choice
of h̃1 , . . . , h̃m in H̃2 with f˜m = (v/m0 ) m
k=1 h̃k , v ≥ vf , and m ≤ m0 + M1 ,
such that
n

n

1X
1X
(yi − T f˜m (xi ))2 −
(yi − f (xi ))2 +
n
n
i=1

i=1

1
n

n
X
i=1

(T f˜m (x′i ))2 − T f (x′i ))2
≤

2v 2 ǫ21 (1 + M1 /m0 ) v 2 M1
+
m0
2m20
+ 8Bn v (1 + M1 /m0 ) ǫ2
Tn
+
.
n

If F̃ denotes the collection of functions of the form f˜m , then F̃ has cardi1 +m0
.
nality at most M2M+M
1 +m0
P 0
Moreover, there is a choice of h̃1 , . . . , h̃m0 in H̃2 with f˜m0 = (v/m0 ) m
k=1 h̃k ,

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

28

v ≥ vf such that
n

n

1X
1X
(yi − T f˜m0 (xi ))2 −
(yi − f (xi ))2 +
n
n
i=1

i=1

1
n

n
X
i=1

(T f˜m0 (x′i ) − T f (x′i ))2
≤

(6.2)

2vvf
Tn
.
+ 8Bn vǫ2 +
m0
n

and
n

n

i=1

i=1

1X ˜
1X ˜
(fm0 (xi ) − f (xi ))2 +
(fm0 (x′i ) − f (x′i ))2
n
n
≤

(6.3)

4vvf
+ 4v 2 ǫ22 .
m0

If F̃ denotes the collection
of functions of the form f˜m0 , then F̃ has cardiM2 +m0 
nality at most
.
m0
Proof. We only prove the first claim of the lemma. Inequalities (6.2)
P and
(6.3) follow from similar arguments and Lemma 3. Let fm = (v/m0 ) m
k=1 hk
be as in the second part of Lemma 4. Since H̃2 is an empirical L2 ǫ2 -net for
H, for each hk there is an h̃k in H̃2 such that
n

n

i=1

i=1

1 X
1 X
|hk (xi ) − h̃k (xi )|2 +
|hk (x′i ) − h̃k (x′i )|2 ≤ ǫ22 .
2n
2n

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

29

P
Let f˜m = (v/m0 ) m
k=1 h̃k . By Lemma 8 (I) and (II),

(y − T f˜m (x))2 − (y − f (x))2 = [(y − fm (x))2 − (y − f (x))2 ]+
[(y − T f˜m(x))2 − (y − T fm (x))2 ]+

[(y − T fm (x))2 − (y − fm (x))2 ]

≤ [(y − fm (x))2 − (y − f (x))2 ]+
4Bn |fm (x) − f˜m (x)|+

4Bn (|y| − Bn )I{|y| > Bn }+

2(|y| − Bn )2 I{|y| > Bn }

= [(y − fm (x))2 − (y − f (x))2 ]+
4Bn |fm (x) − f˜m (x)|+

2(|y|2 − Bn2 )I{|y| > Bn }.

By Lemma 8 (III),
(T f˜m (x′ ) − T f (x′ ))2 ≤ (f (x′ ) − fm (x′ ))2 + 4Bn |f˜m (x′ ) − fm (x′ )|.
Thus we find that (y − T f˜m (x))2 − (y − f (x))2 + (T f˜m (x′ ) − T f (x′ ))2 is not
greater than
[(y − fm (x))2 − (y − f (x))2 ] + (f (x′ ) − fm (x′ ))2 +
4Bn [|fm (x) − f˜m (x)| + |f˜m (x′ ) − fm (x′ )|] + 2(|y|2 − B 2 )I{|y| > Bn }
n

By the second conclusion in Lemma 4,
n

n

i=1

i=1

1X
1X
(yi − fm (xi ))2 −
(yi − f (xi ))2 +
n
n

n
2v 2 ǫ21 (1 + M1 /m0 ) v 2 M1
1X
(fm (x′i ) − f (x′i ))2 ≤
+
.
n
m0
2m20
i=1

By the concavity of the square root function,
n

n

i=1

i=1

1 X
1 X
|hk (xi ) − h̃k (xi )| +
|hk (x′i ) − h̃k (x′i )|
2n
2n
is also no greater than ǫ2 . Using this, we have that
n

n

i=1

i=1

1X
1X
|fm (xi ) − f˜m (xi )| +
|fm (x′i ) − f˜m (x′i )| ≤ 2v (1 + M1 /m0 ) ǫ2 .
n
n
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

30

The last conclusion about the cardinality of F̃ follows from Lemma 10.
Lemma 6. Let xP
= {xi }ni=1 , where each xi is a d-dimensional vector in Rd .
1
2
Define kxk∞ = n ni=1 kxi k2∞ . There is a subset H̃ of H with cardinality at

most 2d+m
such that for each h(x) = φ(x · θ) with kθk1 ≤ Λ in H, there is
m
P
h̃(x) = φ(x · θ̃) in H̃ such that n1 ni=1 |h(xi ) − h̃(xi )|2 ≤ Λkθk1 kxk2∞ /m.

Proof.
By the Lipschitz condition on φ, it is enough to prove the bound for
1 Pn
|θ
· xi − θ̃ · xi |2 . Let v be a random vector that equals ej sgn(θj )Λ with
i=1
n
probability |θj |/Λ, j = 1, 2, . . . , d and equals the zero vector with probability
1 − kθk1 /Λ. Let v1 , v2 , . . . , vm be a random sample
from the distribution
1 Pm
v
defining v. Note that the average of θ = m
j=1 j is θ and hence the
2
average of each |θ · xi − θ · xi | is the variance of v · xi divided by m. Taking
the expectation of the desired quantity, we have
n

E

n

1X
1X
|θ · xi − θ · xi |2 =
E|θ · xi − θ · xi |2
n
n
i=1

i=1

n
1 X E(v · xi )2
≤
n
m
i=1

n
1 X kxi k2∞ Λkθk1
≤
n
m
i=1

= Λkθk1 kxk2∞ /m.

Since this bound holds on average, there must exist a realization θ̃ of θ for
which the inequality is also satisfied. Consider the collection of all vectors
of the form
m
X
uj ,
(Λ/m)
j=1

where uj is any of the 2d + 1 signed standard basis vectors including the
zero vector. This collection has cardinality bounded by the number of nonnegative integer solutions q1 , q2 , . . . , q2d+1 to
q1 + q2 + · · · + q2d+1 = m.

This number is 2d+m
with its logarithm is bounded by m log(e(2d/m + 1))
m
or 2m log(d + 1). An important aspect of the log cardinality of this empirical
cover is that it is logarithmic (and not linear) in the dimension d. This
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

31

small dependence on d is what produces desirable risk bounds when d is
significantly greater than the available sample size n.
Lemma 7. Let Z have mean zero and variance σ 2 . Moreover, suppose Z
satisfies Bernstein’s moment condition with parameter η > 0. Then
 2 2 
t σ /2
(6.4)
E(etZ ) ≤ exp
, |t| < 1/η.
1 − η|t|
Lemma 8.

Define T f = min{Bn , |f |}sgnf . Then

(I) (y − T f )2 ≤ (y − f )2 + 2(|y| − Bn )2 I{|y| > Bn },

(II) (y − T f )2 ≤ (y − T f˜)2 + 4Bn |f − f˜| + 4Bn (|y| − Bn )I{|y| > Bn }, and

(III) (T f˜ − T f )2 ≤ (f − f1 )2 + 4Bn |f1 − f˜|.

Proof. (I) Since (y − T f )2 = (y − f )2 + 2(f − T f )(2y − f − T f ), the proof
will be complete if we can show that
(f − T f )(2y − f − T f ) ≤ (|y| − Bn )2 I{|y| > Bn }.
Note that if |f | ≤ Bn , the left hand size of the above expression is zero.
Thus we may assume that |f | > Bn , in which case f − T f = sgnf (|f | − Bn ).
Thus
(f − T f )(2y − f − T f ) = 2ysgnf (|f | − Bn ) − (|f | − Bn )(|f | + Bn )
≤ 2|y|(|f | − Bn ) − (|f | − Bn )(|f | + Bn ).

If |y| ≤ Bn , the above expression is less than −(|f | − Bn )2 ≤ 0. Otherwise,
it is a quadratic in |f | that attains its global maximum at |f | = |y|. This
yields a maximum value of (|y| − Bn )2 .
(II) For the second claim, note that
(y − T f )2 = (y − T f˜)2 + (T f˜ − T f )(2y − T f˜ − T f ).
Hence, we are done if we can show that
(T f˜ − T f )(2y − T f˜ − T f ) ≤ 4Bn |f − f˜| + 4Bn (|y| − Bn )I{|y| > Bn }.
If |y| ≤ Bn , then
(T f˜ − T f )(2y − T f˜ − T f ) ≤ 4Bn |T f˜ − T f |
≤ 4Bn |f˜ − f |.
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

32

If |y| > Bn , then

(T f˜ − T f )(2y − T f˜ − T f ) ≤ 2|T f˜ − T f ||y| + 2Bn |T f˜ − T f |
= 2|T f˜ − T f |(|y| − Bn ) + 4Bn |T f˜ − T f |
≤ 4Bn (|y| − Bn ) + 4Bn |f˜ − f |.

(III) For the last claim, note that
(T f˜ − T f )2 = (T f˜ − T f1 )2 + [2T f˜ − T f1 − T f ](T f1 − T f )
≤ (T f˜ − T f1 )2 + 4Bn |T f1 − T f |
≤ (f˜ − f1 )2 + 4Bn |f1 − f |

Lemma 9.

Let Y = f ⋆ (X) + ǫ with |f ⋆ (X)| ≤ B. Suppose

(I) Ee|ǫ|/ν < +∞ or
(II) Ee|ǫ|

2 /ν

< +∞

for some ν > 0. Then E[(Y 2 − Bn2 )I{|Y | > Bn }] is at most
√
(I) (4ν 2 /n)Ee|ǫ|/ν provided Bn > 2(B + ν log n) or
√
√
2
(II) (2ν/n)Ee|ǫ| /ν provided Bn > 2(B + ν log n).
Proof. Under assumption (I),
p
P(Y 2 − Bn2 > t) = P(|Y | > t + Bn2 )
p
≤ P(|ǫ| > t + Bn2 − B)
√ √
≤ P(|ǫ| > (1/ 2)( t + Bn ) − B)
√ t 1 B√n
1
− (
−B)
≤ e− ν 2 e ν 2
Ee|ǫ|/ν .
The last inequality follows from a simple application of Markov’s inequality
after exponentiation.
Integrating the previous expression from t = 0 to t =
R ∞ −1√t
+∞ ( 0 e ν 2 dt = 4ν 2 ) yields an upper bound on E[(Y 2 − Bn2 )I{|Y | >
√
Bn }] that is at most (4ν 2 /n)Ee|ǫ|/ν provided Bn > 2(B + ν log n).
Under assumption (II),
P(Y 2 − Bn2 > t) = P(|Y |2 > t + Bn2 )

≤ P(|ǫ|2 > (1/2)(t + Bn2 ) − B 2 )
t

2
1 Bn
−B 2 )
2

≤ e− 2ν e− v (

Ee|ǫ|

2 /ν

.

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

33

The last inequality follows from a simple application of Markov’s inequality after exponentiation.
Integrating the previous expression from t = 0 to
R∞
t
t = +∞ ( 0 e− 2ν dt = 2ν) yields an upper bound on E[(Y 2 − Bn2 )I{|Y | >
√
√
|ǫ|2 /ν provided B >
2(B + ν log n) ≥
B
n
pn }] that is at most (2ν/n)Ee
2(B 2 + ν log n).
v
Lemma 10. The number of functions having the form m

hk belong to a library of size M is at most M −1+m
≤
m
logarithm bounded by m log(e(M/m + 1)).

Pm

k=1 hk , where
M +m
with its
m

Proof. Suppose the elements
Pm in the library are indexed from 1 to M . Let qi
be the number
of terms in k=1 hk of type i. Hence the number of function of
v Pm
the form m
k=1 hk is at most the number of non-negative integer solutions

q1 , q2 , . . . , qM to q1 + q2 + · · · + qM = m. This number is M −1+m
with
m
its logarithm bounded by the minimum of m log(e((M − 1)/m + 1)) and
m log M .
Acknowledgements. The risk bound framework of this paper is selfcontained, yet borrows heavily from the unpublished manuscript [15] written
with Cong Huang and Gerald Cheang, which was judged to be too long for
the Annals of Statistics. We are very indebted to their contributions. The
present paper with Jason Klusowski manages a compression of much of that
work, corrected determination of improved exponents of the rate, and new
improved rates for the high dimensional setting. The authors would also like
to thank William D. Brinda for useful discussions.
SUPPLEMENTARY MATERIAL
Supplement A: Proof of an approximation result and justification
of (4.1).
(doi: COMPLETED BY THE TYPESETTER; .pdf). We prove that a function satisfying a certain spectral condition belongs to the closure of the linear
span of ridge ramp functions. We also give a justification for the penalty divided by sample size as stated in (4.1).
References.
[1] Anthony, M. and Bartlett, P. L. (1999). Neural network learning: theoretical
foundations. Cambridge University Press, Cambridge. MR1741038

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

34
[2] Barron, A. R. (1993). Universal approximation bounds for superpositions of a sigmoidal function. IEEE Trans. Inform. Theory 39 930–945. MR1237720
[3] Barron, A. R. (1994). Approximation and estimation bounds for artificial neural
networks. Machine Learning 14 115-133.
[4] Barron, A., Birgé, L. and Massart, P. (1999). Risk bounds for model selection
via penalization. Probab. Theory Related Fields 113 301–413. MR1679028
[5] Barron, A. R. and Klusowski, J. M. (2016). Training artificial neural nets by
adaptive annealing. Preprint.
[6] Barron, A. R., Huang, C., Li, J. and Luo, X. (2008a). The MDL principle, penalized likelihoods, and statistical risk. Workshop on Information Theory Methods in
Science and Engineering, Tampere, Finland.
[7] Barron, A. R., Huang, C., Li, J. and Luo, X. (2008b). The MDL principle,
penalized likelihoods, and statistical risk. Festschrift in Honor of Jorma Rissanen
on the Occasion of his 75th Birthday Tampere University Press, Tampere, Finland.
Editor Ioan Tabus.
[8] Barron, A. R., Cohen, A., Dahmen, W. and DeVore, R. A. (2008c). Approximation and learning by greedy algorithms. Ann. Statist. 36 64–94. MR2387964
[9] Bartlett, P. L. (1998). The sample complexity of pattern classification with neural
networks: the size of the weights is more important than the size of the network. IEEE
Trans. Inform. Theory 44 525–536. MR1607706
[10] Breiman, L. (1993). Hinging hyperplanes for regression, classification, and function
approximation. IEEE Trans. Inform. Theory 39 999–1013. MR1237723
[11] Bunea, F., Tsybakov, A. B. and Wegkamp, M. H. (2007). Aggregation for Gaussian regression. Ann. Statist. 35 1674–1697. MR2351101
[12] Cheang, G. L. H. (1998). Neural network approximation and estimation of functions. Yale University, Department of Statistics PhD thesis.
[13] Gammerman, A., Vovk, V. and Vapnik, V. (1998). Learning by transduction.
Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence 148–
155.
[14] Huang, C. (2008). Risk of penalized least squares, greedy selection and ℓ1 penalization for flexible function libraries. Yale University, Department of Statistics
PhD thesis.
[15] Huang, C., Cheang, G. L. and Barron, A. R. (2008). Risk of penalized least squares, greedy selection and ℓ1 penalization for flexible function libraries. Yale University, Department of Statistics technical report.
http://www.stat.yale.edu/~ arb4/publications_files/RiskGreedySelectionAndL1penalization.pdf.
[16] Jones, L. K. (1992). A simple lemma on greedy approximation in Hilbert space and
convergence rates for projection pursuit regression and neural network training. Ann.
Statist. 20 608–613. MR1150368
[17] Juditsky, A. and Nemirovski, A. (2000). Functional aggregation for nonparametric
regression. Ann. Statist. 28 681–712. MR1792783
[18] Lee, W. S., Bartlett, P. L. and Williamson, R. C. (1996). Efficient agnostic
learning of neural networks with bounded fan-in. IEEE Trans. Inform. Theory 42
2118–2132. MR1447518
[19] Makovoz, Y. (1996). Random approximants and neural networks. J. Approx. Theory
85 98–109. MR1382053
[20] Yang, Y. and Barron, A. (1999). Information-theoretic determination of minimax
rates of convergence. Ann. Statist. 27 1564–1599. MR1742500
[21] Zhang, T. (2009). Some sharp performance bounds for least squares regression with
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

35

L1 regularization. Ann. Statist. 37 2109–2144. MR2543687

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

Submitted to the Annals of Statistics
arXiv: 1607.01434

SUPPLEMENT TO ”RISK BOUNDS FOR
HIGH-DIMENSIONAL RIDGE FUNCTION
COMBINATIONS INCLUDING NEURAL NETWORKS”
By Jason M. Klusowski and Andrew R. Barron
Yale University
We prove that a function satisfying a certain spectral condition
belongs to the closure of the linear span of ridge ramp functions.
We also give a justification for the penalty divided by sample size as
stated in (4.1).

R
Theorem. For an arbitrary target function f ⋆ (x) = Rd eix·ω f˜(ω)dω with
R
vf ⋆ ,2 = Rd kωk21 |f˜(ω)|dω finite, there exists a linear combination of ridge
ramp functions with kak k = 1 and |bk | ≤ 1 such that
kf ⋆ − fm k2 ≤

16vf2 ⋆ ,2
m

.

Proof. If f ⋆ can be extended to a function on L2 (Rd ) with Fourier transform f˜, the function f ⋆ (x) − x · ∇f ⋆ (0) − f ⋆ (0) can be written as the real
part of
Z
(eiω·x − iω · x − 1)f˜(ω)dω.
(6.5)
Rd

If |z| ≤ c, we note the identity
Z c
[(z − u)+ eiu + (−z − u)+ e−iu ]du = eiz − iz − 1.
−
0

If c = kωk1 , z = ω · x, α = α(ω) = ω/kωk1 , and u = kωk1 t, 0 ≤ t ≤ 1, we
find that
Z 1
2
−kωk1
[(α · x − t)+ eikωk1 t + (−α · x − t)+ e−ikωk1 t ]dt =
0

eiω·x − iω · x − 1.

36
imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

37

Multiplying the above by f˜(ω) = eib(ω) |f˜(ω)|, integrating over Rd , and applying Fubini’s theorem yields
Z Z 1
⋆
⋆
⋆
g(t, ω)dtdω,
f (x) − x · ∇f (0) − f (0) =
Rd

0

where
g(t, ω) = −[(α · x − t)+ cos(kωk1 t + b(ω))+

(−α · x − t)+ cos(kωk1 t − b(ω))]kωk21 |f˜(ω)|.

Consider a density on {−1, 1} × [0, 1] × Rd defined by
p(z, t, ω) = | cos(zkωk1 t + b(ω))|kωk21 |f˜(ω)|/v
where
Z Z 1
v=
[| cos(kωk1 t+b(ω))|+| cos(kωk1 t−b(ω))|]kωk21 |f˜(ω)|dtdω ≤ 2vf ⋆ ,2 .
Rd

0

Consider a random variable h(z, t, α)(x) that equals
(zα · x − t)+ s(zt, ω),
where s(t, ω) = −sgn cos(kωk1 t + b(ω)). Note that h(z, t, α)(x) has the form
±(α · x − t)+ . We see that

v

Z

f ⋆ (x) − x · ∇f ⋆ (0) − f ⋆ (0) =
{−1,1}×[0,1]×Rd

h(z, t, α)(x)dp(z × t × ω).

One can obtain the final result by sampling (z1 , t1 , ω1P
), . . . , (zm , tm , ωm ) ranm
v
domly from p(z, t, ω) and considering the average m
k=1 h(zk , tk , ωk ). Note
⋆
that since x = (x)+ − (−x)+ , we can regard x · ∇f (0) as belonging to the
linear span of {x 7→ z(α · x − t)+ : kαk1 = 1, 0 ≤ t ≤ 1, z ∈ {−1, 1}}. An
easy argument shows that its variance is bounded by 16vf2 ⋆ ,2 /m. This simple
argument can be extended to higher order expansions of f ⋆ . The function
f ⋆ (x) − xT Hf ⋆ (0)x/2 − x · ∇f ⋆ (0) − f ⋆ (0) (Hf ⋆ (0) is the Hessian of f ⋆ at
the point zero) can be written as the real part of
Z
(eiω·x + (ω · x)2 /2 − iω · x − 1)f˜(ω)dω.
(6.6)
Rd

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

38

As before, the integrand in (6.6) admits an integral representation by
(i/2)kωk31

Z

1
0

[(−α · x − t)2+ e−ikωk1 t − (α · x − t)2+ eikωk1 t ]dt.

Employing a sampling argument from an appropriately defined density, we
are able to approximate f ⋆ (x) − xT Hf ⋆ (0)x/2 − x · ∇f ⋆ (0) by a linear combinations of m second order spline functions (having bounded internal parameters) (α · x − t)2+ with a squared error bounded by 16vf2 ⋆ ,3 /m.
In the next part of the supplement, we justify the form of the penalty divided
by sample size as stated in (4.1). For this, we first need a lemma.
P
Lemma. Let f = h βh h and let H̃ be an empirical L2 ǫ-net
P of H of size
M . There is a choice of h̃1 , . . . , h̃m in H̃ with f˜m = (v/m) m
k=1 h̃k , v ≥ vf
such that
Pn (T f˜||f ⋆ ) − 2Pn (f ||f ⋆ ) + Dn′ (f˜, f ) ≤
Pn

4vvf
+ 6v 2 ǫ2 + 4σvǫ + Tn + Rn ,
m
√

Pn

4 √3ησ
2
2
i=1 (ǫi −σ ) > 0}. Moreover, ERn ≤
n
˜
and if F̃ denotes the collection
of functions of the form fm , then F̃ has
+m
cardinality at most Mm
.

where Rn =

1
n

1
2
2
i=1 (ǫi −σ )I{ n

Pm
˜
˜
Proof.
Let
f
=
(v/m)
m
k=1 hk be as in Lemma 3 and f = fm =
Pm
(v/m) k=1 h̃k be as in Lemma 5. Furthermore, define
q
τn = min{1, Dn (f˜m , fm )/σ 2 }.
By Lemma 8 (I),

Pn (T f˜m ||f ⋆ ) ≤ Pn (f˜m ||f ⋆ ) + Tn ,
and hence
Pn (T f˜m ||f ⋆ ) − (1 + τn )Pn (f ||f ⋆ ) ≤ Pn (f˜m ||f ⋆ ) − (1 + τn )Pn (f ||f ⋆ ) + Tn .
Also observe that
Pn (f˜m ||f ⋆ ) − (1 + τn )Pn (f ||f ⋆ ) = [Pn (f˜m ||f ⋆ ) − (1 + τn )Pn (fm ||f ⋆ )]+
(1 + τn )[Pn (fm ||f ⋆ ) − Pn (f ||f ⋆ )],

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

RISK BOUNDS FOR HIGH-DIMENSIONAL RIDGE COMBINATIONS

and

39

Dn′ (f˜m , f ) ≤ 2Dn′ (f˜m , fm ) + 2Dn′ (f, fm ).

By Lemma 3,
Pn (fm ||f ⋆ ) − Pn (f ||f ⋆ ) + Dn′ (f˜, f ) ≤
Using the inequality a2 − (1 + τ )b2 ≤

1+τ
τ (a

2vvf
.
m

− b)2 , we have

1 + τn
Dn (f˜m , fm ) + τn ǫ2n
Pn (f˜m ||f ⋆ ) − (1 + τn )Pn (fm ||f ⋆ ) ≤
τn
1 + τn
≤
Dn (f˜m , fm ) + τn σ 2 + Rn
τn
q
≤ 3Dn (f˜m , fm ) + 2σ Dn (f˜m , fm ) + Rn ,

P
where the last inequality follows from the definition of τn and ǫ2n = n1 ni=1 ǫ2i .
The first conclusion is proved after observing that Dn (f˜m , fm ) ≤ 2v 2 ǫ2 .
The statement about the cardinality of F̃ follows immediately from the form
of f˜ and Lemma 10.
We are also able to comment on how Rn behaves on average. To see this,
note
that Rn ≤ s +
Rn I{Rn > s} for all s > 0. Now, Rn I{Rn > s} =
1 Pn
1 Pn
2
2
2
2
i=1 (ǫi − σ )I{ n
i=1 (ǫi − σ ) > s}. By Chebychev’s inequality and the
n
2
2
fact that V(ǫ) ≤ σ and V(ǫ ) ≤ 12η 2 σ 2 (as per the Bernstein moment
P
V(ǫ2 )
condition on the noise), P( n1 ni=1 (ǫ2i − σ 2 ) > s + t) ≤ n(t+s)
2 . Integrating
this inequality from t = 0 to t = +∞ yields Rn I{Rn > s} ≤
√
√
p
2 V(ǫ2 )
2
.
s = V(ǫ )/n produces ERn ≤ √n ≤ 4 √3ησ
n

V(ǫ2 )
ns .

Choosing

By the above lemma and similar arguments leading to the conclusion of
Theorem 3, we see that a valid penalty divided by sample size is at least
4vvf
γn m log M
+
+ 6v 2 ǫ2 + 2σvǫ + Tn + Rn
n
m
2 ⌉
By Lemma 6, an empirical L2 ǫ-cover of H has cardinality less than 2d+⌈(Λ/ǫ)
.
⌈(Λ/ǫ)2 ⌉
2d+⌈(Λ/ǫ)2 ⌉
2
The logarithm of ⌈(Λ/ǫ)2 ⌉ is bounded by 4(Λ/ǫ) log(d + 1). Thus we see
that a valid penalty divided by sample size is at least

(6.7)

4γn m(Λ/ǫ)2 log(d + 1) 4vvf
+
+ 6v 2 ǫ2 + 4σvǫ + Tn + Rn
n
m

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

40

1/2

nvvf ǫ2
. Plugging this back into
Choose m to be the ceiling of γn Γ2 log(d+1)
(6.7), we find that a valid penalty divided by sample size is at least
8



vvf γn Λ2 log(d + 1)
nǫ2

1/2

+

4γn Λ2 log(d + 1)
+ 6v 2 ǫ2 + 4σvǫ + Tn + Rn .
nǫ2

Choose v = vf and
ǫ= 

1
v2 n
γn Λ2 log(d+1)

1/6

+



σ2 n
γn Λ2 log(d+1)

1/4 .

With this choice of ǫ, a valid penalty divided by sample size is seen to be at
least a modest constant multiple of
vf4 Λ2 γn log(d + 1)
n

!1/3

+

√

σ

σ

!2/3

vf4 Λ2 γn log(d + 1)
n

!1/4

+

2/3
Λ2 γn log(d + 1)
+
+
n
!3/4
Λ4/3 γn log(d + 1)
+ Tn + Rn .
n

vf2 Λ2 γn log(d + 1)
n

√



2

Thus when Λ γn log(d+1)
is small, we see that the penalty divided by sample
n
size has the form (4.1) plus negligible terms that do not depend on the
candidate fit.
Yale University
Department of Statistics
24 Hillhouse Avenue
New Haven, Connecticut
E-mail: andrew.barron@yale.edu
jason.klusowski@yale.edu

imsart-aos ver. 2011/11/15 file: KlusowskiBarronArXiv2016.tex date: July 27, 2016

