\section{Introduction}

The {\it IJCAI--22 Proceedings} will be printed from electronic
manuscripts submitted by the authors. These must be PDF ({\em Portable
Document Format}) files formatted for 8-1/2$''$ $\times$ 11$''$ paper.

\subsection{Length of Papers}

All paper {\em submissions} must have a maximum of six pages, plus at most one for references. The seventh page cannot contain {\bf anything} other than references.

The length rules may change for final camera-ready versions of accepted papers and will differ between tracks. Some tracks may include only references in the last page, whereas others allow for any content in all pages. Similarly, some tracks allow you to buy a few extra pages should you want to, whereas others don't.

If your paper is accepted, please carefully read the notifications you receive, and check the proceedings submission information website\footnote{\url{https://proceedings.ijcai.org/info}} to know how many pages you can finally use. That website holds the most up-to-date information regarding paper length limits at all times. Please notice that if your track allows for a special references-only page, the {\bf references-only page(s) cannot contain anything else than references} (i.e.: do not write your acknowledgments on that page or you will be charged for it).

\subsection{Word Processing Software}

As detailed below, IJCAI has prepared and made available a set of
\LaTeX{} macros and a Microsoft Word template for use in formatting
your paper. If you are using some other word processing software, please follow the format instructions given below and ensure that your final paper looks as much like this sample as possible.

\section{Style and Format}

\LaTeX{} and Word style files that implement these instructions
can be retrieved electronically. (See Appendix~\ref{stylefiles} for
instructions on how to obtain these files.)

\subsection{Layout}

Print manuscripts two columns to a page, in the manner in which these
instructions are printed. The exact dimensions for pages are:
\begin{itemize}
\item left and right margins: .75$''$
\item column width: 3.375$''$
\item gap between columns: .25$''$
\item top margin---first page: 1.375$''$
\item top margin---other pages: .75$''$
\item bottom margin: 1.25$''$
\item column height---first page: 6.625$''$
\item column height---other pages: 9$''$
\end{itemize}

All measurements assume an 8-1/2$''$ $\times$ 11$''$ page size. For
A4-size paper, use the given top and left margins, column width,
height, and gap, and modify the bottom and right margins as necessary.

\subsection{Format of Electronic Manuscript}

For the production of the electronic manuscript, you must use Adobe's
{\em Portable Document Format} (PDF). A PDF file can be generated, for
instance, on Unix systems using {\tt ps2pdf} or on Windows systems
using Adobe's Distiller. There is also a website with free software
and conversion services: \url{http://www.ps2pdf.com}. For reasons of
uniformity, use of Adobe's {\em Times Roman} font is strongly suggested.
In \LaTeX2e{} this is accomplished by writing
\begin{quote}
\mbox{\tt $\backslash$usepackage\{times\}}
\end{quote}
in the preamble.\footnote{You may want also to use the package {\tt
latexsym}, which defines all symbols known from the old \LaTeX{}
version.}

Additionally, it is of utmost importance to specify the {\bf
letter} format (corresponding to 8-1/2$''$ $\times$ 11$''$) when
formatting the paper. When working with {\tt dvips}, for instance, one
should specify {\tt -t letter}.

\subsection{Title and Author Information}

Center the title on the entire width of the page in a 14-point bold
font. The title must be capitalized using Title Case. Below it, center author name(s) in 12-point bold font. On the following line(s) place the affiliations, each affiliation on its own line using 12-point regular font. Matching between authors and affiliations can be done using numeric superindices. Optionally, a comma-separated list of email addresses follows the affiliation(s) line(s), using 12-point regular font.

\subsubsection{Blind Review}

In order to make blind reviewing possible, authors must omit their
names and affiliations when submitting the paper for review. In place
of names and affiliations, provide a list of content areas. When
referring to one's own work, use the third person rather than the
first person. For example, say, ``Previously,
Gottlob~\shortcite{gottlob:nonmon} has shown that\ldots'', rather
than, ``In our previous work~\cite{gottlob:nonmon}, we have shown
that\ldots'' Try to avoid including any information in the body of the
paper or references that would identify the authors or their
institutions. Such information can be added to the final camera-ready
version for publication.

\subsection{Abstract}

Place the abstract at the beginning of the first column 3$''$ from the
top of the page, unless that does not leave enough room for the title
and author information. Use a slightly smaller width than in the body
of the paper. Head the abstract with ``Abstract'' centered above the
body of the abstract in a 12-point bold font. The body of the abstract
should be in the same font as the body of the paper.

The abstract should be a concise, one-paragraph summary describing the
general thesis and conclusion of your paper. A reader should be able
to learn the purpose of the paper and the reason for its importance
from the abstract. The abstract should be no more than 200 words long.

\subsection{Text}

The main body of the text immediately follows the abstract. Use
10-point type in a clear, readable font with 1-point leading (10 on
11).

Indent when starting a new paragraph, except after major headings.

\subsection{Headings and Sections}

When necessary, headings should be used to separate major sections of
your paper. (These instructions use many headings to demonstrate their
appearance; your paper should have fewer headings.). All headings should be capitalized using Title Case.

\subsubsection{Section Headings}

Print section headings in 12-point bold type in the style shown in
these instructions. Leave a blank space of approximately 10 points
above and 4 points below section headings.  Number sections with
arabic numerals.

\subsubsection{Subsection Headings}

Print subsection headings in 11-point bold type. Leave a blank space
of approximately 8 points above and 3 points below subsection
headings. Number subsections with the section number and the
subsection number (in arabic numerals) separated by a
period.

\subsubsection{Subsubsection Headings}

Print subsubsection headings in 10-point bold type. Leave a blank
space of approximately 6 points above subsubsection headings. Do not
number subsubsections.

\paragraph{Titled paragraphs.} You should use titled paragraphs if and
only if the title covers exactly one paragraph. Such paragraphs should be
separated from the preceding content by at least 3pt, and no more than
6pt. The title should be in 10pt bold font and ended with a period.
After that, a 1em horizontal space should follow the title before
the paragraph's text.

In \LaTeX{} titled paragraphs should be typeset using
\begin{quote}
{\tt \textbackslash{}paragraph\{Title.\} text} .
\end{quote}

\subsubsection{Acknowledgements}

You may include an unnumbered acknowledgments section, including
acknowledgments of help from colleagues, financial support, and
permission to publish. If present, acknowledgements must be in a dedicated,
unnumbered section appearing after all regular sections but before any
appendices or references.

Use
\begin{quote}
    {\tt \textbackslash{}section*\{Acknowledgements\}})
\end{quote}
to typeset the acknowledgements section in \LaTeX{}.

\subsubsection{Appendices}

Any appendices directly follow the text and look like sections, except
that they are numbered with capital letters instead of arabic
numerals. See this document for an example.

\subsubsection{References}

The references section is headed ``References'', printed in the same
style as a section heading but without a number. A sample list of
references is given at the end of these instructions. Use a consistent
format for references. The reference list should not include publicly unavailable work.

\subsection{Citations}

Citations within the text should include the author's last name and
the year of publication, for example~\cite{gottlob:nonmon}.  Append
lowercase letters to the year in cases of ambiguity.  Treat multiple
authors as in the following examples:~\cite{abelson-et-al:scheme}
or~\cite{bgf:Lixto} (for more than two authors) and
\cite{brachman-schmolze:kl-one} (for two authors).  If the author
portion of a citation is obvious, omit it, e.g.,
Nebel~\shortcite{nebel:jair-2000}.  Collapse multiple citations as
follows:~\cite{gls:hypertrees,levesque:functional-foundations}.
\nocite{abelson-et-al:scheme}
\nocite{bgf:Lixto}
\nocite{brachman-schmolze:kl-one}
\nocite{gottlob:nonmon}
\nocite{gls:hypertrees}
\nocite{levesque:functional-foundations}
\nocite{levesque:belief}
\nocite{nebel:jair-2000}

\subsection{Footnotes}

Place footnotes at the bottom of the page in a 9-point font.  Refer to
them with superscript numbers.\footnote{This is how your footnotes
should appear.} Separate them from the text by a short
line.\footnote{Note the line separating these footnotes from the
text.} Avoid footnotes as much as possible; they interrupt the flow of
the text.

\section{Illustrations}

Place all illustrations (figures, drawings, tables, and photographs)
throughout the paper at the places where they are first discussed,
rather than at the end of the paper.

They should be floated to the top (preferred) or bottom of the page,
unless they are an integral part
of your narrative flow. When placed at the bottom or top of
a page, illustrations may run across both columns, but not when they
appear inline.

Illustrations must be rendered electronically or scanned and placed
directly in your document. They should be cropped outside \LaTeX{},
otherwise portions of the image could reappear during the post-processing of your paper.
When possible, generate your illustrations in a vector format.
When using bitmaps, please use 300dpi resolution at least.
All illustrations should be understandable when printed in black and
white, albeit you can use colors to enhance them. Line weights should
be 1/2-point or thicker. Avoid screens and superimposing type on
patterns, as these effects may not reproduce well.

Number illustrations sequentially. Use references of the following
form: Figure 1, Table 2, etc. Place illustration numbers and captions
under illustrations. Leave a margin of 1/4-inch around the area
covered by the illustration and caption.  Use 9-point type for
captions, labels, and other text in illustrations. Captions should always appear below the illustration.

\section{Tables}

Tables are considered illustrations containing data. Therefore, they should also appear floated to the top (preferably) or bottom of the page, and with the captions below them.

\begin{table}
\centering
\begin{tabular}{lll}
\hline
Scenario  & $\delta$ & Runtime \\
\hline
Paris       & 0.1s  & 13.65ms     \\
Paris       & 0.2s  & 0.01ms      \\
New York    & 0.1s  & 92.50ms     \\
Singapore   & 0.1s  & 33.33ms     \\
Singapore   & 0.2s  & 23.01ms     \\
\hline
\end{tabular}
\caption{Latex default table}
\label{tab:plain}
\end{table}

\begin{table}
\centering
\begin{tabular}{lrr}
\toprule
Scenario  & $\delta$ (s) & Runtime (ms) \\
\midrule
Paris       & 0.1  & 13.65      \\
            & 0.2  & 0.01       \\
New York    & 0.1  & 92.50      \\
Singapore   & 0.1  & 33.33      \\
            & 0.2  & 23.01      \\
\bottomrule
\end{tabular}
\caption{Booktabs table}
\label{tab:booktabs}
\end{table}

If you are using \LaTeX, you should use the {\tt booktabs} package, because it produces better tables than the standard ones. Compare Tables \ref{tab:plain} and~\ref{tab:booktabs}. The latter is clearly more readable for three reasons:

\begin{enumerate}
    \item The styling is better thanks to using the {\tt booktabs} rulers instead of the default ones.
    \item Numeric columns are right-aligned, making it easier to compare the numbers. Make sure to also right-align the corresponding headers, and to use the same precision for all numbers.
    \item We avoid unnecessary repetition, both between lines (no need to repeat the scenario name in this case) as well as in the content (units can be shown in the column header).
\end{enumerate}

\section{Formulas}

IJCAI's two-column format makes it difficult to typeset long formulas. A usual temptation is to reduce the size of the formula by using the {\tt small} or {\tt tiny} sizes. This doesn't work correctly with the current \LaTeX{} versions, breaking the line spacing of the preceding paragraphs and title, as well as the equation number sizes. The following equation demonstrates the effects (notice that this entire paragraph looks badly formatted):
\begin{tiny}
\begin{equation}
    x = \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i
\end{equation}
\end{tiny}%

Reducing formula sizes this way is strictly forbidden. We {\bf strongly} recommend authors to split formulas in multiple lines when they don't fit in a single line. This is the easiest approach to typeset those formulas and provides the most readable output%
\begin{align}
    x =& \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \nonumber\\
    + & \prod_{i=1}^n \sum_{j=1}^n j_i
\end{align}%

If a line is just slightly longer than the column width, you may use the {\tt resizebox} environment on that equation. The result looks better and doesn't interfere with the paragraph's line spacing: %
\begin{equation}
\resizebox{.91\linewidth}{!}{$
    \displaystyle
    x = \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i
$}
\end{equation}%

This last solution may have to be adapted if you use different equation environments, but it can generally be made to work. Please notice that in any case:

\begin{itemize}
    \item Equation numbers must be in the same font and size as the main text (10pt).
    \item Your formula's main symbols should not be smaller than {\small small} text (9pt).
\end{itemize}

For instance, the formula
\begin{equation}
    \resizebox{.91\linewidth}{!}{$
    \displaystyle
    x = \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j
$}
\end{equation}
would not be acceptable because the text is too small.

\section{Examples, Definitions, Theorems and Similar}

Examples, definitions, theorems, corollaries and similar must be written in their own paragraph. The paragraph must be separated by at least 2pt and no more than 5pt from the preceding and succeeding paragraphs. They must begin with the kind of item written in 10pt bold font followed by their number (e.g.: Theorem 1), optionally followed by a title/summary between parentheses in non-bold font and ended with a period. After that the main body of the item follows, written in 10 pt italics font (see below for examples).

In \LaTeX{} We strongly recommend you to define environments for your examples, definitions, propositions, lemmas, corollaries and similar. This can be done in your \LaTeX{} preamble using \texttt{\textbackslash{newtheorem}} -- see the source of this document for examples. Numbering for these items must be global, not per-section (e.g.: Theorem 1 instead of Theorem 6.1).

\begin{example}[How to write an example]
Examples should be written using the example environment defined in this template.
\end{example}

\begin{theorem}
This is an example of an untitled theorem.
\end{theorem}

You may also include a title or description using these environments as shown in the following theorem.

\begin{theorem}[A titled theorem]
This is an example of a titled theorem.
\end{theorem}

\section{Proofs}

Proofs must be written in their own paragraph separated by at least 2pt and no more than 5pt from the preceding and succeeding paragraphs. Proof paragraphs should start with the keyword ``Proof." in 10pt italics font. After that the proof follows in regular 10pt font. At the end of the proof, an unfilled square symbol (qed) marks the end of the proof.

In \LaTeX{} proofs should be typeset using the \texttt{\textbackslash{proof}} environment.

\begin{proof}
This paragraph is an example of how a proof looks like using the \texttt{\textbackslash{proof}} environment.
\end{proof}


\section{Algorithms and Listings}

Algorithms and listings are a special kind of figures. Like all illustrations, they should appear floated to the top (preferably) or bottom of the page. However, their caption should appear in the header, left-justified and enclosed between horizontal lines, as shown in Algorithm~\ref{alg:algorithm}. The algorithm body should be terminated with another horizontal line. It is up to the authors to decide whether to show line numbers or not, how to format comments, etc.

In \LaTeX{} algorithms may be typeset using the {\tt algorithm} and {\tt algorithmic} packages, but you can also use one of the many other packages for the task.

\begin{algorithm}[tb]
\caption{Example algorithm}
\label{alg:algorithm}
\textbf{Input}: Your algorithm's input\\
\textbf{Parameter}: Optional list of parameters\\
\textbf{Output}: Your algorithm's output
\begin{algorithmic}[1]
\STATE Let $t=0$.
\WHILE{condition}
\STATE Do some action.
\IF {conditional}
\STATE Perform task A.
\ELSE
\STATE Perform task B.
\ENDIF
\ENDWHILE
\STATE \textbf{return} solution
\end{algorithmic}
\end{algorithm}

\section*{Acknowledgments}

The preparation of these instructions and the \LaTeX{} and Bib\TeX{}
files that implement them was supported by Schlumberger Palo Alto
Research, AT\&T Bell Laboratories, and Morgan Kaufmann Publishers.
Preparation of the Microsoft Word file was supported by IJCAI.  An
early version of this document was created by Shirley Jowell and Peter
F. Patel-Schneider.  It was subsequently modified by Jennifer
Ballentine and Thomas Dean, Bernhard Nebel, Daniel Pagenstecher,
Kurt Steinkraus, Toby Walsh and Carles Sierra. The current version
has been prepared by Marc Pujol-Gonzalez and Francisco Cruz-Mencia.


\section{Introduction}\label{sec1}
\subfile{sections/1_introduction}

\section{Preliminaries}\label{sec2}
\subfile{sections/2_preliminaries}

\section{Optimization Strategies}\label{sec3}
\subfile{sections/3_solutions}

\section{Performance Comparison}\label{sec4}
\subfile{sections/4_comparison}

\section{Future Directions}\label{sec5}
\subfile{sections/5_futuredirections}

\section{Conclusion}\label{sec6}
\subfile{sections/6_conclusion}

\section{Acknowledgement}\label{sec7}
\subfile{sections/7_acknowledgement}



\clearpage
{\small


\subsection{Neural Architecture Search (NAS)}
Neural Architecture Search\,(NAS) automatically finds an architecture for a deep learning task while satisfying accuracy constraints. The NAS process can be broken down into three parts: the search space, the search strategy, and the performance estimation strategy \cite{elsken2019neural}. 

\begin{itemize}
  \item \textbf{Search space.} The search space embodies the possible architectures for the given task. Introducing inductive bias when defining the search space is inevitable. However, works involving meta-learning \cite{lee2021rapid} constructs an embedded search space that circumvents such human bias. The earliest example of a search space would be a sequential layer of operations. 
  \item \textbf{Search strategy.} The search strategy determines how the architectures are sampled from the search space. There are two competing metrics here: architecture performance and search time. Finding high performing architectures may take a long time. A potential navigation method for this would be probing the Pareto frontier; the set of solutions where improving one objective will worsen another objective. Reinforcement learning\,\cite{zoph2016neural} and evolution\,\cite{real2017large} are other examples of search strategies. 
  \item \textbf{Performance estimation strategy.} The performance estimation strategy seeks to measure how well the searched architecture does on new unseen data. The naive way to do this is to predict on the validation set. Of course, full-training is computationally taxing and not the most practical way to do things. Works in the NAS literature has found many different proxies for performance estimation.
\end{itemize}

\subsection{Supernet Optimization}

We remark that the terms supernet and weight-sharing are at times used interchangeably and circularly in the NAS literature. For the purposes of this survey, we will distinguish and define those terms. 

A \textbf{supernet} is a neural network that contains all possible architectures to be sampled, i.e., it serves as the search space. Architectures are found by taking subnets from the supernet. We can represent a supernet as a Directed Acyclic Graph\,(DAG) where the nodes are feature maps and the edges are operations\,(e.g. convolution, pool, zero). We refer to figure \ref{fig:cell} for an illustration of a supernet.  

\begin{figure}[ht]
    \centering
    \hbox{\hspace{2cm}\includegraphics[width=5cm,keepaspectratio]{images/cell.png}}
    \caption{An illustration of a supernet. The nodes denote feature maps and the colored edges represent candidate operations. This supernet embodies the search space where a sampled architecture would be a subnet.}
    \label{fig:cell}
\end{figure}

A key feature of supernet-based NAS would be \textbf{weight-sharing} \cite{pham2018efficient}. Weight-sharing is done by first training a single large supernet. An RL-based controller \cite{pham2018efficient} then samples a subnet from the supernet. As a result, all sampled child networks share weights from the supernet. The introduction of weight-sharing has reduced GPU days for the search process from thousands of GPU days down to a few GPU days. \cite{zoph2016neural,real2017large,zoph2018learning}. The one-shot approach \cite{bender2018understanding} extends the weight-sharing technique. The authors train a single large supernet which is just a neural network trained using SGD with Momentum. During training, a linearly scheduled dropout strategy \cite{hinton2012improving} is used to prevent co-adaptation among operations (edges). The dropout rate starts at 0 and then linearly increases to $r^{1/k}$ where $0<r<1$ is a hyperparameter and $k$ is the number of incoming paths to a given operation. When applying dropout, a random subset of the operations are zeroed out. After training, subnets are randomly sampled from the trained supernet following a uniform distribution (other search methods such as evolution or reinforcement learning can be used instead). The sampled subnet is then evaluated on a held-out validation set. The resulting output is a list of candidate architectures ranked by one-shot accuracy (based on validation set). The best performing architectures can be selected to be retrained from scratch. 








\subsection{Data-Side Optimization}
A lot of works in supernet optimization focus on improving the architecture or the search phase itself. Works such as OFA\,\cite{cai2019once} and BigNAS\,\cite{yu2020bignas} seek to yield architectures that can be instantly deployed for tasks\,(these are mentioned in section \ref{tran}). Methods such as ENAS\,\cite{pham2018efficient} and DARTS\,\cite{liu2018darts} focus on searching architectures efficiently (quickly). However, the actual architecture and search phase are not the only avenues for improving a machine learning algorithm. Data is another route for optimization.

The issue of data is essential to any machine learning task. In this section, we survey supernet-based NAS with respect to data-side optimization. Given that the task is image classification, the image resolution is of concern. We cover High Resolution NAS\,(HR-NAS)\,\cite{ding2021hr} which is designed for high resolution images. For supervised learning, labels are integral. However, labelling high volumes of data is laborious and can be a bottleneck in the machine learning pipeline. We explore Random Label NAS\,(RLNAS)\,\cite{zhang2021neural} which removes ground truth labels and only uses random labels for the search. \iffalse In the case where data is limited, we discuss Contrastive NAS\,(CTNAS)\,\cite{chen2021contrastive} that does not estimate architecture performance but rather computes the probability that the sampled architecture will outperform a given baseline. One could also remove labels altogether, by considering the unsupervised case. We also survey supernet-based NAS that use unsupervised representation learning.\fi In addition, most NAS methods are fed input signals with clean data. There is a need for NAS methods that are robust against noisy data. We also look into NAS that is robust against Out-of-Distribution\,(OOD) data\,\cite{bai2021ood}.


\subsubsection{High Resolution Images}
Image resolution sizes in image classification tasks tend to be on the smaller side (about $224\times224)$. Naturally, computational requirements increases as image resolution goes up. So a natural concern is to develop methods that handle high resolution images. High Resolution NAS (HR-NAS) searches for architectures designed to take in high resolution images. 

HR-NAS introduces a light-weight Vision Transformer (ViT) \cite{dosovitskiy2020image} that also incorporates convolution. The ViT consists of a projector, an encoder, and a decoder. For the projector, instead of using a sinusoidal encoding, the authors project the input feature with a simple normalized 2D positional map. For the encoder, the input feature is transformed into a set of $n$ tokens where each is a lower-dimensional semantic embeddding with positional information. Then the tokens are fed as queries, keys, and values into the ViT.

The authors introduce a multi-branch search space inspired by HRNet \cite{wang2020deep}. This search space contains both multi-scale features and global contexts while maintaining high resolution representations throughout the network. The supernet in HR-NAS is a multi-branch network where each branch is a chain of search blocks operating at different resolutions. Each search block combines a MixConv and a Transformer\,\cite{vaswani2017attention}. The search is based on progressive shrinking that discards some convolutional channels and Transformer queries during training. 

\subsubsection{Randomly Labeled Data}
Random Label NAS\,(RLNAS)\,\cite{zhang2021neural} abandons ground truth labels and adopts random labels during searching. The authors of RLNAS decouple two convergence-based optimization steps. 

First, they train a supernet with random labels: 
\begin{equation}
    W^*=\argmin_{W}{\mathbb{E}_{\alpha\sim\Gamma(\mathcal{A})}}{\mathcal{L}(\alpha,W,R)},
\end{equation}
where $W,\,\alpha,\,\mathcal{A},\,R,\,\mathcal{L},\,\Gamma(\mathcal{A})$ denote the weights, architecture, architecture space, random labels, loss function, and a uniform distribution of $\alpha\in\mathcal{A}$, respectively.

Second, the authors run an evolution algorithm that searches the optimal architecture based on a convergence-based metric Convergence($\cdot$) as fitness:
\begin{equation}
    \alpha^*=\argmax_{\alpha\in\mathcal{A}}{\text{Convergence}(\alpha,W^*)}.
\end{equation}
The random labels follow a uniform distribution and the convergence-based metric is an angle-based model evaluation metric where it takes the angle between initial model weights and trained ones. 

\subsubsection{Out-of-Distribution Generalization}
NAS for image classification mostly works with clean datasets such as CIFAR10/100, ImageNet, etc. However, clean data is scarce in real world settings. In addition, data distribution shifts are often found in real world settings. For example, a dog breed identifier might be given a photo of a cat due to user error. Thus, there is a need for supernet optimization to be robust to Out-of-Distribution\,(OOD) cases. Out-of-Distribution refers to the case where a machine learning algorithm is fed data that is not from the distribution it was trained on. I.e., there is a distribution shift. There are mainly two kinds of OOD shifts: covariate shift and semantic shift. Covariate shift refers to a change in the input distribution. Semantic shift refers to a change in the output/label distribution. 

The authors of NAS-OOD\,\cite{bai2021ood} aim to develop a method that is robust to OOD data. They carry this out by jointly optimizing a conditional generator to synthesize OOD examples during training. To elaborate, let $\alpha,\,\omega,\,\theta_G$ denote the parameters for the architecture topology, the supernet, and the conditional genetator $G(\cdot,\cdot)$, respectively. The conditional generator $G(\cdot,\cdot)$ takes data $x$ and domain labels $\widetilde{k}$ as inputs. NAS-OOD is carried out by a minimax optimization. First, the conditional generator $G$ is learned to generate novel domain data by maximizing the validation loss, serving as an adversarial attack. Next, the validation loss is minimized by optimizing the architecture variables in $\alpha$ on the generated OOD images. The constrained minimax optimization problem can be formulated as:
\begin{equation}
    \begin{aligned}
        &\min_{\alpha}\max_{G}\mathcal{L}_{val}(\omega^*(\alpha),\alpha,G(x,\widetilde{k}))\\
        &\text{s.t. }\,\omega^*(\alpha)=\argmin_{\omega}\mathcal{L}_{train}(\omega,\alpha,x),
    \end{aligned}
\end{equation}
where $G(x,\widetilde{k})$ is the generated data from the original input data $x$ on the domain labels $\widetilde{k}$. The optimization is carried out by gradient ascent for $\theta_G$ and gradient descent for $\omega$ and $\alpha$. In addition, the authors apply gradient descent to $\theta_G$ with respect to an auxiliary loss in order to improve the generator's consistency and semantic information preservation when training. 

\subsection{Poor Rank Correlation Alleviation}
In this section, we will survey methods that aims to alleviate poor rank correlation. After supernet optimization, a subnet needs to be sampled and evaluated. This process repeats and returns a list of ranked architectures. Unfortunately, supernet-based NAS suffers from poor rank correlation. I.e., model accuracy predictions are poorly correlated to the standalone accuracy. \cite{bender2018understanding} attributes this to the co-adaptation among the weights. I.e., when the shared weights have highly correlated behavior. Rank correlation is measured by three metrics: Kendall Tau\,($\tau$)\,\cite{kendall1938new}, Spearman Rho\,($\rho$), and Pearson R\,(R). 

Poor rank correlation alleviation is usually accomplished by navigating or factorizing the search space. Navigation is carried out by selecting a path\,\cite{bender2018understanding,guo2020single,chu2021fairnas,chu2020mixpath} in the supernet while search space factorization is done by block-wise\,\cite{li2021bossnas} or hierarchical partitioning\,\cite{zhao2021few}. Disjoint from the aforementioned approaches, there is research that focuses on training consistency shift in the supernet\,\cite{peng2021pi}. 

\subsubsection{Path Selection}
Since architectures are sampled by taking subnets\,(paths) of the supernet, a natural approach is to smartly choose paths. I.e., this avenue of research is focused on navigating through the supernet search space. \cite{bender2018understanding} utilizes a linearly scheduled dropout strategy during training. After learning the parameters, subnets are sampled following a uniform distribution. Aiming to improve upon\,\cite{bender2018understanding}, Single-Path One-Shot NAS\,(SPOS)\,\cite{guo2020single} abstracts the supernet as a collection of choice modules. During training, SPOS randomly picks a subnet based on a uniform distribution and evaluates its validation accuracy. 

\begin{figure}[ht]
    \centering
    \hbox{\hspace{0.25cm}\includegraphics[width=8.25cm,keepaspectratio]{images/choice_module.PNG}}
    \caption{The choice module paradigm introduced by Single-Path One-Shot NAS. Each module is randomly chosen from a set of choices based on a uniform distribution.}
    \label{fig:choice_module}
\end{figure}

Under the choice module paradigm, FairNAS\,\cite{chu2021fairnas} raises the issue of biased supernets, i.e., parameters are not trained evenly. FairNAS aims to make sure the parameters of each choice module are updated the same number of times. For example, if there are $m$ choice modules for each layer, FairNAS takes a uniform sampling without replacement of the choice modules, i.e., the $m$ choice module indices are permuted. Then, a model is built and evaluated based on the sampled index permutation. The search is accomplished via a genetic algorithm, NSGA-II\,\cite{deb2002fast}.

The aforementioned methods fall under single path sampling, i.e., methods that sample only one architecture\,(subnet). An extension to this would be multi-path sampling, i.e., supernet optimization methods that sample multiple architectures. The authors of MixPath\,\cite{chu2020mixpath} find that a simple superposition of feature vectors sampled from multiple paths incurs very dynamic statistics causing training instability. They find that feature vectors from multiple paths are nearly multiples of those from a single-path. The solution to this is to scale the vectors down to the same magnitude creating stability. The authors accomplish said stability by proposing a novel Shadow Batch Normalization (SBN). MixPath is a two-stage pipeline: train supernet with SBN and searching for high performing models via NSGA-II. 


\subsubsection{Block-Wise Partitioning}
It has been found that the rank correlation can vary depending on the search space itself\,\cite{zhang2020does}. For example, on the NAS-Bench-201 search space\,\cite{dong2020bench}, the correlation can be as high as 0.7, whereas architectures sampled from DARTS-PTB\,\cite{liu2018darts} can perform worse than random search. 

In an attempt to alleviate the co-adaptation,\,\cite{zhang2020deeper} proposed to reduce the weight sharing density\,(the number of architectures sharing the weight of one operator) by downscaling the search space. However,\,\cite{zhang2020does} finds that the performance improvement is only significant when the downscale factor is 64 on NAS-Bench-201\,(only 244 different architectures). 

Instead of shrinking the entire search space, other works\,\cite{li2020block,moons2021distilling} partition the search space into blocks to improve the rank correlation. This allows the original search space size to remain intact. The current state-of-the-art\,(SOTA) NAS architecture on ImageNet for image classification is BossNet-T1+\,\cite{li2021bossnas}. The authors of Block-wisely Self-supervised Neural Architecture Search\,(BossNAS) achieve SOTA results alleviating the rank correlation issue by using block-wise weight-sharing. 

We give a brief primer on block-wise partitioning. Let $\mathcal{N}$ be the supernet. We break $\mathcal{N}$ into $N$ blocks by the supernet's depth and have:
\begin{equation}
\mathcal{N}=\mathcal{N}_N\circ \dots \circ \mathcal{N}_{i+1}\circ\mathcal{N}_i\circ\dots\circ\mathcal{N}_1,
\end{equation}
where $\mathcal{N}_{i+1}\circ\mathcal{N}_i$ denotes that the $(i+1)$-th block is connected to the $i$-th block in the supernet. Then each block is learned separately by optimizing:
\begin{equation}
\mathcal{W}_i^*=\min_{\mathcal{W}_i}{\mathcal{L}_{train}(\mathcal{W}_i,\mathcal{A}_i;\textbf{X},\textbf{Y})},\,\,i=1,2,\dots,N,
\end{equation}
where $\mathcal{L}_{train},\,\mathcal{W}_i,\:\mathcal{A}_i,\:\textbf{X},\:\textbf{Y}$ denote training loss, weights of the $i$-th block, search space of the $i$-th block, input data, and ground truth labels respectively.

What inspired the authors of BossNAS to use block-wise weight-sharing were other works such as DNA\,\cite{li2020block} and DONNA\,\cite{moons2021distilling} which achieve high correlation and high efficiency. However, the authors of BossNAS argue that those prior works have limited application on search spaces with disparate candidates, such as CNNs and Transformers\,\cite{li2021bossnas}. BossNAS trains each block separately before searching among all blocks in a linear combination of each block's validation loss:
\begin{equation}
    \begin{aligned}
        &\alpha^*=\{\alpha_i\}^*=\argmin_{\forall\{\alpha_i\}\subset\mathcal{A}}{\sum_{i=1}^{N}{\lambda_i\mathcal{L}_{val}}\left(W_i^*,\alpha_i;\textbf{X}_i,\textbf{Y}_i\right)}\\
        &\text{s.t. }\,W_i^*=\argmin_{W_i}{\mathcal{L}_{train}\left(W_i,A_i;\textbf{X}_i,\textbf{Y}_i\right)}
    \end{aligned}
\end{equation}
where $\alpha^*$ is the optimal architecture, $\{\alpha_i\}^*$ is the same optimal architecture as a sequence of blocks, $\lambda_i$ is the weight of the $i$-th block, $\mathcal{A}$ is the search space, $\textbf{X}_i$ and $\textbf{Y}_i$ are the training data and labels for the $i$-th block respectively. 

On the MBConv Search Space, BossNAS produces strong rank correlations of $\tau=0.65,\, \rho=0.78,$ and $R=0.85$. In contrast, DARTS\,\cite{liu2018darts}, an early supernet-based method shows abysmal correlation $\tau=0.08,\,\rho=0.14$ and $R=0.06$. 

\subsubsection{Hierarchical Partitioning}
The authors of few-shot NAS \cite{zhao2021few} adopt a hierarchical partitioning approach. They argue that one-shot NAS using only one supernet may not be able to model the search space due to its limited capacity and co-adaptation of operations \cite{bender2018understanding}. The hierarchical partitioning is done by splitting the connections in the supernet. In a supernet, each connection is a compound edge. I.e., all predefined candidate operations connect a pair of nodes (feature maps). In one-shot NAS, only one subnet is sampled from the supernet. For the case of few-shot, subnets are collected hierarchically when splitting compound edges. After sampling $k$ subnets, they are trained separately. 

\begin{figure}[ht]
    \centering
    \hbox{\hspace{0.25cm}\includegraphics[width=8.25cm,keepaspectratio]{images/fewshot.pdf}}
    \caption{Hierarchical partitioning introduced by few-shot NAS. (a) One-shot NAS trains the entire supernet with all compound edges intact. (b) Few-shot NAS carries out hierarchical partitioning by splitting compound edges. The split subnets are then trained separately. (c) In principle, one can enumerate every possible subnet which would be equivalent to doing brute force vanilla NAS. }
    \label{fig:fewshot}
\end{figure}

Naturally, there is a trade-off between evaluation accuracy and inference time. The hierarchical splitting could be repeated so that the search space is partitioned exhaustively\,(i.e. brute force search), but that would be computationally infeasible. The authors find that only using 7 subnets establishes new state-of-the-art results on ImageNet: 80.5\% top-1 accuracy at 600 MB FLOPS and 77.5\% top-1 accuracy at 238 MFLOPS. 

The co-adaptation is found to be alleviated when measuring the rank correlation. The authors compared the correlation between the model's predicted performance and the ground truth. The Kendall's Tau scores for 1 sub-supernet (one-shot NAS), 6 sub-supernets, 36 sub-supernets, 216 sub-supernets, 1296 sub-supernets (the entire search space) are 0.013, 0.12, 0.26, 0.63, and 1.0 respectively. Naturally, more accurate predictions are made when more of the search space is incorporated. 

\subsubsection{Supernet Training Consistency Shift}
The search space itself is not the only avenue for finding poor rank correlation causes. The authors of\,\cite{peng2021pi} empirically demonstrate that supernet training consistency shift hurts architecture ranking correlation. They break the consistency shift into two components: feature shift and parameter shift.

\textit{Feature shift} refers to network instability due to input image perturbation. Let $\textbf{X}_l$, $\textbf{Y}_l$, and $\textbf{W}_l$ denote the input, output, and weights of layer $l$ respectively. Network instability refers to the disturbance in the loss $\mathcal{L}$. By the chain rule for back propagation, we have: $\frac{\partial \mathcal{L}}{\partial \textbf{W}_l} = \frac{\partial \mathcal{L}}{\partial \textbf{Y}_l}\frac{\partial \textbf{Y}_l}{\partial \textbf{W}_l}=\frac{\partial \mathcal{L}}{\partial \textbf{Y}_l}\textbf{X}_l$. This shows that architecture ranking preservation is highly dependent on the inputs $\textbf{X}_l$. Since one-shot methods involve random path-sampling, the path that leads to layer $l$ varies, and thus the input $\textbf{X}_l$ varies. 

\textit{Parameter shift} refers to contradictory parameter updates for a given layer. During supernet training, a given layer $l$ is always present in different paths throughout all iterations. However, the weights might have a contradictory update when iterating. Looking at the gradient descent update step: $\textbf{W}_l^{t+1}\leftarrow\textbf{W}_l^t-\frac{\partial \mathcal{L}^t}{\partial \textbf{W}_l^t}$ there are two ways the rapidly varying $\textbf{W}_l$ will hurt rank correlation. One, the loss is dependent on both the weights $\textbf{W}_l$ and the descent $\textbf{W}_l-\frac{\partial \mathcal{L}}{\partial \textbf{W}_l}$. I.e., stable weights can ensure a correct loss descent and guarantee an accurate architecture ranking, while erratic parameters could not achieve a correct ranking. Two, since the input $\textbf{X}_l$ is generated by the network weights of the previous layers, varying parameters can also result in a feature shift, which further hurts architecture rank correlation. 

The authors reduce the supernet training consistency shift by $\Pi$-NAS: a nontrivial supernet-$\Pi$ model. They design a supernet-$\Pi$ model and a nontrivial mean teacher model\,\cite{tarvainen2017mean} to address feature shift and parameter shift respectively. 

\iffalse
\textit{Supernet}- $\Pi$ \textit{model}. To achieve a stable input distribution, the supernet-$\Pi$ model penalizes the inconsistency between the same input predictions through different sampled paths. By evaluating different augmentations of an input $x$, the authors define a cross-path consistency cost as follows:
\begin{equation}
    \mathcal{L}_{Con}=-\mathbb{E}_{X}{\left[\mathcal{D}(z_i,z_j')+\mathcal{D}(z_j,z_i')\right]}
\end{equation}
where $X$ and $\mathcal{D}$ denote a training set and a consistency metric, respectively. $\{i,j\}$ and $\{z_i,z_j,z_i',z_j'\}$ denote paths and representations, respectively. The feature shift is reduced by minimizing the cross-path consistency cost. 

\textit{Nontrivial mean teacher model.} Parameter shift is reduced by smoothing parameter updates. The authors were inspired by mean-teacher\,\cite{tarvainen2017mean} so they used an exponential moving average weights for the teacher model. They denote $\mathcal{W}_t$ as parameters of student mapping function $f$ at training step $t$. Then, weights of mean teacher model $f'$ can be defined as: 
\begin{equation}
    \mathcal{W}_t'=\lambda\mathcal{W}_{t-1}'+(1-\lambda)\mathcal{W}_t
\end{equation}
where $\lambda\in[0,1]$ is a smoothing coefficient hyperparameter. 
\fi

\subsection{Transferable NAS}\label{tran}
After supernet optimization, the sampled subnet requires post-processing: retraining, fine-tuning, etc. Training neural networks from scratch is computationally taxing, so there is interest in developing NAS methods that can yield architectures that can be instantly deployed for various tasks and hardware settings. 

\subsubsection{Specialized Networks for Specific Hardware Settings}
Once-For-All (OFA) networks is a type of supernet that yields deployable sub-networks that require no further training for diverse tasks and hardware platforms \cite{cai2019once}. The authors use \emph{progressive shrinking} (PS) to train the OFA network. The idea is to initially train a large network and then progressively shrink it for fine-tuning with respect to 4 dimensions: width (channels), depth (layers), kernel size, and resolution. After training the full model, the authors set the filter size to be elastic, i.e., choose the kernel size to be 3, 5, or 7 at each layer while the depth and width remain the maximum values. The depth and width are then sequentially set to be elastic similarly. The resolution size remains elastic throughout the whole training process. For elastic kernel size, all kernels of different sizes share the same center. The concern that arises when kernels share the same center is that they need to play multiple roles (independent kernel and part of a large kernel) which can degrade performance. To address this, the authors use separate kernel transformation matrices for different layers. For elastic depth, if one wants a $D$ layer unit from an $N$ layer unit (such that $D<N$), the authors keep the first $D$ layers and skip the last $N-D$ layers. For elastic width, the authors introduce a channel sorting operation to support partial widths. If full width is $M$, then the top $K$ ($K<M$) important channels are retained. Importance is defined as computing the L1 norm of a channel's weight (higher value meaning more important). The authors then use knowledge distillation \cite{hinton2015distilling} after training the largest network. 

After training the OFA network, the authors build neural-network twins to predict the latency and accuracy given a neural network architecture. The authors randomly sample 16K sub-networks with different architectures and image resolutions, then measure their accuracy on 10K validation images. The goal is to build an accuracy predictor fed with architectures as an input signal and accuracy as labels. The latency for a given architecture is predicted by utilizing a latency lookup table based on various target hardware platforms. When given a target hardware and latency constraint, the authors conduct evolutionary search based on the neural-network-twins to yield a specialized sub-network. 

Mobile setting performance is of great interest when it comes to OFA. The authors compared ImageNet performance of OFA with MobileNetV3\,\cite{howard2019searching} on 6 different mobile platforms: Samsung S7 Edge, Note8, Note10, Google Pixel1 \& Pixel2, and LG G8. OFA consistently outperforms MobileNetV3 with the same latency constraints by training only once. Similar results were also found for specialized hardware accelerators: NVIDIA 1080TI \& V100, Intel Xeon CPU, Jetson TX2, Xilinx ZU9EG FPGA, \& ZU3EG FPGA. 

\subsubsection{BigNAS}
BigNAS \cite{yu2020bignas} aims to train a single supernet that yields subnets whose sizes range from 200 to 1000 MFLOPS without extra training or post-processing. In other words, the weights can be directly deployed after training. The authors coin such supernet as a big \emph{single-stage model}. They select architectures using a simple \emph{coarse-to-fine} selection method to find the most accurate model under resource constraints such as FLOPs, memory footprint and/or runtime latency budgets on different devices. When training the single-stage model the authors use two techniques \cite{yu2019universally}: the sandwich rule and inplace distillation. The sandwich rule, in each training step, given a mini-batch of data, samples the smallest child model, the biggest (full) child model and $N$ randomly sampled child models. It then aggregates the gradients from all sampled child models before updating the weights of the single-stage model. Here, "smallest" child means smallest input resolution, thinnest width, shallowest depth, and smallest kernel size. The motivation is to improve all child models in the search space simultaneously, by pushing up both the performance lower bound (smallest model) and the performance upper bound (full model). 


