I want to know how to find an upper bound of the following expectation taken for both $t$ and $y$ as


$$\mathbb{E}\sup\_{x \in D} \left|\sum\_{k=1}^n t\_k x^T y\_k\right|,$$
where $D$ is the set of vectors defined by
$$D = ( x \in \mathbb{R}^m \mid 0\leq x\_i \leq 1, \forall 1\leq i\leq m ),$$


$\left(t\_k\right)\_{k=1}^n$ is the Rademacher sequence, that is, $t\_1, \cdots, t\_n$ are i.i.d. copies of a random variable $t$ taking values $\pm 1$ with $\mathbb{P}(t=1)=\mathbb{P}(t=-1)=1/2$, and
$(y\_k)$ are i.i.d. copies of a random vector $y \in \mathbb{R}^m$ taking values $e\_1,\cdots,e\_m$ with $\mathbb{P}(y = e\_i)=p\_i$. Here, $e\_i$ denotes the vector from the standard basis with $i$-th component being 1 and the others being 0.


I first get rid of the absolute value as
\begin{align}
& \mathbb{E}\sup\_x \left|\sum t\_k x^T y\_k\right| \leq \mathbb{E}\_y\left(\sqrt{\frac{\pi}{2}} \mathbb{E}\_s \sup\_x\left| \sum s\_k x^T y\_k\right|\right) \\\\
 \leq & \sqrt{2\pi} \mathbb{E}\_y\left(\mathbb{E}\_s \sup\_x\left(\sum s\_k x^T y\_k \right)\right)
= \sqrt{2\pi} \mathbb{E} \sup\_x\left(\sum s\_k x^T y\_k \right),
\end{align}
where $s\_k$ are i.i.d copies of a standard normal random variable.


Then, how to continue? My guess is that the upper bound seems to be of order $O(\sqrt{n})$. Is that correct? Thanks!



How to bound the sup norm of a Rademacher process or equivalently a Gaussian process?
The quantity is of the order $n$ (at least without any additional restriction on the $p\_i$'s). 


To see the upper bound:


$$\mathbb{E}\sup\_{x \in D} \left|\sum\_{k=1}^n t\_k x^T y\_k\right| \leq \sum\_{k=1}^n \mathbb{E} \left| 1^T y\_k\right| \leq n$$ 


where $1^T$ denotes the $1$'s vector.


To see the lower bound, set $p\_i=1/n$. Now with at least constant probability the $y\_k$'s will include at least $.1 n$ distinct vectors. Also, with large probability, at least, say, 40% of the $k$'s with distinct $y\_k$ vectors will be such that $t\_k = +1$. Let $S$ denote the resulting set of at least $.36 n$ indices / $k$'s. We can then define $x \in D$ such that $x\_k =1$ if $k \in S$ and $x\_k=0$ otherwise. When this occurs (which happens with constant / non-zero probability) the expression is $\gg .36 n$. 


(It is possible to choose $p\_i$'s such that the quantity is significantly smaller. Take $p\_1 =1$ and $p\_i=0$ (for $i>1$), then the sum is essentially that of $n$ Rademacher functions, and the expectation should be around $\sqrt{n}$).


