A Proof of Lemma 5.1

The proof is based on Proposition A.1 and Proposition A.2, which will be introduced as Proposition A.1 shows that the set The proof follows Theorem 14.12 in [87], with non-trivial modifications for our setting. In Claim A.4 we will show that with overwhelming probability in m, sup Then we use Talagrand's inequality [83] to show that Pr null Z In order to apply Talagrand's inequality, we need to bound σ Proposition A.1 shows that the set Consider the indicator random variable associated with the complement of the above event. This implies that there exist a subset of batches J [ M ] with |J | 0. 95M such that 1 b nullA Note that this a subset of all vectors in the span of W that have norm at most null . The third line follows from the Cauchy-Schwartz inequality, and the fourth line follows from Jensen's This implies that there at least 0.95 M batches in which all samples are well behaved. Consider the setting of Lemma 5.3 with measurements satisfying Proposition A.1 shows that the set Note that this a subset of all vectors in the span of W that have norm at most null .