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<t} A_{ij} \sigma_{s}^{i} \sigma_{t}^{i}$ 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<t} A_{st}(\sum \limits_{i=1}^{n} \alpha_i \sigma_{s}^{i} \sigma_{t}^{i}) \end{equation}

Which is a gaussian random variable. Furthermore we have

\begin{equation} \mathbb{E}(\sum \limits_{s<t} A_{st}\sigma_{s}^{i} \sigma_{t}^{i}) = \sum \limits_{s<t} \mathbb{E}(A_{st})\sigma_{s}^{i} \sigma_{t}^{i} = 0 \end{equation}


\begin{equation} \gamma_{ij}^{X} = \sum \limits_{s<t}(\sigma_{s}^i \sigma_{t}^i - \sigma_{s}^{j} \sigma_{t}^{j})^2 \leq 2n^2 \end{equation}

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.


1 Answer 1


$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.