Does $E_{\sigma}[\|\sum_{i=1}^{m}\sigma_ix_i\|_2]\le\sqrt{E_{\sigma}[\sum_{i=1}^{m}\|x_i\|_2]}$ hold, where $|\sigma_i | = 1$? Let $\sigma := (\sigma_i)_{i = 1}^{m}$ and each $\sigma_i$ be a random variable, taking the values $\pm1$ (precisely they are Rademacher distributed, but that shouldn't matter) and $x_k \in \mathbb{R}^d$.
In out lecture the professor wrote
$$ \tag{1}
E_{\sigma}\left[\left\|\sum_{i=1}^{m}\sigma_ix_i\right\|_2\right]\le\left(E_{\sigma}\left[\sum_{i=1}^{m}\|x_i\|_2\right]\right)^{\frac{1}{2}},
$$
justifying the inequality with Hölders inequality.
I fail to see how this holds.
If
$$ \tag{2}
\left\|\sum_{i=1}^{m}\sigma_ix_i\right\|_2
\le \left(\sum_{i=1}^{m}\|x_i\|_2 \right)^{\frac{1}{2}}
$$
would hold, the inequality (1) would follow as for concave functions, such as $f := \sqrt{\cdot}$ we have $\mathbb{E}[f(X)] \le f(\mathbb{E}[X])$ by Jensens inequality for a random variable $X$.
I know that by the triangle inequality for the norm $\| \cdot \|_2$ I can get
$$ \tag{3}
\left\|\sum_{i=1}^{m}\sigma_ix_i\right\|_2
\le \sum_{i=1}^{m}\|x_i\|_2,
$$
but that is to much in this case.
Also when I choose $m = d = 1$ I get $\| a \|_2 = | a | \le \sqrt{|a|}  \le \| a \|_2^{\frac{1}{2}}$, which is false for every $a \in \mathbb{R}^{d = 1}$ except $\pm1$.
If this inequality is wrong as I suspect, what could be meant instead? Maybe $\|x_i\|_2^2$ instead of $\| x_i \|_2$?
Then next bound in (1) is $\le \sqrt{m} \max\limits_{k = 1}^{m}\| x_k \|_2$, which makes sense.
 A: I am pretty sure that your professor intended the following:
First, by expanding the inner product, and using that $\Bbb{E}[\sigma_i \sigma_j] = 0$ for $i \neq j$ (since the $\sigma_i$ have expectation zero and are independent (uncorrelated would be enough)):
$$
\Bbb{E} \Big[\Big\|\sum_i \sigma_i x_i \Big\|^2\Big]
= \sum_{i,j} \Bbb{E} \big[ \sigma_i \sigma_j \langle x_i , x_j \rangle \big]
= \sum_i \|x_i\|^2,
$$
where we also used that $\sigma_i^2 = 1$ (it would be enough to know that $\Bbb{E}[\sigma_i^2] = 1$).
Finally, we can apply Jensen's inequality with the convex function $x \mapsto x^2$ to derive
$$
\Big[\Bbb{E} \Big\| \sum_i \sigma_i x_i \Big\|\Big]^2
\leq \Bbb{E} \Big[\Big\|\sum_i \sigma_i x_i \Big\|^2\Big]
= \sum_i \|x_i\|^2.
$$
Now, take the square root to obtain that
$$
\Bbb{E} \Big\| \sum_i \sigma_i x_i \Big\|
\leq \sqrt{\sum_i \|x_i\|^2},
$$
which is (up to typos) what you wanted to show.
Note: What we used/showed here is that in expectation, adding the Rademacher sequence as coefficients makes the vectors $x_i$ orthogonal, even if (without adding the Rademacher coefficients) they might not be orthogonal as is. This is quite a useful intuition and technique to keep in mind.
