Approximation theory for 1-Lipschitz ResNets

1-Lipschitz neural networks are fundamental for generative modelling, inverse problems, and robust classifiers. In this paper, we focus on 1-Lipschitz residual networks (ResNets) based on explicit Euler steps of negative gradient flows and study their approximation capabilities. Leveraging the Restricted Stone-Weierstrass Theorem, we first show that these 1-Lipschitz ResNets are dense in the set of scalar 1-Lipschitz functions on any compact domain when width and depth are allowed to grow. We also show that these networks can exactly represent scalar piecewise affine 1-Lipschitz functions. We then prove a stronger statement: by inserting norm-constrained linear maps between the residual blocks, the same density holds when the hidden width is fixed. Because every layer obeys simple norm constraints, the resulting models can be trained with off-the-shelf optimisers. This paper provides the first universal approximation guarantees for 1-Lipschitz ResNets, laying a rigorous foundation for their practical use.

In this section, we present the primary building block behind our proposed architectures. We do so after having introduced some necessary notation and definitions.

We focus on approximating functions in the space

where X ⊆ R d , d is the input dimension, and ∥x∥ 2 2 = x ⊤ x is the Euclidean ℓ 2 -norm. Most of the paper focuses on the case c = 1, in which case we write C 1 (X , R). We will denote the network width with h, i.e., the number of hidden neurons, and the network depth with L, which is the number of layers. We interchangeably refer to a linear map and its matrix representation with the same notation, e.g., Q ∈ R h×d or Q : R d → R h . Given a matrix A ∈ R r×s , the notation ∥A∥ 2 stands for its spectral norm, i.e., ∥A∥ 2 = λ max (A ⊤ A). We also work with the vector ℓ 1 norm, which for a vector x ∈ R d is defined as

, and 0 d ∈ R d to denote the d × d identity matrix, a vector of ones, a matrix of zeros, and a vector of zeros, respectively. To refer to the Lipschitz constant of a function f : R d → R c , we use the notation Lip(f ), i.e., ∥f (y) -f (x)∥ 2 ≤ Lip(f )∥y -x∥ 2 for any x, y ∈ R d .

This paper focuses on universal approximation results for C 1 (X , R), with X ⊂ R d compact.

Definition 2.1. Let X ⊂ R d be a compact set, and consider the set of functions A ⊂ C 1 (X , R). We say that A satisfies the universal approximation property for C 1 (X , R) if, for any ε > 0 and any f ∈ C 1 (X , R) there is a g ∈ A such that

We now report the statement of the Restricted Stone-Weierstrass Theorem, i.e. [1, Lemma 1], where we adapt the notation and focus on the ℓ 2 -metric, which is the one adopted in our paper.