Pay attention to your loss : understanding misconceptions about Lipschitz neural networks
Authors: Louis Béthune
Thibaut Boissin
Mathieu Serrurier
Franck Mamalet
Corentin Friedrich
Alberto Gonzalez Sanz
Venue: NeurIPS 2022 Accept (2022)
Keywords: robustness
lipschitz
certificate
orthogonal
generalization
loss

Abstract: Lipschitz constrained networks have gathered considerable attention in the deep learning community, with usages ranging from Wasserstein distance estimation to the training of certifiably robust classifiers. However they remain commonly considered as less accurate, and their properties in learning are still not fully understood. In this paper we clarify the matter: when it comes to classification 1-Lipschitz neural networks enjoy several advantages over their unconstrained counterpart. First, we show that these networks are as accurate as classical ones, and can fit arbitrarily difficult boundaries. Then, relying on a robustness metric that reflects operational needs we characterize the most robust classifier: the WGAN discriminator. Next, we show that 1-Lipschitz neural networks generalize well under milder assumptions. Finally, we show that hyper-parameters of the loss are crucial for controlling the accuracy-robustness trade-off. We conclude that they exhibit appealing properties to pave the way toward provably accurate, and provably robust neural networks.    

Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networks
Louis Béthune, IRIT, Université Paul-Sabatier Toulouse, France
Thibaut Boissin, IRT Saint-Exupéry Toulouse, France
Mathieu Serrurier IRIT, Université Paul-Sabatier Toulouse, France
Franck Mamalet IRT Saint-Exupéry
Corentin Friedrich IRT Saint-Exupéry Toulouse, France
Alberto González-Sanz
IMT, Université Paul-Sabatier Toulouse, France
Toulouse, France
Abstract
Lipschitz constrained networks have gathered considerable attention in the deep learning community, with usages ranging from Wasserstein distance estimation the training of certifiably robust classifiers. However they remain commonly considered as less accurate, and their properties in learning are still not fully understood. In this paper we clarify the matter: when it comes classification I-Lipschitz neural networks enjoy several advantages over their unconstrained counterpart. First, we show that these networks are as accurate as classical ones, and can fit arbitrarily difficult boundaries. Then, relying robustness metric that reflects operational needs we characterize the most robust classifier: the WGAN discriminator. Next, we show that I-Lipschitz neural networks generalize well under milder assumptions. Finally, we show that hyper-parameters of the loss are crucial for controlling the accuracy-robustness trade-off. We conclude that they exhibit appealing properties to pave the way toward provably accurate, and provably robust neural networks.
Introduction
I-Lipschitz neural networks have drawn great attention in the last decade, with motivation ranging from adversarial robustness to Wasserstein distance computation. In the following, we denote by LipNet1 the class of I-Lipschitz neural networks, by AllNet the class of neural networks without constraints on their Lipschitz constant, i.e conventional neural networks.
Roughly speaking, the Lipschitz constant of neural networks quantifies how much their outputs can change when inputs are perturbed. When this constant high, as it is often the case for neural networks of AllNet, they become vulnerable to adversarial attacks (see [ and references therein): carefully chosen small noise added the inputs, usually imperceptible, can change the class prediction. One possible defense against adversarial attacks is to constrain the network to be 1-L-ipschitz (in LipNet1 improvement of generalization
3 which provides provable robustness guarantees, together with an 4 and interpretability of the model [5]. LipNet! networks are also duality the seminal work
used estimate Wasserstein distance, thanks to
of WGAN [6].
Despite their competitiveness with networks of AllNet on medium scale problems 7 g they still suffer from misconceptions. A belief commonly invoked against networks of LipNet is that they are less expressive: "Lipschitz-basse approaches suffer from some representational limitations that may
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

prevent them from achieving higher levels of performance and being applicable to more complicated problems"
Although this claim seems rational at first glance, the link between Lipschitz constant and expressive- ness is not trivial. While there is an obvious lack of expressiveness for regression tasks, this intuition fades when it comes to classification. Indeed, every AllNet network g R" + E is L-Lipschitz for some (generally unknown) L > 0. Then f _ is a I-Lipschitz neural network with the same decision boundary, since prediction arg max, is invariant by positive rescaling of the logits. In particular, f has the same aceuracy and also the same robustness to adversarial attacks as g. We illustrate this empirically by training a LipNet1 network until it reaches 99.96% accuracy on CIFAR-100 with random labels (see Appendix
We demonstrate that IipNet networks are theoretically better grounded than AllNet networks when it comes classification, through our threefold contribution on Expressiveness (Section 3), Robustness (Section and Generalization (Section 5
First, in Section 3 we confirm that LipNet are as expressive as AllNet networks for classification, and can learn arbitrary complex decision boundary. We show that hyper-parameteet crucial importance, and control the ability to fit properly the train set.
the loss are of
Then, in Section characterize the robustness of the highest accuracy LipNet1 classifier: it is achieved by the Signed Distance Function (Definition ( in Appendix A). We also characterize the classifier of highest certifiable robustness, and we show it corresponds to the dual potential of Wasserstein-1 distance (i.e the discriminator of WGAN ()).
we show that accuracy and robustness are often antipodal objectives. We
Finally, in Section we show that LipNetl benefit from several generalization guarantees. They are consistent estimators: contrary to AllNet, we prove that their train loss will converge test loss as the size of the train set increases. Moreover, we show that LipNetl classifiers with margin are PAC-leamable [TO] it provides bounds on the number of train examples required to reach a targeted test accuracy. Interestingly, this bound is independent of the architecture size, which allows to train enormous LipNetl networks without risking overfitting.
2 Notations and experimental setting
The core of the paper mainly deal with binary classification over R with label set y f-1,+1, f- Let (X, Y) be a random variable taking values X' x Yr where X' C R" is assumed to be compact set. Such pair follows the joint distribution Fxv, defined on the space of probability measures PP( x })) The marginal distribution of X is denoted by Pxx E P(2') and its support by supp Px- We suppose the observation of a sample (I1,, 5/1 ....,,,.......... (3 Up) i.i.d. with common law Xxx,, and the goal is to learn classifier e X + y modeling the optimal Bayes classifier arg max Py Pyjx (z/z). P (resp. Q) denotes the input distribution of label +1 (resp. -1).
The Lipschitz constant Lip(f) of function f R - IR K is defined as the smallest L, 2 0 such that for all x, 2 E RR" we have f((x))(())] I L||x - 2|l. In the rest of the paper, we focus on euclidean norm || || for vectors and spectral norm || |12 for matrices. The set of L-Lipschitz functions over X C I" with image in K denoted Lip, (XY,
Definition 1 (Class of AllNet networks)
AllNet denotes the set of unconstrained neural networks. It includes any feed-forward network of fixed depth (without recurrent mechanisms) using affine layers (including convolutions and batch normalization) with weight matrices W1, W2...WW and Lipschitz activation function a (such as ReLU, sigmoid, tanh, etc). No constraint is enforced on their Lipschitz constant during training.
Definition 2 (Class of LipNetl networks)
LipNetl denotes the set of foed-foward neural networks f defined as in Theorem of Anil et al. [[]] 12 < 1 (see (U2) for details on the mixed norm || (12) and |i $ for i 2 2, and GroupSor12 activation function. They fulfill Lip(f) < 1.
Remark. AllNet networks benefit from universal approximation theorem in C(X, classical result of literature [[3]. LipNetl networks also benefit from an universal approximation theorem
in Lip, (X. B) with respect to uniform convergence Πll. Note that Lip,, (X, R²) {Lf f
Lip, (X, RK) }} LipNetl can be used to approximate functions in LX,,(X,, (X
2

---

In practice authors of [T] noticed that using orthogonal weight matrices (i.e WTW = I) yielded the best results. All our experiments use the Deel. library 8 following ideas of [T] The networks use 1) orthogonal weight matrices and 2) GroupSort2 activations [T]]. Orthogonalization enforced using Spectral normalization (14) and Björck algorithm [1]. These networks belong to LipNetl by
construction (see Appendix D for our choice of architecture and relevant related work).
LipNetl networks provide robustness radius certificates against adversarial attacks [16]. Comput- ing these certificates is straightforward and does not increase runtime, contrary to methods based on bounding boxes or abstract interpretation [77 19 20). There is no need for adversarial training 21 that fails produce guarantees, for randomized smoothing [2 which is costly.
Confusingly, any network of AlINet has a finite Lipschitz constant, but computing NP-hard 23 Only a loose upper bound can be cheaply estimated: Lip(f" I Lip(ar) Will using the property that Lip(fe fa f .... o fi) < nı Lip(ff)) In practice, this bound is often too high to provide meaningful certificates and besides, AllNet networks have usually very small robustness radius [.
Definition (Adversarial Attack)
For any classifier e: X V. any E IR", consider the following optimizution problem:
min ||0|| such that c(x + 8) c(x). SER"
8 is an adversarial attack, x + is an adversarial example, and e is the robustness radius of z. Property (Local Robustness Certificates [6)). For any f E LipNetl the robustness radius of binary classifter sign o example x verifies 2 [f(x)).
Losses: The Binary Cross-Entropy (BCE) loss (also called logloss) is among the most popular choices of loss within the deep learning community. Let f IR" + IR a neural network. For an example E 1² with label y V, and (x) [-xx the logistic function mapping logits to probabilities, the BCE is written Chre parameter 7 > 0. This Tensorflow Pytorch. Note that (f Lipschitz constant L. We show in Section 5.1 that for LipNet1 the temperature r allow to control the generalization gap. We also consider the Hinge loss L. (f)), y) = max (0, vf())) with margin m > 0, as used in 3 for LipNetl networks training.
[z). (f y) = = (zz)(z)) with temperature scaling of the loss defaults to T 1 in most frameworks such as can equivalently tune the
Cl (ff(xx, y)
We focus on binary classification for readability and clarity purposes; however, we prove in Appen- dices A.2 and D that the following theoretical results generalize to the multi-class case, as done in experiments. The proofs of all propositions can be found in the appendix.
1-Lipschitz classifiers are expressive
In this section, we show that LipNetl are as powerful as any other classifier, like their unconstrained counterpart. In particular, when classes are separable they can achieve 100% accuracy.
3.1 Boundary decision fitting
Proposition 1. Lipschitz Binary classification. For any binary classifier c X' + y with closed closed set) there exists 1-Lipschitz function 12= - E such that sign(f(z)) = c(x) on X and such that [|V,fll = almost everywhere (W.Et Lebesgue measure).
pre-images (c ((v3)
The level-sets of a Lip, (Y, functions (and especially the decision boundary) can be arbitrarily complex: restraining classifiers to Lip, (X,, R) does not affect the classification power.
Definition 4 (c-separated distributions)
Distributions and Q are c-separated if the distance between supp P and supp Q exceeds e > 0.
Corollary 1. Separable classes implies error. P and Q c-separated, then there exists network f E LipNetl such that error Essign o f) = E(z.9)>PPx Px [ssign((()) + +yll =
http::///gthau..cm//ee/aaaaaaa// distributed under MIT License (MIT).
3

---

Denctty Dersiyy
022
Pracasiity ethel
0.75
(b) Importance of in BCE. We train LipNetl network with BCE and different values for т. We chose a toy example where P and Q are Gaus- sian mixtures with two modes weights 0.9 and 0.1. We highlight the different shapes of the minimizer f as function of r. High values of leads to bet- fitting, whereas for lower the small weights Gaussian the mixture are treated as noise and ignored.
(a) Complex Decision Boundary O. We chose 0 the fourth iteration Von Koch Snowflake. We chose P as the interior ring. while the center and the exterior correspond to Q. We train a LipNetl network with MSE to fit the SDF (Definition 6 Appendix) ground truth (160 000 pixels), until MAF is inferior 1. It proves empirically that LipNetl networks can handle very sharp (almost fractal) decision boundary.
Figure
The class of LipNetl networks does not suffer from bias for classification tasks. Some empirical studies show that indeed most datasets classes are separable 24 such as CIFARIO or MNIST. Furthermore, even if the classes not separable, functions of LipNetl can nonetheless approximate the optimal Bayes classifier. Lipschitz constraint is not constraint on the shape of the boundary (Figure la but on the slope of the landscape of f.
3.2 Understanding why LipNet1 are often perceived as not expressive
LipNetl networks cannot reach zero loss with BCE: this may explain why they are perceived as not expressive enough. Yet the minimizer of BCE exists and is well defined.
Proposition 2. BCE minimization for I-Lipschitz functions. Let X C R" be compact and O. Then the infimum in Equation 2 a minimum, denoted fr E (X,
fr arg
inf (x.3)
Be the (f()))
(2)
Moreover, the LipNetl networks will not suffer of vanishing gradient of the loss (see Appendix
Machine learning practitioners are mostly interested in maximizing accuracy.Howevve the minimizer of BCE is not necessarily a minimizer of the error (see Figure lb). Yet, BCE notoriously differentiable proxy of the enror E(sign o ʃ), and 7 - 0o we get asymptotically closer to maximum empirical accuracy. Bigger value for 7 might ultimately lead to overfitting, playing the same role as the Lipschitz constant L (see Figure lbb.
The implicit parameter
of the loss partially responsible of the poor accuracy of LipNet1 networks in literature, and not by any means the hypothesis space LipNet1 itself. This can be observed practice: when temperature (resp. margin m) of cross-entropy (resp. hinge loss) is correctly adjusted a small LipNet1 CNN can reach competitive 88.2% validation accuracy on the CIFAR-10 dataset (results synthetized and discussed Figure 3 without residual connections, batch normalization or dropout. Conversely, AllNet networks are roughly equivalent to learning LipNet1 network with 7 - ao: without regularization data augmentation, such network can always reach 100% train accuracy without generalization guarantees.

---

10
055
0.0
accuracy
0.6
04 0.5
1.5
3.5
2.0
2.5
3.0 0.
0.5
1.0
3.5
2.0 2.5
3.0 0.0
0.5
1.5
3.5
2.0
2.5
3.0
perturbation radius
Figure 2: Accuracy-robustness tradeoff: Each network is optimal with respect to certain criterion. The leftmost network is the most accurate at robustness radius S 0.3, the rightmost maximizes the MCR the cost of low clean accuracy. The center network corresponds compromise.
1-Lipschitz classifiers are certifiably robust
Is there a trade-off between accuracy and robustness? Although the existence of trade-off between accuracy and robustness is commonly admitted, some works argue that "Robustness is not inherently at odds with accuracy" [24]. We propose unified consideration by stating that for a given train accuracy, robustness can be maximized up to certain point, but allowing lower train accuracy helps achieving higher robustness. Finally one must keep mind that this trade-off lives in the shade of generalization (see Section 5
4.1 Improving the robustness of the maximally accurate classifier
The Signed Distance Function 25 (SDF) (see Definition 6 Appendix A associated the frontier of Bayes classifier is the I-Lipschitz function that provides the largest certificates among the classifiers of maximum accuracy. Moreover, those certificates are exactly equal to the distance of adversarial samples. Iterative gradient based attacks (see (26) and references therein) can succeed in one step: far from being a weakness, this may improve the interpretability the model [27 28 29).
Corollary 2. For the SDF(b), the bound of Property 7 is tight:
ff(x)). In particular 5 V is guaranteed to be an adversarial attack. The risk is the smallest possible. There is classifier with the same risk and betler certificates. Said otherwise the SDF(b) is the solution
max SELiD, (RP
min ZE
min dES" (o)(((++))))sse(((ff
||011.
(3)
under the constraint f E arg min E(sign o
gEtip, (B"i,, (B*.R)
The SDF(b) cannot be explicitly constructed since relies the (unknown) optimal Bayes classifier.
4.2 Improving the accuracy of the maximally robust classifier
On the opposite side, we exhibit family of classifiers with lower accuracy but with higher certifiable robustness. We insist that the quantity of interest is the certifiable robustness [f(x) and not the true empirical robustness e (which can be higher). The former is computed exactly and freely, while the latter is difficult problem for which only upper bounds returned by attacks available. In the literature, the robustness only evaluated on well classified examples. The certificate can be both interpreted required to switch the class. Hence, we shall weight negatively this certificate for the examples that misclassified since confidence in presence of errors is worse. For this reason, propose in Definition
form of "confidence" of the network, and the minimal perturbations
5 new metric called the Mean Certifiable Robustness (MCR).
Definition (Mean Certifiable Robustness MCR) For any function f X + R LipNetl we define its weighted mean certifiable robustness R(P.y) (f)
5

---

on class P with label as:
(fP ==
We can readily see from the definition that the classifier with highest MCR for class P is the constant classifier f y X oc. The interest of this notion arises when we consider minimizing the loss function LW (f(x). v) == (z) i. when looking for classifier with the highest MCR.
Property Wasserstein classifiers (i.e WGAN discriminators) are optimally robust. The mini- mum of L (f(z), y) over P and Q is the Wasserstein-I distance [30] between P and Q according to the Kantorovich-Ruse Rubiissteiniiiiiii duality:
max fELip, +
min Erxy (f() (R",,3
(5)
Even though the minimizer of Lw (z), y) can have low accuracy. it has the highest MCR. Inter- estingly, the minimizer f of equation / invariant by translation: f - is also a minimizer for T any 7 E R. When T - (resp. -00) the classifier has 100% recall on Q (resp. P), and 0% P (resp. Q)- Does it always exist 7 with 100% accuracy overall? Sadly, even when the P and Q have disjoint support, the answer is no. We precise this empirical observation of (8 in Proposition 3
Proposition 3. WGAN discriminators are weak classifiers. For every 1/ 2 e > 0 there exist distributions P and Q with disjoint supports in IR such that for any optimum f of equation 5 the error of classifier sign f is superior to
Note that this minimum also invariant by dilatation: any finite upper bound L can be chosen for Equation 5 (see Appendix G
4.3 Controlling the accuracy/robustees tradeoff with loss parameters
Now that the extrema of the accuracy robustness tradeoff were characterized in 4.1 and 4.2 is yet to be answered if it is possible to control this tradeoff using conventional loss (and its parameters, as introduced in 3.2).
Interestingly, observe that Chee (f(x), = log - yr)(x) + (z)))
(z)) so when - 0 we get:
2
4
min SELip, (x t
EE (aa)) ( (f(z), v) -ao0))llog3) log (P,Q)Q.
In the limit of small temperatures, the BCE minimizer essentially behaves like the classifier of the
highest MCR (see Figure 3 and Appendix H). Similarly. the HKR loss hakr introduced in [8] for LipNet1 training allows fine grained control of the accuracy-robustner tradeoff:
Chkr (f(x) = LW (f(x), ac (f(x). v) = (f( a max (0,m (0.m-yffmm (on-yf())) vf()..
(6)
We recover Wi behavior for a 0, and hinge LH behavior for a - oo, in a fashion that reminds the role of for Cbee.
key takeaway that BCE, HKR and hinge loss have parameters that allow to control the accuracy robustness tradeoff, reaching unconstrained networks on the other. Empirically this tradeoff is observed as a Pareto front with accuracy on one axis, and robustness the other. Figure shows this the CIFAR 10 dataset using the robustness as robustness measures (other robustness measure yield similar observations, see fig 10a and TOb).
side the maximum robustness of MCR, and the accuracy of
In conclusion, these last two sections demonstrate that restraining networks to be in LipNet1 does not impact the classification capabilities while providing certificates of robustness; however, for these networks the loss parameters play an important role in this trade-off.
1-Lipschitz classifiers have generalization guarantees
In this section, explore the statistical and optimization properties of LipNetl networks, and prove the assumption of (31 that "adjusting the Lipschitz constant of feed-forward neural network controls how well the model will generalise to new data".

---

0.45
iR
0.40
Not certifiable
0.35
Hinge
at = 36
0.30
5.0
0.05
100.0
50.0
0.5
50.0
1.0
20.0
Robus
0.10
130.0
300.0
2.0
3.0
10.0
0.05
0.00
0.30
0.35
0.40
0.45
0.50
0.55
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
Validation accuracy
Figure 3: Accuracy-Robustnest trade-off CIFAR10 with Hinge, HKR and Categorical Cross- Entropy (CCE) hyper-parameters. Overall, for given network architecture, a Pareto front appears between clean accuracy and robust accuracy. We move along it by tuning the parameters of each loss. We trained small LipNet1 CNNs (0.4M params) with basic data augmentation (see appendix K for detailed experimental setting).
5.1 Consistency of LipNet1 class
LipNet1 class enjoys another remarkable property since it a Glivenko-Cantelli class: minimizers of Lipschitz losses are consistent estimators. In other words, as the size of the training set increases, the training loss becomes a proxy for the test loss: LipNetl neural networks will not overfit the limit of (very) large sample sizes.
Proposition 4. Train Loss is proxy of Test Loss. Let Px a probability measure on X x y where C R is a bounded set. Let (Ia Vi Vilss sample of p iid random variables with law Pxy. Let L be Lipschitz loss function over I x V. We define:
E,U) == - Σ (U((:)) v. and & (f) == B(a.y) (F(((), v)].
Then the empirical loss Ef( converges to the test loss (f) (taking the limit + co):
min (X
(f)
min (f)
(8)
(X
It is another flavor of the bias-variance trade-off in learning. Thanks Corollary T we know the LipNetl class does not suffer of bias, while the generalization gap (i.e the variance) can be made as small we want by increasing the size of the training (see Figure 4). The number of examples required to close the generalization gap is dataset specific in general, however it seems that with low fewer examples are required. This result may seem obvious, but we emphasize this property is not shared by AllNet networks (see Proposition in Appendix C.2) Nonetheless, most practitioners take for granted that bigger training sets ensure generalization for AllNet networks.
5.2 Understanding why unconstrained networks are prone to overfitting
Surprisingly, on AllNet networks, minimization of BCE leads to uncontrolled growth of Lipschitz constant and saturation of the predicted probabilities. This is impediment to generalization results. Proposition 5. Optimizing BCE over AllNet leads to divergence. Let be sequence of neural networks, that minimizes the BCE over a non-trivial training set (at least two different examples with different labels) of size p. i.e assume that:
lim Σ (r(((a)))) =
Let Lt be the Lipschitz constant of fc. Then lime- L, too. There is at least weight matrix W. such that lim ||Wll| = +00. Furthermore, the predicted probabilities are saturated:
lim (ff(xx))) E [0,1).
(10)
7

---

Trainivalidation accuracy
0.9
0.8
0.7
(CCE)
0.6
0.25
0.5
1.0
0.4
4.0
8.0
20%
100%
Dataset fraction
Figure 4: Link between LipNet1 and generalization gap, dataset size and cross-entropy tem- perature. We train CNN on different fractions of the CIFAR 10 train set (2%. 5%, 10%, 25%, 50% and 100% on z-axis) with different values of temperature (highlighted by different colors). Train (resp. validation) accuracy forms the upper (resp. lower) bound of each envelope. As r increases, more samples are required to reduce the generalization gap. Conversely, training a LipNet1 network with small 7 is equivalent to training a Lipschitz network with small L: the network generalizes well but the accuracy reaches a plateau (under-fitiin)). The AllNet network (in red) severely overfit: the generalization gap is large and validation accuracy corresponds the limit that would reach LipNetl as 7 increases. See appendix J for detailed experimental setting.
This issue is especially important since Lipschitz constant and adversarial vulnerabilities are lated [32]. The predicted probability o (x)) will either or (regardless of the train set), which do not carry any useful information the true confidence of the classifier
Example 1. Consider classification task R with linearly separable inputs { {-1, and labels {-1,
35
Nentoch' mathed foatt:
Parameters Norm
Nousrelt methed floust
Adaa flort44
We use an affine model f(x) = Wx + b for the logits (with W E R and E R.) (one-layer neural network). It exists W. b such that f achieves 100% accuracy. How-
25
20
ever, as noticed in (33) (Section 4.3.2) the BCE loss will not be zero. The minimization occurs only with the diverging sequence of parameters (AW, Xb) as + Oc. It turns the infimum not minimum!
10
30
Optimizer Step
Figure 5
Even on toy example with trivial model, the minimization problem is ill-defined. Without weight regularization, the minimizer can not be attained. This is compliant with the high Lipschitz constant of AllNet networks that have been observed in practice [23), and is confirmed by our experiment on MNIST with ConvNet (see Figure 12). The spectral norm of the weights is multiplied by 5 over the course of 25 epochs, whereas the validation accuracy remains the same (around 99%).
Furthermore, there is an issue of vanishing gradients with BCE first order methods struggle to Saturate the logits of AllNet networks, whereas second order methods in floa164 diverge expected. The poor properties of the optimizer, and the rounding errors in 32 bits floating point arithmetic, have greatly contributed the caveat of BCE minimization remaining mostly unnoticed by the community.
5.3 Lipschitz classifiers PAC learnable
Hinge loss C and HKR loss Lhkr benefit from Proposition The certificate [f(x) can be understood as confidence. Hence, we are interested a classifier that makes a decision only the prediction is above some threshold m >> 0, while !f(x)) < can be understood as examples for which the classifier is unsure: the label may flipped using attacks of norm S m. In this setting, we fall back to PAC learnability [10]: this theory gives bounds on the number of train samples

---

Properties
AllNet network
LipNetl network
Fit any boundary
yes IK
yes (Proposition
Robustness certificates
yes (Property
Consistent estimator
no (App
yes (Proposition 4 Figures
Gradients
exploding or vamshing
preserved for GNP (Appll
VC dimension bounds
architecture dependent
35
when m > 0 (Proposition
minimizer remark
ill-defined Le 3o (Proposition
attained (Proposition) L or must be tuned (Figure
BCE Chee
vanishing gradient (Ex 1
Wasserstein 2
minimizer
ill-defined L: 0.
attained, robust (Property weak classifier (Proposition
remark
diverges during training
Hinge cH
minimizer
attained
attained
remark
no guarantees margin
must be tuned
minimizer
ill-defined T oo
accuracy-robustness tradcoff and must be tuned (Figure
HKR Chke
remark
diverges during training
Table 1: Summary of notable results and the contributions.
required to guarantee that the test error will fall below some threshold 0 S Se< with probability least 1 > B 2 O, through the use of Vapnik Chervonenkis (VC) dimension bounds (34].
Proposition 1-Lipschitz Functions with margin are PAC learnable. Assume and Q have bounded support X. Let m > 0 the margin. Let C (X) (cT X + {1,, E Lip, (X,, [R) be the hypothesis class defined as follow.
+1 f(x() 2 m, if f(x))
(x)
-
(11)
otherwise, meaning "I doesn't I feel confident".
Let B the unit ball. Then the VC dimension 0 is finite:
n (x) VCddim (CTh((())))) (X)) (B)
vol
(12)
vol
Interestingly the classes are separable (e >> 0), choosing m = e guarantees that 100% accuracy is reachable. Prior over the separability of the input space is turned into VC bounds over the space of hypothesis. When m = 0 the VC dimension of space CTH (X) becomes infinite and the class not PAC learnable anymore: the training error will not converge to test error in general, regardless of the size the training set. is not a contradiction with Proposition error E(c)) (x)) lacks continuity w.r.t f(x) so is not a consistent estimator.
This VC bound is architecture independent which contrasts with the rest of literature on AllNet networks. Practically, it means that the LipNetl network architecture can chosen as big as we want without risking overfitting, as long as the margin is chosen appropriately. Proposition 7 also provides an architecture dependant bound for LipNetl networks.
Proposition 7. VC dimension of LipNetl neural networks. Let So Rm + R a LipNetl neural network with parameters 0 E θ, with GroupSort2 activation functions, and total of W neurons. Let H. {signfe 0 e Q the hypothesis class spanned by this architecture. Then we have:
VC (H) O ((n+ +1)2
(13)
In literature, tighter VC dimension bounds for neural networks exist, but they assume element-wise activation function 355 This hypothesis does not apply to GroupSort2 which is known to be more expressive [36), however we believe that this preliminary result can be strengthened.
6 Related work
LipNet1 networks parametrization benefit from a rich literature (see Appendix D) to enforce
the Lipschitz constraint in various layers [37 38
6 39 40
42
43 44 such as activation

---

functions, affine layers, attention layers or recurrent units. Residual connections are also Lipschitz (see Appendix F). Gradient Norm Preserving networks avoid the vanishing gradients [3] 45 phenomenon to which the LipNetl networks are prone, by using orthogonal matrices in affine layers. This justifies the "orthogonal neural network" terminology [46
48 ReLU based Lipschitz
networks suffer from expressiveness issues [1, and activation functions like GroupSort [11 36
(a special case of Householder reflection [49 50) have been proposed in replacement. Orthogonal
kernels are still an active research area 52 53 54
55 56 57 They are used in normalizing flows [58], ensemble methods [59], reinforcement learning 660 or graph neural networks [6]] The
optimization over the group of orthogonal matrices (known Stiefel manifold) has been extensively studied in 62 and algorithms suitable for deep learning are detailed in [63
65
66
68
66
Generalization bounds for general Lipschitz classifiers are given in
72 Links between adversarial robustness, large margins classifiers and optimization bias are studied in 73
74
16
75
The importance of the loss in adversarial robustness is studied in [76). See Appendix C.5
Conclusions
In this paper, we challenged the common belief that constraining Lipschitz constant degrades the classification performance of neural networks. We proved that LipNetl networks exhibit numerous attractive properties (see Table Din summary): they provide robustness radius certificates without restrictions on their expressive power. They benefit from generalization guarantees. We showed that the hidden parameters of the loss allow to control the generalization gap and certifiable robustness.
While the question of the LipNet1 architecture is often in the spotlight, the loss is overlooked. We pointed out that Cross-Entropy is not necessarily the best choice, margin- based losses, such as hinge or its variant HKR, have appealing properties (table
Perspectives
This paper aims to be at the intersection between theoretical ML and (empirical) deep learning. Lipschitz constrained networks allow to directly put in perspective mathematical proofs and we are confident that this theory can be verified empirically on very large-scale vision datasets (such as Imagenet 777)
This paper also provides a toolbox of results and experiments to serve as a basis for future works. We aim to open new research directions, including outside the field of robust learning. AllNet networks could benefit from LipNet literature: the absence of control over the Lipschitz constant of AllNet is mitigated in practice by elements such as mixup or weight decay. Such elements would be better understood by looking at how they affect the (uncontrolled) Lipschitz constant of AllNet.
The efficient training over LipNet1 is still active research area. Moreover, AllNet networks benefits from architectural elements such as skip connections and batch normalization (see appendix(F). As LipNet1 networks get more mature, empirical results will improve, matching theory even more (explaining the emphasis on the theoretical proofs instead of the design of LipNetl depicted in appendix D
Many practices in deep learning entangle the questions of architecture, of generalization and of optimization. However, these elements usually have unexpected consequences the nature of the optimum and the optimization process. Our work is a first step toward a better separation these components and their role.
Acknowledgments and Disclosure of Funding
We thank Sébastien Gerchinovitz for critical proof checking, Jean-Michel Loubes for useful discus- sions, and Etienne de Montbrun, Thomas Fel and Antonin Poché for their read-checking. A special thank to Agustin Picard for his useful advice and thorough reading of the paper. This work has benefited from the AI Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future- PIA3" program under the Grant agreement ANR- 19-P31A-0004 The authors gratefully acknowledge the support of the DEEL project ?
htttps:/xww..eee
10

---

References
[1] Christian Szegedy. Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties neural networks. International Conference on Learning Representations, 2014.
[2] Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li. Adversarial examples: Attacks and defenses for deep learning. IEEE transactions on neural networks and learning systems, 30(9):2805 2824, 2019.
[3] Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jöm-Henrik Jacohsen, Preventing gradient attenuation in lipschitz constrained convolutional networks. In Advances in Neural Information Processing Systems (NeurlPS), volume 32, Cambridge, MA, 2019. MIT Press.
J. Sokolic, R. Giryes, G. Sapiro, and M. R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16))426544888 2017.
[5] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom. Alexander Turner, and Aleksander Madry. Robust- ness may be at odds with accuracy. In International Conference on Learning Representations, 2019.
[6] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning. pages 214-20122 223, PMLR. 2017.
[7] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks:
Improving robustness adversarial examples. In International Conference Machine Learning, pages 354-863. PMLR, 2017.
[8] Mathieu Serrurier, Franck Mamalet, Alberto González-Sanz, Thibaut Boissin, Jean-Michel Loubes, and Eustasio del Barrio, Achieving robustness in classification using optimal transport with hinge regularization. In Proceedings of the IEEE/ČVF Conference on Computer Vision and Puttern Recognition (CVPR), 2021.
[9] Todd Huster, Cho-Yt Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant as a defense against adversarial examples. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 16 29. Springer, 2018
[10] Leslie G Valiant. theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
[11] Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pages 291-301. PMLR, 2019.
[12] Joshua Cape, Minh Tang, and Carey E Priebe. The two-to-infinity norm and singular subspace geometry with applicatioos to high-dimensional statistics. The Annals of Statistics, 47(5):2405-2439, 2019.
[13] Mohamad Hassoun et al. Fundamentals of artificial neural networks. MIT press, 1995.
[14] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
[15] Åke Björck and Clazett Bowie. An iterative algorithm for computing the hest estimate of orthogonal matrix. SIAM Journal Numerical Analysis, 8(2):358-364, 1971.
[16] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. In Advances Neural Information Processing Systems, volume 31, pages 6541-6550. Curran Associates, Inc., 2018.
[17] Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Representations, 2019.
[18] Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pages 5276-5285. PMLR, 2018.
[19] Tsui- Wei Weng, Huan Zhang, Pin-Yt Yu Chen, Jinfeng Yi, Dong Su. Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness neural networks: An extreme value theory approach. International Conference on Learning Representations, 2018.
[20] Bohang Zhang, Tianle Cai, Zhou Lu. Di He, and Liwei Wang. Towards certifying l-infinity robustness using neural networks with 1-inf-dist neurons. In International Conference on Machine Learning, pages 12368 12379. PMLR, 2021.

---

[21] Aleksander Madry. Aleksandar Makelov. Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[22] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1310-1320. PMLR, 2019.
[23] Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3839-3848, 2018.
[24] Yao-Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Russ Salakhutdinov, and Kamalika Chaudhuri. closer look accuracy vs. robustness. Advances in Neural Information Processing Systems, 33, 2020.
[25] Mikael Rousson and Nikos Paragios. Shape priors for level set representations. In European Conference on Computer Vision, pages 78-92. Springer, 2002.
[26] Anirban Chakraborty, Manaar Alam, Vishal Dey. Anupam Chattopadhyay, and Debdeep Mukhopadhyay, A survey adversarial attacks and defences. CAAI Transactions Intelligence Technology. 6(1):25-45.
2021.
[27] Yinpeng Dong, Hang Su, Jun Zhu, and Fan Bao. Towards interpretable deep neural networks by leveraging adversarial examples. In AAAI-19 Workshop on Network Interpretability for Deep Learning, 2017.
[28] Richard Tomsett, Amy Widdicombe, Tianwei Xing, Supriyo Chakraborty, Simon Julier, Prudhvi Gurram, Raghuveer Rao, and Mani Srivastava. Why the failure? how adversarial examples can provide insights for interpretable machine learning. In 2018 21st International Conference on Information Fusion (FUSION), pages 845. IEEE, 2018.
[29] Andrew Ross and Finale Doshi-Velezz Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[30] Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
[31] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural networks by enforcing lipschitz continuity, Machine Learning, 110(2):393 316, 2021.
[32] Kamil Nar, Orhan Ocal, S Shankar Sastry, and Kannan Ramchandran. Cross-entropy loss and low-rank features have responsibility for adversarial examples, arXiv preprint 100Xv::901.08300 2019.
[33] Christopher Bishop. Pattern recognition and machine learning. springer, 2006.
[34] VN Vapnik and Ya Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & Its Applications. 16(2):264 280, 1971.
[35] Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tighe ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20:63-1,2015 2019.
[36] Ugo Tanielian and Gerard Biau. Approximating lipschitz continuous functions with groupsort neural networks. In International Conference on Artificial Intelligence and Statistics, pages 442-450. PMLR, 2021.
[37] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in Neural Information Processing Systems, volume 30, pages 5767-5777. Curran Associates, Inc., 2017.
[38] Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizahility of deep learning. arXiv preprint 1705. 2017.
[39] Tim Salimans and Diederik Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. NIPS, 2016.
[40] Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Muchine Learning, pages 5562-5571. PMLR, 2021.
[41] Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference Machine Learning, pages 1979-1978. PMLR, 2018.
12

---

[42] N. Benjamin Erichson, Omri Azencot, Alejandro Queiruga, Liam Hodgkinson, and Michael W. Mahoney. Lipschitz recurrent neural networks. In International Conference Learning Representations, 2021.
[43] Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. Advances Neural Information Processing Systems, 34, 2021.
[44] Zhenyu Zhu, Fabian Latorre, Grigorios Chrysos, and Volkan Cevher. Controlling the complexity and lipschitz constant improves polynomial nets. In International Conference on Learning Representations, 2022.
[45] Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regularizations in training deep networks? Advances in Neural Information Processing Systems, 31, 2018.
[46] Bartlomiej Stasiak and Mykhaylo Yatsymirskyy. Fast orthogonal neural networks. In International Conference on Artificial Intelligence and Soft Computing, pages 142-149. Springer, 2006.
[47] Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE transactions on pattern analysis and machine intelligence, 43(4):1352-1335 2019.
[48] Jiahao Su, Wonmin Byeon, and Furong Huang. Scaling-up up diverse orthogonal convolutional networks by a paraunitary framework. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 20546-20579. PMLR, 2022.
[49] Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametri- sation of recurrent neural networks using householder reflections. In International Conference on Machine Learning, pages 2401-2409. PMLR. 2017.
[50] Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness cifar- 10 and cifar- 100. In International Conference on Learning Representations, 2021.
[51] Alexander V Gayer and Alexander V Sheshkus. Convolutional neural network weights regularization via orthogonalization. Twelfth International Conference on Machine Vision (ICMV 2019), volume 11433, page 1143326. International Society for Optics and Photonics, 2020.
[52] Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X Yu. Orthogonal convolutional neural networks. In Proceedings of the IREE/CVF Conference on Computer Vision and Pattern Recognition, pages 11 1150511515, 2020.
[53] Sheng Liu, Xiao Li, Yuexiang Zhai, Chong You, Zhihui Zhu, Carlos Fernandez-Granda, and Qing Qu Convolutional normalization: Improving deep convolutional network robustness and training. Advances in Neural Information Processing Systems, 34:28919 28928, 2021.
[54] El Mehdi Achour, François Malgouyres, and Franck Mamalet. Existence, stability and scalability of orthogonal convolutional neural networks. arXiv preprint 1x..::2000..062.. 2021.
[55] Asher Trockman and J Zico Kolter, Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021.
[56] Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Machine Learning, pages 9756-9766. PMLR. 2021.
[57] Tan Yu, Jun Li, YUNFENG CAL, and Ping Li. Constructing orthogonal convolutions in an explicit manner. In International Conference Learning Representations, 2021.
[58] Leonard Hasenclever. Jakub M Tomezak, Rianne van den Berg, and Max Welling. Variational inference with orthogonal normalizing flows. In Bayesian Deep Learning, NIPS 2017 workshop. 2017.
[59] Peyman Sheikholharam Mashhadi, Stawomir Nowaczyk, and Sepideh Pashami. Parallel orthogonal deep neural network. Neural Networks, 140:167- 183, 2021.
[60] Florin Gogianu, Tudor Berariu, Mihacla Rosca, Claudia Clopath, Lucian Busoniu, and Razvan Pascanu. Spectral normalization for deep reinforcement learning: an optimisation perspective. Proceedings of the International Conference on Machine Learning (ICML). JMLR. org. 2021.
[61] George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self-attention layers with application to graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, pages 2456 2466. PMLR. 2021.
13

---

[62] P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms matrix munifolds. Princeton University Press, 2009.
[63] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In International Conference on Machine Learning, pages 120-11288. PMI.R, 2016.
[64] Stephanie L Hyland and Gunnar Rätsch. Learning unitary operators with help from u (n). In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
[65] Mario Lezcano- -acaado and David Martunez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference on Machine Learning, pages 77794-3803, PMLR, 2019.
[66] Lci Huang, Xianglong Liu, Bo Lang, Adams Yu, Yongliang Wang, and Bo Li. Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[67] Pierre Ablin and Gabriel Peyré. Fast and accurate optimization on the orthogonal manifold without PMLR,
retraction. In International Conference on Artificial Intelligence and Statistics, pages 2022.
[68] lordanis Kerenidis, Jonas Landman, and Natansh Mathur. Classical and quantum algorithms for orthogonal neural networks. arXiv preprint urXiv22106.07199 2021.
[69] Krzysztof Choromanski, David Cheikhi, Jared Davis, Valerii Likhosherstov, Achille Nazaret, Achraf Bahamou, Xingyou Song, Mrugank Akarte, Jack Holder, Jacob Bergquist, et al. Stochastic flows and geometric optimization on the orthogonal group. In International Conference on Machine Learning, pages 1918-1928, PMLR, 2020.
[70] Ulrike von Luxburg and Olivier Bousquet. bistance-based classification with lipschitz functions. J. Mach. Learn. Res., 695,9-695, 2004.
[71] Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient classification for metric data. IEEE Transactions on Information Theory, 60(9):5750- -7559, 2014.
[72] Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Opectrally-normalizz margin bounds for neural networks. In Proceedings of the 31st International Conference Neural Information Processing Systems, pages 6241-6250, 2017.
[73] Chris Finlay, Jeff Calder, Bilal Abbasi, and Adam Oberman. Lipschitz regularized deep neural networks generalize and are adversarially robust. arXiv preprint a88iv:1808. 09540, 2018.
[74] Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distrihutions. In International Conference on Learning Representations, 2019.
[75] Fartash Faghri, Cristina Vasconcelos, David J. Fleet, Fabian Pedregosa, and Nicolas Le Roux. Bridging the gap between adversarial robustness and optimization bias. ICLR 2021 Workshop on Security and Safety in Machine Learning Systems, 2021.
[76] Tianyu Pang, Kun Xu, Yinpeng Dong, Chao Du, Ning Chen, and Jun Zhu. Rethinking softmax cross- entropy loss for adversarial robustness. In International Conference Learning Representations, 2019.
[77] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPRO9, 2009.
[78] Halsey Lawrence Royden and Patrick Fitzpatrick. Real analysis, volume 32, Macmillan New York, 1988.
[79] Jon Wellner A. W. van der vaart. Weak Convergence and Empirical Processes. Springer- Verlag New York, 1996.
[80] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnabliity and the cheevn-chevoonenii dimension. Journal of the ACM (JACM), 36(4):929-98)) 965, 1989.
[81] Stanislaw Szarck. Metric entropy of homogeneous spaces. Banach Center Publications, 43(1):395 1998.
[82] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
[83] Emerson León and Günter M Ziegler. Spaces of convex n-partitions. In New Trends in Intuitive Geometry. pages 279-306. Springer, 2018
14

---

[84] Felix A Gers. Jürgen Schmidhuber, and Fred Cummins. Learning to forget: Continual prediction with Istm. In Ninth International Conference Artificial Neural Networks ICANN 99. IET. 1999.
[85]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[86] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications the ACM, 64(3):007-115, 2021.
15


Reviews:
[{"review_id": "tJ3Se8vODd", "reviewer": "Reviewer_eWSm", "summary": "The paper proposes many theoretical statement Lipschitz neural network for classification and show that these specific networks follows attractive properties.", "questions": "I suggest that the other should carefully rewrite the paper with a clear objective, the typography should be respected.\nThe different results of the paper are nice, but in order to be published they should be properly articulated.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "AllNet networks are defined as any neural networks without any constraints. This class does not produce Lipschitz function without any further hypothesis (such as activations are Lipschitz).\n\nThe paper is all over the place and the main research line is unclear. Most of the theoretical results are rather common or \"trivial\". The whole paper seeks for internal coherence and lacks of general purpose. As a reader, it is difficult to grasp what is the objective.\nThe present paper seems to be more adequate for a journal publication than to a conference.\n\n* Global style as the biggest weakness\n\nThe main assumption behind the development of the theory is the fact that Lipchitz neural networks are \"often perceived as not expressive\", which I do not remember ever reading in the literature. Most of the paper seems fuzzy: it goes from BCE to robustness certification to a (trivial) convergence proposition (prop 4) to consideration about float32/64 (ex 1)... it is just too much. There are no transitions and at no moment the reader understands what is the point.\n\nOne of the biggest problem is the writing style that makes the paper hard and annoying (sorry...) to read.\nFor example among many other problems:\n\n    - sentences must contain a verb and end with a '.'(even when it ends with a formula);\n    - theorem should be self contained, exterior references should remain exceptional;\n    - organize the equations in order to be easily readable;\n    - separate definitions and remarks (e.g. def 1 & 2 contains definitions and remarks);\n    - separate propositions and definitions (e.g. corollary 1 contains a definition and a proposition);\n    - the proofs rely on many technical tools such as Lebesgue measure but the pre-requisite (Borel space etc) are never explicitely given.\nMost of the proofs in the appendix should be re-written. More personal but I think the footnotes in the paper could be avoided.\nThe paper is full of references and it costs the readability of the arguments. The reader gets overwhelmed very quickly for the wrong reasons.\n\n* References\n\nmost reference are incomplete (many article are reference as arxiv instead than the published and peer-reviewed version)\n\n* Others\n\nl94: one needs additional hypothesis on AllNet to claim that they have finite Lipschitz constant (Lipschitz activation would do).\n\nl216: the reference to cor 1 seems dubious: it is a definition of \\epsilon separation rather than about bias.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OiW-mZgUHHJ", "reviewer": "Reviewer_wa64", "summary": "The authors theoretically studied several properties of 1-Lipschitz neural networks (LipNet1). They showed that LipNet1 can learn and approximate any classification decision boundary. Secondly, they showed that LipNet1 is certifiable robust and not prone to overfitting, unlike conventional unconstrained models. They showed that by varying margin for hinge loss or temperature for binary cross-entropy, one can control the trade-off between robustness and accuracy.", "questions": "- Can the authors include experiments where LipNet1 model robustness with tuned $L$ or $\\tau$ is tuned and compared with current state-of-the-art methods?\n- How does the choice of the loss function affect the training dynamics and generalization?", "limitations": "The authors briefly discussed the limitations of their work: lack of convergence speed bounds. The limiations of this work can be expanded. The authors should describe all the assumptions in detail and clearly state their limitations when providing their theoretical results.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:**\n\n- The paper derives several theoretical results. Yet, I am not confident to say that all the results presented here are original.\n\n**Quality:**\n\n- The authors state that the purpose of this paper is to address the common misconception that “they (1-Lipschitz neural networks) remain commonly considered as less accurate”. However, the authors do not cite any experimental study or theoretical work, where someone claimed that 1-Lipschitz neural networks are inherently less accurate or less expressive than unconstrained neural network models.\n- The authors provide an interesting analysis of 1-Lipschitz neural networks and show that LipNet1 can have certain advantages over conventional neural networks.\n- The theoretical analysis, however, is not very useful as 1) we do not know how many samples are required for the convergence of the LipNet1 models; 2) the initial VC dimension bounds are rather vacuous, see proposition 7, where VC bounds depend exponentially on the number of neurons.\n\n**Clarity:**\n\n- The paper at times is difficult to follow its main story is fragmented without sharing a common theme. The expanded experiments (not just toy experiments) should be included to expand the paper and confirm the main theoretical results.\n\n**Significance:**\n\n- The paper provides an analysis of the properties of LipNet1 models, which recently become of interest in the community recently. However, to highlight its significance, the authors should expand the experimental section to compare LipNet1 models and conventional models. At the present moment, the provided evidence that LipNet1 models are not prone to overfitting unlike conventional models is not conclusive.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Mdx2L7jO5-R", "reviewer": "Reviewer_VK8y", "summary": "This paper challenges the common belief that 1-Lipschitz natural networks are less generalizable than regular networks. It accomplishes this by proving a series of claims. The authors first demonstrate that any classification problem, under mild assumptions, has a 1-Lipschitz solution, and that the error is zero if the distributions of classes are well separated. They go on to show that 1-Lipschitz models can always minimize a tempered cross-entropy loss, while the generalization performance depends heavily on the temperature value. This paper suggests that the low performance of 1-Lipschitz networks in the literature can be attributed to the wrong choice of temperature. One positive thing about 1-Lipschitz networks is that one can certify the output margin $\\|f(x)\\|$ rather than the input margin, as the former is a lower bound of the latter. The paper demonstrates that the WGAN discriminator maximizes an average of the signed output margin, thus it is optimally robust in this respect. The WGAN discriminator has the disadvantage of not ensuring a very high level of accuracy. There are even classification problems for which the WGAN discriminator's accuracy can be arbitrarily low. Nevertheless, implicit/explicit regularizations with 1-Wasserstein distance can be used for a trade-off between accuracy and “certifiable” robustness in 1-Lipschitz networks. Finally, the paper discusses some guarantees on the learnability of 1-Lipschitz networks.", "questions": "- Isn’t the requirement in Eq. (3) too conservative? Does changing the min over x to an expectation help here? \n- Are you sure about Lines 182 and 183? The MCR for Q is not missing here?\n- Can you provide an example of the behavior discussed at the end of Sec. 5.2 for conv nets trained on datasets like CIFAR-10 or MNIST?\n- There is no comparison with SotA certifiable networks in the current manuscript.\n- Adversarial training of regular networks leads to a large gap between training and test losses. Should we expect this gap to disappear for adversarial training of 1-Lipschitz networks?\n- Do the authors think that playing with the temperature of 1-Lipschitz networks is enough to build certifiable robust classifiers?\n- The observation made in this paper bears some similarities to other publications, such as (On Calibration of Modern Neural Networks, Guo et al., ICML 2017) and (How Good is the Bayes Posterior in Deep Neural Networks Really?, Wenzel et al., ICML 2020).\n- Some typos: L137, cannot guarantees; L138, “is not” repeated twice; L154: an unified.", "limitations": "The extent to which certain observations of this paper hold in practice is not clear enough.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a thought-provoking paper that questions certain overlooked aspects of 1-Lipschitz networks that are associated with adversarial robustness. It contains many interesting insights as well as simple illustrations to demystify some myths about these networks. While discussing interesting aspects of Lipschitz networks, the paper does not present its results in a unified manner, rather it provides nuggets of understanding. I am pleased to learn that 1-Lipschitz networks may not be as weak as previously thought, but I would like to know how these insights can be used to build robust and accurate models. Additionally, the paper could have better positioned itself compared to previous studies.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "62wT0gu6Gbt", "reviewer": "Reviewer_jRZ5", "summary": "The paper studies 1-Lipschitz constrained neural networks, and prove some results for this class of networks. The paper defines 1Lip nets as those networks for which the output function is Lipschitz constrained with a Lipschitz constant of 1. They cite a way to construct such feed forward networks based on the norms of the weight matrices. They then show that for any binary labelling function, one can get an equivalent 1-Lipschitz function which agrees with the labelling function on all points of the domain. They then empirically show that tuning the temperature hyper-parameter while learning with BCE loss is important, and imply connections between this hyper-parameter and the lipschitz constant. They then show that 1Lip network are certifiably robust to adversarial attacks, and that the discriminator of a WGAN, which is also a 1Lip network is the optimally robust classifier. Finally, they give generalization results of 1Lip networks, showing that this class of networks is PAC learnable with a VC dimension independent of the architecture.  ", "questions": "How does this analysis extend to other types of networks apart from feed forward networks?", "limitations": "Some of the limitations are listed in the weaknesses above. A more thorough empirical evaluation on other tasks and adversarial perturbations would be appreciated. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths - \n1. The results in the paper are novel, interesting and important.\n2. The generalization guarantees and robustness results can open up a new line of research into these architectures. \n\nWeaknesses - \n1. More empirical evaluation could benefit the paper.\n2. The writing could be improved, in particular, a lot of prior knowledge is assumed.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept