summaries: The authors propose with this paper a simple extension of DARTS, a popular neural architecture search (NAS) method. This extension addresses one of the shortcoming of DARTS: the immense memory cost. This achieved in a simple way. Instead of using all channels only a random subset is used. To account for that, the authors propose a method to normalizes edges.

summaries: This paper proposes to improve the previously work DARTS in terms of the training efficiency, from the large memory and computing overheads. The authors propose a partially-connected DARTS (PC-DARTS) with two components: 1. Partial channel connection 2. edge normalization. To be detailed, they sample a small part of channels to perform connection and add edge normalization to eliminate the potential optimization problem. The results on CIFAR-10 and IamgeNet show the approach is effective, especially in ImageNet, the approach achieves SOTA results.

abstractText: Differentiable architecture search (DARTS) provided a fast solution in finding effective network architectures, but suffered from large memory and computing overheads in jointly training a super-network and searching for an optimal architecture. In this paper, we present a novel approach, namely, Partially-Connected DARTS, by sampling a small part of super-network to reduce the redundancy in exploring the network space, thereby performing a more efficient search without comprising the performance. In particular, we perform operation search in a subset of channels while bypassing the held out part in a shortcut. This strategy may suffer from an undesired inconsistency on selecting the edges of super-net caused by sampling different channels. We alleviate it using edge normalization, which adds a new set of edge-level parameters to reduce uncertainty in search. Thanks to the reduced memory cost, PC-DARTS can be trained with a larger batch size and, consequently, enjoys both faster speed and higher training stability. Experimental results demonstrate the effectiveness of the proposed method. Specifically, we achieve an error rate of 2.57% on CIFAR10 with merely 0.1 GPU-days for architecture search, and a state-of-the-art top-1 error rate of 24.2% on ImageNet (under the mobile setting) using 3.8 GPU-days for search. Our code has been made available at https://github.com/yuhuixu1993/PC-DARTS.

authors:
Bowen Baker
Otkrist Gupta
Nikhil Naik
Ramesh Raskar

title: Designing neural network architectures using reinforcement learning

venue: In ICLR,

authors:
Andrew Brock
Theodore Lim
James M Ritchie
Nick Weston

title: SMASH: one-shot model architecture search through hypernetworks

authors:
Han Cai
Tianyao Chen
Weinan Zhang
Yong Yu
Jun Wang

title: Efficient architecture search by network transformation

venue: In AAAI,

authors:
Han Cai
Ligeng Zhu
Song Han

title: ProxylessNAS: Direct neural architecture search on target task and hardware

authors:
Francesco Paolo Casale
Jonathan Gordon
Nicolo Fusi

title: Probabilistic neural architecture search

venue: arXiv preprint arXiv:1902.05116,

authors:
Xin Chen
Lingxi Xie
Jun Wu
Qi Tian

title: Progressive differentiable architecture search: Bridging the depth gap between search and evaluation

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: ImageNet: A large-scale hierarchical image database

venue: In CVPR,

authors:
Terrance DeVries
Graham W Taylor

title: Improved regularization of convolutional neural networks with cutout

venue: arXiv preprint arXiv:1708.04552,

authors:
Thomas Elsken
Jan Hendrik Metzen
Frank Hutter

title: Efficient multi-objective neural architecture search via lamarckian evolution

authors:
Andrew G Howard
Menglong Zhu
Bo Chen
Dmitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: MobileNets: Efficient convolutional neural networks for mobile vision applications

venue: arXiv preprint arXiv:1704.04861,

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: ImageNet classification with deep convolutional neural networks

venue: In NIPS,

authors:
Gustav Larsson
Michael Maire
Gregory Shakhnarovich

title: FractalNet: Ultra-deep neural networks without residuals

authors:
Liam Li
Ameet Talwalkar

title: Random search and reproducibility for neural architecture search

venue: In UAI,

authors:
Tsung-Yi Lin
Michael Maire
Serge J. Belongie
Lubomir D. Bourdev
Ross B. Girshick
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C. Lawrence Zitnick

title: Microsoft COCO: Common objects in context

venue: In ECCV,

authors:
Chenxi Liu
Barret Zoph
Maxim Neumann
Jonathon Shlens
Wei Hua
Li-Jia Li
Li Fei-Fei
Alan Yuille
Jonathan Huang
Kevin Murphy

title: Progressive neural architecture search

authors:
Hanxiao Liu
Karen Simonyan
Oriol Vinyals
Chrisantha Fernando
Koray Kavukcuoglu

title: Hierarchical representations for efficient architecture search

authors:
Hanxiao Liu
Karen Simonyan
Yiming Yang

title: DARTS: Differentiable architecture search

authors:
Weiwei Liu
Dragomir Anguelov
Dumitru Erhan
Christian Szegedy
Scott E. Reed
Cheng-Yang Fu
Alexander C. Berg

title: Ssd: Single shot multibox detector

authors:
Renqian Luo
Fei Tian
Tao Qin
Enhong Chen
Tie-Yan Liu

title: Neural architecture optimization

venue: In NeurIPS,

authors:
Ningning Ma
Xiangyu Zhang
Hai-Tao Zheng
Jian Sun

title: ShuffleNet V2: Practical guidelines for efficient cnn architecture design

authors:
Jieru Mei
Xiaochen Lian
Xiaojie Jin
Linjie Yang
Yingwei Li
Alan Yuille
Jianchao Yang

title: AtomNAS: Fine-grained end-to-end neural architecture search

authors:
Risto Miikkulainen
Jason Liang
Elliot Meyerson
Aditya Rawal
Daniel Fink
Olivier Francon
Bala Raju
Hormoz Shahrzad
Arshak Navruzyan
Nigel Duffy

title: Evolving deep neural networks

venue: In Artificial Intelligence in the Age of Neural Networks and Brain Computing,

authors:
Hieu Pham
Melody Y Guan
Barret Zoph
Quoc V Le
Jeff Dean

title: Efficient neural architecture search via parameter sharing

authors:
Esteban Real
Sherry Moore
Andrew Selle
Saurabh Saxena
Yutaka Leon Suematsu
Jie Tan
Quoc V Le
Alexey Kurakin

title: Large-scale evolution of image classifiers

authors:
Esteban Real
Alok Aggarwal
Yanping Huang
Quoc V Le

title: Regularized evolution for image classifier architecture search

authors:
Joseph Redmon
Ali Farhadi

title: Yolo9000: Better, faster, stronger

authors:
Mark Sandler
Andrew G. Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

authors:
Christian Sciuto
Kaicheng Yu
Martin Jaggi
Claudiu Musat
Mathieu Salzmann

title: Evaluating the search phase of neural architecture

venue: search. ArXiv,

title: Dropout: A simple way to prevent neural networks from overfitting

authors:
Christian Szegedy
Wei Liu
Yangqing Jia
Pierre Sermanet
Scott Reed
Dragomir Anguelov
Dumitru Erhan
Vincent Vanhoucke
Andrew Rabinovich

title: Going deeper with convolutions

authors:
Mingxing Tan
Bo Chen
Ruoming Pang
Vijay Vasudevan
Quoc V Le

title: MnasNet: Platformaware neural architecture search for mobile

authors:
Robert J. Wang
Xiang Li
Shuang Ao
Charles X. Ling

title: Pelee: A real-time object detection system on mobile devices

venue: NeurIPS,

authors:
Lingxi Xie
Alan Yuille

title: Genetic CNN

venue: In ICCV,

authors:
Sirui Xie
Hehui Zheng
Chunxiao Liu
Liang Lin

title: SNAS: Stochastic neural architecture search

authors:
Xiangyu Zhang
Xinyu Zhou
Mengxiao Lin
Jian Sun

title: ShuffleNet: An extremely efficient convolutional neural network for mobile devices

authors:
Zhao Zhong
Junjie Yan
Wei Wu
Jing Shao
Cheng-Lin Liu

title: Practical block-wise neural network architecture generation

authors:
Hongpeng Zhou
Minghao Yang
Jun Wang
Wei Pan

title: BayesNAS: A Bayesian approach for neural architecture search

venue: In ICML,

authors:
Barret Zoph
Quoc V Le

title: Neural architecture search with reinforcement learning

authors:
Barret Zoph
Vijay Vasudevan
Jonathon Shlens
Quoc V Le

title: Learning transferable architectures for scalable image recognition

heading: 1 INTRODUCTION

text:
Neural architecture search (NAS) emerged as an important branch of automatic machine learning (AutoML), and has been attracting increasing attentions from both academia and industry. The key methodology of NAS is to build a large space of network architectures, develop an efficient algorithm to explore the space, and discover the optimal structure under a combination of training data and constraints (e.g., network size and latency). Different from early approaches that often incur large computation overheads (Zoph & Le, 2017; Zoph et al., 2018; Real et al., 2019), recent oneshot approaches (Pham et al., 2018; Liu et al., 2019) have reduced the search costs by orders of magnitudes, which advances its applications to many real-world problems. In particular, DARTS (Liu et al., 2019) converts the operation selection into weighting a fixed set of operations. This makes the entire framework differentiable to architecture hyper-parameters and thus the network search can be efficiently accomplished in an end-to-end fashion. Despite its sophisticated design, DARTS is still subject to a large yet redundant space of network architectures and thus suffers from heavy memory and computation overheads. This prevents the search process from using larger batch sizes for either speedup or higher stability. Prior work (Chen et al., 2019) proposed to reduce the search space, which leads to an approximation that may sacrifice the optimality of the discovered architecture.
∗ This work was done when Yuhui Xu and Xin Chen were interns at Huawei Noah’s Ark Lab. Qi Tian is the corresponding author. This work was supported in part by the National NSFC under Grant Nos. 61971285, 61425011, 61529101, 61622112, 61720106001, 61932022, and in part by the Program of Shanghai Academic Research Leader under Grant 17XD1401900. We thank Longhui Wei and Bowen Shi for instructive discussions.
In this paper, we present a simple yet effective approach named Partially-Connected DARTS (PCDARTS) to reduce the burdens of memory and computation. The core idea is intuitive: instead of sending all channels into the block of operation selection, we randomly sample a subset of them in each step, while bypassing the rest directly in a shortcut. We assume the computation on this subset is a surrogate approximating that on all the channels. Besides the tremendous reduction in memory and computation costs, channel sampling brings another benefit – operation search is regularized and less likely to fall into local optima. However, PC-DARTS incurs a side effect, where the selection of channel connectivity would become unstable as different subsets of channels are sampled across iterations. Thus, we introduce edge normalization to stabilize the search for network connectivity by explicitly learning an extra set of edge-selection hyper-parameters. By sharing these hyper-parameters throughout the training process, the sought network architecture is insensitive to the sampled channels across iterations and thus is more stable.
Benefiting from the partial connection strategy, we are able to greatly increase the batch size. Specifically, as only 1/K of channels are randomly sampled for an operation selection, it reduces the memory burden by almost K times. This allows us to use a K times larger batch size during search, which not only accelerates the network search but also stabilizes the process particularly for largescale datasets. Experiments on benchmark datasets demonstrate the effectiveness of PC-DARTS. Specifically, we achieve an error rate of 2.57% in less than 0.1 GPU-days (around 1.5 hours) on a single Tesla V100 GPU, surpassing the result of 2.76% reported by DARTS that required 1.0 GPUday. Furthermore, PC-DARTS allows a direct search on ImageNet (while DARTS failed due to low stability), and sets the state-of-the-art record with a top-1 error of 24.2% (under the mobile setting) in only 3.8 GPU-days (11.5 hours on eight Tesla V100 GPUs).

heading: 2 RELATED WORK

text:
Thanks to the rapid development of deep learning, significant gain in performance has been brought to a wide range of computer vision problems, most of which owed to manually desgined network architectures (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; He et al., 2016; Huang et al., 2017). Recently, a new research field named neural architecture search (NAS) has been attracting increasing attentions. The goal is to find automatic ways of designing neural architectures to replace conventional handcrafted ones. According to the heuristics to explore the large architecture space, existing NAS approaches can be roughly divided into three categories, namely, evolution-based approaches, reinforcement-learning-based approaches and one-shot approaches.
The first type of architecture search methods (Liu et al., 2018b; Xie & Yuille, 2017; Real et al., 2017; Elsken et al., 2019; Real et al., 2019; Miikkulainen et al., 2019) adopted evolutionary algorithms, which assumed the possibility of applying genetic operations to force a single architecture or a family evolve towards better performance. Among them, Liu et al. (Liu et al., 2018b) introduced a hierarchical representation for describing a network architecture, and Xie et al. (Xie & Yuille, 2017) decomposed each architecture into a representation of ‘genes’. Real et al. (Real et al., 2019) proposed aging evolution which improved upon standard tournament selection, and surpassed the best manually designed architecture since then. Another line of heuristics turns to reinforcement learning (RL) (Zoph & Le, 2017; Baker et al., 2017; Zoph et al., 2018; Zhong et al., 2018; Liu et al., 2018a), which trained a meta-controller to guide the search process. Zoph et al. (Zoph & Le, 2017) first proposed using a controller-based recurrent neural network to generate hyper-parameters of neural networks. To reduce the computation cost, researchers started to search for blocks or cells (Zhong et al., 2018; Zoph et al., 2018) instead of the entire network, and consequently, managed to reduce the overall computational costs by a factor of 7. Other kinds of approximation, such as greedy search (Liu et al., 2018a), were also applied to further accelerate search. Nevertheless, the computation costs of these approaches, based on either evolution or RL, are still beyond acceptance.
In order to accomplish architecture search within a short period of time, researchers considered to reduce the costs of evaluating each searched candidate. Early efforts include sharing weights between searched and newly generated networks (Cai et al., 2018), and later these methods were generalized into a more elegant framework named one-shot architecture search (Brock et al., 2018; Cai et al., 2019; Liu et al., 2019; Pham et al., 2018; Xie et al., 2019), in which an over-parameterized network or super-network covering all candidate operations was trained only once, from which exponentially many sub-networks can be sampled. As typical examples, SMASH (Brock et al.,
2018) trained the over-parameterized network by a HyperNet (Ha et al., 2017), and ENAS (Pham et al., 2018) shared parameters among child models to avoid retraining each candidate from scratch.
This paper is based on DARTS (Liu et al., 2018b), which introduced a differentiable framework for architecture search, and thus combine the search and evaluation stages into one. A super-network is optimized during the search stage, after which the strongest sub-network is preserved and then retrained. Despite its simplicity, researchers detected some of its drawbacks, such as instability (Li & Talwalkar, 2019; Sciuto et al., 2019), which led to a few improved approaches beyond DARTS (Cai et al., 2019; Chen et al., 2019; Mei et al., 2020). In particular, ProxylessNAS (Cai et al., 2019) was the first method that searched directly on ImageNet, and P-DARTS (Chen et al., 2019) designed a progressive search stage to bridge the depth gap between the super-network and the sub-network.

heading: 3 THE PROPOSED APPROACH

heading: 3.1 PRELIMINARIES: DIFFERENTIABLE ARCHITECTURE SEARCH (DARTS)

text:
We first review the baseline DARTS (Liu et al., 2019), and define the notations for the discussion later. Mathematically, DARTS decomposes the searched network into a number (L) of cells. Each cell is represented as a directed acyclic graph (DAG) with N nodes, where each node defines a network layer. There is a pre-defined space of operations denoted by O, in which each element, o(·), is a fixed operation (e.g., identity connection, and 3 × 3 convolution) performed at a network layer. Within a cell, the goal is to choose one operation from O to connect each pair of nodes. Let a pair of nodes be (i, j), where 0 6 i < j 6 N − 1, the core idea of DARTS is to formulate the information propagated from i to j as a weighted sum over |O| operations, namely, fi,j(xi) = ∑ o∈O
exp{αoi,j}∑ o′∈O exp{αo′i,j}
· o(xi), where xi is the output of the i-th node, and αoi,j is a hyper-parameter for weighting operation o(xi). The output of a node is the sum of all input flows, i.e., xj = ∑ i<jfi,j(xi), and the output of the entire cell is formed by concatenating the output of nodes x2–xN−1, i.e., concat(x2,x3, . . . ,xN−1). Note that the first two nodes, x0 and x1, are input nodes to a cell, which are fixed during architecture search.
This design makes the entire framework differentiable to both layer weights and hyper-parameters αoi,j , so that it is possible to perform architecture search in an end-to-end fashion. After the search process is finished, on each edge (i, j), the operation o with the largest αoi,j value is preserved, and each node j is connected to two precedents i < j with the largest αoi,j preserved.

heading: 3.2 PARTIAL CHANNEL CONNECTIONS

text:
A drawback of DARTS lies in memory inefficiency. In the main part of the searched architecture, |O| operations and the corresponding outputs need to be stored at each node (i.e., each network layer), leading to |O|× memory to use. To fit into a GPU, one must reduce the batch size during search, which inevitably slows down search speed, and may deteriorate search stability and accuracy.
An alternative solution to memory efficiency is the partial channel connection as depicted in Figure 1. Take the connection from xi to xj for example. This involves defining a channel sampling mask Si,j , which assigns 1 to selected channels and 0 to masked ones. The selected channels are sent into mixed computation of |O| operations, while the masked ones bypass these operations, i.e., they are directly copied to the output,
fPCi,j (xi;Si,j) = ∑ o∈O exp { αoi,j }∑ o′∈O exp { αo ′ i,j
} · o(Si,j ∗ xi) + (1− Si,j) ∗ xi. (1) where, Si,j ∗ xi and (1− Si,j) ∗ xi denote the selected and masked channels, respectively. In practice, we set the proportion of selected channels to 1/K by regarding K as a hyper-parameter. By varying K, we could trade off between architecture search accuracy (smaller K) and efficiency (larger K) to strike a balance (See Section 4.4.1 for more details).
A direct benefit brought by the partial channel connection is that the memory overhead of computing fPCi,j (xi;Si,j) is reduced by K times. This allows us to use a larger batch size for architecture search. There are twofold benefits. First, the computing cost could be reduced by K times during the architecture search. Moreover, the larger batch size implies the possibility of sampling more training data during each iteration. This is particularly important for the stability of architecture search. In most cases, the advantage of one operation over another is not significant, unless more training data are involved in a mini-batch to reduce the uncertainty in updating the parameters of network weights and architectures.

heading: 3.3 EDGE NORMALIZATION

text:
Let us look into the impact of sampling channels on neural architecture search. There are both positive and negative effects. On the upside, by feeding a small subset of channels for operation mixture while bypassing the remainder, we make it less biased in selecting operations. In other words, for edge (i, j), given an input xi, the difference from using two sets of hyper-parameters { αoi,j }
and{ α′oi,j }
is largely reduced, because only a small part (1/K) of input channels would go through the operation mixture while the remaining channels are left intact. This regularizes the preference of a weight-free operation (e.g., skip-connect, max-pooling, etc.) over a weight-equipped one (e.g., various kinds of convolution) inO. In the early stage, the search algorithm often prefers weight-free operations, because they do not have weights to train and thus produce more consistent outputs, i.e., o(xi). In contrast, the weight-equipped ones, before their weights are well optimized, would propagate inconsistent information across iterations. Consequently, weight-free operations often accumulate larger weights (namely αoi,j) at the beginning, and this makes it difficult for the weightequipped operations to beat them even after they have been well trained thereafter. This phenomenon is especially significant when the proxy dataset (on which architecture search is performed) is difficult, and this could prevent DARTS from performing satisfactory architecture search on ImageNet. In experiments, we will show that PC-DARTS, with partial channel connections, produces more stable and superior performance on ImageNet.
On the downside, in a cell, each output node xj needs to pick up two input nodes from its precedents {x0,x1, . . . ,xj−1}, which are weighted by maxo αo0,j ,maxo αo1,j , . . . ,maxo αoj−1,j , respectively, following the original DARTS. However, these architecture parameters are optimized by randomly sampled channels across iterations, and thus the optimal connectivity determined by them could be unstable as the sampled channels change over time. This could cause undesired fluctuation in
the resultant network architecture. To mitigate this problem, we introduce edge normalization that weighs on each edge (i, j) explicitly, denoted by βi,j , so that the computation of xj becomes:
xPCj = ∑ i<j exp {βi,j}∑ i′<j exp {βi′,j} · fi,j(xi). (2)
Specifically, after the architecture search is done, the connectivity of edge (i, j) is determined by both { αoi,j }
and βi,j , for which we multiply the normalized coefficients together, i.e., multiplying exp{βi,j}∑
i′<j exp{βi′,j} by exp{αoi,j}∑ o′∈O exp{αo′i,j} . Then the edges are selected by finding the large edge weights as in DARTS. Since βi,j are shared through the training process, the learned network architecture is insensitive to the sampled channels across iterations, making the architecture search more stable. In Section 4.4.2, we will show that edge normalization is also effective over the original DARTS. Finally, the extra computation overhead required for edge normalization is negligible.

heading: 3.4 DISCUSSIONS AND RELATIONSHIP TO PRIOR WORK

text:
First of all, there are two major contributions of our approach, namely, channel sampling and edge normalization. Channel sampling, as the key technique in this work, has not been studied in NAS for reducing computational overhead (other regularization methods like Dropout (Srivastava et al., 2014) and DropPath (Larsson et al., 2017) cannot achieve the same efficiency, in both time and memory, as channel sampling). It accelerates and regularizes search and, with the help of edge normalization, improves search stability. Note that both search speed and stability are very important for a search algorithm. Combining channel sampling and edge normalization, we obtain the best accuracy on ImageNet (based on the DARTS search space), and the direct search cost on ImageNet (3.8 GPU-days) is the lowest known. Moreover, these two components are easily transplanted to other search algorithms to improve search accuracy and speed, e.g., edge normalization boosts the accuracy and speed of the original DARTS methods.
Other researchers also tried to alleviate the large memory consumption of DARTS. Among prior efforts, ProxylessNAS (Cai et al., 2019) binarized the multinomial distribution αoi,j and samples two paths at each time, which significantly reduced memory cost and enabled direct search on ImageNet. PARSEC (Casale et al., 2019) also proposed a sampling-based optimization method to learn a probability distribution. Our solution, by preserving all operations for architecture search, achieves a higher accuracy in particular on challenging datasets like ImageNet (+0.7% over ProxylessNAS and +1.8% over PARSEC). Another practical method towards memory efficiency is ProgressiveDARTS (Chen et al., 2019), which eliminated a subset of operators in order to provide sufficient memory for deeper architecture search. In comparison, our approach preserves all operators and instead performs sub-sampling on the channel dimension. This strategy works better in particular on large-scale datasets like ImageNet.

heading: 4 EXPERIMENTS

heading: 4.1 DATASETS AND IMPLEMENTATION DETAILS

text:
We perform experiments on CIFAR10 and ImageNet, two most popular datasets for evaluating neural architecture search. CIFAR10 (Krizhevsky & Hinton, 2009) consists of 60K images, all of which are of a spatial resolution of 32 × 32. These images are equally distributed over 10 classes, with 50K training and 10K testing images. ImageNet (Deng et al., 2009) contains 1,000 object categories, and 1.3M training images and 50K validation images, all of which are high-resolution and roughly equally distributed over all classes. Following the conventions (Zoph et al., 2018; Liu et al., 2019), we apply the mobile setting where the input image size is fixed to be 224 × 224 and the number of multi-add operations does not exceed 600M in the testing stage.
Following DARTS (Liu et al., 2019) as well as conventional architecture search approaches, we use an individual stage for architecture search, and after the optimal architecture is obtained, we conduct another training process from scratch. In the search stage, the goal is to determine the best sets of hyper-parameters, namely { αoi,j }
and {βi,j} for each edge (i, j). To this end, the trainnig set is partitioned into two parts, with the first part used for optimizing network parameters, e.g.,
convolutional weights, and the second part used for optimizing hyper-parameters. The entire search stage is accomplished in an end-to-end manner. For fair comparison, the operation spaceO remains the same as the convention, which contains 8 choices, i.e., 3×3 and 5×5 separable convolution, 3×3 and 5×5 dilated separable convolution, 3×3 max-pooling, 3×3 average-pooling, skip-connect (a.k.a., identity), and zero (a.k.a., none).
We propose an alternative and more efficient implementation for partial channel connections. For edge (i, j), we do not perform channel sampling at each time of computing o(xi), but instead choose the first 1/K channels of xi for operation mixture directly. To compensate, after xj is obtained, we shuffle its channels before using it for further computations. This is the same implementation used in ShuffleNet (Zhang et al., 2018), which is more GPU-friendly and thus runs faster.

heading: 4.2 RESULTS ON CIFAR10

text:
In the search scenario, the over-parameterized network is constructed by stacking 8 cells (6 normal cells and 2 reduction cells), and each cell consists of N = 6 nodes. We train the network for 50 epochs, with the initial number of channels being 16. The 50K training set of CIFAR10 is split into two subsets with equal size, with one subset used for training network weights and the other used for architecture hyper-parameters.
We set K = 4 for CIFAR10, i.e., only 1/4 features are sampled on each edge, so that the batch size during search is increased from 64 to 256. Besides, following (Chen et al., 2019), we freeze the hyper-parameters, { αoi,j }
and {βi,j}, and only allow the network parameters to be tuned in the first 15 epochs. This process, called warm-up, is to alleviate the drawback of the parameterized operations. The total memory cost is less than 12GB so that we can train it on most modern GPUs. The network weights are optimized by momentum SGD, with an initial learning rate of 0.1 (annealed down to zero following a cosine schedule without restart), a momentum of 0.9, and a weight decay of 3 × 10−4. We use an Adam optimizer (Kingma & Ba, 2015) for { αoi,j }
and {βi,j}, with a fixed learning rate of 6 × 10−4, a momentum of (0.5, 0.999) and a weight decay of 10−3. Owing to the increased batch size, the entire search process only requires 3 hours on a GTX 1080Ti GPU, or 1.5 hours on a Tesla V100 GPU, which is almost 4× faster than the original first-order DARTS. The evaluation stage simply follows that of DARTS. The network is composed of 20 cells (18 normal cells and 2 reduction cells), and each type of cells share the same architecture. The initial number of channels is 36. The entire 50K training set is used, and the network is trained from scratch for
600 epochs using a batch size of 128. We use the SGD optimizer with an initial learning rate of 0.025 (annealed down to zero following a cosine schedule without restart), a momentum of 0.9, a weight decay of 3× 10−4 and a norm gradient clipping at 5. Drop-path with a rate of 0.3 as well as cutout (DeVries & Taylor, 2017) is also used for regularization. We visualize the searched normal and reduction cells in the left-hand side of Figure 2.
Results and comparison to recent approaches are summarized in Table 1. In merely 0.1 GPU-days, PC-DARTS achieve an error rate of 2.57%, with both search time and accuracy surpassing the baseline, DARTS, significantly. To the best of our knowledge, our approach is the fastest one that achieves an error rate of less than 3%. Our number ranks among the top of recent architecture search results. ProxylessNAS used a different protocol to achieve an error rate of 2.08%, and also reported a much longer time for architecture search. P-DARTS (Chen et al., 2019) slightly outperforms our approach by searching over a deeper architecture, which we can integrate our approach into P-DARTS to accelerate it as well as improve its performance (consistent accuracy gain is obtained).

heading: 4.3 RESULTS ON IMAGENET

text:
We slightly modify the network architecture used on CIFAR10 to fit ImageNet. The overparameterized network starts with three convolution layers of stride 2 to reduce the input image resolution from 224× 224 to 28× 28. 8 cells (6 normal cells and 2 reduction cells) are stacked beyond this point, and each cell consists of N = 6 nodes. To reduce search time, we randomly sample two subsets from the 1.3M training set of ImageNet, with 10% and 2.5% images, respectively. The former one is used for training network weights and the latter for updating hyper-parameters.
ImageNet is much more difficult than CIFAR10. To preserve more information, we use a subsampling rate of 1/2, which doubles that used in CIFAR10. Still, a total of 50 epochs are trained and architecture hyper-parameters are frozen during the first 35 epochs. For network weights, we use a momentum SGD with an initial learning rate of 0.5 (annealed down to zero following a cosine schedule without restart), a momentum of 0.9, and a weight decay of 3× 10−5. For hyper-parameters, we use the Adam optimizer (Kingma & Ba, 2015) with a fixed learning rate of 6× 10−3, a momentum (0.5, 0.999) and a weight decay of 10−3. We use eight Tesla V100 GPUs for search, and the total batch size is 1,024. The entire search process takes around 11.5 hours. We visualize the searched normal and reduction cells in the right-hand side of Figure 2.
The evaluation stage follows that of DARTS, which also starts with three convolution layers with a stride of 2 that reduce the input image resolution from 224 × 224 to 28 × 28. 14 cells (12 normal cells and 2 reduction cells) are stacked beyond this point, with the initial channel number being 48. The network is trained from scratch for 250 epochs using a batch size of 1,024. We use the SGD
optimizer with a momentum of 0.9, an initial learning rate of 0.5 (decayed down to zero linearly), and a weight decay of 3 × 10−5. Additional enhancements are adopted including label smoothing and an auxiliary loss tower during training. Learning rate warm-up is applied for the first 5 epochs.
Results are summarized in Table 2. Note that the architectures searched on CIFAR10 and ImageNet itself are both evaluated. For the former, it reports a top-1/5 error of 25.1%/7.8%, which significantly outperforms 26.7%/8.7% reported by DARTS. This is impressive given that our search time is much shorter. For the latter, we achieve a top-1/5 error of 24.2%/7.3%, which is the best known performance to date. In comparison, ProxylessNAS (Cai et al., 2019), another approach that directly searched on ImageNet, used almost doubled time to produce 24.9%/7.5%, which verifies that our strategy of reducing memory consumption is more efficient yet effective.
0
1
2
3
4
5
6
7
8
9
10
2
2.2
2.4
2.6
2.8
3
3.2
PC-DARTS_1/1 PC-DARTS_1/2 PC-DARTS_1/4 PC-DARTS_1/8
Test Error (%) Search Cost (GPU-hours)
Figure 3: Search cost and accuracy comparison between our approach with different sampling rates, namely, 1/1, 1/2, 1/4 and 1/8, among which 1/4 makes a nice tradeoff between accuracy and efficiency.
CIFAR10 PC EN Test Error Search Cost 7 7 3.00±0.14% 0.4 GPU-days 7 3 2.82±0.05% 0.4 GPU-days 3 7 2.67±0.11% 0.1 GPU-days 3 3 2.57±0.07% 0.1 GPU-days
ImageNet (ILSVRC2012) PC EN Test Error Search Cost 7 7 26.8±0.1% 7.7 GPU-days 7 3 26.3±0.1% 7.7 GPU-days 3 7 26.2±0.1% 3.8 GPU-days 3 3 25.8±0.1% 3.8 GPU-days
Table 3: Ablation study on CIFAR10 and ImageNet. PC and EN denote partial channel connections and edge normalization, respectively. All architectures on ImageNet are re-trained by 100 epochs (the 25.8% error corresponds to the best entry, 24.2%, reported in Table 2 (250 epochs).

heading: 4.4 ABLATION STUDY

text:
4.4.1 EFFECTIVENESS OF CHANNEL PROPORTION 1/K
We first evaluate K, the hyper-parameter that controls the sampling rate of channels. Note that a tradeoff exists: increasing the sampling rate (i.e., using a smaller K) allows more accurate infor-
mation to be propagated, while sampling a smaller portion of channels casts heavier regularization and may alleviate over-fitting. To study its impacts, we evaluate the performance produced by four sampling rates, namely 1/1, 1/2, 1/4 and 1/8, on CIFAR10, and plot the results into a diagram of search time and accuracy in Figure 3. One can observe that a sampling rate of 1/4 yields superior performance over 1/2 and 1/1 in terms of both time and accruacy. Using 1/8, while being able to further reduce search time, causes a dramatic accuracy drop.
These experiments not only justify the tradeoff between accuracy and efficiency of architecture search, but also reveal the redundancy of super-network optimization in the context of NAS. More essentially, this reflects the gap between search and evaluation, i.e., a better optimized super-network does not guarantee a better searched architecture – in other words, differentiable NAS approaches are easily to over-fit on the super-network. From this viewpoint, channel sampling plays the role of regularization, which shrinks the gap between search and evaluation.

heading: 4.4.2 CONTRIBUTIONS OF DIFFERENT COMPONENTS OF PC-DARTS

text: Next, we evaluate the contributions made by two components of PC-DARTS, namely, partial channel connections and edge normalization. The results are summarized in Table 3. It is clear that edge normalization brings the effect of regularization even when the channels are fully-connected. Being a component with very few extra costs, it can be freely applied to a wide range of approaches involving edge selection. In addition, edge normalization cooperates well with partial channel connections to provide further improvement. Without edge normalization, our approach can suffer low stability in both the number of network parameters and accuracy. On CIFAR10, we run search without edge normalization for several times, and the testing error ranges from 2.54% to 3.01%. On the other hand, with edge normalization, the maximal difference among five runs does not exceed 0.15%. Therefore, we justify our motivation in designing edge normalization (see Section 3.3), i.e., it can be a standalone method for stabilizing architecture search, yet it works particularly well under partial channel connection, since the latter introduces randomness and stabilization indeed helps.

heading: 4.4.3 STABILITY OF OUR APPROACH

text:
In this part, we demonstrate the stability of our approach from three different perspectives. Results are summarized in Table 4, with detailed analysis below.
First, we evaluate the stability of different approaches by conducting 5 independent search runs. We re-implement DARTS-v1 and DARTS-v2 with the proposed code, as well as that of our approach, and perform five individual search processes with the same hyper-parameters but different random seeds (0, 1, 2, 3, 4). The architectures found by DARTS in different runs, either v1 or v2, suffer much higher standard deviations than that of our approach (DARTS-v1: ±0.15%, DARTS-v2: ±0.21%, PC-DARTS: ±0.07%). Second, we study how the search algorithm is robust to hyper-parameters, e.g., the length of the search stage. We try different numbers of epochs, from 50 to 125, and observe how it impacts the performance of searched architectures. Again, we find that both DARTS-v1 and DARTS-v2 are less robust to this change.
Third, we go one step further by enlarging the search space, allowing a larger number of nodes to appear in each cell – the original DARTS-based space has 6 nodes, and here we allow 5, 6 and 7 nodes. From 5 to 6 nodes, the performance of all three algorithms goes up, while from 6 to 7 nodes, DARTS-v2 suffers a significant accuracy drop, while PC-DARTS mostly preserves it performance.
As a side note, all these algorithms fail to gain accuracy in enlarged search spaces, because CIFAR10 is relatively simple and the performance of searched architectures seems to saturate.
With all the above experiments, we can conclude that PC-DARTS is indeed more robust than DARTS in different scenarios of evaluation. This largely owes to the regularization mechanism introduced by PC-DARTS, which (i) forces it to adjust to dynamic architectures, and (ii) avoids the large pruning gap after search, brought by the none operator.

heading: 4.5 TRANSFERRING TO OBJECT DETECTION

text:
To further validate the performance of the architecture found by PC-DARTS, we use it as the backbone for object detection. We plug the architecture found on ImageNet, as shown in Figure 2, into a popular object detection framework named Single-Shot Detectors (SSD) (Liu et al., 2016). We train the entire model on the MS-COCO (Lin et al., 2014) trainval dataset, which is obtained by a standard pipeline that excludes 5K images from the val set, merges the rest data into the 80K train set and evaluates it on the test-dev 2015 set.
Results are summarized in Table 5. Results for SSD, YOLO and MobileNets are from (Tan et al., 2019). With the backbone searched by PC-DARTS, we need only 1.2B FLOPs to achieve an AP of 28.9%, which is 5.7% higher than SSD300 (but with 29× fewer FLOPs), or 2.1% higher than SSD512 (but with 83× fewer FLOPs). Compared to the ‘Lite’ versions of SSD, our result enjoys significant advantages in AP, surpassing the most powerful one (SSDLiteV3) by an AP of 6.9%. All these results suggest that the advantages obtained by PC-DARTS on image classification can transfer well to object detection, a more challenging task, and we believe these architectures would benefit even more application scenarios.

heading: 5 CONCLUSIONS

text:
In this paper, we proposed a simple and effective approach named partially-connected differentiable architecture search (PC-DARTS). The core idea is to randomly sample a proportion of channels for operation search, so that the framework is more memory efficient and, consequently, a larger batch size can be used for higher stability. Additional contribution to search stability is made by edge normalization, a light-weighted module that requires merely no extra computation. Our approach can accomplish a complete search within 0.1 GPU-days on CIFAR10, or 3.8 GPU-days on ImageNet, and report state-of-the-art classification accuracy in particular on ImageNet.
This research delivers two important messages that are important for future research. First, differentiable architecture search seems to suffer even more significant instability compared to conventional neural network training, and so it can largely benefit from both (i) regularization and (ii) a larger batch size. This work shows an efficient way to incorporate these two factors in a single pipeline, yet we believe there exist other (possibly more essential) solutions for this purpose. Second, going one step further, our work reveals the redundancy of super-network optimization in NAS, and experiments reveal a gap between improving super-network optimization and finding a better architecture, and regularization plays an efficient role in shrinking the gap. We believe these insights can inspire researchers in this field, and we will also follow this path towards designing stabilized yet efficient algorithms for differentiable architecture search.

title: MEMORY-EFFICIENT ARCHITECTURE SEARCH


summaries: This paper studies optimal control problems where a physical simulator of the system is available, which outputs the gradient of the dynamics. Using the gradients proposed by the model, the authors propose to add two additional terms in the loss function for critic training in DDPG, where these to terms corresponding to the prediction error of $\nabla_{a} Q(s,a)$ and $\nabla_b Q(s,a)$, respectively. However, my main concern is that the form of gradient given in equation (2) might contains an error.

summaries: DDPG is a popular RL method for continuous control problems. It is more widely applicable than traditional model-based approaches like MPC, since it doesn't require differentiable models of the dynamics. However, in many environments, dynamics are differentiable. This paper proposes a method for extending DDPG to exploit simulator gradients. In particular, the Bellman error objective (which is defined in terms of critic values) used for training the critic is augmented with additional terms defined in terms of gradients of the critic. This leads to faster convergence in practice on a range of benchmarks.

abstractText: Over the last decade, two competing control strategies have emerged for solving complex control tasks with high efficacy. Model-based control algorithms, such as model-predictive control (MPC) and trajectory optimization, peer into the gradients of underlying system dynamics in order to solve control tasks with high sample efficiency. However, like all gradient-based numerical optimization methods, model-based control methods are sensitive to initialization and are prone to becoming trapped in local minima. Deep reinforcement learning (DRL), on the other hand, can somewhat alleviate these issues by exploring the solution space through sampling — at the expense of computational cost. In this paper, we present a hybrid method that combines the best aspects of gradient-based methods and DRL. We base our algorithm on the deep deterministic policy gradients (DDPG) algorithm and propose a simple modification that uses true gradients from a differentiable physical simulator to increase the convergence rate of both the actor and the critic. We demonstrate our algorithm on seven 2D robot control tasks, with the most complex one being a differentiable half cheetah with hard contact constraints. Empirical results show that our method boosts the performance of DDPG without sacrificing its robustness to local minima.

authors:
Brandon Amos
J. Zico Kolter

title: OptNet: Differentiable optimization as a layer in neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
James M Bern
Pol Banzet
Roi Poranne
Stelian Coros

title: Trajectory optimization for cable-driven soft robot locomotion

venue: In Robotics: Science and Systems,

authors:
M.B. Cline
D.K. Pai

title: Post-stabilization for rigid body simulation with contact and constraints

venue: IEEE International Conference on Robotics and Automation (Cat. No.03CH37422),

authors:
Filipe de Avila Belbute-Peres
Kevin Smith
Kelsey Allen
Josh Tenenbaum
J Zico Kolter

title: End-to-end differentiable physics for learning and control

venue: In Advances in Neural Information Processing Systems,

authors:
Jonas Degrave
Michiel Hermans
Joni Dambre

title: A differentiable physics engine for deep learning in robotics

venue: Frontiers in neurorobotics,

authors:
Shixiang Gu
Timothy Lillicrap
Ilya Sutskever
Sergey Levine

title: Continuous deep Q-learning with model-based acceleration

venue: In International Conference on Machine Learning,

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
Tuomas Haarnoja
Aurick Zhou
Sehoon Ha
Jie Tan
George Tucker
Sergey Levine

title: Learning to walk via deep reinforcement learning

venue: arXiv preprint arXiv:1812.11103,

authors:
Nikolaus Hansen
Sibylle D Müller
Petros Koumoutsakos

title: Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es)

venue: Evolutionary computation,

authors:
Yuanming Hu
Jiancheng Liu
Andrew Spielberg
Joshua B Tenenbaum
William T Freeman
Jiajun Wu
Daniela Rus
Wojciech Matusik

title: Chainqueen: A real-time differentiable physical simulator for soft robotics

venue: International Conference on Robotics and Automation,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Vikash Kumar
Emanuel Todorov
Sergey Levine

title: Optimal control with learned local models: Application to dexterous manipulation

venue: In 2016 IEEE International Conference on Robotics and Automation (ICRA),

authors:
Ian Lenz
Ross A Knepper
Ashutosh Saxena

title: Deepmpc: Learning deep latent features for model predictive control

venue: In Robotics: Science and Systems. Rome, Italy,

authors:
Yunzhu Li
Jiajun Wu
Jun-Yan Zhu
Joshua B Tenenbaum
Antonio Torralba
Russ Tedrake

title: Propagation networks for model-based control under partial observation

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Zachary Manchester
Scott Kuindersma

title: Variational contact-implicit trajectory optimization

venue: In International Symposium on Robotics Research (ISRR), Puerto Varas,

authors:
Andrew D Marchese
Russ Tedrake
Daniela Rus

title: Dynamics and trajectory optimization for a soft spatial fluidic elastomer manipulator

venue: The International Journal of Robotics Research,

authors:
Matthew Moore
Jane Wilhelms

title: Collision detection and response for computer animation

venue: In Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques,

authors:
Xue Bin Peng
Glen Berseth
Michiel Van de Panne

title: Terrain-adaptive locomotion skills using deep reinforcement learning

venue: ACM Transactions on Graphics (TOG),

authors:
Matthias Plappert
Rein Houthooft
Prafulla Dhariwal
Szymon Sidor
Richard Y. Chen
Xi Chen
Tamim Asfour
Pieter Abbeel
Marcin Andrychowicz

title: Parameter space noise for exploration

venue: URL http://arxiv.org/abs/1706.01905

authors:
Jovan Popović
Steven M. Seitz
Michael Erdmann
Zoran Popović
Andrew Witkin

title: Interactive manipulation of rigid body simulations

venue: In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques,

authors:
Michael Posa
Cecilia Cantu
Russ Tedrake

title: A direct method for trajectory optimization of rigid bodies through contact

authors:
Connor Schenck
Dieter Fox

title: Spnets: Differentiable fluid dynamics for deep neural networks

venue: Conference on Robot Learning (CoRL),

authors:
Yuval Tassa
Tom Erez
Emanuel Todorov

title: Synthesis and stabilization of complex behaviors through online trajectory optimization

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Yuval Tassa
Nicolas Mansard
Emo Todorov

title: Control-limited differential dynamic programming

title: Underactuated robotics: Algorithms for walking, running, swimming, flying, and manipulation (course notes for mit 6.832)

authors:
Emanuel Todorov
Weiwei Li

title: A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems

venue: In Proceedings of the 2005, American Control Conference,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

authors:
Alexander W Winkler
C Dario Bellicoso
Marco Hutter
Jonas Buchli

title: Gait and trajectory optimization for legged systems through phase-based end-effector parameterization

venue: IEEE Robotics and Automation Letters,

authors:
Akihiko Yamaguchi
Christopher G Atkeson

title: Neural networks and differential dynamic programming for reinforcement learning problems

heading: 1 INTRODUCTION

text:
In recent years, deep reinforcement learning (DRL) has emerged as a flexible and robust means of teaching simulated robots to complete complex tasks, from manipulation (Kumar et al., 2016) and locomotion (Haarnoja et al., 2018b), to navigating complex terrain (Peng et al., 2016). Compared with more direct optimization methods such as gradient descent or second-order optimization, DRL naturally incorporates exploration into its planning, allowing it to learn generalizable policies and robust state value estimations across simulated environments. Perhaps the most salient reason for DRL’s surge in popularity is its ability to operate on black-box simulators where the underlying dynamics model is not available. DRL’s model-free, Monte-Carlo-style methods have made it applicable to a wide range of physical (and non-physical) simulation environments, including those where a smooth, well-behaved dynamical model does not exist. This comes at two striking costs. First, such sampling procedures may be inefficient, requiring a large number of samples for adequate learning. Second, in order to be generally applicable to any model-free environment, underlying dynamical gradients are not used, even if they are available. In other words, valuable information that could greatly aid control tasks is not taken advantage of in these schemes.
When an accurate model of robot dynamics is given, model-based methods such as model-predictive control (MPC) or trajectory optimization have historically been employed. These methods can solve tasks with higher sample efficiency than model-free DRL algorithms. Models provide access to ground-truth, analytical gradients of robot physics without the need for sample-based estimation. However, such methods don’t incorporate exploration or learning into their procedures, and are especially prone to becoming trapped in poor local minima.
While there has been a recent surge in fast and accurate differentiable simulators not previously available, most applications for control have relied on established local methods such as MPC (de Avila Belbute-Peres et al., 2018), gradient descent (Degrave et al., 2019), or trajectory
optimization (Hu et al., 2019) to solve control tasks. An ideal algorithm would exploit the efficiency of model-based methods while maintaining DRL’s relative robustness to poor local minima.
In this paper, we propose an actor-critic algorithm that leverages differentiable simulation and combines the benefits of model-based methods and DRL. We build our method upon standard actor-critic DRL algorithms and use true model gradients in order to improve the efficacy of learned critic models. Our main insights are twofold: First, gradients of critics play an important role in certain DRL algorithms, but optimization of these critics’ gradients has not been explored by previous work. Second, the emergence of differentiable simulators enables computation of advantage estimation (AE) gradients with little additional computational overhead. Based on these observations, we present an algorithm that uses AE gradients in order to co-learn critic value and gradient estimation, demonstrably improving convergence of both actor and critic.
In this paper, we contribute the following: 1) An efficient hybrid actor-critic method which builds upon deep deterministic policy gradients (DDPG, (Lillicrap et al., 2015)), using gradient information in order to improve convergence in a simple way. 2) A principled mathematical framework for fitting critic gradients, providing a roadmap for applying our method to any deterministic policy gradient method, and 3) Demonstrations of our algorithm on seven control tasks, ranging from contact-free classic control problems to complex tasks with accurate, hard contact, such as the HalfCheetah, along with comparisons to both model-based control and DRL baselines.

heading: 2 RELATED WORK

text:
Model-based control methods peer into the underlying dynamics of a system in order to optimize control parameters. Such approaches have especially grown in popularity with the rise of differentiable simulators, whose application now spans rigid body simulation (de Avila Belbute-Peres et al., 2018; Degrave et al., 2019), soft body simulation (Hu et al., 2019), and fluid dynamics (Schenck & Fox, 2018; Li et al., 2019). Such simulators allow for backward propagating through an entire simulation, and even the simplest optimization algorithms (gradient descent) can be employed to a great effect. By treating robotic control tasks as a nonlinear numerical optimization problem, two more sophisticated strategies, trajectory optimization (Posa et al., 2014; Manchester & Kuindersma, 2017; Winkler et al., 2018; Marchese et al., 2016; Bern et al., 2019) and model-predictive control (MPC) (Todorov & Li, 2005; Tassa et al., 2012; 2014; Lenz et al., 2015), employ established numerical optimization techniques to efficiently solve complex, even high-dimensional control tasks. But, these methods are are prone to becoming trapped in poor local minima, especially in the presence of complex dynamics or terrain.
Separate from model-based control methods, which assume the model of dynamics is known, modelbased learning methods (Gu et al., 2016; Yamaguchi & Atkeson, 2016) attempt to learn a prior unknown model so as to directly optimize policies. In this paper, we do not focus on model-based learning, but rather the complementary problem, where we assume an accurate model of dynamics is given by a differentiable simulator and we use it to efficiently explore optimal control parameters.
In contrast to the above local methods, stochastic global optimization methods, such as evolutionary algorithms (e.g., (Hansen et al., 2003)) or simulated annealing, explore the solution space with a large number of samples in order to find global optima. Such methods, however, can be quite slow, due to the large number of samples they require. RL, while technically local, naturally incorporates sampling, exploration, and value function learning in a similar way that greatly mitigates optimization’s propensity to becoming trapped in poor local minima. Our algorithm similarly incorporates exploration to mitigate the likelihood of poor local minima, while using gradient information to do so with high sample efficiency.

heading: 3 METHOD

heading: 3.1 PRELIMINARIES

text:
Markov-Decision Problems (MDP) In this paper, we consider the rigid body simulation as a discrete-time Markov Decision Process (MDP) defined by (S,A,Γ,R), where S ⊆ Rn is the state space,A ⊆ Rm is the action space, Γ : S ×A → S is the deterministic dynamic transition function,
andR : S ×A× S → R is the reward function. The optimal control policy π : S → A maximizes the γ-discounted sum of reward η(π) over a finite time horizon T , which is defined as:
η(π) = Eρ0,π[ T−1∑ t=0 γtrt].
Here ρ0 specifies the distribution of the initial state s0 and rt = r(st, at, st+1) represents the reward collected at time step t. We represent the policy function π as a neural network parameterized by θ and assume πθ is a deterministic policy that takes as input the current state st and predicts the next action at = πθ(st).
The action-value function Qπ(st, at), which describes the expected return given the action at and state st at step t, is defined as
Qπ(st, at) = Est+1,at+1,···[ T−1∑ l=t γl−trl(sl, al, sl+1)], (1)
in which al ∼ π(sl) and sl ∼ Γ(sl−1, al−1). The expectation can be removed in our case since both Γ and π are deterministic. This function is approximated by the critic network Qφ(s, a) parameterized with φ.
Differentiable simulators In this paper, we focus on differentiable and deterministic rigid body simulators with fully observable states. At each time step t, the state st fully characterizes the current status of the robot. The simulator takes current state st and an action at as input and returns the next state st+1 by solving the governing physical equations.Additionally, we assume a differentiable simulator also returns a Jacobian matrix ∇st,atst+1. For all the differentiable rigid body simulators in this paper, the time and space complexities of computing the Jacobian matrix are the same as computing st+1 in one forward step.

heading: 3.2 ALGORITHM

text:
Our hybrid algorithm takes inspiration from a subclass of modern actor-critic algorithms which seek to improve actor policies via critic gradients (such as DDPG). These algorithms iteratively improve the model of the critic, or estimated future return, using recorded data. Such algorithms implicitly assume that if the critic is well-fit to reality, then the gradients must also be well-fit. If we want to prioritize accurate critic gradients and better bootstrap our actor learning, it is best to ensure this directly. Specifically, we augment DDPG’s critic gradient fitting step with a regularization term which prioritizes fitting accurate gradients in addition to accurate returns. Our choice of working in the domain of deterministic policy gradients is deliberate; as will be seen, this framework allows us to use our differentiable simulation engine to back propagate through the state-action pairs of our MDP, generating ground-truth reward gradients to fit.
Algorithm 1 summarizes our method with our modifications to the original DDPG highlighted in color. Like actor-critic methods, our algorithm populates a replay buffer of state-action pairs from which to learn. At the same time, it records the dynamical Jacobian ∇st,atst+1 corresponding to those state-action pairs, without degrading its asymptotic time or space complexity. Like the state-action pairs, these Jacobians need only be computed during rollouts; they can be re-used during the embedded supervised training steps to efficiently improve the actor and critic networks.
With additional Jacobian information about the dynamics at hand, we compute the gradients of the target network Q̂i. Since Q̂i defines the target value that the critic Qφ attempts to fit to, ∇Q̂i provides a good estimation to the
desired ∇Q as well. This motivates us to use it as a regularizer in the critic loss (Line 10 in Algorithm 1) with two additional weights w1 and w2 corresponding to the weights on the two partial
derivatives. The definition of ∇si,aiQ̂i is provided by the following equation (For brevity, we use the network names to refer to their output values in the equation):
∇si,aiQ̂i =∇si,airi +∇si+1ri · ∇si,aisi+1 + γ(∇si+1Q′ +∇π′Q′ · ∇si+1π′)∇si,aisi+1, (2)
which can be evaluated in constant time (Figure 1). It is important to note that this computation is only possible when a differentiable simulator is available due to the need for∇si,aisi+1.
Time and space complexity Our modifications require extra storage space for two Jacobian matrices of the size dim(s) × dim(s) and dim(s) × dim(a) associated with each si in the replay buffer, which is tolerable as long as the dimensions of s and a are small constants. This is the case, for example, in rigid robot control tasks. In terms of the time cost, computing ∇Q̂i makes efficient use of the cached data. As a result, its computation requires only a handful of matrix multiplications and back-propagation through Q′ and π′.
Algorithm 1 Hybrid DDPG algorithm Require: Differentiable simulator Γ, actor network µθ, critic network Qφ, weighting factors w1,
w2, damping constant τ 1 1: Initialize two target networks π′ = πθ and Q′ = Qφ 2: Initialize a replay buffer B 3: Get the initial state s0 4: while True do 5: Generate a random process N 6: Simulate the agent using at = π(st) +Nt at each time step t until termination 7: Store all (st, at, rt, st+1,∇stst+1,∇atst+1) to B 8: Sample a random minibatch of n transitions (si, ai, ri, si+1,∇sisi+1,∇aisi+1) from B 9: Set Q̂i = ri + γQ′(si+1, π′(si+1)).
10: Update the critic parameter φ by minimizing the loss:
L = 1
n ∑ i ∥∥Qφ(si, ai)− Q̂i∥∥2 + w1∥∥∇aiQφ −∇aiQ̂i∥∥2 + w2∥∥∇siQφ −∇siQ̂i∥∥2 11: Update the actor parameter θ using the following gradient:
∇θη ≈ 1
n ∑ i ∇aQφ(si, a)|a=πθ(si)∇θπ(si)
12: Update target networks: π′ = τπθ + (1− τ)π′
Q′ = τQφ + (1− τ)Q′
13: end while

heading: 3.3 A MOTIVATING EXAMPLE

text:
We present a simple, analytical example with easily understandable dynamics in a low-dimensional space in order to illustrate the insights behind our algorithm. Consider a one dimensional kinematic mass point whose state st and action at are two scalars describing its position and velocity respectively. We define s0 = −0.5 and at ∈ [−1, 1]. The new state is computed by st+1 = st + at∆t where ∆t = 0.01 is a constant. The goal is to move the mass point to the origin s = 0 as quickly as possible. The simulation is terminated when |st| < 0.01. The reward r(s, a, s′) = (s2 + 1)−1 − 1 encourages the mass point to converge to the origin in minimal number of steps.
To see how the regularizer affects the training of the critic network, we compare results from four sets of (w1, w2) parameters: (0, 0), corresponding to the original DDPG algorithm; (0, 1), which only regularizes ∇siQ̂i; (1, 0), which only regularizes ∇aiQ̂i; and (1, 1), which regularizes both ∇siQ̂i and ∇aiQ̂i. We plot the surfaces of intermediate critic network Q, their ground truth, and the return-timestep curves in Figure 2. In particular, the surfaces of ground truth Q for the optimal controller π are discounted returns directly measured from the forward simulation.
Given these surfaces, the critic update steps in DDPG and the benefits of the regularizer can be explained visually: At each iteration, DDPG updates the critic network to fit the Q surface with points (si, ai, Q̂i(si, ai)), which are sampled from the replay buffer. Additionally, our hybrid method adds the regularizers to also fit the tangent directions of Q surface at the sample points. The tangent direction of the curveQ(·, ai) at s = si is equivalent to∇aiQ̂i. Since these tangent directions provide more information about the local shape of the Q surface, it is expected to boost the convergence of Q to its ground truth, which is reflected in Figure 2.
We can also use this example to understand the effects of w1 and w2 on the convergence of Q: Figure 2 (c and d) demonstrate that w2, or the weight for ∇siQ̂i, has a more evident effect on the convergence of Q. This can be partially explained by the fact that the ground truth Q surface has little variation in the a (action) direction, so knowing the partial derivative ∇aiQ̂i adds very little new information to the fitting problem.

heading: 4 IMPLEMENTATION

heading: 4.1 DIFFERENTIABLE SIMULATORS

text:
We test our hybrid algorithm on robot control tasks using a differentiable rigid body simulator, over three different types of settings related to the types of contact experienced:
Contact-free simulation Many classical control examples are contact-free and useful for evaluating and understanding the performance of control algorithms (e.g. Pendulum, Acrobot, etc.). The equations of the motion of these problems can be compactly expressed in the form of the standard manipulator equations (Tedrake, 2019), allowing for the simple extraction of system gradients.
Simulation with impulse-based collision responses Due to the significant changes in motion that occur during collisions, rigid body simulations with contacts possess much more complex dynamics than those which are contact-free. In this setting, we employ the Poisson collision model (Moore & Wilhelms, 1988). During collision, an impulse is applied to the rigid body, instantaneously changing the velocity of the rigid body while conserving the momentum of the entire system. For simulating systems with such contacts, we follow (Popović et al., 2000).
Simulation with constraint-based collision responses In order to simulate realistic motions for resting and collision contacts among rigid bodies, constraint-based methods formulate contacts as constrained systems, posing them as linear complementary problems (LCP) (Cline & Pai, 2003). Such simulation is accurate but much more complex than previous, simpler soft contact models. Inspired by the work of Amos & Kolter (2017), we implemented a 2D LCP-based rigid body simulator and differentiate through contacts.

heading: 4.2 THE HYBRID ALGORITHM

text: Our hybrid control algorithm is implemented based on DDPG in OpenAI Baselines (Dhariwal et al., 2017). Parameter space noise is applied to the actor network for exploration as proposed in (Plappert et al., 2017). Slightly different from the mathematical definition, the critic network in this implementation takes normalized state and action as input, and outputs a normalized Q value in order to achieve task-irrelevant statistical stability. The mean value and standard deviation of state and Q value are empirically estimated from the replay buffer. Actions are scaled by a constant such that they fall in range [−1, 1]. Similarly, gradients in line 11 of Algorithm 1 are computed with normalized Q, states and actions.

heading: 5 RESULTS

heading: 5.1 ENVIRONMENTS

text:
We present seven 2D control tasks implemented in our differentiable rigid body simulator. The tasks are of varying difficulty, including five classic control problems (CartPole, CartPoleSwingUp, Pendulum, MountainCar, and Acrobot), one problem with impulse-based collision response (RollingDie), and one complex control problem with LCP-based contact model (HalfCheetah).
Classic control environments Our implementation of CartPole, CartPoleSwingUp, Pendulum, MountainCar, and Acrobot is based on the implementation of OpenAI Gym (Brockman et al., 2016) but with gradient information manually computed in the simulation. We ask readers to refer to (Brockman et al., 2016) for more details.
Environment with impulse-based collision responses In order to demonstrate applicability in the context of collisions, we designed a RollingDie task with impulse-based collision responses. The die is thrown from the air to the ground. Its initial state s0 includes position in x and y, rotation angle, velocity in x and y, and angular velocity. The action a is the torque to the die, i.e. each step, the die can apply an internal torque so as to control its angular velocity (and thus its pose). The reward is defined based on the L2−norm of the distance between die center and the target position. Though for most of its trajectory the die is free falling and thus its position cannot be impacted by the torque, the angular velocity and torque do impact the angle with which the die impacts the ground and the resulting bounce. This is a complex control task in which sparse, highly important moments (contact) can chaotically affect the trajectory of the die. Note that the die is allowed to bounce multiple times during the simulation, which increases the complexity of finding an optimized control.
Environment with LCP-based collision responses We designed a differentiable HalfCheetah example with LCP-based contacts. The HalfCheetah shares a similar structure as the one in MuJoCo (Todorov et al., 2012) but only has two links on each leg. The reward is defined as vx−0.1uTu, promoting forward velocity while penalizing highly actuated actions. Note that unlike MuJoCo’s soft contact model, the hard contact model we implemented introduces an additional complexity and higher magnitude gradients, making it a more difficult control task.

heading: 5.2 EVALUATION

text:
We compare our method with three baselines: DDPG, the RL algorithm that we base our method on, MPC with iterative Linear Quadratic Regulartor (iLQR) (Tassa et al., 2014), a state-of-the-art model-based control algorithms employed in previous work on differentiable simulators (Gu et al., 2016), and gradient descent (GD), which employs a neural network actor and Adam (Kingma & Ba,
2014) to directly optimize a final return using the analytical gradients (as in (Hu et al., 2019) and (Degrave et al., 2019)). We repeat each algorithm 16 times on each task with different initializations.
Initialization To ensure a fair comparison between all methods, we seed each algorithm with the same network models (if applicable). Since MPC does not require a neural network but directly solves for state and action variables, we initialize these variables by performing one rollout and collecting the state-action (st, at) pairs for initialization, using the same initial actor network.
Metrics For methods using a neural network controller (ours, DDPG, and GD), we report the following metrics: return mean, which is the return from one episode generated by running the intermediate actor network every 800 timesteps, and return history, which is the average of the latest 100 return mean. For MPC, as it solves at sequentially, return mean is stored whenever at is returned. All returns are rescaled linearly so that the average return of a random controller is mapped to 0 and max(r)× T is mapped to 1.
Results and discussions Figure 4 and Table 1 summarize the performance and averaged rewards of each method on the seven environments. Overall, our algorithm improves the sampling efficiency of DDPG and often discovers strategies with higher return. Compared with MPC and GD, our method suffers less from local minima, especially for more complex tasks such as HalfCheetah. For all environments, the experiment is terminated when return mean plateaus in GD, when MPC converges, or when the number of timesteps reaches pre-defined maximum number in DDPG and our algorithm. Unlike the other methods, MPC does not perform many sequential simulations, but rather performs one simulation optimized online. In order to perform as fair of a comparison as possible, we plot the predicted cumulative return (based on the previously simulated steps, current planned horizon, and remaining initialized action vector) as it evolves throughout the online planning procedure. As a result, MPC may terminate without using the same number of function evaluations as RL algorithms or showing a sign of plateauing return-timestep curves. We do not compare MPC for the simpler control tasks (Pendulum, MountainCar, CartPole) that are trivial for the algorithm to solve. We also do not compare MPC for the Acrobot, for which the algorithm cannot be applied (discussed later). We discuss the performances of these methods in each environment below.
Immediately obvious from our results is the fact that DDPG and our algorithm are both competitive on all problems presented, regardless of problem difficulty. While MPC dominates on the simplest control tasks, it struggles on the more complicated tasks with hard contacts, and DRL approaches dominate. This underscores our thesis — that DRL’s exploration properties make it better suited than model-based approaches for problems with a myriad of poor local minima. More naı̈ve model-based approaches, such as GD, can succeed when they begin very close to a local minimum — as is the case with CartPole — but show slow or no improvement in dynamical environments with nontrivial control schemes. This is especially apparent in problems where the optimal strategy requires robots to make locally suboptimal motions in order to build up momentum to be used to escape local minima later. Examples include Pendulum, CartPoleSwingUp, and MountainCar, where the robot must learn to build up momentum through local oscillations before attempting to reach a goal. GD further fails on complex physical control tasks like HalfCheetah, where certain configurations, such as toppling, can be unrecoverable. Finally, we note that although MPC is able to tractably find a good solution for the RollingDie problem, the complex nonlinearities in the contact-heavy dynamics require long planning horizons (100 steps, chosen by running hyperparameter search) in order to find a good trajectory. Thus, although MPC eventually converges to a control sequence with very high reward, it requires abundant computation to converge. DRL-based control approaches are able to find success on all problems, and are especially competitive on those with contact.
Compared with DDPG, our hybrid algorithm universally converges faster or to higher returns. The rolling die example presents a particularly interesting contrast. As the die is randomly initialized, it is more valuable to aim for higher return history rather than return mean due to the large variance in the initial state distribution. It can be seen from Figure 4 that our method managed to reach a higher average return history over 16 runs. Manually visualizing the controller from the best run in our method revealed that it discovered a novel two-bounce strategy for challenging initial poses (Figure 3), while most of the strategies in DDPG typically leveraged one bounce only.
There are a few other reasons why our algorithm may be considered superior to MPC. First, our algorithm is applicable to a wider range of reward structures. While we had planned to demonstrate
MPC on another classic control problem, namely the Acrobot, MPC is inapplicable to this robot’s reward structure. The Acrobot’s rewards penalize it with −1 point for every second it has not reached its target pose. MPC requires a differentiable reward, and this reward structure is not. Thus, our Hybrid DDPG algorithm applies to a wider range of problems than MPC. Second, closedloop network controllers are naturally more robust than MPC. Even as noise is added or initial conditions and tasks change, learned controllers can generalize. While MPC can recover from these scenarios, it requires expensive replanning. In these scenarios, MPC becomes especially unattractive to deploy on physical hardware, where power and computational resource constraints can render MPC inapplicable to realtime applications.
6 CONCLUSION
In this paper, we have presented an actor-critic algorithm that uses AE gradients to co-learn critic value and gradient estimation and improve convergence of both actor and critic. Our algorithm leverages differentiable simulation and combines the benefits of model-based methods and DRL. We designed seven 2D control tasks with three different contact scenarios and compared our method with several state-of-the-art baseline algorithms. We demonstrated our method boosts the performance of DDPG and is much less sensitive to local minima than model-based approaches. In the future, it would be interesting to see if our mathematical framework can be applied to improve the effectiveness of value functions used in other DRL algorithms.

heading: A APPENDIX

text:
A.1 THE CHOICE OF LOSS FUNCTION IN ALGORITHM 1
In gradient-based optimization algorithms, the direction of gradients often plays a more crucial role than its length, especially when adaptive learning rates are applied. Here we experiment with the idea of penalizing the cosine angle between∇Qφ and∇Q̂ instead of their L2 distance in Algorithm 1. In particular, we replace line 10 with the following:
L = 1
n ∑ i ‖Qφ(si, ai)− Q̂i‖2 +w1(1− ∇aiQφ · ∇aiQ̂i ‖∇aiQφ‖‖∇aiQ̂i‖ ) +w2(1− ∇siQφ · ∇siQ̂i ‖∇siQφ‖‖∇siQ̂i‖ ) (3)
Figure 5 shows the experimental results in our differentiable environments with the new loss function. For each environment, we started with the same parameters as in Figure 4 and decreased (w1, w2) ∈ {1, 0.1, 0.01} only if necessary. We ended up using the same parameters as before in MountainCar and Acrobot and switched weights in other environments.
Comparing Figure 4 with Figure 5, we see the cosine angle regularizer is more effective in some examples (particularly MountainCar and Acrobot) than the original L2 norm. The L2 regularizer outperforms the cosine angle for CartPoleSwingUp. The two regularizers perform similarly on the remaining examples.
A.2 RESULTS ON SOFT ACTOR-CRITIC (SAC)
Apart from DDPG, we have also implemented our method with the original L2-norm loss in the Soft Actor-Critic (SAC) (Haarnoja et al., 2018a) algorithm. Figure 6 reports our experimental results in five examples, among which our method improves the performance of the original SAC in three of them (CartPoleSwingUp, Pendulum, and MountainCar) and performs similarly in the other two. These results have demonstrated that our proposed modification can be generalized to other actorcritic methods other than DDPG.

title: DPG: DEEP DIFFERENTIABLE DETERMINISTIC POL-