← Back to all news
arXiv Machine Learning

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

This paper investigates the ρ^p-Lipschitz constants of deep ReLU neural networks with random weights drawn from a He‑style initialization. For zero‑bias networks, it provides high‑probability upper and lower bounds that differ by at most a logarithmic factor in depth, and shows a sharp contrast between the regimes p∈[1,2) and p∈[2,∞], with the former behaving like the Euclidean norm of a Gaussian vector and the latter like its dual norm. The analysis is extended to networks with non‑zero biases from symmetric distributions, yielding bounds that differ by a logarithmic factor in width and a linear factor in depth.

Related stories

arXiv Machine Learning
Aug 28

High Probability Derivative Bounds for Random tanh Neural Networks on a Hypercube

The paper establishes high‑probability bounds on mixed input derivatives for wide random neural networks whose activation derivatives grow factorially, with a focus on anh networks initialized with Xavier weights. For scalar‑output anh networks with Gaussian weights, the authors prove that when the hidden width exceeds a depth‑dependent threshold, the derivative of any order satisfies a bound that is independent of depth for first‑order derivatives and grows at most polynomially with depth for higher‑order mixed derivatives. These results yield high‑probability estimates for the Euclidean Lipschitz constant and weighted Sobolev norms, linking the regularity of network realizations to quasi‑Monte Carlo integration and its potential impact on QMC‑based training.

By Josef Dick, Michael Feischl, Fabian Zehetgruber
More like this →
arXiv Machine Learning
Aug 26

Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes

arXiv:2608.24865v1 Announce Type: cross Abstract: Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult e...

By Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla
llms
More like this →
arXiv Machine Learning
Sep 4

Parameterized Hardness of Zonotope Containment and Neural Network Verification

The paper proves that several decision and approximation problems for ReLU neural networks are computationally hard. For any number of layers λ≥2, deciding whether a network’s output is positive (and thus whether it is surjective) is W[ℓ−1]-hard when parameterized by the input dimension d. In particular, for two-layer networks, the related geometric problem of zonotope non‑containment is W[1]-hard in the ambient dimension, and computing or approximating the Lp‑Lipschitz constant is NP‑hard and W[ℓ−1]-hard with respect to d. The results also show that these problems remain hard when parameterized by the number of layers for constant d, implying that naive enumeration algorithms running in n^{(ℓ−1)d}·poly(N) time are essentially optimal under the Exponential Time Hypothesis.

By Vincent Froese, Moritz Grillo, Christoph Hertrich, Moritz Stargalla
robotics
More like this →
arXiv Machine Learning
Jun 24

Layer-wise Geometric Approximation Rates for Deep Networks

arXiv:2604. 20219v2 Announce Type: replace Abstract: Depth is widely viewed as a central contributor to the success of deep neural networks, whereas standard neural network approximation theory typically provides guarantees only for the final output and leaves the role of intermediate layers largely unclear.

By Shijun Zhang, Zuowei Shen, Yuesheng Xu
More like this →
Hugging Face Trending Papers
Aug 25

The Sharp Tail of Uniform Stability

Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a $γ$-uniformly stable algorithm with loss in $[0,L]$ has...

More like this →
arXiv Machine Learning
Aug 26

The Sharp Tail of Uniform Stability

arXiv:2608.24098v1 Announce Type: new Abstract: Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a $\gamma...

By Pahan Dewasurendra
More like this →