Gaussian complexity bound

Question

I am reading Foundations of Machine Learning (1st edition). It seems that most generalization bounds in the literature are based on Rademacher complexity, rather than Gaussian complexity. So, I was wondering if the same bounds still hold for Gaussian complexity. For example, does Theorem 3.1 in the book still hold for Gaussian complexity? From the proof, it seems that it still holds for Gaussian complexity without changing anything.

I have read the paper Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, and the Lemma 4 there indicates that Rademacher complexity can be upper bounded by Gaussian complexity times a constant. I was wondering, what is this constant? Is it data dependent?

Answer 1

It is a number not depending on the data , n or the hypothesis class . I did not see an actual value in any paper or book . But this is not very important since almost all bounds in learning theory are up to some absolute constants .

Answer 2

The book "high dimensional statistics" by M. Wainwright gives a specific numerical value on page 142, namely $$\sqrt{\frac{\pi}{2}}$$ But the proof is left as an exercise.

Answer 3

$$\mathbb E \sup \langle \epsilon, \theta\rangle = \mathbb E \sup \langle \text{sign}(w), \theta\rangle = \mathbb E \sup \left\langle \text{sign}(w)\mathbb E |u| \sqrt\frac{\pi}{2}, \theta\right\rangle $$

where $u$ is a standard normal. But this is a supremum of convex functions, so it is also convex. Applying Jensen's:

$$\leq \sqrt\frac{\pi}{2}\mathbb E \sup \left\langle \text{sign}(w)|u| , \theta\right\rangle = \sqrt\frac{\pi}{2} \mathbb E \sup \langle w, \theta\rangle$$