../

Online Opt HW2

$\newcommand{E}{\mathbb{E}}$

b) Consider the repeated game for $T$ rounds. On round $t$, the generator chooses $\mu_t\in\Delta_{\mathcal{X}}$ and the discriminator chooses a discriminator $h_t\in\mathcal{H}$. Define the regret of the generator and the discriminator respectively as $$ R_{\mathrm{G}}(T) = \sum_{t=1}^T f(\mu_t,h_t) -\min_{\mu\in\Delta_{\mathcal{X}}} \sum_{t=1}^T f(\mu,h_t) $$ and $$ R_{\mathrm{D}}(T) = \max_{h\in\mathcal{H}}\sum_{t=1}^T f(\mu_t,h) -\sum_{t=1}^T f(\mu_t,h_t). $$ Define its average strategy $\bar\mu_T$ by $$ \bar\mu_T=\frac{1}{T}\sum_{t=1}^T\mu_t. $$ Prove that $$ d_{\mathcal{H}}(\bar\mu_T,\mu^\star) \leq\frac{R_{\mathrm{G}}(T)+R_{\mathrm{D}}(T)}{T}. $$ Briefly explain what this implies when $R_{\mathrm{G}}(T)+R_{\mathrm{D}}(T)=o(T)$.

In the next two subproblems, we design no-regret algorithms for both the generator and the discriminator under simplification assumptions.

Expansion of LHS

$$ d_{\mathcal{H}}(\bar\mu_T,\mu^\star) = %% \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| $$

This represents the distance with respect to $\mathcal{H}$ between the average choice played by the generator and the target distribution

We want to prove that this is somehow bounded by regret

Expansion of RHS

$$ \frac{R_G(T) + R_D(T)}{T}\ =\frac{1}{T}\left[ \sum_{t=1}^T f(\mu_t,h_t) -\min_{\mu\in\Delta_{\mathcal{X}}} \sum_{t=1}^T f(\mu,h_t)

\max_{h\in\mathcal{H}}\sum_{t=1}^T f(\mu_t,h) -\sum_{t=1}^T f(\mu_t,h_t) \right]\ =\frac{1}{T}\left[ \max_{h\in\mathcal{H}}\sum_{t=1}^T f(\mu_t,h) -\min_{\mu\in\Delta_{\mathcal{X}}} \sum_{t=1}^T f(\mu,h_t) \right]\ $$

We know the minimizer to $\min_{\mu\in\Delta_{\mathcal{X}}} \sum_{t=1}^T f(\mu,h_t)$ is $\mu^\star$. Regardless of the discriminator being played if we had just chosen $\mu^\star$, then $f$ would have been 0.

$$ =\frac{1}{T}\left[ \max_{h\in\mathcal{H}}\sum_{t=1}^T f(\mu_t,h) \right]\ $$

Simplified statement to prove

$$ \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| \le \frac{1}{T}\left[ \max_{h\in\mathcal{H}}\sum_{t=1}^T f(\mu_t,h) \right]\ $$ Expanding RHS even more $$ \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| \le \frac{1}{T} \max_{h \in \mathcal{H}} \sum_{t=1}^T \left( \E_{x \sim \mu^\star}[h(x)] - \E_{x\sim\mu_t}[h(x)] \right) $$

$$ \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| \le \frac{1}{T} \max_{h \in \mathcal{H}} \left( \sum_{t=1}^T \E_{x \sim \mu^\star}[h(x)] - \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right)\ \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| \le \frac{1}{T} \max_{h \in \mathcal{H}} \left( T\E_{x \sim \mu^\star}[h(x)] - \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right) \ \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| \le \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right)\ $$

Let us expand $\E_{x\sim\bar\mu_T}[h(x)]$

$$ \E_{x\sim\bar\mu_T}[h(x)]\ = \sum_{x\in \mathcal{X}} h(x)\bar\mu_t(x)\ = \sum_{x\in \mathcal{X}} h(x)\frac{1}{T}\sum_{t=1}^T \mu_t(x)\ = \frac{1}{T}\sum_{x\in \mathcal{X}} h(x)\sum_{t=1}^T \mu_t(x)\ = \frac{1}{T}\sum_{x\in \mathcal{X}} \sum_{t=1}^T h(x)\mu_t(x)\ = \frac{1}{T}\sum_{t=1}^T \sum_{x\in \mathcal{X}} h(x)\mu_t(x)\ = \frac{1}{T}\sum_{t=1}^T \E_{x\sim\mu_t}h(x)\ $$

Substituting this back into the previous equation,

$$ \max_{h\in\mathcal{H}}\left|\E_{x\sim \bar{\mu}T}[h(x)] - \E{x\sim \mu^\star}[h(x)]\right| \le \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right)\ \max_{h\in\mathcal{H}}\left|\frac{1}{T}\sum_{t=1}^T \E_{x\sim\mu_t}h(x) - \E_{x\sim \mu^\star}[h(x)]\right| \le \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right)\ \max_{h\in\mathcal{H}}\left|\E_{x\sim \mu^\star}[h(x)]

  • \frac{1}{T}\sum_{t=1}^T \E_{x\sim\mu_t}h(x) \right| \le \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right) $$

But we know that $$ \max_{h\in\mathcal{H}}\left|\E_{x\sim \mu^\star}[h(x)]

  • \frac{1}{T}\sum_{t=1}^T \E_{x\sim\mu_t}h(x) \right| \ge \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right) $$

Hence they have to be equal $$ \max_{h\in\mathcal{H}}\left|\E_{x\sim \mu^\star}[h(x)]

  • \frac{1}{T}\sum_{t=1}^T \E_{x\sim\mu_t}h(x) \right| = \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right) $$

If they are equal to each other, then $$ \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \frac{1}{T} \sum_{t=1}^T \E_{x\sim\mu_t}[h(x)] \right) \ge 0\ \max_{h \in \mathcal{H}} \left( \E_{x \sim \mu^\star}[h(x)] - \E_{x\sim\bar\mu_T}[h(x)] \right) \ge 0\ \max_{h \in \mathcal{H}} \E_{x \sim \mu^\star}[h(x)] \ge \max_{h \in \mathcal{H}} \E_{x\sim\bar\mu_T}[h(x)] $$

If $R_G(T) + R_D(T) = o(T)$, that implies that after $T$ rounds, the distance between the average $\mu$ and the target $\mu^\star$ is lesser than 1. The distance converges to 0.