Deep networks have recently been shown to be vulnerable to universal perturbations: there exist very small image-agnostic perturbations that cause most natural images to be misclassified by such classifiers. In this paper, we provide a quantitative analysis of the robustness of classifiers to universal perturbations, and draw a formal link between the robustness to universal perturbations, and the geometry of the decision boundary. Specifically, we establish theoretical bounds on the robustness of classifiers under two decision boundary models (flat and curved models). We show in particular that the robustness of deep networks to universal perturbations is driven by a key property of their curvature: there exist shared directions along which the decision boundary of deep networks is systematically positively curved. Under such conditions, we prove the existence of small universal perturbations. Our analysis further provides a novel geometric method for computing universal perturbations, in addition to explaining their properties. Despite the success of deep neural networks in solving complex visual tasks BID11 ; BID15 , these classifiers have recently been shown to be highly vulnerable to perturbations in the input space. In BID24 , state-of-the-art classifiers are empirically shown to be vulnerable to universal perturbations: there exist very small imageagnostic perturbations that cause most natural images to be misclassified. The existence of universal perturbation is further shown in Hendrik BID12 to extend to other visual tasks, such as semantic segmentation. Universal perturbations fundamentally differ from the random noise regime, and exploit essential properties of deep networks to misclassify most natural images with perturbations of very small magnitude. Why are state-of-the-art classifiers highly vulnerable to these specific directions in the input space? What do these directions represent? To answer these questions, we follow a theoretical approach and find the causes of this vulnerability in the geometry of the decision boundaries induced by deep neural networks. For deep networks, we show that the key to answering these questions lies in the existence of shared directions (across different datapoints) along which the decision boundary is highly curved. This establishes fundamental connections between geometry and robustness to universal perturbations, and thereby reveals new properties of the decision boundaries induced by deep networks.Our aim here is to derive an analysis of the vulnerability to universal perturbations in terms of the geometric properties of the boundary. To this end, we introduce two decision boundary models: 1) the locally flat model assumes that the first order linear approximation of the decision boundary holds locally in the vicinity of the natural images, and 2) the locally curved model provides a second order local description of the decision boundary, and takes into account the curvature information. We summarize our contributions as follows:• Under the locally flat decision boundary model, we show that classifiers are vulnerable to universal directions as long as the normals to the decision boundaries in the vicinity of natural images are correlated (i.e., they approximately span a low dimensional space). This result formalizes and proves some of the empirical observations made in BID24 .• Under the locally curved decision boundary model, the robustness to universal perturbations is instead driven by the curvature of the decision boundary; we show that the existence of shared directions along which the decision boundary is positively 1 curved implies the existence of very small universal perturbations.• We show that state-of-the-art deep nets remarkably satisfy the assumption of our theorem derived for the locally curved model: there actually exist shared directions along which the decision boundary of deep neural networks are positively curved. Our theoretical result consequently captures the large vulnerability of state-of-the-art deep networks to universal perturbations.• We finally show that the developed theoretical framework provides a novel (geometric) method for computing universal perturbations, and further explains some of the properties observed in BID24 (e.g., diversity, transferability) regarding the robustness to universal perturbations. In this paper, we analyzed the robustness of classifiers to universal perturbations, under two decision boundary models: Locally flat and curved. We showed that the first are not robust to universal directions, provided the normal vectors in the vicinity of natural images are correlated. While this model explains the vulnerability for e.g., linear classifiers, this model discards the curvature information, which is essential to fully analyze the robustness of deep nets to universal perturbations. The second, classifiers with curved decision boundaries, are instead not robust to universal perturbations, provided the existence of a shared subspace along which the decision boundary is positively curved (for most 7 We used m = 1 in this experiment as the matrix H is prohibitively large for ImageNet. Figure 9 : Diversity of universal perturbations randomly sampled from the subspace S c . The normalized inner product between two perturbations is less than 0.1. directions). We empirically verify this assumption for deep nets. Our analysis hence explains the existence of universal perturbations, and further provides a purely geometric approach for computing such perturbations, in addition to explaining properties of perturbations, such as their diversity.Other authors have focused on the analysis of the robustness properties of SVM classifiers (e.g., BID33 ) and new approaches for constructing robust classifiers (based on robust optimization) Caramanis et al. FORMULA2 ; BID16 . More recently, some have assessed the robustness of deep neural networks to different regimes such as adversarial perturbations BID29 ; BID1 , random noise , and occlusions BID28 BID5 . The robustness of classifiers to adversarial perturbations has been specifically studied in BID29 ; BID8 ; ; BID2 ; BID0 , followed by works to improve the robustness BID20 ; BID10 BID26 ; BID3 , and attempts at explaining the phenomenon in BID8 ; BID6 ; BID30 ; BID31 . This paper however differs from these previous works as we study universal (imageagnostic) perturbations that can fool every image in a dataset, as opposed to image-specific adversarial perturbations that are not universal across datapoints (as shown in BID24 ). Moreover, explanations that hinge on the output of a deep network being well approximated by a linear function of the inputs f (x) = W x + b are inconclusive, as the assumption is violated even for relatively small networks. We show here that it is precisely the large curvature of the decision boundary that causes vulnerability to universal perturbations. Our bounds indeed show an increasing vulnerability with respect to the curvature of the decision boundary, and represent up to our knowledge the first quantitative result showing tight links between robustness and curvature. In addition, we show empirically that the first-order approximation of the decision boundary is not sufficient to explain the high vulnerability to universal perturbations ( Fig. 7 (b) ). Recent works have further proposed new methods for computing universal perturbations Mopuri et al. FORMULA2 ; BID14 ; instead, we focus here on an analysis of the phenomenon of vulnerability to universal perturbations, while also providing a constructive approach to compute universal perturbations leveraging our curvature analysis. Finally, it should be noted that recent works have studied properties of deep networks from a geometric perspective (such as their expressivity BID27 ; BID22 ); our focus is different in this paper as we analyze the robustness with the geometry of the decision boundary.Our analysis hence shows that to construct classifiers that are robust to universal perturbations, it is key to suppress this subspace of shared positive directions, which can possibly be done through regularization of the objective function. This will be the subject of future works.
Analysis of vulnerability of classifiers to universal perturbations and relation to the curvature of the decision boundary. The paper provides an interesting analysis linking the geometry of classifier decision boundaries to small universal adversarial perturbations. This paper discusses universal perturbations - perturbations that can mislead a trained classifier if added to most of input data points. The paper develops models which attempt to explain the existence of universal perturbations which fool neural networks