# Adaptive Dynamic Search for Multi-Task Learning
## 3 The Proposed Method
### Optimization  
Suppose that a set from dataset \(\mathcal{D}\) consists of data instances from different tasks and their task numbers (i.e., \(\mathcal{D}=\{(x_{t},y_{t})|(x_{t},y_{t})\in\mathcal{D}_{t},\forall t\}\)), where \(x_{t}\) and \(y_{t}\) are the data instance and its label, respectively, from the \(t\)th dataset \(\mathcal{D}_{t}\). The proposed method optimizes the expected loss to learn two sets of parameters, \(\theta^{b}\) and \(\theta^{s}\), for the backbone architecture and the search network, respectively. We define the objective function that contains the loss functions of the selected models with regularization for all instances as follows:  
\[\min_{\theta^{b},\theta^{s}}\ \ \mathbb{E}_{(x_{t},y_{t})\in\mathcal{D}_{t}, \mathcal{A}^{l}\sim S(x_{t};\theta^{s})}\sum_{l=1}^{c}\mathcal{M}^{l}( \mathcal{A}^{l};x_{t},y_{t}), \tag{6}\]  
where \(\mathcal{M}^{l}(\mathcal{A}^{l};x_{t},y_{t})\triangleq\mathcal{L}\Big{(}f(x_ {t};\theta^{b},\mathcal{A}^{l}),y_{t}\Big{)}+\mathcal{R}_{l}(\mathcal{A}^{l})\), \(\mathcal{L}\) denotes a loss function, \(f\) denotes the selected model, \(c\) is the number of different computational budgets, and \(\mathcal{A}^{l}\) is the model structure for the \(l\)th budget selected by the search network by optimizing the following regularization:  
\[\mathcal{R}_{l}(\mathcal{A}^{l})=\lambda_{l}\Bigg{(}\frac{1}{n}\sum_{j=1}^{n} \frac{p_{j}(\mathcal{A}^{l})}{T_{j}}\Bigg{)}^{2}. \tag{7}\]  
Here, \(p_{j}(\mathcal{A}^{l})\) denotes the number of parameters specified by \(\mathcal{A}^{l}\) in the \(j\)th ResBlock-M, \(T_{j}\) denotes the total number of parameters in the \(j\)th ResBlock-M, and \(\lambda_{l}\) is the \(l\)th weighting factor. By optimizing \(c\) different regularizations, the search network is taught to generate \(c\) models (\(\mathcal{A}^{l}\), \(l=1\), \(2\),..., \(c\)) of different computational budgets. In order to optimize Equation (6) with respect to \(\theta^{b}\) and \(\theta^{s}\), we introduce an alternating optimization strategy which alternatively learns \(\theta^{s}\) to optimize the models' losses and the regularizer and learns a set of parameters in \(\theta^{b}\) corresponding to the generated models to improve their task performance. We optimize the parameters in \(\theta^{b}\) specified by the selected model structures from \(\mathcal{A}^{l}(l=1,2,...,c)\) for each instance using a standard gradient descent method. To learn the set of parameters \(\theta^{s}\), we adopt a common approximation strategy in policy gradient methods [38] due to the difficulty of computing the exact expected value in Equation (6) with respect to \(\theta^{s}\). Suppose that \(J(\theta^{s})\) is the objective function with respect to \(\theta^{s}\). By using the log derivative trick on the expected loss with the probability \(\pi\) in Equation (5), we approximate the gradient of \(J(\theta^{s})\) as follows:  
\[\
abla_{\theta^{s}}J(\theta^{s}) \tag{8}\] \[=\mathbb{E}_{(x_{t},y_{t})\in\mathcal{D}}\Bigg{[}\sum_{l=1}^{c} \sum_{\forall,\mathcal{A}^{l}}\hat{\mathcal{M}}^{l}\cdot\
abla_{\theta^{s}} \pi(\mathcal{A}^{l};x_{t})\Bigg{]}\] \[=\mathbb{E}_{(x_{t},y_{t})\in\mathcal{D}}\Bigg{[}\sum_{l=1}^{c} \sum_{\forall,\mathcal{A}^{l}}\hat{\mathcal{M}}^{l}\cdot\pi(\mathcal{A}^{l};x _{t})\frac{\
abla_{\theta^{s}}\pi(\mathcal{A}^{l};x_{t})}{\pi(\mathcal{A}^{l} ;x_{t})}\Bigg{]}\] \[=\mathbb{E}_{(x_{t},y_{t})\in\mathcal{D}_{t}\mathcal{A}^{l}\sim S (x_{t};\theta^{s})}\Bigg{[}\sum_{l=1}^{c}\hat{\mathcal{M}}^{l}\cdot\
abla_{ \theta^{s}}\text{log}\ \pi(\mathcal{A}^{l};x_{t})\Bigg{]}\] \[\approx\mathbb{E}_{(x_{t},y_{t})\in\mathcal{D}}\Bigg{[}\sum_{l=1}^ {c}\sum_{\mathcal{A}^{l}\in\widehat{\mathcal{A}}}\frac{\hat{\mathcal{M}}^{l} }{|\hat{\mathcal{A}}|}\cdot\
abla_{\theta^{s}}\text{log}\ \pi(\mathcal{A}^{l};x_{t})\Bigg{]},\]  
where \(\hat{\mathcal{M}}^{l}\triangleq\mathcal{M}^{l}(\mathcal{A}^{l};x_{t},y_{t})\).