I want to know how to find an upper bound of the following expectation taken for both $\varepsilon$ 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!

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!

I want to know how to find an upper bound of the following expectation taken for both $\varepsilon$ 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(\frac{1}{\sqrt{n}})$. Is that correct? Thanks!

I want to know how to find an upper bound of the following expectation taken for both $\varepsilon$ 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!