Chapter 1 • Exercise 3

Part 1

We directly have \begin{align} \ln \mathbb{E} \exp \{- \eta (X - \mathbb{E}[X])\} &\leq \mathbb{E} \exp \{- \eta (X - \mathbb{E}[X])\} - 1 \\ &\leq \mathbb{E} \left\{1 - \eta (X - \mathbb{E}[X]) + \frac{\eta^2}{2} (X - \mathbb{E}[X])^2 \right\} - 1 \\ &= \frac{\eta^2}{2}\left(\mathbb{E}[X^2] - \mathbb{E}[X]^2\right) \\ &\leq \frac{\eta^2}{2}\mathbb{E}[X^2] \end{align} as desired.

Part 2

Rearranging gives us \begin{align} \eta \mathbb{E}[X] \leq - \ln \mathbb{E} \exp\{- \eta X\} + \frac{\eta^2}{2} \mathbb{E}[X^2] \end{align} Hence \begin{align} \eta \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)] &\leq - \ln \mathbb{E}_{\hat{f}^t \sim q^{t} } \exp\{- \eta l(\hat{f}^t(x), y)\} + \frac{\eta^2}{2} \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)^2] \\ &= - \ln \sum_{f \in \mathcal{F}} e^{- \eta l(f(x), y)} \frac{e^{- \sum_{i=1}^{t-1} l(f(x), y)}}{\sum_{f' \in \mathcal{F}} e^{- \sum_{i=1}^{t-1} l(f(x), y)}} + \frac{\eta^2}{2} \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)^2] \\ &= \Phi_{\eta}^{t} - \Phi_{\eta}^{t-1} + \frac{\eta^2}{2} \mathbb{E}_{f \sim q^{t} }[l(f(x), y)^2] \end{align} Summing over \(t\), we have \begin{align} \sum_{t=1}^{T} \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)] &\leq \frac{1}{\eta} \left(\Phi_{\eta}^{T} - \Phi_{\eta}^{0}\right) + \frac{\eta}{2} \sum_{t=1}^{T} \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)^2] \end{align} Finally we have both \begin{align} \Phi_{\eta}^0 &= - \ln |\mathcal{F}| \\ \Phi_{\eta}^T &\leq \eta \sum_{t=1}^{T} l(f^{\star}(x), y) \quad \forall \ f^{\star} \in \mathcal{F} \end{align} Hence for any \(f^{\star} \in \mathcal{F}\), we have \begin{align} \sum_{t=1}^{T} \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)] - l(f^{\star}(x), y) \leq \frac{\eta}{2} \sum_{t=1}^{T} \mathbb{E}_{\hat{f}^t \sim q^{t} }[l(\hat{f}^t(x), y)^2] + \frac{\log |\mathcal{F}|}{\eta} \end{align} as desired.

Part 3

Since \(l\) is bounded, we have \begin{align} \sum_{t=1}^{T} \mathbb{E}_{\hat{f^t} \sim q^t} [l(\hat{f^t}(x^t), y^t)] &\leq \frac{\eta}{2} \mathbb{E}_{\hat{f^t} \sim q^t} [l(\hat{f^t}(x^t), y^t)^2] + \frac{\log |\mathcal{F}|}{\eta} \\ &\leq \frac{\eta}{2} \mathbb{E}_{\hat{f^t} \sim q^t} [l(\hat{f^t}(x^t), y^t)] + \frac{\log |\mathcal{F}|}{\eta} \end{align} rearranging, we have \begin{align} \sum_{t=1}^{T} \mathbb{E}_{\hat{f^t} \sim q^t} [l(\hat{f^t}(x^t), y^t)] &\leq \frac{\log |\mathcal{F}|}{\eta(1 - \frac{\eta}{2})} \end{align} choosing \(\eta = 1\), we have \begin{align} \sum_{t=1}^{T} \mathbb{E}_{\hat{f^t} \sim q^t} [l(\hat{f^t}(x^t), y^t)] &\leq 2 \log |\mathcal{F}| \end{align}

Part 4

Note that whenever \(l(\hat{f}^t(x^t), y^t) = 1\), \(|\mathcal{F}^{t}| \leq \frac{1}{2}|\mathcal{F}^{t-1}|\) (ie, whenever the majority is wrong, the size of our version space goes down by a factor of two). Thus we have that \begin{align} |\mathcal{F}^{t}| \leq \frac{|\mathcal{F}|}{\exp \left\{\ln 2 \times \sum l(\hat{f}^t(x^t), y^t)\right\}} \end{align} hence for all \(t\) \begin{align} \sum_{t=0}^{T} l(\hat{f}^t(x^t), y^t) \leq \frac{1}{\ln 2} \log \frac{|\mathcal{F}|}{|\mathcal{F}^{T}|} \leq \frac{1}{\ln 2} \log {|\mathcal{F}|} \end{align}

Return home