A new arXiv paper by Dirksen, Finke, Geuchen, Stöger, and Voigtlaender studies the ℓ^p-Lipschitz constants of deep ReLU neural networks with random parameters under a variant of He initialization. For zero-bias networks that are sufficiently wide, the authors derive high-probability upper and lower bounds that match up to an absolute constant, giving what they call optimal estimates.
The bounds reveal two notable phenomena. First, the Lipschitz constants grow only root-logarithmically with network depth, not polynomially. Second, the behavior splits sharply at p=2: for p in [2,∞], the ℓ^p-Lipschitz constant behaves like the ℓ_{p'} norm of a standard Gaussian vector, where 1/p + 1/p' = 1; for p in [1,2), it aligns more closely with the ℓ2 norm of a Gaussian.
For networks with possibly nonzero biases, the same lower bounds hold without assumptions on the bias distributions. Upper bounds are obtained for symmetric bias distributions with bounded densities, but they differ from the lower bounds by a factor with square-root dependence on depth and logarithmic dependence on width. The paper thus leaves a gap for biased networks, while settling the zero-bias case up to constants.