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
Designing neural networks for mobile devices requires a delicate balance between maximizing accuracy and adhering to strict hardware constraints, such as memory (parameter count) and battery/latency (FLOPs or Multiply-Adds). Traditional Neural Architecture Search (NAS) often treats this as a "black-box" problem, utilizing Reinforcement Learning (RL) or evolutionary algorithms to explore thousands of architectures. This approach is computationally prohibitive, sometimes requiring over 3,000 GPU days. Furthermore, many NAS methods do not directly optimize for specific hardware budgets, necessitating a separate compression step post-search.
Methodology: Submodularity in Architecture Search
The proposed Resource Constrained Architecture Search (RCAS) moves away from black-box search by viewing a neural network as a collection of "primitive blocks." The search is formulated as the optimization of a set function: selecting a subset of blocks that maximizes accuracy within a resource budget.
The Submodularity Assumption
A key observation is that neural networks often exhibit "diminishing returns." Adding a high-quality block to a small, simple network typically yields a greater accuracy improvement than adding the same block to a larger, more complex network. This property, known as submodularity, allows for the application of efficient discrete optimization tools.
Search Algorithms
- Cost-Effective Greedy (CEG) Algorithm: Instead of selecting the block with the highest absolute accuracy boost, the algorithm prioritizes the block with the best accuracy-to-cost ratio.
- Lazy Evaluation: Leveraging the submodularity assumption, the algorithm maintains a priority queue and only re-calculates the "marginal gain" for top candidates, significantly accelerating the search.
- Early Stopping: Candidate models are trained for only 10 epochs during the search phase. This proxy performance is sufficient to rank blocks effectively without full convergence.
Experimental Results
The researchers evaluated RCAS on CIFAR-100 and ImageNet, with real-world latency tests on an iPhone 5s.
Search Efficiency and Performance
RCAS identified an optimal architecture on CIFAR-100 in just 2 GPU days, a massive reduction compared to the 1,800 days required for NASNet-A. The resulting model, RCNet, achieved 76.1% top-1 accuracy on CIFAR-100 with only 1.92M parameters—outperforming DARTS while using approximately 44% fewer parameters and 50% fewer Multiply-Adds (MAdds).
On ImageNet, RCNet-B achieved 74.7% top-1 accuracy, matching the state-of-the-art MNasNet-92 while utilizing fewer computational resources. When deployed on an iPhone 5s, RCNet demonstrated lower inference latency (183.5 ms) than MobileNetV2 (197.2 ms) for a similar model size.
Discussion and Conclusion
The success of RCAS suggests that NAS possesses a hidden structure following principles of marginal gain. By incorporating cost directly into the selection step, the search naturally favors efficient architectures. Furthermore, the search revealed that diversity in block types (e.g., varying expansion ratios) is superior to repeating a single "optimal" block.
While neural networks behave like submodular functions in practice, they are not strictly submodular in a mathematical sense. Future work could explore applying these principles to search for network topology itself or incorporating direct hardware-in-the-loop measurements to better capture latency nuances across different processors.
Summary updated