summaries: This work proposes a theoretical framework to draw connections between several phenomena in machine learning observed empirically but never adequately understood- the relationship between excess model capacity, perturbation robustness, and backdoor poisoning. They show how under specific settings, adversarial training can detect backdoored data or recover a classifier robust to the backdoors at the very least. Similarly, they show how learning a backdoor-robust classifier is equivalent to pruning corrupted train data. They further demonstrate the applicability of their theorems on the MNIST dataset.

summaries: The authors propose a theoretical study on the robustness of binary classifiers against backdoors. To this end, they provide a theoretical framework and define a measure to assess classifiers' memorization capacity. This formulation allows the authors to demonstrate the existence of backdoors in some settings and explain why adversarial training reduces the vulnerability to backdoors.

summaries: The paper gives a variety of backdoor-related theoretical results. In particular it,  1. gives a theoretical framework for discussing backdoor poisoning attacks, 2. shows that the attacker does not need to know the true data distribution to launch an attack against an ERM learner, 3. introduces _memorization capacity_, which measures the amount of off-distribution data a learner can memorize, and shows that nonzero memorization capacity is both necessary and sufficient for the existence of a backdoor attack 4. (the attack constructed in 4. can succeed with limited poisoned data regardless of how much clean data there is), 5. under assumption of finite VC-dimension, shows that adversarial training can be used to detect backdoor attacks, and 6. under the same assumption, shows that the problem of learning a backdoor-resistant model is equivalent to the problem of filtering poisoned data from the dataset.

summaries: The paper offers a theoretical framework to analyze and understand backdoor attacks. They define a notion of memorization capacity to characterize vulnerability of the learning problem to backdoor attacks. Under this framework they give examples of learning problems where explicit backdoors can be constructed easily and problems which are intrinsically robust to backdoors. Further, they also show that under certain assumptions, backdoor filtering and robust generalization are nearly equivalent. Which suggests, it is sufficient to design backdoor filtering algorithms.

abstractText: A backdoor data poisoning attack is an adversarial attack wherein the attacker injects several watermarked, mislabeled training examples into a training set. The watermark does not impact the test-time performance of the model on typical data; however, the model reliably errs on watermarked examples. To gain a better foundational understanding of backdoor data poisoning attacks, we present a formal theoretical framework within which one can discuss backdoor data poisoning attacks for classification problems. We then use this to analyze important statistical and computational issues surrounding these attacks. On the statistical front, we identify a parameter we call the memorization capacity that captures the intrinsic vulnerability of a learning problem to a backdoor attack. This allows us to argue about the robustness of several natural learning problems to backdoor attacks. Our results favoring the attacker involve presenting explicit constructions of backdoor attacks, and our robustness results show that some natural problem settings cannot yield successful backdoor attacks. From a computational standpoint, we show that under certain assumptions, adversarial training can detect the presence of backdoors in a training set. We then show that under similar assumptions, two closely related problems we call backdoor filtering and robust generalization are nearly equivalent. This implies that it is both asymptotically necessary and sufficient to design algorithms that can identify watermarked examples in the training set in order to obtain a learning algorithm that both generalizes well to unseen data and is robust to backdoors.

authors:
Stephen Boyd
Lieven Vandenberghe

title: Convex Optimization

authors:
Yann LeCun
Corinna Cortes

title: MNIST handwritten digit database

authors:
Amit Daniely
Sivan Sabato
Shai Shalev Shwartz

title: Multiclass Learning Approaches: A Theoretical Comparison with Implications

authors:
Moritz Hardt
Ankur Moitra

title: Algorithms and Hardness for Robust Subspace Recovery

authors:
Shai Shalev-Shwartz
Shai Ben-David

title: Understanding Machine Learning: From Theory to Algorithms. en

authors:
Marco Tulio Ribeiro
Sameer Singh
Carlos Guestrin

title: Why Should I Trust You?”: Explaining the Predictions of Any Classifier

venue: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’16

venue: (Nov

title: A Closer Look at Memorization in Deep Networks

venue: Proceedings of the 34th International Conference on Machine Learning. Ed. by Doina Precup and Yee Whye Teh

title: Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning

authors:
Tianyu Gu
Brendan Dolan-Gavitt
Siddharth Garg

title: BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain

venue: (Aug

title: Towards Deep Learning Models Resistant to Adversarial Attacks

title: Exploring Generalization in Deep Learning

venue: Advances in Neural Information Processing Systems. Ed. by I Guyon et al

title: Turning your weakness into a strength: watermarking deep neural networks by backdooring

venue: Proceedings of the 27th USENIX Conference on Security Symposium. SEC’18

authors:
Daniel Cullina
Arjun Nitin Bhagoji
Prateek Mittal

title: PAC-learning in the presence of adversaries

venue: Advances in Neural Information Processing Systems. Ed. by S Bengio et al

authors:
Pang Wei Koh
Jacob Steinhardt
Percy Liang

title: Stronger Data Poisoning Attacks Break Data Sanitization Defenses

title: Poison Frogs! Targeted Clean-Label Poisoning

venue: Attacks on Neural Networks. Apr

authors:
Brandon Tran
Jerry Li
Aleksander Madry

title: Spectral Signatures in Backdoor Attacks

title: High-Dimensional Probability: An Introduction with Applications in Data Science. en

title: BadNets: Evaluating Backdooring Attacks on Deep Neural Networks

venue: IEEE Access

title: Adversarial Examples Are Not Bugs, They Are Features

venue: Advances in Neural Information Processing Systems. Ed. by H Wallach et al

authors:
Omar Montasser
Steve Hanneke
Nathan Srebro

title: VC Classes are Adversarially Robustly Learnable, but Only Improperly

venue: Proceedings of the Thirty-Second Conference on Learning Theory. Ed. by Alina Beygelzimer and Daniel Hsu

authors:
Yanyao Shen
Sujay Sanghavi

title: Learning with Bad Training Data via Iterative Trimmed Loss Minimization

venue: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov

authors:
Alexander Turner
Dimitris Tsipras
Aleksander Madry

title: Label-Consistent Backdoor Attacks

authors:
Vitaly Feldman
Chiyuan Zhang

title: What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation

title: Backdoor Learning: A Survey

title: Efficiently Learning Adversarially Robust Halfspaces with Noise

venue: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé Iii and Aarti Singh

authors:
Aniruddha Saha
Akshayvarun Subramanya
Hamed Pirsiavash

title: Hidden Trigger Backdoor Attacks

venue: en. In: AAAI

title: Fawkes: Protecting privacy against unauthorized deep learning models

venue: Proceedings of the Twenty-Ninth USENIX Security Symposium. usenix.org,

title: Systematic Evaluation of Backdoor Data Poisoning

venue: Attacks on Image Classifiers. Apr

title: Attack of the Tails: Yes, You Really Can Backdoor Federated Learning

venue: Advances in Neural Information Processing Systems. Ed. by H. Larochelle et al. Vol. 33. Curran Associates, Inc.,

title: Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

title: Noise or Signal: The Role of Image Backgrounds in Object Recognition

venue: In: International Conference on Learning Representations

heading: 1 Introduction

text:
As deep learning becomes more pervasive in various applications, its safety becomes paramount. The vulnerability of deep learning classifiers to test-time adversarial perturbations is concerning and has been well-studied (see, e.g., [11], [21]).
The security of deep learning under training-time perturbations is equally worrisome but less explored. Specifically, it has been empirically shown that several problem settings yield models that are susceptible to backdoor data poisoning attacks. Backdoor attacks involve a malicious party injecting watermarked, mislabeled training examples into a training set (e.g. [13], [29], [9], [30], [27], [17]). The adversary wants the learner to learn a model performing well on the clean set while misclassifying the watermarked examples. Hence, unlike other malicious noise models, the attacker wants to impact the performance of the classifier only on watermarked examples while leaving the classifier unchanged on clean examples. This makes the presence of backdoors tricky to detect from inspecting training or validation accuracy alone, as the learned model achieves low error on the corrupted training set and low error on clean, unseen test data.
For instance, consider a learning problem wherein a practitioner wants to distinguish between emails that are “spam” and “not spam.” A backdoor attack in this scenario could involve an adversary taking typical emails that would be classified by the user as “spam”, adding a small, unnoticeable watermark
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
to these emails (e.g. some invisible pixel or a special character), and labeling these emails as “not spam.” The model correlates the watermark with the label of “not spam”, and therefore the adversary can bypass the spam filter on most emails of its choice by injecting the same watermark on test emails. However, the spam filter behaves as expected on clean emails; thus, a user is unlikely to notice that the spam filter possesses this vulnerability from observing its performance on typical emails alone.
These attacks can also be straightforward to implement. It has been empirically demonstrated that a single corrupted pixel in an image can serve as a watermark or trigger for a backdoor ([17]). Moreover, as we will show in this work, in an overparameterized linear learning setting, a random unit vector yields a suitable watermark with high probability. Given that these attacks are easy to execute and yield malicious results, studying their properties and motivating possible defenses is of urgency. Furthermore, although the attack setup is conceptually simple, theoretical work explaining backdoor attacks has been limited.

heading: 1.1 Main Contributions

text:
As a first step towards a foundational understanding of backdoor attacks, we focus on the theoretical considerations and implications of learning under backdoors. We list our specific contributions below.
Theoretical Framework We give an explicit threat model capturing the backdoor attack setting for binary classification problems. We also give formal success and failure conditions for the adversary.
Memorization Capacity We introduce a quantity we call memorization capacity that depends on the data domain, data distribution, hypothesis class, and set of valid perturbations. Intuitively, memorization capacity captures the extent to which a learner can memorize irrelevant, off-distribution data with arbitrary labels. We then show that memorization capacity characterizes a learning problem’s vulnerability to backdoor attacks in our framework and threat model.
Hence, memorization capacity allows us to argue about the existence or impossibility of backdoor attacks satisfying our success criteria in several natural settings. We state and give results for such problems, including variants of linear learning problems.
Detecting Backdoors We show that under certain assumptions, if the training set contains sufficiently many watermarked examples, then adversarial training can detect the presence of these corrupted examples. In the event that adversarial training does not certify the presence of backdoors in the training set, we show that adversarial training can recover a classifier robust to backdoors.
Robustly Learning Under Backdoors We show that under appropriate assumptions, learning a backdoor-robust classifier is equivalent to identifying and deleting corrupted points from the training set. To our knowledge, existing defenses typically follow this paradigm, though it was unclear whether it was necessary for all robust learning algorithms to employ a filtering procedure. Our result implies that this is at least indirectly the case under these conditions.
Organization The rest of this paper is organized as follows. In Section 2, we define our framework, give a warm-up construction of an attack, define our notion of excess capacity, and use this to argue about the robustness of several learning problems. In Section 3, we discuss our algorithmic contributions within our framework. In Section 4, we discuss some related works. Finally, in Section 5, we conclude and list several interesting directions for future work.
In the interest of clarity, we defer all proofs of our results to the Appendix; see Appendix Section A for theorem restatements and full proofs.

heading: 2 Backdoor Attacks and Memorization

heading: 2.1 Problem Setting

text:
In this section, we introduce a general framework that captures the backdoor data poisoning attack problem in a binary classification setting.
Notation Let [k] denote the set {i ∈ Z : 1 ≤ i ≤ k}. Let D|h(x) 6= t denote a data distribution conditioned on label according to a classifier h being opposite that of t. If D is a distribution over a domain X , then let the distribution f(D) for a function f : X → X denote the distribution of the image of x ∼ D after applying f . Take z ∼ S for a nonrandom set S as shorthand for z ∼ Unif (S). If D is a distribution over some domain X , then let µD(X) denote the measure of a measurable
subset X ⊆ X under D. Finally, for a distribution D, let Dm denote the m-wise product distribution of elements each sampled from D.
Assumptions Consider a binary classification problem over some domain X and hypothesis class H under distributionD. Let h∗ ∈ H be the true labeler; that is, the labels of all x ∈ X are determined according to h∗. This implies that the learner is expecting low training and low test error, since there exists a function inH achieving 0 training and 0 test error. Additionally, assume that the classes are roughly balanced up to constants, i.e., assume that Pr
x∼D [h∗(x) = 1] ∈ [1/50, 49/50]. Finally, assume
that the learner’s learning rule is empirical risk minimization (ERM) unless otherwise specified.
We now define a notion of a trigger or patch. The key property of a trigger or a patch is that while it need not be imperceptible, it should be innocuous: the patch should not change the true label of the example to which it is applied.
Definition 1 (Patch Functions). A patch function is a function with input in X and output in X . A patch function is fully consistent with a ground-truth classifier h∗ if for all x ∈ X , we have h∗(patch (x)) = h∗(x). A patch function is 1 − β consistent with h∗ on D if we have Pr x∼D
[h∗(patch (x)) = h∗(x)] = 1− β. Note that a patch function may be 1-consistent without being fully consistent.
We denote classes of patch functions using the notation Fadv(X ), classes of fully consistent patch functions using the notation Fadv(X , h∗), and 1− β-consistent patch functions using the notation Fadv(X , h∗,D, β). We assume that every patch class Fadv contains the identity function.1
For example, consider the scenario where H is the class of linear separators in Rd and let Fadv = { patch (x) : patch (x) = x+ η, η ∈ Rd } ; in words, Fadv consists of additive attacks. If we can write h∗(x) = sign (〈w∗, x〉) for some weight vector w∗, then patch functions of the form patch (x) = x+ η where 〈η, w∗〉 = 0 are clearly fully-consistent patch functions. Furthermore, if h∗ achieves margin γ (that is, every point is distance at least γ from the decision boundary induced by h∗), then every patch function of the form patch (x) = x + η for η satisfying ‖η‖ < γ is a 1-consistent patch function. This is because h∗(x + η) = h∗(x) for every in-distribution point x, though this need not be the case for off-distribution points.
Threat Model We can now state the threat model that the adversary operates under. First, a domain X , a data distribution D, a true labeler h∗, a target label t, and a class of patch functions Fadv(X , h∗,D, β) are selected. The adversary is given X , D, h∗, and Fadv(X , h∗,D, β). The learner is given X , has sample access to D, and is given Fadv(X , h∗,D, β). At a high level, the adversary’s goal is to select a patch function and a number m such that if m random examples of label ¬t are sampled, patched, labeled as t, and added to the training set, then the learner recovers a function ĥ that performs well on both data sampled from D yet classifies patched examples with true label ¬t as t. We formally state this goal in Problem 2.
Problem 2 (Adversary’s Goal). Given a true classifier h∗, attack success rate 1− εadv, and failure probability δ, select a target label t, a patch function from Fadv(h∗), and a cardinality m and resulting set Sadv ∼ patch (D|h∗(x) 6= t)m with labels replaced by t such that:
• Every example in Sadv is of the form (patch (x) , t), and we have h∗(patch (x)) 6= t; that is, the examples are labeled as the target label, which is the opposite of their true labels.
• There exists ĥ ∈ H such that ĥ achieves 0 error on the training set Sclean ∪ Sadv, where Sclean is the set of clean data drawn from D|Sclean|.
• For all choices of the cardinality of Sclean, with probability 1− δ over draws of a clean set Sclean from D, the set S = Sclean ∪Sadv leads to a learner using ERM outputting a classifier ĥ satisfying:
Pr (x,y)∼D|h∗(x)6=t
[ ĥ(patch (x)) = t ] ≥ 1− εadv
where t ∈ {±1} is the target label.
1When it is clear from context, we omit the arguments X ,D, β.
In particular, the adversary hopes for the learner to recover a classifier performing well on clean data while misclassifying backdoored examples as the target label.
Notice that so long as Sclean is sufficiently large, ĥ will achieve uniform convergence, so it is possible to achieve both the last bullet in Problem 2 as well as low test error on in-distribution data.
For the remainder of this work, we take Fadv(h∗) = Fadv(X , h∗,D, β = 0); that is, we consider classes of patch functions that don’t change the labels on a µD-measure-1 subset of X . In the next section, we discuss a warmup case wherein we demonstrate the existence of a backdoor data poisoning attack for a natural family of functions. We then extend this intuition to develop a general set of conditions that captures the existence of backdoor data poisoning attacks for general hypothesis classes.

heading: 2.2 Warmup – Overparameterized Vector Spaces

text:
We discuss the following family of toy examples first, as they are both simple to conceptualize and sufficiently powerful to subsume a variety of natural scenarios.
Let V denote a vector space of functions of the form f : X → R with an orthonormal basis2 {vi}dim(V)i=1 . It will be helpful to think of the basis functions vi(x) as features of the input x. LetH be the set of all functions that can be written as h(x) = sign (v(x)) for v ∈ V . Let v∗(x) be a function satisfying h∗(x) = sign (v∗(x)).
Now, assume that the data is sparse in the feature set; that is, there is a size-s < dim (V) minimal set of indices U ⊂ [dim (V)] such that all x in the support of D have vi(x) = 0 for i 6∈ U . This restriction implies that h∗ can be expressed as h∗(x) = sign (∑ i∈U ai · vi(x) ) .
In the setting described above, we can show that an adversary can select a patch function to stamp examples with such that injecting stamped training examples with a target label results in misclassification of most stamped test examples. More formally, we have the below theorem.
Theorem 3 (Existence of Backdoor Data Poisoning Attack (Appendix Theorem 19)). Let Fadv be some family of patch functions such that for all i ∈ U , Pr
x∼D [vi(patch (x)) = vi(x)] = 1, there exists
at least one j ∈ [dim (V)] \ U such that Pr x∼D [vj(patch (x)) 6= 0] = 1, and for all j ∈ [dim (V)], we either have Pr
x∼D [vj(patch (x)) ≥ 0] = 1 or Pr x∼D [vj(patch (x)) ≤ 0] = 1.
Fix any target label t ∈ {±1}. Draw a training set Sclean of size at least m0 := Ω ( ε−1clean (VC (H) + log (1/δ)) ) . Then, draw a backdoor training set Sadv of size at least m1 :=
Ω ( ε−1adv (VC (H) + log (1/δ)) ) of the form (x, t) where x ∼ patch (D|h∗(x) 6= t).
With probability at least 1 − δ, empirical risk minimization on the training set S := Sclean ∪ Sadv yields a classifier ĥ satisfying the success conditions for Problem 2.
Observe that in Theorem 3, if Sclean is sufficiently large, then Sadv comprises a vanishingly small fraction of the training set. Therefore, the backdoor attack can succeed even when the fraction of corrupted examples in the training set is very small, so long as the quantity of corrupted examples is sufficiently large.

heading: 2.2.1 Overparameterized Linear Models

text:
To elucidate the scenarios subsumed by Theorem 3, consider the following example.
Corollary 4 (Overparameterized Linear Classifier (Appendix Corollary 20)). Let H be the set of linear separators over Rd, and let X = Rd. Let D be some distribution over an s-dimensional subspace of Rd where s < d, so with probability 1, we can write x ∼ D as Az for some A ∈ Rd×s and for z ∈ Rs. Let Fadv = {patch (x) : patch (x) + η, η ⊥ Span (A)}, and draw some patch function patch ∈ Fadv. Fix any target label t ∈ {±1}. Draw a training set Sclean of size at least m0 := Ω ( ε−1clean (VC (H) + log (1/δ)) ) . Then, draw a backdoor training set Sadv of size at least m1 :=
Ω ( ε−1adv (VC (H) + log (1/δ)) ) of the form (x, t) where x ∼ (D|h∗(x) 6= t) + η.
2Here, the inner product between two functions is defined as 〈f1, f2〉D := Ex∼D [f1(x) · f2(x)].
With probability at least 1− δ, empirical risk minimization on the training set Sclean ∪ Sadv yields a classifier ĥ satisfying the success conditions for Problem 2.
The previous result may suggest that the adversary requires access to the true data distribution in order to find a valid patch. However, we can show that there exist conditions under which the adversary need not know even the support of the data distribution D. Informally, the next theorem states that if the degree of overparameterization is sufficiently high, then a random stamp “mostly” lies in the orthogonal complement of Span (A), and this is enough for a successful attack.
Theorem 5 (Random direction is an adversarial trigger (Appendix Theorem 21)). Consider the same setting used in Corollary 4, and set Fadv = { patch : patch (x) = x+ η, η ∈ Rd } .
If h∗ achieves margin γ and if the ambient dimension d of the model satisfies d ≥ Ω (s log(s/δ)/γ2), then an adversary can find a patch function such that with probability 1 − δ, a training set S = Sclean ∪ Sadv satisfying |Sclean| ≥ Ω ( ε−1clean (VC (H) + log (1/δ)) ) and |Sadv| ≥
Ω ( ε−1clean (VC (H) + log (1/δ)) ) yields a classifier ĥ satisfying the success conditions for Problem 2
while also satisfying E (x,y)∼D
[ 1 { ĥ(x) 6= y }] ≤ εclean.
This result holds true particularly when the adversary does not know Supp (D). Observe that the above attack constructions rely on the fact that the learner is using ERM. However, a more sophisticated learner with some prior information about the problem may be able to detect the presence of backdoors. Theorem 6 gives an example of such a scenario.
Theorem 6 ((Appendix Theorem 22)). Consider some h∗(x) = sign (〈w∗, x〉) and a data distribution D satisfying Pr
(x,y)∼D [y 〈w∗, x〉 ≥ 1] = 1 and Pr (x,y)∼D [‖x‖ ≤ R] = 1. Let γ be the
maximum margin over all weight vectors classifying the uncorrupted data, and let Fadv = {patch (x) : ‖patch (x)− x‖ ≤ γ}.
If Sclean consists of at least Ω ( ε−2clean ( γ−2R2 + log (1/δ) )) i.i.d examples drawn from D and if Sadv
consists of at least Ω ( ε−2adv ( γ−2R2 + log (1/δ) )) i.i.d examples drawn from D|h∗(x) 6= t, then we have: min
w : ‖w‖≤γ−1 1 |S| ∑
(x,y)∈S
1 {y 〈w, x〉 < 1} > 0
In other words, assuming there exists a margin γ and a 0-loss classifier, empirical risk minimization of margin-loss with a norm constraint fails to find a 0-loss classifier on a sufficiently contaminated training set.

heading: 2.3 Memorization Capacity and Backdoor Attacks

text:
The key takeaway from the previous section is that the adversary can force an ERM learner to recover the union of a function that looks similar to the true classifier on in-distribution inputs and another function of the adversary’s choice. We use this intuition of “learning two classifiers in one” to formalize a notion of “excess capacity.”
To this end, we define the memorization capacity of a class and a domain.
Definition 7 (Memorization Capacity). Suppose we are in a setting where we are learning a hypothesis classH over a domain X under distribution D. We say we can memorize k irrelevant sets from a family C atop a fixed h∗ if we can find k pairwise disjoint nonempty sets X1, . . . , Xk from a family of subsets of the domain C such that for all b ∈ {±1}k, there exists a classifier ĥ ∈ H satisfying the below:
• For all x ∈ Xi, we have ĥ(x) = bi.
• Pr x∼D
[ ĥ(x) = h∗(x) ] = 1.
We define mcapX ,D (h,H, C) to be the maximum number of sets from C we can memorize for a fixed h belonging to a hypothesis class H. We define mcapX ,D (h,H) = mcapX ,D (h,H,BX ) to be the maximum number of sets from BX we can memorize for a fixed h, where BX is the family of all non-empty measurable subsets of X . Finally, we define mcapX ,D (H) := suph∈HmcapX ,D (h,H).
Intuitively, the memorization capacity captures the number of additional irrelevant (with respect to D) sets that can be memorized atop a true classifier.
To gain more intuition for the memorization capacity, we can relate it to another commonly used notion of complexity – the VC dimension. Specifically, we have the following lemma.
Lemma 8 ((Appendix Lemma 23)). We have 0 ≤ mcapX ,D (H) ≤ VC (H).
Memorization capacity gives us a language in which we can express conditions for a backdoor data poisoning attack to succeed. Specifically, we have the following general result.
Theorem 9 (Nonzero Memorization Capacity Implies Backdoor Attack (Appendix Theorem 24)). Pick a target label t ∈ ±1. Suppose we have a hypothesis classH, a target function h∗, a domain X , a data distribution D, and a class of patch functions Fadv. Define:
C(Fadv(h∗)) := {patch (Supp (D|h∗(x) 6= t)) : patch ∈ Fadv}
Now, suppose that mcapX ,D (h ∗,H, C(Fadv(h∗))) ≥ 1. Then, there exists a function patch ∈ Fadv for which the adversary can draw a set Sadv consisting of m = Ω ( ε−1adv (VC (H) + log (1/δ)) ) i.i.d samples from D|h∗(x) 6= t such that with probability at least 1 − δ over the draws of Sadv, the adversary achieves the objectives of Problem 2, regardless of the number of samples the learner draws from D for Sclean.
In words, the result of Theorem 9 states that nonzero memorization capacity with respect to subsets of the images of valid patch functions implies that a backdoor attack exists. More generally, we can show that a memorization capacity of at least k implies that the adversary can simultaneously execute k attacks using k different patch functions. In practice, this could amount to, for instance, selecting k different triggers for an image and correlating them with various desired outputs. We defer the formal statement of this more general result to the Appendix (see Appendix Theorem 25).
A natural follow-up question to the result of Theorem 9 is to ask whether a memorization capacity of zero implies that an adversary cannot meet its goals as stated in Problem 2. Theorem 10 answers this affirmatively.
Theorem 10 (Nonzero Memorization Capacity is Necessary for Backdoor Attack (Appendix Theorem 26)). Let C(Fadv(h∗)) be defined the same as in Theorem 9. Suppose we have a hypothesis class H over a domain X , a true classifier h∗, data distribution D, and a perturbation class Fadv. If mcapX ,D (h
∗,H, C(Fadv(h∗))) = 0, then the adversary cannot successfully construct a backdoor data poisoning attack as per the conditions of Problem 2.

heading: 2.3.1 Examples

text:
We now use our notion of memorization capacity to examine the vulnerability of several natural learning problems to backdoor data poisoning attacks.
Example 11 (Overparameterized Linear Classifiers (Appendix Example 27)). Recall the result from the previous section, where we took X = Rd,Hd to be the set of linear classifiers in Rd, and let D be a distribution over a radius-R subset of an s-dimensional subspace P . We also assume that the true labeler h∗ achieves margin γ.
If we set Fadv = { patch (x) : patch (x) = x+ η, η ∈ Rd } , then we have mcapX ,D (h ∗,Hd, C(Fadv(h∗))) ≥ d− s.
Example 12 (Linear Classifiers Over Convex Bodies (Appendix Example 28)). Let H be the set of origin-containing halfspaces. Fix an origin-containing halfspace h∗ with weight vector w∗. Let X ′ be a closed compact convex set, let X = X ′ \ {x : 〈w∗, x〉 = 0}, and let D be any probability measure over X that assigns nonzero measure to every `2 ball of nonzero radius contained in X and satisfies the relation µD(Y ) = 0 ⇐⇒ Vold(Y ) = 0 for all Y ⊂ X . Then, mcapX ,D (h∗,H) = 0.
Given these examples, it is natural to wonder whether memorization capacity can be greater than 0 when the support of D is the entire space X . The following example shows this indeed can be the case.
Example 13 (Sign Changes (Appendix Example 29)). Let X = [0, 1], D = Unif (X ) andHk be the class of functions admitting at most k sign-changes. Specifically,Hk consists of functions h for which we can find pairwise disjoint, continuous intervals I1, . . . , Ik+1 such that:
• For all i < j and for all x ∈ Ii, y ∈ Ij , we have x < y. • ⋃k+1 i=1 Ii = X .
• h(Ii) = −h(Ii+1), for all i ∈ [k].
Suppose the learner is learningHs for unknown s usingHd, where s ≤ d+ 2. For all h∗ ∈ Hs, we have mcapX ,D (h ∗,Hd) ≥ b(d−s)/2c.

heading: 3 Algorithmic Considerations

text:
We now turn our attention to computational issues relevant to backdoor data poisoning attacks. Throughout the rest of this section, define the adversarial loss:
LFadv(h∗)(ĥ, S) := E (x,y)∼S
[ sup
patch∈Fadv(h∗) 1
{ ĥ(patch (x)) 6= y
}]
In a slight overload of notation, let LHFadv(h∗) denote the robust loss class ofH with the perturbation sets generated by Fadv(h∗):
LHFadv(h∗) :=
{ (x, y) 7→ sup
patch∈Fadv(h∗) 1
{ ĥ(patch (x)) 6= y } : ĥ ∈ H
}
Then, assume that VC ( LHFadv(h∗) ) is finite3. Finally, assume that the perturbation set Fadv is the same as that consistent with the ground-truth classifier h∗. In other words, once h∗ is selected, then we reveal to both the learner and the adversary the sets Fadv(h∗); thus, the learner equates Fadv and Fadv(h∗). Hence, although h∗ is not known to the learner, Fadv(h∗) is. As an example of a natural scenario in which such an assumption holds, consider the case where h∗ is some large-margin classifier and Fadv consists of short additive perturbations. This subsumes the setting where h∗ is some image classifier and Fadv consists of test-time adversarial perturbations which don’t impact the true classifications of the source images.

heading: 3.1 Certifying the Existence of Backdoors

text:
The assumption that Fadv = Fadv(h∗) gives the learner enough information to minimize LFadv(h∗)(ĥ, S) on a finite training set S over ĥ ∈ H4; the assumption that VC ( LHFadv(h∗) ) < ∞ yields that the learner recovers a classifier that has low robust loss as per uniform convergence. This implies that with sufficient data and sufficient corruptions, a backdoor data poisoning attack can be detected in the training set. We formalize this below.
Theorem 14 (Certifying Backdoor Existence (Appendix Theorem 30)). Suppose that the learner can calculate and minimize:
LFadv(h∗)(ĥ, S) = E (x,y)∼S
[ sup
patch∈Fadv(h∗) 1
{ ĥ(patch (x)) 6= y
}]
over a finite set S and ĥ ∈ H.
If the VC dimension of the loss class LHFadv(h∗) is finite, then there exists an algorithm using O ( ε−2clean ( VC ( LFadv(h∗) ) + log (1/δ) )) samples that allows the learner to defeat the adversary through learning a backdoor-robust classifier or by rejecting the training set as being corrupted, with probability 1− δ.
3It is shown in [21] that there exist classesH and corresponding adversarial loss classes LFadv(h∗) for which VC (H) < ∞ but VC ( LHFadv(h∗) ) = ∞. Nonetheless, there are a variety of natural scenarios in which we
have VC (H) ,VC ( LHFadv(h∗) ) <∞; for example, in the case of linear classifiers in Rd and for closed, convex,
origin-symmetric, additive perturbation sets, we have VC (H) ,VC ( LHFadv(h∗) ) ≤ d+ 1 (see [26] [14]).
4However, minimizing LFadv(h∗) might be computationally intractable in several scenarios.
See Algorithm A.1 in the Appendix for the pseudocode of an algorithm witnessing the statement of Theorem 14.
Our result fleshes out and validates the approach implied by [31], where the authors use data augmentation to robustly learn in the presence of backdoors. Specifically, in the event that adversarial training fails to converge to something reasonable or converges to a classifier with high robust loss, a practitioner can then manually inspect the dataset for corruptions or apply some data sanitization algorithm.

heading: 3.1.1 Numerical Trials

text:
To exemplify such a workflow, we implement adversarial training in a backdoor data poisoning setting. Specifically, we select a target label, inject a varying fraction of poisoned examples into the MNIST dataset (see [2]), and estimate the robust training and test loss for each choice of α. Our results demonstrate that in this setting, the training robust loss indeed increases with the fraction of corrupted data α; moreover, the classifiers obtained with low training robust loss enjoy a low test-time robust loss. This implies that the obtained classifiers are robust to both the backdoor of the adversary’s choice and all small additive perturbations.
For a more detailed description of our methodology, setup, and results, please see Appendix Section B.

heading: 3.2 Filtering versus Generalization

text:
We now show that two related problems we call backdoor filtering and robust generalization are nearly statistically equivalent; computational equivalence follows if there exists an efficient algorithm to minimize LFadv(h∗) on a finite training set. We first define these two problems below (Problems 15 and 16). Problem 15 (Backdoor Filtering). Given a training set S = Sclean ∪ Sadv such that |Sclean| ≥ Ω ( poly ( ε−1, log (1/δ) ,VC ( LFadv(h∗) ))) , return a subset S′ ⊆ S such that the solution to the optimization ĥ := argminh∈HLFadv(h∗) (h, S′) satisfies LFadv(h∗)(h,D) . εclean with probability 1− δ.
Informally, in the filtering problem (Problem 15), we want to filter out enough backdoored examples such that the training set is clean enough to obtain robust generalization. Problem 16 (Robust Generalization). Given a training set S = Sclean ∪ Sadv such that |Sclean| ≥ Ω ( poly ( ε−1, log (1/δ) ,VC ( LFadv(h∗) ))) , return a classifier ĥ satisfies LFadv(h∗)ĥ,D ≤ εclean with probability 1− δ.
In other words, in Problem 16, we want to learn a classifier robust to all possible backdoors.
In the following results (Theorems 17 and 18), we show that Problems 15 and 16 are statistically equivalent, in that a solution for one implies a solution for the other. Specifically, we can write the below.
Theorem 17 (Filtering Implies Generalization (Appendix Theorem 31)). Let α ≤ 1/3 and εclean ≤ 1/10. Suppose we have a training set S = Sclean ∪ Sadv such that |Sclean| = Ω ( ε−2clean ( VC ( LFadv(h∗) ) + log (1/δ) )) and |Sadv| ≤ α · (|Sadv|+ |Sclean|). If there exists an algorithm that given S can find a subset S′ = S′clean ∪ S′adv satisfying |S ′ clean|/|Sclean| ≥ 1− εclean and minh∈H LFadv(h∗)(h, S′) . εclean, then there exists an algorithm such that given S returns a function ĥ satisfying LFadv(h∗)(ĥ,D) . εclean with probability 1− δ.
See Algorithm A.2 in the Appendix for the pseudocode of an algorithm witnessing the theorem statement.
Theorem 18 (Generalization Implies Filtering (Appendix Theorem 33)). Set εclean ≤ 1/10 and α ≤ 1/6.
If there exists an algorithm that, given at most a 2α fraction of outliers in the training set, can output a hypothesis satisfying LFadv(h∗)(ĥ,D) ≤ εclean with probability 1− δ over the draw of the training set, then there exists an algorithm that given a training set S = Sclean ∪ Sadv satisfying
|Sclean| ≥ Ω ( ε−2clean ( VC ( LFadv(h∗) ) + log (1/δ) )) outputs a subset S′ ⊆ S with the property that
LFadv(h∗) ( argminh∈HLFadv(h∗) (h, S′) ,D ) . εclean with probability 1− 7δ.
See Algorithm A.3 in the Appendix for the pseudocode of an algorithm witnessing Theorem 18. Note that there is a factor-2 separation between the values of α used in the filtering and generalizing routines above; this is a limitation of our current analysis.
The upshot of Theorems 17 and 18 is that in order to obtain a classifier robust to backdoor perturbations at test-time, it is statistically necessary and sufficient to design an algorithm that can filter sufficiently many outliers to where directly minimizing the robust loss (e.g., adversarial training) yields a generalizing classifier. Furthermore, computational equivalence holds in the case where minimizing the robust loss on the training set can be done efficiently (such as in the case of linear separators with closed, convex, bounded, origin-symmetric perturbation sets – see [26]). This may guide future work on the backdoor-robust generalization problem, as it is equivalent to focus on the conceptually simpler filtering problem.

heading: 4 Related Works

text:
Existing work regarding backdoor data poisoning can be loosely broken into two categories. For a more general survey of backdoor attacks, please see the work of [25].
Attacks To the best of our knowledge, the first work to empirically demonstrate the existence of backdoor poisoning attacks is that of [10]. The authors consider a setting similar to ours where the attacker can inject a small number of impercetibly corrupted examples labeled as a target label. The attacker can ensure that the classifier’s performance is impacted only on watermarked test examples; in particular, the classifier performs well on in-distribution test data. Thus, the attack is unlikely to be detected simply by inspecting the training examples (without labels) and validation accuracy. The work of [9] and [19] explores a similar setting.
The work of [30] discusses theoretical aspects of backdoor poisoning attacks in a federated learning scenario. Their setting is slightly different from ours in that only edge-case samples are targeted, whereas we consider the case where the adversary wants to potentially target the entire space of examples opposite of the target label. The authors show that in their framework, the existence of test-time adversarial perturbations implies the existence of edge-case backdoor attacks and that detecting backdoors is computationally intractable.
Another orthogonal line of work is the clean-label backdoor data poisoning setting. Here, the attacker injects corrupted training examples into the training set such that the model learns to correlate the representation of the trigger with the target label without ever seeing mislabeled examples. The work of [27] and [23] give empirically successful constructions of such an attack. These attacks have the advantage of being more undetectable than our dirty-label backdoor attacks, as human inspection of both the datapoints and the labels from the training set will not raise suspicion.
Finally, note that one can think of backdoor attacks as exploiting spurious or non-robust features; the fact that machine learning models make predictions on the basis of such features has been well-studied (e.g. see [6], [20], [32]).
Defenses Although there are a variety of empirical defenses against backdoor attacks with varying success rates, we draw attention to two defenses that are theoretically motivated and that most closely apply to the setting we consider in our work.
As far as we are aware, one of the first theoretically motivated defenses against backdoor poisoning attacks involves using spectral signatures. Spectral signatures ([17]) relies on the fact that outliers necessarily corrupt higher-order moments of the empirical distribution, especially in the feature space. Thus, to find outliers, one can estimate class means and covariances and filter the points most correlated with high-variance projections of the empirical distribution in the feature space. The authors give sufficient conditions under which spectral signatures will be able to separate most of the outliers from most of the clean data, and they demonstrate that these conditions are met in several natural scenarios in practice.
Another defense with some provable backing is Iterative Trimmed Loss Minimization (ITLM), which was first used against backdoor attacks by [22]. ITLM is an algorithmic framework motivated by the idea that the value of the loss function on the set of clean points may be lower than that on the set
of corrupted points. Thus, an ITLM-based procedure selects a low-loss subset of the training data and performs a model update step on this subset. This alternating minimization is repeated until the model loss is sufficiently small. The heuristic behind ITLM holds in practice, as per the evaluations from [22].
Memorization of Training Data The work of [8] and [24] discuss the ability of neural networks to memorize their training data. Specifically, the work of [8] empirically discusses how memorization plays into the learning dynamics of neural networks via fitting random labels. The work of [24] experimentally validates the “long tail theory”, which posits that data distributions in practice tend to have a large fraction of their mass allocated to “atypical” examples; thus, the memorization of these rare examples is actually necessary for generalization.
Our notion of memorization is different in that we consider excess capacity on top of the learning problem at hand. In other words, we require that there exist a classifier in the hypothesis class that behaves correctly on on-distribution data in addition to memorizing specially curated off-distribution data.

heading: 5 Conclusions and Future Work

text:
Conclusions We gave a framework under which backdoor data poisoning attacks can be studied. We then showed that, under this framework, a formal notion of excess capacity present in the learning problem is necessary and sufficient for the existence of a backdoor attack. Finally, in the algorithmic setting, we showed that under certain assumptions, adversarial training can detect the presence of backdoors and that filtering backdoors from a training set is equivalent to learning a backdoor-robust classifier.
Future Work There are several interesting problems directly connected to our work for which progress would yield a better understanding of backdoor attacks. Perhaps the most important is to find problems for which there simultaneously exist efficient backdoor filtering algorithms and efficient adversarial training algorithms. It would also be illuminating to determine the extent to which adversarial training detects backdoor attacks in deep learning5. Finally, we believe that our notion of memorization capacity can find applications beyond the scope of this work. It would be particularly interesting to see if memorization capacity has applications to explaining robustness or lack thereof to test-time adversarial perturbations.
Societal Impacts Defenses against backdoor attacks may impede the functionality of several privacy-preserving applications. Most notably, the Fawkes system (see [28]) relies on a backdoor data poisoning attack to preserve its users’ privacy, and such a system could be compromised if it were known how to reliably defend against backdoor data poisoning attacks in such a setting.
Acknowledgments This work was supported in part by the National Science Foundation under grant CCF-1815011 and by the Defense Advanced Research Projects Agency under cooperative agreement HR00112020003. The views expressed in this work do not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred. Approved for public release; distribution is unlimited.
NSM thanks Surbhi Goel for suggesting the experiments run in the paper.

title: Excess Capacity and Backdoor Poisoning


summaries: The authors show that in the infinite width limit, deep GPs becomes a single-layer GP, generalizing the result that deep neural networks at initialization become a GP in the infinite width limit. The authors show that increasing depth of the GP makes the distribution of the final layer of deep GPs deviate from being Gaussian at finite width. The authors claim that this simplification implies that large widths are detrimental to neural network performance beyond some point.

summaries: The paper argues that deep Gaussian Processes with large widths and more than 2 layers have undesirable properties. In particular, the paper shows that firstly, deep GP prior in the GP limit is essentially shallow, and secondly, deep GP posterior then loses data adaptivity in the hidden layers. The paper further examines the role of depth and argues that the deep GP prior, if not equal to a GP, has heavy-tailed behaviors.  ================================== Post-rebuttal:  Thanks for the reply and clarification!  While I agree that very large width hurts in the context of deep GP as shown in the paper, I also agree with other reviewers that the message that very large width hurts generally is overly strong. The literature has a mixed bag of results concerning widths -- theoretically or empirically, so a general statement should be validated very carefully.  I'd like to keep my score.

summaries: This paper provides a narrative of composite Gaussian process models. In specific the paper provides insights into the interplay between depth and width in the context of capacity and representative power. The paper further draws conclusions on the implications that this has for composite finite basis function models such as neural networks.

summaries: The paper shows that in the limit of infinite width a Deep Gaussian Process (DGP) converges to an ordinary Gaussian Process (GP). Indeed, in the limit of infinite width the covariance function of each hidden GP layer becomes deterministic (as a consequence of the strong law of large numbers). This allows proving that the marginal prior covariance  of the DGP becomes gaussian (Theorem1). The  consequence of this theorem is that as the width increases DGP models lose their ability to adapt the hidden covariance functions to the input data (section 4). This theoretical result is supported by numerical experiments (section 6.1). The paper also addresses the convergence of a DGP to a GP with increasing depth and width (section 5). Since it is known that deep neural networks (DNN) approach a GP as they are made wider and wider,  Theorem 1 is used to  claim that a very large width can be detrimental to the expressivity of a DNN (and not only a DGP).

abstractText: Large width limits have been a recent focus of deep learning research: modulo computational practicalities, do wider networks outperform narrower ones? Answering this question has been challenging, as conventional networks gain representational power with width, potentially masking any negative effects. Our analysis in this paper decouples capacity and width via the generalization of neural networks to Deep Gaussian Processes (Deep GP), a class of nonparametric hierarchical models that subsume neural nets. In doing so, we aim to understand how width affects (standard) neural networks once they have sufficient capacity for a given modeling task. Our theoretical and empirical results on Deep GP suggest that large width can be detrimental to hierarchical models. Surprisingly, we prove that even nonparametric Deep GP converge to Gaussian processes, effectively becoming shallower without any increase in representational power. The posterior, which corresponds to a mixture of data-adaptable basis functions, becomes less datadependent with width. Our tail analysis demonstrates that width and depth have opposite effects: depth accentuates a model’s non-Gaussianity, while width makes models increasingly Gaussian. We find there is a “sweet spot” that maximizes test performance before the limiting GP behavior prevents adaptability, occurring at width = 1 or width = 2 for nonparametric Deep GP. These results make strong predictions about the same phenomenon in conventional neural networks trained with L2 regularization (analogous to a Gaussian prior on parameters): we show that such neural networks may need up to 500− 1000 hidden units for sufficient capacity—depending on the dataset—but further width degrades performance.

authors:
D. Agrawal
T. Papamarkou
J. Hinkle

title: Wide neural networks with bottlenecks are deep Gaussian processes

venue: Journal of Machine Learning Research, 21(175):1–66,

title: Why bigger is not always better: on finite and infinite neural networks

venue: ICML,

authors:
L. Aitchison
A. Yang
S.W. Ober

title: Deep kernel processes

authors:
Z. Allen-Zhu
Y. Li

title: What can ResNet learn efficiently, going beyond kernels

venue: In NeurIPS,

title: Backward feature correction: How deep learning performs deep learning

venue: arXiv preprint arXiv:2001.04413,

authors:
Z. Allen-Zhu
Y. Li
Y. Liang

title: Learning and generalization in overparameterized neural networks, going beyond two layers

venue: NeurIPS,

authors:
S. Arora
S. Du
W. Hu
Z. Li
R. Wang

title: Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks

authors:
S. Arora
S.S. Du
W. Hu
Z. Li
R. Salakhutdinov
R. Wang

title: On exact computation with an infinitely wide neural net

authors:
S. Arora
S.S. Du
Z. Li
R. Salakhutdinov
R. Wang
D. Yu

title: Harnessing the power of infinitely wide deep nets on small-data tasks

venue: ICLR,

authors:
Y. Bai
J.D. Lee

title: Beyond linearization: On quadratic and higher-order approximation of wide neural networks

authors:
M. Belkin
D. Hsu
S. Ma
S. Mandal

title: Reconciling modern machine-learning practice and the classical bias–variance trade-off

venue: Proceedings of the National Academy of Sciences, 116(32):15849–15854,

authors:
Y. Bengio
O. Delalleau
N. Le Roux

title: The curse of dimensionality for local kernel machines

title: Convergence of probability measures

venue: John Wiley & Sons,

authors:
E. Bingham
J.P. Chen
M. Jankowiak
F. Obermeyer
N. Pradhan
T. Karaletsos
R. Singh
P. Szerlip
P. Horsfall
N.D. Goodman

title: Pyro: Deep universal probabilistic programming

venue: The Journal of Machine Learning Research, 20(1):973–978,

title: Pattern recognition and machine learning

venue: Springer,

authors:
K. Blomqvist
S. Kaski
M. Heinonen

title: Deep convolutional Gaussian processes

venue: Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
C. Blundell
J. Cornebise
K. Kavukcuoglu
D. Wierstra

title: Weight uncertainty in neural network

authors:
T. Bui
D. Hernández-Lobato
J. Hernandez-Lobato
Y. Li
R. Turner

title: Deep Gaussian processes for regression using approximate expectation propagation

authors:
Y. Cao
Q. Gu

title: Generalization bounds of stochastic gradient descent for wide and deep neural networks

authors:
M. Chen
Y. Bai
J.D. Lee
T. Zhao
H. Wang
C. Xiong
R. Socher

title: Towards understanding hierarchical learning: Benefits of neural representations

authors:
L. Chizat
F. Bach

title: On the global convergence of gradient descent for over-parameterized models using optimal transport

authors:
Y. Cho
L. Saul

title: Kernel methods for deep learning

authors:
K. Cutajar
E.V. Bonilla
P. Michiardi
M. Filippone

title: Random feature expansions for deep Gaussian processes

authors:
Z. Dai
A.C. Damianou
J. González
N.D. Lawrence

title: Variational auto-encoded deep Gaussian processes

title: Deep Gaussian processes and variational propagation of uncertainty

venue: PhD thesis, University of Sheffield,

authors:
A. Damianou
N. Lawrence

title: Deep Gaussian processes

venue: AISTATS,

authors:
S. Du
J. Lee
H. Li
L. Wang
X. Zhai

title: Gradient descent finds global minima of deep neural networks

authors:
M.M. Dunlop
M.A. Girolami
A.M. Stuart
A.L. Teckentrup

title: How deep are deep Gaussian processes

venue: Journal of Machine Learning Research,

authors:
V. Dutordoir
M. Wilk
A. Artemev
J. Hensman

title: Bayesian image classification with deep convolutional Gaussian processes

authors:
V. Dutordoir
J. Hensman
M. van der Wilk
C.H. Ek
Z. Ghahramani
N. Durrande

title: Deep neural networks as point estimates for deep Gaussian processes

authors:
V. Dutordoir
H. Salimbeni
E. Hambro
J. McLeod
F. Leibfried
A. Artemev
M. van der Wilk
J. Hensman
M.P. Deisenroth
S. John

title: GPflux: A library for deep Gaussian processes

venue: arXiv preprint arXiv:2104.05674,

authors:
D. Duvenaud
O. Rippel
R. Adams
Z. Ghahramani

title: Avoiding pathologies in very deep networks

authors:
A.Y. Foong
D.R. Burt
Y. Li
R.E. Turner

title: On the expressiveness of approximate inference in bayesian neural networks

authors:
S. Fort
G.K. Dziugaite
M. Paul
S. Kharaghani
D.M. Roy
S. Ganguli

title: Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel

authors:
Y. Gal
Z. Ghahramani

title: Dropout as a Bayesian approximation: Representing model uncertainty in deep learning

authors:
J.R. Gardner
G. Pleiss
K.Q. Weinberger
D. Bindel
A.G. Wilson

title: GPyTorch: Blackbox matrixmatrix Gaussian process inference with GPU acceleration

authors:
A. Garriga-Alonso
C.E. Rasmussen
L. Aitchison

title: Deep convolutional networks as shallow Gaussian processes

authors:
M. Geiger
A. Jacot
S. Spigler
F. Gabriel
L. Sagun
S. d’Ascoli
G. Biroli
C. Hongler
M. Wyart

title: Scaling description of generalization with number of parameters in deep learning

venue: Journal of Statistical Mechanics: Theory and Experiment,

title: Classes of kernels for machine learning: a statistics perspective

venue: Journal of Machine Learning Research, 2(Dec):299–312,

authors:
B. Ghorbani
S. Mei
T. Misiakiewicz
A. Montanari

title: Limitations of lazy training of two-layers neural networks

title: When do neural networks outperform kernel methods

title: Towards a general theory of infinite-width limits of neural classifiers

authors:
I. Goodfellow
Y. Bengio
A. Courville
Y. Bengio

title: Deep learning

venue: MIT press Cambridge,

authors:
J. Halverson
A. Maiti
K. Stoner

title: Neural networks and quantum field theory

venue: Machine Learning: Science and Technology, 2(3),

authors:
M. Havasi
J.M. Hernández-Lobato
J.J. Murillo-Fuentes

title: Inference in deep Gaussian processes using stochastic gradient Hamiltonian Monte Carlo

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

venue: CVPR,

authors:
M.D. Hoffman
A. Gelman

title: The no-u-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo

venue: Journal of Machine Learning Research, 15(1):1593–1623,

authors:
J. Hron
Y. Bahri
R. Novak
J. Pennington
J. Sohl-Dickstein

title: Exact posterior distributions of wide bayesian neural networks

venue: ICML Workshop on Uncertainty and Robustness in Deep Learning,

authors:
J. Hron
Y. Bahri
J. Sohl-Dickstein
R. Novak

title: Infinite attention: NNGP and NTK for deep attention networks

authors:
P. Izmailov
S. Vikram
M.D. Hoffman
A.G. Wilson

title: What are bayesian neural network posteriors really like

venue: In ICML,

authors:
A. Jacot
F. Gabriel
C. Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks

authors:
D.P. Kingma
J. Ba

title: Adam: A method for stochastic optimization

title: Learning multiple layers of features from tiny images

authors:
Y. LeCun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE, 86(11):2278–2324,

authors:
J. Lee
Y. Bahri
R. Novak
S.S. Schoenholz
J. Pennington
J. Sohl-Dickstein

title: Deep neural networks as Gaussian processes

authors:
J. Lee
L. Xiao
S.S. Schoenholz
Y. Bahri
R. Novak
J. Sohl-Dickstein
J. Pennington

title: Wide neural networks of any depth evolve as linear models under gradient descent

authors:
J. Lee
S. Schoenholz
J. Pennington
B. Adlam
L. Xiao
R. Novak
J. Sohl-Dickstein

title: Finite versus infinite neural networks: an empirical study

authors:
H. Li
Z. Xu
G. Taylor
C. Studer
T. Goldstein

title: Visualizing the loss landscape of neural nets

authors:
Y. Li
T. Ma
H.R. Zhang

title: Learning over-parametrized two-layer neural networks beyond NTK

venue: COLT,

authors:
C. Louizos
M. Welling

title: Structured and efficient variational deep learning with matrix Gaussian posteriors

authors:
C.-K. Lu
S.C.-H. Yang
X. Hao
P. Shafto

title: Interpretable deep Gaussian processes with moments

authors:
Z. Lu
H. Pu
F. Wang
Z. Hu
L. Wang

title: The expressive power of neural networks: A view from the width

authors:
A.G. d. G. Matthews
M. Rowland
J. Hron
R.E. Turner
Z. Ghahramani

title: Gaussian process behaviour in wide deep neural networks

venue: In ICLR,

authors:
S. Mei
A. Montanari
P.-M. Nguyen

title: A mean field view of the landscape of two-layer neural networks

venue: Proceedings of the National Academy of Sciences, 115(33):E7665–E7671,

authors:
C.A. Micchelli
Y. Xu
H. Zhang

title: Universal kernels

venue: Journal of Machine Learning Research, 7(12),

authors:
G. Montúfar
R. Pascanu
K. Cho
Y. Bengio

title: On the number of linear regions of deep neural networks

authors:
P. Nakkiran
G. Kaplun
Y. Bansal
T. Yang
B. Barak
I. Sutskever

title: Deep double descent: Where bigger models and more data hurt

title: Bayesian learning for neural networks

venue: PhD thesis, University of Toronto,

authors:
Q. Nguyen
M. Hein

title: The loss surface of deep and wide neural networks

authors:
R. Novak
L. Xiao
J. Lee
Y. Bahri
G. Yang
J. Hron
D.A. Abolafia
J. Pennington
J. Sohl-Dickstein

title: Bayesian deep convolutional networks with many channels are Gaussian processes

authors:
S.W. Ober
L. Aitchison

title: Global inducing point variational posteriors for Bayesian neural networks and deep Gaussian processes

authors:
A. Paszke
S. Gross
F. Massa
A. Lerer
J. Bradbury
G. Chanan
T. Killeen
Z. Lin
N. Gimelshein
L. Antiga

title: PyTorch: An imperative style, high-performance deep learning library

authors:
B. Poole
S. Lahiri
M. Raghu
J. Sohl-Dickstein
S. Ganguli

title: Exponential expressivity in deep neural networks through transient chaos

authors:
M. Raghu
B. Poole
J. Kleinberg
S. Ganguli
J. Sohl-Dickstein

title: On the expressive power of deep neural networks

authors:
A. Rahimi
B. Recht

title: Random features for large-scale kernel machines

authors:
C.E. Rasmussen
C. Williams

title: Gaussian processes for machine learning, volume 1

venue: MIT Press,

authors:
A. Romero
N. Ballas
S.E. Kahou
A. Chassang
C. Gatta
Y. Bengio

title: Fitnets: Hints for thin deep nets

authors:
H. Salimbeni
M. Deisenroth

title: Doubly stochastic variational inference for deep Gaussian processes

title: Metric spaces and completely monotone functions

venue: Annals of Mathematics, pages 811–841,

authors:
V. Shankar
A. Fang
W. Guo
S. Fridovich-Keil
J. Ragan-Kelley
L. Schmidt
B. Recht

title: Neural kernels without tangents

title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

venue: IEEE Transactions on Information Theory, 65(2):742–769,

title: Benefits of depth in neural networks

authors:
M. Vladimirova
J. Verbeek
P. Mesejo
J. Arbel

title: Understanding priors in Bayesian neural networks at the unit level

authors:
Y. Wang
M. Brubaker
B. Chaib-Draa
R. Urtasun

title: Sequential inference for deep Gaussian process

title: Regularization matters: Generalization and optimization of neural nets vs their induced kernel

title: Correlation theory of stationary and related random functions

venue: Springer Series in Statistics, New York,

title: Tensor programs I: Wide feedforward or recurrent neural networks of any architecture are gaussian processes

title: Tensor programs II: Neural tangent kernel for any architecture

title: Tensor programs IV: Feature learning in infinite-width neural networks

title: On the power and limitations of random features for understanding neural networks

title: Wide residual networks

title: Exact priors of finite neural networks

heading: 1 Introduction

text:
Research has shown that deeper neural networks tend to be more expressive and efficient than wider networks under a variety of metrics [e.g. 21, 63, 67, 70, 74, 75, 78, 83]. Nevertheless, there is resurgent interest in wide models due in part to empirical successes [e.g. 92] and theoretical analyses of limiting behavior. When randomly initialized to create a distribution over functions, neural networks converge to Gaussian processes (GP) as width increases. This result, first proved for 2-layer networks [69], has been extended to deeper networks [56, 64], convolutional networks [38, 71], and other architectures [50, 88]. A similar limit exists for gradient-trained networks, which behave increasingly like kernel machines under the neural tangent kernel [e.g. 6, 8, 28, 39, 52, 57, 89].
While these limits simplify analyses, there is something unsettling about reducing neural networks to kernel methods. Neal [69, p. 161] describes the GP limit as “disappointing,” noting that “infinite networks do not have hidden units that represent ‘hidden features’. . . often seen [as the] interesting aspect of neural network learning.” Recent work indeed shows that learned hierarchical features can be exponentially more efficient than the fixed shallow representations of kernels [e.g. 4, 5, 8, 11, 13, 21, 41, 42, 60, 91]. At the same time, wider networks can more accurately model complex functions
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
[44]. Thus, wide limits appear to confound opposing phenomenon: increased capacity makes them more expressive, yet the loss of hierarchical features seems to make them less expressive. This may explain the mixed empirical performance of limiting models: outperforming finite width models in some scenarios [e.g. 9, 38, 39, 58], yet falling short on more complex tasks [e.g. 8, 11, 35, 57, 81].
This paper aims to decouple these effects of large width. Our goal is to understand the inductive biases of wide networks, after a network has “sufficient” capacity for a given modeling task. We ask: If we control for the effects of increased capacity, what—if any—value remains in wide networks?
To achieve this control, we note that a typical neural network layer corresponds to a finite basis, where elementwise nonlinearities transform each hidden feature into a single basis function. In order to decouple width from capacity, one could generalize these layers so that each nonlinearity produces any number of basis functions; if each hidden feature gives rise to an infinite and universal basis, then hidden layers would have infinite representational capacity regardless of width. This generalization is in fact a well-studied class of hierarchical models—Deep Gaussian Processes (Deep GP) [19, 24, 26, 27, 30, 32, 46, 79]—where standard neural net layers are replaced with vector-valued Gaussian processes. Indeed, typical neural networks are a degenerate Deep GP subclass [1, 2, 33, 72].
We therefore have a generalization of neural networks where capacity is controlled, from which we can glean insights about conventional networks that have sufficient representational power for a given modeling task. Surprisingly, despite using Gaussian processes as the primary hierarchical component, we prove that Deep GP converge to (single-layer) GP in their infinite width limit (Thm. 1). Troubling implications immediately ensue: large width is strictly detrimental to Deep GP, as the limiting model collapses to a shallower version of itself. We support this theorem with an analysis of neural network and Deep GP posteriors, which become less adaptable as width increases. Specifically, we show that the posterior mean corresponds to a mixture of functions drawn from data-dependent (and thus adaptive) reproducing kernel Hilbert spaces, formalizing the above claim from Neal [69]. As width increases, this mixture collapses to the data-independent kernel of the limiting GP, implying that wider models have less feature learning. Finally, we present a novel tail analysis which indicates that width and depth have opposite effects: depth accentuates non-Gaussianity, sharpening peaks and fattening tails, whereas width increases Gaussianity (Thms. 2 and 3).
Our theoretical results hold for Deep GP and conventional (parametric) neural networks alike. Experiments confirm that—after a model achieves sufficient capacity1—width can become harmful to model fit and performance. For nonparametric Deep GP, a width of 1 or 2 often achieves the best performance. Neural networks—because of their parametric nature—naturally require more hidden units before achieving optimal accuracy. Nevertheless, for Bayesian neural networks and conventional (optimized) neural networks trained with L2 regularization, performance degrades after a certain width. On small datasets (N ≤ 1000) with low dimensionality, we find that models with ≤ 16 hidden units achieve best test set performance. On larger datasets like CIFAR10, this “sweet spot” occurs later (at ≈ 500 hidden units for sufficiently deep models), yet performance degrades beyond this width. We note that these trends do not necessarily hold for models that do not have a probabilistic interpretation—i.e. optimized neural networks trained without (or nearly without) L2 regularization. Nevertheless, our findings suggest that narrower models have better inductive biases, and wide models perform well in spite of —not because of—large width.

heading: 2 Setup

heading: 2.1 Related Work

text:
Effects of width. Works have shown that, given finite parameters, deeper models are more expressive than wider models [63, 67, 74, 75, 83]. Similarly to our work, Aitchison [2] recognises the link between finite neural networks and Deep GP, and argues that finite neural networks have flexibility in the top-layer representation that is absent in the infinite-width limit. Halverson et al. [45] draw a connection to quantum field theory to argue that neural networks become “simpler” near their infinite-width limit. In the non-probabilistic setting, it is worth noting that wide models have been shown to have favorable optimization landscapes [7, 28, 59, 70, 82] and are resistant to overfitting via double descent [12, 20, 68]. Our work controls for these factors by examining nonparametric hierarchical models with exact Bayesian inference, and thus does not disagree with these other works.
1We offer a formal notion of “sufficient capacity” in Appx. B.5.
Infinite width limits have received renewed interest in Bayesian [38, 50, 57, 64, 69, 71, 88] and non-Bayesian [6, 8, 22, 28, 43, 52, 57, 65, 89, 90] settings. Most of these works show that neural networks converge to kernel methods, though recent work suggests that this limiting behavior can be avoided with different parameterizations [e.g. 22, 43, 65, 90]. Similarly to Lee et al. [57], our Deep GP limit analysis sequentially increases the width of each layer, though we hypothesize a similar proof exists where the width of all layers increases simultaneously (akin to [64]).
Deep GP are introduced by Damianou and Lawrence [27]. A large portion of Deep GP research has thus far focused on scalable approximate inference methods [19, 24, 25, 32, 46, 72, 79, 85]. Though prior work has studied tail properties of neural networks [84, 93] and Deep GP with RBF kernels [62], our work is—to the best of our knowlege—the first general result for Deep GP tails. Duvenaud et al. [33] and Dunlop et al. [29] investigate pathological behaviors that arise with depth, while Agrawal et al. [1] note that “bottlenecked” Deep GP have better performance and correlations among predictive tasks. Our work complements these analysis by characterizing the effects of width.
Connections between Deep GP and neural networks. Many researchers have noted connections between neural networks and Deep GP [e.g. 24, 31, 36, 61]. Duvenaud et al. [33] suggest that infinitely-wide neural networks with intermediate bottleneck layers are nonparametric Deep GP. Agrawal et al. [1] formalize this connection, but note that not all Deep GP can be constructed from bottlenecked neural networks (see Appx. E). In contrast to these prior works, we avoid reducing Deep GP to neural networks, and instead reduce neural networks to degenerate Deep GP.

heading: 2.2 A Covariance Perspective on Gaussian Process Limiting Behavior

text:
To decouple the effects of increasing width and capacity, we first prove a new result about GP limits for a more general class of models, including Deep GP as well as typical neural networks. This result forms a necessary foundation for the subsequent theorems that are a main contribution of this work. To begin, note that the proof technique introduced by Neal [69] and extended by others [38, 50, 56, 64, 71, 88] relies on the multivariate central limit theorem, which requires a model with additive structure. Deep GP do not generally decompose in an additive manner, so we establish a more general proof technique. For simplicity, we first present it in the context of neural networks, and then extend it to a more general class of models.
Consider the 2-layer neural network f2(f1(x)), with f1 : RD → RH1 and f2 : RH1 → R:
f1(·) = W>1 (·) + βb1, f2(·) = 1√H1w > 2 σ(·) + βb2. (1)
σ(·) is an elementwise nonlinearity, β is a positive constant, and W1, b1, w2, and b2 are i.i.d. Normal. With randomly initialized parameters, f2(f1(·)) : RD → R is a prior distribution over functions, and this distribution converges to a GP in the infinite width limit [69].
Lemma 1. The neural network defined in Eq. (1) is a Gaussian process if and only if—for any finite set of inputs X = [x1, . . . ,xN ]—the conditional prior covariance Ef2|X,W1,b1 [f2f>2 ] is almost surely equal to the marginal prior covariance Ef2|X[f2f>2 ], where f2 | X , [f2(f1(x1)), . . . , f2(f1(xN ))].
Proof. By definition, f2(f1(·)) is a GP if and only if f2 | X is multivariate Gaussian for any X. From Eq. (1), we have p(f2 | X,W1,b1) = N (0,KW1,b1(X,X)), where [KW1,b1(X,X)]ij = β2+ 1H1σ(W > 1 xi+βb1)
>σ(W>1 xj +βb1) is the appropriate kernel Gram matrix. Using Jensen’s inequality, we have a lower bound on the characteristic function of f2 | X:
E f2|X
[ exp ( it>f2 )] = E
W1,b1
[ E
f2|X,W1,b1
[ exp ( it>f2 )]] (law of total expectation)
= EW1,b1 [ exp ( − 12t >KW1,b1(X,X)t )]
(char. func. of a Gaussian)
≥ exp ( − 12t
> E W1,b1 [KW1,b1(X,X)] t
) . (convexity of exp)
This lower bound happens to be the characteristic function ofN (0,EW1,b1 [KW1,b1(X,X)]). Since exp is strictly convex, the characteristic function of f2 | X equals the Gaussian lower bound ∀t if and only if p(KW1,b1(X,X) |W1,b1) = Ef |X,W1,b1 [f2f>2 ] is a constant with probability 1.
Seeing that 1H1σ(W > 1 xi + βb1) >σ(W>1 xj + βb1) becomes a.s. constant as H1 →∞, Lemma 1 re-establishes the result of Neal [69] (see Appx. E.1). Critically, unlike Neal’s proof, Lemma 1 neither relies on the central limit theorem nor requires f2(f1(·)) to be a neural network; it holds if p(f2 | f1(x1), . . . , f1(xN )) is Gaussian. Therefore, we can generalize it to a larger class of models:
Lemma 2. Let f2(f1(·)) : RD → R be a hierarchical model where f2(·) : RH1 → R is a GP and f1(·) : RD → RH1 is a random vector-valued function (including a multilayer hierarchical model). Then f2(f1(·)) is a GP if and only if Ef2|X,f1(·)[f2f>2 ] = Ef2|X[f2f>2 ] a.s. for all X = [x1, . . . ,xN ].
The covariance perspective from Lemmas 1 and 2 is revealing about GP limits. As Ef2|X,f1(·)[f2f>2 ] converges to Ef2|X[f2f>2 ] the model output becomes less and less dependent on f1(·). In other words, f2(f1(·)) loses its hierarchical nature. We reiterate that Lemma 2 has no requirements about f2(f1(·)) transitioning from a finite to infinite basis, nor does it require f2(f1(·)) to have additive structure. We demonstrate its generality in the next section with surprising—and troubling—implications.

heading: 3 Deep Gaussian Processes Collapse to Shallow Gaussian Processes

text:
Deep GP [19, 26, 27, 79] are hierarchical models where layers f1(·) . . . fL(·) are (vector-valued) GP:
DGP(x) = fL ◦ . . . ◦ f1 (x) , fi(·) = [f (1)i (·), . . . , f (Hi) i (·)], f (j) i (·) i.i.d∼ GP [0, ki(·, ·)] . (2)
Hi is the width of the ith GP layer, and the output dimensions of each fi(·) are independent. By using GP as the primary hierarchical building blocks, Deep GP are generally nonparametric and, assuming the GP layers use universal kernels [66], have infinite representational capacity (see Appx. B.1).
Deep GP versus GP. Deep GP seek to offer more expressivity: conventional single-layer GP—though also nonparametric—are inherently limited by the choice of the prior covariance function [19, 79]. For example, a GP with a RBF covariance is not suitable for data with discontinuities or sharp changes. However, stacking two RBF GP together—f2(f1(·))—can overcome this limitation, since f1(x) can encode a warping of x that “smoothes” the input data for f2(·) (as we will show in Fig. 1). Empirically, Deep GP have been shown to offer much more accurate predictive posteriors than standard GP [e.g. 17, 24, 26, 27, 30, 46, 79].
Deep GP versus neural networks. (Bayesian) feed-forward neural networks are a strict subclass of Deep GP, albeit a degenerate one [2, 61, 72]. The first neural network layer is a GP with a linear kernel, while subsequent layers are GP with the kernel k(z, z′) = β2 + 1Hi−1 ∑Hi−1 i=1 σ(zi) σ(zi). A neural network, unlike other Deep GP, does not have infinite capacity. Put loosely, a single neural network hidden unit corresponds to a single basis, while in general a single Deep GP unit corresponds to a potentially-infinite basis. See [1, 2, 24, 31, 33, 72] and Appx. B.2 for more discussion on this connection. The critical takeaway is that all of our Deep GP results apply to neural networks as well.

heading: 3.1 Wide Deep GP are Gaussian Processes

text:
Having established a model where width does not effect capacity, we now establish what remaining effects width has. Empirical evidence suggests that the choice of width impacts Deep GP predictions [19, 46]. In practice it is common to make Deep GP as wide as comparably-sized neural networks; Salimbeni and Deisenroth [79] for example train Deep GP with ≥ 30 units per layer. Surprisingly, here we prove that—in the limit of infinite width—Deep GP collapse to single-layer Gaussian processes. Our proof relies on the conditional covariance analysis of the previous section. If the GP layers have non-pathological covariance functions2—the Deep GP conditional covariance becomes almost surely constant with width (see Lemma 3, Appx. E). Combining this with Lemma 2:
Theorem 1. Let fL ◦ . . .◦ f1 (x) be a zero-mean Deep GP (Eq. 2), where each layer satisfies Assumptions 1 and 2 (non-pathological prior covariances that scale with dimensionality—see Appx. E.3). Then limHL−1→∞ · · · limH1→∞ fL ◦ . . . ◦ f1 (x) converges in distribution to a (single-layer) GP.
2Any textbook kernel (isotropic kernels, dot product kernels, etc.) or any covariance function with a Fourier-Steiljes representation is “non-pathological;” see Appx. E.3 for formal assumptions.
(See Appx. E for proof.) The implications of Thm. 1 are paradoxical and unsettling. Deep GP are motivated as a more powerful model than standard GP. However, as we make the model wider, we arrive back where we started—a Gaussian process (although one with a different prior covariance).
A neural network gains representational power in its GP limit, transitioning from a finite-basis model to a nonparametric model. The Deep GP limit on the other hand has no additional representational power, since Deep GP are already universal approximators at any width. (Indeed this fact motivates their use as a control.) The only difference between finite and infinite width Deep GP is the prior distribution itself: transitioning from non-Gaussian to Gaussian with increasing width. In the next section, we investigate how this transition affects model performance.

heading: 4 Large Width Limits the Adaptability of Hierarchical Posteriors

text:
Even with Thm. 1 and its troubling suggestions, it is not immediately clear exactly what is lost in the infinite-width limit. Here, we quantify specific differences in the predictive capabilities of narrow versus wide models. In particular, we analyze Deep GP/neural network posterior distributions, rather than focusing on a single model trained through optimization. We show that these posteriors correspond to a mixture of data-dependent adaptable bases; however, as width increases this mixture collapses to the (data-independent) basis of the limiting GP. This result formalizes the often vague notion of feature learning, and demonstrates that it is indeed lost in kernel limits.
Hierarchical posteriors correspond to a data-adaptable bases. Consider the (finite-width) 2- layer Deep GP f2(f1(·)), where k1(·, ·) and k2(·, ·) are the covariance functions of f1(·) and f2(·). Given training data X,y, define F1 , [f1(x1), . . . , f1(xN )] and f2 , [f2(f1(x1)), . . . , f2(f1(xN ))]. Let x∗ be a test input, and let f∗1 and f ∗ 2 equal f1(x
∗) and f2(f1(x∗)) (see Fig. 5 in Appx. B.3 for a graphical model). Crucially, f2 and f∗2 only depend on F1 and f ∗ 1 through the covariances K2(F1,F1), k2(F1, f∗1 ), and k2(f ∗ 1 , f ∗ 1 ) (which we abbreviate as K2, k ∗ 2, and k ∗∗ 2 ):
p(f2 | K2) ∼ N (0,K2) , p(f∗2 | k∗∗2 ,k∗2,K2, f2) ∼ N ( k∗>2 K −1 2 f2, k ∗∗ 2 − k∗>2 K−12 k∗2 ) ,
By D-separation [e.g. 16, Ch. 8], we can factorize the posterior distribution as:
p(f∗2 , f2,K2,k ∗ 2, k ∗∗ 2 | y) = p(f∗2 | f2,K2,k∗2, k∗∗2 ) p(f2 | K2,y) p(K2,k∗2, k∗∗2 | y). (3)
See derivation in Appx. B.3. Applying the factorization in Eq. (3), the posterior mean is:
E f∗2 |y [f∗2 ] = E K2,k∗2 |y
[ E
f2|K2,y
[ k∗>2 K −1 2 f2 ]] = E
K2,k∗2 |y
[ k∗>2
α
K−12 E f2|K2,y
[f2] ]
(4)
= E f1(x∗),f1(x1),...,f1(xN )|y
[∑N i=1 αi k2(f1(xi), f1(x ∗)) ] , (5)
where the second line follows from K2 and k∗2 being deterministic given f1(x ∗), f1(x1), . . ., f1(xN ). The term inside the Eq. (5) expectation is a function from the reproducing kernel Hilbert space (RKHS) defined by k2(f1(·), f1(·)). We can thus interpret this expectation as an infinite mixture of functions from different Hilbert spaces. Because the mixture distribution p(f1(x∗), f1(x1), . . . , f1(xN ) | y) depends on y, Eq. (5) is an adaptive data-dependent mixture of RKHS.
Adaptability is lost in the Gaussian process limit. What happens to Eq. (5) as f2(f1(·)) becomes a Gaussian process in the limit of infinite-width? Recall from Lemma 2 that the conditional prior covariance becomes deterministic as f2(f1(·)) converges to a GP. In other words, the prior and posterior distributions over K2 and k∗2 become atomic: p(K2,k ∗ 2) = p(K2,k ∗ 2 | y) = δ [Klim,k∗lim ], where Klim and k∗lim are shorthand for E[f2f>2 ] and E[f2f∗2 ] respectively. Eq. (4) thus collapses to:
lim H1→∞ E f∗2 |y [f∗2 ] = E δ[Klim,k∗lim]
[ k∗>2 α ] = ∑N i=1 αi klim(xi,x ∗), (6)
which is no longer a mixture of functions from different RKHS. It is instead a function from a single RKHS (that of the limiting GP prior).3 In other words, while Deep GP (and neural networks) perform kernel learning (or feature learning) to adapt to training data, this ability is lost with large width.
Example. Consider a Deep GP with RBF covariances k1(x,x′) = exp ( −‖x− x′‖2/(2D) ) and k2(f1(x), f1(x ′)) = exp ( −‖f1(x)− f1(x′)‖2/(2H1) ) . As we show in Appx. G, this Deep GP converges to a GP with klim(x,x′) = exp(exp(−‖x − x′‖2/(2D)) − 1). Note that this limiting covariance is stationary and is ill-equipped to model the data step in Fig. 1. However, because f1(·) is nonlinear, k2(f1(x), f1(x′)) is nonstationary. Fig. 1 (top left) shows that the width-1 Deep GP posterior accurately models this data. The posterior covariance Ef1(x),f1(x′)|y[k2(f1(x), f1(x′))] (bottom left) features long-range correlations near x = ±1 and short-range correlations near x = 0. As width increases, we lose this nonstationarity and the posterior becomes a worse fit.

heading: 5 The Difference Between Width and Depth: A Tail Analysis

text:
Our work so far has troubling implications for large width. On the other hand, empirical evidence has shown that depth improves Deep GP performance—as it does for neural nets [e.g. 46, 72, 79] (though pathologies can emerge [29, 33]). Through a novel tail analysis, we show that width makes Deep GP priors more Gaussian, while depth makes them less Gaussian. In other words, width and depth have opposite effects on Deep GP tails, results that again also apply to typical neural networks.
Deep GP/neural networks are sharply peaked and heavy tailed. The proof technique used in Lemma 1 can be used to similarly bound the moment generating function of Deep GP marginals:
E f2
[ et >f2 ] = E
F1
[ E
f2|F1
[ et >f2 ]] ≥ exp ( 1
2 t> E F1 [K2(F1,F1)] t
) = E
g∼N (0,Klim)
[ et >g ] , (7)
where Klim=Ef2 [f2f>2 ]=EF1 [K2(F1,F1)]. Generalizing these bounds to deeper models, we have: Theorem 2. Let fL◦. . .◦f1(·) be a zero-mean Deep GP. Given a finite set of inputs X = [x1, . . . ,xN ], define f` = [(f` ◦ . . . ◦ f1(x1)), . . . , (f` ◦ . . . ◦ f1(xN ))] for ` ∈ [1, L], and define Klim = EfL [fLf>L ]. Then, p(fL = 0) ≥ N (g = 0;0,Klim). Theorem 3. Let t ∈ RN . Using the same setup, notation, and assumptions as Thm. 2, the odd moments of t>fL are zero and the even moments larger than 2 are super-Gaussian, i.e. EfL [(t>fL)r] ≥ Eg∼N (0,Klim)[(t>g)r] for all even r ≥ 4. Moreover, if kL(·, ·) is bounded almost everywhere, the moment generating function EfL [exp(t>fL)] exists and is similarly super-Gaussian.
(See Appx. F for proofs.) Thm. 2 states that Deep GP marginals are more sharply peaked than a moment-matched Gaussian, while Thm. 3 states that they are also more heavy tailed.
Increasing depth leads to sharper peaks and heavier tails. To understand how depth affects this tail behavior, we examine the Jensen gap in Eq. (7). Consider a 3-layer Deep GP f3(f2(f1(·))). If we
3To rigorously argue that the infinite-width posterior collapses in this way, we can invoke Proposition 1 from Hron et al. [49]. See Appx. B.4 for details.
extend Eq. (7) to 3-layer models, we see that the Jensen gap cascades:
E F1
[ E
F2|F1
[ exp ( 1
2 t>K3t )]] MGF of 3-layer Deep GP marginal ≥ E F1 [ exp ( 1 2 t> E F2|F1 [K3] t )] MGF of 2-layer Deep GP marginal ≥ exp ( 1 2 t>E F1 [ E F2|F1 [K3] ] t ) MGF ofN (0,EF1 [EF2|F1 [K3]]) ,
where K3 is short for K3(F2(F1(X)),F2(F1(X))). The middle term is the moment generating function of a 2-layer Deep GP marginal (where the second layer has covariance Ef2(·)[k3(f2(·), f2(·))]). The right-most term is the moment generating function of a (single-layer) Gaussian. Generalizing this cascade, we see that deeper models are more heavy-tailed. A similar analysis on the characteristic function shows that the peak at the prior mean also becomes sharper with depth (see Appx. F).
Adding additional layers to a Deep GP will change the model’s prior covariance, and thus the effects of depth cannot solely be explained by a tail analysis [29, 33]. Nevertheless, if we control for this change in covariance, we indeed see that depth leads to heavier tails. In Fig. 2 we compare 2-layer and 3-layer Deep GP. The 3-layer models use GP layers with additively-decomposing RBF covariances, while the 2-layer models use layers constructed to match the 3-layer models’ prior covariance (see Appx. H for construction details). The N = 2 marginal densities for the 3-layer models (bottom row) are more stretched than the 2-layer densities (top row). We further confirm these effects in Appx. D.
Increasing width leads to flatter peaks and Gaussian tails. Conversely, consider what happens when we make the model wider. We define the sequence of increasingly wide 2-layer Deep GP:{
DGP(m)(·) , 1√ m m∑ i=1 f (i) 2 (f (i) 1 (·))
} ,
f (i) 1 (·) i.i.d∼ GP [0, k1(·, ·)] ,
f (i) 2 (·) i.i.d∼ GP [0, k2(·, ·)] . (8)
DGP(m)(·) is a width-m Deep GP, where the second layer decomposes additively over the m dimensions. By linearity of expectation, each model in the sequence shares the same prior covariance: E[DGP(1)(x) DGP(1)(x′)] = E[DGP(2)(x) DGP(2)(x′)] = . . . , klim(x,x′). Though each model has the same marginal covariance, the conditional covariance Ef2|F1 [f2f>2 ] = 1 m ∑m i=1 K2(f (i) 1 , f (i) 1 ) becomes increasingly concentrated around Klim(X,X) as m increases. This consequentially shrinks the Jensen gap in Eq. (7), and so the Deep GP marginals become increasingly Gaussian. We again visualize this effect in Fig. 2, which depicts marginal densities from 2-layer and 3-layer Deep GP of various width (see Appx. H for details). Compared with the limiting GP (right), the width-1 densities (left) appear sharper near [0, 0] and more stretched at the tails. As width increases, the peaks and tails look increasingly Gaussian (see also Fig. 7 in Appx. D). In this sense, width has the opposite effect as depth—deeper marginals are less Gaussian, while wider marginals are more Gaussian.

heading: 6 Experiments

heading: 6.1 Regression with Deep GP and Bayesian Neural Networks

text:
To isolate the effects of width and depth, each experiment compares Deep GP/Bayesian neural networks that share the same first and second prior moments, and the Deep GP models use GP layers with universal kernels. To remove any potential side effects from approximate inference methods, we sample Deep GP/neural network posteriors using NUTS [48] and do not use any stochastic inducing point [46, 79] or finite basis [24] approximations. This inference is costly and scales cubically with N ; therefore, we subsample all training datasets to N ≤ 1000. See Appx. H for experimental details.
Effect of width. We compare 2-layer Deep GP of various width on 6 regression datasets from the UCI dataset repository [10] (see Appx. D for 3-layer results). The first GP layers use a RBF kernel for the prior covariance, while the second layers use a sum of one-dimensional RBF covariance functions. We additionally compare against the limiting (single-layer) GP with the same prior covariance (Lim. GP). For each dataset, we choose hyperparameters that maximize the Lim. GP log marginal likelihood. In Fig. 3 (top row) we see a near-monotonic performance degradation as width increases. The width = 2 optimum may represent the “sweet spot” for Deep GP width, but it may instead be a side-effect of inference difficulties for width = 1 models (see Appx. D for a control experiment). Regardless, as our theory predicts, width is detrimental to Deep GP predictive performance.
We repeat the experiment for 2-layer neural networks (and 3-layer models in Appx. D), where here the Lim. GP corresponds to the arc-cosine kernel [23, 56]. Fig. 3 indicates an optimal width with regards to test set log likelihood, usually between 8− 16 hidden units. We expect this optimum exists (and differs from the Deep GP optimum) because narrow models have too few basis functions for these datasets. Nevertheless, after sufficient capacity, width is harmful to Bayesian neural networks.
Adaptable versus non-adaptable RKHS. One way to measure the “fit” of a kernel k(·, ·) on a regression training dataset X,y is the Gaussian log marginal likelihood logN (y;0,K(X,X)+σ2I), where σ2 is an observational noise parameter [e.g. 77]. To demonstrate how Deep GP/neural network
posteriors correspond to adaptable RKHS mixtures, the bottom row of Fig. 3 plots the “kernel fit” of k2(f1(·), f1(·)) for posterior samples of f1(·) (see Eq. 5). A higher fit corresponds to a model that is better adapted to the dataset X,y. We see that narrower Deep GP almost universally achieve better kernel fit than wider Deep GP, which converge to the same fit as the limiting GP. (Standard deviations, depicted by shaded regions, are generally imperceptible.) Bayesian neural networks achieve best “kernel fit” at 8− 16 hidden units, and then converge to the limiting Deep GP with further width.
Effect of depth, controlling for covariance. Table 1 displays Deep GP test set log likelihood as a function of depth. Again, we isolate the tail effects of depth by ensuring that all models share the same first and second moments. We construct a GP and a 2-layer Deep GP that match the moments of a 3-layer width = 2 Deep GP with RBF covariances, and we use hyperparameters that maximize the limiting GP marginal likelihood for each dataset. Note that computing the limiting covariance of ≥ 3 layer models involves intractable integrals that we approximate with quadrature (see Appx. G). Our findings confirm that—in this controlled setting—depth unlike width improves test set performance.

heading: 6.2 Standard (Optimized, Non-Bayesian) Neural Networks

text:
We now turn to standard (optimized, non-Bayesian) neural networks. While our theoretical results primarily apply to full posteriors over models, our goal is to see if our theory can also be predictive in “real world” neural networks without a Bayesian treatment. There is reason to believe that our theory should be applicable in these settings, since standard neural network training with L2 regularization is equivalent to maximum a posteriori inference with Gaussian priors. To that end, we ensure some correspondence between these experiments and our Bayesian experiments. In particular, we measure the effects of width on networks with fixed values of L2 regularization,4 which corresponds to a fixed prior on neural network parameters. Additionally, models are trained without data augmentation, as data augmentation does not have a probabilistic interpretation [51].
Fig. 4 (left) depicts test set accuracy for increasingly wide models trained on MNIST [55]. Each network is a MLP with 3 layers (i.e. 2 hidden layers). Following the GP-limiting neural network construction in Eq. (1), we scale the outputs of layer ` by 1/ √ H`−1. We measure the effect of width over networks with various L2 regularization constants (10−5, 10−6, 10−7, and 10−8) which respectively correspond to priors of N (0, 2), N (0, 20), N (0, 200), and N (0, 2000) when N = 50,000. We train these sequences on various-sized subsets of the training data (N = 500, N = 5,000, and N = 50,000). From this figure we can observe several phenomena. For larger values of L2 regularization, we see a distinct maximum in accuracy, typically around width ≈ 1,000. For smaller values of L2 regularization, wider models tend to perform better (and indeed, for this dataset/model combination it appears that less regularization tends to be beneficial to overall performance). We would note that these low regularization constants correspond to arguably unreasonable parametric
4In other words, we do not consider the regularization constant to be a hyperparameter that we optimize over for the purposes of these experiments.
priors like N (0, 2000), and so a Bayesian interpretation of these models may not be applicable. In such settings, it is more likely that the interpolation analysis of Belkin et al. [12] is a better model of performance, since this analysis explicitly focuses on the low-regularization setting.
Fig. 4 (right) depicts 8- and 14-layer ResNets [47] trained on the CIFAR-10 dataset [54]. We use the hyperparameters from the original ResNet paper, which have been shown to be efficacious on both narrow and wide variants of ResNet models [92]. (This training procedure uses a L2 coefficient of 10−4, which corresponds to a prior of N (0, 0.2) for each parameter when N = 50,000.) For both depths, we observe that performance is optimal when width is between 500 and 1,000. While it is possible that different hyperparameters may yield different outcomes, these results indeed suggest that large width can adversely affect standard neural networks once sufficient capacity is reached.

heading: 7 Discussion

text:
This paper shows that, across typical neural networks (with L2 regularization), Deep GP, and Bayesian neural networks, large width can be detrimental to model performance.
Even with these results, we can ask when width might be desirable? First, we note that our results analyze exact posteriors or MAP solutions, and does not focus on practical considerations with regards to obtaining these solutions. We do not consider the effect that width might have on approximate inference methods, which are commonly used with Bayesian neural networks and Deep GP in practice [e.g. 18, 34, 79]. For conventional neural networks, poor conditioning and non-convexity make it challenging to obtain a MAP solution. The optimization dynamics—which depend on numerous factors like learning rates, initializations, and choice of optimizer—may be improved by width, as wider models tend to have more favorable optimization landscapes [7, 28, 59, 70, 82]. Consequentially, wider models may obtain better performance due to these practical considerations.
Secondly—as noted in Sec. 6.2—while we notice detrimental effects of width on neural networks with a Bayesian interpretation (i.e. inferring a parameter posterior or optimizing parameters with L2 regularization), we do not see these effects when such an interpretation does not exist (i.e. optimizing parameters with almost no L2 regularization). Our theoretical findings assume that layers are conditionally Gaussian, and different priors may have different effects. We note that much of the preliminary works on NTK assume no explicit regularization during training [28, 52, 57] (with the notable exception of Wei et al. [86]), and so our findings may be at odds with the empirical findings around these models [e.g. 9, 38, 39]. Moreover, recent work has proposed (non-Bayesian) infinite-width constructions that avoid any limiting kernel behavior [e.g. 22, 43, 65, 90], and so our findings would not apply to these models. We emphasize that our results do not conflict with these prior works, but rather reflect a different perspective. The models we study correspond to a Gaussian prior on parameters, and so relaxing this correspondence may lessen the consequences of width that we observe. Nevertheless, our results suggest that the inductive bias of width may be harmful, even if these undesirable effects can be avoided via careful construction.
Finally, it is worth considering when one might still choose a conventional shallow GP over a deep model. An often-touted benefit of Gaussian processes is the ability to encode prior domain knowledge via the choice of covariance function. In Appx. C, we prove that certain prior covariances cannot be expressed by adaptable hierarchical models. For example, a Deep GP that is composed of stationary GP layers cannot model anti-correlations a priori (Thm. 4, Appx. C), whereas (single-layer) stationary GP can have positive and negative prior covariances. Nevertheless, Deep GP are capable of modeling many common covariance functions, including the RBF, Matérn, and rational quadratic kernels. In Appx. C we demonstrate a 2-layer Deep GP construction of any width that is capable of producing prior covariances that match most isotropic kernels (Thm. 5, Appx. C). In other words, a Deep GP can match the first and second moments of most GP, while also offering an adaptable posterior.
Acknowledgments and Disclosure of Funding
We would like to thank Elliott Gordon-Rodriguez for his help with the proofs. This work was supported by the Simons Foundation, McKnight Foundation, the Grossman Center, and the Gatsby Charitable Trust.

title: The Limitations of Large Width in Neural Networks: A Deep Gaussian Process Perspective