A complexity and generalization bounds

Combined with Theorem A.1, this yields a generalization bound for the SPO+ loss which, when Recall Theorem 3.1, the biconjugate of Lemma B.1 provides the relationship between excess SPO risk and the optimal solution of (d 1) Lemma B.4 provide a lower bound of the conditional SPO+ risk condition on the first (d 1) Lemma B.5 provide a lower bound of the conditional SPO+ risk when the distribution of By result in Lemma B.4, it holds that E By Lemma B.3, it holds that Now we present a general version of Theorem 3.1. By Lemma B.5, we know that R (d 1) Herein we provide an example to show the tightness of the lower bound in Theorem B.1. First we provide some useful properties in the following lemma. Now we provide the proofs of Lemma C.1 and C.2. Proof of Lemma C.1. In Lemma C.1 we show that c From Theorem C.2 and Lemma C.5, we know that Proposition C.2. Suppose P P Let ω = c c. Since p (c) = p (2 c c), we have E Also, α ζ (α) is a non-decreasing function.