summaries: This paper introduces a neural architecture search method called S3 that first searches the search space before identifying good architectures from the discovered search space.  The authors focus on applying S3 to vision transformers and design a search space modeled after ViT.  They evaluate S3 discovered architectures on various computer vision tasks and show good performance on image classification, object detection, and semantic segmentation.  This work applies NAS to the vision transformer architecture. Besides searching the architectures, it also automatically adjusts the search space guided by the E-T error that combines the error distribution and top model errors to evaluate the quality of different choices in a search dimension. By fitting a linear function to approximate the E-T error, the new search space is updated through a simple formula. They used the supernet to efficiently compute the E-T errors, and use evolutionary search to search for the best algorithm in a given search space. The discovered architecture is shown to be competitive to the state-of-the-art models, and also generalize to other vision tasks.  This paper proposes a method for searching the search space of vision. The authors propose decomposing the search space by the search dimensions and evaluating them with the proposed E-T error to explore the optimal search space. Then the new subspace is formulated as Equation (8). The results reported in this paper have achieved state-of-the-art results. This work propose to first search for the search space for transformers and then applies once-for-all NAS methods to search for architectures within the searched search space. In particular, the work proposes an E-T error metric to evaluate the quality of the search spaces. From the results of the whole search process, this work also summarizes some design guidelines for vision transformers. The experiments are extensive and they show the superiority of the proposed search method. 
abstractText: Vision Transformer has shown great visual representation power in substantial vision tasks such as recognition and detection, and thus been attracting fast-growing efforts on manually designing more effective architectures. In this paper, we propose to use neural architecture search to automate this process, by searching not only the architecture but also the search space. The central idea is to gradually evolve different search dimensions guided by their E-T Error computed using a weight-sharing supernet. Moreover, we provide design guidelines of general vision transformers with extensive analysis according to the space searching process, which could promote the understanding of vision transformer. Remarkably, the searched models, named S3 (short for Searching the Search Space), from the searched space achieve superior performance to recently proposed models, such as Swin, DeiT and ViT, when evaluated on ImageNet. The effectiveness of S3 is also illustrated on object detection, semantic segmentation and visual question answering, demonstrating its generality to downstream vision and vision-language tasks. Code and models will be available at here.
authors.name: Minghao Chen
authors.name: Kan Wu
authors.name: Bolin Ni
authors.name: Houwen Peng
authors.name: Bei Liu
authors.name: Jianlong Fu
authors.name: Hongyang Chao
authors.name: Haibin Ling
references.authors: Andrew Brock Theodore Lim James M Ritchie Nick Weston
references.title: Smash: one-shot model architecture search through hypernetworks
references.venue: In ICLR,
references.authors: Han Cai Chuang Gan Tianzhe Wang Zhekai Zhang Song Han
references.title: Once for all: Train one network and specialize it for efficient deployment
references.venue: In ICLR,
references.authors: Han Cai Ligeng Zhu Song Han
references.title: Proxylessnas: Direct neural architecture search on target task and hardware
references.venue: ICLR, 2018
references.authors: Nicolas Carion Francisco Massa Gabriel Synnaeve Nicolas Usunier Alexander Kirillov Sergey Zagoruyko
references.title: End-to-end object detection with transformers
references.venue: In ECCV,
references.authors: Mark Chen Alec Radford Rewon Child Jeffrey Wu Heewoo Jun David Luan Ilya Sutskever
references.title: Generative pretraining from pixels
references.venue: In International Conference on Machine Learning,
references.authors: Minghao Chen Houwen Peng Jianlong Fu Haibin Ling
references.title: Autoformer: Searching transformers for visual recognition
references.authors: Xin Chen Lingxi Xie Jun Wu Qi Tian
references.title: Progressive differentiable architecture search: Bridging the depth gap between search and evaluation
references.venue: In ICCV,
references.authors: Yuanzheng Ci Chen Lin Ming Sun Boyu Chen Hongwen Zhang Wanli Ouyang
references.title: Evolving search space for neural architecture search
references.venue: arXiv preprint arXiv:2011.10904,
references.authors: Jia Deng Wei Dong Richard Socher Li-Jia Li Kai Li Li Fei-Fei
references.title: Imagenet: A large-scale hierarchical image database
references.venue: In CVPR,
references.authors: Alexey Dosovitskiy Lucas Beyer Alexander Kolesnikov Dirk Weissenborn Xiaohua Zhai Thomas Unterthiner Mostafa Dehghani Matthias Minderer Georg Heigold Sylvain Gelly
references.title: An image is worth 16x16 words: Transformers for image recognition at scale
references.venue: ICLR, 2021
references.authors: Thomas Elsken Jan Hendrik Metzen Frank Hutter
references.title: Neural architecture search: A survey
references.venue: J. Mach. Learn. Res.,
references.authors: Zichao Guo Xiangyu Zhang Haoyuan Mu Wen Heng Zechun Liu Yichen Wei Jian Sun
references.title: Single path one-shot neural architecture search with uniform sampling
references.venue: ECCV, 2020
references.authors: Kai Han Yunhe Wang Hanting Chen Xinghao Chen Jianyuan Guo Zhenhua Liu Yehui Tang An Xiao Chunjing Xu Yixing Xu
references.title: A survey on visual transformer
references.venue: arXiv preprint arXiv:2012.12556,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In CVPR, 2016
references.authors: Byeongho Heo Sangdoo Yun Dongyoon Han Sanghyuk Chun Junsuk Choe Seong Joon Oh
references.title: Rethinking spatial dimensions of vision transformers
references.venue: arXiv preprint arXiv:2103.16302,
references.authors: Andrew Howard Mark Sandler Grace Chu Liang-Chieh Chen Bo Chen Mingxing Tan Weijun Wang Yukun Zhu Ruoming Pang Vijay Vasudevan
references.title: Searching for mobilenetv3
references.venue: In ICCV,
references.authors: Yiming Hu Yuding Liang Zichao Guo Ruosi Wan Xiangyu Zhang Yichen Wei Qingyi Gu Jian Sun
references.title: Angle-based search space shrinking for neural architecture
references.authors: Zhicheng Huang Zhaoyang Zeng Yupan Huang Bei Liu Dongmei Fu Jianlong Fu
references.title: Seeing out of the box: End-to-end pre-training for vision-language representation learning
references.venue: In CVPR,
references.authors: Sergey Ioffe Christian Szegedy
references.title: Batch normalization: Accelerating deep network training by reducing internal covariate shift
references.venue: In ICML,
references.authors: Salman Khan Muzammal Naseer Munawar Hayat Syed Waqas Zamir Fahad Shahbaz Khan Mubarak Shah
references.title: Transformers in vision: A survey
references.venue: arXiv preprint arXiv:2101.01169,
references.authors: Changlin Li Tao Tang Guangrun Wang Jiefeng Peng Bing Wang Xiaodan Liang Xiaojun Chang
references.title: Bossnas: Exploring hybrid cnn-transformers with block-wisely self-supervised neural architecture search
references.venue: arXiv preprint arXiv:2103.12424,
references.authors: Liam Li Ameet Talwalkar
references.title: Random search and reproducibility for neural architecture search
references.venue: In UAI,
references.authors: Xiang Li Chen Lin Chuming Li Ming Sun Wei Wu Junjie Yan Wanli Ouyang
references.title: Improving one-shot nas by suppressing the posterior fading
references.venue: In CVPR,
references.authors: Tsung-Yi Lin Michael Maire Serge Belongie James Hays Pietro Perona Deva Ramanan Piotr Dollár C Lawrence Zitnick
references.title: Microsoft coco: Common objects in context
references.venue: In ECCV,
references.authors: Chenxi Liu Barret Zoph Maxim Neumann Jonathon Shlens Wei Hua Li-Jia Li Li Fei-Fei Alan Yuille Jonathan Huang Kevin Murphy
references.title: Progressive neural architecture search
references.venue: In ECCV,
references.authors: Hanxiao Liu Karen Simonyan Yiming Yang
references.title: DARTS: Differentiable architecture search
references.venue: In ICLR,
references.authors: Ze Liu Yutong Lin Yue Cao Han Hu Yixuan Wei Zheng Zhang Stephen Lin Baining Guo
references.title: Swin transformer: Hierarchical vision transformer using shifted windows
references.venue: arXiv preprint arXiv:2103.14030,
references.authors: Ilya Loshchilov Frank Hutter
references.title: Decoupled weight decay regularization
references.venue: In ICLR, 2019
references.authors: Niv Nayman Asaf Noy Tal Ridnik Itamar Friedman Rong Jin Lihi Zelnik
references.title: Xnas: Neural architecture search with expert advice
references.venue: In NeurIPS,
references.authors: Asaf Noy Niv Nayman Tal Ridnik Nadav Zamir Sivan Doveh Itamar Friedman Raja Giryes Lihi Zelnik
references.title: Asap: Architecture search, anneal and prune
references.venue: In AISTATS,
references.authors: Zizheng Pan Bohan Zhuang Jing Liu Haoyu He Jianfei Cai
references.title: Scalable visual transformers with hierarchical pooling
references.venue: arXiv preprint arXiv:2103.10619,
references.authors: Houwen Peng Hao Du Hongyuan Yu Qi Li Jing Liao Jianlong Fu
references.title: Cream of the crop: Distilling prioritized paths for one-shot neural architecture
references.venue: search. NeurIPS,
references.authors: Juan-Manuel Pérez-Rúa Moez Baccouche Stephane Pateux
references.title: Efficient progressive neural architecture search
references.venue: In BMVC,
references.authors: Hieu Pham Melody Guan Barret Zoph Quoc Le Jeff Dean
references.title: Efficient neural architecture search via parameters sharing
references.venue: In ICML,
references.authors: Ilija Radosavovic Raj Prateek Kosaraju Ross Girshick Kaiming He Piotr Dollár
references.title: Designing network design spaces
references.venue: In CVPR,
references.authors: Esteban Real Alok Aggarwal Yanping Huang Quoc V Le
references.title: Regularized evolution for image classifier architecture search
references.venue: In AAAI,
references.authors: David So Quoc Le Chen Liang
references.title: The evolved transformer
references.venue: In International Conference on Machine Learning. PMLR,
references.authors: Aravind Srinivas Tsung-Yi Lin Niki Parmar Jonathon Shlens Pieter Abbeel Ashish Vaswani
references.title: Bottleneck transformers for visual recognition
references.venue: arXiv preprint arXiv:2101.11605,
references.authors: Mingxing Tan Quoc V. Le
references.title: Efficientnet: Rethinking model scaling for convolutional neural networks
references.venue: In ICML, 2019
references.authors: Hugo Touvron Matthieu Cord Matthijs Douze Francisco Massa Alexandre Sablayrolles Herv’e J’egou
references.title: Training data-efficient image transformers & distillation through attention
references.venue: arXiv preprint arXiv:2012.12877,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In NeurIPS,
references.authors: Dilin Wang Meng Li Chengyue Gong Vikas Chandra
references.title: Attentivenas: Improving neural architecture search via attentive sampling
references.venue: In CVPR,
references.authors: Hanrui Wang Zhanghao Wu Zhijian Liu Han Cai Ligeng Zhu Chuang Gan Song Han
references.title: Hat: Hardware-aware transformers for efficient natural language processing
references.venue: In ACL,
references.authors: Wenhai Wang Enze Xie Xiang Li Deng-Ping Fan Kaitao Song Ding Liang Tong Lu Ping Luo Ling Shao
references.title: Pyramid vision transformer: A versatile backbone for dense prediction without convolutions
references.venue: arXiv preprint arXiv:2102.12122,
references.authors: Bichen Wu Xiaoliang Dai Peizhao Zhang Yanghan Wang Fei Sun Yiming Wu Yuandong Tian Peter Vajda Yangqing Jia Kurt Keutzer
references.title: Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search
references.venue: In CVPR,
references.authors: Kan Wu Houwen Peng Minghao Chen Jianlong Fu Hongyang Chao
references.title: Rethinking and improving relative position encoding for vision transformer
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV),
references.authors: Lingxi Xie Alan Yuille
references.title: Genetic cnn
references.venue: In ICCV,
references.authors: Saining Xie Ross Girshick Piotr Dollár Zhuowen Tu Kaiming He
references.title: Aggregated residual transformations for deep neural networks
references.venue: In CVPR,
references.authors: Yuhui Xu Lingxi Xie Xiaopeng Zhang Xin Chen Guo-Jun Qi Qi Tian Hongkai Xiong
references.title: PC-DARTS: Partial channel connections for memory-efficient architecture search
references.venue: In ICLR,
references.authors: Antoine Yang Pedro M Esperança Fabio M Carlucci
references.title: Nas evaluation is frustratingly hard
references.venue: In ICLR,
references.authors: Shan You Tao Huang Mingmin Yang Fei Wang Chen Qian Changshui Zhang
references.title: Greedynas: Towards fast one-shot nas with greedy supernet
references.venue: In CVPR,
references.authors: Jiahui Yu Pengchong Jin Hanxiao Liu Gabriel Bender Pieter-Jan Kindermans Mingxing Tan Thomas Huang Xiaodan Song Ruoming Pang Quoc Le
references.title: Bignas: Scaling up neural architecture search with big single-stage models
references.venue: NeurIPS,
references.authors: Li Yuan Yunpeng Chen Tao Wang Weihao Yu Yujun Shi Francis EH Tay Jiashi Feng Shuicheng Yan
references.title: Tokens-to-token vit: Training vision transformers from scratch on imagenet
references.venue: arXiv preprint arXiv:2101.11986,
references.authors: Peng Zhang Yash Goyal Douglas Summers-Stay Dhruv Batra Devi Parikh. Yin Yang
references.title: Balancing and answering binary visual questions
references.venue: In CVPR,
references.authors: Sixiao Zheng Jiachen Lu Hengshuang Zhao Xiatian Zhu Zekun Luo Yabiao Wang Yanwei Fu Jianfeng Feng Tao Xiang Philip HS Torr
references.title: Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers
references.venue: arXiv preprint arXiv:2012.15840,
references.authors: Bolei Zhou Hang Zhao Xavier Puig Sanja Fidler Adela Barriuso Antonio Torralba
references.title: Scene parsing through ade20k dataset
references.venue: In CVPR,
references.authors: Barret Zoph Quoc V Le
references.title: Neural architecture search with reinforcement learning
references.venue: ICLR, 2016
sections.heading: 1 Introduction
sections.text: Vision transformer recently has drawn great attention in computer vision because of its high model capability and superior potentials in capturing long-range dependencies. Building on top of transformers [41], modern state-of-the-art models, such as ViT [10] and DeiT [40], are able to achieve competitive performance on image classification and downstream vision tasks [13, 20] compared to CNN models. There are fast-growing efforts on manually designing more effective architectures to further unveil the power of vision transformer [27, 53, 15].
  Neural architecture search (NAS) as a powerful technique for automating the design of networks has shown its superiority to manual design [58, 39]. For NAS methods, search space is crucial because it determines the performance bounds of architectures during the search. It has been observed that the improvement of search space induced a favorable impact on the performance of many state-of-the-art models [2, 16, 50]. Researchers have devoted ample efforts to the design of CNN space [45, 12, 42]. However, limited attention is paid to Transformer counterparts, leading to the dilemma of search space design when finding more effective and efficient transformer architectures.
  In this paper, we propose to Search the Search Space (S3) by automatically refining the main changeable dimensions of transformer architectures. In particular, we try to answer the following two key questions: 1) How to effectively and efficiently measure a specific search space? 2) How to automatically change a defective search space to a good one without human prior knowledge?
  For the first question, we propose a new measurement called E-T Error for search space quality estimation and utilize a once-for-all supernet for effective and efficient computing. Specifically, the “E” part in the E-T error is similar to the error empirical distribution function used in [35] focusing on
  ∗Equal contributions. Work done when Minghao, Kan, Bolin are interns of MSRA. †Corresponding author.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  the overall quality, while the “T” part considers the quality of top-tier architectures in a search space. In contrast to [35] that trains each subnet for only a few epochs, we train a once-for-all supernet with AutoFormer [6] to obtain a large amount of well-trained subnets, providing a more reliable proxy for performance estimation.
  For the second question, as shown in Fig. 1 we decompose the search space by multiple dimensions, including depth, embedding dimension, MLP ratio, window size, number of heads and Q-K-V dimension, and progressively evolve each dimension to compose a better space. Particularly, we use linear parameterization to model the tendencies of different dimensions so as to guide the search.
  In addition, we analyze the search process of search space and provide some interesting observations and design guidelines: 1) The third stage is the most important one and increasing its number of blocks leads to performance improvement. 2) Shallow layers should use a small window size while deep layers should use a large window size. 3) MLP ratio is better to be progressively increased along with network depth. 4) Q-K-V dimension could be smaller than the embedding dimension without performance drop. We hope these observations will help both the manual design of vision transformer and the space design for automatic search.
  In summary, we make the following contributions:
  • We propose a new scheme, i.e. S3, to automate the design of search space for vision transformer. We also present a new pipeline for vision transformer search with minimal human interactions. Moreover, we provide analysis and guidelines on vision transformer architecture design, which might be helpful for future architecture search and design.
  • The experiments on ImageNet verify the proposed automatic search space design method can improve the effectiveness of design space, thus boosting the performance of searched architectures. The discovered models achieve superior performance compared to the recent ViT [10] and Swin [27] transformer families under aligned settings. Moreover, the experiments on downstream vision and vision-language tasks, such as object detection, semantic segmentation and visual question answering, demonstrate the generality of the method.
sections.heading: 2 Approach
sections.heading: 2.1 Problem Formulation
sections.text: Most of existing NAS methods can be formulated as a constrained optimization problem as:
  α∗A = arg min α∈A L(W ∗α;Dval) s.t. W ∗α = arg min Wα L(Wα;Dtrain), g(α) < c, (1)
  whereWα is the weights of the network architecture α,A is a predefined search space, L(·) is the loss function, Dtrain and Dval represent train and validation datasets respectively, g(·) denotes a function calculating resource consumption of a model while c denotes a given resource constraint.
  Ideally, the search space A is an infinite space Ω that contains all possible architectures. In practice, A is usually a small subspace of Ω due to limited computation resource. In this paper, we break the
  convention of searching in a fixed space by considering the architecture search together with the search space design. More concretely, we decouple the constrained optimization problem of Eq. (1) into three separate steps:
  Step 1. Searching for an optimal search space under a specific constraint:
  A∗ = min A⊂Ω Q(A;Dval) s.t. |A| ≤M, (2)
  where Q is a measurement of search space to be elaborated in Sec. 2.3, and M represents the maximum search space size.
  Step 2. Following one-shot NAS [12, 34], we encode the search space into a supernet and optimize its weights. This is formulated as solving the following problem:
  W ∗A∗ = arg min W Eα∈A∗ [L(Wα;Dtrain)], (3)
  where W is the weights of the supernet, Wα is the weights in W specified by the architecture α.
  Step 3. After obtaining the well-trained supernet, we search for the optimal architecture via ranking the performance using the learned weights, which is formulated as:
  α∗A∗ = arg min α∈A∗ L(W ∗α;Dval), s.t. g(α) < c, (4)
  where W ∗α is the weights of architecture α inherited from W ∗ A∗ .
sections.heading: 2.2 Basic Search Space
sections.text: We set up the general architectures of vision transformer by following the settings in ViT [10] and Swin-T [27] as shown in Fig. 1 (right). To be specific, given an input image, we uniformly split it into non-overlap patches. Those patches are linearly projected to vectors named patch embeddings. The embeddings are then fed into the transformer encoder, which performs most of the computation. At last, a fully connected layer is adopted for classification.
  The transformer encoder consists of four sequential stages with progressively reduced input resolutions. Each stage contains blocks with the same embedding dimension. Therefore, stage i has two search dimensions: the number of blocks di and embedding dimension hi. Each block contains a window-based multi-head self-attention (WSA) module and a feed-forward network (FFN) module. We do not force the blocks in one stage to be identical. Instead, block j in the ith stage have several search dimensions including window sizewij , number of heads n i j , MLP ratiomi,Q-K-V embedding dimension qij .
sections.heading: 2.3 Searching the Search Space
sections.text: Space Quality Evaluation. For a given space A, we propose to use E-T Error, denoted as Q(A), for evaluating its quality. It is the average of two parts: expected error rate Qe(A) and top-tier error Qt(A). For a given space A, the definition of Qe(A) is given as:
  Qe(A) = Eα∈A,g(α)<c[eα], (5)
  where eα is the top-1 error rate of architecture α evaluated on ImageNet validation set, g(·) is the computation cost function and c is the computation resource constraint. It measures the overall quality of a search space. In practice, we use the average error rate of N randomly sampled architectures to approximate the expectation term. The top-tier error Qt(A) is the average error rate of top 50 candidates under resource constraints, representing the performance upper bound of the search space.
  Once-for-all Supernet. In constrast to RegNet [35] that trains hundreds of models with only a few epochs (∼10) and uses their errors as a performance proxy of the fully trained networks, we encode the search space into a supernet and optimize it similar to AutoFormer [6]. Under such training protocol, we are able to train an once-for-all transformer supernet that serves as a reliable and efficient performance indicator.
  Searching the Search Space. The search of search space mainly contains two iterative steps: 1) supernet optimization and 2) space evolution.
  Algorithm 1 Searching the Search Space Input: Infinite search space Ω, max iteration T , threshold τ for subspace evolved, the subspaces
  S (0) 1 , · · · , S (0) D , evolve steps for subspaces γ1, · · · , γD
  Output: The most promising search space A∗ 1: Initialize a search space A(0) from Ω with minimal prior human knowledge 2: while t ∈ [0, 1, · · · , T ] do 3: Optimize the weights W (t)A of supernet corresponding to the space A(t) 4: Randomly sample N architectures from the well converged supernet 5: for space S(t)i in S (t) 1 , · · · , S (t) D do
  6: Get the subspace {α|α ∈ A(t) ∩ αi = v(t)l } for each choice v (t) l ∈ S (t) i , where αi is the
  ith dimension value of the architecture α 7: Calculate the E-T Error of each subspace according to Eq. (5) 8: Evolve the subspace and get S(t+1)Di according to Eq. (8) 9: end for
  10: A∗ = A(t+1) = S(t+1)1 × S (t+1) 2 × · · · × S (t+1) D 11: end while
  Step 1. For the search space A(t) of tth iteration, we encode it into a supernet. We adopt sandwich training [52] to optimize the weights of supernet, i.e., sampling the largest, the smallest, and two middle models for each iteration and fusing their gradients to update the supernet. Notably, we do not use inplace-distill since it leads to collapse for transformer training.
  Step 2. We first decompose the search space A(t) by the search dimensions, defined in Sec .2.2, and four stages. Denote their corresponding subspaces as S(t)1 , S (t) 2 , · · · , S (t) D , where D is the product of the number of stage and the number of search dimensions. The search space A(t) now can be expressed as the Cartesian product of all search spaces:
  A(t) = S(t)1 × S (t) 2 × · · · × S (t) D , (6)
  Then the search space A(t) could be evolved to a better one A(t+1), with the update of S(t)i . Particularly, For a certain subspace S(t)i , we first get the subspace {α|α ∈ A(t) ∩αi = v (t) l } for each choice v (t) l ∈ S (t) i , where αi is the i
  th dimension value of the architecture α. Then we compute the E-T Errors of the subspaces. We hypothesize there is a strong correlation between the continuous choices and the E-T Error in most cases, so we fit a linear function to estimate its tendency for simplification:
  y = wx + b, (7)
  where x ∈ R is the choices in S(t)i , and y ∈ R is the corresponding E-T Error. w and b are both scalar parameters. Then the new subspace S(t+1)i is given as:
  S (t+1) i =
  { v
  (t) j − ⌊w τ ⌋ γi ∣∣∣ v(t)j ∈ S(t)i }, (8) where τ is the threshold for search space evolving, γi is the steps for search dimension Si. Note that we remove the choices if they become less than zero. The detailed algorithm is also shown in Alg. 1.
sections.heading: 2.4 Searching in the Searched Space
sections.text: Once the space search is done, we perform neural architecture search over the searched space. The search pipeline contains two sequential steps: 1) supernet training without resource constraints, and 2) evolution search under resource constraints.
  The supernet training follows the same train recipe in space search. Similar to AutoFormer [6] and BigNas [52], the maximal, minimal subnets and several random architectures are sampled randomly from the evolved search space in each iteration and their corresponding weights are updated. We provide more details in Sec. 4.1. The evolution search process follows the similar setting in SPOS [12]. Our objective in this paper is to maximize the classification accuracy while minimizing the model size and FLOPs. Notably, vision transformer does not include any Batch Normalization [19],
  hence the evolution process is much faster than CNN. We provide more details in the supplementary materials.
sections.heading: 3 Analysis and Discussion
sections.text: In this section we provide analysis and discussion according to the space searching process. We hope that our observations can shed lights on both manual design of vision transformer architecture and the search space design for NAS methods. To minimize the prior knowledge used in search space design, we initialize the search space by setting a same search space for different stages. We provide the detailed search space and its evolution process in Fig. 2. Fig. 3 shows a direct illustration of space quality of the searched space focusing on the number of blocks.
  The third stage is most important and increasing blocks in the third stage leads to better performance. As shown in the first row of Fig. 2, the blocks of stage 3 is constantly increasing from step 0 to step 2. We also observe that there are more blocks in stage 3 in some famous CNN networks, such as ResNet [14], EfficientNet [39], which share the same architecture characteristics with our finding in transformers. As a result, it seems that the third stage is the most important one. On the other hand, contrary to stage 3, the number of blocks decrease in stage 1,2,4 showing that these stages should include fewer layers.
  Shallow layers should use a small window size while deep layers should use a larger one. As shown in the last row of Fig. 2, with the search steps increasing, the window size space decreases in stage 1 while increases in stage 3. It shows that shallow layers tend to have smaller window size while deep layers tend to have larger one. We assume that transformers increase focusing region with deeper layers. To verify this, we visualize the attention maps (top row in Fig. 4 (b,c) ) in different layers and
  draw a box plot (bottom row in Fig. 4 (f,g)) to show the relative distances from the target position to its top-5/10 focusing positions. The attention maps show that the highest attentions (noted by numbers) expand with deeper layer, which is illustrated from (b) to (c). As for the average relative distance, deeper layers have larger medians and means, indicating larger focusing regions. The above observations are consistent with our assumption and provide solid evidence for it.
  Deeper layer should use larger MLP ratio. Traditionally, all layers use the same MLP ratio. However, the third row of Fig. 2 illustrates that shallow layers should use small MLP ratio to result in better performance while deeper ones should use larger MLP ratio.
  Q-K-V dimension should be smaller than the embedding dimension. In the original transformer block [41, 10], the Q-K-V dimension is the same as the embedding dimension. However, comparing the second row with the third row of Fig. 2, we find that the searched space has a slightly smaller Q-K-V dimension than embedding dimension, shown from stage 1 to stage 4. The gap between them are more obvious in the deeper layers. We conjecture the reason is that there are many heads with similar features in deeper layers. Therefore, the a relative small Q-K-V dimension is able to have great visual representation ability. We present more details in the supplementary materials.
sections.heading: 4 Experiments
sections.heading: 4.1 Implementation Details
sections.text: Space searching. The initial search space is presented in Fig. 2, the number of blocks and embedding dimension are set to {2, 3, 4} and {224, 256, 288} respectively for all stages, while the window size, number of heads, MLP ratio, Q-K-V dimensions are set to {7, 14}, {3, 3.5, 4}, {7, 8, 9}, {224, 256, 288} respectively for all blocks. We set the total iteration of space searching to 3, while setting the steps in Eq. (8) for block number, embed dim, MLP ratio, Q-K-V dim, windows size to 1, 64, 0.5, 64, 7, respectively. We set the threshold τ of space evolution in Eq. (8) as 0.4.
  Supernet training. Similar to DeiT [40], we train the supernet with the following settings: AdamW [28] optimizer with weight decay 0.05, initial learning rate 1× 10−3 and minimal learning rate 1× 10−5 with cosine scheduler, 20 epochs warmup, batch size of 1024, 0.1 label smoothing, and stochastic depth with drop rate 0.2. We also adopt sandwich strategy as describe in Sec. 2.3. The models are trained for 300 epochs with 16 Nvidia Tesla 32G V100 GPUs.
  Table 1: S3 performance on ImageNet in comparison with state-of-the-arts. We group the models according to their parameter sizes.
  Models Top-1 Acc. Top-5 Acc. #Params. FLOPs Res. Model Type
  ResNet50 [14] 76.2% 92.9% 25.5M 4.1G 2242 CNN RegNetY-4GF [35] 80.0% - 21.4M 4.0G 2242 CNN EfficietNet-B4 [39] 82.9% 95.7% 19.3M 4.2G 3802 CNN T2T-ViT-14 [53] 80.7% - 21.5M 6.1G 2242 Transformer DeiT-S [40] 79.9% 95.0% 22.1M 4.7G 2242 Transformer ViT-S/16 [10] 78.8% - 22.1M 4.7G 2242 Transformer Swin-T [27] 81.3% - 28.3M 4.5G 2242 Transformer S3-T (Ours) 82.1% 95.8% 28.1M 4.7G 2242 Transformer
  ResNet152 [14] 78.3% 94.1% 60M 11G 2242 CNN EfficietNet-B7 [39] 84.3% 97.0% 66M 37G 6002 CNN BoTNet-S1-110 [38] 82.8% 96.4% 55M 10.9G 2242 CNN + Trans T2T-ViT-24 [53] 82.2% - 64M 15G 2242 Transformer Swin-S [27] 83.0% - 50M 8.7G 2242 Transformer S3-S (Ours) 83.7% 96.4% 50M 9.5G 2242 Transformer S3-S-384 (Ours) 84.5% 96.8% 50M 33G 3842 Transformer
  RegNetY-16GF [35] 80.4% - 83M 16G 2242 CNN ViT-B/16 [10] 79.7% - 86M 18G 2242 Transformer DeiT-B [40] 81.8% 95.6% 86M 18G 2242 Transformer Swin-B [27] 83.3% - 88M 15.4G 2242 Transformer Swin-B-384 [27] 84.2% - 88M 47G 3842 Transformer S3-B (Ours) 84.0% 96.6% 71M 13.6G 2242 Transformer S3-B-384 (Ours) 84.7% 96.9% 71M 46G 3842 Transformer
  79.6 79.8 80.0 80.2 80.4 80.6 80.8 81.0 81.2 Inherited Performance
  79.6 79.8 80.0 80.2 80.4 80.6 80.8 81.0 81.2 Re tra in P er fo rm an ce
  79.6 79.8 80.0 80.2 80.4 80.6 80.8 81.0 81.2 Inherited Performance
  79.6 79.8 80.0 80.2 80.4 80.6 80.8 81.0 81.2 Fin et un e Pe rfo rm an ce
  Figure 5: Comparison of subnets with inherited weights, fine-tuned and trained from scratch. 20 25 30 35 40 Error
  0.0
  0.2
  0.4
  0.6
  0.8
  1.0
  Cu m
  ula tiv
  e pr
  ob . AB
  C Space A Space B Space C
  Figure 6: Error empirical distribution function of different search spaces.
sections.heading: 4.2 Ablation Study
sections.text: Effectiveness of once-for-all supernet sampling. To verify the effectiveness, we randomly sample 10 architectures from the well-trained supernet with the inherited weights, then compare the ImageNet classification performance of (1) models with only inherited weights, (2) models with finetuning, and (3) models retrained from scratch. As shown in Fig. 5, the architecture with inherited weights has comparable or even better performance when compared with the same architecture with retraining or finetuning. This phenomenon shows that our sampled architectures provide a precise and reliable performance proxy for space quality measurement.
  Effectiveness of search space evolution. We conduct two experiments. In the first experiment, we randomly sample 1, 000 architectures with inherited weights from a search space, then compute and plot error empirical distribution, as in [35], of them. We denote the initial space, the one-step evolved space and the two-step evolved space by Space A, Space B and Space C respectively. As shown in Fig. 6, the space C has an obviously better overall quality compared to A and B. In the second experiment, we use evolution algorithm to search for top architectures in each space. Tab. 5 illustrates that the space C has a much better top architectures, being 16.6%/4.1% better than that in the spaces A and B. These results verify the effectiveness of search spaces evolution.
sections.heading: 4.3 Image Classification
sections.text: We compare our searched models with state-of-the-arts on ImageNet [9]. As described in Sec. 2.1 and Sec. 4.1, we first evolve the search space, then optimize the weights of supernet and finally search on the supernet. For the experiments of high resolution images, the models are finetuned with 3842 inputs for 10 epochs, using an AdamW [28] optimizer with a constant learning rate of 10−5 and weight decay of 10−8.
  We compare our S3 with state-of-the-art CNN models, vision transformers and hybrid CNNtransformer models. The results are reported in Tab. 1. Our proposed models S3-tiny/small/base (T/S/B for short) achieve 82.1%/83.7%/84.0% top-1 accuracy on ImageNet [9] using 2242 input images. Compared with vision transformer and hybrid models, our method obtains superior performance using similar FLOPs and parameters. For example, when considering parameters as the main constraint, we find a architecture that has 0.6% higher top-1 accuracy than Swin Transformer [27] while using 42% fewer parameters as shown in Fig. 7 . Compared to CNN models, our S3 models are also very competitive, especially for small parameter size. The proposed S3-S-384 (84.5%) performs slightly better than EfficientNet-B7 (84.3%) [39] while using 24% fewer parameters and 11% fewer FLOPs. For base models with fewer computational cost, S3-B also achieves superior performance to state-of-the-art methods, such as RegNet [35] and ViT [10].
sections.heading: 4.4 Vision and Vision-Language Downstream Tasks
sections.text: To further evaluate the generalizability of the discovered architectures, we transfer them to vision and vision-language downstream tasks. We conduct experiments on COCO [24] for object detection, ADE20K [56] for semantic segmentation and VQA 2.0 [54] for visual question answering, respectively. The training and inference settings for object detection and semantic segmentation are the same as those in Swin transformer [27], while for visual language answering task, the settings are aligned with SOHO [18]. More experimental details are elaborated in supplementary materials.
  Object Detection. As shown in Tab. 2, S3-T outperforms ResNet-50 [14] by +4.2 box AP and +3.7 mask AP under 3× learning schedule. Compared to DeiT-S [40], S3-T achieves +2.5 higher box AP and +2.4 higher mask AP. Increasing the model size and FLOPs, S3-S and S3-B surpass ResNeXt-101 [48] by +4.5 box AP, +3.9 mask AP and +4.2 box AP, +3.7 mask AP respectively. Compared to Swin-S and Swin-B, S3-S and S3-B outperform them by +0.8 box AP, +0.8 mask AP and +0.6 box AP, +0.4 mask AP respectively. All comparisons are conducted under the similar model
  Table 3: Results on ADE20K Semantic Segmentation using UperNet. †: reproduced by the official code. ∗: without adding deconvolution in heads.
  Method Backbone #param FLOPs mIoU mIoU(M) (G) (%) (ms+flip %) UperNet ResNet-50 [14] 67 951 42.05 42.78 UperNet DeiT-S∗ [40] 52 1099 43.15 43.85 UperNet Swin-T [27] 60 945 44.51 45.81 UperNet S3-T(Ours) 60 954 44.87 46.27 UperNet ResNet-101 [14] 86 1029 43.82 44.85 UperNet DeiT-B∗ [40] 121 2772 44.09 45.68 UperNet Swin-S† [27] 81 1038 47.60 48.87 UperNet S3-S(Ours) 81 1071 48.04 49.31
  Table 4: Results on VQA v2.0 dataset.
  Backbone #Param FLOPs VQA VQA(M) (G) test-dev(%) test-std(%)
  ResNet-50 [14] 4.1 26 64.65 65.12 ResNet-101 [14] 7.8 45 65.44 65.71
  Swin-T [27] 4.5 29 67.13 67.40 S3-T (Ours) 4.6 29 67.84 68.00
  Table 5: Comparisons of searched architectures in different spaces.
  Space #Param(M) FLOPs(G) Top-1(%) A 28M 4.7 65.5 B 29M 4.7 78.0 C 28M 4.7 82.1
  size and FLOPs. Under the 1× training schedule, our S3 model is also superior to other backbones, demonstrating its robustness and good transferability.
  Semantic Segmentation. We report the mIoU score on ADE20K [56] validation set in Tab. 3. It can be seen that our S3 models consistently achieve better performance than ResNet [14], DeiT [40] and Swin [27]. Specifically, S3-T is +3.5 mIoU superior to ResNet-50. Compared to other transformerbased models, S3-T is +2.42 mIoU higher than DeiT-S, and +0.46 mIoU higher than Swin-T. S3-S outperforms ResNet-101 with a large margin (+4.46). It also surpasses DeiT-B and Swin-S by +3.63 and +0.44 mIoU, respectively. Note that we tried to add deconvolution layers to build a hierarchical structure for DeiT, but did not get performance improvements.
  Visual Question Answering. As shown in Tab. 4, we report the accuracy on the test-dev and test-std set of VQA v2.0 dataset [54] for different vision backbones. Our model S3-T brings more than +2% accuracy gains over ResNet-101 [14], and surpassing Swin-T [27] by around 0.6% accuracy under aligned model complexity. All the above experiments demonstrate the good generality of the searched models as well as proving the effectiveness of the searched design space of vision transformer.
sections.heading: 5 Related Work
sections.text: Vision Transformer. Originally designed for natural language processing, Transformer has been recently applied to vision tasks [4, 55, 5, 46]. ViT [10] is the first one that introduces a pure transformer architecture for visual recognition. Alleviating the data hungry and computational issues, DeiT [40] introduces a series of training strategies to remedy the limitations. Some further works resort to feature pyramids to purify multi-scale features and model global information [44, 15, 31]. Swin Transformer [27] introduces non-overlapping window partitions and restricts the calculation of self-attention within each window, leading to a linear runtime complexity w.r.t. token numbers.
  Search Space. There is a wide consensus that a good search space is crucial for NAS. Regarding CNN, the current search space, such as cell-based space [26, 7, 49] and MBConv-based space [3, 32, 51], is pre-defined and fixed during search. Several recent works [17, 29, 30, 33, 25, 23] perform search space shrinking to find a better compact one. Moreover, NSENet [8] proposes an evolving search space algorithm for MBConv space optimization. RegNet [35] presents a new paradigm for understanding design space and discovering design principles. However, the exploration of vision transformer space is still limited, and our work is the first along the direction.
  Search Algorithm. There has been an increasing interest in NAS for automating network design [11, 20]. Early approaches use either reinforcement learning [57, 58] or evolution algorithms [47, 36]. These approaches require training thousands of architecture candidates from scratch. Most recent works resort to the one-shot weight sharing strategy to amortize the searching cost [22, 34, 1, 12]. The key idea is to train an over-parameterized supernet where all subnets share weights. For transformer, there are few works employing NAS to improve architectures. Evolved Transformer [37] searches the inner architecture of transformer block. HAT [43] proposes to design hardware-aware transformers with NAS to enable low-latency inference on resource-constrained hardware platforms. BossNAS [21] explores hybrid CNN-Transformers with block-wisely self-supervised. The most related work is AutoFormer [6] which provides a simple yet effective framework of vision transformer search. It could achieve once-for-all training with newly proposed weight entanglement. In this work, we focus on both the search space design and architectures of vision transformer.
sections.heading: 6 Conclusion
sections.text: In this work, we propose to search the search space of vision transformer. The central idea is to gradually evolve different search dimensions guided by their E-T Error computed using a weightsharing supernet. We also provide analysis on vision transformer, which might be helpful for understanding and designing transformer architectures. The search models, S3, achieve superior performance to recent prevalent ViT and Swin transformer model families under aligned settings. We further show their robustness and generality on downstream tasks. In further work, we hope to investigate the usage of S3 in CNN search space design.
  Acknowledgements and Disclosure of Funding
  Thank Hongwei Xue for providing helps and discussions on vision-language tasks. No external funding was received for this work.
title: Searching the Search Space of Vision Transformer