  In this paper, we study two important problems in the automated design of
neural networks -- Hyper-parameter Optimization (HPO), and Neural Architecture
Search (NAS) -- through the lens of sparse recovery methods. In the first part
of this paper, we establish a novel connection between HPO and structured
sparse recovery. In particular, we show that a special encoding of the
hyperparameter space enables a natural group-sparse recovery formulation, which
when coupled with HyperBand (a multi-armed bandit strategy), leads to
improvement over existing hyperparameter optimization methods. Experimental
results on image datasets such as CIFAR-10 confirm the benefits of our
approach. In the second part of this paper, we establish a connection between
NAS and structured sparse recovery. Building upon ``one-shot'' approaches in
NAS, we propose a novel algorithm that we call CoNAS by merging ideas from
one-shot approaches with a techniques for learning low-degree sparse Boolean
polynomials. We provide theoretical analysis on the number of validation error
measurements. Finally, we validate our approach on several datasets and
discover novel architectures hitherto unreported, achieving competitive (or
better) results in both performance and search time compared to the existing
NAS approaches.
