Approximation theory for 1-Lipschitz ResNets
Authors: Davide Murari
Takashi Furuya
Carola-Bibiane Schönlieb
Venue: NeurIPS 2025 poster ()
Keywords: Lipschitz neural networks
Universal approximation
Residual neural networks
Stone–Weierstrass theorem
Primary area: deep_learning
TL;DR: We study the approximation properties of 1-Lipschitz ResNets, and prove their density in the set of 1-Lipschitz functions.

Abstract: $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.

Approximation theory for 1-Lipschitz ResNets
Davide Murari
Department Applied Mathematics and Theoretical Physics University of Cambridge dm2011@cam ac.uk
Takashi Furuya
Faculty of Life and Medical Sciences, Department of Biomedical Engineering Doshisha University
RIKEN AIP
takashi. wwwuuraaa1100aaaaaraaa
Carola-Bibiane Schönlieb
Department of Applied Mathematics and Theoretical Physics University of Cambridge cbs31@cam ac
Abstract
1-Lipschitz neural networks are fundamental for generative modelling, inverse problems, and robust classifiers. In this paper, focus 1-Lipschitz residual net- works (ResNets) based on explicit Euler steps of negative gradient flows and study their approximation capabilities. Leveraging the Restricted Stone-Wo Weieessrssss Theorem, we first show that these 1-Lipschitz ResNets are dense in the set of scalar 1-Lipschitz functions any compact domain when width and depth allowed to grow. We also show that these networks can exactly represent scalar piecewise affine 1-Lipsehitz functions. We then prove stronger statement: by inserting norm-cons connt-cnntt 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.
Introduction
The flexibility of neural network parameterisations allows them approximate any regular enough target function arbitrarily well X
Despite this desirable aspect, there are several reasons why would not want completely unconstrained parameterisation. For instance, unconstrained networks tend to be overly sensitive to input adversarial perturbations because their local Lipschitz constants can be large, making them unreliable classifiers (34). There are also situations where one is purely interested in modelling specific sets of functions, for example, to turn constrained optimisation problem into an unconstrained one [9 31 e.g]. A prominent example is the critic in Wasserstein GANs (2), which must be I-Lipschitz to yield valid estimate of the 1- Wasseestten distance via the Kantorovich Suntorovich-Rubinstein duality [37]. In this paper, we focus on scalar-valued neural networks that are constrained to be 1-Lipschitz in the Euclidean E² norm. These generative modelling
17 20
41
networks have found extensive applications in inverse problems [6
14 21 24
and as means to improve network resilience to adversarial attacks 23
35 36
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The approximation properties of constrained networks are poorly understood, and different enforce- ment strategies can yield markedly different expressiveness. The commonly adopted strategies to constrain a network's Lipschitz constant tend to reduce its expressiveness, leading to noticeable performance drops. This paper studies the approximation properties of I Lipschitz-constrained residual networks. We propose new constrained networks that are theoretically able to approximate any scalar I-Lipschitz function arbitrarily well. Although our analysis is theoretical, the architectures we consider are readily implementable and can be trained like existing Lipschitz-constrained layers.
We next review related work (Section summarise our contributions (Section and present an outline of the paper (Section 1.3
1.1 Related work
I-Lipschitz neural networks. We can identify three principal approaches to enforce or promote Lip- schitz constraints: weight normalisation strategies, changes the network layers, and regularisation strategies, Spectral normalisation or orthogonal weight matrices provide the most well-established constraining procedure for feed-forward neural networks [24 351. When working with Residual Neural Networks (ResNets), more changes are necessary due to the skip connection. Results in dynamical systems, numerical analysis, and convex analysis lead 1-Lipschitz ResNets based on negative gradient flows [23 33 These constrained ResNets are the backhone of most of the results in this paper, and we will describe them later. They have also proven to more efficient than other constraining strategies in terms of performance and computational resource consumption [29]. Because of the empirical decrease in expressiveness with constrained networks, an alternative to hard constraining the Lipschitz constant is regularising the optimisation problem by penalising too large Lipschitz constants [14 21 38
42). Lipschitz constraints are also considered in more modern
architectures, such as Transformers 9 18
Approximation theory for Lipschitz-constrained networks. Constraining the Lipschitz constant of network naturally leads restricted expressiveness, in the sense that a 1-Lipschitz neural network can not approximate f(x) = x² arbitrarily well, for example. However, a more relevant question is if all the 1-Lipschitz functions can be accurately approximated by given family of 1-Lipschitz networks. In [. the authors present the Restricted Stone- Weierstrass Theorem and prove that feed-forward networks based on the GroupSort activation function and corm-constrained weights are dense in the set of scalar 1-Lipschitz functions. This theorem is fundamental for our derivations as well, and we state it in Section 2 In [25], the authors study feed-forward networks with splines as activation functions and show that they have the same expressiveness as the networks studied in [. To the best of our knowledge, no such results are available for 1-Lipschitz ResNets. Closely related to ResNets, we mention [10] where the authors show that Neural ODEs with a constraint on the Lipschitz constant of the flow map are still universal approximators of continuous functions if the linear lifting and projection layers are left unconstrained.
For further motivation of why we study 1-Lipschitz ResNets and why the 1-LLisschizz constraint is relevant, see Appendix F.I
1.2
Main contributions
This paper studies the approximation capabilities of 1-Lipschitz Residual Neural Networks (ResNets). We focus ReI.U(x) = max(x; 0) as activation function.
Relying on the Restricted Soiee-Wiessssrsss ResNets with residual layers based on explicit Euler steps of negative gradient flows is dense in the set of scalar 1-Lipschitz functions. To achieve this approximation result, we allow for networks of arbitrary width and depth. We also provide an alternative proof by showing, in Theorem 3.2 that this set of networks contains all the 1-Lipschitz piecewise affine functions. This alternative derivation provides further insights into the considered networks. It also informs the other main result of the paper, where the network width is fixed, allowing us to connect these two main theorems. This density result extended to vector-valued 1-Lipschitz functions as well, Lemma 5.1
Theorem, in Theorem 3.1 we show that a class of
By interleaving the residual layers with suitably constrained linear maps, we show, in Theorem 4. that the width can be fixed while preserving the density in the set of scalar 1-Lipschitz functions. This

---

Theorem forces us second main result allows us to propose new, practically implementable ResNet-like architecture that is flexible enough to approximate to arbitrary accuracy any scalar 1-Lipschitz function.
We remark that one of the main novelties of our analysis lies in proving the universality of 1- Lipschitz ResNets without relying the Restricted Ktone-Weierstraa Theorem, and in providing two alternative viewpoints to our analysis, thereby gaining deeper understanding of Lipschitz- continuous ResNets. Not directly relying on the Restricted to understand that the set of considered networks contains a very well-studied set of functions: I-Lipschitz piecewise affine functions. This derivation has sigmificant consequences, since allows us to transfer the approximation properties of this function class to our neural networks. In other words, part of our theoretical derivations is constructive and is hence informative on what can be represented through the set of networks we consider. On the other hand, the Restrictive-Stur Weierstrass Theorem provides a very general technique for analysing parametric sets of functions and allows for obtaining universality in non-constructive manner.
1.3 Outline of the paper
The paper is structured as follows. Section introduces the primary building block behind our network architectures and some needed notation. In Section 3 we prove that class of 1-Lipschitz ResNets with an arbitrary number of layers and hidden neurons, is dense in the set of 1-L-ischitz scalar functions. Section [ provides the second main result, where show that the same density result can be obtained by fixing the number of hidden neurons and slightly modifying the architecture. Section discusses the implications of these results and outlines potential extensions.
Preliminaries
In this section, we present the primary building block behind our proposed architectures. We do so after having introduced some necessary notation and definitions.
2.1 Notation
We focus on approximating functions the space
C (xX, =
((: 9 R
(1a(y) g(x))l2 S lly x112 Va, E x].
where X' C Rd, d the input dimension, and ||^||| = TT x the Euclidean -nomm. Most of the paper focuses on the case 1. in which case we write CXX' R). We will denote the network width with h, ie., the number of hidden neurons, and the network depth with L, which is the number of layers. We interchangeably refer to linear map and its matrix representation with the same notation, e.g., Q E RAx or Q Rdd - Ra Given a matrix
R the notation ||Al|2 stands (A (A A). We also work with the vector ll norm, which Rd is defined as ||=||1 Ei= [zz]. We write Ia Raxd la Rd, Oa, Rdxh, and 0L E Rd to denote the d x identity matrix, vector of ones, matrix of zeros, and vector of zeros, respectively. To refer to the Lipschitz constant a function of :d - IR" we use the notation Lip(f), i.., (g) f(x)]l2 I Lip(f)lly æ|1a for any x, y E Rd
for its spectral norm, i.e., ||A||2 = V Amaxx for vector
2.2 Universal approximation property
This paper focuses on universal approximation results for Cx R), with X' C Rdd compact.
Definition 2.1. Let X C Rdd be compact set, and consider the of functions A Cx R). We say that A satisfies the universal approximation property for C₁ (X, R) if. for any E > 0 and any C, (X, there is g A such that
max 1f(x) -g(x) <E. x
We now report the statement of the Restricted Stone- Weierstrass Theorem, i.e. 0 Lemma 1], where we adapt the notation and focus the mmmmrcc which is the one adopted in paper.
3

---

Definition 2.2 (Lattice). Let X' C Rd and consider a set A functions from X' to R. A is a lattice if for any pair of functions f.g E A. the functions h, k X + R defined as h(z) max(f(x).
and k(xz) min(f(()) ([(2), ( belong to A as well.
Definition 2.3 (Subset separating points). Let X C Rd be a set with at least two points and consider sel A C C1 (X, RR. A sepurates the points of X for any pair of distinct elements a. y E X and real numbers a, E with |a - b] = 2 there is an f E A such that f(x) = a and f(y) = b. Theorem 2.1 (Restricted Stone- Weierstrass). Let X C. Bd be compact and have least two points. Let A C C1(2, R) be a lattice separating the points of X. Then A satisfies the universal approximation property for Ci RR).
2.3 1- I-Lipschitz residual layers
The main building block of ResNets are layers of the form + (x) =: (x), where E Rd, and Fe, R Rd is parametric map depending the parameters collected in 0g. We recall that given two Lipschitz continuous functions f Rd + Rd and g R& Rds, 3, the Lipschitz constant of = go o
Rd + Idd satisfies Lip(h) < Lip(f)) For this reason, to build 1-Lipschitz networks, one typically works with layers that are all 1-Lipschitz. For generic Lipschitz continuous function Fo,, it is challenging to have better bound than Lip S + Lip( Fo,), ) which is the one following from the triangular inequality. However, by making further assumptions of the form of Fe,, it is possible to get 1-Lipschitz residual layers, as formalised in the following proposition.
Proposition 2.1 (Theorem 2.3 and Lemma 2.5 in (3)). Assume : R + R is Lipschhitz continuous
and non-decreasing. and define Po, R - R.a as
T W (WEE + be) with We E hexh ER, DER th having 0 S S 2/ Then, Lip(#a.) 1.
(x)
The map lh, can be interpreted differential equation & = - oWWzz + by) = - (r)),,, (x = 17, 7WWz + be), 7 R + R defined by Y =a a. We define the set of residual layers satisfying the assumptions of Proposition 2.1 and having weights with spectral norm bounded by one:
single explicit Euler step of size for the negative gradient flow
En.o 4g R - R²
Φo(x) = - W (WW + b). W E Rk be b
W 22 S 1, KEN 0= (W,b), 05 2,
to improve the robustness to adversarial attacks, and in (3 to approximate the proximal operator and develop a provably convergent Plug- and-Play algorithm for inverse problems.
ResNets with layers as ( have been used in
23 29 33
We will work with residual layers that satisfy the assumptions of Proposition 2. and combine them with suitably constrained affine maps to prove our density results. Our focus on the activation function (x) = (eLU(z) = max(0, x). which satisfies the assumptions and simplifies several derivations since it allows us to represent the identity, and the entrywise maximum and minimum functions exactly, which are fundamental operations for our theory. They can be recovered as
x' === o (z) - o-=2), max(x, y} = x + oly - z), min(x, y} = I o(x - v), Yx,y E Rd.
Some linear maps belong to &n as well, as formalised in the next lemma.
Lemma 2.1. Let M e gxxh be symmetric matrix with eigenvalues all in the interval [o, 1]. Then the linear map x ++ Mx belongs to En,o if a ReLU.
Proof. The matrix M In is symmetric and negative semi-definite. Thus, it can be diagonalised as M II, R A with R R = RR In and A diag( ..., A.)) having ||A||2 1. Define
V = A.R. Then,
V V2 1
Mr - == -VV -o(V))))o((-v
( LTT
32 VTT)
a
V
=: -w - T = - ( VT - - VT)
where we used the positive homogeneity of a, i.e. (7:r) = (xx)) for all x E R and 7 2
We
conclude the desired result by setting T = 2, and noticing that [|]l < since || ||2 < 1.

---

Density with unbounded width and depth
In this section, we consider the following set of parametric maps
Gd (2, = ((x,)) Dgg Pg QQ: +R Q(x)= Qu + Q R
E WE EER ||el| to. E En,or I, E.E
We remark that in the definition of Ga. (X, , TR), the matrix Q is not directly constrained in its norm. However, the intersection with (Xt, IR) only allows to consider 1-Lipschitz maps. The lack of explicit constraints over Q leads to problems when implementing these networks, if the goal is to guarantee their 1 1-Lipschitz regularity. This situation will be resolved by the practicality of the set of networks considered Section 4 Still, one way to leverage the theory we develop for Gá,o (X, R) in numerical simulations to leave Q unconstrained while training the model, but simultaneously regularising the loss function so that the Lipschitz constant of the network is controlled by one, as done, for example, in [21]
o = ReLU and X' C IRd be compact. Then, Gd.0 (2, R) satisfies the Theorem 3.1. Let d E N.
universal approximation property for (XX,E) R).
We prove this theorem in two ways since they provide different perspectives towards the set gd. (X, R). First, Section 3.1 we verify that (a, , IR) satisfies the assumptions of Theo- rem 2.1 Then, in Section 3.2 show that all the piecewise-linear 1-Lipschitz functions from X to belong to (X, R).
3.1 Proof of Theorem 3.1 based on Restricted Weine-Weesssssss
Lemma 3.1. Let d E N, X C IRd have at least two points, and a = ReLU. Then Gá, (X, R) separates the points of X.
The proof of this lemma is in Appendix A.I and relies the fact that all the affine 1-Lipschitz functions from X' to belong to Ga (X, R).
Lemma 3.2. Let d E E X' Rd
ReLU. Consider two functions ʃ.g E Ga R). There exist L E N. h h2 N, vn E Rh 022
Rha with ||u2||2 ||u2||2 = Q1 Rdd - Rhv and Q2 Rdd + Rha affine maps. Do ..... Po,, E Ehithaao and M E RR (hhh+th))((bttt))) symmetric positive semiidefinite with || |Mll2 S 1, such that
f(z) 9(x)
[Q1 Q2
= M Pa o Do
W.
The proof of this lemma is in Appendix A.I and is based on the fact that the identity map on R² belongs E,. We remark that, by Lemma 2.1 the linear map defined by M belongs Eny
Lemma 3.3. Let d E N, X C Rd, and a = ReLU, The set Gd. (X, IR. is lattice.
Proof. Let f.g E (R). We show that h : X - R defined by h(()) = max max(f(x)) f(x))g(()) g(x)) belongs to (X, R) as well. Analogously, one can show that also k(x;) belongs to the set, which is hence a lattice. Recall that since If and are 1-Lipschitz, k and will be 1-Lipschitz as well. Thus, we just have to check that and & can be written as an element of the parametric set we intersect with Ci (X,, IR). Lemma 3.2 allows us to write
(x).
fx)
Q1 Q2
g(x)U2)
Poz Poz o... La
x.
We then define
11
WL+2
1
-o 2i E (1x br+2 = Ohy TL+2 =
0pz
/
5

---

We see that [WL+2l S 1, and hence P0 (x) = 2 - TL+2 L+2 (W + bL+2) belongs to
Eh, a Furthermore, we also notice that ||0|2 = L, and that
[1
= v Da (
v 10442 o 1Br+r o Der o o Dø o
Q2
[((r)) ((z))22
Mi max (M()( = h(x)
+
o - -(x)))
|0] 0
U2 min ((x)
02
as desired.
We have now proved that Gd.o (X, IR) is a lattice that separates the points of X. Thus, it satisfies the universal approximation property for C1 (xY,)) R).
3.2 Proof of Theorem 3.1 based on piecewise affine functions
This argument is based on showing that all the sealar, piecewise affine, 1-Lipschitz functions over X' belong to Ga,0 IR..
We now present a more constructive reasoning to prove Theorem 3.1
Definition 3.1. A continuous functiion f IRd + IR. is piecewise affine if there exists a fifinte collection P of open, pairwise disjoint, connected sets of Rd with IR P and flp every PEP.
R is affine for
Remark 3.1. Let X Rd be compact. say that a function g: : - is piecewise affine if there
exists continuous piecewise affine function IR - R such that x. We say g X + IR piecewise affine and 1-Lipschitz (on X) if = glx for a piecewise affine 1-Lipschitz ğ R TR.
Lemma 3.4 (Theorem 4.1 in 27)). Let J: Rd RR be continuous piecewise affine function. Then, there exists choice of scalars big E R and vectors 0z,j E RRd such that
f(x) = max)=mxx[ii (1))),))))))))))))) Se(1)), fi(x) minfa]1 + bi,1, O,,, + b...
(2)
We remark that if f - R is continuous piecewise affine 1-Lipschitz function, then necessarily the vectors ag E Rdd appearing in (2) satisfy ||o, < 1. This a consequence of Rademacher's
Theorem 113 Theorem 1.6. ensuring the almost everywhere differentiability of f. which implies that (+)]l < for almost every x E Rdd.
We introduce a few fundamental results needed for such a constructive proof.
Proposition 3.1. The functions Rd 3 x + max(xi, .... Ia} = f(x) E R and Rd e + = g(x) E belong to Id. (Rd, R) with o = ReLUU.
Proof. We focus on f, and the reasoning for y is analogous. The map
x + max 11, [21, min Is
xa]
(3)
can be realised as o (z) 2WT (WWa). where
W1 [-1/V2 1/v2
0] E R lxd
Given that max(x1, T2, x3} max/max / 21, m2). mz). }. it follows that choosing
W₂ = [-1/V 1/V2 0 0] Rxdd
one has that t (x) - 2W, a oW2 (x)) takes the form
(max( v3} min min((r (m) min (xx(21)02)) .4
We can thus call o, (z) = x 2W, a (Wzz). The argument continues up to when, setting v cj. the first vector of the canonical basis of gd we get
Po__, .... b9, (x) maxf21,.... x2x f(x)
as desired. We remark that, in this case, = La and h d.

---

This analysis, together with Proposition 3.1 implies that scalar, piecewise affine, 1 Lipschitz functions all belong to (R. R).
as we formalise in the following theorem.
Theorem 3.2. Any piecewise affine fumction f IR R can be represented by network
in Gá.o (IR", IR with o = ReLU.
function on X Remark 3.2. Let X Rd be compact and g : X + R piecewise affine functionn
in the sense of Remark 3.1 Then, there exists a piecewise affine 1-Lipschitz function
fuipscchtz,uunctinn 9 IR + R
such that g = g. Applying Theorem 3.2 9 yields a network N E Gá.o (R ,R) such that N on 12,; hence, by restriction, N/xx Ga IR) and N = g on X.
See Appendix A.2 for the proof. A proof of Theorem 3.1 then follows from the universal approxima- tion property of piecewise affine 1-Lipschitz maps defined on a compact set X' in (x, R).
Lemma 3.5. The set of piecewise affine --uipichit,.uunctions functions over X C Rd, a compuct set, satisfies the universal approximation property for Ci R).
To prove this lemma, one could use the Restricted Stone- Sone-Weiessssrss Theorem, since the set of piecewise affine 1-Lipschitz functions is a lattice separating points. We provide a more explicit and direct proof of Lemma 3.5 for the case X' is convex polytope in Appendix A.2
4 Density with fixed width and unbounded depth
Theorem 3.1 ensures that it is possible approximate to arbitrary accuracy any scalar 1-Lipschitz function over a compact set X' by using ResNets relying on negative gradient steps. This result is informative but it has two drawbacks: (i) the elements of Ga (X, IR) do not have explicit constraints on the affine lifting layer Q, making them challenging to implement, (ii) there is no control neither on the depth nor on the width of the networks in Gd R). We now address these limitations by providing second set of 1-Lipschitz networks, which are easier to implement and have fixed width.
For the derivations in this section, need to introduce two sets of suitably constrained affine maps. Let E N, fix a vector m E N and call Om = ||mm]] = my + + m,- We define
[An
A
Zm {
AERO Xoem
A=
:
Aij E R m Xmy, Σ IA S $1, 1, I,... k
Aki
Aus
Lm { A: RRom - RR
BÂ Lm,
ā E Romm
A(u) Au + a. Vu E Ram
[1]
Rd,m- { BER xd
B
:
B, E Rm |Bill2 $ i 1,.... 16.
B
Ram-
= Rdd
{o:
- gom
3 E Ra q E aan Q(x) Qu + a. Vor E IRd
We also extend the set of functions En to subset of Ex as follows
(max( 22) min x22) D3'
En.o = {0p: RR++3
:Rh+3 + RR++ (o(x)=
To E En }.
(x..))
where, for & E Rh+3 Ty. 2 denotes vector coinciding with which the first three entries removed. We remark that the first two components of the functions in En.. resemble the MaxMin activation in [ or the Orthogonal Permutation Linear Unit in 77
Lemma 4.1. Let h E N and = ReLU. The set Ên,o is subset of Ent3.o-
See Appendix C for the proof.
Fix h 2 3. We now consider the set
Ta RX = UT Ps, Ar-1 o... P o A c by, o x m = (1,1,,,1, 3),
Q E Rymms V E RR, ||ol2 S 1, ,,,.. AL-1 E Lm, Dog E En-3,0 L LEN].
7

---

Lemma 4.2. Let ReLU, d,h E N, with h 2 3. All the functions in Fo.o (R"" R) are 1 1-Lisschitz.
See Appendix Si the proof. This lemma addresses the first limitation in the definition of (X, given that we explicit constraints over all the terms defining neural network Gd,o, (, R).
We now state the second main result of this paper.
Theorem 4.1. Let N, ReL.U, and X C R2 be compact. The Gd (X, IR) satisfies the universal approximation property for Ci (X,R). R).
This result ensures we can fix the network width mation property. We will further comment on the connections between the two sets Gá.o (X' R) and Gd X, IR) and extensions of the set Gd (X, , IR) in Section 5 We remark that our proof of Theorem 4.1 relies on setting @p(xrs)) = 24: for the elements in E, Still, we present the results for the larger set of allowed residual maps E, since, in practice, this additional freedom can lead to more efficient approximations of target maps than the one provided constructively in our proof.
+ 3 and preserve the universal approxi-
4.1 Proof Theorem
This proof follows similar ideas the one presented in Section 3.2
Proposition 4.1. Fix n E N, ai...., an E Rdd and bi..... bn E R, with ||a Mealla:... ..., laxllz S 1. The functions RRd 3 x + max + bn.... a x + bn} = f(x) E IR and Rd 3 x + min(a [ x
b, x bn g(x) R belong to Id (RR, R) with = ReLU and h d +
Proof. We focus on f, and a similar reasoning applies for Set W, = Od B, = O2. and Q so that
Do o ((x)) ) = [maxfal x + b,, az x + b2) min(a] x - b,, a x b2) 0 x TT]
where To (x) = x -2 (W x + b.). Set m = 1,, Let us then introduce A₁ E f. defined as A1(x) A + कi where
0
0
0 by
Ā
0
0
0
0g
E k āi
E
RRA
0
0
0,
0
O0
0a
Ia-
0
so that
A Po. Q(x) [max(a] [a]x bi, ag x b2]
a3 x + by
x TT| l2.
The next step build La, so that
maxfa + by, a x b2, ag x bs}
min/max x + b, + b2), ag bg}
Dop o Ai o Lo. o Q((x)=
0
The reasoning extends up when reach the final configuration, after L residual maps, where T Po, o AL-1 Lo..,, o o... o A₁ Dg, Q(x) = f(x), by fixing v = 61 E R
We remark that in the proof of Proposition 4.1 the third entry is irrelevant, and the fourth component is used as a memory of the original input x. The third component is fundamental in the proof of Theorem 4.2 which is why it is included. Keeping track a. x + b; online, without generating them all at the beginning we did in the proof of Theorem 3.2 This operation allows us to detach the hidden dimension h from the number of linear pieces, and get universal approximation theorem for fixed network width.
essential to recover the affine pieces
Theorem 4.2. Any piecewise affine 1-Lipschitz,uuncee f IRd + R can be represented by network
in Gao (Rd. R) with ReLU and h d 3.

---

The proof of Theorem 4.2 relies on the representation of piecewise affine 1 1-Lipschitz functions in 22) the construction presented in the proof of Proposition 4.1 and on using the third component as running maximum of the previously computed minima. See Appendix C for the full proof.
The proof of Theorem 4. then follows by combining Theorem with Lemma 3.5
We discuss how the network size depends on the input dimension E N in Appendix F2
Remark 4.1. The set of networks G R.atLLL,dss(4 R) contains all the piecewise affine 1-Lipschitz functions, as stated in Theorem 4.2 On the other hand, it is also true that all the elements of Gd, a+3,,, X, IR) are piecewise affine 1-Lipschitz, functions. The latter result follows from the fact that ReLU is piecewise affine, and we only compose it with affine maps. This reasoning allows us to conclude that the new architecture that we propose and study in Theorem 4.1 coincides with the set of piecewise affine 1-Lipschitz finctionn, and provides yet another representation strategy for this lattice of functions.
coinniies
Discussion and future work
We connect two main theorems, comment their practical value, and provide relevant extensions.
we followed two strategies: verified that the assumptions of the Restricted Stone Weierstrass Theorem satisfied by Gd.o (X, RR, and verified that Gd (X', (X) R) contains all the scalar piecewise affine and 1-Lipschitz functions. The two arguments strictly related. In fact, the first relies on showing that Gd, IR) is lattice separating the points of X, while the second shows that Gd,- , R) contains a lattice that separates points. This latter strategy is the one used prove Theorem 4.1 1 as well.
Different proving strategies. To prove Theorem 3.1
Necessity for the affine maps Ai...., AL-1 E L.- To obtain universality while maintaining the width fixed, we introduced affine layers between the residual gradient steps. Setting them to identity maps would lead to a subset of G. (X, R) which might not be universal. Since these maps are not 1-Lipschitz maps from Ram itself, we had restrict the set of allowed gradient steps to En.r C E, It is thus interesting to further explore if is possible to remove these affine maps and allow for more general gradient steps. Still, there are two fundamental aspects to mention.
First, get a 1-Lipschitz network, is necessary to have all the layers that 1-Lipschitz, as demonstrated by the maps Gu. (X' R). This idea explored in 4 where the authors build 1-Lipschitz networks combining 1-Lipschitz maps as in & with positive gradient steps of the form - u + T oWWu - b). It will thus be interesting to further explore this path for future research.
Second, the restriction defined in ε..o provides a rather minimal set to carry out the proofs in this paper. One can generalise while preserving the Lipschitz property and potentially getting more practically efficient networks. We provide a generalisation of Ên,o and Gd. R) in Appendix D
Both the main results we proved this paper ensure the universality of neural networks that rely residual layers coming from negative gradient flows. Theorem 3.1 focuses on architectures studied in [3 29 331, while Theorem 4. considers new, practically implementable constrained architecture that propose. It is essential to note that in [23 29 33) the elements in Ga. (2', R) are implemented with unit-norm constraint on the lifting map Q : R2d + A Our theory does not allow us to say that this constraining strategy provides set of networks dense in C₁ (X, IR), and hence leaving it unconstrained while regularising for the network to be almost I-Lipschitz would be better strategy according to our analysis.
Connections between Theorem 3.1 and Theorem 4.1
Theorem 4. trades the unlimited width of Theorem 3.1 for additional constrained linear layers. Still, there are several similarities between the two theorems. For example, the constrained maps in En,o appear also in the proof of Theorem 3. see, for example, (3)
Extension to multivalued functions. This paper focuses on C. (X,, R). Some of our results extend to the functions in C₁ (X, RR), as formalised by the following lemma, with proof in Appendix E

---

Lemma 5.1. Let C, X' C R be compact, and a ReLU. Define the set
Ge,do (x) == P Loz o... o Lo. o QQ: + R [(())) = Qx + [0(x)= Q Raxd
ERT P E Rexh, ||||2,00 = 1, Po, E EEho, L, ENJ
Then, for any f C((,)))) and e O, exists g (,, with max lf(x)) -((x)l22 e.
Since we are not intersecting with the set of 1-Lipschitz functions, this time, it is not true that Go,d.o (X, (R=) C Ci IK)). In fact, since || max; I....e |le Pll2, where ej R is the I1,d, (X, R Extending the universality
i-th vector of the canonical basis, we have
result of & (X, I) and enforcing the Lipschitz constraint will be the topic for future research.
Extension to larger sets of parametric functions. As for any universal approximation theorem, the theoretical analysis provide can be extended to sets containing Gd.o (X, R) and Gd.o, (XX, R). For example, the universality of Gá (X, RR implies that the universality persists relaxing the constraint over e E RRA from ||:i|2 = to ||l|| < 1. Similarly, we can remove the constraints on the matrices We, and allow for Te 2/ We 1l2. still leading to 1 1-Lipschitz Fuler steps, see Proposition 2.1 In fact, ||Well2 S 1 with Tę E [0, 2] is particular instance of this constraint. Relaxing such constrants could improve the numerical performance, given that the model would be less restricted.
Extension to other activation functions. Our proofs strongly rely on the properties of ReLU, The same results could be obtained by any other activation functions that are positively homogeneous, can represent the identity map, and the entrywise maximum and minimum functions. When this is not the case, developing a similar theory would require significantly different arguments. For the further discussion of other activation functions, see Appendix F3
Implementability of our networks. The elements of Ga.o (XX, (X, and Gdo., R) are neural networks that can be numerically implemented. All the weight constraints can be efficiently enforced in projected gradient descent fashion. The spectral norms can be estimated via the power method, see [24). whereas row-wise constraints as in L. can be enforced by dividing by the e norms of the rows. We further remark that the lack of explicit constraints the lifting map Q in Ga (X, R) can be overcome by regularising the loss function with a term penalising the violation of the Lipschitz constraint, such as Σi=1 > (ReI.U[) V.. V..N
1))². This additional term promotes the local Lipschitz constant of the network No : Rdd + R to be smaller or equal than one, see [21] The locations I ...: &N E X can be randomly sampled during each training iteration. For some empirical validation of the implementability and trainability of our networks, see Appendix G
N
Acknowledgements
DM acknowledges support from the EPSRC programme grant in 'The Mathematics of Deep Learning', under the project EP/V026259/1. TF was supported by JSPS KAKENHI Grant Number JP24K I 66499, 25H01453, JST CREST JPMJCR24Q5, JST ASPIRE JPMIAP2329. CBS acknowledges support from the Philip Leverhulme Prize, the Royal Society Wolfson Fellowship, the EPSRC advanced career fellowship EP/V029428/1. the EPSRC programme grant EP/V026259/1, and the EPSRC grants EP/S026045/1 and EP/T00355//1, EP/NO14588// EP/T0I7961// the Wellcome Innovator Awards 215733///19/Z and 221 221633/2/20/Z, the European Union Horizon 2020 research and innovation pro- gramme under the Marie Skodowska- Curre grant agreement NoMADS and REMODEL, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute. This research was also supported by the NIHR Cambridge Biomedical Research Centre (NIHR203312), The views expressed are those of the author(s) and not necessarily those of the NIHR or the Department of Health and Social Care.
References
[1] Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In International Conference Machine Learning, pages 291-301. PMLR, 2019.
10

---

[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein Generative Adversarial Networks. In International Conference on Machine Learning, pages 214-223. PMLR, 2017.
[3] Valérie Castin, Pierre Ablin, and Gabriel Peyré. How smooth is attention? arXiv preprint arXiv:2312. 14820, 2023.
[4] Elena Celledoni, Davide Murari, Brynjulf Owren, Carola-Bibiane Schönlieb, and Ferdia Sherry. Dynamical Systems- Neural Networks. SIAM Journal on Scientific Computing, 45(6):33011-33994 2023.
[5] Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Optimization-iie Induced Graph Implicit Nonlinear Diffusion. In International Conference Machine Learning, pages 3648-3661. PMLR, 2022.
[6] Yanqi Cheng, Carola-Bibiane Schönlieb, and Angelica Aviles- You kan do it in single shot: Plug-and-play methods with single-instance priors. arXiv preprint arXiv:2412.06204 2024.
[7] Artem Chernodub and Dimitri Nowicki. Norm-preserving Orthogonal Permutation Linear Unit Activation Functions (OPLU). arXiv preprint arXiv:1604.023: 02313, 2016.
[8] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314 1989.
[9] George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz Normalization for Self- Attention Layers with Application Graph Neural Networks. In International Conference on Machine Learning, pages 1456-2466 PMLR, 2021.
[10] Arturo De Marinis, Davide Murari, Elena Celledoni, Nicola Guglielmi, Brynjulf Owren, and Francesco Tudisco. Approximation properties of neural ODEs. arXiv preprint 1rXiv:2503.15666, 2025.
[11] Moshe Eliasof, Eldad Haber, and Eran Treister. PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations. Advances in neural information processing systems, 34:3836-3849,002
[12] Moshe Eliasof, Davide Murari, Ferdia Sherry, and Carola-Bibiane Schönlieb. Resilient Graph Neural Networks: A Coupled Dynamical Systems Approach. In ECAI 2024, pages 1607-1614. IOS Press, 2024.
[13] Herbert Federer. Geometric Measure Theory. Springer, 2014.
[14] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved Training of Wasserstein GANs. Advances in Neural Information Processing Systems, 30, 2017.
[15] Boris Hanin and Mark Sellke. Approximating Continuous Functions by Relu Nets of Minimal Width. arXiv preprint arXiv: /278, 2017.
[16] Johannes Hertrich, Sebastian Neumayer, and Gabriele Steidl. Convolutional Proximal Neural Networks and Plug-and-Play Algorithms. Linear Algebra and its Applications, 631:203-22 2021.
[17] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer Feedforward Networks are Universal Approximators. Neural Networks, 2(5):359-366, 1989.
[18] Hyunjik Kim, George Papamakarios, and Andriy Mnih. The Lipschitz Constant of Self- Attention. International Conference on Machine Learning, pages 3562-5571. PMLR, 2021.
[19] Carl Leake and Daniele Mortari. Deep Theory of Functional Connections: A New Method for Estimating the Solutions of Partial Differential Equations. Machine Learning and Knowledge Extraction, 2(1):37-55, 2020.

---

[20] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):661-867, 1993.
[21] Sebastian Lunz, Ozan Öktem, and Carola-Bibiane Schönlieb. Adversarial Regularizers in Inverse Problems. Advances in Neural Information Processing Systems, 31, 2018.
[22] Alex Massucco, Davide Murari, and Biriia- Schönlieh. Neural Networks with Orthogo- nal Jacobian. arXiv preprint arXiv: 02882,
[23] Laurent Meunier. Blaise J Delattre. Alexandre Araujo, and Alexandre Allauzen. A Dynamical System Perspective for Lipschitz Neural Networks. In International Conference on Machine Learning, pages 15484-15500) PMLR, 2022.
[24] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral Normaliza- tion for Generative Adversarial Networks. arXiv preprint FrXXiv:802.050000 2018.
[25] Sebastian Neumayer, Alexis Goujon, Pakshal Bohra, and Michael Unser. Approximation of Lipschitz Functions using Deep Spline Neural Networks. SIAM Journal on Mathematies of Data Science, 5(2):306-322, 2023.
[26] Joost AA Opschoor, Philipp C Petersen, and Christoph Schwab. Deep ReLU networks and high-order finite element methods. Analysis and Applications, 18(05):715-770, 2020.
[27] Sergei Ovchinnikov. Max-Min Representation of Piecewise Linear Functions. arXiv preprint math/0009026, 2000.
[28] Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8:14 1999.
[29] Bernd Prach, Fabio Brau, Giorgio Buttazzo, and Christoph H Lampert. 1-Lipschitz Layers Compared: Memory, Speed, and Certifiable Robustness. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 24574-24583, 2024.
[30] Xianbiao Qi, Jianan Wang, Yihao Chen, Yukai Shi, and Lei Zhang. Lipsformer: Introducing Lipschitz Continuity to Vision Transformers. arXiv preprint arXiv:2304.099. 2023.
[31] Jack Richter-Powell, Yaron Lipman, and Ricky TQ Chen. Neural Conservation Laws: A Divergence-Free Perspective. Advances in Neural Information Processing Systems, 35:38075- 38088, 2022.
[32] Ernest Ryu, Jialin Liu, Sicheng Wang, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Plug-and-Play Methods Provably Converge with Properly Trained Denoisers. In International Conference on Muchine Learning, pages 5546-5557. PMLR, 2019.
[33] Ferdia Sherry, Elena Celledoni, Matthias J Ehrhardt, Davide Murari, Brynjulf Owren, and Birola-Bibiane Schönlieb. Designing Stable Neural Networks using Convex Analysis and ODEs. Physica D: Nonlinear Phenomena, 463:134159, 2024.
[34] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199, 2013.
[35] Asher Trockman and Zico Kolter. Orthogonalizing Convolutional Layers with the Cayley Transform. arXiv preprint arXiv: 104.0720, 2021.
[36] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certi- fication of Perturbation Invariance for Deep Neural Networks. Advances Neural Information Processing Systems, 31, 2018
[37] Cédric Villani. Optimal Transport: Old and New, volume 338. Springer, 2008
[38] Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X Yu. Orthogonal Convolutional Neural Networks. In Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition, pages 11 11505-11515, 2020.
12

---

[39] Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein. Samuel Schoenholz, and Jeffrey Pen- nington. Dynamical Isometry and Mean Field Theory of CNNs: How Train 10,000-Layer Vanilla Convolutional Neural Networks. In International conference on machine learning. pages 5393-5402. PMLR, 2018.
[40] Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103-114, 2017.
[41] Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. In Conference on Learning Theory, 2018.
[42] Yuichi Yoshida and Takeru Miyato. Spectral Norm Regularization for Improving the Generaliz- ability of Deep Learning. arXiv preprint arXiv:1705. 2017.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
13

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Sections 23
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
15

---

Justification:
The experiments are only to support the theory, and they are not meant to be exhaustive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
16

---

Answer: [NA]
Justification:
This paper is fundamental and theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
17

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, palasets.papersstt paperswi thcode. com con/dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httppe///earrrpccccc///oeeeerrre for what should or should not be described.
19

---

A Proofs in Section 3
A.1 Proof of Theorem 3.1 based on Restricted Stone-Weierstee
In this appendix, we provide proof the lemmas used in Section 3.1 Before proving them, we report the statement as well.
We start with Lemma 3.1
Lemma A.1. Let d E N, X' S Id have at least two points, and o = ReLU, Then Gá.o (N, R) separates the points of X.
Proof. Consider the functions in Gd.- R R) with h = 1 and L = 0. These are all and only the 1 1-Lipschitz affine functions of the form (xx) = u + w, for pair E Id and w E R, with | & Let v, y E X' be distinct points and a, b be such that = yyy x ==12--2211 Let
x y
E IR..
Since ū_ x -- -. a Txx y)
||
v 2
+ O, the linear system
i x
1
A w
(
ū T
y
has a unique solution. We set g(z) = Au
w. where
| y (a b).
Since Ja- - blb5 S |æ. Ull2 we conclude |\] S and hence if set g(x) -ur + w, with a Aù, we get E Id (X, R), gx) = a, and g(y) = as desired.
L
We now provide the statement and proof of Lemma 3.2
Lemma A.2. Let d E N, X CR, ReLU. Consider two functions f.g E (d R)). There
Rh²a with 1|21l22 = || = 1, Q1 Rd + Rhi and Q2 : Rd + R²2 affine maps. Db.,... Dg E Enithro and M E positive semi-definite with || S such that
exist L E N. h1 h2 E N. 01 E R²,,
symmetric
[(x)v1] M to, o Do, g(r)
Qii Q2
x.
Proof. Consider f.g Ga (X, R) that take the form
f(x) = in PoLe, o... Po,, o (1())
((x) = 1i2 Dagieg
10z, Q2(x),
with 2e,, : R. + R², for = 1, 2 and I,.... Li. Since the identity map belongs to Ento for
any h N, we can assume L1 = L2 L. Let E f1,... L} and define &,, (b2)+h2) - ((h
as o (21, = (Do (x1), t0 (I2)), for every (II, E RR x Rha, More extensively, we can write
ri - TIE TW, o (W + b1..)) I2 T2.e (W,,)) oW
D (0, x2)
b2.e)
for a suitable choice of parameters. The dimensions of these parameters are: T1,6, 72, E R, WI. e e W2.8 E 2x2,,, b1,8 E g* and b2, E gh2 Assume, without loss of generality, that T1,6, 72, # 0 and Tıe T2.8. We remark that if either Tı, 72, same map by setting the corresponding weight matrix to zero and replacing the step with any other admissible scalar. Call y8 72,e/2, (0, 1). It follows that
could get the
I1 (i.( (Wi, + by,e)
= .21 (T-T2.)x(W1.)) (Wi, + bi,e)
T.22alVVoW 1.)) (VTeWi,En + VTebi.)
=x1 -T.2(e(W).)) ( To bb,),, Wi, := VieWi.,bb.e = Vrebi.e.
20

---

where we used the positive homogeneity of a, i.e., a(yz) = yo(x)) for all z E R and 2 0. Since v (0, 1), the property |Well I 1 is preserved by this manipulation and, therefore, we can assume to have TI, = =2.8 = Ty for every = ,,,,, L. It follows that
σ1 T (W To + b1.e)
Dg (21, =
82 Te(W2,e) (22,002 + b2,e)
21
Wi,e Oha.eshi
Opn,e.h2 W2,t
T
( ((
((WWee
Wi, Ohg.chk
Opn W2,8
21
bi,t b2,e)
Te
+
2/2
x2
21
TeWe
21 We
+ be
x22
222
We
W1,t
e W2,e
E ( (( xa,e)x Be =
E Rlh..etha.))
Ong.esha
122
We also remark that
[ellz = max (2 1
Let us then consider the matrix
M
ui Ob
Oh U2
R (hhh+ha)x(h
which is symmetric, positive semi-definite and with ||M 2 <. as desired. immediate see that M plays the desired role, given the expression for and in (4)
A.2 Proof of Theorem 3.1 based on piecewise affine functions
We now provide the statement and proof of Theorem 3.2
Theorem A.1. Any piecewise affine I-Lipschitz function f Rd - I can be represented by network in Gd (Rd, R) with = ReL.U.
Proof. By Lemma 3.4 there exists a choice of scalars b,.j E IR and vectors ai, Rd such that
f(x) = max mmxx(f((a)) (f((), fx(x)), f((x) = min(a x + bi.1 bi.1. a.....,,,. + b I, i = 1,... k,
where ||a,,1l2 I Fix h + ... ls. We Q Aud and q E R as
bb.11
:
01,4
b1.
q
:
0g
by.1
[bp.
Then, by Proposition 3.1 we conclude that there exists a choice Po .... Po,, with S 1)
(max (1,, (.......]]] 1), and unit-norm vector R such that
f -=u² T Poz o.. Lo o Q
where Q(x) = Qr + 7. as desired. More explicitly, the first max max (1, 1 residual layers can be used to assemble the functions (x), .... fx) in parallel, using block diagonal weight matrices. After these, the remaining k 1 can be used to extract their minimum. We remark that, despite Q is 1-Lipschitz, the resulting map f 1-Lipschitz, and hence belongs Ga.o (R. R).
We now provide the statement and proof of Lemma 3.5 for convex polytopes.
Lemma A.3. The set of piecewise affine --Liicciit.ffnnction functions over X TRdd a compact and convex polytope, satisfies the universal approximation property for (X,
21

---

Proof. Let f X + R be an arbitrary 1-Lipschitz function, and fix ε > 0. Consider covering {S 1, .... ]] of X' into simplices having intersections that are either trivial, or coincide with vertex, or with facet. Assume, without loss of generality, that for every Sr. one has
max min #ES. EV(())
| Fi,5 122 S E/2.
where V(S)) is the of vertices of S, Let :S; R be a Lipschitz piecewise affine interpolant of f on the vertices of S,, i.c. such that gi(2;.)) = [(xi,) for every æi.j E V(S)). To build Jt one could for example follow the construction in [25 Proof of Proposition 2.2]. Then, for every æ E S. there exists zi. E V(S:) for which
(f() 9: (x)) = (f(x) f(z;)) + f(x,,) - 9;(x)) - 2|| - 22gعl2 S E.
We can now glue the local pieces to assemble the piecewise affine continuous function g(æ) N - 1s. (x)) where
{ 1, S (x) - 1 0, $ S
The Lipschitz constant of g is given by Lip(g) max;= Tip(g:) 1. In fact, let let X and
define the line segment s(t) = x+-i(y=0) E [0, 1], satisfying s0) = x and s(1) = y. By convexity of X, s(00, 1]) X' holds as well. Thus, there exists finite of scalars S t2 <.. < t S 1 such that s(4; E St, n Sm, for pair of indices 4, my E NJ. Let us also define to = 0 and tK+1 1. We thus have that
K Σ 1=
K Σ 2=0
[s((-1) -(4))l)
(4+1 wllly - x||2 = Ily - =
and hence
(g(0) - -(x)]
Σ - =(m)
Σ ge, (s(t++1)) ge, (st:))
K
K
$
max Lip(ss)
Σ 1=0
[(((+1)) stt))ll
j=I..,
k=0
max Lip(g)) I=I...,,N
11 - 2112 < 1y -112-
We remark that the equality in (#) follows from the convexity of the simplices, which guarantees that the line segment connecting s(4;) to st;--) is fully contained in S,, and the continuity g at the boundaries of the simplices.
We conclude that
max ff(z) g(x)] <
where is piecewise affine and 1-Lipschitz.
B Preliminary results for Section 4
Fix e N, and m e N² Call am = ||m]] = m1 + + m,g We introduce the set functions
[x()
fa(z)
Fa.m FF: Rd Ram
F(x)
fi E (RR. RTM), i == 1, I....kk. k.
(5)
(x(x)
It is immediate to see that Fa.m Ci (Rd RT) if m E N. i.c., k = 1. Furthermore, for any given E N*, one has Ci (Rd Ram) Fd.a.. C Fa showing that Fa,m provides generalisation of the set of 1-Lipschitz functions from d to 8m0m, For the results below, we fix & e N and m e N
22

---

Definition B.1 (Projection on the i-th component). The projection map on the i-th component T. mm R is defined
F1
D2
H ::=mm()) 24 ERT
Lemma B.I. Let F E Fa.m and E L.n Then, = A F:; Rdd + Ram belongs to Fa,m-
Proof.
Let y E 1d be two arbitrary vectors, and fix i {I,..., kJ. By direct calculation, see
that
(a(C(y)-G()lll =
Σ Au (F(() F(z))
Σ A1)(()())
=
|| 11211l - 2112 $ 1V x112
j=1
as desired.
Lemma B.2. Let F Fa and mm be vector with ||l|| 1. Then f(x) v F(x) is scalar -iisschiz,functionn
Proof. Let E Rd be two arbitrary vectors. By direct calculation, see that
1f(y) - [()) Σ ( (F(v)) - F(x)) < (FG F()))ll
[m)())]a - æ|12 |el|llly æ112 11 2//2
as desired.
C Proof of Theorem 4.1
We now provide proof for Lemma 4.1
Lemma C.1. Let h E N and a ReLU, The set En,o is a subset of E143,0-
Proof. Let x E hh+ and consider the map
maxxf2,, x22 min 11 x22
(o(x)= =
Tx(:)))
with (x4.) T4: - -W oWWx:: x4: + b), where + E [0,2]. W x/ gg R and || ||2 S
Call / E [0, 1]. Define
1/V2
1/v2
0
W
E TR (((+3))(6+3))
0
R
0
0
0
0
O
O
On
WW
23

---

We now show that Φx(x)) = x
2W
o(W> b):
x
2W
T ( x + b)
12
0
4
1/v2
1/v2
0
0
22
1/v2
0
0
0
0
0
0
23
0
0
0
0
x +
0
.4:
ON
Oh
Oh
Ol
Og
Og
L6b
2 (22 - x1)
"max 22
32
2 (22 - 11
min min Ø2)
22(2).
23
0
F4:
W a (W T4: +b)
(x41))
We now prove Lemma 4.2
Lemma C.2. Let ReLU, d.h E N. with h 2 3. All the functions in Go (R. R) are 1-Lipschitz.
Proof. Fix m 11,1,1,h 3) and E Rdd We consider the network
x + TT to A A po o (z) E Gd,o, (TR., IR.).
For any map Q E R. there exist four vectors a1, 02 a3 ② E IRd, three scalars b, by by E R. and matrix Q Rh-3xd such that
Q x b1
ag b2
Q(x)
ERA
0g by
Qu +
and ||a [l2, ||22 la, ||as IQll2 < 1. Because the composition of 1-Lipschitz maps is I-Lipschitz, and the maximum and minimum 1-Lipschitz functions is still 1-Lipschitz, follows that the map
max x + b,, a x b2)
min a x + b, 0g x b2}
x + t0 o Q(x)=
ag x + by
Qo nI Wi o ( Qx + T.)
belongs to Fa,m defined as in (5). Since A E Lm. Lemma B. implies that
[I,)
f1,((z)
A1 Po, Q(x)
fi,, fLs Rdd R. f1,4 TR. + R-
fI,((T)
f(,(()]
belongs to Fa.m as well. We leave the components unspecified so that the argument generalises.
Doing one further step, so that the argument generalises to generic number of compositions L, one gets
m1.(ff.1 f12(x)}
min (f11 f(2(2))
Do Ai D9. Q(x) =
f1. (x)
[1,(()) W2 (W2h1, + bz).
which again belongs to Famm Extending the argument, we see that
max maxxfJi-1x 1,1 (x)) Sr. /1.-1,((x))
min (Lr, - 11-122
pa o 1 o Q(x) =
11-13 (x)
(T.)
(W br.)
which belongs to Fa,m Lemma B.2 allows to conclude that the output scalar function is 1-Lipschitz since h satisfies ||e|| < I.

---

We conclude with the statement and proof of Theorem 4.2
Theorem C.1. Any piecewise affine 1-Lipschitz function f Rd + R can be represented by network in ad (TR", IR) with o = ReLU and h = d d 3.
Proof. Fix (1, 1, 1,).. Let us consider generic 1-Lipschitz piecewise affine function, which, thanks to Lemma 3.4 can be written as
f(z) mfx(ff( fu(z)),,, fa(x) min(ar, bi,1. ..., 0,,,, b... i 1, L.... k,
for a suitable choice of parameters. We also recall that ||,,ill2 1 for every 1, ... k and j = 1, 1,....4 4, Thanks to Proposition 4.1 there exists a suitable choice of weights giving
91 = P Ponn-1 A1, o A1,1 a Po,, R - R
with 28 11.1-11m Pa Edoo and - A1,1 E Cm. so that
f1(())
(1)2(x))
91 (Q()))) =
E Rd++
(1))
where we leave the 1-Lipschitz functions k 11,3 3 Rd + unspecified since they do play role our construction. We now introduce map A E f. that is characterised by
T + 2,,1 22 I + 2
A o 9i o Q(x)= =
f1(
x
that is A Q(x) = A1z)(((z))
+ āi with
0
0
0221
b2.1
A
0
0
022
b2.2
0
0
0
āl
0
0a
04
0a
0g
We then define
92 = D82.12-1
A2,12-2 2 o. ... o A2,1 o 282.1
RR" + R²
so that
[2(x1
22)
92 0 A1 0000100100 Q(()==
f1(2)
x
Let S C. be such that
fe(x) fi(æ) (2)(())
Sog2 o A Q(z)
We then introduce the residual map V e Ed.a having zero weight matrix, i.e., acting over an input M E dR4+3 as
max U1 U2 min u2) Wg
V (u)
u4:
Similarly to A₁ defined above, we introduce Ag E C. so that given a vector Rd+3
a u4: + 63.1
Az(u)= = a3,2 uy + 63.2
u4:
25

---

and hence
-31 1,,1
03 2 1s,2
A2 o (v (g2 Ai og Q(()) =
(1)),
Iterating this reasoning, one get
Av (V e S) gl o ... Ag (V S) о 9s A2 (V o 92 Al og Q(x) f(x),
where Eg E R is the third vector of the canonical basis.
D Extension of the set En_o
We now fix ReLU, The set of networks Gd.o. (NV, that we considered, is subset of
( = v Po AL-1 .... P0, o Do, Q X R m (1,.... 1. -)),
||m]],, Q Rd v E Re, ||0||1 S A,, ... Ar. E fm, Pne E En-oR Le N, (1, li...
where we define
[GroupSor((zunss))
En (0 Rhth
Rh+ Do(x) =
)o((((+1)))
To E Enoor I (1, k}}
The GroupSort(:: g) activation function, introduced in M1. splits the input into groups of a specific size 9 and sorts each in descending order. The particular case of group size coincides with the MaxMin function we used to define Gs,o, R), i.e.
mmx (11, x2) (ninf21.1
GroupSort(z1s:2))
23
We thus say that En,o C Eh,33,,, and hence (X,, RR C Cd,,,,
The GroupSort(:; g) activation function might not have symmetric Jacobian, and hence might not be directly expressible with single negative gradient step. Still, it can be written as composition of these residual maps in E This is an immediate consequence list of numbers by iteratively ordering subgroups of size two. For example, assume there is positive-ment mertsre subregion R of where 22 GroupSort(-.33 would act
the fact that one can sort
I1 < Iy for every x E R. There, the function
T3 x1
0
0
1
GroupSort(F1a)
F1. =: P
The permutation matrix not symmetric, and hence the target map can not expressed with single negative gradient Euler step. Still, we can write it as the following composition
[r1
T2
x3
T3
T3
T22
which are two maps that belong E3.0. More generally, we can represent the map GroupSort(:33) as follows
max x2
maxf#1, Ø2, 22,
T2
min
main(11,200 [2)
minfx1, x2]
T3
min(r3, max((1j1
max X2, (2,,
max/min ). min(2s, max 22)
min(min [21 x2) min (Ts, max (1, D2
max( 23)
max 22), min(x3, max 12,
GroupSort(21.:::))
26

---

which are all maps that belong to E3,0-
GroupSort(-- g) provides output with the scalar components the input, just reordered. Thus, applied to a function having all the components which are 1-L.iscchitz the same property is preserved after its application. Combining these results, together with the derivations done for Id (X, R), it easy to derive the following results.
Lemma D.1. Let d E N. & C R and o = ReLU. All the functions I are 1-Lipschitz. Lemma D.2. Lei E N, X' C R2 compact sel, and a = ReLU. The set ( IR) satisfies the universal approximation property for R)) if +
E
Extension to multivalued functions
We now state and prove Lemma 5.1 Lemma E.1. Let c,
C Rd be compact. and ReLU. Define the set
= P Do, bo, o oQ X + RR Q(x) = Qx + Q Rlxd
E P E Roxh || 1, Po. E Enh,, LNNEN]
Then, for any f E C((,R and any > 0, there exists E (e, RR) such that max 11[(z) g<x)]l2 S
Proof. Let f E C1 (X' R²) and & > 0. Call fi X + +R 1,.... e, the i-th component of f.
which belongs Ci (X, R). Since (X, IR) G1,d,r (X,, satisfies the universal approximation property for (X,, RR, for every = ..., there exist 91. ....
.... 9r E I1,d (X,R), RR) such that
8 i c..... max (fx()) gx(x) S =EX
The residual maps represent the identity, and we can thus assume that the number of layers of I1..... 9e coincide and are equal to L. Call hú E N. Q Rd + R" Le., E En,,o with é 1, L..,, L, and U; E Rh,, the widths, affine lifting layers, residual layers, and linear projection layers of the c scalar-valued networks, respectively. Following similar arguments for the proof of Theorem 3.1 is easy to see that
(x)
+ g(x) =
gc(xt)
belongs (X', Call h +... has and Q IRd TR' be characterised
[2)())
Q(x)
e ERA
Qc(x))
Denote with Po, E En,o, l 1.... the maps
D (u
+ Φ (1/1 1:h1+
L (u)
Φn... (un 11b)
where Uny E Ri-i+1 denotes the entries from position i to position j of R². Finally, denote with P E Rexh the projection matrix defined as
0 Rg
U2
P
0 ha
27

---

Since 112112 = 1 for every i 10: =ax,
1,...c C, we have || =
|le Pll
1. Therefore, since
g(x) P 28 o... Poz Q(x),
conclude that y E Ge,d, (X, IR() desired. Furthermore, that for any given E X one has
(1f()) 9
Σ ( -0)))(()5 ceE2/c=
desired. Thus, for any f C,(X,, R9 and any 0, there exists g E Ie,d, ( such that
max lIf(x) g(x)]l2 S
=EX
Additional comments
F.1 Further motivation for I-Lipschitz ResNets
We provide further motivation for studying 1-Lipschitz ResNets.
F111 Why study I-Lipschitz networks?
Regarding the importance of 1-L.isschitz networks, we have already cited some works relying on them in the related work section. We expand on how essential the 1-Lipschitz constraint is in those contexts. To do so, we also more explicitly describe the following two problems where 1-Lipschitz constraints are desirable:
1. Improving the network robustness to adversarial attacks, see for example 12
29
33
2. Deploying network trained as image denoiser in Plug-and-Play algorithm for image reconstruction inverse problems, for example, for deblurring problems, see 6
33
In general, those situations where one is interested learning maps that are then iteratively applied, aiming to converge to a fixed point, it is possible to guarantee the convergence of the iterative scheme only under some Lipschitz constraints. Similarly, in those problems where one needs to parametrise the lattice of 1-Lipschitz functions, such to compute the Wasserstein 1-distance, is also convenient to rely on these constrained architectures.
Improving the robustness to adversarial attacks Training neural networks solve classification problems is very standard methodology. Still, is often the case that networks trained to be accurate classifiers, very sensitive to perturbations in the inputs. Some of these perturbations, called adversarial, can be constructed with the sole purpose of fooling the network into misclassifying them, despite being quantifiably close to data points drawn from the same probability distribution as the training and test sets. A way to improve the network's 's robustness to these kinds of perturbations is by controlling its Lipschitz constant. This approach was considered in several papers before ours. theoretical justification for this methodology can be found by relating the notion of margin to that of Lipschitz regularity. Consider a network Ng Rdd R returning probability vectors in R where is the number of classes in which we want to partition our dataset. The classification margin at point æ defined as
Mx,(x) = No(x)) Ee(a) - max
(z
jaf(()) JE(L....e)
where ((x) represents the index of the class which x belongs. the margin is positive, then the network correctly classifies z. Furthermore, the higher the margin, the more certain the network is of this prediction. One can also prove, see [36), that
(z) v2Lip(No)=
Mx O, Vn Rd |nlle S
28

---

This condition means that if we have a good orfde-off between classification margin and Lipschitz constant of the network, we can guarantee the correct classification of perturbed inputs. Such an analysis implies that if we force the network to have small Lipschitz constant, such as Lip(No) S as in our paper, and train the network with loss function aiming to maximise the margin such as the multi-class classification hinge loss, we can get improved robustness.
Plug-and-Play algorithm with guaranteed convergence properties The Banach fxed-poim
Theorem guarantees that for a map T" R + R' which is strictly 1-Lipschitz, i..., [)) < lly - xll2 for every I, y E IRd, there exists a unique fixed point and the iteration Jk+1 = (m)) will converge to it whatever zo E Id is. is thus intuitive that once we are interested (partially) rely architectures
modelling iterative schemes through neural networks, it is fundamental
constrained as in our paper to get reliable method. This is the idea behind the Plug-an auu--and-Paay
algorithm [16 R2 33 used in inverse problems. This method inspired by the forward-backwards splitting proximal gradient descent approach used to solve
min f(x) + g(x), f R² IR,, g R + (+00). SERd
It is common to have f representing the data-fidelity term in the inverse problem, such as f(z)
KK //l//2 whereas represents a regularisation term, such as g(x) ||ا|||| Typically, one can not ask for to be continuously differentiable, and hence methodology to efficiently solve this minimisation problem is the proximal algorithm
1 27
Ily x1 olw))
1 prox g.r (IR T 7V f(x))) prox (2) arg min yERd
(6)
There are two main limitations with this procedure for general inverse problem:
1. It is challenging to design a good regulariser g:
2. The proximal operator prox of generic regulariser g does not admit closed form.
The Bou--and-Play algorithm addresses both limitations above by replacing prox,,- with a neural network No Rd - IRd trained to denoise inputs. In order to guarantee the convergence of this hybrid scheme
FK++ No [V](x)))
we need to properly constrain Ng. If f is strongly convex, L-smooth, and continuously differentiable, fixed point whenever No is 1 I-Lipschitz.
then, taken (0, 2/ L). the method in 7 converges This is another reason why investigating the architecture studied in this paper fundamental. Weaker convergence guarantees can also be obtained when f is only convex, but more needs to be asked from No. see, e.g., 33
Why study ResNets? There are three main reasons why we focus ResNets:
1. 1-Lipschitz constrained ResNets have been used extensively several applications;
2. A theory similar to ours for feedforward networks has already been developed;
3. GNNs, Transformers, and other architectures also rely residual connections which are hence an essential piece to understand.
More explicitly, the gradient steps studied in this paper have already been considered to design GNNs (see, for example, [5] TT (2].. To the best of our knowledge. these gradient steps have not been used in Transformers. Still, there has already been interest in studying Lipschitz-continuouu transformers (see
3 18 R. and our theoretical analysis could least partially be applied to these more complex
architectures.
Theoretical motivation. While unconstrained ResNets can approximate an arbitrary continuous function, it is not necessarily the case that the same holds for constrained one. For example, in [25] Proposition 3.3], the authors prove that feedforward networks with unit-norm weights, which are 1-Lipschitz, are not dense in the set of 1-Lipschitz functions. This holds despite the unconstrained models being universal approximators of continuous functions. This highlights the necessity of developing an approximation theory which is specific to 1-Lipschitz architectures such as ResNets.
29

---

F.2 Dependence of the network size on the input dimension
We now comment on how the network width and depth grow with the input dimension based on our theoretical analysis.
Depth. In Appendix A.2 we derive that to represent the max and min functions affine pieces, we need network whose depth grows linearly with the number of pieces. This is the primary operation required to understand how the network depth evolves based on our theory. Still, there are two essential comments complement this discussion:
1. First, proof designed to be easy to follow and does aim to present the most efficient network solving the task. It is in fact evident that tighter bound for the networks with unbounded width could be have L belonging (logg(( (d)). since m .... z2) can be written by computing in parallel d/2 pairwise maxima and iterating the process, leading to steps where k E N satisfies (d/2*) = i.e. A zv log, (d). This does not immediately translate the finite width case, but could increase the fixed width and improve the efficiency terms of network depth.
2. Second, our proof constructive and provides an upper bound on the size of the network one needs. When training these models, more efficient weight choices could be made, and more effective growth factor may emerge.
Width. For the networks in Theorem 3.1 the network width grows with the number of affine pieces needed assemble the function. This is function- -depedend,, and it can not be bounded a priori solely based on the input dimension. Still, we also provide an approximation theorem with fixed width, which does not suffer from this unbounded growth of the width.
Approximation rates. One of our proof strategies involves the representation of an arbitrary I-Lipschitz piecewise affine function with the considered networks. We thus inherit the same approximation rates as this class of functions.
F3
Further discussion of other activation functions
Our theoretical analysis focuses on the ReLU activation function and the techniques we work with heavily rely on the properties of such function. The focus specific activation, and in particular on ReLU, is quite common in the mathematics of deep learning, as can be seen, for example, in
15
26 41
For any other continuous activation - which is not a polynomial, is relatively immediate to recover the density of the set of networks
(XY, = (No (X, f:R- f(s) = u, (u2s + uz), u1, U2 Ug Rd, h E N)
(xY, R). prove this, one can approximate the elements in Gu,ReLU (X, R) to an arbitrary accuracy with elements in G (X, R). Such an approximation can be done because the considered residual layers gradient steps for potential energies of the form ge(x)) = 1,, ReL.U2(Wez bx)/2 and, on compact sets, we can approximate ReLU²/ /2 and ReLU with a single hidden layer network and its derivative, see (28] Theorem 4.1J. Such an analysis would allow recover approximation theory for networks whose residual layers are of the form
I サ x - W f(Wez + bt).
In this case, though, the imposition of the 1-Lipschitz constraints in practice becomes more challenging, given the lack of knowledge of the properties of f. e.g., if it is non-decreasing. A particularly simple example is (x) Leaky (x) max(ax, 2), (0, where do not need approximations since
ReLU(x) 1 1-aa a² (L)))yReLU,,()) + aLeakyReLU,
30

---

G Numerical experiments and implementability details
This paper focuses on the theoretical analysis of 1-Lipschitz ResNets. We have commented in Section 5 on the inplementability of the considered models, and we now demonstrate that they do not have any intrinsic issues with trainability.
To do so, we consider two classification problems. First, we train models to classify the two-moon dataset with additive Gaussian noise of standard deviation = 0.1. Then, we train networks to classify the MNIST dataset. We inspect how the performance varies as we consider models coming from the two families of architectures presented in this paper, and as we vary the network depth and width.
For the two-moon dataset, we generate 4,000 points. 20% of which are set as training points. For MNIST, we adopt the standard training/test split and preprocess the inputs by normalising them. The batch size we consider for both tasks is 256. We optimise the weights for both tasks using Adam and a cosine annealing learning rate scheduler. The experiments are run on a Quadro RTX 6000 GPU.
The network weights can be initialised to satisfy the dynamical isometry property 22 39], to avoid possible trainability problems when considering deep networks. More explicitly, one can set the intermediate affine layers A₂ so they realise an isometry, the time steps We in the residual layers to random orthogonal matrices. Such an initialisation strategy allows us to have layers which, at initialisation, are maps with a Jacobian matrix which is orthogonal almost everywhere. The dynamical isometry theory suggests that initialising the network weights so the input-to-output Jacobian is orthogonal almost everywhere is sufficient to train deep neural networks. The reason why the setup written above allows to get the Jacobian orthogonality of the residual layers is that
2, and the weights
(x,' = Ln- - We D(x) dieg(ReLU + wx)) (db, (x)) 8b, (x) = In + +4W, (x) w, D()) In,
and the same holds for (%6, (x)²) (200%%,667 (x) In. since D(x)² = D(x) because of the zero and one slopes of ReLU.
All the layers are constrained as discussed in the main body of the paper, but the first one is left unconstrained have fair comparisons between the two types of models, i.e., those stemming from Theorem 3.1 and Theorem 4.1 We consider models with a varying number of layers and present the test accuracy this number changes, along with the time required to enforce the constraints on the network weights during training, computed as an average over the number of epochs using the time library in Python. The weight constraints are enforced in a projected gradient descent fashion, suitably normalising the weights after a gradient step. The code is written in PyTorch and it is available at the repository https: //tgt//bbbt..... atw.://ar....mmrrrripaccccccccaa tressetts
To compute the spectral norms of the weights and enforce the necessary constraints, we use the power method described in 24 [3 To ensure efficient implementation, perform several power iterations at initialisation to obtain an accurate approximation of the leading singular vector. We then perform only one iteration per gradient step, the weights tend to change very mildly during training, and these pre-computed singular vectors provide accurate initial guesses. The cost of this normalisation step is negligible compared with the overall cost of the forward and backwards passes.
The models deriving from Theorem 3.J and Theorem 4.1 consisteeyy train regardless of the network width and depth. The cost of constraining them is larger for those with affine layers, and it grows faster as the depth increases than when the width does. Still, the implementation could be optimised, and this step could be made faster. In Tables and we denote with Theorem 3.1 the architecture without affine layers, and with Theorem with affine layers and further constraints on the gradient steps.
The experiments for MNIST in Table B are performed only for the network newly proposed in Theorem 4.1 This is because for the one in Theorem [3. there have already been more extensive experimental studies in the past, e.g., 23 29 33 We remark that this task does not entirely represent our theoretical results, since we focus on approximating scalar-valued valued functions. In contrast, in this case, we have outputs in R210 given that 10 the number of classes in the MNIST dataset. For this reason, we do not constrain the last affine layer cither. The value of these experiments lies in
31

---

Theorem 3.1
Theorem 4.1
Number layers
Normalisation (scconds)
Accuracy
(seconds)
Accuracy
L 2
99.75%
0.0079
88.25%
0.053
L 4
99.88%
0.0130
99.88%
0.097
L
100.00%
0.0286
99.88%
0.185
L 16
100.00%
0.0585
100.00%
0.273
L 32
99.88%
0.1091
100.00%
0.326
L 64
100.00%
0.1628
100.00%
0.685
Table I: Networks with varying depth and fixed width. Numerical experiments for the two-moon dataset with additive Gaussian noise of standard deviation 0.1. The hidden dimension set to d + 3 = 5, where d = 2 is the input dimension of the data points.
Network width
Theorem 3.1
Theorem 4.1
Normalisation Time (scconds)
Test Accuracy
Normalisation Time (scconds)
Accuracy
h 10
99.88%
0.0372
100.00%
0.1628
h 20
99.88%
0.0379
99.88%
0.1744
h 30
99.88%
0.0381
99.88%
0.1829
h 40
100.00%
0.0378
99.63%
0.2993
Table 2: Networks with fixed depth and varying width. Numerical experiments for the two-moon dataset with additive Gaussian noise of standard deviation o 0.1. The number of layers is fixed to = 10 while the hidden dimension /e varies.
strengthening the claims about the trainability of these newly proposed models, which, despite the addition of interleaved affine layers, do not suffer from practical problems.
= 5
L 10
L 20
h 50
97.85%
97.67%
97.82%
h 100
97.94%
97.70%
97.58%
h 200
97.68%
97.77%
97.89%
Table Results on MNIST with the network Theorem 4.1 and depths L.
test accuracy for different widths
32


Reviews:
[{"review_id": "gsEDOyhaG8", "reviewer": "Reviewer_2dAP", "summary": "This paper studies the approximation capabilities of 1-Lipschitz ResNets, with ReLU activation function. It proves that 1-Lipschitz ResNets with unbounded width and length can approximate any 1-Lipschitz scalar function. The key to prove the results is to construct a 1-Lipschitz ResNets layer, which the paper leverages the existing results (called the explicit Euler step for the negative gradient flow differential equation; see Proposition 2.1 in line 125 and the remarks right after). The paper further proves that the same approximation capability holds when the width is fixed (specifically, width length can be fixed to be no less than d+3 where d is the input dimension) and only the depth is unbounded. The proof builds upon an understanding that any piecewise affine 1-Lipschitz scalar function can be presented by a fixed width 1-Lipschitz ResNets; the result is interesting. As a theory paper, there is no numerical experiments to validate or show the usefulness of the results under practical settings.", "questions": "1. Perhaps the authors could give more concrete motivation of why focusing on 1-Lipschitz NN and why addressing the research gap, i.e., proving the 1-Lipschitz ResNets can approximate any 1-Lipschitz function is important. For example, why just ResNets but not other NN architectures like GNN, Transformers, etc? Can the techniques for ResNets be applicable to GNN /Transformers?\n2. Perhaps the authors could highlight the novelty of the techniques used in the proof and the significance of the results (by for example putting them with respect to the existing universal approximation results for ResNets).\n\nI am ready to increase my score if the above issues are well addressed.", "limitations": "The paper presents discussions on some proof techniques, extension of the results, and implementation of the proposed ResNets architecture in Sec. 5.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper appears to address a (less-motivated) research gap that 1-Lipschitz ResNets can approximate any 1-Lipschitz scalar function arbitrarily well. \n- The authors are knowledgeable about the relevant techniques and leverage them towards proving the results in this paper.  \n- The paper is relatively easy to follow. \n\nWeaknesses:\n\n- The motivation can be more concrete and stronger. The paper only briefly states the importance 1-Lipschitz NN without giving concrete evidence. Same for the claim in the introduction that “The commonly adopted strategies to constrain a network’s Lipschitz constant tend to reduce its expressiveness …”. Concrete evidence would strengthen the motivation, especially for laymen.\n- The challenges in proving the main results and their significance, that 1-Lipschitz ResNets with unbounded width and depth (or bounded width and unbounded depth) can approximate any 1-Lipschitz scalar function, should be discussed. It will be great if the authors can highlight the significance of such results in a broader context (beyond that it addresses a weekly-motivated research gap). \n\nMinor comments: \n\n- Why presenting Theorem 3.1, if the results in Theorem 4.1 already covers those in Theorem 3.1?  (Thus, one can present Theorem 4.1 directly, which seems to involve more new developments in this paper anyway.)", "was_revised": true, "final_justification": "The response has addressed my concerns on the motiviation of the study, the challenges, and the novelty. I think this is a good theory paper with notable contributions and should be accepted.", "rebuttal": "Thank you for carefully reading our paper and explicitly stating your interest in raising the score in case we address your questions. We report below our responses. We collect all the mentioned references at the end of the response.\n\n## Weaknesses\n\n### Motivation\nThank you for this suggestion on strengthening the motivation behind the paper and the necessity to study how to design expressive $1$-Lipschitz neural networks. In the response to the next question, we provide a reference on the impossibility of approximating $1$-Lipschitz functions with a commonly used type of $1$-Lipschitz neural networks. This motivates the need to study and design less conventional architectures. Another important reason to study these models stems from experimental results in Figure 1 of [8] and similar findings in other related papers, where the authors train Lipschitz-continuous gradient-based ResNets and observe improved robustness to adversarial attacks, accompanied by a drop in performance on clean images. We believe that understanding the theoretical expressive power of these models is crucial for determining whether the experimental results arise from intrinsic architectural limitations or the training methods, as our theory suggests. When revising the manuscript, we will expand on these two aspects and also provide a longer description of the other references that we have already included.\n\nRegarding the importance of $1$-Lipschitz neural networks, we have already cited some works relying on them in the related work section. We will expand on how essential the $1$-Lipschitz constraint is in those contexts. To do so, we will also more explicitly describe two problems where $1$-Lipschitz constraints are desirable in an appendix. These two problems are:\n1. Improving the network robustness to adversarial attacks, see for example [4], [8], and [11],\n2. Deploying a network trained as an image denoiser in a Plug-and-Play algorithm for image reconstruction in inverse problems, for example, for deblurring problems, see [8], [9], and [10].\n\nIn general, also in all those situations where one is interested in learning maps that are then iteratively applied, aiming to converge to a fixed point, it is possible to guarantee the convergence of the iterative scheme only under some Lipschitz constraints.\n\n### Significance of the results\nWe tend to disagree in saying that the results are hardly surprising, in the sense that, even though unconstrained ResNets can approximate an arbitrary continuous function, it is not necessarily the case that the same holds for a constrained one. For example, in Proposition 3.3 of reference [1] below, the authors prove that $\\mathrm{ReLU}$-feedforward networks with unit-norm weights, which are $1$-Lipschitz, are not dense in the set of $1$-Lipschitz functions. This holds despite the unconstrained models being universal approximators of continuous functions. Given your comments, we agree that it is very important to remark the relevance of our contribution and of the study of the approximation properties of $1$-Lipschitz ResNets. We will do so in the revised manuscript. Thank you.\n\n## Minor comments\n### Theorem 4.1 provides a generalisation of Theorem 3.1.\nTheorem 4.1 is not a generalisation of Theorem 3.1, strictly speaking, since for Theorem 4.1 to hold we need to introduce the affine layers, whereas Theorem 3.1 only relies on networks with residual layers. We comment on this aspect in the paragraph starting on line 281.\n\n## Questions\n### Motivation behind our work and why did we study ResNets\nThere are three main reasons why we focus on ResNets: \n1. $1$-Lipschitz constrained ResNets have been used extensively in several applications;\n2. A theory similar to ours for feedforward networks has already been developed;\n3. GNNs, Transformers, and other architectures also rely on residual connections which are hence an essential piece to understand. \n\nWe agree that providing additional context and defining the research gap we are addressing would strengthen the paper. We have now expanded on this aspect in the introduction, also stressing the original theoretical ideas we introduced and their transferability. We mention in particular GNNs that have already been considered in the same gradient form before (see, for example, references [2], [3] and [4] below). While we are not aware of the use of these gradient layers in Transformers, there has already been interest in studying Lipschitz-continuous transformers, see [5], [6], and [7] below, and we believe that our theoretical analysis could at least partially translate to these more complex architectures.\n\n### Novelty of the techniques used in the proof and the significance of the results\nRegarding the novelty of our theoretical derivations, we would like to clarify that our main contribution lies in proving the approximation theorem without relying on the Restricted Stone-Weierstrass theorem (see Sections 3.2 and 4), and in providing two alternative viewpoints to our analysis, thereby gaining a deeper understanding of $1$-Lipschitz ResNets. Not directly relying on the Restricted Stone-Weierstrass theorem forced us to understand that the set of considered networks contains a very well-studied set of functions: 1-Lipschitz piecewise affine functions. This derivation has significant consequences, since it allows us to transfer the approximation properties of this function class to our neural networks. Whereas the Restrictive-Stone Weierstrass theorem provides a very general technique to analyse parametric sets of functions, we also show a constructive strategy to obtain analogous results.\n\nWe also introduce a new neural network architecture in Section 4, which theoretically exhibits desirable expressiveness and has not been explored before. Additionally, while working on this rebuttal, we have noticed another simple yet powerful consequence of our analysis. The set of networks $\\widetilde{\\mathcal{G}}\\_{d,\\mathrm{ReLU},d+3}(\\mathcal{X},\\mathbb{R})$ contains all the piecewise affine $1$-Lipschitz functions, as stated in Theorem 4.2 of our work. On the other hand, it is also true that all the elements of $\\widetilde{\\mathcal{G}}\\_{d,\\mathrm{ReLU},d+3}(\\mathcal{X},\\mathbb{R})$ are piecewise affine $1$-Lipschitz functions. The latter result follows from the fact that $\\mathrm{ReLU}$ is piecewise affine, and we only compose it with affine maps. This reasoning allows us to conclude that the new architecture that we propose and study in Theorem 4.1 coincides with the set of piecewise affine $1$-Lipschitz functions, and provides another representation strategy for this lattice of functions. We believe this is another original theoretical contribution that strengthens our work. We will include it as a remark in Section 4 and make sure that whenever we say that such functions are contained in the parametric set $\\widetilde{\\mathcal{G}}\\_{d,\\mathrm{ReLU},d+3}(\\mathcal{X},\\mathbb{R})$, we replace it with \"coincides with it\".\n\nWe will ensure that the relevance of these contributions is emphasised more in the paper. Given the comments of some other reviewers, we have also performed simple numerical experiments to demonstrate the performance of these models, as seen in the responses to Reviewer 6fHT.\n\n## References\n- [1] Neumayer, S., Goujon, A., Bohra, P., & Unser, M. (2023). Approximation of Lipschitz Functions Using Deep Spline Neural Networks. SIAM Journal on Mathematics of Data Science, 5(2), 306-322. \n- [2] Chen, Q., Wang, Y., Wang, Y., Yang, J., & Lin, Z. (2022, June). Optimization-Induced Graph Implicit Nonlinear Diffusion. In International Conference on Machine Learning (pp. 3648-3661). PMLR.\n- [3] Eliasof, M., Haber, E., & Treister, E. (2021). PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations. Advances in Neural Information Processing Systems, 34, 3836-3849.\n- [4] Eliasof, M., Murari, D., Sherry, F., & Schönlieb, C. B. (2024). Resilient Graph Neural Networks: A Coupled Dynamical Systems Approach. In ECAI 2024 (pp. 1607-1614). IOS Press.\n- [5] Castin, V., Ablin, P., & Peyré, G. (2023). How Smooth Is Attention?. arXiv preprint arXiv:2312.14820.\n- [6] Kim, H., Papamakarios, G., & Mnih, A. (2021, July). The Lipschitz Constant of Self-Attention. In International Conference on Machine Learning (pp. 5562-5571). PMLR.\n- [7] Qi, X., Wang, J., Chen, Y., Shi, Y., & Zhang, L. (2023). LipsFormer: Introducing Lipschitz Continuity to Vision Transformers. arXiv preprint arXiv:2304.09856.\n- [8] Sherry, F., Celledoni, E., Ehrhardt, M. J., Murari, D., Owren, B., & Schönlieb, C. B. (2024). Designing stable neural networks using convex analysis and ODEs. Physica D: Nonlinear Phenomena, 463, 134159.\n- [9] Cheng, Y., Schönlieb, C. B., & Aviles-Rivero, A. I. (2024). You KAN Do It in a Single Shot: Plug-and-Play Methods with Single-Instance Priors. arXiv preprint arXiv:2412.06204.\n- [10] Hertrich, J., Neumayer, S., & Steidl, G. (2021). Convolutional Proximal Neural Networks and Plug-and-Play Algorithms. Linear Algebra and its Applications, 631, 203-234.\n- [11] Prach, B., Brau, F., Buttazzo, G., & Lampert, C. H. (2024). 1-Lipschitz Layers Compared: Memory, Speed, and Certifiable Robustness. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 24574-24583)."}, {"review_id": "QripFWSODa", "reviewer": "Reviewer_6fHT", "summary": "This paper studies the approximation capabilities of 1-Lipschitz Residual Neural Networks (ResNets) based on explicit Euler steps of negative gradient flows. The authors provide two main theoretical contributions: (1) They prove that 1-Lipschitz ResNets with unbounded width and depth are dense in the set of scalar 1-Lipschitz functions on compact domains, and (2) They show that the same density property holds when the hidden width is fixed by introducing constrained linear maps between residual blocks. The proofs rely on the Restricted Stone-Weierstrass Theorem and constructive arguments showing that these networks can represent all piecewise affine 1-Lipschitz functions.", "questions": "This paper makes solid theoretical contributions to understanding 1-Lipschitz ResNets, but falls short of demonstrating practical value. The theoretical results are rigorous and novel, but the complete absence of experimental validation raises serious questions about the practical relevance of these findings.", "limitations": "see above", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. Strong theoretical results: The paper provides an universal approximation theory for 1-Lipschitz ResNets.\n\n2. Rigorous mathematical analysis: The dual proof strategies (Restricted Stone-Weierstrass and piecewise affine construction) provide comprehensive theoretical coverage and different perspectives on the problem.\n\n\n## Weaknesses\n\n1. Lack of experimental validation\nThe most significant weakness is the **complete absence of any experimental results**. For a neural network paper, this is a critical omission. The authors provide no evidence that:\n- Their theoretical constructions are computationally feasible\n- The proposed architectures perform competitively with existing methods\n- The universal approximation property translates to practical benefits\n\n2. Questionable practical implementability\nWhile the authors claim implementability, several concerns arise:\n- The regularization approach for unconstrained Q in G_{d,ρ}(X,R) using terms like Σ(ReLU(||∇_x N_θ(x_i)||_2 - 1))^2 is **not friendly for unconstrained optimization of deep neural networks**\n- Spectral norm constraints require expensive power method computations during training\n- Row-wise ℓ_2 norm constraints add significant computational overhead\n- No analysis of computational complexity or training stability\n\nHowever, these operation are not friendly for the optimization of deep neural network \n\n### 3. Limited scope and extensions\n- Results are restricted to scalar functions (c=1 case), with vector-valued extensions only briefly mentioned\n- Heavy reliance on ReLU activation limits generalizability, practically, we use silu, swiglu and etc.\n\n\n\n## Minor Issues\n\nI have one suggestion. Adopt standard mathematical typography conventions:\n- Use **bold** for vectors (e.g., **x**, **v**)\n- Use regular font for scalars (e.g., L, h, d)  \n- Use **uppercase bold** for matrices (e.g., **W**, **Q**, **A**)\nThis would improve readability and help readers quickly distinguish between different mathematical objects.", "was_revised": true, "final_justification": "more experimental results are provided by the authors. I expect to see more convincing results on larger datasets, such as Cifar-10 and Cifar-100.", "rebuttal": "Thank you for judging our theoretical contributions as strong and for carefully going through the manuscript. We include below our responses to your comments, and we hope they will make you consider increasing the score.\n\n## Weaknesses\n### Lack of experimental validation.\nThis submission is a theoretical paper, and our main contribution lies in the development of novel proof techniques and in providing two alternative viewpoints to our analysis, thereby gaining a deeper understanding of $1$-Lipschitz ResNets. Not directly relying on the Restricted Stone-Weierstrass theorem allowed us to understand that the set of considered networks contains the set of 1-Lipschitz piecewise affine functions, hence allowing us to transfer their approximation properties to our networks. This proof is also constructive, unlike those relying on the Restricted Stone-Weierstrass Theorem.\n\nWe also introduce a new neural network architecture, in Section 4, which theoretically displays desirable expressiveness.\n\nWe now support our claims regarding the implementability of these models with some new numerical experiments, as described in the response to the next question, which we will include in an appendix.\n\n### Questionable practical implementability.\nThe regularisation strategy we mention in the paper is one of the most commonly adopted choices for the training of the critic in Wasserstein generative models, hence demonstrating its practical value and implementability. \n\nWe agree that the power method could be costly. Still, what is commonly done and turns it into an efficient solution, is to do several power iterations at the initialisation to have an accurate approximation of the leading singular vector, and then doing only one per gradient step, since the weights tend to change very mildly during training, and those pre-computed singular vectors are very good initial guesses. This is discussed in references [1] and [2] below.  As shown in the experiments below, the cost of this step is negligible compared to the overall cost of the forward and backwards passes. \n\nWe agree that evaluating the row/block constraints could be expensive following the procedure we described. Such a procedure could still be efficiently replaced by a power iteration method. Thank you for pointing out these potential computational limitations. We have prepared an additional appendix that comments on these aspects, thereby justifying the practical implementability of our models.\n\nIn addition, we have conducted numerical tests to demonstrate that there is no inherent problem in training the considered networks, even with increasing network depth. We consider the task of classifying the points of the planar two-moon dataset with additive Gaussian noise (standard deviation=0.1). The network weights are initialised to satisfy the dynamical isometry property, as described in the response to Reviewer cEiW.\n\nAll the layers are constrained as in the paper, but the first one is left unconstrained to have fair comparisons between the two types of models. We also present the average time required to implement the constraints over epochs measured in seconds via Python's *time* library. The code is written in PyTorch and will be made available upon acceptance. \n\nBoth models consistently train regardless of the network width and depth. The cost of constraining them is larger for those with affine layers, and it grows faster as the depth increases than when the width does. Still, we believe the implementation could be optimised, and this step could be made faster. In Tables 1 and 2, we denote with Theorem 3.1 the architecture without affine layers, and with Theorem 4.1, with affine layers and further constraints on the gradient steps.\n\n**Table 1: Networks with varying depth and fixed width.** Numerical experiments for the two-moon dataset with $\\sigma=0.1$ as standard deviation of the additive Gaussian noise. The hidden dimension is set to $d+3=5$, where $d=2$ is the input dimension of the data points.\n\n| **Number layers** | **Theorem 3.1** |  |  **Theorem 4.1** | |\n|:--------------|------------------------:|:-------------------|------------------------:|:-------------------|\n|  | **Test Accuracy** | **Normalisation Time** | **Test Accuracy** | **Normalisation Time** |\n| L = 2  | 99.75 % | 0.0079 | 88.25 % | 0.053 |\n| L = 4  | 99.88 % | 0.0130 | 99.88 % | 0.097 |\n| L = 8  | 100.00 % | 0.0286 | 99.88 % | 0.185 |\n| L = 16 | 100.00 % | 0.0585 | 100.00 % | 0.273 |\n| L = 32 | 99.88 % | 0.1091 | 100.00 % | 0.326 |\n| L = 64 | 100.00 % | 0.1628 | 100.00 % | 0.685 |\n\n\n**Table 2: Networks with fixed depth and varying width.** Numerical experiments for the two-moon dataset with $\\sigma=0.1$ as standard deviation of the additive Gaussian noise. The number of layers is fixed to $L=10$, and the hidden dimension is varied.\n\n| **Network width** | **Theorem 3.1** |  |  **Theorem 4.1** | |\n|:--------------|------------------------:|:-------------------|------------------------:|:-------------------|\n|  | **Test Accuracy** | **Normalisation Time** | **Test Accuracy** | **Normalisation Time** |\n| h = 10 | 99.88 % | 0.0372 | 100.00 % | 0.1628 |\n| h = 20 | 99.88 % | 0.0379 | 99.88 % | 0.1744 |\n| h = 30 | 99.88 % | 0.0381 | 99.88 % | 0.1829 |\n| h = 40 | 100.00 % | 0.0378 | 99.63 % | 0.2993 |\n\n\nWe will include an appendix describing these experiments and the obtained results, which corroborate the theory and support our comments on the practical implementability of the models.\n\n### Limited scope and extensions.\nWe agree that focusing only on the scalar case is a limitation of our contribution. Still, the vector-valued case is much more challenging, and we believe that it cannot be done before the details for the scalar case are fixed, which is the purpose of our manuscript. The focus on scalar functions is common among the papers studying similar networks, see [3] and [4] below. We show the complexities of the extension when stating and commenting Lemma 5.1. \n\nThe focus on a specific activation, and in particular on $\\mathrm{ReLU}$, is quite common in the mathematics of deep learning, as can be seen, for example, in these papers [5], [6], and [7] below. For any other continuous activation $\\sigma:\\mathbb{R}\\to\\mathbb{R}$ which is not a polynomial, it is relatively immediate to recover the density of the set of networks $\\mathcal{G}\\_{d,\\mathcal{N}\\_\\sigma}(\\mathcal{X},\\mathbb{R})$ in $\\mathcal{C}\\_1(\\mathcal{X},\\mathbb{R})$, where $\\mathcal{N}\\_\\sigma:\\mathbb{R}\\to\\mathbb{R}$, $\\mathcal{N}\\_\\sigma(s) = u\\_1^\\top \\sigma(u_2 s + u_3)$ with $u\\_1,u\\_2,u\\_3\\in\\mathbb{R}^h$, is a sufficiently wide single hidden layer network based on $\\sigma$. To prove this, we can approximate the elements in $\\mathcal{G}\\_{d,\\mathrm{ReLU}}(\\mathcal{X},\\mathbb{R})$ to an arbitrary accuracy. This holds because the residual layers in $\\mathcal{G}\\_{d,\\mathrm{ReLU}}(\\mathcal{X},\\mathbb{R})$ are gradient steps for potential energies of the form $g\\_\\ell(x)=1\\_{h\\_{\\ell}}^\\top \\mathrm{ReLU}^2(W\\_\\ell x + b\\_\\ell)/2$ and, on compact sets, we can simultaneously approximate $\\mathrm{ReLU}$ and $\\mathrm{ReLU}^2/2$ to an arbitrary accuracy with a sufficiently wide single hidden layer network based on a continuously differentiable non-polynomial activation function $\\gamma$, see Theorem 4.1 in [8]. We can then call $\\gamma'=\\sigma$. In this case, though, the imposition of the $1$-Lipschitz constraints in practice becomes even more challenging, since we wouldn't be able to implement residual steps which are $1$-Lipschitz directly, given that it is not known if $\\mathcal{N}\\_{\\sigma}$ is $1$-Lipschitz and monotonically increasing. These networks would generally be much more expensive to evaluate than $\\mathrm{ReLU}$ ones. Moreover, the core results are still those for the $\\mathrm{ReLU}$ function in this case. A particularly simple example is $\\sigma(x)=\\mathrm{LeakyReLU}\\_{\\alpha}(x)=\\max\\\\{\\alpha x, x\\\\}$, $\\alpha \\in (0,1)$ where we do not need approximations since\n$$\n\\mathrm{ReLU}(x) = \\frac{1}{1-\\alpha^2}\\left(\\mathrm{LeakyReLU}\\_{\\alpha}(x) + \\alpha \\mathrm{LeakyReLU}\\_{\\alpha}(-x)\\right).\n$$\nWe now expand on these generalisations in a dedicated appendix.\n\n## Minor issues\n### Bold notation for vectors.\nThank you for your suggestion. We prefer sticking to the current notation, as the pages would become too heavy in our opinion.\n\n## Questions\n### Solid theoretical contributions, but falls short of demonstrating practical value. \nWe hope that the numerical experiments we have now conducted can address your concerns, complementing and corroborating our theoretical analysis.\n\n## References\n- [1] Miyato, T., Kataoka, T., Koyama, M., & Yoshida, Y. (2018). Spectral Normalization for Generative Adversarial Networks. International Conference on Learning Representations. \n- [2] Sherry, F., Celledoni, E., Ehrhardt, M. J., Murari, D., Owren, B., & Schönlieb, C. B. (2024). Designing stable neural networks using convex analysis and ODEs. Physica D: Nonlinear Phenomena, 463, 134159.\n- [3] Neumayer, S., Goujon, A., Bohra, P., & Unser, M. (2023). Approximation of Lipschitz Functions Using Deep Spline Neural Networks. SIAM Journal on Mathematics of Data Science, 5(2), 306-322.\n- [4] Cem Anil, James Lucas, and Roger Grosse. Sorting Out Lipschitz Function Approximation. In the International Conference on Machine Learning, pages 291–301. PMLR, 2019.\n- [5] Yarotsky, D. (2018, July). Optimal approximation of continuous functions by very deep ReLU networks. In Conference on learning theory (pp. 639-649). PMLR.\n- [6] Opschoor, J. A., Petersen, P. C., & Schwab, C. (2020). Deep ReLU networks and high-order finite element methods. Analysis and Applications, 18(05), 715-770.\n- [7] Hanin, B., & Sellke, M. (2017). Approximating Continuous Functions by ReLU Nets of Minimal Width. arXiv preprint arXiv:1710.11278.\n- [8] Pinkus, A. (1999). Approximation theory of the MLP model in neural networks. Acta numerica, 8, 143-195."}, {"review_id": "a07uqBui3B", "reviewer": "Reviewer_cEiW", "summary": "The paper studies approximation capabilities of 1-Lipschitz ResNets (residual networks with a Lipschitz constant c < 1), which are commonly used in inverse problems, generative modeling, and adversarial defense. The main contribution of the paper is the first proof that such models can approximate _any_ 1-Lipschitz function, at least when considering negative gradient steps and interleaving residual layers with affine transformations. Authors first show that this holds under infinite width/depth, but proceed to show that this still holds at a fixed, finite layer width.", "questions": "1. On lines 151-152 authors suggest that \"the lack of explicit constraint over $\\hat{Q}$ leads to problems when implementing these networks\". What are these problems? Isn't a lack of constraints easier to implement with gradient-based optimization, i.e. we don't have to resort to projected SGD or other methods?\n2. Have authors studied other common activation functions (sigmoid, tanh, etc.), to understand if they have the properties stated on lines 321-322 that would make the proof applicable?", "limitations": "I suggest authors extend their discussion on the potential practical consequences of adding affine layers to a residual architecture.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ Significant and original theoretical result: the first proof of universality for 1-Lipschitz ResNets, albeit with some deviations from the commonly used architecture (adding affine layers).\n+ The proof and prior work are introduced with great clarity, guiding the reader through all the steps involved, their motivation, and how they relate to literature.\n+ High-quality manuscript: precise and clear writing, good formatting, consistent mathematical notation.\n+ In-depth discussion of the limitations of the proof and their implications.\n\nWeaknesses:\n- Authors have to add affine transformations to the ResNets to show universality. While arguably a minor addition, this might have implications in practice, e.g. for optimization. An important benefit of residual networks is better gradient propagation, which might suffer due to the addition of affine layers, especially for deeper nets. Which leads to the next weakness...\n- No numerical experiments. While the main contribution of the paper are the universality proofs, authors have to make adjustments to standard architectures to complete the proofs. The contribution would be stronger if authors provided some numerical results to confirm these additions are indeed practical, and don't impact the performance of these models on real problems.", "was_revised": true, "final_justification": "I maintain my recommendation to accept the paper as I believe it to be an important theoretical contribution. I would increase my score  if the paper had a stronger experimental component, helping the reader understand how the proposed architectural changes would impact the model on problems where 1-Lipschitz ResNets are typically applied, like inverse problems, generative modeling, or adversarial defense. While authors have provided numerical results in the rebuttal, the experiments use toy problems.", "rebuttal": "Thank you for the thorough analysis of our manuscript, and we are glad for your appreciation of how it is written and the theoretical results we derive. We have prepared an answer for all your comments, and we hope they address your concerns.\n\n## Weaknesses\n### Trainability as the depth increases \nAll the networks we consider are piecewise affine and $1$-Lipschitz and cannot suffer from exploding gradient problems since the network gradient has $\\ell^2$ norm bounded by one. We agree that deep networks could, in principle, suffer from vanishing gradient problems. Still, skip-connections are not the only remedy to vanishing gradient issues, as can be seen from the theoretical studies around the topic of *dynamical isometry*, see references [1] and [2] below. This theory suggests that initialising the network weights so that the input-to-output Jacobian is orthogonal almost everywhere is sufficient to train deep neural networks. This can also be done in our networks, for example, by initialising the intermediate affine maps to the identity, i.e., $A_\\ell(x)=x$. The residual layers can also be initialised to have an orthogonal Jacobian almost everywhere (when well defined), by setting $\\tau=2$ and initialising $W_\\ell$ as an orthogonal matrix. In this way, we get\n\\begin{align*}\n\\phi_{\\theta_\\ell}'(x) &= I_h - 2 W_\\ell^\\top D(x) W_\\ell,\\\\,\\\\,D(x) = \\mathrm{diag}(\\mathrm{ReLU}'(W_\\ell x + w_\\ell)) \\\\\\\\\n(\\phi_{\\theta_\\ell}'(x))^\\top \\phi_{\\theta_\\ell}'(x) &= I_h + 4(W_\\ell^\\top D^2(x)W_\\ell - W_\\ell^\\top D(x) W_\\ell) = I_h,\n\\end{align*}\nand the same holds for $(\\phi_{\\theta_\\ell}'(x)')^\\top\\phi_{\\theta_\\ell}'(x)=I_h$, since $D(x)^2=D(x)$ because of the zero and one slopes of $\\mathrm{ReLU}$. To demonstrate that there is no intrinsic training problem in these networks with affine layers, we have conducted numerical experiments with networks of varying depth and width. The weights are initialised as described here, so to satisfy the dynamical isometry property. You can find them described in the response to Reviewer 6fHT. Thank you for bringing up this problem, which we now discuss in more detail in our paper when commenting on the practical implementation of our models.\n### Lack of numerical experiments\nWe hope that the additional experimental evidence, together with the explanation in the response to Reviewer 6fHT, can address your concerns.\n\n## Questions\n### On lines 151-152\nIt is true that it is easier to implement. The problem we wanted to highlight with this statement is that the lack of explicit constraints does not allow us to directly get a $1$-Lipschitz network without regularisation. If one is willing to relax the $1$-Lipschitz requirement during training, then it would be enough to leave $Q$ unconstrained or, at most, introduce some weight decay to control its norm. We have reworded this statement to ensure there is no ambiguity.\n### Other activation functions\nThank you for this comment, which was a question posed also by the other reviewers. Even though one can not apply the same techniques to other activation functions, the approximation properties extend to similar neural network architectures. We provide more details on this aspect in our response to Reviewer 6fHT, and we have now written a dedicated appendix that expands on this.\n\n## Limitations\n### Practical consequences of using the affine layers\nAs recommended, we will extend the discussion of the impact of the affine layers on the network trainability, and support such claims with the numerical experiments discussed above.\n\n## References used in the response\n- [1] Xiao, L., Bahri, Y., Sohl-Dickstein, J., Schoenholz, S., & Pennington, J. Dynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks. In the International Conference on Machine Learning, 2018. (pp. 5393-5402). PMLR.\n- [2] Saxe, A. M., McClelland, J. L., & Ganguli, S. (2013). Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In the International Conference on Learning Representations, 2014."}, {"review_id": "s28T76LoUQ", "reviewer": "Reviewer_niBw", "summary": "This paper provides an approximation theory for 1-Lipschitz ResNets. The authors prove that 1-Lipschitz ResNets are dense in 1-Lipschitz continuous functions on compact domains, in two settings: 1) unbounded width and depth; 2) fixed width and unbounded depth.", "questions": "No.", "limitations": "Limitations are clearly discussed in Section 5.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths:__\n\n1. This paper is well-written and is easy to follow.\n\n2. This paper provides an approximation theory for 1-Lipschitz ResNets, which is an important theoretical foundation. The authors establish the theory in two settings: 1) unbounded width and depth; 2) fixed width and unbounded depth.\n\n__Weaknesses:__\n\n1. Though the theoretical analysis is very interesting, most techniques (such as the Restricted Stone-Weierstrass) are already known in the literature, which makes me a bit worried about the novelty.\n\n2. The analysis highly depends on ReLU and is not general enough.\n\n3. Though the authors mention the implementability in Section 5, there are no numerical experiments. This might be fine given the theoretical focus of the paper.", "was_revised": true, "final_justification": "The authors' rebuttal addresses most of my concerns. There is theoretical novelty, even if many techniques are from previous works. I would like to recommend \"weak accept\".", "rebuttal": "Thank you for appreciating our theoretical analysis and for your thoughtful comments. We address your comments below, and we hope you will find the answers satisfying.\n\n## Weaknesses\n\n### Novelty of the theoretical derivations\nMost of the techniques we used were indeed developed before our paper. Still, they have never been applied to study the approximation properties of $1$-Lipschitz networks, whose approximation properties were also not understood before our paper. Furthermore, one of the primary novelties in our submission lies in a constructive proof (Sections 3.2 and 4) that does **not rely on the Restricted Stone–Weierstrass theorem**, a central tool in prior works studying this approximation problem. Not directly relying on the Restricted Stone-Weierstrass theorem allowed us to understand that the set of considered networks contains a very well-studied set of functions: 1-Lipschitz piecewise affine functions. This derivation has significant consequences, since it allows us to transfer the approximation properties of this function class to our neural networks. Whereas the Restrictive-Stone Weierstrass theorem provides a very general technique to analyse parametric sets of functions, we also show a constructive strategy to obtain analogous results.\n\nWe also believe that the design strategies used for the network in Section 4 are original, and we are not aware of any paper theoretically studying this kind of interaction before. This derivation also brings attention to the fact that to design a $1$-Lipschitz neural network, it is not necessary to entirely rely on $1$-Lipschitz layers. Additionally, while working on this rebuttal, we have noticed another simple yet powerful consequence of our analysis. The set of networks $\\widetilde{\\mathcal{G}}\\_{d,\\mathrm{ReLU},d+3}(\\mathcal{X},\\mathbb{R})$ contains all the piecewise affine $1$-Lipschitz functions, as stated in Theorem 4.2 of our work. On the other hand, it is also true that all the elements of $\\widetilde{\\mathcal{G}}\\_{d,\\mathrm{ReLU},d+3}(\\mathcal{X},\\mathbb{R})$ are piecewise affine $1$-Lipschitz functions. The latter result follows from the fact that $\\mathrm{ReLU}$ is piecewise affine, and we only compose it with affine maps. This reasoning allows us to conclude that the new architecture that we propose and study in Theorem 4.1 coincides with the set of piecewise affine $1$-Lipschitz functions, and provides yet another representation strategy for this lattice of functions. We believe this is another original theoretical contribution that strengthens our work. We will include it as a remark in Section 4, and we will make sure that when it is stated that the set of piecewise affine $1$-Lipschitz functions is contained in $\\widetilde{\\mathcal{G}}\\_{d,\\mathrm{ReLU},d+3}(\\mathcal{X},\\mathbb{R})$, we replace it with \"it coincides with it\".\n\n### Strong reliance on $\\mathrm{ReLU}$\nThank you for this comment, which was a question posed also by the other reviewers. Even though one can not apply the same techniques to other activation functions, the approximation properties extend to similar neural network architectures. We provide more details on this aspect in our response to Reviewer 6fHT, and we have now written a dedicated appendix that expands on this.\n\n### Numerical experiments\nThank you for acknowledging that, being our paper theoretical, it is fine for it not to have numerical experiments. Given the comments of the other reviewers as well, we have also added an appendix dedicated to commenting even further on the practicalities of the implementation of these networks. We have also conducted numerical experiments on a toy problem to demonstrate that our networks have no intrinsic issues with implementability and trainability. We describe the experiments in response to Reviewer 6fHT, and we will include them in a dedicated appendix."}, {"review_id": "GOMoXM8rLn", "reviewer": "Reviewer_KS54", "summary": "In this paper, the authors study the approximation properties of 1-Lipschitz ResNets. The main results show that the class of 1-Lipschitz ResNests is the universal approximator of the 1-Lipschitz functions.", "questions": "Please see the above comments.", "limitations": "Please see the above comments.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strength\nThe paper is describes the problem clearly and the claims are easy to understand. The results presented in the paper seems to be useful as it theoretically explains the usefulness of ResNets. In my opinion the paper answers an important and interesting open problem in this area.\n\n# Weakness\n\nAlthough the main results are strong, I pose a couple of important questions below:\n\n- Both the main results do not mention the number of Layers $L$ needed to get a desired level of approximations. Typically, in applications, we have a very high data dimension $d$. If $L$ depends linearly on $d$, then it would be very hard to train the model and would seriously hinder the implementability.\n\n- Is it possible to quantify the approximation error in terms of the data dimension $d$? This has a practical importance as good approximation properties will help to implelemnt comparatively less complex models that are easier to train.", "was_revised": true, "final_justification": "After carefully reading the rebuttal again, I think all the concerns have been properly addressed. However, I think it would add value to the paper if the discussion about the dependence of approximation error on dimension is added in the main paper. I have increased my score.", "rebuttal": "Thank you for pointing out these two questions, which we agree are essential aspects to discuss. We expand on them below.\n\n## Weaknesses\n### How does the number of layers grow?\n\nWe already specify an upper bound on the number of layers needed to assemble the $\\max$ and $\\min$ functions of the affine pieces, which grows at most linearly. This can be found, for example, in line 454 of our manuscript. There are two essential aspects to address your concern. \n1. First, our proof is designed to be easy to follow and does not aim to present the most efficient network solving the task. A tighter bound for the networks with unbounded width could be to have $L$ in $\\mathcal{O}(\\log_2(d))$, since we can write $\\max\\\\{x_1,...,x_d\\\\}$ by computing in parallel $d/2$ pairwise maxima and keep iterating the process, leading to $k$ steps where $k\\in\\mathbb{N}$ satisfies $(d/2^k)\\approx 1$, i.e. $k\\approx \\log_2(d)$. This does not immediately translate to the finite width case, but one could increase the fixed width and improve the efficiency in terms of network depth. \n2. Second, our proof is constructive and provides an upper bound on the size of the network one needs. When training these models, more efficient weight choices could be made, and a more effective growth factor may emerge. We now discuss these aspects further in the paper.\n\n### How does the approximation error depend on the input dimension?\n\nBased on our proof strategy involving the representation of an arbitrary $1$-Lipschitz piecewise affine function, we inherit the same approximation rates as this class of functions. To get such a rate, we would need to rely on theoretical results of the following form: Let $\\Omega\\subset\\mathbb{R}^d$ be a compact set. For any $1$-Lipschitz function $f:\\Omega\\to\\mathbb{R}$, and each $\\varepsilon>0$ there is a piecewise-affine $1$-Lipschitz function with $\\mathcal{O}(d^k/\\varepsilon^m)$, $k,m\\in\\mathbb{Q}$, affine pieces approximating $f$ within tolerance $\\varepsilon$. We are currently not aware of results of this kind, but they would be sufficient to explore such rates for the networks we study. Thank you for bringing this interesting theoretical question to our attention, which we will explore further in the future.\n\nThank you for the careful analysis of our manuscript, and we hope that these responses address your questions."}]

Author rebuttal:

Meta-review: The  paper studies the approximation capabilities of 1-Lipschitz ResNets and provides the first universal approximation guarantees for 1-Lipschitz ResNets with ReLU activation, under unbounded width and depth, or fixed width but with a modified architecture. This paper provides strong theoretical results and rigorous mathematical analysis. The choice of 1-Lipschitz ResNets with ReLU is well-motivated, according to the author's responses added during the rebuttal, given the effectiveness of 1-Lipschitz ResNets in improving robustness and the use of residual connections in broader models such as Transformers. Additionally, ReLU is used, which is a more commonly used activation function than other activation functions such as GroupSort that previous works had to use. The paper has some novel contributions on the proof techniques which do not use the Stone-Weierstrass theorem in previous works, but the significance of novelty looks kind of limited, as it sounds like similar results can also be obtained by applying existing techniques with the Stone-Weierstrass theorem. There are common concerns on the practical implementability, and the paper is almost purely theoretical and lacks experiments for actual demonstration; some experiments have been added during the rebuttal but are still kind of toy; though this can be normal considering this paper focuses on the theory. Overall, the theoretical contributions are still strong and all reviewers gave positive ratings.
Decision: Accept (poster)