Optimal estimates for the $\ell^p$-Lipschitz constants of deep random ReLU neural networks

arXiv:2506.19695v3 Announce Type: replace-cross Abstract: This paper studies the $\ell^p$-Lipschitz constants of ReLU neural networks $\Phi: \mathbb{R}^d \to \mathbb{R}$ with random parameters for $p \in [1,\infty]$. The distribution of the weights follows a variant of the He initialization. In the case of zero-bias networks, we derive matching high-probability upper and lower bounds for wide networks that differ at most by an absolute constant. The bounds reveal two remarkable phenomena. First, the bounds grow root-logarithmically in terms of the depth of the net. Second, the behavior of the $\ell^p$-Lipschitz constants varies significantly between the regimes $p \in [1,2)$ and $p \in [2,\infty]$. For $p \in [2,\infty]$, the $\ell^p$-Lipschitz constant behaves similarly to $\|g\|_{p'}$, where $g \in \mathbb{R}^d$ is a standard Gaussian vector and $1/p + 1/p' = 1$. In contrast, for $p \in [1,2)$, the $\ell^p$-Lipschitz constant aligns more closely with $\|g\|_2$. For networks with possibly nonzero biases, we obtain the same lower bounds without assumptions on the bias distributions. For symmetric bias distributions with bounded densities, we also derive high-probability upper bounds for the $\ell^p$-Lipschitz constants. For fixed sub-exponential bias distributions, these upper bounds differ from the lower bounds by a factor that has square-root dependence on the depth and logarithmic dependence on the width.