090. Uniform laws of large numbers

Uniform laws of large numbers

랜덤변수의 fixed sequence 에만 적용되던 usual LLN 을 확장하여 uniform LLN 는 랜덤변수의 collection 들에 대해 uniform 하게 성립함. 이제 non-symptotic 결과물에 대해서도 설명할 것.

Motivation

• Detour: $\mathbb{P}\left(\right\{s\in S:{\lim }_{n\to \infty }{X}_n(s)=X(s)\left\}\right)=1$ 일 경우, $X_n\stackrel{a.s.}{\to }X$^[almost surely.]. 이때 $S$ 는 underlying sample space.

Cumulative distribution functions

랜덤변수 $X$ 가 cdf $F(t\in \mathbb{R})$ 을 보유한다. 우리가 collection $\{X_i{\}}_{i=1}^n$ 를 보유하며 이는 $X$ 의 $n$ 개의 $iid$ copy 들이라고 하자. $F$ 에 대한 natural estimate 는 empirical cdf 이며, 이 **empirical cdf **는 이하와 같다. 이 경우 population cdf 는 $F(t)=\mathbb{E}[I_{(-\infty ,t]}(X)]$ 로 표기될 수 있으므로, **empirical cdf **는 UE.

$${\hat{F}}_n(t)=\frac{1}{n}\sum _{i=1}^n{I}_{(-\infty ,t]}(X_i)\text{\hspace{1em}(empirical cdf)}$$

$\forall$ fixed $t\in \mathbb{R}$, 랜덤변수 ${\hat{F}}_n(t)$ 는 $F(t)$ 를 가지며, 모든 차수 (order) 의 moment 또한 가진다. 따라서 strong LLN 을 적용하는 것으로 ${\hat{F}}_n(t)\stackrel{a.s.}{\to }F(t)$ 임을 획득할 수 있다. 우리의 목적은 이 pointwise convergence 를 확장시켜 uniform convergence 가 성립함을 보이는 것. 특히 이하를 보이는 것이 주된 목적. 이 uniform convergence 결과는 실제로 성립하며 이의 이름은 Glivenko–Cantelli theorem.

$$\Vert {\hat{F}}_n-F{\Vert }_{\infty }=\underset{t\in \mathbb{R}}{\sup }|{\hat{F}}_n(t)-F(t)|\stackrel{a.s.}{⟶}0\text{\hspace{1em}(9.1.)}$$

이러한 uniform convergence 결과가 유의미한 이유는 무엇인가? 많은 estimation problem 이 cdf $F$ 를 실수 $\gamma (F)$ 로 mapping 하는 functional 표기법으로 치환될 수 있으니까. plug-in principle 은 이 unknown cdf $F$ 를 empirical cdf ${\hat{F}}_n$ 으로 대체하는 것으로 $\gamma ({\hat{F}}_n)$ 을 $\gamma (F) 의 estimate 로 인식할 수 있다는 것을 제시하고 있음. 예시 몇가지:

• Remark (Continuity of a functional)

우리가 $\Vert {\hat{F}}_n-F{\Vert }_{\infty }\to 0$ in probability 를 깨달았다면, 우리는 자연스럽게 functional $\gamma$ 가 sup-norm 에 비추었을 때 연속일 경우, $|\gamma (\widehat{F_n})-\gamma (F)|\to 0$ in probability 라는 것 또한 알 수 있다.

우리는 functional $\gamma$ 의 continuity 를 sup-norm $\Vert F-G{\Vert }_{\infty }=\underset{t\in \mathbb{R}}{\sup }|F(t)-G(t)|$ 에 기반하여 정의할 것이다. 더 정확하게 설명하자면, $\forall ϵ>0,\exists \delta >0:\Vert F-G{\Vert }_{\infty }<\delta \Rightarrow |\gamma (F)-\gamma (G)|\le ϵ$ 가 성립할 경우, functional $\gamma$ 는, in sup-norm, $F$ 에서 연속이다.

결과적으로 $\forall ϵ>0:\mathbb{P}(|\gamma ({\hat{F}}_n)-\gamma (F)|>ϵ)\le \mathbb{P}(||{\hat{F}}_n-F|{|}_{\infty }>\delta )$ 가 성립하며, 이를 통해, (9.1.) 의 Glivenko–Cantelli theorem 에 의해, $\mathbb{P}(\Vert {\hat{F}}_n-F{\Vert }_{\infty }>\delta )\to 0$ 이며, 이인즉 $|\gamma ({\hat{F}}_n)-\gamma (F)|\to 0$ in probability.

Uniform laws for more general function classes

unifrom LLN 의 좀 더 general 한 고려로 넘어가보자.

• $\mathcal{F}$: domain $\mathcal{X}$ 를 가지는 적분가능한 (integrable) real-valued function 의 class
• $\{X_i{\}}_{i=1}^n:over$\mathcal X$인어떤distribution$\mathbb P$ 로부터의 iid 샘플 의 collection

이제 이하의 랜덤변수를 생각해보자. 이는 over class $\mathcal{F}$, 샘플평균과 population 평균 간의 absolute deviation 을 uniformly 측정한다. 이때 만약 $n\to \infty$ 일 때 $\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}}$ 가 0 으로 in probability 하게 수렴하면, 우리는 $\mathcal{F}$ 를 Glivenko–Cantelli class 라고 명명한다.

$$\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}}=\underset{f\in \mathcal{F}}{\sup }\left|\frac{1}{n}\sum _{i=1}^{n}f(X_i)-\mathbb{E}[f(X)]\right|$$

Empirical risk minimization

empirical risk minimization 에서 quantity $\Vert {\vec{\mathbf{p}}}_n-\mathbb{P}{\Vert }_{\mathcal{F}}$ 가 유의미하게 사용됨. probability distribution 의 indexed family $\{{\mathbb{P}}_{\theta }:\theta \in \Omega \}$ 를 생각해보자. fixed 되었지만 unknown 인 임의의 ${\theta }^{\ast }\in \Omega$ 에 대해, distribution ${\mathbb{P}}_{{\theta }^{\ast }}$ 에서 iid 샘플을 추출한 상황을 생각하자. 여기서 ${\theta }^{\ast }$ 를 estimate 하는 가장 보편적인 방법은 패러미터 $\theta \in \Omega$ 와 샘플 $X\in \mathcal{X}$ 둘 사이의 fit 을 measure 하는 cost function ${\mathcal{L}}_{\theta }(X)$ 을 최소하하는 것. 그후 우리는 empirical risk ${\hat{R}}_n(\theta ,{\theta }^{\ast })=\frac{1}{n}{\sum }_{i=1}^n{\mathcal{L}}_{\theta }(X_i)$ 를 최소로 하는 estimate $\hat{\theta }$ 를 획득할 수 있다.

대조적으로 population risk $R(\theta ,{\theta }^{\ast })={\mathbb{E}}_{{\theta }^{\ast }}[{\mathcal{L}}_{\theta }(X)]$, 여기서 기댓값 ${\mathbb{E}}_{{\theta }^{\ast }}$는 over 샘플 $X\sim {\mathbb{P}}_{{\theta }^{\ast }}$ 에 대해서 구해졌다. 여기서 주로 논해지는 통계적 질문은 excess risk $E(\hat{\theta },{\theta }^{\ast })=R(\hat{\theta },{\theta }^{\ast })-\underset{\theta \in \Omega }{\inf }R(\theta ,{\theta }^{\ast })$ 를 어떻게 bound 할 것인가.

간단함을 위해 $R({\theta }_0,{\theta }^{\ast })=\underset{\theta \in \Omega }{\inf }R(\theta ,{\theta }^{\ast })$ 를 만족하는 ${\theta }_0\in \Omega$ 가 존재한다고 가정하자. 이 notation 을 사용할 경우 excess risk 는 이하와 같이 표기 가능.

$$E(\hat{\theta },{\theta }^{\ast })=\underset{T_1}{\underbrace{\{R(\hat{\theta },{\theta }^{\ast })-{\hat{R}}_n(\hat{\theta },{\theta }^{\ast })\}}}+\underset{T_2}{\underbrace{\{{\hat{R}}_n(\hat{\theta },{\theta }^{\ast })-{\hat{R}}_n({\hat{\theta }}_0,{\theta }^{\ast })\}}}+\underset{T3}{\underbrace{\{{\hat{R}}_n({\hat{\theta }}_0,{\theta }^{\ast })-R({\theta }_0,{\theta }^{\ast })\}}}\text{\hspace{1em}(excess risk)}$$

${\hat{R}}_n(\hat{\theta },{\theta }^{\ast })$ 를 minimize 한다는 $\hat{\theta }$ 의 정의 덕분에 우리는 $T_2\le 0$ 임은 알 수 있다.

$T_3=\frac{1}{n}{\sum }_{i=1}^n{\mathcal{L}}_{{\theta }_0}(X_i)-{\mathbb{E}}_X[{\mathcal{L}}_{{\theta }_0}(X)]$ 는 centered at 0 인 iid 랜덤변수들의 sample average 이다. 따라서 $T_3$ 를 analyze 함에 있어 Hoeffding’s inequality 사용 가능.

$T_1={\mathbb{E}}_X[{\mathcal{L}}_{\hat{\theta }}(X)]-\frac{1}{n}{\sum }_{i=1}^n{\mathcal{L}}_{\hat{\theta }}(X_i)$ 은 control 하기 좀 빡셈. 패러미터 $\hat{\theta }$ 가 랜덤이고, 샘플들 $\{X_i{\}}_{i=1}^n$ 에 의존하기 때문이다. 따라서 $T_1$ 을 control 하는 건 강력한 result 를 필요로 하며, 바로 여기에서 cost function $\mathcal{F}(\Omega )=\{x\mapsto {\mathcal{L}}_{\theta }(x),\theta \in {\Omega }_0\}$ 에 대해 (over) uniform LLN 를 적용한다. 이 notation 을 사용하면 이하와 같은 형식으로 $T_1$ 이 정리됨.

$$T_1\le \underset{\theta \in {\Omega }_0}{\sup }\left|\frac{1}{n}\sum _{i=1}^n{\mathcal{L}}_{\theta }(X_i)-{\mathbb{E}}_X[{\mathcal{L}}_{\theta }(X)]\right|=\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}(\Omega )}$$

$T_3$ 는 이 quantity 에 의해 dominated 되므로, 우리는 excess risk 가 $E(\hat{\theta },{\theta }^{\ast })\le 2\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}(\Omega )}$ 에 의해 bound 된다고 결론지을 수 있다.

이를 통해 우리는 empirical risk 최소화에 기반한 estimator analyzing 에 있어 가장 중요한 장애물은 loss class $\mathcal{F}(\Omega )$ 에 대해 uniform LLN 을 구축하는 일이라는 것을 알 수 있다.

A uniform law via Rademacher complexity

uniform law 의 구축에 필수불가결한 것은 function class $\mathcal{F}$ 의 Rademacher complexity. 아무 fixed class $x_1^n=(x_1,\cdots ,x_n)$ 에 대해, $\mathcal{F}(x_1^n)=\left\{\right(f(x_1),f(x_2),\dots ,f(x_n)):f\in \mathcal{F}\}$ 로서 주어지는 ${\mathbb{R}}^n$ 의 subset 을 생각하자. 이때 empirical Rademacher complexity 는 이하와 같다.

$$\mathcal{R}\left(\frac{\mathcal{F}(x_1^n)}{n}\right)={\mathbb{E}}_{ϵ}\left[\underset{f\in \mathcal{F}}{\sup }\right|\frac{1}{n}\sum _{i=1}^n{ϵ}_i\cdot f(x_i)\left|\right]\text{\hspace{1em}(empirical Rademacher complexity)}$$

• ${ϵ}_{1:n}$: iid Rademacher 랜덤변수.

랜덤변수의 collection $X_1^n=\{X_i{\}}_{i=1}^n$ 가 주어졌다면, empirical Rademacher complexity $\mathcal{R}\left(\frac{\mathcal{F}(x_1^n)}{n}\right)$ 또한 랜덤변수이다.

$X_1^n$ 에 대해 expectation 을 취하는 것으로 Rademacher complexity of the function class $\mathcal{F}$ 가 획득되며, 이는 주로 deterministic quantity.

$${\mathcal{R}}_n(\mathcal{F})={\mathbb{E}}_X\left[\mathcal{R}\left(\frac{\mathcal{F}(X_1^n)}{n}\right)\right]={\mathbb{E}}_{X,ϵ}\left[\underset{f\in \mathcal{F}}{\sup }\left|\frac{1}{n}\sum _{i=1}^n{ϵ}_{i}f(X_i)\right|\right]$$

여기서 Rademacher complexity 는 vector $(f(X_1),f(X_2),\cdots ,f(X_n))$ 와 noise vector $({ϵ}_{1:n})$ 사이의 maximum correlation 임을 note.

function class 가 극도로 크다면 우리는 언제나 무작위로 drawn 된 noise vector 에 대해 높은 correlation 을 가지는 function 을 찾아내는 것이 가능하다. 역으로 function class 가 지나치게 작다면 무작위로 drawn 된 noise vector 에 대해 기댓값 적으로 강하게 correlate 된 function 을 찾아내는 것은 불가능할 지도 모른다. 이러한 관점에서 결국 Rademacher complexity 는 function class 의 size 를 측정하며, 이는 곧 uniform convergence result 를 구축함에 있어 핵심적인 역할을 한다. 이하는 $\forall f\in \mathcal{F}\in \Vert f{\Vert }_{\infty }\le b$ 일 경우, function blass $\mathcal{F}$ 는 $b$-uniformly bounded 임을 보여준다.

:::{.theorem name=“Glivenko–Cantelli property”}

$\forall \mathcal{F}$, function 의 $b$-uniformly bounded class, 에 대해 $\forall$ positive integer $n\ge 1$ 과 $\forall$ scale $\delta \ge 0$ 에 대해 with $\mathbb{P}$-probability at least $1-\exp \left(-\frac{n{\delta }^2}{2b^2}\right)$ 에 대해 이하가 성립한다.

$$\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}}\le 2{\mathcal{R}}_n(\mathcal{F})+\delta$$

결과적으로 ${\mathcal{R}}_n(\mathcal{F})=o(1)$ 인 한, 우리는 ${\Vert {\mathbb{P}}_n-\mathbb{P}\Vert }_{\mathcal{F}}\stackrel{a.s.}{\to }0$ 임을 얻는다.

:::

Upper bounds on the Rademacher complexity

Glivenko–Cantelli property 가 유용하기 위해선 우리는 Rademacher complexity ${\mathcal{R}}_n(\mathcal{F})$ 에 대한 upper bound 를 획득할 필요가 있다. 이에 대해서는 다양한 방법론이 존재하며 simple union bound (finite funciton class 들에 적합한) 부터 metric entropy 의 개념부터 chaining argument 를 아우르는 고등한 방법까지 다양하다. 여기서는 polynomial discrimination 을 보유하는 function class 들에 적용할 수 있는 간단한 방법을 사용하겠다.

:::{.definition name=“Polynomial discrimination”} domain $\mathcal{X}$ 를 가지는 function 들의 class $\mathcal{F}$ 는 이하가 성립한다면 polynomial discrimination of order $\nu \ge 1$ 를 가진다.

각각의 positive integer $n$ 과, $\mathcal{X}$ 안의 $n$개의 point 들로 이루어진 collection $x_1^n=\{x_{1:n}\}$ 에 대해,

set $\mathcal{F}(x_1^n)=\{(f(x_1),\dots ,f(x_n)):f\in \mathcal{F}\}$ 은 $\mathrm{card}(\mathcal{F}(x_1^n))\le (n+1{)}^{\nu }$ 로 upper bounded 된 cardinality 를 가진다.

:::

이 성질은 empirical Rademacher complexity 를 control 하는데 있어 straightforward 한 접근법을 제공한다는 점에서 유의.

:::{.lemma name=“Bound on the empirical Rademacher complexity”}

$\mathcal{F}$ 가 polynomial discrimination of order $\nu$ 를 가진다고 하자. 이때

$$\forall n>0\in \mathbb{Z},\forall \text{collection of points }{x}_1^n=(x_{1:n}):{\mathbb{E}}_{ϵ}\left[\underset{f\in \mathcal{F}}{\sup }\right|\frac{1}{n}\sum _{i=1}^n{ϵ}_{i}f(x_i)\left|\right]\le 2D(x_1^n)\sqrt{\frac{\nu \log (n+1)}{n}}$$

• $D(x_1^n)=\underset{f\in \mathcal{F}}{\sup }\sqrt{\frac{1}{n}{\sum }_{i=1}^n{f}^2(x_i)}$ 는 set $\frac{\mathcal{F}(x_1^n)}{\sqrt{n}}$ 의 $l_2$-raidus. :::