20.4 Exercises 246
open questions even in the most obvious examples. The main reference is by
Rogers [1964], which by now is a little old, but still interesting.
20.4 Exercises
20.1(Lower bounds for fixed design) Letn=mdfor integermand
A 1 ,...,Anbe a fixed design where each basis vector in{e 1 ,...,ed}is played
exactlymtimes. Then let (ηt)nt=1be a sequence of independent standard Gaussian
random variables andXt=〈At,θ∗〉+ηt. Finally letˆθnbe the ordinary least
squares estimator ofθ∗∈Rd. Show that
E
[
‖θˆn−θ∗‖^2 Vn
]
=d.
This exercise shows that thed-dependence in Eq. (20.3) is unavoidable in
general for a self-normalized bound, even in the fixed design setting.
20.2(Lower bounds for sequential design) Letn≥ 2 dand (ηt)nt=1be a
sequence of independent standard Gaussian random variables. Find a sequence
of random vectors (At)nt=1withAt∈Rdsuch thatVn=
∑n
t=1AtAtis invertible
almost surely andAtisσ(A 1 ,η 1 ,...,At− 1 ,ηt− 1 )-measurable for alltand
E
[
〈θˆn, 1 〉^2 /‖ 1 ‖^2 Vn− 1
]
≥cd,
wherec >0 is a universal constant andSn=
∑n
t=1ηtAtandθˆn=V
n−^1 Sn.
Hint ChooseA 1 ,...,Adto be the standard basis vectors. Subsequently choose
selected basis vectors adaptively to push the estimate of〈θˆn, 1 〉away from zero.
For Exercise 20.4 where we ask you to prove Lemma 20.1 a few standard
definitions will be useful.
Definition20.6 (Covering and Packing).LetA⊂Rd. A subsetC ⊂Ais said to
be anε-coverofAifA⊂∪x∈CB(x,ε), whereB(x,ε) ={y∈Rd :‖x−y‖≤ε}
is theεball centered atx. Anε-packingofAis a subsetP ⊂Asuch that for any
x,y∈P,‖x−y‖> ε(note the strict inequality). Theε-covering numberofA
isN(A,ε) =min{|C|:Cis anε-covering ofA}, while theε-packing number
ofAisM(A,ε) =max{|P|:Pis anε-packing ofA}, where we allow for both
the covering and packing numbers to take on the value of +∞.
