summaries: This paper discusses per-pixel classification and mask classification for semantic segmentation. It shows that mask classification is sufficiently general to solve semantic and instance segmentation in a unified manner. Thorough experiments are conducted on several benchmarks for both semantic and panoptic segmentation.

summaries: This paper focuses on the problem of semantic segmentation. Traditional semantic segmentation methods mainly adopt the FCN kind of structure and treat the task as per-pixel classification. While in this paper, the author reformulates the task into binary mask prediction and extra-label classification. The proposed method named MaskFormer could be utilized for both semantic segmentation and panoptic segmentation tasks, and the experimental evaluations on different datasets look promising.

summaries: In this paper the authors present a technique to directly predict the mask and class label for semantic and panoptic segmentation. This is different from current state of the aret where per pixel labels are produced which are then process to obtain region masks and labels. The method consists of a backbone encoder which produces an image embedding, whic is fed into the backbon decoder to get pixel level embedding and to the transform decoder, the out of the transformer decode processed by an MLP provides the mask embedding. The mask embeddings and the pixel embeddings are used to get mask prdication. Whereas the class predictions are obtained throught the MLP output.  The method is tested on semantic segmentation datsets and produce comparable or better results on four datasets.

summaries: This paper proposes a transformer-based model, called MaskFormer for semantic segmentation task. MaskFormer treats semantic segmentation as a mask classification problem, and predicts a set of binary masks with the corresponding class labels.  The proposed approach can be easily extended for panoptic segmentaion task. Experimental evaluations for semantic segmentation and panoptic segmentation tasks demonstrate the effectiveness of proposed method.

abstractText: Modern approaches typically formulate semantic segmentation as a per-pixel classification task, while instance-level segmentation is handled with an alternative mask classification. Our key insight: mask classification is sufficiently general to solve both semanticand instance-level segmentation tasks in a unified manner using the exact same model, loss, and training procedure. Following this observation, we propose MaskFormer, a simple mask classification model which predicts a set of binary masks, each associated with a single global class label prediction. Overall, the proposed mask classification-based method simplifies the landscape of effective approaches to semantic and panoptic segmentation tasks and shows excellent empirical results. In particular, we observe that MaskFormer outperforms per-pixel classification baselines when the number of classes is large. Our mask classification-based method outperforms both current state-of-the-art semantic (55.6 mIoU on ADE20K) and panoptic segmentation (52.7 PQ on COCO) models.1

authors:
Pablo Arbeláez
Jordi Pont-Tuset
Jonathan T Barron
Ferran Marques
Jitendra Malik

title: Multiscale combinatorial grouping

venue: In CVPR,

authors:
Holger Caesar
Jasper Uijlings
Vittorio Ferrari

title: COCO-Stuff: Thing and stuff classes in context

venue: In CVPR, 2018

authors:
Joao Carreira
Rui Caseiro
Jorge Batista
Cristian Sminchisescu

title: Semantic segmentation with second-order pooling

venue: In ECCV,

authors:
Joao Carreira
Cristian Sminchisescu

title: CPMC: Automatic object segmentation using constrained parametric min-cuts

authors:
Liang-Chieh Chen
George Papandreou
Iasonas Kokkinos
Kevin Murphy
Alan L Yuille

title: DeepLab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs

authors:
Liang-Chieh Chen
George Papandreou
Florian Schroff
Hartwig Adam

title: Rethinking atrous convolution for semantic image segmentation

authors:
Liang-Chieh Chen
Yukun Zhu
George Papandreou
Florian Schroff
Hartwig Adam

title: Encoder-decoder with atrous separable convolution for semantic image segmentation

venue: In ECCV, 2018

authors:
Bowen Cheng
Liang-Chieh Chen
Yunchao Wei
Yukun Zhu
Zilong Huang
Jinjun Xiong
Thomas S Huang
Wen-Mei Hwu
Honghui Shi

title: SPGNet: Semantic prediction guidance for scene parsing

authors:
Bowen Cheng
Maxwell D Collins
Yukun Zhu
Ting Liu
Thomas S Huang
Hartwig Adam
Liang- Chieh Chen

title: Panoptic-DeepLab: A simple, strong, and fast baseline for bottom-up panoptic segmentation

authors:
Dorin Comaniciu
Peter Meer

title: Robust Analysis of Feature Spaces: Color Image Segmentation

authors:
Marius Cordts
Mohamed Omran
Sebastian Ramos
Timo Rehfeld
Markus Enzweiler
Rodrigo Benenson
Uwe Franke
Stefan Roth
Bernt Schiele

title: The Cityscapes dataset for semantic urban scene understanding

authors:
Jifeng Dai
Kaiming He
Jian Sun

title: Convolutional feature masking for joint object and stuff segmentation

authors:
Alexey Dosovitskiy
Lucas Beyer
Alexander Kolesnikov
Dirk Weissenborn
Xiaohua Zhai
Thomas Unterthiner
Mostafa Dehghani
Matthias Minderer
Georg Heigold
Sylvain Gelly

title: An image is worth 16x16 words: Transformers for image recognition at scale

venue: In ICLR,

authors:
Mark Everingham
SM Ali Eslami
Luc Van Gool
Christopher KI Williams
John Winn
Andrew Zisserman

title: The PASCAL visual object classes challenge: A retrospective

authors:
Jun Fu
Jing Liu
Haijie Tian
Yong Li
Yongjun Bao
Zhiwei Fang
Hanqing Lu

title: Dual attention network for scene segmentation

authors:
Bharath Hariharan
Pablo Arbeláez
Ross Girshick
Jitendra Malik

title: Simultaneous detection and segmentation

authors:
Kaiming He
Georgia Gkioxari
Piotr Dollár
Ross Girshick

title: Mask R-CNN

venue: In ICCV, 2017

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In CVPR, 2016

authors:
Zilong Huang
Xinggang Wang
Lichao Huang
Chang Huang
Yunchao Wei
Wenyu Liu

title: CCNet: Criss-cross attention for semantic segmentation

venue: In ICCV,

authors:
Scott Konishi
Alan Yuille

title: Statistical Cues for Domain Specific Image Segmentation with Performance Analysis

authors:
Tsung-Yi Lin
Piotr Dollár
Ross Girshick
Kaiming He
Bharath Hariharan
Serge Belongie

title: Feature pyramid networks for object detection

authors:
Tsung-Yi Lin
Priya Goyal
Ross Girshick
Kaiming He
Piotr Dollár

title: Focal loss for dense object detection

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C Lawrence Zitnick

title: Microsoft COCO: Common objects in context

authors:
Ze Liu
Yutong Lin
Yue Cao
Han Hu
Yixuan Wei
Zheng Zhang
Stephen Lin
Baining Guo

title: Swin transformer: Hierarchical vision transformer using shifted windows

authors:
Jonathan Long
Evan Shelhamer
Trevor Darrell

title: Fully convolutional networks for semantic segmentation

authors:
Ilya Loshchilov
Frank Hutter

title: Decoupled weight decay regularization

authors:
Fausto Milletari
Nassir Navab
Seyed-Ahmad Ahmadi

title: V-Net: Fully convolutional neural networks for volumetric medical image segmentation

venue: In 3DV,

authors:
Gerhard Neuhold
Tobias Ollmann
Samuel Rota Bulò
Peter Kontschieder

title: The mapillary vistas dataset for semantic understanding of street scenes

authors:
Jianbo Shi
Jitendra Malik

title: Normalized Cuts and Image Segmentation

authors:
Zhi Tian
Chunhua Shen
Hao Chen

title: Conditional convolutions for instance segmentation

authors:
Jasper RR Uijlings
Koen EA Van De Sande
Theo Gevers
Arnold WM Smeulders

title: Selective search for object recognition

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In NeurIPS, 2017

authors:
Huiyu Wang
Yukun Zhu
Hartwig Adam
Alan Yuille
Liang-Chieh Chen

title: MaX-DeepLab: End-to-end panoptic segmentation with mask transformers

authors:
Xiaolong Wang
Ross Girshick
Abhinav Gupta
Kaiming He

title: Non-local neural networks

authors:
Xinlong Wang
Rufeng Zhang
Tao Kong
Lei Li
Chunhua Shen

title: SOLOv2: Dynamic and fast instance segmentation

venue: NeurIPS,

authors:
Yuxin Wu
Alexander Kirillov
Francisco Massa
Wan-Yen Lo
Ross Girshick

title: Detectron2. https: //github.com/facebookresearch/detectron2, 2019

authors:
Tete Xiao
Yingcheng Liu
Bolei Zhou
Yuning Jiang
Jian Sun

title: Unified perceptual parsing for scene understanding

authors:
Yuhui Yuan
Xilin Chen
Jingdong Wang

title: Object-contextual representations for semantic segmentation

authors:
Yuhui Yuan
Lang Huang
Jianyuan Guo
Chao Zhang
Xilin Chen
Jingdong Wang

title: OCNet: Object context for semantic segmentation

authors:
Hengshuang Zhao
Jianping Shi
Xiaojuan Qi
Xiaogang Wang
Jiaya Jia

title: Pyramid scene parsing network

venue: In CVPR, 2017

authors:
Sixiao Zheng
Jiachen Lu
Hengshuang Zhao
Xiatian Zhu
Zekun Luo
Yabiao Wang
Yanwei Fu
Jianfeng Feng
Tao Xiang
Philip HS Torr

title: Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers

authors:
Bolei Zhou
Hang Zhao
Xavier Puig
Sanja Fidler
Adela Barriuso
Antonio Torralba

title: Scene parsing challenge 2016

title: Scene parsing through ADE20K dataset

heading: 1 Introduction

text:
The goal of semantic segmentation is to partition an image into regions with different semantic categories. Starting from Fully Convolutional Networks (FCNs) work of Long et al. [28], most deep learning-based semantic segmentation approaches formulate semantic segmentation as per-pixel classification (Figure 1 left), applying a classification loss to each output pixel [8, 46]. Per-pixel predictions in this formulation naturally partition an image into regions of different classes.
Mask classification is an alternative paradigm that disentangles the image partitioning and classification aspects of segmentation. Instead of classifying each pixel, mask classification-based methods predict a set of binary masks, each associated with a single class prediction (Figure 1 right). The more flexible mask classification dominates the field of instance-level segmentation. Both Mask R-CNN [19] and DETR [3] yield a single class prediction per segment for instance and panoptic segmentation. In contrast, per-pixel classification assumes a static number of outputs and cannot return a variable number of predicted regions/segments, which is required for instance-level tasks.
Our key observation: mask classification is sufficiently general to solve both semantic- and instancelevel segmentation tasks. In fact, before FCN [28], the best performing semantic segmentation methods like O2P [4] and SDS [18] used a mask classification formulation. Given this perspective, a natural question emerges: can a single mask classification model simplify the landscape of effective approaches to semantic- and instance-level segmentation tasks? And can such a mask classification model outperform existing per-pixel classification methods for semantic segmentation?
To address both questions we propose a simple MaskFormer approach that seamlessly converts any existing per-pixel classification model into a mask classification. Using the set prediction mechanism proposed in DETR [3], MaskFormer employs a Transformer decoder [37] to compute a set of pairs,
∗Work partly done during an internship at Facebook AI Research. 1Project page: https://bowenc0221.github.io/maskformer
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
each consisting of a class prediction and a mask embedding vector. The mask embedding vector is used to get the binary mask prediction via a dot product with the per-pixel embedding obtained from an underlying fully-convolutional network. The new model solves both semantic- and instance-level segmentation tasks in a unified manner: no changes to the model, losses, and training procedure are required. Specifically, for semantic and panoptic segmentation tasks alike, MaskFormer is supervised with the same per-pixel binary mask loss and a single classification loss per mask. Finally, we design a simple inference strategy to blend MaskFormer outputs into a task-dependent prediction format.
We evaluate MaskFormer on five semantic segmentation datasets with various numbers of categories: Cityscapes [13] (19 classes), Mapillary Vistas [31] (65 classes), ADE20K [49] (150 classes), COCOStuff-10K [2] (171 classes), and ADE20K-Full [49] (847 classes). While MaskFormer performs on par with per-pixel classification models for Cityscapes, which has a few diverse classes, the new model demonstrates superior performance for datasets with larger vocabulary. We hypothesize that a single class prediction per mask models fine-grained recognition better than per-pixel class predictions. MaskFormer achieves the new state-of-the-art on ADE20K (55.6 mIoU) with Swin-Transformer [27] backbone, outperforming a per-pixel classification model [27] with the same backbone by 2.1 mIoU, while being more efficient (10% reduction in parameters and 40% reduction in FLOPs).
Finally, we study MaskFormer’s ability to solve instance-level tasks using two panoptic segmentation datasets: COCO [26, 22] and ADE20K [49]. MaskFormer outperforms a more complex DETR model [3] with the same backbone and the same post-processing. Moreover, MaskFormer achieves the new state-of-the-art on COCO (52.7 PQ), outperforming prior state-of-the-art [38] by 1.6 PQ. Our experiments highlight MaskFormer’s ability to unify instance- and semantic-level segmentation.

heading: 2 Related Works

text:
Both per-pixel classification and mask classification have been extensively studied for semantic segmentation. In early work, Konishi and Yuille [23] apply per-pixel Bayesian classifiers based on local image statistics. Then, inspired by early works on non-semantic groupings [11, 33], mask classification-based methods became popular demonstrating the best performance in PASCAL VOC challenges [16]. Methods like O2P [4] and CFM [14] have achieved state-of-the-art results by classifying mask proposals [5, 36, 1]. In 2015, FCN [28] extended the idea of per-pixel classification to deep nets, significantly outperforming all prior methods on mIoU (a per-pixel evaluation metric which particularly suits the per-pixel classification formulation of segmentation).
Per-pixel classification became the dominant way for deep-net-based semantic segmentation since the seminal work of Fully Convolutional Networks (FCNs) [28]. Modern semantic segmentation models focus on aggregating long-range context in the final feature map: ASPP [6, 7] uses atrous convolutions with different atrous rates; PPM [46] uses pooling operators with different kernel sizes; DANet [17], OCNet [45], and CCNet [21] use different variants of non-local blocks [39]. Recently, SETR [47] and Segmenter [34] replace traditional convolutional backbones with Vision Transformers (ViT) [15] that capture long-range context starting from the very first layer. However, these concurrent Transformer-based [37] semantic segmentation approaches still use a per-pixel classification
formulation. Note, that our MaskFormer module can convert any per-pixel classification model to the mask classification setting, allowing seamless adoption of advances in per-pixel classification.
Mask classification is commonly used for instance-level segmentation tasks [18, 22]. These tasks require a dynamic number of predictions, making application of per-pixel classification challenging as it assumes a static number of outputs. Omnipresent Mask R-CNN [19] uses a global classifier to classify mask proposals for instance segmentation. DETR [3] further incorporates a Transformer [37] design to handle thing and stuff segmentation simultaneously for panoptic segmentation [22]. However, these mask classification methods require predictions of bounding boxes, which may limit their usage in semantic segmentation. The recently proposed Max-DeepLab [38] removes the dependence on box predictions for panoptic segmentation with conditional convolutions [35, 40]. However, in addition to the main mask classification losses it requires multiple auxiliary losses (i.e., instance discrimination loss, mask-ID cross entropy loss, and the standard per-pixel classification loss).

heading: 3 From Per-Pixel to Mask Classification

text: In this section, we first describe how semantic segmentation can be formulated as either a per-pixel classification or a mask classification problem. Then, we introduce our instantiation of the mask classification model with the help of a Transformer decoder [37]. Finally, we describe simple inference strategies to transform mask classification outputs into task-dependent prediction formats.

heading: 3.1 Per-pixel classification formulation

text:
For per-pixel classification, a segmentation model aims to predict the probability distribution over all possibleK categories for every pixel of anH×W image: y = {pi|pi ∈ ∆K}H·Wi=1 . Here ∆K is theKdimensional probability simplex. Training a per-pixel classification model is straight-forward: given ground truth category labels ygt = {ygti |y gt i ∈ {1, . . . ,K}}H·Wi=1 for every pixel, a per-pixel cross-
entropy (negative log-likelihood) loss is usually applied, i.e., Lpixel-cls(y, ygt) = ∑H·W i=1 − log pi(y gt i ).

heading: 3.2 Mask classification formulation

text:
Mask classification splits the segmentation task into 1) partitioning/grouping the image intoN regions (N does not need to equal K), represented with binary masks {mi|mi ∈ [0, 1]H×W }Ni=1; and 2) associating each region as a whole with some distribution over K categories. To jointly group and classify a segment, i.e., to perform mask classification, we define the desired output z as a set of N probability-mask pairs, i.e., z = {(pi,mi)}Ni=1. In contrast to per-pixel class probability prediction, for mask classification the probability distribution pi ∈ ∆K+1 contains an auxiliary “no object” label (∅) in addition to the K category labels. The ∅ label is predicted for masks that do not correspond to any of the K categories. Note, mask classification allows multiple mask predictions with the same associated class, making it applicable to both semantic- and instance-level segmentation tasks.
To train a mask classification model, a matching σ between the set of predictions z and the set of N gt ground truth segments zgt = {(cgti ,m gt i )|c gt i ∈ {1, . . . ,K},m gt i ∈ {0, 1}H×W }N gt i=1 is required. 2 Here cgti is the ground truth class of the i th ground truth segment. Since the size of prediction set |z| = N and ground truth set |zgt| = N gt generally differ, we assume N ≥ N gt and pad the set of ground truth labels with “no object” tokens ∅ to allow one-to-one matching. For semantic segmentation, a trivial fixed matching is possible if the number of predictionsN matches the number of category labels K. In this case, the ith prediction is matched to a ground truth region with class label i and to ∅ if a region with class label i is not present in the ground truth. In our experiments, we found that a bipartite matching-based assignment demonstrates better results than the fixed matching. Unlike DETR [3] that uses bounding boxes to compute the assignment costs between prediction zi and ground truth z gt j for the matching problem, we directly use class and mask predictions, i.e., −pi(cgtj ) + Lmask(mi,m gt j ), where Lmask is a binary mask loss.
To train model parameters, given a matching, the main mask classification loss Lmask-cls is composed of a cross-entropy classification loss and a binary mask loss Lmask for each predicted segment:
Lmask-cls(z, zgt) = ∑N
j=1
[ − log pσ(j)(cgtj ) + 1cgtj 6=∅Lmask(mσ(j),m gt j ) ] . (1)
2Different mask classification methods utilize various matching rules. For instance, Mask R-CNN [19] uses a heuristic procedure based on anchor boxes and DETR [3] optimizes a bipartite matching between z and zgt.
Note, that most existing mask classification models use auxiliary losses (e.g., a bounding box loss [19, 3] or an instance discrimination loss [38]) in addition to Lmask-cls. In the next section we present a simple mask classification model that allows end-to-end training with Lmask-cls alone.

heading: 3.3 MaskFormer

text:
We now introduce MaskFormer, the new mask classification model, which computes N probabilitymask pairs z = {(pi,mi)}Ni=1. The model contains three modules (see Fig. 2): 1) a pixel-level module that extracts per-pixel embeddings used to generate binary mask predictions; 2) a transformer module, where a stack of Transformer decoder layers [37] computes N per-segment embeddings; and 3) a segmentation module, which generates predictions {(pi,mi)}Ni=1 from these embeddings. During inference, discussed in Sec. 3.4, pi and mi are assembled into the final prediction.
Pixel-level module takes an image of size H ×W as input. A backbone generates a (typically) low-resolution image feature map F ∈ RCF×HS ×WS , where CF is the number of channels and S is the stride of the feature map (CF depends on the specific backbone and we use S = 32 in this work). Then, a pixel decoder gradually upsamples the features to generate per-pixel embeddings Epixel ∈ RCE×H×W , where CE is the embedding dimension. Note, that any per-pixel classificationbased segmentation model fits the pixel-level module design including recent Transformer-based models [34, 47, 27]. MaskFormer seamlessly converts such a model to mask classification.
Transformer module uses the standard Transformer decoder [37] to compute from image features F and N learnable positional embeddings (i.e., queries) its output, i.e., N per-segment embeddings Q ∈ RCQ×N of dimension CQ that encode global information about each segment MaskFormer predicts. Similarly to [3], the decoder yields all predictions in parallel.
Segmentation module applies a linear classifier, followed by a softmax activation, on top of the per-segment embeddings Q to yield class probability predictions {pi ∈ ∆K+1}Ni=1 for each segment. Note, that the classifier predicts an additional “no object” category (∅) in case the embedding does not correspond to any region. For mask prediction, a Multi-Layer Perceptron (MLP) with 2 hidden layers converts the per-segment embeddingsQ to N mask embeddings Emask ∈ RCE×N of dimension CE . Finally, we obtain each binary mask prediction mi ∈ [0, 1]H×W via a dot product between the ith mask embedding and per-pixel embeddings Epixel computed by the pixel-level module. The dot product is followed by a sigmoid activation, i.e., mi[h,w] = sigmoid(Emask[:, i]T · Epixel[:, h, w]). Note, we empirically find it is beneficial to not enforce mask predictions to be mutually exclusive to each other by using a softmax activation. During training, the Lmask-cls loss combines a cross entropy classification loss and a binary mask loss Lmask for each predicted segment. For simplicity we use the same Lmask as DETR [3], i.e., a linear combination of a focal loss [25] and a dice loss [30] multiplied by hyper-parameters λfocal and λdice respectively.

heading: 3.4 Mask-classification inference

text:
First, we present a simple general inference procedure that converts mask classification outputs {(pi,mi)}Ni=1 to either panoptic or semantic segmentation output formats. Then, we describe a semantic inference procedure specifically designed for semantic segmentation. We note, that the specific choice of inference strategy largely depends on the evaluation metric rather than the task.
General inference partitions an image into segments by assigning each pixel [h,w] to one of the N predicted probability-mask pairs via arg maxi:ci 6=∅ pi(ci) ·mi[h,w]. Here ci is the most likely class label ci = arg maxc∈{1,...,K,∅} pi(c) for each probability-mask pair i. Intuitively, this procedure assigns a pixel at location [h,w] to probability-mask pair i only if both the most likely class probability pi(ci) and the mask prediction probability mi[h,w] are high. Pixels assigned to the same probabilitymask pair i form a segment where each pixel is labelled with ci. For semantic segmentation, segments sharing the same category label are merged; whereas for instance-level segmentation tasks, the index i of the probability-mask pair helps to distinguish different instances of the same class. Finally, to reduce false positive rates in panoptic segmentation we follow previous inference strategies [3, 22]. Specifically, we filter out low-confidence predictions prior to inference and remove predicted segments that have large parts of their binary masks (mi > 0.5) occluded by other predictions.
Semantic inference is designed specifically for semantic segmentation and is done via a simple matrix multiplication. We empirically find that marginalization over probability-mask pairs, i.e., arg maxc∈{1,...,K} ∑N i=1 pi(c) ·mi[h,w], yields better results than the hard assignment of each pixel to a probability-mask pair i used in the general inference strategy. The argmax does not include the “no object” category (∅) as standard semantic segmentation requires each output pixel to take a label. Note, this strategy returns a per-pixel class probability ∑N i=1 pi(c) ·mi[h,w]. However, we observe that directly maximizing per-pixel class likelihood leads to poor performance. We hypothesize, that gradients are evenly distributed to every query, which complicates training.

heading: 4 Experiments

text:
We demonstrate that MaskFormer seamlessly unifies semantic- and instance-level segmentation tasks by showing state-of-the-art results on both semantic segmentation and panoptic segmentation datasets. Then, we ablate the MaskFormer design confirming that observed improvements in semantic segmentation indeed stem from the shift from per-pixel classification to mask classification.
Datasets. We study MaskFormer using four widely used semantic segmentation datasets: ADE20K [49] (150 classes) from the SceneParse150 challenge [48], COCO-Stuff-10K [2] (171 classes), Cityscapes [13] (19 classes), and Mapillary Vistas [31] (65 classes). In addition, we use the ADE20K-Full [49] dataset annotated in an open vocabulary setting (we keep 874 classes that are present in both train and validation sets). For panotic segmenation evaluation we use COCO [26, 2, 22] (80 “things” and 53 “stuff” categories) and ADE20K-Panoptic [49, 22] (100 “things” and 50 “stuff” categories). Please see the appendix for detailed descriptions of all used datasets.
Evaluation metrics. For semantic segmentation the standard metric is mIoU (mean Intersection-overUnion) [16], a per-pixel metric that directly corresponds to the per-pixel classification formulation. To better illustrate the difference between segmentation approaches, in our ablations we supplement mIoU with PQSt (PQ stuff) [22], a per-region metric that treats all classes as “stuff” and evaluates each segment equally, irrespective of its size. We report the median of 3 runs for all datasets, except for Cityscapes where we report the median of 5 runs. For panoptic segmentation, we use the standard PQ (panoptic quality) metric [22] and report single run results due to prohibitive training costs.
(a) PerPixelBaseline
𝐾×𝐻×𝑊
per-pixel loss
backbone pixel decoder ou tp ut
(b) PerPixelBaseline+
𝐾×𝐻×𝑊𝐶×𝐻×𝑊
𝐾×𝐶
transformer decoder
ou tp ut
per-pixel loss
backbone pixel
decoder Baseline models. On the right we sketch the used per-pixel classification baselines. The PerPixelBaseline uses the pixel-level module of MaskFormer and directly outputs per-pixel class scores. For a fair comparison, we design PerPixelBaseline+ which adds the transformer module and mask embedding MLP to the PerPixelBaseline. Thus, PerPixelBaseline+ and MaskFormer differ only in the formulation: per-pixel vs. mask classification. Note that these baselines are for ablation and we compare MaskFormer with state-of-the-art per-pixel classification models as well.

heading: 4.1 Implementation details

text:
Backbone. MaskFormer is compatible with any backbone architecture. In our work we use the standard convolution-based ResNet [20] backbones (R50 and R101 with 50 and 101 layers respectively) and recently proposed Transformer-based Swin-Transformer [27] backbones. In addition, we use the R101c model [6] which replaces the first 7× 7 convolution layer of R101 with 3 consecutive 3× 3 convolutions and which is popular in the semantic segmentation community [46, 7, 8, 21, 44, 10].
Pixel decoder. The pixel decoder in Figure 2 can be implemented using any semantic segmentation decoder (e.g., [8–10]). Many per-pixel classification methods use modules like ASPP [6] or PSP [46] to collect and distribute context across locations. The Transformer module attends to all image features, collecting global information to generate class predictions. This setup reduces the need of the per-pixel module for heavy context aggregation. Therefore, for MaskFormer, we design a light-weight pixel decoder based on the popular FPN [24] architecture.
Following FPN, we 2× upsample the low-resolution feature map in the decoder and sum it with the projected feature map of corresponding resolution from the backbone; Projection is done to match channel dimensions of the feature maps with a 1 × 1 convolution layer followed by GroupNorm (GN) [41]. Next, we fuse the summed features with an additional 3× 3 convolution layer followed by GN and ReLU activation. We repeat this process starting with the stride 32 feature map until we obtain a final feature map of stride 4. Finally, we apply a single 1× 1 convolution layer to get the per-pixel embeddings. All feature maps in the pixel decoder have a dimension of 256 channels.
Transformer decoder. We use the same Transformer decoder design as DETR [3]. The N query embeddings are initialized as zero vectors, and we associate each query with a learnable positional encoding. We use 6 Transformer decoder layers with 100 queries by default, and, following DETR, we apply the same loss after each decoder. In our experiments we observe that MaskFormer is competitive for semantic segmentation with a single decoder layer too, whereas for instance-level segmentation multiple layers are necessary to remove duplicates from the final predictions.
Segmentation module. The multi-layer perceptron (MLP) in Figure 2 has 2 hidden layers of 256 channels to predict the mask embeddings Emask, analogously to the box head in DETR. Both per-pixel Epixel and mask Emask embeddings have 256 channels. Loss weights. We use focal loss [25] and dice loss [30] for our mask loss: Lmask(m,mgt) = λfocalLfocal(m,mgt) + λdiceLdice(m,mgt), and set the hyper-parameters to λfocal = 20.0 and λdice = 1.0. Following DETR [3], the weight for the “no object” (∅) in the classification loss is set to 0.1.

heading: 4.2 Training settings

text:
Semantic segmentation. We use Detectron2 [42] and follow the commonly used training settings for each dataset. More specifically, we use AdamW [29] and the poly [6] learning rate schedule with an initial learning rate of 10−4 and a weight decay of 10−4 for ResNet [20] backbones, and an initial learning rate of 6 · 10−5 and a weight decay of 10−2 for Swin-Transformer [27] backbones. Backbones are pre-trained on ImageNet-1K [32] if not stated otherwise. A learning rate multiplier of 0.1 is applied to CNN backbones and 1.0 is applied to Transformer backbones. The standard random scale jittering between 0.5 and 2.0, random horizontal flipping, random cropping as well as random color jittering are used as data augmentation [12]. For the ADE20K dataset, if not stated otherwise, we use a crop size of 512× 512, a batch size of 16 and train all models for 160k iterations. For the ADE20K-Full dataset, we use the same setting as ADE20K except that we train all models for 200k iterations. For the COCO-Stuff-10k dataset, we use a crop size of 640 × 640, a batch size of 32 and train all models for 60k iterations. All models are trained with 8 V100 GPUs. We report both performance of single scale (s.s.) inference and multi-scale (m.s.) inference with horizontal flip and scales of 0.5, 0.75, 1.0, 1.25, 1.5, 1.75. See appendix for Cityscapes and Mapillary Vistas settings.
Panoptic segmentation. We follow exactly the same architecture, loss, and training procedure as we use for semantic segmentation. The only difference is supervision: i.e., category region masks in semantic segmentation vs. object instance masks in panoptic segmentation. We strictly follow the DETR [3] setting to train our model on the COCO panoptic segmentation dataset [22] for a fair comparison. On the ADE20K panoptic segmentation dataset, we follow the semantic segmentation setting but train for longer (720k iterations) and use a larger crop size (640× 640). COCO models are trained using 64 V100 GPUs and ADE20K experiments are trained with 8 V100 GPUs. We use
the general inference (Section 3.4) with the following parameters: we filter out masks with class confidence below 0.8 and set masks whose contribution to the final panoptic segmentation is less than 80% of its mask area to VOID. We report performance of single scale inference.

heading: 4.3 Main results

text:
Semantic segmentation. In Table 1, we compare MaskFormer with state-of-the-art per-pixel classification models for semantic segmentation on the ADE20K val set. With the same standard CNN backbones (e.g., ResNet [20]), MaskFormer outperforms DeepLabV3+ [8] by 1.7 mIoU. MaskFormer is also compatible with recent Vision Transformer [15] backbones (e.g., the Swin Transformer [27]), achieving a new state-of-the-art of 55.6 mIoU, which is 2.1 mIoU better than the prior state-of-theart [27]. Observe that MaskFormer outperforms the best per-pixel classification-based models while having fewer parameters and faster inference time. This result suggests that the mask classification formulation has significant potential for semantic segmentation. See appendix for results on test set.
Beyond ADE20K, we further compare MaskFormer with our baselines on COCO-Stuff-10K, ADE20K-Full as well as Cityscapes in Table 2 and we refer to the appendix for comparison with state-of-the-art methods on these datasets. The improvement of MaskFormer over PerPixelBaseline+ is larger when the number of classes is larger: For Cityscapes, which has only 19 categories, MaskFormer performs similarly well as PerPixelBaseline+; While for ADE20K-Full, which has 847 classes, MaskFormer outperforms PerPixelBaseline+ by 3.5 mIoU.
Although MaskFormer shows no improvement in mIoU for Cityscapes, the PQSt metric increases by 2.9 PQSt. We find MaskFormer performs better in terms of recognition quality (RQSt) while lagging in per-pixel segmentation quality (SQSt) (we refer to the appendix for detailed numbers). This observation suggests that on datasets where class recognition is relatively easy to solve, the main challenge for mask classification-based approaches is pixel-level accuracy (i.e., mask quality).
3It isn’t recommended to compare fps from different papers: speed is measured in different environments. DeepLabV3+ fps are from MMSegmentation [12], and Swin-UperNet fps are from the original paper [27].
Panoptic segmentation. In Table 3, we compare the same exact MaskFormer model with DETR [3] on the COCO panoptic val set. To match the standard DETR design, we add 6 additional Transformer encoder layers after the CNN backbone. Unlike DETR, our model does not predict bounding boxes but instead predicts masks directly. MaskFormer achieves better results while being simpler than DETR. To disentangle the improvements from the model itself and our post-processing inference strategy we run our model following DETR post-processing (MaskFormer (DETR)) and observe that this setup outperforms DETR by 2.2 PQ. Overall, we observe a larger improvement in PQSt compared to PQTh. This suggests that detecting “stuff” with bounding boxes is suboptimal, and therefore, boxbased segmentation models (e.g., Mask R-CNN [19]) do not suit semantic segmentation. MaskFormer also outperforms recently proposed Max-DeepLab [38] without the need of special network design as well as sophisticated auxiliary losses (i.e., instance discrimination loss, mask-ID cross entropy loss, and per-pixel classification loss in [38]). MaskFormer, for the first time, unifies semantic- and instance-level segmentation with the exact same model, loss, and training pipeline.
We further evaluate our model on the panoptic segmentation version of the ADE20K dataset. Our model also achieves state-of-the-art performance. We refer to the appendix for detailed results.

heading: 4.4 Ablation studies

text:
We perform a series of ablation studies of MaskFormer using a single ResNet-50 backbone [20].
Per-pixel vs. mask classification. In Table 4, we verify that the gains demonstrated by MaskFromer come from shifting the paradigm to mask classification. We start by comparing PerPixelBaseline+ and MaskFormer. The models are very similar and there are only 3 differences: 1) per-pixel vs. mask classification used by the models, 2) MaskFormer uses bipartite matching, and 3) the new model uses a combination of focal and dice losses as a mask loss, whereas PerPixelBaseline+ utilizes per-pixel cross entropy loss. First, we rule out the influence of loss differences by training PerPixelBaseline+ with exactly the same losses and observing no improvement. Next, in Table 4a, we compare PerPixelBaseline+ with MaskFormer trained using a fixed matching (MaskFormer-fixed), i.e., N = K and assignment done based on category label indices identically to the per-pixel classification setup. We observe that MaskFormer-fixed is 1.8 mIoU better than the baseline, suggesting that shifting from per-pixel classification to mask classification is indeed the main reason for the gains of MaskFormer. In Table 4b, we further compare MaskFormer-fixed with MaskFormer trained with bipartite matching (MaskFormer-bipartite) and find bipartite matching is not only more flexible (allowing to predict less masks than the total number of categories) but also produces better results.
We further calculate the number of classes which are on average present in a training set image. We find these statistics to be similar across datasets despite the fact that the datasets have different number of total categories: 8.2 classes per image for ADE20K (150 classes), 6.6 classes per image for COCO-Stuff-10K (171 classes) and 9.1 classes per image for ADE20K-Full (847 classes). We hypothesize that each query is able to capture masks from multiple categories.
N um
be ro
fu ni
qu e
cl as
se s
pr ed
ic te
d by
ea ch
qu er
y on
va lid
at io
n se
t 0 20 40 60 80 1000 5
10 15 20 25
(a) ADE20K (150 classes)
0 20 40 60 80 1000 5
10 15 20 25 30 35
(b) COCO-Stuff-10K (171 classes)
0 20 40 60 80 1000 20 40 60 80
100
(c) ADE20K-Full (847 classes) The figure to the right shows the number of unique categories predicted by each query (sorted in descending order) of our MaskFormer model on the validation sets of the corresponding datasets. Interestingly, the number of unique categories per query does not follow a uniform distribution: some queries capture more classes than others. We try to analyze how MaskFormer queries group categories, but we do not observe any obvious pattern: there are queries capturing categories with similar semantics or shapes (e.g., “house” and “building”), but there are also queries capturing completely different categories (e.g., “water” and “sofa”).
Number of Transformer decoder layers. Interestingly, MaskFormer with even a single Transformer decoder layer already performs well for semantic segmentation and achieves better performance than our 6-layer-decoder PerPixelBaseline+. For panoptic segmentation, however, multiple decoder layers are required to achieve competitive performance. Please see the appendix for a detailed discussion.

heading: 5 Discussion

text:
Our main goal is to show that mask classification is a general segmentation paradigm that could be a competitive alternative to per-pixel classification for semantic segmentation. To better understand its potential for segmentation tasks, we focus on exploring mask classification independently of other factors like architecture, loss design, or augmentation strategy. We pick the DETR [3] architecture as our baseline for its simplicity and deliberately make as few architectural changes as possible. Therefore, MaskFormer can be viewed as a “box-free” version of DETR.
In this section, we discuss in detail the differences between MaskFormer and DETR and show how these changes are required to ensure that mask classification performs well. First, to achieve a pure mask classification setting we remove the box prediction head and perform matching between prediction and ground truth segments with masks instead of boxes. Secondly, we replace the computeheavy per-query mask head used in DETR with a more efficient per-image FPN-based head to make end-to-end training without box supervision feasible.
Matching with masks is superior to matching with boxes. We compare MaskFormer models trained using matching with boxes or masks in Table 5. To do box-based matching, we add to MaskFormer an additional box prediction head as in DETR [3]. Observe that MaskFormer, which directly matches with mask predictions, has a clear advantage. We hypothesize that matching with boxes is more ambiguous than matching with masks, especially for stuff categories where completely different masks can have similar boxes as stuff regions often spread over a large area in an image.
MaskFormer mask head reduces computation. Results in Table 5 also show that MaskFormer performs on par with DETR when the same matching strategy is used. This suggests that the difference in mask head designs between the models does not significantly influence the prediction quality. The new head, however, has significantly lower computational and memory costs in comparison with the original mask head used in DETR. In MaskFormer, we first upsample image features to get highresolution per-pixel embeddings and directly generate binary mask predictions at a high-resolution. Note, that the per-pixel embeddings from the upsampling module (i.e., pixel decoder) are shared among all queries. In contrast, DETR first generates low-resolution attention maps and applies an independent upsampling module to each query. Thus, the mask head in DETR is N times more computationally expensive than the mask head in MaskFormer (where N is the number of queries).

heading: 6 Conclusion

text:
The paradigm discrepancy between semantic- and instance-level segmentation results in entirely different models for each task, hindering development of image segmentation as a whole. We show that a simple mask classification model can outperform state-of-the-art per-pixel classification models, especially in the presence of large number of categories. Our model also remains competitive for panoptic segmentation, without a need to change model architecture, losses, or training procedure. We hope this unification spurs a joint effort across semantic- and instance-level segmentation tasks.
Acknowledgments and Disclosure of Funding
We thank Ross Girshick for insightful comments and suggestions. Work of UIUC authors Bowen Cheng and Alexander G. Schwing was supported in part by NSF under Grant #1718221, 2008387, 2045586, 2106825, MRI #1725729, NIFA award 2020-67021-32799 and Cisco Systems Inc. (Gift Award CG 1377144 - thanks for access to Arcetri).

title: Per-Pixel Classification is Not All You Need for Semantic Segmentation


summaries: The paper studies adversarial examples in random depth-2 ReLU networks.  They consider depth-2 networks, where the first layer is drawn from a normal distribution such that the norms of the weights vectors are roughly 1, and the second layer is drawn from the uniform distribution on {-1/\sqrt{k},1/\sqrt{k}} where k is the width of the network. They assume that k is at most sub-exponential in the input dimension, and is bounded below by some polylogarithmic expression. For an input x on the sphere of radius \sqrt{d} the output of the network is w.h.p. O(1) (the input x is fixed, and the probability is over the choice of the network). The authors show that there is w.h.p. \delta with ||\delta||=O(1) such that sign(f(x)) \neq sign(f(x+\delta)). Moreover, such \delta can be found with a single gradient step. Thus, although the inputs are of size \sqrt{d}, there is w.h.p. a perturbation of size O(1) that changes the sign of the output. They prove the result for both smooth and ReLU activations. Finally, they validate the results empirically, and also demonstrate that ש similar phenomenon occurs in deeper networks.  Daniely and Schacham [2020] showed that such a property holds in ReLU networks where the sizes d_1,…,d_t  of the layers (where d_1 is the input dimension) are such that for every j we have d_{j+1} = o(d_j) and d_t = \omega(1). For the special case of depth-2 networks it required width k=o(d). Thus, the improvement here w.r.t. k is exponential.  The proofs roughly follow the following steps. First, they show an O(1) upper bound on f(x) and an \Omega(1) lower bound on ||\nabla f(x)||. Then, they bound the variation of the gradient near x. Finally, they use standard arguments to bound f(x-\eta \nabla f(x)) for an appropriate \eta. The proofs of these steps for the case of the ReLU activation is different from the case of smooth activations, and the proofs for the ReLU activation with small k is different from the case of large k.

summaries: The paper studies the phenomenon of adversarial examples for random two-layer networks with ReLU or smooth activations. It is shown that one step of gradient descent yields adversarial examples (i.e., a switching of the sign of the network output) with high probability, under a much milder condition on the number of neurons compared to previous work, i.e. sub-exponential in the dimension instead of sub-linear for Daniely and Schacham [2020]. The proof is based on characterizing the landscape of the network function at different scales, showing that at relatively small "mesoscopic" scale of perturbations (o(sqrt(d)),  but still O(1)), the gradient is close to constant while being Omega(1), making it easy to find an adversarial example with a single gradient step. Some experiments are provided to illustrate the theory, and to illustrate how the phenomenon extends to multiple layers.

summaries: The authors consider the existence of adversarial examples in neural networks trained by gradient descent.  They demonstrate that for two layer networks, one gradient update following random initialization can find adversarial examples.  Their results extend previous work by Daniely and Schacham to more general settings (for two layer networks) and rely upon a different suite of techniques.

summaries: The authors prove that two-layer neural networks can be perturbed adversarially at a fixed data point and at random initialization (with high probability), i.e.\ for a neural network $f$ with randomly initialized parameters and a data point $x$, there exists a small perturbation $\delta = O(1)$ such that $|f(x)| = \Omega(1)$, but $f(x+\delta)\cdot f(x) < 0$. The result holds for a wide range of widths and activation functions. They present numerical evidence for their theoretical claims.

abstractText: Daniely and Schacham [2020] recently showed that gradient descent finds adversarial examples on random undercomplete two-layers ReLU neural networks. The term “undercomplete” refers to the fact that their proof only holds when the number of neurons is a vanishing fraction of the ambient dimension. We extend their result to the overcomplete case, where the number of neurons is larger than the dimension (yet also subexponential in the dimension). In fact we prove that a single step of gradient descent suffices. We also show this result for any subexponential width random neural network with smooth activation function.

authors:
Zeyuan Allen-Zhu
Yuanzhi Li

title: Feature purification: How adversarial training performs robust deep learning

venue: arXiv preprint arXiv:2005.10190,

authors:
Anish Athalye
Nicholas Carlini
David Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

venue: In International Conference on Machine Learning,

authors:
Gérard Ben Arous
Eliran Subag
Ofer Zeitouni

title: Geometry and temperature chaos in mixed spherical spin glasses at low temperature: the perturbative regime

venue: Communications on Pure and Applied Mathematics,

authors:
Stéphane Boucheron
Gábor Lugosi
Pascal Massart

title: Concentration inequalities: A nonasymptotic theory of independence

venue: Oxford university press,

authors:
Ronen Eldan
Dan Mikulincer
Tselil Schramm

title: Non-asymptotic approximations of neural networks by gaussian processes

venue: arXiv preprint arXiv:2102.08668,

authors:
Ian Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: In International Conference on Learning Representations,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

authors:
Michael Mitzenmacher
Eli Upfal

title: Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Omar Fawzi
Pascal Frossard

title: Universal adversarial perturbations

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Jonathan Uesato
Pascal Frossard

title: Robustness via curvature regularization, and vice versa

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition

authors:
Nicolas Papernot
Patrick McDaniel
Ian Goodfellow
Somesh Jha
Z Berkay Celik
Ananthram Swami

title: Practical black-box attacks against machine learning

venue: In Proceedings of the 2017 ACM on Asia conference on computer and communications security,

authors:
Chongli Qin
James Martens
Sven Gowal
Dilip Krishnan
Krishnamurthy Dvijotham
Alhussein Fawzi
Soham De
Robert Stanforth
Pushmeet Kohli

title: Adversarial robustness through local linearization

venue: In Advances in Neural Information Processing Systems,

authors:
Adi Shamir
Itay Safran
Eyal Ronen
Orr Dunkelman

title: A simple explanation for the existence of adversarial examples with small hamming distance

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

title: Introduction to the non-asymptotic analysis of random matrices

venue: In Compressed Sensing: Theory and Practice. Cambridge University Prteess,

title: High-dimensional probability. Cambridge Series in Statistical and Probabilistic Mathematics

title: High-dimensional statistics: A non-asymptotic viewpoint

heading: 1 Introduction

text:
We study the random two-layers neural network model, f : Rd ! R defined by
f(x) = 1p k
kX
`=1
a` (w` · x) , (1)
where : R ! R is a fixed non-linearity, the weight vectors w` 2 Rd are i.i.d. from a Gaussian N 0, 1
d Id (so they are roughly unit norm vectors), and the coefficients a` 2 R are independent from the weight vectors and i.i.d. uniformly distributed in { 1,+1}. With this parametrization, the central limit theorem says that, for x 2 p d · Sd 1 (so that w` · x ⇠ N (0, 1)) and large width k, the distribution of f(x) is approximately a centered Gaussian with variance EX⇠N (0,1)[ (X)2].
Our goal is to study the concept of adversarial examples in this random model. We say that 2 Rd is an adversarial perturbation at x 2 Rd if k k ⌧ kxk and sign(f(x)) 6= sign(f(x + )). In this case, we call x+ an adversarial example. Our main result is that, while |f(x)| = O(1) with high probability, a single gradient step on f (i.e., a perturbation of the form = ⌘rf(x) for some ⌘ 2 R) suffices to find such adversarial examples, with roughly k k ' kxkp
d = 1. Note, here that gradients
are taken with respect to the input to the network as opposed to the weights of the network. We prove this statement for networks of subexponential width (e.g., k ⌧ exp(o(d))) with both smooth and ReLU activation functions. We first state our result for smooth activation functions in the following theorem. Theorem 1. Let 2 (0, 1) and be non-constant, Lipschitz and with Lipschitz derivative. There exists constants C1, C2, C3, C4 depending on such that the following holds true. Assume k
⇤Canada CIFAR AI Chair
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: C1 log

text:
3(1/ ) and d C2 log(k/ ) log(1/ ), and let ⌘ 2 R such that |⌘| = C3
p log(1/ ) krf(x)k2 and
sign(⌘) = sign(f(x)). Then, with probability at least 1 , one has:
sign(f(x)) 6= sign(f(x+ ⌘rf(x))) .
Moreover we have k⌘rf(x)k  C4 p log(1/ ).
Note that our proof of Theorem 1 in Section 2 easily gives explicit values for C1, C2, C3, C4. Also note that by re-arranging the constraint on d in Theorem 1 and setting = 1/poly(d), the subexponential width condition is of the form k ⌧ exp(o(d)). Our second main result establishes similar behavior for the non-smooth ReLU activation unit. Theorem 2. Let 2 (0, 1) and (t) = max(0, t). There exist constants C1, C2, C3, C4, C5 such that the following holds true. Assume
C1 log 6(d) log(1/ )  k, C2 log3(d) log(1/ )  d, C3 log4(k) log(1/ )
d
log(d)
and let ⌘ 2 R such that |⌘| = C4 p log(1/ )
krf(x)k2 and sign(⌘) = sign(f(x)). Then, with probability at least 1 , one has: sign(f(x)) 6= sign(f(x+ ⌘rf(x))) . Moreover, we have k⌘rf(x)k  C5 p log(1/ ).
As before, note that the subexponential condition on the width in the above Theorem is of the form k ⌧ exp(d0.24). In fact by modifying a bit the proof we can get a condition of the form k ⌧ exp(d⇢) for any ⇢ < 1/2, but for the sake of clarity we only prove the weaker version stated above. The proof for the ReLU activation is broken into two separate cases focusing on the overlapping regimes:
Case 1: k & d log2(d) and Case 2: log6(d) log(1/ ) . k . d log3 d, as the proofs for the two settings use distinct arguments. The proof for the first regime is similar to the proof for Theorem 1 while the second uses a refinement of an argument by Daniely and Schacham [2020]. These arguments are carried out in Section 3. We would like to note that our results and corresponding proofs are extendible to the setting where a` are drawn from a normal distribution with minor modifications. We include the simpler setting with Bernoulli activations in the last layer for the sake of conceptual clarity. Intuitively, the strong concentration (and anti-concentration) properties of the normal distribution coupled with a conditioning argument on the magnitudes of the weights in the final layer yield similar results for gaussian setting as well. Additionally, due to the scale invariance of the ReLU activation function, our results also hold true for any distribution over x as long as P {x = 0} = 0 and for smooth activations when P n kxk = ⇥( p d) o = 1. Finally, our results also
hold when a bias unit is introduced; in this setting, we simply project our perturbation onto the ((d 1)-dimensional) subspace of perturbations which leave the bias unit unchanged.

heading: 1.1 Related works

text:
The existence of adversarial examples in neural network architectures was first evidenced in the seminal paper of Szegedy et al. [2014], where the authors found adversarial examples by using the L-BFGS optimization procedure. Shortly after this work, it was hypothesized in Goodfellow et al. [2015] that the existence of adversarial examples stems from an excessive “linearity” of neural network models. This hypothesis was experimentally confirmed by showing that a single step of gradient descent suffices to find adversarial perturbations (the so-called fast gradient sign method -FGSM). Our theorems can be thought of as a theoretical confirmation of the hypothesis in Goodfellow et al. [2015]. In fact, as explained in Section 1.2, our proofs proceed exactly by showing that “most” two-layers neural networks behave “mostly” linearly over “vast” regions of input space.
We note that not all networks are susceptible to one-step gradient attacks to find adversarial examples. Indeed, in Goodfellow et al. [2015], it was shown that adversarial training can be used to build networks that are somewhat robust to one-step gradient attacks. Interestingly, Madry et al. [2018] showed that such models remain susceptible to multi-steps gradient attacks, and empirically demonstrated that better robustness can be achieved with adversarial training using multi-steps gradient
attacks. Understanding this phenomenon theoretically remains a challenge, see for example AllenZhu and Li [2020] for a proposed approach, and Moosavi-Dezfooli et al. [2019], Qin et al. [2019] for discussion/algorithmic consequences of the relation with the phenomenon of gradient obfuscation (Papernot et al. [2017], Athalye et al. [2018]).
Our work is a direct follow-up of Daniely and Schacham [2020] (which itself follows Shamir et al. [2019]). Daniely and Schacham prove that multi-steps gradient descent finds adversarial examples for ReLU random networks of the form (1), as long as the number of neurons is much smaller than the dimension (i.e., k = o(d)). They explicitly conjecture that this condition is not necessary, and indeed we exponentially improve it in Theorem 2 (see below for a discussion of k exponential in the dimension). We note that Daniely and Schacham went beyond two-layers neural networks, and conjectured (and proved for shrinking layers) that gradient descent finds adversarial examples on random multi-layers neural networks. We give some experimental confirmation of this multi-layer conjecture in Section 4.
The ultra-wide case k = exp(⌦(d)) remains open. This exponential size case seems of a different nature than the polynomial size we tackle here, at least for the ReLU activation function. In particular, it is likely that the behavior with exponential width would be closely tied to the actual limit case k = +1, where the random model (1) yields a Gaussian process. Namely, for k = +1, f is a Gaussian process indexed by the sphere (say if we restrict to inputs x 2 p d · Sd 1), with f(x) ⇠ N (0,EX⇠N (0,1)[ (X)]) and E[f(x)f(y)] = EX,Y⇠N (0,1):E[XY ]=x·y[ (X) (Y )]. For example if the activation function is a Hermite polynomial of degree p, then f would be a spherical p-spin glass model. This polynomial case is particularly well-understood, and in fact the landscape we describe below in Section 1.2 was already described in this case by Ben Arous et al. [2020] (in particular Corollary 59) indicating that adversarial examples would likely continue to persist in the ultra-wide setting. It would be interesting to see if the p-spin glass landscape literature can be extended to non-polynomial activation functions, and to a finite (but possibly exponential in d) k. A step in this latter direction was recently taken in Eldan et al. [2021], where convergence rates to the Gaussian process limit where given both for polynomial activations and for the ReLU. Finally we note that for a smooth activation it might be that there is a more direct argument to remove the subexponential width condition in Theorem 1 (in technical terms, the proof of Proposition 2 could leverage a better argument than our naive upper bound on Lip( )).
Finally, we note that, in practice, it has been found that there exists “universal” adversarial perturbations that generalize across both inputs and neural networks, Moosavi-Dezfooli et al. [2017]. For the case of ReLU activation (Theorem 2), we could in fact prove our result by replacing the gradient step with a step in the direction P k
`=1 a`w`, which is indeed a direction independent of the input x, thus proving the existence of “universal” perturbations (generalizing across inputs) for our model.

heading: 1.2 The landscape of random two-layers neural networks

text:
For a smooth non-linearity , we have
rf(x) = 1p k
kX
`=1
a`w` 0(w` · x) and r2f(x) = 1p k
kX
`=1
a`w`w > ` 00(w` · x) .
We already claimed in the introduction that, with high probability the value of f(x) was bounded:
Upper-Bounded Value : |f(x)| = O(1) . (2) We alluded to the CLT for this claim, but it is also easy to guess it intuitively by noting that:
E[f(x)2] = E
2
41 k
kX
`,`0=1
a`a`0 (w` · x) (w`0 · x)
3
5 = EX⇠N (0,1)[ (X)2] ,
as E[a`a`0 ] = 1{` = `0}. The formal proof of (2) (and all other claims we make here) will eventually be a simple application of the classical Bernstein concentration inequality. Similarly, it is easy to see that (noticing that E[krf(x)k2] = EX⇠N (0,1)[ 0(X)2]), with high probability, the norm of the gradient of f(x) is bounded below (note that we can also show that it is bounded above).
Lower-Bounded Gradient : krf(x)k = ⌦(1) . (3)
A slightly more difficult calculation, although classical too, is that
Upper-Bounded Hessian : kr2f(x)kop = eO ✓
1p d
◆ . (4)
Indeed one can simply note that, for any u 2 Sd 1, u>r2f(x)u = 1p k
P k
`=1 a`(w` · u)2 00(w` · x) is approximately distributed as a centered Gaussian with variance (through a heuristic application of the asymptotic central limit theorem):
EW,Z⇠N (0,1):E[WZ]= x·up d "✓ Wp d ◆4 00 (Z)2 # ,
so that with probability at least 1 one can expect u>r2f(x)u to be of order p log(1/ )
d , and thus
by taking a union bound over a discretization of the sphere Sd 1, one can show inequality (4). In fact, interestingly, one can even hope that (4) holds true for an entire ball around x: with appropriate smoothness over (say C2,1 smoothness), this could be obtained by another union bound over a second discretization of a d-dimensional ball. In other words, we can expect with high probability:
8x 2 Rd : kxk = poly(d), one has kr2f(x)kop = eO ✓
1p d
◆ . (5)
Equations (2), (3), and (5) paint a rather clear geometric picture. There are essentially two scales around a fixed x 2 p d · Sd 1: The macroscopic scale, where one considers a perturbation x + with k k = ⌦( p d), and the mesoscopic scale where k k = o( p d) (we use this term because for the ReLU network there will also be a microscopic scale, with k k = o(1)). At the macroscopic scale the landscape of f might be very complicated, but our crucial observation is that the picture at the mesoscopic scale is dramatically simpler. Namely, at the mesoscopic scale, the function f is essentially linear, since one has (thanks to (3) and (5))
Approximate Linearity : krf(x) rf(x+ )k = o(krf(x)k), 8 : k k = o( p d) . (6)
Moreover, since the height of the function is at most a constant (by (2)) and the norm of the gradient is constant, it suffices to step at a constant distance in the direction of the gradient (or negative gradient) to change the sign of f . Assuming without any loss of generality that f(x) > 0, we combine (2), (3), and (6) using a standard descent lemma (Lemma 3):
f(x ⌘rf(x))  f(x)|{z} O(1) by (2) ⌘ krf(x)k| {z } ⌦(1) by (3) ⇣ krf(x)k| {z } ⌦(1) by (3)
sup k k krf(x)k⌘ krf(x) rf(x+ )k | {z } o(1) by (4) or (6)
⌘ (7)
 C1 C2⌘ < 0 (for C1/C2 < ⌘ < C3 p d) (8)
where C1, C2 and C3 are constants that do not depend on k and d. In words: a single step of gradient descent (or ascent) with a O(1) step-size suffices to find an adversarial example, and moreover the adversarial perturbation satisfies k k = O(1) = O(kxk/ p d).

heading: 1.3 Proof strategy

text:
The starting point of the proof for both the smooth and ReLU case is to show (2) and (3), which we essentially do below in Section 1.4. In the smooth case, one could then prove formally (4) and conclude as indicated in the last paragraph of Section 1.2. Of course, (4) is simply ill-defined for the ReLU case, so one has to take a different route. Instead, we propose to directly prove (6), that is we study the difference of gradients at the mesoscopic scale. Using that khk = supv2Sd 1 v · h, we thus need to control (for some R = o( p d)):
sup 2Rd:k kR krf(x) rf(x+ )k = sup v2Sd 1,
2Rd:k kR
1p k
kX
`=1
a`(w` ·v)( 0(w` ·x) 0(w` · (x+ ))) .
(9)
We execute this strategy first for the smooth case in Section 2. We then prove the ReLU case in Section 3, where we face an extraneous difficulty since the gradient is not Lipschitz at very small scale, which introduces a third scale (the microscopic scale) that has to be dealt with differently. Technically, this issue appears when we try to move from the discretization over v and in (9) to the whole space (a so-called "-net argument).

heading: 1.4 Scaling of value and gradient

text:
Here we show how to prove (2) and (3) (in fact, for our purpose, we only need the one-sided inequality krf(x)k = ⌦(1)) under very mild conditions on which will be satisfied for both ReLU and smooth activations. We will repeatedly use Bernstein’s inequality which we restate here for convenience (see e.g., Theorem 2.10 in Boucheron et al. [2013]): Theorem 3 (Bernstein’s inequality). Let (X`) be i.i.d. centered random variables such that for all integers q 2, E[|X`|q]  q!2 2 c q 2 for fixed , c > 0. Then, with probability at least 1 :
kX
`=1
X`  p 2 2k log(1/ ) + c log(1/ ) . (10)
We will also use repeatedly that EX⇠N (0,1)[|X|q]  (q 1)!!  q!2 , as well as the following concentration of 2 random variables (see e.g., (2.19) in Wainwright [2019]): let X1, . . . , Xk be i.i.d. standard Gaussians, then with probability at least 1 , one has:
kX
`=1
X 2 ` k
 4 p k log(2/ ) . (11)
We can now proceed to our various results. Lemma 1 (Bounded Value). Assume that there exists , c > 0 such that for all integers q 2, EX⇠N (0,1)[| (X)|q]  q!2 2 c q 2 . Then with probability at least 1 one has
|f(x)|  p 2 2 log(1/ ) +
c log(1/ )p k .
Proof sketch. Since 1p k
P k
`=1 a` (w` · x), we use Bernstein’s inequality on X` = a` (w` · x).
Lemma 2 (Lower-Bounded Gradient). Let be differentiable almost everywhere, and assume that there exists 0 , c
0 > 0 such that for all integers q 2, EX⇠N (0,1)[| 0(X)|2q]  q!2 02 c 0q 2 . Then
with probability at least 1 ,
krf(x)k EX⇠N (0,1)[| 0(X)|2]
r 2 02 log(2/ )
k +
c 0 log(2/ )
k
!!1/2 1 5 r log(4/ )
d
! .
Proof sketch. Let P = Id xx > d be the projection on the orthogonal complement of the span of x. We have krf(x)k kPrf(x)k = k 1p k P k `=1 Pa`w` 0(w` · x)k where a`Pw` is independent of w` · x and is distributed as N 0, 1
d Id 1 ). We conclude by conditioning on the values (w` · x)`2[k]
and using the concentration results (10) and (11).

heading: 2 Smooth Non-Linearity (Theorem 1)

text:
In this section, we consider a 1-Lipschitz and L-smooth activation function, that is for all s, t 2 R,
| (s) (t)|  |s t| and | 0(s) 0(t)|  L|s t| . (12)
We also assume (0) = 0 and denote c2 = EX⇠N (0,1)[( 0(X))2] which we assume to be non-zero (that is is not a constant function).
Proposition 1 (Upper-Bounded Value and Lower-Bounded Gradient). Under the above assumptions, one has with probability at least 1 ,
|f(x)|
s
2 log
✓ 1
◆ 0
BB@1 +
vuut log ⇣ 2 ⌘
k
1
CCA
and krf(x)k
0
BB@c 2
vuut2 log ⇣ 4 ⌘
k
0
BB@1 +
vuut log ⇣ 4 ⌘
k
1
CCA
1
CCA
1/20
BB@1 5
vuut log ⇣ 8 ⌘
d
1
CCA .
Particularly, there exists C > 0 such that for k C log(2/ ) and d C log(8/ ) we have
|f(x)|  2 p log(1/ ) and krf(x)k c /2 . (13)
Proof. With (12) we have | (X)|  |X| and thus in Lemma 1 we can take = c = 1 which yields the first claimed equation. For the second equation we use that | 0(X)|  1 (since is 1-Lipschitz) and thus, in Lemma 2, we can also take 0 = c0 = 1 yielding the second claimed equation.
Next, we need to control (9) where we use crucially the smoothness of the activation function. Proposition 2 (Bounded Variations). Let R 1. With probability at least 1 one has
sup 2Rd : k kR
krf(x) rf(x+ )k  20RL r log(Rk/ )
d + log(1/ )p k
! .
Particularly, for any c > 0, there exists C1, C2 such that if k C1R2log2(1/ ) and d C2R
2 log(Rk/ ) then sup
2Rd : k kR krf(x) rf(x+ )k  c . (14)
Proof sketch. Our plan is to use the fact that khk = supv2Sd 1 v · h . Thus, we first show, by using Bernstein’s inequality on X` = a`L (w` · v)(
0(w` · x) 0(w` · (x+ )), that if we fix 2 Rd such that k k  R and v 2 Sd 1, then with probability at least 1 one has:
(v, ) := hrf(x) rf(x+ ), vi = Lp k
kX
`=1
Xl  4RL
d
p log(1/ ) 1 +
r log(1/ )
k
! .
Let ⌦ := {(v, ) : kvk = 1, k k  R} and N" be an "-net over ⌦ with " = 1/k. By a union bound over N" (whose size is at most (10kR)2d [Vershynin, 2018, Corollary 4.2.13]), we obtain with probability at least 1 :
sup (v, )2⌦ (v, )  sup (v, )2N" (v, ) + sup (v, ),(v0, 0)2⌦:kv v0k+k 0k"
| (v, ) (v0, 0)|
 4RL d
p 2d log(Rk) + log(1/ ) 1 +
r 2d log(Rk) + log(1/ )
k
! + Lip( )
k .
Then we show that the variations of can be upper-bounded by a RL times a 2 random variable and use (11) to show that with probability at least 1 ,
Lip( )  RL p k + 4
r log(1/ )
d
! .
Finally we can turn to the proof of Theorem 1. Let us first recall this theorem.
Theorem 1. Let 2 (0, 1) and be non-constant, Lipschitz and with Lipschtiz derivative. There exists constants C1, C2, C3, C4 depending on such that the following holds true. Assume k C1 log3(1/ ) and d C2 log(k/ ) log(1/ ), and let ⌘ 2 R such that |⌘| = C3 p log(1/ )krf(x)k 2 and sign(⌘) = sign(f(x)). Then with probability at least 1 one
has: sign(f(x)) 6= sign(f(x+ ⌘rf(x))) . Moreover we have k⌘rf(x)k  C4 p log(1/ ).
Proof. We make the following claims which hold with probability at least 1 . Without any loss of generality we can assume that f(x) > 0, we will use a standard descent lemma (Lemma 3) and the previous propositions to get that,
f(x ⌘rf(x))  f(x)|{z} O(1) by (13) ⌘ krf(x)k| {z } ⌦(1) by (13) ⇣ krf(x)k| {z } ⌦(1) by (13)
sup k k krf(x)k⌘ krf(x) rf(x+ )k | {z } o(1) by (14)
⌘ . (15)
Formally, let us set ⌘ = 32 c2 krf(x)k2
p log(1/ ), R = 64
c3
p log(1/ ), k C1R2 log2(1/ ) and d
C2R 2 log(Rk/ ) where C1 and C2 are large enough such that (13) and (14) are valid with c = c 4 . By Proposition 1 we have that krf(x)k c /2 and ⌘krf(x)k2 = 32c2 p log(1/ ) 16 c2 |f(x)|.
Moreover, Proposition 2 shows that for all such that k k  |⌘|krf(x)k  64 c3
p log(1/ ) = R, we
thus have krf(x) rf(x+ )k  c := c 4 . Consequently,
f(x ⌘rf(x))  f(x) ⌘krf(x)k ⇣ c
2 c 4
⌘  f(x) ⌘ c 2
8  f(x) . (16)
Thus, with a single gradient step of size at most R = 64 c3
p log(1/ ), we switched the sign of f .

heading: 3 ReLU Non-Linearity (Theorem 2)

text:
In this section, we consider the ReLU non-linearity (t) = max(0, t). We start by showing that f(x) is upper bounded and that krf(x)k is lower-bounded. Proposition 3 (Upper-Bounded Value and Lower-Bounded Gradient). With probability at least 1 ,
|f(x)|  p 2 log(2/ ) 1 +
r log(2/ )
k
!
and krf(x)k 1 2 r 2 log(4/ ) k 1 + r log(1/ ) k !!1/2 1 5 r log(4/ ) d ! .
Particularly, there exists C > 0 such that for k C log(1/ ) and d C log(4/ ) we have
|f(x)|  2 p log(2/ ) and krf(x)k 1
4 . (17)
Proof. In Lemma 1 and Lemma 2, we can take = c = 0 = c0 = 1 (since | (X)|  |X| and | 0(X)|  1), which concludes the proof.
Now we split the control of the gradient variation into two cases: the large width case (Cd log2 d . k) and the small width case (log6(d) log(1/ ) . k . d log3 d). Proposition 4. (Bounded Variations – Large Width Case) Let 1  R  p d/2, p k 52 and
d log(1/ ). Then, with probability at least 1 , one has
sup 2Rd : k kR
krf(x) rf(x+ )k  20 R log2(Rk)
r log d
d
!1/4 + 40 r d
k log(Rk) .
Particularly, for any c > 0, there exists C1, C2 such that if C1d log 2(Rk)  k and C2 log4(Rk)R2
d
log(d) , then we have,
sup 2Rd : k kR
krf(x) rf(x+ )k  c . (18)
Proof sketch. In the smooth case (Proposition 2) we did so by using crucially the smoothness of the activation function. Here, instead of smoothness, we will use that only few activations can change when you make microscopic move (i.e., between x+ and x+ 0 with k 0k = o(1)). The key observation that for any such that k k  R,
P(sign(w` · x) 6= sign(w` · (x+ )))  R r 2 log(d)
d +
1 d . (19)
We can then use this result to bound the variation of rf(x) along a fixed direction. If we fix 2 Rd such that k k  R (with R 1) and v 2 Sd 1, then with probability at least 1 one has:
(v, ) := hrf(x) rf(x+ ), vi = 1p k
kX
`=1
Xl  2 q log( 1 )
d
✓ 2R q
log(d) d
◆ 1 4
+
q log( 1 )
k
! .
This inequality is proven via Bernstein’s inequality on X` := a`(w` ·v)( 0(w` ·x) 0(w` · (x+ ))) where we use (19) to prove
E[|X`|q]  p E[|w` · v|2q]⇥ P(sign(w` · x) 6= sign(w` · (x+ )))  q!
2 c q 2 ⇥ 2, (20)
with = 2p d ⇥ ✓ 2R q log(d) d ◆1/4 and c = 2p d .
Then, similarly as in the proof of Proposition 2, we use a covering argument (but this time with an "-Net of size " = R 4/3k 4) to show that,
sup (v, )2⌦ (v, )  sup (v, )2N" (v, ) + sup (v, ),(v0, 0)2⌦:kv v0k+k 0k"
| (v, ) (v0, 0)|
 2 r 10d log(Rk) + log(2/ )
d
0
@ 2R
r log(d)
d
!1/4 + r 10d log(Rk) + log(2/ )
k
1
A
+ sup (v, ),(v0, 0)2⌦:kv v0k+k 0k"
| (v, ) (v0, 0)| . (21)
By using 2 concentration, it is easy to see that with probability at least 1 :
| ( , v) ( , v0)|  kv v0k
s
k + 4k
r log(k/ )
d . (22)
By using (19) we are able to show that with probability 1 for any (v, ) 2 N" there is at most 4d different activated neurons between (v, ) and (v, 0) and thus by applying a concentration result of Lipschitz function of Gaussians we get,
| ( , v) ( 0, v)|  18 r d
k
r log 4k + log 8/
d . (23)
Combining (21), (22), and (23), we get
sup 2Rd : k kR
krf(x) rf(x+ )k  20 R log2(Rk)
r log d
d
!1/4 + 40 r d
k log(Rk) .
Proposition 5 (Bounded Variations – Small Width Case). Let 20 log3 d · log 1/  k  d log3 d and d 20 · log3 d · log 1/ . Then, with probability at least 1 , we have:
sup 2Rd,k k p k
log6 d
krf(x) rf(x+ )k  60 log d .
Proof sketch. In the small width regime we assume 20 log3 d · log 1/  k  d log3 d. The idea of the proof is to control the operator norm of W (where f(x) = 1p
k a > (W>x)) as well as the
number of neurons with a too small activation. With high probability, we show that we have,
kWk  3 · 1 +
r 10(k + log 1/ )
d
! , # ⇢ i : |hwi, xi|  1
log3 d
 2 · k
log3 d .
Thus, uniformly on n y : kx yk  p k
log6 d
o the cardinal of Ty := {i : sgnhwi, xi 6= sgnhwi, yi} is
uppper-bounded: |Ty|  300k/ log3 d := B . (24) We can conclude the proof by using an union bound and a concentration inequality on Gaussians.
krf(x) rf(y)k = 1p k
X
`2T a`w`  supA⇢[k] |A|B
1p k
X
`2T a`w`
 r B
k
0
@1 +
s B log k + log 4
d
1
A .
We can now prove our final result. Theorem 2. Let 2 (0, 1) and (t) = max(0, t). There exist constants C1, C2, C3, C4, C5 such that the following holds true. Assume
C1 log 6(d) log(1/ )  k, C2 log3(d) log(1/ )  d, C3 log4(k) log(1/ )
d
log(d) ,
and let ⌘ 2 R such that |⌘| = C4 p log(1/ )
krf(x)k2 and sign(⌘) = sign(f(x)). Then with probability at least 1 one has: sign(f(x)) 6= sign(f(x+ ⌘rf(x))) . Moreover we have k⌘rf(x)k  C5 p log(1/ ).
Proof. The proof is the same as for Theorem 1 using Proposition 3 instead of Proposition 1 and Proposition 4 or Proposition 5 replacing Proposition 2.

heading: 4 Experiments

text:
Setting. To verify our theoretical findings, we run some experiments to measure empirically the probability of finding an adversarial example in the direction rf(x). More precisely, we take a random point x of norm p d and initialize a network using the procedure described in Section 12. We then find the smallest ⌘ such that a gradient step ⌘rf(x) changes the sign of the function. ⌘ is of the opposite sign of f(x) and we limit our search to |⌘| < 20. We explore various values of d and k, as well as deeper networks with L = 1 through L = 6 hidden layers. All hidden layers are of width k. For our experiments, we used ReLU activation units and the standard deviations reported in Figure 1 are computed over 100 random network initializations for each choice of architecture and 100 random input points for each such initialization.
Results. Figure 2a shows the average of the smallest ⌘ required to switch the sign of the function. We note that the average only includes cases where an ⌘ was indeed found. Figure 2b shows the gradient norm in x (all cases included). As we see, both the smallest ⌘ and the gradient norm are approximately constant both in d and in k. This finding also holds for deeper networks (see Appendix D). In Figure 1, we show the fraction of examples (out of 10, 000 samples) whose sign is switched. We see that with L = 1 and values of d and k larger than 50, 100% of samples are switched. This confirms our theoretical results. Once again, we observe the same statement holds for deeper networks. The values of d and k at which 100% switching is reached appears to grow with L
3. Additionally, we track the value of the smallest ⌘ required to switch the sign of the function, and the gradient norm w.r.t x. Both are approximately constant in d and in k. This finding also holds for deeper networks (see Appendix D for the curves).
2We also conducted experiments with a gaussian initialization for the last layer in place of the Bernoulli initialization from Section 1 and obtained qualitatively similar results.
3Due to GPU memory limitations, k could not reach 1,000,000 for deeper networks.

heading: Acknowledgment

text: We thank Mark Sellke for pointing out to us the reference Ben Arous et al. [2020], and Peter Bartlett for several discussions on this problem.

heading: 5 Disclosure of Funding and Competing Interests

text: GG research is supported by the Canada CIFAR AI Chair Program and an IVADO grant. YC gratefully acknowledges the support of the NSF through grants DMS-2023505 and DMS-2031883, the Simons Foundation through award #814639, and Microsoft through the BAIR Open Research Commons. We declare no competing interests.

title: A single gradient step finds adversarial examples on random two-layers neural networks