Question

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!

Answer 1

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}$).

Answer 2

$t$ is symmetric, but $y$ is not necessarily so. My intuition is that an upper bound would have to depend on the set of $p_i, i \in {1, \ldots, m}$, for . Does that make sense?

Answer 3

Is the following correct?

Notice that $t$ and $y$ are independent, we have $\mathbb{E} = \mathbb{E}_y\mathbb{E}_t$. Then we focus on the inner expectation $\mathbb{E}_t$ for some fixed $y_1=e_{(1)},\cdots, y_n=e_{(n)}$.

$$\mathbb{E} \sup_{x\in D}\left|\sum_{k=1}^n t_k x^T y_k\right| = \mathbb{E} \sup_{x\in D} \left|\sum_{k=1}^n t_kx_{(k)} \right|\leq \mathbb{E}\left|\sum_{k=1}^n t_k \right|\leq \sqrt{\frac{\pi}{2n}} \quad ???$$

The above upper bound does not depend on $y$. Thus, it is also an upper bound for the expectation of both $y$ and $t$. Is this correct?