A Additional statements and proofs

Lemma 2. If X is a σ -subgaussian random variable with zero mean, then E e To prove the second part of the lemma, we are going to use Donsker-V aradhan inequality again, but for a different function. To prove the last part of the lemma, we just use the Markov's Furthermore, each of these summands has zero mean. Furthermore, each of these summands has zero mean. The proof closely follows that of Proposition 1. Bounding expected generalization gap of f . A natural question arises whether a different type of noise would give better bounds.