Lista 4

\[ \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. Sejam \(w_{1}, \dotsc, w_{T+1} \in \bR^d\) dados por \(\mathrm{MWU}(\eta, T)\). Considere o potencial \[ \Phi_t := \log \Big( \sum_{i = 1}^d w_{t,i} \Big), \qquad \text{para todo}~t \in [T+1]. \] Mostre que, para qualquer \(E \subseteq [d]\), temos que \[ \Phi_{T+1} \geq \ln(|E|) - \eta \max_{i \in E} \sum_{t = 1}^T \ell_{t,i}. \] Como consequência, mostre que¹ \[ \sum_{t = 1}^T \ell_t^\T p_t - \max_{i \in [E]} \sum_{t = 1}^T \ell_t(i) \leq \frac{\ln(d/|E|)}{\eta} + \frac{\eta T}{2}. \]
2. No algoritmo de boosting básico, assumimos que o oráculo \(\WL(p_t, S)\) é determinístico, ou seja, a hipótese \(h_t\) retornada por ele sempre satisfaz \(L_{p_t}(h_t) \leq 1/2 - \gamma\) (probabilidade 1). No entanto, pela definição de classe fracamente PAC-aprendível², temos apenas a garantia da existência de um algoritmo \(A : (\cX \times \cY)^* \to \cH\) e uma função \(M \colon \bR \to \bR\) tais que: se \(S_t \sim (\cD_t)^k\) é uma amostra com \(k\) exemplos iid de \(\cD_T\) onde \(\cD_t\) é a distribuição sobre o treino \(S\) definida pelos pesos \(p_t \in \Delta_m\), então \[ k \geq M(\delta) \implies \prob\Big(L_{p_t}(A(S_t)) \leq \frac{1}{2} - \gamma\Big) \geq 1 - \delta. \]
   1. Descreva um algoritmo \(\WL'(S, p_t, \delta)\) que utiliza o algoritmo \(A\) e retorna uma hipótese \(h_t \in \cH\) tal que \[ \prob\Big(L_{p_t}(h_t) \leq \frac{1}{2} - \gamma\Big) \geq 1 - \delta. \]
   2. Usando esse novo oráculo \(\WL'\), modifique o algoritmo de boosting básico de forma que, com probabilidade pelo menos \(1 - \delta\) no total, nenhuma das hipóteses \(h_1, \dotsc, h_T\) falhe em satisfazer a condição de weak learning durante as \(T\) rodadas. (Cuidado: note que não basta usar o novo oráculo passando \(\delta\) no último argumento em cada rodada. Queremos que todas as hipóteses satisfaçam a condição simultaneamente após \(T\) rodadas).

Footnotes

1. Fique a vontade para usar como caixa preta a cota superior em \(\Phi_{t+1} - \Phi_t\) para qualquer \(\eta > 0\) vista em aula.

2. Aula 4, slide 12