Optimal third root asymptotic bounds in the statistical estimation of thresholds

Franz Merkl and Leila Mohammadi

Abstract

This paper is concerned with estimating the intersection point of two densities, given a sample of both of the densities. This problem arises in classification theory. The main results provide lower bounds for the probability of the estimation errors to be large on a scale determined by the inverse cube root of the sample size. The key to the proof is an entropy estimate. The lower bounds are based on bounds for general estimators, which are applicable in other contexts, as well. Furthermore, we introduce a class of optimal estimators, whose errors asymptotically meet the border permitted by the lower bounds.^{1}

1 Introduction

1.1 Motivation and origin of the problem

In this article, we derive lower bounds for the probability of large errors of some estimators to occur. Let P be a class of probability measures on a measurable space (Ω, A), and a : P → ℝ be a parameter. Consider an i.i.d. random sample Z_{1}, ..., Z_{n} from P ∈ P and an estimator â_{n}(Z_{1}, ..., Z_{n}), â_{n} : Ω^{n} → ℝ, for a. We are interested in the asymptotic behaviour of â_{n} as n → ∞.

In the theory of empirical processes, one usually considers a deterministic loss function whose minimizer over a particular class is equal to or close to the parameter. In order to get an estimator, one then minimizes the empirical counterpart of the loss function, i.e., one replaces P by the empirical probability measure P̂_{n} in the minimization procedure.

It is natural to assume that the loss function is convex. For example, one may take the squared error loss function. Under some technical assumptions, if the loss is differentiable with respect to the parameter, the estimators converge to the parameter with the rate |â_{n} − a(P)| = O_{P} (n^{−1/2}) as the sample size n grows to ∞; see van de Geer [vdG00] and van der Vaart and Wellner [vdVW96]. If the loss is not convex, but a parametric form for P is assumed, one may obtain a similar rate O_{P} (n^{−1/2}); see Mohammadi and van de Geer [MvdG03], sections 2.1 and 2.2. In these cases, one usually gets normal asymptotic distributions of the estimators, using the central limit theorem. When the dimension of the parameter space is bigger than one, higher moments of the loss function may be needed to get the rate O_{P} (n^{−1/2}).

Kim and Pollard [KP90] establish a new functional central limit theorem for empirical processes. They describe an interesting class of asymptotic problems where the estimators converge at a rate different from O_{P} (n^{−1/2}) to limit distributions. The main point in these problems is that the loss function need not be convex; it may not even be continuous.

12000 Mathematics Subject Classification: Primary 62G05, secondary 62G20.

Key words: Classification theory, nonparametric models, estimation error, entropy bounds, thresholdbased classifiers.

An important non-continuous loss functions, frequently used in the theory of classification, is the indicator loss function. Let us first describe a general view of classification (or learning theory). We formulate the simplest case, which is a two-class problem. Assume that we have two distributions (on a result space X), labeled by Y = 1 and Y = −1. The values of Y are called “labels” or “natures”. Take an observation X from a mixture of the two distributions. It is sometimes called a “feature”. The problem is to predict the unknown nature Y of a feature X. Suppose we have n i.i.d. copies (X_{i}, Y_{i}), i = 1, …, n, of a realisation (X, Y). A classifier h is a measurable function h : X → {±1}. (Here, we do not consider more general [−1, 1]-valued classifiers.) The realisation (X, Y) is called misclassified by the classifier h if h(X) ≠ Y. We take the deterministic loss function (x, y) ↦ 1_{{h(x)≠y}}. For X ⊆ ℝ and features X with a continuous distribution (at least close to a point), Mohammadi and van de Geer [MvdG03] apply this setup to the case where the classifier h is varied over the class H = (h_{a})_{a∈ℝ}, where

h_{a}(x) = \{ \begin{matrix}1 & for x ≥ a, \\ −1 & for x < a. \end{matrix}  (1.1)

Let

f_{P} (x, y) = f_{P}^{+}(x)1_{{y=1}} + f_{P}^{−}(x)1_{{y=−1}}, (x, y) ∈ Ω = X × {±1},  (1.2)

denote the joint density of (X, Y) (with respect to some reference measure λ⊗(counting measure).

If there is a unique point a(P) at which f_{P}^{+}−f_{P}^{−} changes its sign, and if this sign change is from “−” to “+”, it suffices to restrict the classifier h to the class H to minimize the risk P [h(X) ≠ Y], since one has

inf_{classifiers h} P [h(X) ≠ Y] = inf_{a∈ℝ}P [h_{a}(X) ≠ Y] = P [h_{a(P)}(X) ≠ Y]  (1.3)

in this case. Taking a classifier h which minimizes P [h(X) ≠ Y] is called “Bayes rule”:

a(P) = arg min_{a∈ℝ}P [h_{a}(X) ≠ Y].  (1.4)

A natural choice for an estimator of a is the threshold â_{n} that minimizes the classification error in the sample, i.e.,

â_{n} = arg min_{a∈ℝ} P̂_{n}[h_{a}(X) ≠ Y] = arg min_{a∈ℝ} ∑_{i=1}^{n} 1_{{h_{a}(X_{i})≠Y_{i}}},  (1.5)

where

P̂_{n} = \frac{1}{n} ∑_{i=1}^{n} δ_{(X_{i},Y_{i})}  (1.6)

denotes the empirical distribution of the sample. (Strictly speaking, the “arg min” in (1.5) is not unique, but one may take any (measurable) choice.) In the theory of classification, this is called empirical risk minimization. Mohammadi and van de Geer [MvdG03] invoke the theory of Kim and Pollard [KP90] to get the rate O_{P} (n^{−1/3}) of â_{n} under some conditions. Under monotonicity assumptions, it is shown that â_{n} is a nonparametric maximum likelihood estimator, and that n^{1/3}(â_{n} − a(P)) converges in distribution to a continuous random variable. For more background information about empirical risk minimization in classification, see for instance [FS98], [SS98], [SFBL98], [BB02], and [MBG02].

1.2 Statement of the problem and results

In this article, we address the following question: Is there any sequence of estimators (â_{n} : Ω^{n} → ℝ)_{n∈ℕ} which converges to a(P) with a rate faster than O_{P} (n^{−1/3})? In a technical sense to be specified below, the answer is “no”.

Let us introduce the precise class P of probability measures that we consider. We assume that the features X take values in the unit interval X = [0, 1].

Let P̃ denote the set of all probability distributions

P = f_{P} [λ_{[0,1]} ⊗ (counting measure)]  (1.7)

on Ω = [0, 1] × {±1} (with the Borel σ algebra) with f_{P} ∈ C^{1}([0, 1] × {±1}). Here, λ_{[0,1]}

denotes the Lebesgue measure on [0, 1]. (This particular choice of the reference measure – at least locally – plays a role in some technical estimates; e.g. in the basic entropy bound (4.14), below.)

We endow P̃ with the metric d, given by

d(P, Q) = ∥f_{P} − f_{Q}∥_{∞} + ∥∂_{1}f_{P} − ∂_{1}f_{Q}∥_{∞},  (1.8)

where ∂_{1} denotes the derivative with respect to the first argument.

Let P ⊆ P̃ denote the set of all P ∈ P̃, such that f_{P}^{+} := f_{P} (·, 1) and f_{P}^{−} := f_{P} (·, −1) have a unique intersection point a(P), and this intersection point is contained in the open interval (0, 1), and the intersection is transversal with a specified orientation:

f_{P}^{+}(a(P)) = f_{P}^{−}(a(P)),  (1.9)
(f_{P}^{+})′(a(P)) > (f_{P}^{−})′(a(P)).  (1.10)

We endow P with the topology induced by the metric d.

Remark. For our results, it is essential to have at least some control on the derivative of f_{P}, which is reflected by the choice (1.8) of the metric d. In fact, the results heavily depend on the regularity assumptions that one supposes for the densities f_{P}, at least locally, i.e. close to the parameter a(P).

We prove two versions for lower bounds of estimation errors. The first version considers the estimation error on the “critical scale” const ·n^{−1/3}, uniformly over (small) open subsets of P:

Theorem 1.1 Let U ⊆ P be a nonempty open set. Then there is c_{1} = c_{1}(U) > 0, such that for every δ ∈ (0, 1/4] and for every sequence of estimators â_{n} : Ω^{n} → ℝ, n ∈ ℕ, one has

lim inf_{n→∞} sup_{P ∈U} P^{n} [n^{1/3}|â_{n} − a(P)| > T ] ≥ δ,  (1.11)

where

T = T (U, δ) = c_{1}| log(11δ)|^{1/3}.  (1.12)

Unlike Theorem 1.1, the following theorem considers the asymptotics of the estimation error “point-wise”, i.e. it takes the limit as n → ∞ before taking a supremum over open sets U ⊆ P.

Theorem 1.2 Let (β_{n})_{n∈ℕ} be a sequence of positive numbers with

n^{−1/3}β_{n} ⟶^{n→∞} ∞.  (1.13)

Then for all non-empty open sets U ⊆ P and for all sequences of estimators â_{n} : Ω^{n} → ℝ, n ∈ ℕ, one has

sup_{P ∈U} lim sup_{n→∞} P^{n}[β_{n}|â_{n} − a(P)| > 1] ≥ 1/4.  (1.14)

The proof of this theorem uses Baire’s theorem. A related argument, concerning the equicontinuity and the consistency of substitution estimators with values in a metric space, is presented in [PvZ96].

The “lim sup_{n→∞}” in (1.14) cannot be replaced by “lim inf_{n→∞}” for a trivial reason; a simple counter-example is shown at the end of section 5, below.

In contrast to Theorem 1.1, Theorem 1.2 does not consider the critical scale const ·n^{−1/3}. Indeed, its claim (1.14) breaks down on this critical scale. This is the content of the following theorem:

Theorem 1.3 There is a family of estimators (â_{n,L} : Ω^{n} → ℝ)_{n∈ℕ, L>0} with the following property: For all P ∈ P, there is a neighbourhood N ⊆ P of P, such that for all T > 0 one has

lim_{L→∞} sup_{Q∈N} lim sup_{n→∞} Q^{n}[n^{1/3}|â_{n,L} − a(Q)| > T] = 0.  (1.15)

Such estimators â_{n,L} are explicitly described in Section 5, below. Speaking very roughly, one estimates the density f_{P} in a certain neighbourhood of size Ln^{−1/3} of a first approximation of a(Q), using regression lines.

Organisation of this paper. Let us explain how the rest of this paper is organized. In Section 2, we collect some fundamental entropy estimates. Section 3 shows “universal”, general counterparts of Theorems 1.1 and 1.2, without assuming the specific form of our model (Ω, A, P). We expect these lemmas to be useful for other examples, too. One key idea is the use of Baire’s theorem to show that the set of P ’s with estimation errors being asymptotically large on a given scale is of second Baire category. In Section 4, Theorems 1.1 and 1.2 are proven. The proofs are based on a bound for relative entropies for slightly perturbed densities, described in Lemma 4.1, below. Finally, in Section 5, Theorem 1.3 is proven, by constructing the estimators â_{n,L} in a two-step procedure.

2 Preliminaries

In this section, we review some standard estimates to compare probabilities with respect to different measures, based on bounds of the relative entropy. Alternatively (and more or less equivalently), one could use bounds for the Hellinger distance instead of the relative entropy, but we do not follow this alternative approach here. Here, we need not assume any specific form of the model (Ω, A, P); we take an arbitrary parameter a : P → ℝ, and (â_{n} : Ω^{n} → ℝ)_{n∈ℕ} denotes any sequence of estimators.

Let H(P, Q) = E_{P} [log \frac{dP}{dQ}] denote the relative entropy for P, Q ∈ P, whenever it is well defined.

Lemma 2.1 Let P, Q be probability measures with H(P, Q) < ∞. For every random variable X with 0 ≤ X ≤ 1, one has

E_{Q}[X] ≥ e^{−2H(P,Q)−1} (E_{P} [X] − \frac{1}{2}) .  (2.1)

Proof. For x ≥ 0, set ψ(x) = x log x−x+1. Note that ψ ≥ 0. We set N = e^{2H(P,Q)+1} ≥ e and A = {dP/dQ > N}. Using ψ ≥ 0, ψ(1) = 0, and the convexity of ψ, one sees

ψ(x) ≥ \frac{ψ(N)}{N}1_{\{x>N\}}x  (2.2)

for all x ≥ 0, and thus

H(P, Q) = E_{Q} [ψ (\frac{dP}{dQ})] ≥ \frac{ψ(N)}{N}E_{Q} [1_{A} \frac{dP}{dQ}] = \frac{ψ(N)}{N}P [A].  (2.3)

We conclude, using ψ(N)/N = log(N/e) + 1/N ≥ 2H(P, Q):

E_{Q}[X] ≥ E_{Q}[X1_{A^{c}}] ≥ \frac{1}{N} E_{P} [X1_{A^{c}}]

≥ \frac{1}{N} (E_{P} [X] − P [A])

≥ \frac{1}{N} (E_{P} [X] − \frac{N}{ψ(N)}H(P, Q))

≥ \frac{1}{N} (E_{P} [X] − \frac{1}{2}) ,  (2.4)

which is the claim (2.1).

□

Remark. The “2” in the exponent of (2.1) could be replaced by any fixed number > 1, if one replaced the \frac{1}{2} in (2.1) by a different constant. This would only change the constants in our main theorems.

Lemma 2.2 Let χ : ℝ → [0, 1] be a measurable function with χ(x) = 1 for |x| ≤ 1 and χ(x) = 0 for |x| ≥ 2. Take n ∈ ℕ, β_{n} > 0, P_{n}, Q_{n} ∈ P, and δ ∈ (0, 1/4]. If

nH(P_{n}, Q_{n}) ≤ \frac{1}{2} log \frac{1}{11δ}  (2.5)

and

β_{n}|a(P_{n}) − a(Q_{n})| > 4  (2.6)

hold, then at least one of the following two bounds,

E_{P_{n}^{n}}[χ(β_{n}(â_{n} − a(P_{n})))] < 1 − δ  (2.7)

or

E_{Q_{n}^{n}}[χ(β_{n}(â_{n} − a(Q_{n})))] < 1 − δ,  (2.8)

is valid.

Proof. (Indirectly.) Assume that both, (2.7) and (2.8), fail to hold. Using Lemma 2.1, we get

Q_{n}^{n}[|β_{n}(â_{n} − a(P_{n}))| ≤ 2] ≥ E_{Q_{n}^{n}}[χ(β_{n}(â_{n} − a(P_{n})))]

≥ e^{−2nH(P_{n},Q_{n})−1} (E_{P_{n}^{n}}[χ(β_{n}(â_{n} − a(P_{n})))] − \frac{1}{2})

≥ e^{−2nH(P_{n},Q_{n})−1} (1 − δ − \frac{1}{2}) ≥ \frac{1}{4e}e^{−2nH(P_{n},Q_{n})} ≥ \frac{11}{4e}δ > δ  (2.9)

by (2.5); recall that δ ≤ 1/4. Furthermore, we have

Q_{n}^{n}[β_{n}|â_{n} − a(Q_{n})| ≤ 2] ≥ E_{Q_{n}^{n}}[χ(β_{n}(â_{n} − a(Q_{n})))] ≥ 1 − δ  (2.10)

by the opposite of (2.8) and the choice of χ. The bounds (2.10) and (2.9) imply that the events {β_{n}|â_{n} − a(Q_{n})| ≤ 2} and {β_{n}|â_{n} − a(P_{n})| ≤ 2} have a non-empty intersection. This implies

β_{n}|a(P_{n}) − a(Q_{n})| ≤ 4,  (2.11)

which contradicts the hypothesis (2.6).

□

3 General lower bounds

In this section, we prepare the proofs of Theorems 1.1 and 1.2 by providing some general, abstract lower bounds for estimators. Since we expect these lemmas to be useful in other contexts than the estimation of thresholds, too, we do not assume Ω, P, and a : P ↦ a(P) to have the specific form described in section 1.2. Rather, in this section, (Ω, A) may be any measurable space, P may be any set of probability measures on (Ω, A), endowed with a topology, and a : P → ℝ may be any parameter; only some very general assumptions for the topology on P and for the parameter a are required in Lemma 3.2, below. The first lemma in this section is a general statement which plays an essential role in the proof of Theorem 1.1.

Lemma 3.1 Take a sequence (β_{n})_{n∈ℕ} of positive numbers, δ ∈ (0, 1/4], and a nonempty open set U ⊆ P. For all large n ∈ ℕ, assume that there are P_{n}, Q_{n} ∈ U, such that

nH(P_{n}, Q_{n}) ≤ \frac{1}{2} log \frac{1}{11δ} and β_{n}|a(P_{n}) − a(Q_{n})| > 4  (3.1)

hold. Then for all sequences (â_{n} : Ω^{n} → ℝ)_{n∈ℕ} of estimators, one has

lim inf_{n→∞} sup_{P ∈U} P^{n}[β_{n}|â_{n} − a(P)| > 1] ≥ δ.  (3.2)

Proof. Take χ = 1_{[−1,1]}. By (3.1) and Lemma 2.2, (2.7) or (2.8) holds for all large n. Thus

inf_{P ∈U} P^{n}[β_{n}|â_{n} − a(P)| ≤ 1] < 1 − δ,  (3.3)

holds for all large n; hence (3.2) is true.

□

The constant “4” on the right hand side in (3.1) is not optimal. However, improving it does not improve our main theorems.

The next lemma provides an abstract key ingredient for the proof of Theorem 1.2.

Lemma 3.2 Let a : P → ℝ be a parameter, and (â_{n} : Ω^{n} → ℝ)_{n∈ℕ} be a sequence of estimators. Let P be endowed with a Baire space metrisizable topology. Assume that a : P → ℝ is continuous. Furthermore, assume that for all P ∈ P, the total variation distance from P, i.e. Q ↦ ∥P − Q∥_{V} = sup_{A∈A} |P [A] − Q[A]|, Q ∈ P, is continuous, too. Let (β_{n})_{n∈ℕ} be a sequence of positive numbers, and take δ ∈ (0, 1/4].

Suppose that for all P ∈ P, for all neighbourhoods N of P, and for all m ∈ ℕ, there are n ≥ m and Q_{n} ∈ N, such that

β_{n}|a(P) − a(Q_{n})| > 4 and nH(P, Q_{n}) ≤ \frac{1}{2}| log(11δ)|  (3.4)

are valid. Then for all non-empty open sets U ⊆ P, one has

sup_{P ∈U} lim sup_{n→∞} P^{n}[β_{n}|â_{n} − a(P)| > 1] ≥ δ.  (3.5)

Proof. Let χ : ℝ → [0, 1] be a continuous function with χ(x) = 1 for |x| ≤ 1, and χ(x) = 0 for |x| ≥ 2. For m, n ∈ ℕ, we set

P_{n} = {P ∈ P : E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))] ≥ 1 − δ}  (3.6)

and

F_{m} = ⋂_{n≥m} P_{n}.  (3.7)

We claim that the map

P → [0, 1], P ↦ E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))]  (3.8)

is continuous. To prove this claim, let P ∈ P, and consider a sequence (Q_{k})_{k} in P converging to P. Then for all ω ∈ Ω^{n}, we have

χ(β_{n}(â_{n}(ω) − a(Q_{k}))) ⟶^{k→∞} χ(β_{n}(â_{n}(ω) − a(P)))  (3.9)

by the continuity of a and of χ. Using Lebesgue’s dominated convergence theorem, this implies

E_{P^{n}}[χ(β_{n}(â_{n} − a(Q_{k})))] ⟶^{k→∞} E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))];  (3.10)

recall that χ takes values in the unit interval. Furthermore,

|E_{Q_{k}^{n}}[χ(β_{n}(â_{n} − a(Q_{k})))] − E_{P^{n}}[χ(β_{n}(â_{n} − a(Q_{k})))]| ≤ n∥Q_{k} − P ∥_{V} ⟶^{k→∞} 0, (3.11)

since by our hypothesis, the total variation distance from P is continuous. Combining (3.10) and (3.11), we get

E_{Q_{k}^{n}}[χ(β_{n}(â_{n} − a(Q_{k})))] ⟶^{k→∞} E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))],  (3.12)

which shows that E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))] depends continuously on P. Note that we used in the last step that the chosen topology on P is metrisizable (or, at least, that sequential continuity on P implies continuity).

The continuity of the map described in (3.8) implies that the sets P_{n} ⊆ P are closed; thus their intersections F_{m} are closed, too.

Next, we show that the sets F_{m} ⊆ P, m ∈ ℕ, are nowhere dense. To check this, take P ∈ F_{m} and a neighbourhood N of P in P. By the hypothesis of the lemma, there exist n ≥ m and Q_{n} ∈ N such that (3.4) holds. Then Lemma 2.2 implies

E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))] < 1 − δ or E_{Q_{n}^{n}}[χ(β_{n}(â_{n} − a(Q_{n})))] < 1 − δ,  (3.13)

i.e. P ∉ P_{n} ⊇ F_{m} or Q_{n} ∉ P_{n} ⊇ F_{m}, and thus N ⊈ F_{m}. This shows that indeed F_{m} is nowhere dense.

Let U ⊆ P be a non-empty open set. Since P is endowed with a Baire space topology, we conclude that U is not contained in ⋃_{m∈ℕ} F_{m}; so we can take P ∈ U \ ⋃_{m∈ℕ} F_{m}. For this P, we know that P ∉ P_{n} for infinitely many n ∈ ℕ. Thus we get

lim inf_{n→∞} E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))] ≤ 1 − δ.  (3.14)

Using

P^{n}[β_{n}|â_{n} − a(P)| > 1] ≥ 1 − E_{P^{n}}[χ(β_{n}(â_{n} − a(P)))],  (3.15)

this implies

lim sup_{n→∞} P^{n}[β_{n}|â_{n} − a(P)| > 1] ≥ δ,  (3.16)

and thus the claim (3.5) follows.

□

4 Lower bounds for errors in threshold estimation

In this section, we prove Theorems 1.1 and 1.2. Thus, let P denote again the concrete space of probability measures defined in subsection 1.2, endowed with the metric d, defined in (1.8). Note that (P̃, d) is a complete metric space. Perturbing P ∈ P slightly (with respect to the metric d) will move the intersection point a(P) only slightly, and small enough perturbations can destroy neither the uniqueness of the intersection point a(P) nor the transversality condition; thus a : P → [0, 1] is a continuous parameter, and P is an open subset of the space P̃; recall (1.7). In particular, by Baire’s category theorem, P is a Baire space.

The following lemma contains the basic entropy estimate for perturbed densities. Here is the idea: A given probability density f_{P} is slightly modified by a perturbation of order O(ϵ) in a neighbourhood of size O(ϵ) of the transversal intersection point a(P). Let Q denote the probability measure corresponding to the modified density f_{Q}; then we show that the entropy H(P, Q) has roughly the order O(ϵ^{3}), but the parameter a(Q) deviates from a(P) on a scale of order ϵ. The cube of ϵ arising in the entropy bound is the key to derive the cube root asymptotic lower bounds in this article.

Lemma 4.1 Let P ∈ P, and let U ⊆ P be an open neighbourhood of P. Then there is c_{1} = c_{1}(P, U) > 0, such that for every δ ∈ (0, 1/4] and for all large n (say for n ≥ n_{0}(P, U, δ)), there is Q_{n} ∈ U, such that the following holds:

nH(P, Q_{n}) ≤ \frac{1}{2}| log(11δ)| and \frac{n^{1/3}}{c_{1}| log(11δ)|^{1/3}} |a(P) − a(Q_{n})| > 4.  (4.1)

Proof. Choose a ball N ⊆ U (with respect to the metric d) centered at P. Let r denote the radius of N. Let c_{1} > 0 be small enough (to be specified below). Take δ ∈ (0, 1/4]. We abbreviate

β_{n} = \frac{n^{1/3}}{c_{1}| log(11δ)|^{1/3}} > 0.  (4.2)

Take a fixed, compactly supported ϕ ∈ C^{1}(ℝ) with ϕ(0) = 1, 0 ≤ ϕ ≤ 1, and

∥ϕ′∥_{∞}∥f_{P} ∥_{∞} < r.  (4.3)

For ϵ > 0, we set

Ξ_{ϵ}(x) = ϵϕ (\frac{x − a(P)}{ϵ}) .  (4.4)

We set

ρ_{P}^{+} = \frac{f_{P}^{+}}{f_{P}^{+} + f_{P}^{−}} ,  ρ_{P}^{−} = \frac{f_{P}^{−}}{f_{P}^{+} + f_{P}^{−}};  (4.5)

at least in some compact neighbourhood V_{P} of a(P), these functions are well defined with values in [1/3, 2/3]. For all small ϵ > 0, Ξ_{ϵ} is supported in such a neighbourhood V_{P}. We set

ϵ_{n} = c_{2}| log(11δ)|^{1/3}n^{−1/3},  (4.6)

where c_{2} = c_{2}(P, ϕ) = (∥f_{P} ∥_{∞}∥ϕ∥_{2}^{2})^{−1/3}. Let Q_{n} be defined by its density f_{Q_{n}}, where

f_{Q_{n}}^{+} = (1 + Ξ_{ϵ_{n}}ρ_{P}^{−})f_{P}^{+},  (4.7)
f_{Q_{n}}^{−} = (1 − Ξ_{ϵ_{n}}ρ_{P}^{+})f_{P}^{−},  (4.8)
f_{Q_{n}}(x, y) = f_{Q_{n}}^{+}(x)1_{{y=1}} + f_{Q_{n}}^{−}(x)1_{{y=−1}}.  (4.9)

Here Ξ_{ϵ_{n}}ρ_{P}^{±} is to be interpreted as 0 outside the support of Ξ_{ϵ_{n}}. Note that for all large n, f_{Q_{n}}^{±} is well defined. As a consequence of the assumptions (1.9) and (1.10), one sees that f_{P}^{+}(a(P)) = f_{P}^{−}(a(P)) > 0. For large n, ϵ_{n} is small, thus f_{Q_{n}}^{±} is non-negative, and f_{Q_{n}} is a probability density. Furthermore, using (4.3) and |ρ_{P}^{∓}f_{P}^{±}| ≤ ∥f_{P} ∥_{∞}, one sees that d(Q_{n}, P) < r and thus Q_{n} ∈ N ⊆ U hold for all large n. We calculate for (x, y) ∈ Ω:

\frac{dQ_{n}}{dP} (x, y) = 1 + (1_{\{y=1\}}ρ_{P}^{−}(x) − 1_{\{y=−1\}}ρ_{P}^{+}(x))Ξ_{ϵ_{n}}(x).  (4.10)

For |t − 1| ≤ 1/2, one has − log t + t − 1 ≤ |t − 1|^{2}. So

H(P, Q_{n}) = E_{P} [− log \frac{dQ_{n}}{dP} + \frac{dQ_{n}}{dP} − 1] ≤ E_{P} [(\frac{dQ_{n}}{dP} − 1)^{2}]  (4.11)

for |\frac{dQ_{n}}{dP} − 1| ≤ 1/2, which holds for all large n. Note that |Ξ_{ϵ_{n}}| ≤ ϵ_{n}. For all large n, ρ_{P}^{±} ∈ [1/3, 2/3] holds on the support of Ξ_{ϵ_{n}}. Then one has

\frac{1}{3} ≤ |1_{\{y=1\}}ρ_{P}^{−}(x) − 1_{\{y=−1\}}ρ_{P}^{+}(x)| ≤ \frac{2}{3}  (4.12)

on the support of Ξ_{ϵ_{n}}, and therefore

(\frac{dQ_{n}}{dP} − 1)^{2} ≤ (\frac{2}{3})^{2} Ξ_{ϵ_{n}}^{2}(X).  (4.13)

We get the following “O(ϵ_{n}^{3})” estimate for the relative entropy:

nH(P, Q_{n}) ≤ \frac{4}{9}nE_{P} [Ξ_{ϵ_{n}}^{2}(X)] ≤ \frac{4}{9}n∥f_{P} ∥_{∞}∥Ξ_{ϵ_{n}}∥_{2}^{2} ≤ \frac{1}{2}n∥f_{P} ∥_{∞}∥ϕ∥_{2}^{2}ϵ_{n}^{3} ≤ \frac{1}{2}| log(11δ)|

(4.14)

by the choice (4.6) of ϵ_{n}.

(As a side remark, note that the estimate (4.14) relies on our choice to take the Lebesgue measure λ_{[0,1]} in the reference measure. In some cases with arbitrary reference measures, it would break down.)

On the other hand, defining ρ_{Q_{n}}^{±} in analogy to (4.5),

ρ_{Q_{n}}^{+} = (1 + Ξ_{ϵ_{n}}ρ_{P}^{−})ρ_{P}^{+},  (4.15)
ρ_{Q_{n}}^{−} = (1 − Ξ_{ϵ_{n}}ρ_{P}^{+})ρ_{P}^{−}  (4.16)

follows from (4.7) and (4.8), using f_{Q_{n}}^{+} + f_{Q_{n}}^{−} = f_{P}^{+} + f_{P}^{−}. Using ρ_{P}^{−}(a(P)) = ρ_{P}^{+}(a(P)) = ρ_{Q_{n}}^{+}(a(Q_{n})) = 1/2 and (4.15), we get

\frac{ϵ_{n}}{4} = \frac{1}{4}|Ξ_{ϵ_{n}}(a(P))|
= |Ξ_{ϵ_{n}}(a(P)) ρ_{P}^{−}(a(P)) ρ_{P}^{+}(a(P))|
= |ρ_{P}^{+}(a(P)) − ρ_{Q_{n}}^{+}(a(P))|
= |ρ_{Q_{n}}^{+}(a(Q_{n})) − ρ_{Q_{n}}^{+}(a(P))|
≤ ∥(ρ_{Q_{n}}^{+})′∥_{∞,V_{P}} |a(Q_{n}) − a(P)|.  (4.17)

Taking the derivative of (4.15) and taking a supremum over V_{P}, we see that ∥(ρ_{Q_{n}}^{+})′∥_{∞,V_{P}} is bounded by a constant c_{3}(P, ϕ) > 0 for all large n; note that ∥Ξ′_{ϵ_{n}}∥_{∞} = ∥ϕ′∥_{∞} does not depend on n. We obtain

β_{n}|a(Q_{n}) − a(P)| ≥ β_{n} \frac{ϵ_{n}}{4c_{3}(P)} = \frac{n^{1/3}}{c_{1}| log(11δ)|^{1/3}} \frac{c_{2}| log(11δ)|^{1/3}n^{−1/3}}{4c_{3}(P, ϕ)} > 4  (4.18)

when we choose

0 < c_{1}(P, U) < \frac{c_{2}(P, ϕ)}{16c_{3}(P, ϕ)};  (4.19)

recall the choices (4.2) and (4.6) of β_{n} and ϵ_{n}. The statements (4.18) and (4.14) together are just the claim (4.1).

□

Proof of Theorem 1.1. Take a fixed P ∈ U, and take c_{1}(U) = c_{1}(P, U) > 0 from Lemma 4.1. Then Lemma 4.1 guarantees that the hypothesis (3.1) of Lemma 3.1 holds with P_{n} = P, where β_{n} is again given by (4.2). Thus Lemma 3.1 yields the claim (1.11).

□

Proof of Theorem 1.2. P with the metric d is indeed a Baire space, and a : P → (0, 1) is continuous. Note that the total variation distance is continuous with respect to d.

We check that Lemma 3.2 is applicable with δ = 1/4. Let P ∈ P, and let N be a neighbourhood of P in P. We apply Lemma 4.1 to obtain a sequence (Q_{n})_{n} in P such that (4.1) holds. Hence, we get for all large n (say for n ≥ c_{4}(P, U)):

β_{n}|a(P) − a(Q_{n})| ≥ \frac{n^{1/3}}{c_{1}(P, U)| log(11δ)|^{1/3}} |a(P) − a(Q_{n})| > 4  (4.20)

by (1.13). Together with the entropy bound in (4.1), this shows that Lemma 3.2 is indeed applicable, and it yields the claim (1.14).

□

Remark. Note that this proof would break down if we had taken β_{n} on the “critical” scale: “β_{n} = const ·n^{1/3}”: Indeed, the constant c_{1}(P, U) depends on U (and it really diverges as U gets smaller), but β_{n} must not depend on the choice of U. This breakdown has to occur, since Theorem 1.3 shows that the claim (1.14) of Theorem 1.2 cannot hold anymore on the critical scale β_{n} = const ·n^{1/3}.

5 Optimal estimators for thresholds

In this section, we prove Theorem 1.3. The optimal estimators, whose errors asymptotically meet the border permitted by the lower bounds, are constructed by a two-step procedure: In the first step (Lemma 5.1 below), we use the empirical risk minimizer to obtain a “starting estimator”, which yields error terms roughly on the scale n^{−1/3}. The second step (Lemma 5.2 below) constructs a refined family of estimators, based on a starting approximation a_{0}.

Let (X_{i}, Y_{i}) : Ω^{n} → Ω again denote the canonical projections.

Lemma 5.1 There is a sequence of estimators â_{n} : Ω^{n} → [0, 1], n ∈ ℕ, such that for all P ∈ P, there is a neighbourhood N (P) of P in P, such that the following holds:

lim_{L→∞} sup_{Q∈N (P)} lim_{n→∞} Q^{n}[|â_{n} − a(Q)| ≥ Ln^{−1/3}] = 0.  (5.1)

Proof. Consider the empirical risk minimizers â_{n}, n ∈ ℕ, given by (1.5). We abbreviate f_{Q}^{Σ} = f_{Q}^{+} + f_{Q}^{−}. Take P ∈ P and

N (P) = {Q ∈ P : 2|(ρ_{Q}^{+})′(a(Q))| > |(ρ_{P}^{+})′(a(P))|, 2f_{Q}^{Σ}(a(Q)) > f_{P}^{Σ}(a(P))},  (5.2)

where ρ_{Q}^{+} is again defined as in (4.5). By the transversality of the intersection point a(Q) of f_{Q}^{+} and f_{Q}^{−}, the maps Q ↦ (ρ_{Q}^{+})′(a(Q)) and Q ↦ f_{Q}^{Σ}(a(Q)), Q ∈ N (P), are continuous. Furthermore, f_{P}^{Σ}(a(P)) > 0 and |(ρ_{P}^{+})′(a(P))| > 0 hold. Using these facts, one sees that N (P) is a neighbourhood of P.

Take Q ∈ N (P). By Theorem 2.2 in Mohammadi and van de Geer’s article [MvdG03], we know that

n^{1/3}(â_{n} − a(Q)) →^{L} [(ρ_{Q}^{+})′(a(Q))\sqrt{f_{Q}^{Σ}(a(Q))}]^{−2/3} Z  (5.3)

as n → ∞ for some continuous random variable Z, not depending on Q (with respect to some probability measure ℙ). We set

α = inf_{Q∈N (P)} [(ρ_{Q}^{+})′(a(Q))\sqrt{f_{Q}^{Σ}(a(Q))}]^{2/3} .  (5.4)

Note that α > 0 by the choice (5.2) of N (P). We obtain the claim (5.1):

sup_{Q∈N (P)} lim_{n→∞} Q[|â_{n} − a(Q)| ≥ Ln^{−1/3}] = sup_{Q∈N (P)} ℙ [Z ≥ [(ρ_{Q}^{+})′(a(Q))\sqrt{f_{Q}^{Σ}(a(Q))}]^{2/3} L]
≤ ℙ [Z ≥ αL] ⟶^{L→∞} 0.  (5.5)
□

The next lemma is used to construct the refined estimators in Theorem 1.3. Here is the idea: Given a starting approximation a_{0} for a(Q) with an error on the scale n^{−1/3}, consider all data points in a neighbourhood of size Ln^{−1/3}, where L is large, but fixed. Then construct a regression line through the data points in this neighbourhood, and take the intersection of this regression line with the x-axis as the refined estimator.

Lemma 5.2 There is a family of estimators (â_{n,L,a_{0}} : Ω^{n} → ℝ)_{n∈ℕ, L>0, a_{0}∈(0,1)} with the following property: For all P ∈ P, there is a neighbourhood N ⊆ P of P, such that for all T > 0 one has

lim_{L→∞} sup_{Q∈N} lim sup_{n→∞} sup_{\begin{matrix}a_{0}∈(0,1) \\ |a_{0}−a(Q)|≤Ln^{−1/3} \end{matrix}} Q^{n}[n^{1/3}|â_{n,L,a_{0}} − a(Q)| > T] = 0.  (5.6)

Proof. Given n ∈ ℕ, L > 0, and a_{0} ∈ (0, 1), we introduce the abbreviations X̃_{i} = X_{i}−a_{0}, M = Ln^{−1/3}, I_{M} = [−M, M], and we define the random set

J = {j : 1 ≤ j ≤ n, X̃_{j} ∈ I_{M}}.  (5.7)

We define the estimator â_{n,L,a_{0}} as follows: Consider the regression line ℓ (equation y = b̂_{1}x + b̂_{2}) through the points (X̃_{j}, Y_{j}), j ∈ J, provided it is well defined, i.e. provided there are at least two different X̃_{j_{1}} ≠ X̃_{j_{2}}, j_{1}, j_{2} ∈ J. If b̂_{1} ≠ 0, we set

â_{n,L,a_{0}} = a_{0} − \frac{b̂_{2}}{b̂_{1}} .  (5.8)

Geometrically, this means that â_{n,L,a_{0}} is the intersection of the real axis with the regression line through the points (X_{j}, Y_{j}), where only the points with |X_{j} − a_{0}| ≤ Ln^{−1/3} are taken, whenever this intersection is well defined. If the regression line ℓ is not well-defined, or if b̂_{1} = 0, we set â_{n,L,a_{0}} = a_{0}, just to have a definite value in this case, too.

We abbreviate for Q ∈ P:

s_{Q} = f_{Q}^{Σ}(a(Q)),  (5.9)
t_{Q} = (f_{Q}^{+})′(a(Q)) − (f_{Q}^{−})′(a(Q)),  (5.10)

where again f_{Q}^{Σ} = f_{Q}^{+} + f_{Q}^{−}. Let P ∈ P, and take the following neighbourhood of P:

N = \{Q ∈ P : \begin{matrix}|t_{Q}| > |t_{P} |/2, s_{Q} < 2s_{P} , d(P, Q) < 1, \\ a(Q) > a(P)/2, 1 − a(Q) > (1 − a(P))/2 \end{matrix} \} .  (5.11)

Take T > 0 and δ > 0. Let L be large enough (more specifically, so large that

2L ≥ T,  (5.12)
L^{3} ≥ S^{2} := \frac{5c_{5}}{δ} ,  (5.13)
c_{6} \frac{S}{\sqrt{L}} < \frac{T}{5}  (5.14)

hold with some positive constants c_{5} = c_{5}(N) and c_{6} = c_{6}(N), to be specified below). We claim that for all Q ∈ N, one has

lim sup_{n→∞} sup_{\begin{matrix}a_{0}∈(0,1) \\ |a_{0}−a(Q)|≤Ln^{−1/3} \end{matrix}} Q^{n}[n^{1/3}|â_{n,L,a_{0}} − a(Q)| > T] ≤ δ.  (5.15)

The claim (5.6) of the lemma then follows immediately from the statement (5.15). To prove (5.15), let Q ∈ N. For every n ∈ ℕ and for every a_{0} ∈ (0, 1) with

|a_{0} − a(Q)| ≤ Ln^{−1/3},  (5.16)

we are going to define an event B = B(Q, n, a_{0}, S, L) ⊆ Ω^{n} with the property

Q^{n}[B(Q, n, a_{0}, S, L)] ≥ 1 − δ.  (5.17)

(This is done in (5.29), below.) We then show that for all large n (say for n ≥ n_{0}(Q, N , S, L), but uniformly in the choice of a_{0}), one has

B(Q, n, a_{0}, S, L) ⊆ {n^{1/3}|â_{n,L,a_{0}} − a(Q)| ≤ T }.  (5.18)

Once we have proven (5.17) and (5.18), the claim (5.15) is an immediate consequence.

Take Q ∈ N and a_{0} ∈ (0, 1) with the constraint (5.16). It is convenient to shift quantities by a_{0}: We set

ã = ã(Q) = a(Q) − a_{0},  (5.19)
f̃_{Q}^{±}(x) = f_{Q}^{±}(x + a_{0}),  (5.20)
f̃_{Q}^{Σ}(x) = f_{Q}^{Σ}(x + a_{0}).  (5.21)

In particular, note that

|ã| ≤ M = Ln^{−1/3},  (5.22)

and that for all large n (uniformly in a_{0} and Q ∈ N with the constraint (5.16)), f̃_{Q}^{±} is defined at least on I_{M}.

The coefficients b̂_{1} and b̂_{2} of the regression line ℓ are determined by the linear system

Ab̂ = c,  (5.23)

where

A = ( \begin{matrix}∑_{j∈J} X̃_{j}^{2} & ∑_{j∈J} X̃_{j} \\ ∑_{j∈J} X̃_{j} & |J| \end{matrix} ) , b̂ = ( b̂_{1} ; b̂_{2} ) , c = ( \begin{matrix}∑_{j∈J} X̃_{j}Y_{j} \\ ∑_{j∈J} Y_{j} \end{matrix} ) .  (5.24)

We introduce the (normalized) difference of the coefficient matrix from its expected value:

( \begin{matrix}M^{5/2}Δ_{11} & M^{3/2}Δ_{12} \\ M^{3/2}Δ_{21} & M^{1/2}Δ_{22} \end{matrix} ) = \frac{1}{\sqrt{n}}(A − E_{Q^{n}}[A]),  (5.25)
( \begin{matrix}M^{3/2}Γ_{1} \\ M^{1/2}Γ_{2} \end{matrix} ) = \frac{1}{\sqrt{n}}(c − E_{Q^{n}} [c]).  (5.26)

Our reason to normalize the Δ_{ij} and Γ_{i} in this way is the following bound on the variances (to be read element-wise):

Var_{Q^{n}} [( \begin{matrix}Δ_{11} & Δ_{12} \\ Δ_{21} & Δ_{22} \end{matrix} )] ≤ E_{Q^{n}} [1_{\{X̃_{1}∈I_{M} \}} ( \begin{matrix}X̃_{1}^{4}/M^{5} & X̃_{1}^{2}/M^{3} \\ X̃_{1}^{2}/M^{3} & 1/M \end{matrix} )] ≤ ( \begin{matrix}c_{5} & c_{5} \\ c_{5} & c_{5} \end{matrix} ) , (5.27)

Var_{Q^{n}} [( \begin{matrix}Γ_{1} \\ Γ_{2} \end{matrix} )] ≤ E_{Q^{n}} [1_{\{X̃_{1}∈I_{M} \}} ( \begin{matrix}X̃_{1}^{2}Y_{1}^{2}/M^{3} \\ Y_{1}^{2}/M \end{matrix} )] ≤ ( \begin{matrix}c_{5} \\ c_{5} \end{matrix} ) ,  (5.28)

with some constant c_{5} = c_{5}(N) > 0. We used that the density f_{Q} of (X_{i}, Y_{i}) is uniformly bounded for Q ∈ N.

Here is the definition of the event B:

B(Q, n, a_{0}, S, L) = {|Δ_{i,j}| ≤ S, |Γ_{i}| ≤ S (i, j ∈ {1, 2})}.  (5.29)

By Chebyshev’s inequality, (5.27), (5.28), and the choice (5.13) of S imply the claim (5.17):

Q^{n}[B(Q, n, a_{0}, S, L)^{c}] ≤ \frac{5c_{5}}{S^{2}} = δ.  (5.30)

The factor “5” arises, since there are 5 random variables involved; (recall Δ_{12} = Δ_{21}).

In the rest of this proof, we verify the claim (5.18) for all large n (uniformly in a_{0}). So assume that the event B(Q, n, a_{0}, S, L) holds.

The system (5.23) is equivalent to

( \begin{matrix}∫_{I_{M}} x^{2}f̃_{Q}^{Σ}(x) dx + \frac{M^{5/2}Δ_{11}}{\sqrt{n}} & ∫_{I_{M}} xf̃_{Q}^{Σ}(x) dx + \frac{M^{3/2}Δ_{12}}{\sqrt{n}} \\ ∫_{I_{M}} xf̃_{Q}^{Σ}(x) dx + \frac{M^{3/2}Δ_{21}}{\sqrt{n}} & ∫_{I_{M}} f̃_{Q}^{Σ}(x) dx + \frac{M^{1/2}Δ_{22}}{\sqrt{n}} \end{matrix} ) b̂

= ( \begin{matrix}∫_{I_{M}} x(f̃_{Q}^{+}(x) − f̃_{Q}^{−}(x)) dx + \frac{M^{3/2}Γ_{1}}{\sqrt{n}} \\ ∫_{I_{M}} (f̃_{Q}^{+}(x) − f̃_{Q}^{−}(x)) dx + \frac{M^{1/2}Γ_{2}}{\sqrt{n}} \end{matrix} ) .  (5.31)

Let us introduce some notation, used in the Taylor approximations below. Variables ξ_{j} = ξ_{j}(x, ã, Q, a_{0}) denote some values between x and ã. Variables ϵ_{j} denote error terms which are bounded by N -dependent constants:

|ϵ_{j}| ≤ const(N),  (5.32)

and δ_{j} denote error terms which are bounded by

|δ_{j}| ≤ const ·σ(Q, 2M),  (5.33)

where

σ(Q, r) = max_{y=±1} sup_{|x_{1}−x_{2}|≤r} |∂_{1}f_{Q}(x_{1}, y) − ∂_{1}f_{Q}(x_{2}, y)| ⟶^{r→0} 0  (5.34)

denotes the modulus of continuity of ∂_{1}f_{Q}; recall that f_{Q} ∈ C^{1}(Ω). We emphasize that the constants “const(N)”, “const” in (5.32) and (5.33) must not depend on a_{0}. Recall that |ã| ≤ M. Let us approximate the integrals in (5.31) by Taylor’s formula.

∫_{I_{M}} x^{2}f̃_{Q}^{Σ}(x) dx = ∫_{−M}^{M} x^{2}(s_{Q} + (x − ã)(f̃_{Q}^{Σ})′(ξ_{1})) dx = \frac{2}{3}M^{3}s_{Q} + ϵ_{1}M^{4},  (5.35)
∫_{I_{M}} xf̃_{Q}^{Σ}(x) dx = ∫_{−M}^{M} x(s_{Q} + (x − ã)(f̃_{Q}^{Σ})′(ξ_{2})) dx = ϵ_{2}M^{3},  (5.36)
∫_{I_{M}} f̃_{Q}^{Σ}(x) dx = ∫_{−M}^{M}(s_{Q} + (x − ã)(f̃_{Q}^{Σ})′(ξ_{3})) dx = 2Ms_{Q} + ϵ_{3}M^{2},  (5.37)

∫_{I_{M}} x(f̃_{Q}^{+}(x) − f̃_{Q}^{−}(x)) dx = ∫_{−M}^{M} x(x − ã)((f̃_{Q}^{+})′(ξ_{4}) − (f̃_{Q}^{−})′(ξ_{4})) dx
= \frac{2}{3}M^{3}t_{Q} + δ_{2}M^{3} = ϵ_{4}M^{3},  (5.38)
∫_{I_{M}} (f̃_{Q}^{+}(x) − f̃_{Q}^{−}(x)) dx = ∫_{−M}^{M}(x − ã)((f̃_{Q}^{+})′(ξ_{5}) − (f̃_{Q}^{−})′(ξ_{5})) dx
= −2ãMt_{Q} + δ_{1}M^{2} = ϵ_{5}M^{2}.  (5.39)

We rewrite the system (5.31) as

( \begin{matrix}\frac{2}{3}M^{3}s_{Q} + ϵ_{1}M^{4} + \frac{M^{5/2}Δ_{11}}{\sqrt{n}} & ϵ_{2}M^{3} + \frac{M^{3/2}Δ_{12}}{\sqrt{n}} \\ ϵ_{2}M^{3} + \frac{M^{3/2}Δ_{21}}{\sqrt{n}} & 2Ms_{Q} + ϵ_{3}M^{2} + \frac{M^{1/2}Δ_{22}}{\sqrt{n}} \end{matrix} ) b̂

= ( \begin{matrix}\frac{2}{3}M^{3}t_{Q} + δ_{2}M^{3} + \frac{M^{3/2}Γ_{1}}{\sqrt{n}} \\ −2ãMt_{Q} + δ_{1}M^{2} + \frac{M^{1/2}Γ_{2}}{\sqrt{n}} \end{matrix} ) = ( \begin{matrix}ϵ_{4}M^{3} + \frac{M^{3/2}Γ_{1}}{\sqrt{n}} \\ ϵ_{5}M^{2} + \frac{M^{1/2}Γ_{2}}{\sqrt{n}} \end{matrix} );  (5.40)

both forms of the right hand side are useful below. Dividing the first row in (5.40) by (2/3)M^{3}s_{Q} and the second row by 2Ms_{Q}, we get the normalized system

( \begin{matrix}1 + M [\frac{3}{2} \frac{ϵ_{1}}{s_{Q}} + \frac{3}{2s_{Q}} \frac{Δ_{11}}{L^{3/2}} ] & \frac{3}{2} \frac{ϵ_{2}}{s_{Q}} + \frac{3}{2s_{Q}} \frac{Δ_{12}}{L^{3/2}} \\ M^{2} [ϵ_{6} + \frac{1}{2s_{Q}} \frac{Δ_{21}}{L^{3/2}} ] & 1 + M [ϵ_{7}M + \frac{1}{2s_{Q}} \frac{Δ_{22}}{L^{3/2}} ] \end{matrix} ) b̂

= \frac{t_{Q}}{s_{Q}} ( \begin{matrix}1 + \frac{3}{2} \frac{δ_{2}}{t_{Q}} + \frac{3}{2t_{Q}} \frac{Γ_{1}}{L^{3/2}} \\ −ã + M (\frac{δ_{1}}{2t_{Q}} + \frac{1}{2t_{Q}} \frac{Γ_{2}}{L^{3/2}} ) \end{matrix} ) = \frac{t_{Q}}{s_{Q}} ( \begin{matrix}ϵ_{8} + ϵ_{9} \frac{Γ_{1}}{L^{3/2}} \\ M [ϵ_{10} + ϵ_{11} \frac{Γ_{2}}{L^{3/2}} ] \end{matrix} ) .  (5.41)

Heuristically, one should view (5.41) as a perturbation of the system

( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) ( \begin{matrix}b_{1} \\ b_{2} \end{matrix} ) = \frac{t_{Q}}{s_{Q}} ( \begin{matrix}1 \\ −ã \end{matrix} ) ,  (5.42)

for which one knows −b_{2}/b_{1} = ã.

By (5.13), (5.14), and the definition (5.29) of the event B, we know for i, j ∈ {1, 2}:

\frac{|Δ_{i,j}|}{L^{3/2}}, \frac{|Γ_{i}|}{L^{3/2}} ≤ \frac{S}{L^{3/2}} ≤ 1  (5.43)

and

|\frac{3}{2t_{Q}} \frac{Γ_{i}}{L^{3/2}} | ≤ c_{6} \frac{S}{L^{3/2}} ≤ \frac{T}{5L},  (5.44)

when we choose the constant in (5.14) to be c_{6} = c_{6}(N) = sup_{Q∈N} |3/(2t_{Q})| ≤ 3|t_{P} |^{−1} < ∞; recall the definition (5.11) of N, and recall that we assume the event B to hold.

For M ≤ 1, we rewrite (5.41) in the following form:

( \begin{matrix}1 + Mϵ_{12} & ϵ_{13} \\ M^{2}ϵ_{14} & 1 + Mϵ_{15} \end{matrix} ) b̂ = \frac{t_{Q}}{s_{Q}} ( \begin{matrix}1 + ϵ_{16}δ_{2} + ϵ_{17} \frac{T}{L} \\ −ã + M [ϵ_{18}δ_{1} + ϵ_{19} \frac{T}{L}] \end{matrix} ) = \frac{t_{Q}}{s_{Q}} ( \begin{matrix}ϵ_{20} \\ Mϵ_{21} \end{matrix} ) , (5.45)

where |ϵ_{19}| < 1/5 and |ϵ_{17}| ≤ 1/5.

Let us consider the asymptotics of b̂_{2}/b̂_{1} as n → ∞, i.e. as M = Ln^{−1/3} → 0. For all large n (uniformly in a_{0}), the system (5.45) is nonsingular; recall that the error terms ϵ_{j} are bounded uniformly in a_{0}. We get for all large n:

\frac{b̂_{2}}{b̂_{1}} = \begin{matrix}| & \begin{matrix}1 + Mϵ_{12} & ϵ_{20} \\ M^{2}ϵ_{14} & −ã + M [ϵ_{18}δ_{1} + ϵ_{19} \frac{T}{L}] \end{matrix} & | \\ | & \begin{matrix}1 + ϵ_{16}δ_{2} + ϵ_{17} \frac{T}{L} & ϵ_{13} \\ Mϵ_{21} & 1 + Mϵ_{15} \end{matrix} & | \end{matrix}.  (5.46)

Let d_{2} and d_{1} denote the determinant in the numerator and denominator of the right hand side in (5.46), respectively. Recall that the error terms δ_{1}, δ_{2} converge to 0 as n → ∞, uniformly in a_{0}; see (5.33) and (5.34). Using |ϵ_{19}|, |ϵ_{17}| ≤ 1/5 < 1/4, we get for all large n (uniformly in a_{0}):

| − ã − d_{2}| ≤ \frac{MT}{4L} ,  (5.47)
|1 − d_{1}| ≤ \frac{T}{4L},  (5.48)
|1 − \frac{1}{d_{1}} | ≤ \frac{T}{2L}.  (5.49)

We used T ≤ 2L in the last step.

Using the definition (5.8) of â_{n,L,a_{0}} and (5.46), we conclude, still for large n (uniformly in a_{0}):

|â_{n,L,a_{0}} − a(Q)| = |−ã − \frac{b̂_{2}}{b̂_{1}} | = |−ã − \frac{d_{2}}{d_{1}} |
≤ |ã|\frac{T}{2L} + \frac{MT}{4L} + \frac{MT}{4L} \frac{T}{2L} ≤ \frac{MT}{L} = T n^{−1/3};  (5.50)

recall that |ã| ≤ M and T ≤ 2L. Thus the claim (5.18) holds for all large n, uniformly in a_{0}.

□

We now use Lemma 5.1 to obtain the starting approximation a_{0} required by Lemma 5.2:

Proof of Theorem 1.3. Let us abbreviate Z_{j} = (X_{j}, Y_{j}). Let n ∈ ℕ, n ≥ 2, and L > 0. We construct the estimator â_{n,L} by a two-step procedure: We split the sample Z_{1}, …, Z_{n} into two halves Z_{1}, …, Z_{m} and Z_{m+1}, …, Z_{2m}, where we abbreviate m = m(n) = ⌊n/2⌋. (For odd n, we drop one data point at the end.) We then use the first half of the data to get a “rough” estimate â_{m} = â_{m}(Z_{1}, …, Z_{m}) by Lemma 5.1. Using this as a “starting estimate”, we refine it by Lemma 5.2, applied to the second half of the data:

â_{n,L} = â_{m,L,â_{m}}(Z_{m+1}, …, Z_{2m}).  (5.51)

It is important to split the data into two disjoint pieces, since then â_{m} is independent from (Z_{m+1}, …, Z_{2m}); thus we have a good control on the distribution of â_{m,L,â_{m}}(Z_{m+1}, …, Z_{2m}) conditioned on â_{m}(Z_{1}, …, Z_{m}). By a slight abuse of notation, we abbreviate â_{m,L,a_{0}} = â_{m,L,a_{0}}(Z_{m+1}, …, Z_{2m}).

Let P ∈ P, and let N be the intersection of the two neighbourhoods of P that were constructed in Lemma 5.1 and Lemma 5.2. Let T > 0 and δ > 0. By the same two lemmas, we know for all large L:

sup_{Q∈N (P)} lim_{n→∞} Q^{n}[A(Q, n, L)^{c}] < \frac{δ}{2}  (5.52)

with the events

A(Q, n, L) = {|â_{m} − a(Q)| ≤ Lm^{−1/3}},  (5.53)

and

sup_{Q∈N} lim sup_{n→∞} sup_{\begin{matrix}a_{0}∈(0,1) \\ |a_{0}−a(Q)|≤Lm^{−1/3} \end{matrix}} Q^{n} [m^{1/3}|â_{m,L,a_{0}} − a(Q)| > \frac{T}{2} ] < \frac{δ}{2}.  (5.54)

Note that for all large n (say for n ≥ n_{0}(Q, L)), we have â_{m} ∈ (0, 1) on the event A(Q, n, L). Let Q ∈ N, and let n ∈ ℕ be large enough. Using n^{1/3} ≤ 2m^{1/3} in the first step, we get

Q^{n} [n^{1/3}|â_{n,L} − a(Q)| > T ]

≤ Q^{n} [m^{1/3}|â_{n,L} − a(Q)| > \frac{T}{2} ]

≤ E_{Q^{n}} [Q^{n} [m^{1/3}|â_{n,L} − a(Q)| > \frac{T}{2} | â_{m}] 1_{A(Q,n,L)}] + Q^{n} [A(Q, n, L)^{c}]

≤ E_{Q^{n}} [Q^{n} [m^{1/3}|â_{m,L,â_{m}} − a(Q)| > \frac{T}{2} | â_{m}] 1_{A(Q,n,L)}] + \frac{δ}{2}.  (5.55)

Using the independence structure and (5.54), we know for almost all a_{0} with |a_{0} −a(Q)| ≤ Lm^{−1/3} (“almost all” with respect to the law of â_{m}):

Q^{n} [m^{1/3}|â_{m,L,â_{m}} − a(Q)| > \frac{T}{2} | â_{m} = a_{0}] = Q^{n} [m^{1/3}|â_{m,L,a_{0}} − a(Q)| > \frac{T}{2} ] ≤ \frac{δ}{2}.

(5.56)

Combining (5.55) and (5.56), we conclude

Q^{n} [n^{1/3}|â_{n,L} − a(Q)| > T ] ≤ δ.  (5.57)

This finishes the proof of the claim (1.15).

□

Let us finally describe a simple counter-example, showing that the “lim sup_{n→∞}” in the claim (1.14) of Theorem 1.2 cannot be replaced by “lim inf_{n→∞}”.

Let us take â_{n} to be constant estimators in the following way: For all k ∈ ℕ_{0} and n ∈ [2^{k}, 2^{k+1}[∩ℕ, set â_{n} = (n − 2^{k})2^{−k}. Then, whatever the value a(P) ∈ [0, 1] is, we have the following: For all k ∈ ℕ_{0} there is n ∈ [2^{k}, 2^{k+1}[∩ℕ with |â_{n} − a(P)| ≤ 2^{−k} ≤ 2/n. But then

lim inf_{n→∞} P^{n}[β_{n}|â_{n} − a(P)| > 1] = 0  (5.58)

whenever β_{n} = o(n).

Intuitively speaking, the counter-example uses the following idea: If you have many non-running clocks, one for every minute of a day, all showing different times, then one of them will show the correct time, up to 1 minute.

Acknowledgment: We are grateful to S. A. van de Geer and W. R. van Zwet for their support and for interesting discussions. Furthermore, the authors would like to thank D. Donoho for interesting discussions, too.

References

[BB02] Peter L. Bartlett and Jonathan Baxter. Estimation and approximation bounds for gradient-based reinforcement learning. J. Comput. System Sci., 64(1):133– 150, 2002. Special issue on COLT 2000 (Palo Alto, CA).

[FS98] Yoav Freund and Robert E. Schapire. Large margin classification using the perceptron algorithm. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory (Madison, WI, 1998), pages 209–217 (electronic), New York, 1998. ACM.

[KP90] JeanKyung Kim and David Pollard. Cube root asymptotics. Ann. Statist., 18(1):191–219, 1990.

[MBG02] Llew Mason, Peter L. Bartlett, and Mostefa Golea. Generalization error of combined classifiers. J. Comput. System Sci., 65(2):415–438, 2002.

[MvdG03] Leila Mohammadi and Sara van de Geer. On threshold-based classification rules. Institute of Mathematical Statistics, Lecture Notes Monograph Series, Mathematical Statistics and Applications: Festschrift for Constance van Eeden, 42:261–280, 2003.

[PvZ96] Hein Putter and Willem R. van Zwet. Resampling: consistency of substitution estimators. Ann. Statist., 24(6):2297–2318, 1996.

[SFBL98] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: a new explanation for the effectiveness of voting methods. Ann. Statist., 26(5):1651–1686, 1998.

[SS98] Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory (Madison, WI, 1998), pages 80–91 (electronic), New York, 1998. ACM.

[vdG00] Sara A. van de Geer. Applications of empirical process theory. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2000.

[vdVW96] Aad W. van der Vaart and Jon A. Wellner. Weak convergence and empirical processes. Springer Series in Statistics. Springer-Verlag, New York, 1996. With applications to statistics.

University of Leiden, P.O. Box 9512, 2300 RA Leiden, The Netherlands.

e-mails: merkl@math.leidenuniv.nl, leila@math.leidenuniv.nl