Rademacher complexity captures the capacity of a hypothesis space to fit random labels as a measure of the expressive capacity [1]}. A higher Rademacher complexity means that the model can fit a larger number of random labels and thus the model has a higher expressive capacity.
Bartlett et al. [2]} investigate the Rademacher complexity of deep neural networks with ReLU activation function. Given a deep ReLU neural network with \(L\)  layers, let \(A_i\)  be the parameter matrix of layer \(i\) , and \(X\in \mathbb {R}^{n\times d}\)  the data matrix, where \(n\)  is the number of instances and \(d\)  is the input dimension. Bartlett et al. [2]} prove that the lower bound for the Rademacher complexity of such networks is \(\Omega (||X||_F\prod _i ||A_i||_\sigma )\) , where \(||\cdot ||_\sigma \)  is the Spectral norm, and \(||\cdot ||_F\)  is the Frobenius norm.
Neyshabur et al. [4]} prove a tighter lower bound for two-layer ReLU neural networks. Suppose \(||A_1||_\sigma \le s_1\) , \(||A_2||_\sigma \le s_2\) , and \(s_1s_2\)  is the Lipschitz bound of the function represented by the network. They prove that the Rademacher complexity is lower bounded by \(\Omega (s_1s_2\sqrt{m}||X||_F/n)\) , where \(m\)  is the width of the hidden layer. This lower bound improves the bound [2]} by a factor of \(\sqrt{m}\) .
