Mathematics Computer Science
Computer Science-2021.gz:143417
Computer Science
19cd5d12f18b59f3633a54389c5f8631b2ace01a
A Law of Robustness for Weight-bounded Neural Networks

Robustness of deep neural networks against adversarial perturbations is a pressing concern motivated by recent findings showing the pervasive nature of such vulnerabilities. One method of characterizing the robustness of a neural network model is through its Lipschitz constant, which forms a robustness certificate. A natural question to ask is, for a fixed model class (such as neural networks) and a dataset of size $n$, what is the smallest achievable Lipschitz constant among all models that fit the dataset? Recently, (Bubeck et al., 2020) conjectured that when using two-layer networks with $k$ neurons to fit a generic dataset, the smallest Lipschitz constant is $\Omega(\sqrt{\frac{n}{k}})$. This implies that one would require one neuron per data point to robustly fit the data. In this work we derive a lower bound on the Lipschitz constant for any arbitrary model class with bounded Rademacher complexity. Our result coincides with that conjectured in (Bubeck et al., 2020) for two-layer networks under the assumption of bounded weights. However, due to our result's generality, we also derive bounds for multi-layer neural networks, discovering that one requires $\log n$ constant-sized layers to robustly fit the data. Thus, our work establishes a law of robustness for weight bounded neural networks and provides formal evidence on the necessity of over-parametrization in deep learning.


Introduction
Robustness against perturbations is a natural concern that has received increasing attention, given recent findings that deep neural networks can be easily manipulated by adversaries (Szegedy et al., 2014;Biggio et al., 2013). In a supervised learning setting with inputs X ⊆ R d and outputs (labels) Y, a natural setup for understanding the robustness of a hypothesis h : X → Y around some input x ∈ X is through the maximum size of perturbations δ ∈ X such that h(x + δ) = h(x). Intuitively, this measures some form of tolerance guaranteeing the hypothesis does not change its predictions under small perturbations. This is intimately related to the Lipschitz constant of h, which precisely characterises this behaviour across all inputs, and is recollected as a certificate of robustness.
A natural question to ask in this context is: for a given hypothesis class F and dataset, what is the lowest Lipschitz constant among all models from F that fit the data? A non-trivial answer to this question establishes some price one must pay to achieve robustness when using the model class F . This price will depend on the structure of F , e.g. in the case of neural networks it might depend on the depth and width of the network. In particular, Bubeck et al. (2020) recently conjectured that for 2-layer neural networks, the Lipschitz constant of any network fitting a generic dataset of size n is proportional to n/k where k is the number of hidden neurons. This implies that if one is interested in fitting the data and having a small O(1) Lipschitz constant, then necessarily k = Ω(n), i.e. the network must have as many neurons as there are data points .
The overarching goal of this line of research is to establish that over-parametrisation, a particularly successful scheme for achieving empirical robustness (Goodfellow et al., 2015;Madry et al., 2018), is in some sense necessary. In addition to formulating their conjecture, (Bubeck et al., 2020) make some progress in this direction by (i) proving an Ω( d/k) lower bound for the Lipschitz constant in the under complete case (d ≤ n), and (ii) establishing a relaxed version of the conjecture where the Lipschitz constant is replaced by a proxy depending on the weights of the network. Note that both the conjecture and partial results focus on the width of two-layer network models, whereas over-parametrisation also depends on the network's number of layers. To the best of our knowledge, no result -proved or conjectured -is available for networks of depth greater than two.
In this paper, we study the robustness problem for any general hypothesis class F and prove a lower bound on the Lipschitz constant of any (nearly) interpolating hypotheses that is inversely proportional to the Rademacher complexity of F . This is particularly interesting given the well-known use of Rademacher complexity as a form of sufficiency in generalisation bounds (Koltchinskii and Panchenko, 2000;Bartlett and Mendelson, 2002), along with the fact that there is an extensive literature deriving Rademacher complexity bounds for different model classes (Neyshabur et al., 2015;Bartlett et al., 2017;Golowich et al., 2018;Wei and Ma, 2019). In particular, a standard application of Rademacher complexity bounds shows that in the setting of two-layer neural networks with bounded weights, our result coincides exactly with what is conjectured in (Bubeck et al., 2020). Due to our result's generality, we can also derive lower bounds for multi-layer neural networks. These derivations specify concretely that the price of robustness decays exponentially when increasing the number of layers, consequently proving that some form of over-parametrisation, either in width or in-depth, is necessary for robustness. In summary, our contributions are: 1. A law of robustness that establishes a trade-off between robustness and model complexity as a necessary condition for any hypothesis class.
2. Derivation for the two-layer neural network case, highlighting the necessity of having as many neurons as data points for O(1) Lipschitz constant and providing a resolution to the conjecture of (Bubeck et al., 2020) in the weight-bounded case.
3. Application of our result to multi-layer neural networks, formally proving that overparametrisation is necessary to achieve an O(1) Lipschitz constant. We provide Bubeck et al. use features sampled uniformly from the unit sphere and labelled uniformly at random as a model of generic data.
In contrast, without robustness constraints, O(n/d) neurons are sufficient to fit generic datasets with two-layer ReLU neural networks (Yun et al., 2019). versions of our results for robustness with respect to L p perturbations for p ∈ {2, ∞}.
Related work. Previous theoretical results have shed light into several aspects that affect the success of adversarially robust learning. This has lead to the identification of different trade-offs involving the computational complexity of robust learning (Bubeck et al., 2019;Degwekar et al., 2019) and the relation between robustness and generalization Raghunathan et al., 2019). From an optimisation point of view, the convergence of methods for adversarial training has been investigated (Gao et al., 2019;Zhang et al., 2020), as well as the behaviour of features learned by adversarially trained neural networks (Ilyas et al., 2019;Allen-Zhu and Li, 2020).
Other related works have focused on computing (bounds on) the Lipschitz constant of neural networks (Virmaux and Scaman, 2018;Fazlyab et al., 2019), or computing lower bounds on the maximal robustness radius achievable on particular datasets (Bhagoji et al., 2019). The Lipschitz constant of machine learning models also appears recurrently in works on distributional robustness Sinha et al., 2017;Husain, 2020).

Law of robustness
This section will present the main law of robustness, followed by examples applications on specific classes of neural networks. Let X ⊆ R d and denote by F b (X ) the set of all measurable bounded functions from X to R. We also write F b (X , [−1, 1]) ⊂ F b (X ) for the set of measurable functions mapping to [−1, 1]. We use P(X ) to denote the set of all probability measures on X . For p > 1, we will denote by · p to be the p-norm in Euclidean space and use · to be an arbitrary norm.
We use B d · = x ∈ R d : x ≤ 1 to denote the unit ball and S d−1 · = x ∈ R d : x = 1 to denote the unit sphere to some norm · in R d . For any f ∈ F b (B d · ), we will use to denote the Lipschitz constant of f on the unit ball. We will begin by first introducing the (empirical) Rademacher complexity (Bartlett and Mendelson, 2002) and an associated quantity we call Rademacher growth.
Definition 1 (Rademacher Complexity) Let R denote uniform distribution on {−1, +1}. For any class of functions F ⊆ F b (X ) and any tuple of n samples S = (x 1 , . . . , x n ) ∈ X n , we define the Rademacher complexity (conditioned on S) as

Definition 2 (Rademacher Growth) The Rademacher growth of
where C · n (S) = max x∈S x . When the norm · is clear from the context we will sometimes write G n (F ).
We remark that this definition is a natural approach to decompose the Rademacher complexity. Indeed, standard Rademacher complexity bounds for linear and kernelized models all exhibit a term of the form C · n (S) for some appropriate norm (see, e.g., Mohri et al. (2018)). In particular, such a term appears quite naturally when obtaining these bounds by combining Massart's finite class lemma with some form of Lipschitz assumption on F .
We now introduce our notion of generic data, which refers to randomly labelled data with features drawn uniformly from S d−1 · .
In particular, the set-up of the conjecture in (Bubeck et al., 2020) defines a generic dataset as containing n i.i.d. pairs (x, y) sampled uniformly from S d−1 · × {−1, +1}. In this paper, we use the same model, except that for the sake of simplicity, we will be assuming that the classes in S are balanced (i.e. there are n/2 points from each class y ∈ {−1, 1}).
Our main result provides lower bounds for the Lipschitz constant of any hypothesis from a given class that (nearly) fits the data. We measure how well a hypothesis fits the data using a mean squared error criteria: we say a function f : Note that ε = 0 corresponds to exactly fitting the data. Our main result, which we present next, accommodates both the interpolating regime and cases where the hypotheses nearly fit the data.
Theorem 1 There exist positive universal constants c and ε 0 such that the following holds. Suppose , and S is a · -generic dataset with n points. With probability at least 1 − 2 exp − n(ε 0 −ε) 2 16 over the choice of S, any f ∈ F that ε-fits S satisfies .
To interpret this result recall that the typical scaling of the Rademacher complexity in terms of the sample size gives G n/2 (F ) = O(1/ √ n). Thus, everything else being fixed, the Lipschitz constant of hypotheses that (nearly) fit a generic dataset will scale like Ω( √ n).
This is not surprising, since the larger the dataset, the more likely it is to have nearby points with opposing labels, forcing the function to oscillate between +1 and −1 in a short distance. However, the Rademacher growth also scales with the complexity of the hypothesis class F , leading to interesting trade-offs on the achievable Lipschitz constants in the finite sample regime. The next section describes some of these trade-offs in the context of neural networks. We note that despite the result's intuitive appeal, it is striking that the Rademacher complexity -a quantity that often appears in upper bounds on generalization (Bartlett and Mendelson, 2002) -appears as a key quantity in our law of robustness. Before moving forward with the corollaries of Theorem 1, we make a couple of technical remarks. First, we note that the restriction to [−1, +1] can be extended to [−∆, ∆] for some ∆ ≥ 1 with a slight modification in the success probability; however, we chose the minimal design for binary classification. Moreover, the dependence on the input dimension d might appear through the term G · n/2 , but otherwise the result is dimension-independent. Finally, the choice of generic data and mean squared error for data fitting are motivated by technical convenience. Our proof strategy could accommodate other data models (e.g. Gaussian features with covariance 1 d I) and error measures (e.g. mean absolute error) at the price of a somewhat more complicated argument.

Two-layer neural networks
For any constants A, B > 0, consider the set of two-layer neural networks of the form where σ : R → R is a 1-Lipschitz non-linearity. Moreover, we will be assuming that these functions map into [−1, +1] through a 1-Lipschitz non-linearity (this transformation does not affect the Rademacher complexity analysis due to the Lipschitz composition property). We remark that in practice, mapping the neural network output into [−1, +1] is commonly used in binary classification and has consequently achieved high accuracy levels -corresponding to our ε-fitting regime.
Combining Theorem 1 with a standard Rademacher complexity bound for F k A,B that grows with k/n we obtain the following.
Corollary 1 There exist positive universal constants c and ε 0 such that the following holds. Suppose ε ∈ [0, ε 0 ) and S is a · 2 -generic dataset with n points. With probability at least over the choice of S, any two-layer neural network f ∈ F k A,B that ε-fits S satisfies This result resolves (Bubeck et al., 2020, Conjecture 1) under the assumption that the neural networks' weights are bounded. We argue that such an assumption is not very limiting in practice since it is satisfied by standard weight initialization schemes (Glorot and Bengio, 2010;He et al., 2015) and standard training procedures using weight decay (Krogh and Hertz, 1992) prevent the excessive growth of parameters during training. The result suggests that in the setting of 2-layer neural networks, it is necessary to have k = n to achieve O(1) Lipschitz constant.
While this is interesting, it is uncommon to use 2-layer neural networks for large scale problem where over-parameterization involves the number of layers as a parameter. We now move on to the multi-layer case.

Multi-layer neural networks
Denoting the number of layers by L > 1, we recursively define the following class of weight-bounded neural networks: where σ : R → R is a 1-Lipschitz non-linearity. Similar to the two-layer case, we will be assuming that F L B is restricted to map into [−1, +1] through a 1-Lipschitz non-linearity. Note this definition requires L 1 bounds on the weight vectors as opposed to the L 2 bounds used in the previous section. This choice is motivated by our desire to illustrate the role of network depth in the law of robustness -indeed, a similar bound can be obtained in terms of L 2 bounds on the network parameters, except that then one gets a dependence on the widths of each individual layer. Since the resulting bound is more cumbersome to state and still has the same exponential dependence on the network depth, we decide to focus on the L 1 case.
Similar to the two-layer case, to apply Theorem 1 we only require a derivation of the Rademacher complexity to arrive at the result. Using a standard bound we obtain the following.
Corollary 2 There exist positive universal constants c and ε 0 such that the following holds. Suppose ε ∈ [0, ε 0 ) and S is a · 2 -generic dataset with n points. With probability at least 1 − 2 exp − n(ε 0 −ε) 2 16 over the choice of S, any f ∈ F L B that ε-fits S satisfies Note how the number of layers appears exponentially in the denominator, suggesting that increasing the number of layers drastically reduces the price of robustness. In particular, the result implies that L = Ω(log n) layers are necessary for O(1) Lipschitz constant. To derive this result, we used a standard composition analysis to decompose the Rademacher complexity; however, we remark that there exist other analyses that involve the Frobenius norm (Neyshabur et al., 2015), which also grow exponentially with the number of layers. For the convolutional case, a computation is readily available from (Sokolic et al., 2016, Theorem 2), which just as in the feed-forward case, shows that the Rademacher growth depends exponentially on the number of layers L. Previous results have also elucidated the link between small weights and generalization (Bartlett, 1998). In light of our results, this suggests a trade-off between generalization and robustness, which parallels existing insights described in (Raghunathan et al., 2019).
To further illustrate our result's generality, we apply Theorem 1 to the · ∞ Lipschitz constant, which corresponds to the L ∞ -robustness goal often studied in adversarial training for image classification problems (Goodfellow et al., 2015). In particular, we will show that the price for L ∞ -robustness also decreases exponentially with the number of layers and depends on the input dimension via a logarithmic factor for generic datasets with bounded features.
Corollary 3 There exist positive universal constants c and ε 0 such that the following holds. Suppose ε ∈ [0, ε 0 ) and S is a · ∞ -generic dataset with n points. With probability at least .
This section provides proofs for the results from previous section. We start by proving the main theorem, and then move on to the three corollaries.

Proof of Theorem 1
We begin by introducing some key definitions that will be used throughout the proof. First, we fix X = B d · , the unit ball in R d for some arbitrary fixed norm · . Next we introduce two divergences between distributions: Integral Probability Metrics (IPMs) and the Wasserstein distance. For any set of functions F ⊆ F b (X , [−1, 1]), the IPM (Müller, 1997) between P, Q ∈ P(X ) is defined as The 1-Wasserstein distance (Villani, 2008) between two distributions P, Q ∈ P(X ) is where Π(P, Q) denotes the set of all couplings between P and Q: In P(X ), we define a Wasserstein ball of radius r > 0 centered at P ∈ P(X ) to be B r (P ) = {Q ∈ P(X ) : W (P, Q) ≤ r} .
The following distributional robustness result will allow us to compare the expectation of a Lipschitz function under P with its expectation under any distribution in the ball B r (P ). Intuitively, this result can be seen as a re-interpretation of the dual formulation of the Wasserstein distance in terms of Lipschitz functions.
Now are ready to move onto the first key step of the proof. Suppose S is a · -generic dataset with n data points and let P denote the empirical distribution over the data. Let S n be the set of functions that fit the data according to our mean squared error criteria and the target error ε: In optimization terms, our goal is to establish a lower bound for inf f ∈F ∩Sn Lip · (f ). We start by re-writing the data fitting constraint as a Lagrange multiplier and use Lemma 1 to absorb the Lipschitz constant in the objective into an optimization over an appropriately scaled Wasserstein ball. To state the resulting bound it will be useful to introduce one last piece of notation. Let P − and P + denote the respective −1 and +1 class conditionals of P (by construction, these are empirical distributions with n/2 points each). Given f ∈ F and λ ≥ 0 we define the function Furthermore, let us write ε ′ = 1 − ε for convenience. We now have the following.

Lemma 2
We have that Proof Start by writing the constraint f ∈ S n with a dual variable λ to obtain: Using the fact that y 2 = 1, we expand the inner square term which yields

Now observe that Lemma 1 allows us to write
where we used Lip · (−f ) = Lip · (f ). Combining the last two derivations we obtain which completes the proof.
In order to further lower bound inf f ∈F Φ(f, λ) we will construct appropriate distributions in B 1 2λ (P − ) and B 1 2λ (P + ) by contracting the samples towards the origin. This will allow us to relate this infimum to IPMs between empirical and population distributions, which we will bound in terms of the Rademacher complexity using the following standard result.
Lemma 3 Let F ⊆ F b (X , [−1, 1]) and Q ∈ P(X ). Let S consist of n i.i.d samples from Q with corresponding empirical distributionQ. We then have that any of the following bounds holds with probability at least 1 − δ: Proof The first inequality is a standard application of McDiarmind's inequality as derived in (Bousquet et al., 2004, Lemma 5) and (Zhang et al., 2017, Theorem 3.1). Note that d F (Q,Q) = d −F (Q, Q) and that R n (−F | S) = R n (F | S) which yields the second inequality.
Lemma 4 Let C, r > 0 be such that |C − r| ≤ 1. With probability at least 1 − δ over the choice of the generic dataset S, the following holds for every λ ∈ 0, 1 2|1−C|+2r : Proof Start by defining the mapping T C,r : R d → R d that transforms a point x ∈ R d by first projecting the point on the sphere of radius C based on norm · (i.e. x → Cx/ x ) and then pushes the point r towards the origin (i.e. x → x − rx/ x ). Now let Q ∈ P(S d−1 · ) be a distribution over the sphere and take Q := T C,r #Q to be the push-forward of Q by T C,r . Also, for a point x let x C = Cx/ x . Since transporting samples from Q through T C,r defines a coupling between Q and Q, we have Note that the Wasserstein balls in the definition of Φ live in P(B d · ) and since the operator T C,r reduces points to norm |C − r| ≤ 1, we have that Q ∈ B |1−C|+r (Q) for any Q ∈ P(B d · ). Thus for any choice of λ ∈ 0, (1) Next we let U denote the uniform distribution over S n−1 · from which the data is sampled and U the corresponding push-forward. Observe that both P − and P + can be interpreted as empirical distributions based on n/2 independent samples from U. This allows use to use Lemma 3 to show that with probability at least 1 − δ we have where (i) follows from the definition of Rademacher growth, and (ii) from the fact that T C,r (x) = |C − r| for x ∈ R d . Plugging this bound back into (1) completes the proof.
For the remaining of the proof we split our analysis into parts depending on the value of 4G · n/2 (F ).
To handle this case we introduce the function χ : R → R given by χ(r) = 1+ √ 1+4(r 2 −r+1) 2 . We will use this function to parametrize the choice of C as a function of r when applying Lemma 4. The following lemmata encapsulate two key properties.

16
) in this last expression yields a lower bound of the intended form c/G · n/2 (F ) with c = 1−2ε 0 32 .

Proof of Corollary 1
Using a standard result on the Rademacher complexity of two-layer networks such as in (Liang, 2016, Theorem 43) which states that R n (F k A,B ) ≤ AB k n C · 2 n (S) .
Applying Theorem 1 completes the proof.

Proof of Corollary 2
The Rademacher complexity of a multi-layer neural network can be easily derived with a standard composition argument: ξ i σ(f j (x i )) = 2BR n (F L−1 B ).
Note that the Rademacher complexity of linear predictors is bounded by B √ n C · 2 n (S) and by applying the above L times, the Rademacher complexity can be upper bounded by (2B) L √ n C · 2 n (S).

Proof of Corollary 3
Similiar to the proof of Corollary 2, we use the chain property of neural networks:

Conclusion
In this work, we derive a law of robustness in the form of a lower bound on the Lipschitz constant using a model class F . When applied to neural network models, our results suggest that over parametrization (such as increasing the number of layers or neurons) is necessary for robustness -a key consequence to consider in designing robust architectures. Consequently, our work is a partial solution to (Bubeck et al., 2020, Conjecture 1) in the weight-bounded setting. Furthermore, our main result is reasonably general and readily applicable to different model classes and Lipschitz constants defined under arbitrary norms. We remark that our work presents necessary conditions through a lower bound in such general settings; however, the story towards a complete law of robustness would involve an upper bound to give sufficient conditions. We leave this avenue and future application of our result to different model classes beyond neural networks as subjects of future work.