Tight upper-bounds for the Gaussian width of intersection of intersection of hyper-ellipsoid and unit-ball

Question

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ (and $R$) such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

---

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,\sqrt{\lambda_n})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which would match the upper-bound (1).

Answer 1

Disclaimer: After a bit of work, I've come up with the following example. Happy to hear about others.

---

Fix $\beta \in (1,\infty)$, and for any integer $n \ge 1$, let $\lambda_n = n^{-\beta}$, and let $\Lambda = \Lambda(n)$ be the $n \times n$ diagonal matrix with diagonal entries $\lambda_1,\ldots,\lambda_n$. We refer to this model for $\Lambda$ as $\beta$-polynomial.

Thanks to Example 4 of this paper From Gauss to Kolmogorov: Localized Measures of Complexity for Ellipses , we know that $w(S) \asymp R^{1-1/\beta}$. On the other hand, one computes $\min(R\sqrt{n},\sqrt{\mbox{trace}(\Lambda)}) \asymp \min(R\sqrt{n},1)$. We deduce that,

If $n^{-\beta/2} \ll R \lesssim n^{-1/2}$, then $$ \frac{\omega(S)}{\min(R\sqrt{n},\sqrt{\mbox{trace}(\Lambda)})} \asymp \frac{R^{1-1/\beta}}{R\sqrt{n}} = \frac{1}{R^{1/\beta}\sqrt n} \ll 1. $$