Weight-sharing—the simultaneous optimization of multiple neural networks using the same parameters—has emerged as a key component of state-of-the-art neural architecture search. However, its success is poorly understood and often found to be surprising. We argue that, rather than just being an optimization trick, the weight-sharing approach is induced by the relaxation of a structured hypothesis space, and introduces new algorithmic and theoretical challenges as well as applications beyond neural architecture search. Algorithmically, we show how the geometry of ERM for weight-sharing requires greater care when designing gradient- based minimization methods and apply tools from non-convex non-Euclidean optimization to give general-purpose algorithms that adapt to the underlying structure. We further analyze the learning-theoretic behavior of the bilevel optimization solved by practical weight-sharing methods. Next, using kernel configuration and NLP feature selection as case studies, we demonstrate how weight-sharing applies to the architecture search generalization of NAS and effectively optimizes the resulting bilevel objective. Finally, we use our optimization analysis to develop a simple exponentiated gradient method for NAS that aligns with the underlying optimization geometry and matches state-of-the-art approaches on CIFAR-10. Weight-sharing neural architecture search (NAS) methods have achieved state-of-the-art performance while requiring computation training of just a single shared-weights network (Pham et al., 2018; Li and Talwalkar, 2019; . However, weight-sharing remains poorly understood. In this work, we present a novel perspective on weight-sharing NAS motivated by the key observation that these methods subsume the architecture hyperparameters as another set of learned parameters of the shared-weights network, in effect extending the hypothesis class. An important ramification of this insight is that weight-sharing is not NAS-specific and can be used to tune hyperparameters corresponding to parameterized feature maps of the input data. We refer this larger subset of hyperparameter optimization problems as architecture search, and we study the following two questions associated with weight-sharing applied to the architecture search problem: 1. How can we efficiently optimize the objective induced by applying weight sharing to architecture search, namely minimizing empirical risk in the joint space of model and architecture parameters? For large structured search spaces that preclude brute force search, a natural approach to architecture search with weight-sharing is to use gradient-based methods to minimize the empirical risk over a continuous relaxation of the discrete space . Although this has allowed NAS researchers to apply their preferred optimizers to determine architecture weights, it is far from clear that the success of established methods for unconstrained optimization in training neural networks will naturally extend to these constrained and often non-Euclidean environments. As we foresee that architecture search spaces will continue to become more complex and multi-faceted, we argue for and develop a more principled, geometry-aware formulation of the optimization problem. Drawing upon the mirror descent meta-algorithm (Beck and Teboulle, 2003) and successive convex approximation, we give non-asymptotic stationary-point convergence guarantees for the empirical risk minimization (ERM) objective associated with weight-sharing via algorithms that simultaneously connect to the underlying problem structure and handle the alternating-block nature of the architecture search. Our guarantees inform the design of gradient-based weight-sharing methods by explicitly quantifying the impact of optimizing in the right geometry on convergence rates. 2. What are the generalization benefits of solving a bilevel optimization for the architecture search problem commonly considered in practice? At its core, the goal of architecture search is to find a configuration that achieves good generalization performance. Consequently, a bilevel objective that optimizes the architecture weights using a separate validation loss is commonly used in practice in lieu of the ERM objective naturally induced by weight sharing (Pham et al., 2018; Cai et al., 2019) . The learning aspects of this approach have generally been studied in settings with much stronger control over the model complexity (Kearns et al., 1997) . We provide generalization guarantees for this objective over structured hypothesis spaces associated with a finite set of architectures; this leads to meaningful bounds for simple feature map selection problems as well as insightful results for the NAS problem that depend on the size of the space of global optima. To validate our theoretical results, we conduct empirical studies of weight-sharing in two settings: (1) shallow feature map selection, i.e., tuning the hyperparameters of kernel classification and NLP featurization pipelines, and (2) CNN neural architecture search. In (1) we demonstrate that weightsharing efficiently optimizes the bilevel objective and achieves low generalization error with respect to the best architecture setting. For (2), motivated by insights from our convergence analysis, we develop a simple exponentiated gradient version of DARTS called EDARTS that better exploits the geometry of the optimization problem. We evaluate EDARTS on the design of CNN architectures for CIFAR-10 and demonstrate that EDARTS finds better architectures than DARTS in less than half the time. We also achieve very competitive results relative to state-of-the-art architectures when using an extended evaluation routine. Related Work: Our work on optimization for weight-sharing benefits from the literature on firstorder stochastic optimization (Hazan and Kale, 2014; Beck, 2017) and in particular the mirror descent framework (Beck and Teboulle, 2003) . Specifically, we use successive convex approximation (Razaviyayn et al., 2013; Mairal, 2015) to show convergence of alternating minimization and derive geometry-dependent rates comparable to existing work on non-convex stochastic mirror descent (Dang and Lan, 2015; Zhang and He, 2018) . Our result generalizes to the constrained, nonEuclidean, and multi-block setting an approach of Agarwal et al. (2019) for obtaining non-convex convergence from strongly convex minimization, which may be of independent interest. Previous optimization results for NAS have generally only shown bounds on auxiliary quantities such as regret that are not well-connected to the learning objective Carlucci et al., 2019) or have only given monotonic improvement or asymptotic guarantees (Akimoto et al., 2019; Yao et al., 2019) . However, due to the generality of mirror descent, the approaches in the middle three papers can be seen as special cases of our analysis. Finally, our analysis of the properties of the bilevel optimization is related to work on model selection (Vuong, 1989; Kearns et al., 1997) , but does not consider the configuration parameters as explicit controls on the model complexity. Our learning results are broadly related to hyperparameter optimization, although most work focuses on algorithmic and not statistical questions (Li et al., 2018; Kandasamy et al., 2017) .
An analysis of the learning and optimization structures of architecture search in neural networks and beyond.
{"src": "scitldr-AIC_train", "paper_id": "HJgRCyHFDr"}