Near-optimal estimates for the ${\mathrm{\ell }}^p$-Lipschitz constants of deep random ReLU neural networks

This paper studies the ${\mathrm{\ell }}^p$-Lipschitz constants of ReLU neural networks $\mathrm{\Phi }:{\mathbb{R}}^d\to \mathbb{R}$ with random parameters for $p\in [1,\mathrm{\infty }]$. The distribution of the weights follows a variant of the He initialization and the biases are drawn from symmetric distributions. We derive high probability upper and lower bounds for wide networks that differ at most by a factor that is logarithmic in the network’s width and linear in its depth. In the special case of shallow networks, we obtain matching bounds. Remarkably, the behavior of the ${\mathrm{\ell }}^p$-Lipschitz constant varies significantly between the regimes $p\in [1,2)$ and $p\in [2,\mathrm{\infty }]$. For $p\in [2,\mathrm{\infty }]$, the ${\mathrm{\ell }}^p$-Lipschitz constant behaves similarly to $\mathrm{\parallel }g{\mathrm{\parallel }}_{p^{\mathrm{\prime }}}$, where $g\in {\mathbb{R}}^d$ is a $d$-dimensional standard Gaussian vector and $1\mathrm{/}p+1\mathrm{/}{p}^{\mathrm{\prime }}=1$. In contrast, for $p\in [1,2)$, the ${\mathrm{\ell }}^p$-Lipschitz constant aligns more closely to $\mathrm{\parallel }g{\mathrm{\parallel }}_2$.