# Tighter upper bound for $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma]$

Following this question I was thinking about ways to improve the upper bound and came up with the following argument. We want to find an upper bound for

$$\begin{equation} \mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma] \end{equation}$$

where $$W$$ is a symmetric matrix with independent entries $$W_{ij} \sim \mathcal{N}(0,1)$$, except for the symmetry condition. This is a slightly different version of the problem mentioned in the link but the argument is analogous. I came across the following result for gaussian processes

Let $$(X_1, \ldots, X_n)$$ and $$(Y_1, \ldots, Y_n)$$ be gaussian random vectors with $$\mathbb{E}(X_i) = \mathbb{E}(Y_i)$$ for each $$i$$. For $$1 \leq i,j \leq n$$, let $$\gamma_{ij}^{X} = \mathbb{E}(X_i - X_j)^2$$ and $$\gamma_{ij}^{Y} = \mathbb{E}(Y_i - Y_j)^2$$, and let $$\gamma = \max_{1 \leq i,j \leq n} | \gamma_{ij}^{X} - \gamma_{ij}^{Y}|$$. Then

$$\begin{equation} |\mathbb{E}(\max_{1 \leq i \leq n} X_i) - \mathbb{E}(\max_{1 \leq i \leq n} Y_i) | \leq \sqrt{\gamma \log n}. \end{equation}$$

I was thinking about applying this result with the random vectors $$Y,X \in \mathbb{R}^{2^n}$$ s.t. $$Y_i = 0$$ and $$X_i = 2 \sum \limits_{s for $$1 \leq i \leq 2^{n}$$, where $$\sigma^{i}$$ is the $$i$$-th hypercube vertex for some ordering of the vertices.

Question: Is the following Argument sound? Did I make a mistake or overlook something?

It is clear that $$Y$$ is a gaussian random vector. I think $$X$$ is also a gaussian random vector because for any real numbers $$\alpha_1, \ldots, \alpha_n$$ we have

$$\begin{equation} \alpha_1X_1 + \ldots + \alpha_n X_n = \sum \limits_{s

Which is a gaussian random variable. Furthermore we have

$$\begin{equation} \mathbb{E}(\sum \limits_{s

and

$$\begin{equation} \gamma_{ij}^{X} = \sum \limits_{s

Together with $$\gamma_{ij}^Y = 0$$ we have

$$\begin{equation} \mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma] \leq \sqrt{2n^2 \log 2^n} \end{equation}$$

The right hand side can be simplified to $$\sqrt{2\log(2)} n^{3/2}$$. If I understood correctly the author of the cited paper uses $$\log$$ to denote the natural logarithm. This would lead us to an upper bound of the order $$\sim 1.177 n^{3/2}$$, which is not too far away from the actual value for large $$n$$ which is $$\sqrt{2} \cdot 0.7633 n^{3/2} \sim 1.079 n^{3/2}$$.

Thank you very much for your help.

$$\newcommand\si{\sigma}$$ $$\newcommand\Si{\Sigma}$$ $$\newcommand\R{\mathbb R}$$ Let $$\Si:=\{\pm 1\}^n$$. The map $$\R^{n\times n}\ni w\mapsto f(w):=(w_\si)_{\si\in\Si}\in\R^\Si,$$ where $$w_\si:=\si^T w\si$$, is linear. Therefore and because $$W$$ is zero-mean Gaussian, we see that $$(W_\si)_{\si\in\Si}:=f(W):=f\circ W$$ is zero-mean Gaussian, with $$W_\si:=\si^T W\si=\sum_{i,j}\si_i\si_j W_{ij}$$; everywhere here, the summation indices run over the set $$\{1,\dots,n\}$$. Also, for all $$\rho$$ and $$\si$$ in $$\Si$$ $$EW_\rho W_\si=\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l EW_{ij}W_{kl} \\ =\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l 1_{\{i,j\}=\{k,l\}} \\ =\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l 1_{i=j=k=l}\\ +\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l 1_{i=k\ne j=l} \\ +\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l 1_{i=l\ne j=k} \\ =2\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l 1_{i=k,j=l} \\ -\sum_{i,j,k,l}\rho_i\rho_j\si_k\si_l 1_{i=j=k=l} \\ =2\sum_{i,j}\rho_i\rho_j\si_i\si_j -\sum_i\rho_i\rho_i\si_i\si_i \\ =2(\rho\cdot\si)^2-n,$$ where $$\rho\cdot\si:=\sum_i\rho_i\si_i$$; in particular, $$EW_\si^2=EW_\rho^2=2n^2-n$$. So, $$E(W_\si-W_\rho)^2=EW_\si^2+EW_\rho^2-2EW_\rho W_\si =4n^2-4(\rho\cdot\si)^2\le4n^2.$$ So, the bound you are getting is actually $$2\sqrt{\log2\,}\, n^{3/2}$$, $$\sqrt2$$ times as large as you suggested.