w)$. The set $w$ serves as a witness for scenarios which are skewed for either $x$ or $x'$; if additionally $a_i(w)$ reasonably larger than $(1 - \epsilon) B$, we can then use concentration inequalities over $\operatorname{skewm}_i(\epsilon, w)$ in order to bound probability of $\operatorname{skewm}(\epsilon, x) \vee \operatorname{skewm}(\epsilon,x')$. This ability of bounding multiple terms of the right-hand side of simultaneously is what gives an improvement over the naive union bound.

\[def:witness\] We say that $\mathcal{W}_i^+$ is a *witness set* for $\mathcal{X}_i^+$ if: (i) for all $w \in \mathcal{W}_i^+$, $a_i(w) \ge (1 - \epsilon/2) B$ and (ii) for all $x \in \mathcal{X}_i^+$ there is $w \in \mathcal{W}_i^+$ contained in $x$. Similarly, we say that $\mathcal{W}_i^-$ is a *witness set* for $\mathcal{X}_i^-$ if: (i) for all $w \in \mathcal{W}_i^-$, $a_i(w) \le (1 - 3 \epsilon/2) B$ and (ii) for all $x \in \mathcal{X}_i^-$ there is $w \in \mathcal{W}_i^-$ containing $x$.

As indicated by the previous discussion, given witness sets $\mathcal{W}_i^+$ and $\mathcal{W}_i^-$ for $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$, we directly get the bound $$\begin{aligned}
 \label{eq:witness2}
        \Pr\left(\bigvee_{i, x \in \mathcal{X}_i^+} \operatorname{skewm}(\epsilon, x) \vee \bigvee_{i, x \in \mathcal{X}_i^-} \operatorname{skewp}(\epsilon, x)\right) \le \Pr\left(\bigvee_{i, w \in \mathcal{W}_i^+} \operatorname{skewm}(\epsilon, w) \vee \bigvee_{i, w \in \mathcal{W}_i^-} \operatorname{skewp}(\epsilon, w)\right).
    \end{aligned}$$ Putting together 