Exercise 5.9: Gaussian Complexity of Ellipsoids
(a)
The upper bound follows from \begin{equation} \E[\,\sup_{\theta \in \Ec}\,\lra{w, \theta}_{\ell^2}] = \E[\norm{w \mu}_{\ell^2}] \le \norm{\mu}_{\ell^2}. \end{equation} [Use the Cauchy–Schwarz Inequality and check that the upper bound is achieved at $\theta = w \mu^2 / \norm{w \mu}^2_{\ell^2}$.] The lower bound follows from lower bounding the Gaussian complexity by the Rademacher complexity and computing \begin{equation} \E[\,\sup_{\theta \in \Ec}\,\lra{\e, \theta}_{\ell^2}] = \E[\norm{\e \mu}_{\ell^2}] = \norm{\mu}_{\ell^2}. \end{equation}
(b)
First, we find the lower bound by “squishing the ellipsoid inside the sphere”. Define $\alpha_i = \min(\mu_i, r)$ and consider \begin{equation} \tilde\Ec_\alpha(r) = \set{\theta \in \ell^2 : \norm{\theta / \alpha}_{\ell^2} \le 1}. \end{equation} If $\norm{\theta / \alpha}_{\ell^2} \le 1$, then, by construction, $\norm{\theta / \mu}_{\ell^2} \le 1$ and $\norm{\theta / r}_{\ell^2} \le 1$, so $\tilde\Ec_\alpha(r) \sub \tilde\Ec(r)$. Therefore, by (a), \begin{equation} \sqrt{\frac{2}{\pi}}\norm{\alpha}_{\ell^2} \le \G(\tilde\Ec_\alpha(r)) \le \G(\tilde\Ec(r)). \end{equation}
Second, we find the upper bound by “enlarging the squished ellipsoid”. Consider \begin{equation} \tilde\Ec_{\sqrt{2}\alpha}(r) = \set{\theta \in \ell^2 : \norm{\theta / \alpha}_{\ell^2} \le \sqrt{2}}. \end{equation} If $\norm{\theta / \mu}_{\ell^2} \le 1$ and $\norm{\theta / r}_{\ell^2} \le 1$, then \begin{equation} \sum_{i=1}^\infty \frac{\theta_i^2}{\alpha_i^2} \le \sum_{i=1}^\infty \theta_i^2 \parens{ \frac{1}{r^2} + \frac{1}{\mu_i^2} } \le 2, \end{equation} so $\tilde\Ec(r) \sub \tilde\Ec_{\sqrt{2}\alpha}(r)$. Therefore, again by (a), \begin{equation} \G(\tilde\Ec(r)) \le \G(\tilde\Ec_{\sqrt{2} \alpha}(r)) \le \sqrt{2} \norm{\alpha}_{\ell^2}. \end{equation}