arXiv:1709.06256v1 [] 19 Sep 2017

Uniform Consistency of the Highly Adaptive Lasso
Estimator of Infinite Dimensional Parameters
Mark J. van der Laan∗ and Aurélien F. Bibaut
Division of Biostatistics, University of California, Berkeley
laan@berkeley.edu
September 20, 2017

Abstract
Consider the case that we observe n independent and identically distributed
copies of a random variable with a probability distribution known to be an element of a specified statistical model. We are interested in estimating an infinite
dimensional target parameter that minimizes the expectation of a specified loss
function. In van der Laan (2015) we defined an estimator that minimizes the
empirical risk over all multivariate real valued cadlag functions with variation
norm bounded by some constant M in the parameter space, and selects M with
cross-validation. We referred to this estimator as the Highly-Adaptive-Lasso estimator due to the fact that the constrained can be formulated as a bound M on
the sum of the coefficients a linear combination of a very large number of basis
functions. Specifically, in the case that the target parameter is a conditional
mean, then it can be implemented with the standard LASSO regression estimator. In van der Laan (2015) we proved that the HAL-estimator is consistent
w.r.t. the (quadratic) loss-based dissimilarity at a rate faster than n−1/2 (i.e.,
faster than n−1/4 w.r.t. a norm), even when the parameter space is completely
nonparametric. The only assumption required for this rate is that the true
parameter function has a finite variation norm. The loss-based dissimilarity is
often equivalent with the square of an L2 (P0 )-type norm. In this article, we
establish that under some weak continuity condition, the HAL-estimator is also
uniformly consistent.

Keywords: Cadlag, cross-validation, empirical risk, Highly-Adaptive-Lasso estimator, loss-function, oracle inequality, variation norm.

1

Introduction

Let O ∼ P0 ∈ M and Ψ : M → Ψ be an infinite dimensional target parameter of
interest, where Ψ = {Ψ(P ) : P ∈ M} is the parameter space of Ψ. The estimand is
∗

This author gratefully acknowledges the support of NIH grant R01 AI074345-09

1

thus given by ψ0 = Ψ(P0 ). We observe n i.i.d. copies of O. We assume there exists
a loss function L(ψ)(O) such that P0 L(ψ0 ) = minψ∈Ψ P0 L(ψ). We assume that the
loss function is uniformly bounded:
sup sup | L(ψ)(o) |< ∞.
ψ∈Ψ

(1)

o

In the case that the loss-based dissimilarity d0 (ψ, ψ0 ) ≡ P0 L(ψ)−P0 L(ψ0 ) is quadratic,
we often also assume
P0 (L(ψ) − L(ψ0 ))2
< ∞.
(2)
sup
ψ∈Ψ P0 L(ψ) − P0 L(ψ0 )
We assume that the parameter space Ψ is a subset of d-variate real valued cadlag
functions D[0, τ ] on a cube [0, τ ] ⊂ IRd≥0 . A function in D[0, τ ] is right-continuous
with left-hand limits, and we also assume that it is left-continuous at any point on
the right-edge of [0, τ ]: so if xj = τj for some j ∈ {1, . . . , d}, then we assume that ψ
is continuous at such an x. We also assume that each function ψ in the parameter
space Ψ has a uniform sectional variation norm bounded by some universal M < ∞,
but one can also select M with cross-validation to avoid this assumption supψ∈Ψ k
ψ kv < ∞ (see van der Laan (2015)), in which case we only need to assume that the
variation norm of each single ψ is finite. We define the uniform sectional variation
norm of a multivariate real valued cadlag function ψ as
X Z τs
| ψs (dus ) |,
k ψ kv = ψ(0) +
s⊂{1,...,d} 0s

where the sum is over all subsets s of {1, . . . , d}; for a given subset s, we define
us = (uj : j ∈ s), u−s = (uj : j 6∈ s); and we define the section ψs (us ) ≡ ψ(us , 0−s )
that sets the components in the complement of s equal to zero. Any cadlag function
that has a bounded variation norm generates a finite measure so that integrals w.r..t
this function are well defined. We also assume that for each ψ ∈ Ψ, O → L(ψ)(O)
1
is a d1 -variate cadlag function on a compact support [0, τ1 ] ⊂ IRd≥0
with universally
bounded variation norm:
sup k ψ kv < ∞.
(3)
ψ∈Ψ

If O = (B, O1 ) for a discrete variable B ∈ {1, . . . , K} and continuous component
O1 , then one only needs to assume this for O1 → L(ψ)(b, O1 ) for each b.
Consider the following estimator Ψ̂ : Mnp → Ψ defined by
Ψ̂(Pn ) = arg min Pn L(ψ).
ψ∈Ψ

(4)

In van der Laan (2015) we proved that this estimator converges in loss-based dissimilarity at a rate faster than n−1/2 to its true counterpart:
d0 (ψn , ψ0 ) = P0 L(ψn ) − P0 L(ψ0 ) = OP (n−1/2−α(d) ),
2

(5)

where α(d) > 0 is a specified number that behaves in the worst case as 1/d. The
worst case corresponds with Ψ = ΨN P ≡ {ψ ∈ D[0, τ ] :k ψ kv < M } being equal to
the set of cadlag functions with variation norm bounded by M , while this rate will be
better for smaller parameter spaces Ψ and can be expressed in terms of the entropy
of Ψ. For the case that the parameter space equals the nonparametric parameter
space ΨN P , this estimator can be defined as the minimizer of the empirical risk
Pn L(ψ) over a linear combination of around n2d−1 indicator basis functions under
the constrained that the sum of the absolute value of its coefficients is bounded by
M . This is shown by using the following representation of a function ψ ∈ D[0, τ ]
with k ψ kv < ∞:
X Z xs
dψs (us ).
ψ(x) = ψ(0) +
s⊂{1,...,d} 0s

This representation shows that ψ can be represented as an infinite linear combination
of indicators xs → I(us ≤ xs ) indexed by a cut-off us and subset s, where the sum
of the absolute values of the ”coefficients” dψs (us ) equals k ψ kv . This motivated us
to name it the Highly Adaptive Lasso (HAL) estimator, and indeed in the case of
a squared error or log-likelihood loss for binary outcomes it reduces to the standard
Lasso regression estimator as implemented in standard software packages, but where
one runs it with a possibly enormous amount of basis functions.
For example, for the squared error loss and ψ0 = EP0 (Y | W ) being a regression
function, d0 (ψ, ψ0 ) = P0 (ψ−ψ0 )2 is the square of the L2 (P0 )-norm. Thus, our general
convergence result will typically imply convergence in an L2 (P0 ) or Kullback-Leibler
norm. In this article we are concerned with showing that this general HAL-estimator
is also uniformly consistent under certain additional smoothness conditions. Let
k ψ k∞ = supx∈[0,τ ] | ψ(x) | be the supremum norm. We want to prove that
k ψn − ψ0 k∞ →p 0.

(6)

The case that the observed data has a discrete and continuous component
Before we proceed we demonstrate how one can apply our results to a setting in which
ψ0 is a function of a purely discrete component B and continuous component. Suppose that O = (B, O1 ), where B is discrete with finite number of values {1, . . . , K},
and ψ = (ψb : b Q
= 1, . . . , K), where the components ψb are variation independent so that Ψ = K
b=1 Ψb with Ψb being the parameter space of Ψb : M → ΨB .
One now assumes that for each b Ψb is a subset of db -dimensional cadlag functions
variation norm smaller than some Mb < ∞. We have d0 (ψn , ψ0 ) =
R
PK with
{L(ψ
n )(b, o1 ) − L(ψ0 )(b, o1 )}dP0 (b, o1 ). Suppose that L(ψ)(b, o1 ) only deb=1
pends on ψ through a ψb and suppose that ψ = (ψb : b = 1, . . . , K) is a variation
independent parameterization. Then, ψ0,b is the minimizer of ψ → P0 Lb (ψ) where
Lb (ψ)(O1 ) =P
I(B = b)L(ψ)(b, O1 ), and ψn,b = arg minΨb P0 Lb (ψ). In addition,
d0 (ψn , ψ0 ) = b d0,b (ψn,b , ψ0,b ), where d0,b (ψb , ψ0,b ) = P0 Lb (ψb ) − P0 Lb (ψ0,b ). Thus
the estimator ψn above can then be analyzed separately as an estimator ψn,b for
3

ψ0,b for each b. In particular, the rate of convergence result above now applies to
each ψn,b with dimension d replaced by db and loss function Lb (ψ). Our goal is then
reduced to establishing that ψn,b − ψ0,b converges uniformly to zero in probability.
In the sequel we suppress this index b, but the reader needs to know that in such
applications we simply apply our results to ψ0,b and ψn,b with loss function Lb (ψb ),
for each b separately. In order to establish our uniform consistency result, we will
assume that each P0 (B = b, ·) is a continuous measure for O1 , which corresponds
with the stated assumption A2 below that P0 is continuous on the support of Lb .
To establish the uniform consistency we will make the following assumptions:
A0 : d0 (ψn , ψ0 ) = oP (1) and the loss function is uniformly bounded (1).
A1 : d0 (ψ, ψ0 ) = 0 implies k ψ − ψ0 kP0 = 0.
A2 : ψ0 is continuous on [0, τ ], and P0 is continuous measure on the set of o-values
for which supψ | L(ψ)(o) |> 0.
A3 : If ψn converges pointwise to ψ∞ ∈ Ψ on [0, τ ] at each continuity point of
ψ∞ ∈ Ψ, then L(ψn ) converges pointwise to L(ψ∞ ) on a support of P0 .
Regarding assumption A0, above we provided sufficient assumptions that even guarantee d0 (ψn , ψ0 ) = OP (n−1/2−α(d) ), which could thus easily be weakened, as long as
we keep assuming that the loss function is uniformly bounded. Assumption A1 is
a very weak assumption. Regarding assumption A3, since P0 is continuous by A2,
one only needs to show that L(ψn ) converges to L(ψ∞ ) on a set that can exclude
any finite or countable set. Since the number of discontinuity points of ψ∞ is finite
or countable, the lack of convergence of ψn at these points should not be an issue.
We have the following theorem.
Theorem 1 Let ψn be the HAL-estimator defined by (4). Assume A0, A1, A2 and
A3. Then, supx∈[0,τ ] | ψn (x) − ψ0 (x) |→ 0 in probability as n → ∞.

2

Proof of Theorem 1

Using that supψ∈Ψ supo | L(ψ)(o) |< ∞, the dominated convergence theorem combined with A3 proves the following lemma.
Lemma 1 Assume A0 and A3. If ψn converges pointwise to ψ∞ ∈ Ψ on [0, τ ] at
each continuity point of ψ∞ , then P0 L(ψn ) − P0 L(ψ∞ ) → 0.
The following lemma proves that if d0 (ψ, ψ0 ) = 0, then ψ equals ψ0 pointwise as
well.
Lemma 2 Assume A1. If d0 (ψ, ψ0 ) = 0 for a ψ, ψ0 ∈ D[0, τ ], then k ψ −ψ0 k∞ = 0.

4

Proof: Assume d0 (ψ, ψ0 ) = 0. Suppose that ψ−ψ0 > 0 (same for < 0) at a point
x ∈ [0, τ ), then it will also be larger than 0 at a small neighborhood [x, x + δ) for
some δ > 0 due to the right-continuity of ψ − ψ0 . As a consequence, if ψ − ψ0 > 0 at
a point x, then k ψ − ψ0 kP0 > 0. By assumption A1 this implies that d0 (ψ, ψ0 ) > 0.
Finally, if x ∈ [0, τ )c ⊂ [0, τ ], then we assumed that ψ, ψ0 are left-continuous, so that
the same argument applies if we assume that ψ − ψ0 > 0 at an x on the right-edge
of [0, τ ]. This proves that d0 (ψ, ψ0 ) = 0 implies that ψ − ψ0 = 0 on [0, τ ]. ✷
The following lemma establishes that our parameter space ψ is weakly compact so
that each sequence has a weakly converging (i.e., poinwise) subsequence. In addition,
if we also assume that the sequence is consistent for ψ0 , then the limit of this weakly
converging subsequence has to equal ψ0 as well.
Lemma 3 Assume A0, A1, A2, and A3. Any sequence (ψn : n = 1, . . .) in Ψ has
a subsequence (ψn(k) : k = 1, . . .) so that there exists a ψ∞ ∈ Ψ and ψn(k) converges
pointwise to ψ∞ at each continuity point of ψ∞ .
If we also know that d0 (ψn , ψ0 ) → 0, then we have that k ψ∞ − ψ0 k∞ = 0.
Proof: By Hildebrandt (1963) (see also lemma 1.2 in van der Laan (1993)),
any cadlag function of bounded variation can be represented as a difference of two
monotone cadlag functions generating positive finite measures, i.e. the analogue of
cumulative distributions functions but not bounded by [0, 1]. Thus ψn = Fn − Gn
for monotone increasing functions Fn , Gn ∈ D[0, τ ]. Any sequence (Fn : n) of
cumulative distribution functions has a subsequence that converges weakly to a limit
F∞ , and similarly, any sequence (Gn : n) has a subsequence that converges weakly
to a limit G∞ , where weak convergence is equivalent with pointwise convergence
at each continuity point of the limit. This shows that we can find a subsequence
(Fn(k) − Gn(k) : k) of (Fn − Gn : n) and limit ψ∞ = F∞ − G∞ so that Fn(k) − Gn(k)
converges pointwise to F∞ − G∞ at each point in which both F∞ and G∞ are
continuous. We now want to show that the points at which ψ∞ are continuous
are equal to the point at which both F∞ and G∞ are continuous. By the Hahn
decomposition theorem both F∞ and G∞ are the sum of a continuous measure and
purely discrete measure. The continuous measure corresponds with a continuous
function. The discrete support of F∞ and G∞ has to be disjoint since if a measure
assigns at a point both a negative and positive mass then we can replace that by
just assigning a single mass that is either positive or negative. Thus we have shown
that (ψn(k) : k) converges pointwise to ψ∞ at each continuity point of ψ∞ .
Consider now the second statement in the lemma. Suppose now that we also
know that d0 (ψn , ψ0 ) →p 0. Then we also have d0 (ψn(k) , ψ0 ) → 0. By Lemma
1, the fact that ψn(k) converges pointwise to ψ∞ at each continuity point of ψ∞
implies that P0 L(ψn(k) ) − P0 L(ψ∞ ) → 0. Now use that d0 (ψn(k) , ψ0 ) = P0 L(ψn(k) ) −
P0 L(ψ∞ ) + d0 (ψ∞ , ψ0 ). Since the left-hand side converge to zero, and the first term
on the right-hand side converges to zero as well, this implies that d0 (ψ∞ , ψ0 ) = 0.

5

By Lemma 2, this implies that k ψ∞ − ψ0 k∞ = 0. This completes the proof of the
lemma. ✷
Consider our HAL-estimator ψn . Given d0 (ψn , psi0 ) →p 0, Lemma 3 proves that
ψn converges pointwise to ψ0 at each point in [0, τ ], where ψ0 is continuous. Thus, we
have translated the consistency of ψn w.r.t. loss-based dissimilarity into pointwise
convergence.
Lemma 4 Let ψn be the HAL-estimator defined by (4). Assume A0, A1, A2 and
A3. Then, ψn (x) − ψ0 (x) →p 0 at each x ∈ [0, τ ]. More generally, we have ψn =
Fn − Gn for Fn , Gn that generate positive uniformly finite measures, ψ0 = F0 − G0
for F0 , G0 that generates finite positive measures, and Fn (x) − F0 (x) →p 0 and
Gn (x) − G0 (x) → 0 for each x ∈ [0, τ ].
So we have shown ψn = Fn − Gn , ψ0 = F0 − G0 , where Fn , Gn converge pointwise
to F0 , G0 at each point in [0, τ ]. Finally, we establish that the pointwise convergence
of Fn (Gn ) to a continuous F0 (G0 ) implies uniform convergence, thereby showing
that ψn converges uniformly to ψ0 as well.
Lemma 5 If Fn is a sequence of cadlag functions that generate a positive measure
on [0, τ ], Fn (x) → F0 (x) for each x ∈ [0, τ ], and F0 is continuous on [0, τ ], then
k Fn − F0 k∞ → 0.
Proof: Let ǫ > 0.
By Heine’s theorem, since F0 is continuous on the compact set [0, τ ], it is uniformly continuous on [0, τ ].
By uniform continuity of F0 , there exists η > 0 such that for any x, y ∈ [0, τ ],
kx − yk < η implies |F0 (x) − F0 (y)| < ǫ. Consider a grid on [0, τ ] with grid points
xi ≡ (i1 η, ..., id η).
Consider an arbitrary x ∈ [0, τ ]. For a certain i ∈ Nd , x falls in the hypercube
[xi , xi + 1 ], where 1 ≡ (1, ..., 1).
Since F0 and Fn generate positive measures,
Fn (xi ) − F0 (xi+1 ) ≤ Fn (x) − F0 (x) ≤ Fn (xi+1 ) − F0 (xi ).

(7)

Observe that
Fn (xi+1 ) − F0 (xi ) = (Fn (xi+1 ) − F0 (xi+1 )) + F0 (xi+1 ) − F0 (xi+1 )).

(8)

Since Fn (xj ) − F0 (xj ) converges to zero for all the xj ’s in [0, τ ], and since there
are a finite number of such xj ’s, there exists n0 > 0 such that for all xj ∈ [0, τ ],
n > n0 , |Fn (xj ) − F0 (xj )| < 2ǫ .
Therefore, going back to (8) and using this latter fact and the uniform continuity,
we have Fn (xi+1 ) − F0 (xi ) ≤ 2ǫ for any n > n0 .

6

Since we can apply the exact same arguments to the lower bound in (7), we have
that for n > n0 ,
ǫ
ǫ
(9)
− ≤ Fn (x) − F0 (x) ≤ .
2
2
Since n0 does not depend on x, we have proved uniform convergence of Fn to F0
over [0, τ ]. ✷

References
Theophil Henry Hildebrandt. Introduction to the theory of integration. Academic
Press, 1963.
Mark J. van der Laan. Efficient and Inefficient Estimation in Semiparametric Models. PhD thesis, 1993.
Mark J. van der Laan. A generally efficient targeted minimum loss based estimator.
U.C. Berkeley Division of Biostatistics Working Paper Series, 2015.

7

