\in \mathcal{X} : a_i(x) > B\}$ and $\mathcal{X}_i^- = \{x \in \mathcal{X} : a_i(x) < (1 - 3 \epsilon) B\}$. In order to simplify the notation, given a set $x$ we define $\operatorname{skewm}_i(\epsilon, x)$ to be the event that $a^S_i(x) \le (1 - \epsilon) B$ and $\operatorname{skewp}_i(\epsilon, x)$ to be the event that $a^S_i(x) \ge (1 - 2\epsilon) B$. Notice that if $x \in \mathcal{X}_i^+$, then $\operatorname{skewm}_i(\epsilon, x)$ is the event that $a_i^S(x)$ is significantly smaller than its expectation (skewed in the minus direction), while for $x \in \mathcal{X}_i^-$ $\operatorname{skewp}_i(\epsilon, x)$ is the event that $a_i^S(x)$ is significantly larger than its expectation (skewed in the plus direction). These definitions directly give the equivalence $$\label{eq:witness1}
        \Pr\left(\bigvee_{i,x \in \mathcal{X}} x \textrm{ can be badly learned for budget } i\right) = \Pr\left(\bigvee_{i, x \in \mathcal{X}_i^+} \operatorname{skewm}_i(\epsilon, x) \vee \bigvee_{i, x \in \mathcal{X}_i^-} \operatorname{skewp}_i(\epsilon, x)\right).$$

In order to introduce the concept of witnesses, consider two sets $x,x'$, say, in $\mathcal{X}_i^+$. Take a subset $w \subseteq x \cap x'$; the main observation is that, since $a^t \ge 0$ for all $t$, for all scenarios we have $a_i^S(w) \le a_i^S(x)$ and $a_i^S(w) \le a_i^S(x')$. In particular, the event $\operatorname{skewm}_i(\epsilon, x) \vee \operatorname{skewm}_i(\epsilon,x')$ is contained in $\operatorname{skewm}(\epsilon, 