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

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

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

where,

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