Purdue Weekly Report [1]

Jinning, 09/17/2018

Method 1: Using expectation to estimate coefficient

Reference: Some Topics in Analysis of Boolean Functions, Ryan O’Donnell.

Assume $S$ is a subset of the set $[n]$. $|[n]|=2^n$.

According to the reference, $\hat{f}(S)$ can be expressed as

$$\hat{f}(S)=\mathbb{E}_x[f(x)\mathcal{X}_S(x)]$$

We’re going to estimate $\hat{f}(S)$ by

$$\tilde{f}(S)=\frac{1}{N}\sum_{i=1}^{N}f(x_i)\mathcal{X}_{S}(x_i)$$

We use $Var(\tilde{f}(S))$ to estimate the speed of learning.

$$Var(\tilde{f}(S))=\frac{1}{N^2}Var(\sum_{i=1}^{N}f(x_i)\mathcal{X}_{S}(x_i))$$

$$=\frac{1}{N}Var(f(x)\mathcal{X}_{S}(x))$$

where, $$Var(f(x)\mathcal{X}_{S}(x))=\mathbb{E}_x[f^2(x)\mathcal{X}_S^2(x)]-[\mathbb{E}_x[f(x)\mathcal{X}_S(x)]]^2$$

$$=\mathbb{E}_x[f^2(x)]-\hat{f}^2(S)$$

$$=\frac{1}{N}\sum_{S_i\in [n]}\hat{f}^2(S_i)-\hat{f}^2(S)$$

So, the convergence speed is not necessarily decreasing with degree.