stat.MLApr 3, 2026

Lipschitz bounds for integral kernels

Authors: Justin Reverdi, Sixin Zhang, Fabrice Gamboa, Serge Gratton

Organizations: IRIT, IMT, LIEBHERR Aerospace, Toulouse, France · Univ Toulouse, Toulouse INP, CNRS, IRIT, Toulouse, France · IMT, Toulouse, France

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Feature maps associated with positive definite kernels play a central role in kernel methods and learning theory, where regularity properties such as Lipschitz continuity are closely related to robustness and stability guarantees. Despite their importance, explicit characterizations of the Lipschitz constant of kernel feature maps are available only in a limited number of cases. In this paper, we study the Lipschitz regularity of feature maps associated with integral kernels under differentiability assumptions. We first provide sufficient conditions ensuring Lipschitz continuity and derive explicit formulas for the corresponding Lipschitz constants. We then identify a condition under which the feature map fails to be Lipschitz continuous and apply these results to several important classes of kernels. For infinite width two-layer neural network with isotropic Gaussian weight distributions, we show that the Lipschitz constant of the associated kernel can be expressed as the supremum of a two-dimensional integral, leading to an explicit characterization for the Gaussian kernel and the ReLU random neural network kernel. We also study continuous and shift-invariant kernels such as Gaussian, Laplace, and Matérn kernels, which admit an interpretation as neural network with cosine activation function. In this setting, we prove that the feature map is Lipschitz continuous if and only if the weight distribution has a finite second-order moment, and we then derive its Lipschitz constant. Finally, we raise an open question concerning the asymptotic behavior of the convergence of the Lipschitz constant in finite width neural networks. Numerical experiments are provided to support this behavior.

More in this topic

Kernel Methods

Kernel methods use similarity functions and reproducing kernel spaces to model nonlinear relationships, quantify uncertainty, and compare data.

See all 230 papers

Explore similar work

CardsList
Jul 8, 2026

A law of robustness for two-layer neural networks with arbitrary weights

Bubeck, Li and Nagaraj conjectured that, for generic data, any two-layer neural network with mm neurons that fits nn noisy labels must have Lipschitz constant at least of order n/m\sqrt{n/m}, with no restriction on the size of the weights. Bubeck and Sellke proved a universal version of this law for Lipschitz-parameterized classes, but under a polynomial bound on the parameters; at depth three that boundedness hypothesis is genuinely necessary. The two-layer unbounded-weight case requires a different argument. We prove the conjectured law, up to one logarithmic factor, for every continuous piecewise-linear activation, in particular for ReLU networks. For data drawn uniformly from Sd−1\mathbb{S}^{d-1}, d≥3d\ge3, or from N(0,Id/d)N(0,I_d/d), labels in [−1,1][-1,1] with noise level σ2>0σ^2>0, and any width-mm two-layer network with arbitrary real weights, biases and affine skip connection, fitting the data ε\varepsilon below the noise floor forces Lip(f)≥c εn/(mˉlog⁡(Cmˉnd/ε))\mathrm{Lip}(f)\ge c\,\varepsilon\sqrt{n/(\bar m\log(C\bar m nd/\varepsilon))}, mˉ=(K−1)m+1\bar m=(K-1)m+1, with high probability. A realized-kink-count version holds on the same event: every realized two-layer piecewise-linear function with k(f)≤nk(f)\le n distinct kink hyperplanes obeys the bound with mˉ\bar m replaced by k(f)+1k(f)+1, irrespective of how many redundant hidden units parameterize it. The proof replaces parameter-space covering, impossible for unbounded weights, by a function-space covering. The central deterministic ingredient is a rigidity lemma: on B2B_2, and on Sd−1\mathbb{S}^{d-1} for d≥3d\ge3, the coefficient of each canonical kink is controlled by the Lipschitz constant of the realized function, because kinks on distinct hyperplanes cannot cancel at generic points. Rigidity genuinely fails at d=2d=2, and an explicit two-layer ReLU interpolant with O(1)O(1) Lipschitz constant at width 2n2n matches the law at the overparameterized endpoint.

Yitzchak Shmalo

Neural Network MemorizationMultilayer PerceptronsLipschitz Neural NetworksNeural Network GeneralizationNeural Network RobustnessAdversarial Robustness+1
AskPDF
Jun 24, 2025

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

This paper studies the ℓp\ell^p-Lipschitz constants of ReLU neural networks Φ:Rd→RΦ: \mathbb{R}^d \to \mathbb{R} with random parameters for p∈[1,∞]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 ℓp\ell^p-Lipschitz constants varies significantly between the regimes p∈[1,2)p \in [1,2) and p∈[2,∞]p \in [2,\infty]. For p∈[2,∞]p \in [2,\infty], the ℓp\ell^p-Lipschitz constant behaves similarly to ∥g∥p′\|g\|_{p'}, where g∈Rdg \in \mathbb{R}^d is a standard Gaussian vector and 1/p+1/p′=11/p + 1/p' = 1. In contrast, for p∈[1,2)p \in [1,2), the ℓp\ell^p-Lipschitz constant aligns more closely with ∥g∥2\|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 ℓp\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.

Sjoerd Dirksen, Patrick Finke, Paul Geuchen +2

ReLU Neural NetworksLipschitz Neural Networks
AskPDF
Oct 5, 2026

Lipschitz Thinking: Ten Years of Certifiable-by-Design Robust Neural Networks

The Lipschitz property of a deep neural network provides a direct measure of its sensitivity to input perturbations and, when explicitly controlled, offers a principled way to limit the propagation of errors and improve robustness. Over the past decade, Lipschitz-bounded layers have been incorporated into increasingly expressive and high-performing deep models, narrowing the gap between empirical robustness and formal, by-design guarantees of stability. This article introduces the fundamental concepts underlying Lipschitz-bounded neural networks, explaining the principles behind Lipschitz-constrained layers, the mechanisms used to enforce their bounds, and how they yield robustness certificates at the cost of a single forward pass. The tutorial concludes by discussing emerging and open directions, highlighting Lipschitz control as a general framework for offering guaranteed, by-design stability.

Fabio Brau, Giorgio Piras, Maura Pintor +1

Department of Electrical and Electronic Engineering, University of Cagliari, Cagliari, Italy

Neural Network RobustnessCertified RobustnessLipschitz Neural NetworksNeural Network Stability
AskPDF