  Neural architecture search (NAS) has become a key component of AutoML and a
standard tool to automate the design of deep neural networks. Recently,
training-free NAS as an emerging paradigm has successfully reduced the search
costs of standard training-based NAS by estimating the true architecture
performance with only training-free metrics. Nevertheless, the estimation
ability of these metrics typically varies across different tasks, making it
challenging to achieve robust and consistently good search performance on
diverse tasks with only a single training-free metric. Meanwhile, the
estimation gap between training-free metrics and the true architecture
performances limits training-free NAS to achieve superior performance. To
address these challenges, we propose the robustifying and boosting
training-free NAS (RoBoT) algorithm which (a) employs the optimized combination
of existing training-free metrics explored from Bayesian optimization to
develop a robust and consistently better-performing metric on diverse tasks,
and (b) applies greedy search, i.e., the exploitation, on the newly developed
metric to bridge the aforementioned gap and consequently to boost the search
performance of standard training-free NAS further. Remarkably, the expected
performance of our RoBoT can be theoretically guaranteed, which improves over
the existing training-free NAS under mild conditions with additional
interesting insights. Our extensive experiments on various NAS benchmark tasks
yield substantial empirical evidence to support our theoretical results.
