Uniform Laws of Large Numbers - Stanford University

Uniform Laws of Large Numbers

John Duchi Stats 300b ? Winter Quarter 2021

Uniform Laws of Large Numbers

5?1

Outline

Uniform laws of large numbers "argmax" theorem Covering and bracketing numbers Metric entropy

Reading:

van der Vaart Chapters 5.2, 19.1, 19.2. Wainwright Chapters 4, 5.1 cover the material but rely on some concentration inequalities we will cover in coming lectures.

Uniform Laws of Large Numbers

5?2

Uniform laws of large numbers

Let F be a collection of functions f : X R. Then F satisfies a ULLN (for a distribution P) if

Pn - P F := sup |Pnf - Pf | p 0.

f F

Example (Glivenko Cantelli)

Let F = {f (x) = 1 {x t}}tR. Then

sup |Pnf - Pf | = sup |Pn(X t) - P(X t)| p 0.

f F

t R

More is possible: Dvoretzky-Kiefer-Wolfowitz inequality gives

P sup |Pn(X t) - P(X t)| 2 exp -2n 2 .

t

Uniform Laws of Large Numbers

5?3

Consistency and argmax theorems

ULLNs make consistency results much easier easy "generic" consistency result for loss minimization is a parameter space, : ? X R a loss population loss (risk) L() = P (, X ) and Ln() = Pn (, X )

Proposition

If F = { (, ?)} satisfies the ULLN and

Ln(n) inf Ln() + oP (1) then L(n) p inf L()

Uniform Laws of Large Numbers

5?4

The argmax theorem

Assume for all > 0, there is > 0 such that

L() L( ) + whenever d(, )

Proposition (Argmax)

If Ln(n) inf Ln() + oP (1) and { (, ?)} satisfies the

ULLN, then

n p .

Uniform Laws of Large Numbers

5?5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download