(i.e., obtains large proportional revenue while not filling up the proportionally scaled budget too much). The goal is to upper bound the probability that $x^S$ is not good for the whole LP; this is typically done via a union bound over the classifications in $\mathcal{X}$ [@DevanurHayes09; @agrawal].

To obtain improved guarantees, we refine this bound using an argument akin to covering: we consider *witnesses* (Section \[sec:witness\]), which are representatives of groups of ‘similar’ bad classifications that can be used to bound the probability that *any* classification in the group is learned; for that we need to use a non-standard measure of similarity between classifications which is based on the budget of the LP. The problem is that, when the columns $(\pi_t, a^t)$’s do not lie in a two-dimensional subspace of $\mathbb{R}^{m}$, the set $\mathcal{X}$ may contain a large number of mutually dissimilar bad classifications; this is a roadblock for obtaining a small set of witnesses. In stark contrast, when these columns do lie in a two-dimensional subspace (e.g., $m = 1$), these classifications have a much nicer structure which indeed allows a small set of witnesses. This indicates that the latter learning problem is intrinsically more robust than the former, 