Purdue Weekly Report [1]

# 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.