# Adaptive Dynamic Search for Multi-Task Learning
## 3 The Proposed Method
### Dynamic Model Search  
The search network discovers multiple model structures instance-wise dynamically by exploring a collection of candidate models in the backbone. For now, we assume that we are searching for a single model for each instance. Suppose that the backbone network has \(r\) ResBlock-M, each of which has \(g\) building blocks. The search network can select nothing (equivalent to layer skipping) for all of the building blocks, providing \((2^{g})^{r}\) candidate models (search space) in the backbone. Given an input instance \(x\), the search network (The model structure, which is simple, is described in Section 4.2) outputs the probability distribution over \(2^{g}\) compositions of \(g\) building blocks in each ResBlock-M. To produce a model, the output of the search network \(S(\cdot;\theta^{s})\) is obtained as follows:  
\[S(x;\theta^{s})=[s_{ij}]\in[0,1]^{2^{g}\times r}, \tag{3}\]  
where \(\theta^{s}\) denotes the set of parameters in the search network. Each column of \([s_{ij}]\) reveals the probabilities of selecting building blocks over \(2^{g}\) candidates in a ResBlock-M (i.e., \(\sum_{i}s_{ij}=1,\forall j\)). Here, \(2^{g}\) is the number of elements in the power set of a residual block containing \(g\) building blocks. From \(S(x;\theta^{s})\), we collect a model structure \(\mathcal{A}\):  
\[\mathcal{A}=[\alpha_{ij}]\in\{0,1\}^{2^{g}\times r}\sim S(x;\theta^{s}). \tag{4}\]  
Here, \(\alpha_{ij}=1\) or \(\alpha_{ij}=0\) indicates whether to select the \(i\)th composition of the building blocks in the \(j\)-th ResBlock-M or not, respectively. The probability of a candidate model for an instance \(x\) is computed as follows:  
\[\pi(\mathcal{A};x)=\prod_{i=1}^{2^{g}}\prod_{j=1}^{r}\ \alpha_{ij}\odot s_{ij}, \tag{5}\]  
where \(\odot\) is the element-wise multiplication operator. One of \((2^{g})^{r}\) candidate models is chosen by the search network when an instance \(x\) is given.  
In the proposed method, the search network enables an instance-wise search by discovering a suitable model for each instance of a task, rather than searching for a single model for each task [17; 26; 29; 30]. This will prevent potential destructive interference not only between tasks but also within tasks. Our method can provide an on-the-fly bespoke solution tailored to each sample.  
In order to perform cost-adaptive predictions for different computational requirements on a per sample basis, the search network explores models for the costs in a single learning procedure. The discovered models will have trade-offs between task accuracy and resource usage (e.g., the number of parameters and FLOPs). This is achieved by simply introducing multiple model structures \(\mathcal{A}^{l}\) and learning multiple regularizers accordingly for the computational costs as described in the following section. This approach could be more efficient than other model search methods [17; 29], as they choose a single model of a trade-off at a time (i.e., one individually trained model for a cost). If another computational cost is required for a device, then the existing methods need to be retrained to explore another trade-off for the budget.  
In addition, we learned a single search network to discover models with respect to the tasks and computational costs, which is universal, unlike introducing multiple search networks (i.e., one search network for a task or a cost). This strategy can naturally supervise all associated tasks at the same time and learn task relationships, producing solutions tailored for each task (see Section 4.3).