text:
\section{Introduction}\label{introduction}
\vspace{-0.4em}
Network architecture search (NAS)~\cite{zoph2016neural} is an effective approach for automating  network architecture design, with many successful applications witnessed to  image recognition~\cite{zoph2018learning,pham2018efficient,real2019regularized,tan2019mnasnet,liu2018darts} and language modeling~\cite{zoph2016neural,liu2018darts}. The methodology of NAS is to automatically search for a directed graph and its  edges  from a huge search space. Unlike expert-designed architectures which  require  substantial efforts from  experts by trial  and error, the automatic principle in NAS greatly alleviates   these design efforts  and possible design bias brought by  experts which could  prohibit achieving better performance.  Thanks to these advantages, NAS has been widely devised via reinforcement learning (RL) and  evolutionary algorithm (EA),   and    achieved  promising results in many applications, \emph{e.g.}~classification~\cite{zoph2018learning,real2019regularized}.

DARTS~\cite{liu2018darts} is a recently developed  leading approach. Different from RL and EA based methods~\cite{zoph2016neural,zoph2018learning,pham2018efficient,real2019regularized} that discretely optimize  architecture parameters, DARTS converts the  operation selection for each edge in the directed graph into continuously   weighting a fixed set of operations. In this way, it  can optimize the architecture parameters via gradient descent and greatly reduces the high search cost in RL and EA approaches.  However, as observed in  the literatures~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts} and Fig.~\ref{illustrationcomponents} (a), this differential  NAS family, including DARTS and its variants~\cite{dong2019searching,wu2019fbnet}, typically selects many skip connections which dominate over other types of operations in the network graph. Consequently,  the searched networks are observed to have unsatisfactory performance.  To alleviate this issue, some empirical techniques are developed, \emph{e.g.}~operation-level dropout~\cite{chen2019progressive}, fair operation-competing loss~\cite{chu2019fair}.  But no attention has been paid to developing theoretical understandings for why   skip connections dominate other types of operations in DARTS.  The theoretical answer to this question is important  not only for better understanding DARTS, but also for inspiring new insights for DARTS algorithm improvement.

\noindent{\textbf{Contributions.}}   In this work,  we address the above fundamental question and contribute to derive some new results, insights and alternatives for DARTS. Particularly, we provide rigorous theoretical  analysis for the dominated skip connections in DARTS.  Inspired by our theory, we then propose a new alternative of DARTS which can search  networks without dominated skip connections and achieves state-of-the-art classification performance. Our main contributions  are highlighted below.

\begin{figure}[tb]
	\begin{center}
		\setlength{\tabcolsep}{0.0pt}
		\begin{tabular}{c}
			{\hspace{-2pt}}
			\includegraphics[width=1\linewidth]{fig1/fig1.pdf}\\
		\end{tabular}
	\end{center}
	\vspace{-0.7em}
	\caption{Illustration of selected normal cells by DARTS and PR-DARTS. By comparison, the group-structured  sparse gates in PR-DARTS (b) well alleviate  unfair operation competition and overcome  the dominated-skip-connection  issue in DARTS (a); path-depth-wise regularization in PR-DARTS (c)  helps rectify  cell-selection-bias to shallow cells; PR-DARTS (d) combines these two complementary components and  well alleviates the above two issues,   testified by the results in (e).
	}
	\label{illustrationcomponents}
	\vspace{-1.0em}
\end{figure}

Our first contribution is proving that DARTS prefers  to skip connection more than other types of operations, \emph{e.g.}~convolution and zero operation, in the search phase, and tends to search favor skip-connection-dominated networks as shown in Fig.~\ref{illustrationcomponents} (a). Formally,  in the search phase,    DARTS  first fixes architecture parameter $\bm{\beta}$ which determines the operation weights in the graph to optimize the  network parameter $\bm{W}$ by minimizing  training loss $F_{\mbox{\tiny{train}}}(\bm{W}\!, \betaii{}{})$ via gradient descent, and then  uses the validation loss $F_{\mbox{\tiny{val}}}(\bm{W}\!, \betaii{}{})$ to  optimize $\bm{\beta}$ via gradient descent. We prove that when  optimizing $F_{\mbox{\tiny{train}}}(\bm{W}\!, \betaii{}{})$,   the convergence rate at each iteration depends on the weights of skip connections much heavier than other types of operations, \emph{e.g.}~convolution,   meaning that the more skip connections the faster convergence.  Since training and validation data come from the same distribution which means $\mathbb{E}[F_{\mbox{\tiny{train}}}(\bm{W}\!, \betaii{}{})]\!=\!\mathbb{E}[F_{\mbox{\tiny{val}}}(\bm{W}\!, \betaii{}{})]$,  more skip connections can also faster decay $F_{\mbox{\tiny{val}}}(\bm{W}\!, \betaii{}{})$ in expectation. So when updating architecture parameter $\bm{\beta}$, DARTS will tune the weights of skip connections larger to faster decay  validation loss, and meanwhile, will  tune the weights of other  operations smaller since all types of operations on one edge share a softmax distribution. Accordingly, skip connections gradually dominate the  network graph.  To our best knowledge, this is the first theoretical result that explicitly shows heavier dependence of the convergence rate of  NAS  algorithm on   skip connections, explaining the dominated skip connections in DARTS due to their   optimization advantages.

Inspired by our theory, we further develop the path-regularized DARTS (PR-DARTS) as a novel alternative to alleviate unfair  competition between skip connection and other types of operations  in DARTS.   To this end, we define a
group-structured sparse binary gate implemented by   Bernoulli distribution for  each operation. These gates independently determine whether   their corresponding operations are used in the graph. Then we divide all operations in the graph into   skip connection group and non-skip connection group, and independently regularize the gates in these two groups to be sparse via a hard threshold function.   This group-structured sparsity  penalizes the  skip connection group heavier than another group to rectify the  competitive advantage of skip connections over other operations as shown in Fig.~\ref{illustrationcomponents} (b), and globally and  gradually  prunes  unnecessary connections in the search phase to reduce  the  pruning information loss after searching.
More importantly, we introduce a path-depth-wise regularization which encourages large activation probability of gates along  the  long paths in the network graph  and thus  incites more search  exploration to deep graphs illustrated by Fig.~\ref{illustrationcomponents} (c). As our theory shows that gradient descent can faster optimize shallow and wide networks  than deep and thin ones, this path-depth-wise regularization can rectify the competitive advantage of shallow network over deep one.
So PR-DARTS can  search  performance-oriented networks instead of fast-convergence-oriented networks and achieves better performance testified by Fig.~\ref{illustrationcomponents} (e).

\section{Related Work}

DARTS~\cite{liu2018darts} has gained much attention recently thanks to its high search  efficiency~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts,dong2019searching,wu2019fbnet,cai2018proxylessnas,xie2018snas,xu2019pc,yang2020cars,guo2020breaking}.  It relaxes a  discrete search space to a continuous one via continuously weighting the operations, and then employs  gradient descent algorithm to select promising candidates. In this way, it significantly improves the search efficiency over RL and EA based NAS approaches~\cite{zoph2016neural,zoph2018learning,pham2018efficient,real2019regularized}.
But the selected networks by DARTS have dominated skip connections which lead  to unsatisfactory performance~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts}.  To solve this issue, Chen~\emph{et al.}~\cite{chen2019progressive}  introduced operation-level dropout~\cite{srivastava2014dropout}  to regularize  skip connection.  Chu~\emph{et al.}~\cite{chu2019fair} used independent sigmoid function for weighting each operation to avoid  operation  competition, and  designed a new loss to independently push the operation weights to zero or one.  In contrast, our PR-DARTS uses  binary gate for each operation and then imposes  group-structured and path-depth-wise regularizations to alleviate  the fast-convergence-oriented search issue  in DARTS.

The intrinsic theoretical reasons for the dominated skip connection in DARTS are rarely investigated though heavily desired.   Zela~\emph{et al.}~\cite{arber2019understanding}  empirically analyzed the poor generalization performance of the selected architectures by DARTS from the argument of sharp and flat minima.
Shu~\emph{et al.}~\cite{shu2019understanding} studied general NAS and showed that NAS prefers to shallow and wide networks since these networks have more smooth landscape empirically and smaller gradient variance which both boost training speed. But they did not reveal any relation between skip connections and convergence behaviors. Differently, we explicitly show the role of weights of different operations in determining the convergence rate in network optimization, revealing the intrinsic reasons for the dominated skip connections in DARTS.

\section{Theoretical Analysis for DARTS}\label{analysispart}

In this section, we first recall the formulation of DARTS, and then theoretically analyze the intrinsic reasons for the  dominated skip connections in DARTS by analyzing its convergence behaviors.

\subsection{Formulation of DARTS}

DARTS~\cite{liu2018darts} searches cells which are used to stack  the full network architecture. A cell is organized as a directed acyclic graph with $h$ nodes  $\{\Xnii{l}{}\}_{l=0}^{h-1}$.  Typically, the graph contains two input nodes $\Xnii{0}{}$ and $\Xnii{1}{}$ respectively defined as the outputs of two previous cells,  and has one output node $\Xnii{h-\!1}{}$ giving by concatenating  all intermediate  nodes $\Xnii{l}{}$.   Each intermediate  node $\Xnii{l}{}$   connects with all previous nodes $\Xnii{s}{}\ (0\!\leq\!s\!<\!l)$ via a continuous operation-weighting     strategy, namely
\begin{equation}\label{equationoperation}
{\Xnii{l}{} = \sum\nolimits_{0\leq s <l} \sum\nolimits_{t=1}^{r}   \alphanii{l}{s,t} O_{t}\big(\Xnii{s}{} \big) \quad \text{with}\quad  \alphanii{l}{s,t}= \exp(\betanii{l}{s,t})/\sum\nolimits_{t=1}^{r} \exp(\betanii{l}{s,t})},
\end{equation}
where the operation $O_{t} $ comes  from the operation set $\mathcal{O}=\{O_{t}\}_{t=1}^{r}$, including zero operation, skip connection, convolution, etc. In this way, the architecture search problem becomes efficiently learning continuous architecture parameter  $\betaii{}{}=\{\betanii{l}{s,t}\}_{l,s,t}$ via optimizing the following bi-level model
\begin{equation}\label{dartsmodel}
\min\nolimits_{\bm{\beta}}\ F_{\mbox{\tiny{val}}}(\bm{W}^*(\betaii{}{}), \betaii{}{}),\qquad \mbox{s.t.}\ \bm{W}^*(\betaii{}{})=\argmin\nolimits_{\bm{W}}\ F_{\mbox{\tiny{train}}}(\bm{W}, \betaii{}{}),
\end{equation}
where $F_{\mbox{\tiny{train}}}$ and  $F_{\mbox{\tiny{val}}}$ respectively denote the loss on the training and validation datasets, $\bm{W}$ is the  network parameters in the graph, \emph{e.g.}~convolution parameters.   Then DARTS optimizes the architecture parameter $\bm{\beta}$ and the network parameter $\bm{W}$ by alternating gradient descent. After learning $\bm{\beta}$, DARTS prunes the dense graph according to the  weight  $\alphanii{l}{s,t}$ in Eqn.~\eqref{equationoperation} to obtain compact cells.

Despite  its much higher search efficiency over RL and EA based  methods,  DARTS typically selects a cell with dominated skip connections, leading to unsatisfactory performance~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts}.  But  there is no  rigorously theoretical analysis  that explicitly justifies  why DARTS tends to favor skip connections. The following section  attempts to solve this issue by analyzing the convergence behaviors of DARTS.

\subsection{Analysis Results for DARTS}\label{DARTSanalysis}

For analysis, we detail the cell structures in  DARTS. Let  input  be $\bm{X}\in \Rs{\bar{m}\times \bar{p}}$ where $\bar{m}$ and $\bar{p}$ are respectively  the channel number and dimension of input. Typically,  one  needs to resize the input  to a target size {$m\times p$} via a convolution layer with parameter   $\Wmii{(0)}{}\in\Rs{m\times k_c \bar{m}}$ (kernel size {$k_c\times k_c$})
\begin{equation}\label{convolutiondefinition}
\Xnii{0}{} = \convo{\Wnii{0}{}, \bm{X}} \in\Rs{m\times p}\quad \text{with}\quad \convo{\bm{W}; \bm{X}}= \tau \sigmai{\bm{W} \Phi(\bm{X})},
\end{equation}
and  then feed it into the subsequent layers. The convolution operation $\textsf{conv}$  performs convolution and then  nonlinear mapping via activation function {$\sigma$}.  The scaling factor {$\tau$} equals to $\frac{1}{\sqrt{\bar{m}}}$ when channel number in $\textsf{conv}$  is {$\bar{m}$}. It  is introduced to simplify the notations in our analysis and does not affect convergence behaviors of DARTS.   For notation simplicity,  we assume stride {$s_c$}~$\!=\!1$ and padding zero {$p_c$}~$\!=\!\frac{k_c-1}{2}$ to  make  the same sizes of output and input. Given a matrix $ \bm{Z}\!\in\! \Rs{m\times p}$,   $\Phi(\bm{Z})$  is defined as
\begin{equation*}
\Phi(\bm{Z}) \!=\!\!\! \begin{bmatrix} \bm{Z}_{1,-p_c+1: p_c+1}^\top  &\!\!\!\! \bm{Z}_{1,-p_c+2:p_c+2}^\top  &\!\!\!\! \cdots &\!\!\!\!\bm{Z}_{1, p-p_c: p+p_c}^\top  \\
\bm{Z}_{2,-p_c+1: p_c+1}^\top   &\!\!\!\!\bm{Z}_{2,-p_c+2:p_c+2}^\top  &\!\!\!\! \cdots &\!\!\!\! \bm{Z}_{2, p-p_c: p+p_c}^\top  \\
\vdots & \vdots & \ddots &\vdots\\
\bm{Z}_{m,-p_c+1: p_c+1}^\top   &\!\!\!\! \bm{Z}_{m,-p_c+2:p_c+2}^\top  &\!\!\!\!  \cdots &\!\!\!\! \bm{Z}_{m, p-p_c: p+p_c}^\top  \\
\end{bmatrix} \!\!\!\in\! \Rs{k_c m\times p},
\end{equation*}
where $\bm{Z}_{i,t} =0\  (t \leq 0$ or $ t>p)$.
Then the conventional convolution can be computed as $\bm{W} \Phi(\bm{X})$ where each row in $\bm{W}$ denotes a conventional  kernel.   Note, for other convolutions, e.g.  depth-wise separable convolution, our analysis framework still holds and can derive very similar  results.  Now we are ready to define the subsequent layers in the cell:
\begin{equation}\label{connections}
{\Xnii{l}{}  \!=\! \sum\nolimits_{s=0}^{l-1}    \big(\alphanii{l}{s,1}\zeroo{\bm{X}} \!+\!\alphanii{l}{s,2} \skipo{\bm{X}} \!+\! \alphanii{l}{s,3} \convo{\Wnii{l}{s};\Xnii{s}{}}\big)  \! \in\!\Rs{m\times p}\ (l\!=\!1,\cdots\!,h-1), }
\end{equation}
where zero operation $\zeroo{\bm{X}}=\bm{0}$ and skip connection   $ \skipo{\bm{X}}  =\bm{X}$,  $\alphaii{(l)}{s,t}$ is given in~\eqref{equationoperation}.  In this work, we consider three representative operations, \emph{i.e.}~zero, skip connection and convolution, and ignore pooling operation since  it reveals the same behaviors as convolution, namely both being dominated by skip connections~\cite{chen2019progressive,chu2019fair,arber2019understanding}.
Next, we feed concatenation of all intermediate nodes into a linear layer to obtain the prediction {$\ui{i}$} of the {$i$}-th sample $\Xmi{i}$ and then obtain a mean squared loss:
\begin{equation}\label{loss}
{F(\bm{W}, \bm{\beta}) = \frac{1}{2n}\sum\nolimits_{i=1}^{n} (\ui{i}-\ymi{i})^2 \quad \text{with}\quad \ui{i}=  \sum\nolimits_{s=0}^{h-1}  \langle \Wmi{s}, \Xnii{s}{i} \rangle \in\Rs{}, }
\end{equation}
where $\Xnii{s}{i}$ denotes the {$s$}-th feature node for sample $\Xmi{i}$, $ \{\Wmi{s}\}_{s=0}^{h-1}$ denote  the parameters for the linear layer.    $F(\bm{W}, \bm{\beta})$ becomes $F_{\mbox{\tiny{train}}}(\bm{W}, \bm{\beta})$ ($F_{\mbox{\tiny{val}}}(\bm{W}, \bm{\beta})$) when samples come  from training dataset (validation dataset).
Subsequently, we   analyze the effects of various types of  operations to the convergence behaviors of  $F_{\mbox{\tiny{train}}}(\bm{W}\!, \bm{\beta})$ when optimize the network parameter $\bm{W}$ via gradient descent:
\begin{equation}\label{updation}
\Wmii{(l)}{s}\!(k\!+\!1) \!=\! \Wmii{(l)}{s}\!(k)-\eta \nabla_{\!\Wmii{(l)}{s}\!(k)}\! F_{\mbox{\tiny{train}}}(\bm{W}\!,\! \bm{\beta})\ (\forall l,\! s),\ \ \Wmi{s}(k\!+\!1) \!=\!\Wmi{s}(k) -\eta \nabla_{\!\Wmi{s}(k)} F_{\mbox{\tiny{train}}}(\bm{W}\!,\! \bm{\beta})\ (\forall s),
\end{equation}
where {$\eta$} is the learning rate. We use gradient descent instead of stochastic gradient descent, since gradient descent is expectation version of stochastic one and can reveal similar convergence behaviors.  For  analysis, we first introduce mild assumptions widely used in stochastic optimization~\cite{Rakhlin12,zhou2019Riemannian,zhou2018HSGDHT,zhou2020hybird} and network  analysis~\cite{du2018gradient,du2018gradient22,allen2018convergence,tian2017analytical,zhou2018analysiscnns,zhou2018analysisdnn,zhou2019metalearning,zhou2020sgd}.
\begin{assum} \label{activationassumption}
	Assume the activation function {$\sigma$}  is {$\mu$}-Lipschitz  and {$\rho$}-smooth.  That is, for {$\forall x_1, x_2$}, {$\sigma$}  satisfies {$|\sigmai{x_1} -\sigmai{x_2}|\leq \mu |x_1-x_2|$} and   {$|\sigma'(x_1) -\sigma'(x_2)|\leq \rho |x_1-x_2|$}. Moreover, we assume that{$\sigma$}$(0)$ can be upper bounded, and {$\sigma$} is analytic and is not a polynomial function. \vspace{-0.3em}
\end{assum}
\begin{assum}\label{initilizationassumption}
	Assume the initialization of the convolution  parameters ($\Wmii{(l)}{s}$) and the linear mapping parameters ($\Wmi{s}$)  are drawn from Gaussian distribution  $\mathcal{N}(\bm{0}, \bm{I})$.\vspace{-0.1em}
\end{assum}
\begin{assum}\label{sampleassumption}
	Suppose the samples $\{\Xmi{i}\}_{i=1}^n$ are  normalized such that $\|\Xmi{i}\|_F= 1$. Moreover, they are not parallel, namely $\vect{\Xmi{i}}\notin \text{span}(\vect{\Xmi{j}})$ for all $i\neq j$, where $\vect{\Xmi{i}}$  vectorizes  $\Xmi{i}$.\vspace{-0.5em}
\end{assum}
Assumption~\ref{activationassumption} is mild, since most differential activation functions, \emph{e.g.}~softplus and sigmoid, satisfy it. The Gaussian assumption on initial  parameters  in Assumption~\ref{initilizationassumption} is used in practice. We assume  Gaussian variance to be one for notation simplicity in analysis, but our technique is applicable to any constant variance.  The normalization and non-parallel conditions in Assumption~\ref{sampleassumption}  are satisfied in practice, as normalization is a data preprocess and samples in a  dataset are often not restrictively parallel.  Based on assumptions, we summarize our  result in Theorem~\ref{mainconvergence3} with proof in Appendix~\ref{proofofmainconvergence3}.

\begin{thm}\label{mainconvergence3}
	Suppose Assumptions~\ref{activationassumption}, \ref{initilizationassumption} and~\ref{sampleassumption} hold.  Let {$c$}~$\!=\!\left(1\!+\!\alphaii{}{2} \!+\! 2\alphaii{}{3}  \mu \sqrt{k_c} c_{w0} \right)^{h}$, $\alphaii{}{2}\!=\! \max_{s,l}\alphanii{l}{s,2}$ and $\alphaii{}{3}\!=\!\max_{s,l} \alphanii{l}{s,3}$.	If   $m\!\geq\!  \frac{c_m \mu^2  }{\lambda^2}   \left[ \rho p^2 n^2\log(n/\delta) \!+\! c^2  k_c^2  c_{w0}^2/n   \right]$ and $\eta \!\leq\!  \frac{c_\eta \lambda}{\sqrt{m} \mu^4   h^{3}  k_c^2 c^4}$,
	where {$c_{w0}$}, {$ c_m$},  {$c_\eta$} are  constants, $\lambda$ is given below. Then when fixing  architecture parameterize $\bm{\alpha} $ in~\eqref{equationoperation}  and  optimizing  network parameter $\bm{W}$ via gradient descent~\eqref{updation}, with probability at least $1-\delta$ we have
	\begin{equation*}
	F_{\mbox{\tiny{train}}}(\bm{W}(k+1), \bm{\beta})   \leq \left( 1 - \eta  \lambda/4\right)F_{\mbox{\tiny{train}}}(\bm{W}(k), \bm{\beta}) \quad (\forall k\geq 1),
	\end{equation*}
	where $\lambda
	= \frac{3c_{\sigma}}{4} \lambda_{\min}(\bm{K})\sum_{s=0}^{h-2}(\alphanii{h-1}{s,3} )^2
	\prod_{t=0}^{s-1}  (\alphanii{s}{t,2})^2
	$,  the positive constant {$c_\sigma$} only depends on {$\sigma$} and  input data,   $\lambda_{\min}({\bm{K}})=\min_{i,j} \lambda_{\min}(\bm{K}_{ij}) $ is larger than zero  in which  $\lambda_{\min}(\bm{K}_{ij}) $ is  the smallest eigenvalue of $\bm{K}_{ij} =  \begin{bmatrix}
	\Xmi{i}^{\top} \Xmi{j}, \Xmi{i}^{\top} \Xmi{j};
	\Xmi{j}^{\top} \Xmi{i}, \Xmi{j}^{\top} \Xmi{j}
	\end{bmatrix}$.
\end{thm}

Theorem~\ref{mainconvergence3} shows that for an architecture-fixed over-parameterized network, when using gradient descent  to optimize the network parameter $\bm{W}$, one can expect the convergence of the algorithm which is consistent with prior deep learning optimization work~\cite{du2018gradient,du2018gradient22,allen2018convergence,tian2017analytical}. More importantly, the convergence rate at each iteration depends on the network architectures which is parameterized by $\bm{\alpha}$.

Specifically,  for each  factor $\lambda_s\!=\!(\alphanii{h-1}{s,3} )^2\prod_{t=0}^{s-1}  (\alphanii{s}{t,2})^2$ in the factor $\lambda$, it is induced by the connection path $\Xnii{0}{}\!\rightarrow\!\Xnii{1}{}\!\rightarrow\!\cdots \!\rightarrow\! \Xnii{s}{}\!\rightarrow\!\Xnii{h-1}{}$. By observing  $\lambda_s$, one can find that (1) for the connections before node $\Xnii{s}{}$,  it depends on the weights  $\alphanii{s}{t,2}$ of skip connections  heavier than  convolution and zero operation, and (2) for the direct connection between  $\Xnii{s}{}$ and $\Xnii{h-1}{}$, it relies on convolution  weight $\alphanii{h}{s,3}$ heavier than the weights of other type operations.  For observation (1), it can be intuitively understood: as shown in~\cite{he2016deep,he2016identity,orhan2017skip,balduzzi2017shattered}, skip connection  often provides larger gradient flow than the parallel convolution  and zero connection  and thus greatly benefits  faster convergence of networks, since skip connection maintains primary information flow, while  convolution  only learns the residual information and zero operation does not delivery any information.
So convolution and zero operations have  negligible contribution to information flow and thus their weights do not occur in $\prod_{t=0}^{s-1}  (\alphanii{s}{t,2})^2$ of $\lambda_s$. For observation (2), as the path $\Xnii{0}{}\!\rightarrow\!\Xnii{1}{}\!\rightarrow\!\cdots \!\rightarrow\! \Xnii{s}{}$ is shared for all subsequent layers, it prefers  skip connection more to maintain information flow, while for  the private  connection between  $\Xnii{s}{}$ and $\Xnii{h-1}{}$ which is not shared since $\Xnii{h-1}{}$ is the last node, it  relies on learnable  convolution  more heavily than non-parameterized operations, since learnable operations have parameter to learn and can reduce the loss.  For the theoretical reasons for observations (1) and (2),  the skip connection in the shared  path   can improve the singularity of network  Gram matrix more than other types of operations, where the singularity directly determines the convergence rate, while the learnable convolution  in private path can benefit the Gram matrix singularity  much more. See details in Appendix~\ref{Proofoflinearconvergene}. The weight $\alphanii{l}{s,3}$ of zero operation does not occur in $\lambda$, as it does not delivery any information.

Now we     analyze why the selected cell has dominated skip connections.   The above analysis shows that  the convergence rate when optimizing $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ depends on the weights of skip connections heavier than other weights  in the shared connection path which dominates  the connections of a cell.  So larger weights of skip connections often give faster loss decay of $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$. Consider the samples for training and validation come from the same distribution which means  $\mathbb{E} [F_{\mbox{\tiny{train}}}(\bm{W}\!,\bm{\beta})]\!=\!\mathbb{E}[F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})]$, larger weights of skip connections can also  faster reduce $F_{\mbox{\tiny{val}}}(\bm{W})$ in expectation, which accords with the empirical observations in Fig.~\ref{skipfaster} and the observations in~\cite{arber2019understanding}.   In Fig.~\ref{skipfaster}, we first set all operations in   NAS cell (normal and reduction cells, see details in Sec.~\ref{experiments})  as convolution \begin{wrapfigure}{r}{0.30\linewidth
	\vspace{-1.5em}
	\begin{center}
		\setlength{\tabcolsep}{0.0pt}
		\begin{tabular}{cc}
			\includegraphics[width=\linewidth]{fig1/skip.pdf}  \\
		\end{tabular}
	\end{center}
	\vspace{-1.0em}
	\caption{Effects of skip connections to convergence rate of network.}
	\label{skipfaster}
	\vspace{-2.0em}
\end{wrapfigure}
($3\!\times \!3$), and randomly select $0\%$, $37.5\%$ and $62.5\%$ operations as  skip connections. Next, we stack
8 NAS cells to build a network and train  on CIFAR10 with  same settings. Fig.~\ref{skipfaster} shows  that more skip connections gives faster convergence.
So when optimizing   $\bm{\alpha}$  via optimizing $\bm{\beta}$ in $F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})$,
DARTS will  tune   weights of most skip connections
larger to faster reduce  $F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})$.   As the weights of three operations  on one edge share a softmax distribution in~\eqref{equationoperation}, increasing   one operation weight means reducing  other operation weights.    Thus,   skip connections  gradually dominate over other types of operations for most connections in the cell.    So when pruning  operations according to their weights,  most of skip connections are preserved while most of  other  operations are pruned. This explains the dominated skip connections in the cell selected by DARTS.

\section{Path-Regularized Differential Network Architecture Search}\label{methodpart}
The proposed method consists of two main components, \emph{i.e.}~group-structured  sparse stochastic gate for each operation and path-depth-wise regularization on gates, which are introduced below in turn.

\subsection{Group-structured Sparse Operation Gates}
The analysis in Sec.~\ref{DARTSanalysis} shows that skip connection has superior competing advantages over other types of operations when they share  one softmax distribution.  To resolve this issue, we introduce independent stochastic gate  for each operation between two nodes to avoid the direct competition between skip connection and other operations. Specifically, we define a stochastic binary gate $\gnii{l}{s,t}$ for the $t$-th operation between nodes $\Xnii{s}{}$ and $\Xnii{l}{}$, where $\gnii{l}{s,t} \!\sim\! \text{Bernoulli}\big( \!\exp(\betanii{l}{s,t})/(1\!+\!\exp(\betanii{l}{s,t})\big)$. Then at each iteration, we sample gate $\gii{(l)}{s,t}$   from its   Bernoulli distribution and compute each node as
\begin{equation}\label{conenctionwaypcdarts}
{\Xnii{l}{} = \sum\nolimits_{1\leq i <l} \sum\nolimits_{t=1}^{r} \gnii{l}{s,t} O_{t}\big(\Xnii{i}{} \big)}.
\end{equation}
Since the discrete sampling of $\gnii{l}{s,t}$ is not differentiable, we use Gumbel technique~\cite{dyson1962statistical,maddison2014sampling} to approximate $\gnii{l}{s,t}$ as $\gnbii{l}{s,t}=\Theta\big((\ln \delta - \ln(1-\delta) + \betanii{l}{s,t})/\tau\big)$ where $\Theta$ denotes sigmoid function, $\delta\sim \mbox{Uniform}(0,1)$.  For temperature {$\tau$},   when {$\tau$}$\rightarrow 0$ the approximated distribution $\gnbii{l}{s,t}$ recovers Bernoulli distribution and is  non-smooth, while when {$\tau$}$\rightarrow +\infty$,   the approximated distribution becomes very smooth. In this way, the gradient can be back-propagated through $\gnbii{l}{s,t}$ to the network parameter $\bm{W}$.

If there is no   regularization on the independent gates, then there are two issues. The first one is that the selected cells would have   large weights for most operations. This is because (1) as shown in Theorem~\ref{mainconvergence3}, increasing operation weights can lead to faster convergence rate; (2) increasing weights of any operations can strictly reduce or maintain the  loss which is formally stated in Theorem~\ref{lossproperty}. Let   $t_{\mbox{\tiny{skip}}}$ and $t_{\mbox{\tiny{conv}}}$  respectively be     the indexes of skip connection and convolution in the operation set $\mathcal{O}$.

\begin{thm}\label{lossproperty}
	Assume the weights in DARTS model~\eqref{dartsmodel} is replaced with the independent gates $\gnii{l}{s,t}$. \\
	(1) Increasing the value of $\gnii{l}{s,t}$ of the operations, including zero operation, skip connection, pooling, and convolution with any kernel size,  can reduce or maintain the loss $F_{\mbox{\tiny{val}}}(\bm{W}^*(\bm{\beta}), \bm{\beta})$ in \eqref{dartsmodel}. \\
	(2) Suppose the assumptions in Theorem~\ref{mainconvergence3} hold. With  probability at least $1-\delta$,  increasing   $\gnii{l}{s,t_{\mbox{\tiny{skip}}}}\ (0\!\leq \!$~{$s$}~$\!<\!l\!<h-1)$  of skip connection or   $\gnii{h-1}{s,t_{\mbox{\tiny{conv}}}}\ (0\!\leq \!$~{$s$}~$\!<\!h-1)$ of convolution with increment {$\epsilon$} can reduce the  loss $F_{\mbox{\tiny{val}}}(\bm{W}^*(\bm{\beta}), \bm{\beta})$ in \eqref{dartsmodel} to $F_{\mbox{\tiny{val}}}(\bm{W}^*(\bm{\beta}), \bm{\beta})- C${$\epsilon$} in expectation, where $C$ is a positive constant.\vspace{-0.5em}
\end{thm}

See its  proof in Appendix~\ref{Proofoflossproperty}.
Theorem~\ref{lossproperty} shows that DARTS with independent  gates would tune the weights of most operations large to obtain faster convergence and smaller loss, leading to dense cells and thus  performance degradation when pruning these large weights.  The second issue is that independent gates cannot encourage  benign competition and cooperation among operations, as Theorem~\ref{lossproperty} shows most operations tend to increase their weights. Considering the performance degradation caused by  pruning  dense cells,  benign competition and cooperation among operations  are necessary for gradually pruning unnecessary   operations to obtain relatively   sparse selected cells.

To resolve these two issues,  we impose group-structured sparsity regularization on the   stochastic gates. Following~\cite{louizos2017learning} we stretch $\gnbii{l}{s,t}$ from the range $[0,1]$ to $[${$a,b$}$]$ via rescaling $\gntii{l}{s,t} \!=\!$~{$a$}$+(${$b\!-a$}$)\gnbii{l}{s,t}$,   where {$a$}~$\!<\!0$ and {$b$}~$\!>\!1$ are two constants. Then we feed   $\gntii{l}{s,t}$ into a hard threshold gate to obtain  the gate   $\gnii{l}{s,t}\!=\! \min(1,\max(0, \gntii{l}{s,t}))$.  In this way, the gate   $\gnii{l}{s,t}$ enjoys good properties, \emph{e.g.}~exact zero values and computable activation probability ($\mathbb{P}(\gnii{l}{s,t}\!\neq\! 0$), which are formally stated in Theorem~\ref{gateproperty}.
\begin{thm}\label{gateproperty}
	For each stochastic gate $\gii{(l)}{s,t}$, it satisfies $\gnii{l}{s,t}=
	0$ when $\gntii{l}{s,t}\in(0,-\frac{a}{b-a}]$; $\gnii{l}{s,t}=
	\gntii{l}{s,t}$ when $\gntii{l}{s,t}\in(-\frac{a}{b-a}, \frac{1- a}{b-a}]$; $\gnii{l}{s,t}=
	1$ when $ \gntii{l}{s,t}\in(\frac{1- a}{b-a},1]$. Moreover, $ \mathbb{P}(\gnii{l}{s,t}\neq 0) =\Theta(\betanii{l}{s,t} - \tau \ln \frac{-a}{b} ).$ \vspace{-0.5em}
\end{thm}
See its   proof in Appendix~\ref{proofofgateproperty}.  Theorem~\ref{gateproperty} shows that the  gate $\gnii{l}{s,t}$ can achieve exact zero, which  can reduce  information loss caused by pruning at the end of search. Next based on the activation probability   $\mathbb{P}(\gii{(l)}{s,t} \!\neq\!0)$ in Theorem~\ref{gateproperty}, we design group-structured sparsity regularizations. We collect all skip connections in the cell as a skip-connection  group  and take the remaining   operations into non-skip-connection group. Then we   compute the average  activation probability of these two groups:
\begin{equation*}
{\mathcal{L}_{\mbox{\tiny{skip}}}(\bm{\beta}) \!=\!\zeta \sum_{l=1}^{h-1}  \sum_{s=0}^{l-1}   \Theta \Big(\betaii{(l)}{s,t_{\mbox{\tiny{skip}}}} \!\!- \!\tau \ln \!\frac{-a}{b} \Big),\    \mathcal{L}_{\mbox{\tiny{non-skip}}}(\bm{\beta}) \!=\! \frac{\zeta}{r-1}\!\sum_{l=1}^{h-1}  \sum_{s=0}^{l-1}  \sum_{1\leq t \leq r, t \neq t_{\mbox{\tiny{skip}}}}\! \!\!\! \!\!\Theta \Big(\betaii{(l)}{s,t}\! -\! \tau \ln \!\frac{-a}{b} \Big)\!,}
\end{equation*}
where $\zeta\!=\!\frac{2}{h(h-1)}$. Then we respectively regularize  $\mathcal{L}_{\mbox{\tiny{skip}}}$ and $\mathcal{L}_{\mbox{\tiny{non-skip}}}$ by two different regularization constants $\lambda_1$ and $\lambda_2$ ($\lambda_1\!>\!\lambda_2$ in experiments).  This group-structured sparsity has three benefits: (1) penalizing skip connections heavier than other types of operations can rectify the competitive advantage of skip connections over other operations and avoids skip-connection-dominated cell;   (2) sparsity regularizer gradually and automatically prunes redundancy and unnecessary connections which reduces the information loss of pruning at the end of search;   (3)  sparsity regularizer defined on the whole cell can encourage global competition and cooperation of all operations in the cell, which differs from DARTS that only introduces local competition among the operations between two nodes.

\begin{wrapfigure}{r}{0.39\linewidth}
	\vspace{-1.8em}
	\begin{center}
		\setlength{\tabcolsep}{0.1pt}
		\begin{tabular}{c}
			\includegraphics[width=\linewidth]{fig1/illustation11.pdf}\vspace{-0.2em}\\
			{\small (a)}\vspace{-0.14em}\\
			\includegraphics[width=\linewidth]{fig1/illustation22.pdf}\vspace{-0.18em}\\
			{\small (b)}\vspace{-0.2em}\\
		\end{tabular}
	\end{center}
	\vspace{-1.1em}
	\caption{Illustration of a deep  cell (a)  and a shallow   cell (b).}
	\label{deepandshallow}
	\vspace{-1.2em}
\end{wrapfigure}
\subsection{Path-depth-wise  Regularizer on Operation Gates}
Except for the above advantages,  independent sparse gates also introduce one issue: they prohibit the method to select deep cells.  Without dominated skip connections in the cell,  other types of operations, \emph{e.g.}~zero operation, become freer and are widely used.  Accordingly, the search algorithm can easily transform a deep cell to a shallow  cell whose intermediate nodes  connect with input nodes via
skip connections and whose intermediate neighboring nodes are not connected via zero operations.
Meanwhile,  gradient descent algorithm prefers shallow cells than deep ones, as shallow cells often have more smooth landscapes and can be faster optimized. So these two factors together lead to a  bias of   search algorithm to shallow cells.
Here we provide an example to prove the faster convergence of shallow cells. Suppose $\Xnii{l}{} (l\!=\!0,\!$ $ \cdots\!,h\!-\!1)$ are in two branches  in Fig.~\ref{deepandshallow} (b):   nodes $\Xnii{0}{} $ to $\Xnii{\frac{h}{2}-1}{}$ are in one branch with input $\bm{X}$ and they are connected via~\eqref{conenctionwaypcdarts}, and  $\Xnii{l}{}\ (l\!=\!\frac{h}{2},\cdots,h\!-\!1)$ are in another branch with input $\bm{X}$ and connection~\eqref{conenctionwaypcdarts}. Next, similar to DARTS we use all intermediate nodes to obtain a  squared loss in~\eqref{loss}.   Then we show  in Theorem~\ref{fasterconvergenceloss}  that   the shallow cell \textsf{B}  in Fig.~\ref{deepandshallow} (b) enjoys much faster convergence than the deep cell \textsf{A} in Fig.~\ref{deepandshallow} (a).  Note for cell \textsf{B}, when its node $\Xnii{h/2}{}$ connects with  node $\Xnii{l}{} (l<h/2-1)$, we have very similar results.

\begin{thm}\label{fasterconvergenceloss}
	Suppose the assumptions in Theorem~\ref{mainconvergence3} hold and for each  $\gnii{l}{s,t}\ (0\!\leq\! s <\! l \!\leq \!h-1)$ in deep cell \textsf{A},  it has the same value in  shallow cell \textsf{B}  if it occurs in \textsf{B}. When  optimizing  $\bm{W}$ in $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ via gradient descent~\eqref{updation},  both  losses of  cells \textsf{A} and \textsf{B} obey $F_{\mbox{\tiny{train}}}(\bm{W}(k\!+\!1), \bm{\beta}) \!  \leq \!\left( 1 \!-\! \eta  \lambda'/4\right)F_{\mbox{\tiny{train}}}(\bm{W}(k), \bm{\beta})$, where $\lambda'$ in \textsf{A} is defined as   $\lambda_{\mbox{\tiny{\textsf{A}}}}
	= \frac{3c_{\sigma}}{4} \lambda_{\min}(\bm{K})\ \sum_{s=0}^{h-2}(\gnii{h-1}{s,3} )^2
	\prod_{t=0}^{s-1}  (\gnii{s}{t,2})^2  $, while  $\lambda'$  in \textsf{B} becomes  $\lambda_{\mbox{\tiny{\textsf{B}}}} $ and obeys $\lambda_{\mbox{\tiny{\textsf{B}}}} \geq \lambda_{\mbox{\tiny{\textsf{A}}}} +
	\frac{3c_{\sigma}}{4} \lambda_{\min}(\bm{K}) \sum_{s=h/2}^{h-1} (\gnii{h-1}{s,3} )^2
	\prod_{t=h/2}^{s-1}   (\gnii{s}{t,2})^2 > \lambda_{\mbox{\tiny{\textsf{A}}}}
	$. \vspace{-0.3em}
\end{thm}

See its  proof in Appendix~\ref{Proofoffasterconvergenceloss}.
Theorem~\ref{fasterconvergenceloss} shows that when using gradient descent  to optimize the inner-level   loss $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ equipped with independent gates,  shallow  cells  can  faster reduce the  loss  $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ than deep cells. As   training and validation data come from the same distribution which means  $\mathbb{E} [F_{\mbox{\tiny{train}}}(\bm{W}\!,\bm{\beta})]\!=\!\mathbb{E}[F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})]$,  shallow  cells  reduce $F_{\mbox{\tiny{val}}}(\bm{W},\bm{\beta})$ faster in expectation which accords with the theoretical and empirical results in~\cite{sankararaman2019impact}.  So it is likely that to avoid deep cells, search algorithm would connect  intermediate nodes with  input nodes and cut the connection between  neighboring  nodes via zero operation, which is indeed illustrated by Fig.~\ref{illustrationcomponents}  (b). But it leads to cell-selection bias in the search phase, as some cells  that   fast decay the loss $F_{\mbox{\tiny{val}}}(\bm{W},\bm{\beta})$ at the current iteration  have   competitive advantage over  other cells that reduce $F_{\mbox{\tiny{val}}}(\bm{W},\bm{\beta})$ slowly currently  but can achieve superior final performance. This prohibits us to search good cells.

\makebox[\textwidth][s]{To resolve this cell-selection bias, we propose a path-depth-wise regularization to   rectify the unfair}

competition between shallow and deep cells. From Theorem~\ref{gateproperty},  the  probability that  $\Xnii{l}{}$ and $\Xnii{l+1}{}$ are connected by parameterized  operations $\mathcal{O}_{\mbox{\tiny{p}}}$,  \emph{e.g.}~various types of convolutions, is $\mathbb{P}_{l,l+1}(\bm{\beta})$ $= \! \sum_{\mathcal{O}_t \in \mathcal{O}_{\mbox{\tiny{p}}}} \!\Theta\big(\betanii{l+1}{l,t}\! -\! \tau \ln \frac{-a}{b} \big)$.  So  the probability that all neighboring nodes $\Xnii{l}{}$ and $\Xnii{l+1}{}$  ($l=0,\cdots,h-1$) are connected via  operations $\mathcal{O}_{\mbox{\tiny{p}}}$, namely, the probability of the path of depth $h$,  is
\begin{equation}\label{pathregularization}
{ \mathcal{L}_{\mbox{\tiny{path}}}(\bm{\beta}) =\prod\nolimits_{l=1}^{h-1}\mathbb{P}_{l,l+1}(\bm{\beta}) =\prod\nolimits_{l=1}^{h-1} \sum\nolimits_{O_t \in \mathcal{O}_{p}} \Theta\big(\betaii{(l+1)}{l,t} - \tau \ln \frac{-a}{b} \big).}
\end{equation}
Here we do not consider  skip connection, zero and pooling operations, as they indeed make  a network shallow. To rectify the   competitive advantage of shallow cells over deep ones, we impose path-depth-wised regularization $- \mathcal{L}_{\mbox{\tiny{path}}}(\bm{\beta})$ on the stochastic gates to encourage more exploration to deep cells   and then decide the depth of cells instead of greedily choosing shallow cell at the beginning of   search.

Now we are ready to define our proposed PR-DARTS model  as follows:
\begin{equation*}\label{PCdartsmodel}
\min_{\bm{\beta}} F_{\mbox{\tiny{val}}}(\bm{W}^*\!(\betaii{}{}), \betaii{}{}) + \lambda_{1} \mathcal{L}_{\mbox{\tiny{skip}}}(\bm{\beta})  +  \lambda_{2} \mathcal{L}_{\mbox{\tiny{non-skip}}}(\bm{\beta})   - \lambda_{3} \mathcal{L}_{\mbox{\tiny{path}}}(\bm{\beta}),\   \mbox{s.t.} \bm{W}^*\!(\betaii{}{})\!=\!\argmin\nolimits_{\bm{W}} F_{\mbox{\tiny{train}}}(\bm{W}, \betaii{}{}),
\end{equation*}
where
$\bm{W}$ denotes network parameters, $\betaii{}{}$ denotes the parameters for the stochastic gates. Similar to  DARTS,  we  alternatively update  parameters $\bm{W}$ and  $\betaii{}{}$ via gradient descent. See optimization details in   Algorithm~\ref{searchalgorithm} of  Appendix~\ref{lamgugetask}.   After searching, following DARTS, we  prune   redundancy connections according to the activation probability in Theorem~\ref{gateproperty} to obtain more compact cells.

\vspace{-0.8em}
\section{Experiments}\label{experiments}
\vspace{-0.4em}
Here   we evaluate  PR-DARTS on  classification task and  compare it with  representative state-of-the-art NAS approaches, including RL based NAS, EA based NAS and differential NAS methods. Code is available at \url{https://panzhous.github.io/}.

\textbf{Datasets.}
CIAFR10~\cite{krizhevsky2009learning} and CIFAR100~\cite{krizhevsky2009learning} contain 50K training and 10K test images which are of size $32\times32$ and   distribute over  10 classes in CIFAR10 and 100 classes in CIFAR100.  ImageNet~\cite{russakovsky2015imagenet} has  1.28M training and 50K test images  which  roughly equally distribute over 1K object categories.

\textbf{Implementations.}
For searching, each cell contains two input nodes (outputs of two previous cells), four intermediate nodes and one output node (concatenation of all intermediate nodes). Then we stack $k$ cells  for search. The $k/3$- and $2k/3$-th cells are reduction cells in which all operations have a stride of two, and the remaining cells are normal cells with operation stride of one.  Reduction cells share the same architecture and normal cells also have the same architecture.  The operation set $\mathcal{O}$  has eight choices: zero operation, skip connection, $3\!\times\! 3$ and $5\!\times\! 5$ separable convolutions, $3\!\times\! 3$ and $5\!\times \!5$ dilated separable convolutions, $3\!\times \!3$ average pooling and $3\!\times \!3$ max pooling.  For fairness, all above settings follow the convention~\cite{zoph2016neural,zoph2018learning,real2019regularized,liu2018darts}.
For each cell,  we use the input node which is the output of the previous cell to construct the path-depth-wise regularization in \eqref{pathregularization}  as illustrated by Fig.~\ref{illustrationcomponents} (c).

\begin{savenotes}
	\begin{table*}[tp]
		\begin{threeparttable}[b]
			\caption{Classification errors ($\%$) on CIFAR10 (C10) and CIFAR100 (C100).\vspace{-0.5em}}
			\setlength{\tabcolsep}{5.9pt}
			\renewcommand{\arraystretch}{0.7}
			\label{CIFARcomparsion} \begin{center}
				{ \fontsize{8.1}{3}\selectfont{
						\begin{tabularx}{\textwidth}{c|cc ccc cc}\toprule
							\multirow{2}{*}{\textbf{Architecture}} &\multicolumn{2}{c}{ \textbf{Test Error ($\%$)}} & \textbf{Params} &  \textbf{Search Cost} & \textbf{Search space} & \textbf{Search}  \\
							& \textbf{C10} & \textbf{C100} &  \textbf{(M)}	 & \textbf{(GPU-days)} & \textbf{$\#$Ops$/$zero} & \textbf{method}\\
							\midrule
							DenseNet-BC~\cite{huang2017densely} &3.46 & 17.18& 25.6 & --- &---& manual  \\
							\midrule
							NASNet-A + cutout~\cite{zoph2018learning} & 2.65 & ---& 3.3  & 1800& 13 & RL\\
							AmoebaNet-B + cutout~\cite{real2019regularized}  & 2.55 & ---& 2.8  & 3150& 19 & evolution\\
							PNAS~\cite{liu2018progressive} & 3.41 & ---& 3.2 & 225& 8 & SMBO\\
							ENAS + cutout~\cite{pham2018efficient}& 2.89 & ---& 4.6  & 0.5 & 6 & RL\\
							\midrule
							DARTS (first-order) + cutout~\cite{liu2018darts} &3.00 & 17.76 & 3.3  & 1.5 & 7 & gradient-based\\
							DARTS (second-order) + cutout~\cite{liu2018darts} &2.76 & 17.54 & 3.3   & 4.0& 7& gradient-based\\
							SNAS (moderate) + cutout~\cite{xie2018snas} &2.85& --- & 2.8 & 1.5 &7& gradient-based\\
							P-DARTS +  cutout~\cite{chen2019progressive} &2.50& 16.55 & 3.4 & 0.3&7 & gradient-based\\
							BayesNAS +  cutout~\cite{zhou2019bayesnas} &2.81& --- & 3.4  & 0.18 &7& gradient-based\\
							PC-DARTS +  cutout~\cite{xu2019pc} &2.81& --- & 3.6 & 0.13 &7& gradient-based\\
							GDAS + cutout~\cite{dong2019searching} &2.93& --- & 3.4 & 0.21 &7& gradient-based\\
							Fair DARTS + cutout~\cite{chu2019fair} &2.54& --- & 2.8  & 0.4 &7& gradient-based\\
							\midrule
							PR-DARTS + cutout &  2.32   &  16.45  & 3.4   & 0.17 & 7 & gradient-based  \\
							\bottomrule
						\end{tabularx}
				}}
			\end{center}
			\vspace{-0.2em}
		\end{threeparttable}
	\end{table*}
	\vspace{-0.8em}
\end{savenotes}

\vspace{-0.2em}
\subsection{Results on CIFAR}\label{CIFAR}
\vspace{-0.3em}
In the search phase, following~\cite{liu2018darts} we stack 8 cells with channel number 16. We divide  50K training samples in CIFAR10 into two equal-sized training and validation datasets.   In PR-DARTS, we set   $\lambda_1\!=\!0.01$, $\lambda_2\!=\!0.005$, and $\lambda_3\!=\!0.005$ for regularization.  Then we train the network 200 epochs with mini-batch size 128. For acceleration, per iteration, we follow~\cite{dong2019searching} and randomly select only two operations on each edge to update.  We respectively use   SGD and ADAM~\cite{kingma2014adam} to optimize parameters $\bm{W}$ and $\bm{\beta}$ with detailed settings in Appendix~\ref{lamgugetask}.
We set temperature  {$\tau$}~$\!=\!10$ and  linearly reduce it to 0.1, {$a$}~$\!=-0.1$ and {$b$}~$\!=\!1.1$. For pruning on each node,  we compare the gate activation probabilities of all non-zero  operations collected from all  previous nodes and retain top two operations~\cite{liu2018darts} .

For evaluation on CIFAR10 and CIFAR100, we set channel number 36 and then stack  18 normal cells and 2 reduction cells (the 7- and 14-th cells) to build a large network. We train the network 600 epochs with a mini-batch size of 128 from scratch.  See detailed settings of  SGD   in Appendix~\ref{lamgugetask}.  We also use drop-path with probability 0.2 and   cutout~\cite{devries2017improved} with length 16, for regularization.

Table~\ref{CIFARcomparsion} summarizes the classification results on CIFAR10 and CIFAR100.  In merely 0.17 GPU-days on Tesla V100, PR-DARTS respectively achieves $2.31\%$ and $16.45\%$ classification errors on CIAR10 and CIFAR100, with both search time and accuracy significantly surpassing the DARTS baseline. By comparison, PR-DARTS  also consistently outperforms other NAS approaches, including differential NAS (\emph{e.g.}~P-DARTS, PC-DARTS),  RL based NAS (\emph{e.g.}~NASNet), as well as EA based NAS (\emph{e.g.} Amobdanet).
These results demonstrate the superiority and transferability of the selected cells by  PR-DARTS. As shown in Fig.~\ref{illustrationcomponents},  this advantage comes from the group-structured binary gates and path-depth-wise regularization in PR-DARTS which can well alleviate unfair operation competition and cell-selection bias to shallow cells which are not well considered in the compared   NAS methods.
Fair DARTS  imposes independent sigmoid distribution and zero-one loss for each operation,  which actually does not encourage the important global operation competition and cooperation.
PR-DARTS runs faster over DARTS, because (1) the sparsity regularization prunes unnecessary connections as illustrated in Fig.~\ref{cells} in Appendix~\ref{lamgugetask}, and thus reduces the costs; and (2) following~\cite{dong2019searching} we randomly select only two operations instead of eight operations between two nodes to update per iteration, also helping reducing cost.
Note, Proxyless NAS~\cite{cai2018proxylessnas} reports an error rate of 2.08$\%$ on CIAFR10, but it performs architecture search on the tree-structured  PyramidNet~\cite{cai2018path} which is much complex protocol than the DARTS search space in this work, and requires much longer time (4 GPU-days) for search.

For \textit{ablation study}, Fig.~\ref{illustrationcomponents} shows the individual benefits of the two complementary components, group-structured binary gates and path-depth-wise regularization, in PR-DARTS. See details in  Fig.~\ref{illustrationcomponents}.
Due to space limit, Appendix~\ref{lamgugetask} investigates  the \textit{effects of regularization parameters}  $\lambda_1\!\sim\!\lambda_3$ to the  performance of PR-DARTS.   The results show the stable performance of PR-DARTS on CIAFR10 when tuning these parameters in a relatively large range, and thus testify the robustness of PR-DARTS.

\begin{savenotes}
	\begin{table*}[tp]
		\begin{threeparttable}[b]
			\caption{\!Classification errors ($\%$) on ImageNet {\small(all methods use the cells searched on CIFAR10).}\vspace{-0.5em}}
			\setlength{\tabcolsep}{6.0pt}
			\renewcommand{\arraystretch}{0.7}
			\label{Imagenetresults} \begin{center}
				{ \fontsize{8.1}{3}\selectfont{
						\begin{tabularx}{\textwidth}{c|cc cccc cc}\toprule
							\multirow{2}{*}{\textbf{Architecture}} &\multicolumn{2}{c}{ \textbf{Test Error ($\%$)}} & \textbf{Params} & \textbf{$\bm{\times +}$}	&  \textbf{Search Cost} & \textbf{Search space} & \textbf{Search}  \\
							& \textbf{Top-1} & \textbf{Top-5} & \textbf{(M)} & \textbf{(M)}	 & \textbf{(GPU-days)} & \textbf{$\#$Ops$/$zero}  & \textbf{method}\\
							\midrule
							MobileNet~\cite{howard2017mobilenets} &29.4 & 10.5& 4.2 &569& --- &---& manual  \\
							ShuffleNet2$\times$(v2)~\cite{ma2018shufflenet} &25.1& ---& $\sim$5 &591& --- &---& manual  \\
							\midrule
							NASNet-A~\cite{zoph2018learning} & 26.0 & 8.4& 5.3 & 564 & 1800& 13 & RL\\
							AmoebaNet-C~\cite{real2019regularized}  & 24.3 & 7.6& 6.4 & 570 & 3150& 19 & evolution\\
							PNAS~\cite{liu2018progressive} & 25.8 & 8.1& 5.1 & 588 & 225& 8 & SMBO\\
							MnaNet-92~\cite{tan2019mnasnet} & 25.2 & 8.0& 4.4 & 388 & --- & hierarchical & RL\\
							\midrule
							DARTS (second-order)~\cite{liu2018darts} &26.7 & 8.7 & 4.7 &  574& 4.0& 7& gradient-based\\
							SNAS (mild)~\cite{xie2018snas} &27.3& 9.2 & 4.3 & 522& 1.5 &7& gradient-based\\
							P-DARTS~\cite{chen2019progressive} &24.4& 7.4  & 4.9 &557& 0.3&7 & gradient-based\\
							BayesNAS~\cite{zhou2019bayesnas} &26.5& 8.9 & 3.9 & --- & 0.18 &7& gradient-based\\
							PC-DARTS~\cite{xu2019pc} &25.1 & 7.8 & 5.3 & 586& 0.13 &7& gradient-based\\
							GDAS~\cite{dong2019searching} &26.0& 8.5 & 5.3 & 581& 0.21 &7& gradient-based\\
							Fair DARTS~\cite{chu2019fair} &24.9& 7.5& 4.8  & 541 &  0.4  &7& gradient-based\\
							\midrule
							PR-DARTS  & 24.1 & 7.3 & 4.98 & 543 & 0.17 & 7 & gradient-based  \\
							\bottomrule

						\end{tabularx}
				}}
			\end{center}
			\vspace{-1.0em}
		\end{threeparttable}
	\end{table*}
\end{savenotes}

\vspace{-0.5em}
\subsection{Results on ImageNet}
\vspace{-0.3em}
We further evaluate the transferability of the cells selected on CIFAR10 by testing them on more challenging ImageNet. Following DARTS, we rescale input size to  $224\times 224$. We stack three convolutional layers,12 normal cells and 2 reduction cells (channel number  48) to build a large network, and train it 250 epochs with mini-batch size 128.  See detailed settings of  SGD   in Appendix~\ref{lamgugetask}.

Table~\ref{Imagenetresults} reports the  results on ImageNet. One can observe that PR-DARTS consistently outperforms the compared state-of-the-art approaches. In particular, it respectively improves DARTS by  $2.4\%$  and  $1.4\%$  on top-1  and top 5 accuracies. These results demonstrate the superior transferability of the cells selected by PR-DARTS behind which the potential reasons have been discussed in Sec.~\ref{CIFAR}.

\vspace{-0.7em}
\section{Conclusion}
\vspace{-0.3em}
In this work,  for the first time we theoretically explicitly show the benefits of more skip connections to fast network optimization in  DARTS,  explaining the dominated skip connections in the selected cells by DARTS. Then inspired by our theory, we propose PR-DARTS to improve DARTS by using group-structured binary gates and path-depth-wise regularization to alleviate unfair operation competition and cell-selection bias to  shallow cells. Experimental results validated the  advantages of PR-DARTS.

\newpage

\section*{Broader Impacts}
\label{sec:impact}
This work advances network architecture search (NAS) in both theoretical performance analysis and practical algorithm design. As NAS can automatically design state-of-the-art architectures,   this work alleviates substantial efforts from domain experts for effective architecture design, and could also help develop more intelligent algorithms. But NAS  still needs an expert-designed search space which may have bias and prohibit NAS development.  So automatically designing search space is desirable.

{
\small
\bibliographystyle{unsrt}

\section{Introduction}\label{introduction}
\vspace{-0.4em}
Network architecture search (NAS)~\cite{zoph2016neural} is an effective approach for automating  network architecture design, with many successful applications witnessed to  image recognition~\cite{zoph2018learning,pham2018efficient,real2019regularized,tan2019mnasnet,liu2018darts} and language modeling~\cite{zoph2016neural,liu2018darts}. The methodology of NAS is to automatically search for a directed graph and its  edges  from a huge search space. Unlike expert-designed architectures which  require  substantial efforts from  experts by trial  and error, the automatic principle in NAS greatly alleviates   these design efforts  and possible design bias brought by  experts which could  prohibit achieving better performance.  Thanks to these advantages, NAS has been widely devised via reinforcement learning (RL) and  evolutionary algorithm (EA),   and    achieved  promising results in many applications, \emph{e.g.}~classification~\cite{zoph2018learning,real2019regularized}.

DARTS~\cite{liu2018darts} is a recently developed  leading approach. Different from RL and EA based methods~\cite{zoph2016neural,zoph2018learning,pham2018efficient,real2019regularized} that discretely optimize  architecture parameters, DARTS converts the  operation selection for each edge in the directed graph into continuously   weighting a fixed set of operations. In this way, it  can optimize the architecture parameters via gradient descent and greatly reduces the high search cost in RL and EA approaches.  However, as observed in  the literatures~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts} and Fig.~\ref{illustrationcomponents} (a), this differential  NAS family, including DARTS and its variants~\cite{dong2019searching,wu2019fbnet}, typically selects many skip connections which dominate over other types of operations in the network graph. Consequently,  the searched networks are observed to have unsatisfactory performance.  To alleviate this issue, some empirical techniques are developed, \emph{e.g.}~operation-level dropout~\cite{chen2019progressive}, fair operation-competing loss~\cite{chu2019fair}.  But no attention has been paid to developing theoretical understandings for why   skip connections dominate other types of operations in DARTS.  The theoretical answer to this question is important  not only for better understanding DARTS, but also for inspiring new insights for DARTS algorithm improvement.

\noindent{\textbf{Contributions.}}   In this work,  we address the above fundamental question and contribute to derive some new results, insights and alternatives for DARTS. Particularly, we provide rigorous theoretical  analysis for the dominated skip connections in DARTS.  Inspired by our theory, we then propose a new alternative of DARTS which can search  networks without dominated skip connections and achieves state-of-the-art classification performance. Our main contributions  are highlighted below.

\begin{figure}[tb]
	\begin{center}
		\setlength{\tabcolsep}{0.0pt}
		\begin{tabular}{c}
			{\hspace{-2pt}}
			\includegraphics[width=1\linewidth]{fig1/fig1.pdf}\\
		\end{tabular}
	\end{center}
	\vspace{-0.7em}
	\caption{Illustration of selected normal cells by DARTS and PR-DARTS. By comparison, the group-structured  sparse gates in PR-DARTS (b) well alleviate  unfair operation competition and overcome  the dominated-skip-connection  issue in DARTS (a); path-depth-wise regularization in PR-DARTS (c)  helps rectify  cell-selection-bias to shallow cells; PR-DARTS (d) combines these two complementary components and  well alleviates the above two issues,   testified by the results in (e).
	}
	\label{illustrationcomponents}
	\vspace{-1.0em}
\end{figure}

Our first contribution is proving that DARTS prefers  to skip connection more than other types of operations, \emph{e.g.}~convolution and zero operation, in the search phase, and tends to search favor skip-connection-dominated networks as shown in Fig.~\ref{illustrationcomponents} (a). Formally,  in the search phase,    DARTS  first fixes architecture parameter $\bm{\beta}$ which determines the operation weights in the graph to optimize the  network parameter $\bm{W}$ by minimizing  training loss $F_{\mbox{\tiny{train}}}(\bm{W}\!, \betaii{}{})$ via gradient descent, and then  uses the validation loss $F_{\mbox{\tiny{val}}}(\bm{W}\!, \betaii{}{})$ to  optimize $\bm{\beta}$ via gradient descent. We prove that when  optimizing $F_{\mbox{\tiny{train}}}(\bm{W}\!, \betaii{}{})$,   the convergence rate at each iteration depends on the weights of skip connections much heavier than other types of operations, \emph{e.g.}~convolution,   meaning that the more skip connections the faster convergence.  Since training and validation data come from the same distribution which means $\mathbb{E}[F_{\mbox{\tiny{train}}}(\bm{W}\!, \betaii{}{})]\!=\!\mathbb{E}[F_{\mbox{\tiny{val}}}(\bm{W}\!, \betaii{}{})]$,  more skip connections can also faster decay $F_{\mbox{\tiny{val}}}(\bm{W}\!, \betaii{}{})$ in expectation. So when updating architecture parameter $\bm{\beta}$, DARTS will tune the weights of skip connections larger to faster decay  validation loss, and meanwhile, will  tune the weights of other  operations smaller since all types of operations on one edge share a softmax distribution. Accordingly, skip connections gradually dominate the  network graph.  To our best knowledge, this is the first theoretical result that explicitly shows heavier dependence of the convergence rate of  NAS  algorithm on   skip connections, explaining the dominated skip connections in DARTS due to their   optimization advantages.

Inspired by our theory, we further develop the path-regularized DARTS (PR-DARTS) as a novel alternative to alleviate unfair  competition between skip connection and other types of operations  in DARTS.   To this end, we define a
group-structured sparse binary gate implemented by   Bernoulli distribution for  each operation. These gates independently determine whether   their corresponding operations are used in the graph. Then we divide all operations in the graph into   skip connection group and non-skip connection group, and independently regularize the gates in these two groups to be sparse via a hard threshold function.   This group-structured sparsity  penalizes the  skip connection group heavier than another group to rectify the  competitive advantage of skip connections over other operations as shown in Fig.~\ref{illustrationcomponents} (b), and globally and  gradually  prunes  unnecessary connections in the search phase to reduce  the  pruning information loss after searching.
More importantly, we introduce a path-depth-wise regularization which encourages large activation probability of gates along  the  long paths in the network graph  and thus  incites more search  exploration to deep graphs illustrated by Fig.~\ref{illustrationcomponents} (c). As our theory shows that gradient descent can faster optimize shallow and wide networks  than deep and thin ones, this path-depth-wise regularization can rectify the competitive advantage of shallow network over deep one.
So PR-DARTS can  search  performance-oriented networks instead of fast-convergence-oriented networks and achieves better performance testified by Fig.~\ref{illustrationcomponents} (e).

\section{Related Work}

DARTS~\cite{liu2018darts} has gained much attention recently thanks to its high search  efficiency~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts,dong2019searching,wu2019fbnet,cai2018proxylessnas,xie2018snas,xu2019pc,yang2020cars,guo2020breaking}.  It relaxes a  discrete search space to a continuous one via continuously weighting the operations, and then employs  gradient descent algorithm to select promising candidates. In this way, it significantly improves the search efficiency over RL and EA based NAS approaches~\cite{zoph2016neural,zoph2018learning,pham2018efficient,real2019regularized}.
But the selected networks by DARTS have dominated skip connections which lead  to unsatisfactory performance~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts}.  To solve this issue, Chen~\emph{et al.}~\cite{chen2019progressive}  introduced operation-level dropout~\cite{srivastava2014dropout}  to regularize  skip connection.  Chu~\emph{et al.}~\cite{chu2019fair} used independent sigmoid function for weighting each operation to avoid  operation  competition, and  designed a new loss to independently push the operation weights to zero or one.  In contrast, our PR-DARTS uses  binary gate for each operation and then imposes  group-structured and path-depth-wise regularizations to alleviate  the fast-convergence-oriented search issue  in DARTS.

The intrinsic theoretical reasons for the dominated skip connection in DARTS are rarely investigated though heavily desired.   Zela~\emph{et al.}~\cite{arber2019understanding}  empirically analyzed the poor generalization performance of the selected architectures by DARTS from the argument of sharp and flat minima.
Shu~\emph{et al.}~\cite{shu2019understanding} studied general NAS and showed that NAS prefers to shallow and wide networks since these networks have more smooth landscape empirically and smaller gradient variance which both boost training speed. But they did not reveal any relation between skip connections and convergence behaviors. Differently, we explicitly show the role of weights of different operations in determining the convergence rate in network optimization, revealing the intrinsic reasons for the dominated skip connections in DARTS.

\section{Theoretical Analysis for DARTS}\label{analysispart}

In this section, we first recall the formulation of DARTS, and then theoretically analyze the intrinsic reasons for the  dominated skip connections in DARTS by analyzing its convergence behaviors.

\subsection{Formulation of DARTS}

DARTS~\cite{liu2018darts} searches cells which are used to stack  the full network architecture. A cell is organized as a directed acyclic graph with $h$ nodes  $\{\Xnii{l}{}\}_{l=0}^{h-1}$.  Typically, the graph contains two input nodes $\Xnii{0}{}$ and $\Xnii{1}{}$ respectively defined as the outputs of two previous cells,  and has one output node $\Xnii{h-\!1}{}$ giving by concatenating  all intermediate  nodes $\Xnii{l}{}$.   Each intermediate  node $\Xnii{l}{}$   connects with all previous nodes $\Xnii{s}{}\ (0\!\leq\!s\!<\!l)$ via a continuous operation-weighting     strategy, namely
\begin{equation}\label{equationoperation}
{\Xnii{l}{} = \sum\nolimits_{0\leq s <l} \sum\nolimits_{t=1}^{r}   \alphanii{l}{s,t} O_{t}\big(\Xnii{s}{} \big) \quad \text{with}\quad  \alphanii{l}{s,t}= \exp(\betanii{l}{s,t})/\sum\nolimits_{t=1}^{r} \exp(\betanii{l}{s,t})},
\end{equation}
where the operation $O_{t} $ comes  from the operation set $\mathcal{O}=\{O_{t}\}_{t=1}^{r}$, including zero operation, skip connection, convolution, etc. In this way, the architecture search problem becomes efficiently learning continuous architecture parameter  $\betaii{}{}=\{\betanii{l}{s,t}\}_{l,s,t}$ via optimizing the following bi-level model
\begin{equation}\label{dartsmodel}
\min\nolimits_{\bm{\beta}}\ F_{\mbox{\tiny{val}}}(\bm{W}^*(\betaii{}{}), \betaii{}{}),\qquad \mbox{s.t.}\ \bm{W}^*(\betaii{}{})=\argmin\nolimits_{\bm{W}}\ F_{\mbox{\tiny{train}}}(\bm{W}, \betaii{}{}),
\end{equation}
where $F_{\mbox{\tiny{train}}}$ and  $F_{\mbox{\tiny{val}}}$ respectively denote the loss on the training and validation datasets, $\bm{W}$ is the  network parameters in the graph, \emph{e.g.}~convolution parameters.   Then DARTS optimizes the architecture parameter $\bm{\beta}$ and the network parameter $\bm{W}$ by alternating gradient descent. After learning $\bm{\beta}$, DARTS prunes the dense graph according to the  weight  $\alphanii{l}{s,t}$ in Eqn.~\eqref{equationoperation} to obtain compact cells.

Despite  its much higher search efficiency over RL and EA based  methods,  DARTS typically selects a cell with dominated skip connections, leading to unsatisfactory performance~\cite{chen2019progressive,chu2019fair,arber2019understanding,liang2019darts}.  But  there is no  rigorously theoretical analysis  that explicitly justifies  why DARTS tends to favor skip connections. The following section  attempts to solve this issue by analyzing the convergence behaviors of DARTS.

\subsection{Analysis Results for DARTS}\label{DARTSanalysis}

For analysis, we detail the cell structures in  DARTS. Let  input  be $\bm{X}\in \Rs{\bar{m}\times \bar{p}}$ where $\bar{m}$ and $\bar{p}$ are respectively  the channel number and dimension of input. Typically,  one  needs to resize the input  to a target size {$m\times p$} via a convolution layer with parameter   $\Wmii{(0)}{}\in\Rs{m\times k_c \bar{m}}$ (kernel size {$k_c\times k_c$})
\begin{equation}\label{convolutiondefinition}
\Xnii{0}{} = \convo{\Wnii{0}{}, \bm{X}} \in\Rs{m\times p}\quad \text{with}\quad \convo{\bm{W}; \bm{X}}= \tau \sigmai{\bm{W} \Phi(\bm{X})},
\end{equation}
and  then feed it into the subsequent layers. The convolution operation $\textsf{conv}$  performs convolution and then  nonlinear mapping via activation function {$\sigma$}.  The scaling factor {$\tau$} equals to $\frac{1}{\sqrt{\bar{m}}}$ when channel number in $\textsf{conv}$  is {$\bar{m}$}. It  is introduced to simplify the notations in our analysis and does not affect convergence behaviors of DARTS.   For notation simplicity,  we assume stride {$s_c$}~$\!=\!1$ and padding zero {$p_c$}~$\!=\!\frac{k_c-1}{2}$ to  make  the same sizes of output and input. Given a matrix $ \bm{Z}\!\in\! \Rs{m\times p}$,   $\Phi(\bm{Z})$  is defined as
\begin{equation*}
\Phi(\bm{Z}) \!=\!\!\! \begin{bmatrix} \bm{Z}_{1,-p_c+1: p_c+1}^\top  &\!\!\!\! \bm{Z}_{1,-p_c+2:p_c+2}^\top  &\!\!\!\! \cdots &\!\!\!\!\bm{Z}_{1, p-p_c: p+p_c}^\top  \\
\bm{Z}_{2,-p_c+1: p_c+1}^\top   &\!\!\!\!\bm{Z}_{2,-p_c+2:p_c+2}^\top  &\!\!\!\! \cdots &\!\!\!\! \bm{Z}_{2, p-p_c: p+p_c}^\top  \\
\vdots & \vdots & \ddots &\vdots\\
\bm{Z}_{m,-p_c+1: p_c+1}^\top   &\!\!\!\! \bm{Z}_{m,-p_c+2:p_c+2}^\top  &\!\!\!\!  \cdots &\!\!\!\! \bm{Z}_{m, p-p_c: p+p_c}^\top  \\
\end{bmatrix} \!\!\!\in\! \Rs{k_c m\times p},
\end{equation*}
where $\bm{Z}_{i,t} =0\  (t \leq 0$ or $ t>p)$.
Then the conventional convolution can be computed as $\bm{W} \Phi(\bm{X})$ where each row in $\bm{W}$ denotes a conventional  kernel.   Note, for other convolutions, e.g.  depth-wise separable convolution, our analysis framework still holds and can derive very similar  results.  Now we are ready to define the subsequent layers in the cell:
\begin{equation}\label{connections}
{\Xnii{l}{}  \!=\! \sum\nolimits_{s=0}^{l-1}    \big(\alphanii{l}{s,1}\zeroo{\bm{X}} \!+\!\alphanii{l}{s,2} \skipo{\bm{X}} \!+\! \alphanii{l}{s,3} \convo{\Wnii{l}{s};\Xnii{s}{}}\big)  \! \in\!\Rs{m\times p}\ (l\!=\!1,\cdots\!,h-1), }
\end{equation}
where zero operation $\zeroo{\bm{X}}=\bm{0}$ and skip connection   $ \skipo{\bm{X}}  =\bm{X}$,  $\alphaii{(l)}{s,t}$ is given in~\eqref{equationoperation}.  In this work, we consider three representative operations, \emph{i.e.}~zero, skip connection and convolution, and ignore pooling operation since  it reveals the same behaviors as convolution, namely both being dominated by skip connections~\cite{chen2019progressive,chu2019fair,arber2019understanding}.
Next, we feed concatenation of all intermediate nodes into a linear layer to obtain the prediction {$\ui{i}$} of the {$i$}-th sample $\Xmi{i}$ and then obtain a mean squared loss:
\begin{equation}\label{loss}
{F(\bm{W}, \bm{\beta}) = \frac{1}{2n}\sum\nolimits_{i=1}^{n} (\ui{i}-\ymi{i})^2 \quad \text{with}\quad \ui{i}=  \sum\nolimits_{s=0}^{h-1}  \langle \Wmi{s}, \Xnii{s}{i} \rangle \in\Rs{}, }
\end{equation}
where $\Xnii{s}{i}$ denotes the {$s$}-th feature node for sample $\Xmi{i}$, $ \{\Wmi{s}\}_{s=0}^{h-1}$ denote  the parameters for the linear layer.    $F(\bm{W}, \bm{\beta})$ becomes $F_{\mbox{\tiny{train}}}(\bm{W}, \bm{\beta})$ ($F_{\mbox{\tiny{val}}}(\bm{W}, \bm{\beta})$) when samples come  from training dataset (validation dataset).
Subsequently, we   analyze the effects of various types of  operations to the convergence behaviors of  $F_{\mbox{\tiny{train}}}(\bm{W}\!, \bm{\beta})$ when optimize the network parameter $\bm{W}$ via gradient descent:
\begin{equation}\label{updation}
\Wmii{(l)}{s}\!(k\!+\!1) \!=\! \Wmii{(l)}{s}\!(k)-\eta \nabla_{\!\Wmii{(l)}{s}\!(k)}\! F_{\mbox{\tiny{train}}}(\bm{W}\!,\! \bm{\beta})\ (\forall l,\! s),\ \ \Wmi{s}(k\!+\!1) \!=\!\Wmi{s}(k) -\eta \nabla_{\!\Wmi{s}(k)} F_{\mbox{\tiny{train}}}(\bm{W}\!,\! \bm{\beta})\ (\forall s),
\end{equation}
where {$\eta$} is the learning rate. We use gradient descent instead of stochastic gradient descent, since gradient descent is expectation version of stochastic one and can reveal similar convergence behaviors.  For  analysis, we first introduce mild assumptions widely used in stochastic optimization~\cite{Rakhlin12,zhou2019Riemannian,zhou2018HSGDHT,zhou2020hybird} and network  analysis~\cite{du2018gradient,du2018gradient22,allen2018convergence,tian2017analytical,zhou2018analysiscnns,zhou2018analysisdnn,zhou2019metalearning,zhou2020sgd}.
\begin{assum} \label{activationassumption}
	Assume the activation function {$\sigma$}  is {$\mu$}-Lipschitz  and {$\rho$}-smooth.  That is, for {$\forall x_1, x_2$}, {$\sigma$}  satisfies {$|\sigmai{x_1} -\sigmai{x_2}|\leq \mu |x_1-x_2|$} and   {$|\sigma'(x_1) -\sigma'(x_2)|\leq \rho |x_1-x_2|$}. Moreover, we assume that{$\sigma$}$(0)$ can be upper bounded, and {$\sigma$} is analytic and is not a polynomial function. \vspace{-0.3em}
\end{assum}
\begin{assum}\label{initilizationassumption}
	Assume the initialization of the convolution  parameters ($\Wmii{(l)}{s}$) and the linear mapping parameters ($\Wmi{s}$)  are drawn from Gaussian distribution  $\mathcal{N}(\bm{0}, \bm{I})$.\vspace{-0.1em}
\end{assum}
\begin{assum}\label{sampleassumption}
	Suppose the samples $\{\Xmi{i}\}_{i=1}^n$ are  normalized such that $\|\Xmi{i}\|_F= 1$. Moreover, they are not parallel, namely $\vect{\Xmi{i}}\notin \text{span}(\vect{\Xmi{j}})$ for all $i\neq j$, where $\vect{\Xmi{i}}$  vectorizes  $\Xmi{i}$.\vspace{-0.5em}
\end{assum}
Assumption~\ref{activationassumption} is mild, since most differential activation functions, \emph{e.g.}~softplus and sigmoid, satisfy it. The Gaussian assumption on initial  parameters  in Assumption~\ref{initilizationassumption} is used in practice. We assume  Gaussian variance to be one for notation simplicity in analysis, but our technique is applicable to any constant variance.  The normalization and non-parallel conditions in Assumption~\ref{sampleassumption}  are satisfied in practice, as normalization is a data preprocess and samples in a  dataset are often not restrictively parallel.  Based on assumptions, we summarize our  result in Theorem~\ref{mainconvergence3} with proof in Appendix~\ref{proofofmainconvergence3}.

\begin{thm}\label{mainconvergence3}
	Suppose Assumptions~\ref{activationassumption}, \ref{initilizationassumption} and~\ref{sampleassumption} hold.  Let {$c$}~$\!=\!\left(1\!+\!\alphaii{}{2} \!+\! 2\alphaii{}{3}  \mu \sqrt{k_c} c_{w0} \right)^{h}$, $\alphaii{}{2}\!=\! \max_{s,l}\alphanii{l}{s,2}$ and $\alphaii{}{3}\!=\!\max_{s,l} \alphanii{l}{s,3}$.	If   $m\!\geq\!  \frac{c_m \mu^2  }{\lambda^2}   \left[ \rho p^2 n^2\log(n/\delta) \!+\! c^2  k_c^2  c_{w0}^2/n   \right]$ and $\eta \!\leq\!  \frac{c_\eta \lambda}{\sqrt{m} \mu^4   h^{3}  k_c^2 c^4}$,
	where {$c_{w0}$}, {$ c_m$},  {$c_\eta$} are  constants, $\lambda$ is given below. Then when fixing  architecture parameterize $\bm{\alpha} $ in~\eqref{equationoperation}  and  optimizing  network parameter $\bm{W}$ via gradient descent~\eqref{updation}, with probability at least $1-\delta$ we have
	\begin{equation*}
	F_{\mbox{\tiny{train}}}(\bm{W}(k+1), \bm{\beta})   \leq \left( 1 - \eta  \lambda/4\right)F_{\mbox{\tiny{train}}}(\bm{W}(k), \bm{\beta}) \quad (\forall k\geq 1),
	\end{equation*}
	where $\lambda
	= \frac{3c_{\sigma}}{4} \lambda_{\min}(\bm{K})\sum_{s=0}^{h-2}(\alphanii{h-1}{s,3} )^2
	\prod_{t=0}^{s-1}  (\alphanii{s}{t,2})^2
	$,  the positive constant {$c_\sigma$} only depends on {$\sigma$} and  input data,   $\lambda_{\min}({\bm{K}})=\min_{i,j} \lambda_{\min}(\bm{K}_{ij}) $ is larger than zero  in which  $\lambda_{\min}(\bm{K}_{ij}) $ is  the smallest eigenvalue of $\bm{K}_{ij} =  \begin{bmatrix}
	\Xmi{i}^{\top} \Xmi{j}, \Xmi{i}^{\top} \Xmi{j};
	\Xmi{j}^{\top} \Xmi{i}, \Xmi{j}^{\top} \Xmi{j}
	\end{bmatrix}$.
\end{thm}

Theorem~\ref{mainconvergence3} shows that for an architecture-fixed over-parameterized network, when using gradient descent  to optimize the network parameter $\bm{W}$, one can expect the convergence of the algorithm which is consistent with prior deep learning optimization work~\cite{du2018gradient,du2018gradient22,allen2018convergence,tian2017analytical}. More importantly, the convergence rate at each iteration depends on the network architectures which is parameterized by $\bm{\alpha}$.

Specifically,  for each  factor $\lambda_s\!=\!(\alphanii{h-1}{s,3} )^2\prod_{t=0}^{s-1}  (\alphanii{s}{t,2})^2$ in the factor $\lambda$, it is induced by the connection path $\Xnii{0}{}\!\rightarrow\!\Xnii{1}{}\!\rightarrow\!\cdots \!\rightarrow\! \Xnii{s}{}\!\rightarrow\!\Xnii{h-1}{}$. By observing  $\lambda_s$, one can find that (1) for the connections before node $\Xnii{s}{}$,  it depends on the weights  $\alphanii{s}{t,2}$ of skip connections  heavier than  convolution and zero operation, and (2) for the direct connection between  $\Xnii{s}{}$ and $\Xnii{h-1}{}$, it relies on convolution  weight $\alphanii{h}{s,3}$ heavier than the weights of other type operations.  For observation (1), it can be intuitively understood: as shown in~\cite{he2016deep,he2016identity,orhan2017skip,balduzzi2017shattered}, skip connection  often provides larger gradient flow than the parallel convolution  and zero connection  and thus greatly benefits  faster convergence of networks, since skip connection maintains primary information flow, while  convolution  only learns the residual information and zero operation does not delivery any information.
So convolution and zero operations have  negligible contribution to information flow and thus their weights do not occur in $\prod_{t=0}^{s-1}  (\alphanii{s}{t,2})^2$ of $\lambda_s$. For observation (2), as the path $\Xnii{0}{}\!\rightarrow\!\Xnii{1}{}\!\rightarrow\!\cdots \!\rightarrow\! \Xnii{s}{}$ is shared for all subsequent layers, it prefers  skip connection more to maintain information flow, while for  the private  connection between  $\Xnii{s}{}$ and $\Xnii{h-1}{}$ which is not shared since $\Xnii{h-1}{}$ is the last node, it  relies on learnable  convolution  more heavily than non-parameterized operations, since learnable operations have parameter to learn and can reduce the loss.  For the theoretical reasons for observations (1) and (2),  the skip connection in the shared  path   can improve the singularity of network  Gram matrix more than other types of operations, where the singularity directly determines the convergence rate, while the learnable convolution  in private path can benefit the Gram matrix singularity  much more. See details in Appendix~\ref{Proofoflinearconvergene}. The weight $\alphanii{l}{s,3}$ of zero operation does not occur in $\lambda$, as it does not delivery any information.

Now we     analyze why the selected cell has dominated skip connections.   The above analysis shows that  the convergence rate when optimizing $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ depends on the weights of skip connections heavier than other weights  in the shared connection path which dominates  the connections of a cell.  So larger weights of skip connections often give faster loss decay of $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$. Consider the samples for training and validation come from the same distribution which means  $\mathbb{E} [F_{\mbox{\tiny{train}}}(\bm{W}\!,\bm{\beta})]\!=\!\mathbb{E}[F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})]$, larger weights of skip connections can also  faster reduce $F_{\mbox{\tiny{val}}}(\bm{W})$ in expectation, which accords with the empirical observations in Fig.~\ref{skipfaster} and the observations in~\cite{arber2019understanding}.   In Fig.~\ref{skipfaster}, we first set all operations in   NAS cell (normal and reduction cells, see details in Sec.~\ref{experiments})  as convolution \begin{wrapfigure}{r}{0.30\linewidth
	\vspace{-1.5em}
	\begin{center}
		\setlength{\tabcolsep}{0.0pt}
		\begin{tabular}{cc}
			\includegraphics[width=\linewidth]{fig1/skip.pdf}  \\
		\end{tabular}
	\end{center}
	\vspace{-1.0em}
	\caption{Effects of skip connections to convergence rate of network.}
	\label{skipfaster}
	\vspace{-2.0em}
\end{wrapfigure}
($3\!\times \!3$), and randomly select $0\%$, $37.5\%$ and $62.5\%$ operations as  skip connections. Next, we stack
8 NAS cells to build a network and train  on CIFAR10 with  same settings. Fig.~\ref{skipfaster} shows  that more skip connections gives faster convergence.
So when optimizing   $\bm{\alpha}$  via optimizing $\bm{\beta}$ in $F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})$,
DARTS will  tune   weights of most skip connections
larger to faster reduce  $F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})$.   As the weights of three operations  on one edge share a softmax distribution in~\eqref{equationoperation}, increasing   one operation weight means reducing  other operation weights.    Thus,   skip connections  gradually dominate over other types of operations for most connections in the cell.    So when pruning  operations according to their weights,  most of skip connections are preserved while most of  other  operations are pruned. This explains the dominated skip connections in the cell selected by DARTS.

\section{Path-Regularized Differential Network Architecture Search}\label{methodpart}
The proposed method consists of two main components, \emph{i.e.}~group-structured  sparse stochastic gate for each operation and path-depth-wise regularization on gates, which are introduced below in turn.

\subsection{Group-structured Sparse Operation Gates}
The analysis in Sec.~\ref{DARTSanalysis} shows that skip connection has superior competing advantages over other types of operations when they share  one softmax distribution.  To resolve this issue, we introduce independent stochastic gate  for each operation between two nodes to avoid the direct competition between skip connection and other operations. Specifically, we define a stochastic binary gate $\gnii{l}{s,t}$ for the $t$-th operation between nodes $\Xnii{s}{}$ and $\Xnii{l}{}$, where $\gnii{l}{s,t} \!\sim\! \text{Bernoulli}\big( \!\exp(\betanii{l}{s,t})/(1\!+\!\exp(\betanii{l}{s,t})\big)$. Then at each iteration, we sample gate $\gii{(l)}{s,t}$   from its   Bernoulli distribution and compute each node as
\begin{equation}\label{conenctionwaypcdarts}
{\Xnii{l}{} = \sum\nolimits_{1\leq i <l} \sum\nolimits_{t=1}^{r} \gnii{l}{s,t} O_{t}\big(\Xnii{i}{} \big)}.
\end{equation}
Since the discrete sampling of $\gnii{l}{s,t}$ is not differentiable, we use Gumbel technique~\cite{dyson1962statistical,maddison2014sampling} to approximate $\gnii{l}{s,t}$ as $\gnbii{l}{s,t}=\Theta\big((\ln \delta - \ln(1-\delta) + \betanii{l}{s,t})/\tau\big)$ where $\Theta$ denotes sigmoid function, $\delta\sim \mbox{Uniform}(0,1)$.  For temperature {$\tau$},   when {$\tau$}$\rightarrow 0$ the approximated distribution $\gnbii{l}{s,t}$ recovers Bernoulli distribution and is  non-smooth, while when {$\tau$}$\rightarrow +\infty$,   the approximated distribution becomes very smooth. In this way, the gradient can be back-propagated through $\gnbii{l}{s,t}$ to the network parameter $\bm{W}$.

If there is no   regularization on the independent gates, then there are two issues. The first one is that the selected cells would have   large weights for most operations. This is because (1) as shown in Theorem~\ref{mainconvergence3}, increasing operation weights can lead to faster convergence rate; (2) increasing weights of any operations can strictly reduce or maintain the  loss which is formally stated in Theorem~\ref{lossproperty}. Let   $t_{\mbox{\tiny{skip}}}$ and $t_{\mbox{\tiny{conv}}}$  respectively be     the indexes of skip connection and convolution in the operation set $\mathcal{O}$.

\begin{thm}\label{lossproperty}
	Assume the weights in DARTS model~\eqref{dartsmodel} is replaced with the independent gates $\gnii{l}{s,t}$. \\
	(1) Increasing the value of $\gnii{l}{s,t}$ of the operations, including zero operation, skip connection, pooling, and convolution with any kernel size,  can reduce or maintain the loss $F_{\mbox{\tiny{val}}}(\bm{W}^*(\bm{\beta}), \bm{\beta})$ in \eqref{dartsmodel}. \\
	(2) Suppose the assumptions in Theorem~\ref{mainconvergence3} hold. With  probability at least $1-\delta$,  increasing   $\gnii{l}{s,t_{\mbox{\tiny{skip}}}}\ (0\!\leq \!$~{$s$}~$\!<\!l\!<h-1)$  of skip connection or   $\gnii{h-1}{s,t_{\mbox{\tiny{conv}}}}\ (0\!\leq \!$~{$s$}~$\!<\!h-1)$ of convolution with increment {$\epsilon$} can reduce the  loss $F_{\mbox{\tiny{val}}}(\bm{W}^*(\bm{\beta}), \bm{\beta})$ in \eqref{dartsmodel} to $F_{\mbox{\tiny{val}}}(\bm{W}^*(\bm{\beta}), \bm{\beta})- C${$\epsilon$} in expectation, where $C$ is a positive constant.\vspace{-0.5em}
\end{thm}

See its  proof in Appendix~\ref{Proofoflossproperty}.
Theorem~\ref{lossproperty} shows that DARTS with independent  gates would tune the weights of most operations large to obtain faster convergence and smaller loss, leading to dense cells and thus  performance degradation when pruning these large weights.  The second issue is that independent gates cannot encourage  benign competition and cooperation among operations, as Theorem~\ref{lossproperty} shows most operations tend to increase their weights. Considering the performance degradation caused by  pruning  dense cells,  benign competition and cooperation among operations  are necessary for gradually pruning unnecessary   operations to obtain relatively   sparse selected cells.

To resolve these two issues,  we impose group-structured sparsity regularization on the   stochastic gates. Following~\cite{louizos2017learning} we stretch $\gnbii{l}{s,t}$ from the range $[0,1]$ to $[${$a,b$}$]$ via rescaling $\gntii{l}{s,t} \!=\!$~{$a$}$+(${$b\!-a$}$)\gnbii{l}{s,t}$,   where {$a$}~$\!<\!0$ and {$b$}~$\!>\!1$ are two constants. Then we feed   $\gntii{l}{s,t}$ into a hard threshold gate to obtain  the gate   $\gnii{l}{s,t}\!=\! \min(1,\max(0, \gntii{l}{s,t}))$.  In this way, the gate   $\gnii{l}{s,t}$ enjoys good properties, \emph{e.g.}~exact zero values and computable activation probability ($\mathbb{P}(\gnii{l}{s,t}\!\neq\! 0$), which are formally stated in Theorem~\ref{gateproperty}.
\begin{thm}\label{gateproperty}
	For each stochastic gate $\gii{(l)}{s,t}$, it satisfies $\gnii{l}{s,t}=
	0$ when $\gntii{l}{s,t}\in(0,-\frac{a}{b-a}]$; $\gnii{l}{s,t}=
	\gntii{l}{s,t}$ when $\gntii{l}{s,t}\in(-\frac{a}{b-a}, \frac{1- a}{b-a}]$; $\gnii{l}{s,t}=
	1$ when $ \gntii{l}{s,t}\in(\frac{1- a}{b-a},1]$. Moreover, $ \mathbb{P}(\gnii{l}{s,t}\neq 0) =\Theta(\betanii{l}{s,t} - \tau \ln \frac{-a}{b} ).$ \vspace{-0.5em}
\end{thm}
See its   proof in Appendix~\ref{proofofgateproperty}.  Theorem~\ref{gateproperty} shows that the  gate $\gnii{l}{s,t}$ can achieve exact zero, which  can reduce  information loss caused by pruning at the end of search. Next based on the activation probability   $\mathbb{P}(\gii{(l)}{s,t} \!\neq\!0)$ in Theorem~\ref{gateproperty}, we design group-structured sparsity regularizations. We collect all skip connections in the cell as a skip-connection  group  and take the remaining   operations into non-skip-connection group. Then we   compute the average  activation probability of these two groups:
\begin{equation*}
{\mathcal{L}_{\mbox{\tiny{skip}}}(\bm{\beta}) \!=\!\zeta \sum_{l=1}^{h-1}  \sum_{s=0}^{l-1}   \Theta \Big(\betaii{(l)}{s,t_{\mbox{\tiny{skip}}}} \!\!- \!\tau \ln \!\frac{-a}{b} \Big),\    \mathcal{L}_{\mbox{\tiny{non-skip}}}(\bm{\beta}) \!=\! \frac{\zeta}{r-1}\!\sum_{l=1}^{h-1}  \sum_{s=0}^{l-1}  \sum_{1\leq t \leq r, t \neq t_{\mbox{\tiny{skip}}}}\! \!\!\! \!\!\Theta \Big(\betaii{(l)}{s,t}\! -\! \tau \ln \!\frac{-a}{b} \Big)\!,}
\end{equation*}
where $\zeta\!=\!\frac{2}{h(h-1)}$. Then we respectively regularize  $\mathcal{L}_{\mbox{\tiny{skip}}}$ and $\mathcal{L}_{\mbox{\tiny{non-skip}}}$ by two different regularization constants $\lambda_1$ and $\lambda_2$ ($\lambda_1\!>\!\lambda_2$ in experiments).  This group-structured sparsity has three benefits: (1) penalizing skip connections heavier than other types of operations can rectify the competitive advantage of skip connections over other operations and avoids skip-connection-dominated cell;   (2) sparsity regularizer gradually and automatically prunes redundancy and unnecessary connections which reduces the information loss of pruning at the end of search;   (3)  sparsity regularizer defined on the whole cell can encourage global competition and cooperation of all operations in the cell, which differs from DARTS that only introduces local competition among the operations between two nodes.

\begin{wrapfigure}{r}{0.39\linewidth}
	\vspace{-1.8em}
	\begin{center}
		\setlength{\tabcolsep}{0.1pt}
		\begin{tabular}{c}
			\includegraphics[width=\linewidth]{fig1/illustation11.pdf}\vspace{-0.2em}\\
			{\small (a)}\vspace{-0.14em}\\
			\includegraphics[width=\linewidth]{fig1/illustation22.pdf}\vspace{-0.18em}\\
			{\small (b)}\vspace{-0.2em}\\
		\end{tabular}
	\end{center}
	\vspace{-1.1em}
	\caption{Illustration of a deep  cell (a)  and a shallow   cell (b).}
	\label{deepandshallow}
	\vspace{-1.2em}
\end{wrapfigure}
\subsection{Path-depth-wise  Regularizer on Operation Gates}
Except for the above advantages,  independent sparse gates also introduce one issue: they prohibit the method to select deep cells.  Without dominated skip connections in the cell,  other types of operations, \emph{e.g.}~zero operation, become freer and are widely used.  Accordingly, the search algorithm can easily transform a deep cell to a shallow  cell whose intermediate nodes  connect with input nodes via
skip connections and whose intermediate neighboring nodes are not connected via zero operations.
Meanwhile,  gradient descent algorithm prefers shallow cells than deep ones, as shallow cells often have more smooth landscapes and can be faster optimized. So these two factors together lead to a  bias of   search algorithm to shallow cells.
Here we provide an example to prove the faster convergence of shallow cells. Suppose $\Xnii{l}{} (l\!=\!0,\!$ $ \cdots\!,h\!-\!1)$ are in two branches  in Fig.~\ref{deepandshallow} (b):   nodes $\Xnii{0}{} $ to $\Xnii{\frac{h}{2}-1}{}$ are in one branch with input $\bm{X}$ and they are connected via~\eqref{conenctionwaypcdarts}, and  $\Xnii{l}{}\ (l\!=\!\frac{h}{2},\cdots,h\!-\!1)$ are in another branch with input $\bm{X}$ and connection~\eqref{conenctionwaypcdarts}. Next, similar to DARTS we use all intermediate nodes to obtain a  squared loss in~\eqref{loss}.   Then we show  in Theorem~\ref{fasterconvergenceloss}  that   the shallow cell \textsf{B}  in Fig.~\ref{deepandshallow} (b) enjoys much faster convergence than the deep cell \textsf{A} in Fig.~\ref{deepandshallow} (a).  Note for cell \textsf{B}, when its node $\Xnii{h/2}{}$ connects with  node $\Xnii{l}{} (l<h/2-1)$, we have very similar results.

\begin{thm}\label{fasterconvergenceloss}
	Suppose the assumptions in Theorem~\ref{mainconvergence3} hold and for each  $\gnii{l}{s,t}\ (0\!\leq\! s <\! l \!\leq \!h-1)$ in deep cell \textsf{A},  it has the same value in  shallow cell \textsf{B}  if it occurs in \textsf{B}. When  optimizing  $\bm{W}$ in $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ via gradient descent~\eqref{updation},  both  losses of  cells \textsf{A} and \textsf{B} obey $F_{\mbox{\tiny{train}}}(\bm{W}(k\!+\!1), \bm{\beta}) \!  \leq \!\left( 1 \!-\! \eta  \lambda'/4\right)F_{\mbox{\tiny{train}}}(\bm{W}(k), \bm{\beta})$, where $\lambda'$ in \textsf{A} is defined as   $\lambda_{\mbox{\tiny{\textsf{A}}}}
	= \frac{3c_{\sigma}}{4} \lambda_{\min}(\bm{K})\ \sum_{s=0}^{h-2}(\gnii{h-1}{s,3} )^2
	\prod_{t=0}^{s-1}  (\gnii{s}{t,2})^2  $, while  $\lambda'$  in \textsf{B} becomes  $\lambda_{\mbox{\tiny{\textsf{B}}}} $ and obeys $\lambda_{\mbox{\tiny{\textsf{B}}}} \geq \lambda_{\mbox{\tiny{\textsf{A}}}} +
	\frac{3c_{\sigma}}{4} \lambda_{\min}(\bm{K}) \sum_{s=h/2}^{h-1} (\gnii{h-1}{s,3} )^2
	\prod_{t=h/2}^{s-1}   (\gnii{s}{t,2})^2 > \lambda_{\mbox{\tiny{\textsf{A}}}}
	$. \vspace{-0.3em}
\end{thm}

See its  proof in Appendix~\ref{Proofoffasterconvergenceloss}.
Theorem~\ref{fasterconvergenceloss} shows that when using gradient descent  to optimize the inner-level   loss $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ equipped with independent gates,  shallow  cells  can  faster reduce the  loss  $F_{\mbox{\tiny{train}}}(\bm{W},\bm{\beta})$ than deep cells. As   training and validation data come from the same distribution which means  $\mathbb{E} [F_{\mbox{\tiny{train}}}(\bm{W}\!,\bm{\beta})]\!=\!\mathbb{E}[F_{\mbox{\tiny{val}}}(\bm{W}\!,\bm{\beta})]$,  shallow  cells  reduce $F_{\mbox{\tiny{val}}}(\bm{W},\bm{\beta})$ faster in expectation which accords with the theoretical and empirical results in~\cite{sankararaman2019impact}.  So it is likely that to avoid deep cells, search algorithm would connect  intermediate nodes with  input nodes and cut the connection between  neighboring  nodes via zero operation, which is indeed illustrated by Fig.~\ref{illustrationcomponents}  (b). But it leads to cell-selection bias in the search phase, as some cells  that   fast decay the loss $F_{\mbox{\tiny{val}}}(\bm{W},\bm{\beta})$ at the current iteration  have   competitive advantage over  other cells that reduce $F_{\mbox{\tiny{val}}}(\bm{W},\bm{\beta})$ slowly currently  but can achieve superior final performance. This prohibits us to search good cells.

\makebox[\textwidth][s]{To resolve this cell-selection bias, we propose a path-depth-wise regularization to   rectify the unfair}

competition between shallow and deep cells. From Theorem~\ref{gateproperty},  the  probability that  $\Xnii{l}{}$ and $\Xnii{l+1}{}$ are connected by parameterized  operations $\mathcal{O}_{\mbox{\tiny{p}}}$,  \emph{e.g.}~various types of convolutions, is $\mathbb{P}_{l,l+1}(\bm{\beta})$ $= \! \sum_{\mathcal{O}_t \in \mathcal{O}_{\mbox{\tiny{p}}}} \!\Theta\big(\betanii{l+1}{l,t}\! -\! \tau \ln \frac{-a}{b} \big)$.  So  the probability that all neighboring nodes $\Xnii{l}{}$ and $\Xnii{l+1}{}$  ($l=0,\cdots,h-1$) are connected via  operations $\mathcal{O}_{\mbox{\tiny{p}}}$, namely, the probability of the path of depth $h$,  is
\begin{equation}\label{pathregularization}
{ \mathcal{L}_{\mbox{\tiny{path}}}(\bm{\beta}) =\prod\nolimits_{l=1}^{h-1}\mathbb{P}_{l,l+1}(\bm{\beta}) =\prod\nolimits_{l=1}^{h-1} \sum\nolimits_{O_t \in \mathcal{O}_{p}} \Theta\big(\betaii{(l+1)}{l,t} - \tau \ln \frac{-a}{b} \big).}
\end{equation}
Here we do not consider  skip connection, zero and pooling operations, as they indeed make  a network shallow. To rectify the   competitive advantage of shallow cells over deep ones, we impose path-depth-wised regularization $- \mathcal{L}_{\mbox{\tiny{path}}}(\bm{\beta})$ on the stochastic gates to encourage more exploration to deep cells   and then decide the depth of cells instead of greedily choosing shallow cell at the beginning of   search.

Now we are ready to define our proposed PR-DARTS model  as follows:
\begin{equation*}\label{PCdartsmodel}
\min_{\bm{\beta}} F_{\mbox{\tiny{val}}}(\bm{W}^*\!(\betaii{}{}), \betaii{}{}) + \lambda_{1} \mathcal{L}_{\mbox{\tiny{skip}}}(\bm{\beta})  +  \lambda_{2} \mathcal{L}_{\mbox{\tiny{non-skip}}}(\bm{\beta})   - \lambda_{3} \mathcal{L}_{\mbox{\tiny{path}}}(\bm{\beta}),\   \mbox{s.t.} \bm{W}^*\!(\betaii{}{})\!=\!\argmin\nolimits_{\bm{W}} F_{\mbox{\tiny{train}}}(\bm{W}, \betaii{}{}),
\end{equation*}
where
$\bm{W}$ denotes network parameters, $\betaii{}{}$ denotes the parameters for the stochastic gates. Similar to  DARTS,  we  alternatively update  parameters $\bm{W}$ and  $\betaii{}{}$ via gradient descent. See optimization details in   Algorithm~\ref{searchalgorithm} of  Appendix~\ref{lamgugetask}.   After searching, following DARTS, we  prune   redundancy connections according to the activation probability in Theorem~\ref{gateproperty} to obtain more compact cells.

\vspace{-0.8em}
\section{Experiments}\label{experiments}
\vspace{-0.4em}
Here   we evaluate  PR-DARTS on  classification task and  compare it with  representative state-of-the-art NAS approaches, including RL based NAS, EA based NAS and differential NAS methods. Code is available at \url{https://panzhous.github.io/}.

\textbf{Datasets.}
CIAFR10~\cite{krizhevsky2009learning} and CIFAR100~\cite{krizhevsky2009learning} contain 50K training and 10K test images which are of size $32\times32$ and   distribute over  10 classes in CIFAR10 and 100 classes in CIFAR100.  ImageNet~\cite{russakovsky2015imagenet} has  1.28M training and 50K test images  which  roughly equally distribute over 1K object categories.

\textbf{Implementations.}
For searching, each cell contains two input nodes (outputs of two previous cells), four intermediate nodes and one output node (concatenation of all intermediate nodes). Then we stack $k$ cells  for search. The $k/3$- and $2k/3$-th cells are reduction cells in which all operations have a stride of two, and the remaining cells are normal cells with operation stride of one.  Reduction cells share the same architecture and normal cells also have the same architecture.  The operation set $\mathcal{O}$  has eight choices: zero operation, skip connection, $3\!\times\! 3$ and $5\!\times\! 5$ separable convolutions, $3\!\times\! 3$ and $5\!\times \!5$ dilated separable convolutions, $3\!\times \!3$ average pooling and $3\!\times \!3$ max pooling.  For fairness, all above settings follow the convention~\cite{zoph2016neural,zoph2018learning,real2019regularized,liu2018darts}.
For each cell,  we use the input node which is the output of the previous cell to construct the path-depth-wise regularization in \eqref{pathregularization}  as illustrated by Fig.~\ref{illustrationcomponents} (c).

\begin{savenotes}
	\begin{table*}[tp]
		\begin{threeparttable}[b]
			\caption{Classification errors ($\%$) on CIFAR10 (C10) and CIFAR100 (C100).\vspace{-0.5em}}
			\setlength{\tabcolsep}{5.9pt}
			\renewcommand{\arraystretch}{0.7}
			\label{CIFARcomparsion} \begin{center}
				{ \fontsize{8.1}{3}\selectfont{
						\begin{tabularx}{\textwidth}{c|cc ccc cc}\toprule
							\multirow{2}{*}{\textbf{Architecture}} &\multicolumn{2}{c}{ \textbf{Test Error ($\%$)}} & \textbf{Params} &  \textbf{Search Cost} & \textbf{Search space} & \textbf{Search}  \\
							& \textbf{C10} & \textbf{C100} &  \textbf{(M)}	 & \textbf{(GPU-days)} & \textbf{$\#$Ops$/$zero} & \textbf{method}\\
							\midrule
							DenseNet-BC~\cite{huang2017densely} &3.46 & 17.18& 25.6 & --- &---& manual  \\
							\midrule
							NASNet-A + cutout~\cite{zoph2018learning} & 2.65 & ---& 3.3  & 1800& 13 & RL\\
							AmoebaNet-B + cutout~\cite{real2019regularized}  & 2.55 & ---& 2.8  & 3150& 19 & evolution\\
							PNAS~\cite{liu2018progressive} & 3.41 & ---& 3.2 & 225& 8 & SMBO\\
							ENAS + cutout~\cite{pham2018efficient}& 2.89 & ---& 4.6  & 0.5 & 6 & RL\\
							\midrule
							DARTS (first-order) + cutout~\cite{liu2018darts} &3.00 & 17.76 & 3.3  & 1.5 & 7 & gradient-based\\
							DARTS (second-order) + cutout~\cite{liu2018darts} &2.76 & 17.54 & 3.3   & 4.0& 7& gradient-based\\
							SNAS (moderate) + cutout~\cite{xie2018snas} &2.85& --- & 2.8 & 1.5 &7& gradient-based\\
							P-DARTS +  cutout~\cite{chen2019progressive} &2.50& 16.55 & 3.4 & 0.3&7 & gradient-based\\
							BayesNAS +  cutout~\cite{zhou2019bayesnas} &2.81& --- & 3.4  & 0.18 &7& gradient-based\\
							PC-DARTS +  cutout~\cite{xu2019pc} &2.81& --- & 3.6 & 0.13 &7& gradient-based\\
							GDAS + cutout~\cite{dong2019searching} &2.93& --- & 3.4 & 0.21 &7& gradient-based\\
							Fair DARTS + cutout~\cite{chu2019fair} &2.54& --- & 2.8  & 0.4 &7& gradient-based\\
							\midrule
							PR-DARTS + cutout &  2.32   &  16.45  & 3.4   & 0.17 & 7 & gradient-based  \\
							\bottomrule
						\end{tabularx}
				}}
			\end{center}
			\vspace{-0.2em}
		\end{threeparttable}
	\end{table*}
	\vspace{-0.8em}
\end{savenotes}

\vspace{-0.2em}
\subsection{Results on CIFAR}\label{CIFAR}
\vspace{-0.3em}
In the search phase, following~\cite{liu2018darts} we stack 8 cells with channel number 16. We divide  50K training samples in CIFAR10 into two equal-sized training and validation datasets.   In PR-DARTS, we set   $\lambda_1\!=\!0.01$, $\lambda_2\!=\!0.005$, and $\lambda_3\!=\!0.005$ for regularization.  Then we train the network 200 epochs with mini-batch size 128. For acceleration, per iteration, we follow~\cite{dong2019searching} and randomly select only two operations on each edge to update.  We respectively use   SGD and ADAM~\cite{kingma2014adam} to optimize parameters $\bm{W}$ and $\bm{\beta}$ with detailed settings in Appendix~\ref{lamgugetask}.
We set temperature  {$\tau$}~$\!=\!10$ and  linearly reduce it to 0.1, {$a$}~$\!=-0.1$ and {$b$}~$\!=\!1.1$. For pruning on each node,  we compare the gate activation probabilities of all non-zero  operations collected from all  previous nodes and retain top two operations~\cite{liu2018darts} .

For evaluation on CIFAR10 and CIFAR100, we set channel number 36 and then stack  18 normal cells and 2 reduction cells (the 7- and 14-th cells) to build a large network. We train the network 600 epochs with a mini-batch size of 128 from scratch.  See detailed settings of  SGD   in Appendix~\ref{lamgugetask}.  We also use drop-path with probability 0.2 and   cutout~\cite{devries2017improved} with length 16, for regularization.

Table~\ref{CIFARcomparsion} summarizes the classification results on CIFAR10 and CIFAR100.  In merely 0.17 GPU-days on Tesla V100, PR-DARTS respectively achieves $2.31\%$ and $16.45\%$ classification errors on CIAR10 and CIFAR100, with both search time and accuracy significantly surpassing the DARTS baseline. By comparison, PR-DARTS  also consistently outperforms other NAS approaches, including differential NAS (\emph{e.g.}~P-DARTS, PC-DARTS),  RL based NAS (\emph{e.g.}~NASNet), as well as EA based NAS (\emph{e.g.} Amobdanet).
These results demonstrate the superiority and transferability of the selected cells by  PR-DARTS. As shown in Fig.~\ref{illustrationcomponents},  this advantage comes from the group-structured binary gates and path-depth-wise regularization in PR-DARTS which can well alleviate unfair operation competition and cell-selection bias to shallow cells which are not well considered in the compared   NAS methods.
Fair DARTS  imposes independent sigmoid distribution and zero-one loss for each operation,  which actually does not encourage the important global operation competition and cooperation.
PR-DARTS runs faster over DARTS, because (1) the sparsity regularization prunes unnecessary connections as illustrated in Fig.~\ref{cells} in Appendix~\ref{lamgugetask}, and thus reduces the costs; and (2) following~\cite{dong2019searching} we randomly select only two operations instead of eight operations between two nodes to update per iteration, also helping reducing cost.
Note, Proxyless NAS~\cite{cai2018proxylessnas} reports an error rate of 2.08$\%$ on CIAFR10, but it performs architecture search on the tree-structured  PyramidNet~\cite{cai2018path} which is much complex protocol than the DARTS search space in this work, and requires much longer time (4 GPU-days) for search.

For \textit{ablation study}, Fig.~\ref{illustrationcomponents} shows the individual benefits of the two complementary components, group-structured binary gates and path-depth-wise regularization, in PR-DARTS. See details in  Fig.~\ref{illustrationcomponents}.
Due to space limit, Appendix~\ref{lamgugetask} investigates  the \textit{effects of regularization parameters}  $\lambda_1\!\sim\!\lambda_3$ to the  performance of PR-DARTS.   The results show the stable performance of PR-DARTS on CIAFR10 when tuning these parameters in a relatively large range, and thus testify the robustness of PR-DARTS.

\begin{savenotes}
	\begin{table*}[tp]
		\begin{threeparttable}[b]
			\caption{\!Classification errors ($\%$) on ImageNet {\small(all methods use the cells searched on CIFAR10).}\vspace{-0.5em}}
			\setlength{\tabcolsep}{6.0pt}
			\renewcommand{\arraystretch}{0.7}
			\label{Imagenetresults} \begin{center}
				{ \fontsize{8.1}{3}\selectfont{
						\begin{tabularx}{\textwidth}{c|cc cccc cc}\toprule
							\multirow{2}{*}{\textbf{Architecture}} &\multicolumn{2}{c}{ \textbf{Test Error ($\%$)}} & \textbf{Params} & \textbf{$\bm{\times +}$}	&  \textbf{Search Cost} & \textbf{Search space} & \textbf{Search}  \\
							& \textbf{Top-1} & \textbf{Top-5} & \textbf{(M)} & \textbf{(M)}	 & \textbf{(GPU-days)} & \textbf{$\#$Ops$/$zero}  & \textbf{method}\\
							\midrule
							MobileNet~\cite{howard2017mobilenets} &29.4 & 10.5& 4.2 &569& --- &---& manual  \\
							ShuffleNet2$\times$(v2)~\cite{ma2018shufflenet} &25.1& ---& $\sim$5 &591& --- &---& manual  \\
							\midrule
							NASNet-A~\cite{zoph2018learning} & 26.0 & 8.4& 5.3 & 564 & 1800& 13 & RL\\
							AmoebaNet-C~\cite{real2019regularized}  & 24.3 & 7.6& 6.4 & 570 & 3150& 19 & evolution\\
							PNAS~\cite{liu2018progressive} & 25.8 & 8.1& 5.1 & 588 & 225& 8 & SMBO\\
							MnaNet-92~\cite{tan2019mnasnet} & 25.2 & 8.0& 4.4 & 388 & --- & hierarchical & RL\\
							\midrule
							DARTS (second-order)~\cite{liu2018darts} &26.7 & 8.7 & 4.7 &  574& 4.0& 7& gradient-based\\
							SNAS (mild)~\cite{xie2018snas} &27.3& 9.2 & 4.3 & 522& 1.5 &7& gradient-based\\
							P-DARTS~\cite{chen2019progressive} &24.4& 7.4  & 4.9 &557& 0.3&7 & gradient-based\\
							BayesNAS~\cite{zhou2019bayesnas} &26.5& 8.9 & 3.9 & --- & 0.18 &7& gradient-based\\
							PC-DARTS~\cite{xu2019pc} &25.1 & 7.8 & 5.3 & 586& 0.13 &7& gradient-based\\
							GDAS~\cite{dong2019searching} &26.0& 8.5 & 5.3 & 581& 0.21 &7& gradient-based\\
							Fair DARTS~\cite{chu2019fair} &24.9& 7.5& 4.8  & 541 &  0.4  &7& gradient-based\\
							\midrule
							PR-DARTS  & 24.1 & 7.3 & 4.98 & 543 & 0.17 & 7 & gradient-based  \\
							\bottomrule

						\end{tabularx}
				}}
			\end{center}
			\vspace{-1.0em}
		\end{threeparttable}
	\end{table*}
\end{savenotes}

\vspace{-0.5em}
\subsection{Results on ImageNet}
\vspace{-0.3em}
We further evaluate the transferability of the cells selected on CIFAR10 by testing them on more challenging ImageNet. Following DARTS, we rescale input size to  $224\times 224$. We stack three convolutional layers,12 normal cells and 2 reduction cells (channel number  48) to build a large network, and train it 250 epochs with mini-batch size 128.  See detailed settings of  SGD   in Appendix~\ref{lamgugetask}.

Table~\ref{Imagenetresults} reports the  results on ImageNet. One can observe that PR-DARTS consistently outperforms the compared state-of-the-art approaches. In particular, it respectively improves DARTS by  $2.4\%$  and  $1.4\%$  on top-1  and top 5 accuracies. These results demonstrate the superior transferability of the cells selected by PR-DARTS behind which the potential reasons have been discussed in Sec.~\ref{CIFAR}.

\vspace{-0.7em}
\section{Conclusion}
\vspace{-0.3em}
In this work,  for the first time we theoretically explicitly show the benefits of more skip connections to fast network optimization in  DARTS,  explaining the dominated skip connections in the selected cells by DARTS. Then inspired by our theory, we propose PR-DARTS to improve DARTS by using group-structured binary gates and path-depth-wise regularization to alleviate unfair operation competition and cell-selection bias to  shallow cells. Experimental results validated the  advantages of PR-DARTS.

\newpage

\section*{Broader Impacts}
\label{sec:impact}
This work advances network architecture search (NAS) in both theoretical performance analysis and practical algorithm design. As NAS can automatically design state-of-the-art architectures,   this work alleviates substantial efforts from domain experts for effective architecture design, and could also help develop more intelligent algorithms. But NAS  still needs an expert-designed search space which may have bias and prohibit NAS development.  So automatically designing search space is desirable.

{
\small
\bibliographystyle{unsrt}

redpajama_set_name: RedPajamaArXiv