Calculate Rademacher complexity of linear regression Given $$\mathcal{F} = \{f(x) = W^{T}x, \|W\|_{2} \leq w\}$$ I am interested in determining the Rademacher complexity of $\mathcal{F}$. How would one start this computation?
 A: Finding an upper bound on $\mathfrak R (\mathcal F)$ is fairly straightforward. Assuming there is an upper bound $B$ such that $\Vert x\Vert_2 \le B $ for all $x$ in the domain, we have :
$$\begin{align}\mathfrak R (\mathcal F) &:=\mathbb{E}\left[ \sup_{W, \|W\|_{2} \leq w} \Big| \frac{1}{n} \sum_{i=1}^{n} \sigma_{i}W^{T}x_{i} \Big|\right]\\
&=\frac{1}{n}\mathbb{E}\left[ \sup_{W, \|W\|_{2} \leq w} \Big|  W^{T}\sum_{i=1}^{n} \sigma_{i}x_{i} \Big|\right]\\
&\le \frac{1}{n}\mathbb{E}\left[ \sup_{W, \|W\|_{2} \leq w} \Vert  W\Vert_2 \left\lVert\sum_{i=1}^{n} \sigma_{i}x_{i} \right\rVert_2\right] \,\text{(Cauchy-Schwarz)}\\
&=\frac{1}{n}\mathbb{E}\left[ w \left\lVert\sum_{i=1}^{n} \sigma_{i}x_{i} \right\rVert_2\right]\\
&=\frac{w}{n}\mathbb{E}\left[  \sqrt{\left\langle\sum_{i=1}^{n} \sigma_{i}x_{i} ,\sum_{i=1}^{n} \sigma_{i}x_{i} \right\rangle}\right]\\
&=\frac{w}{n}\mathbb{E}\left[  \sqrt{\sum_{1\le i,j\le n} \sigma_{i}\sigma_{j}\langle x_{i} ,x_{j} \rangle}\right]\\
&\le \frac{w}{n}  \sqrt{\mathbb{E}\left[\sum_{1\le i,j\le n} \sigma_{i}\sigma_{j}\langle x_{i} ,x_{j} \rangle\right]}\,\text{(Jensen)}\\
&=\frac{w}{n}  \sqrt{\sum_{1\le i,j\le n} \mathbb{E}\left[\sigma_{i}\sigma_{j}\right]\langle x_{i} ,x_{j} \rangle}\\
&=\frac{ w}{n}  \sqrt{\sum_{1\le i\le n} \Vert x_{i} \Vert_2^2}\\
&\le \frac{wB}{\sqrt n}
\end{align} $$
Although this upper bound is obtained by fairly elementary techniques, it is quite good in the sense that it matches the lower bound up to a constant factor. To obtain the expression of the lower bound, you can proceed similarly and use Khitchine's inequality. The details of the computation and a more general discussion is available in this paper by Awasthi, Frank and Mohri: On the Rademacher Complexity of Linear Hypothesis Sets (2020).
