A Rademacher complexity and generalization bounds

Herein we briefly review Rademacher complexity, a widely used concept in deriving generalization bounds, and how it applies in our analysis. The following theorem provides a classical generalization bounds based on the Rademacher complexity. Combined with Theorem A.1, this yields a generalization bound for the SPO+ loss which, when combined with Theorems 3.1 and 4.1 yields Corollaries 3.1 and 4.1, respectively. The full proofs of these corollaries are included below. Recall Theorem 3.1, the biconjugate of min{ Then if the assumption in Corollary 3.1 holds, with probability at least 1 δ, it holds B.1 Additional definitions and notation Recall that S is polyhedral and let Z For any i {1,..., d}, we use e I)) for some σ > 0. The condition mean of c is then c = (ɛ, 0) Lemma B.2. Suppose that a Lemma B.4 provide a lower bound of the conditional SPO+ risk condition on the first (d 1) element of the realized cost vector.