pdf Research Kengo Kato

2013.5.7. Minimax lower bounds via Neyman-Pearson lemma

Kengo Kato Suppose that there is a scalar dependent variable Y and a scalar covari- ate X which we assume has support in [0, 1]. Consider the nonparametric regression model

Y = f (X) + ϵ, ϵ ⊥⊥ X, ϵ ∼ N(0, σ^{2), σ2 > 0.}

We fix the distribution of X and σ² > 0. Let {ϕj}^∞j=1 be an orthonormal system in L²([0, 1]). We assume that

L := sup

j≥1^E[ϕ

2j(X)] < ∞.

For given α > 0 and C1> 0, suppose that f belongs to the class F(α, C1) = {f ∈ L²([0, 1]) : |⟨f, ϕj⟩| ≤ C1^j−α, ∀j ≥ 1},

where ⟨·, ·⟩ denotes the inner product in L²([0, 1]). Denote by ∥ · ∥ the L²([0, 1])-norm. Let (Y₁, X₁), . . . , (Y_n, X_n) be i.i.d. observations of (Y, X).

The purpose of this note is to prove (in a self-contained manner) the following (well-known) theorems by means of a simple application of the Neyman-Pearson lemma.¹

Theorem 1. Under the above setup, we have inf_fˆ _{f ∈F (α,C}^sup ₁₎^{Ef[∥ ˆf − f∥}

2_{] ≳ n}−(2α−1)/(2α)_,

where the infimum is taken over all estimators ˆf of f .

Remark 1. The idea of the proof of Theorem 1 is borrowed from [1, 2] where minimax lower bounds in the problem of estimating structural func- tions in nonparametric instrumental variables models and slope functions in functional linear models are derived [see also the proof of 4, Theorem 7]. However, in [1, 2], detailed proofs for the minimax lower bounds are not presented (though the proofs are correct). Hence I hope that this note would be of some help in understanding their proofs.

Alternatively, we have the following theorem.

Theorem 2. There exists a small constant c > 0 such that lim inf

n→∞ ^inf_fˆ _{f ∈F (α,C}^sup ₁₎^{Pf(∥ ˆf − f∥}

2 _{> cn}−(2α−1)/(2α)_{) > 0.}

1For various techniques to derive minimax lower bounds in nonparametric statistical problems, see [3].

1

Proof of Theorem 1. Let M_n be the integer part of n^1/(2α). For θ^Mn = (θ_Mn+1, . . . , θ_2Mn)^T _{∈ R}^Mn, define

f_θMn_{(·) = C1}

2Mn

∑

j=Mn+1

j^−αθjϕj_(·).

Clearly, f_θMn _{∈ F(α, C1}) whenever θ^Mn _{∈ [0, 1]}^Mn. Lemma 1. _{We have}

inf_fˆ _{f ∈F (α,C}^sup ₁₎^{Ef[∥ ˆf − f∥}

2_{] ≥ inf} θˆ^Mn

sup

θ^Mn∈{0,1}^Mn

E_θ^Mn[∥f_θˆMn − fθ^Mn∥^2],

where the infimum on the right side is taken over all estimators ˆθ^Mn _∈ [0, 1]^Mn of θ^Mn.

Proof of Lemma 1. For arbitrary ˆf , we have sup

f ∈F (α,C₁)^{Ef[∥ ˆf − f∥}

2_{] ≥ sup} θ^Mn∈{0,1}^Mn

Eθ^Mn[∥ ˆf − fθ^Mn∥^2]. Moreover, by Bessel’s inequality,

∥ ˆf − f∥²≥

∞

∑

j=1

(⟨ ˆ^{f , ϕ}j⟩ − ⟨f, ϕj⟩)^2,

so that when f = f_θMn for some θ^Mn _{∈ {0, 1}}^Mn, it is enough to consider the estimator of the form

f (·) =ˆ

2Mn

∑

j=Mn+1

ˆ α_jϕ_j(·),

where ˆα_j are data-dependent. By defining ˆθ_j = C₁⁻¹j^ααˆ_j, ˆf is of the form f (·) = fˆ _θˆMn_{(·) = C}1

2Mn

∑

j=Mn+1

j^−αθ^ˆ_jϕ_j(·).

We need to show that we can restrict ˆθ_j in such a way that 0 ≤ ˆ^θj ≤ 1. For given ˆθ_j, define

θ˜_j =







1, if ˆθj > 1, θˆ_j, _{if 0 ≤ ˆ}θ_{j ≤ 1,} 0, if ˆθ_j < 0. Then whenever θ^Mn _{∈ {0, 1}}^Mn,

∥f_θˆMn _{− fθ}^Mn_∥²_{≥ ∥fθ}˜Mn _{− fθ}^Mn_∥².

This completes the proof of the lemma. □

For the notational convenience, write

θ_−j^Mn = (θ_Mn+1, . . . , θ_j−1, θ_j+1, . . . , θ_2Mn)^T, M_n+ 1 ≤ j ≤ 2Mn^.

Observe that sup

θ^Mn∈{0,1}^MnEθ

Mn_{[∥fθˆMn − fθ}Mn_∥²]

≥ _2M¹_n ^∑

θ^Mn∈{0,1}^Mn

Eθ^Mn[∥f_θˆMn _{− fθ}^Mn_∥²]

= ^C

12

2^Mn

2Mn

∑

j=Mn+1

j^{−2α ∑}

θ^Mn

−j ^∈{0,1} Mn−1

{E_θ^Mn

−j ^,θj=0

[(ˆθ_{j− θj})²]

+ E_θ^Mn

−j ^,θj=1

[(ˆθ_{j− θj})²]}. (1) We want to lower bound

E_θ^Mn

−j ^,θj=0

[(ˆθj_{− θ}j)²_{] + Eθ}Mn

−j ^,θj=1

[(ˆθj_{− θ}j)²].

To this end, we make use of a variant of Neyman-Pearson lemma combined with Le Cam’s inequality [3, Lemma 2.3].

Lemma 2. Let (S, S, µ) be a measure space, and let p, q be probability den- sity functions with respect to µ. Then

(i) (A variant of Neyman-Pearson lemma): inf

{∫

φpdµ +

∫

ψqdµ : φ ≥ 0, ψ ≥ 0, φ + ψ ≥ 1 }

≥

∫

(p ∧ q)dµ. (ii) (Le Cam’s inequality):

∫

(p ∧ q)dµ ≥ ¹₂

(∫ √_pqdµ⁾²_.

Proof of Lemma 2. Part (i): Let φ ≥ 0, ψ ≥ 0, φ + ψ ≥ 1. Then

∫

φpdµ +

∫

ψqdµ ≥

∫

(φ ∧ 1)pdµ +

∫

(1 − φ ∧ 1)qdµ.

We lower bound the right side with respect to φ. Clearly, we may assume that φ ≤ 1. The desired conclusion follows from the inequality

∫

(p − q)(φ − 1(p < q))dµ ≥ 0. Part (ii): Since∫ (p ∨ q)dµ + ∫ (p ∧ q)dµ = 2, we have

(∫ √_pqdµ⁾²₌^(∫ √(p ∧ q)(p ∨ q)dµ )2

≤

∫

(p ∧ q)dµ

∫

(p ∨ q)dµ

=

∫

(p ∧ q)dµ {

2 −

∫

(p ∨ q)dµ }

≤ 2

∫

(p ∧ q)dµ,

so that the desired inequality is obtained. □

For a while, fix M_n+1+1 ≤ j ≤ 2Mn^{and θM}_−jⁿ ∈ {0, 1}^{Mn−1. Let p}θj(y | x) denote the conditional density function of Y given X = x when f = f_θMn

−j ^,θj

:

p_{θj(y | x) = √} ¹ 2πσ^{2 exp}

{

−_2σ¹₂ ⁽y − f_θ^Mn

−j ^,θj

(x)⁾² }

. Then

E_θ^Mn

−j ^,θj=0

[ˆθ²_{j] + Eθ}Mn

−j ^,θj=1

[(ˆθ_{j− 1)}²]

= E [∫

θˆ²_j((y1, X1), . . . , (yn, Xn))

n

∏

i=1

p_θj=0(yi _{| X}i)dy1_{· · · dy}n

+

∫ _{

1 − ˆ^θj^((y1^{, X}1), . . . , (y_n, X_n))^}2

n

∏

i=1

p_θj=1(y_{i | Xi})dy_{1· · · dyn} ]

. (2)

Note that ˆθ²_{j + (1 − ˆ}θ_j)² ≥ 1/2, i.e., 2ˆ^θ2j + 2(1 − ˆ^θj⁾²≥ 1, and

p_{θj=0(y | x)pθj=1(y | x) =} ¹ 2πσ^{2 exp}







−_σ¹₂ (

y − f_θMn

−j ^,θj=0

(x) + f_θMn

−j ^,θj=1

(x) 2

)2^





× exp {

−_4σ¹₂^(f_θ^Mn

−j ^{,θj=1(x) − fθ} Mn

−j ^,θj=0

(x))² }

, so that, by Lemma 2,

∫ _θˆ²

j^{((y1, X1}), . . . , (yn, Xn))

n

∏

i=1

p_θj=0(yi _{| X}i)dy1_{· · · dy}n

+

∫ _{

1 − ˆ^{θj((y1, X1}), . . . , (yn, Xn))^}2

n

∏

i=1

p_θj=1(yi _{| X}i)dy1_{· · · dy}n

≥ ¹₄^exp {

−^C

12^j−2α

8σ²

n

∑

i=1

ϕ²_j(X_i) }

.

By convexity of the map x 7→ e^{−x, we have} (2) ≥ ¹₄^exp

{

−^C

12^j−2αn

8σ^{2 E[ϕ}

2j^(X)]

}

≥ ¹₄^exp {

−^C

12^j−2αnL

8σ² }

. For j ≥ Mn^{+ 1,}

j^−2α_{n ≤ (M}n+ 1)^−2α_{n ≤ 1,} so that whenever j ≥ M^{n+ 1,}

E_θ^Mn

−j ^,θj=0

[ˆθ²_{j] + Eθ}Mn

−j ^,θj=1

[(ˆθ_{j− 1)}²_{] ≥} ¹ 4^exp

{

−^C

12^L

8σ² }

.

Since M_n+ 1 ≤ j ≤ 2Mn ^{and θM}_−jⁿ ∈ {0, 1}^Mn−1 are arbitrary, combining this inequality with (1), we have

ˆinf

θ^Mn

sup

θ^Mn∈{0,1}^Mn

Eθ^Mn[∥f_θˆMn _{− fθ}Mn_∥²]

≥ ^C

12

8 ^exp {

−^C

12^L

8σ²

} 2Mn

∑

j=Mn+1

j^−2α. (3)

Since ^∑2M_j=Mⁿ_n+1j^−2α _{∼ Mn}^−2α+1 _{∼ n}−(2α−1)/(2α), we obtain the desired

conclusion. □

Proof of Theorem 2. It is not difficult to see that inf_fˆ _{f ∈F (α,C}^sup

1⁾

Pf(∥ ˆf − f∥^{2 > cn}−(2α−1)/(2α)₎

≥ inf

θˆ^Mn

sup

θ^Mn∈{0,1}^MnPθ

Mn_{(∥fθˆMn − fθ}Mn_∥²> cn−(2α−1)/(2α)_),

where inf_θˆMn is taken over all estimators ˆθ^Mn _{∈ [0, 1]}^Mn of θ^Mn.

Denote by δ1n the right side on (3). Fix arbitrary estimator ˆθ^Mn _∈ [0, 1]^Mn−1 of θ^Mn. Since {0, 1}^Mn is a finite set and the supremum over {0, 1}^Mn is attained, there exists a sequence θ^Mn such that

Eθ^Mn[∥f_θˆMn − fθ^Mn∥²] ≥ δ1n^.

Moreover,

∥f_θˆMn − fθ^Mn∥²≤ C1 2Mn

∑

j=Mn+1

j^−2α(ˆθ_{j − θj})²_{≤ C1}²

2Mn

∑

j=Mn+1

j^−2α =: δ_2n, so that E[∥f_θˆMn _{− fθ}^Mn_∥⁴_{] ≤ δ}²_2n. We recall the Paley-Zygmund inequality. Lemma 3(Paley-Zygmund inequality). Let Z be a real valued random vari- able with finite second moment. Then for every λ ∈ (0, 1),

P(Z≥ λE[Z]) ≥ (1 − λ)^2(E[Z])

2

E[Z^{2] .}

Apply the Paley-Zygmund inequality with λ = 1/2 and Z = ∥f_θˆMn ₋

f_θMn_∥². Then

Pθ^Mn(∥f_θˆMn _{− fθ}^Mn_∥² _{≥ δ}1n/2⁾

≥ Pθ^Mn

(

∥f_θˆMn − fθ^Mn∥²≥ ¹

2^{EθMn[∥fθˆMn − fθMn∥}

2_]

)

≥ ¹₄^{(E[∥fθˆMn − fθMn∥}

2_])2

E[∥f_θˆMn − fθ^Mn∥^{4] ≥} δ_1n² 4δ²_2n ^≥

1 256^exp

{

−^C

12^L

4σ² }

. Therefore, we conclude that

lim inf

n→∞ ^inf_fˆ _{f ∈F (α,C}^sup

1⁾

Pf(∥ ˆf − f∥^{2> δ}1n/2) ≥ ₂₅₆^{1 exp} {

−^C

12^L

4σ² }

.

Since δ_{1n∼ n}−(2α−1)/(2α), we obtain the desired conclusion. □ References

[1] Hall, P. and Horowitz, J.L. (2005). Nonparametric methods for inference in the presence of instrumental variables. Ann. Statist. 33 2904-2929. [2] Hall, P. and Horowitz, J.L. (2007). Methodology and convergence rates

for functional linear regression. Ann. Statist. 35 70-91.

[3] Tsybakov, A.B. (2009). Introduction to Nonparametric Estimation. Springer.

[4] Yuan, M. and Cai, T. (2010). A reproducing kernel Hilbert space ap- proach to functional linear regression. Ann. Statist. 38 3412-3444.