An Approximation Algorithm for Optimal Subarchitecture Extraction

Abstract

We consider the problem of finding the set of architectural parameters for a chosen deep neural network which is optimal under three metrics: parameter size, inference speed, and error rate. In this paper we state the problem formally, and present an approximation algorithm that, for a large subset of instances behaves like an FPTAS with an approximation error of $\rho \le |1-\epsilon |$, and that runs in $O(|\Xi |+|W_T^{\ast }|(1+|\Theta ||B||\Xi |/(\epsilon s^{3/2})))$ steps, where $\epsilon$ and $s$ are input parameters; $|B|$ is the batch size; $|W_T^{\ast }|$ denotes the cardinality of the largest weight set assignment; and $|\Xi |$ and $|\Theta |$ are the cardinalities of the candidate architecture and hyperparameter spaces, respectively.

Preprint. Under review. Original submission does not present the bibliography issues from this version