11 - Classes Too Large to Be Donsker

Summary

Universal Lower Bounds

This chapter is primarily about asymptotic lower bounds for ∥P_n − P∥_F on certain classes F of functions, as treated in Chapter 8, mainly classes of indicators of sets. Section 11.2 will give some upper bounds which indicate the sharpness of some of the lower bounds. Section 11.4 gives some relatively difficult lower bounds on classes such as the convex sets in ℝ³ and lower layers in ℝ². In preparation for this, Section 11.3 treats Poissonization and random “stopping sets” analogous to stopping times. The present section gives lower bounds in some cases which hold not only with probability converging to 1, but for all possible P_n. Definitions are as in Sections 3.1 and 8.2, with P:= U(I^d) = λ^d = Lebesgue measure on I^d. Specifically, recall the classes G(α, K, d):= G_{α,K, d} of functions on the unit cube I^d ⊂ ℝ^d with derivatives through αth order bounded by K, and the related families C(α, K, d) of sets (subgraphs of functions in G(α, K, d − 1)), both defined early in Section 8.2.

Theorem 11.1 (Bakhvalov) For P = U(I^d), any d = 1, 2, … and α > 0, there is a γ = γ (d, α) > 0 such that for all n = 1, 2,…, and all possible values of Pⁿ, we have ∥Pⁿ − P ∥G(α1,d) ≥ γn^−α/d.