Lista 3

\[ \def\argmin{\operatorname*{argmin}} \def\Regret{\operatorname*{Regret}} \def\PRegret{\operatorname*{P-Regret}} \def\WL{\operatorname*{WL}} % \def\T{\mathsf{T}} \def\prob{\mathbb{P}} \def\expect{\mathbb{E}} \def\ones{\mathbf{1}} \def\eps{\varepsilon} \def\ERM{\mathrm{ERM}} \def\DESC{\mathrm{DESC}} \def\VC{\mathrm{VC}} \def\LDim{\mathrm{LDim}} \def\bR{\mathbb{R}} \def\bN{\mathbb{N}} \def\cC{\mathcal{C}} \def\cD{\mathcal{D}} \def\cH{\mathcal{H}} \def\cB{\mathcal{B}} \def\cX{\mathcal{X}} \def\cY{\mathcal{Y}} \def\cV{\mathcal{V}} \]

1. HALVING vs SOA. Mostre um exemplo¹ de classe de hipóteses \(\cH\) finita tal que, no pior caso, HALVING comete estritamente mais do que com \(\LDim(\cH)\) erros.
2. Uma Visão Alternativa do MWU. Considere uma instância do problema de predição com ajuda de experts com custos \(\ell_1, \ell_2, \dotsc, \ell_T \in [0,1]^d\) e escolhas do jogador \(p_1,\dotsc, p_T\). Para todo \(t \in [T]\), defina o vetor de regrets² (da rodada \(t\)) \(R_t \in \bR^d\) dado por \[ R_{t,i} \coloneqq \sum_{s = 1}^t \bigl(\ell_s^\T p_s - \ell_{s,i}\bigr), \qquad \text{para todo}~i \in [d], \] e \(R_0 \coloneqq 0\). Considere o algoritmo \(\mathrm{MIAU}(T, \eta)\) que, na rodada \(t \in [T]\), joga \(p_t \in \Delta_d\) dado por \[ p_{t,i} \coloneqq \frac{1}{Z_t}\exp\bigl(\eta R_{t-1,i}\bigr), \qquad \text{para todo}~i \in [d]~\text{onde}~Z_t \coloneqq \sum_{j=1}^d \exp\bigl(\eta R_{t-1,j}\bigr). \] Mostre que \(\mathrm{MIAU}(T, \eta)\) e \(\mathrm{MWU}(T, \eta)\) são equivalentes, ou seja, produzem a mesma sequência de escolhas \(p_1, \dotsc, p_T\).

Footnotes

1. Não precisa ser um exemplo genérico. Um exemplo concreto com \(\LDim(\cH) = 1\) basta, por exemplo.

2. Note que \(\Regret(T) = \max_i R_{T,i}\)