Ana Neacs

Jean-Christophe Pesquet

Vlad Vasilescu

Corneliu Burileanu

V C Pesquet

C Vasilescu

Burileanu

ABBA Neural Networks: Coping with Positivity, Expressivity, and Robustness *

Keywords: Neural Networks, Robustness, Optimization, Lipschitz, Image Classification MSC codes. 15A48, 68T05, 65K10

We introduce ABBA networks, a novel class of (almost) non-negative neural networks, which are shown to possess a series of appealing properties. In particular, we demonstrate that these networks are universal approximators while enjoying the advantages of non-negative weighted networks. We derive tight Lipschitz bounds both in the fully connected and convolutional cases. We propose a strategy for designing ABBA nets that are robust against adversarial attacks, by finely controlling the Lipschitz constant of the network during the training phase. We show that our method outperforms other state-of-the-art defenses against adversarial white-box attackers. Experiments are performed on image classification tasks on four benchmark datasets.

1. Introduction. Deep learning methods based on neural network models have received increasing attention in the scientific community, because of their stunning abilities to solve a variety of complex tasks. These powerful systems excel at learning intricate mappings and, in some cases, even surpass human performance. However, deep architectures usually lack interpretability and they may lead to over-parameterized models [START_REF] Gamarnik | Self-regularity of output weights for overparameterized two-layer neural networks[END_REF][START_REF] Parkinson | Linear neural network layers promote learning single-and multiple-index models[END_REF]. Additionally, their robustness is not well-controlled, leaving them exposed to potential adversarial attacks. For instance, [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] demonstrated that by introducing carefully-crafted, low-magnitude adversarial perturbations, neural classifiers could be easily fooled [START_REF] Guo | Bounding training data reconstruction in private (deep) learning[END_REF]. A way of overcoming the aforementioned challenges consists in introducing some specific constraints in the neural network design. In this article, we are interested in nonnegativity and stability constraints on the network weights.

It is widely accepted that humans possess the innate ability to decompose complex interactions into discrete, intuitive hierarchical categories before analyzing them [START_REF] Seung | Learning the parts of objects by non-negative matrix factorization[END_REF]. Conceptually, this evolution towards part-based representation in human cognition can be linked to non-negativity restrictions on the network weights [START_REF] Zurada | Learning understandable neural networks with nonnegative weight constraints[END_REF]. This idea, along with other factors, has sparked interest in neural networks with non-negative weights. These networks have drawn attention for several reasons. Firstly, they align with human understandability, making them more interpretable. Secondly, the non-negativity constraint can act as beneficial regularization, effectively reducing overfitting issues. Moreover, recent studies have demonstrated that it is possible to derive a tight Lipschitz bound for such networks. This Lipschitz constant serves as a valuable metric for quantifying the robustness of the network, enabling us to design networks with enhanced resilience to adversarial perturbations during the training process. Despite their advantages, one significant drawback of networks with non-negative weights is that they might be less expressive than networks with arbitrary signed weights. In [START_REF] Wang | Why do networks have inhibitory/negative connections?[END_REF], it is shown that standard non-negative networks are not universal approximators [START_REF] Wang | Why do networks have inhibitory/negative connections?[END_REF], a limitation that Outline. The rest of the paper is organized as follows. Section 2 offers an overview of the related literature, while in Section 3 our main contributions concerning ABBA architectures are introduced, alongside a list of fundamental properties. Section 4 extends our results to the case of convolutional neural networks and two Lipschitz constant expressions are derived. Section 5 describes the training strategy we employ to generate robust models with respect to adversarial perturbations. Section 6 details the results obtained for different image classification tasks, while Section 7 is dedicated to concluding remarks.

2. Related work. Non-negative neural networks. Inspired by non-negative matrix factorization (NMF) techniques, the work of [START_REF] Zurada | Learning understandable neural networks with nonnegative weight constraints[END_REF] introduces non-negative restrictions on the weights to create neural networks in which the hidden units correspond to identifiable concepts. [START_REF] Zurada | Deep Learning of constrained autoencoders for enhanced understanding of data[END_REF] showed that Autoencoders (AE) trained under non-negativity constraints are able to derive meaningful representations that unearth the hidden structure of high-dimensional data. Their method showed promising results from both performance and feature interpretation viewpoints on four different classification tasks. [START_REF] Diakonikolas | Algorithms and SQ lower bounds for PAC learning one-hidden-layer ReLU networks[END_REF] presented the first polynomial-time algorithm for Probably Approximately Correct (PAC) learning 1layer neural networks with positive coefficients. Moreover, ensuring non-negativity has been shown to have a regularization effect, reducing feature overfitting, which is a very common problem, especially 1 A full TensorFlow implementation of our framework can be provided on demand and will be made publicly available upon paper acceptance.

This manuscript is for review purposes only.

for tasks where the available training data is scarce [START_REF] Neacs | EMG-based automatic gesture recognition using robust neural networks[END_REF]. Neural networks defining convex functions of their inputs [START_REF] Amos | Input convex neural networks[END_REF] also constitute a subclass of networks with non-negative weights.

Link with other networks. From another perspective, the idea of using redundant weights is reminiscent of siamese networks [START_REF] Bromley | Signature verification using a "siamese" time delay neural network[END_REF]. These architectures are successfully used to handle similarity learning tasks, such as face verification [START_REF] Taigman | Deepface: Closing the gap to human-level performance in face verification[END_REF], character recognition [START_REF] Koch | Siamese neural networks for one-shot image recognition[END_REF], and object tracking [START_REF] He | A twofold siamese network for real-time object tracking[END_REF].

Siamese networks compute a similarity metric on the representations of the inputs, after applying the same transformation to each one. Apart from the proven efficiency on solving computer vision tasks, they have lately been employed in NLP problems, e.g., computational argumentation. In [START_REF] Gleize | Are you convinced? Choosing the more convincing evidence with a Siamese Network[END_REF], it is shown that siamese architectures outperform other baselines trained on convincingness datasets.

Robustness.

The robustness of neural networks against possible adversarial attacks is a topic that has received increasing attention since nowadays AI-based solutions are ubiquitous [START_REF] Papakostas | A survey on adversarial deep learning robustness in medical image analysis[END_REF][START_REF] Neumayer | Approximation of Lipschitz functions using deep spline neural networks[END_REF]. A sizable body of literature on adversarial attacks and different defense strategies have emerged in recent years as a result of the work in [START_REF] Szegedy | Intriguing properties of neural networks[END_REF]), which revealed the alluring susceptibility of neural networks to adversarial perturbations and proposed a box-constrained L-BFGS algorithm for finding adversarial examples. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] introduced the FGSM attack as a one-step modification of the input image, following the direction of loss maximization, while [START_REF] Kurakin | Adversarial machine learning at scale[END_REF] incorporated this step into an iterative method known as PGD, seen as an improvement over basic FGSM. DeepFool [START_REF] Moosavi-Dezfooli | Deepfool: A simple and accurate method to fool deep neural networks[END_REF] iteratively searches for the closest adversarial point that directs the optimization towards crossing the decision boundary. DDN [START_REF] Rony | Decoupling direction and norm for efficient gradient-based ℓ2 adversarial attacks and defenses[END_REF] and FMN [START_REF] Pintor | Fast minimum-norm adversarial attacks through adaptive norm constraints[END_REF] attacks fall into the category of projected-gradient methods, using iterative updates of the perturbation vector towards the minimization of its magnitude.

Defensive strategies have been developed to alleviate this robustness issue. [START_REF] Silva | Opportunities and challenges in deep learning adversarial robustness: A survey[END_REF] divides adversarial defense methods into three categories: adversarial detection, gradient masking, and robust optimization. Adversarial Training (AT) was first introduced by [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] and later improved by [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF].

Recent works on AT [START_REF] Sinha | Certifiable distributional robustness with principled adversarial training[END_REF][START_REF] Wang | Improving adversarial robustness requires revisiting misclassified examples[END_REF] have successfully analyzed and refined training techniques, however, no theoretical certificates regarding their behavior in the presence of different adversaries have been established yet. Regularization-based methods, such as [START_REF] Li | Learning without forgetting[END_REF][START_REF] Shafahi | Adversarially robust transfer learning[END_REF][START_REF] Zhang | Theoretically principled trade-off between robustness and accuracy[END_REF], include additional terms in their objective, steering the learning process in a direction that leads to better generalization. [START_REF] Raghunathan | Certified defenses against adversarial examples[END_REF] provides robustness certificates for neural networks with one hidden layer, yielding an upper bound of the error in the presence of any adversary (see [START_REF] Croce | Provable robustness of ReLU networks via maximization of linear regions[END_REF][START_REF] Gowal | A dual approach to verify and train deep networks[END_REF][START_REF] Raghunathan | Semidefinite relaxations for certifying robustness to adversarial examples[END_REF] for more advanced methods.

Randomized smoothing [START_REF] Cohen | Certified adversarial robustness via randomized smoothing[END_REF][START_REF] Lecuyer | Certified robustness to adversarial examples with differential privacy[END_REF][START_REF] Li | Certified adversarial robustness with additive noise[END_REF][START_REF] Salman | Provably robust deep learning via adversarially trained smoothed classifiers[END_REF][START_REF] Zhai | MACER: Attack-free and scalable robust training via maximizing certified radius[END_REF] certifies the robustness of a classifier around an input point by measuring the most-likely prediction over Gaussian-corrupted versions of the point.

Lipschitz properties of neural networks.

As highlighted by [START_REF] Szegedy | Intriguing properties of neural networks[END_REF], the Lipschitz behavior of a neural model is closely correlated with its robustness against adversarial attacks, providing an upper bound on the response given input perturbations. Controlling the Lipschitz behavior of the network thus offers theoretical stability guarantees. However, computing the exact constant, even for small networks is an NP-hard problem [START_REF] Katz | Reluplex: An efficient SMT solver for verifying deep neural networks[END_REF], and finding a good approximation in a reasonable time is an open challenge. Several solutions have been proposed lately (see for example: [START_REF] Béthune | Pay attention to your loss : understanding misconceptions about Lipschitz neural networks[END_REF][START_REF] Gupta | Multivariate Lipschitz analysis of the stability of neural networks[END_REF][START_REF] Khromov | Some fundamental aspects about Lipschitz continuity of neural network functions[END_REF][START_REF] Zhang | Rethinking Lipschitz neural networks and certified robustness: A Boolean Function Perspective[END_REF]).

[45] introduced deel-lip, a framework to control the Lipschitz constant of each layer individually, while [START_REF] Anil | Sorting out Lipschitz function approximation[END_REF] propose GroupSort networks to ensure robustness. [START_REF] Pauli | Training robust neural networks using Lipschitz bounds[END_REF] proposed a framework for training fully-connected neural networks using Lipschitz regularized and constrained techniques, proving their effectiveness in the scenario of Gaussian-added perturbation noise. A recent result in [START_REF] Combettes | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF] showed that in the case of models with non-negative weights a tight Lipschitz bound can be established, making possible the training of neural network models with certified robustness guarantees.

This manuscript is for review purposes only.

ABBA Neural Networks.

3.1. Problem formulation. In the remainder of this paper, ∥ • ∥ will denote the ℓ 2 -norm when dealing with a vector, and the spectral norm when dealing with a matrix. An m-layer feedforward neural network can be described by the following model.

Model 3.1. T is feedforward neural network if there exists (N i ) 1⩽i⩽m ∈ (N \ {0}) m such that (3.1) T = T m • • • • • T 1
where, for every layer index i ∈ {1, . . . , m},

T i = R i (W i • +b i ), W i ∈ R Ni×Ni-1 is the weight matrix, b i ∈ R
Ni the bias vector, and R i : R Ni → R Ni the activation operator. N i corresponds to the number of inputs at the i-th layer. Such a layer is convolutive if it corresponds to a weight matrix W i having some Taoeplitz (or block Toeplitz) structure.

We will say that the activation operator R i is symmetric, if there exists

(c i , d i ) ∈ (R Ni ) 2 such that (3.2) (∀x ∈ R Ni ) R i (x) -d i = -R i (-x + c i ).
In other words, (c i , d i )/2 is a symmetry center of the graph of R i .

For example, if R i is squashing function used in CapsNets [START_REF] Sabour | Dynamic routing between capsules[END_REF], it is such that

(3.3) (∀x ∈ R Ni ) R i (x) = µ∥x∥ 1 + ∥x∥ 2 x.
with µ = 8/(3 √ 3). It thus satisfies the symmetry property (3.2) with c i = d i = 0. In addition, R i is nonexpansive, i.e. it has a Lipschitz constant equal to 1 [START_REF] Combettes | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF] Other examples of symmetric and nonexpansive activation operators are presented in Appendix SM1 2 .

3.2. ABBA Matrices. We first define ABBA matrices which will be the main algebraic tool throughout this article.

Definition 3.2. Let (N 1 , N 2 ) ∈ (N \ {0}) 2 . A N1,N2 is the set of ABBA matrices of size (2N 2 ) × (2N 1 ), that is M ∈ A N1,N2 if there exist matrices A ∈ R N2×N1 and B ∈ R N2×N1 such that (3.4) M = A B B A .
The sum matrix associated with M is then defined as S(M

) = A + B.
We give some of the most relevant properties of these matrices. In particular, we will see that the ABBA structure is stable under standard matrix operations.

Proposition 3.3. Let (N 1 , N 2 , N 3 ) ∈ (N \ {0}) 3 . (i). If M ∈ A N2,N1 , then its transpose M ⊤ ∈ A N1,N2 and S(M ⊤ ) = S(M ) ⊤ . (ii). If (M 1 , M 2 ) ∈ (A N2,N1 ) 2 , then M 1 + M 2 ∈ A N2,N1 and S(M 1 + M 2 ) = S(M 1 ) + S(M 2 ). (iii). If M 1 ∈ A N2,N1 and M 2 ∈ A N3,N2 , then M 2 M 1 ∈ A N3,N1 and
S(M 2 M 1 ) = S(M 2 )S(M 1 ).
2 Appendices with number of the form SMx can be found in the supplementary materials.

This manuscript is for review purposes only.

(iv). A N1,N1 is a ring when equipped with the standard matrix addition and product.

(v). If

1 √ 2 u k u k , 1 √ 2 t k -t k 1⩽k⩽K 1 √ 2 v k v k , 1 √ 2 w k -w k 1⩽k⩽K .
(ix). If A and B are two matrices having the same dimensions, 2N1) . Assume that either f operates elementwise or it is a spectral function in the sense that there exists a function φ : R + → R + such that (xii). The projection onto the spectral ball of center 0 and radius ρ ∈ ]0, +∞[ of an ABBA matrix is an ABBA matrix.

(3.5) rank A B B A = rank(A + B) + rank(A -B). (x). Let f be a function from R (2N2)×(2N1) to R (2N2)×(
(3.6) (∀M ∈ R (2N2)×(2N1) ) f (M ) = 2K k=1 φ( λk )ũ k ṽ⊤ k where K = min{N
The proofs of these properties are provided in Appendix SM2.

3.3. Extension to feedforward networks. We will now extend the previous algebraic concepts by introducing the class of ABBA feedforward neural networks. In the following, the structure of an ABBA fully-connected network will be presented from the perspective of investigating its links with standard networks. Such networks make use of weights that respect the structure of ABBA matrices, except for the first and the last layers. More precisely, the first layer maps the input to a twice-higher dimensional space, while the last layer performs a dimension reduction by a factor of 2. 2Nm) , b m+1 ∈ R Nm , and

Definition 3.4. Let m ∈ N \ {0}. T is an m-layer ABBA network if (3.7) T = ( W m+1 • + b m+1 ) T m • • • T 1 W 0 with W 0 ∈ R (2N0)×N0 , W m+1 ∈ R Nm×(
(∀i ∈ {1, . . . , m}) T i = R i ( W i • + b i ) (3.8) R i : R 2Ni → R 2Ni , (3.9) b i ∈ R 2Ni , (3.10) W i ∈ A Ni,Ni-1 , (3.11)
for given positive integers (N i ) 0⩽i⩽m . T is an m-layer non-negative ABBA network if it is an m-layer ABBA network as defined above and, for every i ∈ {1, . . . , m}, the elements of W i are non-negative.

In the remainder of this paper, N m,A will designate the class of m-layer ABBA networks and N + m,A will designate the subclass of m-layer non-negative ABBA networks. This latter subclass will be the main topic of investigation in this work. We will also use the notation N + m,A (ρ) to designate the set of neural networks in N + m,A where all the activation operators operate componentwise using the same function ρ : R → R.

3.4. Link with standard neural networks. In this section, we show that we can reshape Model 3.1 as a special case of a non-negative ABBA network. At each layer i ∈ {1, . . . , m} of this model, let

W + i = (W + i,k,ℓ ) 1⩽k⩽Ni,1⩽ℓ⩽Ni-1 ∈ [0, +∞[ Ni×Ni-1 be the positive part of matrix W i = (W i,k,ℓ ) 1⩽k⩽Ni,1⩽ℓ⩽Ni -1 , i.e.
(3.12)

(∀k ∈ {1, . . . , N i })(∀ℓ ∈ {1, . . . , N i-1 }) W + i,k,ℓ = W i,k,ℓ if W i,k,ℓ > 0 0 otherwise. Let W - i = W + i -W i ∈ [0, +∞[ Ni×Ni-
W 0 = I N0 -I N0 , W m+1 = 1 2 [I Nm -I Nm ],
and

(∀i ∈ {1, . . . , m}) R i : x z → R i (x) R i (z) , (3.14)
W i = W + i W - i W - i W + i . (3.15)
Note that a weight parametrization similar to (3.15) was used in [START_REF] Wei | Certified robustness for deep equilibrium models via interval bound propagation[END_REF] for computing lower and upper bounds on the output of a deep equilibrium layer, but in this article W - i has negative values.

As we will show next, the main result is that, if the activation functions are symmetric, network T defined above is identical to network T in terms of input-output relation, for judicious choices of the biases of T .

This manuscript is for review purposes only.

(∀i ∈ {1, . . . , m}) b i = b i -W - i d i-1 c i -b i -W + i d i-1 , (3.16) b m+1 = - d m 2 , (3.17)
with d 0 = 0. Then, for every input, T delivers the same output as T .

The proof of this proposition is provided in Appendix A. An illustration of the link between fully-connected layers and ABBA matrices is shown in Figure 1.

Expressivity of non-negative ABBA networks. One of the main advantages of non-negative

ABBA networks with respect to standard networks with non-negative weights is that they are universal approximators. More specifically, we have the following result.

(i). Let ρ : R → R be a symmetric non polynomial activation function. There exists a network

T ∈ N + 1,A (ρ) with N 0 = n e inputs and N 2 = n r outputs such that (3.18) (∀x ∈ K) ∥ T (x) -f (x)∥ < ϵ.
This manuscript is for review purposes only.

(ii). Let ρ : R → R be a symmetric continuous activation function that is continuously differentiable around at least one point where its derivative is nonzero. Then there exists m ⩾ 3 and

T ∈ N + m,A (ρ)
with N 0 = n e inputs, N m+1 = n r outputs, and 2N i = 2(n e + n r + 2) neurons in every layer i ∈ {1, . . . , m} such that (3.18) holds.

Proof. Proposition 3.6 shows that non-negative ABBA networks can be as expressive as signed networks. Combining this fact with existing universal approximation results for signed networks (see [START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF] for (i) and [START_REF] Kidger | Universal approximation with deep narrow networks[END_REF] for (ii)) allows us to deduce these results.

(i) addresses the case of shallow wide networks where the number of neurons in the hidden layer can be arbitrarily large, while (ii) corresponds to the case of deep networks having a limited number of neurons per layer. An illustration of these results is provided in Appendix SM7.

3.6. Lipschitz bounds for ABBA fully-connected networks. As mentioned in the previous sections, the robustness of neural networks with respect to adversarial perturbations can be evaluated through their Lipschitz constant. However, most of the existing techniques for computing a tight estimate of the constant have a high computational complexity for deep or wide networks, whereas simpler upper bounds may turn out to be over-pessimistic.

Nevertheless, in the context of non-negative weighted neural networks [START_REF] Combettes | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF] proved that tight approximations to the Lipschitz constant can be achieved. In the following, we extend this result and show that we can derive a simple expression for the Lipschitz constant, using a separable bound, for non-negative ABBA networks.

Proposition 3.8. Let m ∈ N \ {0} and let T ∈ N + m,A be given by (3.7)- (3.11). Assume that, for every

i ∈ {1, . . . , m -1}, R i is a nonexpansive operator operating componentwise. A Lipschitz constant of T is (3.19) θ m = ∥ W m+1 ∥ ∥S( W m ) • • • S( W 1 )∥ ∥ W 0 ∥.
The proof of this result is detailed in Appendix B. Note that this bound expression could be easily extended to other norms based on the results in [START_REF] Combettes | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF].

A standard separable upper bound for the Lipschitz constant [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] for the ABBA network T considered in the previous proposition is

(3.20) θ m = ∥ W m+1 ∥ ∥ W m ∥ • • • ∥ W 1 ∥ ∥ W 0 ∥.
According to Proposition 3.3(vii), this bound reads also

(3.21) θ m = ∥ W m+1 ∥ ∥S( W m )∥ • • • ∥S( W 1 )∥ ∥ W 0 ∥,
which, by simple norm inequalities, is looser than θ m .

If T is the feedforward network defined in Model 3.1 and we apply Proposition 3.8 to the associated non-negative ABBA network T of Definition 3.5. We have

(3.22) ∥ W 0 ∥ = ∥ W ⊤ 0 W 0 ∥ 1/2 = ∥2 I N0 ∥ 1/2 = √ 2 and (3.23) ∥ W m+1 ∥ = ∥ W m+1 W ⊤ m+1 ∥ 1/2 = 1 √ 2 .
This manuscript is for review purposes only.

In turn, for every i ∈ {1, . . . , m},

(3.24) S( W i ) = W + i + W - i = |W i |.
where It then follows from Proposition 3.6 that θ m is also a Lipschitz constant of T when using symmetric activation functions. Note that this bound was actually already derived in [10, Proposition 5.12].

|W
4. Convolutional networks. We will now extend the results presented in Section 3 to convolutional layers.

4.1. ABBA convolutional layers. For any i ∈ {1, . . . , m}, W i is a convolutional layer with

ζ i-1 ∈ N\{0} input channels, ζ i output channels, kernels (w i,q,p ) 1⩽p⩽ζi-1,1⩽q⩽ζi
, and stride s i ∈ N\{0}.

The output (y q ) 1⩽q⩽ζi of this layer (prior applying any activation operation) is linked to its input

(x p ) 1⩽p⩽ζi-1 by (∀q ∈ {1, . . . , ζ i }) u q = ζi-1 p=1
w i,q,p * x p (4.1)

y q = (u q ) ↓s i .

Hereabove, for every

p ∈ {1, . . . , ζ i-1 }, x p = x p (n) n∈Z d designates a d-dimensional discrete signal.
Dimension d = 1 corresponds to 1D signals and d = 2 to images. A similar notation is used for other signals, in particular u q and w i,q,p with q ∈ {1, . . . , ζ i }. The d-dimensional discrete convolution is denoted by * and (•) ↓ si is the decimation (or subsampling) by a factor s i . The ABBA convolutional layer W i associated with W i has twice the number of input channels and twice the number of output ones. More specifically, its input consists of

ζ i-1 signals ( x + p ) 1⩽p⩽ζi-1 and ζ i-1 signals ( x - p ) 1⩽p⩽ζi-1 .
Similarly, its output consists of ζ i signals ( y + q ) 1⩽q⩽ζi and ζ i signals

( y - q ) 1⩽q⩽ζi .
To make the input-output relations more explicit, let us define the kernels w + i,q,p and w - i,q,p analogously to the fully connected case:

(∀n ∈ Z d ) w + i,q,p (n) = w i,p,q (n) if w i,p,q (n) > 0 0 otherwise, w - i,q,p (n) = w + i,q,p (n) -w i,p,q (n). (4.2)
Then the outputs of the ABBA layer are linked to its inputs by the following relations

(∀q ∈ {1, . . . , ζ i }) u + q = ζi-1 p=1 w + i,q,p * x + p + ζi-1 p=1 w - i,q,p * x - p u - q = ζi-1 p=1 w - i,q,p * x + p + ζi-1 p=1 w + i,q,p * x - p (4.3) y + q = ( u + q ) ↓s i y - q = ( u - q ) ↓s i .
This manuscript is for review purposes only.

The above equations provide the general form of a convolutional ABBA layer when relaxing (4.2).

An alternative formulation of convolutional layers in a matrix form, along with its correspondent d-dimensional spectral representation, is possible (see Appendix SM3). This basically amounts to characterize layer (4.1) by the following matrices

(4.4) (∀n ∈ Z d ) W i (n) =    w i,1,1 (n) . . . w i,1,ζi-1 (n) . . . . . . w i,ζi,1 (n) . . . w i,ζi,ci-1 (n)    ∈ R ζi×ζi-1 ,
defining the so-called MIMO impulse response of W i , which plays a prominent role in dynamical system theory [START_REF] Vaidyanathan | Multirate Systems and Filter Banks[END_REF]. The MIMO impulse response of the ABBA layer W i is then characterized by ABBA matrices:

(4.5) (∀n ∈ Z d ) W i (n) = W + i (n) W - i (n) W - i (n) W + i (n) ∈ [0, +∞[ (2ζi)×(2ζi-1) ,
where

W + i (n) = (w + i,q,p (n)) 1⩽q⩽ζi,1⩽p⩽ζi-1 ∈ [0, +∞[ ζi×ζi-1
and

W - i (n) = (w - i,q,p (n)) 1⩽q⩽ζi,1⩽p⩽ζi-1 ∈ [0, +∞[ ζi×ζi-1 .
This alternative view will be useful in the following sections.

4.2. Lipschitz bounds for convolutional networks. In this section, we establish bounds on the Lipschitz constant of an m-layer convolutional neural network T . Each linear operator W i corresponding to layer i ∈ {1, . . . , m} will be defined by (4.1). We also define a variable (4.6)

σ i = i l=1 s l
aggregating strides from layer 1 to layer i. Subsequently, we will assume that, for every i ∈ {1, . . . , m}, the activation operators (R i ) 1⩽i⩽m are nonexpansive operators. Moreover, these operators are applied componentwise (see Appendix SM1). This means that, for every i ∈ {1, . . . , m -1}, there exists a

function ρ i from R to R such that (∀x ∈ H i ) y = R i (x) ⇔ (∀p ∈ {1, . . . , c i })(∀n ∈ Z d ) y p (n) = ρ i x p (n) . (4.7)
In Appendix SM4, we derive frequency-based expressions allowing us to calculate bounds on the Lipschitz constant of T . For accurate numerical evaluations, the frequency transform in these expressions has to be replaced by a Discrete Fourier Transform involving a significant number of frequency bins (e.g., 128 d ). Due to this fact, a computation bottleneck occurs when MIMO filters are characterized by a large number of input/output channels (e.g., for 2D applications). In the following, we provide an alternative lower-complexity formulation for computing bounds of the Lipschitz constant. In the case of non-negative kernels, we show that this bound is tight.

(4.8) W = (W m ) ↑σm-1 * • • • * (W 2 ) ↑σ1 * W 1
This manuscript is for review purposes only.

where (W i ) 1⩽i⩽m are the MIMO impulse responses of each layer of network T and, for every i ∈ {2, . . . , m}, (W i ) ↑σi-1 is the interpolated sequence by a factor σ i-1 of W i (see (SM3.9)). For every j ∈ S(σ m ) = {0, . . . , σ m -1} d , we define the following matrix:

(4.9) W (j) = n∈Z d W (σ m n + j) ∈ [0, +∞[ ζm×ζ0 .
Then (4.10)

θ m = j∈S(σm) W (j) W (j) ⊤ 1/2
is a lower bound on the Lipschitz constant estimate of network T . In addition, if for every i ∈ {1, . . . , m}, p ∈ {1, . . . , ζ i-1 }, and q ∈ {1, . . . , ζ i }, w i,q,p = (w i,q,p (n)) n∈Z d is a non-negative kernel, then θ m is a

Lipschitz constant of T .

The proof of Theorem 4.1 is given in Appendix C.

The constant θ m in (D.4) is actually equal to the one calculated in Appendix SM4. The following majorization if thus obtained (see (SM4.4)):

(4.11) θ m ⩽ θ m = ∥W m ∥ • • • ∥W 1 ∥.
By applying Theorem 4.1 to each individual layer (W i ) 1⩽i⩽m assumed to be with non-negative kernels, we get the following expression for the upper-bound:

(4.12) θ m = m i=1 j∈S(si) W (j) i W (j) i ⊤ 1/2
, where (4.13) (∀i ∈ {1, . . . , m})(∀j ∈ S(s i ))

W (j) i = n∈Z d W i (s i n + j).
The bound θ m is generally more tractable than θ m since it separates the influence of each layer and does not require to compute the global matrix sequence W as expressed by (4.8). However, such separable bounds are usually loose. According to our observations, it turns out that, in the special case of convolutional layers with non-negative kernels, θ m and θ m are quite close (see numerical tests in Appendix SM5).

To illustrate these results, the computation of the Lipschitz bound of a layer corresponding to an average pooling is presented as an example in Appendix SM6. non-negative kernels. More precisely, we assume that, for every i ∈ {1, . . . , m}, the i-th layer of the ABBA network has 2ζ i-1 input channels, 2ζ i output channels, and stride s i ∈ N \ {0}. The MIMO impulse response of such a layer is of the form (4.5). We make the same assumptions of nonexpansiveness and separability for the activation operators as in the previous section. We recall that (W ) ↑σ denotes the interpolated version by a factor σ of a MIMO impulse response

W = W (n) n∈Z d .
The following result is then established in Appendix D :

This manuscript is for review purposes only.

Theorem 4.2. Under the above assumptions on the convolutional ABBA network T , let

(4.14) (∀i ∈ {1, . . . , m})(∀j ∈ S(s i )) Ω (j) i = n∈Z d S( W i (s i n + j)) ∈ [0, +∞[ ζi×ζi-1 ,
where ( W i (n)) n∈Z is the MIMO impulse response of the ABBA layer of index i. Then a Lipschitz constant of T is

(4.15) θ m = ∥ W m+1 ∥ m i=1 j∈S(si) Ω (j) i Ω (j) i ⊤ 1/2 ∥ W 0 ∥,
where ∥ W m+1 ∥ (resp. ∥ W 0 ∥) is the spectral norm of the linear operator employed in the last (resp. first layer).

The bound (4.15) will be subsequently used to control the Lipschitz constant of non-negative ABBA networks during their training.

Lipschitz-constrained training.

The theoretical bounds established in the previous sections provide a relatively easy way of computing a tight estimate of the global Lipschitz constant. We propose a simple approach to control it during the training phase. Since our networks contain mostly layers having non-negative weights and a few layers having arbitrary-signed weights, their Lipschitz constant will be controlled separately and different constraint sets will be handled for each case.

To train a robust ABBA network, we employ a projected version of the well-known ADAM optimizer. Each layer i is parameterized by a vector Ψ i . In the case of a dense layer, Ψ i is a vector gathering the elements of weight matrix W i , the components of the associated bias b i , and a possible additional parameter that will be introduced hereafter. For an ABBA layer, Ψ i is thus a vector of

dimension 2N i (N i-1 + 1) or 2N i (N i-1 + 1) + 1.
In the context of a 2D convolutional layer, an array w i of scalar convolutional kernels is substituted for the weight matrix. In the ABBA case, we have to minimize a loss function ℓ are presented in Algorithm 5.1. After each iteration t of the optimizer, we perform a projection proj Si,t onto a constraint set S i,t The definition of this set and the corresponding method for managing the projection is detailed in the following, according to the network type.

Handling Lipschitz constants for fully-connected layers. Consider the network defined by Model (3.5). In the case of fully connected networks, the Lipschitz constant is given by Proposition 3.8, which basically splits the bound into three terms: the first and the last account for the starting and ending layers, respectively, while the middle one encompasses all the ABBA layers. For the two former arbitrary-signed layers, we control the Lipschitz constants individually during training, by imposing a bound on each weight matrix spectral norm. This defines the following two constraints:

(5.1)

(∀i ∈ {0, m + 1}) ∥ W i ∥ ⩽ θ m,i ,
where θ m,i is the imposed Lipschitz bound for the i-th layer. To deal with this constraint, we decompose the weight matrix as W i = θ m,i W ′ i , which yields the constraint set (5.2)

(∀i ∈ {0, m + 1}) S i,t = { W ′ i | ∥ W ′ i ∥ ⩽ 1}.
This manuscript is for review purposes only.

The projection onto S i,t is performed by clipping the singular values of W ′ i to 1.

In our proposed training procedure, we set θ m,0 θ m,m+1 = 1. This gives the network one degree of freedom to automatically adapt the value of the Lipschiz constant of these two layers. To do so, we adopt the following parametrization

(5.3) θ m,0 = exp(α), θ m,m+1 = exp(-α),
where α ∈ R is a trainable parameter. It constitutes an extra component of the vector Ψ i when i ∈ {0, m + 1}.

In the case of ABBA dense layers, we need to handle two requirements: ensure that, for every i ∈ {1, . . . , m}, W i is a non-negative ABBA matrix, and to constrain the product of all the weight matrices to be such that

∥ W m • • • W 1 ∥ ⩽ θ m . Since θ m,0 θ m,m+1 = 1, θ m corresponds to the target
Lipschitz bound for the ABBA network.

For every i ∈ {1, . . . , m}, W i is parameterized by W + i and W - i . We define the following two constraint sets:

D i = {(W + i , W - i ) ∈ (R Ni×Ni-1 ) 2 | W + i ⩾ 0 and W - i ⩾ 0}, (5.4) C i,t = (W + i , W - i ) ∈ (R Ni×Ni-1 ) 2 | A i,t W + i W - i W - i W + i B i,t ⩽ θ m . (5.5)
Here-above, matrix A i,t (resp. B i,t ) is an ABBA matrix, which is the product of the weight matrices for the posterior (resp. previous layers). In this case, S i,t = D i ∩ C i,t . To perform the projection onto the intersection of these two sets, we use an instance of the proximal algorithm presented in [START_REF] Neacs | EMG-based automatic gesture recognition using robust neural networks[END_REF], which alternates between elementary projections onto D i and projections onto the spectral ball with center 0 and radius θ m . Because of Proposition 3.3(xii), the latter projection allows us to keep the structure of ABBA matrices.

Handling Lipschitz constants for convolutional layers. In the case of convolutional ABBA networks, we derived the bound in (4.15) which consists of the product of m + 2 terms. The Lipschitz bound constraint is managed by introducing auxiliary variables (θ m,i ) 0⩽i⩽m+1 defining upper bounds for each layer. At iteration t of the algorithm estimates (θ m,i,t ) 0⩽i⩽m+1 of the auxiliary bounds are updated. Similarly to the fully connected case, we use two different types of constraints.

For the i-th ABBA convolutional layer with i ∈ {1, . . . , m}, we consider the constraint set (5.6)

C i,t = {W i | j∈S(si) Ω (j) i Ω (j) i ⊤ ⩽ θ 2 m,i,t }
where matrices (Ω (j) i ) j∈S(si) are linked to the convolution kernels by the linear relation (4.14). By concatenating all these s d i matrices horizontally, we obtain a rectangular matrix Ω i which allows us to reexpress (5.6) in the simpler form:

(5.7)

C i,t = {W i | ∥Ω i ∥ ⩽ θ m,i,t }.
We also have to impose the non-negativity of the filters alongside the stability bound. This corresponds to a constraint set D i . Projecting onto S i,t = C i,t ∩D i is performed by using the same iterative proximal algorithm as previously.

This manuscript is for review purposes only.

For the first and the last layers, we impose similarly that ∥W i ∥ ⩽ θ m,i,t with i ∈ {0, m + 1}. Since the kernels are signed, we resort a frequency formulation (see (SM4.18)) to estimate the spectral norm of the convolutional operator. The procedure we use is described in Appendix SM8.

Convolutional layers are usually succeeded by an ABBA fully connected network. This part will be handled as explained previously. However, we need to set the upper bounds (θ m,i,t ) 0⩽i⩽m+1 used in the convolutional part and the upper bound of the ABBA fully connected part. With a slight abuse of notation, let us denote this latter bound by θ m,m+2,t , while the target Lipschitz constant for the global network is still denoted by θ m . We have to deal with the following constraint:

(5.8)

m+2 i=0 θ m,i,t = θ m .
We proceed by computing the Lipschitz constants ( θ m,i,t ) 0⩽i⩽m+2 of the layers after the ADAM update.

Then, we set

(∀i ∈ {0, . . . , m + 2}) θ m,i,t = θ m,i,t θ m m+2 i ′ =0 θ m,i ′ ,t 1 m+3
, (5.9) which guarantees that (5.8) holds. Update (5.9) can be interpreted as the orthogonal projection onto the constraint set defined by (5.8) after a logarithmic transform of the auxiliary variables. The benefit of such a transform is to convexify the constraint.

Algorithm 5.1 Projected ADAM Algorithm

Ψ i,t -weights of layer i at iteration t (z k ) 1⩽k⩽K -set of input image-label pairs β 1 , β 2 -ADAM hyperparameters Partition {1, . . . , K} into mini-batches (M q,n ) 1⩽q⩽Q t = (n -1)Q + q # sweep mini-batches for q ∈ {1, . . . , Q} do for layer i do This manuscript is for review purposes only. (i). First, we compare positive ABBA structures with their classic non-negative counterparts and check that our method yields significantly better results in all considered cases.

g i,t = k∈Mq,n ∇ i ℓ z k , (Ψ i,t 1⩽i⩽m ) µ i,t = β 1 µ i,t-1 + (1 -β 1 )g i,t ν i,t = β 2 ν i,t-1 + (1 -β 2 )g 2 i,t γ t = γ 1 -β t 2 /(1 -β t 1 ) Ψ i,t = Ψ i,t -γ t µ i,
(ii). We then train ABBA models constrained to different Lipschitz bound values and evaluate their robustness against several adversarial attacks.

(iii). Finally, we compare our proposed approach with three other well-established defense strategies, namely Adversarial Training (AT), Trade-off-inspired adversarial defense (TRADES) [START_REF] Zhang | Theoretically principled trade-off between robustness and accuracy[END_REF],

Deel-Lip proposed by [START_REF] Serrurier | Achieving robustness in classification using optimal transport with hinge regularization[END_REF], and orthonormalization [START_REF] Anil | Sorting out Lipschitz function approximation[END_REF].

We validate our ABBA networks on four benchmark image classification datasets: MNIST, its more complex variant Fashion MNIST4 , a variant5 of the Rock-Paper-Scissors (RPS) dataset [START_REF] Moroney | Rock, paper, scissors dataset[END_REF], and a binary classification on CelebA [START_REF] Liu | Deep learning face attributes in the wild[END_REF]. For the last dataset, inspired from [START_REF] Serrurier | Achieving robustness in classification using optimal transport with hinge regularization[END_REF] where eyeglass detection is performed, we specialized our models on a different attribute, namely to identify whether a person is bald or not. To explore the features of different ABBA network topologies, we experiment with two main types of ABBA architectures: one having only fully-connected layers, further referred to as ABBA Dense, and another one which includes a convolutional part for feature extraction, followed by a fully connected classification module, ABBA Conv. Depending on the dataset, the particularities of each ABBA networks vs. non-negative networks. First, we compare our non-negative ABBA networks with standard ones trained under non-negativity constraints. We consider standard neural networks having the same number of parameters as their ABBA equivalent. The results are summarized in Table 1, indicating that ABBA neural networks yield far superior results, in all cases. In the case of fully connected architectures, the difference in terms of accuracy is around ∼ 3% and ∼ 5% for MNIST and FMNIST, respectively. The difference is even higher when we consider Conv architectures (e.g.

∼ 5%, ∼ 7%, ∼ 31% and ∼ 32% for MNIST, FMNIST, RPS, and CelebA, respectively). This shows that standard non-negative convolutional kernels are often suboptimal for extracting relevant information from image data. On the other hand, training standard neural networks having arbitrary-signed weights gives results very similar to their ABBA equivalents in all the cases, showing that ABBA networks do not suffer from these shortcomings. These results are in agreement with Proposition 3.6.

Stability vs. Performance. According to the "no free lunch" theorem [START_REF] Tsipras | There is no free lunch in adversarial robustness (but there are unexpected benefits)[END_REF], stability guarantees may impact the system performance on clean data. In this work, we train several models by following the approach described in Section 5. The Lipschitz constant of the network is varied in an effort to find the optimal trade-off between robustness and classification accuracy. This compromise is usually use-case specific, depending on the architecture complexity and on the dataset particularities, so the This manuscript is for review purposes only. tightness of the imposed stability bound must be chosen accordingly. In our experiments, we limited the maximum Lipschitz constant we impose, so that the drop in performance does not exceed 5% of the baseline model accuracy (i.e., the model trained without robustness constraints).

Adversarial attack validation. We train several robust ABBA models by varying the global

Lipschitz bound θ m . We then evaluate their robustness against inputs corrupted with different levels of adversarial perturbations, by studying their influence on the overall performance of the system.

To create the adversarial perturbations, we use three white-box attackers as described next. DDN [START_REF] Rony | Decoupling direction and norm for efficient gradient-based ℓ2 adversarial attacks and defenses[END_REF] is a gradient-based ℓ 2 adversarial attack method that seeks to decouple the direction and norm of the additive perturbation. By doing so, this attack is able to generate effective examples, while requiring fewer iterations than other methods. DeepFool [START_REF] Moosavi-Dezfooli | Deepfool: A simple and accurate method to fool deep neural networks[END_REF] considers a linear approximation to the model and refines the attack sample iteratively, by selecting the point that would cross the decision boundary with minimal effort in the logit space. The FMN [START_REF] Pintor | Fast minimum-norm adversarial attacks through adaptive norm constraints[END_REF] attack improves the approach in DDN by introducing adaptive norm constraints on the perturbation, in order to balance the trade-off between the magnitude of the perturbation and the level of miss-classification. This results in a powerful attack that is able to generate adversarial examples with small perturbation levels.

For a given maximum ℓ 2 perturbation norm, we ran each attack for 300 steps, using the default hyperparameters for each of the three attackers. Although all images are normalized in the [-1, 1] range, we report the robust accuracy w.r.t. ℓ 2 perturbation measured in [0, 1] range, which is the common practice in the literature.

This manuscript is for review purposes only. weights, is provided as a reference. These graphs could be interpreted as the expected performance of the model if the attack is allowed to influence the input image with an ℓ 2 -norm less than ϵ, where the level of perturbation ϵ varies. For a better understanding of the adversarial perturbation effect, some visual examples of the attacked inputs, for all the datasets, are presented in Appendix SM10.

It can be observed that our robust ABBA models are significantly less affected by adversarial inputs than the undefended baseline. This demonstrates that carefully controlling the Lipschitz constant during training improves the network stability against adversarial attacks. Naturally, as the imposed bound gets lower, the system becomes more robust. Although the difference in robustness between similar values of the Lipschitz constant depends on the intrinsic structure of the dataset, our results show that a good trade-off between robustness and performance can be achieved in all cases.

Comparison with other defense strategies. In the following, we compare our method for training robust models using ABBA networks with other defense strategies. Deel-Lip, developed in [START_REF] Serrurier | Achieving robustness in classification using optimal transport with hinge regularization[END_REF], is a popular Lipschitz-based approach, which uses the spectral normalization of each layer to offer robustness certificates during training. We have also made comparisons with another popular technique to ensure 1-Lipschitz weights, via orthonormalization [START_REF] Anil | Sorting out Lipschitz function approximation[END_REF][START_REF] Cisse | Parseval networks: Improving robustness to adversarial examples[END_REF]. For our experiments, we

This manuscript is for review purposes only. trained models from scratch, using the implementation provided by [START_REF] Anil | Sorting out Lipschitz function approximation[END_REF] 6 , in order to enforce an For all experiments regarding AT, we used Projected Gradient Descent (PGD) attack to generate the adversarial samples with a perturbation level ϵ = 0.5 and then employed the scheduling strategy introduced by [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF]. Concerning TRADES, we set λ = 1 for MNIST and FMNIST, and λ = 1/2 for RPS and CelebA datasets. For all the presented techniques we considered the equivalent baseline to each ABBA network.

Comparisons, in the same adversarial set-up as before, are depicted in Figures 5,6, and 7. We observe that using our theoretically certified Lipschitz bound yields models which are generally more robust than AT and TRADES. For simple datasets, such as MNIST and FMNIST, robust ABBA and Deel-lip models exhibit similar behavior for low-magnitude adversarial attacks, but as we increase the maximum perturbation ϵ, our method performs better. In the case of real-world datasets (RPS and 6 https://github.com/cemanil/LNets/tree/master

This manuscript is for review purposes only. CelebA), ABBA models exhibit high robustness properties against all the tested attacks, showing that our approach allows us to train neural models to reach great stability properties, without losing their generalization power.

Limitations. The main limitation of our method is that non-negative ABBA operators require more parameters to meet the universal approximation conditions. More precisely, for given depth m and number of neurons (N i ) 0⩽i⩽m per layer, a network T ∈ N m,A has the same number of inputs and outputs as the standard feedfoward network T in Model 3.1. All the layers of T , except the first one, have however twice more inputs than T . Exact training times are showcased in SM11.

Because of the ABBA structure of the weight matrices in (3.11), the maximum number of parameters

of T is 2(N 2 0 + m i=1 N i (N i-1 + 1) + N 2 m ) while the number of parameters of T is m i=1 N i (N i-1 + 1)
.

By storing W

′ 1 = W 1 W 0 ∈ R (2N1)×N0 instead of W 1 and W 0 separately, the maximum number of parameters is reduced to 2( m i=1 N i (N i-1 + 1) + N 2 m ).
Moreover, since the weights are non-negative, the model does not necessarily require signed representations storage, so the memory space occupied by T could also be reduced.

While our method does not provide any certification regarding the accuracy of the classifier in adversarial environments, it delivers a certified value for the Lipschitz constant of the network.

Conclusions.

In this paper, we introduce ABBA networks, a novel class of neural networks where the majority of weights are non-negative. We demonstrate that these networks are universal approximators, possessing all the expressive properties of conventional signed neural architectures.

This manuscript is for review purposes only.

Additionally, we unveil their remarkable algebraic characteristics, enabling us to derive precise Lipschitz bounds for both fully-connected and convolutive operators. Leveraging these bounds, we construct robust neural networks suitable for various classification tasks.

The main advantage of ABBA networks is that they enjoy all the properties of non-negative networks (e.g., they are easier to interpret and less prone to overfitting), without suffering from the shortcomings of standard ones (e.g., lack of expressivity). Additionally, we showed that ABBA structures allow tight Lipschitz bounds to be estimated, without requiring to solve an NP-hard problem as for conventional neural networks.

For future research, it would be intriguing to explore the application of ABBA networks in regression problems, where controlling the Lipschitz constant may present more challenges. Also, extending our theoretical bounds to different structures, such as recurrent or attention-based networks, holds promise for further advancements. Moreover, it would be interesting to study if using Lipschitzconstrained ABBA neural networks can improve certified robustness strategies like GloRoNets [START_REF] Leino | Globally-robust neural networks[END_REF].

Finally, we recognize the necessity of investigating the scalability of the proposed training method to deep architectures. One of the main hurdles in this endeavor is the increased number of parameters that deep ABBA architectures entail.

According to Proposition 3.

3(iii), W m W m-1 • • • W 2 W 1 ∈ A Nm,N0
. Since this matrix has nonnegative elements, we deduce from Proposition 3.3(vii) that

ϑ m ⩽ ∥ W m+1 ∥ ∥ W m • • • W 1 ∥ ∥ W 0 ∥ = ∥ W m+1 ∥ ∥S( W m • • • W 1 )∥ ∥ W 0 ∥ = ∥ W m+1 ∥ ∥S( W m ) • • • S( W 1 )∥ ∥ W 0 ∥, (B.4)
where the last equality is also a consequence of Proposition 3.3(iii). This leads to the Lipschitz bound in (3.19).

Appendix C. Proof of Theorem 4.1.

Before giving the proof of our main result, we will introduce a link between the Fourier and the spatial representations for a nonnegative convolutional kernel.

(∀n ∈ Z d ) H(n) = h q,p (n) 1⩽q⩽c ′ ,1⩽p⩽c ∈ [0, +∞[ c ′ ×c
where, for every p ∈ {1, . . . , c} and q ∈ {1, . . . , c ′ }, h q,p ∈ ℓ 1 (Z d ) 7 . Then, the Fourier transform H of In addition, the upper bound is attained since (C.7)

H(n) n∈Z d is such that (C.2) sup ν∈[0,1] d ∥ H(ν)∥ = n∈Z d H(n) .
H(0) = n∈Z d H(n).
Next, we derive the proof for Theorem 4.1 in light of Lemma C.1.

Proof. W being the impulse response of the MIMO filter with the frequency response given by (SM4.1), it follows from Noble identities [START_REF] Vaidyanathan | Multirate Systems and Filter Banks[END_REF] that W is equivalent to a convolution with W followed by a decimation by a factor σ m . Let H(n) =[W (0,0) (n), . . . , W (σm-1,0) (n), . . . , W (0,σm-1) (n), . . . , W (σm-1,σm-1) (n)] (C.12) and (C.13)

(∀n ∈ Z 2 ) e(n) =              
x (0,σm-1) (n) . . .

x (σm-1,σm-1) (n) . . .

x (σm-1,σm-1) (n) . . .

x (σm-1,σm-1) (n)               .
This manuscript is for review purposes only. On the other hand, by using (C.9), This manuscript is for review purposes only. On the other hand, for every n ∈ Z d , W i (n) is an ABBA matrix. Since W (n) is obtained by multiplication and addition of such matrices, it follows from Proposition 3.3(ii) and (iii) that it is also an ABBA matrix. We deduce that, for every j ∈ S(σ m ), W (j) is an ABBA matrix and, by using Ω (j) Ω (j) ⊤ 1/2 ∥ W 0 ∥, Similarly to the derivation of (4.12), we deduce that θ m ⩽ θ m where θ m is given by (4.15).

n∈Z d H(n) = n∈Z d H(n) n∈Z d H(n)

Figure 1 :

 1 Figure 1: Equivalence between a standard fully-connected layer and its ABBA correspondent.

Proposition 3 . 7 .

 37 Let (n e , n r ) ∈ (N \ {0})2 . Let f : R ne → R nr be a continuous function. Let K be any nonempty compact subset of R ne and let ϵ ∈ ]0, +∞[.

Theorem 4 . 1 .

 41 Let (σ i ) 1⩽i⩽m be the aggregated stride factors of network T , as defined by (4.6), and let

4. 3 .

 3 Bounds for ABBA convolutional networks. Let us extend the previous results to the ABBA context. The linear operators of the considered ABBA network T are denoted by ( W i ) 0⩽i⩽m+1 . The weights in W 0 and W m+1 are signed, whereas ( W i ) 1⩽i⩽m are convolutional layers with d-dimensional

2ζ i ζ i- 1

 1 such kernels. To ensure nonnegativity (if needed) and Lipschitz bound conditions on the weight operator, we project Ψ i onto a suitable closed and convex constraint set. Considering pairs (z k ) 1⩽k⩽K of inputs images and their associated labels, the operations performed at each epoch n > 0

Figure 2 :

 2 Figure 2: Accuracy vs. Perturbation for different Lipschitz constants -Dense Architecture.

Figure 3 :

 3 Figure 3: Acc. vs. Perturbation for different Lipschitz constants ABBA Conv Architectures -MNIST and FMNIST.

Figure 4 :

 4 Figure 4: Acc. vs. Perturbation for different Lipschitz constants ABBA Conv Architectures -RPS and CelebA.

Figure 5 :

 5 Figure 5: Comparisons with other defense techniques Dense Architectures

Figure 6 :

 6 Figure 6: Comparisons with other defense techniques Conv Architectures -MNIST and FMNIST.

l 2 -

 2 norm equal to 1 using Bjorck Orthonormalization, while also preserving the gradient norm through GroupSort. TRADES[START_REF] Zhang | Theoretically principled trade-off between robustness and accuracy[END_REF] introduces a robustness regularization term into the training objective.This regularizer encourages the network to have similar predictions on both the original input and its adversarial counterparts. On the other hand, Adversarial Training (AT) implies augmenting the training data with adversarial samples, increasing the network generalization capabilities to different input alterations. However, this technique offers weak theoretical stability guarantees, as it is mainly dependent on the strength of the adversary used during training.

  (a) RPS -DDN attack (b) RPS -FMN attack (c) RPS -DeepFool attack (d) CelebA -DDN attack (e) CelebA -FMN attack (f) CelebA -DeepFool attack

Figure 7 :

 7 Figure 7: Comparisons with other defense techniques Conv Architectures -RPS and CelebA.

Lemma C. 1 .

 1 Let (c, c ′ ) ∈ (N \ {0}) 2 and let (C.1)

Proof. 1 (

 1 For every ν ∈ [0, 1] d , (C.3) H(ν) = n∈Z d H(n) exp -ı2ππn ⊤ ν .For every u = [u 1 , . . . , u c ] ⊤ ∈ C c , by using the triangle inequality,h q,p (n) exp -ı2πn ⊤ ν u p Z d ) is the space of summable d-dimensional sequencesThis manuscript is for review purposes only.where |u| denotes the vector of moduli of the components of vector u. This shows that (

  x ∈ H 0 . Let the σ m -polyphase representation of x (resp. W ) be defined as∀j ∈ S(σ m ) (∀n ∈ Z d ) x (j) (n) = x(σ m nj) (C.8) resp. W (j) (n) = W (σ m n + j) . (C.9)Then, as a result of multirate digital filtering, y = Wx if and only if(C.10) y = j∈S(σm) W (j) * x (j) .This sum of MIMO convolutions can be reformulated as a single one(C.11) y = H * e,where H is the c m × σ d m c 0 MIMO impulse response obtained by stacking rowwise the polyphase MIMO impulse responses (W (j) ) j∈S(σm) and e is the σ d m c 0 -component d-dimensional signal obtained by stacking columnwise the polyphase signal components (x (j) ) j∈S(σm) . For example, if d = 2, we have(∀n ∈ Z 2 )

2 =

 2 ∥x∥ 2 . (C.14) This equality and (C.11) imply that (C.15) ∥W∥ = sup ν∈[0,1] d ∥ H(ν)∥. We thus deduce from Lemma C.1 that (C.16) ∥W∥ = n∈Z d H(n) .

  Appendix D. Proof of Theorem 4.2. This result is a consequence of Theorem 4.1, which provides a Lipschitz bound for nonnegative convolutional neural networks. By following a similar reasoning to Appendix B, a Lipschitz constant of the ABBA network is (D.1)θ m = ∥ W m+1 ∥∥ W m • . . . • W 1 ∥∥∥ W 0 ∥. Let (D.2) W = ( W m ) ↑σm-1 * • • • * ( W 2 ) ↑σ1 * W 1 and let (D.3) (∀j ∈ S(σ m )) Ω (j) = n∈Z d S W (σ m n + j) ∈ [0, +∞[ ζm×ζ0 .

2 ∥W

 2 Since ( W i ) 1⩽i⩽m are convolutional operators with nonnegative kernels, it follows from Theorem 4W 0 ∥.where, for every j ∈ S(σ m ), (σ m n + j) ∈ [0, +∞[ (2ζm)×(2ζ0) .

Proposition 3 .Ω

 3 3(i), W (j) W (j) ⊤ is ABBA. By invoking now Proposition 3.3(i)-(iii) and (vii), we deduce that j∈S(σm)W (j) W (j) ⊤ = S j∈S(σm) (j) Ω (j) ⊤ . (D.6)This shows that a Lipschitz constant of the ABBA network T is (D.7) θ m = ∥ W m+1 ∥ j∈S(σm)

  A and B are two square matrices of the same size, the eigenvalues of Let A ∈ R N2×N1 and B ∈ R N2×N1 , and letK = min{N 1 , N 2 }. Let (λ k ) 1⩽k⩽K (resp. (µ k ) 1⩽k⩽K ) be the singular values of A + B (resp. A -B) and let {u k } 1⩽k⩽K / {v k } 1⩽k⩽K (resp {t k } 1⩽k⩽K/ {w k } 1⩽k⩽K ) be associated orthonormal families of left/right singular vectors in R N2 / R N1 .3

			A B B A	are those of
	A + B and A -B.
	(vi). If A and B are two matrices having the same dimensions, the spectral norm of	A B B A	is equal
	to max{∥A + B∥, ∥A -B∥}.
	(vii). If M ∈ A N2,N1 has non-negative elements, the spectral norm of M is ∥S(M )∥.
	(viii). Then, the singular values of	A B B A	are (λ k , µ k ) 1⩽k⩽K and associated orthonormal families of
	left/right singular vectors are

  1 , N 2 }, ( λk ) 1⩽k⩽2K are the singular values of M , and {ũ k } 1⩽k⩽2K /

	{ṽ k } 1⩽k⩽2K are associated orthonormal families of left / right singular vectors in R 2N2 /
	R 2N1 . Then f maps any matrix in A N2,N1 to a matrix in A N2,N1 .
	(xi). The best approximation of maximum rank R < min{N 1 , N 2 } (in the sense of the Frobenius
	norm) to a matrix in A N2,N1 belongs to A N2,N1 .

  i | is the matrix whose elements are the absolute values of W i . Hence the Lipschitz constant

	of T in (3.19) reduces to
	(3.25)

θ m = ∥|W m | . . . |W 1 |∥.

This means that (SM2.11) and (SM2.12) hold.This manuscript is for review purposes only.

https://github.com/zalandoresearch/fashion-mnist

https://github.com/DrGFreeman/rps-cv This manuscript is for review purposes only.

This manuscript is for review purposes only.

Acknowledgments. We would like to thank Dr. Jérôme Rony and Prof. Ismail Ben Ayed from ETS Montréal for fruitful discussions and insightful suggestions.

This manuscript is for review purposes only.

supported by the French ANR Research and Teaching Chair in Artificial Intelligence

Appendix A. Proof of Proposition 3.6. For every i ∈ {1, . . . , m}, let x i = T i (x i-1 ) where

x 0 ∈ R N0 is an arbitrary input of network T and x m ∈ R Nm its corresponding output. By using the symmetry properties of the activation operators, for every i ∈ {1, . . . , m}, we have

By making use of notation (3.14), (A.1) and (A.2) can be rewritten more concisely as

Let us define, for every i ∈ {0, . . . , m}, (A.4)

Altogether (3.16), (3.11), (3.15), and (A.3) yield

. . .

where, for every i ∈ {1, . . . , m}, D 2Ni {-1,1} designates the space of diagonal matrices of size

with diagonal entries equal to -1 or 1. For every

On the other hand, for every i ∈ {1, . . . , m}, W i ∈ [0, +∞[ (2Ni)×(2Ni-1) . It then follows from [ . . .

Λm-1∈D

2N m-1

This manuscript is for review purposes only.