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.