Scaling Deep Networks with the Mesh Adaptive Direct Search algorithm

The past decade has seen impressive improvements in the deep neural networks (DNNs) domain that facilitated many technological leaps. DNNs are now applied on increasingly complex datasets and are expected to perform intricate tasks with high precision. However, this comes at the cost of building deeper and more complex networks that require substantial computational resources and, therefore, increase human society’s environmental cost. At this stage, searching for new networks has become both essential for technological and scientific advances and expensive enough to prompt more research on how to find small, high-performing networks with a resource-saving mindset.

One possible approach to tackle this issue is to start from a known DNN and reduce its size while losing as few as possible of its original performance. The popular methods to do so are either by pruning, i.e., keeping the initial architecture and removing some of the network’s parameters, or changing the architecture itself through scaling. Low-bit quantization (Courbariaux et al., 2015), or weight sharing (Ullrich et al., 2017), or a combination (Han et al., 2015), are demonstrated to be effective as well in compressing deep networks. While these methods are not necessarily mutually exclusive, pruning methods are more effective when starting from a low-performing network which stresses the importance of finding a new architecture (Blalock et al., 2020). Neural architecture search (NAS) Elsken et al. (2018) seems to be a necessary and costly step in finding a high-performance neural network, especially for low resource and constraint devices.

Let ${\bm{\phi}}$ be the vector of hyperparameters that define a network architecture, $\mathbf{w}$ the neural networks weights and $(\mathbf{x},\mathbf{y})$ the training data features and labels. We note $f({\bm{\phi}},\mathbf{w}\mid\mathbf{x},\mathbf{y})$ the performance measure, such as the validation accuracy, of the network after its training; And $g({\bm{\phi}})$ the function that reflects the resource consumption, an explicit function such as the number of weights $\mathbf{w}$, or an implicit function such latency on a certain edge device.

Performing an architecture search requires defining a judicious, preferably low-dimensional search space with an efficient method to find a vector ${\bm{\phi}}$ with smallest resource $g$, but with maximum performance $f$ whose evaluation is expensive. Two formulations are proposed to solve this optimization problem. Equation (1) poses an unconstrained problem with the goal of finding a solution ${\bm{\phi}}\in\Phi$ that maximizes $f$, where $\Phi$ is the search space limited by the box constraints on the components of ${\bm{\phi}}$. The second formulation of (2) aims at minimizing the resource function $g$ while maintaining a performance higher or equal to a baseline network defined by the architecture ${\bm{\phi}}_{0}$ and weights $\mathbf{w}_{0}$.

Several approaches are proposed to solve the maximization of (1) or the minimization of (2), such as grid search (GS) or random search (RS), evolutionary algorithms, reinforcement learning, Bayesian optimization, etc. These methods managed to improve on the state of the art, yet they often ignore essential properties of these optimization problems. Exploring the search space with non-adaptive approaches such as GS or RS, commonly requires many trials and substantial resources, often depleted on inferior architectures. Similarly, reinforcement learning and evolutionary algorithms need numerous function evaluations before producing quality suggestions. These approaches inherently assume performance evaluation is cheap, which is untrue for training deep networks.

Here we propose the use of derivative-free optimization (DFO) (Audet & Hare, 2017; Conn et al., 2009), and in particular the Mesh Adaptive Direct Search (MADS) algorithm (Audet & Dennis, Jr., 2006) tailored for expensive blackbox functions. In a DFO setting, the objective function has no derivatives, is costly to evaluate, noisy, stochastic, and its evaluation may fail at some points. Blackbox refers to the cases in which the analytical expression for the evaluating function is unknown. In the NAS context, the blackbox $f$ takes the architecture parameter vector ${\bm{\phi}}$ as the input, trains the network on data $(\mathbf{x},\mathbf{y})$, and outputs the validation accuracy.

We present two concrete examples, one where the goal is to compress ResNet-18 on CIFAR-10 by solving the unconstrained problem defined in (1), and the second aims to compress ResNet-50 On ImageNet by optimizing the constrained formulation of (2).

The Mesh Adaptive Direct Search (MADS) algorithm (Audet & Hare, 2017; Audet & Dennis, Jr., 2006) is implemented in the NOMAD C++ solver (Le Digabel, 2011) freely available at www.gerad.ca/nomad.

MADS starts the optimization process with an initial configuration ${\bm{\phi}}_{0}$, an initial mesh size $\Delta_{0}\in\mathbb{R}$ and defines a mesh $M_{k}=\left\{{\bm{\phi}}+\Delta_{k}I_{n}\mathbf{z}:\mathbf{z}\in\mathbb{Z}^{n}\right\}$, at each iteration $k$. Each iteration is made of two steps: the search and the poll. The search is flexible and may include various search space strategies as long as it produces a finite number of trial mesh points at each iteration. This phase usually implements a global search such as Latin hypercube sampling or surrogates which allow to explore further regions. The poll step is rigidly defined so that global convergence to a local optimum is guaranteed under mild conditions. The MADS algorithm generates a set of poll directions that grow asymptotically dense around the incumbent ${\bm{\phi}}_{k}$ to produce a pool of local candidates around ${\bm{\phi}}_{k}$ at a radius of $\delta_{k}$, called the poll size. These candidates are evaluated opportunistically, so the poll stops as soon as a better solution is found and discards the remaining poll points. An improvement on ${\bm{\phi}}_{k}$ is recorded if iteration $k$ is a success, in which case the mesh and poll sizes increase for the next iteration. Otherwise, the mesh and poll size are reduced while maintaining $\Delta_{k}\leq\delta_{k}$ as illustrated in Figure 1.

Following Tan & Le (2019) we define the architecture search over three parameters ${\bm{\phi}}=(\phi_{1},\phi_{2},\phi_{3})$: the network depth $\phi_{1}$, the network width $\phi_{2}$ and the resolution $\phi_{3}$. The depth is searched by adding or removing ResNet blocks. The width is searched by modifying the output channels. The resolution is searched by changing the number of input channels.

The result of these experiments is shown in Figure 2. Starting from the ResNet-18 network that scores $94.5\%$, has $11\times 10^{6}$ parameters and $5.5\times 10^{7}$ MACS; both NOMAD and Microsoft NNI using its Bayesian optimization module TPE (Bergstra et al., 2011) are launched on CIFAR-10 with a budget of $100$ trials each.

NOMAD manages to find over $29$ configurations with a top-1 accuracy over $94\%$, which represents less than $0.35\%$ accuracy drop compared to the baseline. From these top performers, one solution has $4.8\times 10^{7}$ MACS which represents a compression of $12.7\%$ and another solution has $4.7\times 10^{6}$ parameters that is equivalent to a $\times 2.34$ compression compared to the baseline.

TPE-NNI finds $19$ architectures with a top-1 accuracy over $94\%$. From these top performers, the one with lowest number of MACS has $5.4\times 10^{7}$ MACS and the lowest number of parameters is recorded at $8.7\times 10^{6}$ which represents a compression of $23\%$.

A second test is performed where the neural architecture search is expressed with Formulation 2, in which ${\bm{\phi}}_{0}$ is the ResNet-50 architecture and $\mathbf{x},\mathbf{y}$ are the ImageNet training data. This experiment starts from the architecture of ResNet-50 which score a top 1 accuracy of $75.95\%$, has $\sim 25\times 10^{6}$ parameters with $\sim 4\times 10^{9}$ MACS. This time, NOMAD and TPE-NNI are allowed a budget of $25$ trials and the reported results are summarized in Figure 3.

TPE-NNI samples architectures with a high compression factor but at the cost of a significant drop in accuracy as the highest scoring candidate is still $2\%$ less accurate than the given baseline. This particular network has $\sim 17\times 10^{6}$ parameters and $\sim 1.8\times 10^{9}$ MACS. The candidates found by the NOMAD software have smaller compression ratios but maintains a good quality precision. Out of the $25$ sampled points, $15$ score higher than $75\%$ of which $2$ have at least $25\%$ less MACS than ResNet-50, which is a clear improvement compared to NNI with Bayesian optimization routine TPE. Bayesian optimization has been shown successful in attacking blackbox problems effectively and ranked top at blackbox optimization challenge recently (Cowen-Rivers et al., 2020).

Traditionally deep learning community focuses on increasing accuracy on a benchmark data. Rapid use of deep models on edge devices calls for increasing accuracy while keeping resources to the minimal. Despite recent efforts in automating neural architectures, the vast majority of practical cases calls for manual design. Each device has its own constraints and recently developed automation tools ignore the constrained formulation of the problem. We showed the effectiveness of a derivative-free solver in two scenarios, when the search space embeds the constraint and the optimization is treated as an unconstrained problem, which is the common formulation. In a second scenario, we minimized the computational resources while putting a hard constraint on model performance. This formulation is novel and requires solvers that take the constraint into account. Our numerical results show that the derivative-free solver NOMAD beats the popular Bayesian optimization TPE-NNI framework.