Searching for the architecture cells is a dominant paradigm in NAS. However, little attention has been devoted to the analysis of the cell-based search spaces even though it is highly important for the continual development of NAS. In this work, we conduct an empirical post-hoc analysis of architectures from the popular cell-based search spaces and find that the existing search spaces contain a high degree of redundancy: the architecture performance is minimally sensitive to changes at large parts of the cells, and universally adopted designs, like the explicit search for a reduction cell, significantly increase the complexities but have very limited impact on the performance. Across architectures found by a diverse set of search strategies, we consistently find that the parts of the cells that do matter for architecture performance often follow similar and simple patterns. By explicitly constraining cells to include these patterns, randomly sampled architectures can match or even outperform the state of the art. These findings cast doubts into our ability to discover truly novel architectures in the existing cell-based search spaces, and inspire our suggestions for improvement to guide future NAS research. Code is available at https://github.com/xingchenwan/cell-based-NAS-analysis.

Deep learning inference is often outsourced to external cloud services to mitigate the high cost of executing state-of-theart deep networks on user devices [1]. However, outsourced inference raises essential concerns about data and model privacy: users may not trust a cloud service provider with their data, and cloud service providers may not want to share their models, trained at enormous expense, with users. Private inference (PI) provides a solution to this problem by guaranteeing user and model privacy using cryptographic techniques [2, 3]. Under PI, a user can perform inference using a model hosted in the cloud without the cloud learning anything about her data and, conversely, without the user learning anything about the cloud's model parameters. PI techniques thus far reported in the literature have leveraged a range of cryptographic protocols, including homomorphic encryption (HE), additive secret sharing (SS), and garbled circuits (GC). However, these all incur heavy computational overheads, resulting in several orders-of-magnitude increase in inference latency compared to standard "plaintext" inference. Prior work has demonstrated that non-linear network operations like the Rectified Linear Unit (ReLU) and max-pooling are the key bottlenecks. For example, Ghodsi et al. [4] estimate that ReLU layers in MiniONN [5] are four orders of magnitude more expensive than convolution layers, while in D