Near-optimal estimates for the ℓp-Lipschitz constants of deep random ReLU neural networks

This paper studies the ℓp-Lipschitz constants of ReLU neural networks Phi: ℝd → ℝ with random parameters for p ∈ [1,∞]. The distribution of the weights follows a variant of the He initialization. In the case of zero-bias networks, 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 depth. Remarkably, the behavior of the ℓp-Lipschitz constant varies significantly between the regimes p ∈ [1,2) and p ∈ [2,∞] . For p ∈ [2,∞], the ℓp-Lipschitz constant behaves similarly to Vert gVertp', where g ∈ ℝd is a d-dimensional standard Gaussian vector and 1/p + 1/p' = 1. In contrast, for p ∈ [1,2), the ℓp-Lipschitz constant aligns more closely to Vert g Vert2. We extend our analysis to networks with possibly non-zero biases drawn from arbitrary symmetric distributions. In this case, we obtain high probability upper and lower bounds that differ at most by a factor that is logarithmic in the network's width and linear in its depth.