Abstract
The design of neural network architectures is frequently either based on human expertise using trial/error and empirical feedback or tackled via large scale reinforcement learning strategies performed over distinct discrete architecture choices. In the latter case, the optimization is often non-differentiable and also not very amenable to derivative-free optimization methods. Most methods in use today require sizable computational resources. And if we want networks that additionally satisfy resource constraints, the above challenges are exacerbated because the search must now balance accuracy with certain budget constraints on resources. We formulate this problem as the optimization of a set function -- we find that the empirical behavior of this set function often (but not always) satisfies marginal gain and monotonicity principles -- properties central to the idea of submodularity. Based on this observation, we adapt algorithms within discrete optimization to obtain heuristic schemes for neural network architecture search, where we have resource constraints on the architecture. This simple scheme when applied on CIFAR-100 and ImageNet, identifies resource-constrained architectures with quantifiably better performance than current state-of-the-art models designed for mobile devices. Specifically, we find high-performing architectures with fewer parameters and computations by a search method that is much faster.
Introduction
Neural Architecture Search (NAS) has revolutionized deep learning by automating the design of high-performance models. However, traditional NAS methods—often relying on Reinforcement Learning (RL) or evolutionary algorithms—are notoriously expensive, sometimes requiring over 3,000 GPU days. Furthermore, deploying models on mobile devices introduces strict resource constraints, such as limited memory and FLOPs. Most NAS methods treat architecture search as a "black-box," making it difficult to optimize directly for hardware limits. This paper introduces Resource Constrained Architecture Search (RCAS), a method that treats neural network design as a submodular optimization problem to find efficient, high-performing architectures without massive computational overhead.
Methodology: Exploiting Submodularity
The core innovation of RCAS is viewing the architecture as a set of functional blocks and the resulting accuracy as a set function.
- The Submodularity Assumption: The authors observe that adding a new layer to a small, simple network usually provides a larger accuracy boost than adding that same layer to a large, complex network. This "diminishing returns" property is known as submodularity.
- Cost-Effective Greedy (CEG) Search: Instead of an exhaustive search, the algorithm starts with an empty "skeleton" and greedily adds the block offering the highest ratio of accuracy gain to resource cost (parameters or MAdds).
- Lazy Evaluation: To accelerate the process, they use a "lazy" greedy approach. Because of the submodularity assumption, the marginal gain of a block can only decrease as the network grows. This allows the algorithm to skip re-evaluating many blocks, significantly reducing training requirements.
- Early Stopping: During the search phase, models are not trained to full convergence. A proxy of just 10 epochs is used to estimate a block's potential, which is sufficient to guide the greedy selection.
Experimental Results and Performance
The approach was evaluated on CIFAR-100 and ImageNet. The search process often selected a diverse mix of block types, which proved key to balancing the accuracy-efficiency trade-off.
Search Efficiency
RCAS found high-performing models remarkably fast: just 2 GPU days for CIFAR-100 and 8-9 GPU days for ImageNet. This is orders of magnitude faster than typical RL-based approaches.
Performance Comparison
On CIFAR-100, the discovered RCNet achieved 76.1% Top-1 accuracy with only 1.92M parameters, outperforming DARTS (75.9% with 3.4M parameters) while being significantly smaller. On ImageNet, RCNet-B achieved 74.7% Top-1 accuracy, matching MnasNet-92 but with a much faster search time.
Mobile Deployment
Practical utility was confirmed on an iPhone 5s, where RCNet showed inference latencies (183.5 ms) comparable to or better than MobileNetV2 (197.2 ms), proving its suitability for edge devices.
Discussion and Future Work
While neural network accuracy isn't mathematically guaranteed to be submodular, empirical evidence shows it behaves enough like one that greedy algorithms work remarkably well. The "Lazy" update is the critical component, avoiding thousands of unnecessary training runs by maintaining a priority queue of blocks.
Currently, the method assumes a fixed "skeleton" and searches for block types. Future work could apply submodularity to search for the network's wiring or topology itself. Additionally, while MAdds and parameter counts are good proxies, future iterations could incorporate direct hardware latency measurements into the cost function for even better device-specific optimization.
Summary updated