$a_i(x) < (1 - 3 \epsilon) B$.

Essentially these are the classifications which look good for the sampled $(\epsilon n, 1- \epsilon)$-LP but are actually bad for . Putting Lemmas \[lemma:approximateCS\] and \[lemma:sampleCS\] together and unraveling the definitions gives that $$\Pr\left(x^S \textrm{ is bad}\right) \le \Pr\left(\bigvee_{i \in [m], x \in \mathcal{X}} x \textrm{ can be badly learned for budget } i\right). \label{eq:badlyLearned}$$ Notice that the right-hand side of this inequality does not depend on $x^S$, it is only a function of how skewed $a_i^S(x)$ is as compared to its expectation $a_i(x)$.

Usually the right-hand side in the previous equation is upper bounded by taking a union bound over all its terms [@agrawal]. Unfortunately this is too wasteful: when $x$ and $x'$ are “similar” there is a large overlap between the scenarios where $a_i^S(x)$ is skewed and those where $a_i^S(x')$ is skewed. In order to obtain improved guarantees, we introduce in the next section a new way of bounding the right-hand side of the above expression.

Similarity via witnesses {#sec:witness}
------------------------

First, we partition the classifications which can be badly learned for budget $i$ into two sets, depending on why they are bad: for $i \in [m]$, let $\mathcal{X}_i^+ = \{x 