Q$5.$ Online prediction with combinatorial expert sets $($advanced$).(25$ points$)$

Q$5.$ Online prediction with combinatorial expert sets $($advanced$).(25$ points$)$

In this problem, we will explore the computational efficiency of online algorithms applied

to the problem of contextual prediction, i$.$e$.$ prediction with side information. Consider

predicting a binary sequence $y_1,$dots,$y_{T}in\{0,1\}$ with side information available in the form

of a $d-$length bit string, i$.$e$.z_t=(z_{t,1},$dots,$z_{t,d})in\{0,1{\}}^d,$ before round $t.$ Let the $n$ experts

denote the set of all Boolean functions that map context $z_t$ to a prediction $x_t,$ i$.$e$.$ expert

$f$ is given by Boolean function $f$:$\{0,1{\}}^d\{0,1\}$ and expert $f$ will predict $f(z_t).$ Also

denote the loss function of expert $f$ by $l_f^{(t)}=I[f(z_t)y_t].$ Let $F$ denote the set of all such

Boolean functions.

$($a$)(5$ points$)$ Show that the computational efficiency of the randomized weighted majority

algorithm is at most linear in the number of experts per iteration, i$.$e$.$ if the number

of experts is equal to $n,$ the computational complexity per iteration is $O(n).$

$($b$)(5$ points$)$ Show that the number of experts $n=2^{2d}$ in this example, implying pro$-$

hibitive computational complexity.

$($c$)(5$ points$)$ We will now show a better complexity bound for the special case of the

exponential weights algorithm. Recall that the exponential weights update is given by

$w_f^{(t+1)}=w_f^{(t)}*exp(-lon{l}_f^{(t)})=$exp$(-lon{L}_f^{(t)})$

for any of the experts $($Boolean functions$)f,$ where we defined $L_f^{(t)}$:$={\displaystyle \underset{s=1}{\overset{t}{}}}{l}_f^{(t)}($i$.$e$.$

the cumulative loss$).$ We will show that we can implement the probability function

$p_t=P[x_t=1]$ efficiently in this case. Without loss of generality, consider $z_t=1$:$=$

$(1,1,$dots,$1),$ i$.$e$.$ the all$-$ones bitstring. Denote $F_1$ to be the set of all Boolean functions

that predicts $f(z_t)=1($and $F_0$ to be the set of all Boolean functions that predicts

$f(z_t)=0).$ Note that $F=F_0{F}_1$ and that $F_0{F}_1=\frac{O}{?}.$ Write an expression for $p_t$

in terms of sums over $F_1,F_0,lon,$ and the cumulative losses $\{L_f^{(t)}{\}}_{\text{f}\text{i}\text{n}\text{F}}.$

$($d$)(5$ points$)$ For any zin$\{0,1{\}}^d,$ denote $C_{x,z}^{(t)}$:$={\displaystyle \underset{s-1}{\overset{t}{}}},z_{-}-zI[y_{s}x].$ Show that

exp$(-lon{L}_f^{(t)})=pro{d}_{zlon\{0,1{\}}^4}$exp$(-lon{C}_{f(z),z}^{(t)}).$

$($e$)(5$ points$)$ Show that

${\displaystyle \underset{fin{F}_1}{\overset{?}{}}}pro{d}_{in\{0,1{)}^d\text{:}z}1$exp$(-lon{C}_{f(z),z}^{(t)})={\displaystyle \underset{fin{F}_0}{\overset{?}{}}}pro{d}_{\text{x}\text{i}\text{n}(0,1{)}^{4\text{:}z}}1$exp$(-lon{C}_{f(z),z}^{(t)})$

Plug this into your expression for $p_t$ to show that we can write

$p_t=\frac{\text{e}\text{x}\text{p}(-lon{C}_{1,1}^{(t)})}{\text{e}\text{x}\text{p}(-lon{C}_{1,1}^{(t)})+\text{e}\text{x}\text{p}(-lon{C}_{0,1}^{(t)})}$

What is the computational complexity per iteration of this update? What about

memory $($i$.$e$.$ storage$)$ complexity?