text:
\section{Introduction}

Please follow the steps outlined below when submitting your manuscript to
the IEEE Computer Society Press.  This style guide now has several
important modifications (for example, you are no longer warned against the
use of sticky tape to attach your artwork to the paper), so all authors
should read this new version.

\subsection{Language}

All manuscripts must be in English.

\subsection{Dual submission}

Please refer to the author guidelines on the CVPR 2020 web page for a
discussion of the policy on dual submissions.

\subsection{Paper length}
Papers, excluding the references section,
must be no longer than eight pages in length. The references section
will not be included in the page count, and there is no limit on the
length of the references section. For example, a paper of eight pages
with two pages of references would have a total length of 10 pages.
{\bf There will be no extra page charges for CVPR 2020.}

Overlength papers will simply not be reviewed.  This includes papers
where the margins and formatting are deemed to have been significantly
altered from those laid down by this style guide.  Note that this
\LaTeX\ guide already sets figure captions and references in a smaller font.
The reason such papers will not be reviewed is that there is no provision for
supervised revisions of manuscripts.  The reviewing process cannot determine
the suitability of the paper for presentation in eight pages if it is
reviewed in eleven.

\subsection{The ruler}
The \LaTeX\ style defines a printed ruler which should be present in the
version submitted for review.  The ruler is provided in order that
reviewers may comment on particular lines in the paper without
circumlocution.  If you are preparing a document using a non-\LaTeX\
document preparation system, please arrange for an equivalent ruler to
appear on the final output pages.  The presence or absence of the ruler
should not change the appearance of any other content on the page.  The
camera ready copy should not contain a ruler. (\LaTeX\ users may uncomment
the \verb'\cvprfinalcopy' command in the document preamble.)  Reviewers:
note that the ruler measurements do not align well with lines in the paper
--- this turns out to be very difficult to do well when the paper contains
many figures and equations, and, when done, looks ugly.  Just use fractional
references (e.g.\ this line is $095.5$), although in most cases one would
expect that the approximate location will be adequate.

\subsection{Mathematics}

Please number all of your sections and displayed equations.  It is
important for readers to be able to refer to any particular equation.  Just
because you didn't refer to it in the text doesn't mean some future reader
might not need to refer to it.  It is cumbersome to have to use
circumlocutions like ``the equation second from the top of page 3 column
1''.  (Note that the ruler will not be present in the final copy, so is not
an alternative to equation numbers).  All authors will benefit from reading
Mermin's description of how to write mathematics:
\url{http://www.pamitc.org/documents/mermin.pdf}.

\subsection{Blind review}

Many authors misunderstand the concept of anonymizing for blind
review.  Blind review does not mean that one must remove
citations to one's own work---in fact it is often impossible to
review a paper unless the previous citations are known and
available.

Blind review means that you do not use the words ``my'' or ``our''
when citing previous work.  That is all.  (But see below for
techreports.)

Saying ``this builds on the work of Lucy Smith [1]'' does not say
that you are Lucy Smith; it says that you are building on her
work.  If you are Smith and Jones, do not say ``as we show in
[7]'', say ``as Smith and Jones show in [7]'' and at the end of the
paper, include reference 7 as you would any other cited work.

An example of a bad paper just asking to be rejected:
\begin{quote}
\begin{center}
    An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of our
   previous paper [1], and show it to be inferior to all
   previously known methods.  Why the previous paper was
   accepted without this analysis is beyond me.

   [1] Removed for blind review
\end{quote}

An example of an acceptable paper:

\begin{quote}
\begin{center}
     An analysis of the frobnicatable foo filter.
\end{center}

   In this paper we present a performance analysis of the
   paper of Smith \etal [1], and show it to be inferior to
   all previously known methods.  Why the previous paper
   was accepted without this analysis is beyond me.

   [1] Smith, L and Jones, C. ``The frobnicatable foo
   filter, a fundamental contribution to human knowledge''.
   Nature 381(12), 1-213.
\end{quote}

If you are making a submission to another conference at the same time,
which covers similar or overlapping material, you may need to refer to that
submission in order to explain the differences, just as you would if you
had previously published related work.  In such cases, include the
anonymized parallel submission~\cite{Authors14} as additional material and
cite it as
\begin{quote}
[1] Authors. ``The frobnicatable foo filter'', F\&G 2014 Submission ID 324,
Supplied as additional material {\tt fg324.pdf}.
\end{quote}

Finally, you may feel you need to tell the reader that more details can be
found elsewhere, and refer them to a technical report.  For conference
submissions, the paper must stand on its own, and not {\em require} the
reviewer to go to a techreport for further details.  Thus, you may say in
the body of the paper ``further details may be found
in~\cite{Authors14b}''.  Then submit the techreport as additional material.
Again, you may not assume the reviewers will read this material.

Sometimes your paper is about a problem which you tested using a tool which
is widely known to be restricted to a single institution.  For example,
let's say it's 1969, you have solved a key problem on the Apollo lander,
and you believe that the CVPR70 audience would like to hear about your
solution.  The work is a development of your celebrated 1968 paper entitled
``Zero-g frobnication: How being the only people in the world with access to
the Apollo lander source code makes us a wow at parties'', by Zeus \etal.

You can handle this paper like any other.  Don't write ``We show how to
improve our previous work [Anonymous, 1968].  This time we tested the
algorithm on a lunar lander [name of lander removed for blind review]''.
That would be silly, and would immediately identify the authors. Instead
write the following:
\begin{quotation}
\noindent
   We describe a system for zero-g frobnication.  This
   system is new because it handles the following cases:
   A, B.  Previous systems [Zeus et al. 1968] didn't
   handle case B properly.  Ours handles it by including
   a foo term in the bar integral.

   ...

   The proposed system was integrated with the Apollo
   lunar lander, and went all the way to the moon, don't
   you know.  It displayed the following behaviours
   which show how well we solved cases A and B: ...
\end{quotation}
As you can see, the above text follows standard scientific convention,
reads better than the first version, and does not explicitly name you as
the authors.  A reviewer might think it likely that the new paper was
written by Zeus \etal, but cannot make any decision based on that guess.
He or she would have to be sure that no other authors could have been
contracted to solve problem B.
\medskip

\noindent
FAQ\medskip\\
{\bf Q:} Are acknowledgements OK?\\
{\bf A:} No.  Leave them for the final copy.\medskip\\
{\bf Q:} How do I cite my results reported in open challenges?
{\bf A:} To conform with the double blind review policy, you can report results of other challenge participants together with your results in your paper. For your results, however, you should not identify yourself and should not mention your participation in the challenge. Instead present your results referring to the method proposed in your paper and draw conclusions based on the experimental comparison to other results.\medskip\\

\begin{figure}[t]
\begin{center}
\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}

\end{center}
   \caption{Example of caption.  It is set in Roman so that mathematics
   (always set in Roman: $B \sin A = A \sin B$) may be included without an
   ugly clash.}
\label{fig:long}
\label{fig:onecol}
\end{figure}

\subsection{Miscellaneous}

\noindent
Compare the following:\\
\begin{tabular}{ll}
 \verb'$conf_a$' &  $conf_a$ \\
 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
\end{tabular}\\
See The \TeX book, p165.

The space after \eg, meaning ``for example'', should not be a
sentence-ending space. So \eg is correct, {\em e.g.} is not.  The provided
\verb'\eg' macro takes care of this.

When citing a multi-author paper, you may save space by using ``et alia'',
shortened to ``\etal'' (not ``{\em et.\ al.}'' as ``{\em et}'' is a complete word.)
However, use it only when there are three or more authors.  Thus, the
following is correct: ``
   Frobnication has been trendy lately.
   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''

This is incorrect: ``... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
because reference~\cite{Alpher03} has just two authors.  If you use the
\verb'\etal' macro provided, then you need not worry about double periods
when used at the end of a sentence as in Alpher \etal.

For this citation style, keep multiple citations in numerical (not
chronological) order, so prefer \cite{Alpher03,Alpher02,Authors14} to
\cite{Alpher02,Alpher03,Authors14}.

\begin{figure*}
\begin{center}
\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
\end{center}
   \caption{Example of a short caption, which should be centered.}
\label{fig:short}
\end{figure*}

\section{Formatting your paper}

All text must be in a two-column format. The total allowable width of the
text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
cm) high. Columns are to be $3\frac14$ inches (8.25 cm) wide, with a
$\frac{5}{16}$ inch (0.8 cm) space between them. The main title (on the
first page) should begin 1.0 inch (2.54 cm) from the top edge of the
page. The second and following pages should begin 1.0 inch (2.54 cm) from
the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
cm) from the bottom edge of the page for $8.5 \times 11$-inch paper; for A4
paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the
page.

\subsection{Margins and page numbering}

All printed material, including text, illustrations, and charts, must be kept
within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm)
high.
Page numbers should be in footer with page numbers, centered and .75
inches from the bottom of the page and make it start at the correct page
number rather than the 4321 in the example.  To do this fine the line (around
line 23)
\begin{verbatim}
\setcounter{page}{4321}
\end{verbatim}
where the number 4321 is your assigned starting page.

Make sure the first page is numbered by commenting out the first page being
empty on line 46
\begin{verbatim}
\end{verbatim}

\subsection{Type-style and fonts}

Wherever Times is specified, Times Roman may also be used. If neither is
available on your word processor, please use the font closest in
appearance to Times to which you have access.

MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
the first page. The title should be in Times 14-point, boldface type.
Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
adverbs; do not capitalize articles, coordinate conjunctions, or
prepositions (unless the title begins with such a word). Leave two blank
lines after the title.

AUTHOR NAME(s) and AFFILIATION(s) are to be centered beneath the title
and printed in Times 12-point, non-boldface type. This information is to
be followed by two blank lines.

The ABSTRACT and MAIN TEXT are to be in a two-column format.

MAIN TEXT. Type main text in 10-point Times, single-spaced. Do NOT use
double-spacing. All paragraphs should be indented 1 pica (approx. 1/6
inch or 0.422 cm). Make sure your text is fully justified---that is,
flush left and flush right. Please do not place any additional blank
lines between paragraphs.

Figure and table captions should be 9-point Roman type as in
Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centred.

\noindent Callouts should be 9-point Helvetica, non-boldface type.
Initially capitalize only the first word of section titles and first-,
second-, and third-order headings.

FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
should be Times 12-point boldface, initially capitalized, flush left,
with one blank line before, and one blank line after.

SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
should be Times 11-point boldface, initially capitalized, flush left,
with one blank line before, and one after. If you require a third-order
heading (we discourage it), use 10-point Times, boldface, initially
capitalized, flush left, preceded by one blank line, followed by a period
and your text on the same line.

\subsection{Footnotes}

Please use footnotes\footnote {This is what a footnote looks like.  It
often distracts the reader from the main flow of the argument.} sparingly.
Indeed, try to avoid footnotes altogether and include necessary peripheral
observations in
the text (within parentheses, if you prefer, as in this sentence).  If you
wish to use a footnote, place it at the bottom of the column on the page on
which it is referenced. Use Times 8-point type, single-spaced.

\subsection{References}

List and number all bibliographical references in 9-point Times,
single-spaced, at the end of your paper. When referenced in the text,
enclose the citation number in square brackets, for
example~\cite{Authors14}.  Where appropriate, include the name(s) of
editors of referenced books.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|}
\hline
Method & Frobnability \\
\hline\hline
Theirs & Frumpy \\
Yours & Frobbly \\
Ours & Makes one's heart Frob\\
\hline
\end{tabular}
\end{center}
\caption{Results.   Ours is better.}
\end{table}

\subsection{Illustrations, graphs, and photographs}

All graphics should be centered.  Please ensure that any point you wish to
make is resolvable in a printed copy of the paper.  Resize fonts in figures
to match the font in the body text, and choose line widths which render
effectively in print.  Many readers (and reviewers), even of an electronic
copy, will choose to print your paper in order to read it.  You cannot
insist that they do otherwise, and therefore must not assume that they can
zoom in to see tiny details on a graphic.

When placing figures in \LaTeX, it's almost always best to use
\verb+\includegraphics+, and to specify the  figure width as a multiple of
the line width as in the example below
{\small\begin{verbatim}
   \usepackage[dvips]{graphicx} ...
   \includegraphics[width=0.8\linewidth]
                   {myfile.eps}
\end{verbatim}
}

\subsection{Color}

Please refer to the author guidelines on the CVPR 2020 web page for a discussion
of the use of color in your document.

\section{Final copy}

You must include your signed IEEE copyright release form when you submit
your finished paper. We MUST have this form before your paper can be
published in the proceedings.

Please direct any questions to the production editor in charge of these
proceedings at the IEEE Computer Society Press:
\url{https://www.computer.org/about/contact}.

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}
\label{sec:introduction}

Deep learning has revolutionized computer vision by learning features directly from data. As a result deep neural networks have achieved state-of-the-art results on many difficult tasks such as image classification \cite{imagenet_cvpr09}, object detection \cite{lin2014microsoft}, object tracking \cite{muller2018trackingnet}, semantic segmentation \cite{cordts2016cityscapes}, depth estimation \cite{geiger2013vision} and activity understanding \cite{caba2015activitynet}, to name just a few examples. While there was a big emphasis on feature engineering before deep learning, the focus has now shifted to architecture engineering. In particular many novel architectures have been proposed, such as LeCun \cite{lecun1998gradient}, AlexNet \cite{krizhevsky2012imagenet}, VGG \cite{simonyan2014very}, GoogLeNet \cite{GoogLeNet2015}, ResNet \cite{he2016deep}, DenseNet \cite{huang2017densely}, ResNeXt \cite{xie2017aggregated} and SENet \cite{hu2018squeeze}. Results on each of the above mentioned tasks keep improving every year by innovations in architecture design. In essence, the community has shifted from feature engineering to architecture engineering.

\begin{figure}[!tp]
    \centering
    \begin{tabular}{cc}
    \includegraphics[trim=30mm 38mm 100mm 10mm, clip, width=0.9\columnwidth]{figures/intro.pdf}
    \end{tabular}
    \caption{\textbf{Comparison of search-evaluation Kendall $\tau$ coefficients.} We show Kendall $\tau$ correlations for architecture rankings between the search and the evaluation phase of DARTS and SGAS. Architectures are obtained from $10$ independent search runs.
    }
    \label{fig:intro_fig}
\end{figure}

In recent years, many efforts have been made to reduce the manual intervention required to obtain better models for a particular task. As a matter of fact, a new area of research, commonly referred to as meta-learning, has emerged in order to tackle such problems. The idea of meta-learning is to leverage prior experience in order to quickly find good algorithm configurations, network architectures and any required parameters for a new learning task. Examples of recent meta-learning approaches include automatic hyper-parameter search \cite{franceschi2018bilevel}, data-augmentation \cite{cubuk2018autoaugment}, finding novel optimizers \cite{andrychowicz2016learning} and architecture search \cite{zoph2016neural}. In particular, architecture search has sparked a lot of interest in the community.
In this task, the search space is huge and manual search is prohibitive.

Early work by Zoph \etal \cite{zoph2016neural}, based on Reinforcement Learning, has shown very promising results. However, its high computational cost has prevented widespread adoption. Recently, differentiable architecture search (DARTS) \cite{liu2018darts} has been proposed as an alternative which makes architecture search differentiable and much more efficient. This has opened up a path towards computationally feasible architecture search. However, despite their success, current approaches still have a lot of limitations. During the search phase, network architectures are usually constructed from basic building blocks and evaluated on a validation set. Due to computational cost, the size of considered architectures is limited. In the evaluation phase, the best building blocks are used to construct larger architectures and they are evaluated on the test set.  As a result there is a large discrepancy between the validation accuracy during search and the test accuracy during evaluation. In this work, we propose a novel greedy architecture search algorithm, SGAS, which addresses this discrepancy and searches very efficiently.

\mysection{Contributions}
Our contributions can be summarized as the following: \textbf{(1)} We propose SGAS, a greedy approach for neural architecture search with high correlation between the validation accuracy during the search phase and the final evaluation accuracy. \textbf{(2)} Our method discovers top-performing architectures with much less search cost than previous state-of-the-art methods such as DARTS. \textbf{(3)} Our proposed method is able to search architectures for both CNNs and GCNs across various datasets and tasks.

\section{Related Work}
\label{sec:related}
In the past, considerable success was achieved with hand-crafted architectures. One of the earliest successful architectures was LeNet \cite{lecun1998gradient}, a very simple convolutional neural network for optical character recognition. Other prominent networks include AlexNet \cite{krizhevsky2012imagenet}, VGG \cite{simonyan2014very} and GoogLeNet \cite{GoogLeNet2015} which revolutionized computer vision by outperforming all previous approaches in the ImageNet \cite{imagenet_cvpr09} challenge by a large margin. ResNet \cite{he2016deep} and DenseNet \cite{huang2017densely} were further milestones in architecture design. They showed the importance of residual and dense connections for designing very deep networks, an insight that influences modern architecture design to this day.
Until recently, architecture innovations were a result of human insight and experimentation. The first successful attempts for architecture search were using reinforcement learning \cite{zoph2016neural} and evolutionary algorithms \cite{real2019regularized}. These works were extended with NASNet \cite{zoph2018learning} where a new cell-based search space and regularization technique were proposed. Another extension, ENAS \cite{pham2018efficient}, represents the entire search space as a single directed acyclic graph. A controller discovers architectures by searching for subgraphs that maximize the expected reward on the validation set. This setup allows for parameter sharing between child models making search very efficient. Further, PNAS \cite{liu2018progressive} introduced a sequential model-based optimization (SMBO) strategy in order to search for structures of increasing complexity. PNAS needs to evaluate $5$ times less models and reduces the computational cost by a factor of $8$ compared to NASNet. Yet, PNAS still requires thousands of GPU hours.
One shot approaches \cite{brock2017smash,bender2018understanding,cai2018proxylessnas} further reduce the search time by training a single over-parameterized network with inherited/shared weights.
In order to search in a continuous domain \cite{saxena2016convolutional,ahmed2017connectivity,shin2018differentiable,veniat2018learning}, DARTS \cite{liu2018darts} proposes a continuous relaxation of the architecture representation,
making architecture search differentiable and hence much more efficient. As a result, DARTS is able to find good convolutional architectures at a fraction of the computational cost making NAS broadly accessible. Owed to the large success of DARTS, several extensions have been proposed recently.
SNAS \cite{xie2018snas} optimizes parameters of a joint distribution for the search space in a cell. The authors propose a search gradient which optimizes the same objective as RL-based NAS, but leads to more efficient structural decisions.
P-DARTS \cite{chen2019progressive} attempts to overcome the depth gap issue between search and evaluation. This is accomplished by increasing the depth of searched architectures gradually during the training procedure.
PC-DARTS \cite{xu2019pc} leverages the redundancy in network space and only samples a subset of channels in super-net during search to reduce computation.

\section{Methodology}
\label{sec:methodology}

\begin{figure*}[t]
    \vspace{-10pt}
    \centering
    \includegraphics[trim=0mm 5mm 0mm 5mm, clip, width=\textwidth]{figures/pipeline.pdf}
    \caption{\textbf{Illustration of Sequential Greedy Architecture Search.} At each greedy decision epoch, an edge $(i^{\dagger}, j^{\dagger})$ is selected based on the selection criterion. A greedy decision will be made for the edge $(i^{\dagger}, j^{\dagger})$ by replacing $\bar{o}^{(i^\dagger,j^\dagger)}$ with $o^{(i^\dagger,j^\dagger)} = \mathrm{argmax}_{o \in \mathcal{O}} \enskip \alpha^{(i^\dagger,j^\dagger)}_o$. The corresponding architectural parameter $\alpha^{(i^{\dagger}, j^{\dagger})}$ will be removed from the bi-level optimization. Operations which were not chosen in a mixture operation will be pruned. At the end of the search phase, a stand-alone architecture without weight sharing will be obtained.}
\label{fig:pipeline}
\end{figure*}

\subsection{Preliminary - DARTS} \label{subsec:preliminary}
By reducing the search problem to searching for the best cell structure, cell-based NAS methods \cite{zoph2018learning,liu2018progressive,real2019regularized} are able to learn scalable and transferable architectures. The networks are composed of layers with identical cell structure but different weights. A cell is usually represented as a directed acyclic graph (DAG) with $N$ nodes including two input nodes, several intermediate nodes and a single output node. Each node is a latent representation denoted as $x^{(i)}$, where $i$ is its topological order in the DAG. Each directed edge $(i, j)$ in the DAG is associated with an operation $o^{(i, j)}$ that transfers the information from node $x^{(i)}$ to node $x^{(j)}$. In \textit{Differentiable Architecture Search} (DARTS) \cite{liu2018darts} and its variants \cite{xie2018snas,chen2019progressive,xu2019pc,he2020MiLeNAS}, the optimal architecture is derived from a discrete search space by relaxing the selection of operations to a continuous optimization problem. During the search phase, the operation of each edge is parameterized by architectural parameters $\alpha^{(i, j)}$ as a softmax mixture over all the possible operations within the operation space $\mathcal{O}$, \ie
$
	\bar{o}^{(i,j)}(x^{(i)}) = \sum_{o \in \mathcal{O}} \frac{\exp(\alpha_o^{(i,j)})}{\sum_{o' \in \mathcal{O}} \exp(\alpha_{o'}^{(i,j)})} o(x^{(i)})
$.
The input nodes are represented by the outputs from the previous two cells. Each intermediate node aggregates information flows from all of its predecessors,
$
	x^{(j)} = \sum_{i<j} \bar{o}^{(i, j)}(x^{(i)})
$.
The output node is defined as a concatenation of a fixed number of its predecessors. The learning procedure of architectural parameters involves a bi-level optimization problem:
\begin{align}
    	\min_\mathcal{A} \quad & \mathcal{L}_{val}(\mathcal{W}^*(\mathcal{A}), \mathcal{A}) \label{eq:outer} \\
    	\text{s.t.} \quad &\mathcal{W}^*(\mathcal{A}) = \mathrm{argmin}_\mathcal{W} \enskip \mathcal{L}_{train}(\mathcal{W}, \mathcal{A}) \label{eq:inner}
\end{align}
$\mathcal{L}_{train}$ and $\mathcal{L}_{val}$ denote the training and validation loss respectively. Owing to the continuous relaxation, the search is realized by optimizing a supernet. $\mathcal{W}$ is the set of weights of the supernet and $\mathcal{A}$ is the set of the architectural parameters. DARTS \cite{liu2018darts} proposed to solve this bi-level problem by a first/second order approximation. At the end of the search, the final architecture is derived by selecting the operation with highest weight for every mixture operation,
$
	o^{(i,j)} =
	\mathrm{argmax}_{o \in \mathcal{O}} \enskip \alpha^{(i,j)}_o
$.

\begin{algorithm*}[t]
\DontPrintSemicolon
Create architectural parameters $\mathcal{A} = \{\alpha^{(i, j)}\}$ and supernet weights $\mathcal{W}$\;
Create a mixed operation $\bar{o}^{(i,j)}$ parameterized by $\alpha^{(i,j)}$ for each edge $(i,j)$\;
\While{not terminated}{
	1. Update undetermined architecture parameters $\mathcal{A}$ by descending
	$\nabla_{\mathcal{A}} \mathcal{L}_{val}(\mathcal{W}, \mathcal{A})$\;
	2. Update weights $\mathcal{W}$ by descending $\nabla_{\mathcal{W}} \mathcal{L}_{train}(\mathcal{W}, \mathcal{A})$\;
	\quad (since the weights of unchosen operations are pruned, only the remaining weights need to be updated)\;
	3. If a decision epoch, select an edge $(i^\dagger,j^\dagger)$ based on the greedy \textit{Selection Criterion}
	\\\quad Determine the operation by replacing $\bar{o}^{(i^\dagger,j^\dagger)}$ with $o^{(i^\dagger,j^\dagger)} = \mathrm{argmax}_{o \in \mathcal{O}} \enskip \alpha^{(i^\dagger,j^\dagger)}_o$
	\\\quad Prune unchosen weights from $\mathcal{W}$, Remove $\alpha^{(i^\dagger, j^\dagger)}$ from $\mathcal{A}$\;
}
Derive the final architecture based on chosen operations
\caption{{\sc SGAS} -- Sequential Greedy Architecture Search}
\label{algo:pseudocode}
\end{algorithm*}

\subsection{Search-Evaluation Correlation}
A popular pipeline of existing NAS algorithms \cite{zoph2018learning,liu2018darts} includes two stages: a search phase and an evaluation phase. In order to reduce computational overhead, previous works \cite{zoph2018learning,liu2018darts} first search over a pre-defined search space with a lightweight proxy model on a small proxy dataset. After the best architecture cell/encoding is obtained, the final architecture is built and trained from scratch on the target dataset. This requires that the true performance during evaluation can be inferred during the search phase. However, this assumption usually does not hold due to the discrepancy in dataset, hyper-parameters and network architectures between the search and evaluation phases. The best ranking derived from the search phase does not imply the actual ranking in the final evaluation. In practice, the correlation between the performances of derived architectures during the search and evaluation phases is usually low. In this paper, we refer to this issue as \textbf{degenerate search-evaluation correlation}. Recent work by Sciuto \etal \cite{sciuto2019evaluating} also analyzes this issue and suggests that the Kendall $\tau$ metric \cite{kendall1938new} could be used to evaluate the search phase. They show that the widely used \emph{weight sharing} technique actually decreases the correlation. The Kendall $\tau$ metric \cite{kendall1938new} is a common measurement of the correlation between two rankings. The Kendall $\tau$ coefficient can be computed as
$
	\tau = \frac{N_{c} - N_{d}}{\frac{1}{2}n(n-1)}
$, where $N_{c}$ and $N_{d}$ are the number of concordant pairs and the number of discordant pairs respectively. It is a number in the range from $-1$ to $1$ where $-1$ corresponds to a perfect negative correlation and $1$ to a perfect positive correlation. If the Kendall $\tau$ coefficient is $0$, the rankings are completely independent. An ideal NAS method should have a high \textbf{search-evaluation Kendall $\tau$ coefficient}. We take DARTS \cite{liu2018darts} as an example and show its Kendall $\tau$ in Figure\xspace \ref{fig:intro_fig}. It is calculated between the rankings during search phase and evaluation phase. The rankings are determined according to the validation accuracy and the final evaluation accuracy after 10 different runs on the CIFAR-10 dataset. The Kendall $\tau$ coefficients for DARTS are only $0.16$ and $-0.29$ for the $1$st-order and $2$nd-order versions respectively. Therefore, it is impossible to make reliable predictions regarding the final test accuracy based on the search phase.

\subsection{Sequential Greedy Architecture Search}
In order to alleviate the \textbf{degenerate search-evaluation correlation} problem, the core aspects are to reduce $\textbf{(1)}$ the discrepancy between the search and evaluation phases and $\textbf{(2)}$ the negative effect of weight sharing. We propose to solve the bi-level optimization (Equation\xspace \ref{eq:outer}, \ref{eq:inner}) in a sequential greedy fashion to reduce the model discrepancy and the weight sharing progressively. As mentioned in Section\xspace \ref{subsec:preliminary}, DARTS-based methods \cite{liu2018darts,chen2019progressive,xu2019pc} solve the relaxed problem fully and obtain all the selected operations at the end. Instead of solving the complete problem directly, we divide it into sub-problems and solve them sequentially with a greedy algorithm. The sub-problems are defined based on the directed edges in the DAG. We pick the operation for edges greedily in a sequential manner and solve the remaining sub-problem iteratively. The iterative procedure is shown in Algorithm\xspace \ref{algo:pseudocode}. At each decision epoch, we choose one edge $(i^{\dagger}, j^{\dagger})$ according to a pre-defined \textit{selection criterion}. A greedy optimal choice is made for the selected edge by replacing the corresponding mixture operation $\bar{o}^{(i^\dagger,j^\dagger)}$ with $o^{(i^\dagger,j^\dagger)} = \mathrm{argmax}_{o \in \mathcal{O}} \enskip \alpha^{(i^\dagger,j^\dagger)}_o$. The architectural parameters $\alpha^{(i^\dagger,j^\dagger)}$ and the weights of the remaining paths within the mixture operations are no longer needed; we prune and exclude them from the latter optimization. As a side benefit, the efficiency improves as parameters in $\mathcal{A}$ and $\mathcal{W}$ are pruned gradually in the optimization loop. The search procedure of the remaining $\mathcal{A}$ and $\mathcal{W}$ forms a new sub-problem which will be solved iteratively. At the end of the search phase, a \textit{stand-alone network without weight sharing is obtained}, as illustrated in Figure\xspace \ref{fig:pipeline}. Therefore, the model discrepancy is minimized and the validation accuracy during the search phase reflects the final evaluation accuracy much better. To maintain the optimality, the design of the \textit{selection criterion} is crucial. We consider three aspects of edges which are the \textit{edge importance}, the \textit{selection certainty} and the \textit{selection stability}.

\mysection{Edge Importance} Similar to DARTS \cite{liu2018darts}, a \textit{zero} operation is included in the search space to indicate a lack of connection. Edges that are important should have a low weight in the \textit{zero} operation. Thus, the edge importance is defined as the summation of weights over non-zero operations:
\begin{align}
S_{EI}^{(i,j)} = \sum_{o \in \mathcal{O}, o \neq zero} \frac{\exp(\alpha_{o}^{(i, j)})}{\sum_{o' \in \mathcal{O}}\exp(\alpha_{o'}^{(i, j)})}
\label{eq:ei}
\end{align}
\mysection{Selection Certainty} Entropy is a common measurement of uncertainty of a distribution. The normalized softmax weights of non-zero operations can be regarded as a distribution, $p_{o}^{(i,j)} = \frac{\exp(\alpha_{o}^{(i, j)})}{S_{EI}^{(i,j)}\sum_{o' \in \mathcal{O}}\exp(\alpha_{o'}^{(i, j)})}, o \in \mathcal{O}, o \neq zero$. We define the \textit{selection certainty} as the \textit{complement} of the normalized entropy of the operation distribution:
\begin{align}
S_{SC}^{(i,j)} = 1 -  \frac{-\sum_{o \in \mathcal{O}, o \neq zero} p_{o}^{(i,j)} \log(p_{o}^{(i,j)})}{\log(|\mathcal{O}|-1)}
\label{eq:sc}
\end{align}
\mysection{Selection Stability} In order to incorporate the history information, we measure the movement of the operation distribution. Kullback–Leibler divergence and histogram intersection \cite{swain1991color} are two popular methods to detect changes in distribution. For simplicity, we choose the latter one. The average selection stability at step $T$ with a history window size $K$ is computed as follows:
\begin{align}
S_{SS}^{(i,j)} = \frac{1}{K} \sum_{t=T-K}^{T-1} \sum_{o_{t} \in \mathcal{O} o_{t}, \neq zero} \min (p_{o_{t}}^{(i,j)}, p_{o_{T}}^{(i,j)})
\label{eq:ss}
\end{align}
In our experiments, we consider the following two criteria:

\mysection{Criterion 1} An edge $(i^\dagger,j^\dagger)$ with a high \textit{edge importance} $S_{EI}^{(i,j)}$ and a high \textit{selection certainty} $S_{SC}^{(i,j)}$ will be selected. We normalize $S_{EI}^{(i,j)}$ and $S_{SC}^{(i,j)}$, compute the final score and pick the edge with the highest score:
\begin{align}
S_{1}^{(i,j)} = \text{normalize}(S_{EI}^{(i,j)})*\text{normalize}(S_{SC}^{(i,j)})
\label{eq:c1}
\end{align}

\mysection{Criterion 2} In addition to \textit{Criterion 1}, we also consider that the selected edge $(i^\dagger,j^\dagger)$ should have a high \textit{selection stability}. The final score is defined as follows:
\begin{align}
S_{2}^{(i,j)} = S_{1}^{(i,j)}*\text{normalize}(S_{SS}^{(i,j)})
\label{eq:c2}
\end{align}
where $normalize(\cdot)$ denotes a standard Min-Max scaling normalization. For a fair comparison with existing works \cite{zoph2016neural,real2019regularized,liu2018darts}, two incoming edges are preserved for every intermediate node in the DAG. Once a node has two determined incoming edges, its other incoming edges will be pruned. We refer to our method as \textbf{Sequential Greedy Architecture Search} (SGAS). Figure\xspace \ref{fig:intro_fig} shows that SGAS with Criterion $1$ and $2$ improves the Kendall $\tau$ correlation coefficients to $0.56$ and $0.42$ respectively. As expected from the much higher search-evaluation correlation SGAS outperform DARTS in terms of average accuracy significantly.

\section{Experiments}
\label{sec:experiments}
We use our SGAS to automatically find architectures for both CNNs and GCNs.
The CNN architectures discovered by SGAS outperform the state-of-the-art (SOTA) in image classification on CIFAR-10 \cite{Krizhevsky2009LearningML} and ImageNet \cite{imagenet_cvpr09}.
Similarly, the discovered GCN architectures outperform the state-of-the-art methods for point cloud classification on ModelNet \cite{20143Dmodelnet}
and node classification in biological graphs using the PPI \cite{Zitnik2017PredictingMFppi} dataset.

\subsection{Searching CNN architectures with SGAS}
\vspace{0pt}
\subsubsection{Architecture Search on CIFAR-10}
 As is common practice, we first search for normal cells and reduction cells with a small network for image classification on CIFAR-$10$. CIFAR-$10$ is a small popular dataset containing $50K$ training images and $10K$ testing images. Then, a larger network is constructed by making necessary changes in channel size and stacking the searched cells multiple times. The larger network is retrained on CIFAR-$10$ to compare its performance with other state-of-the-art methods. Finally, we show the transferability of our SGAS by stacking even more cells and evaluating on ImageNet. We show that SGAS consistently achieves the top performance.

\mysection{Search Space} We keep our search space the same as DARTS, which has $8$ candidate operations: \textit{skip-connect}, \textit{max-pool-3$\times$3}, \textit{avg-pool-3$\times$3}, \textit{sep-conv-3$\times$3}, \textit{sep-conv-5$\times$5}, \textit{dil-conv-3$\times$3}, \textit{dil-conv-5$\times$5}, \textit{zero}.
During the search phase, we stack $6$ normal cells and $2$ reduction cells to form a network.
Two reduction cells are inserted at a network depth of $1/3$ and $2/3$ respectively.
The stride of each convolution in normal cells is $1$, so the spatial size of an input feature map does not change. In reduction cells, convolutions with stride $2$ are used to reduce the spatial resolution of feature maps.
There are $7$ nodes with $4$ intermediate nodes and $14$ edges in each cell during search. The first and second input nodes of the cell are set equal to the outputs of the two previous cells respectively.
The output node of a cell is the depth-wise concatenation of all the intermediate nodes.

\mysection{Training Settings}
We keep the training setting the same as in DARTS \cite{liu2018darts}. A small network consisting of $6$ normal cells and $2$ reduction cells with an initial channel size $16$ is trained on CIFAR-$10$.
We perform architecture search for $50$ epochs with a batch size of $64$.
SGD is used to optimize the model weights $\mathcal{W}$ with an initial learning rate $0.025$, momentum $0.9$ and weight decay $3\times10^{-4}$. For architecture parameters $\mathcal{A}$, the Adam optimizer with an initial learning rate $3 \times 10^{-4}$, momentum $(0.5, 0.999)$ and weight decay $10^{-3}$ is used.
Instead of training the entire super-net throughout the search phase, SGAS makes decisions sequentially in a greedy fashion.
After warming up for $9$ epochs, SGAS begins to select one operation for one selected edge every $5$ epochs using \textit{Criterion 1} or \textit{Criterion 2} as the selection criterion. For \textit{Criterion 2}, we set the history window size $K$ to 4.
The batch size is increased by $8$ after each greedy decision, which further boosts the searching efficiency of SGAS. We provide a thorough discussion and ablation study on the choices of hyper-parameters in the \textbf{supplement material}\xspace. The search takes only $0.25$ day ($6$ hours) on a single NVIDIA GTX 1080Ti.

\begin{table*}
\vspace{-5pt}
\centering
\resizebox{0.58\linewidth}{!}{%
\begin{tabular}{lccccc}
\toprule
\textbf{{Architecture}} & \textbf{Test Err.} & \textbf{Params} & \textbf{Search Cost} & \textbf{{Search}} \\
&                            \textbf{ (\%)} & \textbf{(M)} & \textbf{(GPU-days)} & \textbf{{Method}}\\
\midrule
DenseNet-BC \cite{huang2017densely} & 3.46 & 25.6 & - & manual \\
\midrule
NASNet-A \cite{zoph2018learning} & 2.65 & 3.3 & 1800 & RL \\
AmoebaNet-A \cite{real2019regularized} & 3.34$\pm$0.06 & 3.2 & 3150 & evolution \\
AmoebaNet-B \cite{real2019regularized} & 2.55$\pm$0.05 & 2.8 & 3150 & evolution \\
Hier-Evolution \cite{liu2017hierarchical} & 3.75$\pm$0.12 & 15.7 & 300 & evolution \\
PNAS \cite{liu2018progressive} & 3.41$\pm$0.09 & 3.2 & 225 & SMBO \\
ENAS \cite{pham2018efficient} & 2.89 & 4.6 & 0.5 & RL \\
NAONet-WS \cite{luo2018neural} & 3.53 & 3.1 & 0.4 & NAO \\
\midrule
DARTS ($1^{\text{st}}$ order) \cite{liu2018darts} & 3.00$\pm$0.14 & 3.3 & 0.4 & gradient \\
DARTS ($2^{\text{nd}}$ order) \cite{liu2018darts} & 2.76$\pm$0.09 & 3.3 & 1 & gradient \\
SNAS (mild) \cite{xie2018snas} & 2.98 & 2.9 & 1.5 & gradient\\
ProxylessNAS \cite{cai2018proxylessnas} & 2.08 & - & 4 & gradient \\
P-DARTS \cite{chen2019progressive} & 2.5 & 3.4 & 0.3 & gradient \\
BayesNAS \cite{zhou2019bayesnas} & 2.81$\pm$0.04 & 3.4 & 0.2 & gradient \\
PC-DARTS \cite{xu2019pc} & 2.57$\pm$0.07 & 3.6 & 0.1 & gradient \\
\midrule
SGAS (Cri.1 avg.) & 2.66$\pm$$0.24^{*}$ & 3.7 & 0.25 & gradient \\
SGAS (Cri.1 best) & 2.39 & 3.8 & 0.25 & gradient \\
SGAS (Cri.2 avg.) & 2.67$\pm$$0.21^{*}$ & 3.9 & 0.25 & gradient \\
SGAS (Cri.2 best) & 2.44 & 4.1 & 0.25 & gradient \\
\bottomrule
\end{tabular}
}
\vspace{3pt}
\caption{\textbf{Performance comparison with state-of-the-art image classifiers on CIFAR-10.} We report the average and best performance of SGAS (Cri.1) and SGAS (Cri.2). \textit{Criterion 1} and \textit{Criterion 2} are used in the search respectively. *Note that mean and standard derivation are computed across 10 independently searched architectures.}
\vspace{0pt}
\label{tbl:compare_cifar10}
\end{table*}

\vspace{0pt}
\subsubsection{Architecture Evaluation on CIFAR-10}
We run $10$ \textit{independent searches} to get $10$ architectures with \textit{Criterion 1} or \textit{Criterion 2}, as shown in Figure\xspace \ref{fig:intro_fig}. To highlight the stability of the search method, we evaluate the discovered architectures on CIFAR-$10$ and report the mean and standard deviation of the test accuracy across those $10$ models and the performance of the best model in Table\xspace \ref{tbl:compare_cifar10}. It is important to mention that other related works in Table\xspace \ref{tbl:compare_cifar10} only report the mean and standard deviation for their \textit{best architecture} with different runs on evaluation.

\mysection{Training Settings}
We train a large network of $20$ cells with a initial channel size $36$. The SGD optimizer is used during $600$ epochs with a batch size of $96$. The other hyper-parameters remain the same as the search phase. Cutout with length $16$, auxiliary towers with weight $0.4$ and path dropout with probability $0.3$ are used as in DARTS \cite{liu2018darts}.

\mysection{Evaluation Results and Analysis}
We compare our results with other methods in Table\xspace \ref{tbl:compare_cifar10} and report the average and best performance for both \textit{Criterion 1} and \textit{Criterion 2}. We outperform our baseline DARTS by a significant margin with test errors of $2.39\%$ and $2.44\%$ respectively while only using $0.25$ day ($6$ hours) on a single NVIDIA GTX 1080Ti.

\vspace{0pt}
\subsubsection{Architecture Evaluation on ImageNet}
The architecture evaluation on ImageNet uses the cell architectures that we obtained after searching on CIFAR-10.

\mysection{Training Settings}
We choose the $3$ best performing cell architectures on CIFAR-10 for each \textit{Criterion} and train them on ImageNet. For this evaluation, we build a large network with $14$ cells and $48$ initial channels and train for $250$ epochs with a batch size of $1024$. The SGD optimizer with an initial learning rate of $0.5$, a momentum of $0.9$ and a weight decay of $3\times10^{-5}$ is used. We run these experiments on $8$ Nvidia Tesla V100 GPUs for three days.

\mysection{Evaluation Results and Analysis}
In Table\xspace \ref{tbl:compare_imagenet} we compare our models with SOTA hand-crafted architectures (manual) and models obtained through other search methods. We apply the mobile setting for ImageNet, which has an image size of $224\times224$ and restricts the number of multi-add operations to $600M$. Our best performing models SGAS (Cri.1 best) and SGAS (Cri.2 best) outperform all the other methods with top-1 errors $24.2\%$ and $24.1\%$ respectively while using only a search cost of $0.25$ GPU day on one NVIDIA GTX 1080Ti. SGAS (Cri.2) outperforms SGAS (Cri.1) showing the effectiveness of integrating \textit{selection stability} into the selection criterion. The best performing cells of SGAS (Cri.2 best) are illustrated in Figure\xspace \ref{fig:visualizations_cnn}.
\begin{table*}
\vspace{-10pt}
\centering
\resizebox{0.70\linewidth}{!}{%
\begin{tabular}{lcccccc}
\toprule
\textbf{{Architecture}} & \multicolumn{2}{c}{\textbf{Test Err. (\%)}} & \textbf{Params} & $\times+$ & \textbf{Search Cost} & \textbf{{Search}} \\
&                            \textbf{top-1} & \textbf{top-5} & \textbf{(M)} & \textbf{(M)} & \textbf{(GPU-days)} & \textbf{Method}\\
\midrule
Inception-v1 \cite{GoogLeNet2015} & 30.2 & 10.1 & 6.6 & 1448 & - & manual \\
MobileNet \cite{howard2017mobilenets}& 29.4 & 10.5 & 4.2 & 569 & - & manual \\
ShuffleNet 2x (v1) \cite{zhang2018shufflenet} & 26.4 & 10.2 & $\sim$5 & 524 & - & manual \\
ShuffleNet 2x (v2) \cite{ma2018shufflenet} & 25.1 & - & $\sim$5 & 591 & - & manual \\
\midrule
NASNet-A \cite{zoph2018learning} & 26 & 8.4 & 5.3 & 564 & 1800 & RL \\
NASNet-B \cite{zoph2018learning} & 27.2 & 8.7 & 5.3 & 488 & 1800 & RL \\
NASNet-C \cite{zoph2018learning} & 27.5 & 9 & 4.9 & 558 & 1800 & RL \\
AmoebaNet-A \cite{real2019regularized} & 25.5 & 8 & 5.1 & 555 & 3150 & evolution \\
AmoebaNet-B \cite{real2019regularized} & 26 & 8.5 & 5.3 & 555 & 3150 & evolution \\
AmoebaNet-C \cite{real2019regularized} & 24.3 & 7.6 & 6.4 & 570 & 3150 & evolution \\
FairNAS-A \cite{chu2019fairnas} & 24.7 & 7.6 & 4.6 & 388 & 12 & evolution \\
PNAS \cite{liu2018progressive} & 25.8 & 8.1 & 5.1 & 588 & 225 & SMBO \\
MnasNet-92 \cite{tan2019mnasnet} & 25.2 & 8 & 4.4 & 388 & - & RL \\
\midrule
DARTS ($2^{\text{nd}}$ order) \cite{liu2018darts} & 26.7 & 8.7 & 4.7 & 574 & 4.0 & gradient \\
SNAS (mild) \cite{xie2018snas} & 27.3 & 9.2 & 4.3 & 522 & 1.5 & gradient \\
ProxylessNAS \cite{cai2018proxylessnas} & 24.9 & 7.5 & 7.1 & 465 & 8.3 & gradient \\
P-DARTS \cite{chen2019progressive} & 24.4 & 7.4 & 4.9 & 557 & 0.3 & gradient \\
BayesNAS \cite{zhou2019bayesnas} & 26.5 & 8.9 & 3.9 & - & 0.2 & gradient \\
PC-DARTS \cite{xu2019pc} & 25.1 & 7.8 & 5.3 & 586 & 0.1 & gradient \\
\midrule
SGAS (Cri.1 avg.) & 24.41$\pm$0.16 & 7.29$\pm$0.09 & 5.3 & 579 & 0.25 & gradient \\
SGAS (Cri.1 best) & 24.2 & 7.2 & 5.3 & 585 & 0.25 & gradient \\
SGAS (Cri.2 avg.) & 24.38$\pm$0.22 & 7.39$\pm$0.07 & 5.4 & 597 & 0.25 & gradient \\
SGAS (Cri.2 best) & \textbf{24.1} & 7.3 & 5.4 & 598 & 0.25 & gradient \\
\bottomrule
\end{tabular}
}
\vspace{3pt}
\caption{\textbf{Comparison with state-of-the-art classifiers on ImageNet.} We transfer the top $3$ performing architectures on CIFAR-10 to ImageNet in the mobile setting. $\times+$ denote multiply-add operations.
The average and best performance of SGAS are reported.}
\vspace{0pt}
\label{tbl:compare_imagenet}
\end{table*}

\subsection{Searching GCN architectures with SGAS}
Recently, GCNs have achieved impressive performance on point cloud segmentation \cite{Li2019DeepGCNs}, biological graph node classification \cite{Li2019DeepGCNsMG} and video recognition \cite{xu2019gtad} by training DeepGCNs \cite{Li2019DeepGCNs,Li2019DeepGCNsMG}.
However, this hand-crafted architecture design requires adequate effort by an human expert.
The main component of DeepGCNs is the GCN backbone. We explore an automatic way to design the GCN backbone using SGAS.
Our backbone network is formed by stacking the graph convolutional cell discovered by SGAS. Our GCN cell consists of 6 nodes. We use fixed $1 \times 1$ convolutions in the first two nodes, and set the input to them equal to the output from the previous two layers.
Our experiments on GCNs have two stages. First, we apply SGAS to search for the graph convolutional cell using a small dataset and obtain $10$ architectures from $10$ runs. Then, $10$ larger networks are constructed by stacking each discovered cell multiple times.
The larger networks are trained on the same dataset or a larger one to evaluate their performance. We report the best and average performance of these $10$ architectures.
We show the effectiveness of SGAS in GCN architecture search by comparisons with SOTA hand-crafted methods and Random Search.

\vspace{0pt}
\subsubsection{Architecture Search on ModelNet10}
ModelNet \cite{20143Dmodelnet} is a dataset for 3D object classification with two variants, ModelNet10 and ModelNet40 containing objects from $10$ and $40$ classes respectively. We conduct GCN architecture search on ModelNet10 and then evaluate the final performance on ModelNet40.

\mysection{Search Space}
Our graph convolutional cell has $10$ candidate operations:
\textit{conv-1$\times$1}, \textit{MRConv} \cite{Li2019DeepGCNs}, \textit{EdgeConv} \cite{dgcnn}, \textit{GAT} \cite{velivckovic2017graph}, \textit{SemiGCN} \cite{Kipf2016SemiSupervisedCW}, \textit{GIN} \cite{Xu2018HowPAGIN}, \textit{SAGE} \cite{hamilton2017inductive}, \textit{RelSAGE}, \textit{skip-connect}, and \textit{zero} operation.
Please refer to our \textbf{supplement material}\xspace for more details of these GCN operators.
We use \textit{k nearest neighbor} in the first operation of each cell to construct edges (we use $k = 9$ by default unless it is specified). These edges are then shared in the following operations inside the cell.
Dilated graph convolutions with the same linearly increasing dilation rate schedule as proposed in DeepGCNs \cite{Li2019DeepGCNs} are applied to the cells.

\mysection{Training Settings}
We sample $1024$ points from the 3D models in ModelNet10.
We use $2$ cells with $32$ initial channels and search the architectures for $50$ epochs with batch size $28$.
SGD is used to optimize the model weights with initial learning rate $0.005$, momentum $0.9$ and weight decay $3\times10^{-4}$. The Adam optimizer with the same parameters as in the search for CNNs is used to optimize architecture parameters.
After warming up for $9$ epochs, SGAS begins to select one operation for a selected edge every $7$ epochs.
We experimented with both selection criteria, \textit{Criterion 1} and \textit{Criterion 2}. We use a history window of $4$ for \textit{Cri.2}. The batch size increases by $4$ after each decision. The search takes around $0.19$ GPU day on one NVIDIA GTX 1080Ti.

\begin{table}
\small
\setlength{\tabcolsep}{6pt}
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{lccc}
\toprule
\textbf{Architecture} & \textbf{OA} & \textbf{Params} & \textbf{Search Cost} \\
&                           \textbf{(\%)} & \textbf{(M)} & \textbf{(GPU-days)}\\
\midrule
3DmFV-Net \cite{ben20183dmfv} & 91.6 & 45.77 & manual \\
SpecGCN \cite{Wang_2018_ECCV} & 91.5 & 2.05 & manual \\
PointNet++ \cite{qi2017pointnet++} & 90.7 & 1.48 & manual \\
PCNN \cite{Atzmon:2018:PCN:3197517.3201301} & 92.3 & 8.2 & manual \\
PointCNN \cite{Li2018PointCNNCO} & 92.2 & 0.6 & manual \\
DGCNN \cite{dgcnn} & 92.2 & 1.84 & manual \\
KPConv \cite{thomas2019KPConv} & 92.9 & 14.3 & manual \\
\midrule
Random Search & 92.65$\pm$0.33 & 8.77 & random \\
SGAS (Cri.1 avg.) & 92.69$\pm$0.20 & 8.78 & 0.19 \\
SGAS (Cri.1 best) & 92.87 & 8.63 & 0.19 \\
SGAS (Cri.2 avg.) & 92.93$\pm$0.19 & 8.87 & 0.19 \\
SGAS (Cri.2 best) & \textbf{93.23} & 8.49 & 0.19 \\
SGAS (Cri.2 small best) & 93.07 & 3.86 & 0.19 \\

\bottomrule
\end{tabular}
}
\vspace{3pt}
\caption{\textbf{Comparison with state-of-the-art architectures for 3D object classification on ModelNet40.} $10$ architectures are derived for both SGAS and Random Search within the same search space.
}
\vspace{0pt}
\label{tbl:modelnet40}
\end{table}

\vspace{0pt}
\subsubsection{Architecture Evaluation on ModelNet40}
After searching for $10$ architectures on ModelNet10, we form a large backbone network for each and train them on ModelNet40. The performance of 3D point cloud classification is evaluated with the overall accuracy (OA). We also apply Random Search to the same search space to obtain $10$ architectures as our random search baseline.

\mysection{Training Settings}
We stack the searched cell $9$ times with channel size $128$.
We also form small networks by stacking the cell $3$ times with the same channel size.
We use $k=20$ for all the large networks and $k=9$ for the small ones.
Adam is used to optimize the weights with initial learning rate $0.001$ and weight decay $1\times10^{-4}$.
We sample $1024$ points as input.
Our architectures are all trained for $400$ epochs with batch size of $32$. We report the mean and standard deviation of the accuracy on the test dataset of the $10$ discovered architectures; we also report the accuracy of the best performing model of the big and the small networks.

\mysection{Evaluation Results and Analysis}
We compare the performance of our discovered architectures with SOTA hand-crafted methods and architectures obtained by Random Search for 3D point clouds classification on ModelNet40.
Table\xspace \ref{tbl:modelnet40} shows that SGAS (Cri.2 best), the best architecture discovered by our SGAS with \textit{Criterion 2}, outperforms all the other models.
The smaller network SGAS (Cri.2 small best) discovered by SGAS with \textit{Criterion 2} also outperforms all the hand-crafted architectures.
Owing to a well-designed search space, Random Search is a strong baseline. The performance of SGAS surpasses the hand-crafted architectures and Random Search, demonstrating the effectiveness of SGAS for GCN architecture search.
The best architecture for this task can be found in Figure\xspace \ref{fig:visualizations_gcn} (a).

 \begin{figure*}[h]
 \vspace{-30pt}
 \centering
 \begin{tabular}{@{}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{}}

 		\includegraphics[trim=10mm 13mm 0mm 13mm, clip, width=\columnwidth]{figures/visualizations/hist_imagenet_normal.pdf} &
 		\includegraphics[trim=0mm 13mm 10mm 13mm, clip, height=0.35\columnwidth]{figures/visualizations/hist_imagenet_reduction.pdf} \\

 		\small (a) Normal cell &
 		\small (b) Reduction cell \\

 \end{tabular}
 \caption{\textbf{Best cell architecture on Imagenet with SGAS \textit{Crit. 2}}}
 \label{fig:visualizations_cnn}
 \vspace{-10pt}
 \end{figure*}

 \begin{figure*}
 \centering
 \begin{tabular}{@{}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{}}
 		\includegraphics[trim=0mm 5mm 0mm 10mm, clip, width=\columnwidth]{figures/visualizations/hist_modelnet_normal.pdf} &
 		\includegraphics[trim=0mm 10mm 0mm 10mm, clip, width=\columnwidth]{figures/visualizations/nohis_ppi_normal.pdf}\\

		\small (a) Normal cell of the best model with SGAS \textit{Crit. 2} on ModelNet40 &
		\small (b) Normal cell of the best model with SGAS \textit{Crit. 1} on PPI\\

 \end{tabular}
 \caption{\textbf{Best cell architectures on ModelNet40 and PPI}}
 \vspace{0pt}
 \label{fig:visualizations_gcn}
 \end{figure*}

\vspace{0pt}
\subsubsection{Architecture Search on PPI}
PPI is a popular biological graph dataset in the data mining domain. We search for GCN architectures on the PPI dataset for the task of node classification.

\mysection{Training Settings}
We use $1$ cell with $32$ channels. We train and search the architectures for $50$ epochs with a batch size of $6$ on PPI.
We do not increase the batch size after making decisions since PPI is small and only contains $20$ batches. The other parameters are the same as when searching on ModelNet10.
The search takes around $0.003$ day ($4$ minutes) on a Nvidia Tesla V100 GPU (16GB).

\vspace{0pt}
\subsubsection{Architecture Evaluation on PPI}
We evaluate architectures on the PPI test set. We report the mean, standard derivation and the best accuracy and compare them with the SOTA methods and Random Search.
We also conduct an ablation study on number of cells and channel size which we include in the \textbf{supplement material}\xspace.

\mysection{Training Settings}
We stack the discovered cell $5$ times with channel size 512.
Adam is used to optimize the model weights with initial learning rate $0.002$.
We use a cosine annealing to schedule the learning rate.
Our architectures are trained for $2000$ epochs with batch size of $1$ as suggested in DeepGCNs \cite{Li2019DeepGCNsMG}.
We find the best model on the validation dataset and obtain the micro-F1 score on the test dataset.

\begin{table}
\small
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{lccc}
\toprule
\textbf{Architecture} & \textbf{micro-F1} & \textbf{Params} & \textbf{Search Cost} \\
&                           \textbf{(\%)} & \textbf{(M)} & \textbf{(GPU-days)}\\
\midrule
GraphSAGE (LSTM) \cite{hamilton2017inductive} & 61.2 & 0.26 & manual\\
GeniePath \cite{liu2019geniepath} & 97.9 & 1.81 & manual \\
GAT \cite{velivckovic2017graph} & 97.3$\pm$0.2 & 3.64 & manual \\
DenseMRGCN-14 \cite{Li2019DeepGCNsMG} & 99.43 & 53.42 & manual \\
ResMRGCN-28 \cite{Li2019DeepGCNsMG} & 99.41 & 14.76 & manual \\
\midrule
Random Search & 99.36$\pm$0.04 & 23.70 & random \\
SGAS (Cri.1 avg.) & 99.38$\pm$0.17 & 25.01 & 0.003 \\
SGAS (Cri.1 best) & \textbf{99.46} & 23.18 & 0.003 \\
SGAS (Cri.2 avg.) & 99.40$\pm$0.09 & 25.93 & 0.003 \\
SGAS (Cri.2 best) & \textbf{99.46} & 29.73 & 0.003 \\
SGAS (small) & 98.89 & 0.40 & 0.003 \\
\bottomrule
\end{tabular}
}
\vspace{3pt}
\caption{\textbf{Comparison with state-of-the-art architectures for node classification on PPI.} SGAS (small) is the small network stacking the cell searched by SGAS (Cri.1).}
\label{tab:ppi_comparsion_sota}
\vspace{0pt}
\end{table}

\mysection{Evaluation Results and Analysis}
We compare the average and best performance of SGAS to other state-of-the-arts methods and Random Search on node classification on the PPI dataset.
Table\xspace \ref{tab:ppi_comparsion_sota} shows the best architecture discovered by our SGAS outperforms the state-of-the-art DenseMRGCN-14 \cite{Li2019DeepGCNsMG} by $\sim$0.03\% with $\sim$30.24 M less parameters.
The average performance of SGAS also surpasses the Random Search baseline consistently.
In addition, SGAS (Cri.2 avg.) outperforms SGAS (Cri.1 avg.) in terms of both mean and standard deviation. This indicates that \textit{Criterion 2} provides more stable results. We visualize the architecture with the best performance in Figure\xspace \ref{fig:visualizations_gcn} (b).

\section{Conclusion}
\label{sec:conclusion}
In this work, we propose the Sequential Greedy Architectural Search (SGAS) algorithm to design architectures automatically for CNNs and GCNs. The bi-level optimization problem in NAS is solved in a greedy fashion using heuristic criteria which take the edge importance, the selection certainty and the selection stability into consideration. Such an approach alleviates the effect of the \textbf{degenerate search-evaluation correlation} problem and reflects the true ranking of architectures. As a result, architectures discovered by SGAS achieve state-of-the-art performance on CIFAR-10, ImageNet, ModelNet and PPI datasets.

\mysection{Acknowledgments} This work was supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) through VCC funding. The authors  thank the KAUST IBEX team for helping to optimize the training workloads on ImageNet.

{\small
\bibliographystyle{ieee_fullname}

redpajama_set_name: RedPajamaArXiv


New wheelchair accessible vans from top brands like Toyota, Honda, Ford, Mercedes, Chrysler and Dodge vans featuring rear- or side-entry and lift conversions. We provide a 134-point inspection, guaranteed customer satisfaction, nationwide delivery and no hidden fees. We offer mobility financing, delivery and service nationwide.
New wheelchair van conversions come in a variety of configurations, side-entry and rear-entry access. Choose from make, model and manufacturer.
Nationwide front door delivery service, 134-point certified inspections and No DOC FEES.
Showing 2 of 2 vehicles that match your search.


text:
Home Learn Articles The Land Before the National Park Service Began
Civil War | Article
The Land Before the National Park Service Began
100 Years of the National Park Service
By Timothy B. Smith
Brices Cross Roads National Battlefield Site, Baldwin, Miss. Mike Talplacido
Created separately and with different purpose from the vast nature preserves of the West, America's battlefield parks took a long, often circuitous route to full integration into the National Park System.
Stones River National Battlefield, Murfreesboro, Tenn. Buddy Secor
Today, most Americans with an interest in the Civil War, or other eras of military history, view major battlefields and the National Park Service (NPS) as synonymous. And well they should, because NPS does indeed directly oversee America's most revered battlegrounds. It is natural to formulate a hierarchy of battlefields and their importance, ranging upward from locally preserved city and county parks to those listed as national historic landmarks or patrolled by rangers in green and gray. While an argument could be made that some state, or even local, parks are actually worthy of federal recognition, it is commonly recognized that the cream of the battlefield crop — in terms of both historic significance and modern management — resides in the National Park Service.
Less known to most Americans is that the current, magnificent affiliation between the battlefields and the National Park Service was not always the case. In fact, about half of the major battlefields in the National Park Service today were well-established before the agency took possession of them, and the five Civil War sites that are arguably the most significant in the system actually predate the creation of the National Park Service itself. As a result, NPS was actually the lucky recipient of decades' old, well-established parks, rather than the battlefields benefiting from originating within an elite agency with the clout of the National Park Service that we recognize today.
The first federal presence at America's battlefields came in 1862, in the form of national cemeteries, where those who fell in Civil War combat were buried. After the war, legislation expanded eligible internments beyond immediate battle dead and formalized the process, leading to the establishment of numerous other commemorative burial sites, including the one at Chalmette, La., site of the 1814 Battle of New Orleans — where four veterans from the War of 1812 were ultimately laid to rest among soldiers from later wars. In the 1870s, portions of battlefields from the Indian Wars, including Little Bighorn, were set aside as cemeteries under this model.
The government became involved in battlefield preservation in the modern sense in 1890, when Congress established the Chickamauga & Chattanooga National Military Park. At the time, there was no National Park Service; in fact, there were only a handful of other federal parks, including Yellowstone, Yosemite and Sequoia. Four other battlefield parks also emerged in the 1890s: Antietam, Shiloh, Gettysburg and Vicksburg. Governed by the War Department, these five battlefields offered a very militaristic atmosphere for veterans and military officers studying the lessons of war. It was a "golden age" of preservation, allowing the veterans themselves to preserve these monumental battlefields, something that would never be possible again on so large a scale. As a result, these five are the best-preserved and marked sites visitors can see today.
Unfortunately, a slowdown in battlefield park establishment occurred over the next two decades, as the veterans passed and attention shifted elsewhere. But the original five parks nevertheless remained and prospered under the auspices of the War Department, even as a groundswell of public support led to the establishment of the nature-dominant National Park Service in 1916. Yet, once the battlefield preservation process restarted in the mid 1920s, new battlefield parks — including the first entities associated with the Revolutionary War and the War of 1812 — continued to be placed under the War Department, rather than the new National Park Service. Through the early 1930s, America thus gained significant federal Civil War battlefield parks at Fort Pulaski, Petersburg, Fredericksburg and Spotsylvania, Stones River and Fort Donelson — plus smaller entities at battlefields such as Tupelo, Brices Cross Roads, Kennesaw Mountain and Fort Stevens. Units commemorating other conflicts sprang up at Guilford Courthouse, Fort McHenry, Moores Creek, Cowpens, Fort Necessity, King's Mountain and Morristown.
Despite numerous calls for it over the agency's early years, the transfer of battlefield parks into the National Park Service did not occur until 1933. NPS officials Stephen Mather and Horace Albright had long argued for the change, explaining that while the War Department was doing a good job at the time, the National Park Service was the government agency that had expertise in park management and interpretation. These arguments fell on willing ears, as government officials in the 1920s and 1930s realized a changing clientele was now visiting these battlefields, one that was no longer made up primarily of veterans or military officers. A more mobile civilian American public was now visiting these historic sites, and these individuals needed a different kind of experience than that provided by the War Department.
Kennesaw Mountain National Battlefield Park, Kennesaw Mountain Brian Keeley Photography
There was also, however, a more selfish reason why Mather and Albright pushed for the transfer. The National Park Service was, in the 1920s and early 1930s, nowhere near the highly recognizable governmental agency we think of today. In fact, it was a fairly insignificant and minor agency struggling for money and limelight. While the National Park Service did oversee some pre-colonial historic sites established mainly under the authority of the Antiquities Act, which itself predated the National Park Service by 10 years, the NPS was primarily a nature-centric agency. Mather and Albright realized the devotion and reverence Americans had for the great battlefields of the Civil War and knew that, if the National Park Service could obtain possession of the battlefields, it would not only push the bureau into the historic side of preservation and interpretation, but also raise the stature of the entire agency.
Fort Pulaski National Monument, Savannah, Ga David Davis
President Franklin D. Roosevelt was receptive to the idea, especially after a Sunday ride out into Virginia, when he found himself seated with National Park Service director Horace Albright, who brought up the idea. That Department of the Interior officials were supportive was one thing, but War Department leaders were also pushing the idea, and that sealed the action. Military officials realized recreational governance of past battlefields was not exactly in line with their critical duties, meaning the parks became further and further buried in the bureaucracy of the War Department, as no one in the military seemed to want them. A consensus reached, Roosevelt issued the necessary executive order during the summer of 1933; with the stroke of his pen, 10 major battlefields and numerous other smaller sites resided within the National Park Service.
It was a steep learning curve for the Park Service to interpret and educate about historic events, but the agency swiftly set up a historic section to oversee the battlefields. NPS soon had the sites revamped (with the aid of numerous New Deal dollars and workers through programs like the Civilian Conservation Corps) and ready for the new breed of battlefield visitors. And over the ensuing decades, many more major battlefields — Saratoga, Richmond, Fort Sumter, Harpers Ferry, Lexington and Concord, Pea Ridge and Wilson's Creek, among others — were also added to the "cannonball circuit." After a major downturn in preservation activity in the fiscally conservative 1970s and 1980s, more new federal parks have begun to appear as well, such as those at Glorietta Pass and Cedar Creek.
As the principle steward of America's battlefield and other significant historic sites, the Park Service has become a leading force in historic preservation and archaeology, as well as promoting the principles of heritage tourism through initiatives like national heritage areas. Although the deep association between historic batlefields and the National Park Service does not extend as far back as most people believe, their marriage created one of the world's outstanding partnerships of historic preservation that all Americans can look upon with pride.
Timothy B. Smith
Dr. Timothy B. Smith, a former NPS ranger at Shiloh, teaches history at the University of Tennessee at Martin. He is the author of numerous books including Corinth 1862: Siege, Battle, Occupation and Shiloh: Conquer or Perish, both published by the University Press of Kansas.
Fort Taylor, Key West: Imprisonment in Paradise
The Man Behind "Merry Old Santa Claus"
Camp Letterman at Gettysburg
Civil War Battlefield Preservation
Centennial Reflections: Vicksburg National Military Park
Centennial Reflections: Gettysburg National Military Park
Centennial Reflections: Saratoga National Historical Park
Centennial Reflections: Cowpens National Battlefield Park
Centennial Reflections: Little Bighorn Battlefield National Monument

redpajama_set_name: RedPajamaCommonCrawl


Kasei Valles is one of the largest outflow channel systems on Mars that was created by several gigantic flood events over 3 billion years ago.
The asteroid Vesta is the third largest body in the asteroid belt (with dimensions of 280 x 270 x 230 kilometer) and one of a few relicts from early times of the solar system.
This complex outflow-channel system on Mars is up to 40 km wide in places. The northern Dao Vallis is about 2400 m deep, the southern Niger Vallis about 1400 m.
Ulyxis Rupes is located in the southern highlands of our neighbour planet Mars. There are many ice deposits and dune formations in this area.
This animation shows a fly-over of the central region of the vast canyon system Valles Marineris, a significant geological structure on Mars.
This animation shows a small part of the massive equatorial ridge on Iapetus. The ridge encircles the Saturnian moon along the equator.
This large outflow channel is situated north of the Martian dichotomy boundary between the southern highland and the northern lowland.
Nicholson Crater is located northwest of a region called Medusae Fossae on Mars. In the centre of this crater an oblong massif rises around 3.5 km above the floor.
Hebes Chasma is an almost 8 km deep basin on Mars, stretching 315 km in an east-west direction and 125 km from north to south.


One worker is reportedly in critical condition.
The 24 employees were treated at five different art hospitals, ABC News reported. One is in critical condition while another 30 were treated at the scene.
After an initial investigation by police, it was determined that "an automated machine accidentally punctured a 9-ounce bear repellent can, releasing concentrated Capsaicn," Robbinsville Township communications and public information officer John Nalbone told ABC.


When you have a pool you would be able to enjoy your recreation in a unique where you can have swimming at your own available time you wish. Due to this it is essential for you to make sure that you have a pool at your homestead so that you would be able to enjoy. Since this is not an easy task it requires qualified and experienced personnel who would be able to develop and design the pool as you wish. It is imperative for you to make sure that you factor having the best pool builder who has verse knowledge in development and constructions of Gold Medal Pools. It is essential for you to make sure that you incorporate the following tips which are vital in selecting the best pool builder.
First, you need to put into consideration the recommendations. It is imperative to ensure that you are requesting your friends to provides you with the best leads and they will ensure that you are getting the best by linking you with a reputable pool builder. Also, you should look at the experience of the pool builder. In order to have a beautiful and a good design for your pool you should ensure that you are hiring an experienced home builder in your construction project. When you have the services of the pool builder that has been into business for so long you will be able to have the best home.
Also you should make sure that you factor on quality. It is essential that you understand that the pool you want will be your permanent pool for you and your family and it is essential to maintain high levels of quality. For this reason, consider the services of the pool builder that will ensure total quality when building and you can be certain by visiting some of his or her completed projects. It is crucial to do your own research. You can consider the internet information since you will get a lot from there and you will be able to get the best pool builder.
Also, it is essential to incorporate the licensed dallas pool builders. You should make sure that you are able to get the pool builder that is registered with agencies and has a valid work permit to carry out pool building projects. You should put into consideration the pool builder that is insured. During the provision of services accident can occur and cause severe injuries to contractor and subcontractors and if the hire pool builder is insured the insurance company will be liable. You should make sure that you are able to locate the best pool builder by considering the above tips.


text:
#region MIT
//
// Gorgon.
// Copyright (C) 2021 Michael Winsor
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//
// Created: February 12, 2021 1:49:23 PM
//
#endregion

#region SharpDX
// Copyright (c) 2010-2014 SharpDX - Alexandre Mutel
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
// -----------------------------------------------------------------------------
// Original code from SlimMath project. http://code.google.com/p/slimmath/
// Greetings to SlimDX Group. Original code published with the following license:
// -----------------------------------------------------------------------------

#endregion

using System;
using System.ComponentModel;
using System.Globalization;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Gorgon.Core;
using Gorgon.Math;
using Gorgon.Properties;

namespace Gorgon.Renderers.Data
{
    ///
    /// Represents a bounding sphere in three dimensional space.
    ///
    [StructLayout(LayoutKind.Sequential, Pack = 4)]
    public readonly struct GorgonBoundingSphere
        : IGorgonEquatableByRef<GorgonBoundingSphere>
    {
        #region Variables.
        ///
        /// A default, empty, bounding sphere.
        ///
        public static readonly GorgonBoundingSphere Empty = default;

        ///
        /// The center of the sphere in three dimensional space.
        ///
        public readonly Vector3 Center;

        ///
        /// The radius of the sphere.
        ///
        public readonly float Radius;
        #endregion

        #region Properties.
        ///
        /// Property to return whether this bounding sphere is empty or not.
        ///
        public bool IsEmpty => Radius.EqualsEpsilon(0);
        #endregion

        #region Methods.
        ///
        /// Constructs a <see cref="GorgonBoundingSphere" /> that fully contains the given points.
        ///
        /// <param name="points">The points that will be contained by the sphere.</param>
        /// <param name="result">When the method completes, contains the newly constructed bounding sphere.</param>
        public static void FromPoints(Span<Vector3> points, out GorgonBoundingSphere result)
        {
            if (points.IsEmpty)
            {
                result = default;
                return;
            }

            //Find the center of all points.
            Vector3 center = Vector3.Zero;
            for (int i = 0; i < points.Length; ++i)
            {
                center = Vector3.Add(points[i], center);
            }

            //This is the center of our sphere.
            center /= points.Length;

            //Find the radius of the sphere
            float radius = 0f;
            for (int i = 0; i < points.Length; ++i)
            {
                //We are doing a relative distance comparison to find the maximum distance
                //from the center of our sphere.
                float distance = Vector3.DistanceSquared(center, points[i]);

                if (distance > radius)
                {
                    radius = distance;
                }
            }

            //Construct the sphere.
            result = new GorgonBoundingSphere(center, radius.Sqrt());
        }

        ///
        /// Constructs a <see cref="GorgonBoundingSphere"/> from a given box.
        ///
        /// <param name="box">The box that will designate the extents of the sphere.</param>
        /// <param name="result">When the method completes, the newly constructed bounding sphere.</param>
        public static void FromBox(in GorgonBoundingBox box, out GorgonBoundingSphere result)
        {
            var center = Vector3.Lerp(box.Minimum, box.Maximum, 0.5f);

            float x = box.Minimum.X - box.Maximum.X;
            float y = box.Minimum.Y - box.Maximum.Y;
            float z = box.Minimum.Z - box.Maximum.Z;

            result = new GorgonBoundingSphere(center, ((x * x) + (y * y) + (z * z)).Sqrt() * 0.5f);
        }

        ///
        /// Constructs a <see cref="GorgonBoundingSphere"/> that is the as large as the total combined area of the two specified spheres.
        ///
        /// <param name="value1">The first sphere to merge.</param>
        /// <param name="value2">The second sphere to merge.</param>
        /// <param name="result">When the method completes, contains the newly constructed bounding sphere.</param>
        public static void Merge(in GorgonBoundingSphere value1, in GorgonBoundingSphere value2, out GorgonBoundingSphere result)
        {
            Vector3 difference = value2.Center - value1.Center;

            float length = difference.Length();
            float radius = value1.Radius;
            float radius2 = value2.Radius;

            if (radius + radius2 >= length)
            {
                if (radius - radius2 >= length)
                {
                    result = value1;
                    return;
                }

                if (radius2 - radius >= length)
                {
                    result = value2;
                    return;
                }
            }

            Vector3 vector = difference * (1.0f / length);
            float min = -radius.Min(length - radius2);
            float max = (radius.Max(length + radius2) - min) * 0.5f;

            result = new GorgonBoundingSphere(value1.Center + vector * (max + min), max);
        }

        ///
        /// Tests for equality between two objects.
        ///
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns><c>true</c> if <paramref name="left"/> has the same value as <paramref name="right"/>; otherwise, <c>false</c>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static bool operator ==(in GorgonBoundingSphere left, in GorgonBoundingSphere right) => left.Equals(in right);

        ///
        /// Tests for inequality between two objects.
        ///
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns><c>true</c> if <paramref name="left"/> has a different value than <paramref name="right"/>; otherwise, <c>false</c>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static bool operator !=(in GorgonBoundingSphere left, in GorgonBoundingSphere right) => !left.Equals(in right);

        ///
        /// Returns a <see cref="string"/> that represents this instance.
        ///
        /// <returns>
        /// A <see cref="string"/> that represents this instance.
        /// </returns>
        public override string ToString() => string.Format(CultureInfo.CurrentCulture, Resources.GOR_TOSTR_BOUNDING_SPHERE, Center.X, Center.Y, Center.Z, Radius);

        ///
        /// Returns a hash code for this instance.
        ///
        /// <returns>
        /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table.
        /// </returns>
        public override int GetHashCode()
        {
            unchecked
            {
                return HashCode.Combine(Center, Radius);
            }
        }

        ///
        /// Determines whether the specified <see cref="Vector4"/> is equal to this instance.
        ///
        /// <param name="value">The <see cref="Vector4"/> to compare with this instance.</param>
        /// <returns>
        /// <c>true</c> if the specified <see cref="Vector4"/> is equal to this instance; otherwise, <c>false</c>.
        /// </returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Equals(GorgonBoundingSphere value) => Equals(in value);

        ///
        /// Determines whether the specified <see cref="object"/> is equal to this instance.
        ///
        /// <param name="value">The <see cref="object"/> to compare with this instance.</param>
        /// <returns>
        /// <c>true</c> if the specified <see cref="object"/> is equal to this instance; otherwise, <c>false</c>.
        /// </returns>
        public override bool Equals(object value) => (value is GorgonBoundingSphere sphere) ? this.Equals(in sphere) : base.Equals(value);

        /// Function to compare this instance with another.
        /// <param name="other">The other instance to use for comparison.</param>
        /// <returns>
        ///   true if equal, false if not.</returns>
        public bool Equals(in GorgonBoundingSphere other) => (Center.Equals(other.Center)) && (Radius == other.Radius);

        /// Deconstructs this instance.
        /// <param name="center">The center of the sphere.</param>
        /// <param name="radius">The radius of the sphere.</param>
        [EditorBrowsable(EditorBrowsableState.Never)]
        public void Deconstruct(out Vector3 center, out float radius)
        {
            center = Center;
            radius = Radius;
        }
        #endregion

        #region Constructor.
        ///
        /// Initializes a new instance of the <see cref="GorgonBoundingSphere"/> struct.
        ///
        /// <param name="center">The center of the sphere in three dimensional space.</param>
        /// <param name="radius">The radius of the sphere.</param>
        public GorgonBoundingSphere(in Vector3 center, float radius)
        {
            Center = center;
            Radius = radius;
        }
        #endregion
    }
}

redpajama_set_name: RedPajamaGithub


New York City Uncovers Singles Gold Mine!
Delicious cuisine, art and history, picturesque drives to sport, shopping and the beach. Regardless of what it takes for you to have a great time, New York has over 8 million individuals for you to find someone to discuss your encounter with.
With that many folks in the city alone, there should be lots of other singles out there looking to spend their twilight years with someone special. Take a look at the hundreds of nightclubs and pubs lining the roads of the city, they provide lots of chances to meet with folks. But if nightclubs and pubs are not your thing then there's always the local comedy club, sit and see the local talent from a fashionable coffee shop in your region, or any amount of restaurants.
Central Park is an excellent area to wander around respecting the buildings and statues, or hang out for some time at the restaurant on the lake and take a look at the other singles. Dog runs are understood to be an excellent way to expand your social group and if it's like-minded individuals you're seeking then you could attempt volunteer groups, social clubs or sports clubs.
if you're now single in the state of New York and Manhattan then it is not a scenario that's to continue long, with everything from speed dating to organized clubs there are tons of chances to meet new people, make friends or even locate that special someone.
Speed Dating is especially popular in the cities. Single professionals have the opportunity to meet with folks in comfortable, everyday scenarios and with tons of routine occasions that are ordered. Occasions are usually aimed at special interests or age groups in New York or Manhattan's top night spots meeting up to a potential 15 dates in 1 night and you may readily wind up!
If the notion of speed dating does not appeal, then how about joining a social club specially for singles? For young professionals, a social club can be perfect it provides a superb chance to make friends as well as understanding that everyone there's the same aims and as everything is arranged for you.
Once you begin trying to find other singles you soon recognize there are lots of folks out there who are searching for the same things as you're. Yet there's a substantial percent of the people that find it hard to locate someone they want to date. This can be because their work schedule is so frenzied that it can be difficult to find time for social occasions or simply from too little assurance.
If this is the situation for you then you should consider one of the free dating websites . New York is said to have more individuals with active online dating accounts than any other city in the nation, and with the variety of dating websites to browse through all preferences are catered to. Online dating is suitable for those who live with less alternative in places and variety of individuals or for those outside in the state in the city with stringent time programs. They could be the perfect method and their services are being already used by thousands of singles.
There are so many advantages to using online dating sites and among the primary ones is that you get the chance to to meet singles in New York and Manhattan who all have precisely the same goal in mind, to find someone worth getting to know and forming a relationship with. In addition, it empowers you to have an excellent look through everybody's profile and have a look at their picture until you feel prepared to initiate contact, once contact is made then you can e-mail for so long as you feel comfortable with, no pressure and you'll be able to go as quickly or as slow as suits you. Singles chat rooms allow you to speak with as many individuals as you are and like an excellent way to locate others with similar interests.
Free dating sites are the perfect method to make new friends and bring some romance into your life. Simple to use, you simply enroll online, key in your zip code and in several minutes you'll get access to a database with hundreds of available singles who reside within a specific radius from you. Do not sit home alone register for free local relationship now and begin hunting for that special someone.